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 
26 namespace llvm {
27 
28 class LiveIntervals;
29 class MachineFunction;
30 class TargetRegisterInfo;
31 
32 class 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() {}
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;
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 
157 public:
158   InterferenceCache() = default;
159 
160   ~InterferenceCache() {
161     free(PhysRegEntries);
162   }
163 
164   void reinitPhysRegEntries();
165 
166   /// init - Prepare cache for a new function.
167   void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
168             SlotIndexes *indexes, LiveIntervals *lis,
169             const TargetRegisterInfo *tri);
170 
171   /// getMaxCursors - Return the maximum number of concurrent cursors that can
172   /// be supported.
173   unsigned getMaxCursors() const { return CacheEntries; }
174 
175   /// Cursor - The primary query interface for the block interference cache.
176   class Cursor {
177     Entry *CacheEntry = nullptr;
178     const BlockInterference *Current = nullptr;
179     static const BlockInterference NoInterference;
180 
181     void setEntry(Entry *E) {
182       Current = nullptr;
183       // Update reference counts. Nothing happens when RefCount reaches 0, so
184       // we don't have to check for E == CacheEntry etc.
185       if (CacheEntry)
186         CacheEntry->addRef(-1);
187       CacheEntry = E;
188       if (CacheEntry)
189         CacheEntry->addRef(+1);
190     }
191 
192   public:
193     /// Cursor - Create a dangling cursor.
194     Cursor() = default;
195 
196     Cursor(const Cursor &O) {
197       setEntry(O.CacheEntry);
198     }
199 
200     Cursor &operator=(const Cursor &O) {
201       setEntry(O.CacheEntry);
202       return *this;
203     }
204 
205     ~Cursor() { setEntry(nullptr); }
206 
207     /// setPhysReg - Point this cursor to PhysReg's interference.
208     void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg) {
209       // Release reference before getting a new one. That guarantees we can
210       // actually have CacheEntries live cursors.
211       setEntry(nullptr);
212       if (PhysReg.isValid())
213         setEntry(Cache.get(PhysReg));
214     }
215 
216     /// moveTo - Move cursor to basic block MBBNum.
217     void moveToBlock(unsigned MBBNum) {
218       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
219     }
220 
221     /// hasInterference - Return true if the current block has any interference.
222     bool hasInterference() {
223       return Current->First.isValid();
224     }
225 
226     /// first - Return the starting index of the first interfering range in the
227     /// current block.
228     SlotIndex first() {
229       return Current->First;
230     }
231 
232     /// last - Return the ending index of the last interfering range in the
233     /// current block.
234     SlotIndex last() {
235       return Current->Last;
236     }
237   };
238 };
239 
240 } // end namespace llvm
241 
242 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
243