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