DWARF: Should type units be referenced by signature or declaration?

Bunch of initially unrelated context:

  • type units can be referenced in a variety of ways:
  • DW_FORM_ref_sig8 on any attribute needing to reference the type
  • DW_AT_signature on a declaration of the type
  • extra wrinkle: the declaration can be nested into the appropriate namespace and given a name, or not
  • LLVM always does the “most expressive”/expensive thing: a full declaration (though without a name, but with the DW_AT_signature) in the correct namespace.
  • GCC is more selective/nuanced in its choice fo representation, depending on context.
  • Types may be emitted unreferenced (LLVM’s retained types list, which will be more strongly leveraged for C++ modules + debug info in the near future) into type units, or directly into the CU
  • Types that reference addresses (pointer non-type template parameters, for example) may not be in type units when using Fission (they have no way to reference the address pool)
  • The LLVM implementation of this isn’t terribly efficient - a flag is lowered on the address pool, if at any point an address is required the flag is raised and all subsequent type creation is skipped, once control returns to the code responsible for creating the type unit, the flag is examined and if it is up - all the work is thrown out, and the type is then created in the CU.
  • Type units have some overhead (2x on GCC, 1.5x on Clang (as measured by the difference between the reduction in debug_info size compared to the increase in debug_type size) when I measured a while ago)
  • LLVM uses the mangled name of the type as the deduplication key for type units
  • because of this, LLVM doesn’t produce type units for non-public types (eg: classes in anonymous namespaces - or unnamed enums… (this latter one produces some wrinkles))

Motivation:

  • Types that are only emitted once across the program (eg: attached to a template explicit instantiation definition or emitted due to a strong vtable) shouldn’t be put into type units so they don’t pay the overhead.

Issues:

  • This leads to type unit types referencing non-type unit types - what DWARF should be used for that? a type declaration in the type unit? I think: yes
  • This issue sort of already comes up & is punted if the ODR is violated. If an external type references an internal type, the internal type is emitted into the type unit (& into any other TU/CU that uses it - much duplication)
  • If type units may reference other types by declaration (already true - a type may only be available as a declaration) - why not referencing all types by declaration?
  • Is there substantial benefit to the debugger to not have to do name resolution, but rather to match types by signature directly?
  • Since type units can be emitted without an reference to them from the CU, a consumer can’t rely on reachability of the type unit reference graph so this should be only a performance concern, not a correctness one.
  • If declarations are used selectively or pervasively, this would help address pool issue too: even if a type uses an address, it would go in the CU but types referencing that type could still remain in a TU.

So, barring anything else, I’m sort of inclined to just make all references to types in type units plain declarations (oh, also, DW_AT_declaration + DW_AT_name is smaller than DW_AT_declaration + DW_AT_signature (4 bytes instead of 8)). Simpler implementation, possible performance loss for the debugger (lacking the shortcut to find a type by signature instead of name lookup) and should tidy up a bunch of oddities as well as paving the way for improvements around types that don’t need type units.

Any thoughts/suggestions/(dis)recommendations?

  • Dave

Bonus question: it’s possible that the type-with-addresses issue could be checked up front (the DICompositeType could be examined for all its template parameters to see if any involve addresses of globals) but that seems a little brittle (other uses of addresses could crop up - like some IR producer could create a member function declaration in the member list for a member function template instantiation (Clang doesn’t do this - member function template instantiations refer to the class as their scope, but do not appear in the member list - this keeps types uniform across translation units), for example) but could simplify the implementation in terms of not needing to do a bunch of (now much less if all the intermediate types don’t need to be thrown out too) work that may be thrown out. Worth it? Other ideas?
(also: GCC doesn’t implement this rule, so its Fission+type units should have trouble resolving addresses & may end up referring to the wrong address pool, etc)

Hi David, this is pretty dense, I've asked for some clarifications
as well as making a few other comments.

Broadly speaking it seems like there are a couple of problems:
- picking what should be put into a type unit relies on poor heuristics;
- can have an excessive volume of stuff dragged along with the type that
  you actually *want* to put into the type unit.
If there was another one in addition, please reiterate it.

