1 //===- InterferenceCache.h - Caching per-block interference ----*- C++ -*--===//
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
7 //===----------------------------------------------------------------------===//
9 // InterferenceCache remembers per-block interference from LiveIntervalUnions,
10 // fixed RegUnit interference, and register masks.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
15 #define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/CodeGen/LiveInterval.h"
19 #include "llvm/CodeGen/LiveIntervalUnion.h"
20 #include "llvm/CodeGen/SlotIndexes.h"
21 #include "llvm/Support/Compiler.h"
29 class MachineFunction;
30 class TargetRegisterInfo;
32 class LLVM_LIBRARY_VISIBILITY InterferenceCache {
33 /// BlockInterference - information about the interference in a single basic
35 struct BlockInterference {
40 BlockInterference() {}
43 /// Entry - A cache entry containing interference information for all aliases
44 /// of PhysReg in all basic blocks.
46 /// PhysReg - The register currently represented.
49 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
53 /// RefCount - The total number of Cursor instances referring to this Entry.
54 unsigned RefCount = 0;
56 /// MF - The current function.
59 /// Indexes - Mapping block numbers to SlotIndex ranges.
60 SlotIndexes *Indexes = nullptr;
62 /// LIS - Used for accessing register mask interference maps.
63 LiveIntervals *LIS = nullptr;
65 /// PrevPos - The previous position the iterators were moved to.
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.
72 /// Iterator pointing into the LiveIntervalUnion containing virtual
73 /// register interference.
74 LiveIntervalUnion::SegmentIter VirtI;
76 /// Tag of the LIU last time we looked.
79 /// Fixed interference in RegUnit.
80 LiveRange *Fixed = nullptr;
82 /// Iterator pointing into the fixed RegUnit interference.
83 LiveInterval::iterator FixedI;
85 RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) {
86 VirtI.setMap(LIU.getMap());
90 /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
91 /// more than 4 RegUnits.
92 SmallVector<RegUnitInfo, 4> RegUnits;
94 /// Blocks - Interference for each block in the function.
95 SmallVector<BlockInterference, 8> Blocks;
97 /// update - Recompute Blocks[MBBNum]
98 void update(unsigned MBBNum);
103 void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
104 assert(!hasRefs() && "Cannot clear cache entry with references");
111 unsigned getPhysReg() const { return PhysReg; }
113 void addRef(int Delta) { RefCount += Delta; }
115 bool hasRefs() const { return RefCount > 0; }
117 void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
119 /// valid - Return true if this is a valid entry for physReg.
120 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
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);
128 /// get - Return an up to date BlockInterference.
129 BlockInterference *get(unsigned MBBNum) {
130 if (Blocks[MBBNum].Tag != Tag)
132 return &Blocks[MBBNum];
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-
139 enum { CacheEntries = 32 };
141 const TargetRegisterInfo *TRI = nullptr;
142 LiveIntervalUnion *LIUArray = nullptr;
143 MachineFunction *MF = nullptr;
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;
150 // Next round-robin entry to be picked.
151 unsigned RoundRobin = 0;
153 // The actual cache entries.
154 Entry Entries[CacheEntries];
156 // get - Get a valid entry for PhysReg.
157 Entry *get(unsigned PhysReg);
162 InterferenceCache() = default;
164 ~InterferenceCache() {
165 free(PhysRegEntries);
168 void reinitPhysRegEntries();
170 /// init - Prepare cache for a new function.
171 void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
172 SlotIndexes *indexes, LiveIntervals *lis,
173 const TargetRegisterInfo *tri);
175 /// getMaxCursors - Return the maximum number of concurrent cursors that can
177 unsigned getMaxCursors() const { return CacheEntries; }
179 /// Cursor - The primary query interface for the block interference cache.
181 Entry *CacheEntry = nullptr;
182 const BlockInterference *Current = nullptr;
183 static const BlockInterference NoInterference;
185 void setEntry(Entry *E) {
187 // Update reference counts. Nothing happens when RefCount reaches 0, so
188 // we don't have to check for E == CacheEntry etc.
190 CacheEntry->addRef(-1);
193 CacheEntry->addRef(+1);
197 /// Cursor - Create a dangling cursor.
200 Cursor(const Cursor &O) {
201 setEntry(O.CacheEntry);
204 Cursor &operator=(const Cursor &O) {
205 setEntry(O.CacheEntry);
209 ~Cursor() { setEntry(nullptr); }
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.
217 setEntry(Cache.get(PhysReg));
220 /// moveTo - Move cursor to basic block MBBNum.
221 void moveToBlock(unsigned MBBNum) {
222 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
225 /// hasInterference - Return true if the current block has any interference.
226 bool hasInterference() {
227 return Current->First.isValid();
230 /// first - Return the starting index of the first interfering range in the
233 return Current->First;
236 /// last - Return the ending index of the last interfering range in the
239 return Current->Last;
244 } // end namespace llvm
246 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H