[llvm][DebugInfo] Add DW_TAG_imported_declaration to accelerator tables

[Michael137]

Summary

Summary

After this patch, DW_TAG_imported_declarations will be emitted into
the DWARF accelerator tables (under .apple_namespaces)

Motivation

Currently LLDB expression evaluation doesn't see through namespace
aliases. This is because LLDB only considers namespaces that are
part of .apple_namespaces when building a nested namespace
identifier for C++, which currently doesn't include import
declarations. The alternative to putting imports into accelerator
tables is to do a linear scan of a DW_TAG_namespace and look
for import declarations that look like they would satisfy the lookup
request, which is prohibitively expensive.

Testing

• Added unit-test

[Michael137]

llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

1295

Since import declarations could have empty names I'll have to decide what to do here w.r.t. accelerator tables. The spec says in the case of an empty name we can refer to the entity by the name of the entity it is importing.

[dblaikie]

It'd be good if this issue were submitted to the DWARF committee as a fix for the .debug_names accelerator tables.

I don't /think/ you need unnamed entries in the index - since these entries are only for finding named entities by unqualified name, so an unnamed using namespace doesn't introduce any new unqualified names?

I guess if the user writes "x::y" (and the code has "z::y" defined and "using namespace z" in namespace x) then you need some breadcrumb that when you do unqualified lookup for "y" and unqualified lookup for "x" you can see that they're connected/actually would resolve to that name? How does this work currently for "z::y"? You do lookup for "y" then check its parent DIE and see that it's "z" and so it satisfies the lookup?

[Michael137]

In D143397#4107079, @dblaikie wrote:

It'd be good if this issue were submitted to the DWARF committee as a fix for the .debug_names accelerator tables.

I don't /think/ you need unnamed entries in the index - since these entries are only for finding named entities by unqualified name, so an unnamed using namespace doesn't introduce any new unqualified names?

I guess if the user writes "x::y" (and the code has "z::y" defined and "using namespace z" in namespace x) then you need some breadcrumb that when you do unqualified lookup for "y" and unqualified lookup for "x" you can see that they're connected/actually would resolve to that name? How does this work currently for "z::y"? You do lookup for "y" then check its parent DIE and see that it's "z" and so it satisfies the lookup?

I don't /think/ you need unnamed entries in the index - since these entries are only for finding named entities by unqualified name, so an unnamed using namespace doesn't introduce any new unqualified names?

Actually I'm not quite sure how we can get empty import declarations (since using namespace Foo is represented by DW_TAG_imported_module)

I guess if the user writes "x::y" (and the code has "z::y" defined and "using namespace z" in namespace x) then you need some breadcrumb that when you do unqualified lookup for "y" and unqualified lookup for "x" you can see that they're connected/actually would resolve to that name?

Good point, currently this isn't supported. And this patch wouldn't help with that. To support x::y in LLDB we'd have to add the DW_TAG_imported_module into the accelerator table too, under the name of the module it's importing (?) Though I'd be fine with not adding support for this for now

How does this work currently for "z::y"? You do lookup for "y" then check its parent DIE and see that it's "z" and so it satisfies the lookup?

The order of operations is:

1. Lookup z. Finds namespace
2. Lookup y. Finds namespace
3. Check that y "is contained in" z (accounts for inline namespaces between the two). This is purely based on walking through the parent DIEs of y

[dblaikie]

In D143397#4107156, @Michael137 wrote:

In D143397#4107079, @dblaikie wrote:

It'd be good if this issue were submitted to the DWARF committee as a fix for the .debug_names accelerator tables.

I don't /think/ you need unnamed entries in the index - since these entries are only for finding named entities by unqualified name, so an unnamed using namespace doesn't introduce any new unqualified names?

I guess if the user writes "x::y" (and the code has "z::y" defined and "using namespace z" in namespace x) then you need some breadcrumb that when you do unqualified lookup for "y" and unqualified lookup for "x" you can see that they're connected/actually would resolve to that name? How does this work currently for "z::y"? You do lookup for "y" then check its parent DIE and see that it's "z" and so it satisfies the lookup?