Relying on "has a mangled name" as a proxy for "can go into a type unit"
(which is what it sounded like, not sure I understood that part correctly)
seems like not a great fit. In the original type-unit discussions, I
remember Cary talking about using the signature as the group key; is that
infeasible for some reason? It would keep unnamed enums from being
excluded from type units, as well as being considerably shorter than most
mangled names (saving even more space!).

(Nothing from inside an anonymous namespace should go into a type unit.
Type units are for enabling de-duplication, and anonymous namespaces by
definition do not contain anything sharable across CUs. It wasn't clear
whether you thought the current state of things there was good or bad.)

And the part about throwing away work late, after discovering something
relies on an address... That one would depend on how often you had to
throw away work in practice. I could imagine doing some kind of
isOKForTypeUnit() predicate, traversing the type tree before we actually
emit anything, but whether that's profitable is a performance question
that requires experimental evidence.

As for reducing the volume of stuff in the type unit, I think I need
the clarifications I've asked for below in order to get a handle on
what you are thinking there.

I am interested in having type units be useful and effective, so this
is something I am happy to devote some time to. See inline comments
and looking forward to figuring all this stuff out.
--paulr

From: David Blaikie [mailto:dblaikie@gmail.com]
Sent: Friday, February 03, 2017 7:16 PM
To: llvm-dev; Robinson, Paul; Eric Christopher
Cc: Adrian Prantl
Subject: DWARF: Should type units be referenced by signature or declaration?

Bunch of initially unrelated context:

* type units can be referenced in a variety of ways:
* DW_FORM_ref_sig8 on any attribute needing to reference the type
* DW_AT_signature on a declaration of the type
* extra wrinkle: the declaration can be nested into the appropriate namespace and given a name, or not

Sorry, didn't follow the wrinkle.

* LLVM always does the "most expressive"/expensive thing: a full declaration (though without a name, but with the DW_AT_signature) in the correct namespace.

If you could unpack this a little more, that would help.

* GCC is more selective/nuanced in its choice fo representation, depending on context.
* Types may be emitted unreferenced (LLVM's retained types list, which will be more strongly leveraged for C++ modules + debug info in the near future) into type units, or directly into the CU
* Types that reference addresses (pointer non-type template parameters, for example) may not be in type units when using Fission (they have no way to reference the address pool)
* The LLVM implementation of this isn't terribly efficient - a flag is lowered on the address pool, if at any point an address is required the flag is raised and all subsequent type creation is skipped, once control returns to the code responsible for creating the type unit, the flag is examined and if it is up - all the work is thrown out, and the type is then created in the CU.
* Type units have some overhead (2x on GCC, 1.5x on Clang (as measured by the difference between the reduction in debug_info size compared to the increase in debug_type size) when I measured a while ago)
* LLVM uses the mangled name of the type as the deduplication key for type units
* because of this, LLVM doesn't produce type units for non-public types (eg: classes in anonymous namespaces - or unnamed enums... (this latter one produces some wrinkles))

Motivation:
* Types that are only emitted once across the program (eg: attached to a template explicit instantiation definition or emitted due to a strong vtable) shouldn't be put into type units so they don't pay the overhead.

Issues:
* This leads to type unit types referencing non-type unit types - what DWARF should be used for that? a type declaration in the type unit? I think: yes

A type unit has "a single complete type definition." If the type's definition can be considered complete while making use of other types that are merely declarations, seems fine to me.

* This issue sort of already comes up & is punted if the ODR is violated. If an external type references an internal type, the internal type is emitted into the type unit (& into any other TU/CU that uses it - much duplication)

Yep

* If type units may reference other types by declaration (already true - a type may only be available as a declaration) - why not referencing all types by declaration?

You can probably figure out how to replace some referenced definitions by declarations, when constructing the type unit. Can't be done for everything (there's no way to turn a base_type into a declaration) and for cases where you can substitute, the question is whether the consumer can do anything useful with the breadcrumbs you have left behind.

* Is there substantial benefit to the debugger to not have to do name resolution, but rather to match types by signature directly?

Once I understand the question, I can ask our debugger people. :slight_smile:

* Since type units can be emitted without an reference to them from the CU, a consumer can't rely on reachability of the type unit reference graph so this should be only a performance concern, not a correctness one.

Rely on reachability of the type unit reference graph? Feels like there's a use-case you have in mind that I am not reconstructing.

Hi David, this is pretty dense, I’ve asked for some clarifications
as well as making a few other comments.

Broadly speaking it seems like there are a couple of problems:

  • picking what should be put into a type unit relies on poor heuristics;
  • can have an excessive volume of stuff dragged along with the type that
    you actually want to put into the type unit.
    If there was another one in addition, please reiterate it.

Relying on “has a mangled name” as a proxy for “can go into a type unit”
(which is what it sounded like, not sure I understood that part correctly)
seems like not a great fit.

It’s a pretty good fit. All public types have mangled names. All types with mangled names are public. So it’s pretty much the set of things that can be present in more than one translation unit and represent the same entity (that’s why it has a mangled name - so it can be consistently identified across translation units)

In the original type-unit discussions, I
remember Cary talking about using the signature as the group key; is that
infeasible for some reason?

Ah, practical details - Clang doesn’t produce a type unit signature the way the DWARF spec describes (I believe the spec is overly prescriptive here - how the hash is computed is/should be an implementation detail, I think), instead it hashes the mangled name of the type and uses that as the signature and as the group key.

I suppose this means that the mangling between two different compilers could accidentally/erroneously collide given they’re using different hashing schemes. Don’t think we’ve seen a problem with that in practice so far. It does make sure we hash more equivalent things and requires less work. (actually one of the cases where LLVM produces different DWARF for the same type but still provides a matching hash is this case we’re talking about - if there’s type A with a pointer to B and in one translation unit B is defined and the other B is declared then the type unit for A looks different (in the first it has a DW_AT_signature to reference B, in the second it has a DW_AT_name instead))

It would keep unnamed enums from being
excluded from type units,

Here’s some more details about the unnamed enum situation.

Unnamed enums are actually file-local names. Technically the following would produce an ODR violation in C++, for example:

enum { MY_CONST = 3; }
inline void f() {
(void)MY_CONST;
}

(the ODR requires that every definition of ‘f’ consist of the same sequence of tokens, and that the names referenced from it find the same entities - and since MY_CONST in one translation unit is a different entity from MY_CONST in some other translation unit - two definitions of ‘f’ wouldn’t meet the ODR requirement)

This would be more visible, in say a template instantiation:

template f(T) { }
… f(MY_CONST);

produces an instantiation of ‘f’ with internal linkage (because it has an internal linkage type as a template type parameter).

as well as being considerably shorter than most
mangled names (saving even more space!).

nod no worries about size - the mangled names are in the IR, but they’re hashed for the DWARF output, so it doesn’t make a difference to size.

(Nothing from inside an anonymous namespace should go into a type unit.
Type units are for enabling de-duplication, and anonymous namespaces by
definition do not contain anything sharable across CUs. It wasn’t clear
whether you thought the current state of things there was good or bad.)

Right - but by that same logic, anonymous enums shouldn’t go in type units either, because they have internal/no linkage.

This is a bit of a bug in the C++ spec, probably - Clang’s C++ Modules support works around this by mangling the first member of the enum, so I hear. So we might do the same thing and/or hope someone fixes the C++ spec, then this would all fall out naturally.

And the part about throwing away work late, after discovering something
relies on an address… That one would depend on how often you had to
throw away work in practice. I could imagine doing some kind of
isOKForTypeUnit() predicate, traversing the type tree before we actually
emit anything, but whether that’s profitable is a performance question
that requires experimental evidence.

Sure enough.

As for reducing the volume of stuff in the type unit, I think I need
the clarifications I’ve asked for below in order to get a handle on
what you are thinking there.

I am interested in having type units be useful and effective, so this
is something I am happy to devote some time to. See inline comments
and looking forward to figuring all this stuff out.
–paulr

