WIP: [llvm-locstats] Add the llvm-locstats tool

[djtodoro]

Summary

As we discussed, I am sharing the patch that introduces the llvm-locstats tool.

(I am copying the summary from the README from https://github.com/djolertrk/llvm-locstats).

This tool calculates and reports verbose output for the debug location coverage of a binary.

It is very similar to a tool (locstats) from the Elfutils package, but the tool is not being maintained and released for a long time.

The llvm-locstats for each variable or formal parameter DIE computes what percentage from the code section bytes, where it is in scope, it has location description. There are options to ignore inlined instances or/and entry value locations. The line 0 shows the number (and the percentage) of DIEs with no location information, but the line 100 shows the number (and the percentage) of DIEs where there is location information in all code section bytes (where the variable or parameter is in the scope). The line 51..59 shows the number (and the percentage) of DIEs where the location information is in between 51 and 59 percentage of its scope covered.
...
Using the tool

Running the tool on a simple test case:
bin/llvm-locstats test

=================================================
          Debug Location Statistics
=================================================
  cov%          samples       percentage
-------------------------------------------------
    0                1              25%
    1..9             0               0%
    11..19           0               0%
    21..29           0               0%
    31..39           0               0%
    41..49           0               0%
    51..59           0               0%
    61..69           0               0%
    71..79           0               0%
    81..89           0               0%
    91..99           0               0%
    100              3              75%
=================================================
  -the number of debug variables processed: 4
  -the average coverage per var: ~ 75%
=================================================

Running the tool on the GDB 7.11 binary:
bin/llvm-locstats gdb

=================================================
          Debug Location Statistics
=================================================
  cov%          samples       percentage
-------------------------------------------------
    0             8495               8%
    1..9          3037               3%
    11..19        3015               3%
    21..29        2769               2%
    31..39        2802               2%
    41..49        2766               2%
    51..59        3141               3%
    61..69        3173               3%
    71..79        3923               3%
    81..89        4948               5%
    91..99        7354               7%
    100          53433              54%
=================================================
  -the number of debug variables processed: 98856
  -the average coverage per var: ~ 76%
=================================================

Running the tool on the GDB 7.11 binary by ignoring debug entry values:
bin/llvm-locstats --ignore-entry-values gdb

=================================================
          Debug Location Statistics
=================================================
  cov%          samples       percentage
-------------------------------------------------
    0             8765               8%
    1..9          3948               3%
    11..19        4436               4%
    21..29        4152               4%
    31..39        4107               4%
    41..49        3846               3%
    51..59        4490               4%
    61..69        4140               4%
    71..79        4998               5%
    81..89        7072               7%
    91..99       15478              15%
    100          33424              33%
=================================================
  -the number of debug variables processed: 98856
  -the average coverage per var: ~ 69%
=================================================

[aprantl]

As David said, this does look like it could fit into dwarfdump --statistics (tools/llvm-dwarfdump/Statistics.cpp).

[djtodoro]

@aprantl Thanks for your comment. WDYT about implementing this as a llvm-dwarfdump subtool?

I think that having a tool where we can add options to operate and output a verbose info on the debug location generated would be useful. As I said on the mailing list, not only reporting the results by ignoring some kind of debug location entry (inlined or entry values) is interested. Interested will be calculating what is the number of entry values that have corresponding call_site_param info, and calculate a new kind of stats (such as valuable entry values) and that is some kind of evaluation of the debug location generated. We can add more options that evaluate some other interesting things regarding the debug location, not only regarding the debug entry values feature. I agree that every single functionality I described can be embedded into the llvm-dwarfdump, but maybe the subtool can be a better solution.

[MaskRay]

llvm/tools/llvm-locstats/llvm-locstats.cpp

29

largest category -> number of categories

32

constexpr?

44

list<std::string>?

116

Place if inside LLVM_DEBUG otherwise gcc -Wall warns [-Wunused-variable]

120

[&](StringRef D)

123

clang-format this line

125

Delete IsEntryVal

138

if (auto FormValue = ...)

145

auto -> DWARFDebugLoc::Entry

147

IsEntryValue(Entry.Loc)

(I just changed the type of Loc to SmallString.)

183

++CumulNumOfVars;

228

auto -> DWARFAddressRange

243

for (DWARFDie Child : Die)

264

formatv(" {0,8} {1,8}", ..., ...) might be clearer

294

std::vector<int> LocStatistics(largest_cov_category, 0);

317

This function is also a candidate for inlining.

328

Can this function be inlined? (only called once)

331

Indent this line

334

*Buffer -> **BuffOrErr and delete Buffer.

358

Ideally these switches can be ORed together.

372

Trailing space.

[djtodoro]

@MaskRay Thanks for your review! We are still discussing on the llvm-dev mailing list how we should continue with this. As soon as we finished, I will start cleaning up the code and addressing comments.

[djtodoro]

@aprantl, @vsk,
IIUC, I can abandon this patch and make a separate patch(es) for adding additional fields into the llvm-dwarfdump stats output, and then make a script (and put into the utils/) parsing the fields by doing the locstats job?

[vsk]

In D65585#1618508, @djtodoro wrote:

@aprantl, @vsk,
IIUC, I can abandon this patch and make a separate patch(es) for adding additional fields into the llvm-dwarfdump stats output, and then make a script (and put into the utils/) parsing the fields by doing the locstats job?

+ 1, I think that would be great.

[djtodoro]

I am abandoning this and creating new revisions for the tool implemented as an utility (within utils/).

(back in the office now, sorry for the late response)

[djtodoro]

The revisions are: D66525 and D66526.

llvm/tools/llvm-locstats/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  DebugInfoDWARF
+  AllTargetsDescs
+  AllTargetsInfos
+  MC
+  Object
+  Support
+  )
+
+add_llvm_tool(llvm-locstats
+  llvm-locstats.cpp
+  )

