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