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