lib/CodeGen/InterferenceCache.h

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