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