LLVM 19.0.0git
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
22#include <cassert>
23#include <cstddef>
24#include <cstdlib>
25
26namespace llvm {
27
28class LiveIntervals;
29class MachineFunction;
30class TargetRegisterInfo;
31
33 /// BlockInterference - information about the interference in a single basic
34 /// block.
35 struct BlockInterference {
36 unsigned Tag = 0;
37 SlotIndex First;
39
40 BlockInterference() = default;
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 MCRegister 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 = nullptr;
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 = MCRegister::NoRegister;
106 MF = mf;
107 Indexes = indexes;
108 LIS = lis;
109 }
110
111 MCRegister 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(MCRegister physReg, LiveIntervalUnion *LIUArray,
124 const TargetRegisterInfo *TRI, const MachineFunction *MF);
125
126 /// get - Return an up to date BlockInterference.
127 BlockInterference *get(unsigned MBBNum) {
128 if (Blocks[MBBNum].Tag != Tag)
129 update(MBBNum);
130 return &Blocks[MBBNum];
131 }
132 };
133
134 // We don't keep a cache entry for every physical register, that would use too
135 // much memory. Instead, a fixed number of cache entries are used in a round-
136 // robin manner.
137 enum { CacheEntries = 32 };
138
139 const TargetRegisterInfo *TRI = nullptr;
140 LiveIntervalUnion *LIUArray = nullptr;
141 MachineFunction *MF = nullptr;
142
143 // Point to an entry for each physreg. The entry pointed to may not be up to
144 // date, and it may have been reused for a different physreg.
145 unsigned char* PhysRegEntries = nullptr;
146 size_t PhysRegEntriesCount = 0;
147
148 // Next round-robin entry to be picked.
149 unsigned RoundRobin = 0;
150
151 // The actual cache entries.
152 Entry Entries[CacheEntries];
153
154 // get - Get a valid entry for PhysReg.
155 Entry *get(MCRegister PhysReg);
156
157public:
158 InterferenceCache() = default;
160 InterferenceCache(const InterferenceCache &other) = delete;
162 free(PhysRegEntries);
163 }
164
165 void reinitPhysRegEntries();
166
167 /// init - Prepare cache for a new function.
168 void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
169 SlotIndexes *indexes, LiveIntervals *lis,
170 const TargetRegisterInfo *tri);
171
172 /// getMaxCursors - Return the maximum number of concurrent cursors that can
173 /// be supported.
174 unsigned getMaxCursors() const { return CacheEntries; }
175
176 /// Cursor - The primary query interface for the block interference cache.
177 class Cursor {
178 Entry *CacheEntry = nullptr;
179 const BlockInterference *Current = nullptr;
180 static const BlockInterference NoInterference;
181
182 void setEntry(Entry *E) {
183 Current = nullptr;
184 // Update reference counts. Nothing happens when RefCount reaches 0, so
185 // we don't have to check for E == CacheEntry etc.
186 if (CacheEntry)
187 CacheEntry->addRef(-1);
188 CacheEntry = E;
189 if (CacheEntry)
190 CacheEntry->addRef(+1);
191 }
192
193 public:
194 /// Cursor - Create a dangling cursor.
195 Cursor() = default;
196
197 Cursor(const Cursor &O) {
198 setEntry(O.CacheEntry);
199 }
200
202 setEntry(O.CacheEntry);
203 return *this;
204 }
205
206 ~Cursor() { setEntry(nullptr); }
207
208 /// setPhysReg - Point this cursor to PhysReg's interference.
210 // Release reference before getting a new one. That guarantees we can
211 // actually have CacheEntries live cursors.
212 setEntry(nullptr);
213 if (PhysReg.isValid())
214 setEntry(Cache.get(PhysReg));
215 }
216
217 /// moveTo - Move cursor to basic block MBBNum.
218 void moveToBlock(unsigned MBBNum) {
219 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
220 }
221
222 /// hasInterference - Return true if the current block has any interference.
224 return Current->First.isValid();
225 }
226
227 /// first - Return the starting index of the first interfering range in the
228 /// current block.
230 return Current->First;
231 }
232
233 /// last - Return the ending index of the last interfering range in the
234 /// current block.
236 return Current->Last;
237 }
238 };
239};
240
241} // end namespace llvm
242
243#endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static cl::opt< unsigned > CacheEntries("cdsort-cache-entries", cl::ReallyHidden, cl::desc("The size of the cache"))
#define LLVM_LIBRARY_VISIBILITY
Definition: Compiler.h:131
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:145
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Cursor - The primary query interface for the block interference cache.
SlotIndex first()
first - Return the starting index of the first interfering range in the current block.
SlotIndex last()
last - Return the ending index of the last interfering range in the current block.
Cursor & operator=(const Cursor &O)
bool hasInterference()
hasInterference - Return true if the current block has any interference.
void moveToBlock(unsigned MBBNum)
moveTo - Move cursor to basic block MBBNum.
Cursor()=default
Cursor - Create a dangling cursor.
void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg)
setPhysReg - Point this cursor to PhysReg's interference.
InterferenceCache & operator=(const InterferenceCache &other)=delete
InterferenceCache(const InterferenceCache &other)=delete
unsigned getMaxCursors() const
getMaxCursors - Return the maximum number of concurrent cursors that can be supported.
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
LiveSegments::iterator SegmentIter
unsigned getTag() const
getTag - Return an opaque tag representing the current state of the union.
const Map & getMap() const
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
constexpr bool isValid() const
Definition: MCRegister.h:81
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:68
SlotIndexes pass.
Definition: SlotIndexes.h:300
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)