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, /*TRI=*/nullptr))
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 =
365 PhysRegDef[Reg]->findRegisterDefOperand(SubReg, /*TRI=*/nullptr);
366 if (MO) {
367 NeedDef = false;
368 assert(!MO->isDead());
369 }
370 }
371 if (NeedDef)
372 PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
373 true/*IsDef*/, true/*IsImp*/));
374 MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
375 if (LastSubRef)
376 LastSubRef->addRegisterKilled(SubReg, TRI, true);
377 else {
378 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
379 for (MCPhysReg SS : TRI->subregs_inclusive(SubReg))
380 PhysRegUse[SS] = LastRefOrPartRef;
381 }
382 for (MCPhysReg SS : TRI->subregs(SubReg))
383 PartUses.erase(SS);
384 }
385 } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) {
386 if (LastPartDef)
387 // The last partial def kills the register.
388 LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
389 true/*IsImp*/, true/*IsKill*/));
390 else {
391 MachineOperand *MO =
392 LastRefOrPartRef->findRegisterDefOperand(Reg, TRI, false, false);
393 bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
394 // If the last reference is the last def, then it's not used at all.
395 // That is, unless we are currently processing the last reference itself.
396 LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
397 if (NeedEC) {
398 // If we are adding a subreg def and the superreg def is marked early
399 // clobber, add an early clobber marker to the subreg def.
400 MO = LastRefOrPartRef->findRegisterDefOperand(Reg, /*TRI=*/nullptr);
401 if (MO)
402 MO->setIsEarlyClobber();
403 }
404 }
405 } else
406 LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
407 return true;
408}
409
410void LiveVariables::HandleRegMask(const MachineOperand &MO, unsigned NumRegs) {
411 // Call HandlePhysRegKill() for all live registers clobbered by Mask.
412 // Clobbered registers are always dead, sp there is no need to use
413 // HandlePhysRegDef().
414 for (unsigned Reg = 1; Reg != NumRegs; ++Reg) {
415 // Skip dead regs.
416 if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
417 continue;
418 // Skip mask-preserved regs.
419 if (!MO.clobbersPhysReg(Reg))
420 continue;
421 // Kill the largest clobbered super-register.
422 // This avoids needless implicit operands.
423 unsigned Super = Reg;
424 for (MCPhysReg SR : TRI->superregs(Reg))
425 if (SR < NumRegs && (PhysRegDef[SR] || PhysRegUse[SR]) &&
426 MO.clobbersPhysReg(SR))
427 Super = SR;
428 HandlePhysRegKill(Super, nullptr);
429 }
430}
431
432void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI,
434 // What parts of the register are previously defined?
436 if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
437 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
438 Live.insert(SubReg);
439 } else {
440 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
441 // If a register isn't itself defined, but all parts that make up of it
442 // are defined, then consider it also defined.
443 // e.g.
444 // AL =
445 // AH =
446 // = AX
447 if (Live.count(SubReg))
448 continue;
449 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
450 for (MCPhysReg SS : TRI->subregs_inclusive(SubReg))
451 Live.insert(SS);
452 }
453 }
454 }
455
456 // Start from the largest piece, find the last time any part of the register
457 // is referenced.
458 HandlePhysRegKill(Reg, MI);
459 // Only some of the sub-registers are used.
460 for (MCPhysReg SubReg : TRI->subregs(Reg)) {
461 if (!Live.count(SubReg))
462 // Skip if this sub-register isn't defined.
463 continue;
464 HandlePhysRegKill(SubReg, MI);
465 }
466
467 if (MI)
468 Defs.push_back(Reg); // Remember this def.
469}
470
471void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
473 while (!Defs.empty()) {
474 Register Reg = Defs.pop_back_val();
475 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) {
476 PhysRegDef[SubReg] = &MI;
477 PhysRegUse[SubReg] = nullptr;
478 }
479 }
480}
481
482void LiveVariables::runOnInstr(MachineInstr &MI,
484 unsigned NumRegs) {
485 assert(!MI.isDebugOrPseudoInstr());
486 // Process all of the operands of the instruction...
487 unsigned NumOperandsToProcess = MI.getNumOperands();
488
489 // Unless it is a PHI node. In this case, ONLY process the DEF, not any
490 // of the uses. They will be handled in other basic blocks.
491 if (MI.isPHI())
492 NumOperandsToProcess = 1;
493
494 // Clear kill and dead markers. LV will recompute them.
498 for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
499 MachineOperand &MO = MI.getOperand(i);
500 if (MO.isRegMask()) {
501 RegMasks.push_back(i);
502 continue;
503 }
504 if (!MO.isReg() || MO.getReg() == 0)
505 continue;
506 Register MOReg = MO.getReg();
507 if (MO.isUse()) {
508 if (!(MOReg.isPhysical() && MRI->isReserved(MOReg)))
509 MO.setIsKill(false);
510 if (MO.readsReg())
511 UseRegs.push_back(MOReg);
512 } else {
513 assert(MO.isDef());
514 // FIXME: We should not remove any dead flags. However the MIPS RDDSP
515 // instruction needs it at the moment: http://llvm.org/PR27116.
516 if (MOReg.isPhysical() && !MRI->isReserved(MOReg))
517 MO.setIsDead(false);
518 DefRegs.push_back(MOReg);
519 }
520 }
521
522 MachineBasicBlock *MBB = MI.getParent();
523 // Process all uses.
524 for (unsigned MOReg : UseRegs) {
526 HandleVirtRegUse(MOReg, MBB, MI);
527 else if (!MRI->isReserved(MOReg))
528 HandlePhysRegUse(MOReg, MI);
529 }
530
531 // Process all masked registers. (Call clobbers).
532 for (unsigned Mask : RegMasks)
533 HandleRegMask(MI.getOperand(Mask), NumRegs);
534
535 // Process all defs.
536 for (unsigned MOReg : DefRegs) {
538 HandleVirtRegDef(MOReg, MI);
539 else if (!MRI->isReserved(MOReg))
540 HandlePhysRegDef(MOReg, &MI, Defs);
541 }
542 UpdatePhysRegDefs(MI, Defs);
543}
544
545void LiveVariables::runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs) {
546 // Mark live-in registers as live-in.
548 for (const auto &LI : MBB->liveins()) {
550 "Cannot have a live-in virtual register!");
551 HandlePhysRegDef(LI.PhysReg, nullptr, Defs);
552 }
553
554 // Loop over all of the instructions, processing them.
555 DistanceMap.clear();
556 unsigned Dist = 0;
557 for (MachineInstr &MI : *MBB) {
558 if (MI.isDebugOrPseudoInstr())
559 continue;
560 DistanceMap.insert(std::make_pair(&MI, Dist++));
561
562 runOnInstr(MI, Defs, NumRegs);
563 }
564
565 // Handle any virtual assignments from PHI nodes which might be at the
566 // bottom of this basic block. We check all of our successor blocks to see
567 // if they have PHI nodes, and if so, we simulate an assignment at the end
568 // of the current block.
569 if (!PHIVarInfo[MBB->getNumber()].empty()) {
570 SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
571
572 for (unsigned I : VarInfoVec)
573 // Mark it alive only in the block we are representing.
575 MBB);
576 }
577
578 // MachineCSE may CSE instructions which write to non-allocatable physical
579 // registers across MBBs. Remember if any reserved register is liveout.
580 SmallSet<unsigned, 4> LiveOuts;
581 for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
582 if (SuccMBB->isEHPad())
583 continue;
584 for (const auto &LI : SuccMBB->liveins()) {
585 if (!TRI->isInAllocatableClass(LI.PhysReg))
586 // Ignore other live-ins, e.g. those that are live into landing pads.
587 LiveOuts.insert(LI.PhysReg);
588 }
589 }
590
591 // Loop over PhysRegDef / PhysRegUse, killing any registers that are
592 // available at the end of the basic block.
593 for (unsigned i = 0; i != NumRegs; ++i)
594 if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i))
595 HandlePhysRegDef(i, nullptr, Defs);
596}
597
599 MF = &mf;
600 MRI = &mf.getRegInfo();
601 TRI = MF->getSubtarget().getRegisterInfo();
602
603 const unsigned NumRegs = TRI->getNumSupportedRegs(mf);
604 PhysRegDef.assign(NumRegs, nullptr);
605 PhysRegUse.assign(NumRegs, nullptr);
606 PHIVarInfo.resize(MF->getNumBlockIDs());
607
608 // FIXME: LiveIntervals will be updated to remove its dependence on
609 // LiveVariables to improve compilation time and eliminate bizarre pass
610 // dependencies. Until then, we can't change much in -O0.
611 if (!MRI->isSSA())
612 report_fatal_error("regalloc=... not currently supported with -O0");
613
614 analyzePHINodes(mf);
615
616 // Calculate live variable information in depth first order on the CFG of the
617 // function. This guarantees that we will see the definition of a virtual
618 // register before its uses due to dominance properties of SSA (except for PHI
619 // nodes, which are treated as a special case).
620 MachineBasicBlock *Entry = &MF->front();
622
623 for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
624 runOnBlock(MBB, NumRegs);
625
626 PhysRegDef.assign(NumRegs, nullptr);
627 PhysRegUse.assign(NumRegs, nullptr);
628 }
629
630 // Convert and transfer the dead / killed information we have gathered into
631 // VirtRegInfo onto MI's.
632 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) {
633 const Register Reg = Register::index2VirtReg(i);
634 for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
635 if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
636 VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
637 else
638 VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
639 }
640
641 // Check to make sure there are no unreachable blocks in the MC CFG for the
642 // function. If so, it is due to a bug in the instruction selector or some
643 // other part of the code generator if this happens.
644#ifndef NDEBUG
645 for (const MachineBasicBlock &MBB : *MF)
646 assert(Visited.contains(&MBB) && "unreachable basic block found");
647#endif
648
649 PhysRegDef.clear();
650 PhysRegUse.clear();
651 PHIVarInfo.clear();
652
653 return false;
654}
655
657 assert(Reg.isVirtual());
658
659 VarInfo &VI = getVarInfo(Reg);
660 VI.AliveBlocks.clear();
661 VI.Kills.clear();
662
663 MachineInstr &DefMI = *MRI->getUniqueVRegDef(Reg);
664 MachineBasicBlock &DefBB = *DefMI.getParent();
665
666 // Initialize a worklist of BBs that Reg is live-to-end of. (Here
667 // "live-to-end" means Reg is live at the end of a block even if it is only
668 // live because of phi uses in a successor. This is different from isLiveOut()
669 // which does not consider phi uses.)
670 SmallVector<MachineBasicBlock *> LiveToEndBlocks;
671 SparseBitVector<> UseBlocks;
672 unsigned NumRealUses = 0;
673 for (auto &UseMO : MRI->use_nodbg_operands(Reg)) {
674 UseMO.setIsKill(false);
675 if (!UseMO.readsReg())
676 continue;
677 ++NumRealUses;
678 MachineInstr &UseMI = *UseMO.getParent();
679 MachineBasicBlock &UseBB = *UseMI.getParent();
680 UseBlocks.set(UseBB.getNumber());
681 if (UseMI.isPHI()) {
682 // If Reg is used in a phi then it is live-to-end of the corresponding
683 // predecessor.
684 unsigned Idx = UseMO.getOperandNo();
685 LiveToEndBlocks.push_back(UseMI.getOperand(Idx + 1).getMBB());
686 } else if (&UseBB == &DefBB) {
687 // A non-phi use in the same BB as the single def must come after the def.
688 } else {
689 // Otherwise Reg must be live-to-end of all predecessors.
690 LiveToEndBlocks.append(UseBB.pred_begin(), UseBB.pred_end());
691 }
692 }
693
694 // Handle the case where all uses have been removed.
695 if (NumRealUses == 0) {
696 VI.Kills.push_back(&DefMI);
697 DefMI.addRegisterDead(Reg, nullptr);
698 return;
699 }
700 DefMI.clearRegisterDeads(Reg);
701
702 // Iterate over the worklist adding blocks to AliveBlocks.
703 bool LiveToEndOfDefBB = false;
704 while (!LiveToEndBlocks.empty()) {
705 MachineBasicBlock &BB = *LiveToEndBlocks.pop_back_val();
706 if (&BB == &DefBB) {
707 LiveToEndOfDefBB = true;
708 continue;
709 }
710 if (VI.AliveBlocks.test(BB.getNumber()))
711 continue;
712 VI.AliveBlocks.set(BB.getNumber());
713 LiveToEndBlocks.append(BB.pred_begin(), BB.pred_end());
714 }
715
716 // Recompute kill flags. For each block in which Reg is used but is not
717 // live-through, find the last instruction that uses Reg. Ignore phi nodes
718 // because they should not be included in Kills.
719 for (unsigned UseBBNum : UseBlocks) {
720 if (VI.AliveBlocks.test(UseBBNum))
721 continue;
722 MachineBasicBlock &UseBB = *MF->getBlockNumbered(UseBBNum);
723 if (&UseBB == &DefBB && LiveToEndOfDefBB)
724 continue;
725 for (auto &MI : reverse(UseBB)) {
726 if (MI.isDebugOrPseudoInstr())
727 continue;
728 if (MI.isPHI())
729 break;
730 if (MI.readsVirtualRegister(Reg)) {
731 assert(!MI.killsRegister(Reg, /*TRI=*/nullptr));
732 MI.addRegisterKilled(Reg, nullptr);
733 VI.Kills.push_back(&MI);
734 break;
735 }
736 }
737 }
738}
739
740/// replaceKillInstruction - Update register kill info by replacing a kill
741/// instruction with a new one.
743 MachineInstr &NewMI) {
744 VarInfo &VI = getVarInfo(Reg);
745 std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
746}
747
748/// removeVirtualRegistersKilled - Remove all killed info for the specified
749/// instruction.
751 for (MachineOperand &MO : MI.operands()) {
752 if (MO.isReg() && MO.isKill()) {
753 MO.setIsKill(false);
754 Register Reg = MO.getReg();
755 if (Reg.isVirtual()) {
756 bool removed = getVarInfo(Reg).removeKill(MI);
757 assert(removed && "kill not in register's VarInfo?");
758 (void)removed;
759 }
760 }
761 }
762}
763
764/// analyzePHINodes - Gather information about the PHI nodes in here. In
765/// particular, we want to map the variable information of a virtual register
766/// which is used in a PHI node. We map that to the BB the vreg is coming from.
767///
768void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
769 for (const auto &MBB : Fn)
770 for (const auto &BBI : MBB) {
771 if (!BBI.isPHI())
772 break;
773 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
774 if (BBI.getOperand(i).readsReg())
775 PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
776 .push_back(BBI.getOperand(i).getReg());
777 }
778}
779
781 Register Reg, MachineRegisterInfo &MRI) {
782 unsigned Num = MBB.getNumber();
783
784 // Reg is live-through.
785 if (AliveBlocks.test(Num))
786 return true;
787
788 // Registers defined in MBB cannot be live in.
789 const MachineInstr *Def = MRI.getVRegDef(Reg);
790 if (Def && Def->getParent() == &MBB)
791 return false;
792
793 // Reg was not defined in MBB, was it killed here?
794 return findKill(&MBB);
795}
796
799
801 for (MachineInstr *MI : VI.Kills)
802 Kills.insert(MI->getParent());
803
804 // Loop over all of the successors of the basic block, checking to see if
805 // the value is either live in the block, or if it is killed in the block.
806 for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
807 // Is it alive in this successor?
808 unsigned SuccIdx = SuccMBB->getNumber();
809 if (VI.AliveBlocks.test(SuccIdx))
810 return true;
811 // Or is it live because there is a use in a successor that kills it?
812 if (Kills.count(SuccMBB))
813 return true;
814 }
815
816 return false;
817}
818
819/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
820/// variables that are live out of DomBB will be marked as passing live through
821/// BB.
823 MachineBasicBlock *DomBB,
824 MachineBasicBlock *SuccBB) {
825 const unsigned NumNew = BB->getNumber();
826
827 DenseSet<unsigned> Defs, Kills;
828
829 MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
830 for (; BBI != BBE && BBI->isPHI(); ++BBI) {
831 // Record the def of the PHI node.
832 Defs.insert(BBI->getOperand(0).getReg());
833
834 // All registers used by PHI nodes in SuccBB must be live through BB.
835 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
836 if (BBI->getOperand(i+1).getMBB() == BB)
837 getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
838 }
839
840 // Record all vreg defs and kills of all instructions in SuccBB.
841 for (; BBI != BBE; ++BBI) {
842 for (const MachineOperand &Op : BBI->operands()) {
843 if (Op.isReg() && Op.getReg().isVirtual()) {
844 if (Op.isDef())
845 Defs.insert(Op.getReg());
846 else if (Op.isKill())
847 Kills.insert(Op.getReg());
848 }
849 }
850 }
851
852 // Update info for all live variables
853 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
855
856 // If the Defs is defined in the successor it can't be live in BB.
857 if (Defs.count(Reg))
858 continue;
859
860 // If the register is either killed in or live through SuccBB it's also live
861 // through BB.
862 VarInfo &VI = getVarInfo(Reg);
863 if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber()))
864 VI.AliveBlocks.set(NumNew);
865 }
866}
867
868/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
869/// variables that are live out of DomBB will be marked as passing live through
870/// BB. LiveInSets[BB] is *not* updated (because it is not needed during
871/// PHIElimination).
873 MachineBasicBlock *DomBB,
874 MachineBasicBlock *SuccBB,
875 std::vector<SparseBitVector<>> &LiveInSets) {
876 const unsigned NumNew = BB->getNumber();
877
878 SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()];
879 for (unsigned R : BV) {
881 LiveVariables::VarInfo &VI = getVarInfo(VirtReg);
882 VI.AliveBlocks.set(NumNew);
883 }
884 // All registers used by PHI nodes in SuccBB must be live through BB.
885 for (MachineBasicBlock::iterator BBI = SuccBB->begin(),
886 BBE = SuccBB->end();
887 BBI != BBE && BBI->isPHI(); ++BBI) {
888 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
889 if (BBI->getOperand(i + 1).getMBB() == BB &&
890 BBI->getOperand(i).readsReg())
891 getVarInfo(BBI->getOperand(i).getReg())
892 .AliveBlocks.set(NumNew);
893 }
894}
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: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
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:341
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:751
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...
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: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:159
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.