From: David Blaikie [mailto:dblaikie@gmail.com]
Sent: Friday, February 03, 2017 7:16 PM
To: llvm-dev; Robinson, Paul; Eric Christopher
Cc: Adrian Prantl
Subject: DWARF: Should type units be referenced by signature or declaration?

Bunch of initially unrelated context:

  • type units can be referenced in a variety of ways:
  • DW_FORM_ref_sig8 on any attribute needing to reference the type
  • DW_AT_signature on a declaration of the type
  • extra wrinkle: the declaration can be nested into the appropriate namespace and given a name, or not

Sorry, didn’t follow the wrinkle.

OK - so here’s an example of the 3 ways I’ve seen GCC produce a reference to a type unit:

  1. If a type is referenced exactly once from this (type or compile)unit:
    AT_type FORM_ref_sig8

  2. If the type is referenced more than once (the choice of representation is cost-neutral at this point (two FORM_ref_sig8 or two FORM_ref4 and a structure_type with FORM_ref_sig8) 2 * 8 == 8 + 2 * 4, which doesn’t account for the extra abbrev reference for the TAG_structure_type, but’s probably close enough for government work)
    AT_type FORM_ref4 →
    TAG_structure_type // omits namespaces
    AT_signature FORM_ref_sig8

  3. Only used from a CU, when the type has member functions (with definitions in this CU) or other entities (like nested types) that need to be referenced in the CU.
    AT_type FORM_ref4 →
    TAG_namespace // includes all relevant namespaces
    TAG_structure_type
    AT_name
    AT_declaration
    AT_signature FORM_ref_sig8
    DW_TAG_subprogram, etc…

Here’s an example source file you can compile with GCC and Clang to see how this all looks:

namespace ns {
struct single_reference {
};
struct multiple_reference {
single_reference s;
};
struct full_reference {
void f(single_reference s, multiple_reference m1, multiple_reference m2) {
}
};
}
using namespace ns;
void (full_reference::* x)(single_reference, multiple_reference, multiple_reference) = &full_reference::f;

One extra wrinkle I just spotted - GCC doesn’t produce DIEs for the parameters in the declaration of a member function in a type unit reference (in case (3) above, the DW_TAG_subprogram in the declaration of the type (“full_reference” in the worked example) - that could save us a few bytes)

GCC never uses (3) to reference a type from another type unit - Clang could/should probably do that…

Clang always use (3) but skips the DW_AT_name. I haven’t tested extensively to see which things work/don’t work with GDB for example, but this seemed the most descriptive option and Clang’s debug info was still so much smaller than GCC’s it wasn’t a real priority for me to make it even better at the time.

  • LLVM always does the “most expressive”/expensive thing: a full declaration (though without a name, but with the DW_AT_signature) in the correct namespace.

If you could unpack this a little more, that would help.

Hopefully the above example and details help there. If it’s not clear in any way, I can try to explain differently/better.

  • GCC is more selective/nuanced in its choice fo representation, depending on context.
  • Types may be emitted unreferenced (LLVM’s retained types list, which will be more strongly leveraged for C++ modules + debug info in the near future) into type units, or directly into the CU
  • Types that reference addresses (pointer non-type template parameters, for example) may not be in type units when using Fission (they have no way to reference the address pool)
  • The LLVM implementation of this isn’t terribly efficient - a flag is lowered on the address pool, if at any point an address is required the flag is raised and all subsequent type creation is skipped, once control returns to the code responsible for creating the type unit, the flag is examined and if it is up - all the work is thrown out, and the type is then created in the CU.
  • Type units have some overhead (2x on GCC, 1.5x on Clang (as measured by the difference between the reduction in debug_info size compared to the increase in debug_type size) when I measured a while ago)
  • LLVM uses the mangled name of the type as the deduplication key for type units
  • because of this, LLVM doesn’t produce type units for non-public types (eg: classes in anonymous namespaces - or unnamed enums… (this latter one produces some wrinkles))

Motivation:

  • Types that are only emitted once across the program (eg: attached to a template explicit instantiation definition or emitted due to a strong vtable) shouldn’t be put into type units so they don’t pay the overhead.

Issues:

  • This leads to type unit types referencing non-type unit types - what DWARF should be used for that? a type declaration in the type unit? I think: yes

