llvm dev - Feb 2017 - 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)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170204/720408db/attachment.html>

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 at 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. :-)
> * 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.
> * 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)

On Tue, Feb 14, 2017 at 7:32 PM Robinson, Paul <paul.robinson at sony.com>
wrote:
> 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<typename T> 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 at 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. :-)
>
> > * 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.

>
> > * 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)
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170215/e5d55cdb/attachment.html>