1 //===-- LiveIntervalUnion.h - Live interval union data struct --*- C++ -*--===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // LiveIntervalUnion is a union of live segments across multiple live virtual 11 // registers. This may be used during coalescing to represent a congruence 12 // class, or during register allocation to model liveness of a physical 13 // register. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef LLVM_CODEGEN_LIVEINTERVALUNION 18 #define LLVM_CODEGEN_LIVEINTERVALUNION 19 20 #include "llvm/ADT/IntervalMap.h" 21 #include "llvm/CodeGen/LiveInterval.h" 22 23 namespace llvm { 24 25 class MachineLoopRange; 26 class TargetRegisterInfo; 27 28 #ifndef NDEBUG 29 // forward declaration 30 template <unsigned Element> class SparseBitVector; 31 typedef SparseBitVector<128> LiveVirtRegBitSet; 32 #endif 33 34 /// Compare a live virtual register segment to a LiveIntervalUnion segment. 35 inline bool 36 overlap(const LiveRange &VRSeg, 37 const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) { 38 return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; 39 } 40 41 /// Union of live intervals that are strong candidates for coalescing into a 42 /// single register (either physical or virtual depending on the context). We 43 /// expect the constituent live intervals to be disjoint, although we may 44 /// eventually make exceptions to handle value-based interference. 45 class LiveIntervalUnion { 46 // A set of live virtual register segments that supports fast insertion, 47 // intersection, and removal. 48 // Mapping SlotIndex intervals to virtual register numbers. 49 typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments; 50 51 public: 52 // SegmentIter can advance to the next segment ordered by starting position 53 // which may belong to a different live virtual register. We also must be able 54 // to reach the current segment's containing virtual register. 55 typedef LiveSegments::iterator SegmentIter; 56 57 // LiveIntervalUnions share an external allocator. 58 typedef LiveSegments::Allocator Allocator; 59 60 class Query; 61 62 private: 63 unsigned Tag; // unique tag for current contents. 64 LiveSegments Segments; // union of virtual reg segments 65 66 public: 67 explicit LiveIntervalUnion(Allocator &a) : Tag(0), Segments(a) {} 68 69 // Iterate over all segments in the union of live virtual registers ordered 70 // by their starting position. 71 SegmentIter begin() { return Segments.begin(); } 72 SegmentIter end() { return Segments.end(); } 73 SegmentIter find(SlotIndex x) { return Segments.find(x); } 74 bool empty() const { return Segments.empty(); } 75 SlotIndex startIndex() const { return Segments.start(); } 76 77 // Provide public access to the underlying map to allow overlap iteration. 78 typedef LiveSegments Map; 79 const Map &getMap() { return Segments; } 80 81 /// getTag - Return an opaque tag representing the current state of the union. 82 unsigned getTag() const { return Tag; } 83 84 /// changedSince - Return true if the union change since getTag returned tag. 85 bool changedSince(unsigned tag) const { return tag != Tag; } 86 87 // Add a live virtual register to this union and merge its segments. 88 void unify(LiveInterval &VirtReg); 89 90 // Remove a live virtual register's segments from this union. 91 void extract(LiveInterval &VirtReg); 92 93 // Remove all inserted virtual registers. 94 void clear() { Segments.clear(); ++Tag; } 95 96 // Print union, using TRI to translate register names 97 void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; 98 99 #ifndef NDEBUG 100 // Verify the live intervals in this union and add them to the visited set. 101 void verify(LiveVirtRegBitSet& VisitedVRegs); 102 #endif 103 104 /// Query interferences between a single live virtual register and a live 105 /// interval union. 106 class Query { 107 LiveIntervalUnion *LiveUnion; 108 LiveInterval *VirtReg; 109 LiveInterval::iterator VirtRegI; // current position in VirtReg 110 SegmentIter LiveUnionI; // current position in LiveUnion 111 SmallVector<LiveInterval*,4> InterferingVRegs; 112 bool CheckedFirstInterference; 113 bool SeenAllInterferences; 114 bool SeenUnspillableVReg; 115 unsigned Tag, UserTag; 116 117 public: 118 Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} 119 120 Query(LiveInterval *VReg, LiveIntervalUnion *LIU): 121 LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), 122 SeenAllInterferences(false), SeenUnspillableVReg(false) 123 {} 124 125 void clear() { 126 LiveUnion = NULL; 127 VirtReg = NULL; 128 InterferingVRegs.clear(); 129 CheckedFirstInterference = false; 130 SeenAllInterferences = false; 131 SeenUnspillableVReg = false; 132 Tag = 0; 133 UserTag = 0; 134 } 135 136 void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) { 137 assert(VReg && LIU && "Invalid arguments"); 138 if (UserTag == UTag && VirtReg == VReg && 139 LiveUnion == LIU && !LIU->changedSince(Tag)) { 140 // Retain cached results, e.g. firstInterference. 141 return; 142 } 143 clear(); 144 LiveUnion = LIU; 145 VirtReg = VReg; 146 Tag = LIU->getTag(); 147 UserTag = UTag; 148 } 149 150 LiveInterval &virtReg() const { 151 assert(VirtReg && "uninitialized"); 152 return *VirtReg; 153 } 154 155 // Does this live virtual register interfere with the union? 156 bool checkInterference() { return collectInterferingVRegs(1); } 157 158 // Count the virtual registers in this union that interfere with this 159 // query's live virtual register, up to maxInterferingRegs. 160 unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); 161 162 // Was this virtual register visited during collectInterferingVRegs? 163 bool isSeenInterference(LiveInterval *VReg) const; 164 165 // Did collectInterferingVRegs collect all interferences? 166 bool seenAllInterferences() const { return SeenAllInterferences; } 167 168 // Did collectInterferingVRegs encounter an unspillable vreg? 169 bool seenUnspillableVReg() const { return SeenUnspillableVReg; } 170 171 // Vector generated by collectInterferingVRegs. 172 const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { 173 return InterferingVRegs; 174 } 175 176 /// checkLoopInterference - Return true if there is interference overlapping 177 /// Loop. 178 bool checkLoopInterference(MachineLoopRange*); 179 180 private: 181 Query(const Query&); // DO NOT IMPLEMENT 182 void operator=(const Query&); // DO NOT IMPLEMENT 183 }; 184 185 // Array of LiveIntervalUnions. 186 class Array { 187 unsigned Size; 188 LiveIntervalUnion *LIUs; 189 public: 190 Array() : Size(0), LIUs(0) {} 191 ~Array() { clear(); } 192 193 // Initialize the array to have Size entries. 194 // Reuse an existing allocation if the size matches. 195 void init(LiveIntervalUnion::Allocator&, unsigned Size); 196 197 unsigned size() const { return Size; } 198 199 void clear(); 200 201 LiveIntervalUnion& operator[](unsigned idx) { 202 assert(idx < Size && "idx out of bounds"); 203 return LIUs[idx]; 204 } 205 }; 206 }; 207 208 } // end namespace llvm 209 210 #endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION) 211
