LLVM 20.0.0git
|
LiveInterval - This class represents the liveness of a register, or stack slot. More...
#include "llvm/CodeGen/LiveInterval.h"
Classes | |
class | SingleLinkedListIterator |
class | SubRange |
A live range for subregisters. More... | |
Public Types | |
using | super = LiveRange |
using | subrange_iterator = SingleLinkedListIterator< SubRange > |
using | const_subrange_iterator = SingleLinkedListIterator< const SubRange > |
Public Types inherited from llvm::LiveRange | |
using | Segments = SmallVector< Segment, 2 > |
using | VNInfoList = SmallVector< VNInfo *, 2 > |
using | SegmentSet = std::set< Segment > |
using | iterator = Segments::iterator |
using | const_iterator = Segments::const_iterator |
using | vni_iterator = VNInfoList::iterator |
using | const_vni_iterator = VNInfoList::const_iterator |
Public Member Functions | |
Register | reg () const |
float | weight () const |
void | incrementWeight (float Inc) |
void | setWeight (float Value) |
LiveInterval (unsigned Reg, float Weight) | |
~LiveInterval () | |
subrange_iterator | subrange_begin () |
subrange_iterator | subrange_end () |
const_subrange_iterator | subrange_begin () const |
const_subrange_iterator | subrange_end () const |
iterator_range< subrange_iterator > | subranges () |
iterator_range< const_subrange_iterator > | subranges () const |
SubRange * | createSubRange (BumpPtrAllocator &Allocator, LaneBitmask LaneMask) |
Creates a new empty subregister live range. | |
SubRange * | createSubRangeFrom (BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom) |
Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom . | |
bool | hasSubRanges () const |
Returns true if subregister liveness information is available. | |
void | clearSubRanges () |
Removes all subregister liveness information. | |
void | removeEmptySubRanges () |
Removes all subranges without any segments (subranges without segments are not considered valid and should only exist temporarily). | |
unsigned | getSize () const |
getSize - Returns the sum of sizes of all the LiveRange's. | |
bool | isSpillable () const |
isSpillable - Can this interval be spilled? | |
void | markNotSpillable () |
markNotSpillable - Mark interval as not spillable | |
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 <def,read-undef> definitions. | |
void | refineSubRanges (BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0) |
Refines the subranges to support LaneMask . | |
bool | operator< (const LiveInterval &other) const |
void | print (raw_ostream &OS) const |
void | dump () const |
void | verify (const MachineRegisterInfo *MRI=nullptr) const |
Walks the interval and assert if any invariants fail to hold. | |
Public Member Functions inherited from llvm::LiveRange | |
iterator | begin () |
iterator | end () |
const_iterator | begin () const |
const_iterator | end () const |
vni_iterator | vni_begin () |
vni_iterator | vni_end () |
const_vni_iterator | vni_begin () const |
const_vni_iterator | vni_end () const |
iterator_range< vni_iterator > | vnis () |
iterator_range< const_vni_iterator > | vnis () const |
LiveRange (bool UseSegmentSet=false) | |
Constructs a new LiveRange object. | |
LiveRange (const LiveRange &Other, BumpPtrAllocator &Allocator) | |
Constructs a new LiveRange object by copying segments and valnos from another LiveRange. | |
void | assign (const LiveRange &Other, BumpPtrAllocator &Allocator) |
Copies values numbers and live segments from Other into this range. | |
iterator | advanceTo (iterator I, SlotIndex Pos) |
advanceTo - Advance the specified iterator to point to the Segment containing the specified position, or end() if the position is past the end of the range. | |
const_iterator | advanceTo (const_iterator I, SlotIndex Pos) const |
iterator | find (SlotIndex Pos) |
find - Return an iterator pointing to the first segment that ends after Pos, or end(). | |
const_iterator | find (SlotIndex Pos) const |
void | clear () |
size_t | size () const |
bool | hasAtLeastOneValue () const |
bool | containsOneValue () const |
unsigned | getNumValNums () const |
VNInfo * | getValNumInfo (unsigned ValNo) |
getValNumInfo - Returns pointer to the specified val#. | |
const VNInfo * | getValNumInfo (unsigned ValNo) const |
bool | containsValue (const VNInfo *VNI) const |
containsValue - Returns true if VNI belongs to this range. | |
VNInfo * | getNextValue (SlotIndex Def, VNInfo::Allocator &VNInfoAllocator) |
getNextValue - Create a new value number and return it. | |
VNInfo * | createDeadDef (SlotIndex Def, VNInfo::Allocator &VNIAlloc) |
createDeadDef - Make sure the range has a value defined at Def. | |
VNInfo * | createDeadDef (VNInfo *VNI) |
Create a def of value VNI . | |
VNInfo * | createValueCopy (const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator) |
Create a copy of the given value. | |
void | RenumberValues () |
RenumberValues - Renumber all values in order of appearance and remove unused values. | |
VNInfo * | MergeValueNumberInto (VNInfo *V1, VNInfo *V2) |
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent. | |
void | MergeSegmentsInAsValue (const LiveRange &RHS, VNInfo *LHSValNo) |
Merge all of the live segments of a specific val# in RHS into this live range as the specified value number. | |
void | MergeValueInAsValue (const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo) |
MergeValueInAsValue - Merge all of the segments of a specific val# in RHS into this live range as the specified value number. | |
bool | empty () const |
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 | expiredAt (SlotIndex index) const |
bool | liveAt (SlotIndex index) const |
const Segment * | getSegmentContaining (SlotIndex Idx) const |
Return the segment that contains the specified index, or null if there is none. | |
Segment * | getSegmentContaining (SlotIndex Idx) |
Return the live segment that contains the specified index, or null if there is none. | |
VNInfo * | getVNInfoAt (SlotIndex Idx) const |
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. | |
VNInfo * | getVNInfoBefore (SlotIndex Idx) const |
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx, or NULL. | |
iterator | FindSegmentContaining (SlotIndex Idx) |
Return an iterator to the segment that contains the specified index, or end() if there is none. | |
const_iterator | FindSegmentContaining (SlotIndex Idx) const |
bool | overlaps (const LiveRange &other) const |
overlaps - Return true if the intersection of the two live ranges is not empty. | |
bool | overlaps (const LiveRange &Other, const CoalescerPair &CP, const SlotIndexes &) const |
overlaps - Return true if the two ranges have overlapping segments that are not coalescable according to CP. | |
bool | overlaps (SlotIndex Start, SlotIndex End) const |
overlaps - Return true if the live range overlaps an interval specified by [Start, End). | |
bool | overlapsFrom (const LiveRange &Other, const_iterator StartPos) const |
overlapsFrom - Return true if the intersection of the two live ranges is not empty. | |
bool | covers (const LiveRange &Other) const |
Returns true if all segments of the Other live range are completely covered by this live range. | |
iterator | addSegment (Segment S) |
Add the specified Segment to this range, merging segments as appropriate. | |
std::pair< VNInfo *, bool > | extendInBlock (ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill) |
Attempt to extend a value defined after StartIdx to include Use . | |
VNInfo * | extendInBlock (SlotIndex StartIdx, SlotIndex Kill) |
Simplified version of the above "extendInBlock", which assumes that no register lanes are undefined by <def,read-undef> operands. | |
void | join (LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo) |
join - Join two live ranges (this, and other) together. | |
bool | isLocal (SlotIndex Start, SlotIndex End) const |
True iff this segment is a single segment that lies between the specified boundaries, exclusively. | |
void | removeSegment (SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false) |
Remove the specified interval from this live range. | |
void | removeSegment (Segment S, bool RemoveDeadValNo=false) |
iterator | removeSegment (iterator I, bool RemoveDeadValNo=false) |
Remove segment pointed to by iterator I from this range. | |
void | removeValNoIfDead (VNInfo *ValNo) |
Mark ValNo for deletion if no segments in this range use it. | |
LiveQueryResult | Query (SlotIndex Idx) const |
Query Liveness at Idx. | |
void | removeValNo (VNInfo *ValNo) |
removeValNo - Remove all the segments defined by the specified value#. | |
bool | isZeroLength (SlotIndexes *Indexes) const |
Returns true if the live range is zero length, i.e. | |
bool | isLiveAtIndexes (ArrayRef< SlotIndex > Slots) const |
bool | operator< (const LiveRange &other) const |
bool | isUndefIn (ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const |
Returns true if there is an explicit "undef" between Begin End . | |
void | flushSegmentSet () |
Flush segment set into the regular segment vector. | |
template<typename Range , typename OutputIt > | |
bool | findIndexesLiveAt (Range &&R, OutputIt O) const |
Stores indexes from the input index sequence R at which this LiveRange is live to the output O iterator. | |
void | print (raw_ostream &OS) const |
void | dump () const |
void | verify () const |
Walk the range and assert if any invariants fail to hold. | |
Additional Inherited Members | |
Public Attributes inherited from llvm::LiveRange | |
Segments | segments |
VNInfoList | valnos |
std::unique_ptr< SegmentSet > | segmentSet |
Protected Member Functions inherited from llvm::LiveRange | |
void | append (const LiveRange::Segment S) |
Append a segment to the list of segments. | |
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition at line 687 of file LiveInterval.h.
Definition at line 766 of file LiveInterval.h.
Definition at line 765 of file LiveInterval.h.
using llvm::LiveInterval::super = LiveRange |
Definition at line 689 of file LiveInterval.h.
|
inline |
Definition at line 723 of file LiveInterval.h.
|
inline |
Definition at line 725 of file LiveInterval.h.
References clearSubRanges().
void LiveInterval::clearSubRanges | ( | ) |
Removes all subregister liveness information.
Definition at line 861 of file LiveInterval.cpp.
References I.
Referenced by ~LiveInterval().
void LiveInterval::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 <def,read-undef> definitions.
Definition at line 965 of file LiveInterval.cpp.
References assert(), llvm::SlotIndexes::getInstructionIndex(), llvm::SlotIndex::getRegSlot(), MI, MRI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), reg(), SubReg, and TRI.
|
inline |
Creates a new empty subregister live range.
The range is added at the beginning of the subrange list; subrange iterators stay valid.
Definition at line 792 of file LiveInterval.h.
References Allocator, and Range.
Referenced by llvm::ConnectedVNInfoEqClasses::Distribute(), and refineSubRanges().
|
inline |
Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom
.
Definition at line 801 of file LiveInterval.h.
References Allocator, and Range.
Referenced by llvm::LiveIntervalCalc::calculate(), and refineSubRanges().
LLVM_DUMP_METHOD void LiveInterval::dump | ( | ) | const |
Definition at line 1052 of file LiveInterval.cpp.
References llvm::dbgs().
unsigned LiveInterval::getSize | ( | ) | const |
getSize - Returns the sum of sizes of all the LiveRange's.
Definition at line 958 of file LiveInterval.cpp.
References llvm::LiveRange::segments.
Referenced by llvm::MLPriorityAdvisor::getPriorityImpl(), and llvm::VirtRegAuxInfo::weightCalcHelper().
|
inline |
Returns true if subregister liveness information is available.
Definition at line 810 of file LiveInterval.h.
Referenced by llvm::LiveIntervals::addKillFlags(), llvm::GCNDownwardRPTracker::advanceBeforeNext(), llvm::LiveRangeEdit::allUsesAvailableAt(), llvm::LiveIntervalCalc::calculate(), llvm::ConnectedVNInfoEqClasses::Distribute(), llvm::SIRegisterInfo::findReachingDef(), foreachUnit(), getLanesWithProperty(), llvm::getLiveLaneMask(), getRegLiveThroughMask(), llvm::LiveIntervals::repairIntervalsInRange(), and llvm::LiveIntervals::HMEditor::updateAllRanges().
|
inline |
Definition at line 720 of file LiveInterval.h.
|
inline |
isSpillable - Can this interval be spilled?
Definition at line 826 of file LiveInterval.h.
References llvm::huge_valf.
Referenced by llvm::LiveRangeEdit::createFrom(), and llvm::VirtRegAuxInfo::weightCalcHelper().
|
inline |
markNotSpillable - Mark interval as not spillable
Definition at line 829 of file LiveInterval.h.
References llvm::huge_valf.
Referenced by llvm::LiveRangeEdit::createFrom(), and llvm::VirtRegAuxInfo::weightCalcHelper().
|
inline |
Definition at line 883 of file LiveInterval.h.
References llvm::LiveRange::beginIndex().
void LiveInterval::print | ( | raw_ostream & | OS | ) | const |
Definition at line 1034 of file LiveInterval.cpp.
References OS, and llvm::printReg().
Referenced by llvm::operator<<().
void LiveInterval::refineSubRanges | ( | BumpPtrAllocator & | Allocator, |
LaneBitmask | LaneMask, | ||
std::function< void(LiveInterval::SubRange &)> | Apply, | ||
const SlotIndexes & | Indexes, | ||
const TargetRegisterInfo & | TRI, | ||
unsigned | ComposeSubRegIdx = 0 |
||
) |
Refines the subranges to support LaneMask
.
This may only be called for LI.hasSubrange()==true. Subregister ranges are split or created until LaneMask
can be matched exactly. Mod
is executed on the matching subranges.
Example: Given an interval with subranges with lanemasks L0F00, L00F0 and L000F, refining for mask L0018. Will split the L00F0 lane into L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod function will be applied to the L0010 and L0008 subranges.
Indexes
and TRI
are required to clean up the VNIs that don't define the related lane masks after they get shrunk. E.g., when L000F gets split into L0007 and L0008 maybe only a subset of the VNIs that defined L000F defines L0007.
The clean up of the VNIs need to look at the actual instructions to decide what is or is not live at a definition point. If the update of the subranges occurs while the IR does not reflect these changes, ComposeSubRegIdx
can be used to specify how the definition are going to be rewritten. E.g., let say we want to merge: V1.sub1:<2 x s32> = COPY V2.sub3:<4 x s32> We do that by choosing a class where sub1:<2 x s32> and sub3:<4 x s32> overlap, i.e., by choosing a class where we can find "offset + 1 == 3". Put differently we align V2's sub3 with V1's sub1: V2: sub0 sub1 sub2 sub3 V1: <offset> sub0 sub1
This offset will look like a composed subregidx in the class: V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32> => V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32>
Now if we didn't rewrite the uses and def of V1, all the checks for V1 need to account for this offset. This happens during coalescing where we update the live-ranges while still having the old IR around because updating the IR on-the-fly would actually clobber some information on how the live-ranges that are being updated look like.
Definition at line 919 of file LiveInterval.cpp.
References Allocator, llvm::LaneBitmask::any(), createSubRange(), createSubRangeFrom(), llvm::LiveInterval::SubRange::LaneMask, llvm::LaneBitmask::none(), reg(), stripValuesNotDefiningMask(), subranges(), and TRI.
Referenced by llvm::LiveIntervalCalc::calculate().
|
inline |
Definition at line 718 of file LiveInterval.h.
Referenced by llvm::RegAllocBase::allocatePhysRegs(), llvm::LiveRegMatrix::assign(), assignedRegPartiallyOverlaps(), llvm::LiveIntervalCalc::calculate(), llvm::LiveRangeEdit::calculateRegClassAndHint(), canMemFoldInlineAsm(), llvm::RegAllocEvictionAdvisor::canReassign(), llvm::LiveIntervals::checkRegMaskInterference(), llvm::LiveRegMatrix::checkRegMaskInterference(), llvm::LiveRegMatrix::checkRegUnitInterference(), computeSubRangeUndefs(), llvm::LiveIntervalCalc::constructMainRangeFromSubranges(), llvm::ConnectedVNInfoEqClasses::Distribute(), llvm::LiveRangeEdit::eliminateDeadDefs(), llvm::RegAllocBase::enqueue(), llvm::getLiveLaneMask(), llvm::LiveRegMatrix::getOneVReg(), llvm::RegAllocEvictionAdvisor::getOrderLimit(), llvm::LiveRangeEdit::getReg(), llvm::RAGreedy::ExtraRegInfo::getStage(), llvm::SplitAnalysis::isOriginalEndpoint(), llvm::VirtRegAuxInfo::isRematerializable(), llvm::SplitEditor::leaveIntvAtTop(), readsLaneSubset(), refineSubRanges(), llvm::RAGreedy::ExtraRegInfo::setStage(), llvm::TargetRegisterInfo::shouldRegionSplitForVirtReg(), llvm::LiveIntervals::shrinkToUses(), llvm::LiveIntervals::splitSeparateComponents(), llvm::LiveRegMatrix::unassign(), and llvm::VirtRegAuxInfo::weightCalcHelper().
void LiveInterval::removeEmptySubRanges | ( | ) |
Removes all subranges without any segments (subranges without segments are not considered valid and should only exist temporarily).
Definition at line 842 of file LiveInterval.cpp.
References I.
Referenced by llvm::LiveIntervalCalc::calculate(), llvm::ConnectedVNInfoEqClasses::Distribute(), llvm::SplitEditor::finish(), llvm::LiveIntervals::removeVRegDefAt(), llvm::LiveIntervals::repairIntervalsInRange(), and llvm::LiveIntervals::shrinkToUses().
|
inline |
Definition at line 721 of file LiveInterval.h.
Referenced by llvm::VirtRegAuxInfo::calculateSpillWeightAndHint().
|
inline |
Definition at line 768 of file LiveInterval.h.
Referenced by subranges().
|
inline |
Definition at line 775 of file LiveInterval.h.
|
inline |
Definition at line 771 of file LiveInterval.h.
Referenced by subranges().
|
inline |
Definition at line 778 of file LiveInterval.h.
|
inline |
Definition at line 782 of file LiveInterval.h.
References llvm::make_range(), subrange_begin(), and subrange_end().
Referenced by llvm::LiveIntervals::addKillFlags(), llvm::GCNDownwardRPTracker::advanceBeforeNext(), llvm::LiveRangeEdit::allUsesAvailableAt(), llvm::LiveIntervalCalc::calculate(), llvm::LiveIntervalCalc::constructMainRangeFromSubranges(), llvm::ConnectedVNInfoEqClasses::Distribute(), llvm::SIRegisterInfo::findReachingDef(), foreachUnit(), getLanesWithProperty(), llvm::getLiveLaneMask(), getRegLiveThroughMask(), getSubRangeForMask(), isDefInSubRange(), readsLaneSubset(), refineSubRanges(), llvm::LiveIntervals::removeVRegDefAt(), llvm::LiveIntervals::repairIntervalsInRange(), llvm::LiveIntervals::shrinkToUses(), subRangeLiveAt(), and llvm::LiveIntervals::HMEditor::updateAllRanges().
|
inline |
Definition at line 786 of file LiveInterval.h.
References llvm::make_range(), subrange_begin(), and subrange_end().
void LiveInterval::verify | ( | const MachineRegisterInfo * | MRI = nullptr | ) | const |
Walks the interval and assert if any invariants fail to hold.
Note that this is a no-op when asserts are disabled.
Definition at line 1074 of file LiveInterval.cpp.
References assert(), llvm::LiveRange::covers(), llvm::LaneBitmask::getAll(), MRI, and none.
|
inline |
Definition at line 719 of file LiveInterval.h.
Referenced by llvm::MLPriorityAdvisor::getPriorityImpl().