X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalUnion.h;h=4d41fca85ad32ccbd79229b1280b96d1b6971fe8;hb=3e2d76c946ba753c2b11af192a52e25b6f9b46ff;hp=54761c715f7eb90363c895376fb1b49d617a0f97;hpb=b853e6c3702149cdbbd6fa404334e3ba0055641a;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h index 54761c715f7..4d41fca85ad 100644 --- a/lib/CodeGen/LiveIntervalUnion.h +++ b/lib/CodeGen/LiveIntervalUnion.h @@ -22,19 +22,15 @@ namespace llvm { +class MachineLoopRange; +class TargetRegisterInfo; + #ifndef NDEBUG // forward declaration template class SparseBitVector; typedef SparseBitVector<128> LiveVirtRegBitSet; #endif -/// Abstraction to provide info for the representative register. -class AbstractRegisterDescription { -public: - virtual const char *getName(unsigned Reg) const = 0; - virtual ~AbstractRegisterDescription() {} -}; - /// Compare a live virtual register segment to a LiveIntervalUnion segment. inline bool overlap(const LiveRange &VRSeg, @@ -61,23 +57,32 @@ public: // LiveIntervalUnions share an external allocator. typedef LiveSegments::Allocator Allocator; - class InterferenceResult; class Query; private: - const unsigned RepReg; // representative register number + unsigned Tag; // unique tag for current contents. LiveSegments Segments; // union of virtual reg segments public: - LiveIntervalUnion(unsigned r, Allocator &a) : RepReg(r), Segments(a) {} + 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 find(SlotIndex x) { return Segments.find(x); } - bool empty() { return Segments.empty(); } - SlotIndex startIndex() { return Segments.start(); } + bool empty() const { return Segments.empty(); } + SlotIndex startIndex() const { return Segments.start(); } + + // Provide public access to the underlying map to allow overlap iteration. + typedef LiveSegments Map; + const Map &getMap() { return Segments; } + + /// getTag - Return an opaque tag representing the current state of the union. + unsigned getTag() const { return Tag; } + + /// changedSince - Return true if the union change since getTag returned tag. + bool changedSince(unsigned tag) const { return tag != Tag; } // Add a live virtual register to this union and merge its segments. void unify(LiveInterval &VirtReg); @@ -85,68 +90,36 @@ public: // Remove a live virtual register's segments from this union. void extract(LiveInterval &VirtReg); - void dump(const AbstractRegisterDescription *RegDesc) const; + // Remove all inserted virtual registers. + void clear() { Segments.clear(); ++Tag; } - // If tri != NULL, use it to decode RepReg - void print(raw_ostream &OS, const AbstractRegisterDescription *RegDesc) const; + // Print union, using TRI to translate register names + void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; #ifndef NDEBUG // Verify the live intervals in this union and add them to the visited set. void verify(LiveVirtRegBitSet& VisitedVRegs); #endif - /// 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 VirtRegI; // current position in VirtReg - SegmentIter LiveUnionI; // current position in LiveUnion - - // Internal ctor. - InterferenceResult(LiveInterval::iterator VRegI, SegmentIter UnionI) - : VirtRegI(VRegI), LiveUnionI(UnionI) {} - - public: - // Public default ctor. - InterferenceResult(): VirtRegI(), LiveUnionI() {} - - // Note: this interface provides raw access to the iterators because the - // result has no way to tell if it's valid to dereference them. - - // Access the VirtReg segment. - LiveInterval::iterator virtRegPos() const { return VirtRegI; } - - // Access the LiveUnion segment. - const SegmentIter &liveUnionPos() const { return LiveUnionI; } - - bool operator==(const InterferenceResult &IR) const { - return VirtRegI == IR.VirtRegI && LiveUnionI == IR.LiveUnionI; - } - bool operator!=(const InterferenceResult &IR) const { - return !operator==(IR); - } - }; - /// Query interferences between a single live virtual register and a live /// interval union. class Query { LiveIntervalUnion *LiveUnion; LiveInterval *VirtReg; - InterferenceResult FirstInterference; + 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(): LiveUnion(), VirtReg() {} + Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} Query(LiveInterval *VReg, LiveIntervalUnion *LIU): - LiveUnion(LIU), VirtReg(VReg), SeenAllInterferences(false), - SeenUnspillableVReg(false) + LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), + SeenAllInterferences(false), SeenUnspillableVReg(false) {} void clear() { @@ -156,16 +129,22 @@ public: CheckedFirstInterference = false; SeenAllInterferences = false; SeenUnspillableVReg = false; + Tag = 0; + UserTag = 0; } - void init(LiveInterval *VReg, LiveIntervalUnion *LIU) { - if (VirtReg == VReg && LiveUnion == LIU) { + 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; } clear(); LiveUnion = LIU; VirtReg = VReg; + Tag = LIU->getTag(); + UserTag = UTag; } LiveInterval &virtReg() const { @@ -173,26 +152,8 @@ public: return *VirtReg; } - bool isInterference(const InterferenceResult &IR) const { - if (IR.VirtRegI != VirtReg->end()) { - assert(overlap(*IR.VirtRegI, IR.LiveUnionI) && - "invalid segment iterators"); - return true; - } - return false; - } - // Does this live virtual register interfere with the union? - bool checkInterference() { return isInterference(firstInterference()); } - - // Get the first pair of interfering segments, or a noninterfering result. - // This initializes the firstInterference_ cache. - const InterferenceResult &firstInterference(); - - // Treat the result as an iterator and advance to the next interfering pair - // of segments. Visiting each unique interfering pairs means that the same - // VirtReg or LiveUnion segment may be visited multiple times. - bool nextInterference(InterferenceResult &IR) const; + bool checkInterference() { return collectInterferingVRegs(1); } // Count the virtual registers in this union that interfere with this // query's live virtual register, up to maxInterferingRegs. @@ -212,12 +173,35 @@ public: return InterferingVRegs; } + /// checkLoopInterference - Return true if there is interference overlapping + /// Loop. + bool checkLoopInterference(MachineLoopRange*); + private: - Query(const Query&); // DO NOT IMPLEMENT - void operator=(const Query&); // DO NOT IMPLEMENT + 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(); } - // Private interface for queries - void findIntersection(InterferenceResult &IR) const; + // 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]; + } }; };