[llvm-dwarfdump][Statistics] Handle LTO cases with cross CU referencing

With link-time optimizations enabled, resulting DWARF mayend up containing
cross CU references (through the DW_AT_abstract_origin attribute).
Consider the following example:

// sum.c
__attribute__((always_inline)) int sum(int a, int b)
{
     return a + b;
}
// main.c
extern int sum(int, int);
int main()
{
     int a = 5, b = 10, c = sum(a, b);
     return 0;
}

Compiled as follows:

$ clang -g -flto -fuse-ld=lld main.c sum.c -o main

Results in the following DWARF:

-- sum.c CU: abstract instance tree
...
0x000000b0:   DW_TAG_subprogram
                DW_AT_name	("sum")
                DW_AT_decl_file	("sum.c")
                DW_AT_decl_line	(1)
                DW_AT_prototyped	(true)
                DW_AT_type	(0x000000d3 "int")
                DW_AT_external	(true)
                DW_AT_inline	(DW_INL_inlined)

0x000000bc:     DW_TAG_formal_parameter
                  DW_AT_name	("a")
                  DW_AT_decl_file	("sum.c")
                  DW_AT_decl_line	(1)
                  DW_AT_type	(0x000000d3 "int")

0x000000c7:     DW_TAG_formal_parameter
                  DW_AT_name	("b")
                  DW_AT_decl_file	("sum.c")
                  DW_AT_decl_line	(1)
                  DW_AT_type	(0x000000d3 "int")
...
-- main.c CU: concrete inlined instance tree
...
0x0000006d:     DW_TAG_inlined_subroutine
                  DW_AT_abstract_origin	(0x00000000000000b0 "sum")
                  DW_AT_low_pc	(0x00000000002016ef)
                  DW_AT_high_pc	(0x00000000002016f1)
                  DW_AT_call_file	("main.c")
                  DW_AT_call_line	(5)
                  DW_AT_call_column	(0x19)

0x00000081:       DW_TAG_formal_parameter
                    DW_AT_location	(DW_OP_reg0 RAX)
                    DW_AT_abstract_origin	(0x00000000000000bc "a")

0x00000088:       DW_TAG_formal_parameter
                    DW_AT_location	(DW_OP_reg2 RCX)
                    DW_AT_abstract_origin	(0x00000000000000c7 "b")
...

Note that each entry within the concrete inlined instance tree in
the main.c CU has a DW_AT_abstract_origin attribute which
refers to a corresponding entry within the abstract instance
tree in the sum.c CU.
llvm-dwarfdump --statistics did not properly report
DW_TAG_formal_parameters/DW_TAG_variables from concrete inlined
instance trees which had 0% location coverage and which
referred to a different CU, mainly because information about abstract
instance trees and their parameters/variables was stored
locally - just for the currently processed CU,
rather than globally - for all CUs.
In particular, if the concrete inlined instance tree from
the example above was to look like this
(i.e. parameter b has 0% location coverage, hence why it's missing):

0x0000006d:     DW_TAG_inlined_subroutine
                  DW_AT_abstract_origin	(0x00000000000000b0 "sum")
                  DW_AT_low_pc	(0x00000000002016ef)
                  DW_AT_high_pc	(0x00000000002016f1)
                  DW_AT_call_file	("main.c")
                  DW_AT_call_line	(5)
                  DW_AT_call_column	(0x19)

0x00000081:       DW_TAG_formal_parameter
                    DW_AT_location	(DW_OP_reg0 RAX)
                    DW_AT_abstract_origin	(0x00000000000000bc "a")

llvm-dwarfdump --statistics would have not reported b as such.

Patch by Dimitrije Milosevic.

Differential revision: https://reviews.llvm.org/D113465

1 files changed, 113 insertions, 26 deletions

diff --git a/llvm/tools/llvm-dwarfdump/Statistics.cpp b/llvm/tools/llvm-dwarfdump/Statistics.cpp
index b237e01..5c08e43 100644
--- a/llvm/tools/llvm-dwarfdump/Statistics.cpp
+++ b/llvm/tools/llvm-dwarfdump/Statistics.cpp
@@ -60,6 +60,19 @@ struct SaturatingUINT64 {
   }
 };
 
+/// Utility struct to store the full location of a DIE - its CU and offset.
+struct DIELocation {
+  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).
 struct PerFunctionStats {
@@ -450,15 +463,18 @@ static void collectStatsForDie(DWARFDie Die, const std::string &FnPrefix,
 /// Recursively collect variables from subprogram with DW_AT_inline attribute.
 static void collectAbstractOriginFnInfo(
     DWARFDie Die, uint64_t SPOffset,
-    AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo) {
+    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)
+        ChildTag == dwarf::DW_TAG_variable) {
       GlobalAbstractOriginFnInfo[SPOffset].push_back(Child.getOffset());
-    else if (ChildTag == dwarf::DW_TAG_lexical_block)
-      collectAbstractOriginFnInfo(Child, SPOffset, GlobalAbstractOriginFnInfo);
+      LocalAbstractOriginFnInfo[SPOffset].push_back(Child.getOffset());
+    } else if (ChildTag == dwarf::DW_TAG_lexical_block)
+      collectAbstractOriginFnInfo(Child, SPOffset, GlobalAbstractOriginFnInfo,
+                                  LocalAbstractOriginFnInfo);
     Child = Child.getSibling();
   }
 }
