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 in LiveIntervalUnions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CODEGEN_INTERFERENCECACHE
  15 #define LLVM_CODEGEN_INTERFERENCECACHE
  16
  17 #include "LiveIntervalUnion.h"
  18
  19 namespace llvm {
  20
  21 class InterferenceCache {
  22   const TargetRegisterInfo *TRI;
  23   LiveIntervalUnion *LIUArray;
  24   SlotIndexes *Indexes;
  25   MachineFunction *MF;
  26
  27   /// BlockInterference - information about the interference in a single basic
  28   /// block.
  29   struct BlockInterference {
  30     BlockInterference() : Tag(0) {}
  31     unsigned Tag;
  32     SlotIndex First;
  33     SlotIndex Last;
  34   };
  35
  36   /// Entry - A cache entry containing interference information for all aliases
  37   /// of PhysReg in all basic blocks.
  38   class Entry {
  39     /// PhysReg - The register currently represented.
  40     unsigned PhysReg;
  41
  42     /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
  43     /// change.
  44     unsigned Tag;
  45
  46     /// Indexes - Mapping block numbers to SlotIndex ranges.
  47     SlotIndexes *Indexes;
  48
  49     /// PrevPos - The previous position the iterators were moved to.
  50     SlotIndex PrevPos;
  51
  52     /// AliasTags - A LiveIntervalUnion pointer and tag for each alias of
  53     /// PhysReg.
  54     SmallVector<std::pair<LiveIntervalUnion*, unsigned>, 8> Aliases;
  55
  56     typedef LiveIntervalUnion::SegmentIter Iter;
  57
  58     /// Iters - an iterator for each alias
  59     SmallVector<Iter, 8> Iters;
  60
  61     /// Blocks - Interference for each block in the function.
  62     SmallVector<BlockInterference, 8> Blocks;
  63
  64     /// update - Recompute Blocks[MBBNum]
  65     void update(unsigned MBBNum);
  66
  67   public:
  68     Entry() : PhysReg(0), Tag(0), Indexes(0) {}
  69
  70     void clear(SlotIndexes *indexes) {
  71       PhysReg = 0;
  72       Indexes = indexes;
  73     }
  74
  75     unsigned getPhysReg() const { return PhysReg; }
  76
  77     void revalidate();
  78
  79     /// valid - Return true if this is a valid entry for physReg.
  80     bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
  81
  82     /// reset - Initialize entry to represent physReg's aliases.
  83     void reset(unsigned physReg,
  84                LiveIntervalUnion *LIUArray,
  85                const TargetRegisterInfo *TRI,
  86                const MachineFunction *MF);
  87
  88     /// get - Return an up to date BlockInterference.
  89     BlockInterference *get(unsigned MBBNum) {
  90       if (Blocks[MBBNum].Tag != Tag)
  91         update(MBBNum);
  92       return &Blocks[MBBNum];
  93     }
  94   };
  95
  96   // We don't keep a cache entry for every physical register, that would use too
  97   // much memory. Instead, a fixed number of cache entries are used in a round-
  98   // robin manner.
  99   enum { CacheEntries = 32 };
 100
 101   // Point to an entry for each physreg. The entry pointed to may not be up to
 102   // date, and it may have been reused for a different physreg.
 103   SmallVector<unsigned char, 2> PhysRegEntries;
 104
 105   // Next round-robin entry to be picked.
 106   unsigned RoundRobin;
 107
 108   // The actual cache entries.
 109   Entry Entries[CacheEntries];
 110
 111   // get - Get a valid entry for PhysReg.
 112   Entry *get(unsigned PhysReg);
 113
 114 public:
 115   InterferenceCache() : TRI(0), LIUArray(0), Indexes(0), MF(0), RoundRobin(0) {}
 116
 117   /// init - Prepare cache for a new function.
 118   void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*,
 119             const TargetRegisterInfo *);
 120
 121   /// Cursor - The primary query interface for the block interference cache.
 122   class Cursor {
 123     Entry *CacheEntry;
 124     BlockInterference *Current;
 125   public:
 126     /// Cursor - Create a cursor for the interference allocated to PhysReg and
 127     /// all its aliases.
 128     Cursor(InterferenceCache &Cache, unsigned PhysReg)
 129       : CacheEntry(Cache.get(PhysReg)), Current(0) {}
 130
 131     /// moveTo - Move cursor to basic block MBBNum.
 132     void moveToBlock(unsigned MBBNum) {
 133       Current = CacheEntry->get(MBBNum);
 134     }
 135
 136     /// hasInterference - Return true if the current block has any interference.
 137     bool hasInterference() {
 138       return Current->First.isValid();
 139     }
 140
 141     /// first - Return the starting index of the first interfering range in the
 142     /// current block.
 143     SlotIndex first() {
 144       return Current->First;
 145     }
 146
 147     /// last - Return the ending index of the last interfering range in the
 148     /// current block.
 149     SlotIndex last() {
 150       return Current->Last;
 151     }
 152   };
 153
 154   friend class Cursor;
 155 };
 156
 157 } // namespace llvm
 158
 159 #endif