Line data Source code
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/ADT/SmallVector.h"
19 : #include "llvm/CodeGen/LiveInterval.h"
20 : #include "llvm/CodeGen/LiveIntervalUnion.h"
21 : #include "llvm/CodeGen/SlotIndexes.h"
22 : #include "llvm/Support/Compiler.h"
23 : #include <cassert>
24 : #include <cstddef>
25 : #include <cstdlib>
26 :
27 : namespace llvm {
28 :
29 : class LiveIntervals;
30 : class MachineFunction;
31 : class TargetRegisterInfo;
32 :
33 : class LLVM_LIBRARY_VISIBILITY InterferenceCache {
34 : /// BlockInterference - information about the interference in a single basic
35 : /// block.
36 : struct BlockInterference {
37 : unsigned Tag = 0;
38 : SlotIndex First;
39 : SlotIndex Last;
40 :
41 1607403 : BlockInterference() {}
42 : };
43 :
44 : /// Entry - A cache entry containing interference information for all aliases
45 : /// of PhysReg in all basic blocks.
46 : class Entry {
47 : /// PhysReg - The register currently represented.
48 : unsigned PhysReg = 0;
49 :
50 : /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
51 : /// change.
52 : unsigned Tag = 0;
53 :
54 : /// RefCount - The total number of Cursor instances referring to this Entry.
55 : unsigned RefCount = 0;
56 :
57 : /// MF - The current function.
58 : MachineFunction *MF;
59 :
60 : /// Indexes - Mapping block numbers to SlotIndex ranges.
61 : SlotIndexes *Indexes = nullptr;
62 :
63 : /// LIS - Used for accessing register mask interference maps.
64 : LiveIntervals *LIS = nullptr;
65 :
66 : /// PrevPos - The previous position the iterators were moved to.
67 : SlotIndex PrevPos;
68 :
69 : /// RegUnitInfo - Information tracked about each RegUnit in PhysReg.
70 : /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos)
71 : /// had just been called.
72 118807 : struct RegUnitInfo {
73 : /// Iterator pointing into the LiveIntervalUnion containing virtual
74 : /// register interference.
75 : LiveIntervalUnion::SegmentIter VirtI;
76 :
77 : /// Tag of the LIU last time we looked.
78 : unsigned VirtTag;
79 :
80 : /// Fixed interference in RegUnit.
81 : LiveRange *Fixed = nullptr;
82 :
83 : /// Iterator pointing into the fixed RegUnit interference.
84 : LiveInterval::iterator FixedI;
85 :
86 237110 : RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) {
87 : VirtI.setMap(LIU.getMap());
88 : }
89 : };
90 :
91 : /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
92 : /// more than 4 RegUnits.
93 : SmallVector<RegUnitInfo, 4> RegUnits;
94 :
95 : /// Blocks - Interference for each block in the function.
96 : SmallVector<BlockInterference, 8> Blocks;
97 :
98 : /// update - Recompute Blocks[MBBNum]
99 : void update(unsigned MBBNum);
100 :
101 : public:
102 628444 : Entry() = default;
103 :
104 : void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
105 : assert(!hasRefs() && "Cannot clear cache entry with references");
106 6200544 : PhysReg = 0;
107 6200544 : MF = mf;
108 6200544 : Indexes = indexes;
109 6200544 : LIS = lis;
110 : }
111 :
112 0 : unsigned getPhysReg() const { return PhysReg; }
113 :
114 2076983 : void addRef(int Delta) { RefCount += Delta; }
115 :
116 0 : bool hasRefs() const { return RefCount > 0; }
117 :
118 : void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
119 :
120 : /// valid - Return true if this is a valid entry for physReg.
121 : bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
122 :
123 : /// reset - Initialize entry to represent physReg's aliases.
124 : void reset(unsigned physReg,
125 : LiveIntervalUnion *LIUArray,
126 : const TargetRegisterInfo *TRI,
127 : const MachineFunction *MF);
128 :
129 : /// get - Return an up to date BlockInterference.
130 : BlockInterference *get(unsigned MBBNum) {
131 0 : if (Blocks[MBBNum].Tag != Tag)
132 0 : update(MBBNum);
133 : return &Blocks[MBBNum];
134 : }
135 : };
136 :
137 : // We don't keep a cache entry for every physical register, that would use too
138 : // much memory. Instead, a fixed number of cache entries are used in a round-
139 : // robin manner.
140 : enum { CacheEntries = 32 };
141 :
142 : const TargetRegisterInfo *TRI = nullptr;
143 : LiveIntervalUnion *LIUArray = nullptr;
144 : MachineFunction *MF = nullptr;
145 :
146 : // Point to an entry for each physreg. The entry pointed to may not be up to
147 : // date, and it may have been reused for a different physreg.
148 : unsigned char* PhysRegEntries = nullptr;
149 : size_t PhysRegEntriesCount = 0;
150 :
151 : // Next round-robin entry to be picked.
152 : unsigned RoundRobin = 0;
153 :
154 : // The actual cache entries.
155 : Entry Entries[CacheEntries];
156 :
157 : // get - Get a valid entry for PhysReg.
158 : Entry *get(unsigned PhysReg);
159 :
160 : public:
161 : friend class Cursor;
162 :
163 648086 : InterferenceCache() = default;
164 :
165 643988 : ~InterferenceCache() {
166 19515 : free(PhysRegEntries);
167 19515 : }
168 :
169 : void reinitPhysRegEntries();
170 :
171 : /// init - Prepare cache for a new function.
172 : void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
173 : SlotIndexes *indexes, LiveIntervals *lis,
174 : const TargetRegisterInfo *tri);
175 :
176 : /// getMaxCursors - Return the maximum number of concurrent cursors that can
177 : /// be supported.
178 0 : unsigned getMaxCursors() const { return CacheEntries; }
179 :
180 : /// Cursor - The primary query interface for the block interference cache.
181 : class Cursor {
182 : Entry *CacheEntry = nullptr;
183 : const BlockInterference *Current = nullptr;
184 : static const BlockInterference NoInterference;
185 :
186 0 : void setEntry(Entry *E) {
187 1407225 : Current = nullptr;
188 : // Update reference counts. Nothing happens when RefCount reaches 0, so
189 : // we don't have to check for E == CacheEntry etc.
190 1068462 : if (CacheEntry)
191 : CacheEntry->addRef(-1);
192 1407225 : CacheEntry = E;
193 320084 : if (CacheEntry)
194 : CacheEntry->addRef(+1);
195 0 : }
196 :
197 : public:
198 : /// Cursor - Create a dangling cursor.
199 6200562 : Cursor() = default;
200 :
201 748378 : Cursor(const Cursor &O) {
202 748378 : setEntry(O.CacheEntry);
203 : }
204 :
205 0 : Cursor &operator=(const Cursor &O) {
206 0 : setEntry(O.CacheEntry);
207 0 : return *this;
208 : }
209 :
210 : ~Cursor() { setEntry(nullptr); }
211 :
212 : /// setPhysReg - Point this cursor to PhysReg's interference.
213 338763 : void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
214 : // Release reference before getting a new one. That guarantees we can
215 : // actually have CacheEntries live cursors.
216 : setEntry(nullptr);
217 338763 : if (PhysReg)
218 320084 : setEntry(Cache.get(PhysReg));
219 338763 : }
220 :
221 : /// moveTo - Move cursor to basic block MBBNum.
222 0 : void moveToBlock(unsigned MBBNum) {
223 0 : Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
224 0 : }
225 :
226 : /// hasInterference - Return true if the current block has any interference.
227 0 : bool hasInterference() {
228 0 : return Current->First.isValid();
229 : }
230 :
231 : /// first - Return the starting index of the first interfering range in the
232 : /// current block.
233 0 : SlotIndex first() {
234 773352 : return Current->First;
235 : }
236 :
237 : /// last - Return the ending index of the last interfering range in the
238 : /// current block.
239 0 : SlotIndex last() {
240 798043 : return Current->Last;
241 : }
242 : };
243 : };
244 :
245 : } // end namespace llvm
246 :
247 : #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
|
