On Tue, Dec 19, 2017 at 4:56 PM, Alexandre Oliva <aol...@redhat.com> wrote: > On Dec 14, 2017, Jason Merrill <ja...@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
