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