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");
60 : LIS(lis), LastInsertPoint(BBNum) {}
63 InsertPointAnalysis::computeLastInsertPoint(
const LiveInterval &CurLI,
66 std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
70 bool EHPadSuccessor =
false;
72 if (SMBB->isEHPad()) {
73 ExceptionalSuccessors.push_back(SMBB);
74 EHPadSuccessor =
true;
75 }
else if (SMBB->isInlineAsmBrIndirectTarget())
76 ExceptionalSuccessors.push_back(SMBB);
81 if (!LIP.first.isValid()) {
83 if (FirstTerm ==
MBB.
end())
94 if (ExceptionalSuccessors.empty())
97 if ((EHPadSuccessor &&
MI.isCall()) ||
124 if (
I->getOpcode() == TargetOpcode::STATEPOINT)
154 : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis),
Loops(mli),
155 TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
160 ThroughBlocks.
clear();
165 void SplitAnalysis::analyzeUses() {
166 assert(UseSlots.empty() &&
"Call clear first");
172 UseSlots.push_back(VNI->
def);
184 UseSlots.erase(
std::unique(UseSlots.begin(), UseSlots.end(),
191 LLVM_DEBUG(
dbgs() <<
"Analyze counted " << UseSlots.size() <<
" instrs in "
192 << UseBlocks.size() <<
" blocks, through "
193 << NumThroughBlocks <<
" blocks.\n");
198 void SplitAnalysis::calcLiveBlockInfo() {
200 NumThroughBlocks = NumGapBlocks = 0;
208 UseI = UseSlots.begin();
209 UseE = UseSlots.end();
223 if (UseI == UseE || *UseI >= Stop) {
225 ThroughBlocks.
set(BI.MBB->getNumber());
228 assert(LVI->end >= Stop &&
"range ends mid block with no uses");
231 BI.FirstInstr = *UseI;
232 assert(BI.FirstInstr >= Start);
234 while (UseI != UseE && *UseI < Stop);
235 BI.LastInstr = UseI[-1];
236 assert(BI.LastInstr < Stop);
239 BI.LiveIn = LVI->start <= Start;
243 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
244 assert(LVI->start == BI.FirstInstr &&
"First instr should be a def");
245 BI.FirstDef = BI.FirstInstr;
250 while (LVI->end < Stop) {
252 if (++LVI == LVE || LVI->start >= Stop) {
254 BI.LastInstr = LastStop;
258 if (LastStop < LVI->start) {
265 UseBlocks.push_back(BI);
266 UseBlocks.back().LastInstr = LastStop;
271 BI.FirstInstr = BI.FirstDef = LVI->start;
275 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
277 BI.FirstDef = LVI->start;
280 UseBlocks.push_back(BI);
288 if (LVI->end == Stop && ++LVI == LVE)
292 if (LVI->start < Stop)
321 }
while (Stop <= LVI->start);
328 assert(!Orig.
empty() &&
"Splitting empty interval?");
332 if (
I != Orig.
end() &&
I->start <= Idx)
333 return I->start == Idx;
336 return I != Orig.
begin() && (--
I)->
end == Idx;
353 : SA(SA), LIS(LIS), VRM(VRM),
MRI(VRM.getMachineFunction().getRegInfo()),
354 MDT(MDT),
TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),
355 TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),
356 MBFI(MBFI), VRAI(VRAI), RegAssign(
Allocator) {}
375 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
377 if (RegAssign.
empty()) {
378 dbgs() <<
" empty\n";
383 dbgs() <<
" [" <<
I.start() <<
';' <<
I.stop() <<
"):" <<
I.value();
393 for (
auto &
S : LI.subranges())
394 if (
S.LaneMask == LM)
416 if ((
S.LaneMask & LM) == LM)
435 if (PV !=
nullptr && PV->
def ==
Def)
449 if (
unsigned SR = DefOp.getSubReg())
457 if ((
S.LaneMask & LM).any())
462 VNInfo *SplitEditor::defValue(
unsigned RegIdx,
466 assert(ParentVNI &&
"Mapping NULL value");
475 ValueForcePair
FP(Force ?
nullptr : VNI, Force);
477 std::pair<ValueMap::iterator, bool> InsP =
478 Values.
insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->
id), FP));
482 if (!Force && InsP.second)
486 if (
VNInfo *OldVNI = InsP.first->second.getPointer()) {
487 addDeadDef(*LI, OldVNI, Original);
491 InsP.first->second = ValueForcePair(
nullptr, Force);
495 addDeadDef(*LI, VNI, Original);
499 void SplitEditor::forceRecompute(
unsigned RegIdx,
const VNInfo &ParentVNI) {
500 ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.
id)];
501 VNInfo *VNI = VFP.getPointer();
515 VFP = ValueForcePair(
nullptr,
true);
522 bool FirstCopy = !
Def.isValid();
526 .
addReg(FromReg, 0, SubIdx);
566 for (
unsigned BestIdx : SubIndexes) {
567 Def = buildSingleSubRegCopy(FromReg, ToReg,
MBB, InsertBefore, BestIdx,
582 VNInfo *SplitEditor::defFromParent(
unsigned RegIdx,
const VNInfo *ParentVNI,
590 bool Late = RegIdx != 0;
598 bool DidRemat =
false;
613 if (
S.liveAt(UseIdx))
614 LaneMask |=
S.LaneMask;
620 if (LaneMask.
none()) {
632 return defValue(RegIdx, ParentVNI,
Def,
false);
642 OpenIdx = Edit->
size();
648 assert(Idx != 0 &&
"Cannot select the complement interval");
649 assert(Idx < Edit->
size() &&
"Can only select previously opened interval");
650 LLVM_DEBUG(
dbgs() <<
" selectIntv " << OpenIdx <<
" -> " << Idx <<
'\n');
655 assert(OpenIdx &&
"openIntv not called before enterIntvBefore");
665 assert(
MI &&
"enterIntvBefore called with invalid index");
667 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *
MI->getParent(),
MI);
672 assert(OpenIdx &&
"openIntv not called before enterIntvAfter");
682 assert(
MI &&
"enterIntvAfter called with invalid index");
684 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *
MI->getParent(),
690 assert(OpenIdx &&
"openIntv not called before enterIntvAtEnd");
718 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last,
MBB,
720 RegAssign.
insert(VNI->
def, End, OpenIdx);
731 assert(OpenIdx &&
"openIntv not called before useIntv");
732 LLVM_DEBUG(
dbgs() <<
" useIntv [" << Start <<
';' << End <<
"):");
733 RegAssign.
insert(Start, End, OpenIdx);
738 assert(OpenIdx &&
"openIntv not called before leaveIntvAfter");
750 assert(
MI &&
"No instruction at index");
757 MI->readsVirtualRegister(Edit->
getReg())) {
758 forceRecompute(0, *ParentVNI);
759 defFromParent(0, ParentVNI, Idx, *
MI->getParent(),
MI);
763 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *
MI->getParent(),
769 assert(OpenIdx &&
"openIntv not called before leaveIntvBefore");
782 assert(
MI &&
"No instruction at index");
783 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *
MI->getParent(),
MI);
788 assert(OpenIdx &&
"openIntv not called before leaveIntvAtTop");
799 VNInfo *VNI = defFromParent(0, ParentVNI, Start,
MBB,
801 RegAssign.
insert(Start, VNI->
def, OpenIdx);
808 return MO.isReg() && MO.isTied() && MO.getReg() == Reg;
813 assert(OpenIdx &&
"openIntv not called before overlapIntv");
816 "Parent changes value in extended range");
818 "Range cannot span basic blocks");
822 forceRecompute(0, *ParentVNI);
833 LLVM_DEBUG(
dbgs() <<
" overlapIntv [" << Start <<
';' << End <<
"):");
834 RegAssign.
insert(Start, End, OpenIdx);
846 AssignI.setMap(RegAssign);
851 assert(
MI &&
"No instruction for back-copy");
857 while (!AtBegin && (--
MBBI)->isDebugOrPseudoInstr());
862 MI->eraseFromParent();
866 AssignI.find(
Def.getPrevSlot());
867 if (!AssignI.valid() || AssignI.start() >=
Def)
870 if (AssignI.stop() !=
Def)
872 unsigned RegIdx = AssignI.value();
878 AtBegin ?
SlotIndex() : LIS.getInstructionIndex(*
MBBI).getRegSlot();
879 if (AtBegin || !
MBBI->readsVirtualRegister(Edit->
getReg()) ||
880 Kill <= AssignI.start()) {
881 LLVM_DEBUG(
dbgs() <<
" cannot find simple kill of RegIdx " << RegIdx
886 AssignI.setStop(
Kill);
919 if (
Loop == DefLoop) {
922 <<
" in the same loop\n");
928 if (
Depth < BestDepth) {
933 <<
" at depth " <<
Depth <<
'\n');
941 if (!IDom || !MDT.
dominates(DefDomNode, IDom))
948 void SplitEditor::computeRedundantBackCopies(
960 EqualVNs[ParentVNI->
id].insert(VNI);
967 if (!NotToHoistSet.
count(ParentVNI->
id))
971 for (; It1 != EqualVNs[ParentVNI->
id].end(); ++It1) {
973 for (++It2; It2 != EqualVNs[ParentVNI->
id].end(); ++It2) {
974 if (DominatedVNIs.
count(*It1) || DominatedVNIs.
count(*It2))
980 DominatedVNIs.
insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
982 DominatedVNIs.
insert(*It2);
984 DominatedVNIs.
insert(*It1);
988 if (!DominatedVNIs.
empty()) {
989 forceRecompute(0, *ParentVNI);
991 DominatedVNIs.
clear();
1001 void SplitEditor::hoistCopies() {
1008 using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1022 assert(ParentVNI &&
"Parent not live at complement def");
1031 DomPair &Dom = NearestDom[ParentVNI->
id];
1036 if (VNI->
def == ParentVNI->
def) {
1038 Dom = DomPair(ValMBB, VNI->
def);
1050 Dom = DomPair(ValMBB, VNI->
def);
1051 }
else if (Dom.first == ValMBB) {
1053 if (!Dom.second.isValid() || VNI->
def < Dom.second)
1054 Dom.second = VNI->
def;
1061 Dom = DomPair(ValMBB, VNI->
def);
1062 else if (Near != Dom.first)
1069 << VNI->
def <<
" for parent " << ParentVNI->
id <<
'@'
1070 << ParentVNI->
def <<
" hoist to "
1077 DomPair &Dom = NearestDom[
i];
1078 if (!Dom.first || Dom.second.isValid())
1084 Dom.first = findShallowDominator(Dom.first, DefMBB);
1087 NotToHoistSet.
insert(ParentVNI->
id);
1091 if (LSP <= ParentVNI->def) {
1092 NotToHoistSet.
insert(ParentVNI->
id);
1095 Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first,
1106 const DomPair &Dom = NearestDom[ParentVNI->
id];
1107 if (!Dom.first || Dom.second == VNI->
def ||
1108 NotToHoistSet.
count(ParentVNI->
id))
1110 BackCopies.push_back(VNI);
1111 forceRecompute(0, *ParentVNI);
1117 computeRedundantBackCopies(NotToHoistSet, BackCopies);
1119 removeBackCopies(BackCopies);
1124 bool SplitEditor::transferValues() {
1125 bool Skipped =
false;
1132 AssignI.advanceTo(Start);
1136 if (!AssignI.valid()) {
1138 }
else if (AssignI.start() <= Start) {
1139 RegIdx = AssignI.value();
1140 if (AssignI.stop() < End) {
1141 End = AssignI.stop();
1146 End =
std::min(End, AssignI.start());
1150 LLVM_DEBUG(
dbgs() <<
" [" << Start <<
';' << End <<
")=" << RegIdx <<
'('
1155 ValueForcePair VFP = Values.
lookup(std::make_pair(RegIdx, ParentVNI->
id));
1156 if (
VNInfo *VNI = VFP.getPointer()) {
1158 LI.
addSegment(LiveInterval::Segment(Start, End, VNI));
1181 if (Start != BlockStart) {
1183 assert(VNI &&
"Missing def for complex mapped value");
1186 if (BlockEnd <= End)
1191 BlockStart = BlockEnd;
1195 assert(Start <= BlockStart &&
"Expected live-in block");
1196 while (BlockStart < End) {
1199 if (BlockStart == ParentVNI->
def) {
1201 assert(ParentVNI->
isPHIDef() &&
"Non-phi defined at block start?");
1203 assert(VNI &&
"Missing def for complex mapped parent PHI");
1204 if (End >= BlockEnd)
1217 BlockStart = BlockEnd;
1221 }
while (Start !=
S.end);
1236 if (Seg->
end !=
Def.getDeadSlot())
1257 LIC.
extend(LR, End, 0, Undefs);
1261 void SplitEditor::extendPHIKillRanges() {
1273 unsigned RegIdx = RegAssign.
lookup(V->
def);
1285 for (
const VNInfo *V : PS.valnos) {
1288 unsigned RegIdx = RegAssign.
lookup(V->
def);
1299 extendPHIRange(
B, SubLIC,
S, PS.LaneMask, Undefs);
1305 void SplitEditor::rewriteAssigned(
bool ExtendRanges) {
1308 : MO(
O), RegIdx(
R), Next(
N) {}
1321 if (
MI->isDebugValue()) {
1331 if (MO.isDef() || MO.isUndef())
1335 unsigned RegIdx = RegAssign.
lookup(Idx);
1337 MO.setReg(LI.
reg());
1339 <<
'\t' << Idx <<
':' << RegIdx <<
'\t' << *
MI);
1342 if (!ExtendRanges || MO.isUndef())
1347 if (!MO.getSubReg() && !MO.isEarlyClobber())
1355 bool IsEarlyClobber =
false;
1369 unsigned OpIdx =
MI->getOperandNo(&MO);
1370 unsigned DefOpIdx =
MI->findTiedOperandIdx(OpIdx);
1385 ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1392 for (ExtPoint &EP : ExtPoints) {
1397 Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1401 if ((
S.LaneMask & LM).none())
1414 SubLIC.
extend(
S, EP.Next, 0, Undefs);
1428 void SplitEditor::deleteRematVictims() {
1434 if (
S.end !=
S.valno->def.getDeadSlot())
1436 if (
S.valno->isPHIDef())
1439 assert(
MI &&
"Missing instruction for dead def");
1440 MI->addRegisterDead(LI->
reg(), &TRI);
1442 if (!
MI->allDefsAreDead())
1453 Edit->eliminateDeadDefs(
Dead,
None);
1456 void SplitEditor::forceRecomputeVNI(
const VNInfo &ParentVNI) {
1459 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1460 forceRecompute(
I, ParentVNI);
1467 Visited.
insert(&ParentVNI);
1468 WorkList.push_back(&ParentVNI);
1473 const VNInfo &VNI = *WorkList.back();
1474 WorkList.pop_back();
1475 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1476 forceRecompute(
I, VNI);
1484 assert(PredVNI &&
"Value available in PhiVNI predecessor");
1485 if (Visited.
insert(PredVNI).second)
1486 WorkList.push_back(PredVNI);
1488 }
while(!WorkList.empty());
1498 for (
const VNInfo *ParentVNI : Edit->getParent().valnos) {
1501 unsigned RegIdx = RegAssign.
lookup(ParentVNI->
def);
1502 defValue(RegIdx, ParentVNI, ParentVNI->
def,
true);
1506 if (Edit->didRematerialize(ParentVNI))
1507 forceRecomputeVNI(*ParentVNI);
1511 switch (SpillMode) {
1522 bool Skipped = transferValues();
1525 rewriteAssigned(Skipped);
1528 extendPHIKillRanges();
1534 deleteRematVictims();
1545 auto Seq = llvm::seq<unsigned>(0, Edit->size());
1546 LRMap->
assign(Seq.begin(), Seq.end());
1551 for (
unsigned i = 0,
e = Edit->size();
i !=
e; ++
i) {
1563 LRMap->
resize(Edit->size(),
i);
1569 assert(!LRMap || LRMap->size() == Edit->size());
1577 bool SingleInstrs)
const {
1622 unsigned IntvOut,
SlotIndex EnterAfter){
1626 LLVM_DEBUG(
dbgs() <<
"%bb." << MBBNum <<
" [" << Start <<
';' << Stop
1627 <<
") intf " << LeaveBefore <<
'-' << EnterAfter
1628 <<
", live-through " << IntvIn <<
" -> " << IntvOut);
1630 assert((IntvIn || IntvOut) &&
"Use splitSingleBlock for isolated blocks");
1632 assert((!LeaveBefore || LeaveBefore < Stop) &&
"Interference after block");
1633 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) &&
"Impossible intf");
1634 assert((!EnterAfter || EnterAfter >= Start) &&
"Interference before block");
1647 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1661 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1666 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1679 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) &&
"Impossible intf");
1681 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1691 if (LeaveBefore && LeaveBefore < LSP) {
1699 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1700 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1710 assert(LeaveBefore <= EnterAfter &&
"Missed case");
1715 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1720 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1724 unsigned IntvIn,
SlotIndex LeaveBefore) {
1729 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1730 << BI.
LastInstr <<
", reg-in " << IntvIn
1731 <<
", leave before " << LeaveBefore
1732 << (BI.
LiveOut ?
", stack-out" :
", killed in block"));
1734 assert(IntvIn &&
"Must have register in");
1736 assert((!LeaveBefore || LeaveBefore > Start) &&
"Bad interference");
1764 LLVM_DEBUG(
dbgs() <<
", spill after last use before interference.\n");
1768 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1775 assert((!LeaveBefore || Idx <= LeaveBefore) &&
"Interference");
1785 LLVM_DEBUG(
dbgs() <<
", creating local interval " << LocalIntv <<
".\n");
1798 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1813 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1817 unsigned IntvOut,
SlotIndex EnterAfter) {
1822 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1823 << BI.
LastInstr <<
", reg-out " << IntvOut
1824 <<
", enter after " << EnterAfter
1825 << (BI.
LiveIn ?
", stack-in" :
", defined in block"));
1829 assert(IntvOut &&
"Must have register out");
1831 assert((!EnterAfter || EnterAfter < LSP) &&
"Bad interference");
1855 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1871 assert((!EnterAfter || Idx >= EnterAfter) &&
"Interference");
1882 << (
LiveIn ?
"live in" :
"dead in") <<
", "
1883 << (
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.
This is an optimization pass for GlobalISel generic memory operations.
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
bool anyRematerializable()
anyRematerializable - Return true if any parent values may be rematerializable.
void clear()
clear - Removes all bits from the bitvector.
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
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.
Reg
All possible values of the reg field in the ModR/M byte.
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.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
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.
SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM, MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI)
Create a new SplitEditor for editing the LiveInterval analyzed by SA.
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")
(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()
@ Kill
The last use of a register.
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.
auto & getSubrangeImpl(LaneBitmask LM, T &LI)
Find a subrange corresponding to the exact lane mask LM in the live interval LI.
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.
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.
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.
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 if End does not ha...
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.
static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg)
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
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.
bool isEarlyClobber() const
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)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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,...
LiveInterval::SubRange & getSubRangeForMaskExact(LaneBitmask LM, LiveInterval &LI)
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...
const LiveInterval & getParent() const
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.
void assign(size_type NumElts, ValueParamT Elt)
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
@ Define
Register definition.
BlockT * getHeader() const
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
auto unique(Range &&R, Predicate P)
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.
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.
iterator SkipPHIsLabelsAndDebug(iterator I, bool SkipPseudoOp=true)
Return the first instruction in MBB after I that is not a PHI, label or debug.
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.
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.
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 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()