[llvm-debuginfo-analyzer] Support both Reference and Type attrs in single DIE

[scott.linder]

Summary

Relax the assumption that at most one Reference-or-Type-like attribute is
present on a DWARF DIE.

Add support for at most one Type attribute (i.e. DW_AT_import xor
DW_AT_type) and separately at most one Reference attribute (i.e.
DW_AT_specification xor DW_AT_abstract_origin xor ...).

Update comment describing old assumption and tag it as a "FIXME" to
reflect the fact that this is perhaps still not general enough.

Add a test based on the case which led me to encounter the bug in the
wild.

[CarlosAlbertoEnciso]

@scott.linder Thanks for taking the time to create the patch.

[CarlosAlbertoEnciso]

llvm/lib/DebugInfo/LogicalView/Readers/LVELFReader.cpp

1131

In the case of a new offset the original code created:

[Offset, LVElementEntry(nullptr, {Element}) ]

The new code:

[Offset, LVElementEntry(nullptr, References{}, Types{}) ]

The Element parameter is not recorded.

[scott.linder]

(Cross-posting from the other thread, to keep everything in one place)

In D147270#4348913, @CarlosAlbertoEnciso wrote:

In D147270#4346528, @scott.linder wrote:

I did a little digging and it seems like there is a faulty assumption in LVELFReader:

// We are assuming that DW_AT_specification, DW_AT_abstract_origin,
// DW_AT_type and DW_AT_extension do not appear at the same time
// in the same DIE.

Thanks very much for your analysis and for creating a small reproducible test.

This seems true for GCC, but not for Clang, at least for the simplest reproducer I could create:

$ cat a.cpp
struct S {
    static const int Arr[];
};
const int S::Arr[] = {
    0, 1, 2
};
$ gcc -g -c a.cpp -o a.o
$ build/bin/llvm-dwarfdump --debug-info a.o | grep -B1 -A2 DW_AT_specification
0x00000053:   DW_TAG_variable
                DW_AT_specification     (0x00000028 "Arr")
                DW_AT_decl_line (4)
                DW_AT_decl_column       (0x0b)
$ clang++ -g -c a.cpp -o a.o
$ build/bin/llvm-dwarfdump --debug-info a.o | grep -B1 -A2 DW_AT_specification
0x0000001e:   DW_TAG_variable
                DW_AT_specification     (0x0000003e "Arr")
                DW_AT_type      (0x00000068 "const int[3]")
                DW_AT_location  (DW_OP_addr 0x0)

It seems like the code could be adapted to track these independently, rather than assume only one is present? I can prepare a patch if that sounds reasonable to you!

I am happy with your proposal and a patch.

Edit: This may also be a Clang bug. I haven't read the relevant DWARF sections with enough detail to say whether the DWARF itself is valid or not, but either way it seems nice to support it in llvm-debuginfo-analyzer, especially considering how much flexibility the tool already affords in terms of input

I compiled your test case with the latest Clang:

0x0000001e:   DW_TAG_variable
                     DW_AT_specification	(0x00000031 "Arr")
                     DW_AT_type	(0x00000052 "const int[3]")
                     DW_AT_location	(DW_OP_addrx 0x0)
                     DW_AT_linkage_name	("_ZN1S3ArrE")

0x00000031:     DW_TAG_member
                       DW_AT_name	("Arr")
                       DW_AT_type	(0x0000003a "const int[]")
                       DW_AT_decl_file	("/data/projects/sandbox/pr-62716.cpp")
                       DW_AT_decl_line	(2)
                       DW_AT_external	(true)
                       DW_AT_declaration	(true)

From the DWARF section for DW_AT_specification:

A debugging information entry with a DW_AT_specification attribute does not need to duplicate information provided by the debugging information entry referenced by that specification attribute.

Clang:

• Added an extra entry for DW_AT_type which seems redundant in DIE (0x1e) as by following the DW_AT_specification we can get the type
• The referenced types are pointing to different DIEs (0x52 and 0x3a).

