llvm/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

//===- InstrRefBasedImpl.cpp - Tracking Debug Value MIs -------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
/// \file InstrRefBasedImpl.cpp
///
/// This is a separate implementation of LiveDebugValues, see
/// LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information.
///
/// This pass propagates variable locations between basic blocks, resolving
/// control flow conflicts between them. The problem is SSA construction, where
/// each debug instruction assigns the *value* that a variable has, and every
/// instruction where the variable is in scope uses that variable. The resulting
/// map of instruction-to-value is then translated into a register (or spill)
/// location for each variable over each instruction.
///
/// The primary difference from normal SSA construction is that we cannot
/// _create_ PHI values that contain variable values. CodeGen has already
/// completed, and we can't alter it just to make debug-info complete. Thus:
/// we can identify function positions where we would like a PHI value for a
/// variable, but must search the MachineFunction to see whether such a PHI is
/// available. If no such PHI exists, the variable location must be dropped.
///
/// To achieve this, we perform two kinds of analysis. First, we identify
/// every value defined by every instruction (ignoring those that only move
/// another value), then re-compute an SSA-form representation of the
/// MachineFunction, using value propagation to eliminate any un-necessary
/// PHI values. This gives us a map of every value computed in the function,
/// and its location within the register file / stack.
///
/// Secondly, for each variable we perform the same analysis, where each debug
/// instruction is considered a def, and every instruction where the variable
/// is in lexical scope as a use. Value propagation is used again to eliminate
/// any un-necessary PHIs. This gives us a map of each variable to the value
/// it should have in a block.
///
/// Once both are complete, we have two maps for each block:
///  * Variables to the values they should have,
///  * Values to the register / spill slot they are located in.
/// After which we can marry-up variable values with a location, and emit
/// DBG_VALUE instructions specifying those locations. Variable locations may
/// be dropped in this process due to the desired variable value not being
/// resident in any machine location, or because there is no PHI value in any
/// location that accurately represents the desired value.  The building of
/// location lists for each block is left to DbgEntityHistoryCalculator.
///
/// This pass is kept efficient because the size of the first SSA problem
/// is proportional to the working-set size of the function, which the compiler
/// tries to keep small. (It's also proportional to the number of blocks).
/// Additionally, we repeatedly perform the second SSA problem analysis with
/// only the variables and blocks in a single lexical scope, exploiting their
/// locality.
///
/// ### Terminology
///
/// A machine location is a register or spill slot, a value is something that's
/// defined by an instruction or PHI node, while a variable value is the value
/// assigned to a variable. A variable location is a machine location, that must
/// contain the appropriate variable value. A value that is a PHI node is
/// occasionally called an mphi.
///
/// The first SSA problem is the "machine value location" problem,
/// because we're determining which machine locations contain which values.
/// The "locations" are constant: what's unknown is what value they contain.
///
/// The second SSA problem (the one for variables) is the "variable value
/// problem", because it's determining what values a variable has, rather than
/// what location those values are placed in.
///
/// TODO:
///   Overlapping fragments
///   Entry values
///   Add back DEBUG statements for debugging this
///   Collect statistics
///
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/CodeGen/LexicalScopes.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineInstrBundle.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GenericIteratedDominanceFrontier.h"
#include "llvm/Support/TypeSize.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <functional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

#include "InstrRefBasedImpl.h"
#include "LiveDebugValues.h"
#include <optional>

usingnamespacellvm;
usingnamespaceLiveDebugValues;

// SSAUpdaterImple sets DEBUG_TYPE, change it.
#undef DEBUG_TYPE
#define DEBUG_TYPE …

// Act more like the VarLoc implementation, by propagating some locations too
// far and ignoring some transfers.
static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
                                   cl::desc("Act like old LiveDebugValues did"),
                                   cl::init(false));

// Limit for the maximum number of stack slots we should track, past which we
// will ignore any spills. InstrRefBasedLDV gathers detailed information on all
// stack slots which leads to high memory consumption, and in some scenarios
// (such as asan with very many locals) the working set of the function can be
// very large, causing many spills. In these scenarios, it is very unlikely that
// the developer has hundreds of variables live at the same time that they're
// carefully thinking about -- instead, they probably autogenerated the code.
// When this happens, gracefully stop tracking excess spill slots, rather than
// consuming all the developer's memory.
static cl::opt<unsigned>
    StackWorkingSetLimit("livedebugvalues-max-stack-slots", cl::Hidden,
                         cl::desc("livedebugvalues-stack-ws-limit"),
                         cl::init(250));

