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 analysis pass. For each machine
10// instruction in the function, this pass calculates the set of registers that
11// are immediately dead after the instruction (i.e., the instruction calculates
12// the value, but it is never used) and the set of registers that are used by
13// the instruction, but are never used after the instruction (i.e., they are
14// killed).
15//
16// This class computes live variables using a sparse implementation based on
17// the machine code SSA form. This class computes live variable information for
18// each virtual and _register allocatable_ physical register in a function. It
19// uses the dominance properties of SSA form to efficiently compute live
20// variables for virtual registers, and assumes that physical registers are only
21// live within a single basic block (allowing it to do a single local analysis
22// to resolve physical register lifetimes in each basic block). If a physical
23// register is not register allocatable, it is not tracked. This is useful for
24// things like the stack pointer and condition codes.
25//
26//===----------------------------------------------------------------------===//
27
28#include "llvm/CodeGen/LiveVariables.h"
29#include "llvm/ADT/DenseSet.h"
30#include "llvm/ADT/DepthFirstIterator.h"
31#include "llvm/ADT/STLExtras.h"
32#include "llvm/ADT/SmallPtrSet.h"
33#include "llvm/ADT/SmallSet.h"
34#include "llvm/CodeGen/MachineInstr.h"
35#include "llvm/CodeGen/MachineRegisterInfo.h"
36#include "llvm/CodeGen/Passes.h"
37#include "llvm/Config/llvm-config.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/ErrorHandling.h"
40#include "llvm/Support/raw_ostream.h"
41using namespace llvm;
42
43AnalysisKey LiveVariablesAnalysis::Key;
44
45LiveVariablesAnalysis::Result
46LiveVariablesAnalysis::run(MachineFunction &MF,
47 MachineFunctionAnalysisManager &) {
48 return Result(MF);
49}
50
51PreservedAnalyses
52LiveVariablesPrinterPass::run(MachineFunction &MF,
53 MachineFunctionAnalysisManager &MFAM) {
54 OS << "Live variables in machine function: " << MF.getName() << '\n';
55 MFAM.getResult<LiveVariablesAnalysis>(IR&: MF).print(OS);
56 return PreservedAnalyses::all();
57}
58
59char LiveVariablesWrapperPass::ID = 0;
60char &llvm::LiveVariablesID = LiveVariablesWrapperPass::ID;
61INITIALIZE_PASS_BEGIN(LiveVariablesWrapperPass, "livevars",
62 "Live Variable Analysis", false, false)
63INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElimLegacy)
64INITIALIZE_PASS_END(LiveVariablesWrapperPass, "livevars",
65 "Live Variable Analysis", false, false)
66
67void LiveVariablesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
68 AU.addRequiredID(ID&: UnreachableMachineBlockElimID);
69 AU.setPreservesAll();
70 MachineFunctionPass::getAnalysisUsage(AU);
71}
72
73LiveVariables::LiveVariables(MachineFunction &MF)
74 : MF(&MF), MRI(&MF.getRegInfo()), TRI(MF.getSubtarget().getRegisterInfo()) {
75 analyze(MF);
76}
77
78void LiveVariables::print(raw_ostream &OS) const {
79 for (size_t I = 0, E = VirtRegInfo.size(); I != E; ++I) {
80 const Register Reg = Register::index2VirtReg(Index: I);
81 OS << "Virtual register '%" << I << "':\n";
82 VirtRegInfo[Reg].print(OS);
83 }
84}
85
86MachineInstr *
87LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const {
88 for (MachineInstr *MI : Kills)
89 if (MI->getParent() == MBB)
90 return MI;
91 return nullptr;
92}
93
94void LiveVariables::VarInfo::print(raw_ostream &OS) const {
95 OS << " Alive in blocks: ";
96 for (unsigned AB : AliveBlocks)
97 OS << AB << ", ";
98 OS << "\n Killed by:";
99 if (Kills.empty())
100 OS << " No instructions.\n\n";
101 else {
102 for (unsigned i = 0, e = Kills.size(); i != e; ++i)
103 OS << "\n #" << i << ": " << *Kills[i];
104 OS << "\n";
105 }
106}
107
108#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
109LLVM_DUMP_METHOD void LiveVariables::VarInfo::dump() const { print(dbgs()); }
110#endif
111
112/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
113LiveVariables::VarInfo &LiveVariables::getVarInfo(Register Reg) {
114 assert(Reg.isVirtual() && "getVarInfo: not a virtual register!");
115 VirtRegInfo.grow(n: Reg);
116 return VirtRegInfo[Reg];
117}
118
119void LiveVariables::MarkVirtRegAliveInBlock(
120 VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *MBB,
121 SmallVectorImpl<MachineBasicBlock *> &WorkList) {
122 unsigned BBNum = MBB->getNumber();
123
124 // Check to see if this basic block is one of the killing blocks. If so,
125 // remove it.
126 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
127 if (VRInfo.Kills[i]->getParent() == MBB) {
128 VRInfo.Kills.erase(position: VRInfo.Kills.begin()+i); // Erase entry
129 break;
130 }
131
132 if (MBB == DefBlock) return; // Terminate recursion
133
134 if (VRInfo.AliveBlocks.test(Idx: BBNum))
135 return; // We already know the block is live
136
137 // Mark the variable known alive in this bb
138 VRInfo.AliveBlocks.set(BBNum);
139
140 assert(MBB != &MF->front() && "Can't find reaching def for virtreg");
141 WorkList.insert(I: WorkList.end(), From: MBB->pred_rbegin(), To: MBB->pred_rend());
142}
143
144void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
145 MachineBasicBlock *DefBlock,
146 MachineBasicBlock *MBB) {
147 SmallVector<MachineBasicBlock *, 16> WorkList;
148 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
149
150 while (!WorkList.empty()) {
151 MachineBasicBlock *Pred = WorkList.pop_back_val();
152 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB: Pred, WorkList);
153 }
154}
155
156void LiveVariables::HandleVirtRegUse(Register Reg, MachineBasicBlock *MBB,
157 MachineInstr &MI) {
158 assert(MRI->getVRegDef(Reg) && "Register use before def!");
159
160 unsigned BBNum = MBB->getNumber();
161
162 VarInfo &VRInfo = getVarInfo(Reg);
163
164 // Check to see if this basic block is already a kill block.
165 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
166 // Yes, this register is killed in this basic block already. Increase the
167 // live range by updating the kill instruction.
168 VRInfo.Kills.back() = &MI;
169 return;
170 }
171
172#ifndef NDEBUG
173 for (MachineInstr *Kill : VRInfo.Kills)
174 assert(Kill->getParent() != MBB && "entry should be at end!");
175#endif
176
177 // This situation can occur:
178 //
179 // ,------.
180 // | |
181 // | v
182 // | t2 = phi ... t1 ...
183 // | |
184 // | v
185 // | t1 = ...
186 // | ... = ... t1 ...
187 // | |
188 // `------'
189 //
190 // where there is a use in a PHI node that's a predecessor to the defining
191 // block. We don't want to mark all predecessors as having the value "alive"
192 // in this case.
193 if (MBB == MRI->getVRegDef(Reg)->getParent())
194 return;
195
196 // Add a new kill entry for this basic block. If this virtual register is
197 // already marked as alive in this basic block, that means it is alive in at
198 // least one of the successor blocks, it's not a kill.
199 if (!VRInfo.AliveBlocks.test(Idx: BBNum))
200 VRInfo.Kills.push_back(x: &MI);
201
202 // Update all dominating blocks to mark them as "known live".
203 for (MachineBasicBlock *Pred : MBB->predecessors())
204 MarkVirtRegAliveInBlock(VRInfo, DefBlock: MRI->getVRegDef(Reg)->getParent(), MBB: Pred);
205}
206
207void LiveVariables::HandleVirtRegDef(Register Reg, MachineInstr &MI) {
208 VarInfo &VRInfo = getVarInfo(Reg);
209
210 if (VRInfo.AliveBlocks.empty())
211 // If vr is not alive in any block, then defaults to dead.
212 VRInfo.Kills.push_back(x: &MI);
213}
214
215/// FindLastPartialDef - Return the last partial def of the specified register.
216/// Also returns the sub-registers that're defined by the instruction.
217MachineInstr *
218LiveVariables::FindLastPartialDef(Register Reg,
219 SmallSet<Register, 4> &PartDefRegs) {
220 Register LastDefReg = 0;
221 unsigned LastDefDist = 0;
222 MachineInstr *LastDef = nullptr;
223 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
224 MachineInstr *Def = PhysRegDef[SubReg];
225 if (!Def)
226 continue;
227 unsigned Dist = DistanceMap[Def];
228 if (Dist > LastDefDist) {
229 LastDefReg = SubReg;
230 LastDef = Def;
231 LastDefDist = Dist;
232 }
233 }
234
235 if (!LastDef)
236 return nullptr;
237
238 PartDefRegs.insert(V: LastDefReg);
239 for (MachineOperand &MO : LastDef->all_defs()) {
240 if (MO.getReg() == 0)
241 continue;
242 Register DefReg = MO.getReg();
243 if (TRI->isSubRegister(RegA: Reg, RegB: DefReg))
244 PartDefRegs.insert_range(R: TRI->subregs_inclusive(Reg: DefReg));
245 }
246 return LastDef;
247}
248
249/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
250/// implicit defs to a machine instruction if there was an earlier def of its
251/// super-register.
252void LiveVariables::HandlePhysRegUse(Register Reg, MachineInstr &MI) {
253 MachineInstr *LastDef = PhysRegDef[Reg.id()];
254 // If there was a previous use or a "full" def all is well.
255 if (!LastDef && !PhysRegUse[Reg.id()]) {
256 // Otherwise, the last sub-register def implicitly defines this register.
257 // e.g.
258 // AH =
259 // AL = ... implicit-def EAX, implicit killed AH
260 // = AH
261 // ...
262 // = EAX
263 // All of the sub-registers must have been defined before the use of Reg!
264 SmallSet<Register, 4> PartDefRegs;
265 MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
266 // If LastPartialDef is NULL, it must be using a livein register.
267 if (LastPartialDef) {
268 LastPartialDef->addOperand(Op: MachineOperand::CreateReg(Reg, isDef: true/*IsDef*/,
269 isImp: true/*IsImp*/));
270 PhysRegDef[Reg.id()] = LastPartialDef;
271 SmallSet<MCPhysReg, 8> Processed;
272 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
273 if (Processed.count(V: SubReg))
274 continue;
275 if (PartDefRegs.count(V: SubReg))
276 continue;
277 // This part of Reg was defined before the last partial def. It's killed
278 // here.
279 LastPartialDef->addOperand(Op: MachineOperand::CreateReg(Reg: SubReg,
280 isDef: false/*IsDef*/,
281 isImp: true/*IsImp*/));
282 PhysRegDef[SubReg] = LastPartialDef;
283 Processed.insert_range(R: TRI->subregs(Reg: SubReg));
284 }
285 }
286 } else if (LastDef && !PhysRegUse[Reg.id()] &&
287 !LastDef->findRegisterDefOperand(Reg, /*TRI=*/nullptr))
288 // Last def defines the super register, add an implicit def of reg.
289 LastDef->addOperand(Op: MachineOperand::CreateReg(Reg, isDef: true/*IsDef*/,
290 isImp: true/*IsImp*/));
291
292 // Remember this use.
293 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
294 PhysRegUse[SubReg] = &MI;
295}
296
297/// FindLastRefOrPartRef - Return the last reference or partial reference of
298/// the specified register.
299MachineInstr *LiveVariables::FindLastRefOrPartRef(Register Reg) {
300 MachineInstr *LastDef = PhysRegDef[Reg.id()];
301 MachineInstr *LastUse = PhysRegUse[Reg.id()];
302 if (!LastDef && !LastUse)
303 return nullptr;
304
305 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
306 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
307 unsigned LastPartDefDist = 0;
308 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
309 MachineInstr *Def = PhysRegDef[SubReg];
310 if (Def && Def != LastDef) {
311 // There was a def of this sub-register in between. This is a partial
312 // def, keep track of the last one.
313 unsigned Dist = DistanceMap[Def];
314 if (Dist > LastPartDefDist)
315 LastPartDefDist = Dist;
316 } else if (MachineInstr *Use = PhysRegUse[SubReg]) {
317 unsigned Dist = DistanceMap[Use];
318 if (Dist > LastRefOrPartRefDist) {
319 LastRefOrPartRefDist = Dist;
320 LastRefOrPartRef = Use;
321 }
322 }
323 }
324
325 return LastRefOrPartRef;
326}
327
328bool LiveVariables::HandlePhysRegKill(Register Reg, MachineInstr *MI) {
329 MachineInstr *LastDef = PhysRegDef[Reg.id()];
330 MachineInstr *LastUse = PhysRegUse[Reg.id()];
331 if (!LastDef && !LastUse)
332 return false;
333
334 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
335 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
336 // The whole register is used.
337 // AL =
338 // AH =
339 //
340 // = AX
341 // = AL, implicit killed AX
342 // AX =
343 //
344 // Or whole register is defined, but not used at all.
345 // dead AX =
346 // ...
347 // AX =
348 //
349 // Or whole register is defined, but only partly used.
350 // dead AX = implicit-def AL
351 // = killed AL
352 // AX =
353 MachineInstr *LastPartDef = nullptr;
354 unsigned LastPartDefDist = 0;
355 SmallSet<unsigned, 8> PartUses;
356 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
357 MachineInstr *Def = PhysRegDef[SubReg];
358 if (Def && Def != LastDef) {
359 // There was a def of this sub-register in between. This is a partial
360 // def, keep track of the last one.
361 unsigned Dist = DistanceMap[Def];
362 if (Dist > LastPartDefDist) {
363 LastPartDefDist = Dist;
364 LastPartDef = Def;
365 }
366 continue;
367 }
368 if (MachineInstr *Use = PhysRegUse[SubReg]) {
369 PartUses.insert_range(R: TRI->subregs_inclusive(Reg: SubReg));
370 unsigned Dist = DistanceMap[Use];
371 if (Dist > LastRefOrPartRefDist) {
372 LastRefOrPartRefDist = Dist;
373 LastRefOrPartRef = Use;
374 }
375 }
376 }
377
378 if (!PhysRegUse[Reg.id()]) {
379 // Partial uses. Mark register def dead and add implicit def of
380 // sub-registers which are used.
381 // dead EAX = op implicit-def AL
382 // That is, EAX def is dead but AL def extends pass it.
383 PhysRegDef[Reg.id()]->addRegisterDead(Reg, RegInfo: TRI, AddIfNotFound: true);
384 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
385 if (!PartUses.count(V: SubReg))
386 continue;
387 bool NeedDef = true;
388 if (PhysRegDef[Reg.id()] == PhysRegDef[SubReg]) {
389 MachineOperand *MO = PhysRegDef[Reg.id()]->findRegisterDefOperand(
390 Reg: SubReg, /*TRI=*/nullptr);
391 if (MO) {
392 NeedDef = false;
393 assert(!MO->isDead());
394 }
395 }
396 if (NeedDef)
397 PhysRegDef[Reg.id()]->addOperand(
398 Op: MachineOperand::CreateReg(Reg: SubReg, isDef: true /*IsDef*/, isImp: true /*IsImp*/));
399 MachineInstr *LastSubRef = FindLastRefOrPartRef(Reg: SubReg);
400 if (LastSubRef)
401 LastSubRef->addRegisterKilled(IncomingReg: SubReg, RegInfo: TRI, AddIfNotFound: true);
402 else {
403 LastRefOrPartRef->addRegisterKilled(IncomingReg: SubReg, RegInfo: TRI, AddIfNotFound: true);
404 for (MCPhysReg SS : TRI->subregs_inclusive(Reg: SubReg))
405 PhysRegUse[SS] = LastRefOrPartRef;
406 }
407 for (MCPhysReg SS : TRI->subregs(Reg: SubReg))
408 PartUses.erase(V: SS);
409 }
410 } else if (LastRefOrPartRef == PhysRegDef[Reg.id()] &&
411 LastRefOrPartRef != MI) {
412 if (LastPartDef)
413 // The last partial def kills the register.
414 LastPartDef->addOperand(Op: MachineOperand::CreateReg(Reg, isDef: false/*IsDef*/,
415 isImp: true/*IsImp*/, isKill: true/*IsKill*/));
416 else {
417 MachineOperand *MO =
418 LastRefOrPartRef->findRegisterDefOperand(Reg, TRI, isDead: false, Overlap: false);
419 bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
420 // If the last reference is the last def, then it's not used at all.
421 // That is, unless we are currently processing the last reference itself.
422 LastRefOrPartRef->addRegisterDead(Reg, RegInfo: TRI, AddIfNotFound: true);
423 if (NeedEC) {
424 // If we are adding a subreg def and the superreg def is marked early
425 // clobber, add an early clobber marker to the subreg def.
426 MO = LastRefOrPartRef->findRegisterDefOperand(Reg, /*TRI=*/nullptr);
427 if (MO)
428 MO->setIsEarlyClobber();
429 }
430 }
431 } else
432 LastRefOrPartRef->addRegisterKilled(IncomingReg: Reg, RegInfo: TRI, AddIfNotFound: true);
433 return true;
434}
435
436void LiveVariables::HandleRegMask(const MachineOperand &MO, unsigned NumRegs) {
437 // Call HandlePhysRegKill() for all live registers clobbered by Mask.
438 // Clobbered registers are always dead, sp there is no need to use
439 // HandlePhysRegDef().
440 for (unsigned Reg = 1; Reg != NumRegs; ++Reg) {
441 // Skip dead regs.
442 if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
443 continue;
444 // Skip mask-preserved regs.
445 if (!MO.clobbersPhysReg(PhysReg: Reg))
446 continue;
447 // Kill the largest clobbered super-register.
448 // This avoids needless implicit operands.
449 unsigned Super = Reg;
450 for (MCPhysReg SR : TRI->superregs(Reg))
451 if (SR < NumRegs && (PhysRegDef[SR] || PhysRegUse[SR]) &&
452 MO.clobbersPhysReg(PhysReg: SR))
453 Super = SR;
454 HandlePhysRegKill(Reg: Super, MI: nullptr);
455 }
456}
457
458void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI,
459 SmallVectorImpl<Register> &Defs) {
460 // What parts of the register are previously defined?
461 SmallSet<unsigned, 32> Live;
462 if (PhysRegDef[Reg.id()] || PhysRegUse[Reg.id()]) {
463 Live.insert_range(R: TRI->subregs_inclusive(Reg));
464 } else {
465 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
466 // If a register isn't itself defined, but all parts that make up of it
467 // are defined, then consider it also defined.
468 // e.g.
469 // AL =
470 // AH =
471 // = AX
472 if (Live.count(V: SubReg))
473 continue;
474 if (PhysRegDef[SubReg] || PhysRegUse[SubReg])
475 Live.insert_range(R: TRI->subregs_inclusive(Reg: SubReg));
476 }
477 }
478
479 // Start from the largest piece, find the last time any part of the register
480 // is referenced.
481 HandlePhysRegKill(Reg, MI);
482 // Only some of the sub-registers are used.
483 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
484 if (!Live.count(V: SubReg))
485 // Skip if this sub-register isn't defined.
486 continue;
487 HandlePhysRegKill(Reg: SubReg, MI);
488 }
489
490 if (MI)
491 Defs.push_back(Elt: Reg); // Remember this def.
492}
493
494void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
495 SmallVectorImpl<Register> &Defs) {
496 while (!Defs.empty()) {
497 Register Reg = Defs.pop_back_val();
498 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) {
499 PhysRegDef[SubReg] = &MI;
500 PhysRegUse[SubReg] = nullptr;
501 }
502 }
503}
504
505void LiveVariables::runOnInstr(MachineInstr &MI,
506 SmallVectorImpl<Register> &Defs,
507 unsigned NumRegs) {
508 assert(!MI.isDebugOrPseudoInstr());
509 // Process all of the operands of the instruction...
510 unsigned NumOperandsToProcess = MI.getNumOperands();
511
512 // Unless it is a PHI node. In this case, ONLY process the DEF, not any
513 // of the uses. They will be handled in other basic blocks.
514 if (MI.isPHI())
515 NumOperandsToProcess = 1;
516
517 // Clear kill and dead markers. LV will recompute them.
518 SmallVector<Register, 4> UseRegs;
519 SmallVector<Register, 4> DefRegs;
520 SmallVector<unsigned, 1> RegMasks;
521 for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
522 MachineOperand &MO = MI.getOperand(i);
523 if (MO.isRegMask()) {
524 RegMasks.push_back(Elt: i);
525 continue;
526 }
527 if (!MO.isReg() || !MO.getReg())
528 continue;
529 Register MOReg = MO.getReg();
530 if (MO.isUse()) {
531 if (!(MOReg.isPhysical() && MRI->isReserved(PhysReg: MOReg)))
532 MO.setIsKill(false);
533 if (MO.readsReg())
534 UseRegs.push_back(Elt: MOReg);
535 } else {
536 assert(MO.isDef());
537 // FIXME: We should not remove any dead flags. However the MIPS RDDSP
538 // instruction needs it at the moment: http://llvm.org/PR27116.
539 if (MOReg.isPhysical() && !MRI->isReserved(PhysReg: MOReg))
540 MO.setIsDead(false);
541 DefRegs.push_back(Elt: MOReg);
542 }
543 }
544
545 MachineBasicBlock *MBB = MI.getParent();
546 // Process all uses.
547 for (Register MOReg : UseRegs) {
548 if (MOReg.isVirtual())
549 HandleVirtRegUse(Reg: MOReg, MBB, MI);
550 else if (!MRI->isReserved(PhysReg: MOReg))
551 HandlePhysRegUse(Reg: MOReg, MI);
552 }
553
554 // Process all masked registers. (Call clobbers).
555 for (unsigned Mask : RegMasks)
556 HandleRegMask(MO: MI.getOperand(i: Mask), NumRegs);
557
558 // Process all defs.
559 for (Register MOReg : DefRegs) {
560 if (MOReg.isVirtual())
561 HandleVirtRegDef(Reg: MOReg, MI);
562 else if (!MRI->isReserved(PhysReg: MOReg))
563 HandlePhysRegDef(Reg: MOReg, MI: &MI, Defs);
564 }
565 UpdatePhysRegDefs(MI, Defs);
566}
567
568void LiveVariables::runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs) {
569 // Mark live-in registers as live-in.
570 SmallVector<Register, 4> Defs;
571 for (const auto &LI : MBB->liveins()) {
572 assert(LI.PhysReg.isPhysical() &&
573 "Cannot have a live-in virtual register!");
574 HandlePhysRegDef(Reg: LI.PhysReg, MI: nullptr, Defs);
575 }
576
577 // Loop over all of the instructions, processing them.
578 DistanceMap.clear();
579 unsigned Dist = 0;
580 for (MachineInstr &MI : *MBB) {
581 if (MI.isDebugOrPseudoInstr())
582 continue;
583 DistanceMap.insert(KV: std::make_pair(x: &MI, y: Dist++));
584
585 runOnInstr(MI, Defs, NumRegs);
586 }
587
588 // Handle any virtual assignments from PHI nodes which might be at the
589 // bottom of this basic block. We check all of our successor blocks to see
590 // if they have PHI nodes, and if so, we simulate an assignment at the end
591 // of the current block.
592 if (!PHIVarInfo[MBB->getNumber()].empty()) {
593 SmallVectorImpl<Register> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
594
595 for (Register I : VarInfoVec)
596 // Mark it alive only in the block we are representing.
597 MarkVirtRegAliveInBlock(VRInfo&: getVarInfo(Reg: I), DefBlock: MRI->getVRegDef(Reg: I)->getParent(),
598 MBB);
599 }
600
601 // MachineCSE may CSE instructions which write to non-allocatable physical
602 // registers across MBBs. Remember if any reserved register is liveout.
603 SmallSet<unsigned, 4> LiveOuts;
604 for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
605 if (SuccMBB->isEHPad())
606 continue;
607 for (const auto &LI : SuccMBB->liveins()) {
608 if (!TRI->isInAllocatableClass(RegNo: LI.PhysReg))
609 // Ignore other live-ins, e.g. those that are live into landing pads.
610 LiveOuts.insert(V: LI.PhysReg);
611 }
612 }
613
614 // Loop over PhysRegDef / PhysRegUse, killing any registers that are
615 // available at the end of the basic block.
616 for (unsigned i = 0; i != NumRegs; ++i)
617 if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(V: i))
618 HandlePhysRegDef(Reg: i, MI: nullptr, Defs);
619}
620
621void LiveVariables::analyze(MachineFunction &mf) {
622 MF = &mf;
623 MRI = &mf.getRegInfo();
624 TRI = MF->getSubtarget().getRegisterInfo();
625
626 const unsigned NumRegs = TRI->getNumSupportedRegs(mf);
627 PhysRegDef.assign(n: NumRegs, val: nullptr);
628 PhysRegUse.assign(n: NumRegs, val: nullptr);
629 PHIVarInfo.resize(new_size: MF->getNumBlockIDs());
630
631 // FIXME: LiveIntervals will be updated to remove its dependence on
632 // LiveVariables to improve compilation time and eliminate bizarre pass
633 // dependencies. Until then, we can't change much in -O0.
634 if (!MRI->isSSA())
635 reportFatalUsageError(reason: "regalloc=... not currently supported with -O0");
636
637 analyzePHINodes(Fn: mf);
638
639 // Calculate live variable information in depth first order on the CFG of the
640 // function. This guarantees that we will see the definition of a virtual
641 // register before its uses due to dominance properties of SSA (except for PHI
642 // nodes, which are treated as a special case).
643 MachineBasicBlock *Entry = &MF->front();
644 df_iterator_default_set<MachineBasicBlock*,16> Visited;
645
646 for (MachineBasicBlock *MBB : depth_first_ext(G: Entry, S&: Visited)) {
647 runOnBlock(MBB, NumRegs);
648
649 PhysRegDef.assign(n: NumRegs, val: nullptr);
650 PhysRegUse.assign(n: NumRegs, val: nullptr);
651 }
652
653 // Convert and transfer the dead / killed information we have gathered into
654 // VirtRegInfo onto MI's.
655 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) {
656 const Register Reg = Register::index2VirtReg(Index: i);
657 for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
658 if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
659 VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, RegInfo: TRI);
660 else
661 VirtRegInfo[Reg].Kills[j]->addRegisterKilled(IncomingReg: Reg, RegInfo: TRI);
662 }
663
664 // Check to make sure there are no unreachable blocks in the MC CFG for the
665 // function. If so, it is due to a bug in the instruction selector or some
666 // other part of the code generator if this happens.
667#ifndef NDEBUG
668 for (const MachineBasicBlock &MBB : *MF)
669 assert(Visited.contains(&MBB) && "unreachable basic block found");
670#endif
671
672 PhysRegDef.clear();
673 PhysRegUse.clear();
674 PHIVarInfo.clear();
675}
676
677void LiveVariables::recomputeForSingleDefVirtReg(Register Reg) {
678 assert(Reg.isVirtual());
679
680 VarInfo &VI = getVarInfo(Reg);
681 VI.AliveBlocks.clear();
682 VI.Kills.clear();
683
684 MachineInstr &DefMI = *MRI->getUniqueVRegDef(Reg);
685 MachineBasicBlock &DefBB = *DefMI.getParent();
686
687 // Initialize a worklist of BBs that Reg is live-to-end of. (Here
688 // "live-to-end" means Reg is live at the end of a block even if it is only
689 // live because of phi uses in a successor. This is different from isLiveOut()
690 // which does not consider phi uses.)
691 SmallVector<MachineBasicBlock *> LiveToEndBlocks;
692 SparseBitVector<> UseBlocks;
693 unsigned NumRealUses = 0;
694 for (auto &UseMO : MRI->use_nodbg_operands(Reg)) {
695 UseMO.setIsKill(false);
696 if (!UseMO.readsReg())
697 continue;
698 ++NumRealUses;
699 MachineInstr &UseMI = *UseMO.getParent();
700 MachineBasicBlock &UseBB = *UseMI.getParent();
701 UseBlocks.set(UseBB.getNumber());
702 if (UseMI.isPHI()) {
703 // If Reg is used in a phi then it is live-to-end of the corresponding
704 // predecessor.
705 unsigned Idx = UseMO.getOperandNo();
706 LiveToEndBlocks.push_back(Elt: UseMI.getOperand(i: Idx + 1).getMBB());
707 } else if (&UseBB == &DefBB) {
708 // A non-phi use in the same BB as the single def must come after the def.
709 } else {
710 // Otherwise Reg must be live-to-end of all predecessors.
711 LiveToEndBlocks.append(in_start: UseBB.pred_begin(), in_end: UseBB.pred_end());
712 }
713 }
714
715 // Handle the case where all uses have been removed.
716 if (NumRealUses == 0) {
717 VI.Kills.push_back(x: &DefMI);
718 DefMI.addRegisterDead(Reg, RegInfo: nullptr);
719 return;
720 }
721 DefMI.clearRegisterDeads(Reg);
722
723 // Iterate over the worklist adding blocks to AliveBlocks.
724 bool LiveToEndOfDefBB = false;
725 while (!LiveToEndBlocks.empty()) {
726 MachineBasicBlock &BB = *LiveToEndBlocks.pop_back_val();
727 if (&BB == &DefBB) {
728 LiveToEndOfDefBB = true;
729 continue;
730 }
731 if (VI.AliveBlocks.test(Idx: BB.getNumber()))
732 continue;
733 VI.AliveBlocks.set(BB.getNumber());
734 LiveToEndBlocks.append(in_start: BB.pred_begin(), in_end: BB.pred_end());
735 }
736
737 // Recompute kill flags. For each block in which Reg is used but is not
738 // live-through, find the last instruction that uses Reg. Ignore phi nodes
739 // because they should not be included in Kills.
740 for (unsigned UseBBNum : UseBlocks) {
741 if (VI.AliveBlocks.test(Idx: UseBBNum))
742 continue;
743 MachineBasicBlock &UseBB = *MF->getBlockNumbered(N: UseBBNum);
744 if (&UseBB == &DefBB && LiveToEndOfDefBB)
745 continue;
746 for (auto &MI : reverse(C&: UseBB)) {
747 if (MI.isDebugOrPseudoInstr())
748 continue;
749 if (MI.isPHI())
750 break;
751 if (MI.readsVirtualRegister(Reg)) {
752 assert(!MI.killsRegister(Reg, /*TRI=*/nullptr));
753 MI.addRegisterKilled(IncomingReg: Reg, RegInfo: nullptr);
754 VI.Kills.push_back(x: &MI);
755 break;
756 }
757 }
758 }
759}
760
761/// replaceKillInstruction - Update register kill info by replacing a kill
762/// instruction with a new one.
763void LiveVariables::replaceKillInstruction(Register Reg, MachineInstr &OldMI,
764 MachineInstr &NewMI) {
765 VarInfo &VI = getVarInfo(Reg);
766 llvm::replace(Range&: VI.Kills, OldValue: &OldMI, NewValue: &NewMI);
767}
768
769/// removeVirtualRegistersKilled - Remove all killed info for the specified
770/// instruction.
771void LiveVariables::removeVirtualRegistersKilled(MachineInstr &MI) {
772 for (MachineOperand &MO : MI.operands()) {
773 if (MO.isReg() && MO.isKill()) {
774 MO.setIsKill(false);
775 Register Reg = MO.getReg();
776 if (Reg.isVirtual()) {
777 bool removed = getVarInfo(Reg).removeKill(MI);
778 assert(removed && "kill not in register's VarInfo?");
779 (void)removed;
780 }
781 }
782 }
783}
784
785/// analyzePHINodes - Gather information about the PHI nodes in here. In
786/// particular, we want to map the variable information of a virtual register
787/// which is used in a PHI node. We map that to the BB the vreg is coming from.
788///
789void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
790 for (const auto &MBB : Fn)
791 for (const auto &BBI : MBB) {
792 if (!BBI.isPHI())
793 break;
794 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
795 if (BBI.getOperand(i).readsReg())
796 PHIVarInfo[BBI.getOperand(i: i + 1).getMBB()->getNumber()]
797 .push_back(Elt: BBI.getOperand(i).getReg());
798 }
799}
800
801bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
802 Register Reg, MachineRegisterInfo &MRI) {
803 unsigned Num = MBB.getNumber();
804
805 // Reg is live-through.
806 if (AliveBlocks.test(Idx: Num))
807 return true;
808
809 // Registers defined in MBB cannot be live in.
810 const MachineInstr *Def = MRI.getVRegDef(Reg);
811 if (Def && Def->getParent() == &MBB)
812 return false;
813
814 // Reg was not defined in MBB, was it killed here?
815 return findKill(MBB: &MBB);
816}
817
818bool LiveVariables::isLiveOut(Register Reg, const MachineBasicBlock &MBB) {
819 LiveVariables::VarInfo &VI = getVarInfo(Reg);
820
821 SmallPtrSet<const MachineBasicBlock *, 8> Kills;
822 for (MachineInstr *MI : VI.Kills)
823 Kills.insert(Ptr: MI->getParent());
824
825 // Loop over all of the successors of the basic block, checking to see if
826 // the value is either live in the block, or if it is killed in the block.
827 for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
828 // Is it alive in this successor?
829 unsigned SuccIdx = SuccMBB->getNumber();
830 if (VI.AliveBlocks.test(Idx: SuccIdx))
831 return true;
832 // Or is it live because there is a use in a successor that kills it?
833 if (Kills.count(Ptr: SuccMBB))
834 return true;
835 }
836
837 return false;
838}
839
840/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
841/// variables that are live out of DomBB will be marked as passing live through
842/// BB.
843void LiveVariables::addNewBlock(MachineBasicBlock *BB,
844 MachineBasicBlock *DomBB,
845 MachineBasicBlock *SuccBB) {
846 const unsigned NumNew = BB->getNumber();
847
848 DenseSet<Register> Defs, Kills;
849
850 MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
851 for (; BBI != BBE && BBI->isPHI(); ++BBI) {
852 // Record the def of the PHI node.
853 Defs.insert(V: BBI->getOperand(i: 0).getReg());
854
855 // All registers used by PHI nodes in SuccBB must be live through BB.
856 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
857 if (BBI->getOperand(i: i+1).getMBB() == BB)
858 getVarInfo(Reg: BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
859 }
860
861 // Record all vreg defs and kills of all instructions in SuccBB.
862 for (; BBI != BBE; ++BBI) {
863 for (const MachineOperand &Op : BBI->operands()) {
864 if (Op.isReg() && Op.getReg().isVirtual()) {
865 if (Op.isDef())
866 Defs.insert(V: Op.getReg());
867 else if (Op.isKill())
868 Kills.insert(V: Op.getReg());
869 }
870 }
871 }
872
873 // Update info for all live variables
874 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
875 Register Reg = Register::index2VirtReg(Index: i);
876
877 // If the Defs is defined in the successor it can't be live in BB.
878 if (Defs.count(V: Reg))
879 continue;
880
881 // If the register is either killed in or live through SuccBB it's also live
882 // through BB.
883 VarInfo &VI = getVarInfo(Reg);
884 if (Kills.count(V: Reg) || VI.AliveBlocks.test(Idx: SuccBB->getNumber()))
885 VI.AliveBlocks.set(NumNew);
886 }
887}
888
889/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
890/// variables that are live out of DomBB will be marked as passing live through
891/// BB. LiveInSets[BB] is *not* updated (because it is not needed during
892/// PHIElimination).
893void LiveVariables::addNewBlock(MachineBasicBlock *BB,
894 MachineBasicBlock *DomBB,
895 MachineBasicBlock *SuccBB,
896 std::vector<SparseBitVector<>> &LiveInSets) {
897 const unsigned NumNew = BB->getNumber();
898
899 SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()];
900 for (unsigned R : BV) {
901 Register VirtReg = Register::index2VirtReg(Index: R);
902 LiveVariables::VarInfo &VI = getVarInfo(Reg: VirtReg);
903 VI.AliveBlocks.set(NumNew);
904 }
905 // All registers used by PHI nodes in SuccBB must be live through BB.
906 for (MachineBasicBlock::iterator BBI = SuccBB->begin(),
907 BBE = SuccBB->end();
908 BBI != BBE && BBI->isPHI(); ++BBI) {
909 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
910 if (BBI->getOperand(i: i + 1).getMBB() == BB &&
911 BBI->getOperand(i).readsReg())
912 getVarInfo(Reg: BBI->getOperand(i).getReg())
913 .AliveBlocks.set(NumNew);
914 }
915}
916