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