[llvm-dwarfdump][Statistics] Distinguish functions/variables with same name across different CUs

[krisb]

Summary

Different variables and functions might have the same name in different CU.
To calculate 'Availability' metric more accurate (i.e. to avoid getting
availability above 100%), we need to have some additional logic to
distinguish between them.

The patch introduces a DIE identifier that consists of a function/variable name
and declaration information: a filename and a line number. This allows
distinguishing different functions/variables (different means declared in
different files/lines) with the same name, keeping duplicates counted
as duplicates.

This patch is the first one from a set of 6 that aims to improve 'Availability' statistics. 

For testing purposes, I used clang-3.4 non-optimized build and here are
the results for 10 most 'heavy' binaries before and after all the 6 patches:

             |   "source   |      baseline(master)    |         patched          |
Binary name  |  variables" | "Availability" | time(s) | "Availability" | time(s) |
----------------------------------------------------------------------------------
opt          |    637923   |         214%   |   1.644 |         100%   |   2.47  |
lli          |    362669   |         177%   |   0.898 |          99%   |   1.346 |
diagtool     |    459671   |         184%   |   1.399 |         100%   |   2.103 |
arcmt-test   |    572726   |         180%   |   1.665 |         100%   |   2.53  |
llc          |    527603   |         200%   |   1.431 |         100%   |   2.282 |
clang-3.4    |   1445548   |         208%   |   4.33  |         100%   |   6.413 |
llvm-lto     |    629415   |         208%   |   1.652 |         100%   |   2.666 |
clang-check  |    621696   |         195%   |   2.108 |         100%   |   3.302 |
clang-format |    470768   |         184%   |   1.429 |          99%   |   2.154 |
llvm-c-test  |    478700   |         200%   |   1.302 |         100%   |   2.033 |

[aprantl]

This five patches reduces 'total availability' metric of clang binary (debug build) from 126% to 87%.

For a debug build you'd expect 100% where are the missing 13% coming from?

Otherwise this change seems to go into the right direction.

llvm/tools/llvm-dwarfdump/Statistics.cpp

397

When are these generated? Could we write something more descriptive into the comment?

[djtodoro]

Nice, thanks! Please post the rest of the patches, when you are ready, and make a stack of the patches.

This five patches reduces 'total availability' metric of clang binary
(debug build) from 126% to 87%.

I guess we are talking about the build with -g -O2?

llvm/tools/llvm-dwarfdump/Statistics.cpp

160

Could you please add an explanation here why '(probably)'?

[djtodoro]

In D72797#1823452, @djtodoro wrote:

Nice, thanks! Please post the rest of the patches, when you are ready, and make a stack of the patches.

This five patches reduces 'total availability' metric of clang binary
(debug build) from 126% to 87%.

I guess we are talking about the build with -g -O2?

Or any level of optimization higher than -O0 + -g.

[krisb]

Applied the comments.

[krisb]

@aprantl @djtodoro thanks for the comments!

I updated the description adding more clear and reproducible testing results for 'O0' build.
There is no 100% of availability even on non-optimized build because of 2 issues:

• some variables really don't have locations. They are usually artificial or global variables, but the number of them is really small (for example, 46/1435958 for clang-34 binary).
• parameters may have different DW_AT_decl_file and DW_AT_decl_line among instances of the same function. It looks like this happens when a function has its declaration and definition in different header files. So, one can find something like this in dwarf (these are two concrete out-of-line instances of the same 'foo' function).

DW_TAG_subprogram
  DW_AT_name  ("foo")
  DW_AT_decl_file ("definition.h")
  DW_AT_decl_line (222)
  DW_TAG_formal_parameter
    DW_AT_name  ("__a")
    DW_AT_decl_file ("declaration.h")
    DW_AT_decl_line (370)
  DW_TAG_formal_parameter
    DW_AT_name  ("__b")
    DW_AT_decl_file ("declaration.h")
    DW_AT_decl_line (370)

DW_TAG_subprogram
  DW_AT_name  ("foo")
  DW_AT_decl_file ("definition.h")
  DW_AT_decl_line (222)
  DW_TAG_formal_parameter
    DW_AT_name  ("__a")
    DW_AT_decl_file ("definition.h")
    DW_AT_decl_line (222)
  DW_TAG_formal_parameter
    DW_AT_name  ("__b")
    DW_AT_decl_file ("definition.h")
    DW_AT_decl_line (222)

