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