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() = 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 
RegUnitInfoRegUnitInfo85       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 
clear(MachineFunction * mf,SlotIndexes * indexes,LiveIntervals * lis)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 
getPhysReg()111     MCRegister getPhysReg() const { return PhysReg; }
112 
addRef(int Delta)113     void addRef(int Delta) { RefCount += Delta; }
114 
hasRefs()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.
get(unsigned MBBNum)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   InterferenceCache &operator=(const InterferenceCache &other) = delete;
160   InterferenceCache(const InterferenceCache &other) = delete;
~InterferenceCache()161   ~InterferenceCache() {
162     free(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.
getMaxCursors()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 
setEntry(Entry * E)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(-1);
188       CacheEntry = E;
189       if (CacheEntry)
190         CacheEntry->addRef(+1);
191     }
192 
193   public:
194     /// Cursor - Create a dangling cursor.
195     Cursor() = default;
196 
Cursor(const Cursor & O)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 
~Cursor()206     ~Cursor() { setEntry(nullptr); }
207 
208     /// setPhysReg - Point this cursor to PhysReg's interference.
setPhysReg(InterferenceCache & Cache,MCRegister PhysReg)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.
moveToBlock(unsigned 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.
hasInterference()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.
first()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.
last()235     SlotIndex last() {
236       return Current->Last;
237     }
238   };
239 };
240 
241 } // end namespace llvm
242 
243 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
244