So, this increases number of 'total vars' because these 'a' and 'b' variables counted twice.

I also was a bit optimistic about how this patch(es) affects the performance of the statistics, it actually became two times slower than before the patches.

llvm/tools/llvm-dwarfdump/Statistics.cpp

397

I haven't had a chance to debug such cases properly, but I believe they are a result of some bugs in dwarf generation flow.
Such functions have no attributes at all but can contain some children (usually structures or classes). So, I removed the check by now cause it's better to fix the issue in dwarf generation than workaround it in statistics.

[djtodoro]

Thanks for doing this!

So, this increases number of 'total vars' because these 'a' and 'b' variables counted twice.

I see... Can we do something to avoid the additional calculation? Somehow to recognize we already observed the a and b, although they have different DIE ID.

I also was a bit optimistic about how this patch(es) affects the performance of the statistics, it actually became two times slower than before the patches.

What patch from the stack adds the overhead? This one?

[krisb]

In D72797#1829031, @djtodoro wrote:

So, this increases number of 'total vars' because these 'a' and 'b' variables counted twice.

I see... Can we do something to avoid the additional calculation? Somehow to recognize we already observed the a and b, although they have different DIE ID.

I also was a bit optimistic about how this patch(es) affects the performance of the statistics, it actually became two times slower than before the patches.

What patch from the stack adds the overhead? This one?

