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