DbgOpID DbgOpID::UndefID = …;

/// Tracker for converting machine value locations and variable values into
/// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs
/// specifying block live-in locations and transfers within blocks.
///
/// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker
/// and must be initialized with the set of variable values that are live-in to
/// the block. The caller then repeatedly calls process(). TransferTracker picks
/// out variable locations for the live-in variable values (if there _is_ a
/// location) and creates the corresponding DBG_VALUEs. Then, as the block is
/// stepped through, transfers of values between machine locations are
/// identified and if profitable, a DBG_VALUE created.
///
/// This is where debug use-before-defs would be resolved: a variable with an
/// unavailable value could materialize in the middle of a block, when the
/// value becomes available. Or, we could detect clobbers and re-specify the
/// variable in a backup location. (XXX these are unimplemented).
class TransferTracker { … };

//===----------------------------------------------------------------------===//
//            Implementation
//===----------------------------------------------------------------------===//

ValueIDNum ValueIDNum::EmptyValue = …;
ValueIDNum ValueIDNum::TombstoneValue = …;

#ifndef NDEBUG
void ResolvedDbgOp::dump(const MLocTracker *MTrack) const {
  if (IsConst) {
    dbgs() << MO;
  } else {
    dbgs() << MTrack->LocIdxToName(Loc);
  }
}
void DbgOp::dump(const MLocTracker *MTrack) const {
  if (IsConst) {
    dbgs() << MO;
  } else if (!isUndef()) {
    dbgs() << MTrack->IDAsString(ID);
  }
}
void DbgOpID::dump(const MLocTracker *MTrack, const DbgOpIDMap *OpStore) const {
  if (!OpStore) {
    dbgs() << "ID(" << asU32() << ")";
  } else {
    OpStore->find(*this).dump(MTrack);
  }
}
void DbgValue::dump(const MLocTracker *MTrack,
                    const DbgOpIDMap *OpStore) const {
  if (Kind == NoVal) {
    dbgs() << "NoVal(" << BlockNo << ")";
  } else if (Kind == VPHI || Kind == Def) {
    if (Kind == VPHI)
      dbgs() << "VPHI(" << BlockNo << ",";
    else
      dbgs() << "Def(";
    for (unsigned Idx = 0; Idx < getDbgOpIDs().size(); ++Idx) {
      getDbgOpID(Idx).dump(MTrack, OpStore);
      if (Idx != 0)
        dbgs() << ",";
    }
    dbgs() << ")";
  }
  if (Properties.Indirect)
    dbgs() << " indir";
  if (Properties.DIExpr)
    dbgs() << " " << *Properties.DIExpr;
}
#endif

MLocTracker::MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI,
                         const TargetLowering &TLI)
    : … { … }

LocIdx MLocTracker::trackRegister(unsigned ID) { … }

void MLocTracker::writeRegMask(const MachineOperand *MO, unsigned CurBB,
                               unsigned InstID) { … }

std::optional<SpillLocationNo> MLocTracker::getOrTrackSpillLoc(SpillLoc L) { … }

std::string MLocTracker::LocIdxToName(LocIdx Idx) const { … }

std::string MLocTracker::IDAsString(const ValueIDNum &Num) const { … }

#ifndef NDEBUG
LLVM_DUMP_METHOD void MLocTracker::dump() {
  for (auto Location : locations()) {
    std::string MLocName = LocIdxToName(Location.Value.getLoc());
    std::string DefName = Location.Value.asString(MLocName);
    dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
  }
}

LLVM_DUMP_METHOD void MLocTracker::dump_mloc_map() {
  for (auto Location : locations()) {
    std::string foo = LocIdxToName(Location.Idx);
    dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n";
  }
}
#endif

MachineInstrBuilder
MLocTracker::emitLoc(const SmallVectorImpl<ResolvedDbgOp> &DbgOps,
                     const DebugVariable &Var, const DILocation *DILoc,
                     const DbgValueProperties &Properties) { … }

