1 //===-- InterferenceCache.cpp - Caching per-block interference ---------*--===//
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 #define DEBUG_TYPE "regalloc"
15 #include "InterferenceCache.h"
16 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
17 #include "llvm/Support/ErrorHandling.h"
18 #include "llvm/Target/TargetRegisterInfo.h"
22 // Static member used for null interference cursors.
23 InterferenceCache::BlockInterference InterferenceCache::Cursor::NoInterference;
25 // Initializes PhysRegEntries (instead of a SmallVector, PhysRegEntries is a
26 // buffer of size NumPhysRegs to speed up alloc/clear for targets with large
27 // reg files). Calloced memory is used for good form, and quites tools like
28 // Valgrind too, but zero initialized memory is not required by the algorithm:
29 // this is because PhysRegEntries works like a SparseSet and its entries are
30 // only valid when there is a corresponding CacheEntries assignment. There is
31 // also support for when pass managers are reused for targets with different
32 // numbers of PhysRegs: in this case PhysRegEntries is freed and reinitialized.
33 void InterferenceCache::reinitPhysRegEntries() {
34 if (PhysRegEntriesCount == TRI->getNumRegs()) return;
36 PhysRegEntriesCount = TRI->getNumRegs();
37 PhysRegEntries = (unsigned char*)
38 calloc(PhysRegEntriesCount, sizeof(unsigned char));
41 void InterferenceCache::init(MachineFunction *mf,
42 LiveIntervalUnion *liuarray,
45 const TargetRegisterInfo *tri) {
49 reinitPhysRegEntries();
50 for (unsigned i = 0; i != CacheEntries; ++i)
51 Entries[i].clear(mf, indexes, lis);
54 InterferenceCache::Entry *InterferenceCache::get(unsigned PhysReg) {
55 unsigned E = PhysRegEntries[PhysReg];
56 if (E < CacheEntries && Entries[E].getPhysReg() == PhysReg) {
57 if (!Entries[E].valid(LIUArray, TRI))
58 Entries[E].revalidate(LIUArray, TRI);
61 // No valid entry exists, pick the next round-robin entry.
63 if (++RoundRobin == CacheEntries)
65 for (unsigned i = 0; i != CacheEntries; ++i) {
66 // Skip entries that are in use.
67 if (Entries[E].hasRefs()) {
68 if (++E == CacheEntries)
72 Entries[E].reset(PhysReg, LIUArray, TRI, MF);
73 PhysRegEntries[PhysReg] = E;
76 llvm_unreachable("Ran out of interference cache entries.");
79 /// revalidate - LIU contents have changed, update tags.
80 void InterferenceCache::Entry::revalidate(LiveIntervalUnion *LIUArray,
81 const TargetRegisterInfo *TRI) {
82 // Invalidate all block entries.
84 // Invalidate all iterators.
85 PrevPos = SlotIndex();
87 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units, ++i)
88 RegUnits[i].VirtTag = LIUArray[*Units].getTag();
91 void InterferenceCache::Entry::reset(unsigned physReg,
92 LiveIntervalUnion *LIUArray,
93 const TargetRegisterInfo *TRI,
94 const MachineFunction *MF) {
95 assert(!hasRefs() && "Cannot reset cache entry with references");
96 // LIU's changed, invalidate cache.
99 Blocks.resize(MF->getNumBlockIDs());
102 PrevPos = SlotIndex();
104 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
105 RegUnits.push_back(LIUArray[*Units]);
106 RegUnits.back().Fixed = &LIS->getRegUnit(*Units);
110 bool InterferenceCache::Entry::valid(LiveIntervalUnion *LIUArray,
111 const TargetRegisterInfo *TRI) {
112 unsigned i = 0, e = RegUnits.size();
113 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units, ++i) {
116 if (LIUArray[*Units].changedSince(RegUnits[i].VirtTag))
122 void InterferenceCache::Entry::update(unsigned MBBNum) {
123 SlotIndex Start, Stop;
124 std::tie(Start, Stop) = Indexes->getMBBRange(MBBNum);
126 // Use advanceTo only when possible.
127 if (PrevPos != Start) {
128 if (!PrevPos.isValid() || Start < PrevPos) {
129 for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
130 RegUnitInfo &RUI = RegUnits[i];
131 RUI.VirtI.find(Start);
132 RUI.FixedI = RUI.Fixed->find(Start);
135 for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
136 RegUnitInfo &RUI = RegUnits[i];
137 RUI.VirtI.advanceTo(Start);
138 if (RUI.FixedI != RUI.Fixed->end())
139 RUI.FixedI = RUI.Fixed->advanceTo(RUI.FixedI, Start);
145 MachineFunction::const_iterator MFI = MF->getBlockNumbered(MBBNum);
146 BlockInterference *BI = &Blocks[MBBNum];
147 ArrayRef<SlotIndex> RegMaskSlots;
148 ArrayRef<const uint32_t*> RegMaskBits;
151 BI->First = BI->Last = SlotIndex();
153 // Check for first interference from virtregs.
154 for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
155 LiveIntervalUnion::SegmentIter &I = RegUnits[i].VirtI;
158 SlotIndex StartI = I.start();
161 if (!BI->First.isValid() || StartI < BI->First)
165 // Same thing for fixed interference.
166 for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
167 LiveInterval::const_iterator I = RegUnits[i].FixedI;
168 LiveInterval::const_iterator E = RegUnits[i].Fixed->end();
171 SlotIndex StartI = I->start;
174 if (!BI->First.isValid() || StartI < BI->First)
178 // Also check for register mask interference.
179 RegMaskSlots = LIS->getRegMaskSlotsInBlock(MBBNum);
180 RegMaskBits = LIS->getRegMaskBitsInBlock(MBBNum);
181 SlotIndex Limit = BI->First.isValid() ? BI->First : Stop;
182 for (unsigned i = 0, e = RegMaskSlots.size();
183 i != e && RegMaskSlots[i] < Limit; ++i)
184 if (MachineOperand::clobbersPhysReg(RegMaskBits[i], PhysReg)) {
185 // Register mask i clobbers PhysReg before the LIU interference.
186 BI->First = RegMaskSlots[i];
191 if (BI->First.isValid())
194 // No interference in this block? Go ahead and precompute the next block.
195 if (++MFI == MF->end())
197 MBBNum = MFI->getNumber();
198 BI = &Blocks[MBBNum];
201 std::tie(Start, Stop) = Indexes->getMBBRange(MBBNum);
204 // Check for last interference in block.
205 for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
206 LiveIntervalUnion::SegmentIter &I = RegUnits[i].VirtI;
207 if (!I.valid() || I.start() >= Stop)
210 bool Backup = !I.valid() || I.start() >= Stop;
213 SlotIndex StopI = I.stop();
214 if (!BI->Last.isValid() || StopI > BI->Last)
220 // Fixed interference.
221 for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
222 LiveInterval::iterator &I = RegUnits[i].FixedI;
223 LiveRange *LR = RegUnits[i].Fixed;
224 if (I == LR->end() || I->start >= Stop)
226 I = LR->advanceTo(I, Stop);
227 bool Backup = I == LR->end() || I->start >= Stop;
230 SlotIndex StopI = I->end;
231 if (!BI->Last.isValid() || StopI > BI->Last)
237 // Also check for register mask interference.
238 SlotIndex Limit = BI->Last.isValid() ? BI->Last : Start;
239 for (unsigned i = RegMaskSlots.size();
240 i && RegMaskSlots[i-1].getDeadSlot() > Limit; --i)
241 if (MachineOperand::clobbersPhysReg(RegMaskBits[i-1], PhysReg)) {
242 // Register mask i-1 clobbers PhysReg after the LIU interference.
243 // Model the regmask clobber as a dead def.
244 BI->Last = RegMaskSlots[i-1].getDeadSlot();