llvm dev - Jun 2018 - [lldb-dev] Adding DWARF5 accelerator table support to llvm

> On Jun 15, 2018, at 10:40 AM, <paul.robinson at sony.com>
<paul.robinson at sony.com> wrote:
> 
> 
> 
>> -----Original Message-----
>> From: Greg Clayton [mailto:clayborg at gmail.com <mailto:clayborg at
gmail.com>]
>> Sent: Friday, June 15, 2018 12:46 PM
>> To: Robinson, Paul
>> Cc: labath at google.com <mailto:labath at google.com>; dblaikie
at gmail.com <mailto:dblaikie at gmail.com>; aprantl at apple.com
<mailto:aprantl at apple.com>;
>> echristo at google.com <mailto:echristo at google.com>;
jdevlieghere at apple.com <mailto:jdevlieghere at apple.com>; llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>;
>> jan.kratochvil at redhat.com <mailto:jan.kratochvil at
redhat.com>; lldb-dev at lists.llvm.org <mailto:lldb-dev at
lists.llvm.org>; Jim Ingham
>> Subject: Re: [llvm-dev] [lldb-dev] Adding DWARF5 accelerator table
support
>> to llvm
>> 
>> 
>> 
>>> On Jun 15, 2018, at 9:23 AM, <paul.robinson at sony.com>
>> <paul.robinson at sony.com> wrote:
>>> 
>>>> From: Greg Clayton [mailto:clayborg at gmail.com]
>>>> 
>>>> ...
>>>> If a class has templated functions, they will only be in the
DWARF is a
>>>> specialization was created and used. If you have a class that
looks
>> like:
>>>> 
>>>> class A {
>>>>   A();
>>>>   <template T> void Foo(T t);
>>>> };
>>>> 
>>>> And then you have main.cpp that has a "double" and
"int"
>> specialization,
>>>> the class definition in DWARF looks like:
>>>> 
>>>> class A {
>>>>   A();
>>>>   <int> void Foo(int t);
>>>>   <double> void Foo(double t);
>>>> };
>>>> 
>>>> In another source file, say foo.cpp, if its use of class A
doesn't
>>>> specialize Foo, we have a class definition in DWARF that looks
like:
>>>> 
>>>> class A {
>>>>   A();
>>>> };
>>>> 
>>> 
>>> I think it would be more instructive to think about a case where
>>> main.cpp had Foo<int> and foo.cpp had Foo<double>.
>> 
>> Any difference is the problem here for clang ASTs, so it just matters
that
>> they are different. We make a CXXRecordDecl in the clang AST and if we
see
>> even one specialization, then we add the generic version to the
>> CXXRecordDecl and we are good to go. So the main.cpp had Foo<int>
and
>> foo.cpp had Foo<double> is actually fine. If I make a
CXXRecordDecl from
>> either of these then the two definitions match since the clang AST
>> CXXRecordDecl just needs to have the templated function declaration.
> 
> Got it, good to know.
> You don't actually care what instantiations exist? That seems odd.
The compiler will use the generic type and ask where the specialized version
lives. For the template method type, we will in the right stuff when we make the
function type, but the class itself just has the generic definition.
> 
>> 
>>> 
>>>> With the C++ ODR rules, we can pick any of the "class
A" definitions
>>>> whose qualified name matches ("::A") and has the same
decl file +
>>>> decl line. So when parsing "class A", the DWARF
parser will use the
>>>> accelerator tables to find all instances of "class
A", and it will
>>>> pick on and use it and this will become the one true definition
for
>>>> "class A".
>>> 
>>> FTR, the Sony debugger finds them all and then merges them into the
one
>>> true definition, because there's no promise that any one
description is
>>> a superset of the rest.
>> 
>> At the expense of parsing every definition for a class within each
file.
>>> 
>>>> This is because DWARF is only emitted for template functions
when
>>>> there is a specialization, that mean any definition of
"class A" might
>>>> or might not include any definition for "<template
T> A::Foo(T t);".
>>> 
>>> It's not just template functions, you know; the implicit
ctors/dtors
>>> might or might not be in any given description.  Those are also
only
>>> instantiated and described in CUs that require them.
>> 
>> We don't care about those as those are marked as DW_AT_artificial
and we
>> leave those out of the clang AST Context CXXRecordDecl because they are
>> implicit and the compiler can add those back in if needed since it
knows
>> if a class can have the constructors implicitly created.
>> 
>>> 
>>>> When we copy types between ASTs, everything is fine if the
classes
>>>> match (no copy needs to be made), but things go wrong if things
>>>> don't match and this causes expression errors.
>>>> 
>>>> Some ways to fix this:
>>>> 1 - anytime we need _any_ C++ class, we must dig up all
definitions
>>>> and check _all_ DW_TAG_subprogram DIEs within the class to
check if
>>>> any functions have templates and use the class with the most
>>>> specializations
>>> 
>>> This still fails in my "more instructive" case.  The
accelerator table
>>> does make it fast to find all the classes with the same name, and
you
>>> can then merge them.
>> 
>> That is a lot of DWARF parsing and logic to try and figure out what the
>> full set of DW_TAG_subprograms are.
>> 
>>> 
>>>> 2 - have DWARF actually emit the template function info all the
time
>>>> as a type T, not a specialization, so we always have the full
>> definition
>>> 
>>> Hm.  You mean a subroutine_type with template_parameter children
that
>>> don't have actual values?  That would give you a pattern, but
not tell
>>> you what/where definitions exist.  I don't see how that can
help?
>> 
>> Right now DWARF does only specializations, so DWARF would need to be
>> extended to be able to specify the template details without requiring a
>> specialization. Not easy for sure.
>> 
>>> 
>>>> 3 - have some accelerator table that explicitly points us to
all
>>>> specializations of class methods given a class name
>>> 
>>> So you want an accelerator to tell you what bits you need to pick
up
>>> from the various descriptions in order to construct the overall
>>> superset definition, which would be a little cheaper than parsing
>>> each entire class description (which you can already find through
>>> the existing accelerator tables).  I can see that.
>> 
>> Yes. This is the most appealing to me as well.
>> 
>>> 
>>>> Solution #1 would cause us to dig through all definitions of
all C++
>>>> classes all the time when parsing DWARF to check if definitions
of
>>>> the classes had template methods. And we would need to find the
class
>>>> that has the most template methods. This would cause us to
parse much
>>>> more of the debug info all of the time and cause increased
memory
>>>> consumption and performance regressions.
>>> 
>>> It would be cheap to put a flag on the class DIE that tells you
there
>>> are template methods to go look for.  Then you incur the cost only
>>> when necessary.  And the accelerator table makes it fast to find
the
>>> other class descriptions.
>> 
>> That is a fine solution. But we still run into the problem where we
don't
>> know if the DWARF knows about that flag. If we do a flag, it would be
nice
>> if it were mandatory on all classes to indicate support for the flag.
But
>> this would be a fine solution and not hard to implement.
> 
> So what you really want is not a flag, but a count, so you can tell when
> you've found all the different templates.  If the count is zero,
there's
> nothing to look for.  If the count is two, you look around at all the
> various definitions of the class until you find two different templates,
> then you stop.  If there's no count attribute, your producer
doesn't
> know you want this information and you do it the hard way.  Or, we've
> invented a way to describe the templates directly in the class.
> 
> How's that?
that would work fine.
> --paulr
> 
>>> 
>>>> Solution #2: not sure if DWARF even supports generic template
>>>> definitions where the template isn't specialized. And, how
would we
>>>> be able to tell DWARF that emits only specialized templates vs
one
>>>> that has generic definitions...
>>> 
>>> Right, DWARF today doesn't do that, although as I mentioned
earlier
>>> conjuring up a subroutine_type with template parameters would not
>>> appear to be any more helpful than a simple flag on the class.
>> 
>> Yeah, there would have to be new DWARF and a lot of DW_AT_specification
or
>> DW_AT_abstract_origin references involved...
>> 
>>> 
>>>> 
>>>> Solution #3 will require compiler changes.
>>> 
>>> Well, so does #2.
>> 
>> Indeed.
>> 
>>> 
>>>> So this is another vote to support the ability for a given
class
>>>> to be able to locate all of its functions, kind of like we need
>>>> for Objective C where the class definition doesn't contain
all of
>>>> methods, so we have the .apple_objc section that provides this
>>>> mapping for us. We would need something similar for C++.
>>>> 
>>>> So maybe a possible solution is some sort of section that can
>>>> specify all of the DIEs related to a class that are not
contained
>>>> in the class hierarchy itself. This would work for Objective C
>>>> and for C++.
>>>> 
>>>> Thoughts?
>>>> 
>>>> Greg
>>> 
>>> So, would it be helpful to have a flag on the class that tells you
>>> whether there are method instantiations to go look for?
>> 
>> That would be a great start to solution #1 if that is the way we choose
to
>> go.
>> 
>>> My
>>> impression is that templated class methods are unusual so it would
>>> save the performance cost a lot of the time right there.
>>> 
>>> I don't know enough about Obj-C to say whether it can know up
front
>>> there are potentially other methods elsewhere.
>> 
>> Another way to do the objective C solution would be to have an
attribute
>> on a DW_TAG_class_type that could specify a list of DIEs that are not
>> contained in the class definition that are required for the class. In
>> Objective C, the DW_TAG_subprogram for methods are outside of the class
>> itself. This would involve DWARF changes, but it could be an attribute
>> that specifies a section offset into a new section that contains a DIE
>> offset list.
>> 
>> So the Objective C case is still different enough from the C++ case
>> because in the C++ case all functions are still contained within the
>> DW_TAG_class_type DIE IIRC.
>> 
>> 
>> Greg
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180615/5b198169/attachment-0001.html>

