#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/Intrinsics.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>

Classes
struct	llvm::DenseMapInfo< VariableID >

struct	std::hash< VarLocInsertPt >

class	FunctionVarLocsBuilder
	Helper class to build FunctionVarLocs, since that class isn't easy to modify. More...

Namespaces
namespace	std
	Implement std::hash so that hash_code can be used in STL containers.

Macros
#define	DEBUG_TYPE "debug-ata"

Typedefs
using	VarLocInsertPt = PointerUnion< const Instruction , const DbgRecord >

using	DebugAggregate = std::pair< const DILocalVariable , const DILocation >
	A whole (unfragmented) source variable.

Functions
	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 std::pair< Value , DIExpression >	walkToAllocaAndPrependOffsetDeref (const DataLayout &DL, Value Start, DIExpression Expression)
	Walk backwards along constant GEPs and bitcasts to the base storage from `Start` as far as possible.

static std::optional< int64_t >	getDerefOffsetInBytes (const DIExpression *DIExpr)
	Extract the offset used in `DIExpr`.

static DebugAggregate	getAggregate (const DebugVariable &Var)

static bool	shouldCoalesceFragments (Function &F)

static DIAssignID *	getIDFromInst (const Instruction &I)

static DIAssignID *	getIDFromMarker (const DbgVariableRecord &DVR)

const char *	locStr (AssignmentTrackingLowering::LocKind Loc)

VarLocInsertPt	getNextNode (const DbgRecord *DVR)

VarLocInsertPt	getNextNode (const Instruction *Inst)

VarLocInsertPt	getNextNode (VarLocInsertPt InsertPt)

static bool	hasZeroSizedFragment (DbgVariableRecord &DbgValue)

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

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

AllocaInst *	getUnknownStore (const Instruction &I, const DataLayout &Layout)

static AssignmentTrackingLowering::OverlapMap	buildOverlapMapAndRecordDeclares (Function &Fn, FunctionVarLocsBuilder *FnVarLocs, const DenseSet< DebugAggregate > &VarsWithStackSlot, AssignmentTrackingLowering::UntaggedStoreAssignmentMap &UntaggedStoreVars, AssignmentTrackingLowering::UnknownStoreAssignmentMap &UnknownStoreVars, unsigned &TrackedVariablesVectorSize)
	Build a map of {Variable x: Variables y} where all variable fragments contained within the variable fragment x are in set y.

