LiveIntervalUnion.h revision 263508
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 23namespace llvm { 24 25class TargetRegisterInfo; 26 27#ifndef NDEBUG 28// forward declaration 29template <unsigned Element> class SparseBitVector; 30typedef SparseBitVector<128> LiveVirtRegBitSet; 31#endif 32 33/// Compare a live virtual register segment to a LiveIntervalUnion segment. 34inline bool 35overlap(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. 44class 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 50public: 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 61private: 62 unsigned Tag; // unique tag for current contents. 63 LiveSegments Segments; // union of virtual reg segments 64 65public: 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); 88 89 // Remove a live virtual register's segments from this union. 90 void extract(LiveInterval &VirtReg); 91 92 // Remove all inserted virtual registers. 93 void clear() { Segments.clear(); ++Tag; } 94 95 // Print union, using TRI to translate register names 96 void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; 97 98#ifndef NDEBUG 99 // Verify the live intervals in this union and add them to the visited set. 100 void verify(LiveVirtRegBitSet& VisitedVRegs); 101#endif 102 103 /// Query interferences between a single live virtual register and a live 104 /// interval union. 105 class Query { 106 LiveIntervalUnion *LiveUnion; 107 LiveInterval *VirtReg; 108 LiveInterval::iterator VirtRegI; // current position in VirtReg 109 SegmentIter LiveUnionI; // current position in LiveUnion 110 SmallVector<LiveInterval*,4> InterferingVRegs; 111 bool CheckedFirstInterference; 112 bool SeenAllInterferences; 113 bool SeenUnspillableVReg; 114 unsigned Tag, UserTag; 115 116 public: 117 Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} 118 119 Query(LiveInterval *VReg, LiveIntervalUnion *LIU): 120 LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), 121 SeenAllInterferences(false), SeenUnspillableVReg(false) 122 {} 123 124 void clear() { 125 LiveUnion = NULL; 126 VirtReg = NULL; 127 InterferingVRegs.clear(); 128 CheckedFirstInterference = false; 129 SeenAllInterferences = false; 130 SeenUnspillableVReg = false; 131 Tag = 0; 132 UserTag = 0; 133 } 134 135 void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) { 136 assert(VReg && LIU && "Invalid arguments"); 137 if (UserTag == UTag && VirtReg == VReg && 138 LiveUnion == LIU && !LIU->changedSince(Tag)) { 139 // Retain cached results, e.g. firstInterference. 140 return; 141 } 142 clear(); 143 LiveUnion = LIU; 144 VirtReg = VReg; 145 Tag = LIU->getTag(); 146 UserTag = UTag; 147 } 148 149 LiveInterval &virtReg() const { 150 assert(VirtReg && "uninitialized"); 151 return *VirtReg; 152 } 153 154 // Does this live virtual register interfere with the union? 155 bool checkInterference() { return collectInterferingVRegs(1); } 156 157 // Count the virtual registers in this union that interfere with this 158 // query's live virtual register, up to maxInterferingRegs. 159 unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); 160 161 // Was this virtual register visited during collectInterferingVRegs? 162 bool isSeenInterference(LiveInterval *VReg) const; 163 164 // Did collectInterferingVRegs collect all interferences? 165 bool seenAllInterferences() const { return SeenAllInterferences; } 166 167 // Did collectInterferingVRegs encounter an unspillable vreg? 168 bool seenUnspillableVReg() const { return SeenUnspillableVReg; } 169 170 // Vector generated by collectInterferingVRegs. 171 const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { 172 return InterferingVRegs; 173 } 174 175 private: 176 Query(const Query&) LLVM_DELETED_FUNCTION; 177 void operator=(const Query&) LLVM_DELETED_FUNCTION; 178 }; 179 180 // Array of LiveIntervalUnions. 181 class Array { 182 unsigned Size; 183 LiveIntervalUnion *LIUs; 184 public: 185 Array() : Size(0), LIUs(0) {} 186 ~Array() { clear(); } 187 188 // Initialize the array to have Size entries. 189 // Reuse an existing allocation if the size matches. 190 void init(LiveIntervalUnion::Allocator&, unsigned Size); 191 192 unsigned size() const { return Size; } 193 194 void clear(); 195 196 LiveIntervalUnion& operator[](unsigned idx) { 197 assert(idx < Size && "idx out of bounds"); 198 return LIUs[idx]; 199 } 200 }; 201}; 202 203} // end namespace llvm 204 205#endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION_H) 206