LiveVariables.cpp | Explore in Territory

//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the LiveVariable analysis pass.  For each machine
// instruction in the function, this pass calculates the set of registers that
// are immediately dead after the instruction (i.e., the instruction calculates
// the value, but it is never used) and the set of registers that are used by
// the instruction, but are never used after the instruction (i.e., they are
// killed).
//
// This class computes live variables using a sparse implementation based on
// the machine code SSA form.  This class computes live variable information for
// each virtual and _register allocatable_ physical register in a function.  It
// uses the dominance properties of SSA form to efficiently compute live
// variables for virtual registers, and assumes that physical registers are only
// live within a single basic block (allowing it to do a single local analysis
// to resolve physical register lifetimes in each basic block).  If a physical
// register is not register allocatable, it is not tracked.  This is useful for
// things like the stack pointer and condition codes.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
usingnamespacellvm;

AnalysisKey LiveVariablesAnalysis::Key;

LiveVariablesAnalysis::Result
LiveVariablesAnalysis::run(MachineFunction &MF,
                           MachineFunctionAnalysisManager &) { … }

PreservedAnalyses
LiveVariablesPrinterPass::run(MachineFunction &MF,
                              MachineFunctionAnalysisManager &MFAM) { … }

char LiveVariablesWrapperPass::ID = …;
char &llvm::LiveVariablesID = …;
INITIALIZE_PASS_BEGIN(LiveVariablesWrapperPass, "livevars",
                      "Live Variable Analysis", false, false)
INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim)
INITIALIZE_PASS_END(LiveVariablesWrapperPass, "livevars",
                    "Live Variable Analysis", false, false)

void LiveVariablesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

LiveVariables::LiveVariables(MachineFunction &MF)
    : … { … }

void LiveVariables::print(raw_ostream &OS) const { … }

MachineInstr *
LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const { … }

void LiveVariables::VarInfo::print(raw_ostream &OS) const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LiveVariables::VarInfo::dump() const { print(dbgs()); }
#endif

/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
LiveVariables::VarInfo &LiveVariables::getVarInfo(Register Reg) { … }

void LiveVariables::MarkVirtRegAliveInBlock(
    VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *MBB,
    SmallVectorImpl<MachineBasicBlock *> &WorkList) { … }

void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
                                            MachineBasicBlock *DefBlock,
                                            MachineBasicBlock *MBB) { … }

void LiveVariables::HandleVirtRegUse(Register Reg, MachineBasicBlock *MBB,
                                     MachineInstr &MI) { … }

void LiveVariables::HandleVirtRegDef(Register Reg, MachineInstr &MI) { … }

/// FindLastPartialDef - Return the last partial def of the specified register.
/// Also returns the sub-registers that're defined by the instruction.
MachineInstr *
LiveVariables::FindLastPartialDef(Register Reg,
                                  SmallSet<unsigned, 4> &PartDefRegs) { … }

/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
/// implicit defs to a machine instruction if there was an earlier def of its
/// super-register.
void LiveVariables::HandlePhysRegUse(Register Reg, MachineInstr &MI) { … }

/// FindLastRefOrPartRef - Return the last reference or partial reference of
/// the specified register.
MachineInstr *LiveVariables::FindLastRefOrPartRef(Register Reg) { … }

bool LiveVariables::HandlePhysRegKill(Register Reg, MachineInstr *MI) { … }

void LiveVariables::HandleRegMask(const MachineOperand &MO, unsigned NumRegs) { … }

void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI,
                                     SmallVectorImpl<unsigned> &Defs) { … }

void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
                                      SmallVectorImpl<unsigned> &Defs) { … }

void LiveVariables::runOnInstr(MachineInstr &MI,
                               SmallVectorImpl<unsigned> &Defs,
                               unsigned NumRegs) { … }

void LiveVariables::runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs) { … }

void LiveVariables::analyze(MachineFunction &mf) { … }

void LiveVariables::recomputeForSingleDefVirtReg(Register Reg) { … }

/// replaceKillInstruction - Update register kill info by replacing a kill
/// instruction with a new one.
void LiveVariables::replaceKillInstruction(Register Reg, MachineInstr &OldMI,
                                           MachineInstr &NewMI) { … }

/// removeVirtualRegistersKilled - Remove all killed info for the specified
/// instruction.
void LiveVariables::removeVirtualRegistersKilled(MachineInstr &MI) { … }

/// analyzePHINodes - Gather information about the PHI nodes in here. In
/// particular, we want to map the variable information of a virtual register
/// which is used in a PHI node. We map that to the BB the vreg is coming from.
///
void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { … }

bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
                                      Register Reg, MachineRegisterInfo &MRI) { … }

bool LiveVariables::isLiveOut(Register Reg, const MachineBasicBlock &MBB) { … }

/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
/// variables that are live out of DomBB will be marked as passing live through
/// BB.
void LiveVariables::addNewBlock(MachineBasicBlock *BB,
                                MachineBasicBlock *DomBB,
                                MachineBasicBlock *SuccBB) { … }

/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
/// variables that are live out of DomBB will be marked as passing live through
/// BB. LiveInSets[BB] is *not* updated (because it is not needed during
/// PHIElimination).
void LiveVariables::addNewBlock(MachineBasicBlock *BB,
                                MachineBasicBlock *DomBB,
                                MachineBasicBlock *SuccBB,
                                std::vector<SparseBitVector<>> &LiveInSets) { … }
llvm/llvm/lib/CodeGen/LiveVariables.cpp
