InterferenceCache.h revision 224145
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// 10221337Sdim// InterferenceCache remembers per-block interference in LiveIntervalUnions. 11221337Sdim// 12221337Sdim//===----------------------------------------------------------------------===// 13221337Sdim 14221337Sdim#ifndef LLVM_CODEGEN_INTERFERENCECACHE 15221337Sdim#define LLVM_CODEGEN_INTERFERENCECACHE 16221337Sdim 17221337Sdim#include "LiveIntervalUnion.h" 18221337Sdim 19221337Sdimnamespace llvm { 20221337Sdim 21221337Sdimclass InterferenceCache { 22221337Sdim const TargetRegisterInfo *TRI; 23221337Sdim LiveIntervalUnion *LIUArray; 24221337Sdim SlotIndexes *Indexes; 25221337Sdim MachineFunction *MF; 26221337Sdim 27221337Sdim /// BlockInterference - information about the interference in a single basic 28221337Sdim /// block. 29221337Sdim struct BlockInterference { 30221337Sdim BlockInterference() : Tag(0) {} 31221337Sdim unsigned Tag; 32221337Sdim SlotIndex First; 33221337Sdim SlotIndex Last; 34221337Sdim }; 35221337Sdim 36221337Sdim /// Entry - A cache entry containing interference information for all aliases 37221337Sdim /// of PhysReg in all basic blocks. 38221337Sdim class Entry { 39221337Sdim /// PhysReg - The register currently represented. 40221337Sdim unsigned PhysReg; 41221337Sdim 42221337Sdim /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions 43221337Sdim /// change. 44221337Sdim unsigned Tag; 45221337Sdim 46224145Sdim /// RefCount - The total number of Cursor instances referring to this Entry. 47224145Sdim unsigned RefCount; 48224145Sdim 49221337Sdim /// MF - The current function. 50221337Sdim MachineFunction *MF; 51221337Sdim 52221337Sdim /// Indexes - Mapping block numbers to SlotIndex ranges. 53221337Sdim SlotIndexes *Indexes; 54221337Sdim 55221337Sdim /// PrevPos - The previous position the iterators were moved to. 56221337Sdim SlotIndex PrevPos; 57221337Sdim 58221337Sdim /// AliasTags - A LiveIntervalUnion pointer and tag for each alias of 59221337Sdim /// PhysReg. 60221337Sdim SmallVector<std::pair<LiveIntervalUnion*, unsigned>, 8> Aliases; 61221337Sdim 62221337Sdim typedef LiveIntervalUnion::SegmentIter Iter; 63221337Sdim 64221337Sdim /// Iters - an iterator for each alias 65221337Sdim SmallVector<Iter, 8> Iters; 66221337Sdim 67221337Sdim /// Blocks - Interference for each block in the function. 68221337Sdim SmallVector<BlockInterference, 8> Blocks; 69221337Sdim 70221337Sdim /// update - Recompute Blocks[MBBNum] 71221337Sdim void update(unsigned MBBNum); 72221337Sdim 73221337Sdim public: 74224145Sdim Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(0) {} 75221337Sdim 76221337Sdim void clear(MachineFunction *mf, SlotIndexes *indexes) { 77224145Sdim assert(!hasRefs() && "Cannot clear cache entry with references"); 78221337Sdim PhysReg = 0; 79221337Sdim MF = mf; 80221337Sdim Indexes = indexes; 81221337Sdim } 82221337Sdim 83221337Sdim unsigned getPhysReg() const { return PhysReg; } 84221337Sdim 85224145Sdim void addRef(int Delta) { RefCount += Delta; } 86224145Sdim 87224145Sdim bool hasRefs() const { return RefCount > 0; } 88224145Sdim 89221337Sdim void revalidate(); 90221337Sdim 91221337Sdim /// valid - Return true if this is a valid entry for physReg. 92221337Sdim bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI); 93221337Sdim 94221337Sdim /// reset - Initialize entry to represent physReg's aliases. 95221337Sdim void reset(unsigned physReg, 96221337Sdim LiveIntervalUnion *LIUArray, 97221337Sdim const TargetRegisterInfo *TRI, 98221337Sdim const MachineFunction *MF); 99221337Sdim 100221337Sdim /// get - Return an up to date BlockInterference. 101221337Sdim BlockInterference *get(unsigned MBBNum) { 102221337Sdim if (Blocks[MBBNum].Tag != Tag) 103221337Sdim update(MBBNum); 104221337Sdim return &Blocks[MBBNum]; 105221337Sdim } 106221337Sdim }; 107221337Sdim 108221337Sdim // We don't keep a cache entry for every physical register, that would use too 109221337Sdim // much memory. Instead, a fixed number of cache entries are used in a round- 110221337Sdim // robin manner. 111221337Sdim enum { CacheEntries = 32 }; 112221337Sdim 113221337Sdim // Point to an entry for each physreg. The entry pointed to may not be up to 114221337Sdim // date, and it may have been reused for a different physreg. 115221337Sdim SmallVector<unsigned char, 2> PhysRegEntries; 116221337Sdim 117221337Sdim // Next round-robin entry to be picked. 118221337Sdim unsigned RoundRobin; 119221337Sdim 120221337Sdim // The actual cache entries. 121221337Sdim Entry Entries[CacheEntries]; 122221337Sdim 123221337Sdim // get - Get a valid entry for PhysReg. 124221337Sdim Entry *get(unsigned PhysReg); 125221337Sdim 126221337Sdimpublic: 127221337Sdim InterferenceCache() : TRI(0), LIUArray(0), Indexes(0), MF(0), RoundRobin(0) {} 128221337Sdim 129221337Sdim /// init - Prepare cache for a new function. 130221337Sdim void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, 131221337Sdim const TargetRegisterInfo *); 132221337Sdim 133224145Sdim /// getMaxCursors - Return the maximum number of concurrent cursors that can 134224145Sdim /// be supported. 135224145Sdim unsigned getMaxCursors() const { return CacheEntries; } 136224145Sdim 137221337Sdim /// Cursor - The primary query interface for the block interference cache. 138221337Sdim class Cursor { 139221337Sdim Entry *CacheEntry; 140221337Sdim BlockInterference *Current; 141224145Sdim 142224145Sdim void setEntry(Entry *E) { 143224145Sdim Current = 0; 144224145Sdim // Update reference counts. Nothing happens when RefCount reaches 0, so 145224145Sdim // we don't have to check for E == CacheEntry etc. 146224145Sdim if (CacheEntry) 147224145Sdim CacheEntry->addRef(-1); 148224145Sdim CacheEntry = E; 149224145Sdim if (CacheEntry) 150224145Sdim CacheEntry->addRef(+1); 151224145Sdim } 152224145Sdim 153221337Sdim public: 154224145Sdim /// Cursor - Create a dangling cursor. 155224145Sdim Cursor() : CacheEntry(0), Current(0) {} 156224145Sdim ~Cursor() { setEntry(0); } 157221337Sdim 158224145Sdim Cursor(const Cursor &O) : CacheEntry(0), Current(0) { 159224145Sdim setEntry(O.CacheEntry); 160224145Sdim } 161224145Sdim 162224145Sdim Cursor &operator=(const Cursor &O) { 163224145Sdim setEntry(O.CacheEntry); 164224145Sdim return *this; 165224145Sdim } 166224145Sdim 167224145Sdim /// setPhysReg - Point this cursor to PhysReg's interference. 168224145Sdim void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) { 169224145Sdim // Release reference before getting a new one. That guarantees we can 170224145Sdim // actually have CacheEntries live cursors. 171224145Sdim setEntry(0); 172224145Sdim if (PhysReg) 173224145Sdim setEntry(Cache.get(PhysReg)); 174224145Sdim } 175224145Sdim 176221337Sdim /// moveTo - Move cursor to basic block MBBNum. 177221337Sdim void moveToBlock(unsigned MBBNum) { 178221337Sdim Current = CacheEntry->get(MBBNum); 179221337Sdim } 180221337Sdim 181221337Sdim /// hasInterference - Return true if the current block has any interference. 182221337Sdim bool hasInterference() { 183221337Sdim return Current->First.isValid(); 184221337Sdim } 185221337Sdim 186221337Sdim /// first - Return the starting index of the first interfering range in the 187221337Sdim /// current block. 188221337Sdim SlotIndex first() { 189221337Sdim return Current->First; 190221337Sdim } 191221337Sdim 192221337Sdim /// last - Return the ending index of the last interfering range in the 193221337Sdim /// current block. 194221337Sdim SlotIndex last() { 195221337Sdim return Current->Last; 196221337Sdim } 197221337Sdim }; 198221337Sdim 199221337Sdim friend class Cursor; 200221337Sdim}; 201221337Sdim 202221337Sdim} // namespace llvm 203221337Sdim 204221337Sdim#endif 205