Yeah, this one mostly causes the overhead.
Actually, adding declaration info for ID is only necessary for functions, global variables, and members (because we need to handle static/inline functions/variables, and don't respect namespaces, classes, and structures). For local variables and parameters, Prefix + Name should be enough to distinguish all the cases (because their prefix already guaranteed uniqueness, for parameters the prefix is going to be added in D73003).
This approach shows better results:

             |   "source   |      baseline(master)    |         patched          |
Binary name  |  variables" | "Availability" | time(s) | "Availability" | time(s) |
----------------------------------------------------------------------------------
opt          |    637923   |         214%   |   1.644 |         100%   |   2.47  |
lli          |    362669   |         177%   |   0.898 |          99%   |   1.346 |
diagtool     |    459671   |         184%   |   1.399 |         100%   |   2.103 |
arcmt-test   |    572726   |         180%   |   1.665 |         100%   |   2.53  |
llc          |    527603   |         200%   |   1.431 |         100%   |   2.282 |
clang-3.4    |   1445548   |         208%   |   4.33  |         100%   |   6.413 |
llvm-lto     |    629415   |         208%   |   1.652 |         100%   |   2.666 |
clang-check  |    621696   |         195%   |   2.108 |         100%   |   3.302 |
clang-format |    470768   |         184%   |   1.429 |          99%   |   2.154 |
llvm-c-test  |    478700   |         200%   |   1.302 |         100%   |   2.033 |

It also reduces the overhead of this patch to up to 61% (instead of up to 100% previously).
With this approach, we have a really small amount of 'collisions' but still have some.
I'll update the patch when I find the reason for the 'collisions' left.

[krisb]

Use declaration info only to identify functions, global variables, and members.

[krisb]

@djtodoro those two binaries with 99% of availability just have some variables w/o locations (mostly artificial 'this' parameters of member functions).
But this change reveals one more interesting case.
For code like this:

int foo() {
	if (cond1) {
		static const int a = 1;
		...
	}
	if (cond2) {
		static const int a = 1;
		...
	}
}

clang (unlike gcc) generates both a variables in the function scope, not in a corresponded DW_TAG_lexical_block (as gcc does).
I'm not sure clang is right here, cause a - despite it is static - isn't visible outside the if.
What do you think about this?

[djtodoro]

Hmm.. it looks lika a bug.

@aprantl What do you think?

[aprantl]

In D72797#1834089, @djtodoro wrote:

Hmm.. it looks lika a bug.

@aprantl What do you think?

If they are two separate (storage) variables that is a bug. Can you file a PR on bugzilla (libraries/debuginfo) and CC the usual suspects?

[krisb]

@djtodoro @aprantl thanks for reviewing this whole set of patches!

I've opened a PR for that issue with static variables https://bugs.llvm.org/show_bug.cgi?id=44695

llvm/test/tools/llvm-dwarfdump/X86/stats-multiple-cu-same-name.ll

+; RUN: llc -O0 %s -o - -filetype=obj \
+; RUN:   | llvm-dwarfdump -statistics - | FileCheck %s
+
+; Test that statistics distinguish functions with the same name.
+
+; CHECK:      "source functions":4,
+; CHECK-SAME: "unique source variables":2
+; CHECK-SAME: "source variables":2
+
+; $ cat test1.cpp
+; static int foo(int a) {
+;   return a;
+; }
+; int boo() { return foo(42); }
+;
+; $ cat test2.cpp
+; static int foo(int a) {
+;   return a;
+; }
+; int bar() { return foo(42); }
+
+source_filename = "llvm-link"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: noinline optnone uwtable
+define dso_local i32 @_Z3boov() !dbg !9 {
+entry:
+  %call = call i32 @_ZL3fooi(i32 42), !dbg !13
+  ret i32 %call
+}
+; Function Attrs: noinline nounwind optnone uwtable
+define internal i32 @_ZL3fooi(i32 %a) !dbg !15 {
+entry:
+  %a.addr = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %a.addr, metadata !18, metadata !DIExpression()), !dbg !19
+  %0 = load i32, i32* %a.addr, align 4, !dbg !20
+  ret i32 %0
+}
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+; Function Attrs: noinline optnone uwtable
+define dso_local i32 @_Z3barv() !dbg !22 {
+entry:
+  %call = call i32 @_ZL3fooi.1(i32 442), !dbg !23
+  ret i32 %call
+}
+; Function Attrs: noinline nounwind optnone uwtable
+define internal i32 @_ZL3fooi.1(i32 %a) !dbg !25 {
+entry:
+  %a.addr = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %a.addr, metadata !26, metadata !DIExpression()), !dbg !27
+  %0 = load i32, i32* %a.addr, align 4, !dbg !28
+  %mul = mul nsw i32 %0, 2
+  ret i32 %mul
+}
+
+!llvm.dbg.cu = !{!0, !3}
+!llvm.ident = !{!5, !5}
+!llvm.module.flags = !{!6, !7, !8}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 10.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "test1.cpp", directory: "/")
+!2 = !{}
+!3 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !4, producer: "clang version 10.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!4 = !DIFile(filename: "test2.cpp", directory: "/")
+!5 = !{!"clang version 10.0.0"}
+!6 = !{i32 7, !"Dwarf Version", i32 4}
+!7 = !{i32 2, !"Debug Info Version", i32 3}
+!8 = !{i32 1, !"wchar_size", i32 4}
+!9 = distinct !DISubprogram(name: "boo", linkageName: "_Z3boov", scope: !1, file: !1, line: 5, type: !10, scopeLine: 5, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!10 = !DISubroutineType(types: !11)
+!11 = !{!12}
+!12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!13 = !DILocation(line: 6, column: 10, scope: !9)
+!15 = distinct !DISubprogram(name: "foo", linkageName: "_ZL3fooi", scope: !1, file: !1, line: 1, type: !16, scopeLine: 1, flags: DIFlagPrototyped, spFlags: DISPFlagLocalToUnit | DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!16 = !DISubroutineType(types: !17)
+!17 = !{!12, !12}
+!18 = !DILocalVariable(name: "a", arg: 1, scope: !15, file: !1, line: 1, type: !12)
+!19 = !DILocation(line: 1, column: 20, scope: !15)
+!20 = !DILocation(line: 2, column: 10, scope: !15)
+!22 = distinct !DISubprogram(name: "bar", linkageName: "_Z3barv", scope: !4, file: !4, line: 5, type: !10, scopeLine: 5, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !3, retainedNodes: !2)
+!23 = !DILocation(line: 6, column: 10, scope: !22)
+!25 = distinct !DISubprogram(name: "foo", linkageName: "_ZL3fooi", scope: !4, file: !4, line: 1, type: !16, scopeLine: 1, flags: DIFlagPrototyped, spFlags: DISPFlagLocalToUnit | DISPFlagDefinition, unit: !3, retainedNodes: !2)
+!26 = !DILocalVariable(name: "a", arg: 1, scope: !25, file: !4, line: 1, type: !12)
+!27 = !DILocation(line: 1, column: 20, scope: !25)
+!28 = !DILocation(line: 2, column: 10, scope: !25)

llvm/tools/llvm-dwarfdump/Statistics.cpp

static void collectLocStats(uint64_t BytesCovered, uint64_t BytesInScope,
 
   unsigned CoverageBucket = getCoverageBucket();
   VarParamLocStats[CoverageBucket]++;
   if (IsParam)
     ParamLocStats[CoverageBucket]++;
   else if (IsLocalVar)
     VarLocStats[CoverageBucket]++;
 }
+/// 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 keep the same among different instances of the same entity.
+/// Constructing the ID this way cannot garantee full uniqueness (in case of
+/// entities with the same name and accidentally matching or missed
+/// declaration info).
+static std::string constructDieID(DWARFDie Die,
+                                  StringRef Prefix = StringRef()) {
+  std::string IDStr;
+  llvm::raw_string_ostream ID(IDStr);
+  ID << Prefix
+     << Die.getName(DINameKind::LinkageName) << ":";
+
+  auto DeclFile = Die.findRecursively(dwarf::DW_AT_decl_file);
+  std::string File;
+  if (DeclFile) {
+    DWARFUnit *U = Die.getDwarfUnit();
+    if (const auto *LT = U->getContext().getLineTableForUnit(U))
+      if (LT->getFileNameByIndex(
+              dwarf::toUnsigned(DeclFile, 0), U->getCompilationDir(),
+              DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, File))
+        File = sys::path::filename(File);
+  }
+  if (File.empty())
+    ID << "/";
+  else
+    ID << File;
+
+  ID << ":"
+     << dwarf::toUnsigned(Die.findRecursively(dwarf::DW_AT_decl_line), 0);
+  ID.str();
+  return IDStr;
+}
 
 /// Collect debug info quality metrics for one DIE.
 static void collectStatsForDie(DWARFDie Die, std::string FnPrefix,
                                std::string VarPrefix, uint64_t BytesInScope,
                                uint32_t InlineDepth,
                                StringMap<PerFunctionStats> &FnStatMap,
                                GlobalStats &GlobalStats,
                                LocationStats &LocStats) {
collectLocStats(BytesCovered - BytesEntryValuesCovered, BytesInScope,
                     LocStats.ParamNonEntryValLocStats,
                     LocStats.VarNonEntryValLocStats, IsParam, IsLocalVar);
   }
 
   // Collect PC range coverage data.
   if (DWARFDie D =
           Die.getAttributeValueAsReferencedDie(dwarf::DW_AT_abstract_origin))
     Die = D;
-  // By using the variable name + the path through the lexical block tree, the
-  // keys are consistent across duplicate abstract origins in different CUs.
-  std::string VarName = StringRef(Die.getName(DINameKind::ShortName));
-  FnStats.VarsInFunction.insert(VarPrefix + VarName);
+
+  std::string VarID = constructDieID(Die, VarPrefix);
+  FnStats.VarsInFunction.insert(VarID);
+
   if (BytesInScope) {
     FnStats.TotalVarWithLoc += (unsigned)HasLoc;
     // Turns out we have a lot of ranges that extend past the lexical scope.
     GlobalStats.ScopeBytesCovered += std::min(BytesInScope, BytesCovered);
     GlobalStats.ScopeBytes += BytesInScope;
     GlobalStats.ScopeEntryValueBytesCovered += BytesEntryValuesCovered;
     if (IsParam) {
       GlobalStats.ParamScopeBytesCovered +=
if (IsFunction || IsInlinedFunction || IsBlock) {
 
     auto Ranges = RangesOrError.get();
     uint64_t BytesInThisScope = 0;
     for (auto Range : Ranges)
       BytesInThisScope += Range.HighPC - Range.LowPC;
 
     // Count the function.
     if (!IsBlock) {
-      StringRef Name = Die.getName(DINameKind::LinkageName);
-      if (Name.empty())
-        Name = Die.getName(DINameKind::ShortName);
-      FnPrefix = Name;
       // Skip over abstract origins.
       if (Die.find(dwarf::DW_AT_inline))
         return;
+      std::string FnID = constructDieID(Die);
       // We've seen an (inlined) instance of this function.
-      auto &FnStats = FnStatMap[Name];
+      auto &FnStats = FnStatMap[FnID];
+      FnStats.IsFunction = true;
       if (IsInlinedFunction) {
         FnStats.NumFnInlined++;
         if (Die.findRecursively(dwarf::DW_AT_abstract_origin))
           FnStats.NumAbstractOrigins++;
       }
       FnStats.IsFunction = true;
       if (BytesInThisScope && !IsInlinedFunction)
         FnStats.HasPCAddresses = true;
-      std::string FnName = StringRef(Die.getName(DINameKind::ShortName));
       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;
       else if (IsInlinedFunction && InlineDepth == 0)
         GlobalStats.InlineFunctionSize += BytesInThisScope;