31#include "llvm/Config/llvm-config.h"
46#define DEBUG_TYPE "regalloc"
50 cl::desc(
"Enable loop iv regalloc heuristic"),
54STATISTIC(NumSimple,
"Number of splits that were simple");
55STATISTIC(NumCopies,
"Number of copies inserted for splitting");
56STATISTIC(NumRemats,
"Number of rematerialized defs for splitting");
64 : LIS(lis), LastInsertPoint(BBNum) {}
67InsertPointAnalysis::computeLastInsertPoint(
const LiveInterval &CurLI,
70 std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
74 bool EHPadSuccessor =
false;
76 if (SMBB->isEHPad()) {
78 EHPadSuccessor =
true;
79 }
else if (SMBB->isInlineAsmBrIndirectTarget())
85 if (!LIP.first.isValid()) {
87 if (FirstTerm ==
MBB.
end())
98 if (ExceptionalSuccessors.
empty())
101 if ((EHPadSuccessor &&
MI.isCall()) ||
102 MI.getOpcode() == TargetOpcode::INLINEASM_BR) {
128 if (
I->getOpcode() == TargetOpcode::STATEPOINT)
157 : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis),
Loops(mli),
158 TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
163 ThroughBlocks.
clear();
168void SplitAnalysis::analyzeUses() {
169 assert(UseSlots.empty() &&
"Call clear first");
175 UseSlots.push_back(VNI->
def);
187 UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
194 LLVM_DEBUG(
dbgs() <<
"Analyze counted " << UseSlots.size() <<
" instrs in "
195 << UseBlocks.size() <<
" blocks, through "
196 << NumThroughBlocks <<
" blocks.\n");
201void SplitAnalysis::calcLiveBlockInfo() {
203 NumThroughBlocks = NumGapBlocks = 0;
211 UseI = UseSlots.begin();
212 UseE = UseSlots.end();
226 if (UseI == UseE || *UseI >= Stop) {
228 ThroughBlocks.
set(BI.MBB->getNumber());
231 assert(LVI->end >= Stop &&
"range ends mid block with no uses");
234 BI.FirstInstr = *UseI;
235 assert(BI.FirstInstr >= Start);
237 while (UseI != UseE && *UseI < Stop);
238 BI.LastInstr = UseI[-1];
239 assert(BI.LastInstr < Stop);
242 BI.LiveIn = LVI->start <= Start;
246 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
247 assert(LVI->start == BI.FirstInstr &&
"First instr should be a def");
248 BI.FirstDef = BI.FirstInstr;
253 while (LVI->end < Stop) {
255 if (++LVI == LVE || LVI->start >= Stop) {
257 BI.LastInstr = LastStop;
261 if (LastStop < LVI->start) {
268 UseBlocks.push_back(BI);
269 UseBlocks.back().LastInstr = LastStop;
274 BI.FirstInstr = BI.FirstDef = LVI->start;
278 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
280 BI.FirstDef = LVI->start;
283 UseBlocks.push_back(BI);
291 if (LVI->end == Stop && ++LVI == LVE)
295 if (LVI->start < Stop)
302 any_of(UseBlocks, [
this](BlockInfo &BI) {
304 return BI.LiveIn && BI.LiveOut && BI.FirstDef && L &&
305 L->isLoopLatch(BI.MBB);
331 }
while (Stop <= LVI->start);
338 assert(!Orig.
empty() &&
"Splitting empty interval?");
342 if (
I != Orig.
end() &&
I->start <=
Idx)
343 return I->start ==
Idx;
346 return I != Orig.
begin() && (--
I)->end ==
Idx;
363 : SA(SA), LIS(LIS), VRM(VRM),
MRI(VRM.getMachineFunction().getRegInfo()),
364 MDT(MDT),
TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),
365 TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),
366 MBFI(MBFI), VRAI(VRAI), RegAssign(
Allocator) {}
385#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
387 if (RegAssign.
empty()) {
388 dbgs() <<
" empty\n";
393 dbgs() <<
" [" <<
I.start() <<
';' <<
I.stop() <<
"):" <<
I.value();
403 for (
auto &S : LI.subranges())
404 if (S.LaneMask == LM)
426 if ((S.LaneMask & LM) == LM)
444 VNInfo *PV = PS.getVNInfoAt(Def);
445 if (PV !=
nullptr && PV->
def == Def)
459 if (
unsigned SR = DefOp.getSubReg())
462 LM =
MRI.getMaxLaneMaskForVReg(R);
467 if ((S.LaneMask & LM).any())
472VNInfo *SplitEditor::defValue(
unsigned RegIdx,
476 assert(ParentVNI &&
"Mapping NULL value");
477 assert(
Idx.isValid() &&
"Invalid SlotIndex");
485 ValueForcePair
FP(Force ?
nullptr : VNI, Force);
487 std::pair<ValueMap::iterator, bool> InsP =
488 Values.
insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->
id),
FP));
492 if (!Force && InsP.second)
496 if (
VNInfo *OldVNI = InsP.first->second.getPointer()) {
497 addDeadDef(*LI, OldVNI, Original);
501 InsP.first->second = ValueForcePair(
nullptr, Force);
505 addDeadDef(*LI, VNI, Original);
509void SplitEditor::forceRecompute(
unsigned RegIdx,
const VNInfo &ParentVNI) {
510 ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.
id)];
511 VNInfo *VNI = VFP.getPointer();
525 VFP = ValueForcePair(
nullptr,
true);
528SlotIndex SplitEditor::buildSingleSubRegCopy(
532 bool FirstCopy = !
Def.isValid();
536 .
addReg(FromReg, 0, SubIdx);
553 if (LaneMask.
all() || LaneMask ==
MRI.getMaxLaneMaskForVReg(FromReg)) {
568 assert(RC ==
MRI.getRegClass(ToReg) &&
"Should have same reg class");
577 for (
unsigned BestIdx : SubIndexes) {
578 Def = buildSingleSubRegCopy(FromReg, ToReg,
MBB, InsertBefore, BestIdx,
579 DestLI, Late, Def,
Desc);
593VNInfo *SplitEditor::defFromParent(
unsigned RegIdx,
const VNInfo *ParentVNI,
601 bool Late = RegIdx != 0;
609 bool DidRemat =
false;
624 if (S.liveAt(UseIdx))
625 LaneMask |= S.LaneMask;
631 if (LaneMask.
none()) {
638 Def = buildCopy(Edit->
getReg(), Reg, LaneMask,
MBB,
I, Late, RegIdx);
643 return defValue(RegIdx, ParentVNI, Def,
false);
653 OpenIdx = Edit->
size();
659 assert(
Idx != 0 &&
"Cannot select the complement interval");
660 assert(Idx < Edit->
size() &&
"Can only select previously opened interval");
666 assert(OpenIdx &&
"openIntv not called before enterIntvBefore");
676 assert(
MI &&
"enterIntvBefore called with invalid index");
678 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI,
Idx, *
MI->getParent(),
MI);
683 assert(OpenIdx &&
"openIntv not called before enterIntvAfter");
685 Idx =
Idx.getBoundaryIndex();
693 assert(
MI &&
"enterIntvAfter called with invalid index");
695 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI,
Idx, *
MI->getParent(),
701 assert(OpenIdx &&
"openIntv not called before enterIntvAtEnd");
742 assert(OpenIdx &&
"openIntv not called before useIntv");
749 assert(OpenIdx &&
"openIntv not called before leaveIntvAfter");
761 assert(
MI &&
"No instruction at index");
768 MI->readsVirtualRegister(Edit->
getReg())) {
769 forceRecompute(0, *ParentVNI);
770 defFromParent(0, ParentVNI,
Idx, *
MI->getParent(),
MI);
774 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *
MI->getParent(),
780 assert(OpenIdx &&
"openIntv not called before leaveIntvBefore");
788 return Idx.getNextSlot();
793 assert(
MI &&
"No instruction at index");
794 VNInfo *VNI = defFromParent(0, ParentVNI,
Idx, *
MI->getParent(),
MI);
799 assert(OpenIdx &&
"openIntv not called before leaveIntvAtTop");
812 VNInfo *VNI = defFromParent(RegIdx, ParentVNI, Start,
MBB,
814 RegAssign.
insert(Start, VNI->
def, OpenIdx);
821 return MO.isReg() && MO.isTied() && MO.getReg() == Reg;
826 assert(OpenIdx &&
"openIntv not called before overlapIntv");
829 "Parent changes value in extended range");
831 "Range cannot span basic blocks");
835 forceRecompute(0, *ParentVNI);
859 AssignI.setMap(RegAssign);
864 assert(
MI &&
"No instruction for back-copy");
870 while (!AtBegin && (--
MBBI)->isDebugOrPseudoInstr());
875 MI->eraseFromParent();
879 AssignI.find(Def.getPrevSlot());
880 if (!AssignI.valid() || AssignI.start() >= Def)
883 if (AssignI.stop() != Def)
885 unsigned RegIdx = AssignI.value();
891 AtBegin ?
SlotIndex() : LIS.getInstructionIndex(*
MBBI).getRegSlot();
892 if (AtBegin || !
MBBI->readsVirtualRegister(Edit->
getReg()) ||
893 Kill <= AssignI.start()) {
894 LLVM_DEBUG(
dbgs() <<
" cannot find simple kill of RegIdx " << RegIdx
899 AssignI.setStop(Kill);
917 unsigned BestDepth = std::numeric_limits<unsigned>::max();
932 if (
Loop == DefLoop) {
935 <<
" in the same loop\n");
941 if (
Depth < BestDepth) {
946 <<
" at depth " <<
Depth <<
'\n');
954 if (!IDom || !MDT.
dominates(DefDomNode, IDom))
961void SplitEditor::computeRedundantBackCopies(
973 EqualVNs[ParentVNI->
id].insert(VNI);
978 for (
unsigned i = 0, e = Parent->
getNumValNums(); i != e; ++i) {
980 if (!NotToHoistSet.
count(ParentVNI->
id))
984 for (; It1 != EqualVNs[ParentVNI->
id].end(); ++It1) {
986 for (++It2; It2 != EqualVNs[ParentVNI->
id].end(); ++It2) {
987 if (DominatedVNIs.
count(*It1) || DominatedVNIs.
count(*It2))
993 DominatedVNIs.
insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
995 DominatedVNIs.
insert(*It2);
997 DominatedVNIs.
insert(*It1);
1001 if (!DominatedVNIs.
empty()) {
1002 forceRecompute(0, *ParentVNI);
1004 DominatedVNIs.
clear();
1014void SplitEditor::hoistCopies() {
1021 using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1035 assert(ParentVNI &&
"Parent not live at complement def");
1044 DomPair &Dom = NearestDom[ParentVNI->
id];
1049 if (VNI->
def == ParentVNI->
def) {
1051 Dom = DomPair(ValMBB, VNI->
def);
1056 if (Values.
lookup(std::make_pair(0, ParentVNI->
id)).getPointer()) {
1063 Dom = DomPair(ValMBB, VNI->
def);
1064 }
else if (Dom.first == ValMBB) {
1066 if (!Dom.second.isValid() || VNI->
def < Dom.second)
1067 Dom.second = VNI->
def;
1074 Dom = DomPair(ValMBB, VNI->
def);
1075 else if (Near != Dom.first)
1082 << VNI->
def <<
" for parent " << ParentVNI->
id <<
'@'
1083 << ParentVNI->
def <<
" hoist to "
1089 for (
unsigned i = 0, e = Parent->
getNumValNums(); i != e; ++i) {
1090 DomPair &Dom = NearestDom[i];
1091 if (!Dom.first || Dom.second.isValid())
1097 Dom.first = findShallowDominator(Dom.first, DefMBB);
1100 NotToHoistSet.
insert(ParentVNI->
id);
1104 if (LSP <= ParentVNI->def) {
1105 NotToHoistSet.
insert(ParentVNI->
id);
1108 Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first,
1119 const DomPair &Dom = NearestDom[ParentVNI->
id];
1120 if (!Dom.first || Dom.second == VNI->
def ||
1121 NotToHoistSet.
count(ParentVNI->
id))
1124 forceRecompute(0, *ParentVNI);
1130 computeRedundantBackCopies(NotToHoistSet, BackCopies);
1132 removeBackCopies(BackCopies);
1137bool SplitEditor::transferValues() {
1138 bool Skipped =
false;
1142 VNInfo *ParentVNI = S.valno;
1145 AssignI.advanceTo(Start);
1149 if (!AssignI.valid()) {
1151 }
else if (AssignI.start() <= Start) {
1152 RegIdx = AssignI.value();
1153 if (AssignI.stop() <
End) {
1154 End = AssignI.stop();
1159 End = std::min(
End, AssignI.start());
1168 ValueForcePair VFP = Values.
lookup(std::make_pair(RegIdx, ParentVNI->
id));
1169 if (
VNInfo *VNI = VFP.getPointer()) {
1194 if (Start != BlockStart) {
1196 assert(VNI &&
"Missing def for complex mapped value");
1199 if (BlockEnd <=
End)
1204 BlockStart = BlockEnd;
1208 assert(Start <= BlockStart &&
"Expected live-in block");
1209 while (BlockStart <
End) {
1212 if (BlockStart == ParentVNI->
def) {
1214 assert(ParentVNI->
isPHIDef() &&
"Non-phi defined at block start?");
1216 assert(VNI &&
"Missing def for complex mapped parent PHI");
1217 if (
End >= BlockEnd)
1230 BlockStart = BlockEnd;
1234 }
while (Start != S.end);
1249 if (Seg->
end != Def.getDeadSlot())
1274void SplitEditor::extendPHIKillRanges() {
1283 if (
V->isUnused() || !
V->isPHIDef())
1286 unsigned RegIdx = RegAssign.
lookup(
V->def);
1298 for (
const VNInfo *V : PS.valnos) {
1299 if (
V->isUnused() || !
V->isPHIDef())
1301 unsigned RegIdx = RegAssign.
lookup(
V->def);
1312 extendPHIRange(
B, SubLIC, S, PS.LaneMask, Undefs);
1318void SplitEditor::rewriteAssigned(
bool ExtendRanges) {
1321 : MO(
O), RegIdx(
R), Next(
N) {}
1334 if (
MI->isDebugValue()) {
1344 if (MO.isDef() || MO.isUndef())
1345 Idx =
Idx.getRegSlot(MO.isEarlyClobber());
1348 unsigned RegIdx = RegAssign.
lookup(
Idx);
1350 MO.setReg(LI.
reg());
1352 <<
'\t' <<
Idx <<
':' << RegIdx <<
'\t' << *
MI);
1355 if (!ExtendRanges || MO.isUndef())
1360 if (!MO.getSubReg() && !MO.isEarlyClobber())
1368 bool IsEarlyClobber =
false;
1382 unsigned OpIdx = MO.getOperandNo();
1383 unsigned DefOpIdx =
MI->findTiedOperandIdx(OpIdx);
1388 Idx =
Idx.getRegSlot(IsEarlyClobber);
1398 ExtPoints.
push_back(ExtPoint(MO, RegIdx, Next));
1405 for (ExtPoint &EP : ExtPoints) {
1410 Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1412 :
MRI.getMaxLaneMaskForVReg(Reg);
1427 SubLIC.
extend(S, EP.Next, 0, Undefs);
1441void SplitEditor::deleteRematVictims() {
1452 assert(
MI &&
"Missing instruction for dead def");
1453 MI->addRegisterDead(LI->
reg(), &TRI);
1455 if (!
MI->allDefsAreDead())
1466 Edit->eliminateDeadDefs(Dead, std::nullopt);
1469void SplitEditor::forceRecomputeVNI(
const VNInfo &ParentVNI) {
1472 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1473 forceRecompute(
I, ParentVNI);
1480 Visited.
insert(&ParentVNI);
1488 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1489 forceRecompute(
I, VNI);
1497 assert(PredVNI &&
"Value available in PhiVNI predecessor");
1498 if (Visited.
insert(PredVNI).second)
1501 }
while(!WorkList.
empty());
1511 for (
const VNInfo *ParentVNI : Edit->getParent().valnos) {
1514 unsigned RegIdx = RegAssign.
lookup(ParentVNI->
def);
1515 defValue(RegIdx, ParentVNI, ParentVNI->
def,
true);
1519 if (Edit->didRematerialize(ParentVNI))
1520 forceRecomputeVNI(*ParentVNI);
1524 switch (SpillMode) {
1535 bool Skipped = transferValues();
1538 rewriteAssigned(Skipped);
1541 extendPHIKillRanges();
1547 deleteRematVictims();
1558 auto Seq = llvm::seq<unsigned>(0, Edit->size());
1559 LRMap->
assign(Seq.begin(), Seq.end());
1564 for (
unsigned i = 0, e = Edit->size(); i != e; ++i) {
1576 LRMap->
resize(Edit->size(), i);
1582 assert(!LRMap || LRMap->
size() == Edit->size());
1590 bool SingleInstrs)
const {
1637 unsigned IntvOut,
SlotIndex EnterAfter){
1641 LLVM_DEBUG(
dbgs() <<
"%bb." << MBBNum <<
" [" << Start <<
';' << Stop
1642 <<
") intf " << LeaveBefore <<
'-' << EnterAfter
1643 <<
", live-through " << IntvIn <<
" -> " << IntvOut);
1645 assert((IntvIn || IntvOut) &&
"Use splitSingleBlock for isolated blocks");
1647 assert((!LeaveBefore || LeaveBefore < Stop) &&
"Interference after block");
1648 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) &&
"Impossible intf");
1649 assert((!EnterAfter || EnterAfter >= Start) &&
"Interference before block");
1662 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1676 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1681 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1694 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) &&
"Impossible intf");
1696 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1706 if (LeaveBefore && LeaveBefore < LSP) {
1714 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1715 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1725 assert(LeaveBefore <= EnterAfter &&
"Missed case");
1730 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1735 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1739 unsigned IntvIn,
SlotIndex LeaveBefore) {
1744 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1745 << BI.
LastInstr <<
", reg-in " << IntvIn
1746 <<
", leave before " << LeaveBefore
1747 << (BI.
LiveOut ?
", stack-out" :
", killed in block"));
1749 assert(IntvIn &&
"Must have register in");
1751 assert((!LeaveBefore || LeaveBefore > Start) &&
"Bad interference");
1779 LLVM_DEBUG(
dbgs() <<
", spill after last use before interference.\n");
1783 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1790 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1800 LLVM_DEBUG(
dbgs() <<
", creating local interval " << LocalIntv <<
".\n");
1813 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1828 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1832 unsigned IntvOut,
SlotIndex EnterAfter) {
1837 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1838 << BI.
LastInstr <<
", reg-out " << IntvOut
1839 <<
", enter after " << EnterAfter
1840 << (BI.
LiveIn ?
", stack-in" :
", defined in block"));
1844 assert(IntvOut &&
"Must have register out");
1846 assert((!EnterAfter || EnterAfter < LSP) &&
"Bad interference");
1870 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1886 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1897 << (
LiveIn ?
"live in" :
"dead in") <<
", "
1898 << (
LiveOut ?
"live out" :
"dead out") <<
"}";
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock MachineBasicBlock::iterator MBBI
This file defines the BumpPtrAllocator interface.
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LiveInterval::SubRange & getSubRangeForMaskExact(LaneBitmask LM, LiveInterval &LI)
static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg)
static bool removeDeadSegment(SlotIndex Def, LiveRange &LR)
auto & getSubrangeImpl(LaneBitmask LM, T &LI)
Find a subrange corresponding to the exact lane mask LM in the live interval LI.
const LiveInterval::SubRange & getSubRangeForMask(LaneBitmask LM, const LiveInterval &LI)
Find a subrange corresponding to the lane mask LM, or a superset of it, in the live interval LI.
static cl::opt< bool > EnableLoopIVHeuristic("enable-split-loopiv-heuristic", cl::desc("Enable loop iv regalloc heuristic"), cl::init(true))
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clear()
clear - Removes all bits from the bitvector.
Allocate memory in an ever growing pool, as if by bump-pointer.
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
Base class for the actual dominator tree node.
MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, MachineBasicBlock &MBB)
Returns the last insert point as an iterator for \pCurLI in \pMBB.
SlotIndex getLastInsertPoint(const LiveInterval &CurLI, const MachineBasicBlock &MBB)
Return the base index of the last valid insert point for \pCurLI in \pMBB.
InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum)
const_iterator begin() const
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
ValT lookup(KeyT x, ValT NotFound=ValT()) const
lookup - Return the mapped value at x or NotFound.
friend class const_iterator
bool empty() const
empty - Return true when no intervals are mapped.
void clear()
clear - Remove all entries.
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
bool hasSubRanges() const
Returns true if subregister liveness information is available.
iterator_range< subrange_iterator > subranges()
void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
SlotIndexes * getSlotIndexes() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
VNInfo::Allocator & getVNInfoAllocator()
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
LiveInterval & getInterval(Register Reg)
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
void calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
Register get(unsigned idx) const
LiveInterval & createEmptyInterval()
create - Create a new register with the same class and original slot as parent.
const LiveInterval & getParent() const
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false, unsigned SubIdx=0, MachineInstr *ReplaceIndexMI=nullptr)
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, bool cheapAsAMove)
canRematerializeAt - Determine if ParentVNI can be rematerialized at UseIdx.
bool didRematerialize(const VNInfo *ParentVNI) const
didRematerialize - Return true if ParentVNI was rematerialized anywhere.
bool anyRematerializable()
anyRematerializable - Return true if any parent values may be rematerializable.
This class represents the liveness of a register, stack slot, etc.
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
bool liveAt(SlotIndex index) const
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
unsigned getNumValNums() const
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified interval from this live range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
Represents a single loop in the control flow graph.
Describe properties that are true of each instruction in the target description file.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator SkipPHIsLabelsAndDebug(iterator I, Register Reg=Register(), bool SkipPseudoOp=true)
Return the first instruction in MBB after I that is not a PHI, label or debug.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
BasicBlockListType::const_iterator const_iterator
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
void bundleWithPred()
Bundle this instruction with its predecessor.
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
MachineOperand class - Representation of each machine instruction operand.
bool isEarlyClobber() const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getNextSlot() const
Returns the next slot in the index list.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
typename SuperClass::const_iterator const_iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, const MachineLoopInfo &mli)
const MachineFunction & MF
MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB)
bool isOriginalEndpoint(SlotIndex Idx) const
isOriginalEndpoint - Return true if the original live range was killed or (re-)defined at Idx.
unsigned countLiveBlocks(const LiveInterval *li) const
countLiveBlocks - Return the number of blocks where li is live.
SlotIndex getLastSplitPoint(unsigned Num)
const LiveIntervals & LIS
void analyze(const LiveInterval *li)
analyze - set CurLI to the specified interval, and analyze how it may be split.
void clear()
clear - clear all data structures so SplitAnalysis is ready to analyze a new interval.
const MachineLoopInfo & Loops
const TargetInstrInfo & TII
unsigned getNumLiveBlocks() const
getNumLiveBlocks - Return the number of blocks where CurLI is live.
bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const
shouldSplitSingleBlock - Returns true if it would help to create a local live range for the instructi...
void overlapIntv(SlotIndex Start, SlotIndex End)
overlapIntv - Indicate that all instructions in range should use the open interval if End does not ha...
unsigned openIntv()
Create a new virtual register and live interval.
SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM, MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI)
Create a new SplitEditor for editing the LiveInterval analyzed by SA.
void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvOut, SlotIndex EnterAfter)
splitRegOutBlock - Split CurLI in the given block such that it enters the block on the stack (or isn'...
SlotIndex enterIntvAfter(SlotIndex Idx)
enterIntvAfter - Enter the open interval after the instruction at Idx.
SlotIndex enterIntvBefore(SlotIndex Idx)
enterIntvBefore - Enter the open interval before the instruction at Idx.
void useIntv(const MachineBasicBlock &MBB)
useIntv - indicate that all instructions in MBB should use OpenLI.
SlotIndex leaveIntvAfter(SlotIndex Idx)
leaveIntvAfter - Leave the open interval after the instruction at Idx.
void reset(LiveRangeEdit &, ComplementSpillMode=SM_Partition)
reset - Prepare for a new split.
SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB)
enterIntvAtEnd - Enter the open interval at the end of MBB.
SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB)
leaveIntvAtTop - Leave the interval at the top of MBB.
SlotIndex leaveIntvBefore(SlotIndex Idx)
leaveIntvBefore - Leave the open interval before the instruction at Idx.
void finish(SmallVectorImpl< unsigned > *LRMap=nullptr)
finish - after all the new live ranges have been created, compute the remaining live range,...
void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvIn, SlotIndex LeaveBefore)
splitRegInBlock - Split CurLI in the given block such that it enters the block in IntvIn and leaves i...
void splitLiveThroughBlock(unsigned MBBNum, unsigned IntvIn, SlotIndex LeaveBefore, unsigned IntvOut, SlotIndex EnterAfter)
splitLiveThroughBlock - Split CurLI in the given block such that it enters the block in IntvIn and le...
ComplementSpillMode
ComplementSpillMode - Select how the complement live range should be created.
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
@ SM_Speed
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
void selectIntv(unsigned Idx)
selectIntv - Select a previously opened interval index.
void splitSingleBlock(const SplitAnalysis::BlockInfo &BI)
splitSingleBlock - Split CurLI into a separate live interval around the uses in a single block.
void dump() const
dump - print the current interval mapping to dbgs().
virtual unsigned getLiveRangeSplitOpcode(Register Reg, const MachineFunction &MF) const
Allows targets to use appropriate copy instruction while spilitting live range of a register in regis...
std::optional< DestSourcePair > isCopyInstr(const MachineInstr &MI) const
If the specific machine instruction is a instruction that moves/copies value from one register to ano...
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
bool getCoveringSubRegIndexes(const MachineRegisterInfo &MRI, const TargetRegisterClass *RC, LaneBitmask LaneMask, SmallVectorImpl< unsigned > &Indexes) const
Try to find one or more subregister indexes to cover LaneMask.
VNInfo - Value Number Information.
bool isUnused() const
Returns true if this value is unused.
unsigned id
The ID number of this value.
SlotIndex def
The index of the defining instruction.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
void setIsSplitFromReg(Register virtReg, Register SReg)
records virtReg is a split live interval from SReg.
Register getOriginal(Register VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting.
MachineFunction & getMachineFunction() const
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
@ Define
Register definition.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
unsigned getInternalReadRegState(bool B)
unsigned getUndefRegState(bool B)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Description of the encoding of one expression Op.
static constexpr LaneBitmask getAll()
constexpr bool none() const
constexpr bool all() const
static constexpr LaneBitmask getNone()
Remat - Information needed to rematerialize at a specific location.
This represents a simple continuous liveness interval for a value.
Additional information about basic blocks where the current variable is live.
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
bool LiveOut
Current reg is live out.
bool LiveIn
Current reg is live in.
bool isOneInstr() const
isOneInstr - Returns true when this BlockInfo describes a single instruction.
void print(raw_ostream &OS) const
SlotIndex LastInstr
Last instr accessing current reg.
SlotIndex FirstInstr
First instr accessing current reg.