gc> Solution #1 would cause us to dig through all definitions of all C++
gc> classes all the time when parsing DWARF to check if definitions of
gc> the classes had template methods. And we would need to find the class
gc> that has the most template methods. This would cause us to parse much
gc> more of the debug info all of the time and cause increased memory
gc> consumption and performance regressions.

pr> It would be cheap to put a flag on the class DIE that tells you there
pr> are template methods to go look for.  Then you incur the cost only
pr> when necessary.  And the accelerator table makes it fast to find the
pr> other class descriptions.

gc> That is a fine solution. But we still run into the problem where we
don't
gc> know if the DWARF knows about that flag. If we do a flag, it would be
nice
gc> if it were mandatory on all classes to indicate support for the flag. But
gc> this would be a fine solution and not hard to implement.

pr> So what you really want is not a flag, but a count, so you can tell when
pr> you've found all the different templates.  If the count is zero,
there's
pr> nothing to look for.  If the count is two, you look around at all the
pr> various definitions of the class until you find two different templates,
pr> then you stop.  If there's no count attribute, your producer
doesn't 
pr> know you want this information and you do it the hard way.  Or, we've
pr> invented a way to describe the templates directly in the class.
pr>
pr> How's that?

gc> that would work fine.

I filed PR37816 to track this idea.

