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, const 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(const LiveInterval &VirtReg, const LiveRange &Range); 92 93 // Remove a live virtual register's segments from this union. 94 void extract(const 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 // Get any virtual register that is assign to this physical unit 108 const LiveInterval *getOneVReg() const; 109 110 /// Query interferences between a single live virtual register and a live 111 /// interval union. 112 class Query { 113 const LiveIntervalUnion *LiveUnion = nullptr; 114 const LiveRange *LR = nullptr; 115 LiveRange::const_iterator LRI; ///< current position in LR 116 ConstSegmentIter LiveUnionI; ///< current position in LiveUnion 117 SmallVector<const LiveInterval *, 4> InterferingVRegs; 118 bool CheckedFirstInterference = false; 119 bool SeenAllInterferences = false; 120 unsigned Tag = 0; 121 unsigned UserTag = 0; 122 123 // Count the virtual registers in this union that interfere with this 124 // query's live virtual register, up to maxInterferingRegs. 125 unsigned collectInterferingVRegs(unsigned MaxInterferingRegs); 126 127 // Was this virtual register visited during collectInterferingVRegs? 128 bool isSeenInterference(const LiveInterval *VirtReg) const; 129 130 public: 131 Query() = default; Query(const LiveRange & LR,const LiveIntervalUnion & LIU)132 Query(const LiveRange &LR, const LiveIntervalUnion &LIU) 133 : LiveUnion(&LIU), LR(&LR) {} 134 Query(const Query &) = delete; 135 Query &operator=(const Query &) = delete; 136 reset(unsigned NewUserTag,const LiveRange & NewLR,const LiveIntervalUnion & NewLiveUnion)137 void reset(unsigned NewUserTag, const LiveRange &NewLR, 138 const LiveIntervalUnion &NewLiveUnion) { 139 LiveUnion = &NewLiveUnion; 140 LR = &NewLR; 141 InterferingVRegs.clear(); 142 CheckedFirstInterference = false; 143 SeenAllInterferences = false; 144 Tag = NewLiveUnion.getTag(); 145 UserTag = NewUserTag; 146 } 147 init(unsigned NewUserTag,const LiveRange & NewLR,const LiveIntervalUnion & NewLiveUnion)148 void init(unsigned NewUserTag, const LiveRange &NewLR, 149 const LiveIntervalUnion &NewLiveUnion) { 150 if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion && 151 !NewLiveUnion.changedSince(Tag)) { 152 // Retain cached results, e.g. firstInterference. 153 return; 154 } 155 reset(NewUserTag, NewLR, NewLiveUnion); 156 } 157 158 // Does this live virtual register interfere with the union? checkInterference()159 bool checkInterference() { return collectInterferingVRegs(1); } 160 161 // Vector generated by collectInterferingVRegs. 162 const SmallVectorImpl<const LiveInterval *> &interferingVRegs( 163 unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max()) { 164 if (!SeenAllInterferences || MaxInterferingRegs < InterferingVRegs.size()) 165 collectInterferingVRegs(MaxInterferingRegs); 166 return InterferingVRegs; 167 } 168 }; 169 170 // Array of LiveIntervalUnions. 171 class Array { 172 unsigned Size = 0; 173 LiveIntervalUnion *LIUs = nullptr; 174 175 public: 176 Array() = default; ~Array()177 ~Array() { clear(); } 178 179 // Initialize the array to have Size entries. 180 // Reuse an existing allocation if the size matches. 181 void init(LiveIntervalUnion::Allocator&, unsigned Size); 182 size()183 unsigned size() const { return Size; } 184 185 void clear(); 186 187 LiveIntervalUnion& operator[](unsigned idx) { 188 assert(idx < Size && "idx out of bounds"); 189 return LIUs[idx]; 190 } 191 192 const LiveIntervalUnion& operator[](unsigned Idx) const { 193 assert(Idx < Size && "Idx out of bounds"); 194 return LIUs[Idx]; 195 } 196 }; 197 }; 198 199 } // end namespace llvm 200 201 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H 202