[LLDB][DWARF] Fix duplicate TypeSP in type list

[zequanwu]

Summary

The call graph is SymbolFileDWARF::ParseType -> DWARFASTParserClang::ParseTypeFromDWARF -> DWARFASTParserClang::UpdateSymbolContextScopeForType.
This patch removed the insertion of type to type list at UpdateSymbolContextScopeForType, since SymbolFileDWARF::ParseType always inserts the type returned by ParseTypeFromDWARF into the type list.

[labath]

Thanks for fixing this. I assume that the type is already being added to the type list somewhere else -- it'd be nice to say, for future archaeologists' sake, where that actually happens.

But my main question is really about the test.

lldb/test/Shell/SymbolFile/DWARF/x86/find-basic-type.cpp

40

Does this actually check that the type is not emitted more than once?

This is the reason why the other checks have the "Found <X> types" assertion above. We currently don't have such output from --find=none, but feel free to add something.

It might also be better to make this a separate test, as the output also includes things like int -- it would start to get messy if you included all of that here, and this test was about testing something different anyway.

[zequanwu]

I found that is actually a problem in TypeList. We need to uniquify Type in
TypeList. Otherwise, ParseTypes will add the same types twice because it
parses types in a dfs way without keeping track of what has been parsed.

• Use an additional set of Type* to check if it exists or not.
• Print number of types in TypeList.

[shafik]

I would also like to know where this duplicate insertion is happening. Can you walk us through the steps that lead to the duplicate entries? thank you!

[zequanwu]

In D115308#3184564, @shafik wrote:

I would also like to know where this duplicate insertion is happening. Can you walk us through the steps that lead to the duplicate entries? thank you!

Firstly, I found that SymbolFileDWARF::ParseType -> DWARFASTParserClang::ParseTypeFromDWARF -> DWARFASTParserClang::UpdateSymbolContextScopeForType. It's inserting the same type at both places (SymbolFileDWARF::ParseType and DWARFASTParserClang::UpdateSymbolContextScopeForType ). In my first revision, I just attempted to remove the insertion in UpdateSymbolContextScopeForType. Then I found that when running lldb-test symbols [binary], it's inserting same types at ParseTypes. For following dwarf info, when ParseType was called for DW_TAG_subroutine_type, it will also call ParseType for the type DW_TAG_base_type inside it. When the top-level ParseTypes iterates to 0x0000010f, the type will be inserted twice:

0x0000010a:   DW_TAG_subroutine_type
                DW_AT_type      (0x0000010f "int")

0x0000010f:   DW_TAG_base_type
                DW_AT_name      ("int")
                DW_AT_encoding  (DW_ATE_signed)
                DW_AT_byte_size (0x04)

So, I figured it might be better to deduplicate the types inside TypeList when insertion happens, though ParseTypes is only used at lldb-test.

[labath]

I don't know whether the types should be uniqued at this level (obviously, they should be uniqued somewhere), but these are the thoughts that spring to mind:

• if this is a problem for lldb-test, then it would be preferable to come up with a solution that does not negatively impact the performance and memory consumption of the production code
• it seems like this patch essentially implements its own copy of llvm::SetVector
• It's unfortunate to have set-like semanticts in TypeList, when we already have a type called TypeSet.

lldb/test/Shell/SymbolFile/DWARF/x86/dump-types.cpp

3–13 ↗

