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;
291 IsRootReserved =
false;
293 IsReserved |= IsRootReserved;
296 "reserved computation mismatch");
306 LICalc->extendToUses(LR, Reg);
319void LiveIntervals::computeLiveInRegUnits() {
321 LLVM_DEBUG(
dbgs() <<
"Computing live-in reg-units in ABI blocks.\n");
337 unsigned Unit = *Units;
354 for (
unsigned Unit : NewRanges)
355 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
360 for (
VNInfo *VNI : VNIs) {
368void LiveIntervals::extendSegmentsToUses(
LiveRange &Segments,
369 ShrinkToUsesWorkList &WorkList,
381 if ((SR.LaneMask & M).any()) {
382 assert(SR.LaneMask == M &&
"Expecting lane masks to match exactly");
390 const LiveRange &OldRange = getSubRange(LI, LaneMask);
393 while (!WorkList.empty()) {
395 VNInfo *VNI = WorkList.back().second;
402 assert(ExtVNI == VNI &&
"Unexpected existing value number");
406 !UsedPHIs.
insert(VNI).second)
410 if (!LiveOut.
insert(Pred).second)
415 WorkList.push_back(std::make_pair(Stop, PVNI));
426 if (!LiveOut.
insert(Pred).second)
430 assert(OldVNI == VNI &&
"Wrong value out of predecessor");
432 WorkList.push_back(std::make_pair(Stop, VNI));
438 "Missing value out of predecessor for main range");
442 "Missing value out of predecessor for subrange");
455 bool NeedsCleanup =
false;
470 if (
UseMI.isDebugInstr() || !
UseMI.readsVirtualRegister(Reg))
481 <<
"Warning: Instr claims to read non-existent value in "
502 bool CanSeparate = computeDeadValues(*li, dead);
509 bool MayHaveSplitComponents =
false;
516 assert(
I != LI.
end() &&
"Missing segment for VNI");
522 if ((
I == LI.
begin() || std::prev(
I)->end < Def) && !VNI->
isPHIDef()) {
524 MI->setRegisterDefReadUndef(VReg);
528 if (
I->end !=
Def.getDeadSlot())
534 LLVM_DEBUG(
dbgs() <<
"Dead PHI at " << Def <<
" may separate interval\n");
538 assert(
MI &&
"No instruction defining live value");
539 MI->addRegisterDead(LI.
reg(), TRI);
541 if (dead &&
MI->allDefsAreDead()) {
546 MayHaveSplitComponents =
true;
548 return MayHaveSplitComponents;
553 assert(Reg.isVirtual() &&
"Can only shrink virtual registers");
564 unsigned SubReg = MO.getSubReg();
567 if ((LaneMask & SR.
LaneMask).none())
595 extendSegmentsToUses(NewLR, WorkList, Reg, SR.
LaneMask);
605 assert(Segment !=
nullptr &&
"Missing segment for VNI");
611 <<
" may separate interval\n");
623 assert(LICalc &&
"LICalc not initialized.");
648 if (EndPoints) EndPoints->
push_back(MBBEnd);
681 if (EndPoints) EndPoints->
push_back(MBBEnd);
723 if (RI->end.isBlock())
737 for (
auto &RUP : RU) {
740 if (
I == RURange.
end())
743 if (
I == RURange.
end() ||
I->start >= RI->end)
767 if (Segment.
start >= RI->end)
769 if (Segment.
end == RI->end) {
770 DefinedLanesMask |= SR.LaneMask;
777 bool IsFullWrite =
false;
779 if (!MO.isReg() || MO.getReg() != Reg)
783 unsigned SubReg = MO.getSubReg();
786 if ((UseMask & ~DefinedLanesMask).any())
788 }
else if (MO.getSubReg() == 0) {
802 if (
N != LI.
end() &&
N->start == RI->end)
807 MI->addRegisterKilled(Reg,
nullptr);
810 MI->clearRegisterKills(Reg,
nullptr);
838 return MBB1 == MBB2 ? MBB1 :
nullptr;
844 if (
PHI->isUnused() || !
PHI->isPHIDef())
889 if (
MI->getOpcode() != TargetOpcode::STATEPOINT)
931 auto unionBitMask = [&](
unsigned Idx) {
942 assert(*SlotI >= LiveI->start);
944 while (*SlotI < LiveI->end) {
946 unionBitMask(SlotI - Slots.
begin());
947 if (++SlotI == SlotE)
951 if (*SlotI == LiveI->end)
954 unionBitMask(SlotI++ - Slots.
begin());
957 if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.
endIndex())
959 while (LiveI->end < *SlotI)
962 while (*SlotI < LiveI->start)
963 if (++SlotI == SlotE)
987 : LIS(LIS),
MRI(
MRI),
TRI(
TRI), OldIdx(OldIdx), NewIdx(NewIdx),
988 UpdateFlags(UpdateFlags) {}
995 if (UpdateFlags && !
MRI.isReservedRegUnit(Unit))
1003 LLVM_DEBUG(
dbgs() <<
"handleMove " << OldIdx <<
" -> " << NewIdx <<
": "
1005 bool hasRegMask =
false;
1016 MO.setIsKill(
false);
1022 if (Reg.isVirtual()) {
1025 unsigned SubReg = MO.getSubReg();
1027 :
MRI.getMaxLaneMaskForVReg(Reg);
1029 if ((S.LaneMask & LaneMask).none())
1031 updateRange(S, Reg, S.LaneMask);
1042 unsigned SubReg = MO.getSubReg();
1044 :
MRI.getMaxLaneMaskForVReg(Reg);
1046 if ((S.LaneMask & LaneMask).none() || LI.
covers(S))
1065 updateRegMaskSlots();
1072 if (!Updated.
insert(&LR).second)
1076 if (Reg.isVirtual()) {
1083 dbgs() <<
":\t" << LR <<
'\n';
1088 handleMoveUp(LR, Reg, LaneMask);
1115 if (MOP.isReg() && MOP.isUse())
1116 MOP.setIsKill(
false);
1127 if (NewIdxIn ==
E ||
1133 OldIdxIn->end = Next->start;
1140 OldIdxIn->end = NewIdx.
getRegSlot(OldIdxIn->end.isEarlyClobber());
1150 OldIdxOut = OldIdxIn;
1157 VNInfo *OldIdxVNI = OldIdxOut->valno;
1158 assert(OldIdxVNI->
def == OldIdxOut->start &&
"Inconsistent def");
1164 OldIdxVNI->
def = NewIdxDef;
1165 OldIdxOut->start = OldIdxVNI->
def;
1175 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1176 if (!OldIdxDefIsDead &&
1180 if (OldIdxOut != LR.
begin() &&
1182 OldIdxOut->start)) {
1187 IPrev->end = OldIdxOut->end;
1191 assert(INext !=
E &&
"Must have following segment");
1197 INext->start = OldIdxOut->end;
1198 INext->valno->def = INext->start;
1201 if (AfterNewIdx ==
E) {
1206 std::copy(std::next(OldIdxOut),
E, OldIdxOut);
1211 DefVNI->
def = NewIdxDef;
1214 Prev->end = NewIdxDef;
1220 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1228 Prev->valno->def = NewIdxDef;
1231 DefVNI->
def = Prev->start;
1236 DefVNI->
def = NewIdxDef;
1237 assert(DefVNI != AfterNewIdx->valno);
1243 if (AfterNewIdx !=
E &&
1247 assert(AfterNewIdx->valno != OldIdxVNI &&
"Multiple defs of value?");
1255 assert(AfterNewIdx != OldIdxOut &&
"Inconsistent iterators");
1256 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1259 VNInfo *NewSegmentVNI = OldIdxVNI;
1260 NewSegmentVNI->
def = NewIdxDef;
1290 = std::max(OldIdxIn->start.getDeadSlot(),
1291 NewIdx.
getRegSlot(OldIdxIn->end.isEarlyClobber()));
1292 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1295 OldIdxOut = std::next(OldIdxIn);
1299 OldIdxOut = OldIdxIn;
1300 OldIdxIn = OldIdxOut != LR.
begin() ? std::prev(OldIdxOut) :
E;
1307 VNInfo *OldIdxVNI = OldIdxOut->valno;
1308 assert(OldIdxVNI->
def == OldIdxOut->start &&
"Inconsistent def");
1309 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1315 assert(NewIdxOut->valno != OldIdxVNI &&
1316 "Same value defined more than once?");
1318 if (!OldIdxDefIsDead) {
1321 OldIdxVNI->
def = NewIdxDef;
1322 OldIdxOut->start = NewIdxDef;
1331 if (!OldIdxDefIsDead) {
1333 if (OldIdxIn !=
E &&
1339 OldIdxVNI = OldIdxIn->valno;
1341 SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;
1343 if (OldIdxIn != LR.
begin() &&
1351 NewDefEndPoint = std::min(OldIdxIn->start,
1352 std::next(NewIdxOut)->start);
1356 OldIdxOut->valno->def = OldIdxIn->start;
1363 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1374 Next->valno->def = SplitPos;
1379 NewSegment->valno->def = SplitPos;
1383 OldIdxOut->start = NewIdxDef;
1384 OldIdxVNI->
def = NewIdxDef;
1386 OldIdxIn->end = NewIdxDef;
1388 }
else if (OldIdxIn !=
E
1399 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1404 NewIdxOut->start, NewIdxDef.
getRegSlot(), NewIdxOut->valno);
1406 NewIdxDef.
getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1407 OldIdxVNI->
def = NewIdxDef;
1409 for (
auto *
Idx = NewIdxOut + 2;
Idx <= OldIdxOut; ++
Idx)
1410 Idx->valno = OldIdxVNI;
1416 if (MO->isReg() && !MO->isUse())
1417 MO->setIsDead(
false);
1424 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1427 VNInfo *NewSegmentVNI = OldIdxVNI;
1430 NewSegmentVNI->
def = NewIdxDef;
1435 void updateRegMaskSlots() {
1439 "No RegMask at OldIdx.");
1441 assert((RI == LIS.RegMaskSlots.begin() ||
1443 "Cannot move regmask instruction above another call");
1444 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1446 "Cannot move regmask instruction below another call");
1452 if (
Reg.isVirtual()) {
1457 unsigned SubReg = MO.getSubReg();
1459 && (
TRI.getSubRegIndexLaneMask(
SubReg) & LaneMask).none())
1464 if (InstSlot > LastUse && InstSlot < OldIdx)
1472 assert(Before < OldIdx &&
"Expected upwards move");
1481 if (
MI->getParent() ==
MBB)
1485 while (MII != Begin) {
1486 if ((--MII)->isDebugOrPseudoInstr())
1496 if (MO->isReg() && !MO->isUndef() && MO->getReg().isPhysical() &&
1497 TRI.hasRegUnit(MO->getReg(), Reg))
1498 return Idx.getRegSlot();
1508 assert((!
MI.isBundled() ||
MI.getOpcode() == TargetOpcode::BUNDLE) &&
1509 "Cannot move instruction in bundle");
1515 "Cannot handle moves across basic block boundaries.");
1517 HMEditor HME(*
this, *
MRI, *
TRI, OldIndex, NewIndex, UpdateFlags);
1524 "Bundle start is not a bundle");
1531 while (
I != BundleEnd) {
1540 HMEditor HME(*
this, *
MRI, *
TRI, OldIndex, NewIndex, UpdateFlags);
1567 if (LII != LR.
end() && LII->start < EndIdx) {
1568 lastUseIdx = LII->end;
1569 }
else if (LII == LR.
begin()) {
1579 if (
MI.isDebugOrPseudoInstr())
1589 if (!MO.isReg() || MO.getReg() != Reg)
1592 unsigned SubReg = MO.getSubReg();
1594 if ((Mask & LaneMask).
none())
1598 if (!isStartValid) {
1599 if (LII->end.isDead()) {
1601 if (LII != LR.
begin())
1606 if (MO.getSubReg() && !MO.isUndef())
1619 }
else if (LII->start != instrIdx.
getRegSlot()) {
1625 if (MO.getSubReg() && !MO.isUndef())
1629 }
else if (MO.isUse()) {
1633 if (!isEndValid && !LII->end.isBlock())
1642 if (!isStartValid && LII->end.isDead())
1671 if (
MI.isDebugOrPseudoInstr())
1674 if (MO.isReg() && MO.getReg().isVirtual()) {
1681 MRI->shouldTrackSubRegLiveness(Reg))
1692 for (
Register Reg : RegsToRepair) {
1693 if (!Reg.isVirtual())
1702 repairOldRegInRange(Begin, End, EndIdx, S, Reg, S.LaneMask);
1705 repairOldRegInRange(Begin, End, EndIdx, LI, Reg);
1721 if (VNI !=
nullptr) {
1728 if (
VNInfo *SVNI = S.getVNInfoAt(Pos))
1730 S.removeValNo(SVNI);
1738 unsigned NumComp = ConEQ.
Classify(LI);
1741 LLVM_DEBUG(
dbgs() <<
" Split " << NumComp <<
" components: " << LI <<
'\n');
1743 for (
unsigned I = 1;
I < NumComp; ++
I) {
1744 Register NewVReg =
MRI->cloneVirtualRegister(Reg);
1752 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
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.
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
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.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
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.
MCSuperRegIterator enumerates all super-registers of Reg.
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.
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
bool isVirtual() const
Return true if the specified register number is in the virtual 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)
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.