lib/CodeGen/InterferenceCache.h

   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   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
 125 public:
 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