Statistics.cpp

//===-- Statistics.cpp - Debug Info quality metrics -----------------------===//
//
// 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-dwarfdump.h"
#include"llvm/ADT/DenseMap.h"
#include"llvm/ADT/StringSet.h"
#include"llvm/DebugInfo/DWARF/DWARFContext.h"
#include"llvm/DebugInfo/DWARF/DWARFDebugLoc.h"
#include"llvm/DebugInfo/DWARF/DWARFExpression.h"
#include"llvm/Object/ObjectFile.h"
#include"llvm/Support/JSON.h"

#defineDEBUG_TYPE"dwarfdump"
usingnamespacellvm;
usingnamespacellvm::dwarfdump;
usingnamespacellvm::object;

namespace {
/// This represents the number of categories of debug location coverage being
/// calculated. The first category is the number of variables with 0% location
/// coverage, but the last category is the number of variables with 100%
/// location coverage.
constexprint NumOfCoverageCategories = 12;

/// This is used for zero location coverage bucket.
constexprunsigned ZeroCoverageBucket = 0;

/// The UINT64_MAX is used as an indication of the overflow.
constexpruint64_t OverflowValue = std::numeric_limits<uint64_t>::max();

/// This represents variables DIE offsets.
using AbstractOriginVarsTy = llvm::SmallVector<uint64_t>;
/// This maps function DIE offset to its variables.
using AbstractOriginVarsTyMap = llvm::DenseMap<uint64_t, AbstractOriginVarsTy>;
/// This represents function DIE offsets containing an abstract_origin.
using FunctionsWithAbstractOriginTy = llvm::SmallVector<uint64_t>;

/// This represents a data type for the stats and it helps us to
/// detect an overflow.
/// NOTE: This can be implemented as a template if there is an another type
/// needing this.
structSaturatingUINT64 {
/// Number that represents the stats.
uint64_t Value;

SaturatingUINT64(uint64_t Value_) : Value(Value_) {}

voidoperator++(int) { return *this += 1; }
voidoperator+=(uint64_t Value_) {
if (Value != OverflowValue) {
if (Value < OverflowValue - Value_)
 Value += Value_;
else
 Value = OverflowValue;
 }
 }
};

/// Utility struct to store the full location of a DIE - its CU and offset.
structDIELocation {
 DWARFUnit *DwUnit;
uint64_t DIEOffset;
DIELocation(DWARFUnit *_DwUnit, uint64_t _DIEOffset)
 : DwUnit(_DwUnit), DIEOffset(_DIEOffset) {}
};
/// This represents DWARF locations of CrossCU referencing DIEs.
using CrossCUReferencingDIELocationTy = llvm::SmallVector<DIELocation>;

/// This maps function DIE offset to its DWARF CU.
using FunctionDIECUTyMap = llvm::DenseMap<uint64_t, DWARFUnit *>;

/// Holds statistics for one function (or other entity that has a PC range and
/// contains variables, such as a compile unit).
structPerFunctionStats {
/// Number of inlined instances of this function.
uint64_t NumFnInlined = 0;
/// Number of out-of-line instances of this function.
uint64_t NumFnOutOfLine = 0;
/// Number of inlined instances that have abstract origins.
uint64_t NumAbstractOrigins = 0;
/// Number of variables and parameters with location across all inlined
/// instances.
uint64_t TotalVarWithLoc = 0;
/// Number of constants with location across all inlined instances.
uint64_t ConstantMembers = 0;
/// Number of arificial variables, parameters or members across all instances.
uint64_t NumArtificial = 0;
/// List of all Variables and parameters in this function.
 StringSet<> VarsInFunction;
/// Compile units also cover a PC range, but have this flag set to false.
bool IsFunction = false;
/// Function has source location information.
bool HasSourceLocation = false;
/// Number of function parameters.
uint64_t NumParams = 0;
/// Number of function parameters with source location.
uint64_t NumParamSourceLocations = 0;
/// Number of function parameters with type.
uint64_t NumParamTypes = 0;
/// Number of function parameters with a DW_AT_location.
uint64_t NumParamLocations = 0;
/// Number of local variables.
uint64_t NumLocalVars = 0;
/// Number of local variables with source location.
uint64_t NumLocalVarSourceLocations = 0;
/// Number of local variables with type.
uint64_t NumLocalVarTypes = 0;
/// Number of local variables with DW_AT_location.
uint64_t NumLocalVarLocations = 0;
};

/// Holds accumulated global statistics about DIEs.
structGlobalStats {
/// Total number of PC range bytes covered by DW_AT_locations.
 SaturatingUINT64 TotalBytesCovered = 0;
/// Total number of parent DIE PC range bytes covered by DW_AT_Locations.
 SaturatingUINT64 ScopeBytesCovered = 0;
/// Total number of PC range bytes in each variable's enclosing scope.
 SaturatingUINT64 ScopeBytes = 0;
/// Total number of PC range bytes covered by DW_AT_locations with
/// the debug entry values (DW_OP_entry_value).
 SaturatingUINT64 ScopeEntryValueBytesCovered = 0;
/// Total number of PC range bytes covered by DW_AT_locations of
/// formal parameters.
 SaturatingUINT64 ParamScopeBytesCovered = 0;
/// Total number of PC range bytes in each parameter's enclosing scope.
 SaturatingUINT64 ParamScopeBytes = 0;
/// Total number of PC range bytes covered by DW_AT_locations with
/// the debug entry values (DW_OP_entry_value) (only for parameters).
 SaturatingUINT64 ParamScopeEntryValueBytesCovered = 0;
/// Total number of PC range bytes covered by DW_AT_locations (only for local
/// variables).
 SaturatingUINT64 LocalVarScopeBytesCovered = 0;
/// Total number of PC range bytes in each local variable's enclosing scope.
 SaturatingUINT64 LocalVarScopeBytes = 0;
/// Total number of PC range bytes covered by DW_AT_locations with
/// the debug entry values (DW_OP_entry_value) (only for local variables).
 SaturatingUINT64 LocalVarScopeEntryValueBytesCovered = 0;
/// Total number of call site entries (DW_AT_call_file & DW_AT_call_line).
 SaturatingUINT64 CallSiteEntries = 0;
/// Total number of call site DIEs (DW_TAG_call_site).
 SaturatingUINT64 CallSiteDIEs = 0;
/// Total number of call site parameter DIEs (DW_TAG_call_site_parameter).
 SaturatingUINT64 CallSiteParamDIEs = 0;
/// Total byte size of concrete functions. This byte size includes
/// inline functions contained in the concrete functions.
 SaturatingUINT64 FunctionSize = 0;
/// Total byte size of inlined functions. This is the total number of bytes
/// for the top inline functions within concrete functions. This can help
/// tune the inline settings when compiling to match user expectations.
 SaturatingUINT64 InlineFunctionSize = 0;
};

/// Holds accumulated debug location statistics about local variables and
/// formal parameters.
structLocationStats {
/// Map the scope coverage decile to the number of variables in the decile.
/// The first element of the array (at the index zero) represents the number
/// of variables with the no debug location at all, but the last element
/// in the vector represents the number of fully covered variables within
/// its scope.
 std::vector<SaturatingUINT64> VarParamLocStats{
 std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
/// Map non debug entry values coverage.
 std::vector<SaturatingUINT64> VarParamNonEntryValLocStats{
 std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
/// The debug location statistics for formal parameters.
 std::vector<SaturatingUINT64> ParamLocStats{
 std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
/// Map non debug entry values coverage for formal parameters.
 std::vector<SaturatingUINT64> ParamNonEntryValLocStats{
 std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
/// The debug location statistics for local variables.
 std::vector<SaturatingUINT64> LocalVarLocStats{
 std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
/// Map non debug entry values coverage for local variables.
 std::vector<SaturatingUINT64> LocalVarNonEntryValLocStats{
 std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
/// Total number of local variables and function parameters processed.
 SaturatingUINT64 NumVarParam = 0;
/// Total number of formal parameters processed.
 SaturatingUINT64 NumParam = 0;
/// Total number of local variables processed.
 SaturatingUINT64 NumVar = 0;
};
} // namespace

/// Collect debug location statistics for one DIE.
staticvoidcollectLocStats(uint64_t ScopeBytesCovered, uint64_t BytesInScope,
 std::vector<SaturatingUINT64> &VarParamLocStats,
 std::vector<SaturatingUINT64> &ParamLocStats,
 std::vector<SaturatingUINT64> &LocalVarLocStats,
bool IsParam, bool IsLocalVar) {
auto getCoverageBucket = [ScopeBytesCovered, BytesInScope]() -> unsigned {
// No debug location at all for the variable.
if (ScopeBytesCovered == 0)
return0;
// Fully covered variable within its scope.
if (ScopeBytesCovered >= BytesInScope)
return NumOfCoverageCategories - 1;
// Get covered range (e.g. 20%-29%).
unsigned LocBucket = 100 * (double)ScopeBytesCovered / BytesInScope;
 LocBucket /= 10;
return LocBucket + 1;
 };

unsigned CoverageBucket = getCoverageBucket();

 VarParamLocStats[CoverageBucket].Value++;
if (IsParam)
 ParamLocStats[CoverageBucket].Value++;
elseif (IsLocalVar)
 LocalVarLocStats[CoverageBucket].Value++;
}

/// Construct an identifier for a given DIE from its Prefix, Name, DeclFileName
/// and DeclLine. The identifier aims to be unique for any unique entities,
/// but keeping the same among different instances of the same entity.
static std::string constructDieID(DWARFDie Die,
 StringRef Prefix = StringRef()) {
 std::string IDStr;
 llvm::raw_string_ostream ID(IDStr);
 ID << Prefix
 << Die.getName(DINameKind::LinkageName);

// Prefix + Name is enough for local variables and parameters.
if (!Prefix.empty() && !Prefix.equals("g"))
return ID.str();

auto DeclFile = Die.findRecursively(dwarf::DW_AT_decl_file);
 std::string File;
if (DeclFile) {
 DWARFUnit *U = Die.getDwarfUnit();
if (constauto *LT = U->getContext().getLineTableForUnit(U))
if (LT->getFileNameByIndex(
dwarf::toUnsigned(DeclFile, 0), U->getCompilationDir(),
 DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, File))
 File = std::string(sys::path::filename(File));
 }
 ID << ":" << (File.empty() ? "/" : File);
 ID << ":"
 << dwarf::toUnsigned(Die.findRecursively(dwarf::DW_AT_decl_line), 0);
return ID.str();
}

/// Return the number of bytes in the overlap of ranges A and B.
staticuint64_tcalculateOverlap(DWARFAddressRange A, DWARFAddressRange B) {
uint64_t Lower = std::max(A.LowPC, B.LowPC);
uint64_t Upper = std::min(A.HighPC, B.HighPC);
if (Lower >= Upper)
return0;
return Upper - Lower;
}

/// Collect debug info quality metrics for one DIE.
staticvoidcollectStatsForDie(DWARFDie Die, const std::string &FnPrefix,
const std::string &VarPrefix,
uint64_t BytesInScope, uint32_t InlineDepth,
 StringMap<PerFunctionStats> &FnStatMap,
 GlobalStats &GlobalStats,
 LocationStats &LocStats,
 AbstractOriginVarsTy *AbstractOriginVariables) {
const dwarf::Tag Tag = Die.getTag();
// Skip CU node.
if (Tag == dwarf::DW_TAG_compile_unit)
return;

bool HasLoc = false;
bool HasSrcLoc = false;
bool HasType = false;
uint64_t TotalBytesCovered = 0;
uint64_t ScopeBytesCovered = 0;
uint64_t BytesEntryValuesCovered = 0;
auto &FnStats = FnStatMap[FnPrefix];
bool IsParam = Tag == dwarf::DW_TAG_formal_parameter;
bool IsLocalVar = Tag == dwarf::DW_TAG_variable;
bool IsConstantMember = Tag == dwarf::DW_TAG_member &&
 Die.find(dwarf::DW_AT_const_value);

// For zero covered inlined variables the locstats will be
// calculated later.
bool DeferLocStats = false;

if (Tag == dwarf::DW_TAG_call_site || Tag == dwarf::DW_TAG_GNU_call_site) {
 GlobalStats.CallSiteDIEs++;
return;
 }

if (Tag == dwarf::DW_TAG_call_site_parameter ||
 Tag == dwarf::DW_TAG_GNU_call_site_parameter) {
 GlobalStats.CallSiteParamDIEs++;
return;
 }

if (!IsParam && !IsLocalVar && !IsConstantMember) {
// Not a variable or constant member.
return;
 }

// Ignore declarations of global variables.
if (IsLocalVar && Die.find(dwarf::DW_AT_declaration))
return;

if (Die.findRecursively(dwarf::DW_AT_decl_file) &&
 Die.findRecursively(dwarf::DW_AT_decl_line))
 HasSrcLoc = true;

if (Die.findRecursively(dwarf::DW_AT_type))
 HasType = true;

if (Die.find(dwarf::DW_AT_abstract_origin)) {
if (Die.find(dwarf::DW_AT_location) || Die.find(dwarf::DW_AT_const_value)) {
if (AbstractOriginVariables) {
auto Offset = Die.find(dwarf::DW_AT_abstract_origin);
// Do not track this variable any more, since it has location
// coverage.
llvm::erase_value(*AbstractOriginVariables, (*Offset).getRawUValue());
 }
 } else {
// The locstats will be handled at the end of
// the collectStatsRecursive().
 DeferLocStats = true;
 }
 }

auto IsEntryValue = [&](ArrayRef<uint8_t> D) -> bool {
 DWARFUnit *U = Die.getDwarfUnit();
 DataExtractor Data(toStringRef(D),
 Die.getDwarfUnit()->getContext().isLittleEndian(), 0);
 DWARFExpression Expression(Data, U->getAddressByteSize(),
 U->getFormParams().Format);
// Consider the expression containing the DW_OP_entry_value as
// an entry value.
returnllvm::any_of(Expression, [](const DWARFExpression::Operation &Op) {
return Op.getCode() == dwarf::DW_OP_entry_value ||
 Op.getCode() == dwarf::DW_OP_GNU_entry_value;
 });
 };

if (Die.find(dwarf::DW_AT_const_value)) {
// This catches constant members *and* variables.
 HasLoc = true;
 ScopeBytesCovered = BytesInScope;
 TotalBytesCovered = BytesInScope;
 } else {
// Handle variables and function arguments.
 Expected<std::vector<DWARFLocationExpression>> Loc =
 Die.getLocations(dwarf::DW_AT_location);
if (!Loc) {
consumeError(Loc.takeError());
 } else {
 HasLoc = true;
// Get PC coverage.
auto Default = find_if(
 *Loc, [](const DWARFLocationExpression &L) { return !L.Range; });
if (Default != Loc->end()) {
// Assume the entire range is covered by a single location.
 ScopeBytesCovered = BytesInScope;
 TotalBytesCovered = BytesInScope;
 } else {
// Caller checks this Expected result already, it cannot fail.
auto ScopeRanges = cantFail(Die.getParent().getAddressRanges());
for (auto Entry : *Loc) {
 TotalBytesCovered += Entry.Range->HighPC - Entry.Range->LowPC;
uint64_t ScopeBytesCoveredByEntry = 0;
// Calculate how many bytes of the parent scope this entry covers.
// FIXME: In section 2.6.2 of the DWARFv5 spec it says that "The
// address ranges defined by the bounded location descriptions of a
// location list may overlap". So in theory a variable can have
// multiple simultaneous locations, which would make this calculation
// misleading because we will count the overlapped areas
// twice. However, clang does not currently emit DWARF like this.
for (DWARFAddressRange R : ScopeRanges) {
 ScopeBytesCoveredByEntry += calculateOverlap(*Entry.Range, R);
 }
 ScopeBytesCovered += ScopeBytesCoveredByEntry;
if (IsEntryValue(Entry.Expr))
 BytesEntryValuesCovered += ScopeBytesCoveredByEntry;
 }
 }
 }
 }

// Calculate the debug location statistics.
if (BytesInScope && !DeferLocStats) {
 LocStats.NumVarParam.Value++;
if (IsParam)
 LocStats.NumParam.Value++;
elseif (IsLocalVar)
 LocStats.NumVar.Value++;

collectLocStats(ScopeBytesCovered, BytesInScope, LocStats.VarParamLocStats,
 LocStats.ParamLocStats, LocStats.LocalVarLocStats, IsParam,
 IsLocalVar);
// Non debug entry values coverage statistics.
collectLocStats(ScopeBytesCovered - BytesEntryValuesCovered, BytesInScope,
 LocStats.VarParamNonEntryValLocStats,
 LocStats.ParamNonEntryValLocStats,
 LocStats.LocalVarNonEntryValLocStats, IsParam, IsLocalVar);
 }

// Collect PC range coverage data.
if (DWARFDie D =
 Die.getAttributeValueAsReferencedDie(dwarf::DW_AT_abstract_origin))
 Die = D;

 std::string VarID = constructDieID(Die, VarPrefix);
 FnStats.VarsInFunction.insert(VarID);

 GlobalStats.TotalBytesCovered += TotalBytesCovered;
if (BytesInScope) {
 GlobalStats.ScopeBytesCovered += ScopeBytesCovered;
 GlobalStats.ScopeBytes += BytesInScope;
 GlobalStats.ScopeEntryValueBytesCovered += BytesEntryValuesCovered;
if (IsParam) {
 GlobalStats.ParamScopeBytesCovered += ScopeBytesCovered;
 GlobalStats.ParamScopeBytes += BytesInScope;
 GlobalStats.ParamScopeEntryValueBytesCovered += BytesEntryValuesCovered;
 } elseif (IsLocalVar) {
 GlobalStats.LocalVarScopeBytesCovered += ScopeBytesCovered;
 GlobalStats.LocalVarScopeBytes += BytesInScope;
 GlobalStats.LocalVarScopeEntryValueBytesCovered +=
 BytesEntryValuesCovered;
 }
assert(GlobalStats.ScopeBytesCovered.Value <= GlobalStats.ScopeBytes.Value);
 }

if (IsConstantMember) {
 FnStats.ConstantMembers++;
return;
 }

 FnStats.TotalVarWithLoc += (unsigned)HasLoc;

if (Die.find(dwarf::DW_AT_artificial)) {
 FnStats.NumArtificial++;
return;
 }

if (IsParam) {
 FnStats.NumParams++;
if (HasType)
 FnStats.NumParamTypes++;
if (HasSrcLoc)
 FnStats.NumParamSourceLocations++;
if (HasLoc)
 FnStats.NumParamLocations++;
 } elseif (IsLocalVar) {
 FnStats.NumLocalVars++;
if (HasType)
 FnStats.NumLocalVarTypes++;
if (HasSrcLoc)
 FnStats.NumLocalVarSourceLocations++;
if (HasLoc)
 FnStats.NumLocalVarLocations++;
 }
}

/// Recursively collect variables from subprogram with DW_AT_inline attribute.
staticvoidcollectAbstractOriginFnInfo(
 DWARFDie Die, uint64_t SPOffset,
 AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
 AbstractOriginVarsTyMap &LocalAbstractOriginFnInfo) {
 DWARFDie Child = Die.getFirstChild();
while (Child) {
const dwarf::Tag ChildTag = Child.getTag();
if (ChildTag == dwarf::DW_TAG_formal_parameter ||
 ChildTag == dwarf::DW_TAG_variable) {
 GlobalAbstractOriginFnInfo[SPOffset].push_back(Child.getOffset());
 LocalAbstractOriginFnInfo[SPOffset].push_back(Child.getOffset());
 } elseif (ChildTag == dwarf::DW_TAG_lexical_block)
collectAbstractOriginFnInfo(Child, SPOffset, GlobalAbstractOriginFnInfo,
 LocalAbstractOriginFnInfo);
 Child = Child.getSibling();
 }
}

/// Recursively collect debug info quality metrics.
staticvoidcollectStatsRecursive(
 DWARFDie Die, std::string FnPrefix, std::string VarPrefix,
uint64_t BytesInScope, uint32_t InlineDepth,
 StringMap<PerFunctionStats> &FnStatMap, GlobalStats &GlobalStats,
 LocationStats &LocStats, FunctionDIECUTyMap &AbstractOriginFnCUs,
 AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
 AbstractOriginVarsTyMap &LocalAbstractOriginFnInfo,
 FunctionsWithAbstractOriginTy &FnsWithAbstractOriginToBeProcessed,
 AbstractOriginVarsTy *AbstractOriginVarsPtr = nullptr) {
// Skip NULL nodes.
if (Die.isNULL())
return;

const dwarf::Tag Tag = Die.getTag();
// Skip function types.
if (Tag == dwarf::DW_TAG_subroutine_type)
return;

// Handle any kind of lexical scope.
constbool HasAbstractOrigin = Die.find(dwarf::DW_AT_abstract_origin) != None;
constbool IsFunction = Tag == dwarf::DW_TAG_subprogram;
constbool IsBlock = Tag == dwarf::DW_TAG_lexical_block;
constbool IsInlinedFunction = Tag == dwarf::DW_TAG_inlined_subroutine;
// We want to know how many variables (with abstract_origin) don't have
// location info.
constbool IsCandidateForZeroLocCovTracking =
 (IsInlinedFunction || (IsFunction && HasAbstractOrigin));

 AbstractOriginVarsTy AbstractOriginVars;

// Get the vars of the inlined fn, so the locstats
// reports the missing vars (with coverage 0%).
if (IsCandidateForZeroLocCovTracking) {
auto OffsetFn = Die.find(dwarf::DW_AT_abstract_origin);
if (OffsetFn) {
uint64_t OffsetOfInlineFnCopy = (*OffsetFn).getRawUValue();
if (LocalAbstractOriginFnInfo.count(OffsetOfInlineFnCopy)) {
 AbstractOriginVars = LocalAbstractOriginFnInfo[OffsetOfInlineFnCopy];
 AbstractOriginVarsPtr = &AbstractOriginVars;
 } else {
// This means that the DW_AT_inline fn copy is out of order
// or that the abstract_origin references another CU,
// so this abstract origin instance will be processed later.
 FnsWithAbstractOriginToBeProcessed.push_back(Die.getOffset());
 AbstractOriginVarsPtr = nullptr;
 }
 }
 }

if (IsFunction || IsInlinedFunction || IsBlock) {
// Reset VarPrefix when entering a new function.
if (IsFunction || IsInlinedFunction)
 VarPrefix = "v";

// Ignore forward declarations.
if (Die.find(dwarf::DW_AT_declaration))
return;

// Check for call sites.
if (Die.find(dwarf::DW_AT_call_file) && Die.find(dwarf::DW_AT_call_line))
 GlobalStats.CallSiteEntries++;

// PC Ranges.
auto RangesOrError = Die.getAddressRanges();
if (!RangesOrError) {
llvm::consumeError(RangesOrError.takeError());
return;
 }

auto Ranges = RangesOrError.get();
uint64_t BytesInThisScope = 0;
for (auto Range : Ranges)
 BytesInThisScope += Range.HighPC - Range.LowPC;

// Count the function.
if (!IsBlock) {
// Skip over abstract origins, but collect variables
// from it so it can be used for location statistics
// for inlined instancies.
if (Die.find(dwarf::DW_AT_inline)) {
uint64_t SPOffset = Die.getOffset();
 AbstractOriginFnCUs[SPOffset] = Die.getDwarfUnit();
collectAbstractOriginFnInfo(Die, SPOffset, GlobalAbstractOriginFnInfo,
 LocalAbstractOriginFnInfo);
return;
 }

 std::string FnID = constructDieID(Die);
// We've seen an instance of this function.
auto &FnStats = FnStatMap[FnID];
 FnStats.IsFunction = true;
if (IsInlinedFunction) {
 FnStats.NumFnInlined++;
if (Die.findRecursively(dwarf::DW_AT_abstract_origin))
 FnStats.NumAbstractOrigins++;
 } else {
 FnStats.NumFnOutOfLine++;
 }
if (Die.findRecursively(dwarf::DW_AT_decl_file) &&
 Die.findRecursively(dwarf::DW_AT_decl_line))
 FnStats.HasSourceLocation = true;
// Update function prefix.
 FnPrefix = FnID;
 }

if (BytesInThisScope) {
 BytesInScope = BytesInThisScope;
if (IsFunction)
 GlobalStats.FunctionSize += BytesInThisScope;
elseif (IsInlinedFunction && InlineDepth == 0)
 GlobalStats.InlineFunctionSize += BytesInThisScope;
 }
 } else {
// Not a scope, visit the Die itself. It could be a variable.
collectStatsForDie(Die, FnPrefix, VarPrefix, BytesInScope, InlineDepth,
 FnStatMap, GlobalStats, LocStats, AbstractOriginVarsPtr);
 }

// Set InlineDepth correctly for child recursion
if (IsFunction)
 InlineDepth = 0;
elseif (IsInlinedFunction)
 ++InlineDepth;

// Traverse children.
unsigned LexicalBlockIndex = 0;
unsigned FormalParameterIndex = 0;
 DWARFDie Child = Die.getFirstChild();
while (Child) {
 std::string ChildVarPrefix = VarPrefix;
if (Child.getTag() == dwarf::DW_TAG_lexical_block)
 ChildVarPrefix += toHex(LexicalBlockIndex++) + '.';
if (Child.getTag() == dwarf::DW_TAG_formal_parameter)
 ChildVarPrefix += 'p' + toHex(FormalParameterIndex++) + '.';

collectStatsRecursive(
 Child, FnPrefix, ChildVarPrefix, BytesInScope, InlineDepth, FnStatMap,
 GlobalStats, LocStats, AbstractOriginFnCUs, GlobalAbstractOriginFnInfo,
 LocalAbstractOriginFnInfo, FnsWithAbstractOriginToBeProcessed,
 AbstractOriginVarsPtr);
 Child = Child.getSibling();
 }

if (!IsCandidateForZeroLocCovTracking)
return;

// After we have processed all vars of the inlined function (or function with
// an abstract_origin), we want to know how many variables have no location.
for (auto Offset : AbstractOriginVars) {
 LocStats.NumVarParam++;
 LocStats.VarParamLocStats[ZeroCoverageBucket]++;
auto FnDie = Die.getDwarfUnit()->getDIEForOffset(Offset);
if (!FnDie)
continue;
auto Tag = FnDie.getTag();
if (Tag == dwarf::DW_TAG_formal_parameter) {
 LocStats.NumParam++;
 LocStats.ParamLocStats[ZeroCoverageBucket]++;
 } elseif (Tag == dwarf::DW_TAG_variable) {
 LocStats.NumVar++;
 LocStats.LocalVarLocStats[ZeroCoverageBucket]++;
 }
 }
}

/// Print human-readable output.
/// \{
staticvoidprintDatum(json::OStream &J, constchar *Key, json::Value Value) {
if (Value == OverflowValue)
 J.attribute(Key, "overflowed");
else
 J.attribute(Key, Value);

LLVM_DEBUG(llvm::dbgs() << Key << ": " << Value << '\n');
}

staticvoidprintLocationStats(json::OStream &J, constchar *Key,
 std::vector<SaturatingUINT64> &LocationStats) {
if (LocationStats[0].Value == OverflowValue)
 J.attribute((Twine(Key) +
" with (0%,10%) of parent scope covered by DW_AT_location")
 .str(),
"overflowed");
else
 J.attribute(
 (Twine(Key) + " with 0% of parent scope covered by DW_AT_location")
 .str(),
 LocationStats[0].Value);
LLVM_DEBUG(
llvm::dbgs() << Key
 << " with 0% of parent scope covered by DW_AT_location: \\"
 << LocationStats[0].Value << '\n');

if (LocationStats[1].Value == OverflowValue)
 J.attribute((Twine(Key) +
" with (0%,10%) of parent scope covered by DW_AT_location")
 .str(),
"overflowed");
else
 J.attribute((Twine(Key) +
" with (0%,10%) of parent scope covered by DW_AT_location")
 .str(),
 LocationStats[1].Value);
LLVM_DEBUG(llvm::dbgs()
 << Key
 << " with (0%,10%) of parent scope covered by DW_AT_location: "
 << LocationStats[1].Value << '\n');

for (unsigned i = 2; i < NumOfCoverageCategories - 1; ++i) {
if (LocationStats[i].Value == OverflowValue)
 J.attribute((Twine(Key) + " with [" + Twine((i - 1) * 10) + "%," +
Twine(i * 10) +
"%) of parent scope covered by DW_AT_location")
 .str(),
"overflowed");
else
 J.attribute((Twine(Key) + " with [" + Twine((i - 1) * 10) + "%," +
Twine(i * 10) +
"%) of parent scope covered by DW_AT_location")
 .str(),
 LocationStats[i].Value);
LLVM_DEBUG(llvm::dbgs()
 << Key << " with [" << (i - 1) * 10 << "%," << i * 10
 << "%) of parent scope covered by DW_AT_location: "
 << LocationStats[i].Value);
 }
if (LocationStats[NumOfCoverageCategories - 1].Value == OverflowValue)
 J.attribute(
 (Twine(Key) + " with 100% of parent scope covered by DW_AT_location")
 .str(),
"overflowed");
else
 J.attribute(
 (Twine(Key) + " with 100% of parent scope covered by DW_AT_location")
 .str(),
 LocationStats[NumOfCoverageCategories - 1].Value);
LLVM_DEBUG(
llvm::dbgs() << Key
 << " with 100% of parent scope covered by DW_AT_location: "
 << LocationStats[NumOfCoverageCategories - 1].Value);
}

staticvoidprintSectionSizes(json::OStream &J, const SectionSizes &Sizes) {
for (constauto &It : Sizes.DebugSectionSizes)
 J.attribute((Twine("#bytes in ") + It.first).str(), int64_t(It.second));
}

/// Stop tracking variables that contain abstract_origin with a location.
/// This is used for out-of-order DW_AT_inline subprograms only.
staticvoidupdateVarsWithAbstractOriginLocCovInfo(
 DWARFDie FnDieWithAbstractOrigin,
 AbstractOriginVarsTy &AbstractOriginVars) {
 DWARFDie Child = FnDieWithAbstractOrigin.getFirstChild();
while (Child) {
const dwarf::Tag ChildTag = Child.getTag();
if ((ChildTag == dwarf::DW_TAG_formal_parameter ||
 ChildTag == dwarf::DW_TAG_variable) &&
 (Child.find(dwarf::DW_AT_location) ||
 Child.find(dwarf::DW_AT_const_value))) {
auto OffsetVar = Child.find(dwarf::DW_AT_abstract_origin);
if (OffsetVar)
llvm::erase_value(AbstractOriginVars, (*OffsetVar).getRawUValue());
 } elseif (ChildTag == dwarf::DW_TAG_lexical_block)
updateVarsWithAbstractOriginLocCovInfo(Child, AbstractOriginVars);
 Child = Child.getSibling();
 }
}

/// Collect zero location coverage for inlined variables which refer to
/// a DW_AT_inline copy of subprogram that is out of order in the DWARF.
/// Also cover the variables of a concrete function (represented with
/// the DW_TAG_subprogram) with an abstract_origin attribute.
staticvoidcollectZeroLocCovForVarsWithAbstractOrigin(
 DWARFUnit *DwUnit, GlobalStats &GlobalStats, LocationStats &LocStats,
 AbstractOriginVarsTyMap &LocalAbstractOriginFnInfo,
 FunctionsWithAbstractOriginTy &FnsWithAbstractOriginToBeProcessed) {
// The next variable is used to filter out functions that have been processed,
// leaving FnsWithAbstractOriginToBeProcessed with just CrossCU references.
 FunctionsWithAbstractOriginTy ProcessedFns;
for (auto FnOffset : FnsWithAbstractOriginToBeProcessed) {
 DWARFDie FnDieWithAbstractOrigin = DwUnit->getDIEForOffset(FnOffset);
auto FnCopy = FnDieWithAbstractOrigin.find(dwarf::DW_AT_abstract_origin);
 AbstractOriginVarsTy AbstractOriginVars;
if (!FnCopy)
continue;
uint64_t FnCopyRawUValue = (*FnCopy).getRawUValue();
// If there is no entry within LocalAbstractOriginFnInfo for the given
// FnCopyRawUValue, function isn't out-of-order in DWARF. Rather, we have
// CrossCU referencing.
if (!LocalAbstractOriginFnInfo.count(FnCopyRawUValue))
continue;
 AbstractOriginVars = LocalAbstractOriginFnInfo[FnCopyRawUValue];
updateVarsWithAbstractOriginLocCovInfo(FnDieWithAbstractOrigin,
 AbstractOriginVars);

for (auto Offset : AbstractOriginVars) {
 LocStats.NumVarParam++;
 LocStats.VarParamLocStats[ZeroCoverageBucket]++;
auto Tag = DwUnit->getDIEForOffset(Offset).getTag();
if (Tag == dwarf::DW_TAG_formal_parameter) {
 LocStats.NumParam++;
 LocStats.ParamLocStats[ZeroCoverageBucket]++;
 } elseif (Tag == dwarf::DW_TAG_variable) {
 LocStats.NumVar++;
 LocStats.LocalVarLocStats[ZeroCoverageBucket]++;
 }
 }
 ProcessedFns.push_back(FnOffset);
 }
for (auto ProcessedFn : ProcessedFns)
llvm::erase_value(FnsWithAbstractOriginToBeProcessed, ProcessedFn);
}

/// Collect zero location coverage for inlined variables which refer to
/// a DW_AT_inline copy of subprogram that is in a different CU.
staticvoidcollectZeroLocCovForVarsWithCrossCUReferencingAbstractOrigin(
 LocationStats &LocStats, FunctionDIECUTyMap AbstractOriginFnCUs,
 AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
 CrossCUReferencingDIELocationTy &CrossCUReferencesToBeResolved) {
for (constauto &CrossCUReferenceToBeResolved :
 CrossCUReferencesToBeResolved) {
 DWARFUnit *DwUnit = CrossCUReferenceToBeResolved.DwUnit;
 DWARFDie FnDIEWithCrossCUReferencing =
 DwUnit->getDIEForOffset(CrossCUReferenceToBeResolved.DIEOffset);
auto FnCopy =
 FnDIEWithCrossCUReferencing.find(dwarf::DW_AT_abstract_origin);
if (!FnCopy)
continue;
uint64_t FnCopyRawUValue = (*FnCopy).getRawUValue();
 AbstractOriginVarsTy AbstractOriginVars =
 GlobalAbstractOriginFnInfo[FnCopyRawUValue];
updateVarsWithAbstractOriginLocCovInfo(FnDIEWithCrossCUReferencing,
 AbstractOriginVars);
for (auto Offset : AbstractOriginVars) {
 LocStats.NumVarParam++;
 LocStats.VarParamLocStats[ZeroCoverageBucket]++;
auto Tag = (AbstractOriginFnCUs[FnCopyRawUValue])
 ->getDIEForOffset(Offset)
 .getTag();
if (Tag == dwarf::DW_TAG_formal_parameter) {
 LocStats.NumParam++;
 LocStats.ParamLocStats[ZeroCoverageBucket]++;
 } elseif (Tag == dwarf::DW_TAG_variable) {
 LocStats.NumVar++;
 LocStats.LocalVarLocStats[ZeroCoverageBucket]++;
 }
 }
 }
}

/// \}

/// Collect debug info quality metrics for an entire DIContext.
///
/// Do the impossible and reduce the quality of the debug info down to a few
/// numbers. The idea is to condense the data into numbers that can be tracked
/// over time to identify trends in newer compiler versions and gauge the effect
/// of particular optimizations. The raw numbers themselves are not particularly
/// useful, only the delta between compiling the same program with different
/// compilers is.
booldwarfdump::collectStatsForObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
const Twine &Filename,
 raw_ostream &OS) {
 StringRef FormatName = Obj.getFileFormatName();
 GlobalStats GlobalStats;
 LocationStats LocStats;
 StringMap<PerFunctionStats> Statistics;
// This variable holds variable information for functions with
// abstract_origin globally, across all CUs.
 AbstractOriginVarsTyMap GlobalAbstractOriginFnInfo;
// This variable holds information about the CU of a function with
// abstract_origin.
 FunctionDIECUTyMap AbstractOriginFnCUs;
 CrossCUReferencingDIELocationTy CrossCUReferencesToBeResolved;
for (constauto &CU : static_cast<DWARFContext *>(&DICtx)->compile_units()) {
if (DWARFDie CUDie = CU->getNonSkeletonUnitDIE(false)) {
// This variable holds variable information for functions with
// abstract_origin, but just for the current CU.
 AbstractOriginVarsTyMap LocalAbstractOriginFnInfo;
 FunctionsWithAbstractOriginTy FnsWithAbstractOriginToBeProcessed;

collectStatsRecursive(
 CUDie, "/", "g", 0, 0, Statistics, GlobalStats, LocStats,
 AbstractOriginFnCUs, GlobalAbstractOriginFnInfo,
 LocalAbstractOriginFnInfo, FnsWithAbstractOriginToBeProcessed);

// collectZeroLocCovForVarsWithAbstractOrigin will filter out all
// out-of-order DWARF functions that have been processed within it,
// leaving FnsWithAbstractOriginToBeProcessed with only CrossCU
// references.
collectZeroLocCovForVarsWithAbstractOrigin(
 CUDie.getDwarfUnit(), GlobalStats, LocStats,
 LocalAbstractOriginFnInfo, FnsWithAbstractOriginToBeProcessed);

// Collect all CrossCU references into CrossCUReferencesToBeResolved.
for (auto CrossCUReferencingDIEOffset :
 FnsWithAbstractOriginToBeProcessed)
 CrossCUReferencesToBeResolved.push_back(
DIELocation(CUDie.getDwarfUnit(), CrossCUReferencingDIEOffset));
 }
 }

/// Resolve CrossCU references.
collectZeroLocCovForVarsWithCrossCUReferencingAbstractOrigin(
 LocStats, AbstractOriginFnCUs, GlobalAbstractOriginFnInfo,
 CrossCUReferencesToBeResolved);

/// Collect the sizes of debug sections.
 SectionSizes Sizes;
calculateSectionSizes(Obj, Sizes, Filename);

/// The version number should be increased every time the algorithm is changed
/// (including bug fixes). New metrics may be added without increasing the
/// version.
unsigned Version = 9;
 SaturatingUINT64 VarParamTotal = 0;
 SaturatingUINT64 VarParamUnique = 0;
 SaturatingUINT64 VarParamWithLoc = 0;
 SaturatingUINT64 NumFunctions = 0;
 SaturatingUINT64 NumInlinedFunctions = 0;
 SaturatingUINT64 NumFuncsWithSrcLoc = 0;
 SaturatingUINT64 NumAbstractOrigins = 0;
 SaturatingUINT64 ParamTotal = 0;
 SaturatingUINT64 ParamWithType = 0;
 SaturatingUINT64 ParamWithLoc = 0;
 SaturatingUINT64 ParamWithSrcLoc = 0;
 SaturatingUINT64 LocalVarTotal = 0;
 SaturatingUINT64 LocalVarWithType = 0;
 SaturatingUINT64 LocalVarWithSrcLoc = 0;
 SaturatingUINT64 LocalVarWithLoc = 0;
for (auto &Entry : Statistics) {
 PerFunctionStats &Stats = Entry.getValue();
uint64_t TotalVars = Stats.VarsInFunction.size() *
 (Stats.NumFnInlined + Stats.NumFnOutOfLine);
// Count variables in global scope.
if (!Stats.IsFunction)
 TotalVars =
 Stats.NumLocalVars + Stats.ConstantMembers + Stats.NumArtificial;
uint64_t Constants = Stats.ConstantMembers;
 VarParamWithLoc += Stats.TotalVarWithLoc + Constants;
 VarParamTotal += TotalVars;
 VarParamUnique += Stats.VarsInFunction.size();
LLVM_DEBUG(for (auto &V
 : Stats.VarsInFunction) llvm::dbgs()
 << Entry.getKey() << ": " << V.getKey() << "\n");
 NumFunctions += Stats.IsFunction;
 NumFuncsWithSrcLoc += Stats.HasSourceLocation;
 NumInlinedFunctions += Stats.IsFunction * Stats.NumFnInlined;
 NumAbstractOrigins += Stats.IsFunction * Stats.NumAbstractOrigins;
 ParamTotal += Stats.NumParams;
 ParamWithType += Stats.NumParamTypes;
 ParamWithLoc += Stats.NumParamLocations;
 ParamWithSrcLoc += Stats.NumParamSourceLocations;
 LocalVarTotal += Stats.NumLocalVars;
 LocalVarWithType += Stats.NumLocalVarTypes;
 LocalVarWithLoc += Stats.NumLocalVarLocations;
 LocalVarWithSrcLoc += Stats.NumLocalVarSourceLocations;
 }

// Print summary.
 OS.SetBufferSize(1024);
 json::OStream J(OS, 2);
 J.objectBegin();
 J.attribute("version", Version);
LLVM_DEBUG(llvm::dbgs() << "Variable location quality metrics\n";
llvm::dbgs() << "---------------------------------\n");

printDatum(J, "file", Filename.str());
printDatum(J, "format", FormatName);

printDatum(J, "#functions", NumFunctions.Value);
printDatum(J, "#functions with location", NumFuncsWithSrcLoc.Value);
printDatum(J, "#inlined functions", NumInlinedFunctions.Value);
printDatum(J, "#inlined functions with abstract origins",
 NumAbstractOrigins.Value);

// This includes local variables and formal parameters.
printDatum(J, "#unique source variables", VarParamUnique.Value);
printDatum(J, "#source variables", VarParamTotal.Value);
printDatum(J, "#source variables with location", VarParamWithLoc.Value);

printDatum(J, "#call site entries", GlobalStats.CallSiteEntries.Value);
printDatum(J, "#call site DIEs", GlobalStats.CallSiteDIEs.Value);
printDatum(J, "#call site parameter DIEs",
 GlobalStats.CallSiteParamDIEs.Value);

printDatum(J, "sum_all_variables(#bytes in parent scope)",
 GlobalStats.ScopeBytes.Value);
printDatum(J,
"sum_all_variables(#bytes in any scope covered by DW_AT_location)",
 GlobalStats.TotalBytesCovered.Value);
printDatum(J,
"sum_all_variables(#bytes in parent scope covered by "
"DW_AT_location)",
 GlobalStats.ScopeBytesCovered.Value);
printDatum(J,
"sum_all_variables(#bytes in parent scope covered by "
"DW_OP_entry_value)",
 GlobalStats.ScopeEntryValueBytesCovered.Value);

printDatum(J, "sum_all_params(#bytes in parent scope)",
 GlobalStats.ParamScopeBytes.Value);
printDatum(J,
"sum_all_params(#bytes in parent scope covered by DW_AT_location)",
 GlobalStats.ParamScopeBytesCovered.Value);
printDatum(J,
"sum_all_params(#bytes in parent scope covered by "
"DW_OP_entry_value)",
 GlobalStats.ParamScopeEntryValueBytesCovered.Value);

printDatum(J, "sum_all_local_vars(#bytes in parent scope)",
 GlobalStats.LocalVarScopeBytes.Value);
printDatum(J,
"sum_all_local_vars(#bytes in parent scope covered by "
"DW_AT_location)",
 GlobalStats.LocalVarScopeBytesCovered.Value);
printDatum(J,