39#include "llvm/Config/llvm-config.h"
58#define DEBUG_TYPE "regalloc"
72 cl::desc(
"Eagerly compute live intervals for all physreg units."));
82 "Use segment set for the computation of the live ranges of physregs."));
105 for (
unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
107 VirtRegIntervals.clear();
108 RegMaskSlots.clear();
110 RegMaskBlocks.
clear();
114 RegUnitRanges.clear();
117 VNInfoAllocator.
Reset();
125 Indexes = &getAnalysis<SlotIndexes>();
126 DomTree = &getAnalysis<MachineDominatorTree>();
136 computeLiveInRegUnits();
149 OS <<
"********** INTERVALS **********\n";
152 for (
unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
172 OS <<
"********** MACHINEINSTRS **********\n";
176#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
188bool LiveIntervals::computeVirtRegInterval(
LiveInterval &LI) {
189 assert(LICalc &&
"LICalc not initialized.");
190 assert(LI.
empty() &&
"Should only compute empty intervals.");
193 return computeDeadValues(LI,
nullptr);
196void LiveIntervals::computeVirtRegs() {
202 bool NeedSplit = computeVirtRegInterval(LI);
210void LiveIntervals::computeRegMasks() {
215 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[
MBB.
getNumber()];
216 RMB.first = RegMaskSlots.size();
247 RegMaskSlots.push_back(
253 RMB.second = RegMaskSlots.size() - RMB.first;
271void LiveIntervals::computeRegUnitRange(
LiveRange &LR,
unsigned Unit) {
272 assert(LICalc &&
"LICalc not initialized.");
280 bool IsReserved =
false;
282 bool IsRootReserved =
true;
289 IsRootReserved =
false;
291 IsReserved |= IsRootReserved;
294 "reserved computation mismatch");
302 LICalc->extendToUses(LR, Reg);
315void LiveIntervals::computeLiveInRegUnits() {
317 LLVM_DEBUG(
dbgs() <<
"Computing live-in reg-units in ABI blocks.\n");
349 for (
unsigned Unit : NewRanges)
350 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
355 for (
VNInfo *VNI : VNIs) {
363void LiveIntervals::extendSegmentsToUses(
LiveRange &Segments,
364 ShrinkToUsesWorkList &WorkList,
376 if ((SR.LaneMask & M).any()) {
377 assert(SR.LaneMask == M &&
"Expecting lane masks to match exactly");
385 const LiveRange &OldRange = getSubRange(LI, LaneMask);
388 while (!WorkList.empty()) {
390 VNInfo *VNI = WorkList.back().second;
397 assert(ExtVNI == VNI &&
"Unexpected existing value number");
401 !UsedPHIs.
insert(VNI).second)
405 if (!LiveOut.
insert(Pred).second)
410 WorkList.push_back(std::make_pair(Stop, PVNI));
421 if (!LiveOut.
insert(Pred).second)
425 assert(OldVNI == VNI &&
"Wrong value out of predecessor");
427 WorkList.push_back(std::make_pair(Stop, VNI));
433 "Missing value out of predecessor for main range");
437 "Missing value out of predecessor for subrange");
450 bool NeedsCleanup =
false;
465 if (
UseMI.isDebugInstr() || !
UseMI.readsVirtualRegister(Reg))
476 <<
"Warning: Instr claims to read non-existent value in "
497 bool CanSeparate = computeDeadValues(*li, dead);
504 bool MayHaveSplitComponents =
false;
511 assert(
I != LI.
end() &&
"Missing segment for VNI");
517 if ((
I == LI.
begin() || std::prev(
I)->end < Def) && !VNI->
isPHIDef()) {
519 MI->setRegisterDefReadUndef(VReg);
523 if (
I->end !=
Def.getDeadSlot())
529 LLVM_DEBUG(
dbgs() <<
"Dead PHI at " << Def <<
" may separate interval\n");
533 assert(
MI &&
"No instruction defining live value");
534 MI->addRegisterDead(LI.
reg(), TRI);
536 if (dead &&
MI->allDefsAreDead()) {
541 MayHaveSplitComponents =
true;
543 return MayHaveSplitComponents;
548 assert(Reg.isVirtual() &&
"Can only shrink virtual registers");
559 unsigned SubReg = MO.getSubReg();
562 if ((LaneMask & SR.
LaneMask).none())
590 extendSegmentsToUses(NewLR, WorkList, Reg, SR.
LaneMask);
600 assert(Segment !=
nullptr &&
"Missing segment for VNI");
606 <<
" may separate interval\n");
618 assert(LICalc &&
"LICalc not initialized.");
643 if (EndPoints) EndPoints->
push_back(MBBEnd);
676 if (EndPoints) EndPoints->
push_back(MBBEnd);
717 if (RI->end.isBlock())
731 for (
auto &RUP : RU) {
734 if (
I == RURange.
end())
737 if (
I == RURange.
end() ||
I->start >= RI->end)
761 if (Segment.
start >= RI->end)
763 if (Segment.
end == RI->end) {
764 DefinedLanesMask |= SR.LaneMask;
771 bool IsFullWrite =
false;
773 if (!MO.isReg() || MO.getReg() != Reg)
777 unsigned SubReg = MO.getSubReg();
780 if ((UseMask & ~DefinedLanesMask).any())
782 }
else if (MO.getSubReg() == 0) {
796 if (
N != LI.
end() &&
N->start == RI->end)
801 MI->addRegisterKilled(Reg,
nullptr);
804 MI->clearRegisterKills(Reg,
nullptr);
832 return MBB1 == MBB2 ? MBB1 :
nullptr;
838 if (
PHI->isUnused() || !
PHI->isPHIDef())
883 if (
MI->getOpcode() != TargetOpcode::STATEPOINT)
925 auto unionBitMask = [&](
unsigned Idx) {
936 assert(*SlotI >= LiveI->start);
938 while (*SlotI < LiveI->end) {
940 unionBitMask(SlotI - Slots.
begin());
941 if (++SlotI == SlotE)
945 if (*SlotI == LiveI->end)
948 unionBitMask(SlotI++ - Slots.
begin());
951 if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.
endIndex())
953 while (LiveI->end < *SlotI)
956 while (*SlotI < LiveI->start)
957 if (++SlotI == SlotE)
981 : LIS(LIS),
MRI(
MRI),
TRI(
TRI), OldIdx(OldIdx), NewIdx(NewIdx),
982 UpdateFlags(UpdateFlags) {}
989 if (UpdateFlags && !
MRI.isReservedRegUnit(Unit))
997 LLVM_DEBUG(
dbgs() <<
"handleMove " << OldIdx <<
" -> " << NewIdx <<
": "
999 bool hasRegMask =
false;
1010 MO.setIsKill(
false);
1016 if (Reg.isVirtual()) {
1019 unsigned SubReg = MO.getSubReg();
1021 :
MRI.getMaxLaneMaskForVReg(Reg);
1023 if ((S.LaneMask & LaneMask).none())
1025 updateRange(S, Reg, S.LaneMask);
1036 unsigned SubReg = MO.getSubReg();
1038 :
MRI.getMaxLaneMaskForVReg(Reg);
1040 if ((S.LaneMask & LaneMask).none() || LI.
covers(S))
1058 updateRegMaskSlots();
1065 if (!Updated.
insert(&LR).second)
1069 if (Reg.isVirtual()) {
1076 dbgs() <<
":\t" << LR <<
'\n';
1081 handleMoveUp(LR, Reg, LaneMask);
1108 if (MOP.isReg() && MOP.isUse())
1109 MOP.setIsKill(
false);
1120 if (NewIdxIn ==
E ||
1126 OldIdxIn->end = Next->start;
1133 OldIdxIn->end = NewIdx.
getRegSlot(OldIdxIn->end.isEarlyClobber());
1143 OldIdxOut = OldIdxIn;
1150 VNInfo *OldIdxVNI = OldIdxOut->valno;
1151 assert(OldIdxVNI->
def == OldIdxOut->start &&
"Inconsistent def");
1157 OldIdxVNI->
def = NewIdxDef;
1158 OldIdxOut->start = OldIdxVNI->
def;
1168 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1169 if (!OldIdxDefIsDead &&
1173 if (OldIdxOut != LR.
begin() &&
1175 OldIdxOut->start)) {
1180 IPrev->end = OldIdxOut->end;
1184 assert(INext !=
E &&
"Must have following segment");
1190 INext->start = OldIdxOut->end;
1191 INext->valno->def = INext->start;
1194 if (AfterNewIdx ==
E) {
1199 std::copy(std::next(OldIdxOut),
E, OldIdxOut);
1204 DefVNI->
def = NewIdxDef;
1207 Prev->end = NewIdxDef;
1213 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1221 Prev->valno->def = NewIdxDef;
1224 DefVNI->
def = Prev->start;
1229 DefVNI->
def = NewIdxDef;
1230 assert(DefVNI != AfterNewIdx->valno);
1236 if (AfterNewIdx !=
E &&
1240 assert(AfterNewIdx->valno != OldIdxVNI &&
"Multiple defs of value?");
1248 assert(AfterNewIdx != OldIdxOut &&
"Inconsistent iterators");
1249 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1252 VNInfo *NewSegmentVNI = OldIdxVNI;
1253 NewSegmentVNI->
def = NewIdxDef;
1283 = std::max(OldIdxIn->start.getDeadSlot(),
1284 NewIdx.
getRegSlot(OldIdxIn->end.isEarlyClobber()));
1285 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1288 OldIdxOut = std::next(OldIdxIn);
1292 OldIdxOut = OldIdxIn;
1293 OldIdxIn = OldIdxOut != LR.
begin() ? std::prev(OldIdxOut) :
E;
1300 VNInfo *OldIdxVNI = OldIdxOut->valno;
1301 assert(OldIdxVNI->
def == OldIdxOut->start &&
"Inconsistent def");
1302 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1308 assert(NewIdxOut->valno != OldIdxVNI &&
1309 "Same value defined more than once?");
1311 if (!OldIdxDefIsDead) {
1314 OldIdxVNI->
def = NewIdxDef;
1315 OldIdxOut->start = NewIdxDef;
1324 if (!OldIdxDefIsDead) {
1326 if (OldIdxIn !=
E &&
1332 OldIdxVNI = OldIdxIn->valno;
1334 SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;
1336 if (OldIdxIn != LR.
begin() &&
1344 NewDefEndPoint = std::min(OldIdxIn->start,
1345 std::next(NewIdxOut)->start);
1349 OldIdxOut->valno->def = OldIdxIn->start;
1356 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1367 Next->valno->def = SplitPos;
1372 NewSegment->valno->def = SplitPos;
1376 OldIdxOut->start = NewIdxDef;
1377 OldIdxVNI->
def = NewIdxDef;
1379 OldIdxIn->end = NewIdxDef;
1381 }
else if (OldIdxIn !=
E
1392 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1397 NewIdxOut->start, NewIdxDef.
getRegSlot(), NewIdxOut->valno);
1399 NewIdxDef.
getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1400 OldIdxVNI->
def = NewIdxDef;
1402 for (
auto *
Idx = NewIdxOut + 2;
Idx <= OldIdxOut; ++
Idx)
1403 Idx->valno = OldIdxVNI;
1409 if (MO->isReg() && !MO->isUse())
1410 MO->setIsDead(
false);
1417 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1420 VNInfo *NewSegmentVNI = OldIdxVNI;
1423 NewSegmentVNI->
def = NewIdxDef;
1428 void updateRegMaskSlots() {
1432 "No RegMask at OldIdx.");
1434 assert((RI == LIS.RegMaskSlots.begin() ||
1436 "Cannot move regmask instruction above another call");
1437 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1439 "Cannot move regmask instruction below another call");
1445 if (
Reg.isVirtual()) {
1450 unsigned SubReg = MO.getSubReg();
1452 && (
TRI.getSubRegIndexLaneMask(
SubReg) & LaneMask).none())
1457 if (InstSlot > LastUse && InstSlot < OldIdx)
1465 assert(Before < OldIdx &&
"Expected upwards move");
1474 if (
MI->getParent() ==
MBB)
1478 while (MII != Begin) {
1479 if ((--MII)->isDebugOrPseudoInstr())
1489 if (MO->isReg() && !MO->isUndef() && MO->getReg().isPhysical() &&
1490 TRI.hasRegUnit(MO->getReg(), Reg))
1491 return Idx.getRegSlot();
1501 assert((!
MI.isBundled() ||
MI.getOpcode() == TargetOpcode::BUNDLE) &&
1502 "Cannot move instruction in bundle");
1508 "Cannot handle moves across basic block boundaries.");
1510 HMEditor HME(*
this, *
MRI, *
TRI, OldIndex, NewIndex, UpdateFlags);
1517 "Bundle start is not a bundle");
1524 while (
I != BundleEnd) {
1533 HMEditor HME(*
this, *
MRI, *
TRI, OldIndex, NewIndex, UpdateFlags);
1560 if (LII != LR.
end() && LII->start < EndIdx) {
1561 lastUseIdx = LII->end;
1562 }
else if (LII == LR.
begin()) {
1572 if (
MI.isDebugOrPseudoInstr())
1582 if (!MO.isReg() || MO.getReg() != Reg)
1585 unsigned SubReg = MO.getSubReg();
1587 if ((Mask & LaneMask).
none())
1591 if (!isStartValid) {
1592 if (LII->end.isDead()) {
1594 if (LII != LR.
begin())
1599 if (MO.getSubReg() && !MO.isUndef())
1612 }
else if (LII->start != instrIdx.
getRegSlot()) {
1618 if (MO.getSubReg() && !MO.isUndef())
1622 }
else if (MO.isUse()) {
1626 if (!isEndValid && !LII->end.isBlock())
1635 if (!isStartValid && LII->end.isDead())
1664 if (
MI.isDebugOrPseudoInstr())
1667 if (MO.isReg() && MO.getReg().isVirtual()) {
1674 MRI->shouldTrackSubRegLiveness(Reg))
1685 for (
Register Reg : RegsToRepair) {
1686 if (!Reg.isVirtual())
1695 repairOldRegInRange(Begin,
End, EndIdx, S, Reg, S.LaneMask);
1698 repairOldRegInRange(Begin,
End, EndIdx, LI, Reg);
1714 if (VNI !=
nullptr) {
1721 if (
VNInfo *SVNI = S.getVNInfoAt(Pos))
1723 S.removeValNo(SVNI);
1731 unsigned NumComp = ConEQ.
Classify(LI);
1734 LLVM_DEBUG(
dbgs() <<
" Split " << NumComp <<
" components: " << LI <<
'\n');
1736 for (
unsigned I = 1;
I < NumComp; ++
I) {
1737 Register NewVReg =
MRI->cloneVirtualRegister(Reg);
1745 assert(LICalc &&
"LICalc not initialized.");
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
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
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
A common definition of LaneBitmask for use in TableGen and CodeGen.
Live Interval static false cl::opt< bool > EnablePrecomputePhysRegs("precompute-phys-liveness", cl::Hidden, cl::desc("Eagerly compute live intervals for all physreg units."))
static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg)
Check whether use of reg in MI is live-through.
static void createSegmentsForValues(LiveRange &LR, iterator_range< LiveInterval::vni_iterator > VNIs)
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Toolkit used by handleMove to trim or extend live intervals.
HMEditor(LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
void updateAllRanges(MachineInstr *MI)
Update all live ranges touched by MI, assuming a move from OldIdx to NewIdx.
LiveRange * getRegUnitLI(unsigned Unit)
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredTransitiveID(char &ID)
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
AnalysisUsage & addRequiredTransitive()
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.
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
void createDeadDefs(LiveRange &LR, Register Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
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 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 releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< Register > OrigRegs)
Update live intervals for instructions in a range of iterators.
bool hasInterval(Register Reg) const
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.
bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
SlotIndexes * getSlotIndexes() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
ArrayRef< const uint32_t * > getRegMaskBits() const
Returns an array of register mask pointers corresponding to getRegMaskSlots().
void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
VNInfo::Allocator & getVNInfoAllocator()
ArrayRef< const uint32_t * > getRegMaskBitsInBlock(unsigned MBBNum) const
Returns an array of mask pointers corresponding to getRegMaskSlotsInBlock(MBBNum).
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
LiveRange * getCachedRegUnit(unsigned Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LiveInterval & getInterval(Register Reg)
void pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl< SlotIndex > *EndPoints)
If LR has a live value at Kill, prune its live range by removing any liveness reachable from Kill.
~LiveIntervals() override
void removeInterval(Register Reg)
Interval removal.
void handleMoveIntoNewBundle(MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals of operands of all instructions in the newly created bundle specified by BundleStart...
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
LiveInterval::Segment addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst)
Given a register and an instruction, adds a live segment from that instruction to the end of its MBB.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
void print(raw_ostream &O, const Module *=nullptr) const override
Implement the dump method.
Result of a LiveRange query.
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
bool isDeadDef() const
Return true if this instruction has a dead def.
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
static LLVM_ATTRIBUTE_UNUSED bool isJointlyDominated(const MachineBasicBlock *MBB, ArrayRef< SlotIndex > Defs, const SlotIndexes &Indexes)
A diagnostic function to check if the end of the block MBB is jointly dominated by the blocks corresp...
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.
This class represents the liveness of a register, stack slot, etc.
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.
iterator_range< vni_iterator > vnis()
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
bool covers(const LiveRange &Other) const
Returns true if all segments of the Other live range are completely covered by this live range.
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
void verify() const
Walk the range and assert if any invariants fail to hold.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
bool hasAtLeastOneValue() const
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
void flushSegmentSet()
Flush segment set into the regular segment vector.
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().
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
iterator_range< MCSuperRegIterator > superregs_inclusive(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, including Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Wrapper class representing physical registers. Should be passed by value.
bool isValid() const
isValid - Returns true until all the operands have been visited.
MIBundleOperands - Iterate over all operands in a bundle of machine instructions.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
bool livein_empty() const
const uint32_t * getBeginClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the start 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()
const uint32_t * getEndClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the end of the basic block.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
float getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const MachineBasicBlock * getParent() const
unsigned getNumOperands() const
Retuns the total number of operands.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setIsDead(bool Val=true)
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
bool subRegLivenessEnabled() const
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
bool shouldTrackSubRegLiveness(const TargetRegisterClass &RC) const
Returns true if liveness for register class RC should be tracked at the subregister level.
iterator_range< reg_instr_iterator > reg_instructions(Register Reg) const
LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
bool isReservedRegUnit(unsigned Unit) const
Returns true when the given register unit is considered reserved.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
bool reg_empty(Register RegNo) const
reg_empty - Return true if there are no instructions using or defining the specified register (it may...
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Wrapper class representing virtual and physical registers.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
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.
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
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.
bool isValid() const
Returns true if this is a valid index.
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getPrevSlot() const
Returns the previous 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.
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
void repairIndexesInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End)
Repair indexes after adding and removing instructions.
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.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
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 swap(SmallVectorImpl &RHS)
typename SuperClass::iterator iterator
void push_back(const T &Elt)
pointer data()
Return a pointer to the vector's buffer, even if empty().
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
MI-level Statepoint operands.
unsigned getNumDeoptArgsIdx() const
Get index of Number Deopt Arguments operand.
uint64_t getFlags() const
Return the statepoint flags.
unsigned getNumGCPtrIdx()
Get index of number of GC pointers.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const uint32_t * getCustomEHPadPreservedMask(const MachineFunction &MF) const
Return a register mask for the registers preserved by the unwinder, or nullptr if no custom mask is n...
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
VNInfo - Value Number Information.
void markUnused()
Mark this value as unused.
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...
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
self_iterator getIterator()
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
cl::opt< bool > UseSegmentSetForPhysRegs
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
@ DeoptLiveIn
Mark the deopt arguments associated with the statepoint as only being "live-in".
iterator_range< MIBundleOperands > mi_bundle_ops(MachineInstr &MI)
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
void initializeLiveIntervalsPass(PassRegistry &)
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.
char & LiveIntervalsID
LiveIntervals - This analysis keeps track of the live ranges of virtual and physical registers.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
static constexpr LaneBitmask getAll()
constexpr bool any() const
static constexpr LaneBitmask getNone()
This represents a simple continuous liveness interval for a value.