static bool	removeRedundantDbgLocsUsingBackwardScan (const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
	Remove redundant definitions within sequences of consecutive location defs.

static bool	removeRedundantDbgLocsUsingForwardScan (const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
	Remove redundant location defs using a forward scan.

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)

Variables
static cl::opt< unsigned >	MaxNumBlocks ("debug-ata-max-blocks", cl::init(10000), cl::desc("Maximum num basic blocks before debug info dropped"), cl::Hidden)

static cl::opt< bool >	EnableMemLocFragFill ("mem-loc-frag-fill", cl::init(true), cl::Hidden)
	Option for debugging the pass, determines if the memory location fragment filling happens after generating the variable locations.

static cl::opt< bool >	PrintResults ("print-debug-ata", cl::init(false), cl::Hidden)
	Print the results of the analysis. Respects -filter-print-funcs.

static cl::opt< cl::boolOrDefault >	CoalesceAdjacentFragmentsOpt ("debug-ata-coalesce-frags", cl::Hidden)
	Coalesce adjacent dbg locs describing memory locations that have contiguous fragments.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "debug-ata"

Definition at line 43 of file AssignmentTrackingAnalysis.cpp.

Typedef Documentation

◆ DebugAggregate

using DebugAggregate = std::pair<const DILocalVariable *, const DILocation *>

A whole (unfragmented) source variable.

Definition at line 330 of file AssignmentTrackingAnalysis.cpp.

◆ VarLocInsertPt

using VarLocInsertPt = PointerUnion<const Instruction *, const DbgRecord *>

Definition at line 86 of file AssignmentTrackingAnalysis.cpp.

Function Documentation

◆ analyzeFunction()

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

static

Definition at line 2736 of file AssignmentTrackingAnalysis.cpp.

References findVarsWithStackSlot(), removeRedundantDbgLocs(), and shouldCoalesceFragments().

Referenced by llvm::DebugAssignmentTrackingAnalysis::run(), and llvm::AssignmentTrackingAnalysis::runOnFunction().

◆ buildOverlapMapAndRecordDeclares()

static AssignmentTrackingLowering::OverlapMap buildOverlapMapAndRecordDeclares	(	Function &	Fn,
		FunctionVarLocsBuilder *	FnVarLocs,
		const DenseSet< DebugAggregate > &	VarsWithStackSlot,
		AssignmentTrackingLowering::UntaggedStoreAssignmentMap &	UntaggedStoreVars,
		AssignmentTrackingLowering::UnknownStoreAssignmentMap &	UnknownStoreVars,
		unsigned &	TrackedVariablesVectorSize
	)

static

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 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, and UnknownStoreVars with a mapping of untagged unknown stores to the stored-to variable aggregates.

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.

Definition at line 2119 of file AssignmentTrackingAnalysis.cpp.

References FunctionVarLocsBuilder::addSingleLocVar(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::at::calculateFragmentIntersect(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::filterDbgVars(), fullyContains(), llvm::Function::getDataLayout(), llvm::DbgRecord::getDebugLoc(), llvm::at::getDVRAssignmentMarkers(), llvm::DbgVariableRecord::getExpression(), llvm::DebugVariable::getInlinedAt(), FunctionVarLocsBuilder::getNumVariables(), llvm::DbgVariableRecord::getRawLocation(), getUnknownStore(), getUntaggedStoreAssignmentInfo(), llvm::DebugVariable::getVariable(), I, Info, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), FunctionVarLocsBuilder::insertVariable(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

◆ findVarsWithStackSlot()

static DenseSet< DebugAggregate > findVarsWithStackSlot ( Function & Fn )

static

Definition at line 2719 of file AssignmentTrackingAnalysis.cpp.

References llvm::DbgRecord::getDebugLoc(), llvm::at::getDVRAssignmentMarkers(), llvm::DebugLoc::getInlinedAt(), llvm::DbgVariableRecord::getVariable(), and I.

Referenced by analyzeFunction().

◆ fullyContains()

static bool fullyContains	(	DIExpression::FragmentInfo	A,
		DIExpression::FragmentInfo	B
	)

static

Return true if A fully contains B.

Definition at line 2053 of file AssignmentTrackingAnalysis.cpp.

References A, and B.

Referenced by buildOverlapMapAndRecordDeclares().

◆ getAggregate()

static DebugAggregate getAggregate ( const DebugVariable & Var )

static

Definition at line 331 of file AssignmentTrackingAnalysis.cpp.

References llvm::DebugVariable::getInlinedAt(), and llvm::DebugVariable::getVariable().

Referenced by removeRedundantDbgLocsUsingBackwardScan().

◆ getDerefOffsetInBytes()

static std::optional< int64_t > getDerefOffsetInBytes ( const DIExpression * DIExpr )

static

Extract the offset used in 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.

Definition at line 288 of file AssignmentTrackingAnalysis.cpp.

References llvm::dwarf::DW_OP_LLVM_fragment, llvm::DIExpression::getElements(), llvm::DIExpression::getNumElements(), and llvm::Offset.

◆ getIDFromInst()

static DIAssignID * getIDFromInst ( const Instruction & I )

static

Definition at line 1428 of file AssignmentTrackingAnalysis.cpp.

References I.

◆ getIDFromMarker()

static DIAssignID * getIDFromMarker ( const DbgVariableRecord & DVR )

static

Definition at line 1432 of file AssignmentTrackingAnalysis.cpp.

References assert(), llvm::DbgVariableRecord::getAssignID(), and llvm::DbgVariableRecord::isDbgAssign().

◆ getNextNode() [1/3]

VarLocInsertPt getNextNode ( const DbgRecord * DVR )

Definition at line 1468 of file AssignmentTrackingAnalysis.cpp.

References llvm::DbgMarker::getDbgRecordRange(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::DbgRecord::getMarker(), and llvm::DbgMarker::MarkedInstr.

Referenced by getNextNode().

◆ getNextNode() [2/3]

VarLocInsertPt getNextNode ( const Instruction * Inst )

Definition at line 1474 of file AssignmentTrackingAnalysis.cpp.

References llvm::Instruction::getDbgRecordRange(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getNextNode(), and llvm::Instruction::hasDbgRecords().

◆ getNextNode() [3/3]

VarLocInsertPt getNextNode ( VarLocInsertPt InsertPt )

Definition at line 1480 of file AssignmentTrackingAnalysis.cpp.

References getNextNode().

◆ getUnknownStore()

AllocaInst * getUnknownStore	(	const Instruction &	I,
		const DataLayout &	Layout
	)

Definition at line 2080 of file AssignmentTrackingAnalysis.cpp.

References llvm::sampleprof::Base, llvm::DataLayout::getIndexTypeSizeInBits(), I, II, and llvm::Offset.

Referenced by buildOverlapMapAndRecordDeclares().

◆ getUntaggedStoreAssignmentInfo()

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

static

Definition at line 2068 of file AssignmentTrackingAnalysis.cpp.

References llvm::at::getAssignmentInfo(), I, and MI.

Referenced by buildOverlapMapAndRecordDeclares().

◆ hasZeroSizedFragment()

static bool hasZeroSizedFragment ( DbgVariableRecord & DbgValue )

static

Definition at line 1832 of file AssignmentTrackingAnalysis.cpp.

References F.

◆ locStr()

const char * locStr ( AssignmentTrackingLowering::LocKind Loc )

Definition at line 1454 of file AssignmentTrackingAnalysis.cpp.

References llvm_unreachable.

◆ removeRedundantDbgLocs()

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

static

Definition at line 2705 of file AssignmentTrackingAnalysis.cpp.

References llvm::dbgs(), llvm::Value::getName(), llvm::BasicBlock::isEntryBlock(), LLVM_DEBUG, removeRedundantDbgLocsUsingBackwardScan(), removeRedundantDbgLocsUsingForwardScan(), and removeUndefDbgLocsFromEntryBlock().

Referenced by analyzeFunction().

◆ removeRedundantDbgLocsUsingBackwardScan()

static bool removeRedundantDbgLocsUsingBackwardScan	(	const BasicBlock *	BB,
		FunctionVarLocsBuilder &	FnVarLocs
	)

static

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.

Definition at line 2466 of file AssignmentTrackingAnalysis.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::divideCeil(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::DbgVariableFragmentInfo::endInBits(), llvm::filterDbgVars(), llvm::BitVector::find_first_unset_in(), getAggregate(), FunctionVarLocsBuilder::getVariable(), FunctionVarLocsBuilder::getWedge(), I, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::reverse(), llvm::BitVector::set(), FunctionVarLocsBuilder::setWedge(), llvm::DbgVariableFragmentInfo::startInBits(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Referenced by removeRedundantDbgLocs().

◆ removeRedundantDbgLocsUsingForwardScan()

static bool removeRedundantDbgLocsUsingForwardScan	(	const BasicBlock *	BB,
		FunctionVarLocsBuilder &	FnVarLocs
	)

static

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

Definition at line 2562 of file AssignmentTrackingAnalysis.cpp.

References llvm::filterDbgVars(), llvm::DebugVariable::getVariable(), FunctionVarLocsBuilder::getVariable(), FunctionVarLocsBuilder::getWedge(), I, llvm::SmallVectorTemplateBase< T, bool >::push_back(), FunctionVarLocsBuilder::setWedge(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Referenced by removeRedundantDbgLocs().

◆ removeUndefDbgLocsFromEntryBlock()

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

static

Definition at line 2621 of file AssignmentTrackingAnalysis.cpp.

References A, llvm::any_of(), assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::filterDbgVars(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::DebugVariable::getVariable(), FunctionVarLocsBuilder::getVariable(), FunctionVarLocsBuilder::getWedge(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::BasicBlock::isEntryBlock(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and FunctionVarLocsBuilder::setWedge().

Referenced by removeRedundantDbgLocs().

◆ shouldCoalesceFragments()

static bool shouldCoalesceFragments ( Function & F )

static

Definition at line 335 of file AssignmentTrackingAnalysis.cpp.

References llvm::cl::BOU_FALSE, llvm::cl::BOU_TRUE, llvm::cl::BOU_UNSET, CoalesceAdjacentFragmentsOpt, llvm::debuginfoShouldUseDebugInstrRef(), F, and llvm_unreachable.

Referenced by analyzeFunction().

◆ STATISTIC() [1/4]

STATISTIC	(	NumDefsRemoved	,
		"Number of dbg locs removed"
	)

◆ STATISTIC() [2/4]

STATISTIC	(	NumDefsScanned	,
		"Number of dbg locs that get scanned for removal"
	)

◆ STATISTIC() [3/4]

STATISTIC	(	NumWedgesChanged	,
		"Number of dbg wedges changed"
	)

◆ STATISTIC() [4/4]

STATISTIC	(	NumWedgesScanned	,
		"Number of dbg wedges scanned"
	)

◆ walkToAllocaAndPrependOffsetDeref()

static std::pair< Value , DIExpression > walkToAllocaAndPrependOffsetDeref	(	const DataLayout &	DL,
		Value *	Start,
		DIExpression *	Expression
	)

static

Walk backwards along constant GEPs and bitcasts to the base storage from 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.

Definition at line 269 of file AssignmentTrackingAnalysis.cpp.

References llvm::DIExpression::append(), DL, End, llvm::APInt::getBoolValue(), llvm::APInt::getZExtValue(), and llvm::DIExpression::prependOpcodes().

Variable Documentation

◆ CoalesceAdjacentFragmentsOpt

cl::opt< cl::boolOrDefault > CoalesceAdjacentFragmentsOpt("debug-ata-coalesce-frags", cl::Hidden)	(	"debug-ata-coalesce-frags"	,
		cl::Hidden
	)

static

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.

Referenced by shouldCoalesceFragments().

◆ EnableMemLocFragFill

cl::opt< bool > EnableMemLocFragFill("mem-loc-frag-fill", cl::init(true), cl::Hidden)	(	"mem-loc-frag-fill"	,
		cl::init(true)	,
		cl::Hidden
	)

static

Option for debugging the pass, determines if the memory location fragment filling happens after generating the variable locations.

◆ MaxNumBlocks

cl::opt< unsigned > MaxNumBlocks("debug-ata-max-blocks", cl::init(10000), cl::desc("Maximum num basic blocks before debug info dropped"), cl::Hidden)	(	"debug-ata-max-blocks"	,
		cl::init(10000)	,
		cl::desc("Maximum num basic blocks before debug info dropped")	,
		cl::Hidden
	)

static

◆ PrintResults

cl::opt< bool > PrintResults("print-debug-ata", cl::init(false), cl::Hidden)	(	"print-debug-ata"	,
		cl::init(false)	,
		cl::Hidden
	)

static

Print the results of the analysis. Respects -filter-print-funcs.

Referenced by llvm::AssignmentTrackingAnalysis::runOnFunction().

Classes

Namespaces

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ DebugAggregate

◆ VarLocInsertPt

Function Documentation

◆ analyzeFunction()

◆ buildOverlapMapAndRecordDeclares()

◆ findVarsWithStackSlot()

◆ fullyContains()

◆ getAggregate()

◆ getDerefOffsetInBytes()

◆ getIDFromInst()

◆ getIDFromMarker()

◆ getNextNode() [1/3]

◆ getNextNode() [2/3]

◆ getNextNode() [3/3]

◆ getUnknownStore()

◆ getUntaggedStoreAssignmentInfo()

◆ hasZeroSizedFragment()

◆ locStr()

◆ removeRedundantDbgLocs()

◆ removeRedundantDbgLocsUsingBackwardScan()

◆ removeRedundantDbgLocsUsingForwardScan()

◆ removeUndefDbgLocsFromEntryBlock()

◆ shouldCoalesceFragments()

◆ STATISTIC() [1/4]

◆ STATISTIC() [2/4]

◆ STATISTIC() [3/4]

◆ STATISTIC() [4/4]

◆ walkToAllocaAndPrependOffsetDeref()

Variable Documentation

◆ CoalesceAdjacentFragmentsOpt

◆ EnableMemLocFragFill

◆ MaxNumBlocks

◆ PrintResults