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