LLVM 19.0.0git
LiveVariables.cpp
Go to the documentation of this file.
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
29#include "llvm/ADT/DenseSet.h"
31#include "llvm/ADT/STLExtras.h"
33#include "llvm/ADT/SmallSet.h"
36#include "llvm/CodeGen/Passes.h"
37#include "llvm/Config/llvm-config.h"
38#include "llvm/Support/Debug.h"
41#include <algorithm>
42using namespace llvm;
43
44AnalysisKey LiveVariablesAnalysis::Key;
45
49 return Result(MF);
50}
51
55 OS << "Live variables in machine function: " << MF.getName() << '\n';
58}
59
63 "Live Variable Analysis", false, false)
64INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim)
66 "Live Variable Analysis", false, false)
67
68void LiveVariablesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
69 AU.addRequiredID(UnreachableMachineBlockElimID);
70 AU.setPreservesAll();
72}
73
74LiveVariables::LiveVariables(MachineFunction &MF)
75 : MF(&MF), MRI(&MF.getRegInfo()), TRI(MF.getSubtarget().getRegisterInfo()) {
76 analyze(MF);
77}
78
80 for (size_t I = 0, E = VirtRegInfo.size(); I != E; ++I) {
82 OS << "Virtual register '%" << I << "':\n";
83 VirtRegInfo[Reg].print(OS);
84 }
85}
86
89 for (MachineInstr *MI : Kills)
90 if (MI->getParent() == MBB)
91 return MI;
92 return nullptr;
93}
94
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)
111#endif
112
113/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
115 assert(Reg.isVirtual() && "getVarInfo: not a virtual register!");
116 VirtRegInfo.grow(Reg);
117 return VirtRegInfo[Reg];
118}
119
121 VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *MBB,
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(VRInfo.Kills.begin()+i); // Erase entry
130 break;
131 }
132
133 if (MBB == DefBlock) return; // Terminate recursion
134
135 if (VRInfo.AliveBlocks.test(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(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend());
143}
144
146 MachineBasicBlock *DefBlock,
149 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
150
151 while (!WorkList.empty()) {
152 MachineBasicBlock *Pred = WorkList.pop_back_val();
153 MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
154 }
155}
156
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(BBNum))
201 VRInfo.Kills.push_back(&MI);
202
203 // Update all dominating blocks to mark them as "known live".
204 for (MachineBasicBlock *Pred : MBB->predecessors())
205 MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(Reg)->getParent(), Pred);
206}
207
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(&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.
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(LastDefReg);
240 for (MachineOperand &MO : LastDef->all_defs()) {
241 if (MO.getReg() == 0)
242 continue;
243 Register DefReg = MO.getReg();
244 if (TRI->isSubRegister(Reg, DefReg)) {
245 for (MCPhysReg SubReg : TRI->subregs_inclusive(DefReg))
246 PartDefRegs.insert(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(MachineOperand::CreateReg(Reg, true/*IsDef*/,
272 true/*IsImp*/));
273 PhysRegDef[Reg] = LastPartialDef;
274 SmallSet<unsigned, 8> Processed;
275 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
276 if (Processed.count(SubReg))
277 continue;
278 if (PartDefRegs.count(SubReg))
279 continue;
280 // This part of Reg was defined before the last partial def. It's killed
281 // here.
283 false/*IsDef*/,
284 true/*IsImp*/));
285 PhysRegDef[SubReg] = LastPartialDef;
286 for (MCPhysReg SS : TRI->subregs(SubReg))
287 Processed.insert(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(MachineOperand::CreateReg(Reg, true/*IsDef*/,
294 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(SubReg))
374 PartUses.insert(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, TRI, true);
389 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
390 if (!PartUses.count(SubReg))
391 continue;
392 bool NeedDef = true;
393 if (PhysRegDef[Reg] == PhysRegDef[SubReg]) {
394 MachineOperand *MO =
395 PhysRegDef[Reg]->findRegisterDefOperand(SubReg, /*TRI=*/nullptr);
396 if (MO) {
397 NeedDef = false;
398 assert(!MO->isDead());
399 }
400 }
401 if (NeedDef)
402 PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
403 true/*IsDef*/, true/*IsImp*/));
404 MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
405 if (LastSubRef)
406 LastSubRef->addRegisterKilled(SubReg, TRI, true);
407 else {
408 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
409 for (MCPhysReg SS : TRI->subregs_inclusive(SubReg))
410 PhysRegUse[SS] = LastRefOrPartRef;
411 }
412 for (MCPhysReg SS : TRI->subregs(SubReg))
413 PartUses.erase(SS);
414 }
415 } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) {
416 if (LastPartDef)
417 // The last partial def kills the register.
418 LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
419 true/*IsImp*/, true/*IsKill*/));
420 else {
421 MachineOperand *MO =
422 LastRefOrPartRef->findRegisterDefOperand(Reg, TRI, false, 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, TRI, 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(Reg, TRI, 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(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(SR))
457 Super = SR;
458 HandlePhysRegKill(Super, nullptr);
459 }
460}
461
462void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI,
464 // What parts of the register are previously defined?
466 if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
467 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
468 Live.insert(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(SubReg))
478 continue;
479 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
480 for (MCPhysReg SS : TRI->subregs_inclusive(SubReg))
481 Live.insert(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(SubReg))
492 // Skip if this sub-register isn't defined.
493 continue;
494 HandlePhysRegKill(SubReg, MI);
495 }
496
497 if (MI)
498 Defs.push_back(Reg); // Remember this def.
499}
500
501void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
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,
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.
528 for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
529 MachineOperand &MO = MI.getOperand(i);
530 if (MO.isRegMask()) {
531 RegMasks.push_back(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(MOReg)))
539 MO.setIsKill(false);
540 if (MO.readsReg())
541 UseRegs.push_back(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(MOReg))
547 MO.setIsDead(false);
548 DefRegs.push_back(MOReg);
549 }
550 }
551
552 MachineBasicBlock *MBB = MI.getParent();
553 // Process all uses.
554 for (unsigned MOReg : UseRegs) {
556 HandleVirtRegUse(MOReg, MBB, MI);
557 else if (!MRI->isReserved(MOReg))
558 HandlePhysRegUse(MOReg, MI);
559 }
560
561 // Process all masked registers. (Call clobbers).
562 for (unsigned Mask : RegMasks)
563 HandleRegMask(MI.getOperand(Mask), NumRegs);
564
565 // Process all defs.
566 for (unsigned MOReg : DefRegs) {
568 HandleVirtRegDef(MOReg, MI);
569 else if (!MRI->isReserved(MOReg))
570 HandlePhysRegDef(MOReg, &MI, Defs);
571 }
572 UpdatePhysRegDefs(MI, Defs);
573}
574
575void LiveVariables::runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs) {
576 // Mark live-in registers as live-in.
578 for (const auto &LI : MBB->liveins()) {
580 "Cannot have a live-in virtual register!");
581 HandlePhysRegDef(LI.PhysReg, 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(std::make_pair(&MI, 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.
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(LI.PhysReg))
616 // Ignore other live-ins, e.g. those that are live into landing pads.
617 LiveOuts.insert(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(i))
625 HandlePhysRegDef(i, 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(NumRegs, nullptr);
635 PhysRegUse.assign(NumRegs, nullptr);
636 PHIVarInfo.resize(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("regalloc=... not currently supported with -O0");
643
644 analyzePHINodes(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();
652
653 for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
654 runOnBlock(MBB, NumRegs);
655
656 PhysRegDef.assign(NumRegs, nullptr);
657 PhysRegUse.assign(NumRegs, 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) {
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, TRI);
667 else
668 VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, 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
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(UseMI.getOperand(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(UseBB.pred_begin(), 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(&DefMI);
725 DefMI.addRegisterDead(Reg, 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(BB.getNumber()))
739 continue;
740 VI.AliveBlocks.set(BB.getNumber());
741 LiveToEndBlocks.append(BB.pred_begin(), 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(UseBBNum))
749 continue;
750 MachineBasicBlock &UseBB = *MF->getBlockNumbered(UseBBNum);
751 if (&UseBB == &DefBB && LiveToEndOfDefBB)
752 continue;
753 for (auto &MI : reverse(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(Reg, nullptr);
761 VI.Kills.push_back(&MI);
762 break;
763 }
764 }
765 }
766}
767
768/// replaceKillInstruction - Update register kill info by replacing a kill
769/// instruction with a new one.
771 MachineInstr &NewMI) {
772 VarInfo &VI = getVarInfo(Reg);
773 std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
774}
775
776/// removeVirtualRegistersKilled - Remove all killed info for the specified
777/// instruction.
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 + 1).getMBB()->getNumber()]
804 .push_back(BBI.getOperand(i).getReg());
805 }
806}
807
809 Register Reg, MachineRegisterInfo &MRI) {
810 unsigned Num = MBB.getNumber();
811
812 // Reg is live-through.
813 if (AliveBlocks.test(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);
823}
824
827
829 for (MachineInstr *MI : VI.Kills)
830 Kills.insert(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(SuccIdx))
838 return true;
839 // Or is it live because there is a use in a successor that kills it?
840 if (Kills.count(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.
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(BBI->getOperand(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+1).getMBB() == BB)
865 getVarInfo(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(Op.getReg());
874 else if (Op.isKill())
875 Kills.insert(Op.getReg());
876 }
877 }
878 }
879
880 // Update info for all live variables
881 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
883
884 // If the Defs is defined in the successor it can't be live in BB.
885 if (Defs.count(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(Reg) || VI.AliveBlocks.test(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).
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) {
909 LiveVariables::VarInfo &VI = getVarInfo(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 + 1).getMBB() == BB &&
918 BBI->getOperand(i).readsReg())
919 getVarInfo(BBI->getOperand(i).getReg())
920 .AliveBlocks.set(NumNew);
921 }
922}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock & MBB
block Block Frequency Analysis
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
IRTranslator LLVM IR MI
livevars
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
Represent the analysis usage information of a pass.
This class represents an Operation in the Expression.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Result run(MachineFunction &MF, MachineFunctionAnalysisManager &)
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
void replaceKillInstruction(Register Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one.
void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
bool isLiveOut(Register Reg, const MachineBasicBlock &MBB)
isLiveOut - Determine if Reg is live out from MBB, when not considering PHI nodes.
void HandleVirtRegDef(Register reg, MachineInstr &MI)
void print(raw_ostream &OS) const
void recomputeForSingleDefVirtReg(Register Reg)
Recompute liveness from scratch for a virtual register Reg that is known to have a single def that do...
void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI)
VarInfo & getVarInfo(Register Reg)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
iterator_range< MCSuperRegIterator > superregs(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, excluding Reg.
iterator_range< MCSubRegIterator > subregs_inclusive(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, including Reg.
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
iterator_range< MCSubRegIterator > subregs(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, excluding Reg.
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
pred_reverse_iterator pred_rbegin()
pred_reverse_iterator pred_rend()
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const MachineBasicBlock & front() const
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:346
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
iterator_range< filtered_mop_iterator > all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
Definition: MachineInstr.h:756
MachineOperand * findRegisterDefOperand(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
MachineOperand class - Representation of each machine instruction operand.
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setIsDead(bool Val=true)
void setIsKill(bool Val=true)
void setIsEarlyClobber(bool Val=true)
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
static constexpr bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:95
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:412
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:344
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:418
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:479
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
bool erase(const T &V)
Definition: SmallSet.h:207
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:818
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
void set(unsigned Idx)
bool test(unsigned Idx) const
virtual unsigned getNumSupportedRegs(const MachineFunction &) const
Return the number of registers for the function. (may overestimate)
bool isInAllocatableClass(MCRegister RegNo) const
Return true if the register is in the allocation of any register class.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ Entry
Definition: COFF.h:811
@ SS
Definition: X86.h:211
Reg
All possible values of the reg field in the ModR/M byte.
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:167
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:78
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:93
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:88
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:83
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
void print(raw_ostream &OS) const
bool isLiveIn(const MachineBasicBlock &MBB, Register Reg, MachineRegisterInfo &MRI)
isLiveIn - Is Reg live in to MBB? This means that Reg is live through MBB, or it is killed in MBB.
VirtRegInfo - Information about a virtual register used by a set of operands.