Home | History | Annotate | Download | only in CodeGen 
      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 LiveIntervals;
     22 
     23 class InterferenceCache {
     24   const TargetRegisterInfo *TRI;
     25   LiveIntervalUnion *LIUArray;
     26   MachineFunction *MF;
     27 
     28   /// BlockInterference - information about the interference in a single basic
     29   /// block.
     30   struct BlockInterference {
     31     BlockInterference() : Tag(0) {}
     32     unsigned Tag;
     33     SlotIndex First;
     34     SlotIndex Last;
     35   };
     36 
     37   /// Entry - A cache entry containing interference information for all aliases
     38   /// of PhysReg in all basic blocks.
     39   class Entry {
     40     /// PhysReg - The register currently represented.
     41     unsigned PhysReg;
     42 
     43     /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
     44     /// change.
     45     unsigned Tag;
     46 
     47     /// RefCount - The total number of Cursor instances referring to this Entry.
     48     unsigned RefCount;
     49 
     50     /// MF - The current function.
     51     MachineFunction *MF;
     52 
     53     /// Indexes - Mapping block numbers to SlotIndex ranges.
     54     SlotIndexes *Indexes;
     55 
     56     /// LIS - Used for accessing register mask interference maps.
     57     LiveIntervals *LIS;
     58 
     59     /// PrevPos - The previous position the iterators were moved to.
     60     SlotIndex PrevPos;
     61 
     62     /// AliasTags - A LiveIntervalUnion pointer and tag for each alias of
     63     /// PhysReg.
     64     SmallVector<std::pair<LiveIntervalUnion*, unsigned>, 8> Aliases;
     65 
     66     typedef LiveIntervalUnion::SegmentIter Iter;
     67 
     68     /// Iters - an iterator for each alias
     69     SmallVector<Iter, 8> Iters;
     70 
     71     /// Blocks - Interference for each block in the function.
     72     SmallVector<BlockInterference, 8> Blocks;
     73 
     74     /// update - Recompute Blocks[MBBNum]
     75     void update(unsigned MBBNum);
     76 
     77   public:
     78     Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(0), LIS(0) {}
     79 
     80     void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
     81       assert(!hasRefs() && "Cannot clear cache entry with references");
     82       PhysReg = 0;
     83       MF = mf;
     84       Indexes = indexes;
     85       LIS = lis;
     86     }
     87 
     88     unsigned getPhysReg() const { return PhysReg; }
     89 
     90     void addRef(int Delta) { RefCount += Delta; }
     91 
     92     bool hasRefs() const { return RefCount > 0; }
     93 
     94     void revalidate();
     95 
     96     /// valid - Return true if this is a valid entry for physReg.
     97     bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
     98 
     99     /// reset - Initialize entry to represent physReg's aliases.
    100     void reset(unsigned physReg,
    101                LiveIntervalUnion *LIUArray,
    102                const TargetRegisterInfo *TRI,
    103                const MachineFunction *MF);
    104 
    105     /// get - Return an up to date BlockInterference.
    106     BlockInterference *get(unsigned MBBNum) {
    107       if (Blocks[MBBNum].Tag != Tag)
    108         update(MBBNum);
    109       return &Blocks[MBBNum];
    110     }
    111   };
    112 
    113   // We don't keep a cache entry for every physical register, that would use too
    114   // much memory. Instead, a fixed number of cache entries are used in a round-
    115   // robin manner.
    116   enum { CacheEntries = 32 };
    117 
    118   // Point to an entry for each physreg. The entry pointed to may not be up to
    119   // date, and it may have been reused for a different physreg.
    120   SmallVector<unsigned char, 2> PhysRegEntries;
    121 
    122   // Next round-robin entry to be picked.
    123   unsigned RoundRobin;
    124 
    125   // The actual cache entries.
    126   Entry Entries[CacheEntries];
    127 
    128   // get - Get a valid entry for PhysReg.
    129   Entry *get(unsigned PhysReg);
    130 
    131 public:
    132   InterferenceCache() : TRI(0), LIUArray(0), MF(0), RoundRobin(0) {}
    133 
    134   /// init - Prepare cache for a new function.
    135   void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*,
    136             const TargetRegisterInfo *);
    137 
    138   /// getMaxCursors - Return the maximum number of concurrent cursors that can
    139   /// be supported.
    140   unsigned getMaxCursors() const { return CacheEntries; }
    141 
    142   /// Cursor - The primary query interface for the block interference cache.
    143   class Cursor {
    144     Entry *CacheEntry;
    145     BlockInterference *Current;
    146     static BlockInterference NoInterference;
    147 
    148     void setEntry(Entry *E) {
    149       Current = 0;
    150       // Update reference counts. Nothing happens when RefCount reaches 0, so
    151       // we don't have to check for E == CacheEntry etc.
    152       if (CacheEntry)
    153         CacheEntry->addRef(-1);
    154       CacheEntry = E;
    155       if (CacheEntry)
    156         CacheEntry->addRef(+1);
    157     }
    158 
    159   public:
    160     /// Cursor - Create a dangling cursor.
    161     Cursor() : CacheEntry(0), Current(0) {}
    162     ~Cursor() { setEntry(0); }
    163 
    164     Cursor(const Cursor &O) : CacheEntry(0), Current(0) {
    165       setEntry(O.CacheEntry);
    166     }
    167 
    168     Cursor &operator=(const Cursor &O) {
    169       setEntry(O.CacheEntry);
    170       return *this;
    171     }
    172 
    173     /// setPhysReg - Point this cursor to PhysReg's interference.
    174     void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
    175       // Release reference before getting a new one. That guarantees we can
    176       // actually have CacheEntries live cursors.
    177       setEntry(0);
    178       if (PhysReg)
    179         setEntry(Cache.get(PhysReg));
    180     }
    181 
    182     /// moveTo - Move cursor to basic block MBBNum.
    183     void moveToBlock(unsigned MBBNum) {
    184       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
    185     }
    186 
    187     /// hasInterference - Return true if the current block has any interference.
    188     bool hasInterference() {
    189       return Current->First.isValid();
    190     }
    191 
    192     /// first - Return the starting index of the first interfering range in the
    193     /// current block.
    194     SlotIndex first() {
    195       return Current->First;
    196     }
    197 
    198     /// last - Return the ending index of the last interfering range in the
    199     /// current block.
    200     SlotIndex last() {
    201       return Current->Last;
    202     }
    203   };
    204 
    205   friend class Cursor;
    206 };
    207 
    208 } // namespace llvm
    209 
    210 #endif
    211