LLVM  9.0.0svn
InterferenceCache.h
Go to the documentation of this file.
1 //===- InterferenceCache.h - Caching per-block interference ----*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // InterferenceCache remembers per-block interference from LiveIntervalUnions,
10 // fixed RegUnit interference, and register masks.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
15 #define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
16 
17 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Support/Compiler.h"
22 #include <cassert>
23 #include <cstddef>
24 #include <cstdlib>
25 
26 namespace llvm {
27 
28 class LiveIntervals;
29 class MachineFunction;
30 class TargetRegisterInfo;
31 
33  /// BlockInterference - information about the interference in a single basic
34  /// block.
35  struct BlockInterference {
36  unsigned Tag = 0;
37  SlotIndex First;
38  SlotIndex Last;
39 
40  BlockInterference() {}
41  };
42 
43  /// Entry - A cache entry containing interference information for all aliases
44  /// of PhysReg in all basic blocks.
45  class Entry {
46  /// PhysReg - The register currently represented.
47  unsigned PhysReg = 0;
48 
49  /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
50  /// change.
51  unsigned Tag = 0;
52 
53  /// RefCount - The total number of Cursor instances referring to this Entry.
54  unsigned RefCount = 0;
55 
56  /// MF - The current function.
57  MachineFunction *MF;
58 
59  /// Indexes - Mapping block numbers to SlotIndex ranges.
60  SlotIndexes *Indexes = nullptr;
61 
62  /// LIS - Used for accessing register mask interference maps.
63  LiveIntervals *LIS = nullptr;
64 
65  /// PrevPos - The previous position the iterators were moved to.
66  SlotIndex PrevPos;
67 
68  /// RegUnitInfo - Information tracked about each RegUnit in PhysReg.
69  /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos)
70  /// had just been called.
71  struct RegUnitInfo {
72  /// Iterator pointing into the LiveIntervalUnion containing virtual
73  /// register interference.
75 
76  /// Tag of the LIU last time we looked.
77  unsigned VirtTag;
78 
79  /// Fixed interference in RegUnit.
80  LiveRange *Fixed = nullptr;
81 
82  /// Iterator pointing into the fixed RegUnit interference.
84 
85  RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) {
86  VirtI.setMap(LIU.getMap());
87  }
88  };
89 
90  /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
91  /// more than 4 RegUnits.
93 
94  /// Blocks - Interference for each block in the function.
96 
97  /// update - Recompute Blocks[MBBNum]
98  void update(unsigned MBBNum);
99 
100  public:
101  Entry() = default;
102 
103  void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
104  assert(!hasRefs() && "Cannot clear cache entry with references");
105  PhysReg = 0;
106  MF = mf;
107  Indexes = indexes;
108  LIS = lis;
109  }
110 
111  unsigned getPhysReg() const { return PhysReg; }
112 
113  void addRef(int Delta) { RefCount += Delta; }
114 
115  bool hasRefs() const { return RefCount > 0; }
116 
117  void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
118 
119  /// valid - Return true if this is a valid entry for physReg.
120  bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
121 
122  /// reset - Initialize entry to represent physReg's aliases.
123  void reset(unsigned physReg,
124  LiveIntervalUnion *LIUArray,
125  const TargetRegisterInfo *TRI,
126  const MachineFunction *MF);
127 
128  /// get - Return an up to date BlockInterference.
129  BlockInterference *get(unsigned MBBNum) {
130  if (Blocks[MBBNum].Tag != Tag)
131  update(MBBNum);
132  return &Blocks[MBBNum];
133  }
134  };
135 
136  // We don't keep a cache entry for every physical register, that would use too
137  // much memory. Instead, a fixed number of cache entries are used in a round-
138  // robin manner.
139  enum { CacheEntries = 32 };
140 
141  const TargetRegisterInfo *TRI = nullptr;
142  LiveIntervalUnion *LIUArray = nullptr;
143  MachineFunction *MF = nullptr;
144 
145  // Point to an entry for each physreg. The entry pointed to may not be up to
146  // date, and it may have been reused for a different physreg.
147  unsigned char* PhysRegEntries = nullptr;
148  size_t PhysRegEntriesCount = 0;
149 
150  // Next round-robin entry to be picked.
151  unsigned RoundRobin = 0;
152 
153  // The actual cache entries.
154  Entry Entries[CacheEntries];
155 
156  // get - Get a valid entry for PhysReg.
157  Entry *get(unsigned PhysReg);
158 
159 public:
160  friend class Cursor;
161 
162  InterferenceCache() = default;
163 
165  free(PhysRegEntries);
166  }
167 
168  void reinitPhysRegEntries();
169 
170  /// init - Prepare cache for a new function.
171  void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
172  SlotIndexes *indexes, LiveIntervals *lis,
173  const TargetRegisterInfo *tri);
174 
175  /// getMaxCursors - Return the maximum number of concurrent cursors that can
176  /// be supported.
177  unsigned getMaxCursors() const { return CacheEntries; }
178 
179  /// Cursor - The primary query interface for the block interference cache.
180  class Cursor {
181  Entry *CacheEntry = nullptr;
182  const BlockInterference *Current = nullptr;
183  static const BlockInterference NoInterference;
184 
185  void setEntry(Entry *E) {
186  Current = nullptr;
187  // Update reference counts. Nothing happens when RefCount reaches 0, so
188  // we don't have to check for E == CacheEntry etc.
189  if (CacheEntry)
190  CacheEntry->addRef(-1);
191  CacheEntry = E;
192  if (CacheEntry)
193  CacheEntry->addRef(+1);
194  }
195 
196  public:
197  /// Cursor - Create a dangling cursor.
198  Cursor() = default;
199 
200  Cursor(const Cursor &O) {
201  setEntry(O.CacheEntry);
202  }
203 
205  setEntry(O.CacheEntry);
206  return *this;
207  }
208 
209  ~Cursor() { setEntry(nullptr); }
210 
211  /// setPhysReg - Point this cursor to PhysReg's interference.
212  void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
213  // Release reference before getting a new one. That guarantees we can
214  // actually have CacheEntries live cursors.
215  setEntry(nullptr);
216  if (PhysReg)
217  setEntry(Cache.get(PhysReg));
218  }
219 
220  /// moveTo - Move cursor to basic block MBBNum.
221  void moveToBlock(unsigned MBBNum) {
222  Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
223  }
224 
225  /// hasInterference - Return true if the current block has any interference.
227  return Current->First.isValid();
228  }
229 
230  /// first - Return the starting index of the first interfering range in the
231  /// current block.
233  return Current->First;
234  }
235 
236  /// last - Return the ending index of the last interfering range in the
237  /// current block.
239  return Current->Last;
240  }
241  };
242 };
243 
244 } // end namespace llvm
245 
246 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
void setPhysReg(InterferenceCache &Cache, unsigned PhysReg)
setPhysReg - Point this cursor to PhysReg&#39;s interference.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Segments::iterator iterator
Definition: LiveInterval.h:207
unsigned const TargetRegisterInfo * TRI
void setMap(const IntervalMap &m)
setMap - Change the map iterated over.
Definition: IntervalMap.h:1355
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:156
const Map & getMap() const
SlotIndexes pass.
Definition: SlotIndexes.h:328
SlotIndex last()
last - Return the ending index of the last interfering range in the current block.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Cursor - The primary query interface for the block interference cache.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
unsigned getTag() const
getTag - Return an opaque tag representing the current state of the union.
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:107
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
bool hasInterference()
hasInterference - Return true if the current block has any interference.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
void moveToBlock(unsigned MBBNum)
moveTo - Move cursor to basic block MBBNum.
Cursor & operator=(const Cursor &O)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getMaxCursors() const
getMaxCursors - Return the maximum number of concurrent cursors that can be supported.
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
SlotIndex first()
first - Return the starting index of the first interfering range in the current block.