I think in this case the duplication may be meaningful, or at least legal and intelligible, as the types at the declaration vs the definition are actually distinct, see https://en.cppreference.com/w/cpp/language/array#Arrays_of_unknown_bound:

extern int x[];      // the type of x is "array of unknown bound of int"
int a[] = {1, 2, 3}; // the type of a is "array of 3 int"

Or from the C++ spec directly, i.e. from 6.8.1 [basic.types.general] in https://github.com/cplusplus/draft/releases/tag/n4917 (emphasis mine):

(6) A class type (such as “class X”) can be incomplete at one point in a translation unit and complete later on;
the type “class X” is the same type at both points. The declared type of an array object can be an array of
incomplete class type and therefore incomplete; if the class type is completed later on in the translation unit,
the array type becomes complete; the array type at those two points is the same type. The declared type of
an array object can be an array of unknown bound and therefore be incomplete at one point in a translation
unit and complete later on; the array types at those two points (“array of unknown bound of T” and “array
of N T”) are different types. The type of a pointer to array of unknown bound, or of a type defined by a
typedef declaration to be an array of unknown bound, cannot be completed.

I also think so long as the DWARF spec does not prohibit it, it makes sense for tooling to support it. Admittedly there is a lot of wiggle-room and ambiguity in much of the DWARF spec, but in this case the phrasing "does not need to duplicate" seems to heavily imply that the duplication is legal, just not necessary when the attributes match.

llvm/lib/DebugInfo/LogicalView/Readers/LVELFReader.cpp

1131

It is handled below now, as the change also removes the if/else: we use try_emplace to find the entry at Offset, creating an empty one if none exists. Then, we always add Element to the appropriate set.

So the previously explicitly special-cased Iter == ElementTable.end() case is all contained in this first line of the function.

[CarlosAlbertoEnciso]

In D150713#4350582, @scott.linder wrote:

(Cross-posting from the other thread, to keep everything in one place)

In D147270#4348913, @CarlosAlbertoEnciso wrote:

In D147270#4346528, @scott.linder wrote:

I did a little digging and it seems like there is a faulty assumption in LVELFReader:

// We are assuming that DW_AT_specification, DW_AT_abstract_origin,
// DW_AT_type and DW_AT_extension do not appear at the same time
// in the same DIE.

Thanks very much for your analysis and for creating a small reproducible test.

This seems true for GCC, but not for Clang, at least for the simplest reproducer I could create:

$ cat a.cpp
struct S {
    static const int Arr[];
};
const int S::Arr[] = {
    0, 1, 2
};
$ gcc -g -c a.cpp -o a.o
$ build/bin/llvm-dwarfdump --debug-info a.o | grep -B1 -A2 DW_AT_specification
0x00000053:   DW_TAG_variable
                DW_AT_specification     (0x00000028 "Arr")
                DW_AT_decl_line (4)
                DW_AT_decl_column       (0x0b)
$ clang++ -g -c a.cpp -o a.o
$ build/bin/llvm-dwarfdump --debug-info a.o | grep -B1 -A2 DW_AT_specification
0x0000001e:   DW_TAG_variable
                DW_AT_specification     (0x0000003e "Arr")
                DW_AT_type      (0x00000068 "const int[3]")
                DW_AT_location  (DW_OP_addr 0x0)

It seems like the code could be adapted to track these independently, rather than assume only one is present? I can prepare a patch if that sounds reasonable to you!

I am happy with your proposal and a patch.

Edit: This may also be a Clang bug. I haven't read the relevant DWARF sections with enough detail to say whether the DWARF itself is valid or not, but either way it seems nice to support it in llvm-debuginfo-analyzer, especially considering how much flexibility the tool already affords in terms of input

I compiled your test case with the latest Clang:

0x0000001e:   DW_TAG_variable
                     DW_AT_specification	(0x00000031 "Arr")
                     DW_AT_type	(0x00000052 "const int[3]")
                     DW_AT_location	(DW_OP_addrx 0x0)
                     DW_AT_linkage_name	("_ZN1S3ArrE")