I don't /think/ you need unnamed entries in the index - since these entries are only for finding named entities by unqualified name, so an unnamed using namespace doesn't introduce any new unqualified names?

Actually I'm not quite sure how we can get empty import declarations (since using namespace Foo is represented by DW_TAG_imported_module)

Oh, right, sorry, didn't notice the distinction between imported module and imported declaration. Ah, you're talking about code like this:

namespace ns1 {
struct t1 { };
};
namespace ns2 {
using ns1::t1;
}
namespace ns3 {
using t2 = ns1::t1;
}

So the DWARF for the first DW_TAG_imported_declaration (in ns2) won't have a name - it inherits the name from the entity.

Oh... seems clang just doesn't emit DWARF for the ns2::t1 case - if you try to use that type it resolves to ns1::t1, which is a (minor) bug. I implemented the imported declaration stuff years ago, and it's... not great (Clang doesn't track usage of using namespaces especially - and I guess unnamed using decls - makes it hard to emit them only when needed, and the usual DWARF-reachability that helps trim DWARF during IR optimization/linking can't kick in because nothing references the imported namespaces especially)

I guess if the user writes "x::y" (and the code has "z::y" defined and "using namespace z" in namespace x) then you need some breadcrumb that when you do unqualified lookup for "y" and unqualified lookup for "x" you can see that they're connected/actually would resolve to that name?

Good point, currently this isn't supported. And this patch wouldn't help with that. To support x::y in LLDB we'd have to add the DW_TAG_imported_module into the accelerator table too, under the name of the module it's importing (?) Though I'd be fine with not adding support for this for now

Ah, right, fair enough.

How does this work currently for "z::y"? You do lookup for "y" then check its parent DIE and see that it's "z" and so it satisfies the lookup?

The order of operations is:

1. Lookup z. Finds namespace
2. Lookup y. Finds namespace
3. Check that y "is contained in" z (accounts for inline namespaces between the two). This is purely based on walking through the parent DIEs of y

yeah, easy for the canonical/original namespace - doing that for imported namespaces/entities would be tricky. I guess, yeah, for named imported entities it's possible to put the name in the index, pointing to the imported entity - then you can do the walk up.

But that doesn't work with unnamed using decls where all the names of the other namespace are brought in. :/

llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

1295

You could go find the name of the entity it's importing to support this, I suppose? Maybe worth a comment/FIXME/etc?

You could try adding a temporary/non-committed assertion here that Name is !empty & bootstrap clang or the like to see if there are cases where we emit an imported declaration with an empty name?

[Michael137]

llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

1295

Ah apparently things like:

using ::nullptr_t;                        
using ::ptrdiff_t _LIBCPP_USING_IF_EXISTS;
using ::size_t _LIBCPP_USING_IF_EXISTS;

Generate empty DW_AT_imported_declaration entries. But apparently this is not supported for namespaces, so I think we can just not handle the empty name case and add a comment as to why we're not doing that.

[Michael137]

yeah, easy for the canonical/original namespace - doing that for imported namespaces/entities would be tricky. I guess, yeah, for named imported entities it's possible to put the name in the index, pointing to the imported entity - then you can do the walk up.

Yup that's exactly how I've prototyped it in LLDB: https://reviews.llvm.org/D143398

But that doesn't work with unnamed using decls where all the names of the other namespace are brought in. :/

True, I think I'll just proceed with not supporting the unnamed (and using namespace ...) cases for now

[Michael137]

• Add FIXME

[Michael137]

• Added an unnamed import declaration to test

[Michael137]

It'd be good if this issue were submitted to the DWARF committee as a fix for the .debug_names accelerator tables.

Would make sense, I'll put something up

Currently section 6.1.1 of the DWARFv5 spec says:

The name index must contain an entry for each debugging information entry that
defines a named subprogram, label, variable, type, or namespace, subject to the
following rules:

Probably just need to adjust this list to include import declarations

