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