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;
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;
510 const int *ValNoAssignments,
511 const int *RHSValNoAssignments,
527 bool RemoveDeadValNo =
false);
552 VNInfo *EarlyVal =
nullptr;
553 VNInfo *LateVal =
nullptr;
556 if (
I->start <=
Idx.getBaseIndex()) {
569 if (EarlyVal->
def ==
Idx.getBaseIndex())
603 return thisIndex < otherIndex;
627 template <
typename Range,
typename OutputIt>
630 auto Idx = R.begin(), EndIdx = R.end();
633 while (
Idx != EndIdx && Seg != EndSeg) {
636 if (Seg->end <= *
Idx) {
638 std::upper_bound(++Seg, EndSeg, *
Idx, [=](
auto V,
const auto &S) {
644 auto NotLessStart = std::lower_bound(
Idx, EndIdx, Seg->start);
645 if (NotLessStart == EndIdx)
647 auto NotLessEnd = std::lower_bound(NotLessStart, EndIdx, Seg->end);
648 if (NotLessEnd != NotLessStart) {
650 O = std::copy(NotLessStart, NotLessEnd, O);
672 void append(
const LiveRange::Segment S);
676 void addSegmentToSet(
Segment S);
677 void markValNoForDeletion(
VNInfo *V);
712 SubRange *SubRanges =
nullptr;
752 return P !=
Other.operator->();
755 return P ==
Other.operator->();
795 appendSubRange(
Range);
805 appendSubRange(
Range);
811 return SubRanges !=
nullptr;
881 unsigned ComposeSubRegIdx = 0);
886 return std::tie(thisIndex, Reg) < std::tie(otherIndex, other.Reg);
898 void verify(
const MachineRegisterInfo *
MRI =
nullptr)
const;
903 void appendSubRange(SubRange *
Range) {
904 Range->Next = SubRanges;
909 void freeSubRange(SubRange *S);
923 raw_ostream &
operator<<(raw_ostream &
OS,
const LiveRange::Segment &S);
unsigned const MachineRegisterInfo * MRI
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Equivalence classes for small integers.
A common definition of LaneBitmask for use in TableGen and CodeGen.
unsigned const TargetRegisterInfo * TRI
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Allocate memory in an ever growing pool, as if by bump-pointer.
A helper class for register coalescers.
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
ConnectedVNInfoEqClasses(LiveIntervals &lis)
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.
unsigned getEqClass(const VNInfo *VNI) const
getEqClass - Classify creates equivalence classes numbered 0..N.
SingleLinkedListIterator< T > operator++(int)
std::forward_iterator_tag iterator_category
SingleLinkedListIterator(T *P)
bool operator==(const SingleLinkedListIterator< T > &Other) const
bool operator!=(const SingleLinkedListIterator< T > &Other) const
SingleLinkedListIterator< T > & operator++()
A live range for subregisters.
void print(raw_ostream &OS) const
SubRange(LaneBitmask LaneMask)
Constructs a new SubRange object.
SubRange(LaneBitmask LaneMask, const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new SubRange object by copying liveness from Other.
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...
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
bool isSpillable() const
isSpillable - Can this interval be spilled?
bool hasSubRanges() const
Returns true if subregister liveness information is available.
const_subrange_iterator subrange_begin() const
SingleLinkedListIterator< SubRange > subrange_iterator
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
LiveInterval(unsigned Reg, float Weight)
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...
iterator_range< subrange_iterator > subranges()
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.
const_subrange_iterator subrange_end() const
void incrementWeight(float Inc)
bool operator<(const LiveInterval &other) const
void print(raw_ostream &OS) const
iterator_range< const_subrange_iterator > subranges() const
subrange_iterator subrange_begin()
subrange_iterator subrange_end()
SingleLinkedListIterator< const SubRange > const_subrange_iterator
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 ...
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
void setWeight(float Value)
void clearSubRanges()
Removes all subregister liveness information.
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 * valueOut() const
Return the value leaving the instruction, if any.
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,...
LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, bool Kill)
bool isKill() const
Return true if the live-in value is killed by this instruction.
Helper class for performant LiveRange bulk updates.
void print(raw_ostream &) const
void setDest(LiveRange *lr)
Select a different destination live range.
void flush()
Flush the updater state to LR so it is valid and contains all added segments.
LiveRangeUpdater(LiveRange *lr=nullptr)
Create a LiveRangeUpdater for adding segments to LR.
void add(SlotIndex Start, SlotIndex End, VNInfo *VNI)
bool isDirty() const
Return true if the LR is currently in an invalid state, and flush() needs to be called.
LiveRange * getDest() const
Get the current destination live range.
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
This class represents the liveness of a register, stack slot, etc.
LiveRange(bool UseSegmentSet=false)
Constructs a new LiveRange object.
iterator_range< const_vni_iterator > vnis() const
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Segments::iterator iterator
const_iterator FindSegmentContaining(SlotIndex Idx) const
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)
join - Join two live ranges (this, and other) together.
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...
iterator_range< vni_iterator > vnis()
const_iterator advanceTo(const_iterator I, SlotIndex Pos) const
LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator)
Constructs a new LiveRange object by copying segments and valnos from another LiveRange.
VNInfo * createValueCopy(const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
Create a copy of the given value.
bool liveAt(SlotIndex index) const
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
std::set< Segment > SegmentSet
const_iterator find(SlotIndex Pos) const
const_iterator begin() const
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
bool containsValue(const VNInfo *VNI) const
containsValue - Returns true if VNI belongs to this range.
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,...
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
std::unique_ptr< SegmentSet > segmentSet
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
const_vni_iterator vni_begin() const
void verify() const
Walk the range and assert if any invariants fail to hold.
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const
overlapsFrom - Return true if the intersection of the two live ranges is not empty.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
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...
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
const_vni_iterator vni_end() const
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
bool expiredAt(SlotIndex index) const
void append(const LiveRange::Segment S)
Append a segment to the list of segments.
VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.
unsigned getNumValNums() const
const VNInfo * getValNumInfo(unsigned ValNo) const
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
const_iterator end() const
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
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 ...
Segment * getSegmentContaining(SlotIndex Idx)
Return the live segment that contains the specified index, or null if there is none.
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
bool containsOneValue() const
bool hasAtLeastOneValue() const
bool isLocal(SlotIndex Start, SlotIndex End) const
True iff this segment is a single segment that lies between the specified boundaries,...
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified interval from this live range.
void removeValNoIfDead(VNInfo *ValNo)
Mark ValNo for deletion if no segments in this range use it.
void removeSegment(Segment S, bool RemoveDeadValNo=false)
bool operator<(const LiveRange &other) const
void print(raw_ostream &OS) const
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().
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
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.
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.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
VNInfo - Value Number Information.
void copyFrom(VNInfo &src)
Copy from the parameter into this VNInfo.
VNInfo(unsigned i, SlotIndex d)
VNInfo constructor.
VNInfo(unsigned i, const VNInfo &orig)
VNInfo constructor, copies values from orig, except for the value number.
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...
LLVM Value Representation.
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.
This is an optimization pass for GlobalISel generic memory operations.
bool operator<(int64_t V1, const APSInt &V2)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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...
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Implement std::hash so that hash_code can be used in STL containers.
This represents a simple continuous liveness interval for a value.
bool operator==(const Segment &Other) const
bool containsInterval(SlotIndex S, SlotIndex E) const
Return true if the given interval, [S, E), is covered by this segment.
bool operator!=(const Segment &Other) const
Segment(SlotIndex S, SlotIndex E, VNInfo *V)
bool contains(SlotIndex I) const
Return true if the index is covered by this segment.
bool operator<(const Segment &Other) const