0x00000031:     DW_TAG_member
                       DW_AT_name	("Arr")
                       DW_AT_type	(0x0000003a "const int[]")
                       DW_AT_decl_file	("/data/projects/sandbox/pr-62716.cpp")
                       DW_AT_decl_line	(2)
                       DW_AT_external	(true)
                       DW_AT_declaration	(true)

From the DWARF section for DW_AT_specification:

A debugging information entry with a DW_AT_specification attribute does not need to duplicate information provided by the debugging information entry referenced by that specification attribute.

Clang:

• Added an extra entry for DW_AT_type which seems redundant in DIE (0x1e) as by following the DW_AT_specification we can get the type
• The referenced types are pointing to different DIEs (0x52 and 0x3a).

I think in this case the duplication may be meaningful, or at least legal and intelligible, as the types at the declaration vs the definition are actually distinct, see https://en.cppreference.com/w/cpp/language/array#Arrays_of_unknown_bound:

extern int x[];      // the type of x is "array of unknown bound of int"
int a[] = {1, 2, 3}; // the type of a is "array of 3 int"

Or from the C++ spec directly, i.e. from 6.8.1 [basic.types.general] in https://github.com/cplusplus/draft/releases/tag/n4917 (emphasis mine):

(6) A class type (such as “class X”) can be incomplete at one point in a translation unit and complete later on;
the type “class X” is the same type at both points. The declared type of an array object can be an array of
incomplete class type and therefore incomplete; if the class type is completed later on in the translation unit,
the array type becomes complete; the array type at those two points is the same type. The declared type of
an array object can be an array of unknown bound and therefore be incomplete at one point in a translation
unit and complete later on; the array types at those two points (“array of unknown bound of T” and “array
of N T”) are different types. The type of a pointer to array of unknown bound, or of a type defined by a
typedef declaration to be an array of unknown bound, cannot be completed.

I also think so long as the DWARF spec does not prohibit it, it makes sense for tooling to support it. Admittedly there is a lot of wiggle-room and ambiguity in much of the DWARF spec, but in this case the phrasing "does not need to duplicate" seems to heavily imply that the duplication is legal, just not necessary when the attributes match.

Thanks very much for the great links and explanations. The generation of both types now makes sense.

[CarlosAlbertoEnciso]

llvm/lib/DebugInfo/LogicalView/Readers/LVELFReader.cpp

1131

Sorry; I missed the Element assignment.
The change looks great.

[CarlosAlbertoEnciso]

Compiling the test case with GCC and Clang, your patch produces:

llvm-debuginfo-analyzer --print=symbols --attribute=reference,producer dw-at-specification-clang.o dw-at-specification-gcc.o

Logical View:
           {File} 'dw-at-specification-clang.o'

             {CompileUnit} 'dw-at-specification.cpp'
               {Producer} 'clang version 17.0.0 ...'
               {Variable} 'Arr' -> 'const int [3]'
                 {Reference} @2
     1         {Struct} 'S'
     2           {Member} extern public 'Arr' -> 'const int [1]'

Logical View:
           {File} 'dw-at-specification-gcc.o'

             {CompileUnit} 'dw-at-specification.cpp'
                {Producer} 'GNU C++17 11.3.0 ...'
     1         {Struct} 'S'
     2           {Variable} extern 'Arr' -> 'const int [1]'
     4         {Variable} 'Arr' -> 'const const int [3]'
                 {Reference} @2

Looks good.

Looking at the DWARF produced by GCC (I have 11.3.0) it produces the same both types as Clang. I think it would be good to include a test for GCC.

llvm/include/llvm/DebugInfo/LogicalView/Readers/LVELFReader.h

class LVELFReader final : public LVBinaryReader {
   // Low PC and High PC values for DIE being processed.
   LVAddress CurrentLowPC = 0;
   LVAddress CurrentHighPC = 0;
   bool FoundLowPC = false;
   bool FoundHighPC = false;
 
