llvm/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() = default;
  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     MCRegister 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 = MCRegister::NoRegister;
 106       MF = mf;
 107       Indexes = indexes;
 108       LIS = lis;
 109     }
 110
 111     MCRegister 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(MCRegister physReg, LiveIntervalUnion *LIUArray,
 124                const TargetRegisterInfo *TRI, const MachineFunction *MF);
 125
 126     /// get - Return an up to date BlockInterference.
 127     BlockInterference *get(unsigned MBBNum) {
 128       if (Blocks[MBBNum].Tag != Tag)
 129         update(MBBNum);
 130       return &Blocks[MBBNum];
 131     }
 132   };
 133
 134   // We don't keep a cache entry for every physical register, that would use too
 135   // much memory. Instead, a fixed number of cache entries are used in a round-
 136   // robin manner.
 137   enum { CacheEntries = 32 };
 138
 139   const TargetRegisterInfo *TRI = nullptr;
 140   LiveIntervalUnion *LIUArray = nullptr;
 141   MachineFunction *MF = nullptr;
 142
 143   // Point to an entry for each physreg. The entry pointed to may not be up to
 144   // date, and it may have been reused for a different physreg.
 145   unsigned char* PhysRegEntries = nullptr;
 146   size_t PhysRegEntriesCount = 0;
 147
 148   // Next round-robin entry to be picked.
 149   unsigned RoundRobin = 0;
 150
 151   // The actual cache entries.
 152   Entry Entries[CacheEntries];
 153
 154   // get - Get a valid entry for PhysReg.
 155   Entry *get(MCRegister PhysReg);
 156
 157 public:
 158   InterferenceCache() = default;
 159
 160   ~InterferenceCache() {
 161     free(PhysRegEntries);
 162   }
 163
 164   void reinitPhysRegEntries();
 165
 166   /// init - Prepare cache for a new function.
 167   void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
 168             SlotIndexes *indexes, LiveIntervals *lis,
 169             const TargetRegisterInfo *tri);
 170
 171   /// getMaxCursors - Return the maximum number of concurrent cursors that can
 172   /// be supported.
 173   unsigned getMaxCursors() const { return CacheEntries; }
 174
 175   /// Cursor - The primary query interface for the block interference cache.
 176   class Cursor {
 177     Entry *CacheEntry = nullptr;
 178     const BlockInterference *Current = nullptr;
 179     static const BlockInterference NoInterference;
 180
 181     void setEntry(Entry *E) {
 182       Current = nullptr;
 183       // Update reference counts. Nothing happens when RefCount reaches 0, so
 184       // we don't have to check for E == CacheEntry etc.
 185       if (CacheEntry)
 186         CacheEntry->addRef(-1);
 187       CacheEntry = E;
 188       if (CacheEntry)
 189         CacheEntry->addRef(+1);
 190     }
 191
 192   public:
 193     /// Cursor - Create a dangling cursor.
 194     Cursor() = default;
 195
 196     Cursor(const Cursor &O) {
 197       setEntry(O.CacheEntry);
 198     }
 199
 200     Cursor &operator=(const Cursor &O) {
 201       setEntry(O.CacheEntry);
 202       return *this;
 203     }
 204
 205     ~Cursor() { setEntry(nullptr); }
 206
 207     /// setPhysReg - Point this cursor to PhysReg's interference.
 208     void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg) {
 209       // Release reference before getting a new one. That guarantees we can
 210       // actually have CacheEntries live cursors.
 211       setEntry(nullptr);
 212       if (PhysReg.isValid())
 213         setEntry(Cache.get(PhysReg));
 214     }
 215
 216     /// moveTo - Move cursor to basic block MBBNum.
 217     void moveToBlock(unsigned MBBNum) {
 218       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
 219     }
 220
 221     /// hasInterference - Return true if the current block has any interference.
 222     bool hasInterference() {
 223       return Current->First.isValid();
 224     }
 225
 226     /// first - Return the starting index of the first interfering range in the
 227     /// current block.
 228     SlotIndex first() {
 229       return Current->First;
 230     }
 231
 232     /// last - Return the ending index of the last interfering range in the
 233     /// current block.
 234     SlotIndex last() {
 235       return Current->Last;
 236     }
 237   };
 238 };
 239
 240 } // end namespace llvm
 241
 242 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H