llvm/tools/llvm-locstats/LLVMBuild.txt

+;===- ./tools/llvm-locstats/LLVMBuild.txt ---------------------*- Conf -*--===;
+;
+; 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
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Tool
+name = llvm-locstats
+parent = Tools
+required_libraries = DebugInfoDWARF Object

llvm/tools/llvm-locstats/llvm-locstats.cpp

+//===-- llvm-locstats.cpp - Debug location coverage utility for llvm ------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This program is a utility that works like debug location coverage calculator.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/Object/MachOUniversal.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Support/WithColor.h"
+#include "llvm/Support/raw_ostream.h"
+
+#define DEBUG_TYPE "locstats"
+using namespace llvm;
+using namespace object;
+
+/// This represents the largest category of debug location coverage being
+/// calculated. The first category is 0% location coverage, but the last
+/// category is 100% location coverage.
+static const int largest_cov_category = 12;
+
+/// @}
+/// Command line options.
+/// @{
+
+namespace {
+using namespace cl;
+
+OptionCategory LocStatsCategory("Specific Options");
+static opt<bool> Help("h", desc("Alias for -help"), Hidden,
+                      cat(LocStatsCategory));
+static opt<std::string>
+    InputFilename(Positional, desc("<input object file>"),
+                  cat(LocStatsCategory));
+static opt<std::string>
+    OutputFilename("out-file", cl::init("-"),
+                   cl::desc("Redirect output to the specified file."),
+                   cl::value_desc("filename"),
+                   cat(LocStatsCategory));
+static alias OutputFilenameAlias("o", desc("Alias for -out-file."),
+                                 aliasopt(OutputFilename),
+                                 cat(LocStatsCategory));
+static opt<bool>
+    OnlyFormalParameters("only-formal-parameters",
+         desc("Calculate the location statistics only for formal parameters."),
+         cat(LocStatsCategory));
+static opt<bool>
+    OnlyVariables("only-variables",
+         desc("Calculate the location statistics only for local variables."),
+         cat(LocStatsCategory));
+static opt<bool>
+    IgnoreInlined("ignore-inlined",
+         desc("Ignore the location statistics on inlined instances."),
+         cat(LocStatsCategory));
+static opt<bool>
+    IgnoreEntryValues("ignore-entry-values",
+         desc("Ignore the location statistics on locations with entry values."),
+         cat(LocStatsCategory));
+} // namespace
+/// @}
+//===----------------------------------------------------------------------===//
+
+using HandlerFn = std::function<void(ObjectFile &, DWARFContext &DICtx, Twine,
+                                     raw_ostream &)>;
+
+/// Extract the low pc from a Die.
+static uint64_t getLowPC(DWARFDie Die) {
+  auto RangesOrError = Die.getAddressRanges();
+  DWARFAddressRangesVector Ranges;
+  if (RangesOrError)
+    Ranges = RangesOrError.get();
+  else
+    llvm::consumeError(RangesOrError.takeError());
+  if (Ranges.size())
+    return Ranges[0].LowPC;
+  return dwarf::toAddress(Die.find(dwarf::DW_AT_low_pc), 0);
+}
+
+static void collectLocStatsForDie(DWARFDie Die, uint64_t ScopeLowPC,
+                                  uint64_t BytesInScope,
+                                  std::map<int, unsigned long> &LocStatistics,
+                                  unsigned &CumulNumOfVars,
+                                  double &TotalAverage,
+                                  DWARFContext &DICtx) {
+  if (Die.getTag() == dwarf::DW_TAG_variable && OnlyFormalParameters)
+    return;
+  if (Die.getTag() == dwarf::DW_TAG_formal_parameter && OnlyVariables)
+    return;
+
+  // Ignore declarations and artificial variables.
+  if (Die.find(dwarf::DW_AT_declaration) || Die.find(dwarf::DW_AT_artificial))
+    return;
+
+  // Also ignore extern globals with no DW_AT_location.
+  if (Die.find(dwarf::DW_AT_external) && !Die.find(dwarf::DW_AT_location))
+    return;
+
+  // Ignore subroutine types.
+  if (Die.getTag() == dwarf::DW_TAG_formal_parameter &&
+      Die.getParent().getTag() == dwarf::DW_TAG_subroutine_type)
+    return;
+
+  if (auto name = Die.getName(DINameKind::ShortName))
+    LLVM_DEBUG(llvm::dbgs() << "    -var (or formal param): " << name << "\n");
+
+  double Coverage = 0;
+
+  auto IsEntryValue = [&] (StringRef D) -> bool {
+    DWARFUnit *U = Die.getDwarfUnit();
+    DataExtractor Data(D, DICtx.isLittleEndian(), 0);
+    DWARFExpression Expression(Data, U->getVersion(),
+                               U->getAddressByteSize());
+    bool IsEntryVal = llvm::any_of(Expression,
+                                  [](DWARFExpression::Operation &Op) {
+      return Op.getCode() == dwarf::DW_OP_entry_value ||
+             Op.getCode() == dwarf::DW_OP_GNU_entry_value;
+    });
+    return IsEntryVal;
+  };
+
+  if (Die.find(dwarf::DW_AT_const_value))
+    // This catches constant members *and* variables.
+    Coverage = 100;
+  else {
+    // Handle variables and function arguments location.
+    auto FormValue = Die.find(dwarf::DW_AT_location);
+    if (FormValue.hasValue()) {
+      uint64_t Covered = 0;
+      // Get PC coverage.
+      if (auto DebugLocOffset = FormValue->getAsSectionOffset()) {
+        auto *DebugLoc = Die.getDwarfUnit()->getContext().getDebugLoc();
+        if (auto List = DebugLoc->getLocationListAtOffset(*DebugLocOffset)) {
+          for (auto Entry : List->Entries) {
+            if (IgnoreEntryValues &&
+                IsEntryValue({Entry.Loc.data(), Entry.Loc.size()}))
+              continue;
+            Covered += Entry.End - Entry.Begin;
+          }
+        }
+
+        // This is wrong location list.
+        if (Covered > BytesInScope) {
+          Covered = BytesInScope;
+          LLVM_DEBUG(llvm::dbgs() << "      -WRONG LOCATION LIST!!!\n");
+        }
+
+        Coverage = 100 * (double)Covered / BytesInScope;
+      } else {
+        // Assume the entire range is covered by a single location.
+        Coverage = 100;
+      }
+    } else {
+      // No at_location attribute.
+      Coverage = 0;
+    }
+  }
+
+  LLVM_DEBUG(llvm::dbgs() << "      -coverage is " << (int)Coverage << "%\n");
+
+  int CoverageRounded = (int)Coverage;
+  TotalAverage += CoverageRounded;
+  int PercentageKey;
+  if (CoverageRounded == 0)
+    PercentageKey = 0;
+  else if (CoverageRounded == 100)
+    PercentageKey = largest_cov_category - 1;
+  else
+    PercentageKey = CoverageRounded / 10 + 1;
+
+  LocStatistics[PercentageKey]++;
+  CumulNumOfVars++;
+}
+
+static void collectStatsRecursive(DWARFDie Die, uint64_t ScopeLowPC,
+                                  uint64_t BytesInScope,
+                                  std::map<int, unsigned long> &LocStatistics,
+                                  unsigned &CumulNumOfVars,
+                                  double &TotalAverage,
+                                  DWARFContext &DICtx) {
+  const dwarf::Tag Tag = Die.getTag();
+  const bool IsFunction = Tag == dwarf::DW_TAG_subprogram;
+  const bool IsBlock = Tag == dwarf::DW_TAG_lexical_block;
+  // TODO: Add a separate option to track inlined functions.
+  const bool IsInlinedFunction = Tag == dwarf::DW_TAG_inlined_subroutine;
+  if (IsFunction || IsInlinedFunction || IsBlock) {
+    if (auto name = Die.getName(DINameKind::ShortName))
+    LLVM_DEBUG(llvm::dbgs() << "The function beeing processed is: "
+                            << name<< "\n");
+
+    // Ignore forward declarations.
+    if (Die.find(dwarf::DW_AT_declaration)) {
+      LLVM_DEBUG(llvm::dbgs() << "  -declaration ignored\n");
+      return;
+    }
+
+    // Ignore inlined subprograms.
+    if (Die.find(dwarf::DW_AT_inline)) {
+      LLVM_DEBUG(llvm::dbgs() << "  -inlined subprogram ignored\n");
+      return;
+    }
+
+    if (IgnoreInlined && IsInlinedFunction) {
+      LLVM_DEBUG(llvm::dbgs() << "  -an inlined instance ignored\n");
+      return;
+    }
+
+    // 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;
+    ScopeLowPC = getLowPC(Die);
+
+    LLVM_DEBUG(llvm::dbgs() << "  -the coverage: " << BytesInThisScope
+                            << " (bytes)\n");
+    BytesInScope = BytesInThisScope;
+  } else if (Die.getTag() == dwarf::DW_TAG_variable ||
+             Die.getTag() == dwarf::DW_TAG_formal_parameter) {
+    collectLocStatsForDie(Die, ScopeLowPC, BytesInScope, LocStatistics,
+                          CumulNumOfVars, TotalAverage, DICtx);
+  }
+
+  // Traverse children.
+  DWARFDie Child = Die.getFirstChild();
+  while (Child) {
+    collectStatsRecursive(Child, ScopeLowPC, BytesInScope, LocStatistics,
+                          CumulNumOfVars, TotalAverage, DICtx);
+    Child = Child.getSibling();
+  }
+}
+
+static void outputLocStats(std::map<int, unsigned long> &LocStatistics,
+                           unsigned &CumulNumOfVars, double &TotalAverage,
+                           raw_ostream &OS) {
+  if (CumulNumOfVars == 0) {
+    OS << "No coverage recorded.\n";
+    return;
+  }
+
+  OS << "=================================================\n";
+  OS << "           Debug Location Statistics\n";
+  OS << "=================================================\n";
+  OS << "    cov%        samples        percentage\n";
+  OS << "-------------------------------------------------\n";
+  OS << "    0"
+     << "         " << format_decimal(LocStatistics[0], 8) << "        "
+     << format_decimal((int)(LocStatistics[0] / (double)CumulNumOfVars * 100),
+                       8)
+     << "%\n";
+  OS << "    1..9"
+     << "      " << format_decimal(LocStatistics[1], 8) << "        "
+     << format_decimal((int)(LocStatistics[1] / (double)CumulNumOfVars * 100),
+                       8)
+     << "%\n";
+  for (unsigned i = 2; i < 11; ++i)
+    OS << "    " << (i - 1) * 10 + 1 << ".." << i * 10 - 1 << "    "
+       << format_decimal(LocStatistics[i], 8) << "        "
+       << format_decimal((int)(LocStatistics[i] / (double)CumulNumOfVars * 100),
+                         8)
+       << "%\n";
+  OS << "    100"
+     << "       " << format_decimal(LocStatistics[11], 8) << "        "
+     << format_decimal((int)(LocStatistics[11] / (double)CumulNumOfVars * 100),
+                       8)
+     << "%\n";
+  OS << "=================================================\n";
+  OS << "-the number of debug variables processed: " << CumulNumOfVars << "\n";
+  OS << "-the average coverage per var: ~ "
+     << (int)std::round((TotalAverage/CumulNumOfVars * 100) / 100) << "%\n";
+  OS << "=================================================\n";
+}
+
+static void collectLocstats(ObjectFile &Obj, DWARFContext &DICtx,
+                            Twine Filename, raw_ostream &OS) {
+  // Map percentage->occurrences.
+  std::map<int, unsigned long> LocStatistics;
+  for (int i = 0; i < largest_cov_category; ++i)
+    LocStatistics[i] = 0;
+
+  unsigned CumulNumOfVars = 0;
+  double TotalAverage = 0.0;
+  
+  for (const auto &CU : static_cast<DWARFContext *>(&DICtx)->compile_units())
+    if (DWARFDie CUDie = CU->getNonSkeletonUnitDIE(false))
+      collectStatsRecursive(CUDie, 0, 0, LocStatistics, CumulNumOfVars,
+                            TotalAverage, DICtx);
+
+  // Output the results.
+  outputLocStats(LocStatistics, CumulNumOfVars, TotalAverage, OS);
+}
+
+static void error(StringRef Prefix, std::error_code EC) {
+  if (!EC)
+    return;
+  WithColor::error() << Prefix << ": " << EC.message() << "\n";
+  exit(1);
+}
+
+static void handleBuffer(StringRef Filename, MemoryBufferRef Buffer,
+                         HandlerFn HandleObj, raw_ostream &OS) {
+  Expected<std::unique_ptr<Binary>> BinOrErr = object::createBinary(Buffer);
+  error(Filename, errorToErrorCode(BinOrErr.takeError()));
+
+  if (auto *Obj = dyn_cast<ObjectFile>(BinOrErr->get())) {
+    std::unique_ptr<DWARFContext> DICtx = DWARFContext::create(*Obj);
+    HandleObj(*Obj, *DICtx, Filename, OS);
+  }
+}
+
+static void handleFile(StringRef Filename, HandlerFn HandleObj,
+                       raw_ostream &OS) {
+  ErrorOr<std::unique_ptr<MemoryBuffer>> BuffOrErr =
+  MemoryBuffer::getFileOrSTDIN(Filename);
+  error(Filename, BuffOrErr.getError());
+  std::unique_ptr<MemoryBuffer> Buffer = std::move(BuffOrErr.get());
+  handleBuffer(Filename, *Buffer, HandleObj, OS);
+}
+
+int main(int argc, char **argv) {
+  InitLLVM X(argc, argv);
+
+  llvm::InitializeAllTargetInfos();
+  llvm::InitializeAllTargetMCs();
+
+  HideUnrelatedOptions({&LocStatsCategory});
+  cl::ParseCommandLineOptions(
+      argc, argv,
+      "calculate debug location coverage on an input file.\n");
+
+  if (Help) {
+    PrintHelpMessage(false, true);
+    return 0;
+  }
+
+  if (InputFilename == "") {
+    WithColor::error(errs()) << "no input file\n";
+    exit(1);
+  }
+
+  if (OnlyFormalParameters && OnlyVariables) {
+    WithColor::error() << "incompatible arguments: specifying both "
+                          "-only-formal-parameters and -only-variables is "
+                          "not allowed.";
+    return 0;
+  }
+
+  std::error_code EC;
+  ToolOutputFile OutputFile(OutputFilename, EC, sys::fs::OF_None);
+  error("Unable to open output file" + OutputFilename, EC);
+  // Don't remove output file if we exit with an error.
+  OutputFile.keep();
+
+  handleFile(InputFilename, collectLocstats, OutputFile.os());
+ 
+  return EXIT_SUCCESS;
+}