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_LIB_CODEGEN_INTERFERENCECACHE_H
16#define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
17
18#include "llvm/CodeGen/LiveIntervalUnion.h"
19
20namespace llvm {
21
22class LiveIntervals;
23
24class LLVM_LIBRARY_VISIBILITY 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      LiveRange *Fixed;
76
77      /// Iterator pointing into the fixed RegUnit interference.
78      LiveInterval::iterator FixedI;
79
80      RegUnitInfo(LiveIntervalUnion &LIU)
81          : VirtTag(LIU.getTag()), Fixed(nullptr) {
82        VirtI.setMap(LIU.getMap());
83      }
84    };
85
86    /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
87    /// more than 4 RegUnits.
88    SmallVector<RegUnitInfo, 4> RegUnits;
89
90    /// Blocks - Interference for each block in the function.
91    SmallVector<BlockInterference, 8> Blocks;
92
93    /// update - Recompute Blocks[MBBNum]
94    void update(unsigned MBBNum);
95
96  public:
97    Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(nullptr), LIS(nullptr) {}
98
99    void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
100      assert(!hasRefs() && "Cannot clear cache entry with references");
101      PhysReg = 0;
102      MF = mf;
103      Indexes = indexes;
104      LIS = lis;
105    }
106
107    unsigned getPhysReg() const { return PhysReg; }
108
109    void addRef(int Delta) { RefCount += Delta; }
110
111    bool hasRefs() const { return RefCount > 0; }
112
113    void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
114
115    /// valid - Return true if this is a valid entry for physReg.
116    bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
117
118    /// reset - Initialize entry to represent physReg's aliases.
119    void reset(unsigned physReg,
120               LiveIntervalUnion *LIUArray,
121               const TargetRegisterInfo *TRI,
122               const MachineFunction *MF);
123
124    /// get - Return an up to date BlockInterference.
125    BlockInterference *get(unsigned MBBNum) {
126      if (Blocks[MBBNum].Tag != Tag)
127        update(MBBNum);
128      return &Blocks[MBBNum];
129    }
130  };
131
132  // We don't keep a cache entry for every physical register, that would use too
133  // much memory. Instead, a fixed number of cache entries are used in a round-
134  // robin manner.
135  enum { CacheEntries = 32 };
136
137  // Point to an entry for each physreg. The entry pointed to may not be up to
138  // date, and it may have been reused for a different physreg.
139  unsigned char* PhysRegEntries;
140  size_t PhysRegEntriesCount;
141
142  // Next round-robin entry to be picked.
143  unsigned RoundRobin;
144
145  // The actual cache entries.
146  Entry Entries[CacheEntries];
147
148  // get - Get a valid entry for PhysReg.
149  Entry *get(unsigned PhysReg);
150
151public:
152  InterferenceCache()
153    : TRI(nullptr), LIUArray(nullptr), MF(nullptr), PhysRegEntries(nullptr),
154      PhysRegEntriesCount(0), RoundRobin(0) {}
155
156  ~InterferenceCache() {
157    free(PhysRegEntries);
158  }
159
160  void reinitPhysRegEntries();
161
162  /// init - Prepare cache for a new function.
163  void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*,
164            const TargetRegisterInfo *);
165
166  /// getMaxCursors - Return the maximum number of concurrent cursors that can
167  /// be supported.
168  unsigned getMaxCursors() const { return CacheEntries; }
169
170  /// Cursor - The primary query interface for the block interference cache.
171  class Cursor {
172    Entry *CacheEntry;
173    const BlockInterference *Current;
174    static const BlockInterference NoInterference;
175
176    void setEntry(Entry *E) {
177      Current = nullptr;
178      // Update reference counts. Nothing happens when RefCount reaches 0, so
179      // we don't have to check for E == CacheEntry etc.
180      if (CacheEntry)
181        CacheEntry->addRef(-1);
182      CacheEntry = E;
183      if (CacheEntry)
184        CacheEntry->addRef(+1);
185    }
186
187  public:
188    /// Cursor - Create a dangling cursor.
189    Cursor() : CacheEntry(nullptr), Current(nullptr) {}
190    ~Cursor() { setEntry(nullptr); }
191
192    Cursor(const Cursor &O) : CacheEntry(nullptr), Current(nullptr) {
193      setEntry(O.CacheEntry);
194    }
195
196    Cursor &operator=(const Cursor &O) {
197      setEntry(O.CacheEntry);
198      return *this;
199    }
200
201    /// setPhysReg - Point this cursor to PhysReg's interference.
202    void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
203      // Release reference before getting a new one. That guarantees we can
204      // actually have CacheEntries live cursors.
205      setEntry(nullptr);
206      if (PhysReg)
207        setEntry(Cache.get(PhysReg));
208    }
209
210    /// moveTo - Move cursor to basic block MBBNum.
211    void moveToBlock(unsigned MBBNum) {
212      Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
213    }
214
215    /// hasInterference - Return true if the current block has any interference.
216    bool hasInterference() {
217      return Current->First.isValid();
218    }
219
220    /// first - Return the starting index of the first interfering range in the
221    /// current block.
222    SlotIndex first() {
223      return Current->First;
224    }
225
226    /// last - Return the ending index of the last interfering range in the
227    /// current block.
228    SlotIndex last() {
229      return Current->Last;
230    }
231  };
232
233  friend class Cursor;
234};
235
236} // namespace llvm
237
238#endif
239