Go to the documentation of this file.
20 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
21 #define LLVM_CODEGEN_LIVEINTERVAL_H
46 class MachineRegisterInfo;
99 : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill)
136 return EarlyVal == LateVal ? nullptr : LateVal;
172 assert(
S <
E &&
"Cannot create empty or backwards segment");
182 assert((
S <
E) &&
"Backwards interval?");
194 return !(*
this ==
Other);
247 "Copying of LiveRanges with active SegmentSets is not supported");
257 "Copying of LiveRanges with active SegmentSets is not supported");
275 while (
I->end <= Pos) ++
I;
283 while (
I->end <= Pos) ++
I;
333 new (VNInfoAllocator)
VNInfo((
unsigned)
valnos.size(), def);
352 new (VNInfoAllocator)
VNInfo((
unsigned)
valnos.size(), *orig);
386 assert(!
empty() &&
"Call to beginIndex() on empty range.");
393 assert(!
empty() &&
"Call to endIndex() on empty range.");
403 return r !=
end() && r->start <=
index;
410 return I ==
end() ? nullptr : &*
I;
417 return I ==
end() ? nullptr : &*
I;
423 return I ==
end() ? nullptr :
I->valno;
431 return I ==
end() ? nullptr :
I->valno;
438 return I !=
end() &&
I->start <= Idx ?
I :
end();
443 return I !=
end() &&
I->start <= Idx ?
I :
end();
510 const int *ValNoAssignments,
511 const int *RHSValNoAssignments,
520 endIndex() < End.getBoundaryIndex();
526 bool RemoveDeadValNo =
false);
551 VNInfo *EarlyVal =
nullptr;
552 VNInfo *LateVal =
nullptr;
589 S.end.getBaseIndex())
602 return thisIndex < otherIndex;
610 return Begin <= Idx && Idx < End;
626 template <
typename Range,
typename OutputIt>
629 auto Idx = R.begin(), EndIdx = R.end();
632 while (Idx != EndIdx && Seg != EndSeg) {
635 if (Seg->end <= *Idx) {
644 if (NotLessStart == EndIdx)
647 if (NotLessEnd != NotLessStart) {
671 void append(
const LiveRange::Segment
S);
676 void markValNoForDeletion(
VNInfo *V);
711 SubRange *SubRanges =
nullptr;
745 return P !=
Other.operator->();
748 return P ==
Other.operator->();
788 appendSubRange(Range);
798 appendSubRange(Range);
804 return SubRanges !=
nullptr;
874 unsigned ComposeSubRegIdx = 0);
879 return std::tie(thisIndex, Reg) < std::tie(otherIndex, other.Reg);
891 void verify(
const MachineRegisterInfo *
MRI =
nullptr)
const;
896 void appendSubRange(SubRange *Range) {
897 Range->Next = SubRanges;
902 void freeSubRange(SubRange *
S);
916 raw_ostream &
operator<<(raw_ostream &OS,
const LiveRange::Segment &
S);
1023 #endif // LLVM_CODEGEN_LIVEINTERVAL_H
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
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 join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)
join - Join two live ranges (this, and other) together.
const_iterator FindSegmentContaining(SlotIndex Idx) const
This is an optimization pass for GlobalISel generic memory operations.
bool containsInterval(SlotIndex S, SlotIndex E) const
Return true if the given interval, [S, E), is covered by this segment.
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void flushSegmentSet()
Flush segment set into the regular segment vector.
void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
SingleLinkedListIterator< T > & operator++()
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
bool isValid() const
Returns true if this is a valid index.
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
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 print(raw_ostream &OS) const
bool isSpillable() const
isSpillable - Can this interval be spilled?
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
const_iterator advanceTo(const_iterator I, SlotIndex Pos) const
bool isDeadDef() const
Return true if this instruction has a dead def.
SingleLinkedListIterator< T > operator++(int)
This represents a simple continuous liveness interval for a value.
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
SlotIndex def
The index of the defining instruction.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
bool operator<(const Segment &Other) const
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 iterat...
void print(raw_ostream &OS) const
Result of a LiveRange query.
unsigned const TargetRegisterInfo * TRI
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
VNInfo * createValueCopy(const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
Create a copy of the given value.
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
SubRange(LaneBitmask LaneMask)
Constructs a new SubRange object.
const VNInfo * getValNumInfo(unsigned ValNo) const
void add(SlotIndex Start, SlotIndex End, VNInfo *VNI)
bool liveAt(SlotIndex index) const
std::set< Segment > SegmentSet
subrange_iterator subrange_begin()
bool covers(const LiveRange &Other) const
Returns true if all segments of the Other live range are completely covered by this live range.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const_subrange_iterator subrange_end() const
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
iterator_range< const_subrange_iterator > subranges() const
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool operator!=(const SingleLinkedListIterator< T > &Other) const
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
Segments::const_iterator const_iterator
Helper class for performant LiveRange bulk updates.
ConnectedVNInfoEqClasses(LiveIntervals &lis)
void clearSubRanges()
Removes all subregister liveness information.
bool isDirty() const
Return true if the LR is currently in an invalid state, and flush() needs to be called.
SingleLinkedListIterator< const SubRange > const_subrange_iterator
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
bool operator==(const SingleLinkedListIterator< T > &Other) const
Common register allocation spilling lr str lr
bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const
overlapsFrom - Return true if the intersection of the two live ranges is not empty.
void setDest(LiveRange *lr)
Select a different destination live range.
LiveInterval - This class represents the liveness of a register, or stack slot.
VNInfo(unsigned i, const VNInfo &orig)
VNInfo constructor, copies values from orig, except for the value number.
const_iterator end() const
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
void removeValNoIfDead(VNInfo *ValNo)
Mark ValNo for deletion if no segments in this range use it.
SlotIndex - An opaque wrapper around machine indexes.
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
subrange_iterator subrange_end()
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
void append(const LiveRange::Segment S)
Append a segment to the list of segments.
const_subrange_iterator subrange_begin() const
LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, bool Kill)
bool contains(SlotIndex I) const
Return true if the index is covered by this segment.
void print(raw_ostream &OS) const
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
bool operator<(const LiveInterval &other) const
LiveRange * getDest() const
Get the current destination live range.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
SingleLinkedListIterator(T *P)
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
void print(raw_ostream &) const
bool hasAtLeastOneValue() const
void incrementWeight(float Inc)
This class represents the liveness of a register, stack slot, etc.
unsigned id
The ID number of this value.
Allocate memory in an ever growing pool, as if by bump-pointer.
unsigned getNumValNums() const
bool operator<(int64_t V1, const APSInt &V2)
bool operator<(const LiveRange &other) const
bool expiredAt(SlotIndex index) const
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new LiveRange object by copying segments and valnos from another LiveRange.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
bool isLocal(SlotIndex Start, SlotIndex End) const
True iff this segment is a single segment that lies between the specified boundaries,...
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
LiveInterval(unsigned Reg, float Weight)
bool containsValue(const VNInfo *VNI) const
containsValue - Returns true if VNI belongs to this range.
typename SuperClass::const_iterator const_iterator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
Segment * getSegmentContaining(SlotIndex Idx)
Return the live segment that contains the specified index, or null if there is none.
unsigned getEqClass(const VNInfo *VNI) const
getEqClass - Classify creates equivalence classes numbered 0..N.
print Print MemDeps of function
bool containsOneValue() const
VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void flush()
Flush the updater state to LR so it is valid and contains all added segments.
iterator_range< vni_iterator > vnis()
void removeSegment(Segment S, bool RemoveDeadValNo=false)
bool operator==(const Segment &Other) const
A helper class for register coalescers.
SubRange(LaneBitmask LaneMask, const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new SubRange object by copying liveness from Other.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
void setWeight(float Value)
A live range for subregisters.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
const_iterator begin() const
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
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 ...
Segments::iterator iterator
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
const_vni_iterator vni_end() const
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
VNInfo - Value Number Information.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
bool operator!=(const Segment &Other) const
void copyFrom(VNInfo &src)
Copy from the parameter into this VNInfo.
void verify() const
Walk the range and assert if any invariants fail to hold.
LiveRangeUpdater(LiveRange *lr=nullptr)
Create a LiveRangeUpdater for adding segments to LR.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Segment(SlotIndex S, SlotIndex E, VNInfo *V)
@ Kill
The last use of a register.
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...
std::optional< std::vector< StOtherPiece > > Other
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
typename SuperClass::iterator iterator
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
A range adaptor for a pair of iterators.
LiveRange(bool UseSegmentSet=false)
Constructs a new LiveRange object.
const_vni_iterator vni_begin() const
VNInfoList::iterator vni_iterator
bool isUnused() const
Returns true if this value is unused.
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
iterator_range< const_vni_iterator > vnis() const
VNInfoList::const_iterator const_vni_iterator
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
SingleLinkedListIterator< SubRange > subrange_iterator
std::unique_ptr< SegmentSet > segmentSet
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
const_iterator find(SlotIndex Pos) const
LLVM Value Representation.
bool isKill() const
Return true if the live-in value is killed by this instruction.
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...
VNInfo(unsigned i, SlotIndex d)
VNInfo constructor.
void markUnused()
Mark this value as unused.
iterator_range< subrange_iterator > subranges()