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/CodeGen/LiveIntervalUnion.h"
24 class InterferenceCache {
25 const TargetRegisterInfo *TRI;
26 LiveIntervalUnion *LIUArray;
29 /// BlockInterference - information about the interference in a single basic
31 struct BlockInterference {
32 BlockInterference() : Tag(0) {}
38 /// Entry - A cache entry containing interference information for all aliases
39 /// of PhysReg in all basic blocks.
41 /// PhysReg - The register currently represented.
44 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
48 /// RefCount - The total number of Cursor instances referring to this Entry.
51 /// MF - The current function.
54 /// Indexes - Mapping block numbers to SlotIndex ranges.
57 /// LIS - Used for accessing register mask interference maps.
60 /// PrevPos - The previous position the iterators were moved to.
63 /// RegUnitInfo - Information tracked about each RegUnit in PhysReg.
64 /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos)
65 /// had just been called.
67 /// Iterator pointing into the LiveIntervalUnion containing virtual
68 /// register interference.
69 LiveIntervalUnion::SegmentIter VirtI;
71 /// Tag of the LIU last time we looked.
74 /// Fixed interference in RegUnit.
77 /// Iterator pointing into the fixed RegUnit interference.
78 LiveInterval::iterator FixedI;
80 RegUnitInfo(LiveIntervalUnion &LIU)
81 : VirtTag(LIU.getTag()), Fixed(nullptr) {
82 VirtI.setMap(LIU.getMap());
86 /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
87 /// more than 4 RegUnits.
88 SmallVector<RegUnitInfo, 4> RegUnits;
90 /// Blocks - Interference for each block in the function.
91 SmallVector<BlockInterference, 8> Blocks;
93 /// update - Recompute Blocks[MBBNum]
94 void update(unsigned MBBNum);
97 Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(nullptr), LIS(nullptr) {}
99 void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
100 assert(!hasRefs() && "Cannot clear cache entry with references");
107 unsigned getPhysReg() const { return PhysReg; }
109 void addRef(int Delta) { RefCount += Delta; }
111 bool hasRefs() const { return RefCount > 0; }
113 void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
115 /// valid - Return true if this is a valid entry for physReg.
116 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
118 /// reset - Initialize entry to represent physReg's aliases.
119 void reset(unsigned physReg,
120 LiveIntervalUnion *LIUArray,
121 const TargetRegisterInfo *TRI,
122 const MachineFunction *MF);
124 /// get - Return an up to date BlockInterference.
125 BlockInterference *get(unsigned MBBNum) {
126 if (Blocks[MBBNum].Tag != Tag)
128 return &Blocks[MBBNum];
132 // We don't keep a cache entry for every physical register, that would use too
133 // much memory. Instead, a fixed number of cache entries are used in a round-
135 enum { CacheEntries = 32 };
137 // Point to an entry for each physreg. The entry pointed to may not be up to
138 // date, and it may have been reused for a different physreg.
139 unsigned char* PhysRegEntries;
140 size_t PhysRegEntriesCount;
142 // Next round-robin entry to be picked.
145 // The actual cache entries.
146 Entry Entries[CacheEntries];
148 // get - Get a valid entry for PhysReg.
149 Entry *get(unsigned PhysReg);
153 : TRI(nullptr), LIUArray(nullptr), MF(nullptr), PhysRegEntries(nullptr),
154 PhysRegEntriesCount(0), RoundRobin(0) {}
156 ~InterferenceCache() {
157 free(PhysRegEntries);
160 void reinitPhysRegEntries();
162 /// init - Prepare cache for a new function.
163 void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*,
164 const TargetRegisterInfo *);
166 /// getMaxCursors - Return the maximum number of concurrent cursors that can
168 unsigned getMaxCursors() const { return CacheEntries; }
170 /// Cursor - The primary query interface for the block interference cache.
173 const BlockInterference *Current;
174 static const BlockInterference NoInterference;
176 void setEntry(Entry *E) {
178 // Update reference counts. Nothing happens when RefCount reaches 0, so
179 // we don't have to check for E == CacheEntry etc.
181 CacheEntry->addRef(-1);
184 CacheEntry->addRef(+1);
188 /// Cursor - Create a dangling cursor.
189 Cursor() : CacheEntry(nullptr), Current(nullptr) {}
190 ~Cursor() { setEntry(nullptr); }
192 Cursor(const Cursor &O) : CacheEntry(nullptr), Current(nullptr) {
193 setEntry(O.CacheEntry);
196 Cursor &operator=(const Cursor &O) {
197 setEntry(O.CacheEntry);
201 /// setPhysReg - Point this cursor to PhysReg's interference.
202 void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
203 // Release reference before getting a new one. That guarantees we can
204 // actually have CacheEntries live cursors.
207 setEntry(Cache.get(PhysReg));
210 /// moveTo - Move cursor to basic block MBBNum.
211 void moveToBlock(unsigned MBBNum) {
212 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
215 /// hasInterference - Return true if the current block has any interference.
216 bool hasInterference() {
217 return Current->First.isValid();
220 /// first - Return the starting index of the first interfering range in the
223 return Current->First;
226 /// last - Return the ending index of the last interfering range in the
229 return Current->Last;