llvm/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

//===- VarLocBasedImpl.cpp - Tracking Debug Value MIs with VarLoc class----===//
//
// 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 VarLocBasedImpl.cpp
///
/// LiveDebugValues is an optimistic "available expressions" dataflow
/// algorithm. The set of expressions is the set of machine locations
/// (registers, spill slots, constants, and target indices) that a variable
/// fragment might be located, qualified by a DIExpression and indirect-ness
/// flag, while each variable is identified by a DebugVariable object. The
/// availability of an expression begins when a DBG_VALUE instruction specifies
/// the location of a DebugVariable, and continues until that location is
/// clobbered or re-specified by a different DBG_VALUE for the same
/// DebugVariable.
///
/// The output of LiveDebugValues is additional DBG_VALUE instructions,
/// placed to extend variable locations as far they're available. This file
/// and the VarLocBasedLDV class is an implementation that explicitly tracks
/// locations, using the VarLoc class.
///
/// The canonical "available expressions" problem doesn't have expression
/// clobbering, instead when a variable is re-assigned, any expressions using
/// that variable get invalidated. LiveDebugValues can map onto "available
/// expressions" by having every register represented by a variable, which is
/// used in an expression that becomes available at a DBG_VALUE instruction.
/// When the register is clobbered, its variable is effectively reassigned, and
/// expressions computed from it become unavailable. A similar construct is
/// needed when a DebugVariable has its location re-specified, to invalidate
/// all other locations for that DebugVariable.
///
/// Using the dataflow analysis to compute the available expressions, we create
/// a DBG_VALUE at the beginning of each block where the expression is
/// live-in. This propagates variable locations into every basic block where
/// the location can be determined, rather than only having DBG_VALUEs in blocks
/// where locations are specified due to an assignment or some optimization.
/// Movements of values between registers and spill slots are annotated with
/// DBG_VALUEs too to track variable values bewteen locations. All this allows
/// DbgEntityHistoryCalculator to focus on only the locations within individual
/// blocks, facilitating testing and improving modularity.
///
/// We follow an optimisic dataflow approach, with this lattice:
///
/// \verbatim
///                    ┬ "Unknown"
///                          |
///                          v
///                         True
///                          |
///                          v
///                      ⊥ False
/// \endverbatim With "True" signifying that the expression is available (and
/// thus a DebugVariable's location is the corresponding register), while
/// "False" signifies that the expression is unavailable. "Unknown"s never
/// survive to the end of the analysis (see below).
///
/// Formally, all DebugVariable locations that are live-out of a block are
/// initialized to \top.  A blocks live-in values take the meet of the lattice
/// value for every predecessors live-outs, except for the entry block, where
/// all live-ins are \bot. The usual dataflow propagation occurs: the transfer
/// function for a block assigns an expression for a DebugVariable to be "True"
/// if a DBG_VALUE in the block specifies it; "False" if the location is
/// clobbered; or the live-in value if it is unaffected by the block. We
/// visit each block in reverse post order until a fixedpoint is reached. The
/// solution produced is maximal.
///
/// Intuitively, we start by assuming that every expression / variable location
/// is at least "True", and then propagate "False" from the entry block and any
/// clobbers until there are no more changes to make. This gives us an accurate
/// solution because all incorrect locations will have a "False" propagated into
/// them. It also gives us a solution that copes well with loops by assuming
/// that variable locations are live-through every loop, and then removing those
/// that are not through dataflow.
///
/// Within LiveDebugValues: each variable location is represented by a
/// VarLoc object that identifies the source variable, the set of
/// machine-locations that currently describe it (a single location for
/// DBG_VALUE or multiple for DBG_VALUE_LIST), and the DBG_VALUE inst that
/// specifies the location. Each VarLoc is indexed in the (function-scope) \p
/// VarLocMap, giving each VarLoc a set of unique indexes, each of which
/// corresponds to one of the VarLoc's machine-locations and can be used to
/// lookup the VarLoc in the VarLocMap. Rather than operate directly on machine
/// locations, the dataflow analysis in this pass identifies locations by their
/// indices in the VarLocMap, meaning all the variable locations in a block can
/// be described by a sparse vector of VarLocMap indices.
///
/// All the storage for the dataflow analysis is local to the ExtendRanges
/// method and passed down to helper methods. "OutLocs" and "InLocs" record the
/// in and out lattice values for each block. "OpenRanges" maintains a list of
/// variable locations and, with the "process" method, evaluates the transfer
/// function of each block. "flushPendingLocs" installs debug value instructions
/// for each live-in location at the start of blocks, while "Transfers" records
/// transfers of values between machine-locations.
///
/// We avoid explicitly representing the "Unknown" (\top) lattice value in the
/// implementation. Instead, unvisited blocks implicitly have all lattice
/// values set as "Unknown". After being visited, there will be path back to
/// the entry block where the lattice value is "False", and as the transfer
/// function cannot make new "Unknown" locations, there are no scenarios where
/// a block can have an "Unknown" location after being visited. Similarly, we
/// don't enumerate all possible variable locations before exploring the
/// function: when a new location is discovered, all blocks previously explored
/// were implicitly "False" but unrecorded, and become explicitly "False" when
/// a new VarLoc is created with its bit not set in predecessor InLocs or
/// OutLocs.
///
//===----------------------------------------------------------------------===//