/// Default construct and initialize the pass.
InstrRefBasedLDV::InstrRefBasedLDV() = default;

bool InstrRefBasedLDV::isCalleeSaved(LocIdx L) const { … }
bool InstrRefBasedLDV::isCalleeSavedReg(Register R) const { … }

//===----------------------------------------------------------------------===//
//            Debug Range Extension Implementation
//===----------------------------------------------------------------------===//

#ifndef NDEBUG
// Something to restore in the future.
// void InstrRefBasedLDV::printVarLocInMBB(..)
#endif

std::optional<SpillLocationNo>
InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { … }

std::optional<LocIdx>
InstrRefBasedLDV::findLocationForMemOperand(const MachineInstr &MI) { … }

/// End all previous ranges related to @MI and start a new range from @MI
/// if it is a DBG_VALUE instr.
bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) { … }

std::optional<ValueIDNum> InstrRefBasedLDV::getValueForInstrRef(
    unsigned InstNo, unsigned OpNo, MachineInstr &MI,
    const FuncValueTable *MLiveOuts, const FuncValueTable *MLiveIns) { … }

bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
                                             const FuncValueTable *MLiveOuts,
                                             const FuncValueTable *MLiveIns) { … }

bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) { … }

void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { … }

void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) { … }

std::optional<SpillLocationNo>
InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
                                     MachineFunction *MF) { … }

bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
                                       MachineFunction *MF, unsigned &Reg) { … }

std::optional<SpillLocationNo>
InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,
                                       MachineFunction *MF, unsigned &Reg) { … }

bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) { … }

bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) { … }

/// Accumulate a mapping between each DILocalVariable fragment and other
/// fragments of that DILocalVariable which overlap. This reduces work during
/// the data-flow stage from "Find any overlapping fragments" to "Check if the
/// known-to-overlap fragments are present".
/// \param MI A previously unprocessed debug instruction to analyze for
///           fragment usage.
void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) { … }

void InstrRefBasedLDV::process(MachineInstr &MI,
                               const FuncValueTable *MLiveOuts,
                               const FuncValueTable *MLiveIns) { … }

void InstrRefBasedLDV::produceMLocTransferFunction(
    MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer,
    unsigned MaxNumBlocks) { … }

bool InstrRefBasedLDV::mlocJoin(
    MachineBasicBlock &MBB, SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
    FuncValueTable &OutLocs, ValueTable &InLocs) { … }

void InstrRefBasedLDV::findStackIndexInterference(
    SmallVectorImpl<unsigned> &Slots) { … }

void InstrRefBasedLDV::placeMLocPHIs(
    MachineFunction &MF, SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
    FuncValueTable &MInLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer) { … }

void InstrRefBasedLDV::buildMLocValueMap(
    MachineFunction &MF, FuncValueTable &MInLocs, FuncValueTable &MOutLocs,
    SmallVectorImpl<MLocTransferMap> &MLocTransfer) { … }

void InstrRefBasedLDV::BlockPHIPlacement(
    const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
    const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,
    SmallVectorImpl<MachineBasicBlock *> &PHIBlocks) { … }

bool InstrRefBasedLDV::pickVPHILoc(
    SmallVectorImpl<DbgOpID> &OutValues, const MachineBasicBlock &MBB,
    const LiveIdxT &LiveOuts, FuncValueTable &MOutLocs,
    const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) { … }

std::optional<ValueIDNum> InstrRefBasedLDV::pickOperandPHILoc(
    unsigned DbgOpIdx, const MachineBasicBlock &MBB, const LiveIdxT &LiveOuts,
    FuncValueTable &MOutLocs,
    const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) { … }

bool InstrRefBasedLDV::vlocJoin(
    MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs,
    SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
    DbgValue &LiveIn) { … }

void InstrRefBasedLDV::getBlocksForScope(
    const DILocation *DILoc,
    SmallPtrSetImpl<const MachineBasicBlock *> &BlocksToExplore,
    const SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks) { … }

