X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveInterval.h;h=f1ea2c03f13cc3f851be190b4d80a9416906be2b;hp=24aad4f67c15308b59ff99966fbf4c91f763eef1;hb=c75c50f45b3d6d1d61ce6b411d12cedaadd71d5b;hpb=1920156982643a1c5c28af6f4684580b516eb597 diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 24aad4f67c1..f1ea2c03f13 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -9,12 +9,12 @@ // // This file implements the LiveRange and LiveInterval classes. Given some // numbering of each the machine instructions an interval [i, j) is said to be a -// live interval for register v if there is no instruction with number j' >= j +// live range for register v if there is no instruction with number j' >= j // such that v is live at j' and there is no instruction with number i' < i such -// that v is live at i'. In this implementation intervals can have holes, -// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each -// individual range is represented as an instance of LiveRange, and the whole -// interval is represented as an instance of LiveInterval. +// that v is live at i'. In this implementation ranges can have holes, +// i.e. a range might look like [1,20), [50,65), [1000,1001). Each +// individual segment is represented as an instance of LiveRange::Segment, +// and the whole range is represented as an instance of LiveRange. // //===----------------------------------------------------------------------===// @@ -25,8 +25,10 @@ #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Allocator.h" +#include "llvm/Target/TargetRegisterInfo.h" #include #include +#include namespace llvm { class CoalescerPair; @@ -35,6 +37,7 @@ namespace llvm { class MachineRegisterInfo; class TargetRegisterInfo; class raw_ostream; + template class SmallPtrSet; /// VNInfo - Value Number Information. /// This class holds information about a machine level values, including @@ -66,7 +69,7 @@ namespace llvm { } /// Returns true if this value is defined by a PHI instruction (or was, - /// PHI instrucions may have been eliminated). + /// PHI instructions may have been eliminated). /// PHI-defs begin at a block boundary, all other defs begin at register or /// EC slots. bool isPHIDef() const { return def.isBlock(); } @@ -78,96 +81,169 @@ namespace llvm { void markUnused() { def = SlotIndex(); } }; - /// LiveRange structure - This represents a simple register range in the - /// program, with an inclusive start point and an exclusive end point. - /// These ranges are rendered as [start,end). - struct LiveRange { - SlotIndex start; // Start point of the interval (inclusive) - SlotIndex end; // End point of the interval (exclusive) - VNInfo *valno; // identifier for the value contained in this interval. + /// Result of a LiveRange query. This class hides the implementation details + /// of live ranges, and it should be used as the primary interface for + /// examining live ranges around instructions. + class LiveQueryResult { + VNInfo *const EarlyVal; + VNInfo *const LateVal; + const SlotIndex EndPoint; + const bool Kill; - LiveRange() : valno(0) {} + public: + LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, + bool Kill) + : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) + {} - LiveRange(SlotIndex S, SlotIndex E, VNInfo *V) - : start(S), end(E), valno(V) { - assert(S < E && "Cannot create empty or backwards range"); + /// Return the value that is live-in to the instruction. This is the value + /// that will be read by the instruction's use operands. Return NULL if no + /// value is live-in. + VNInfo *valueIn() const { + return EarlyVal; } - /// contains - Return true if the index is covered by this range. - /// - bool contains(SlotIndex I) const { - return start <= I && I < end; + /// Return true if the live-in value is killed by this instruction. This + /// means that either the live range ends at the instruction, or it changes + /// value. + bool isKill() const { + return Kill; + } + + /// Return true if this instruction has a dead def. + bool isDeadDef() const { + return EndPoint.isDead(); } - /// containsRange - Return true if the given range, [S, E), is covered by - /// this range. - bool containsRange(SlotIndex S, SlotIndex E) const { - assert((S < E) && "Backwards interval?"); - return (start <= S && S < end) && (start < E && E <= end); + /// Return the value leaving the instruction, if any. This can be a + /// live-through value, or a live def. A dead def returns NULL. + VNInfo *valueOut() const { + return isDeadDef() ? nullptr : LateVal; } - bool operator<(const LiveRange &LR) const { - return start < LR.start || (start == LR.start && end < LR.end); + /// Returns the value alive at the end of the instruction, if any. This can + /// be a live-through value, a live def or a dead def. + VNInfo *valueOutOrDead() const { + return LateVal; } - bool operator==(const LiveRange &LR) const { - return start == LR.start && end == LR.end; + + /// Return the value defined by this instruction, if any. This includes + /// dead defs, it is the value created by the instruction's def operands. + VNInfo *valueDefined() const { + return EarlyVal == LateVal ? nullptr : LateVal; } - void dump() const; - void print(raw_ostream &os) const; + /// Return the end point of the last live range segment to interact with + /// the instruction, if any. + /// + /// The end point is an invalid SlotIndex only if the live range doesn't + /// intersect the instruction at all. + /// + /// The end point may be at or past the end of the instruction's basic + /// block. That means the value was live out of the block. + SlotIndex endPoint() const { + return EndPoint; + } }; - template <> struct isPodLike { static const bool value = true; }; + /// This class represents the liveness of a register, stack slot, etc. + /// It manages an ordered list of Segment objects. + /// The Segments are organized in a static single assignment form: At places + /// where a new value is defined or different values reach a CFG join a new + /// segment with a new value number is used. + class LiveRange { + public: - raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); + /// This represents a simple continuous liveness interval for a value. + /// The start point is inclusive, the end point exclusive. These intervals + /// are rendered as [start,end). + struct Segment { + SlotIndex start; // Start point of the interval (inclusive) + SlotIndex end; // End point of the interval (exclusive) + VNInfo *valno; // identifier for the value contained in this segment. + Segment() : valno(nullptr) {} - inline bool operator<(SlotIndex V, const LiveRange &LR) { - return V < LR.start; - } + Segment(SlotIndex S, SlotIndex E, VNInfo *V) + : start(S), end(E), valno(V) { + assert(S < E && "Cannot create empty or backwards segment"); + } - inline bool operator<(const LiveRange &LR, SlotIndex V) { - return LR.start < V; - } + /// Return true if the index is covered by this segment. + bool contains(SlotIndex I) const { + return start <= I && I < end; + } - /// LiveInterval - This class represents some number of live ranges for a - /// register or value. This class also contains a bit of register allocator - /// state. - class LiveInterval { - public: + /// Return true if the given interval, [S, E), is covered by this segment. + bool containsInterval(SlotIndex S, SlotIndex E) const { + assert((S < E) && "Backwards interval?"); + return (start <= S && S < end) && (start < E && E <= end); + } + + bool operator<(const Segment &Other) const { + return std::tie(start, end) < std::tie(Other.start, Other.end); + } + bool operator==(const Segment &Other) const { + return start == Other.start && end == Other.end; + } - typedef SmallVector Ranges; + void dump() const; + }; + + typedef SmallVector Segments; typedef SmallVector VNInfoList; - const unsigned reg; // the register or stack slot of this interval. - float weight; // weight of this interval - Ranges ranges; // the ranges in which this register is live + Segments segments; // the liveness segments VNInfoList valnos; // value#'s - LiveInterval(unsigned Reg, float Weight) - : reg(Reg), weight(Weight) {} + // The segment set is used temporarily to accelerate initial computation + // of live ranges of physical registers in computeRegUnitRange. + // After that the set is flushed to the segment vector and deleted. + typedef std::set SegmentSet; + std::unique_ptr segmentSet; - typedef Ranges::iterator iterator; - iterator begin() { return ranges.begin(); } - iterator end() { return ranges.end(); } + typedef Segments::iterator iterator; + iterator begin() { return segments.begin(); } + iterator end() { return segments.end(); } - typedef Ranges::const_iterator const_iterator; - const_iterator begin() const { return ranges.begin(); } - const_iterator end() const { return ranges.end(); } + typedef Segments::const_iterator const_iterator; + const_iterator begin() const { return segments.begin(); } + const_iterator end() const { return segments.end(); } typedef VNInfoList::iterator vni_iterator; vni_iterator vni_begin() { return valnos.begin(); } - vni_iterator vni_end() { return valnos.end(); } + vni_iterator vni_end() { return valnos.end(); } typedef VNInfoList::const_iterator const_vni_iterator; const_vni_iterator vni_begin() const { return valnos.begin(); } - const_vni_iterator vni_end() const { return valnos.end(); } + const_vni_iterator vni_end() const { return valnos.end(); } + + /// Constructs a new LiveRange object. + LiveRange(bool UseSegmentSet = false) + : segmentSet(UseSegmentSet ? llvm::make_unique() + : nullptr) {} + + /// Constructs a new LiveRange object by copying segments and valnos from + /// another LiveRange. + LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) { + assert(Other.segmentSet == nullptr && + "Copying of LiveRanges with active SegmentSets is not supported"); + + // Duplicate valnos. + for (const VNInfo *VNI : Other.valnos) { + createValueCopy(VNI, Allocator); + } + // Now we can copy segments and remap their valnos. + for (const Segment &S : Other.segments) { + segments.push_back(Segment(S.start, S.end, valnos[S.valno->id])); + } + } - /// advanceTo - Advance the specified iterator to point to the LiveRange + /// 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 interval. If no LiveRange contains this position, but the + /// end of the range. If no Segment contains this position, but the /// position is in a hole, this method returns an iterator pointing to the - /// LiveRange immediately after the hole. + /// Segment immediately after the hole. iterator advanceTo(iterator I, SlotIndex Pos) { assert(I != end()); if (Pos >= endIndex()) @@ -176,22 +252,34 @@ namespace llvm { return I; } - /// find - Return an iterator pointing to the first range that ends after + const_iterator advanceTo(const_iterator I, SlotIndex Pos) const { + assert(I != end()); + if (Pos >= endIndex()) + return end(); + while (I->end <= Pos) ++I; + return I; + } + + /// find - Return an iterator pointing to the first segment that ends after /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster - /// when searching large intervals. + /// when searching large ranges. /// - /// If Pos is contained in a LiveRange, that range is returned. - /// If Pos is in a hole, the following LiveRange is returned. + /// If Pos is contained in a Segment, that segment is returned. + /// If Pos is in a hole, the following Segment is returned. /// If Pos is beyond endIndex, end() is returned. iterator find(SlotIndex Pos); const_iterator find(SlotIndex Pos) const { - return const_cast(this)->find(Pos); + return const_cast(this)->find(Pos); } void clear() { valnos.clear(); - ranges.clear(); + segments.clear(); + } + + size_t size() const { + return segments.size(); } bool hasAtLeastOneValue() const { return !valnos.empty(); } @@ -209,7 +297,7 @@ namespace llvm { return valnos[ValNo]; } - /// containsValue - Returns true if VNI belongs to this interval. + /// containsValue - Returns true if VNI belongs to this range. bool containsValue(const VNInfo *VNI) const { return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); } @@ -223,7 +311,7 @@ namespace llvm { return VNI; } - /// createDeadDef - Make sure the interval has a value defined at Def. + /// createDeadDef - Make sure the range has a value defined at Def. /// If one already exists, return it. Otherwise allocate a new value and /// add liveness for a dead def. VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); @@ -244,38 +332,38 @@ namespace llvm { /// MergeValueNumberInto - This method is called when two value numbers /// are found to be equivalent. This eliminates V1, replacing all - /// LiveRanges with the V1 value number with the V2 value number. This can + /// segments with the V1 value number with the V2 value number. This can /// cause merging of V1/V2 values numbers and compaction of the value space. VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the - /// current interval, it will replace the value numbers of the overlaped - /// live ranges with the specified value number. - void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); - - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the - /// current interval, but only if the overlapping LiveRanges have the + /// Merge all of the live segments of a specific val# in RHS into this live + /// range as the specified value number. The segments in RHS are allowed + /// to overlap with segments in the current range, it will replace the + /// value numbers of the overlaped live segments with the specified value + /// number. + void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); + + /// MergeValueInAsValue - Merge all of the segments of a specific val# + /// in RHS into this live range as the specified value number. + /// The segments in RHS are allowed to overlap with segments in the + /// current range, but only if the overlapping segments have the /// specified value number. - void MergeValueInAsValue(const LiveInterval &RHS, + void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo); - bool empty() const { return ranges.empty(); } + bool empty() const { return segments.empty(); } - /// beginIndex - Return the lowest numbered slot covered by interval. + /// beginIndex - Return the lowest numbered slot covered. SlotIndex beginIndex() const { - assert(!empty() && "Call to beginIndex() on empty interval."); - return ranges.front().start; + assert(!empty() && "Call to beginIndex() on empty range."); + return segments.front().start; } - /// endNumber - return the maximum point of the interval of the whole, + /// endNumber - return the maximum point of the range of the whole, /// exclusive. SlotIndex endIndex() const { - assert(!empty() && "Call to endIndex() on empty interval."); - return ranges.back().end; + assert(!empty() && "Call to endIndex() on empty range."); + return segments.back().end; } bool expiredAt(SlotIndex index) const { @@ -287,92 +375,96 @@ namespace llvm { return r != end() && r->start <= index; } - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - const LiveRange *getLiveRangeContaining(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx); - return I == end() ? 0 : &*I; + /// Return the segment that contains the specified index, or null if there + /// is none. + const Segment *getSegmentContaining(SlotIndex Idx) const { + const_iterator I = FindSegmentContaining(Idx); + return I == end() ? nullptr : &*I; } - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - LiveRange *getLiveRangeContaining(SlotIndex Idx) { - iterator I = FindLiveRangeContaining(Idx); - return I == end() ? 0 : &*I; + /// Return the live segment that contains the specified index, or null if + /// there is none. + Segment *getSegmentContaining(SlotIndex Idx) { + iterator I = FindSegmentContaining(Idx); + return I == end() ? nullptr : &*I; } /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. VNInfo *getVNInfoAt(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx); - return I == end() ? 0 : I->valno; + const_iterator I = FindSegmentContaining(Idx); + return I == end() ? nullptr : I->valno; } /// getVNInfoBefore - Return the VNInfo that is live up to but not /// necessarilly including Idx, or NULL. Use this to find the reaching def /// used by an instruction at this SlotIndex position. VNInfo *getVNInfoBefore(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot()); - return I == end() ? 0 : I->valno; + const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); + return I == end() ? nullptr : I->valno; } - /// FindLiveRangeContaining - Return an iterator to the live range that - /// contains the specified index, or end() if there is none. - iterator FindLiveRangeContaining(SlotIndex Idx) { + /// Return an iterator to the segment that contains the specified index, or + /// end() if there is none. + iterator FindSegmentContaining(SlotIndex Idx) { iterator I = find(Idx); return I != end() && I->start <= Idx ? I : end(); } - const_iterator FindLiveRangeContaining(SlotIndex Idx) const { + const_iterator FindSegmentContaining(SlotIndex Idx) const { const_iterator I = find(Idx); return I != end() && I->start <= Idx ? I : end(); } - /// overlaps - Return true if the intersection of the two live intervals is + /// overlaps - Return true if the intersection of the two live ranges is /// not empty. - bool overlaps(const LiveInterval& other) const { + bool overlaps(const LiveRange &other) const { if (other.empty()) return false; return overlapsFrom(other, other.begin()); } - /// overlaps - Return true if the two intervals have overlapping segments + /// overlaps - Return true if the two ranges have overlapping segments /// that are not coalescable according to CP. /// - /// Overlapping segments where one interval is defined by a coalescable + /// Overlapping segments where one range is defined by a coalescable /// copy are allowed. - bool overlaps(const LiveInterval &Other, const CoalescerPair &CP, + bool overlaps(const LiveRange &Other, const CoalescerPair &CP, const SlotIndexes&) const; - /// overlaps - Return true if the live interval overlaps a range specified + /// overlaps - Return true if the live range overlaps an interval specified /// by [Start, End). bool overlaps(SlotIndex Start, SlotIndex End) const; - /// overlapsFrom - Return true if the intersection of the two live intervals + /// overlapsFrom - Return true if the intersection of the two live ranges /// is not empty. The specified iterator is a hint that we can begin - /// scanning the Other interval starting at I. - bool overlapsFrom(const LiveInterval& other, const_iterator I) const; - - /// addRange - Add the specified LiveRange to this interval, merging - /// intervals as appropriate. This returns an iterator to the inserted live - /// range (which may have grown since it was inserted. - iterator addRange(LiveRange LR) { - return addRangeFrom(LR, ranges.begin()); - } - - /// extendInBlock - If this interval is live before Kill in the basic block - /// that starts at StartIdx, extend it to be live up to Kill, and return - /// the value. If there is no live range before Kill, return NULL. - VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); - - /// join - Join two live intervals (this, and other) together. This applies - /// mappings to the value numbers in the LHS/RHS intervals as specified. If - /// the intervals are not joinable, this aborts. - void join(LiveInterval &Other, + /// scanning the Other range starting at I. + bool overlapsFrom(const LiveRange &Other, const_iterator I) const; + + /// Returns true if all segments of the @p Other live range are completely + /// covered by this live range. + /// Adjacent live ranges do not affect the covering:the liverange + /// [1,5](5,10] covers (3,7]. + bool covers(const LiveRange &Other) const; + + /// Add the specified Segment to this range, merging segments as + /// appropriate. This returns an iterator to the inserted segment (which + /// may have grown since it was inserted). + iterator addSegment(Segment S); + + /// If this range is live before @p Use in the basic block that starts at + /// @p StartIdx, extend it to be live up to @p Use, and return the value. If + /// there is no segment before @p Use, return nullptr. + VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use); + + /// join - Join two live ranges (this, and other) together. This applies + /// mappings to the value numbers in the LHS/RHS ranges as specified. If + /// the ranges are not joinable, this aborts. + void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl &NewVNInfo); - /// True iff this live range is a single segment that lies between the + /// True iff this segment is a single segment that lies between the /// specified boundaries, exclusively. Vregs live across a backedge are not /// considered local. The boundaries are expected to lie within an extended /// basic block, so vregs that are not live out should contain no holes. @@ -381,71 +473,290 @@ namespace llvm { endIndex() < End.getBoundaryIndex(); } - /// removeRange - Remove the specified range from this interval. Note that - /// the range must be a single LiveRange in its entirety. - void removeRange(SlotIndex Start, SlotIndex End, - bool RemoveDeadValNo = false); + /// Remove the specified segment from this range. Note that the segment + /// must be a single Segment in its entirety. + void removeSegment(SlotIndex Start, SlotIndex End, + bool RemoveDeadValNo = false); + + void removeSegment(Segment S, bool RemoveDeadValNo = false) { + removeSegment(S.start, S.end, RemoveDeadValNo); + } + + /// Remove segment pointed to by iterator @p I from this range. This does + /// not remove dead value numbers. + iterator removeSegment(iterator I) { + return segments.erase(I); + } + + /// Query Liveness at Idx. + /// The sub-instruction slot of Idx doesn't matter, only the instruction + /// it refers to is considered. + LiveQueryResult Query(SlotIndex Idx) const { + // Find the segment that enters the instruction. + const_iterator I = find(Idx.getBaseIndex()); + const_iterator E = end(); + if (I == E) + return LiveQueryResult(nullptr, nullptr, SlotIndex(), false); - void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { - removeRange(LR.start, LR.end, RemoveDeadValNo); + // Is this an instruction live-in segment? + // If Idx is the start index of a basic block, include live-in segments + // that start at Idx.getBaseIndex(). + VNInfo *EarlyVal = nullptr; + VNInfo *LateVal = nullptr; + SlotIndex EndPoint; + bool Kill = false; + if (I->start <= Idx.getBaseIndex()) { + EarlyVal = I->valno; + EndPoint = I->end; + // Move to the potentially live-out segment. + if (SlotIndex::isSameInstr(Idx, I->end)) { + Kill = true; + if (++I == E) + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); + } + // Special case: A PHIDef value can have its def in the middle of a + // segment if the value happens to be live out of the layout + // predecessor. + // Such a value is not live-in. + if (EarlyVal->def == Idx.getBaseIndex()) + EarlyVal = nullptr; + } + // I now points to the segment that may be live-through, or defined by + // this instr. Ignore segments starting after the current instr. + if (!SlotIndex::isEarlierInstr(Idx, I->start)) { + LateVal = I->valno; + EndPoint = I->end; + } + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); } - /// removeValNo - Remove all the ranges defined by the specified value#. + /// removeValNo - Remove all the segments defined by the specified value#. /// Also remove the value# from value# list. void removeValNo(VNInfo *ValNo); - /// getSize - Returns the sum of sizes of all the LiveRange's. - /// - unsigned getSize() const; - - /// Returns true if the live interval is zero length, i.e. no live ranges - /// span instructions. It doesn't pay to spill such an interval. + /// Returns true if the live range is zero length, i.e. no live segments + /// span instructions. It doesn't pay to spill such a range. bool isZeroLength(SlotIndexes *Indexes) const { - for (const_iterator i = begin(), e = end(); i != e; ++i) - if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < - i->end.getBaseIndex()) + for (const Segment &S : segments) + if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() < + S.end.getBaseIndex()) return false; return true; } + // Returns true if any segment in the live range contains any of the + // provided slot indexes. Slots which occur in holes between + // segments will not cause the function to return true. + bool isLiveAtIndexes(ArrayRef Slots) const; + + bool operator<(const LiveRange& other) const { + const SlotIndex &thisIndex = beginIndex(); + const SlotIndex &otherIndex = other.beginIndex(); + return thisIndex < otherIndex; + } + + /// Flush segment set into the regular segment vector. + /// The method is to be called after the live range + /// has been created, if use of the segment set was + /// activated in the constructor of the live range. + void flushSegmentSet(); + + void print(raw_ostream &OS) const; + void dump() const; + + /// \brief Walk the range and assert if any invariants fail to hold. + /// + /// Note that this is a no-op when asserts are disabled. +#ifdef NDEBUG + void verify() const {} +#else + void verify() const; +#endif + + protected: + /// Append a segment to the list of segments. + void append(const LiveRange::Segment S); + + private: + friend class LiveRangeUpdater; + void addSegmentToSet(Segment S); + void markValNoForDeletion(VNInfo *V); + + }; + + inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { + LR.print(OS); + return OS; + } + + /// LiveInterval - This class represents the liveness of a register, + /// or stack slot. + class LiveInterval : public LiveRange { + public: + typedef LiveRange super; + + /// A live range for subregisters. The LaneMask specifies which parts of the + /// super register are covered by the interval. + /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()). + class SubRange : public LiveRange { + public: + SubRange *Next; + LaneBitmask LaneMask; + + /// Constructs a new SubRange object. + SubRange(LaneBitmask LaneMask) + : Next(nullptr), LaneMask(LaneMask) { + } + + /// Constructs a new SubRange object by copying liveness from @p Other. + SubRange(LaneBitmask LaneMask, const LiveRange &Other, + BumpPtrAllocator &Allocator) + : LiveRange(Other, Allocator), Next(nullptr), LaneMask(LaneMask) { + } + }; + + private: + SubRange *SubRanges; ///< Single linked list of subregister live ranges. + + public: + const unsigned reg; // the register or stack slot of this interval. + float weight; // weight of this interval + + LiveInterval(unsigned Reg, float Weight) + : SubRanges(nullptr), reg(Reg), weight(Weight) {} + + ~LiveInterval() { + clearSubRanges(); + } + + template + class SingleLinkedListIterator { + T *P; + public: + SingleLinkedListIterator(T *P) : P(P) {} + SingleLinkedListIterator &operator++() { + P = P->Next; + return *this; + } + SingleLinkedListIterator &operator++(int) { + SingleLinkedListIterator res = *this; + ++*this; + return res; + } + bool operator!=(const SingleLinkedListIterator &Other) { + return P != Other.operator->(); + } + bool operator==(const SingleLinkedListIterator &Other) { + return P == Other.operator->(); + } + T &operator*() const { + return *P; + } + T *operator->() const { + return P; + } + }; + + typedef SingleLinkedListIterator subrange_iterator; + subrange_iterator subrange_begin() { + return subrange_iterator(SubRanges); + } + subrange_iterator subrange_end() { + return subrange_iterator(nullptr); + } + + typedef SingleLinkedListIterator const_subrange_iterator; + const_subrange_iterator subrange_begin() const { + return const_subrange_iterator(SubRanges); + } + const_subrange_iterator subrange_end() const { + return const_subrange_iterator(nullptr); + } + + iterator_range subranges() { + return make_range(subrange_begin(), subrange_end()); + } + + iterator_range subranges() const { + return make_range(subrange_begin(), subrange_end()); + } + + /// Creates a new empty subregister live range. The range is added at the + /// beginning of the subrange list; subrange iterators stay valid. + SubRange *createSubRange(BumpPtrAllocator &Allocator, + LaneBitmask LaneMask) { + SubRange *Range = new (Allocator) SubRange(LaneMask); + appendSubRange(Range); + return Range; + } + + /// Like createSubRange() but the new range is filled with a copy of the + /// liveness information in @p CopyFrom. + SubRange *createSubRangeFrom(BumpPtrAllocator &Allocator, + LaneBitmask LaneMask, + const LiveRange &CopyFrom) { + SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator); + appendSubRange(Range); + return Range; + } + + /// Returns true if subregister liveness information is available. + bool hasSubRanges() const { + return SubRanges != nullptr; + } + + /// Removes all subregister liveness information. + void clearSubRanges(); + + /// Removes all subranges without any segments (subranges without segments + /// are not considered valid and should only exist temporarily). + void removeEmptySubRanges(); + + /// Construct main live range by merging the SubRanges of @p LI. + void constructMainRangeFromSubranges(const SlotIndexes &Indexes, + VNInfo::Allocator &VNIAllocator); + + /// getSize - Returns the sum of sizes of all the LiveRange's. + /// + unsigned getSize() const; + /// isSpillable - Can this interval be spilled? bool isSpillable() const { - return weight != HUGE_VALF; + return weight != llvm::huge_valf; } /// markNotSpillable - Mark interval as not spillable void markNotSpillable() { - weight = HUGE_VALF; + weight = llvm::huge_valf; } bool operator<(const LiveInterval& other) const { const SlotIndex &thisIndex = beginIndex(); const SlotIndex &otherIndex = other.beginIndex(); - return (thisIndex < otherIndex || - (thisIndex == otherIndex && reg < other.reg)); + return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg); } void print(raw_ostream &OS) const; void dump() const; - /// \brief Walk the interval and assert if any invariants fail to hold. + /// \brief Walks the interval and assert if any invariants fail to hold. /// /// Note that this is a no-op when asserts are disabled. #ifdef NDEBUG - void verify() const {} + void verify(const MachineRegisterInfo *MRI = nullptr) const {} #else - void verify() const; + void verify(const MachineRegisterInfo *MRI = nullptr) const; #endif private: + /// Appends @p Range to SubRanges list. + void appendSubRange(SubRange *Range) { + Range->Next = SubRanges; + SubRanges = Range; + } - Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From); - void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); - Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); - void markValNoForDeletion(VNInfo *V); - - LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; - + /// Free memory held by SubRange. + void freeSubRange(SubRange *S); }; inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { @@ -453,54 +764,65 @@ namespace llvm { return OS; } - /// Helper class for performant LiveInterval bulk updates. + raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); + + inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { + return V < S.start; + } + + inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { + return S.start < V; + } + + /// Helper class for performant LiveRange bulk updates. /// - /// Calling LiveInterval::addRange() repeatedly can be expensive on large + /// Calling LiveRange::addSegment() repeatedly can be expensive on large /// live ranges because segments after the insertion point may need to be /// shifted. The LiveRangeUpdater class can defer the shifting when adding /// many segments in order. /// - /// The LiveInterval will be in an invalid state until flush() is called. + /// The LiveRange will be in an invalid state until flush() is called. class LiveRangeUpdater { - LiveInterval *LI; + LiveRange *LR; SlotIndex LastStart; - LiveInterval::iterator WriteI; - LiveInterval::iterator ReadI; - SmallVector Spills; + LiveRange::iterator WriteI; + LiveRange::iterator ReadI; + SmallVector Spills; void mergeSpills(); public: - /// Create a LiveRangeUpdater for adding segments to LI. - /// LI will temporarily be in an invalid state until flush() is called. - LiveRangeUpdater(LiveInterval *li = 0) : LI(li) {} + /// Create a LiveRangeUpdater for adding segments to LR. + /// LR will temporarily be in an invalid state until flush() is called. + LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {} ~LiveRangeUpdater() { flush(); } - /// Add a segment to LI and coalesce when possible, just like LI.addRange(). - /// Segments should be added in increasing start order for best performance. - void add(LiveRange); + /// Add a segment to LR and coalesce when possible, just like + /// LR.addSegment(). Segments should be added in increasing start order for + /// best performance. + void add(LiveRange::Segment); void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { - add(LiveRange(Start, End, VNI)); + add(LiveRange::Segment(Start, End, VNI)); } - /// Return true if the LI is currently in an invalid state, and flush() + /// Return true if the LR is currently in an invalid state, and flush() /// needs to be called. bool isDirty() const { return LastStart.isValid(); } - /// Flush the updater state to LI so it is valid and contains all added + /// Flush the updater state to LR so it is valid and contains all added /// segments. void flush(); /// Select a different destination live range. - void setDest(LiveInterval *li) { - if (LI != li && isDirty()) + void setDest(LiveRange *lr) { + if (LR != lr && isDirty()) flush(); - LI = li; + LR = lr; } /// Get the current destination live range. - LiveInterval *getDest() const { return LI; } + LiveRange *getDest() const { return LR; } void dump() const; void print(raw_ostream&) const; @@ -511,99 +833,6 @@ namespace llvm { return OS; } - /// LiveRangeQuery - Query information about a live range around a given - /// instruction. This class hides the implementation details of live ranges, - /// and it should be used as the primary interface for examining live ranges - /// around instructions. - /// - class LiveRangeQuery { - VNInfo *EarlyVal; - VNInfo *LateVal; - SlotIndex EndPoint; - bool Kill; - - public: - /// Create a LiveRangeQuery for the given live range and instruction index. - /// The sub-instruction slot of Idx doesn't matter, only the instruction it - /// refers to is considered. - LiveRangeQuery(const LiveInterval &LI, SlotIndex Idx) - : EarlyVal(0), LateVal(0), Kill(false) { - // Find the segment that enters the instruction. - LiveInterval::const_iterator I = LI.find(Idx.getBaseIndex()); - LiveInterval::const_iterator E = LI.end(); - if (I == E) - return; - // Is this an instruction live-in segment? - // If Idx is the start index of a basic block, include live-in segments - // that start at Idx.getBaseIndex(). - if (I->start <= Idx.getBaseIndex()) { - EarlyVal = I->valno; - EndPoint = I->end; - // Move to the potentially live-out segment. - if (SlotIndex::isSameInstr(Idx, I->end)) { - Kill = true; - if (++I == E) - return; - } - // Special case: A PHIDef value can have its def in the middle of a - // segment if the value happens to be live out of the layout - // predecessor. - // Such a value is not live-in. - if (EarlyVal->def == Idx.getBaseIndex()) - EarlyVal = 0; - } - // I now points to the segment that may be live-through, or defined by - // this instr. Ignore segments starting after the current instr. - if (SlotIndex::isEarlierInstr(Idx, I->start)) - return; - LateVal = I->valno; - EndPoint = I->end; - } - - /// Return the value that is live-in to the instruction. This is the value - /// that will be read by the instruction's use operands. Return NULL if no - /// value is live-in. - VNInfo *valueIn() const { - return EarlyVal; - } - - /// Return true if the live-in value is killed by this instruction. This - /// means that either the live range ends at the instruction, or it changes - /// value. - bool isKill() const { - return Kill; - } - - /// Return true if this instruction has a dead def. - bool isDeadDef() const { - return EndPoint.isDead(); - } - - /// Return the value leaving the instruction, if any. This can be a - /// live-through value, or a live def. A dead def returns NULL. - VNInfo *valueOut() const { - return isDeadDef() ? 0 : LateVal; - } - - /// Return the value defined by this instruction, if any. This includes - /// dead defs, it is the value created by the instruction's def operands. - VNInfo *valueDefined() const { - return EarlyVal == LateVal ? 0 : LateVal; - } - - /// Return the end point of the last live range segment to interact with - /// the instruction, if any. - /// - /// The end point is an invalid SlotIndex only if the live range doesn't - /// intersect the instruction at all. - /// - /// The end point may be at or past the end of the instruction's basic - /// block. That means the value was live out of the block. - SlotIndex endPoint() const { - return EndPoint; - } - }; - /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a /// LiveInterval into equivalence clases of connected components. A /// LiveInterval that has multiple connected components can be broken into @@ -621,28 +850,23 @@ namespace llvm { LiveIntervals &LIS; IntEqClasses EqClass; - // Note that values a and b are connected. - void Connect(unsigned a, unsigned b); - - unsigned Renumber(); - public: explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} - /// Classify - Classify the values in LI into connected components. - /// Return the number of connected components. - unsigned Classify(const LiveInterval *LI); + /// Classify the values in \p LR into connected components. + /// Returns the number of connected components. + unsigned Classify(const LiveRange &LR); /// getEqClass - Classify creates equivalence classes numbered 0..N. Return /// the equivalence class assigned the VNI. unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } - /// Distribute - Distribute values in LIV[0] into a separate LiveInterval - /// for each connected component. LIV must have a LiveInterval for each - /// connected component. The LiveIntervals in Liv[1..] must be empty. - /// Instructions using LIV[0] are rewritten. - void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI); - + /// Distribute values in \p LI into a separate LiveIntervals + /// for each connected component. LIV must have an empty LiveInterval for + /// each additional connected component. The first connected component is + /// left in \p LI. + void Distribute(LiveInterval &LI, LiveInterval *LIV[], + MachineRegisterInfo &MRI); }; }