The other ideas:

 - accelerator to point to the actual instantiations
 - emitting template definitions not just instantiations

would be trickier to define and harder to implement correctly.
I won't say they can't be done, but somebody else would have to do
the heavy lifting here, unless it turns out that our debugger folks
like the idea.

--paulr

How do you handle name lookup for nested classes? They have the same
problem (they don't appear in all definitions) - don't appear in all
descriptions of the outer/parent class. (in theory we could ensure there's
always at least a declaration of the nested class - but we don't even do
that if the nested class is unused)

Is it just the case that Clang doesn't mind you adding a new nested class
but it does mind you adding a new member function template? If so, maybe we
could change Clang to support adding new member function templates instead
of extending DWARF?

On Fri, Jun 15, 2018 at 11:59 AM <paul.robinson at sony.com> wrote:
> gc> Solution #1 would cause us to dig through all definitions of all C++
> gc> classes all the time when parsing DWARF to check if definitions of
> gc> the classes had template methods. And we would need to find the
class
> gc> that has the most template methods. This would cause us to parse
much
> gc> more of the debug info all of the time and cause increased memory
> gc> consumption and performance regressions.
>
> pr> It would be cheap to put a flag on the class DIE that tells you
there
> pr> are template methods to go look for.  Then you incur the cost only
> pr> when necessary.  And the accelerator table makes it fast to find the
> pr> other class descriptions.
>
> gc> That is a fine solution. But we still run into the problem where we
> don't
> gc> know if the DWARF knows about that flag. If we do a flag, it would
be
> nice
> gc> if it were mandatory on all classes to indicate support for the
flag.
> But
> gc> this would be a fine solution and not hard to implement.
>
> pr> So what you really want is not a flag, but a count, so you can tell
> when
> pr> you've found all the different templates.  If the count is zero,
> there's
> pr> nothing to look for.  If the count is two, you look around at all
the
> pr> various definitions of the class until you find two different
> templates,
> pr> then you stop.  If there's no count attribute, your producer
doesn't
> pr> know you want this information and you do it the hard way.  Or,
we've
> pr> invented a way to describe the templates directly in the class.
> pr>
> pr> How's that?
>
> gc> that would work fine.
>
> I filed PR37816 to track this idea.
>
> The other ideas:
>
>  - accelerator to point to the actual instantiations
>  - emitting template definitions not just instantiations
>
> would be trickier to define and harder to implement correctly.
> I won't say they can't be done, but somebody else would have to do
> the heavy lifting here, unless it turns out that our debugger folks
> like the idea.
>
> --paulr
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180615/d978dfe0/attachment.html>