1//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
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 implements the LiveVariable pass. For each machine instruction in
10// the function, this pass marks the registers that are immediately dead after
11// the instruction (i.e., the instruction calculates the value, but it is never
12// used). It does not compute kill flags or any queryable liveness information.
13//
14// A virtual register def is dead if the register has no reading uses. Physical
15// registers are assumed to only be live within a single basic block, and are
16// resolved with a local analysis of each block. This also adds implicit defs of
17// sub-registers and super-registers to model partially dead physical register
18// definitions. Reserved physical registers are not tracked.
19//
20//===----------------------------------------------------------------------===//
21
22#include "llvm/CodeGen/LiveVariables.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/CodeGen/MachineInstr.h"
26#include "llvm/CodeGen/MachineRegisterInfo.h"
27#include "llvm/CodeGen/Passes.h"
28#include "llvm/InitializePasses.h"
29#include "llvm/Support/ErrorHandling.h"
30using namespace llvm;
31
32AnalysisKey LiveVariablesAnalysis::Key;
33
34LiveVariablesAnalysis::Result
35LiveVariablesAnalysis::run(MachineFunction &MF,
36 MachineFunctionAnalysisManager &) {
37 return Result(MF);
38}
39
40char LiveVariablesWrapperPass::ID = 0;
41char &llvm::LiveVariablesID = LiveVariablesWrapperPass::ID;
42INITIALIZE_PASS_BEGIN(LiveVariablesWrapperPass, "livevars",
43 "Live Variable Analysis", false, false)
44INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElimLegacy)
45INITIALIZE_PASS_END(LiveVariablesWrapperPass, "livevars",
46 "Live Variable Analysis", false, false)
47
48void LiveVariablesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
49 AU.addRequiredID(ID&: UnreachableMachineBlockElimID);
50 AU.setPreservesAll();
51 MachineFunctionPass::getAnalysisUsage(AU);
52}
53
54LiveVariables::LiveVariables(MachineFunction &MF) { analyze(MF); }
55
56/// FindLastPartialDef - Return the last partial def of the specified register.
57MachineInstr *LiveVariables::FindLastPartialDef(Register Reg) {
58 unsigned LastDefDist = 0;
59 MachineInstr *LastDef = nullptr;
60 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
61 MachineInstr *Def = PhysRegDef[SubReg];
62 if (!Def)
63 continue;
64 unsigned Dist = DistanceMap[Def];
65 if (Dist > LastDefDist) {
66 LastDef = Def;
67 LastDefDist = Dist;
68 }
69 }
70
71 return LastDef;
72}
73
74/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
75/// implicit defs to a machine instruction if there was an earlier def of its
76/// super-register.
77void LiveVariables::HandlePhysRegUse(Register Reg, MachineInstr &MI) {
78 MachineInstr *LastDef = PhysRegDef[Reg.id()];
79 // If there was a previous use or a "full" def all is well.
80 if (!LastDef && !PhysRegUse[Reg.id()]) {
81 // Otherwise, the last sub-register def implicitly defines this register.
82 // e.g.
83 // AH =
84 // AL = ... implicit-def EAX, implicit killed AH
85 // = AH
86 // ...
87 // = EAX
88 // All of the sub-registers must have been defined before the use of Reg!
89 MachineInstr *LastPartialDef = FindLastPartialDef(Reg);
90 // If LastPartialDef is NULL, it must be using a livein register.
91 if (LastPartialDef) {
92 LastPartialDef->addOperand(
93 Op: MachineOperand::CreateReg(Reg, /*IsDef=*/isDef: true, /*IsImp=*/isImp: true));
94 }
95 } else if (LastDef && !PhysRegUse[Reg.id()] &&
96 !LastDef->findRegisterDefOperand(Reg, /*TRI=*/nullptr))
97 // Last def defines the super register, add an implicit def of reg.
98 LastDef->addOperand(Op: MachineOperand::CreateReg(Reg, isDef: true/*IsDef*/,
99 isImp: true/*IsImp*/));
100
101 // Remember this use.
102 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) {
103 PhysRegUse[SubReg] = &MI;
104 TrackedRegs.set(SubReg);
105 }
106}
107
108/// FindLastRefOrPartRef - Return the last reference or partial reference of
109/// the specified register.
110MachineInstr *LiveVariables::FindLastRefOrPartRef(Register Reg) {
111 MachineInstr *LastDef = PhysRegDef[Reg.id()];
112 MachineInstr *LastUse = PhysRegUse[Reg.id()];
113 if (!LastDef && !LastUse)
114 return nullptr;
115
116 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
117 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
118 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
119 MachineInstr *Def = PhysRegDef[SubReg];
120 if (Def && Def != LastDef)
121 continue;
122 if (MachineInstr *Use = PhysRegUse[SubReg]) {
123 unsigned Dist = DistanceMap[Use];
124 if (Dist > LastRefOrPartRefDist) {
125 LastRefOrPartRefDist = Dist;
126 LastRefOrPartRef = Use;
127 }
128 }
129 }
130
131 return LastRefOrPartRef;
132}
133
134void LiveVariables::HandlePhysRegKill(Register Reg, MachineInstr *MI) {
135 MachineInstr *LastDef = PhysRegDef[Reg.id()];
136 MachineInstr *LastUse = PhysRegUse[Reg.id()];
137 if (!LastDef && !LastUse)
138 return;
139
140 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
141 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
142 // The whole register is used.
143 // AL =
144 // AH =
145 //
146 // = AX
147 // = AL, implicit killed AX
148 // AX =
149 //
150 // Or whole register is defined, but not used at all.
151 // dead AX =
152 // ...
153 // AX =
154 //
155 // Or whole register is defined, but only partly used.
156 // dead AX = implicit-def AL
157 // = killed AL
158 // AX =
159 MachineInstr *LastPartDef = nullptr;
160 unsigned LastPartDefDist = 0;
161 SmallSet<unsigned, 8> PartUses;
162 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
163 MachineInstr *Def = PhysRegDef[SubReg];
164 if (Def && Def != LastDef) {
165 // There was a def of this sub-register in between. This is a partial
166 // def, keep track of the last one.
167 unsigned Dist = DistanceMap[Def];
168 if (Dist > LastPartDefDist) {
169 LastPartDefDist = Dist;
170 LastPartDef = Def;
171 }
172 continue;
173 }
174 if (MachineInstr *Use = PhysRegUse[SubReg]) {
175 PartUses.insert_range(R: TRI->subregs_inclusive(Reg: SubReg));
176 unsigned Dist = DistanceMap[Use];
177 if (Dist > LastRefOrPartRefDist) {
178 LastRefOrPartRefDist = Dist;
179 LastRefOrPartRef = Use;
180 }
181 }
182 }
183
184 if (!PhysRegUse[Reg.id()]) {
185 // Partial uses. Mark register def dead and add implicit def of
186 // sub-registers which are used.
187 // dead EAX = op implicit-def AL
188 // That is, EAX def is dead but AL def extends pass it.
189 PhysRegDef[Reg.id()]->addRegisterDead(Reg, RegInfo: TRI, AddIfNotFound: true);
190 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
191 if (!PartUses.count(V: SubReg))
192 continue;
193 bool NeedDef = true;
194 if (PhysRegDef[Reg.id()] == PhysRegDef[SubReg]) {
195 MachineOperand *MO = PhysRegDef[Reg.id()]->findRegisterDefOperand(
196 Reg: SubReg, /*TRI=*/nullptr);
197 if (MO) {
198 NeedDef = false;
199 assert(!MO->isDead());
200 }
201 }
202 if (NeedDef)
203 PhysRegDef[Reg.id()]->addOperand(
204 Op: MachineOperand::CreateReg(Reg: SubReg, isDef: true /*IsDef*/, isImp: true /*IsImp*/));
205 if (!FindLastRefOrPartRef(Reg: SubReg)) {
206 for (MCPhysReg SS : TRI->subregs_inclusive(Reg: SubReg)) {
207 PhysRegUse[SS] = LastRefOrPartRef;
208 TrackedRegs.set(SS);
209 }
210 }
211 for (MCPhysReg SS : TRI->subregs(Reg: SubReg))
212 PartUses.erase(V: SS);
213 }
214 } else if (LastRefOrPartRef == PhysRegDef[Reg.id()] &&
215 LastRefOrPartRef != MI && !LastPartDef) {
216 MachineOperand *MO =
217 LastRefOrPartRef->findRegisterDefOperand(Reg, TRI, isDead: false, Overlap: false);
218 bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
219 // If the last reference is the last def, then it's not used at all.
220 // That is, unless we are currently processing the last reference itself.
221 LastRefOrPartRef->addRegisterDead(Reg, RegInfo: TRI, AddIfNotFound: true);
222 if (NeedEC) {
223 // If we are adding a subreg def and the superreg def is marked early
224 // clobber, add an early clobber marker to the subreg def.
225 MO = LastRefOrPartRef->findRegisterDefOperand(Reg, /*TRI=*/nullptr);
226 if (MO)
227 MO->setIsEarlyClobber();
228 }
229 }
230}
231
232void LiveVariables::HandleRegMask(const MachineOperand &MO, unsigned NumRegs) {
233 // Call HandlePhysRegKill() for all live registers clobbered by Mask.
234 // Clobbered registers are always dead, sp there is no need to use
235 // HandlePhysRegDef().
236 for (unsigned Reg : TrackedRegs.set_bits()) {
237 // Skip dead regs.
238 if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
239 continue;
240 // Skip mask-preserved regs.
241 if (!MO.clobbersPhysReg(PhysReg: Reg))
242 continue;
243 // Kill the largest clobbered super-register.
244 // This avoids needless implicit operands.
245 unsigned Super = Reg;
246 for (MCPhysReg SR : TRI->superregs(Reg))
247 if (SR < NumRegs && (PhysRegDef[SR] || PhysRegUse[SR]) &&
248 MO.clobbersPhysReg(PhysReg: SR))
249 Super = SR;
250 HandlePhysRegKill(Reg: Super, MI: nullptr);
251 }
252}
253
254void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI) {
255 // What parts of the register are previously defined?
256 SmallSet<unsigned, 32> Live;
257 if (PhysRegDef[Reg.id()] || PhysRegUse[Reg.id()]) {
258 Live.insert_range(R: TRI->subregs_inclusive(Reg));
259 } else {
260 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
261 // If a register isn't itself defined, but all parts that make up of it
262 // are defined, then consider it also defined.
263 // e.g.
264 // AL =
265 // AH =
266 // = AX
267 if (Live.count(V: SubReg))
268 continue;
269 if (PhysRegDef[SubReg] || PhysRegUse[SubReg])
270 Live.insert_range(R: TRI->subregs_inclusive(Reg: SubReg));
271 }
272 }
273
274 // Start from the largest piece, find the last time any part of the register
275 // is referenced.
276 HandlePhysRegKill(Reg, MI);
277 // Only some of the sub-registers are used.
278 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
279 if (!Live.count(V: SubReg))
280 // Skip if this sub-register isn't defined.
281 continue;
282 HandlePhysRegKill(Reg: SubReg, MI);
283 }
284}
285
286void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
287 ArrayRef<Register> Defs) {
288 for (Register Reg : Defs) {
289 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) {
290 PhysRegDef[SubReg] = &MI;
291 PhysRegUse[SubReg] = nullptr;
292 TrackedRegs.set(SubReg);
293 }
294 }
295}
296
297void LiveVariables::runOnInstr(MachineInstr &MI, unsigned NumRegs) {
298 assert(!MI.isDebugOrPseudoInstr());
299
300 // Clear dead markers. LV will recompute them.
301 SmallVector<Register, 4> UseRegs;
302 SmallVector<Register, 4> DefRegs;
303 SmallVector<unsigned, 1> RegMasks;
304 for (auto [I, MO] : enumerate(First: MI.operands())) {
305 if (MO.isRegMask()) {
306 RegMasks.push_back(Elt: I);
307 continue;
308 }
309 if (!MO.isReg())
310 continue;
311 Register MOReg = MO.getReg();
312 if (!MOReg.isPhysical() || MRI->isReserved(PhysReg: MOReg))
313 continue;
314 if (MO.isUse()) {
315 if (MO.readsReg())
316 UseRegs.push_back(Elt: MOReg);
317 } else {
318 // FIXME: We should not remove any dead flags. However the MIPS RDDSP
319 // instruction needs it at the moment: http://llvm.org/PR27116.
320 MO.setIsDead(false);
321 DefRegs.push_back(Elt: MOReg);
322 }
323 }
324
325 // Process all uses.
326 for (Register MOReg : UseRegs)
327 HandlePhysRegUse(Reg: MOReg, MI);
328
329 // Process all masked registers. (Call clobbers).
330 for (unsigned Mask : RegMasks)
331 HandleRegMask(MO: MI.getOperand(i: Mask), NumRegs);
332
333 // Process all defs.
334 for (Register MOReg : DefRegs)
335 HandlePhysRegDef(Reg: MOReg, MI: &MI);
336 UpdatePhysRegDefs(MI, Defs: DefRegs);
337}
338
339void LiveVariables::runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs) {
340 // Loop over all of the instructions, processing them.
341 DistanceMap.clear();
342 unsigned Dist = 0;
343 for (MachineInstr &MI : *MBB) {
344 if (MI.isDebugOrPseudoInstr())
345 continue;
346 DistanceMap.insert(KV: std::make_pair(x: &MI, y: Dist++));
347
348 runOnInstr(MI, NumRegs);
349 }
350
351 // MachineCSE may CSE instructions which write to non-allocatable physical
352 // registers across MBBs. Remember if any reserved register is liveout.
353 SmallSet<MCRegister, 4> LiveOuts;
354 for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
355 if (SuccMBB->isEHPad())
356 continue;
357 for (const auto &LI : SuccMBB->liveins()) {
358 if (!TRI->isInAllocatableClass(RegNo: LI.PhysReg))
359 // Ignore other live-ins, e.g. those that are live into landing pads.
360 LiveOuts.insert(V: LI.PhysReg);
361 }
362 }
363
364 // Loop over PhysRegDef / PhysRegUse, killing any registers that are
365 // available at the end of the basic block.
366 for (unsigned Reg : TrackedRegs.set_bits())
367 if ((PhysRegDef[Reg] || PhysRegUse[Reg]) && !LiveOuts.count(V: Reg))
368 HandlePhysRegDef(Reg, MI: nullptr);
369}
370
371void LiveVariables::analyze(MachineFunction &mf) {
372 MRI = &mf.getRegInfo();
373 TRI = mf.getSubtarget().getRegisterInfo();
374
375 // FIXME: LiveIntervals will be updated to remove its dependence on
376 // LiveVariables to improve compilation time and eliminate bizarre pass
377 // dependencies. Until then, we can't change much in -O0.
378 if (!MRI->isSSA())
379 reportFatalUsageError(reason: "regalloc=... not currently supported with -O0");
380
381 const unsigned NumRegs = TRI->getNumSupportedRegs(mf);
382 PhysRegDef.assign(n: NumRegs, val: nullptr);
383 PhysRegUse.assign(n: NumRegs, val: nullptr);
384 TrackedRegs.clear();
385 TrackedRegs.resize(N: NumRegs);
386
387 for (MachineBasicBlock &MBB : mf) {
388 runOnBlock(MBB: &MBB, NumRegs);
389
390 for (unsigned Reg : TrackedRegs.set_bits()) {
391 PhysRegDef[Reg] = nullptr;
392 PhysRegUse[Reg] = nullptr;
393 }
394 TrackedRegs.reset();
395 }
396
397 for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) {
398 Register Reg = Register::index2VirtReg(Index: I);
399 MachineInstr *Def = MRI->getVRegDef(Reg);
400 if (Def && none_of(Range: MRI->use_nodbg_operands(Reg),
401 P: [](const MachineOperand &MO) { return MO.readsReg(); }))
402 Def->addRegisterDead(Reg, RegInfo: TRI);
403 }
404
405 PhysRegDef.clear();
406 PhysRegUse.clear();
407 TrackedRegs.clear();
408}
409