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 in LiveIntervalUnions.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_INTERFERENCECACHE
15 #define LLVM_CODEGEN_INTERFERENCECACHE
17 #include "LiveIntervalUnion.h"
21 class InterferenceCache {
22 const TargetRegisterInfo *TRI;
23 LiveIntervalUnion *LIUArray;
27 /// BlockInterference - information about the interference in a single basic
29 struct BlockInterference {
30 BlockInterference() : Tag(0) {}
36 /// Entry - A cache entry containing interference information for all aliases
37 /// of PhysReg in all basic blocks.
39 /// PhysReg - The register currently represented.
42 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
46 /// RefCount - The total number of Cursor instances referring to this Entry.
49 /// MF - The current function.
52 /// Indexes - Mapping block numbers to SlotIndex ranges.
55 /// PrevPos - The previous position the iterators were moved to.
58 /// AliasTags - A LiveIntervalUnion pointer and tag for each alias of
60 SmallVector<std::pair<LiveIntervalUnion*, unsigned>, 8> Aliases;
62 typedef LiveIntervalUnion::SegmentIter Iter;
64 /// Iters - an iterator for each alias
65 SmallVector<Iter, 8> Iters;
67 /// Blocks - Interference for each block in the function.
68 SmallVector<BlockInterference, 8> Blocks;
70 /// update - Recompute Blocks[MBBNum]
71 void update(unsigned MBBNum);
74 Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(0) {}
76 void clear(MachineFunction *mf, SlotIndexes *indexes) {
77 assert(!hasRefs() && "Cannot clear cache entry with references");
83 unsigned getPhysReg() const { return PhysReg; }
85 void addRef(int Delta) { RefCount += Delta; }
87 bool hasRefs() const { return RefCount > 0; }
91 /// valid - Return true if this is a valid entry for physReg.
92 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
94 /// reset - Initialize entry to represent physReg's aliases.
95 void reset(unsigned physReg,
96 LiveIntervalUnion *LIUArray,
97 const TargetRegisterInfo *TRI,
98 const MachineFunction *MF);
100 /// get - Return an up to date BlockInterference.
101 BlockInterference *get(unsigned MBBNum) {
102 if (Blocks[MBBNum].Tag != Tag)
104 return &Blocks[MBBNum];
108 // We don't keep a cache entry for every physical register, that would use too
109 // much memory. Instead, a fixed number of cache entries are used in a round-
111 enum { CacheEntries = 32 };
113 // Point to an entry for each physreg. The entry pointed to may not be up to
114 // date, and it may have been reused for a different physreg.
115 SmallVector<unsigned char, 2> PhysRegEntries;
117 // Next round-robin entry to be picked.
120 // The actual cache entries.
121 Entry Entries[CacheEntries];
123 // get - Get a valid entry for PhysReg.
124 Entry *get(unsigned PhysReg);
127 InterferenceCache() : TRI(0), LIUArray(0), Indexes(0), MF(0), RoundRobin(0) {}
129 /// init - Prepare cache for a new function.
130 void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*,
131 const TargetRegisterInfo *);
133 /// getMaxCursors - Return the maximum number of concurrent cursors that can
135 unsigned getMaxCursors() const { return CacheEntries; }
137 /// Cursor - The primary query interface for the block interference cache.
140 BlockInterference *Current;
142 void setEntry(Entry *E) {
143 // Update reference counts. Nothing happens when RefCount reaches 0, so
144 // we don't have to check for E == CacheEntry etc.
146 CacheEntry->addRef(-1);
149 CacheEntry->addRef(+1);
154 /// Cursor - Create a dangling cursor.
155 Cursor() : CacheEntry(0), Current(0) {}
156 ~Cursor() { setEntry(0); }
158 Cursor(const Cursor &O) {
159 setEntry(O.CacheEntry);
162 Cursor &operator=(const Cursor &O) {
163 setEntry(O.CacheEntry);
167 /// setPhysReg - Point this cursor to PhysReg's interference.
168 void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
169 // Release reference before getting a new one. That guarantees we can
170 // actually have CacheEntries live cursors.
173 setEntry(Cache.get(PhysReg));
176 /// moveTo - Move cursor to basic block MBBNum.
177 void moveToBlock(unsigned MBBNum) {
178 Current = CacheEntry->get(MBBNum);
181 /// hasInterference - Return true if the current block has any interference.
182 bool hasInterference() {
183 return Current->First.isValid();
186 /// first - Return the starting index of the first interfering range in the
189 return Current->First;
192 /// last - Return the ending index of the last interfering range in the
195 return Current->Last;