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