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