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