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
31 using namespace llvm;
32
33 #define DEBUG_TYPE "regalloc"
34
35 STATISTIC(NumAssigned , "Number of registers assigned");
36 STATISTIC(NumUnassigned , "Number of registers unassigned");
37
38 char LiveRegMatrixWrapperLegacy::ID = 0;
39 INITIALIZE_PASS_BEGIN(LiveRegMatrixWrapperLegacy, "liveregmatrix",
40 "Live Register Matrix", false, false)
INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)41 INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
42 INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)
43 INITIALIZE_PASS_END(LiveRegMatrixWrapperLegacy, "liveregmatrix",
44 "Live Register Matrix", false, true)
45
46 void LiveRegMatrixWrapperLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
47 AU.setPreservesAll();
48 AU.addRequiredTransitive<LiveIntervalsWrapperPass>();
49 AU.addRequiredTransitive<VirtRegMapWrapperLegacy>();
50 MachineFunctionPass::getAnalysisUsage(AU);
51 }
52
runOnMachineFunction(MachineFunction & MF)53 bool 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
init(MachineFunction & MF,LiveIntervals & pLIS,VirtRegMap & pVRM)60 void 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(new LiveIntervalUnion::Query[NumRegUnits]);
69 Matrix.init(*LIUAlloc, NumRegUnits);
70
71 // Make sure no stale queries get reused.
72 invalidateVirtRegs();
73 }
74
releaseMemory()75 void LiveRegMatrixWrapperLegacy::releaseMemory() { LRM.releaseMemory(); }
76
releaseMemory()77 void 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
86 template <typename Callable>
foreachUnit(const TargetRegisterInfo * TRI,const LiveInterval & VRegInterval,MCRegister PhysReg,Callable Func)87 static 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(PhysReg)) {
104 if (Func(Unit, VRegInterval))
105 return true;
106 }
107 }
108 return false;
109 }
110
assign(const LiveInterval & VirtReg,MCRegister PhysReg)111 void 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.reg(), PhysReg);
116
117 foreachUnit(
118 TRI, VirtReg, PhysReg, [&](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
unassign(const LiveInterval & VirtReg)128 void LiveRegMatrix::unassign(const LiveInterval &VirtReg) {
129 Register PhysReg = VRM->getPhys(VirtReg.reg());
130 LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI)
131 << " from " << printReg(PhysReg, TRI) << ':');
132 VRM->clearVirt(VirtReg.reg());
133
134 foreachUnit(TRI, VirtReg, PhysReg,
135 [&](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
isPhysRegUsed(MCRegister PhysReg) const145 bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const {
146 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
147 if (!Matrix[Unit].empty())
148 return true;
149 }
150 return false;
151 }
152
checkRegMaskInterference(const LiveInterval & VirtReg,MCRegister PhysReg)153 bool 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(VirtReg, 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(PhysReg.id()));
170 }
171
checkRegUnitInterference(const LiveInterval & VirtReg,MCRegister PhysReg)172 bool 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, VirtReg, PhysReg, [&](unsigned Unit,
179 const LiveRange &Range) {
180 const LiveRange &UnitRange = LIS->getRegUnit(Unit);
181 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
182 });
183 return Result;
184 }
185
query(const LiveRange & LR,MCRegUnit RegUnit)186 LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
187 MCRegUnit RegUnit) {
188 LiveIntervalUnion::Query &Q = Queries[RegUnit];
189 Q.init(UserTag, LR, Matrix[RegUnit]);
190 return Q;
191 }
192
193 LiveRegMatrix::InterferenceKind
checkInterference(const LiveInterval & VirtReg,MCRegister PhysReg)194 LiveRegMatrix::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, VirtReg, PhysReg,
209 [&](MCRegUnit Unit, const LiveRange &LR) {
210 return query(LR, Unit).checkInterference();
211 });
212 if (Interference)
213 return IK_VirtReg;
214
215 return IK_Free;
216 }
217
checkInterference(SlotIndex Start,SlotIndex End,MCRegister PhysReg)218 bool 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(Seg);
225
226 // Check for interference with that segment
227 for (MCRegUnit Unit : TRI->regunits(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(UserTag, LR, Matrix[Unit]);
242 if (Q.checkInterference())
243 return true;
244 }
245 return false;
246 }
247
checkInterferenceLanes(SlotIndex Start,SlotIndex End,MCRegister PhysReg)248 LaneBitmask 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(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(UserTag, LR, Matrix[Unit]);
276 if (Q.checkInterference())
277 InterferingLanes |= Lanes;
278 }
279
280 return InterferingLanes;
281 }
282
getOneVReg(unsigned PhysReg) const283 Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
284 const LiveInterval *VRegInterval = nullptr;
285 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
286 if ((VRegInterval = Matrix[Unit].getOneVReg()))
287 return VRegInterval->reg();
288 }
289
290 return MCRegister::NoRegister;
291 }
292
293 AnalysisKey LiveRegMatrixAnalysis::Key;
294
run(MachineFunction & MF,MachineFunctionAnalysisManager & MFAM)295 LiveRegMatrix LiveRegMatrixAnalysis::run(MachineFunction &MF,
296 MachineFunctionAnalysisManager &MFAM) {
297 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(MF);
298 auto &VRM = MFAM.getResult<VirtRegMapAnalysis>(MF);
299 LiveRegMatrix LRM;
300 LRM.init(MF, LIS, VRM);
301 return LRM;
302 }
303