1 //===- InterferenceCache.h - Caching per-block interference ----*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // InterferenceCache remembers per-block interference from LiveIntervalUnions,
11 // fixed RegUnit interference, and register masks.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
16 #define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
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"
30 class MachineFunction;
31 class TargetRegisterInfo;
33 class LLVM_LIBRARY_VISIBILITY InterferenceCache {
34 /// BlockInterference - information about the interference in a single basic
36 struct BlockInterference {
41 BlockInterference() {}
44 /// Entry - A cache entry containing interference information for all aliases
45 /// of PhysReg in all basic blocks.
47 /// PhysReg - The register currently represented.
50 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
54 /// RefCount - The total number of Cursor instances referring to this Entry.
55 unsigned RefCount = 0;
57 /// MF - The current function.
60 /// Indexes - Mapping block numbers to SlotIndex ranges.
61 SlotIndexes *Indexes = nullptr;
63 /// LIS - Used for accessing register mask interference maps.
64 LiveIntervals *LIS = nullptr;
66 /// PrevPos - The previous position the iterators were moved to.
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.
73 /// Iterator pointing into the LiveIntervalUnion containing virtual
74 /// register interference.
75 LiveIntervalUnion::SegmentIter VirtI;
77 /// Tag of the LIU last time we looked.
80 /// Fixed interference in RegUnit.
81 LiveRange *Fixed = nullptr;
83 /// Iterator pointing into the fixed RegUnit interference.
84 LiveInterval::iterator FixedI;
86 RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) {
87 VirtI.setMap(LIU.getMap());
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;
95 /// Blocks - Interference for each block in the function.
96 SmallVector<BlockInterference, 8> Blocks;
98 /// update - Recompute Blocks[MBBNum]
99 void update(unsigned MBBNum);
104 void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
105 assert(!hasRefs() && "Cannot clear cache entry with references");
112 unsigned getPhysReg() const { return PhysReg; }
114 void addRef(int Delta) { RefCount += Delta; }
116 bool hasRefs() const { return RefCount > 0; }
118 void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
120 /// valid - Return true if this is a valid entry for physReg.
121 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
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);
129 /// get - Return an up to date BlockInterference.
130 BlockInterference *get(unsigned MBBNum) {
131 if (Blocks[MBBNum].Tag != Tag)
133 return &Blocks[MBBNum];
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-
140 enum { CacheEntries = 32 };
142 const TargetRegisterInfo *TRI = nullptr;
143 LiveIntervalUnion *LIUArray = nullptr;
144 MachineFunction *MF = nullptr;
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;
151 // Next round-robin entry to be picked.
152 unsigned RoundRobin = 0;
154 // The actual cache entries.
155 Entry Entries[CacheEntries];
157 // get - Get a valid entry for PhysReg.
158 Entry *get(unsigned PhysReg);
163 InterferenceCache() = default;
165 ~InterferenceCache() {
166 free(PhysRegEntries);
169 void reinitPhysRegEntries();
171 /// init - Prepare cache for a new function.
172 void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
173 SlotIndexes *indexes, LiveIntervals *lis,
174 const TargetRegisterInfo *tri);
176 /// getMaxCursors - Return the maximum number of concurrent cursors that can
178 unsigned getMaxCursors() const { return CacheEntries; }
180 /// Cursor - The primary query interface for the block interference cache.
182 Entry *CacheEntry = nullptr;
183 const BlockInterference *Current = nullptr;
184 static const BlockInterference NoInterference;
186 void setEntry(Entry *E) {
188 // Update reference counts. Nothing happens when RefCount reaches 0, so
189 // we don't have to check for E == CacheEntry etc.
191 CacheEntry->addRef(-1);
194 CacheEntry->addRef(+1);
198 /// Cursor - Create a dangling cursor.
201 Cursor(const Cursor &O) {
202 setEntry(O.CacheEntry);
205 Cursor &operator=(const Cursor &O) {
206 setEntry(O.CacheEntry);
210 ~Cursor() { setEntry(nullptr); }
212 /// setPhysReg - Point this cursor to PhysReg's interference.
213 void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
214 // Release reference before getting a new one. That guarantees we can
215 // actually have CacheEntries live cursors.
218 setEntry(Cache.get(PhysReg));
221 /// moveTo - Move cursor to basic block MBBNum.
222 void moveToBlock(unsigned MBBNum) {
223 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
226 /// hasInterference - Return true if the current block has any interference.
227 bool hasInterference() {
228 return Current->First.isValid();
231 /// first - Return the starting index of the first interfering range in the
234 return Current->First;
237 /// last - Return the ending index of the last interfering range in the
240 return Current->Last;
245 } // end namespace llvm
247 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H