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