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_LIB_CODEGEN_INTERFERENCECACHE_H
16 #define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
17 
18 #include "llvm/CodeGen/LiveIntervalUnion.h"
19 
20 namespace llvm {
21 
22 class LiveIntervals;
23 
24 class LLVM_LIBRARY_VISIBILITY 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 {
BlockInterferenceBlockInterference32     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 
RegUnitInfoRegUnitInfo80       RegUnitInfo(LiveIntervalUnion &LIU)
81           : VirtTag(LIU.getTag()), Fixed(nullptr) {
82         VirtI.setMap(LIU.getMap());
83       }
84     };
85 
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;
89 
90     /// Blocks - Interference for each block in the function.
91     SmallVector<BlockInterference, 8> Blocks;
92 
93     /// update - Recompute Blocks[MBBNum]
94     void update(unsigned MBBNum);
95 
96   public:
Entry()97     Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(nullptr), LIS(nullptr) {}
98 
clear(MachineFunction * mf,SlotIndexes * indexes,LiveIntervals * lis)99     void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
100       assert(!hasRefs() && "Cannot clear cache entry with references");
101       PhysReg = 0;
102       MF = mf;
103       Indexes = indexes;
104       LIS = lis;
105     }
106 
getPhysReg()107     unsigned getPhysReg() const { return PhysReg; }
108 
addRef(int Delta)109     void addRef(int Delta) { RefCount += Delta; }
110 
hasRefs()111     bool hasRefs() const { return RefCount > 0; }
112 
113     void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
114 
115     /// valid - Return true if this is a valid entry for physReg.
116     bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
117 
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);
123 
124     /// get - Return an up to date BlockInterference.
get(unsigned MBBNum)125     BlockInterference *get(unsigned MBBNum) {
126       if (Blocks[MBBNum].Tag != Tag)
127         update(MBBNum);
128       return &Blocks[MBBNum];
129     }
130   };
131 
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-
134   // robin manner.
135   enum { CacheEntries = 32 };
136 
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;
141 
142   // Next round-robin entry to be picked.
143   unsigned RoundRobin;
144 
145   // The actual cache entries.
146   Entry Entries[CacheEntries];
147 
148   // get - Get a valid entry for PhysReg.
149   Entry *get(unsigned PhysReg);
150 
151 public:
InterferenceCache()152   InterferenceCache()
153     : TRI(nullptr), LIUArray(nullptr), MF(nullptr), PhysRegEntries(nullptr),
154       PhysRegEntriesCount(0), RoundRobin(0) {}
155 
~InterferenceCache()156   ~InterferenceCache() {
157     free(PhysRegEntries);
158   }
159 
160   void reinitPhysRegEntries();
161 
162   /// init - Prepare cache for a new function.
163   void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, LiveIntervals*,
164             const TargetRegisterInfo *);
165 
166   /// getMaxCursors - Return the maximum number of concurrent cursors that can
167   /// be supported.
getMaxCursors()168   unsigned getMaxCursors() const { return CacheEntries; }
169 
170   /// Cursor - The primary query interface for the block interference cache.
171   class Cursor {
172     Entry *CacheEntry;
173     const BlockInterference *Current;
174     static const BlockInterference NoInterference;
175 
setEntry(Entry * E)176     void setEntry(Entry *E) {
177       Current = nullptr;
178       // Update reference counts. Nothing happens when RefCount reaches 0, so
179       // we don't have to check for E == CacheEntry etc.
180       if (CacheEntry)
181         CacheEntry->addRef(-1);
182       CacheEntry = E;
183       if (CacheEntry)
184         CacheEntry->addRef(+1);
185     }
186 
187   public:
188     /// Cursor - Create a dangling cursor.
Cursor()189     Cursor() : CacheEntry(nullptr), Current(nullptr) {}
~Cursor()190     ~Cursor() { setEntry(nullptr); }
191 
Cursor(const Cursor & O)192     Cursor(const Cursor &O) : CacheEntry(nullptr), Current(nullptr) {
193       setEntry(O.CacheEntry);
194     }
195 
196     Cursor &operator=(const Cursor &O) {
197       setEntry(O.CacheEntry);
198       return *this;
199     }
200 
201     /// setPhysReg - Point this cursor to PhysReg's interference.
setPhysReg(InterferenceCache & Cache,unsigned PhysReg)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.
205       setEntry(nullptr);
206       if (PhysReg)
207         setEntry(Cache.get(PhysReg));
208     }
209 
210     /// moveTo - Move cursor to basic block MBBNum.
moveToBlock(unsigned MBBNum)211     void moveToBlock(unsigned MBBNum) {
212       Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
213     }
214 
215     /// hasInterference - Return true if the current block has any interference.
hasInterference()216     bool hasInterference() {
217       return Current->First.isValid();
218     }
219 
220     /// first - Return the starting index of the first interfering range in the
221     /// current block.
first()222     SlotIndex first() {
223       return Current->First;
224     }
225 
226     /// last - Return the ending index of the last interfering range in the
227     /// current block.
last()228     SlotIndex last() {
229       return Current->Last;
230     }
231   };
232 
233   friend class Cursor;
234 };
235 
236 } // namespace llvm
237 
238 #endif
239