DWARF: Implement DW_AT_signature lookup for type unit support

[labath]

Summary

This patch implements the main feature of type units. When completing a
type, if we encounter a DW_AT_signature attribute, we use it's value to
lookup the complete definition of the type in the relevant type unit.

To enable this lookup, we build up a map of all type units in a symbol
file when parsing the units. Then we consult this map when resolving the
DW_AT_signature attribute.

I include add a couple of tests which exercise the type lookup feature,
including one that ensure we do something reasonable in case we fail to
lookup the type.

A lot of the ideas in this patch have been taken from D32167 and D61505.

[aprantl]

source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

255

Not your code, but it would be easier to follow the logic if we pulled these cases up front:

  if (type_ptr == DIE_IS_BEING_PARSED)
     return type_sp;
  if (type_ptr)
      return type_ptr->shared_from_this();
...

258

if (type_sp = ParseTypeFromDWARF(sc, signature_die, log, type_is_new_ptr))

[clayborg]

Just fix the return when we have a DW_AT_signature and this is good to go.

source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

267

We should return before the } on line 267, not on line 265. If we have a DW_AT_signature and we fail to parse a type we won't do any better below when there is no type info right?

source/Plugins/SymbolFile/DWARF/DWARFDebugInfo.h

74

llvm::DenseMap?

[JDevlieghere]

source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

261