A type unit has “a single complete type definition.” If the type’s definition can be considered complete while making use of other types that are merely declarations, seems fine to me.

I’m not sure I follow the implication there - are there cases you’ve got in mind where a type might not be “considered complete” when referencing other types by declaration?

At least for Clang - it’s trivial to cause any situation to have a type declaration where it otherwise has a type definition: by giving the type a key function/strong vtable and defining the key function/vtable elsewhere.

eg:

struct foo {
virtual void f();
};
struct bar {
foo f;
};

In some sense ‘bar’ looks like it must have a definition of ‘foo’ available (the code wouldn’t compile if ‘foo’ were only a declaration) but with or without type units, both Clang and GCC produce DWARF containing only a declaration of ‘foo’ and a dfinition of ‘bar’.

This can be done for any type referenced from/used by ‘bar’. So in the sense that all these possible definitions of ‘bar’ are ‘complete’, then it’s true that a type unit for ‘bar’ containing only declarations of other types would be complete.

  • This issue sort of already comes up & is punted if the ODR is violated. If an external type references an internal type, the internal type is emitted into the type unit (& into any other TU/CU that uses it - much duplication)

Yep

  • If type units may reference other types by declaration (already true - a type may only be available as a declaration) - why not referencing all types by declaration?

You can probably figure out how to replace some referenced definitions by declarations, when constructing the type unit. Can’t be done for everything (there’s no way to turn a base_type into a declaration)

Right - this only applies to user defined types, which are the only types that Clang (& I’m pretty sure GCC) put in type units. Base types and the like don’t get separated into their own type unit - the overhead’s probably not worth it, generally. I suppose in theory if you had a particularly complicated composite but not-user-defined type (like a complex pointer type - maybe a function pointer type with lots of interesting parameters, layers of indirection, etc) could be nice to have in a type unit - but I’m not sure the hashing code/type unit spec allows for this since the type doesn’t have a name.

and for cases where you can substitute, the question is whether the consumer can do anything useful with the breadcrumbs you have left behind.

Given that for any case given, one can construct the same type unit that would look identical to the proposed (declarified) output by vtabling all the referenced types - it seems in that sense, any consumer should be OK with a type unit like this, itself.

  • Is there substantial benefit to the debugger to not have to do name resolution, but rather to match types by signature directly?

Once I understand the question, I can ask our debugger people. :slight_smile:

  • Since type units can be emitted without an reference to them from the CU, a consumer can’t rely on reachability of the type unit reference graph so this should be only a performance concern, not a correctness one.

Rely on reachability of the type unit reference graph? Feels like there’s a use-case you have in mind that I am not reconstructing.

I’m not working on/haven’t seen any consumer rely on this, but I could imagine things like the following:

Fission + DWP + type units + GDB Index (made from pubnames/pubtypes)

The GDB index/pubtypes entry for types when using type units from GCC and Clang uses the DW_TAG_compile_unit as the TAG offset to reference for types in a type unit (since the pubtypes doesn’t haev any way of referencing type units, only of referencing offsets within the CU).

So, if GDB (or any other pubtypes-motivated DWARF consumer) wanted to find a reference to type “foo”, looks it up in the index, finds “it’s somewhere in the bar CU”, so it loads the CU and if the type unit were emitted unreferenced (modular codegen, say - where we might pin a definition into the object file even though there’s no code referencing the type - also template explicit instantiation definitions is a place we do this already) there what would it do? Maybe it is referenced from the CU - even then, GDB has to search through every type reference (except the (3) - if ‘foo’ was referenced with a (3), GDB could find the name and then not load any other types, follow the signature and load that one type) and every type they reference, etc.

What’s the alternative? Load every type in the DWP/in the whole program to see if it’s a type called ‘foo’?

Without DWP it’s at least constrained - the pubtypes in this DWO file say “foo” is somewhere here so the consumer can search all the type units in the DWO - not quick, but at least it’s not “ever type in the program”. Once all the types are thrown together into the DWP that constrained environment is lost.

(ping, in case anyone has some thoughts here)