Go to the documentation of this file.
32 #include "llvm/Config/llvm-config.h"
47 #define DEBUG_TYPE "regalloc"
49 STATISTIC(NumFinished,
"Number of splits finished");
50 STATISTIC(NumSimple,
"Number of splits that were simple");
51 STATISTIC(NumCopies,
"Number of copies inserted for splitting");
52 STATISTIC(NumRemats,
"Number of rematerialized defs for splitting");
53 STATISTIC(NumRepairs,
"Number of invalid live ranges repaired");
61 : LIS(lis), LastInsertPoint(BBNum) {}
64 InsertPointAnalysis::computeLastInsertPoint(
const LiveInterval &CurLI,
67 std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
71 bool EHPadSuccessor =
false;
73 if (SMBB->isEHPad()) {
74 ExceptionalSuccessors.push_back(SMBB);
75 EHPadSuccessor =
true;
76 }
else if (SMBB->isInlineAsmBrIndirectTarget())
77 ExceptionalSuccessors.push_back(SMBB);
82 if (!LIP.first.isValid()) {
84 if (FirstTerm ==
MBB.
end())
95 if (ExceptionalSuccessors.empty())
98 if ((EHPadSuccessor &&
MI.isCall()) ||
148 : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis),
Loops(mli),
149 TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
154 ThroughBlocks.
clear();
156 DidRepairRange =
false;
160 void SplitAnalysis::analyzeUses() {
161 assert(UseSlots.empty() &&
"Call clear first");
167 UseSlots.push_back(VNI->
def);
179 UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
184 if (!calcLiveBlockInfo()) {
187 DidRepairRange =
true;
189 LLVM_DEBUG(
dbgs() <<
"*** Fixing inconsistent live interval! ***\n");
193 ThroughBlocks.
clear();
194 bool fixed = calcLiveBlockInfo();
196 assert(fixed &&
"Couldn't fix broken live interval");
199 LLVM_DEBUG(
dbgs() <<
"Analyze counted " << UseSlots.size() <<
" instrs in "
200 << UseBlocks.size() <<
" blocks, through "
201 << NumThroughBlocks <<
" blocks.\n");
206 bool SplitAnalysis::calcLiveBlockInfo() {
208 NumThroughBlocks = NumGapBlocks = 0;
216 UseI = UseSlots.begin();
217 UseE = UseSlots.end();
231 if (UseI == UseE || *UseI >= Stop) {
233 ThroughBlocks.
set(BI.MBB->getNumber());
240 BI.FirstInstr = *UseI;
241 assert(BI.FirstInstr >= Start);
243 while (UseI != UseE && *UseI < Stop);
244 BI.LastInstr = UseI[-1];
245 assert(BI.LastInstr < Stop);
248 BI.LiveIn = LVI->start <= Start;
252 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
253 assert(LVI->start == BI.FirstInstr &&
"First instr should be a def");
254 BI.FirstDef = BI.FirstInstr;
259 while (LVI->end < Stop) {
261 if (++LVI == LVE || LVI->start >= Stop) {
263 BI.LastInstr = LastStop;
267 if (LastStop < LVI->start) {
274 UseBlocks.push_back(BI);
275 UseBlocks.back().LastInstr = LastStop;
280 BI.FirstInstr = BI.FirstDef = LVI->start;
284 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
286 BI.FirstDef = LVI->start;
289 UseBlocks.push_back(BI);
297 if (LVI->end == Stop && ++LVI == LVE)
301 if (LVI->start < Stop)
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;
364 : SA(SA), AA(AA), LIS(LIS), VRM(VRM),
365 MRI(VRM.getMachineFunction().getRegInfo()), MDT(MDT),
366 TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),
367 TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),
368 MBFI(MBFI), VRAI(VRAI), RegAssign(
Allocator) {}
389 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
391 if (RegAssign.
empty()) {
392 dbgs() <<
" empty\n";
397 dbgs() <<
" [" <<
I.start() <<
';' <<
I.stop() <<
"):" <<
I.value();
405 if (
S.LaneMask == LM)
413 if ((
S.LaneMask & LM) == LM)
430 auto &PS = getSubRangeForMask(
S.LaneMask, Edit->
getParent());
432 if (PV !=
nullptr && PV->
def ==
Def)
446 if (
unsigned SR = DefOp.getSubReg())
454 if ((
S.LaneMask & LM).any())
459 VNInfo *SplitEditor::defValue(
unsigned RegIdx,
463 assert(ParentVNI &&
"Mapping NULL value");
472 ValueForcePair
FP(Force ?
nullptr : VNI, Force);
474 std::pair<ValueMap::iterator, bool> InsP =
475 Values.
insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->
id), FP));
479 if (!Force && InsP.second)
483 if (
VNInfo *OldVNI = InsP.first->second.getPointer()) {
484 addDeadDef(*LI, OldVNI, Original);
488 InsP.first->second = ValueForcePair(
nullptr, Force);
492 addDeadDef(*LI, VNI, Original);
496 void SplitEditor::forceRecompute(
unsigned RegIdx,
const VNInfo &ParentVNI) {
497 ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.
id)];
498 VNInfo *VNI = VFP.getPointer();
512 VFP = ValueForcePair(
nullptr,
true);
519 bool FirstCopy = !
Def.isValid();
523 .
addReg(FromReg, 0, SubIdx);
570 for (
unsigned BestIdx : Indexes) {
571 Def = buildSingleSubRegCopy(FromReg, ToReg,
MBB, InsertBefore, BestIdx,
578 VNInfo *SplitEditor::defFromParent(
unsigned RegIdx,
588 bool Late = RegIdx != 0;
596 bool DidRemat =
false;
611 if (
S.liveAt(UseIdx))
612 LaneMask |=
S.LaneMask;
618 if (LaneMask.
none()) {
630 return defValue(RegIdx, ParentVNI,
Def,
false);
640 OpenIdx = Edit->
size();
646 assert(Idx != 0 &&
"Cannot select the complement interval");
647 assert(Idx < Edit->
size() &&
"Can only select previously opened interval");
648 LLVM_DEBUG(
dbgs() <<
" selectIntv " << OpenIdx <<
" -> " << Idx <<
'\n');
653 assert(OpenIdx &&
"openIntv not called before enterIntvBefore");
663 assert(
MI &&
"enterIntvBefore called with invalid index");
665 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *
MI->getParent(),
MI);
670 assert(OpenIdx &&
"openIntv not called before enterIntvAfter");
680 assert(
MI &&
"enterIntvAfter called with invalid index");
682 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *
MI->getParent(),
688 assert(OpenIdx &&
"openIntv not called before enterIntvAtEnd");
699 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last,
MBB,
701 RegAssign.
insert(VNI->
def, End, OpenIdx);
712 assert(OpenIdx &&
"openIntv not called before useIntv");
713 LLVM_DEBUG(
dbgs() <<
" useIntv [" << Start <<
';' << End <<
"):");
714 RegAssign.
insert(Start, End, OpenIdx);
719 assert(OpenIdx &&
"openIntv not called before leaveIntvAfter");
731 assert(
MI &&
"No instruction at index");
738 MI->readsVirtualRegister(Edit->
getReg())) {
739 forceRecompute(0, *ParentVNI);
740 defFromParent(0, ParentVNI, Idx, *
MI->getParent(),
MI);
744 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *
MI->getParent(),
750 assert(OpenIdx &&
"openIntv not called before leaveIntvBefore");
763 assert(
MI &&
"No instruction at index");
764 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *
MI->getParent(),
MI);
769 assert(OpenIdx &&
"openIntv not called before leaveIntvAtTop");
780 VNInfo *VNI = defFromParent(0, ParentVNI, Start,
MBB,
782 RegAssign.
insert(Start, VNI->
def, OpenIdx);
788 assert(OpenIdx &&
"openIntv not called before overlapIntv");
791 "Parent changes value in extended range");
793 "Range cannot span basic blocks");
797 forceRecompute(0, *ParentVNI);
798 LLVM_DEBUG(
dbgs() <<
" overlapIntv [" << Start <<
';' << End <<
"):");
799 RegAssign.
insert(Start, End, OpenIdx);
811 AssignI.setMap(RegAssign);
816 assert(
MI &&
"No instruction for back-copy");
822 while (!AtBegin && (--
MBBI)->isDebugInstr());
827 MI->eraseFromParent();
831 AssignI.find(
Def.getPrevSlot());
832 if (!AssignI.valid() || AssignI.start() >=
Def)
835 if (AssignI.stop() !=
Def)
837 unsigned RegIdx = AssignI.value();
838 if (AtBegin || !
MBBI->readsVirtualRegister(Edit->
getReg())) {
839 LLVM_DEBUG(
dbgs() <<
" cannot find simple kill of RegIdx " << RegIdx
845 AssignI.setStop(
Kill);
878 if (
Loop == DefLoop) {
881 <<
" in the same loop\n");
887 if (
Depth < BestDepth) {
892 <<
" at depth " <<
Depth <<
'\n');
900 if (!IDom || !MDT.
dominates(DefDomNode, IDom))
907 void SplitEditor::computeRedundantBackCopies(
919 EqualVNs[ParentVNI->
id].insert(VNI);
926 if (!NotToHoistSet.
count(ParentVNI->
id))
930 for (; It1 != EqualVNs[ParentVNI->
id].end(); ++It1) {
932 for (++It2; It2 != EqualVNs[ParentVNI->
id].end(); ++It2) {
933 if (DominatedVNIs.
count(*It1) || DominatedVNIs.
count(*It2))
939 DominatedVNIs.
insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
941 DominatedVNIs.
insert(*It2);
943 DominatedVNIs.
insert(*It1);
947 if (!DominatedVNIs.
empty()) {
948 forceRecompute(0, *ParentVNI);
950 DominatedVNIs.
clear();
960 void SplitEditor::hoistCopies() {
967 using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
981 assert(ParentVNI &&
"Parent not live at complement def");
990 DomPair &Dom = NearestDom[ParentVNI->
id];
995 if (VNI->
def == ParentVNI->
def) {
997 Dom = DomPair(ValMBB, VNI->
def);
1009 Dom = DomPair(ValMBB, VNI->
def);
1010 }
else if (Dom.first == ValMBB) {
1012 if (!Dom.second.isValid() || VNI->
def < Dom.second)
1013 Dom.second = VNI->
def;
1020 Dom = DomPair(ValMBB, VNI->
def);
1021 else if (Near != Dom.first)
1028 << VNI->
def <<
" for parent " << ParentVNI->
id <<
'@'
1029 << ParentVNI->
def <<
" hoist to "
1036 DomPair &Dom = NearestDom[
i];
1037 if (!Dom.first || Dom.second.isValid())
1043 Dom.first = findShallowDominator(Dom.first, DefMBB);
1046 NotToHoistSet.
insert(ParentVNI->
id);
1051 defFromParent(0, ParentVNI, Last, *Dom.first,
1062 const DomPair &Dom = NearestDom[ParentVNI->
id];
1063 if (!Dom.first || Dom.second == VNI->
def ||
1064 NotToHoistSet.
count(ParentVNI->
id))
1066 BackCopies.push_back(VNI);
1067 forceRecompute(0, *ParentVNI);
1073 computeRedundantBackCopies(NotToHoistSet, BackCopies);
1075 removeBackCopies(BackCopies);
1080 bool SplitEditor::transferValues() {
1081 bool Skipped =
false;
1088 AssignI.advanceTo(Start);
1092 if (!AssignI.valid()) {
1094 }
else if (AssignI.start() <= Start) {
1095 RegIdx = AssignI.value();
1096 if (AssignI.stop() < End) {
1097 End = AssignI.stop();
1102 End =
std::min(End, AssignI.start());
1106 LLVM_DEBUG(
dbgs() <<
" [" << Start <<
';' << End <<
")=" << RegIdx <<
'('
1111 ValueForcePair VFP = Values.
lookup(std::make_pair(RegIdx, ParentVNI->
id));
1112 if (
VNInfo *VNI = VFP.getPointer()) {
1114 LI.
addSegment(LiveInterval::Segment(Start, End, VNI));
1137 if (Start != BlockStart) {
1139 assert(VNI &&
"Missing def for complex mapped value");
1142 if (BlockEnd <= End)
1147 BlockStart = BlockEnd;
1151 assert(Start <= BlockStart &&
"Expected live-in block");
1152 while (BlockStart < End) {
1155 if (BlockStart == ParentVNI->
def) {
1157 assert(ParentVNI->
isPHIDef() &&
"Non-phi defined at block start?");
1159 assert(VNI &&
"Missing def for complex mapped parent PHI");
1160 if (End >= BlockEnd)
1173 BlockStart = BlockEnd;
1177 }
while (Start !=
S.end);
1192 if (Seg->
end !=
Def.getDeadSlot())
1210 LiveRange &PSR = !LM.
all() ? getSubRangeForMaskExact(LM, PLI)
1213 LIC.
extend(LR, End, 0, Undefs);
1217 void SplitEditor::extendPHIKillRanges() {
1229 unsigned RegIdx = RegAssign.
lookup(V->
def);
1241 for (
const VNInfo *V : PS.valnos) {
1244 unsigned RegIdx = RegAssign.
lookup(V->
def);
1255 extendPHIRange(
B, SubLIC,
S, PS.LaneMask, Undefs);
1261 void SplitEditor::rewriteAssigned(
bool ExtendRanges) {
1264 : MO(
O), RegIdx(
R), Next(
N) {}
1277 if (
MI->isDebugValue()) {
1287 if (MO.isDef() || MO.isUndef())
1291 unsigned RegIdx = RegAssign.
lookup(Idx);
1293 MO.setReg(LI.
reg());
1295 <<
'\t' << Idx <<
':' << RegIdx <<
'\t' << *
MI);
1298 if (!ExtendRanges || MO.isUndef())
1303 if (!MO.getSubReg() && !MO.isEarlyClobber())
1320 ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1327 for (ExtPoint &EP : ExtPoints) {
1332 Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1336 if ((
S.LaneMask & LM).none())
1349 SubLIC.
extend(
S, EP.Next, 0, Undefs);
1363 void SplitEditor::deleteRematVictims() {
1369 if (
S.end !=
S.valno->def.getDeadSlot())
1371 if (
S.valno->isPHIDef())
1374 assert(
MI &&
"Missing instruction for dead def");
1375 MI->addRegisterDead(LI->
reg(), &TRI);
1377 if (!
MI->allDefsAreDead())
1388 Edit->eliminateDeadDefs(
Dead,
None, &AA);
1391 void SplitEditor::forceRecomputeVNI(
const VNInfo &ParentVNI) {
1394 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1395 forceRecompute(
I, ParentVNI);
1402 Visited.
insert(&ParentVNI);
1403 WorkList.push_back(&ParentVNI);
1408 const VNInfo &VNI = *WorkList.back();
1409 WorkList.pop_back();
1410 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1411 forceRecompute(
I, VNI);
1419 assert(PredVNI &&
"Value available in PhiVNI predecessor");
1420 if (Visited.
insert(PredVNI).second)
1421 WorkList.push_back(PredVNI);
1423 }
while(!WorkList.empty());
1433 for (
const VNInfo *ParentVNI : Edit->getParent().valnos) {
1436 unsigned RegIdx = RegAssign.
lookup(ParentVNI->
def);
1437 defValue(RegIdx, ParentVNI, ParentVNI->
def,
true);
1441 if (Edit->didRematerialize(ParentVNI))
1442 forceRecomputeVNI(*ParentVNI);
1446 switch (SpillMode) {
1457 bool Skipped = transferValues();
1460 rewriteAssigned(Skipped);
1463 extendPHIKillRanges();
1469 deleteRematVictims();
1481 for (
unsigned i = 0,
e = Edit->size();
i !=
e; ++
i)
1482 LRMap->push_back(
i);
1487 for (
unsigned i = 0,
e = Edit->size();
i !=
e; ++
i) {
1499 LRMap->
resize(Edit->size(),
i);
1505 assert(!LRMap || LRMap->size() == Edit->size());
1513 bool SingleInstrs)
const {
1558 unsigned IntvOut,
SlotIndex EnterAfter){
1562 LLVM_DEBUG(
dbgs() <<
"%bb." << MBBNum <<
" [" << Start <<
';' << Stop
1563 <<
") intf " << LeaveBefore <<
'-' << EnterAfter
1564 <<
", live-through " << IntvIn <<
" -> " << IntvOut);
1566 assert((IntvIn || IntvOut) &&
"Use splitSingleBlock for isolated blocks");
1568 assert((!LeaveBefore || LeaveBefore < Stop) &&
"Interference after block");
1569 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) &&
"Impossible intf");
1570 assert((!EnterAfter || EnterAfter >= Start) &&
"Interference before block");
1583 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1597 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1602 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1615 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) &&
"Impossible intf");
1617 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1627 if (LeaveBefore && LeaveBefore < LSP) {
1635 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1636 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1646 assert(LeaveBefore <= EnterAfter &&
"Missed case");
1651 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1656 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1660 unsigned IntvIn,
SlotIndex LeaveBefore) {
1665 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1666 << BI.
LastInstr <<
", reg-in " << IntvIn
1667 <<
", leave before " << LeaveBefore
1668 << (BI.
LiveOut ?
", stack-out" :
", killed in block"));
1670 assert(IntvIn &&
"Must have register in");
1672 assert((!LeaveBefore || LeaveBefore > Start) &&
"Bad interference");
1700 LLVM_DEBUG(
dbgs() <<
", spill after last use before interference.\n");
1704 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1711 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1721 LLVM_DEBUG(
dbgs() <<
", creating local interval " << LocalIntv <<
".\n");
1734 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1749 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1753 unsigned IntvOut,
SlotIndex EnterAfter) {
1758 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1759 << BI.
LastInstr <<
", reg-out " << IntvOut
1760 <<
", enter after " << EnterAfter
1761 << (BI.
LiveIn ?
", stack-in" :
", defined in block"));
1765 assert(IntvOut &&
"Must have register out");
1767 assert((!EnterAfter || EnterAfter < LSP) &&
"Bad interference");
1791 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1807 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1818 << (
LiveIn ?
"live in" :
"dead in") <<
", "
1819 << (
LiveOut ?
"live out" :
"dead out") <<
"}";
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
unsigned getNumLiveBlocks() const
getNumLiveBlocks - Return the number of blocks where CurLI is live.
InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum)
Remat - Information needed to rematerialize at a specific location.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
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 ...
void splitSingleBlock(const SplitAnalysis::BlockInfo &BI)
splitSingleBlock - Split CurLI into a separate live interval around the uses in a single block.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB)
enterIntvAtEnd - Enter the open interval at the end of MBB.
bool LiveIn
Current reg is live in.
void clear()
clear - Remove all entries.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
SlotIndex FirstInstr
First instr accessing current reg.
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
unsigned openIntv()
Create a new virtual register and live interval.
SlotIndexes * getSlotIndexes() const
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
bool isValid() const
Returns true if this is a valid index.
bool isOneInstr() const
isOneInstr - Returns true when this BlockInfo describes a single instruction.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Represents a single loop in the control flow graph.
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...
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
void clear()
clear - Removes all bits from the bitvector.
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
SplitEditor(SplitAnalysis &SA, AAResults &AA, LiveIntervals &LIS, VirtRegMap &VRM, MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI)
Create a new SplitEditor for editing the LiveInterval analyzed by SA.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Register getOriginal(Register VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
This represents a simple continuous liveness interval for a value.
void bundleWithPred()
Bundle this instruction with its predecessor.
SlotIndex def
The index of the defining instruction.
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Additional information about basic blocks where the current variable is live.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
const_iterator end(StringRef path)
Get end iterator over path.
MachineFunction & getMachineFunction() const
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
void useIntv(const MachineBasicBlock &MBB)
useIntv - indicate that all instructions in MBB should use OpenLI.
unsigned countLiveBlocks(const LiveInterval *li) const
countLiveBlocks - Return the number of blocks where li is live.
bool empty() const
empty - Return true when no intervals are mapped.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
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 calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
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.
unsigned const TargetRegisterInfo * TRI
bool didRematerialize(const VNInfo *ParentVNI) const
didRematerialize - Return true if ParentVNI was rematerialized anywhere.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
bool isOriginalEndpoint(SlotIndex Idx) const
isOriginalEndpoint - Return true if the original live range was killed or (re-)defined at Idx.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const
shouldSplitSingleBlock - Returns true if it would help to create a local live range for the instructi...
unsigned getUndefRegState(bool B)
void reset(LiveRangeEdit &, ComplementSpillMode=SM_Partition)
reset - Prepare for a new split.
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, const MachineLoopInfo &mli)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const LiveIntervals & LIS
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
const MachineLoopInfo & Loops
Register get(unsigned idx) const
bool liveAt(SlotIndex index) const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool anyRematerializable(AAResults *)
anyRematerializable - Return true if any parent values may be rematerializable.
(vector float) vec_cmpeq(*A, *B) C
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Segments::const_iterator const_iterator
static constexpr LaneBitmask getNone()
MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB)
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...
const HexagonInstrInfo * TII
SlotIndex leaveIntvBefore(SlotIndex Idx)
leaveIntvBefore - Leave the open interval before the instruction at Idx.
Describe properties that are true of each instruction in the target description file.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineOperand class - Representation of each machine instruction operand.
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
STATISTIC(NumFunctions, "Total number of functions")
This class implements an extremely fast bulk output stream that can only output to a stream.
@ Define
Register definition.
LiveInterval - This class represents the liveness of a register, or stack slot.
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 - An opaque wrapper around machine indexes.
@ Kill
The last use of a register.
SlotIndex enterIntvBefore(SlotIndex Idx)
enterIntvBefore - Enter the open interval before the instruction at Idx.
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
LiveInterval & getParent() const
void setIsSplitFromReg(Register virtReg, Register SReg)
records virtReg is a split live interval from SReg.
PointerTy getPointer() const
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
void overlapIntv(SlotIndex Start, SlotIndex End)
overlapIntv - Indicate that all instructions in range should use the open interval,...
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,...
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
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.
SlotIndex LastInstr
Last instr accessing current reg.
Representation of each machine instruction.
bool LiveOut
Current reg is live out.
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
This class represents the liveness of a register, stack slot, etc.
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
unsigned id
The ID number of this value.
Allocate memory in an ever growing pool, as if by bump-pointer.
void dump() const
dump - print the current interval mapping to dbgs().
LiveInterval & createEmptyInterval()
create - Create a new register with the same class and original slot as parent.
unsigned getNumValNums() const
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...
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
ValT lookup(KeyT x, ValT NotFound=ValT()) const
lookup - Return the mapped value at x or NotFound.
iterator_range< reg_iterator > reg_operands(Register Reg) const
iterator SkipPHIsLabelsAndDebug(iterator I)
Return the first instruction in MBB after I that is not a PHI, label or debug.
typename SuperClass::const_iterator const_iterator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getLoopDepth() const
Return the nesting level of this loop.
SlotIndex enterIntvAfter(SlotIndex Idx)
enterIntvAfter - Enter the open interval after the instruction at Idx.
SlotIndex getLastInsertPoint(const LiveInterval &CurLI, const MachineBasicBlock &MBB)
Return the base index of the last valid insert point for \pCurLI in \pMBB.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, bool cheapAsAMove)
canRematerializeAt - Determine if ParentVNI can be rematerialized at UseIdx.
iterator_range< pred_iterator > predecessors()
const MachineFunction & MF
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
LiveInterval & getInterval(Register Reg)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false)
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
iterator_range< succ_iterator > successors()
constexpr bool none() const
MachineBasicBlock MachineBasicBlock::iterator MBBI
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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.
@ SM_Speed
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
self_iterator getIterator()
SlotIndex getNextSlot() const
Returns the next slot in the index list.
void clear()
clear - clear all data structures so SplitAnalysis is ready to analyze a new interval.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Base class for the actual dominator tree node.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void finish(SmallVectorImpl< unsigned > *LRMap=nullptr)
finish - after all the new live ranges have been created, compute the remaining live range,...
A live range for subregisters.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB)
leaveIntvAtTop - Leave the interval at the top of MBB.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Segments::iterator iterator
LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
ComplementSpillMode
ComplementSpillMode - Select how the complement live range should be created.
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Iterator for intrusive lists based on ilist_node.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
constexpr bool all() const
BlockT * getHeader() const
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
VNInfo - Value Number Information.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
static bool removeDeadSegment(SlotIndex Def, LiveRange &LR)
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
SlotIndex leaveIntvAfter(SlotIndex Idx)
leaveIntvAfter - Leave the open interval after the instruction at Idx.
void print(raw_ostream &OS) const
void analyze(const LiveInterval *li)
analyze - set CurLI to the specified interval, and analyze how it may be split.
SlotIndex getLastSplitPoint(unsigned Num)
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
LLVM_NODISCARD bool empty() const
void RemoveMachineInstrFromMaps(MachineInstr &MI)
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
MachineInstrBuilder MachineInstrBuilder & DefMI
const_iterator begin() const
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Align max(MaybeAlign Lhs, Align Rhs)
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
friend class const_iterator
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
bool isUnused() const
Returns true if this value is unused.
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
BlockVerifier::State From
unsigned getInternalReadRegState(bool B)
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
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.
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
void selectIntv(unsigned Idx)
selectIntv - Select a previously opened interval index.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, MachineBasicBlock &MBB)
Returns the last insert point as an iterator for \pCurLI in \pMBB.
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
static constexpr LaneBitmask getAll()
VNInfo::Allocator & getVNInfoAllocator()
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
iterator_range< subrange_iterator > subranges()