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 = nullptr;
  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   InterferenceCache &operator=(const InterferenceCache &other) = delete;
 160   InterferenceCache(const InterferenceCache &other) = delete;
 161   ~InterferenceCache() {
 162     free(PhysRegEntries);
 163   }
 164
 165   void reinitPhysRegEntries();
 166
 167   /// init - Prepare cache for a new function.
 168   void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
 169             SlotIndexes *indexes, LiveIntervals *lis,
 170             const TargetRegisterInfo *tri);
 171
 172   /// getMaxCursors - Return the maximum number of concurrent cursors that can
 173   /// be supported.
 174   unsigned getMaxCursors() const { return CacheEntries; }
 175
 176   /// Cursor - The primary query interface for the block interference cache.
 177   class Cursor {
 178     Entry *CacheEntry = nullptr;
 179     const BlockInterference *Current = nullptr;
 180     static const BlockInterference NoInterference;
 181
 182     void setEntry(Entry *E) {
 183       Current = nullptr;
 184       // Update reference counts. Nothing happens when RefCount reaches 0, so
 185       // we don't have to check for E == CacheEntry etc.
 186       if (CacheEntry)
 187         CacheEntry->addRef(-1);
 188       CacheEntry = E;
 189       if (CacheEntry)
 190         CacheEntry->addRef(+1);
 191     }
 192
 193   public:
 194     /// Cursor - Create a dangling cursor.
 195     Cursor() = default;
 196
 197     Cursor(const Cursor &O) {
 198       setEntry(O.CacheEntry);
 199     }
 200
 201     Cursor &operator=(const Cursor &O) {
 202       setEntry(O.CacheEntry);
 203       return *this;
 204     }
 205
 206     ~Cursor() { setEntry(nullptr); }
 207
 208     /// setPhysReg - Point this cursor to PhysReg's interference.
 209     void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg) {
 210       // Release reference before getting a new one. That guarantees we can
 211       // actually have CacheEntries live cursors.
 212       setEntry(nullptr);
 213       if (PhysReg.isValid())
 214         setEntry(Cache.get(PhysReg));
 215     }
 216
 217     /// moveTo - Move cursor to basic block MBBNum.
 218     void moveToBlock(unsigned MBBNum) {
 219       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
 220     }
 221
 222     /// hasInterference - Return true if the current block has any interference.
 223     bool hasInterference() {
 224       return Current->First.isValid();
 225     }
 226
 227     /// first - Return the starting index of the first interfering range in the
 228     /// current block.
 229     SlotIndex first() {
 230       return Current->First;
 231     }
 232
 233     /// last - Return the ending index of the last interfering range in the
 234     /// current block.
 235     SlotIndex last() {
 236       return Current->Last;
 237     }
 238   };
 239 };
 240
 241 } // end namespace llvm
 242
 243 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H