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"
18#include "llvm/CodeGen/LiveInterval.h"
19#include "llvm/CodeGen/LiveIntervalUnion.h"
20#include "llvm/CodeGen/SlotIndexes.h"
21#include "llvm/Support/Compiler.h"
22#include <cassert>
23#include <cstddef>
24#include <cstdlib>
25
26namespace llvm {
27
28class LiveIntervals;
29class MachineFunction;
30class TargetRegisterInfo;
31
32class LLVM_LIBRARY_VISIBILITY InterferenceCache {
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() = 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.
74 LiveIntervalUnion::SegmentIter VirtI;
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.
83 LiveInterval::iterator FixedI;
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.
92 SmallVector<RegUnitInfo, 4> RegUnits;
93
94 /// Blocks - Interference for each block in the function.
95 SmallVector<BlockInterference, 8> Blocks;
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;
159 InterferenceCache &operator=(const InterferenceCache &other) = delete;
160 InterferenceCache(const InterferenceCache &other) = delete;
161 ~InterferenceCache() {
162 free(ptr: 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(Delta: -1);
188 CacheEntry = E;
189 if (CacheEntry)
190 CacheEntry->addRef(Delta: +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
201 Cursor &operator=(const Cursor &O) {
202 setEntry(O.CacheEntry);
203 return *this;
204 }
205
206 ~Cursor() { setEntry(nullptr); }
207
208 /// setPhysReg - Point this cursor to PhysReg's interference.
209 void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg) {
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.
223 bool hasInterference() {
224 return Current->First.isValid();
225 }
226
227 /// first - Return the starting index of the first interfering range in the
228 /// current block.
229 SlotIndex first() {
230 return Current->First;
231 }
232
233 /// last - Return the ending index of the last interfering range in the
234 /// current block.
235 SlotIndex last() {
236 return Current->Last;
237 }
238 };
239};
240
241} // end namespace llvm
242
243#endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
244