(On Diff #392932)

It doesn't seem necessary to run all three accelerator flavours for this kind of a test.

[zequanwu]

Revert back to first diff.

[zequanwu]

In D115308#3189261, @labath wrote:

I don't know whether the types should be uniqued at this level (obviously, they should be uniqued somewhere), but these are the thoughts that spring to mind:

• if this is a problem for lldb-test, then it would be preferable to come up with a solution that does not negatively impact the performance and memory consumption of the production code

I reverted it back to first diff. But I can't use lldb-test for testing purpose, since there is a problem for lldb-test that inserting duplicate types into type list (https://reviews.llvm.org/D115308?vs=on&id=392599#3188183).

lldb/test/Shell/SymbolFile/DWARF/x86/find-basic-type.cpp

40

It actually still emits types more than once using lldb-test.

[labath]

Since you're simply removing code, I don't think that we need to insist on new test cases -- not breaking existing ones should suffice. That said, if you know of a way to test this via the image dump symfile command, I would definitely encourage you to do so.

And yes, we need to figure out what to do with lldb-test. Maybe we should just rewrite ParseTypes (used only in tests) to do the parsing in a different way...

lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

 }
 
 TypeSP DWARFASTParserClang::UpdateSymbolContextScopeForType(
     const SymbolContext &sc, const DWARFDIE &die, TypeSP type_sp) {
   if (!type_sp)
     return type_sp;
 
   SymbolFileDWARF *dwarf = die.GetDWARF();
-  TypeList &type_list = dwarf->GetTypeList();
   DWARFDIE sc_parent_die = SymbolFileDWARF::GetParentSymbolContextDIE(die);
   dw_tag_t sc_parent_tag = sc_parent_die.Tag();
 
   SymbolContextScope *symbol_context_scope = nullptr;
   if (sc_parent_tag == DW_TAG_compile_unit ||
       sc_parent_tag == DW_TAG_partial_unit) {
     symbol_context_scope = sc.comp_unit;
   } else if (sc.function != nullptr && sc_parent_die) {
     symbol_context_scope =
         sc.function->GetBlock(true).FindBlockByID(sc_parent_die.GetID());
     if (symbol_context_scope == nullptr)
       symbol_context_scope = sc.function;
   } else {
     symbol_context_scope = sc.module_sp.get();
   }
 
   if (symbol_context_scope != nullptr)
     type_sp->SetSymbolContextScope(symbol_context_scope);
 
-  // We are ready to put this type into the uniqued list up at the module
-  // level.
-  type_list.Insert(type_sp);
-
   dwarf->GetDIEToType()[die.GetDIE()] = type_sp.get();
   return type_sp;
 }
 
 TypeSP
 DWARFASTParserClang::ParseStructureLikeDIE(const SymbolContext &sc,
                                            const DWARFDIE &die,
                                            ParsedDWARFTypeAttributes &attrs) {

lldb/test/Shell/SymbolFile/DWARF/x86/find-basic-type.cpp

 // REQUIRES: lld
 
 // RUN: %clang %s -g -c -o %t.o --target=x86_64-pc-linux -gno-pubnames
 // RUN: ld.lld %t.o -o %t
 // RUN: lldb-test symbols --name=foo --find=type %t | \
 // RUN:   FileCheck --check-prefix=NAME %s
 // RUN: lldb-test symbols --name=foo --context=context --find=type %t | \
 // RUN:   FileCheck --check-prefix=CONTEXT %s
 // RUN: lldb-test symbols --name=not_there --find=type %t | \
 // RUN:   FileCheck --check-prefix=EMPTY %s
+// RUN: lldb-test symbols --find=none %t | FileCheck --check-prefix=TYPES %s
 //
 // RUN: %clang %s -g -c -o %t --target=x86_64-apple-macosx
 // RUN: lldb-test symbols --name=foo --find=type %t | \
 // RUN:   FileCheck --check-prefix=NAME %s
 // RUN: lldb-test symbols --name=foo --context=context --find=type %t | \
 // RUN:   FileCheck --check-prefix=CONTEXT %s
 // RUN: lldb-test symbols --name=not_there --find=type %t | \
 // RUN:   FileCheck --check-prefix=EMPTY %s
+// RUN: lldb-test symbols --find=none %t | FileCheck --check-prefix=TYPES %s
 
 // RUN: %clang %s -c -o %t.o --target=x86_64-pc-linux -gdwarf-5 -gpubnames
 // RUN: ld.lld %t.o -o %t
 // RUN: llvm-readobj --sections %t | FileCheck %s --check-prefix NAMES
 // RUN: lldb-test symbols --name=foo --find=type %t | \
 // RUN:   FileCheck --check-prefix=NAME %s
 // RUN: lldb-test symbols --name=foo --context=context --find=type %t | \
 // RUN:   FileCheck --check-prefix=CONTEXT %s
 // RUN: lldb-test symbols --name=not_there --find=type %t | \
 // RUN:   FileCheck --check-prefix=EMPTY %s
+// RUN: lldb-test symbols --find=none %t | FileCheck --check-prefix=TYPES %s
 
 // NAMES: Name: .debug_names
 
 // EMPTY: Found 0 types:
 // NAME: Found 4 types:
 // CONTEXT: Found 1 types:
 struct foo { };
 // NAME-DAG: name = "foo", {{.*}} decl = find-basic-type.cpp:[[@LINE-1]]
+// TYPES: name = "foo", size = 1, decl = find-basic-type.cpp:[[@LINE-2]]
 
 namespace bar {
 int context;
 struct foo {};
 // NAME-DAG: name = "foo", {{.*}} decl = find-basic-type.cpp:[[@LINE-1]]
 // CONTEXT-DAG: name = "foo", {{.*}} decl = find-basic-type.cpp:[[@LINE-2]]
+// TYPES: name = "foo", size = 1, decl = find-basic-type.cpp:[[@LINE-3]]
 namespace baz {
 struct foo {};
 // NAME-DAG: name = "foo", {{.*}} decl = find-basic-type.cpp:[[@LINE-1]]
+// TYPES: name = "foo", size = 1, decl = find-basic-type.cpp:[[@LINE-2]]
 }
 }
 
 struct sbar {
+  // TYPES: name = "sbar", size = 1, decl = find-basic-type.cpp:[[@LINE-1]]
   struct foo {};
   // NAME-DAG: name = "foo", {{.*}} decl = find-basic-type.cpp:[[@LINE-1]]
+  // TYPES: name = "foo", size = 1, decl = find-basic-type.cpp:[[@LINE-2]]
 };
 
 struct foobar {};
+// TYPES: name = "foobar", size = 1, decl = find-basic-type.cpp:[[@LINE-1]]
 
 struct Foo {};
+// TYPES: name = "Foo", size = 1, decl = find-basic-type.cpp:[[@LINE-1]]
 
 extern "C" void _start(foo, bar::foo, bar::baz::foo, sbar::foo, foobar, Foo) {}