1 //===- InterferenceCache.h - Caching per-block interference ----*- 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 // InterferenceCache remembers per-block interference from LiveIntervalUnions, 10 // fixed RegUnit interference, and register masks. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_LIB_CODEGEN_INTERFERENCECACHE_H 15 #define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H 16 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/CodeGen/LiveInterval.h" 19 #include "llvm/CodeGen/LiveIntervalUnion.h" 20 #include "llvm/CodeGen/SlotIndexes.h" 21 #include "llvm/Support/Compiler.h" 22 #include <cassert> 23 #include <cstddef> 24 #include <cstdlib> 25 26 namespace llvm { 27 28 class LiveIntervals; 29 class MachineFunction; 30 class TargetRegisterInfo; 31 32 class LLVM_LIBRARY_VISIBILITY InterferenceCache { 33 /// BlockInterference - information about the interference in a single basic 34 /// block. 35 struct BlockInterference { 36 unsigned Tag = 0; 37 SlotIndex First; 38 SlotIndex Last; 39 40 BlockInterference() {} 41 }; 42 43 /// Entry - A cache entry containing interference information for all aliases 44 /// of PhysReg in all basic blocks. 45 class Entry { 46 /// PhysReg - The register currently represented. 47 MCRegister PhysReg = 0; 48 49 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions 50 /// change. 51 unsigned Tag = 0; 52 53 /// RefCount - The total number of Cursor instances referring to this Entry. 54 unsigned RefCount = 0; 55 56 /// MF - The current function. 57 MachineFunction *MF; 58 59 /// Indexes - Mapping block numbers to SlotIndex ranges. 60 SlotIndexes *Indexes = nullptr; 61 62 /// LIS - Used for accessing register mask interference maps. 63 LiveIntervals *LIS = nullptr; 64 65 /// PrevPos - The previous position the iterators were moved to. 66 SlotIndex PrevPos; 67 68 /// RegUnitInfo - Information tracked about each RegUnit in PhysReg. 69 /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos) 70 /// had just been called. 71 struct RegUnitInfo { 72 /// Iterator pointing into the LiveIntervalUnion containing virtual 73 /// register interference. 74 LiveIntervalUnion::SegmentIter VirtI; 75 76 /// Tag of the LIU last time we looked. 77 unsigned VirtTag; 78 79 /// Fixed interference in RegUnit. 80 LiveRange *Fixed = nullptr; 81 82 /// Iterator pointing into the fixed RegUnit interference. 83 LiveInterval::iterator FixedI; 84 85 RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) { 86 VirtI.setMap(LIU.getMap()); 87 } 88 }; 89 90 /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have 91 /// more than 4 RegUnits. 92 SmallVector<RegUnitInfo, 4> RegUnits; 93 94 /// Blocks - Interference for each block in the function. 95 SmallVector<BlockInterference, 8> Blocks; 96 97 /// update - Recompute Blocks[MBBNum] 98 void update(unsigned MBBNum); 99 100 public: 101 Entry() = default; 102 103 void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) { 104 assert(!hasRefs() && "Cannot clear cache entry with references"); 105 PhysReg = MCRegister::NoRegister; 106 MF = mf; 107 Indexes = indexes; 108 LIS = lis; 109 } 110 111 MCRegister getPhysReg() const { return PhysReg; } 112 113 void addRef(int Delta) { RefCount += Delta; } 114 115 bool hasRefs() const { return RefCount > 0; } 116 117 void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI); 118 119 /// valid - Return true if this is a valid entry for physReg. 120 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI); 121 122 /// reset - Initialize entry to represent physReg's aliases. 123 void reset(MCRegister physReg, LiveIntervalUnion *LIUArray, 124 const TargetRegisterInfo *TRI, const MachineFunction *MF); 125 126 /// get - Return an up to date BlockInterference. 127 BlockInterference *get(unsigned MBBNum) { 128 if (Blocks[MBBNum].Tag != Tag) 129 update(MBBNum); 130 return &Blocks[MBBNum]; 131 } 132 }; 133 134 // We don't keep a cache entry for every physical register, that would use too 135 // much memory. Instead, a fixed number of cache entries are used in a round- 136 // robin manner. 137 enum { CacheEntries = 32 }; 138 139 const TargetRegisterInfo *TRI = nullptr; 140 LiveIntervalUnion *LIUArray = nullptr; 141 MachineFunction *MF = nullptr; 142 143 // Point to an entry for each physreg. The entry pointed to may not be up to 144 // date, and it may have been reused for a different physreg. 145 unsigned char* PhysRegEntries = nullptr; 146 size_t PhysRegEntriesCount = 0; 147 148 // Next round-robin entry to be picked. 149 unsigned RoundRobin = 0; 150 151 // The actual cache entries. 152 Entry Entries[CacheEntries]; 153 154 // get - Get a valid entry for PhysReg. 155 Entry *get(MCRegister PhysReg); 156 157 public: 158 InterferenceCache() = default; 159 160 ~InterferenceCache() { 161 free(PhysRegEntries); 162 } 163 164 void reinitPhysRegEntries(); 165 166 /// init - Prepare cache for a new function. 167 void init(MachineFunction *mf, LiveIntervalUnion *liuarray, 168 SlotIndexes *indexes, LiveIntervals *lis, 169 const TargetRegisterInfo *tri); 170 171 /// getMaxCursors - Return the maximum number of concurrent cursors that can 172 /// be supported. 173 unsigned getMaxCursors() const { return CacheEntries; } 174 175 /// Cursor - The primary query interface for the block interference cache. 176 class Cursor { 177 Entry *CacheEntry = nullptr; 178 const BlockInterference *Current = nullptr; 179 static const BlockInterference NoInterference; 180 181 void setEntry(Entry *E) { 182 Current = nullptr; 183 // Update reference counts. Nothing happens when RefCount reaches 0, so 184 // we don't have to check for E == CacheEntry etc. 185 if (CacheEntry) 186 CacheEntry->addRef(-1); 187 CacheEntry = E; 188 if (CacheEntry) 189 CacheEntry->addRef(+1); 190 } 191 192 public: 193 /// Cursor - Create a dangling cursor. 194 Cursor() = default; 195 196 Cursor(const Cursor &O) { 197 setEntry(O.CacheEntry); 198 } 199 200 Cursor &operator=(const Cursor &O) { 201 setEntry(O.CacheEntry); 202 return *this; 203 } 204 205 ~Cursor() { setEntry(nullptr); } 206 207 /// setPhysReg - Point this cursor to PhysReg's interference. 208 void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg) { 209 // Release reference before getting a new one. That guarantees we can 210 // actually have CacheEntries live cursors. 211 setEntry(nullptr); 212 if (PhysReg.isValid()) 213 setEntry(Cache.get(PhysReg)); 214 } 215 216 /// moveTo - Move cursor to basic block MBBNum. 217 void moveToBlock(unsigned MBBNum) { 218 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference; 219 } 220 221 /// hasInterference - Return true if the current block has any interference. 222 bool hasInterference() { 223 return Current->First.isValid(); 224 } 225 226 /// first - Return the starting index of the first interfering range in the 227 /// current block. 228 SlotIndex first() { 229 return Current->First; 230 } 231 232 /// last - Return the ending index of the last interfering range in the 233 /// current block. 234 SlotIndex last() { 235 return Current->Last; 236 } 237 }; 238 }; 239 240 } // end namespace llvm 241 242 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H 243