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