31#include "llvm/Config/llvm-config.h"
46#define DEBUG_TYPE "regalloc"
49STATISTIC(NumSimple,
"Number of splits that were simple");
50STATISTIC(NumCopies,
"Number of copies inserted for splitting");
51STATISTIC(NumRemats,
"Number of rematerialized defs for splitting");
59 : LIS(lis), LastInsertPoint(BBNum) {}
62InsertPointAnalysis::computeLastInsertPoint(
const LiveInterval &CurLI,
65 std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
69 bool EHPadSuccessor =
false;
71 if (SMBB->isEHPad()) {
73 EHPadSuccessor =
true;
74 }
else if (SMBB->isInlineAsmBrIndirectTarget())
80 if (!LIP.first.isValid()) {
82 if (FirstTerm ==
MBB.
end())
93 if (ExceptionalSuccessors.
empty())
96 if ((EHPadSuccessor &&
MI.isCall()) ||
97 MI.getOpcode() == TargetOpcode::INLINEASM_BR) {
123 if (
I->getOpcode() == TargetOpcode::STATEPOINT)
152 : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis),
Loops(mli),
153 TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
158 ThroughBlocks.
clear();
163void SplitAnalysis::analyzeUses() {
164 assert(UseSlots.empty() &&
"Call clear first");
170 UseSlots.push_back(VNI->
def);
182 UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
189 LLVM_DEBUG(
dbgs() <<
"Analyze counted " << UseSlots.size() <<
" instrs in "
190 << UseBlocks.size() <<
" blocks, through "
191 << NumThroughBlocks <<
" blocks.\n");
196void SplitAnalysis::calcLiveBlockInfo() {
198 NumThroughBlocks = NumGapBlocks = 0;
206 UseI = UseSlots.begin();
207 UseE = UseSlots.end();
221 if (UseI == UseE || *UseI >= Stop) {
223 ThroughBlocks.
set(BI.MBB->getNumber());
226 assert(LVI->end >= Stop &&
"range ends mid block with no uses");
229 BI.FirstInstr = *UseI;
230 assert(BI.FirstInstr >= Start);
232 while (UseI != UseE && *UseI < Stop);
233 BI.LastInstr = UseI[-1];
234 assert(BI.LastInstr < Stop);
237 BI.LiveIn = LVI->start <= Start;
241 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
242 assert(LVI->start == BI.FirstInstr &&
"First instr should be a def");
243 BI.FirstDef = BI.FirstInstr;
248 while (LVI->end < Stop) {
250 if (++LVI == LVE || LVI->start >= Stop) {
252 BI.LastInstr = LastStop;
256 if (LastStop < LVI->start) {
263 UseBlocks.push_back(BI);
264 UseBlocks.back().LastInstr = LastStop;
269 BI.FirstInstr = BI.FirstDef = LVI->start;
273 assert(LVI->start == LVI->valno->def &&
"Dangling Segment start");
275 BI.FirstDef = LVI->start;
278 UseBlocks.push_back(BI);
286 if (LVI->end == Stop && ++LVI == LVE)
290 if (LVI->start < Stop)
319 }
while (Stop <= LVI->start);
326 assert(!Orig.
empty() &&
"Splitting empty interval?");
330 if (
I != Orig.
end() &&
I->start <=
Idx)
331 return I->start ==
Idx;
334 return I != Orig.
begin() && (--
I)->end ==
Idx;
351 : SA(SA), LIS(LIS), VRM(VRM),
MRI(VRM.getMachineFunction().getRegInfo()),
352 MDT(MDT),
TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),
353 TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),
354 MBFI(MBFI), VRAI(VRAI), RegAssign(
Allocator) {}
373#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
375 if (RegAssign.
empty()) {
376 dbgs() <<
" empty\n";
381 dbgs() <<
" [" <<
I.start() <<
';' <<
I.stop() <<
"):" <<
I.value();
391 for (
auto &S : LI.subranges())
392 if (S.LaneMask == LM)
414 if ((S.LaneMask & LM) == LM)
432 VNInfo *PV = PS.getVNInfoAt(Def);
433 if (PV !=
nullptr && PV->
def == Def)
447 if (
unsigned SR = DefOp.getSubReg())
450 LM =
MRI.getMaxLaneMaskForVReg(R);
455 if ((S.LaneMask & LM).any())
460VNInfo *SplitEditor::defValue(
unsigned RegIdx,
464 assert(ParentVNI &&
"Mapping NULL value");
465 assert(
Idx.isValid() &&
"Invalid SlotIndex");
473 ValueForcePair
FP(Force ?
nullptr : VNI, Force);
475 std::pair<ValueMap::iterator, bool> InsP =
476 Values.
insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->
id),
FP));
480 if (!Force && InsP.second)
484 if (
VNInfo *OldVNI = InsP.first->second.getPointer()) {
485 addDeadDef(*LI, OldVNI, Original);
489 InsP.first->second = ValueForcePair(
nullptr, Force);
493 addDeadDef(*LI, VNI, Original);
497void SplitEditor::forceRecompute(
unsigned RegIdx,
const VNInfo &ParentVNI) {
498 ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.
id)];
499 VNInfo *VNI = VFP.getPointer();
513 VFP = ValueForcePair(
nullptr,
true);
516SlotIndex SplitEditor::buildSingleSubRegCopy(
520 bool FirstCopy = !
Def.isValid();
524 .
addReg(FromReg, 0, SubIdx);
541 if (LaneMask.
all() || LaneMask ==
MRI.getMaxLaneMaskForVReg(FromReg)) {
556 assert(RC ==
MRI.getRegClass(ToReg) &&
"Should have same reg class");
565 for (
unsigned BestIdx : SubIndexes) {
566 Def = buildSingleSubRegCopy(FromReg, ToReg,
MBB, InsertBefore, BestIdx,
567 DestLI, Late, Def,
Desc);
581VNInfo *SplitEditor::defFromParent(
unsigned RegIdx,
const VNInfo *ParentVNI,
589 bool Late = RegIdx != 0;
597 bool DidRemat =
false;
612 if (S.liveAt(UseIdx))
613 LaneMask |= S.LaneMask;
619 if (LaneMask.
none()) {
626 Def = buildCopy(Edit->
getReg(), Reg, LaneMask,
MBB,
I, Late, RegIdx);
631 return defValue(RegIdx, ParentVNI, Def,
false);
641 OpenIdx = Edit->
size();
647 assert(
Idx != 0 &&
"Cannot select the complement interval");
648 assert(Idx < Edit->
size() &&
"Can only select previously opened interval");
654 assert(OpenIdx &&
"openIntv not called before enterIntvBefore");
664 assert(
MI &&
"enterIntvBefore called with invalid index");
666 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI,
Idx, *
MI->getParent(),
MI);
671 assert(OpenIdx &&
"openIntv not called before enterIntvAfter");
673 Idx =
Idx.getBoundaryIndex();
681 assert(
MI &&
"enterIntvAfter called with invalid index");
683 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI,
Idx, *
MI->getParent(),
689 assert(OpenIdx &&
"openIntv not called before enterIntvAtEnd");
730 assert(OpenIdx &&
"openIntv not called before useIntv");
737 assert(OpenIdx &&
"openIntv not called before leaveIntvAfter");
749 assert(
MI &&
"No instruction at index");
756 MI->readsVirtualRegister(Edit->
getReg())) {
757 forceRecompute(0, *ParentVNI);
758 defFromParent(0, ParentVNI,
Idx, *
MI->getParent(),
MI);
762 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *
MI->getParent(),
768 assert(OpenIdx &&
"openIntv not called before leaveIntvBefore");
776 return Idx.getNextSlot();
781 assert(
MI &&
"No instruction at index");
782 VNInfo *VNI = defFromParent(0, ParentVNI,
Idx, *
MI->getParent(),
MI);
787 assert(OpenIdx &&
"openIntv not called before leaveIntvAtTop");
798 VNInfo *VNI = defFromParent(0, ParentVNI, Start,
MBB,
800 RegAssign.
insert(Start, VNI->
def, OpenIdx);
807 return MO.isReg() && MO.isTied() && MO.getReg() == Reg;
812 assert(OpenIdx &&
"openIntv not called before overlapIntv");
815 "Parent changes value in extended range");
817 "Range cannot span basic blocks");
821 forceRecompute(0, *ParentVNI);
845 AssignI.setMap(RegAssign);
850 assert(
MI &&
"No instruction for back-copy");
856 while (!AtBegin && (--
MBBI)->isDebugOrPseudoInstr());
861 MI->eraseFromParent();
865 AssignI.find(Def.getPrevSlot());
866 if (!AssignI.valid() || AssignI.start() >= Def)
869 if (AssignI.stop() != Def)
871 unsigned RegIdx = AssignI.value();
877 AtBegin ?
SlotIndex() : LIS.getInstructionIndex(*
MBBI).getRegSlot();
878 if (AtBegin || !
MBBI->readsVirtualRegister(Edit->
getReg()) ||
879 Kill <= AssignI.start()) {
880 LLVM_DEBUG(
dbgs() <<
" cannot find simple kill of RegIdx " << RegIdx
885 AssignI.setStop(Kill);
903 unsigned BestDepth = std::numeric_limits<unsigned>::max();
918 if (
Loop == DefLoop) {
921 <<
" in the same loop\n");
927 if (
Depth < BestDepth) {
932 <<
" at depth " <<
Depth <<
'\n');
940 if (!IDom || !MDT.
dominates(DefDomNode, IDom))
947void SplitEditor::computeRedundantBackCopies(
959 EqualVNs[ParentVNI->
id].insert(VNI);
964 for (
unsigned i = 0, e = Parent->
getNumValNums(); i != e; ++i) {
966 if (!NotToHoistSet.
count(ParentVNI->
id))
970 for (; It1 != EqualVNs[ParentVNI->
id].end(); ++It1) {
972 for (++It2; It2 != EqualVNs[ParentVNI->
id].end(); ++It2) {
973 if (DominatedVNIs.
count(*It1) || DominatedVNIs.
count(*It2))
979 DominatedVNIs.
insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
981 DominatedVNIs.
insert(*It2);
983 DominatedVNIs.
insert(*It1);
987 if (!DominatedVNIs.
empty()) {
988 forceRecompute(0, *ParentVNI);
990 DominatedVNIs.
clear();
1000void SplitEditor::hoistCopies() {
1007 using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1021 assert(ParentVNI &&
"Parent not live at complement def");
1030 DomPair &Dom = NearestDom[ParentVNI->
id];
1035 if (VNI->
def == ParentVNI->
def) {
1037 Dom = DomPair(ValMBB, VNI->
def);
1042 if (Values.
lookup(std::make_pair(0, ParentVNI->
id)).getPointer()) {
1049 Dom = DomPair(ValMBB, VNI->
def);
1050 }
else if (Dom.first == ValMBB) {
1052 if (!Dom.second.isValid() || VNI->
def < Dom.second)
1053 Dom.second = VNI->
def;
1060 Dom = DomPair(ValMBB, VNI->
def);
1061 else if (Near != Dom.first)
1068 << VNI->
def <<
" for parent " << ParentVNI->
id <<
'@'
1069 << ParentVNI->
def <<
" hoist to "
1075 for (
unsigned i = 0, e = Parent->
getNumValNums(); i != e; ++i) {
1076 DomPair &Dom = NearestDom[i];
1077 if (!Dom.first || Dom.second.isValid())
1083 Dom.first = findShallowDominator(Dom.first, DefMBB);
1086 NotToHoistSet.
insert(ParentVNI->
id);
1090 if (LSP <= ParentVNI->def) {
1091 NotToHoistSet.
insert(ParentVNI->
id);
1094 Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first,
1105 const DomPair &Dom = NearestDom[ParentVNI->
id];
1106 if (!Dom.first || Dom.second == VNI->
def ||
1107 NotToHoistSet.
count(ParentVNI->
id))
1110 forceRecompute(0, *ParentVNI);
1116 computeRedundantBackCopies(NotToHoistSet, BackCopies);
1118 removeBackCopies(BackCopies);
1123bool SplitEditor::transferValues() {
1124 bool Skipped =
false;
1128 VNInfo *ParentVNI = S.valno;
1131 AssignI.advanceTo(Start);
1135 if (!AssignI.valid()) {
1137 }
else if (AssignI.start() <= Start) {
1138 RegIdx = AssignI.value();
1139 if (AssignI.stop() <
End) {
1140 End = AssignI.stop();
1145 End = std::min(
End, AssignI.start());
1154 ValueForcePair VFP = Values.
lookup(std::make_pair(RegIdx, ParentVNI->
id));
1155 if (
VNInfo *VNI = VFP.getPointer()) {
1180 if (Start != BlockStart) {
1182 assert(VNI &&
"Missing def for complex mapped value");
1185 if (BlockEnd <=
End)
1190 BlockStart = BlockEnd;
1194 assert(Start <= BlockStart &&
"Expected live-in block");
1195 while (BlockStart <
End) {
1198 if (BlockStart == ParentVNI->
def) {
1200 assert(ParentVNI->
isPHIDef() &&
"Non-phi defined at block start?");
1202 assert(VNI &&
"Missing def for complex mapped parent PHI");
1203 if (
End >= BlockEnd)
1216 BlockStart = BlockEnd;
1220 }
while (Start != S.end);
1235 if (Seg->
end != Def.getDeadSlot())
1260void SplitEditor::extendPHIKillRanges() {
1269 if (
V->isUnused() || !
V->isPHIDef())
1272 unsigned RegIdx = RegAssign.
lookup(
V->def);
1284 for (
const VNInfo *V : PS.valnos) {
1285 if (
V->isUnused() || !
V->isPHIDef())
1287 unsigned RegIdx = RegAssign.
lookup(
V->def);
1298 extendPHIRange(
B, SubLIC, S, PS.LaneMask, Undefs);
1304void SplitEditor::rewriteAssigned(
bool ExtendRanges) {
1307 : MO(
O), RegIdx(
R), Next(
N) {}
1320 if (
MI->isDebugValue()) {
1330 if (MO.isDef() || MO.isUndef())
1331 Idx =
Idx.getRegSlot(MO.isEarlyClobber());
1334 unsigned RegIdx = RegAssign.
lookup(
Idx);
1336 MO.setReg(LI.
reg());
1338 <<
'\t' <<
Idx <<
':' << RegIdx <<
'\t' << *
MI);
1341 if (!ExtendRanges || MO.isUndef())
1346 if (!MO.getSubReg() && !MO.isEarlyClobber())
1354 bool IsEarlyClobber =
false;
1368 unsigned OpIdx = MO.getOperandNo();
1369 unsigned DefOpIdx =
MI->findTiedOperandIdx(OpIdx);
1374 Idx =
Idx.getRegSlot(IsEarlyClobber);
1384 ExtPoints.
push_back(ExtPoint(MO, RegIdx, Next));
1391 for (ExtPoint &EP : ExtPoints) {
1396 Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1398 :
MRI.getMaxLaneMaskForVReg(Reg);
1413 SubLIC.
extend(S, EP.Next, 0, Undefs);
1427void SplitEditor::deleteRematVictims() {
1438 assert(
MI &&
"Missing instruction for dead def");
1439 MI->addRegisterDead(LI->
reg(), &TRI);
1441 if (!
MI->allDefsAreDead())
1452 Edit->eliminateDeadDefs(Dead, std::nullopt);
1455void SplitEditor::forceRecomputeVNI(
const VNInfo &ParentVNI) {
1458 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1459 forceRecompute(
I, ParentVNI);
1466 Visited.
insert(&ParentVNI);
1474 for (
unsigned I = 0,
E = Edit->size();
I !=
E; ++
I)
1475 forceRecompute(
I, VNI);
1483 assert(PredVNI &&
"Value available in PhiVNI predecessor");
1484 if (Visited.
insert(PredVNI).second)
1487 }
while(!WorkList.
empty());
1497 for (
const VNInfo *ParentVNI : Edit->getParent().valnos) {
1500 unsigned RegIdx = RegAssign.
lookup(ParentVNI->
def);
1501 defValue(RegIdx, ParentVNI, ParentVNI->
def,
true);
1505 if (Edit->didRematerialize(ParentVNI))
1506 forceRecomputeVNI(*ParentVNI);
1510 switch (SpillMode) {
1521 bool Skipped = transferValues();
1524 rewriteAssigned(Skipped);
1527 extendPHIKillRanges();
1533 deleteRematVictims();
1544 auto Seq = llvm::seq<unsigned>(0, Edit->size());
1545 LRMap->
assign(Seq.begin(), Seq.end());
1550 for (
unsigned i = 0, e = Edit->size(); i != e; ++i) {
1562 LRMap->
resize(Edit->size(), i);
1568 assert(!LRMap || LRMap->
size() == Edit->size());
1576 bool SingleInstrs)
const {
1623 unsigned IntvOut,
SlotIndex EnterAfter){
1627 LLVM_DEBUG(
dbgs() <<
"%bb." << MBBNum <<
" [" << Start <<
';' << Stop
1628 <<
") intf " << LeaveBefore <<
'-' << EnterAfter
1629 <<
", live-through " << IntvIn <<
" -> " << IntvOut);
1631 assert((IntvIn || IntvOut) &&
"Use splitSingleBlock for isolated blocks");
1633 assert((!LeaveBefore || LeaveBefore < Stop) &&
"Interference after block");
1634 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) &&
"Impossible intf");
1635 assert((!EnterAfter || EnterAfter >= Start) &&
"Interference before block");
1648 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1662 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1667 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1680 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) &&
"Impossible intf");
1682 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1692 if (LeaveBefore && LeaveBefore < LSP) {
1700 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1701 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1711 assert(LeaveBefore <= EnterAfter &&
"Missed case");
1716 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1721 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1725 unsigned IntvIn,
SlotIndex LeaveBefore) {
1730 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1731 << BI.
LastInstr <<
", reg-in " << IntvIn
1732 <<
", leave before " << LeaveBefore
1733 << (BI.
LiveOut ?
", stack-out" :
", killed in block"));
1735 assert(IntvIn &&
"Must have register in");
1737 assert((!LeaveBefore || LeaveBefore > Start) &&
"Bad interference");
1765 LLVM_DEBUG(
dbgs() <<
", spill after last use before interference.\n");
1769 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1776 assert((!LeaveBefore ||
Idx <= LeaveBefore) &&
"Interference");
1786 LLVM_DEBUG(
dbgs() <<
", creating local interval " << LocalIntv <<
".\n");
1799 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1814 assert((!LeaveBefore ||
From <= LeaveBefore) &&
"Interference");
1818 unsigned IntvOut,
SlotIndex EnterAfter) {
1823 << Stop <<
"), uses " << BI.
FirstInstr <<
'-'
1824 << BI.
LastInstr <<
", reg-out " << IntvOut
1825 <<
", enter after " << EnterAfter
1826 << (BI.
LiveIn ?
", stack-in" :
", defined in block"));
1830 assert(IntvOut &&
"Must have register out");
1832 assert((!EnterAfter || EnterAfter < LSP) &&
"Bad interference");
1856 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1872 assert((!EnterAfter ||
Idx >= EnterAfter) &&
"Interference");
1883 << (
LiveIn ?
"live in" :
"dead in") <<
", "
1884 << (
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.
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 segment from this 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.
iterator SkipPHIsLabelsAndDebug(iterator I, bool SkipPseudoOp=true)
Return the first instruction in MBB after I that is not a PHI, label or debug.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
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.
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.
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.
Iterator for intrusive lists based on ilist_node.
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.
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 a range to a container.
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...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
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.