@@ -468,8 +484,9 @@ static void collectStatsRecursive(
     DWARFDie Die, std::string FnPrefix, std::string VarPrefix,
     uint64_t BytesInScope, uint32_t InlineDepth,
     StringMap<PerFunctionStats> &FnStatMap, GlobalStats &GlobalStats,
-    LocationStats &LocStats,
+    LocationStats &LocStats, FunctionDIECUTyMap &AbstractOriginFnCUs,
     AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
+    AbstractOriginVarsTyMap &LocalAbstractOriginFnInfo,
     FunctionsWithAbstractOriginTy &FnsWithAbstractOriginToBeProcessed,
     AbstractOriginVarsTy *AbstractOriginVarsPtr = nullptr) {
   // Skip NULL nodes.
@@ -499,11 +516,12 @@ static void collectStatsRecursive(
     auto OffsetFn = Die.find(dwarf::DW_AT_abstract_origin);
     if (OffsetFn) {
       uint64_t OffsetOfInlineFnCopy = (*OffsetFn).getRawUValue();
-      if (GlobalAbstractOriginFnInfo.count(OffsetOfInlineFnCopy)) {
-        AbstractOriginVars = GlobalAbstractOriginFnInfo[OffsetOfInlineFnCopy];
+      if (LocalAbstractOriginFnInfo.count(OffsetOfInlineFnCopy)) {
+        AbstractOriginVars = LocalAbstractOriginFnInfo[OffsetOfInlineFnCopy];
         AbstractOriginVarsPtr = &AbstractOriginVars;
       } else {
-        // This means that the DW_AT_inline fn copy is out of order,
+        // 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;
@@ -543,7 +561,9 @@ static void collectStatsRecursive(
       // for inlined instancies.
       if (Die.find(dwarf::DW_AT_inline)) {
         uint64_t SPOffset = Die.getOffset();
-        collectAbstractOriginFnInfo(Die, SPOffset, GlobalAbstractOriginFnInfo);
+        AbstractOriginFnCUs[SPOffset] = Die.getDwarfUnit();
+        collectAbstractOriginFnInfo(Die, SPOffset, GlobalAbstractOriginFnInfo,
+                                    LocalAbstractOriginFnInfo);
         return;
       }
 
@@ -597,8 +617,9 @@ static void collectStatsRecursive(
 
     collectStatsRecursive(
         Child, FnPrefix, ChildVarPrefix, BytesInScope, InlineDepth, FnStatMap,
-        GlobalStats, LocStats, GlobalAbstractOriginFnInfo,
-        FnsWithAbstractOriginToBeProcessed, AbstractOriginVarsPtr);
+        GlobalStats, LocStats, AbstractOriginFnCUs, GlobalAbstractOriginFnInfo,
+        LocalAbstractOriginFnInfo, FnsWithAbstractOriginToBeProcessed,
+        AbstractOriginVarsPtr);
     Child = Child.getSibling();
   }
 
@@ -733,16 +754,24 @@ static void updateVarsWithAbstractOriginLocCovInfo(
 /// the DW_TAG_subprogram) with an abstract_origin attribute.
 static void collectZeroLocCovForVarsWithAbstractOrigin(
     DWARFUnit *DwUnit, GlobalStats &GlobalStats, LocationStats &LocStats,
-    AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
+    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;
-
-    AbstractOriginVars = GlobalAbstractOriginFnInfo[(*FnCopy).getRawUValue()];
+    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);
 
@@ -758,6 +787,46 @@ static void collectZeroLocCovForVarsWithAbstractOrigin(
         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.
+static void collectZeroLocCovForVarsWithCrossCUReferencingAbstractOrigin(
+    LocationStats &LocStats, FunctionDIECUTyMap AbstractOriginFnCUs,
+    AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
+    CrossCUReferencingDIELocationTy &CrossCUReferencesToBeResolved) {
+  for (const auto &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]++;
+      } else if (Tag == dwarf::DW_TAG_variable) {
+        LocStats.NumVar++;
+        LocStats.LocalVarLocStats[ZeroCoverageBucket]++;
+      }
+    }
   }
 }
 
@@ -778,28 +847,46 @@ bool dwarfdump::collectStatsForObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
   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 (const auto &CU : static_cast<DWARFContext *>(&DICtx)->compile_units()) {
     if (DWARFDie CUDie = CU->getNonSkeletonUnitDIE(false)) {
-      // These variables are being reset for each CU, since there could be
-      // a situation where we have two subprogram DIEs with the same offsets
-      // in two diferent CUs, and we can end up using wrong variables info
-      // when trying to resolve abstract_origin attribute.
-      // TODO: Handle LTO cases where the abstract origin of
-      // the function is in a different CU than the one it's
-      // referenced from or inlined into.
-      AbstractOriginVarsTyMap GlobalAbstractOriginFnInfo;
+      // 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, GlobalAbstractOriginFnInfo,
-                            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,
-          GlobalAbstractOriginFnInfo, FnsWithAbstractOriginToBeProcessed);
+          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);