[aprantl]

It'd be good if this issue were submitted to the DWARF committee as a fix for the .debug_names accelerator tables.

Sounds good to me. Just to clarify — I don't think that should block adopting this extension in LLVM though, do you agree?

[Michael137]

Open DWARF issue: https://dwarfstd.org/ShowIssue.php?issue=230206.1

llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

DIE *DwarfCompileUnit::constructImportedEntityDIE(
   else if (auto *GV = dyn_cast<DIGlobalVariable>(Entity))
     EntityDie = getOrCreateGlobalVariableDIE(GV, {});
   else
     EntityDie = getDIE(Entity);
   assert(EntityDie);
   addSourceLine(*IMDie, Module->getLine(), Module->getFile());
   addDIEEntry(*IMDie, dwarf::DW_AT_import, *EntityDie);
   StringRef Name = Module->getName();
-  if (!Name.empty())
+  if (!Name.empty()) {
     addString(*IMDie, dwarf::DW_AT_name, Name);
 
+    // FIXME: if consumers ever start caring about handling
+    // unnamed import declarations such as `using ::nullptr_t`
+    // or `using namespace std::ranges`, we could add the
+    // import declaration into the accelerator table with the
+    // name being the one of the entity being imported.
+    DD->addAccelNamespace(*CUNode, Name, *IMDie);
+  }
+
   // This is for imported module with renamed entities (such as variables and
   // subprograms).
   DINodeArray Elements = Module->getElements();
   for (const auto *Element : Elements) {
     if (!Element)
       continue;
     IMDie->addChild(
         constructImportedEntityDIE(cast<DIImportedEntity>(Element)));

llvm/test/DebugInfo/Inputs/accel-imported-declaration.cpp

+// Compiled on MacOS using:
+// clang++ -c -std=c++2a -gdwarf-4 -O0 -o accel-imported-declaration.macho-arm64.o
+
+namespace A {
+namespace B {
+namespace C {
+int a = -1;
+} // namespace C
+} // namespace B
+
+namespace C = B::C;
+
+using namespace B::C;
+using B::C::a;
+} // namespace A

llvm/test/DebugInfo/accel-imported-declaration.test

+RUN: llvm-dwarfdump -v %p/Inputs/accel-imported-declaration.macho-arm64.o | FileCheck %s
+RUN: llvm-dwarfdump -verify %p/Inputs/accel-imported-declaration.macho-arm64.o | FileCheck %s --check-prefix=VERIFY
+
+Gather some DIE indexes to verify the accelerator table contents.
+
+CHECK: .debug_info contents
+CHECK: {{.*}}DW_TAG_namespace
+CHECK:   DW_AT_name{{.*}}"A"
+CHECK: {{.*}}DW_TAG_namespace
+CHECK:   DW_AT_name{{.*}}"B"
+CHECK: [[NAMESPACE:0x[0-9a-f]*]]:{{.*}}DW_TAG_namespace
+CHECK:   DW_AT_name{{.*}}"C"
+CHECK: [[IMPORTED:0x[0-9a-f]*]]:{{.*}}DW_TAG_imported_declaration
+CHECK:   DW_AT_name{{.*}}"C"
+
+Check that the .apple_namespaces section contains two entries for "namespace C"
+
+CHECK:      .apple_namespaces contents:
+CHECK:      Bucket 1 [
+CHECK-NEXT:   Hash {{.*}} [
+CHECK-NEXT:     Name{{.*}} {
+CHECK-NEXT:       String: {{.*}} "C"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: [[NAMESPACE]]
+CHECK-NEXT:       ]
+CHECK-NEXT:       Data 1 [
+CHECK-NEXT:         Atom[0]: [[IMPORTED]]
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+
+VERIFY:      Verifying .apple_names...
+VERIFY-NEXT: Verifying .apple_types...
+VERIFY-NEXT: Verifying .apple_namespaces...
+VERIFY-NEXT: Verifying .apple_objc...
+VERIFY-NEXT: No errors.