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