Index: include/llvm/ADT/STLExtras.h =================================================================== --- include/llvm/ADT/STLExtras.h +++ include/llvm/ADT/STLExtras.h @@ -904,6 +904,13 @@ return std::partition(std::begin(Range), std::end(Range), P); } +/// Provide wrappers to std::lower_bound which take ranges instead of having to +/// pass begin/end explicitly. +template +auto lower_bound(R &&Range, ForwardIt I) -> decltype(std::begin(Range)) { + return std::lower_bound(std::begin(Range), std::end(Range), I); +} + /// \brief Given a range of type R, iterate the entire range and return a /// SmallVector with elements of the vector. This is useful, for example, /// when you want to iterate a range and then sort the results. Index: include/llvm/DebugInfo/DWARF/DWARFDebugLoc.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFDebugLoc.h +++ include/llvm/DebugInfo/DWARF/DWARFDebugLoc.h @@ -20,6 +20,7 @@ class raw_ostream; class DWARFDebugLoc { +public: /// A single location within a location list. struct Entry { /// The beginning address of the instruction range. @@ -37,10 +38,14 @@ unsigned Offset; /// All the locations in which the variable is stored. SmallVector Entries; + bool operator<(const LocationList &Other) const { + return Offset < Other.Offset; + } }; using LocationLists = SmallVector; +private: /// A list of all the variables in the debug_loc section, each one describing /// the locations in which the variable is stored. LocationLists Locations; @@ -52,6 +57,9 @@ /// Parse the debug_loc section accessible via the 'data' parameter using the /// address size also given in 'data' to interpret the address ranges. void parse(const DWARFDataExtractor &data); + + /// Return location list entries at \c Offset. + const LocationList *getLocationList(unsigned Offset) const; }; class DWARFDebugLocDWO { Index: lib/DebugInfo/DWARF/DWARFDebugLoc.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFDebugLoc.cpp +++ lib/DebugInfo/DWARF/DWARFDebugLoc.cpp @@ -72,6 +72,16 @@ errs() << "error: failed to consume entire .debug_loc section\n"; } +const DWARFDebugLoc::LocationList * +DWARFDebugLoc::getLocationList(unsigned Offset) const { + DWARFDebugLoc::LocationList Searched; + Searched.Offset = Offset; + const LocationList *List = llvm::lower_bound(Locations, Searched); + if (List->Offset != Offset) + return nullptr; + return List; +} + void DWARFDebugLocDWO::parse(DataExtractor data) { uint32_t Offset = 0; while (data.isValidOffset(Offset)) { Index: test/tools/llvm-dwarfdump/X86/statistics.ll =================================================================== --- /dev/null +++ test/tools/llvm-dwarfdump/X86/statistics.ll @@ -0,0 +1,135 @@ +; RUN: llc -O0 %s -o - -filetype=obj \ +; RUN: | llvm-dwarfdump -statistics - 2>&1 | FileCheck %s + +; int GlobalConst = 42; +; int Global; +; +; struct S { +; static const int constant = 24; +; } s; +; +; int __attribute__((always_inline)) square(int i) { return i * i; } +; int cube(int i) { +; int squared = square(i); +; return squared*i; +; } + +; CHECK: PC Ranges covered: 9{{[0-9]}}% +; GlobalConst,Global,s,s.constant,square::i,cube::i,cube::squared +; CHECK: "unique source variables":7 +; +1 extra inline i. +; CHECK: "source variables":8 +; -1 square::i +; CHECK: "variables with location":7 +; CHECK: "scope bytes total":[[BYTES:[0-9]+]] +; Because of the dbg.value in the middle of the function, the pc range coverage +; must be below 100%. +; CHECK-NOT: "scope bytes covered":0 +; CHECK-NOT "scope bytes covered":[[BYTES]] +; CHECK: "scope bytes covered": + +; ModuleID = '/tmp/quality.cpp' +source_filename = "/tmp/quality.cpp" +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-apple-macosx10.12.0" + +%struct.S = type { i8 } + +@GlobalConst = global i32 42, align 4, !dbg !0 +@Global = global i32 0, align 4, !dbg !6 +@s = global %struct.S zeroinitializer, align 1, !dbg !9 + +; Function Attrs: alwaysinline nounwind ssp uwtable +define i32 @_Z6squarei(i32 %i) #0 !dbg !20 { +entry: + %i.addr = alloca i32, align 4 + store i32 %i, i32* %i.addr, align 4 + ; Modified to loose debug info for i here. + call void @llvm.dbg.declare(metadata i32* undef, metadata !23, metadata !24), !dbg !25 + %0 = load i32, i32* %i.addr, align 4, !dbg !26 + %1 = load i32, i32* %i.addr, align 4, !dbg !27 + %mul = mul nsw i32 %0, %1, !dbg !28 + ret i32 %mul, !dbg !29 +} + +; Function Attrs: nounwind readnone speculatable +declare void @llvm.dbg.declare(metadata, metadata, metadata) #1 +declare void @llvm.dbg.value(metadata, metadata, metadata) #1 + +; Function Attrs: noinline nounwind optnone ssp uwtable +define i32 @_Z4cubei(i32 %i) #2 !dbg !30 { +entry: + %i.addr.i = alloca i32, align 4 + call void @llvm.dbg.declare(metadata i32* %i.addr.i, metadata !23, metadata !24), !dbg !31 + %i.addr = alloca i32, align 4 + %squared = alloca i32, align 4 + store i32 %i, i32* %i.addr, align 4 + call void @llvm.dbg.declare(metadata i32* %i.addr, metadata !33, metadata !24), !dbg !34 + %0 = load i32, i32* %i.addr, align 4, !dbg !37 + store i32 %0, i32* %i.addr.i, align 4 + %1 = load i32, i32* %i.addr.i, align 4, !dbg !38 + %2 = load i32, i32* %i.addr.i, align 4, !dbg !39 + %mul.i = mul nsw i32 %1, %2, !dbg !40 + ; Modified to cover only about 50% of the lexical scope. + call void @llvm.dbg.value(metadata i32 %mul.i, metadata !35, metadata !24), !dbg !36 + store i32 %mul.i, i32* %squared, align 4, !dbg !36 + %3 = load i32, i32* %squared, align 4, !dbg !41 + call void @llvm.dbg.value(metadata i32 %3, metadata !35, metadata !24), !dbg !36 + %4 = load i32, i32* %i.addr, align 4, !dbg !42 + %mul = mul nsw i32 %3, %4, !dbg !43 + ret i32 %mul, !dbg !44 +} + +attributes #0 = { alwaysinline nounwind ssp uwtable } +attributes #1 = { nounwind readnone speculatable } +attributes #2 = { noinline nounwind optnone ssp uwtable } + +!llvm.dbg.cu = !{!2} +!llvm.module.flags = !{!15, !16, !17, !18} +!llvm.ident = !{!19} + +!0 = !DIGlobalVariableExpression(var: !1) +!1 = distinct !DIGlobalVariable(name: "GlobalConst", scope: !2, file: !3, line: 1, type: !8, isLocal: false, isDefinition: true) +!2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "clang version 6.0.0 (trunk 310529) (llvm/trunk 310534)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5) +!3 = !DIFile(filename: "/tmp/quality.cpp", directory: "/Volumes/Data/llvm") +!4 = !{} +!5 = !{!0, !6, !9} +!6 = !DIGlobalVariableExpression(var: !7) +!7 = distinct !DIGlobalVariable(name: "Global", scope: !2, file: !3, line: 2, type: !8, isLocal: false, isDefinition: true) +!8 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!9 = !DIGlobalVariableExpression(var: !10) +!10 = distinct !DIGlobalVariable(name: "s", scope: !2, file: !3, line: 6, type: !11, isLocal: false, isDefinition: true) +!11 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "S", file: !3, line: 4, size: 8, elements: !12, identifier: "_ZTS1S") +!12 = !{!13} +!13 = !DIDerivedType(tag: DW_TAG_member, name: "constant", scope: !11, file: !3, line: 5, baseType: !14, flags: DIFlagStaticMember, extraData: i32 24) +!14 = !DIDerivedType(tag: DW_TAG_const_type, baseType: !8) +!15 = !{i32 2, !"Dwarf Version", i32 4} +!16 = !{i32 2, !"Debug Info Version", i32 3} +!17 = !{i32 1, !"wchar_size", i32 4} +!18 = !{i32 7, !"PIC Level", i32 2} +!19 = !{!"clang version 6.0.0 (trunk 310529) (llvm/trunk 310534)"} +!20 = distinct !DISubprogram(name: "square", linkageName: "_Z6squarei", scope: !3, file: !3, line: 8, type: !21, isLocal: false, isDefinition: true, scopeLine: 8, flags: DIFlagPrototyped, isOptimized: false, unit: !2, variables: !4) +!21 = !DISubroutineType(types: !22) +!22 = !{!8, !8} +!23 = !DILocalVariable(name: "i", arg: 1, scope: !20, file: !3, line: 8, type: !8) +!24 = !DIExpression() +!25 = !DILocation(line: 8, column: 47, scope: !20) +!26 = !DILocation(line: 8, column: 59, scope: !20) +!27 = !DILocation(line: 8, column: 63, scope: !20) +!28 = !DILocation(line: 8, column: 61, scope: !20) +!29 = !DILocation(line: 8, column: 52, scope: !20) +!30 = distinct !DISubprogram(name: "cube", linkageName: "_Z4cubei", scope: !3, file: !3, line: 9, type: !21, isLocal: false, isDefinition: true, scopeLine: 9, flags: DIFlagPrototyped, isOptimized: false, unit: !2, variables: !4) +!31 = !DILocation(line: 8, column: 47, scope: !20, inlinedAt: !32) +!32 = distinct !DILocation(line: 10, column: 17, scope: !30) +!33 = !DILocalVariable(name: "i", arg: 1, scope: !30, file: !3, line: 9, type: !8) +!34 = !DILocation(line: 9, column: 14, scope: !30) +!35 = !DILocalVariable(name: "squared", scope: !30, file: !3, line: 10, type: !8) +!36 = !DILocation(line: 10, column: 7, scope: !30) +!37 = !DILocation(line: 10, column: 24, scope: !30) +!38 = !DILocation(line: 8, column: 59, scope: !20, inlinedAt: !32) +!39 = !DILocation(line: 8, column: 63, scope: !20, inlinedAt: !32) +!40 = !DILocation(line: 8, column: 61, scope: !20, inlinedAt: !32) +!41 = !DILocation(line: 11, column: 10, scope: !30) +!42 = !DILocation(line: 11, column: 18, scope: !30) +!43 = !DILocation(line: 11, column: 17, scope: !30) +!44 = !DILocation(line: 11, column: 3, scope: !30) Index: tools/llvm-dwarfdump/CMakeLists.txt =================================================================== --- tools/llvm-dwarfdump/CMakeLists.txt +++ tools/llvm-dwarfdump/CMakeLists.txt @@ -5,6 +5,7 @@ ) add_llvm_tool(llvm-dwarfdump + Statistics.cpp llvm-dwarfdump.cpp ) Index: tools/llvm-dwarfdump/Statistics.cpp =================================================================== --- /dev/null +++ tools/llvm-dwarfdump/Statistics.cpp @@ -0,0 +1,229 @@ +#include "llvm/ADT/DenseMap.h" +#include "llvm/DebugInfo/DIContext.h" +#include "llvm/DebugInfo/DWARF/DWARFContext.h" +#include "llvm/DebugInfo/DWARF/DWARFDebugLoc.h" +#define DEBUG_TYPE "dwarfdump" +using namespace llvm; + +/// Holds statistics for one functions (or other entity that has a PC range and +/// contains variables, such as a compile unit). +struct PerFunctionStats { + /// Number of inlined instances of this function. + unsigned NumFnInlined = 0; + /// Number of variables with location across all inlined instances. + unsigned TotalVarWithLoc = 0; + /// Number of constants with location across all inlined instances. + unsigned ConstantMembers = 0; + /// List of all Variables in this function. + SmallDenseMap VarsInFunction; + /// Compile units also cover a PC range, but have this flag set to false. + bool IsFunction = false; +}; + +/// Holds accumulated global statistics about local variables. +struct GlobalStats { + /// Total number of PC range bytes covered by DW_AT_locations. + unsigned ScopeBytesCovered = 0; + /// Total number of PC range bytes in each variable's enclosing scope, + /// starting from the first definition of the variable. + unsigned ScopeBytesFromFirstDefinition = 0; +}; + +/// Extract the low pc from a Die. +static uint64_t getLowPC(DWARFDie Die) { + if (Die.getAddressRanges().size()) + return Die.getAddressRanges()[0].LowPC; + return dwarf::toAddress(Die.find(dwarf::DW_AT_low_pc), 0); +} + +/// Collect debug info quality metrics for one DIE. +static void collectStatsForDie(DWARFDie Die, std::string Prefix, + uint64_t ScopeLowPC, uint64_t BytesInScope, + StringMap &FnStatMap, + GlobalStats &GlobalStats) { + bool HasLoc = false; + uint64_t BytesCovered = 0; + uint64_t OffsetToFirstDefinition = 0; + if (Die.find(dwarf::DW_AT_const_value)) { + // This catches constant members *and* variables. + HasLoc = true; + BytesCovered = BytesInScope; + } else if (Die.getTag() == dwarf::DW_TAG_variable || + Die.getTag() == dwarf::DW_TAG_formal_parameter) { + // Handle variables and function arguments. + auto FormValue = Die.find(dwarf::DW_AT_location); + HasLoc = FormValue.hasValue(); + if (HasLoc) { + // Get PC coverage. + if (auto DebugLocOffset = FormValue->getAsSectionOffset()) { + auto *DebugLoc = Die.getDwarfUnit()->getContext().getDebugLoc(); + if (auto List = DebugLoc->getLocationList(*DebugLocOffset)) { + for (auto Entry : List->Entries) + BytesCovered += Entry.End - Entry.Begin; + if (List->Entries.size()) { + uint64_t FirstDef = List->Entries[0].Begin; + uint64_t UnitOfs = getLowPC(Die.getDwarfUnit()->getUnitDIE()); + // Ranges sometimes start before the lexical scope. + if (UnitOfs + FirstDef >= ScopeLowPC) + OffsetToFirstDefinition = UnitOfs + FirstDef - ScopeLowPC; + // Or even after it. Count that as a failure. + if (OffsetToFirstDefinition > BytesInScope) + OffsetToFirstDefinition = 0; + } + } + assert(BytesInScope); + } else { + // Assume the entire range is covered by a single location. + BytesCovered = BytesInScope; + } + } + } else { + // Not a variable or constant member. + return; + } + + // Collect PC range coverage data. + auto &FnStats = FnStatMap[Prefix]; + const char *Name = Die.getName(DINameKind::ShortName); + FnStats.VarsInFunction.insert({Name, 0}); + if (BytesInScope) { + FnStats.TotalVarWithLoc += (unsigned)HasLoc; + // Adjust for the fact the variables often start their lifetime in the + // middle of the scope. + BytesInScope -= OffsetToFirstDefinition; + // Turns out we have a lot of ranges that extend past the lexical scope. + GlobalStats.ScopeBytesCovered += std::min(BytesInScope, BytesCovered); + GlobalStats.ScopeBytesFromFirstDefinition += BytesInScope; + assert(GlobalStats.ScopeBytesCovered <= + GlobalStats.ScopeBytesFromFirstDefinition); + } else { + FnStats.ConstantMembers++; + } +} + +/// Recursively collect debug info quality metrics. +static void collectStatsRecursive(DWARFDie Die, std::string Prefix, + uint64_t ScopeLowPC, uint64_t BytesInScope, + StringMap &FnStatMap, + GlobalStats &GlobalStats) { + // Handle any kind of lexical scope. + if (Die.getTag() == dwarf::DW_TAG_subprogram || + Die.getTag() == dwarf::DW_TAG_inlined_subroutine || + Die.getTag() == dwarf::DW_TAG_lexical_block) { + // Ignore forward declarations. + if (Die.find(dwarf::DW_AT_declaration)) + return; + + // Count the function. + if (Die.getTag() != dwarf::DW_TAG_lexical_block) { + StringRef Name = Die.getName(DINameKind::LinkageName); + if (Name.empty()) + Name = Die.getName(DINameKind::ShortName); + Prefix = Name; + // Skip over abstract origins. + if (Die.find(dwarf::DW_AT_inline)) + return; + // We've seen an (inlined) instance of this function. + auto &FnStats = FnStatMap[Name]; + FnStats.NumFnInlined++; + FnStats.IsFunction = true; + } + + // PC Ranges. + auto Ranges = Die.getAddressRanges(); + uint64_t BytesInThisScope = 0; + for (auto Range : Ranges) + BytesInThisScope += Range.HighPC - Range.LowPC; + ScopeLowPC = getLowPC(Die); + + if (BytesInThisScope) + BytesInScope = BytesInThisScope; + } else { + // Not a scope, visit the Die itself. It could be a variable. + collectStatsForDie(Die, Prefix, ScopeLowPC, BytesInScope, FnStatMap, + GlobalStats); + } + + // Traverse children. + DWARFDie Child = Die.getFirstChild(); + while (Child) { + collectStatsRecursive(Child, Prefix, ScopeLowPC, BytesInScope, FnStatMap, + GlobalStats); + Child = Child.getSibling(); + } +} + +/// Print machine-readable to stdout, human-readable to stderr. +/// The machine-readable format is single-line JSON output. +/// \{ +static void printDatum(const char *Key, StringRef Value) { + llvm::outs() << ",\"" << Key << "\":\"" << Value << '"'; + llvm::errs() << Key << ": " << Value << '\n'; +} +static void printDatum(const char *Key, uint64_t Value) { + llvm::outs() << ",\"" << Key << "\":" << Value; + llvm::errs() << Key << ": " << Value << '\n'; +} +/// \} + +/// 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. +void collectStats(DIContext &DICtx, StringRef Filename, StringRef FormatName) { + GlobalStats GlobalStats; + StringMap Statistics; + for (const auto &CU : static_cast(&DICtx)->compile_units()) + if (DWARFDie CUDie = CU->getUnitDIE(false)) + collectStatsRecursive(CUDie, "/", 0, 0, Statistics, GlobalStats); + + /// 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 = 1; + unsigned VarTotal = 0; + unsigned VarUnique = 0; + unsigned VarWithLoc = 0; + unsigned NumFunctions = 0; + unsigned NumInlinedFunctions = 0; + for (auto &Entry : Statistics) { + PerFunctionStats &Stats = Entry.getValue(); + unsigned TotalVars = Stats.VarsInFunction.size() * Stats.NumFnInlined; + unsigned Constants = Stats.ConstantMembers; + VarWithLoc += Stats.TotalVarWithLoc + Constants; + VarTotal += TotalVars + Constants; + VarUnique += Stats.VarsInFunction.size(); + DEBUG(for (auto V + : Stats.VarsInFunction) llvm::dbgs() + << Entry.getKey() << ": " << V.first << "\n"); + NumFunctions += Stats.IsFunction; + NumInlinedFunctions += Stats.IsFunction * Stats.NumFnInlined; + } + + // Print summary: Machine-readable to stdout, human-readable to stderr. + llvm::outs().SetBufferSize(1024); + llvm::outs() << "{\"version\":\"" << Version << '"'; + llvm::errs() << "Variable location quality metrics\n"; + llvm::errs() << "---------------------------------\n"; + printDatum("file", Filename); + printDatum("format", FormatName); + printDatum("source functions", NumFunctions); + printDatum("inlined functions", NumInlinedFunctions); + printDatum("unique source variables", VarUnique); + printDatum("source variables", VarTotal); + printDatum("variables with location", VarWithLoc); + printDatum("scope bytes total", GlobalStats.ScopeBytesFromFirstDefinition); + printDatum("scope bytes covered", GlobalStats.ScopeBytesCovered); + llvm::outs() << "}\n"; + llvm::errs() << "Total Availability: " + << (int)std::round((VarWithLoc * 100.0) / VarTotal) << "%\n"; + llvm::errs() << "PC Ranges covered: " + << (int)std::round((GlobalStats.ScopeBytesCovered * 100.0) / + GlobalStats.ScopeBytesFromFirstDefinition) + << "%\n"; + return; +} Index: tools/llvm-dwarfdump/llvm-dwarfdump.cpp =================================================================== --- tools/llvm-dwarfdump/llvm-dwarfdump.cpp +++ tools/llvm-dwarfdump/llvm-dwarfdump.cpp @@ -86,6 +86,9 @@ static cl::opt Brief("brief", cl::desc("Print fewer low-level details")); +static cl::opt + Statistics("statistics", cl::desc("Print debug info quality statistics")); + static void error(StringRef Filename, std::error_code EC) { if (!EC) return; @@ -93,14 +96,16 @@ exit(1); } +void collectStats(DIContext &DICtx, StringRef Filename, StringRef FormatName); + static void DumpObjectFile(ObjectFile &Obj, Twine Filename) { std::unique_ptr DICtx = DWARFContext::create(Obj); + if (Statistics) + return collectStats(*DICtx, Filename.str(), Obj.getFileFormatName()); + // Dump the complete DWARF structure. outs() << Filename.str() << ":\tfile format " << Obj.getFileFormatName() << "\n\n"; - - - // Dump the complete DWARF structure. DIDumpOptions DumpOpts; DumpOpts.DumpType = DumpType; DumpOpts.SummarizeTypes = SummarizeTypes;