Same here: if (clang::DeclContext *decl_ctx ....

[labath]

• implement the sugested changes (except the DenseMap part)
• fix a bug where we would enter an infinite recursion in case the type in the type unit ended up referring back to itself (and add a test). I do this by setting the DIE_IS_BEING_PARSED flag before doing the DW_AT_signature check (instead of at the beginning of each of the DW_TAG switch cases). This part changes the behavior slightly, because two of the switch cases did not set the DIE_IS_BEING_PARSED flag, but I believe this is actually for the better. In the DW_TAG_ptr_to_member case, I believe this is a bug, and could cause us to recurse infinitely in case of self-referring member pointer types (but I did not try to verify that). For the "default" case, this means that we will print the "unhandled type" warning only once for each DIE, which also sounds like a good thing.

[labath]

source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

255

Done in r361471.

source/Plugins/SymbolFile/DWARF/DWARFDebugInfo.h

74

A sorted vector is the recommended approach for sets and maps with an insert-then-query pattern. Also, a DenseMap would blow up if one of the type signatures happened to be 0xfff...f.

lit/SymbolFile/DWARF/Inputs/debug-types-basic.cpp

+enum E { e1, e2, e3 };
+enum class EC { e1, e2, e3 };
+
 struct A {
   int i;
   long l;
   float f;
   double d;
+  E e;
+  EC ec;
 };
 
-enum E { e1, e2, e3 };
-enum class EC { e1, e2, e3 };
-
-extern constexpr A a{42, 47l, 4.2f, 4.7};
+extern constexpr A a{42, 47l, 4.2f, 4.7, e1, EC::e3};
 extern constexpr E e(e2);
 extern constexpr EC ec(EC::e2);

lit/SymbolFile/DWARF/Inputs/debug-types-expressions.cpp

 struct A {
   int i = 47;
   int f() { return i; }
   virtual ~A() = default;
 };
 
 struct B: public A {
   int j = 42;
 };
 
 namespace ns {
 struct A {
   int i = 147;
+  ::A getA();
   A();
 };
 A::A() = default;
+
+::A A::getA() {
+  ::A a;
+  a.i = i - 1;
+  return a;
 }
 
+} // namespace ns
+
 int foo(A *a) {
   return a->f();
 }
 
 int main() {
   return foo(new B);
 }

lit/SymbolFile/DWARF/debug-types-basic.test

 
 type lookup A
 # CHECK-LABEL: type lookup A
 # CHECK:      struct A {
 # CHECK-NEXT:   int i;
 # CHECK-NEXT:   long l;
 # CHECK-NEXT:   float f;
 # CHECK-NEXT:   double d;
+# CHECK-NEXT:   E e;
+# CHECK-NEXT:   EC ec;
 # CHECK-NEXT: }
 
 type lookup E
 # CHECK-LABEL: type lookup E
 # CHECK:      enum E {
 # CHECK-NEXT:   e1,
 # CHECK-NEXT:   e2,
 # CHECK-NEXT:   e3

 
 print (E) 1
 # CHECK-LABEL: print (E) 1
 # CHECK: (E) $0 = e2
 
 print (EC) 1
 # CHECK-LABEL: print (EC) 1
 # CHECK: (EC) $1 = e2
+
+target variable a e ec
+# CHECK-LABEL: target variable a e ec
+# CHECK: (const A) a = (i = 42, l = 47, f = 4.{{[12].*}}, d = 4.{{[67].*}}, e = e1, ec = e3)
+# CHECK: (const E) e = e2
+# CHECK: (const EC) ec = e2

lit/SymbolFile/DWARF/debug-types-expressions.test

 process launch
 
 # CHECK: Process {{.*}} stopped
 
 frame variable a
 # CHECK-LABEL: frame variable a
 # CHECK: (B *) a =
 
+frame variable *a
+# CHECK-LABEL: frame variable *a
+# CHECK:      (B) *a = {
+# CHECK-NEXT:   A = (i = 47)
+# CHECK-NEXT:   j = 42
+# CHECK-NEXT: }
+
 print a->f()
 # CHECK-LABEL: print a->f()
 # CHECK: (int) $0 = 47
 
 print ns::A()
 # CHECK-LABEL: print ns::A()
 # CHECK: (ns::A) $1 = (i = 147)
+
+print ns::A().i + a->i
+# CHECK-LABEL: print ns::A().i + a->i
+# CHECK: (int) $2 = 194
+
+print ns::A().getA()
+# CHECK-LABEL: ns::A().getA()
+# CHECK: (A) $3 = (i = 146)

lit/SymbolFile/DWARF/debug-types-missing-signature.test

+Create a dangling DW_AT_signature reference by stripping the debug_types
+section, and make sure lldb does something reasonable.
+RUN: %clangxx -target x86_64-pc-linux %S/Inputs/debug-types-basic.cpp \
+RUN:   -g -gdwarf-4 -fdebug-types-section -c -o %t.o
+RUN: llvm-objcopy --remove-section=.debug_types %t.o %t
+
+
+RUN: %lldb %t -b -o "type lookup A" | FileCheck --check-prefix=LOOKUPA %s
+LOOKUPA: no type was found matching 'A'
+
+RUN: %lldb %t -b -o "type lookup E" | FileCheck --check-prefix=LOOKUPE %s
+LOOKUPE: no type was found matching 'E'
+
+RUN: %lldb %t -b -o "type lookup EC" | FileCheck --check-prefix=LOOKUPEC %s
+LOOKUPEC: no type was found matching 'EC'
+
+RUN: %lldb %t -b -o "print (E) 1" 2>&1 | FileCheck --check-prefix=PRINTE %s
+PRINTE: use of undeclared identifier 'E'
+
+RUN: %lldb %t -b -o "print (EC) 1" 2>&1 | FileCheck --check-prefix=PRINTEC %s
+PRINTEC: use of undeclared identifier 'EC'
+
+RUN: %lldb %t -b -o "target variable a e ec" | FileCheck --check-prefix=VARS %s
+VARS: (const (anonymous struct)) a = {}
+VARS: (const (anonymous enum)) e = 1
+VARS: (const (anonymous enum)) ec = 1

source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

if (log) {
       dwarf->GetObjectFile()->GetModule()->LogMessage(
           log, "SymbolFileDWARF::ParseType (die = 0x%8.8x, decl_ctx = %p (die "
                "0x%8.8x)) %s name = '%s')",
           die.GetOffset(), static_cast<void *>(context),
           context_die.GetOffset(), die.GetTagAsCString(), die.GetName());
     }
     Type *type_ptr = dwarf->GetDIEToType().lookup(die.GetDIE());
     TypeList *type_list = dwarf->GetTypeList();
     if (type_ptr == NULL) {
+
+      if (DWARFDIE signature_die = die.GetAttributeValueAsReferenceDIE(DW_AT_signature)) {
+        type_sp = ParseTypeFromDWARF(sc, signature_die, log, type_is_new_ptr);
+        if (type_sp) {
+          dwarf->GetDIEToType()[die.GetDIE()] = type_sp.get();
+          clang::DeclContext *decl_ctx =
+              GetCachedClangDeclContextForDIE(signature_die);
+          if (decl_ctx)
+            LinkDeclContextToDIE(decl_ctx, die);
+          return type_sp;
+        }
+      }
+
       if (type_is_new_ptr)
         *type_is_new_ptr = true;
 
       const dw_tag_t tag = die.Tag();
 
       bool is_forward_declaration = false;
       DWARFAttributes attributes;
       const char *type_name_cstr = NULL;

source/Plugins/SymbolFile/DWARF/DWARFDebugInfo.h

 //===-- DWARFDebugInfo.h ----------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SymbolFileDWARF_DWARFDebugInfo_h_
 #define SymbolFileDWARF_DWARFDebugInfo_h_
 
 #include <map>
 #include <vector>
 
 #include "DWARFDIE.h"
+#include "DWARFTypeUnit.h"
 #include "DWARFUnit.h"
 #include "SymbolFileDWARF.h"
 #include "lldb/Core/STLUtils.h"
 #include "lldb/lldb-private.h"
 #include "llvm/Support/Error.h"
 
 namespace lldb_private {
 class DWARFContext;
public:
 
   size_t GetNumUnits();
   DWARFUnit *GetUnitAtIndex(lldb::user_id_t idx);
   DWARFUnit *GetUnitAtOffset(DIERef::Section section,
                              dw_offset_t cu_offset, uint32_t *idx_ptr = NULL);
   DWARFUnit *GetUnitContainingDIEOffset(DIERef::Section section,
                                         dw_offset_t die_offset);
   DWARFUnit *GetUnit(const DIERef &die_ref);
+  DWARFTypeUnit *GetTypeUnitForHash(uint64_t hash);
   DWARFDIE GetDIEForDIEOffset(DIERef::Section section,
                               dw_offset_t die_offset);
   DWARFDIE GetDIE(const DIERef &die_ref);
 
   enum {
     eDumpFlag_Verbose = (1 << 0),  // Verbose dumping
     eDumpFlag_ShowForm = (1 << 1), // Show the DW_form type
     eDumpFlag_ShowAncestors =
         (1 << 2) // Show all parent DIEs when dumping single DIEs
   };
 
   llvm::Expected<DWARFDebugAranges &> GetCompileUnitAranges();
 
 protected:
   typedef std::vector<DWARFUnitSP> UnitColl;
 
   // Member variables
   SymbolFileDWARF *m_dwarf2Data;
   lldb_private::DWARFContext &m_context;
   UnitColl m_units;
   std::unique_ptr<DWARFDebugAranges>
       m_cu_aranges_up; // A quick address to compile unit table
 
+  std::vector<std::pair<uint64_t, uint32_t>> m_type_hash_to_unit_index;
+
 private:
   // All parsing needs to be done partially any managed by this class as
   // accessors are called.
   void ParseUnitHeadersIfNeeded();
 
+  void ParseUnitsFor(DIERef::Section section);
+
   uint32_t FindUnitIndex(DIERef::Section section, dw_offset_t offset);
 
   DISALLOW_COPY_AND_ASSIGN(DWARFDebugInfo);
 };
 
 #endif // SymbolFileDWARF_DWARFDebugInfo_h_

source/Plugins/SymbolFile/DWARF/DWARFDebugInfo.cpp

 
 #include <algorithm>
 #include <set>
 
 #include "lldb/Host/PosixApi.h"
 #include "lldb/Symbol/ObjectFile.h"
 #include "lldb/Utility/RegularExpression.h"
 #include "lldb/Utility/Stream.h"
+#include "llvm/Support/Casting.h"
 
 #include "DWARFCompileUnit.h"
 #include "DWARFContext.h"
 #include "DWARFDebugAranges.h"
 #include "DWARFDebugInfo.h"
 #include "DWARFDebugInfoEntry.h"
 #include "DWARFFormValue.h"
 #include "DWARFTypeUnit.h"
if (cus_with_data.find(offset) == cus_with_data.end())
       cu->BuildAddressRangeTable(m_cu_aranges_up.get());
   }
 
   const bool minimize = true;
   m_cu_aranges_up->Sort(minimize);
   return *m_cu_aranges_up;
 }
 
