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