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