#include "LiveDebugValues.h"

#include "llvm/ADT/CoalescingBitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/CodeGen/LexicalScopes.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.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/Debug.h"
#include "llvm/Support/TypeSize.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <map>
#include <optional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE

STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");

/// If \p Op is a stack or frame register return true, otherwise return false.
/// This is used to avoid basing the debug entry values on the registers, since
/// we do not support it at the moment.
static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
                                  const MachineInstr &MI,
                                  const TargetRegisterInfo *TRI) {}

namespace {

// Max out the number of statically allocated elements in DefinedRegsSet, as
// this prevents fallback to std::set::count() operations.
DefinedRegsSet;

// The IDs in this set correspond to MachineLocs in VarLocs, as well as VarLocs
// that represent Entry Values; every VarLoc in the set will also appear
// exactly once at Location=0.
// As a result, each VarLoc may appear more than once in this "set", but each
// range corresponding to a Reg, SpillLoc, or EntryValue type will still be a
// "true" set (i.e. each VarLoc may appear only once), and the range Location=0
// is the set of all VarLocs.
VarLocSet;

/// A type-checked pair of {Register Location (or 0), Index}, used to index
/// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int
/// for insertion into a \ref VarLocSet, and efficiently converted back. The
/// type-checker helps ensure that the conversions aren't lossy.
///
/// Why encode a location /into/ the VarLocMap index? This makes it possible
/// to find the open VarLocs killed by a register def very quickly. This is a
/// performance-critical operation for LiveDebugValues.
struct LocIndex {};

// Simple Set for storing all the VarLoc Indices at a Location bucket.
VarLocsInRange;
// Vector of all `LocIndex`s for a given VarLoc; the same Location should not
// appear in any two of these, as each VarLoc appears at most once in any
// Location bucket.
LocIndices;

class VarLocBasedLDV : public LDVImpl {};

} // end anonymous namespace

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

VarLocBasedLDV::VarLocBasedLDV() = default;

VarLocBasedLDV::~VarLocBasedLDV() = default;

/// Erase a variable from the set of open ranges, and additionally erase any
/// fragments that may overlap it. If the VarLoc is a backup location, erase
/// the variable from the EntryValuesBackupVars set, indicating we should stop
/// tracking its backup entry location. Otherwise, if the VarLoc is primary
/// location, erase the variable from the Vars set.
void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {}

void VarLocBasedLDV::OpenRangesSet::erase(const VarLocsInRange &KillSet,
                                          const VarLocMap &VarLocIDs,
                                          LocIndex::u32_location_t Location) {}

void VarLocBasedLDV::OpenRangesSet::insertFromLocSet(const VarLocSet &ToLoad,
                                                     const VarLocMap &Map) {}

void VarLocBasedLDV::OpenRangesSet::insert(LocIndices VarLocIDs,
                                           const VarLoc &VL) {}

/// Return the Loc ID of an entry value backup location, if it exists for the
/// variable.
std::optional<LocIndices>
VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {}

void VarLocBasedLDV::collectIDsForRegs(VarLocsInRange &Collected,
                                       const DefinedRegsSet &Regs,
                                       const VarLocSet &CollectFrom,
                                       const VarLocMap &VarLocIDs) {}

void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom,
                                 SmallVectorImpl<Register> &UsedRegs) const {}

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

#ifndef NDEBUG
void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF,
                                       const VarLocInMBB &V,
                                       const VarLocMap &VarLocIDs,
                                       const char *msg,
                                       raw_ostream &Out) const {
  Out << '\n' << msg << '\n';
  for (const MachineBasicBlock &BB : MF) {
    if (!V.count(&BB))
      continue;
    const VarLocSet &L = getVarLocsInMBB(&BB, V);
    if (L.empty())
      continue;
    SmallVector<VarLoc, 32> VarLocs;
    collectAllVarLocs(VarLocs, L, VarLocIDs);
    Out << "MBB: " << BB.getNumber() << ":\n";
    for (const VarLoc &VL : VarLocs) {
      Out << " Var: " << VL.Var.getVariable()->getName();
      Out << " MI: ";
      VL.dump(TRI, TII, Out);
    }
  }
  Out << "\n";
}
#endif

VarLocBasedLDV::VarLoc::SpillLoc
VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {}

/// Do cleanup of \p EntryValTransfers created by \p TRInst, by removing the
/// Transfer, which uses the to-be-deleted \p EntryVL.
void VarLocBasedLDV::cleanupEntryValueTransfers(
    const MachineInstr *TRInst, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
    const VarLoc &EntryVL, InstToEntryLocMap &EntryValTransfers) {}

/// Try to salvage the debug entry value if we encounter a new debug value
/// describing the same parameter, otherwise stop tracking the value. Return
/// true if we should stop tracking the entry value and do the cleanup of
/// emitted Entry Value Transfers, otherwise return false.
void VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
                                      OpenRangesSet &OpenRanges,
                                      VarLocMap &VarLocIDs,
                                      const VarLoc &EntryVL,
                                      InstToEntryLocMap &EntryValTransfers,
                                      RegDefToInstMap &RegSetInstrs) {}

/// End all previous ranges related to @MI and start a new range from @MI
/// if it is a DBG_VALUE instr.
void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
                                        OpenRangesSet &OpenRanges,
                                        VarLocMap &VarLocIDs,
                                        InstToEntryLocMap &EntryValTransfers,
                                        RegDefToInstMap &RegSetInstrs) {}

// This should be removed later, doesn't fit the new design.
void VarLocBasedLDV::collectAllVarLocs(SmallVectorImpl<VarLoc> &Collected,
                                       const VarLocSet &CollectFrom,
                                       const VarLocMap &VarLocIDs) {}

/// Turn the entry value backup locations into primary locations.
void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
                                     OpenRangesSet &OpenRanges,
                                     VarLocMap &VarLocIDs,
                                     InstToEntryLocMap &EntryValTransfers,
                                     VarLocsInRange &KillSet) {}

/// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
/// with \p OldVarID should be deleted form \p OpenRanges and replaced with
/// new VarLoc. If \p NewReg is different than default zero value then the
/// new location will be register location created by the copy like instruction,
/// otherwise it is variable's location on the stack.
void VarLocBasedLDV::insertTransferDebugPair(
    MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
    VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
    const VarLoc::MachineLoc &OldLoc, Register NewReg) {}

/// A definition of a register may mark the end of a range.
void VarLocBasedLDV::transferRegisterDef(MachineInstr &MI,
                                         OpenRangesSet &OpenRanges,
                                         VarLocMap &VarLocIDs,
                                         InstToEntryLocMap &EntryValTransfers,
                                         RegDefToInstMap &RegSetInstrs) {}

void VarLocBasedLDV::transferWasmDef(MachineInstr &MI,
                                     OpenRangesSet &OpenRanges,
                                     VarLocMap &VarLocIDs) {}

bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI,
                                         MachineFunction *MF) {}

bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI,
                                      MachineFunction *MF, Register &Reg) {}

std::optional<VarLocBasedLDV::VarLoc::SpillLoc>
VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI,
                                     MachineFunction *MF, Register &Reg) {}

/// A spilled register may indicate that we have to end the current range of
/// a variable and create a new one for the spill location.
/// A restored register may indicate the reverse situation.
/// We don't want to insert any instructions in process(), so we just create
/// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
/// It will be inserted into the BB when we're done iterating over the
/// instructions.
void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
                                                 OpenRangesSet &OpenRanges,
                                                 VarLocMap &VarLocIDs,
                                                 TransferMap &Transfers) {}

/// If \p MI is a register copy instruction, that copies a previously tracked
/// value from one register to another register that is callee saved, we
/// create new DBG_VALUE instruction  described with copy destination register.
void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
                                           OpenRangesSet &OpenRanges,
                                           VarLocMap &VarLocIDs,
                                           TransferMap &Transfers) {}

/// Terminate all open ranges at the end of the current basic block.
bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
                                         OpenRangesSet &OpenRanges,
                                         VarLocInMBB &OutLocs,
                                         const VarLocMap &VarLocIDs) {}

/// 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_VALUE instruction to analyze for
///           fragment usage.
/// \param SeenFragments Map from DILocalVariable to all fragments of that
///           Variable which are known to exist.
/// \param OverlappingFragments The overlap map being constructed, from one
///           Var/Fragment pair to a vector of fragments known to overlap.
void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI,
                                            VarToFragments &SeenFragments,
                                            OverlapMap &OverlappingFragments) {}

/// This routine creates OpenRanges.
void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
                             VarLocMap &VarLocIDs, TransferMap &Transfers,
                             InstToEntryLocMap &EntryValTransfers,
                             RegDefToInstMap &RegSetInstrs) {}

/// This routine joins the analysis results of all incoming edges in @MBB by
/// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
/// source variable in all the predecessors of @MBB reside in the same location.
bool VarLocBasedLDV::join(
    MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
    const VarLocMap &VarLocIDs,
    SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
    SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {}

void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                       VarLocMap &VarLocIDs) {}

bool VarLocBasedLDV::isEntryValueCandidate(
    const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const {}

/// Collect all register defines (including aliases) for the given instruction.
static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs,
                           const TargetRegisterInfo *TRI) {}

/// This routine records the entry values of function parameters. The values
/// could be used as backup values. If we loose the track of some unmodified
/// parameters, the backup values will be used as a primary locations.
void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
                                       const DefinedRegsSet &DefinedRegs,
                                       OpenRangesSet &OpenRanges,
                                       VarLocMap &VarLocIDs) {}

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

LDVImpl *
llvm::makeVarLocBasedLiveDebugValues()
{}