-void Parse(SymbolFileDWARF *dwarf, const DWARFDataExtractor &data,
-           DIERef::Section section, std::vector<DWARFUnitSP> &units) {
+void DWARFDebugInfo::ParseUnitsFor(DIERef::Section section) {
+  DWARFDataExtractor data = section == DIERef::Section::DebugTypes
+                                ? m_context.getOrLoadDebugTypesData()
+                                : m_context.getOrLoadDebugInfoData();
   lldb::offset_t offset = 0;
   while (data.ValidOffset(offset)) {
-    llvm::Expected<DWARFUnitSP> unit_sp =
-        DWARFUnit::extract(dwarf, units.size(), data, section, &offset);
+    llvm::Expected<DWARFUnitSP> unit_sp = DWARFUnit::extract(
+        m_dwarf2Data, m_units.size(), data, section, &offset);
 
     if (!unit_sp) {
       // FIXME: Propagate this error up.
       llvm::consumeError(unit_sp.takeError());
       return;
     }
 
     // If it didn't return an error, then it should be returning a valid Unit.
     assert(*unit_sp);
-
-    units.push_back(*unit_sp);
-
+    m_units.push_back(*unit_sp);
     offset = (*unit_sp)->GetNextUnitOffset();
+
+    if (auto *type_unit = llvm::dyn_cast<DWARFTypeUnit>(unit_sp->get())) {
+      m_type_hash_to_unit_index.emplace_back(type_unit->GetTypeHash(),
+                                             unit_sp.get()->GetID());
+    }
   }
 }
 
 void DWARFDebugInfo::ParseUnitHeadersIfNeeded() {
   if (!m_units.empty())
     return;
   if (!m_dwarf2Data)
     return;
 
-  Parse(m_dwarf2Data, m_context.getOrLoadDebugInfoData(),
-        DIERef::Section::DebugInfo, m_units);
-  Parse(m_dwarf2Data, m_context.getOrLoadDebugTypesData(),
-        DIERef::Section::DebugTypes, m_units);
+  ParseUnitsFor(DIERef::Section::DebugInfo);
+  ParseUnitsFor(DIERef::Section::DebugTypes);
+  llvm::sort(m_type_hash_to_unit_index, llvm::less_first());
 }
 
 size_t DWARFDebugInfo::GetNumUnits() {
   ParseUnitHeadersIfNeeded();
   return m_units.size();
 }
 
 DWARFUnit *DWARFDebugInfo::GetUnitAtIndex(user_id_t idx) {
DWARFDebugInfo::GetUnitContainingDIEOffset(DIERef::Section section,
                                            dw_offset_t die_offset) {
   uint32_t idx = FindUnitIndex(section, die_offset);
   DWARFUnit *result = GetUnitAtIndex(idx);
   if (result && !result->ContainsDIEOffset(die_offset))
     return nullptr;
   return result;
 }
 
+DWARFTypeUnit *DWARFDebugInfo::GetTypeUnitForHash(uint64_t hash) {
+  auto pos = llvm::lower_bound(m_type_hash_to_unit_index,
+                               std::make_pair(hash, 0u), llvm::less_first());
+  if (pos == m_type_hash_to_unit_index.end() || pos->first != hash)
+    return nullptr;
+  return llvm::cast<DWARFTypeUnit>(GetUnitAtIndex(pos->second));
+}
+
 DWARFDIE
 DWARFDebugInfo::GetDIEForDIEOffset(DIERef::Section section,
                                    dw_offset_t die_offset) {
   DWARFUnit *cu = GetUnitContainingDIEOffset(section, die_offset);
   if (cu)
     return cu->GetDIE(die_offset);
   return DWARFDIE();
 }

source/Plugins/SymbolFile/DWARF/DWARFFormValue.cpp

if (!ref_cu) {
       m_unit->GetSymbolFileDWARF()->GetObjectFile()->GetModule()->ReportError(
           "DW_FORM_ref_addr DIE reference 0x%" PRIx64 " has no matching CU",
           value);
       return {};
     }
     return ref_cu->GetDIE(value);
   }
 
+  case DW_FORM_ref_sig8: {
+    DWARFTypeUnit *tu =
+        m_unit->GetSymbolFileDWARF()->DebugInfo()->GetTypeUnitForHash(value);
+    if (!tu)
+      return {};
+    return tu->GetDIE(tu->GetTypeOffset());
+  }
+
   default:
     return {};
   }
 }
 
 uint64_t DWARFFormValue::Reference(dw_offset_t base_offset) const {
   uint64_t value = m_value.value.uval;
   switch (m_form) {

source/Plugins/SymbolFile/DWARF/DWARFTypeUnit.h

 #include "llvm/Support/Error.h"
 
 class DWARFTypeUnit : public DWARFUnit {
 public:
   void BuildAddressRangeTable(DWARFDebugAranges *debug_aranges) override {}
 
   void Dump(lldb_private::Stream *s) const override;
 
+  uint64_t GetTypeHash() { return m_header.GetTypeHash(); }
+
+  dw_offset_t GetTypeOffset() { return GetOffset() + m_header.GetTypeOffset(); }
+
+  static bool classof(const DWARFUnit *unit) {
+    return unit->GetUnitType() == DW_UT_type;
+  }
+
 private:
   DWARFTypeUnit(SymbolFileDWARF *dwarf, lldb::user_id_t uid,
                 const DWARFUnitHeader &header,
                 const DWARFAbbreviationDeclarationSet &abbrevs,
                 DIERef::Section section)
       : DWARFUnit(dwarf, uid, header, abbrevs, section) {}
 
   friend class DWARFUnit;
 };
 
 #endif // SymbolFileDWARF_DWARFTypeUnit_h_

source/Plugins/SymbolFile/DWARF/DWARFTypeUnit.cpp

 //===-- DWARFTypeUnit.cpp ---------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "DWARFTypeUnit.h"
 
 #include "SymbolFileDWARF.h"
 #include "lldb/Utility/Stream.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
-
 void DWARFTypeUnit::Dump(Stream *s) const {
   s->Printf("0x%8.8x: Type Unit: length = 0x%8.8x, version = 0x%4.4x, "
             "abbr_offset = 0x%8.8x, addr_size = 0x%2.2x (next CU at "
             "{0x%8.8x})\n",
             GetOffset(), GetLength(), GetVersion(), GetAbbrevOffset(),
             GetAddressByteSize(), GetNextUnitOffset());
 }

source/Plugins/SymbolFile/DWARF/DWARFUnit.h

 /// parse the header before deciding what specific kind of unit to construct.
 class DWARFUnitHeader {
   dw_offset_t m_offset = 0;
   dw_offset_t m_length = 0;
   uint16_t m_version = 0;
   dw_offset_t m_abbr_offset = 0;
   uint8_t m_unit_type = 0;
   uint8_t m_addr_size = 0;
+
+  uint64_t m_type_hash = 0;
+  uint32_t m_type_offset = 0;
+
   uint64_t m_dwo_id = 0;
 
   DWARFUnitHeader() = default;
 
 public:
   dw_offset_t GetOffset() const { return m_offset; }
   uint16_t GetVersion() const { return m_version; }
   uint16_t GetAddressByteSize() const { return m_addr_size; }
   dw_offset_t GetLength() const { return m_length; }
   dw_offset_t GetAbbrOffset() const { return m_abbr_offset; }
   uint8_t GetUnitType() const { return m_unit_type; }
+  uint64_t GetTypeHash() const { return m_type_hash; }
+  dw_offset_t GetTypeOffset() const { return m_type_offset; }
   bool IsTypeUnit() const {
     return m_unit_type == DW_UT_type || m_unit_type == DW_UT_split_type;
   }
   uint32_t GetNextUnitOffset() const { return m_offset + m_length + 4; }
 
   static llvm::Expected<DWARFUnitHeader>
   extract(const lldb_private::DWARFDataExtractor &data, DIERef::Section section,
           lldb::offset_t *offset_ptr);
public:
 
   die_iterator_range dies() {
     ExtractDIEsIfNeeded();
     return die_iterator_range(m_die_array.begin(), m_die_array.end());
   }
 
   DIERef::Section GetDebugSection() const { return m_section; }
 
+  uint8_t GetUnitType() const { return m_header.GetUnitType(); }
+
 protected:
   DWARFUnit(SymbolFileDWARF *dwarf, lldb::user_id_t uid,
             const DWARFUnitHeader &header,
             const DWARFAbbreviationDeclarationSet &abbrevs,
             DIERef::Section section);
 
   llvm::Error ExtractHeader(SymbolFileDWARF *dwarf,
                             const lldb_private::DWARFDataExtractor &data,

source/Plugins/SymbolFile/DWARF/DWARFUnit.cpp

if (header.m_unit_type == llvm::dwarf::DW_UT_skeleton)
       header.m_dwo_id = data.GetU64(offset_ptr);
   } else {
     header.m_abbr_offset = data.GetDWARFOffset(offset_ptr);
     header.m_addr_size = data.GetU8(offset_ptr);
     header.m_unit_type =
         section == DIERef::Section::DebugTypes ? DW_UT_type : DW_UT_compile;
   }
 
+  if (header.IsTypeUnit()) {
+    header.m_type_hash = data.GetU64(offset_ptr);
+    header.m_type_offset = data.GetDWARFOffset(offset_ptr);
+  }
+
   bool length_OK = data.ValidOffset(header.GetNextUnitOffset() - 1);
   bool version_OK = SymbolFileDWARF::SupportedVersion(header.m_version);
   bool addr_size_OK = (header.m_addr_size == 4) || (header.m_addr_size == 8);
+  bool type_offset_OK =
+      !header.IsTypeUnit() || (header.m_type_offset <= header.GetLength());
 
   if (!length_OK)
     return llvm::make_error<llvm::object::GenericBinaryError>(
         "Invalid unit length");
   if (!version_OK)
     return llvm::make_error<llvm::object::GenericBinaryError>(
         "Unsupported unit version");
   if (!addr_size_OK)
     return llvm::make_error<llvm::object::GenericBinaryError>(
         "Invalid unit address size");
+  if (!type_offset_OK)
+    return llvm::make_error<llvm::object::GenericBinaryError>(
+        "Type offset out of range");
 
   return header;
 }
 
 llvm::Expected<DWARFUnitSP>
 DWARFUnit::extract(SymbolFileDWARF *dwarf, user_id_t uid,
                    const DWARFDataExtractor &debug_info, DIERef::Section section,
                    lldb::offset_t *offset_ptr) {