InterferenceCache.h revision 1ead68d769f27f6d68d4aaeffe4199fa2cacbc95 
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
20namespace llvm {
21
22class LiveIntervals;
23
24class 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      LiveInterval *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
149public:
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
229