   // Cross references (Elements).
   using LVElementSet = std::unordered_set<LVElement *>;
-  using LVElementEntry = std::pair<LVElement *, LVElementSet>;
+  struct LVElementEntry {
+    LVElement *Element;
+    LVElementSet References;
+    LVElementSet Types;
+    LVElementEntry(LVElement *Element = nullptr) : Element(Element) {}
+  };
   using LVElementReference = std::unordered_map<LVOffset, LVElementEntry>;
   LVElementReference ElementTable;
 
   Error loadTargetInfo(const object::ObjectFile &Obj);
 
   void mapRangeAddress(const object::ObjectFile &Obj) override;
 
   LVElement *createElement(dwarf::Tag Tag);
void processLocationMember(dwarf::Attribute Attr,
                              const DWARFDie &Die, uint64_t OffsetOnEntry);
   void processLocationList(dwarf::Attribute Attr,
                            const DWARFFormValue &FormValue, const DWARFDie &Die,
                            uint64_t OffsetOnEntry,
                            bool CallSiteLocation = false);
   void updateReference(dwarf::Attribute Attr, const DWARFFormValue &FormValue);
 
   // Get an element given the DIE offset.
-  LVElement *getElementForOffset(LVOffset offset, LVElement *Element);
+  LVElement *getElementForOffset(LVOffset offset, LVElement *Element,
+                                 bool IsType);
 
 protected:
   Error createScopes() override;
   void sortScopes() override;
 
