1221337Sdim//===-- InterferenceCache.h - Caching per-block interference ---*- C++ -*--===// 2221337Sdim// 3221337Sdim// The LLVM Compiler Infrastructure 4221337Sdim// 5221337Sdim// This file is distributed under the University of Illinois Open Source 6221337Sdim// License. See LICENSE.TXT for details. 7221337Sdim// 8221337Sdim//===----------------------------------------------------------------------===// 9221337Sdim// 10239462Sdim// InterferenceCache remembers per-block interference from LiveIntervalUnions, 11239462Sdim// fixed RegUnit interference, and register masks. 12221337Sdim// 13221337Sdim//===----------------------------------------------------------------------===// 14221337Sdim 15221337Sdim#ifndef LLVM_CODEGEN_INTERFERENCECACHE 16221337Sdim#define LLVM_CODEGEN_INTERFERENCECACHE 17221337Sdim 18249423Sdim#include "llvm/CodeGen/LiveIntervalUnion.h" 19221337Sdim 20221337Sdimnamespace llvm { 21221337Sdim 22234353Sdimclass LiveIntervals; 23234353Sdim 24221337Sdimclass InterferenceCache { 25221337Sdim const TargetRegisterInfo *TRI; 26221337Sdim LiveIntervalUnion *LIUArray; 27221337Sdim MachineFunction *MF; 28221337Sdim 29221337Sdim /// BlockInterference - information about the interference in a single basic 30221337Sdim /// block. 31221337Sdim struct BlockInterference { 32221337Sdim BlockInterference() : Tag(0) {} 33221337Sdim unsigned Tag; 34221337Sdim SlotIndex First; 35221337Sdim SlotIndex Last; 36221337Sdim }; 37221337Sdim 38221337Sdim /// Entry - A cache entry containing interference information for all aliases 39221337Sdim /// of PhysReg in all basic blocks. 40221337Sdim class Entry { 41221337Sdim /// PhysReg - The register currently represented. 42221337Sdim unsigned PhysReg; 43221337Sdim 44221337Sdim /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions 45221337Sdim /// change. 46221337Sdim unsigned Tag; 47221337Sdim 48224145Sdim /// RefCount - The total number of Cursor instances referring to this Entry. 49224145Sdim unsigned RefCount; 50224145Sdim 51221337Sdim /// MF - The current function. 52221337Sdim MachineFunction *MF; 53221337Sdim 54221337Sdim /// Indexes - Mapping block numbers to SlotIndex ranges. 55221337Sdim SlotIndexes *Indexes; 56221337Sdim 57234353Sdim /// LIS - Used for accessing register mask interference maps. 58234353Sdim LiveIntervals *LIS; 59234353Sdim 60221337Sdim /// PrevPos - The previous position the iterators were moved to. 61221337Sdim SlotIndex PrevPos; 62221337Sdim 63239462Sdim /// RegUnitInfo - Information tracked about each RegUnit in PhysReg. 64239462Sdim /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos) 65239462Sdim /// had just been called. 66239462Sdim struct RegUnitInfo { 67239462Sdim /// Iterator pointing into the LiveIntervalUnion containing virtual 68239462Sdim /// register interference. 69239462Sdim LiveIntervalUnion::SegmentIter VirtI; 70221337Sdim 71239462Sdim /// Tag of the LIU last time we looked. 72239462Sdim unsigned VirtTag; 73221337Sdim 74239462Sdim /// Fixed interference in RegUnit. 75263508Sdim LiveRange *Fixed; 76221337Sdim 77239462Sdim /// Iterator pointing into the fixed RegUnit interference. 78239462Sdim LiveInterval::iterator FixedI; 79239462Sdim 80239462Sdim RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()), Fixed(0) { 81239462Sdim VirtI.setMap(LIU.getMap()); 82239462Sdim } 83239462Sdim }; 84239462Sdim 85239462Sdim /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have 86239462Sdim /// more than 4 RegUnits. 87239462Sdim SmallVector<RegUnitInfo, 4> RegUnits; 88239462Sdim 89221337Sdim /// Blocks - Interference for each block in the function. 90221337Sdim SmallVector<BlockInterference, 8> Blocks; 91221337Sdim 92221337Sdim /// update - Recompute Blocks[MBBNum] 93221337Sdim void update(unsigned MBBNum); 94221337Sdim 95221337Sdim public: 96234353Sdim Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(0), LIS(0) {} 97221337Sdim 98234353Sdim void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) { 99224145Sdim assert(!hasRefs() && "Cannot clear cache entry with references"); 100221337Sdim PhysReg = 0; 101221337Sdim MF = mf; 102221337Sdim Indexes = indexes; 103234353Sdim LIS = lis; 104221337Sdim } 105221337Sdim 106221337Sdim unsigned getPhysReg() const { return PhysReg; } 107221337Sdim 108224145Sdim void addRef(int Delta) { RefCount += Delta; } 109224145Sdim 110224145Sdim bool hasRefs() const { return RefCount > 0; } 111224145Sdim 112239462Sdim void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI); 113221337Sdim 114221337Sdim /// valid - Return true if this is a valid entry for physReg. 115221337Sdim bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI); 116221337Sdim 117221337Sdim /// reset - Initialize entry to represent physReg's aliases. 118221337Sdim void reset(unsigned physReg, 119221337Sdim LiveIntervalUnion *LIUArray, 120221337Sdim const TargetRegisterInfo *TRI, 121221337Sdim const MachineFunction *MF); 122221337Sdim 123221337Sdim /// get - Return an up to date BlockInterference. 124221337Sdim BlockInterference *get(unsigned MBBNum) { 125221337Sdim if (Blocks[MBBNum].Tag != Tag) 126221337Sdim update(MBBNum); 127221337Sdim return &Blocks[MBBNum]; 128221337Sdim } 129221337Sdim }; 130221337Sdim 131221337Sdim // We don't keep a cache entry for every physical register, that would use too 132221337Sdim // much memory. Instead, a fixed number of cache entries are used in a round- 133221337Sdim // robin manner. 134221337Sdim enum { CacheEntries = 32 }; 135221337Sdim 136221337Sdim // Point to an entry for each physreg. The entry pointed to may not be up to 137221337Sdim // date, and it may have been reused for a different physreg. 138221337Sdim SmallVector<unsigned char, 2> PhysRegEntries; 139221337Sdim 140221337Sdim // Next round-robin entry to be picked. 141221337Sdim unsigned RoundRobin; 142221337Sdim 143221337Sdim // The actual cache entries. 144221337Sdim Entry Entries[CacheEntries]; 145221337Sdim 146221337Sdim // get - Get a valid entry for PhysReg. 147221337Sdim Entry *get(unsigned PhysReg); 148221337Sdim 149221337Sdimpublic: 150234353Sdim InterferenceCache() : TRI(0), LIUArray(0), MF(0), RoundRobin(0) {} 151221337Sdim 152221337Sdim /// init - Prepare cache for a new function. 153234353Sdim void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*, 154221337Sdim const TargetRegisterInfo *); 155221337Sdim 156224145Sdim /// getMaxCursors - Return the maximum number of concurrent cursors that can 157224145Sdim /// be supported. 158224145Sdim unsigned getMaxCursors() const { return CacheEntries; } 159224145Sdim 160221337Sdim /// Cursor - The primary query interface for the block interference cache. 161221337Sdim class Cursor { 162221337Sdim Entry *CacheEntry; 163221337Sdim BlockInterference *Current; 164226633Sdim static BlockInterference NoInterference; 165224145Sdim 166224145Sdim void setEntry(Entry *E) { 167224145Sdim Current = 0; 168224145Sdim // Update reference counts. Nothing happens when RefCount reaches 0, so 169224145Sdim // we don't have to check for E == CacheEntry etc. 170224145Sdim if (CacheEntry) 171224145Sdim CacheEntry->addRef(-1); 172224145Sdim CacheEntry = E; 173224145Sdim if (CacheEntry) 174224145Sdim CacheEntry->addRef(+1); 175224145Sdim } 176224145Sdim 177221337Sdim public: 178224145Sdim /// Cursor - Create a dangling cursor. 179224145Sdim Cursor() : CacheEntry(0), Current(0) {} 180224145Sdim ~Cursor() { setEntry(0); } 181221337Sdim 182224145Sdim Cursor(const Cursor &O) : CacheEntry(0), Current(0) { 183224145Sdim setEntry(O.CacheEntry); 184224145Sdim } 185224145Sdim 186224145Sdim Cursor &operator=(const Cursor &O) { 187224145Sdim setEntry(O.CacheEntry); 188224145Sdim return *this; 189224145Sdim } 190224145Sdim 191224145Sdim /// setPhysReg - Point this cursor to PhysReg's interference. 192224145Sdim void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) { 193224145Sdim // Release reference before getting a new one. That guarantees we can 194224145Sdim // actually have CacheEntries live cursors. 195224145Sdim setEntry(0); 196224145Sdim if (PhysReg) 197224145Sdim setEntry(Cache.get(PhysReg)); 198224145Sdim } 199224145Sdim 200221337Sdim /// moveTo - Move cursor to basic block MBBNum. 201221337Sdim void moveToBlock(unsigned MBBNum) { 202226633Sdim Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference; 203221337Sdim } 204221337Sdim 205221337Sdim /// hasInterference - Return true if the current block has any interference. 206221337Sdim bool hasInterference() { 207221337Sdim return Current->First.isValid(); 208221337Sdim } 209221337Sdim 210221337Sdim /// first - Return the starting index of the first interfering range in the 211221337Sdim /// current block. 212221337Sdim SlotIndex first() { 213221337Sdim return Current->First; 214221337Sdim } 215221337Sdim 216221337Sdim /// last - Return the ending index of the last interfering range in the 217221337Sdim /// current block. 218221337Sdim SlotIndex last() { 219221337Sdim return Current->Last; 220221337Sdim } 221221337Sdim }; 222221337Sdim 223221337Sdim friend class Cursor; 224221337Sdim}; 225221337Sdim 226221337Sdim} // namespace llvm 227221337Sdim 228221337Sdim#endif 229