1//===- LiveRegMatrix.cpp - Track register 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// This file defines the LiveRegMatrix analysis pass.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/LiveRegMatrix.h"
14#include "RegisterCoalescer.h"
15#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/CodeGen/LiveInterval.h"
18#include "llvm/CodeGen/LiveIntervalUnion.h"
19#include "llvm/CodeGen/LiveIntervals.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineOperand.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/CodeGen/TargetRegisterInfo.h"
24#include "llvm/CodeGen/TargetSubtargetInfo.h"
25#include "llvm/CodeGen/VirtRegMap.h"
26#include "llvm/InitializePasses.h"
27#include "llvm/MC/LaneBitmask.h"
28#include "llvm/MC/MCRegisterInfo.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Support/raw_ostream.h"
32#include <cassert>
33
34using namespace llvm;
35
36#define DEBUG_TYPE "regalloc"
37
38STATISTIC(NumAssigned , "Number of registers assigned");
39STATISTIC(NumUnassigned , "Number of registers unassigned");
40
41char LiveRegMatrixWrapperLegacy::ID = 0;
42INITIALIZE_PASS_BEGIN(LiveRegMatrixWrapperLegacy, "liveregmatrix",
43 "Live Register Matrix", false, false)
44INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
45INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)
46INITIALIZE_PASS_END(LiveRegMatrixWrapperLegacy, "liveregmatrix",
47 "Live Register Matrix", false, true)
48
49void LiveRegMatrixWrapperLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
50 AU.setPreservesAll();
51 AU.addRequiredTransitive<LiveIntervalsWrapperPass>();
52 AU.addRequiredTransitive<VirtRegMapWrapperLegacy>();
53 MachineFunctionPass::getAnalysisUsage(AU);
54}
55
56bool LiveRegMatrixWrapperLegacy::runOnMachineFunction(MachineFunction &MF) {
57 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
58 auto &VRM = getAnalysis<VirtRegMapWrapperLegacy>().getVRM();
59 LRM.init(MF, LIS, VRM);
60 return false;
61}
62
63void LiveRegMatrix::init(MachineFunction &MF, LiveIntervals &pLIS,
64 VirtRegMap &pVRM) {
65 TRI = MF.getSubtarget().getRegisterInfo();
66 LIS = &pLIS;
67 VRM = &pVRM;
68
69 unsigned NumRegUnits = TRI->getNumRegUnits();
70 if (NumRegUnits != Matrix.size())
71 Queries.reset(p: new LiveIntervalUnion::Query[NumRegUnits]);
72 Matrix.init(*LIUAlloc, Size: NumRegUnits);
73
74 // Make sure no stale queries get reused.
75 invalidateVirtRegs();
76}
77
78void LiveRegMatrixWrapperLegacy::releaseMemory() { LRM.releaseMemory(); }
79
80void LiveRegMatrix::releaseMemory() {
81 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
82 Matrix[static_cast<MCRegUnit>(i)].clear();
83 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
84 // have anything important to clear and LiveRegMatrix's runOnFunction()
85 // does a std::unique_ptr::reset anyways.
86 }
87}
88
89template <typename Callable>
90static bool foreachUnit(const TargetRegisterInfo *TRI,
91 const LiveInterval &VRegInterval, MCRegister PhysReg,
92 Callable Func) {
93 if (VRegInterval.hasSubRanges()) {
94 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
95 MCRegUnit Unit = (*Units).first;
96 LaneBitmask Mask = (*Units).second;
97 for (const LiveInterval::SubRange &S : VRegInterval.subranges()) {
98 if ((S.LaneMask & Mask).any()) {
99 if (Func(Unit, S))
100 return true;
101 break;
102 }
103 }
104 }
105 } else {
106 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
107 if (Func(Unit, VRegInterval))
108 return true;
109 }
110 }
111 return false;
112}
113
114void LiveRegMatrix::assign(const LiveInterval &VirtReg, MCRegister PhysReg) {
115 LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to "
116 << printReg(PhysReg, TRI) << ':');
117 assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment");
118 VRM->assignVirt2Phys(virtReg: VirtReg.reg(), physReg: PhysReg);
119
120 foreachUnit(
121 TRI, VRegInterval: VirtReg, PhysReg, Func: [&](MCRegUnit Unit, const LiveRange &Range) {
122 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
123 Matrix[Unit].unify(VirtReg, Range);
124 return false;
125 });
126
127 ++NumAssigned;
128 LLVM_DEBUG(dbgs() << '\n');
129}
130
131void LiveRegMatrix::unassign(const LiveInterval &VirtReg,
132 bool ClearAllReferencingSegments) {
133 Register PhysReg = VRM->getPhys(virtReg: VirtReg.reg());
134 LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI)
135 << " from " << printReg(PhysReg, TRI) << ':');
136 VRM->clearVirt(virtReg: VirtReg.reg());
137
138 if (!ClearAllReferencingSegments) {
139 foreachUnit(TRI, VRegInterval: VirtReg, PhysReg,
140 Func: [&](MCRegUnit Unit, const LiveRange &Range) {
141 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
142 Matrix[Unit].extract(VirtReg, Range);
143 return false;
144 });
145 } else {
146 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
147 Matrix[Unit].clearAllSegmentsReferencing(VirtRegLI: VirtReg);
148 }
149 }
150
151 ++NumUnassigned;
152 LLVM_DEBUG(dbgs() << '\n');
153}
154
155bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const {
156 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
157 if (!Matrix[Unit].empty())
158 return true;
159 }
160 return false;
161}
162
163bool LiveRegMatrix::checkRegMaskInterference(const LiveInterval &VirtReg,
164 MCRegister PhysReg) {
165 // Check if the cached information is valid.
166 // The same BitVector can be reused for all PhysRegs.
167 // We could cache multiple VirtRegs if it becomes necessary.
168 if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) {
169 RegMaskVirtReg = VirtReg.reg();
170 RegMaskTag = UserTag;
171 RegMaskUsable.clear();
172 LIS->checkRegMaskInterference(LI: VirtReg, UsableRegs&: RegMaskUsable);
173 }
174
175 // The BitVector is indexed by PhysReg, not register unit.
176 // Regmask interference is more fine grained than regunits.
177 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
178 return !RegMaskUsable.empty() &&
179 (!PhysReg || !RegMaskUsable.test(Idx: PhysReg.id()));
180}
181
182bool LiveRegMatrix::checkRegUnitInterference(const LiveInterval &VirtReg,
183 MCRegister PhysReg) {
184 if (VirtReg.empty())
185 return false;
186 CoalescerPair CP(VirtReg.reg(), PhysReg, *TRI);
187
188 bool Result = foreachUnit(
189 TRI, VRegInterval: VirtReg, PhysReg, Func: [&](MCRegUnit Unit, const LiveRange &Range) {
190 const LiveRange &UnitRange = LIS->getRegUnit(Unit);
191 return Range.overlaps(Other: UnitRange, CP, *LIS->getSlotIndexes());
192 });
193 return Result;
194}
195
196bool LiveRegMatrix::checkRegMaskInterference(SlotIndex Start, SlotIndex End,
197 MCRegister PhysReg) {
198 ArrayRef<SlotIndex> Slots = LIS->getRegMaskSlots();
199 ArrayRef<const uint32_t *> Bits = LIS->getRegMaskBits();
200
201 // Find the first regmask slot that is not before Start.
202 auto SlotI = llvm::lower_bound(Range&: Slots, Value&: Start);
203 for (; SlotI != Slots.end() && *SlotI < End; ++SlotI) {
204 if (MachineOperand::clobbersPhysReg(RegMask: Bits[SlotI - Slots.begin()], PhysReg))
205 return true;
206 }
207 return false;
208}
209
210bool LiveRegMatrix::checkRegUnitInterference(SlotIndex Start, SlotIndex End,
211 MCRegister PhysReg) {
212 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
213 if (LIS->getRegUnit(Unit).overlaps(Start, End))
214 return true;
215 }
216 return false;
217}
218
219LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
220 MCRegUnit RegUnit) {
221 LiveIntervalUnion::Query &Q = Queries[static_cast<unsigned>(RegUnit)];
222 Q.init(NewUserTag: UserTag, NewLR: LR, NewLiveUnion: Matrix[RegUnit]);
223 return Q;
224}
225
226LiveRegMatrix::InterferenceKind
227LiveRegMatrix::checkInterference(const LiveInterval &VirtReg,
228 MCRegister PhysReg) {
229 if (VirtReg.empty())
230 return IK_Free;
231
232 // Regmask interference is the fastest check.
233 if (checkRegMaskInterference(VirtReg, PhysReg))
234 return IK_RegMask;
235
236 // Check for fixed interference.
237 if (checkRegUnitInterference(VirtReg, PhysReg))
238 return IK_RegUnit;
239
240 // Check the matrix for virtual register interference.
241 bool Interference = foreachUnit(TRI, VRegInterval: VirtReg, PhysReg,
242 Func: [&](MCRegUnit Unit, const LiveRange &LR) {
243 return query(LR, RegUnit: Unit).checkInterference();
244 });
245 if (Interference)
246 return IK_VirtReg;
247
248 return IK_Free;
249}
250
251bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
252 MCRegister PhysReg) {
253 // Regmask interference is the fastest check.
254 if (checkRegMaskInterference(Start, End, PhysReg))
255 return true;
256
257 // Check for fixed interference.
258 if (checkRegUnitInterference(Start, End, PhysReg))
259 return true;
260
261 // Construct artificial live range containing only one segment [Start, End).
262 VNInfo valno(0, Start);
263 LiveRange::Segment Seg(Start, End, &valno);
264 LiveRange LR;
265 LR.addSegment(S: Seg);
266
267 // Check the matrix for virtual register interference with that segment.
268 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
269 // LR is stack-allocated. LiveRegMatrix caches queries by a key that
270 // includes the address of the live range. If (for the same reg unit) this
271 // checkInterference overload is called twice, without any other query()
272 // calls in between (on heap-allocated LiveRanges) - which would invalidate
273 // the cached query - the LR address seen the second time may well be the
274 // same as that seen the first time, while the Start/End/valno may not - yet
275 // the same cached result would be fetched. To avoid that, we don't cache
276 // this query.
277 //
278 // FIXME: the usability of the Query API needs to be improved to avoid
279 // subtle bugs due to query identity. Avoiding caching, for example, would
280 // greatly simplify things.
281 LiveIntervalUnion::Query Q;
282 Q.reset(NewUserTag: UserTag, NewLR: LR, NewLiveUnion: Matrix[Unit]);
283 if (Q.checkInterference())
284 return true;
285 }
286 return false;
287}
288
289LaneBitmask LiveRegMatrix::checkInterferenceLanes(SlotIndex Start,
290 SlotIndex End,
291 MCRegister PhysReg) {
292 // Construct artificial live range containing only one segment [Start, End).
293 VNInfo valno(0, Start);
294 LiveRange::Segment Seg(Start, End, &valno);
295 LiveRange LR;
296 LR.addSegment(S: Seg);
297
298 LaneBitmask InterferingLanes;
299
300 // Check for interference with that segment
301 for (MCRegUnitMaskIterator MCRU(PhysReg, TRI); MCRU.isValid(); ++MCRU) {
302 auto [Unit, Lanes] = *MCRU;
303 // LR is stack-allocated. LiveRegMatrix caches queries by a key that
304 // includes the address of the live range. If (for the same reg unit) this
305 // checkInterference overload is called twice, without any other query()
306 // calls in between (on heap-allocated LiveRanges) - which would invalidate
307 // the cached query - the LR address seen the second time may well be the
308 // same as that seen the first time, while the Start/End/valno may not - yet
309 // the same cached result would be fetched. To avoid that, we don't cache
310 // this query.
311 //
312 // FIXME: the usability of the Query API needs to be improved to avoid
313 // subtle bugs due to query identity. Avoiding caching, for example, would
314 // greatly simplify things.
315 LiveIntervalUnion::Query Q;
316 Q.reset(NewUserTag: UserTag, NewLR: LR, NewLiveUnion: Matrix[Unit]);
317 if (Q.checkInterference())
318 InterferingLanes |= Lanes;
319 }
320
321 return InterferingLanes;
322}
323
324Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
325 const LiveInterval *VRegInterval = nullptr;
326 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
327 if ((VRegInterval = Matrix[Unit].getOneVReg()))
328 return VRegInterval->reg();
329 }
330
331 return MCRegister::NoRegister;
332}
333
334#ifndef NDEBUG
335bool LiveRegMatrix::isValid() const {
336 // Build set of all valid LiveInterval pointers from LiveIntervals.
337 DenseSet<const LiveInterval *> ValidIntervals;
338 for (unsigned RegIdx = 0, NumRegs = VRM->getRegInfo().getNumVirtRegs();
339 RegIdx < NumRegs; ++RegIdx) {
340 Register VReg = Register::index2VirtReg(RegIdx);
341 // Only track assigned registers since unassigned ones won't be in Matrix
342 if (VRM->hasPhys(VReg) && LIS->hasInterval(VReg))
343 ValidIntervals.insert(&LIS->getInterval(VReg));
344 }
345
346 // Now scan all LiveIntervalUnions in the matrix and verify each pointer
347 unsigned NumDanglingPointers = 0;
348 for (unsigned I = 0, Size = Matrix.size(); I < Size; ++I) {
349 MCRegUnit Unit = static_cast<MCRegUnit>(I);
350 for (const LiveInterval *LI : Matrix[Unit]) {
351 if (!ValidIntervals.contains(LI)) {
352 ++NumDanglingPointers;
353 dbgs() << "ERROR: LiveInterval pointer is not found in LiveIntervals:\n"
354 << " Register Unit: " << printRegUnit(Unit, TRI) << '\n'
355 << " LiveInterval pointer: " << LI << '\n';
356 }
357 }
358 }
359
360 // Reverse check: every VRM-assigned vreg with a non-empty live interval
361 // must have its segments present in the Matrix for its assigned phys reg.
362 unsigned NumMissing = 0;
363 for (unsigned RegIdx = 0, NumRegs = VRM->getRegInfo().getNumVirtRegs();
364 RegIdx < NumRegs; ++RegIdx) {
365 Register VReg = Register::index2VirtReg(RegIdx);
366 if (!VRM->hasPhys(VReg) || !LIS->hasInterval(VReg))
367 continue;
368 const LiveInterval &LI = LIS->getInterval(VReg);
369 if (LI.empty())
370 continue;
371 MCRegister PhysReg = VRM->getPhys(VReg);
372 // Check that the first segment of LI is present in the LiveUnion for
373 // at least one reg unit of PhysReg.
374 SlotIndex FirstStart = LI.beginIndex();
375 bool Found = false;
376 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
377 auto It = Matrix[Unit].find(FirstStart);
378 if (It.valid() && It.start() == FirstStart && It.value() == &LI) {
379 Found = true;
380 break;
381 }
382 }
383 if (!Found) {
384 ++NumMissing;
385 dbgs() << "ERROR: VirtReg " << printReg(VReg, TRI) << " assigned to "
386 << printReg(PhysReg, TRI)
387 << " in VirtRegMap but not found in LiveRegMatrix\n";
388 dbgs() << " LiveInterval: " << LI << "\n";
389 dbgs() << " FirstStart: " << FirstStart << "\n";
390 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
391 dbgs() << " RegUnit " << printRegUnit(Unit, TRI) << " segments: ";
392 auto It = Matrix[Unit].find(FirstStart);
393 if (It.valid())
394 dbgs() << "[" << It.start() << "," << It.stop() << ") -> "
395 << printReg(It.value()->reg(), TRI);
396 else
397 dbgs() << "(none found)";
398 dbgs() << "\n";
399 }
400 }
401 }
402
403 return NumDanglingPointers == 0 && NumMissing == 0;
404}
405#endif
406
407AnalysisKey LiveRegMatrixAnalysis::Key;
408
409LiveRegMatrix LiveRegMatrixAnalysis::run(MachineFunction &MF,
410 MachineFunctionAnalysisManager &MFAM) {
411 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
412 auto &VRM = MFAM.getResult<VirtRegMapAnalysis>(IR&: MF);
413 LiveRegMatrix LRM;
414 LRM.init(MF, pLIS&: LIS, pVRM&: VRM);
415 return LRM;
416}
417