llvm dev - Jun 2018 - [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.
> 
>> 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.
> 
>> 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

> -----Original Message-----
> From: Greg Clayton [mailto:clayborg at gmail.com]
> Sent: Friday, June 15, 2018 12:46 PM
> To: Robinson, Paul
> Cc: labath at google.com; dblaikie at gmail.com; aprantl at apple.com;
> echristo at google.com; jdevlieghere at apple.com; llvm-dev at
lists.llvm.org;
> jan.kratochvil at redhat.com; 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.
> 
> >
> >> 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?
--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

> 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>