Enable use of ranges for translation units in the presence of
[oota-llvm.git] / lib / CodeGen / InterferenceCache.h
1 //===-- InterferenceCache.h - Caching per-block interference ---*- C++ -*--===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // InterferenceCache remembers per-block interference from LiveIntervalUnions,
11 // fixed RegUnit interference, and register masks.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #ifndef LLVM_CODEGEN_INTERFERENCECACHE
16 #define LLVM_CODEGEN_INTERFERENCECACHE
17
18 #include "llvm/CodeGen/LiveIntervalUnion.h"
19
20 namespace llvm {
21
22 class LiveIntervals;
23
24 class InterferenceCache {
25   const TargetRegisterInfo *TRI;
26   LiveIntervalUnion *LIUArray;
27   MachineFunction *MF;
28
29   /// BlockInterference - information about the interference in a single basic
30   /// block.
31   struct BlockInterference {
32     BlockInterference() : Tag(0) {}
33     unsigned Tag;
34     SlotIndex First;
35     SlotIndex Last;
36   };
37
38   /// Entry - A cache entry containing interference information for all aliases
39   /// of PhysReg in all basic blocks.
40   class Entry {
41     /// PhysReg - The register currently represented.
42     unsigned PhysReg;
43
44     /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
45     /// change.
46     unsigned Tag;
47
48     /// RefCount - The total number of Cursor instances referring to this Entry.
49     unsigned RefCount;
50
51     /// MF - The current function.
52     MachineFunction *MF;
53
54     /// Indexes - Mapping block numbers to SlotIndex ranges.
55     SlotIndexes *Indexes;
56
57     /// LIS - Used for accessing register mask interference maps.
58     LiveIntervals *LIS;
59
60     /// PrevPos - The previous position the iterators were moved to.
61     SlotIndex PrevPos;
62
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.
66     struct RegUnitInfo {
67       /// Iterator pointing into the LiveIntervalUnion containing virtual
68       /// register interference.
69       LiveIntervalUnion::SegmentIter VirtI;
70
71       /// Tag of the LIU last time we looked.
72       unsigned VirtTag;
73
74       /// Fixed interference in RegUnit.
75       LiveRange *Fixed;
76
77       /// Iterator pointing into the fixed RegUnit interference.
78       LiveInterval::iterator FixedI;
79
80       RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()), Fixed(0) {
81         VirtI.setMap(LIU.getMap());
82       }
83     };
84
85     /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
86     /// more than 4 RegUnits.
87     SmallVector<RegUnitInfo, 4> RegUnits;
88
89     /// Blocks - Interference for each block in the function.
90     SmallVector<BlockInterference, 8> Blocks;
91
92     /// update - Recompute Blocks[MBBNum]
93     void update(unsigned MBBNum);
94
95   public:
96     Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(0), LIS(0) {}
97
98     void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
99       assert(!hasRefs() && "Cannot clear cache entry with references");
100       PhysReg = 0;
101       MF = mf;
102       Indexes = indexes;
103       LIS = lis;
104     }
105
106     unsigned getPhysReg() const { return PhysReg; }
107
108     void addRef(int Delta) { RefCount += Delta; }
109
110     bool hasRefs() const { return RefCount > 0; }
111
112     void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
113
114     /// valid - Return true if this is a valid entry for physReg.
115     bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
116
117     /// reset - Initialize entry to represent physReg's aliases.
118     void reset(unsigned physReg,
119                LiveIntervalUnion *LIUArray,
120                const TargetRegisterInfo *TRI,
121                const MachineFunction *MF);
122
123     /// get - Return an up to date BlockInterference.
124     BlockInterference *get(unsigned MBBNum) {
125       if (Blocks[MBBNum].Tag != Tag)
126         update(MBBNum);
127       return &Blocks[MBBNum];
128     }
129   };
130
131   // We don't keep a cache entry for every physical register, that would use too
132   // much memory. Instead, a fixed number of cache entries are used in a round-
133   // robin manner.
134   enum { CacheEntries = 32 };
135
136   // Point to an entry for each physreg. The entry pointed to may not be up to
137   // date, and it may have been reused for a different physreg.
138   SmallVector<unsigned char, 2> PhysRegEntries;
139
140   // Next round-robin entry to be picked.
141   unsigned RoundRobin;
142
143   // The actual cache entries.
144   Entry Entries[CacheEntries];
145
146   // get - Get a valid entry for PhysReg.
147   Entry *get(unsigned PhysReg);
148
149 public:
150   InterferenceCache() : TRI(0), LIUArray(0), MF(0), RoundRobin(0) {}
151
152   /// init - Prepare cache for a new function.
153   void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*,
154             const TargetRegisterInfo *);
155
156   /// getMaxCursors - Return the maximum number of concurrent cursors that can
157   /// be supported.
158   unsigned getMaxCursors() const { return CacheEntries; }
159
160   /// Cursor - The primary query interface for the block interference cache.
161   class Cursor {
162     Entry *CacheEntry;
163     BlockInterference *Current;
164     static BlockInterference NoInterference;
165
166     void setEntry(Entry *E) {
167       Current = 0;
168       // Update reference counts. Nothing happens when RefCount reaches 0, so
169       // we don't have to check for E == CacheEntry etc.
170       if (CacheEntry)
171         CacheEntry->addRef(-1);
172       CacheEntry = E;
173       if (CacheEntry)
174         CacheEntry->addRef(+1);
175     }
176
177   public:
178     /// Cursor - Create a dangling cursor.
179     Cursor() : CacheEntry(0), Current(0) {}
180     ~Cursor() { setEntry(0); }
181
182     Cursor(const Cursor &O) : CacheEntry(0), Current(0) {
183       setEntry(O.CacheEntry);
184     }
185
186     Cursor &operator=(const Cursor &O) {
187       setEntry(O.CacheEntry);
188       return *this;
189     }
190
191     /// setPhysReg - Point this cursor to PhysReg's interference.
192     void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
193       // Release reference before getting a new one. That guarantees we can
194       // actually have CacheEntries live cursors.
195       setEntry(0);
196       if (PhysReg)
197         setEntry(Cache.get(PhysReg));
198     }
199
200     /// moveTo - Move cursor to basic block MBBNum.
201     void moveToBlock(unsigned MBBNum) {
202       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
203     }
204
205     /// hasInterference - Return true if the current block has any interference.
206     bool hasInterference() {
207       return Current->First.isValid();
208     }
209
210     /// first - Return the starting index of the first interfering range in the
211     /// current block.
212     SlotIndex first() {
213       return Current->First;
214     }
215
216     /// last - Return the ending index of the last interfering range in the
217     /// current block.
218     SlotIndex last() {
219       return Current->Last;
220     }
221   };
222
223   friend class Cursor;
224 };
225
226 } // namespace llvm
227
228 #endif