[llvm-dev] [DWARF] using simplified template names
David Blaikie via llvm-dev
Context:
We (at Google) have been seeing some significant DWARF growth in binaries lately due to increased use of libraries like Eigen and TensorFlow that use expression templates.
This includes some cases where the debug_str.dwo section has exceeded the DWARF32 limit (& the binutils dwp tool silently wrote overflowed indexes into the debug_str_offsets.dwo section, unfortunately - leading to corrupted/garbled names in backtraces) & most of the growth is from the demangled names of complicated/large expression templates.
Options:
One solution would be to move to DWARF64 - though that does make DWARF overall larger, which is an unfortunate cost that would be nice to avoid.
Another might be to rely solely on linkage names (add linkage names to types), since mangled names generally reduce a lot of the duplication - though in some cases it's not a matter of duplication within a single name, but possibly many distinct types used as template parameters - though those types may also be used in other names (& mangled names have no sharing across names).
Compression doesn't help, since the offsets are into the uncompressed data.
Main idea:
What if templates instead only encoded the base name, such as "vector" (rather than "vector<int, std::allocator<int>>")? The full name could still be reconstructed from the DW_TAG_template_type_parameters (non-type template parameters would be more difficult, and we'd need to add template parameters to template declarations - functionality we have, but is only enabled for SCE today)).
This could significantly reduce debug info size (in some worst-cases I've seen this lead to a 50% reduction in the uncompressed size of .debug_str.dwo in a dwp file, for instance - probably less exciting if the data was compressed - but gives a sense of the headroom available before this limit will be reached again).
Also has the nice property that it's not a new format or encoding that might break existing consumers immediately (DWARF64, for instance isn't widely implemented to my knowledge, so many consumers would need to be fixed before they could parse any of it) - if a consumer doesn't know, it'll still see a name, just not the most fully descriptive/specific name it could be. For a symbolizer this is probably fairly low cost - users would find it more difficult, but not totally useless to get a simple template function name.
As it happens, it seems GDB is already built to cope with this situation - it can print the real name of the type and can even correctly match up two distinct type declarations between translation units by correctly matching their template parameters.
GDB Example:
a.h:
a.cpp:template<typename T>
struct t1 { T t = sizeof(T); };
void f(t1<int> &p1, t1<short> *&p2);
b.cpp:#include "a.h"
int main() {
t1<int> v1;
t1<short> *v2 = nullptr;
t1<bool> *v3 = nullptr;
f(v1, v2);
}
#include "a.h"
void f(t1<int> &p1, t1<short> *&p2) {
static t1<short> v2;
p2 = &v2;
}
// using a clang modified to produce simple template names, and
// to include template parameters on declarations
// (-Xclang -debug-forward-template-params)
$ clang++ a.cpp b.cpp -g
$ llvm-dwarfdump a.out (glossing over some details)
DW_TAG_compile_unit
DW_AT_name ("a.cpp")
DW_TAG_structure_type
DW_AT_name ("t1")
DW_TAG_template_type_parameter
DW_AT_type (0x00000098 "int")
DW_AT_name ("T")
DW_TAG_member
DW_AT_name ("t")
DW_AT_type (0x00000098 "int")
DW_TAG_structure_type
DW_AT_name ("t1")
DW_AT_declaration (true)
DW_TAG_template_type_parameter
DW_AT_type (0x000000e2 "short")
DW_AT_name ("T")
DW_TAG_structure_type
DW_AT_name ("t1")
DW_AT_declaration (true)
DW_TAG_template_type_parameter
DW_AT_type (0x000000fd "bool")
DW_AT_name ("T")
DW_TAG_compile_unit
DW_AT_name ("b.cpp")
DW_TAG_structure_type
DW_AT_name ("t1")
DW_TAG_template_type_parameter
DW_AT_type (0x0000019e "short")
DW_AT_name ("T")
DW_TAG_member
DW_AT_name ("t")
DW_AT_type (0x0000019e "short")
DW_TAG_structure_type
DW_AT_name ("t1")
DW_AT_declaration (true)
DW_TAG_template_type_parameter
DW_AT_type (0x000001b9 "int")
DW_AT_name ("T")
$ gdb ./a.out
(gdb) start
(gdb) ptype v1
type = struct t1<int> [with T = int] {
T t;
}
(gdb) ptype v2
type = struct t1<short> [with T = short] {
T t;
} *
(gdb) ptype v3
type = struct t1<bool> {
<incomplete type>
} *
(gdb) ptype v1.t
type = int
(gdb) ptype v2->t
type = short
(gdb) ptype v3->t
There is no member named t.
GDB has correctly rendered the type names, despite lacking the template parameter lists being in the DW_AT_name - and has correctly associated the definitions with the declarations despite the DW_AT_name being ambiguous, by using the DW_TAG_template_type_parameters.
lldb doesn't cope with this sort of DWARF currently - it has a bunch of assumptions about the names of template instantiations that'll need to be fixed before it can consume this sort of thing.
I haven't tested a wide number of symbolizers, but I assume they'll generally need some work too.
So... how's this sound to everyone? An idea worth pursuing? Concerns/questions/etc.
I don't expect this to become the default for LLVM in the short term at least - but under a flag for those whose consumers can handle it (/maybe/ we do it under debugger tuning for gdb, since it seems OK with it - but that might be a bit stronger than we want to do under the default tuning, since it's really broken for lldb, not just a little bit broken).
- Dave
via llvm-dev
Fully expanded names of template instantiations can become impressively large, yeah.
The DWARF Wiki’s Best Practices page http://wiki.dwarfstd.org/index.php?title=Best_Practices recommends including a canonical form of the template parameters in the DW_AT_name attribute. I don’t know that I agree; it talks about omitting qualifiers (namespaces, containing classes) because those can be reconstructed from the DIE hierarchy, but the same argument can be made for template parameters (the difference being that qualifiers come from higher up the tree, while template parameters come from farther down). The DRY principle would seem to apply here.
I’ll verify with our debugger team, but I’m confident that dropping the <params> from the type name will not affect Sony, as our debugger looks at the template-parameter children already (that’s why we have that turned on by default for sce tuning). LLDB seems to be the odd debugger out, here, and we have some control over that. 😊
Oh, is there any consequence for deduplication in LTO? Isn’t that name-based?
--paulr
David Blaikie via llvm-dev
Fully expanded names of template instantiations can become impressively large, yeah.
The DWARF Wiki’s Best Practices page http://wiki.dwarfstd.org/index.php?title=Best_Practices recommends including a canonical form of the template parameters in the DW_AT_name attribute. I don’t know that I agree; it talks about omitting qualifiers (namespaces, containing classes) because those can be reconstructed from the DIE hierarchy, but the same argument can be made for template parameters (the difference being that qualifiers come from higher up the tree, while template parameters come from farther down). The DRY principle would seem to apply here.
Ah, good to know - and yeah, the asymmetry between omitting namespace qualifiers but including parameters is noteworthy.
I’ll verify with our debugger team, but I’m confident that dropping the <params> from the type name will not affect Sony, as our debugger looks at the template-parameter children already (that’s why we have that turned on by default for sce tuning). LLDB seems to be the odd debugger out, here, and we have some control over that. 😊
Ah, fascinating/good to know!
So even if /maybe/ we wouldn't want to do this for GDB tuning (I'd be a bit hesitant to diverge that much from GCC's defaults even if it seems to work (more testing to see how broadly it works) you might be interested in this being the default for SCE? That'd be good to do. I guess if we fix LLDB might be able to switch the defaults there too.
Oh, is there any consequence for deduplication in LTO? Isn’t that name-based?
Should be OK - that's based on the fully mangled/linkage name of the type, which would be untouched by this.
One quirk is that we probably can't do this for templates with pointer non-type template parameters (I haven't tested non-pointer non-type template parameters (such as integers, chars, etc) but I'd hope GDB can handle that and that would provide at least some "proof of concept") since they don't have an easy unambiguous stringification - even though you can only use a named variable/function/etc (ie: can't use an array offset, or other computed address) - neither GCC nor Clang encode that string, but instead encode the address (well, GCC doesn't even encode the address - so that debug info doesn't adversely affect code generation by causing the symbol to be linked in when it's otherwise unreferenced by the actual code) & so coming up with an unambiguous/consistent string to use in building the name would be a bit much. GDB doesn't seem to handle that situation. (says "UNKNOWN" or similar for the parameter, thus creating ambiguity when matching against others, etc)
The other area I'd be unsure about would be indexes - gdb index and DWARFv5 debug_names. We'll be indexing the linkage/mangled name (hmm, we don't do the linkage name for types - only for functions), and the simple name - but, as you point out - we were skipping namespaces already, so it's not like looking up "foo<int>" was unambiguous anyway - so they'll be a bit more ambiguous after this change. Some consumer performance impact - they'd have to search through more duplicates (take std::vector - now a consumer will have to go look at every CU that has any vector instantiation, whereas previously they were probably able to only look at the vector<int> instantiating CUs (& any nonstd::vector<int> out there as well) for instance).
- Dave
Adrian Prantl via llvm-dev
On Jun 4, 2021, at 6:33 PM, David Blaikie <dbla...@gmail.com> wrote:tl;dr: What if we used only the base name of templates in the DW_AT_name field for function and class templates (eg: "vector" instead of "vector<int, std::allocator<int>>")?
Context:
We (at Google) have been seeing some significant DWARF growth in binaries lately due to increased use of libraries like Eigen and TensorFlow that use expression templates.
This includes some cases where the debug_str.dwo section has exceeded the DWARF32 limit (& the binutils dwp tool silently wrote overflowed indexes into the debug_str_offsets.dwo section, unfortunately - leading to corrupted/garbled names in backtraces) & most of the growth is from the demangled names of complicated/large expression templates.
Options:
One solution would be to move to DWARF64 - though that does make DWARF overall larger, which is an unfortunate cost that would be nice to avoid.
Another might be to rely solely on linkage names (add linkage names to types), since mangled names generally reduce a lot of the duplication - though in some cases it's not a matter of duplication within a single name, but possibly many distinct types used as template parameters - though those types may also be used in other names (& mangled names have no sharing across names).
David Blaikie via llvm-dev
I mean I know it currently breaks lldb in a bunch of ways - when you say "workflows" do you mean more fundamental things than bugs? (like features that could not be built, or would be sort of fundamentally difficult to build, with this proposed alternative format)
but perhaps not necessarily the most useful ones. LLDB will search types by name in many situations, but the fact that template types can be formatted in many different ways and may contain whitespace makes this process brittle already.
Presumably lldb already has to deal with some ambiguity here, since those names don't include the namespace, for instance, in the name?
In order to support currently supported workflows we may need to implement a type lookup where we stri out everything but the basename in the searched type, then do a by-(base)name lookup, and then filter for template arguments. From afar this sounds doable, but we should make sure not to enable this debug info optimization without qualifying it in LLDB first.
Fair - I was thinking worst case can go the other way too: Everywhere lldb currently looks at the name, it could check if the name was "simple" (are there DW_TAG_template_parameters and no angle brackets in the DW_AT_name?) then produce the full name string by checking the template parameter DIEs, etc - then use that as before/without this feature. But yeah, either way - strip everything down, or build everything up.
- Dave
via llvm-dev
I’ve heard back from the Sony debugger folks, and dropping the <params> from the parent DIE’s name will have no bad effect on us. We rebuild the <params> from the children, and we don’t currently make use of the index. If this tactic goes under an option, we’d definitely like to have that set by default under sce-tuning to get the space savings.
David Blaikie via llvm-dev
(out of curiosity, any idea what the Sony debugger does for pointer template parameters? At least GCC doesn't seem to be able to reconstruct those back into strings (you'd basically have to symbolize the address value of the parameter (GCC doesn't even encode this value, so it's not surprising GDB doesn't try to do anything when it's present)) - so I'll probably implement this under a flag but not include (ie: use the current full textual encoding) any template with a pointer template parameter)
eg: extern int i; template<int *> void f1() { } int main() { f1<&i>(); }
via llvm-dev
> pointer template parameters? At least GCC doesn't seem to be
> able to reconstruct those back into strings (you'd basically
> have to symbolize the address value of the parameter (GCC
> doesn't even encode this value, so it's not surprising GDB
> doesn't try to do anything when it's present)) - so I'll
> probably implement this under a flag but not include (ie: use
> the current full textual encoding) any template with a pointer
> template parameter)
>
> eg: extern int i; template<int *> void f1() { } int main() { f1<&i>(); }
appear to be a special case of non-type template params that can
be arbitrary compile-time expressions; for non-pointer params we
provide the computed value of the compile-time expression, which
is arguably sufficient for cases like
constexpr int a = 1; constexpr int b = 2;
template <int> void f2() { }
void int_expr() { f2<a + b>(); }
but it would be nice to do something useful for
extern int j[4];
void ptr_expr() { f1<&j[a+b]>(); }
We can't repurpose DW_AT_name for this because that's the
template parameter's formal name; nothing else comes to mind,
maybe we need a new attribute for this.
--paulr
_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
David Blaikie via llvm-dev
> (out of curiosity, any idea what the Sony debugger does for
> pointer template parameters? At least GCC doesn't seem to be
> able to reconstruct those back into strings (you'd basically
> have to symbolize the address value of the parameter (GCC
> doesn't even encode this value, so it's not surprising GDB
> doesn't try to do anything when it's present)) - so I'll
> probably implement this under a flag but not include (ie: use
> the current full textual encoding) any template with a pointer
> template parameter)
>
> eg: extern int i; template<int *> void f1() { } int main() { f1<&i>(); }
Nice catch, we don't do anything clever here either.
Do you do equality on the computed DW_AT_location value to test whether one DW_TAG_template_value_parameter is equal to another (& so whether the template instantiation in one CU is the same type as in another CU)? Probably pretty reliable if you do the comparison with the result of DWARF expression evaluation.
This would
appear to be a special case of non-type template params that can
be arbitrary compile-time expressions; for non-pointer params we
provide the computed value of the compile-time expression, which
is arguably sufficient for cases like
constexpr int a = 1; constexpr int b = 2;
template <int> void f2() { }
void int_expr() { f2<a + b>(); }
but it would be nice to do something useful for
extern int j[4];
void ptr_expr() { f1<&j[a+b]>(); }
Conveniently this feature is not quite so general, this code would fail to compile (GCC says, for instance: "'& j[3]' is not a valid template argument of type 'int*' because 'j[3]' is not a variable", Clang just says the parameter is "invalid")
But passing only 'j' is valid. So in theory we could have some attribute that points to the variable declaration of 'j' in this case, which could allow structural equality testing using this DWARF. I'm not sure what we'd call that attribute - I guess we could repurpose the DW_AT_location attribute - if it's a DW_FORM_ref* encoding, it refers to another DIE whose location is used (this makes me a bit twitchy because it sounds like DW_OP_implicit_pointer which I think is overly narrow (by describing only an implicit pointer to another object, rather than to an arbitrary value) - but in this case at least for now, C++ doesn't support any generalization, it must point to a named variable so far as I understand), and if it's DW_FORM_exprloc it's what we do today already.
This might help address the difficult issue that GCC and Clang have split on - GCC, by not including the DW_AT_location ensures that enabling debug info doesn't affect codegen/linking. Clang ensures the value is debuggable, but at the cost of causing the value to be linked into the final binary even if the production code doesn't use it (due to the relocation in the DW_AT_location causing the linker to pull in the value). Hmm, actually I don't really know what the issue is there - clearly we use some kind of relocation for functions that doesn't have this problem, so maybe we're just not using the right kind of relocation for variables? Or there's a gap in relocation support/features that we should fill?
In any case, having DW_AT_location refer to the DW_TAG_variable then the DW_TAG_variable doesn't necessarily need to have a DW_AT_location (to avoid the linking issue) & if it has a linkage name, the consumer can look up the symbol itself to find it without a DW_AT_location.
(
Here's an example of the linkage issue:
$ cat > nttp.cpp
extern int i;
template<int*> void f1() { }
int main() { f1<&i>(); }
$ clang++-tot nttp.cpp -g
/usr/local/google/home/blaikie/install/bin/../lib/gcc/x86_64-pc-linux-gnu/10.0.0/../../../../x86_64-pc-linux-gnu/bin/ld: /tmp/nttp-e4e14a.o:(.debug_info+0x63): undefined reference to `i'
clang-13: error: linker command failed with exit code 1 (use -v to see invocation)
$ clang++-tot nttp.cpp
$ g++-tot nttp.cpp
$ g++-tot nttp.cpp -g
$
via llvm-dev
>> Oh, is there any consequence for deduplication in LTO? Isn’t that name-based?
> Should be OK - that's based on the fully mangled/linkage name of the type, which would be untouched by this.
I’ve recently been reminded that type-unit signatures are hashes of the name, not using the standard-recommended algorithm of hashing the content; I tried to work out which name is actually used, but it’s buried deeper than I am comfortable excavating. Can we make sure that hash is using either the name-with-parameters, or the linkage name, as the input string? We don’t want “foo<int>” and “foo<float>” using the same type-unit signature!
--paulr
David Blaikie via llvm-dev
Worth checking, but yeah, not a problem - we don't emit class linkage
names, so the only reason we carry the linkage name on types is for
ODR deduplicating during LTO linking, and also using it for type units
when those are enabled - the linkage name is stored in the
DICompositeType's "identifier" field - not something readily confused
with being guaranteed to be the linkage name nor used for
DW_AT_linkage_name, etc. Only used as a unique identifier. That won't
be touched.
As an aside: I do have another direction I'm interested in pursuing
that's related to linkage names, rather than the pretty names: We
could reduce the number of DW_AT_linkage_names we emit by
reconstituting linkage names in symbolizers instead (eg: if we see a
function called "f3" with a single "int" formal parameter and void
return type - we can reconstruct the linkage name for that function as
_Zf3iv or whatever it is).
On one particularly pathological case I'm looking at, the simplified
pretty template names is worth 43% reduction in the final dwp
.debug_str.dwo and a rough estimate on the linkage name (omitting
linkage names from most cases when Clang's building the IR - there are
certain kinds of template cases that are hard to reconstruct, but
others that are easy/do-able with our current DWARF) 52%, and combined
for 95% reduction in debug string size. (a less pathalogical case, one
of Google's largest binaries, it was 26%/56% for 82% total reduction)
David Blaikie via llvm-dev
A few other remaining pieces:
1) make the "operator" detection a bit better: https://github.com/llvm/llvm-project/blob/main/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp#L308-L311 - Don't think we can rely on there being a space after the word "operator" (because it might be "operator<" for instance) so maybe I just need a full regex/exhaustive list of valid identifier characters, so if it's "operator" followed by an identifier character, then it doesn't trigger this special case? Or the inverse - special case all the whitespace+first characters in operator overloads. That's probably a smaller set.
2) Integrate this into llvm-symbolizer so it rebuilds the names automatically
Then there's some lldb bugs to fix, etc.