 public:
   LVELFReader() = delete;
   LVELFReader(StringRef Filename, StringRef FileFormatName,

llvm/lib/DebugInfo/LogicalView/Readers/LVELFReader.cpp

if (options().getAttributeAnySource() && CurrentElement->isCompileUnit())
       addCompileUnitOffset(Offset,
                            static_cast<LVScopeCompileUnit *>(CurrentElement));
 
     // Insert the newly created element into the element symbol table. If the
     // element is in the list, it means there are previously created elements
     // referencing this element.
     if (ElementTable.find(Offset) == ElementTable.end()) {
       // No previous references to this offset.
-      ElementTable.emplace(
-          std::piecewise_construct, std::forward_as_tuple(Offset),
-          std::forward_as_tuple(CurrentElement, LVElementSet()));
+      ElementTable.emplace(std::piecewise_construct,
+                           std::forward_as_tuple(Offset),
+                           std::forward_as_tuple(CurrentElement));
     } else {
       // There are previous references to this element. We need to update the
       // element and all the references pointing to this element.
       LVElementEntry &Reference = ElementTable[Offset];
-      Reference.first = CurrentElement;
+      Reference.Element = CurrentElement;
       // Traverse the element set and update the elements (backtracking).
-      // Using the bit associated with 'type' or 'reference' allows us to set
-      // the correct target.
-      for (LVElement *Target : Reference.second)
-        Target->getHasReference() ? Target->setReference(CurrentElement)
-                                  : Target->setType(CurrentElement);
+      for (LVElement *Target : Reference.References)
+        Target->setReference(CurrentElement);
+      for (LVElement *Target : Reference.Types)
+        Target->setType(CurrentElement);
       // Clear the pending elements.
-      Reference.second.clear();
+      Reference.References.clear();
+      Reference.Types.clear();
     }
 
     // Add the current element to its parent as there are attributes
     // (locations) that require the scope level.
     if (CurrentScope)
       Parent->addElement(CurrentScope);
     else if (CurrentSymbol)
       Parent->addElement(CurrentSymbol);
void LVELFReader::processLocationMember(dwarf::Attribute Attr,
   else
     // This is a a location description, or a reference to one.
     processLocationList(Attr, FormValue, Die, OffsetOnEntry);
 }
 
 // Update the current element with the reference.
 void LVELFReader::updateReference(dwarf::Attribute Attr,
                                   const DWARFFormValue &FormValue) {
-  // We are assuming that DW_AT_specification, DW_AT_abstract_origin,
-  // DW_AT_type and DW_AT_extension do not appear at the same time
-  // in the same DIE.
+  // FIXME: We are assuming that at most one Reference (DW_AT_specification,
+  // DW_AT_abstract_origin, ...) and at most one Type (DW_AT_import, DW_AT_type)
+  // appear in any single DIE, but this may not be true.
   uint64_t Reference = *FormValue.getAsReference();
   // Get target for the given reference, if already created.
-  LVElement *Target = getElementForOffset(Reference, CurrentElement);
+  LVElement *Target = getElementForOffset(
+      Reference, CurrentElement,
+      /*IsType=*/Attr == dwarf::DW_AT_import || Attr == dwarf::DW_AT_type);
   // Check if we are dealing with cross CU references.
   if (FormValue.getForm() == dwarf::DW_FORM_ref_addr) {
     if (Target) {
       // The global reference is ready. Mark it as global.
       Target->setIsGlobalReference();
       // Remove global reference from the unseen list.
       removeGlobalOffset(Reference);
     } else
case dwarf::DW_AT_type:
     CurrentElement->setType(Target);
     break;
   default:
     break;
   }
 }
 
 // Get an element given the DIE offset.
-LVElement *LVELFReader::getElementForOffset(LVOffset Offset,
-                                            LVElement *Element) {
-  LVElement *Target = nullptr;
-  // Search offset in the cross references.
-  LVElementReference::iterator Iter = ElementTable.find(Offset);
-  if (Iter == ElementTable.end())
-    // Reference to an unseen element.
-    ElementTable.emplace(std::piecewise_construct,
-                         std::forward_as_tuple(Offset),
-                         std::forward_as_tuple(nullptr, LVElementSet{Element}));
-  else {
-    // There are previous references to this element. We need to update the
-    // element and all the references pointing to this element.
-    LVElementEntry &Reference = Iter->second;
-    Target = Reference.first;
-    if (!Target)
-      // Add the element to the set.
-      Reference.second.insert(Element);
+LVElement *LVELFReader::getElementForOffset(LVOffset Offset, LVElement *Element,
+                                            bool IsType) {
+  auto Iter = ElementTable.try_emplace(Offset).first;
+  // Update the element and all the references pointing to this element.
+  LVElementEntry &Entry = Iter->second;
+  if (!Entry.Element) {
+    if (IsType)
+      Entry.Types.insert(Element);
+    else
+      Entry.References.insert(Element);
   }
-  return Target;
+  return Entry.Element;
 }
 
 Error LVELFReader::loadTargetInfo(const ObjectFile &Obj) {
   // Detect the architecture from the object file. We usually don't need OS
   // info to lookup a target and create register info.
   Triple TT;
   TT.setArch(Triple::ArchType(Obj.getArch()));
   TT.setVendor(Triple::UnknownVendor);

llvm/test/tools/llvm-debuginfo-analyzer/DWARF/dw-at-specification.test

+; REQUIRES: x86-registered-target
+
+; dw-at-specification.cpp
+; 1  struct S {
+; 2      static const int Arr[];
+; 3  };
+; 4  const int S::Arr[] = {
+; 5      0, 1, 2
+; 6  };
+
+; The above test compiled with clang++ produces both a DW_AT_type and
+; DW_AT_specification on the definition die for S::Arr, which previously caused
+; an assert in the LVELFReader:
+; $ clang++ -g -c dw-at-specification.cpp -o dw-at-specification.o
+
+; RUN: llvm-debuginfo-analyzer --attribute=level,format,producer \
+; RUN:                         --output-sort=name \
+; RUN:                         --print=symbols \
+; RUN:                         %p/Inputs/dw-at-specification.o 2>&1 | \
+; RUN: FileCheck --strict-whitespace -check-prefix=CHECK %s
+
+; CHECK: Logical View:
+; CHECK: [000]           {File} 'dw-at-specification.o' -> elf64-x86-64
+; CHECK-EMPTY:
+; CHECK: [001]             {CompileUnit} 'a.cpp'
+; CHECK: [002]               {Producer} 'clang version 11.0.0 ({{.*}})'
+; CHECK: [002]               {Variable} 'Arr' -> 'const int [3]'
+; CHECK: [002]     1         {Struct} 'S'
+; CHECK: [003]     2           {Member} extern public 'Arr' -> 'const int [1]'