void InstrRefBasedLDV::buildVLocValueMap(
    const DILocation *DILoc,
    const SmallSet<DebugVariableID, 4> &VarsWeCareAbout,
    SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
    FuncValueTable &MOutLocs, FuncValueTable &MInLocs,
    SmallVectorImpl<VLocTracker> &AllTheVLocs) { … }

void InstrRefBasedLDV::placePHIsForSingleVarDefinition(
    const SmallPtrSetImpl<MachineBasicBlock *> &InScopeBlocks,
    MachineBasicBlock *AssignMBB, SmallVectorImpl<VLocTracker> &AllTheVLocs,
    DebugVariableID VarID, LiveInsT &Output) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void InstrRefBasedLDV::dump_mloc_transfer(
    const MLocTransferMap &mloc_transfer) const {
  for (const auto &P : mloc_transfer) {
    std::string foo = MTracker->LocIdxToName(P.first);
    std::string bar = MTracker->IDAsString(P.second);
    dbgs() << "Loc " << foo << " --> " << bar << "\n";
  }
}
#endif

void InstrRefBasedLDV::initialSetup(MachineFunction &MF) { … }

// Produce an "ejection map" for blocks, i.e., what's the highest-numbered
// lexical scope it's used in. When exploring in DFS order and we pass that
// scope, the block can be processed and any tracking information freed.
void InstrRefBasedLDV::makeDepthFirstEjectionMap(
    SmallVectorImpl<unsigned> &EjectionMap,
    const ScopeToDILocT &ScopeToDILocation,
    ScopeToAssignBlocksT &ScopeToAssignBlocks) { … }

bool InstrRefBasedLDV::depthFirstVLocAndEmit(
    unsigned MaxNumBlocks, const ScopeToDILocT &ScopeToDILocation,
    const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToAssignBlocks,
    LiveInsT &Output, FuncValueTable &MOutLocs, FuncValueTable &MInLocs,
    SmallVectorImpl<VLocTracker> &AllTheVLocs, MachineFunction &MF,
    const TargetPassConfig &TPC) { … }

bool InstrRefBasedLDV::emitTransfers() { … }

/// Calculate the liveness information for the given machine function and
/// extend ranges across basic blocks.
bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
                                    MachineDominatorTree *DomTree,
                                    TargetPassConfig *TPC,
                                    unsigned InputBBLimit,
                                    unsigned InputDbgValLimit) { … }

LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() { … }

namespace {
class LDVSSABlock;
class LDVSSAUpdater;

// Pick a type to identify incoming block values as we construct SSA. We
// can't use anything more robust than an integer unfortunately, as SSAUpdater
// expects to zero-initialize the type.
BlockValueNum;

/// Represents an SSA PHI node for the SSA updater class. Contains the block
/// this PHI is in, the value number it would have, and the expected incoming
/// values from parent blocks.
class LDVSSAPhi { … };

/// Thin wrapper around a block predecessor iterator. Only difference from a
/// normal block iterator is that it dereferences to an LDVSSABlock.
class LDVSSABlockIterator { … };

/// Thin wrapper around a block for SSA Updater interface. Necessary because
/// we need to track the PHI value(s) that we may have observed as necessary
/// in this block.
class LDVSSABlock { … };

/// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
/// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
// SSAUpdaterTraits<LDVSSAUpdater>.
class LDVSSAUpdater { … };

LDVSSABlock *LDVSSABlockIterator::operator*() { … }

#ifndef NDEBUG

raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
  out << "SSALDVPHI " << PHI.PHIValNum;
  return out;
}

#endif

} // namespace

namespace llvm {

/// Template specialization to give SSAUpdater access to CFG and value
/// information. SSAUpdater calls methods in these traits, passing in the
/// LDVSSAUpdater object, to learn about blocks and the values they define.
/// It also provides methods to create PHI nodes and track them.
template <> class SSAUpdaterTraits<LDVSSAUpdater> { … };

} // end namespace llvm

std::optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(
    MachineFunction &MF, const FuncValueTable &MLiveOuts,
    const FuncValueTable &MLiveIns, MachineInstr &Here, uint64_t InstrNum) { … }

std::optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIsImpl(
    MachineFunction &MF, const FuncValueTable &MLiveOuts,
    const FuncValueTable &MLiveIns, MachineInstr &Here, uint64_t InstrNum) { … }