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;
141 static BlockInterference NoInterference;
143 void setEntry(Entry *E) {
145 // Update reference counts. Nothing happens when RefCount reaches 0, so
146 // we don't have to check for E == CacheEntry etc.
148 CacheEntry->addRef(-1);
151 CacheEntry->addRef(+1);
155 /// Cursor - Create a dangling cursor.
156 Cursor() : CacheEntry(0), Current(0) {}
157 ~Cursor() { setEntry(0); }
159 Cursor(const Cursor &O) : CacheEntry(0), Current(0) {
160 setEntry(O.CacheEntry);
163 Cursor &operator=(const Cursor &O) {
164 setEntry(O.CacheEntry);
168 /// setPhysReg - Point this cursor to PhysReg's interference.
169 void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
170 // Release reference before getting a new one. That guarantees we can
171 // actually have CacheEntries live cursors.
174 setEntry(Cache.get(PhysReg));
177 /// moveTo - Move cursor to basic block MBBNum.
178 void moveToBlock(unsigned MBBNum) {
179 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
182 /// hasInterference - Return true if the current block has any interference.
183 bool hasInterference() {
184 return Current->First.isValid();
187 /// first - Return the starting index of the first interfering range in the
190 return Current->First;
193 /// last - Return the ending index of the last interfering range in the
196 return Current->Last;