X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveInterval.h;h=0157bf9117e5362b29e048d048e534187a8bef21;hb=6426aea54e5be9ceb0dd981db8459857785a2e61;hp=3a9fef6fbd78176b9aac3a4d868590fad2e364a5;hpb=eb3602472026dc029beb45ccbe09bc84162ba949;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 3a9fef6fbd7..0157bf9117e 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -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; @@ -116,13 +118,19 @@ namespace llvm { /// 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 isDeadDef() ? nullptr : LateVal; + } + + /// 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; } /// 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 EarlyVal == LateVal ? nullptr : LateVal; } /// Return the end point of the last live range segment to interact with @@ -154,7 +162,7 @@ namespace llvm { SlotIndex end; // End point of the interval (exclusive) VNInfo *valno; // identifier for the value contained in this segment. - Segment() : valno(0) {} + Segment() : valno(nullptr) {} Segment(SlotIndex S, SlotIndex E, VNInfo *V) : start(S), end(E), valno(V) { @@ -173,7 +181,7 @@ namespace llvm { } bool operator<(const Segment &Other) const { - return start < Other.start || (start == Other.start && end < Other.end); + return std::tie(start, end) < std::tie(Other.start, Other.end); } bool operator==(const Segment &Other) const { return start == Other.start && end == Other.end; @@ -188,6 +196,12 @@ namespace llvm { Segments segments; // the liveness segments VNInfoList valnos; // value#'s + // 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 Segments::iterator iterator; iterator begin() { return segments.begin(); } iterator end() { return segments.end(); } @@ -204,6 +218,27 @@ namespace llvm { const_vni_iterator vni_begin() const { return valnos.begin(); } 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 Segment /// containing the specified position, or end() if the position is past the /// end of the range. If no Segment contains this position, but the @@ -217,6 +252,14 @@ namespace llvm { return I; } + 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 ranges. @@ -336,20 +379,20 @@ namespace llvm { /// is none. const Segment *getSegmentContaining(SlotIndex Idx) const { const_iterator I = FindSegmentContaining(Idx); - return I == end() ? 0 : &*I; + return I == end() ? nullptr : &*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() ? 0 : &*I; + return I == end() ? nullptr : &*I; } /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. VNInfo *getVNInfoAt(SlotIndex Idx) const { const_iterator I = FindSegmentContaining(Idx); - return I == end() ? 0 : I->valno; + return I == end() ? nullptr : I->valno; } /// getVNInfoBefore - Return the VNInfo that is live up to but not @@ -357,7 +400,7 @@ namespace llvm { /// used by an instruction at this SlotIndex position. VNInfo *getVNInfoBefore(SlotIndex Idx) const { const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); - return I == end() ? 0 : I->valno; + return I == end() ? nullptr : I->valno; } /// Return an iterator to the segment that contains the specified index, or @@ -397,17 +440,21 @@ namespace llvm { /// 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) { - return addSegmentFrom(S, segments.begin()); - } + iterator addSegment(Segment S); - /// extendInBlock - If this range 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 segment before Kill, return NULL. - VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); + /// 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 @@ -435,6 +482,12 @@ namespace llvm { 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. @@ -443,13 +496,13 @@ namespace llvm { const_iterator I = find(Idx.getBaseIndex()); const_iterator E = end(); if (I == E) - return LiveQueryResult(0, 0, SlotIndex(), false); + return LiveQueryResult(nullptr, nullptr, SlotIndex(), false); // 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 = 0; - VNInfo *LateVal = 0; + VNInfo *EarlyVal = nullptr; + VNInfo *LateVal = nullptr; SlotIndex EndPoint; bool Kill = false; if (I->start <= Idx.getBaseIndex()) { @@ -466,7 +519,7 @@ namespace llvm { // predecessor. // Such a value is not live-in. if (EarlyVal->def == Idx.getBaseIndex()) - EarlyVal = 0; + 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. @@ -484,9 +537,9 @@ namespace llvm { /// 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; } @@ -497,6 +550,12 @@ namespace llvm { 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; @@ -509,11 +568,13 @@ namespace llvm { void verify() const; #endif - private: + protected: + /// Append a segment to the list of segments. + void append(const LiveRange::Segment S); - iterator addSegmentFrom(Segment S, iterator From); - void extendSegmentEndTo(iterator I, SlotIndex NewEnd); - iterator extendSegmentStartTo(iterator I, SlotIndex NewStr); + private: + friend class LiveRangeUpdater; + void addSegmentToSet(Segment S); void markValNoForDeletion(VNInfo *V); }; @@ -529,11 +590,126 @@ namespace llvm { 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) - : reg(Reg), weight(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. /// @@ -552,16 +728,30 @@ namespace llvm { 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 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 MachineRegisterInfo *MRI = nullptr) const {} +#else + void verify(const MachineRegisterInfo *MRI = nullptr) const; +#endif + private: - LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; + /// Appends @p Range to SubRanges list. + void appendSubRange(SubRange *Range) { + Range->Next = SubRanges; + SubRanges = Range; + } + /// Free memory held by SubRange. + void freeSubRange(SubRange *S); }; inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { @@ -598,7 +788,7 @@ namespace llvm { public: /// Create a LiveRangeUpdater for adding segments to LR. /// LR will temporarily be in an invalid state until flush() is called. - LiveRangeUpdater(LiveRange *lr = 0) : LR(lr) {} + LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {} ~LiveRangeUpdater() { flush(); } @@ -655,11 +845,6 @@ 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) {} @@ -671,12 +856,12 @@ namespace llvm { /// 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); }; }