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