39 #include "llvm/Config/llvm-config.h" 58 #define DEBUG_TYPE "regalloc" 63 "Live Interval Analysis",
false,
false)
73 cl::desc(
"Eagerly compute live intervals for all physreg units."));
83 "Use segment set for the computation of the live ranges of physregs."));
110 for (
unsigned i = 0,
e = VirtRegIntervals.size(); i !=
e; ++i)
112 VirtRegIntervals.clear();
113 RegMaskSlots.clear();
115 RegMaskBlocks.
clear();
119 RegUnitRanges.clear();
122 VNInfoAllocator.
Reset();
130 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
131 Indexes = &getAnalysis<SlotIndexes>();
132 DomTree = &getAnalysis<MachineDominatorTree>();
142 computeLiveInRegUnits();
144 if (EnablePrecomputePhysRegs) {
155 OS <<
"********** INTERVALS **********\n";
158 for (
unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
177 void LiveIntervals::printInstrs(
raw_ostream &OS)
const {
178 OS <<
"********** MACHINEINSTRS **********\n";
179 MF->
print(OS, Indexes);
182 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 188 LiveInterval* LiveIntervals::createInterval(
unsigned reg) {
194 void LiveIntervals::computeVirtRegInterval(
LiveInterval &LI) {
195 assert(LRCalc &&
"LRCalc not initialized.");
196 assert(LI.
empty() &&
"Should only compute empty intervals.");
199 computeDeadValues(LI,
nullptr);
202 void LiveIntervals::computeVirtRegs() {
211 void LiveIntervals::computeRegMasks() {
216 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
217 RMB.first = RegMaskSlots.size();
220 if (
const uint32_t *
Mask = MBB.getBeginClobberMask(TRI)) {
237 if (
const uint32_t *
Mask = MBB.getEndClobberMask(TRI)) {
238 assert(!MBB.empty() &&
"empty return block?");
239 RegMaskSlots.push_back(
245 RMB.second = RegMaskSlots.size() - RMB.first;
263 void LiveIntervals::computeRegUnitRange(
LiveRange &LR,
unsigned Unit) {
264 assert(LRCalc &&
"LRCalc not initialized.");
272 bool IsReserved =
false;
274 bool IsRootReserved =
true;
277 unsigned Reg = *Super;
283 IsRootReserved =
false;
285 IsReserved |= IsRootReserved;
288 "reserved computation mismatch");
296 unsigned Reg = *Super;
298 LRCalc->extendToUses(LR, Reg);
311 void LiveIntervals::computeLiveInRegUnits() {
313 LLVM_DEBUG(
dbgs() <<
"Computing live-in reg-units in ABI blocks.\n");
321 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
327 for (
const auto &LI : MBB.liveins()) {
329 unsigned Unit = *Units;
346 for (
unsigned Unit : NewRanges)
347 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
352 for (
VNInfo *VNI : VNIs) {
360 void LiveIntervals::extendSegmentsToUses(
LiveRange &Segments,
361 ShrinkToUsesWorkList &WorkList,
373 if ((SR.LaneMask & M).any()) {
374 assert(SR.LaneMask == M &&
"Expecting lane masks to match exactly");
382 const LiveRange &OldRange = getSubRange(LI, LaneMask);
385 while (!WorkList.empty()) {
387 VNInfo *VNI = WorkList.back().second;
394 assert(ExtVNI == VNI &&
"Unexpected existing value number");
398 !UsedPHIs.
insert(VNI).second)
402 if (!LiveOut.
insert(Pred).second)
407 WorkList.push_back(std::make_pair(Stop, PVNI));
418 if (!LiveOut.
insert(Pred).second)
422 assert(OldVNI == VNI &&
"Wrong value out of predecessor");
424 WorkList.push_back(std::make_pair(Stop, VNI));
430 "Missing value out of predecessor for main range");
434 "Missing value out of predecessor for subrange");
445 "Can only shrink virtual registers");
448 bool NeedsCleanup =
false;
461 unsigned Reg = li->
reg;
463 if (
UseMI.isDebugValue() || !
UseMI.readsVirtualRegister(Reg))
474 <<
"Warning: Instr claims to read non-existent value in " 483 WorkList.
push_back(std::make_pair(Idx, VNI));
495 bool CanSeparate = computeDeadValues(*li, dead);
502 bool MayHaveSplitComponents =
false;
508 assert(I != LI.
end() &&
"Missing segment for VNI");
512 unsigned VReg = LI.
reg;
526 LLVM_DEBUG(
dbgs() <<
"Dead PHI at " << Def <<
" may separate interval\n");
527 MayHaveSplitComponents =
true;
531 assert(MI &&
"No instruction defining live value");
539 return MayHaveSplitComponents;
545 "Can only shrink virtual registers");
556 unsigned SubReg = MO.getSubReg();
559 if ((LaneMask & SR.
LaneMask).none())
581 WorkList.
push_back(std::make_pair(Idx, VNI));
587 extendSegmentsToUses(NewLR, WorkList, Reg, SR.
LaneMask);
597 assert(Segment !=
nullptr &&
"Missing segment for VNI");
603 <<
" may separate interval\n");
615 assert(LRCalc &&
"LRCalc not initialized.");
618 LRCalc->
extend(LR, Idx, 0, Undefs);
640 if (EndPoints) EndPoints->
push_back(MBBEnd);
655 std::tie(MBBStart, MBBEnd) = Indexes->
getMBBRange(MBB);
673 if (EndPoints) EndPoints->
push_back(MBBEnd);
711 for (
const LiveInterval::SubRange &SR : LI.
subranges()) {
712 SRs.push_back(std::make_pair(&SR, SR.find(LI.
begin()->end)));
721 if (RI->end.isBlock())
735 for (
auto &
RUP : RU) {
737 LiveRange::const_iterator &
I =
RUP.second;
738 if (I == RURange.
end())
741 if (I == RURange.
end() || I->start >= RI->end)
763 for (
auto &SRP : SRs) {
764 const LiveInterval::SubRange &SR = *SRP.first;
765 LiveRange::const_iterator &
I = SRP.second;
769 if (I == SR.
end() || I->start >= RI->end)
777 bool IsFullWrite =
false;
779 if (!MO.isReg() || MO.getReg() !=
Reg)
784 if ((UseMask & ~DefinedLanesMask).any())
786 }
else if (MO.getSubReg() == 0) {
799 LiveRange::const_iterator
N = std::next(RI);
800 if (N != LI.
end() && N->start == RI->end)
834 return MBB1 == MBB2 ? MBB1 :
nullptr;
912 assert(*SlotI >= LiveI->start);
914 while (*SlotI < LiveI->
end) {
924 if (++SlotI == SlotE)
932 while (*SlotI < LiveI->start)
933 if (++SlotI == SlotE)
957 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
958 UpdateFlags(UpdateFlags) {}
973 LLVM_DEBUG(
dbgs() <<
"handleMove " << OldIdx <<
" -> " << NewIdx <<
": " 975 bool hasRegMask =
false;
995 unsigned SubReg = MO.getSubReg();
999 if ((S.LaneMask & LaneMask).none())
1001 updateRange(S, Reg, S.LaneMask);
1011 if (
LiveRange *LR = getRegUnitLI(*Units))
1015 updateRegMaskSlots();
1022 if (!Updated.
insert(&LR).second)
1033 dbgs() <<
":\t" << LR <<
'\n';
1038 handleMoveUp(LR, Reg, LaneMask);
1065 if (MO->isReg() && MO->isUse())
1066 MO->setIsKill(
false);
1077 if (NewIdxIn == E ||
1083 OldIdxIn->end = Next->start;
1090 OldIdxIn->end = NewIdx.
getRegSlot(OldIdxIn->end.isEarlyClobber());
1100 OldIdxOut = OldIdxIn;
1107 VNInfo *OldIdxVNI = OldIdxOut->valno;
1108 assert(OldIdxVNI->
def == OldIdxOut->start &&
"Inconsistent def");
1114 OldIdxVNI->
def = NewIdxDef;
1115 OldIdxOut->start = OldIdxVNI->
def;
1125 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1126 if (!OldIdxDefIsDead &&
1130 if (OldIdxOut != LR.
begin() &&
1132 OldIdxOut->start)) {
1137 IPrev->end = OldIdxOut->end;
1141 assert(INext != E &&
"Must have following segment");
1147 INext->start = OldIdxOut->end;
1148 INext->valno->
def = INext->start;
1151 if (AfterNewIdx == E) {
1156 std::copy(std::next(OldIdxOut), E, OldIdxOut);
1161 DefVNI->
def = NewIdxDef;
1164 Prev->end = NewIdxDef;
1170 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1178 Prev->valno->def = NewIdxDef;
1181 DefVNI->
def = Prev->start;
1186 DefVNI->
def = NewIdxDef;
1187 assert(DefVNI != AfterNewIdx->valno);
1193 if (AfterNewIdx != E &&
1197 assert(AfterNewIdx->valno != OldIdxVNI &&
"Multiple defs of value?");
1205 assert(AfterNewIdx != OldIdxOut &&
"Inconsistent iterators");
1206 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1209 VNInfo *NewSegmentVNI = OldIdxVNI;
1210 NewSegmentVNI->
def = NewIdxDef;
1240 =
std::max(OldIdxIn->start.getDeadSlot(),
1241 NewIdx.
getRegSlot(OldIdxIn->end.isEarlyClobber()));
1242 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1245 OldIdxOut = std::next(OldIdxIn);
1249 OldIdxOut = OldIdxIn;
1250 OldIdxIn = OldIdxOut != LR.
begin() ? std::prev(OldIdxOut) :
E;
1257 VNInfo *OldIdxVNI = OldIdxOut->valno;
1258 assert(OldIdxVNI->
def == OldIdxOut->start &&
"Inconsistent def");
1259 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1265 assert(NewIdxOut->valno != OldIdxVNI &&
1266 "Same value defined more than once?");
1268 if (!OldIdxDefIsDead) {
1271 OldIdxVNI->
def = NewIdxDef;
1272 OldIdxOut->start = NewIdxDef;
1281 if (!OldIdxDefIsDead) {
1283 if (OldIdxIn != E &&
1289 OldIdxVNI = OldIdxIn->valno;
1291 SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;
1293 if (OldIdxIn != LR.
begin() &&
1301 NewDefEndPoint = std::min(OldIdxIn->start,
1302 std::next(NewIdxOut)->start);
1306 OldIdxOut->valno->def = OldIdxIn->start;
1313 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1324 Next->valno->def = SplitPos;
1329 NewSegment->valno->def = SplitPos;
1333 OldIdxOut->start = NewIdxDef;
1334 OldIdxVNI->
def = NewIdxDef;
1338 }
else if (OldIdxIn != E
1349 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1354 NewIdxOut->start, NewIdxDef.
getRegSlot(), NewIdxOut->valno);
1357 OldIdxVNI->
def = NewIdxDef;
1359 for (
auto Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx)
1360 Idx->valno = OldIdxVNI;
1366 if (MO->isReg() && !MO->isUse())
1367 MO->setIsDead(
false);
1374 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1377 VNInfo *NewSegmentVNI = OldIdxVNI;
1380 NewSegmentVNI->
def = NewIdxDef;
1385 void updateRegMaskSlots() {
1389 "No RegMask at OldIdx.");
1391 assert((RI == LIS.RegMaskSlots.begin() ||
1393 "Cannot move regmask instruction above another call");
1394 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1396 "Cannot move regmask instruction below another call");
1407 unsigned SubReg = MO.getSubReg();
1408 if (SubReg != 0 && LaneMask.
any()
1414 if (InstSlot > LastUse && InstSlot < OldIdx)
1422 assert(Before < OldIdx &&
"Expected upwards move");
1431 if (
MI->getParent() == MBB)
1435 while (MII != Begin) {
1436 if ((--MII)->isDebugInstr())
1446 if (MO->isReg() && !MO->isUndef() &&
1460 "Cannot move instruction in bundle");
1461 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1462 Indexes->removeMachineInstrFromMaps(MI);
1463 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1466 "Cannot handle moves across basic block boundaries.");
1468 HMEditor HME(*
this, *
MRI, *
TRI, OldIndex, NewIndex, UpdateFlags);
1475 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1476 SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1477 HMEditor HME(*
this, *
MRI, *
TRI, OldIndex, NewIndex, UpdateFlags);
1488 if (LII == LR.
begin()) {
1493 if (LII != LR.
end() && LII->start < endIdx)
1494 lastUseIdx = LII->end;
1519 if ((Mask & LaneMask).none())
1523 if (!isStartValid) {
1524 if (LII->end.isDead()) {
1526 if (LII != LR.
begin())
1527 prevStart = std::prev(LII)->start;
1533 LII = LR.
find(prevStart);
1552 }
else if (LII->start != instrIdx.
getRegSlot()) {
1562 }
else if (MO.
isUse()) {
1566 if (!isEndValid && !LII->end.isBlock())
1582 while (Begin != MBB->
begin() && !Indexes->hasIndex(*Begin))
1584 while (End != MBB->
end() && !Indexes->hasIndex(*End))
1588 if (End == MBB->
end())
1593 Indexes->repairIndexesInRange(MBB, Begin, End);
1602 MOI != MOE; ++MOI) {
1610 for (
unsigned Reg : OrigRegs) {
1620 repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask);
1622 repairOldRegInRange(Begin, End, endIdx, LI, Reg);
1638 if (VNI !=
nullptr) {
1645 if (
VNInfo *SVNI = S.getVNInfoAt(Pos))
1647 S.removeValNo(SVNI);
1655 unsigned NumComp = ConEQ.
Classify(LI);
1658 LLVM_DEBUG(
dbgs() <<
" Split " << NumComp <<
" components: " << LI <<
'\n');
1659 unsigned Reg = LI.
reg;
1661 for (
unsigned I = 1;
I < NumComp; ++
I) {
1662 Register NewVReg =
MRI->createVirtualRegister(RegClass);
1670 assert(LRCalc &&
"LRCalc not initialized.");
1672 LRCalc->constructMainRangeFromSubranges(LI);
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
const_iterator end(StringRef path)
Get end iterator over path.
mop_iterator operands_end()
A common definition of LaneBitmask for use in TableGen and CodeGen.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool isReserved(Register PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex def
The index of the defining instruction.
void createDeadDefs(LiveRange &LR, unsigned Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
void updateAllRanges(MachineInstr *MI)
Update all live ranges touched by MI, assuming a move from OldIdx to NewIdx.
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
LaneBitmask getMaxLaneMaskForVReg(unsigned Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
This class represents lattice values for constants.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
void removePhysRegDefAt(unsigned Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
A Module instance is used to store all the information related to an LLVM module. ...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Segments::iterator iterator
void push_back(const T &Elt)
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
LiveInterval - This class represents the liveness of a register, or stack slot.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
iterator_range< use_nodbg_iterator > use_nodbg_operands(unsigned Reg) const
MIBundleOperands - Iterate over all operands in a bundle of machine instructions. ...
ArrayRef< const uint32_t * > getRegMaskBits() const
Returns an array of register mask pointers corresponding to getRegMaskSlots().
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position...
bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
unsigned getSubReg() const
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
A live range for subregisters.
bool isValid() const
Returns true if this is a valid index.
This represents a simple continuous liveness interval for a value.
unsigned const TargetRegisterInfo * TRI
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
void markUnused()
Mark this value as unused.
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.
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
VNInfo - Value Number Information.
void print(raw_ostream &O, const Module *=nullptr) const override
Implement the dump method.
iterator_range< mop_iterator > operands()
bool checkRegMaskInterference(LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
void flushSegmentSet()
Flush segment set into the regular segment vector.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
LiveInterval::Segment addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst)
Given a register and an instruction, adds a live segment from that instruction to the end of its MBB...
iterator_range< succ_iterator > successors()
This class represents the liveness of a register, stack slot, etc.
bool isUnused() const
Returns true if this value is unused.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
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...
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
void verify() const
Walk the range and assert if any invariants fail to hold.
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
MCSuperRegIterator enumerates all super-registers of Reg.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
VNInfo::Allocator & getVNInfoAllocator()
iterator_range< subrange_iterator > subranges()
Result of a LiveRange query.
static constexpr LaneBitmask getAll()
SlotIndex getInstructionIndex(const MachineInstr &MI) const
Returns the base index for the given instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
static constexpr LaneBitmask getNone()
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
bool hasRegUnit(unsigned Reg, unsigned RegUnit) const
Returns true if Reg contains RegUnit.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
bool isValid() const
isValid - Returns true until all the operands have been visited.
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", "Live Interval Analysis", false, false) INITIALIZE_PASS_END(LiveIntervals
bool hasInterval(Register Reg) const
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range...
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
void setRegisterDefReadUndef(Register Reg, bool IsUndef=true)
Mark all subregister defs of register Reg with the undef flag.
static void createSegmentsForValues(LiveRange &LR, iterator_range< LiveInterval::vni_iterator > VNIs)
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
AnalysisUsage & addPreservedID(const void *ID)
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
virtual const TargetInstrInfo * getInstrInfo() const
char & LiveIntervalsID
LiveIntervals - This analysis keeps track of the live ranges of virtual and physical registers...
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
bool allDefsAreDead() const
Return true if all the defs of this instruction are dead.
LiveRange * getCachedRegUnit(unsigned Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
initializer< Ty > init(const Ty &Val)
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
bool subRegLivenessEnabled() const
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void swap(SmallVectorImpl &RHS)
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
bool isBundled() const
Return true if this instruction part of a bundle.
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval *> &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Represent the analysis usage information of a pass.
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
void initializeLiveIntervalsPass(PassRegistry &)
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr *> *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses...
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions...
LiveInterval & getInterval(Register Reg)
HMEditor(LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
iterator_range< pred_iterator > predecessors()
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< unsigned > OrigRegs)
Update live intervals for instructions in a range of iterators.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
bool isDebugInstr() const
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction, if any.
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
unsigned id
The ID number of this value.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Toolkit used by handleMove to trim or extend live intervals.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Align max(MaybeAlign Lhs, Align Rhs)
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Segments::const_iterator const_iterator
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
MachineOperand class - Representation of each machine instruction operand.
Live Interval static false cl::opt< bool > EnablePrecomputePhysRegs("precompute-phys-liveness", cl::Hidden, cl::desc("Eagerly compute live intervals for all physreg units."))
bool isReservedRegUnit(unsigned Unit) const
Returns true when the given register unit is considered reserved.
LiveRange * getRegUnitLI(unsigned Unit)
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx. ...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx...
A range adaptor for a pair of iterators.
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 ...
bool hasAtLeastOneValue() const
cl::opt< bool > UseSegmentSetForPhysRegs
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
typename SuperClass::iterator iterator
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
const MachineBasicBlock * getParent() const
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
pointer data()
Return a pointer to the vector's buffer, even if empty().
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
Register getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
constexpr bool any() const
uint64_t getEntryFreq() const
AnalysisUsage & addRequiredTransitiveID(char &ID)
AnalysisUsage & addRequiredTransitive()
bool shouldTrackSubRegLiveness(const TargetRegisterClass &RC) const
Returns true if liveness for register class RC should be tracked at the subregister level...
SlotIndexes * getSlotIndexes() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
~LiveIntervals() override
iterator_range< reg_instr_iterator > reg_instructions(unsigned Reg) const
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
mop_iterator operands_begin()
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
bool reg_empty(unsigned RegNo) const
reg_empty - Return true if there are no instructions using or defining the specified register (it may...
void handleMoveIntoBundle(MachineInstr &MI, MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals for operands of MI so that they begin/end on the SlotIndex for BundleStart.
This class implements an extremely fast bulk output stream that can only output to a stream...
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none...
bool isValid() const
Check if the iterator is at the end of the list.
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
Register getReg() const
getReg - Returns the register number.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
OutputIt copy(R &&Range, OutputIt Out)
void clearRegisterKills(Register Reg, const TargetRegisterInfo *RegInfo)
Clear all kill flags affecting Reg.
SlotIndex - An opaque wrapper around machine indexes.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
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...
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
ArrayRef< const uint32_t * > getRegMaskBitsInBlock(unsigned MBBNum) const
Returns an array of mask pointers corresponding to getRegMaskSlotsInBlock(MBBNum).
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block...
Wrapper class representing virtual and physical registers.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos...