AssignmentTrackingAnalysis.cpp | Explore in Territory

//===-- AssignmentTrackingAnalysis.cpp ------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/AssignmentTrackingAnalysis.h"
#include "LiveDebugValues/LiveDebugValues.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/UniqueVector.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DebugProgramInstruction.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PrintPasses.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include <assert.h>
#include <cstdint>
#include <optional>
#include <queue>
#include <sstream>
#include <unordered_map>

usingnamespacellvm;
#define DEBUG_TYPE …

STATISTIC(NumDefsScanned, "Number of dbg locs that get scanned for removal");
STATISTIC(NumDefsRemoved, "Number of dbg locs removed");
STATISTIC(NumWedgesScanned, "Number of dbg wedges scanned");
STATISTIC(NumWedgesChanged, "Number of dbg wedges changed");

static cl::opt<unsigned>
    MaxNumBlocks("debug-ata-max-blocks", cl::init(10000),
                 cl::desc("Maximum num basic blocks before debug info dropped"),
                 cl::Hidden);
/// Option for debugging the pass, determines if the memory location fragment
/// filling happens after generating the variable locations.
static cl::opt<bool> EnableMemLocFragFill("mem-loc-frag-fill", cl::init(true),
                                          cl::Hidden);
/// Print the results of the analysis. Respects -filter-print-funcs.
static cl::opt<bool> PrintResults("print-debug-ata", cl::init(false),
                                  cl::Hidden);

/// Coalesce adjacent dbg locs describing memory locations that have contiguous
/// fragments. This reduces the cost of LiveDebugValues which does SSA
/// construction for each explicitly stated variable fragment.
static cl::opt<cl::boolOrDefault>
    CoalesceAdjacentFragmentsOpt("debug-ata-coalesce-frags", cl::Hidden);

// Implicit conversions are disabled for enum class types, so unfortunately we
// need to create a DenseMapInfo wrapper around the specified underlying type.
template <> struct llvm::DenseMapInfo<VariableID> { … };

VarLocInsertPt;

namespace std {
template <> struct hash<VarLocInsertPt> { … };
} // namespace std

/// Helper class to build FunctionVarLocs, since that class isn't easy to
/// modify. TODO: There's not a great deal of value in the split, it could be
/// worth merging the two classes.
class FunctionVarLocsBuilder { … };

void FunctionVarLocs::print(raw_ostream &OS, const Function &Fn) const { … }

void FunctionVarLocs::init(FunctionVarLocsBuilder &Builder) { … }

void FunctionVarLocs::clear() { … }

/// Walk backwards along constant GEPs and bitcasts to the base storage from \p
/// Start as far as possible. Prepend \Expression with the offset and append it
/// with a DW_OP_deref that haes been implicit until now. Returns the walked-to
/// value and modified expression.
static std::pair<Value *, DIExpression *>
walkToAllocaAndPrependOffsetDeref(const DataLayout &DL, Value *Start,
                                  DIExpression *Expression) { … }

/// Extract the offset used in \p DIExpr. Returns std::nullopt if the expression
/// doesn't explicitly describe a memory location with DW_OP_deref or if the
/// expression is too complex to interpret.
static std::optional<int64_t>
getDerefOffsetInBytes(const DIExpression *DIExpr) { … }

/// A whole (unfragmented) source variable.
DebugAggregate;
static DebugAggregate getAggregate(const DbgVariableIntrinsic *DII) { … }
static DebugAggregate getAggregate(const DebugVariable &Var) { … }

static bool shouldCoalesceFragments(Function &F) { … }

namespace {
/// In dwarf emission, the following sequence
///    1. dbg.value ... Fragment(0, 64)
///    2. dbg.value ... Fragment(0, 32)
/// effectively sets Fragment(32, 32) to undef (each def sets all bits not in
/// the intersection of the fragments to having "no location"). This makes
/// sense for implicit location values because splitting the computed values
/// could be troublesome, and is probably quite uncommon.  When we convert
/// dbg.assigns to dbg.value+deref this kind of thing is common, and describing
/// a location (memory) rather than a value means we don't need to worry about
/// splitting any values, so we try to recover the rest of the fragment
/// location here.
/// This class performs a(nother) dataflow analysis over the function, adding
/// variable locations so that any bits of a variable with a memory location
/// have that location explicitly reinstated at each subsequent variable
/// location definition that that doesn't overwrite those bits. i.e. after a
/// variable location def, insert new defs for the memory location with
/// fragments for the difference of "all bits currently in memory" and "the
/// fragment of the second def".
class MemLocFragmentFill { … };

/// AssignmentTrackingLowering encapsulates a dataflow analysis over a function
/// that interprets assignment tracking debug info metadata and stores in IR to
/// create a map of variable locations.
class AssignmentTrackingLowering { … };
} // namespace

ArrayRef<VariableID>
AssignmentTrackingLowering::getContainedFragments(VariableID Var) const { … }

void AssignmentTrackingLowering::touchFragment(VariableID Var) { … }

void AssignmentTrackingLowering::setLocKind(BlockInfo *LiveSet, VariableID Var,
                                            LocKind K) { … }

AssignmentTrackingLowering::LocKind
AssignmentTrackingLowering::getLocKind(BlockInfo *LiveSet, VariableID Var) { … }

void AssignmentTrackingLowering::addMemDef(BlockInfo *LiveSet, VariableID Var,
                                           const Assignment &AV) { … }

void AssignmentTrackingLowering::addDbgDef(BlockInfo *LiveSet, VariableID Var,
                                           const Assignment &AV) { … }

static DIAssignID *getIDFromInst(const Instruction &I) { … }

static DIAssignID *getIDFromMarker(const DbgAssignIntrinsic &DAI) { … }

static DIAssignID *getIDFromMarker(const DbgVariableRecord &DVR) { … }

/// Return true if \p Var has an assignment in \p M matching \p AV.
bool AssignmentTrackingLowering::hasVarWithAssignment(
    BlockInfo *LiveSet, BlockInfo::AssignmentKind Kind, VariableID Var,
    const Assignment &AV) { … }

#ifndef NDEBUG
const char *locStr(AssignmentTrackingLowering::LocKind Loc) {
  using LocKind = AssignmentTrackingLowering::LocKind;
  switch (Loc) {
  case LocKind::Val:
    return "Val";
  case LocKind::Mem:
    return "Mem";
  case LocKind::None:
    return "None";
  };
  llvm_unreachable("unknown LocKind");
}
#endif

VarLocInsertPt getNextNode(const DbgRecord *DVR) { … }
VarLocInsertPt getNextNode(const Instruction *Inst) { … }
VarLocInsertPt getNextNode(VarLocInsertPt InsertPt) { … }

DbgAssignIntrinsic *CastToDbgAssign(DbgVariableIntrinsic *DVI) { … }

DbgVariableRecord *CastToDbgAssign(DbgVariableRecord *DVR) { … }

void AssignmentTrackingLowering::emitDbgValue(
    AssignmentTrackingLowering::LocKind Kind,
    AssignmentTrackingLowering::AssignRecord Source, VarLocInsertPt After) { … }
template <typename T>
void AssignmentTrackingLowering::emitDbgValue(
    AssignmentTrackingLowering::LocKind Kind, const T Source,
    VarLocInsertPt After) { … }

void AssignmentTrackingLowering::processNonDbgInstruction(
    Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) { … }

void AssignmentTrackingLowering::processUntaggedInstruction(
    Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) { … }

void AssignmentTrackingLowering::processTaggedInstruction(
    Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) { … }

void AssignmentTrackingLowering::processDbgAssign(AssignRecord Assign,
                                                  BlockInfo *LiveSet) { … }

void AssignmentTrackingLowering::processDbgValue(
    PointerUnion<DbgValueInst *, DbgVariableRecord *> DbgValueRecord,
    BlockInfo *LiveSet) { … }

template <typename T> static bool hasZeroSizedFragment(T &DbgValue) { … }

void AssignmentTrackingLowering::processDbgInstruction(
    DbgInfoIntrinsic &I, AssignmentTrackingLowering::BlockInfo *LiveSet) { … }
void AssignmentTrackingLowering::processDbgVariableRecord(
    DbgVariableRecord &DVR, AssignmentTrackingLowering::BlockInfo *LiveSet) { … }

void AssignmentTrackingLowering::resetInsertionPoint(Instruction &After) { … }
void AssignmentTrackingLowering::resetInsertionPoint(DbgVariableRecord &After) { … }

void AssignmentTrackingLowering::process(BasicBlock &BB, BlockInfo *LiveSet) { … }

AssignmentTrackingLowering::LocKind
AssignmentTrackingLowering::joinKind(LocKind A, LocKind B) { … }

AssignmentTrackingLowering::Assignment
AssignmentTrackingLowering::joinAssignment(const Assignment &A,
                                           const Assignment &B) { … }

AssignmentTrackingLowering::BlockInfo
AssignmentTrackingLowering::joinBlockInfo(const BlockInfo &A,
                                          const BlockInfo &B) { … }

bool AssignmentTrackingLowering::join(
    const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited) { … }

/// Return true if A fully contains B.
static bool fullyContains(DIExpression::FragmentInfo A,
                          DIExpression::FragmentInfo B) { … }

static std::optional<at::AssignmentInfo>
getUntaggedStoreAssignmentInfo(const Instruction &I, const DataLayout &Layout) { … }

DbgDeclareInst *DynCastToDbgDeclare(DbgVariableIntrinsic *DVI) { … }

DbgVariableRecord *DynCastToDbgDeclare(DbgVariableRecord *DVR) { … }

/// Build a map of {Variable x: Variables y} where all variable fragments
/// contained within the variable fragment x are in set y. This means that
/// y does not contain all overlaps because partial overlaps are excluded.
///
/// While we're iterating over the function, add single location defs for
/// dbg.declares to \p FnVarLocs.
///
/// Variables that are interesting to this pass in are added to
/// FnVarLocs->Variables first. TrackedVariablesVectorSize is set to the ID of
/// the last interesting variable plus 1, meaning variables with ID 1
/// (inclusive) to TrackedVariablesVectorSize (exclusive) are interesting. The
/// subsequent variables are either stack homed or fully promoted.
///
/// Finally, populate UntaggedStoreVars with a mapping of untagged stores to
/// the stored-to variable fragments.
///
/// These tasks are bundled together to reduce the number of times we need
/// to iterate over the function as they can be achieved together in one pass.
static AssignmentTrackingLowering::OverlapMap buildOverlapMapAndRecordDeclares(
    Function &Fn, FunctionVarLocsBuilder *FnVarLocs,
    const DenseSet<DebugAggregate> &VarsWithStackSlot,
    AssignmentTrackingLowering::UntaggedStoreAssignmentMap &UntaggedStoreVars,
    unsigned &TrackedVariablesVectorSize) { … }

bool AssignmentTrackingLowering::run(FunctionVarLocsBuilder *FnVarLocsBuilder) { … }

bool AssignmentTrackingLowering::emitPromotedVarLocs(
    FunctionVarLocsBuilder *FnVarLocs) { … }

/// Remove redundant definitions within sequences of consecutive location defs.
/// This is done using a backward scan to keep the last def describing a
/// specific variable/fragment.
///
/// This implements removeRedundantDbgInstrsUsingBackwardScan from
/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
/// FunctionVarLocsBuilder instead of with intrinsics.
static bool
removeRedundantDbgLocsUsingBackwardScan(const BasicBlock *BB,
                                        FunctionVarLocsBuilder &FnVarLocs) { … }

/// Remove redundant location defs using a forward scan. This can remove a
/// location definition that is redundant due to indicating that a variable has
/// the same value as is already being indicated by an earlier def.
///
/// This implements removeRedundantDbgInstrsUsingForwardScan from
/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
/// FunctionVarLocsBuilder instead of with intrinsics
static bool
removeRedundantDbgLocsUsingForwardScan(const BasicBlock *BB,
                                       FunctionVarLocsBuilder &FnVarLocs) { … }

static bool
removeUndefDbgLocsFromEntryBlock(const BasicBlock *BB,
                                 FunctionVarLocsBuilder &FnVarLocs) { … }

static bool removeRedundantDbgLocs(const BasicBlock *BB,
                                   FunctionVarLocsBuilder &FnVarLocs) { … }

static DenseSet<DebugAggregate> findVarsWithStackSlot(Function &Fn) { … }

static void analyzeFunction(Function &Fn, const DataLayout &Layout,
                            FunctionVarLocsBuilder *FnVarLocs) { … }

FunctionVarLocs
DebugAssignmentTrackingAnalysis::run(Function &F,
                                     FunctionAnalysisManager &FAM) { … }

AnalysisKey DebugAssignmentTrackingAnalysis::Key;

PreservedAnalyses
DebugAssignmentTrackingPrinterPass::run(Function &F,
                                        FunctionAnalysisManager &FAM) { … }

bool AssignmentTrackingAnalysis::runOnFunction(Function &F) { … }

AssignmentTrackingAnalysis::AssignmentTrackingAnalysis()
    : … { … }

char AssignmentTrackingAnalysis::ID = …;

INITIALIZE_PASS(…)
llvm/llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp
