1//===- InterferenceCache.cpp - Caching per-block interference -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// InterferenceCache remembers per-block interference in LiveIntervalUnions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "InterferenceCache.h"
14#include "llvm/ADT/ArrayRef.h"
15#include "llvm/CodeGen/LiveIntervals.h"
16#include "llvm/CodeGen/MachineBasicBlock.h"
17#include "llvm/CodeGen/MachineFunction.h"
18#include "llvm/CodeGen/MachineOperand.h"
19#include "llvm/CodeGen/TargetRegisterInfo.h"
20#include "llvm/Support/ErrorHandling.h"
21#include <cassert>
22#include <cstdint>
23#include <tuple>
24
25using namespace llvm;
26
27#define DEBUG_TYPE "regalloc"
28
29// Static member used for null interference cursors.
30const InterferenceCache::BlockInterference
31 InterferenceCache::Cursor::NoInterference;
32
33// Initializes PhysRegEntries (instead of a SmallVector, PhysRegEntries is a
34// buffer of size NumPhysRegs to speed up alloc/clear for targets with large
35// reg files). Calloced memory is used for good form, and quites tools like
36// Valgrind too, but zero initialized memory is not required by the algorithm:
37// this is because PhysRegEntries works like a SparseSet and its entries are
38// only valid when there is a corresponding CacheEntries assignment. There is
39// also support for when pass managers are reused for targets with different
40// numbers of PhysRegs: in this case PhysRegEntries is freed and reinitialized.
41void InterferenceCache::reinitPhysRegEntries() {
42 if (PhysRegEntriesCount == TRI->getNumRegs()) return;
43 free(ptr: PhysRegEntries);
44 PhysRegEntriesCount = TRI->getNumRegs();
45 PhysRegEntries = static_cast<unsigned char*>(
46 safe_calloc(Count: PhysRegEntriesCount, Sz: sizeof(unsigned char)));
47}
48
49void InterferenceCache::init(MachineFunction *mf,
50 LiveIntervalUnion *liuarray,
51 SlotIndexes *indexes,
52 LiveIntervals *lis,
53 const TargetRegisterInfo *tri) {
54 MF = mf;
55 LIUArray = liuarray;
56 TRI = tri;
57 reinitPhysRegEntries();
58 for (Entry &E : Entries)
59 E.clear(mf, indexes, lis);
60}
61
62InterferenceCache::Entry *InterferenceCache::get(MCRegister PhysReg) {
63 unsigned char E = PhysRegEntries[PhysReg.id()];
64 if (E < CacheEntries && Entries[E].getPhysReg() == PhysReg) {
65 if (!Entries[E].valid(LIUArray, TRI))
66 Entries[E].revalidate(LIUArray, TRI);
67 return &Entries[E];
68 }
69 // No valid entry exists, pick the next round-robin entry.
70 E = RoundRobin;
71 if (++RoundRobin == CacheEntries)
72 RoundRobin = 0;
73 for (unsigned i = 0; i != CacheEntries; ++i) {
74 // Skip entries that are in use.
75 if (Entries[E].hasRefs()) {
76 if (++E == CacheEntries)
77 E = 0;
78 continue;
79 }
80 Entries[E].reset(physReg: PhysReg, LIUArray, TRI, MF);
81 PhysRegEntries[PhysReg.id()] = E;
82 return &Entries[E];
83 }
84 llvm_unreachable("Ran out of interference cache entries.");
85}
86
87/// revalidate - LIU contents have changed, update tags.
88void InterferenceCache::Entry::revalidate(LiveIntervalUnion *LIUArray,
89 const TargetRegisterInfo *TRI) {
90 // Invalidate all block entries.
91 ++Tag;
92 // Invalidate all iterators.
93 PrevPos = SlotIndex();
94 unsigned i = 0;
95 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg))
96 RegUnits[i++].VirtTag = LIUArray[static_cast<unsigned>(Unit)].getTag();
97}
98
99void InterferenceCache::Entry::reset(MCRegister physReg,
100 LiveIntervalUnion *LIUArray,
101 const TargetRegisterInfo *TRI,
102 const MachineFunction *MF) {
103 assert(!hasRefs() && "Cannot reset cache entry with references");
104 // LIU's changed, invalidate cache.
105 ++Tag;
106 PhysReg = physReg;
107 Blocks.resize(N: MF->getNumBlockIDs());
108
109 // Reset iterators.
110 PrevPos = SlotIndex();
111 RegUnits.clear();
112 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
113 RegUnits.push_back(Elt: LIUArray[static_cast<unsigned>(Unit)]);
114 RegUnits.back().Fixed = &LIS->getRegUnit(Unit);
115 }
116}
117
118bool InterferenceCache::Entry::valid(LiveIntervalUnion *LIUArray,
119 const TargetRegisterInfo *TRI) {
120 unsigned i = 0, e = RegUnits.size();
121 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
122 if (i == e)
123 return false;
124 if (LIUArray[static_cast<unsigned>(Unit)].changedSince(tag: RegUnits[i].VirtTag))
125 return false;
126 ++i;
127 }
128 return i == e;
129}
130
131void InterferenceCache::Entry::update(unsigned MBBNum) {
132 MachineBasicBlock *MBB = MF->getBlockNumbered(N: MBBNum);
133 SlotIndex Start, Stop;
134 std::tie(args&: Start, args&: Stop) = Indexes->getMBBRange(MBB);
135
136 // Use advanceTo only when possible.
137 if (PrevPos != Start) {
138 if (!PrevPos.isValid() || Start < PrevPos) {
139 for (RegUnitInfo &RUI : RegUnits) {
140 RUI.VirtI.find(x: Start);
141 RUI.FixedI = RUI.Fixed->find(Pos: Start);
142 }
143 } else {
144 for (RegUnitInfo &RUI : RegUnits) {
145 RUI.VirtI.advanceTo(x: Start);
146 if (RUI.FixedI != RUI.Fixed->end())
147 RUI.FixedI = RUI.Fixed->advanceTo(I: RUI.FixedI, Pos: Start);
148 }
149 }
150 PrevPos = Start;
151 }
152
153 MachineFunction::const_iterator MFI = MBB->getIterator();
154 BlockInterference *BI = &Blocks[MBBNum];
155 ArrayRef<SlotIndex> RegMaskSlots;
156 ArrayRef<const uint32_t*> RegMaskBits;
157
158 // Find the earliest virtreg and fixed interference start.
159 SlotIndex FirstStart;
160 for (const RegUnitInfo &RUI : RegUnits) {
161 const LiveIntervalUnion::SegmentIter &I = RUI.VirtI;
162 if (I.valid() && (!FirstStart.isValid() || I.start() < FirstStart))
163 FirstStart = I.start();
164 LiveInterval::const_iterator FI = RUI.FixedI;
165 if (FI != RUI.Fixed->end() &&
166 (!FirstStart.isValid() || FI->start < FirstStart))
167 FirstStart = FI->start;
168 }
169
170 while (true) {
171 BI->Tag = Tag;
172 BI->First = BI->Last = SlotIndex();
173
174 // Check for first interference from virtregs and fixed interference.
175 if (FirstStart.isValid() && FirstStart < Stop)
176 BI->First = FirstStart;
177
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(RegMask: RegMaskBits[i], PhysReg)) {
185 // Register mask i clobbers PhysReg before the LIU interference.
186 BI->First = RegMaskSlots[i];
187 break;
188 }
189
190 PrevPos = Stop;
191 if (BI->First.isValid())
192 break;
193
194 // No interference in this block? Go ahead and precompute the next block.
195 if (++MFI == MF->end())
196 return;
197 MBBNum = MFI->getNumber();
198 BI = &Blocks[MBBNum];
199 if (BI->Tag == Tag)
200 return;
201 std::tie(args&: Start, args&: Stop) = Indexes->getMBBRange(MBB: &*MFI);
202 }
203
204 // Check for last interference in block.
205 for (RegUnitInfo &RUI : RegUnits) {
206 LiveIntervalUnion::SegmentIter &I = RUI.VirtI;
207 if (!I.valid() || I.start() >= Stop)
208 continue;
209 I.advanceTo(x: Stop);
210 bool Backup = !I.valid() || I.start() >= Stop;
211 if (Backup)
212 --I;
213 SlotIndex StopI = I.stop();
214 if (!BI->Last.isValid() || StopI > BI->Last)
215 BI->Last = StopI;
216 if (Backup)
217 ++I;
218 }
219
220 // Fixed interference.
221 for (RegUnitInfo &RUI : RegUnits) {
222 LiveInterval::iterator &I = RUI.FixedI;
223 LiveRange *LR = RUI.Fixed;
224 if (I == LR->end() || I->start >= Stop)
225 continue;
226 I = LR->advanceTo(I, Pos: Stop);
227 bool Backup = I == LR->end() || I->start >= Stop;
228 if (Backup)
229 --I;
230 SlotIndex StopI = I->end;
231 if (!BI->Last.isValid() || StopI > BI->Last)
232 BI->Last = StopI;
233 if (Backup)
234 ++I;
235 }
236
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(RegMask: 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();
245 break;
246 }
247}
248