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