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     unsigned 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 = 0;
106       MF = mf;
107       Indexes = indexes;
108       LIS = lis;
109     }
110 
111     unsigned 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(unsigned physReg,
124                LiveIntervalUnion *LIUArray,
125                const TargetRegisterInfo *TRI,
126                const MachineFunction *MF);
127 
128     /// get - Return an up to date BlockInterference.
129     BlockInterference *get(unsigned MBBNum) {
130       if (Blocks[MBBNum].Tag != Tag)
131         update(MBBNum);
132       return &Blocks[MBBNum];
133     }
134   };
135 
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-
138   // robin manner.
139   enum { CacheEntries = 32 };
140 
141   const TargetRegisterInfo *TRI = nullptr;
142   LiveIntervalUnion *LIUArray = nullptr;
143   MachineFunction *MF = nullptr;
144 
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;
149 
150   // Next round-robin entry to be picked.
151   unsigned RoundRobin = 0;
152 
153   // The actual cache entries.
154   Entry Entries[CacheEntries];
155 
156   // get - Get a valid entry for PhysReg.
157   Entry *get(unsigned PhysReg);
158 
159 public:
160   friend class Cursor;
161 
162   InterferenceCache() = default;
163 
164   ~InterferenceCache() {
165     free(PhysRegEntries);
166   }
167 
168   void reinitPhysRegEntries();
169 
170   /// init - Prepare cache for a new function.
171   void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
172             SlotIndexes *indexes, LiveIntervals *lis,
173             const TargetRegisterInfo *tri);
174 
175   /// getMaxCursors - Return the maximum number of concurrent cursors that can
176   /// be supported.
177   unsigned getMaxCursors() const { return CacheEntries; }
178 
179   /// Cursor - The primary query interface for the block interference cache.
180   class Cursor {
181     Entry *CacheEntry = nullptr;
182     const BlockInterference *Current = nullptr;
183     static const BlockInterference NoInterference;
184 
185     void setEntry(Entry *E) {
186       Current = nullptr;
187       // Update reference counts. Nothing happens when RefCount reaches 0, so
188       // we don't have to check for E == CacheEntry etc.
189       if (CacheEntry)
190         CacheEntry->addRef(-1);
191       CacheEntry = E;
192       if (CacheEntry)
193         CacheEntry->addRef(+1);
194     }
195 
196   public:
197     /// Cursor - Create a dangling cursor.
198     Cursor() = default;
199 
200     Cursor(const Cursor &O) {
201       setEntry(O.CacheEntry);
202     }
203 
204     Cursor &operator=(const Cursor &O) {
205       setEntry(O.CacheEntry);
206       return *this;
207     }
208 
209     ~Cursor() { setEntry(nullptr); }
210 
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.
215       setEntry(nullptr);
216       if (PhysReg)
217         setEntry(Cache.get(PhysReg));
218     }
219 
220     /// moveTo - Move cursor to basic block MBBNum.
221     void moveToBlock(unsigned MBBNum) {
222       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
223     }
224 
225     /// hasInterference - Return true if the current block has any interference.
226     bool hasInterference() {
227       return Current->First.isValid();
228     }
229 
230     /// first - Return the starting index of the first interfering range in the
231     /// current block.
232     SlotIndex first() {
233       return Current->First;
234     }
235 
236     /// last - Return the ending index of the last interfering range in the
237     /// current block.
238     SlotIndex last() {
239       return Current->Last;
240     }
241   };
242 };
243 
244 } // end namespace llvm
245 
246 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
247