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/CodeGen/LiveIntervalUnion.h"
  19
  20 namespace llvm {
  21
  22 class LiveIntervals;
  23
  24 class LLVM_LIBRARY_VISIBILITY 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)
  81           : VirtTag(LIU.getTag()), Fixed(nullptr) {
  82         VirtI.setMap(LIU.getMap());
  83       }
  84     };
  85
  86     /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
  87     /// more than 4 RegUnits.
  88     SmallVector<RegUnitInfo, 4> RegUnits;
  89
  90     /// Blocks - Interference for each block in the function.
  91     SmallVector<BlockInterference, 8> Blocks;
  92
  93     /// update - Recompute Blocks[MBBNum]
  94     void update(unsigned MBBNum);
  95
  96   public:
  97     Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(nullptr), LIS(nullptr) {}
  98
  99     void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
 100       assert(!hasRefs() && "Cannot clear cache entry with references");
 101       PhysReg = 0;
 102       MF = mf;
 103       Indexes = indexes;
 104       LIS = lis;
 105     }
 106
 107     unsigned getPhysReg() const { return PhysReg; }
 108
 109     void addRef(int Delta) { RefCount += Delta; }
 110
 111     bool hasRefs() const { return RefCount > 0; }
 112
 113     void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
 114
 115     /// valid - Return true if this is a valid entry for physReg.
 116     bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
 117
 118     /// reset - Initialize entry to represent physReg's aliases.
 119     void reset(unsigned physReg,
 120                LiveIntervalUnion *LIUArray,
 121                const TargetRegisterInfo *TRI,
 122                const MachineFunction *MF);
 123
 124     /// get - Return an up to date BlockInterference.
 125     BlockInterference *get(unsigned MBBNum) {
 126       if (Blocks[MBBNum].Tag != Tag)
 127         update(MBBNum);
 128       return &Blocks[MBBNum];
 129     }
 130   };
 131
 132   // We don't keep a cache entry for every physical register, that would use too
 133   // much memory. Instead, a fixed number of cache entries are used in a round-
 134   // robin manner.
 135   enum { CacheEntries = 32 };
 136
 137   // Point to an entry for each physreg. The entry pointed to may not be up to
 138   // date, and it may have been reused for a different physreg.
 139   unsigned char* PhysRegEntries;
 140   size_t PhysRegEntriesCount;
 141
 142   // Next round-robin entry to be picked.
 143   unsigned RoundRobin;
 144
 145   // The actual cache entries.
 146   Entry Entries[CacheEntries];
 147
 148   // get - Get a valid entry for PhysReg.
 149   Entry *get(unsigned PhysReg);
 150
 151 public:
 152   InterferenceCache()
 153     : TRI(nullptr), LIUArray(nullptr), MF(nullptr), PhysRegEntries(nullptr),
 154       PhysRegEntriesCount(0), RoundRobin(0) {}
 155
 156   ~InterferenceCache() {
 157     free(PhysRegEntries);
 158   }
 159
 160   void reinitPhysRegEntries();
 161
 162   /// init - Prepare cache for a new function.
 163   void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*,
 164             const TargetRegisterInfo *);
 165
 166   /// getMaxCursors - Return the maximum number of concurrent cursors that can
 167   /// be supported.
 168   unsigned getMaxCursors() const { return CacheEntries; }
 169
 170   /// Cursor - The primary query interface for the block interference cache.
 171   class Cursor {
 172     Entry *CacheEntry;
 173     const BlockInterference *Current;
 174     static const BlockInterference NoInterference;
 175
 176     void setEntry(Entry *E) {
 177       Current = nullptr;
 178       // Update reference counts. Nothing happens when RefCount reaches 0, so
 179       // we don't have to check for E == CacheEntry etc.
 180       if (CacheEntry)
 181         CacheEntry->addRef(-1);
 182       CacheEntry = E;
 183       if (CacheEntry)
 184         CacheEntry->addRef(+1);
 185     }
 186
 187   public:
 188     /// Cursor - Create a dangling cursor.
 189     Cursor() : CacheEntry(nullptr), Current(nullptr) {}
 190     ~Cursor() { setEntry(nullptr); }
 191
 192     Cursor(const Cursor &O) : CacheEntry(nullptr), Current(nullptr) {
 193       setEntry(O.CacheEntry);
 194     }
 195
 196     Cursor &operator=(const Cursor &O) {
 197       setEntry(O.CacheEntry);
 198       return *this;
 199     }
 200
 201     /// setPhysReg - Point this cursor to PhysReg's interference.
 202     void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
 203       // Release reference before getting a new one. That guarantees we can
 204       // actually have CacheEntries live cursors.
 205       setEntry(nullptr);
 206       if (PhysReg)
 207         setEntry(Cache.get(PhysReg));
 208     }
 209
 210     /// moveTo - Move cursor to basic block MBBNum.
 211     void moveToBlock(unsigned MBBNum) {
 212       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
 213     }
 214
 215     /// hasInterference - Return true if the current block has any interference.
 216     bool hasInterference() {
 217       return Current->First.isValid();
 218     }
 219
 220     /// first - Return the starting index of the first interfering range in the
 221     /// current block.
 222     SlotIndex first() {
 223       return Current->First;
 224     }
 225
 226     /// last - Return the ending index of the last interfering range in the
 227     /// current block.
 228     SlotIndex last() {
 229       return Current->Last;
 230     }
 231   };
 232
 233   friend class Cursor;
 234 };
 235
 236 } // namespace llvm
 237
 238 #endif