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"
23 class InterferenceCache {
24 const TargetRegisterInfo *TRI;
25 LiveIntervalUnion *LIUArray;
28 /// BlockInterference - information about the interference in a single basic
30 struct BlockInterference {
31 BlockInterference() : Tag(0) {}
37 /// Entry - A cache entry containing interference information for all aliases
38 /// of PhysReg in all basic blocks.
40 /// PhysReg - The register currently represented.
43 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
47 /// RefCount - The total number of Cursor instances referring to this Entry.
50 /// MF - The current function.
53 /// Indexes - Mapping block numbers to SlotIndex ranges.
56 /// LIS - Used for accessing register mask interference maps.
59 /// PrevPos - The previous position the iterators were moved to.
62 /// AliasTags - A LiveIntervalUnion pointer and tag for each alias of
64 SmallVector<std::pair<LiveIntervalUnion*, unsigned>, 8> Aliases;
66 typedef LiveIntervalUnion::SegmentIter Iter;
68 /// Iters - an iterator for each alias
69 SmallVector<Iter, 8> Iters;
71 /// Blocks - Interference for each block in the function.
72 SmallVector<BlockInterference, 8> Blocks;
74 /// update - Recompute Blocks[MBBNum]
75 void update(unsigned MBBNum);
78 Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(0), LIS(0) {}
80 void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
81 assert(!hasRefs() && "Cannot clear cache entry with references");
88 unsigned getPhysReg() const { return PhysReg; }
90 void addRef(int Delta) { RefCount += Delta; }
92 bool hasRefs() const { return RefCount > 0; }
96 /// valid - Return true if this is a valid entry for physReg.
97 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
99 /// reset - Initialize entry to represent physReg's aliases.
100 void reset(unsigned physReg,
101 LiveIntervalUnion *LIUArray,
102 const TargetRegisterInfo *TRI,
103 const MachineFunction *MF);
105 /// get - Return an up to date BlockInterference.
106 BlockInterference *get(unsigned MBBNum) {
107 if (Blocks[MBBNum].Tag != Tag)
109 return &Blocks[MBBNum];
113 // We don't keep a cache entry for every physical register, that would use too
114 // much memory. Instead, a fixed number of cache entries are used in a round-
116 enum { CacheEntries = 32 };
118 // Point to an entry for each physreg. The entry pointed to may not be up to
119 // date, and it may have been reused for a different physreg.
120 SmallVector<unsigned char, 2> PhysRegEntries;
122 // Next round-robin entry to be picked.
125 // The actual cache entries.
126 Entry Entries[CacheEntries];
128 // get - Get a valid entry for PhysReg.
129 Entry *get(unsigned PhysReg);
132 InterferenceCache() : TRI(0), LIUArray(0), MF(0), RoundRobin(0) {}
134 /// init - Prepare cache for a new function.
135 void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*,
136 const TargetRegisterInfo *);
138 /// getMaxCursors - Return the maximum number of concurrent cursors that can
140 unsigned getMaxCursors() const { return CacheEntries; }
142 /// Cursor - The primary query interface for the block interference cache.
145 BlockInterference *Current;
146 static BlockInterference NoInterference;
148 void setEntry(Entry *E) {
150 // Update reference counts. Nothing happens when RefCount reaches 0, so
151 // we don't have to check for E == CacheEntry etc.
153 CacheEntry->addRef(-1);
156 CacheEntry->addRef(+1);
160 /// Cursor - Create a dangling cursor.
161 Cursor() : CacheEntry(0), Current(0) {}
162 ~Cursor() { setEntry(0); }
164 Cursor(const Cursor &O) : CacheEntry(0), Current(0) {
165 setEntry(O.CacheEntry);
168 Cursor &operator=(const Cursor &O) {
169 setEntry(O.CacheEntry);
173 /// setPhysReg - Point this cursor to PhysReg's interference.
174 void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
175 // Release reference before getting a new one. That guarantees we can
176 // actually have CacheEntries live cursors.
179 setEntry(Cache.get(PhysReg));
182 /// moveTo - Move cursor to basic block MBBNum.
183 void moveToBlock(unsigned MBBNum) {
184 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
187 /// hasInterference - Return true if the current block has any interference.
188 bool hasInterference() {
189 return Current->First.isValid();
192 /// first - Return the starting index of the first interfering range in the
195 return Current->First;
198 /// last - Return the ending index of the last interfering range in the
201 return Current->Last;