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