InterferenceCache.h revision 221345 
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
19namespace llvm {
20
21class 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
118public:
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
164