X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalUnion.h;h=4d41fca85ad32ccbd79229b1280b96d1b6971fe8;hb=3e2d76c946ba753c2b11af192a52e25b6f9b46ff;hp=f0bce470875097d609b0ff688953279e9c3d839b;hpb=32d9aeb1df982638766757704c4e23f58ffb40d1;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h index f0bce470875..4d41fca85ad 100644 --- a/lib/CodeGen/LiveIntervalUnion.h +++ b/lib/CodeGen/LiveIntervalUnion.h @@ -17,53 +17,25 @@ #ifndef LLVM_CODEGEN_LIVEINTERVALUNION #define LLVM_CODEGEN_LIVEINTERVALUNION +#include "llvm/ADT/IntervalMap.h" #include "llvm/CodeGen/LiveInterval.h" -#include -#include namespace llvm { -/// A LiveSegment is a copy of a LiveRange object used within -/// LiveIntervalUnion. LiveSegment additionally contains a pointer to its -/// original live virtual register (LiveInterval). This allows quick lookup of -/// the live virtual register as we iterate over live segments in a union. Note -/// that LiveRange is misnamed and actually represents only a single contiguous -/// interval within a virtual register's liveness. To limit confusion, in this -/// file we refer it as a live segment. -/// -/// Note: This currently represents a half-open interval [start,end). -/// If LiveRange is modified to represent a closed interval, so should this. -struct LiveSegment { - SlotIndex start; - SlotIndex end; - LiveInterval *liveVirtReg; - - LiveSegment(SlotIndex s, SlotIndex e, LiveInterval *lvr) - : start(s), end(e), liveVirtReg(lvr) {} - - bool operator==(const LiveSegment &ls) const { - return start == ls.start && end == ls.end && liveVirtReg == ls.liveVirtReg; - } - - bool operator!=(const LiveSegment &ls) const { - return !operator==(ls); - } - - // Order segments by starting point only--we expect them to be disjoint. - bool operator<(const LiveSegment &ls) const { return start < ls.start; } -}; - -inline bool operator<(SlotIndex V, const LiveSegment &ls) { - return V < ls.start; -} +class MachineLoopRange; +class TargetRegisterInfo; -inline bool operator<(const LiveSegment &ls, SlotIndex V) { - return ls.start < V; -} +#ifndef NDEBUG +// forward declaration +template class SparseBitVector; +typedef SparseBitVector<128> LiveVirtRegBitSet; +#endif /// Compare a live virtual register segment to a LiveIntervalUnion segment. -inline bool overlap(const LiveRange &lvrSeg, const LiveSegment &liuSeg) { - return lvrSeg.start < liuSeg.end && liuSeg.start < lvrSeg.end; +inline bool +overlap(const LiveRange &VRSeg, + const IntervalMap::const_iterator &LUSeg) { + return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; } /// Union of live intervals that are strong candidates for coalescing into a @@ -72,18 +44,9 @@ inline bool overlap(const LiveRange &lvrSeg, const LiveSegment &liuSeg) { /// eventually make exceptions to handle value-based interference. class LiveIntervalUnion { // A set of live virtual register segments that supports fast insertion, - // intersection, and removal. - // - // FIXME: std::set is a placeholder until we decide how to - // efficiently represent it. Probably need to roll our own B-tree. - typedef std::set LiveSegments; - - // A set of live virtual registers. Elements have type LiveInterval, where - // each element represents the liveness of a single live virtual register. - // This is traditionally known as a live range, but we refer is as a live - // virtual register to avoid confusing it with the misnamed LiveRange - // class. - typedef std::vector LiveVirtRegs; + // intersection, and removal. + // Mapping SlotIndex intervals to virtual register numbers. + typedef IntervalMap LiveSegments; public: // SegmentIter can advance to the next segment ordered by starting position @@ -91,133 +54,154 @@ public: // to reach the current segment's containing virtual register. typedef LiveSegments::iterator SegmentIter; - class InterferenceResult; + // LiveIntervalUnions share an external allocator. + typedef LiveSegments::Allocator Allocator; + class Query; private: - unsigned repReg_; // representative register number - LiveSegments segments_; // union of virtual reg segements + unsigned Tag; // unique tag for current contents. + LiveSegments Segments; // union of virtual reg segments public: - // default ctor avoids placement new - LiveIntervalUnion() : repReg_(0) {} - - // Initialize the union by associating it with a representative register - // number. - void init(unsigned repReg) { repReg_ = repReg; } + explicit LiveIntervalUnion(Allocator &a) : Tag(0), Segments(a) {} // Iterate over all segments in the union of live virtual registers ordered // by their starting position. - SegmentIter begin() { return segments_.begin(); } - SegmentIter end() { return segments_.end(); } + SegmentIter begin() { return Segments.begin(); } + SegmentIter end() { return Segments.end(); } + SegmentIter find(SlotIndex x) { return Segments.find(x); } + bool empty() const { return Segments.empty(); } + SlotIndex startIndex() const { return Segments.start(); } - // Return an iterator to the first segment after or including begin that - // intersects with lvrSeg. - SegmentIter upperBound(SegmentIter begin, const LiveSegment &seg); + // Provide public access to the underlying map to allow overlap iteration. + typedef LiveSegments Map; + const Map &getMap() { return Segments; } - // Add a live virtual register to this union and merge its segments. - // Holds a nonconst reference to the LVR for later maniplution. - void unify(LiveInterval &lvr); + /// getTag - Return an opaque tag representing the current state of the union. + unsigned getTag() const { return Tag; } - // Remove a live virtual register's segments from this union. - void extract(const LiveInterval &lvr); - - /// Cache a single interference test result in the form of two intersecting - /// segments. This allows efficiently iterating over the interferences. The - /// iteration logic is handled by LiveIntervalUnion::Query which may - /// filter interferences depending on the type of query. - class InterferenceResult { - friend class Query; - - LiveInterval::iterator lvrSegI_; // current position in _lvr - SegmentIter liuSegI_; // current position in _liu - - // Internal ctor. - InterferenceResult(LiveInterval::iterator lvrSegI, SegmentIter liuSegI) - : lvrSegI_(lvrSegI), liuSegI_(liuSegI) {} + /// changedSince - Return true if the union change since getTag returned tag. + bool changedSince(unsigned tag) const { return tag != Tag; } - public: - // Public default ctor. - InterferenceResult(): lvrSegI_(), liuSegI_() {} + // Add a live virtual register to this union and merge its segments. + void unify(LiveInterval &VirtReg); - // Note: this interface provides raw access to the iterators because the - // result has no way to tell if it's valid to dereference them. + // Remove a live virtual register's segments from this union. + void extract(LiveInterval &VirtReg); - // Access the lvr segment. - const LiveInterval::iterator &lvrSegPos() const { return lvrSegI_; } + // Remove all inserted virtual registers. + void clear() { Segments.clear(); ++Tag; } - // Access the liu segment. - const SegmentIter &liuSegPos() const { return liuSegI_; } + // Print union, using TRI to translate register names + void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; - bool operator==(const InterferenceResult &ir) const { - return lvrSegI_ == ir.lvrSegI_ && liuSegI_ == ir.liuSegI_; - } - bool operator!=(const InterferenceResult &ir) const { - return !operator==(ir); - } - }; +#ifndef NDEBUG + // Verify the live intervals in this union and add them to the visited set. + void verify(LiveVirtRegBitSet& VisitedVRegs); +#endif /// Query interferences between a single live virtual register and a live /// interval union. class Query { - LiveIntervalUnion *liu_; - LiveInterval *lvr_; - InterferenceResult firstInterference_; - // TBD: interfering vregs + LiveIntervalUnion *LiveUnion; + LiveInterval *VirtReg; + LiveInterval::iterator VirtRegI; // current position in VirtReg + SegmentIter LiveUnionI; // current position in LiveUnion + SmallVector InterferingVRegs; + bool CheckedFirstInterference; + bool SeenAllInterferences; + bool SeenUnspillableVReg; + unsigned Tag, UserTag; public: - Query(): liu_(), lvr_() {} + Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} - Query(LiveInterval *lvr, LiveIntervalUnion *liu): liu_(liu), lvr_(lvr) {} + Query(LiveInterval *VReg, LiveIntervalUnion *LIU): + LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), + SeenAllInterferences(false), SeenUnspillableVReg(false) + {} void clear() { - liu_ = NULL; - lvr_ = NULL; - firstInterference_ = InterferenceResult(); + LiveUnion = NULL; + VirtReg = NULL; + InterferingVRegs.clear(); + CheckedFirstInterference = false; + SeenAllInterferences = false; + SeenUnspillableVReg = false; + Tag = 0; + UserTag = 0; } - - void init(LiveInterval *lvr, LiveIntervalUnion *liu) { - if (lvr_ == lvr) { - // We currently allow query objects to be reused acrossed live virtual - // registers, but always for the same live interval union. - assert(liu_ == liu && "inconsistent initialization"); + + void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) { + assert(VReg && LIU && "Invalid arguments"); + if (UserTag == UTag && VirtReg == VReg && + LiveUnion == LIU && !LIU->changedSince(Tag)) { // Retain cached results, e.g. firstInterference. return; } - liu_ = liu; - lvr_ = lvr; - // Clear cached results. - firstInterference_ = InterferenceResult(); + clear(); + LiveUnion = LIU; + VirtReg = VReg; + Tag = LIU->getTag(); + UserTag = UTag; } - LiveInterval &lvr() const { assert(lvr_ && "uninitialized"); return *lvr_; } - - bool isInterference(const InterferenceResult &ir) const { - if (ir.lvrSegI_ != lvr_->end()) { - assert(overlap(*ir.lvrSegI_, *ir.liuSegI_) && - "invalid segment iterators"); - return true; - } - return false; + LiveInterval &virtReg() const { + assert(VirtReg && "uninitialized"); + return *VirtReg; } - // Does this live virtual register interfere with the union. - bool checkInterference() { return isInterference(firstInterference()); } + // Does this live virtual register interfere with the union? + bool checkInterference() { return collectInterferingVRegs(1); } + + // Count the virtual registers in this union that interfere with this + // query's live virtual register, up to maxInterferingRegs. + unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); + + // Was this virtual register visited during collectInterferingVRegs? + bool isSeenInterference(LiveInterval *VReg) const; - // Get the first pair of interfering segments, or a noninterfering result. - // This initializes the firstInterference_ cache. - InterferenceResult firstInterference(); + // Did collectInterferingVRegs collect all interferences? + bool seenAllInterferences() const { return SeenAllInterferences; } - // Treat the result as an iterator and advance to the next interfering pair - // of segments. Visiting each unique interfering pairs means that the same - // lvr or liu segment may be visited multiple times. - bool nextInterference(InterferenceResult &ir) const; - - // TBD: bool collectInterferingVirtRegs(unsigned maxInterference) + // Did collectInterferingVRegs encounter an unspillable vreg? + bool seenUnspillableVReg() const { return SeenUnspillableVReg; } + + // Vector generated by collectInterferingVRegs. + const SmallVectorImpl &interferingVRegs() const { + return InterferingVRegs; + } + + /// checkLoopInterference - Return true if there is interference overlapping + /// Loop. + bool checkLoopInterference(MachineLoopRange*); private: - // Private interface for queries - void findIntersection(InterferenceResult &ir) const; + Query(const Query&) LLVM_DELETED_FUNCTION; + void operator=(const Query&) LLVM_DELETED_FUNCTION; + }; + + // Array of LiveIntervalUnions. + class Array { + unsigned Size; + LiveIntervalUnion *LIUs; + public: + Array() : Size(0), LIUs(0) {} + ~Array() { clear(); } + + // Initialize the array to have Size entries. + // Reuse an existing allocation if the size matches. + void init(LiveIntervalUnion::Allocator&, unsigned Size); + + unsigned size() const { return Size; } + + void clear(); + + LiveIntervalUnion& operator[](unsigned idx) { + assert(idx < Size && "idx out of bounds"); + return LIUs[idx]; + } }; };