[llvm-dev] DWARF: Should type units be referenced by signature or declaration?

[David Blaikie via llvm-dev]

(ping, in case anyone has some thoughts here)

On Wed, Feb 15, 2017 at 11:00 AM David Blaikie <dblaikie at gmail.com> wrote:

> 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/20170328/1d2d27c2/attachment.html>