Re: [PR59319] output friends in debug info

[Jason Merrill <jason at redhat dot com>]

On Tue, Dec 19, 2017 at 4:56 PM, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Dec 14, 2017, Jason Merrill <jason@redhat.com> wrote:
>
>> On 12/07/2017 04:04 PM, Alexandre Oliva wrote:
>
>>> For other templates, I ended up writing code to look for
>>> specializations in the hashtables of decl or type specializations.
>>> That's not exactly efficient, but it gets the job done.
>
>> How inefficient is it, exactly?
>
> Err...  O(n)? :-)

For a single friend, but more generally O(M*N) where M is the number
of template friends (including instantiations of class templates
containing template friends) and N is the total number of
instantiations of all (decl) templates.  Right?

> For the cases we go down this path, we iterate over the hashtable of
> specializations of types or functions, testing whether each one fits the
> friend template declaration with is_specialization_of_friend().  The
> tests there are not particularly expensive, but I suppose they could add
> up given tons of template instantiations.  I assume the test is already
> made efficient, but perhaps a different version could be tuned to this
> use, or something, or we could try to come up with a completely
> different algorithm that, I don't know, grouped instantiations and
> friend declarations by identifiers first, or somesuch.
>
> Now, perhaps it is possible to locate instantiations more immediately in
> cases I haven't been able to figure out.  It's not like I know my way
> around the internal representation of templates ;-)  If you have any
> suggestions and directions, I'm all ears.

No, currently instantiations of most templates are only hashed, not
enumerated.  Which was why...

>> I wonder about changing register_specialization to fill out
>> DECL_TEMPLATE_INSTANTIATIONS for more templates (even more than you
>> already do).

...although this would only work for template friends that befriend a
specific template; for friend declarations that befriend a member of a
class template, we'd still need to do the enumeration the way you do
it now, since those declarations also befriend matching members of an
explicit specialization of the class template.

>>> +  /* At DETAIL level 0, returns non-NULL if the named class TYPE has
>>> +     any friends, NULL otherwise.  At higher detail levels, return a
>>> +     tree list with the friends of the named class type.  Each
>>> +     TREE_VALUE contains one friend type or function decl.  For
>>> +     non-template friends, TREE_PURPOSE is NULL.  For template friend
>>> +     declarations, the returned entries depend on the DETAIL level.
>>> +     At level 1, and only at level 1, an entry with NULL TREE_VALUE
>>> +     and non-NULL TREE_PURPOSE will START the returned list to
>>> +     indicate the named class TYPE has at least one template friend.
>>> +     At level 2, each template friend will be in an entry with NULL
>>> +     TREE_VALUE, and with the TEMPLATE_DECL in TREE_PURPOSE.  At level
>>> +     3, instead of a NULL TREE_VALUE, we add one entry for each
>>> +     instantiation or specialization of the template that fits the
>>> +     template friend declaration, as long as there is at least one
>>> +     instantiation or specialization; if there isn't any, an entry
>>> +     with NULL TREE_VALUE is created.  A negative detail level will
>>> +     omit non-template friends from the returned list.  */
>
>> The calls I see only seem to use details 0 and 3, while I would expect
>> level 3 to only be used with -g3.  What is the purpose of the negative
>> level?
>
> I designed the API so as to give dwarf2out some flexibility in getting
> to the information in different ways, allowing queries that wouldn't
> waste much memory building lists just to throw them away right away.  My
> goal was always to list all befriended instantiations at -g, but e.g. if
> we've already got the data for non-template friends in an earlier query,
> I wanted to avoid duplicating them in a subsequent query for template
> friends.  That's where the negative levels would come handy.  The code
> could be structured so as to query at level 1 at first, emit the
> non-template friend attributes, and then issue a level 2 or 3 query to
> deal with template ones only if the special entry is returned in the
> first query.  But that subsequent query would duplicate template
> entries, whereas with a negative level they would be left out, saving
> the memory the list would spend on them.
>
> Now, regardless of what I set out to do, I figured we might want to vary
> the amount of detail put in debug info, and that there might be
> discussion about it, so the detail levels would help in that regard too.
> I envisioned command line options to control some of that, but I didn't
> go down this path further before discussion as to what's desirable,
> costly, etc.

My inclination is not to enumerate specializations of friend templates
at -g1; it seems expensive both in compile time and debug info size.

Jason