[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228 Andrew Pinski changed: What|Removed |Added Target Milestone|--- |12.0
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228 Richard Biener changed: What|Removed |Added Resolution|--- |FIXED Known to work||12.0 Assignee|unassigned at gcc dot gnu.org |rguenth at gcc dot gnu.org Status|UNCONFIRMED |RESOLVED --- Comment #8 from Richard Biener --- Fixed for GCC 12.
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228 --- Comment #7 from CVS Commits --- The master branch has been updated by Richard Biener : https://gcc.gnu.org/g:716a5836928ee6d8fb884d9a2fbc1b1386ec8994 commit r12-3421-g716a5836928ee6d8fb884d9a2fbc1b1386ec8994 Author: Richard Biener Date: Wed Sep 8 10:39:27 2021 +0200 c++/102228 - make lookup_anon_field O(1) For the testcase in PR101555 lookup_anon_field takes the majority of parsing time followed by get_class_binding_direct/fields_linear_search which is PR83309. The situation with anon aggregates is particularly dire when we need to build accesses to their members and the anon aggregates are nested. There for each such access we recursively build sub-accesses to the anon aggregate FIELD_DECLs bottom-up, DFS searching for them. That's inefficient since as I believe there's a 1:1 relationship between anon aggregate types and the FIELD_DECL used to place them. The patch below does away with the search in lookup_anon_field and instead records the single FIELD_DECL in the anon aggregate types lang-specific data, re-using the RTTI typeinfo_var field. That speeds up the compile of the testcase with -fsyntax-only from about 4.5s to slightly less than 1s. I tried to poke holes into the 1:1 relationship idea with my C++ knowledge but failed (which might not say much). It also leaves a hole for the case when the C++ FE itself duplicates such type and places it at a semantically different position. I've tried to poke holes into it with the duplication mechanism I understand (templates) but failed. 2021-09-08 Richard Biener PR c++/102228 gcc/cp/ * cp-tree.h (ANON_AGGR_TYPE_FIELD): New define. * decl.c (fixup_anonymous_aggr): Wipe RTTI info put in place on invalid code. * decl2.c (reset_type_linkage): Guard CLASSTYPE_TYPEINFO_VAR access. * module.cc (trees_in::read_class_def): Likewise. Reconstruct ANON_AGGR_TYPE_FIELD. * semantics.c (finish_member_declaration): Populate ANON_AGGR_TYPE_FIELD for anon aggregate typed members. * typeck.c (lookup_anon_field): Remove DFS search and return ANON_AGGR_TYPE_FIELD directly.
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228 --- Comment #6 from Richard Biener --- I do have a functional patch which improves the -fsyntax-only compile-time for the PR101555 testcase from 14s to 2s. After lookup_anon_field is gone PR83309 pops up of course: Samples: 6K of event 'cycles', Event count (approx.): 6523483993 Overhead Samples Command Shared Object Symbol 20.96% 1375 cc1plus cc1plus [.] get_class_binding_direct 11.83% 776 cc1plus cc1plus [.] fields_linear_search 7.63% 501 cc1plus cc1plus [.] cp_fold I wonder if we should delay duplicate decl diagnostics until after the class is completed so we have the CLASSTYPE_MEMBER_VEC populated.
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228
--- Comment #5 from Richard Biener ---
(In reply to Richard Biener from comment #4)
> I think there must be also a 1:1 correspondence to anon type and its single
> use FIELD_DECL thus building a back-chain via DECL_CONTEXT and a new
> ANON_AGGR_TYPE_FIELD should be possible.
>
> At least I failed to do sth like
>
> typedef struct { int i; } T;
> struct X {
> T;
> };
> struct Y {
> T;
> };
>
> aka use the same aggregate type anonymously from two contexts.
I (fool) proofed this with
diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index 8b78e89ce3a..16156e428be 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -136,6 +136,7 @@ struct GTY(()) deferred_access {
/* Data for deferred access checking. */
static GTY(()) vec *deferred_access_stack;
static GTY(()) unsigned deferred_access_no_check;
+static GTY(()) hash_map *anon_aggr_field;
/* Save the current deferred access states and start deferred
access checking iff DEFER_P is true. */
@@ -3489,6 +3490,15 @@ finish_member_declaration (tree decl)
if (TREE_CODE (decl) != CONST_DECL)
DECL_CONTEXT (decl) = current_class_type;
+ if (TREE_CODE (decl) == FIELD_DECL
+ && ANON_AGGR_TYPE_P (TREE_TYPE (decl)))
+{
+ if (!anon_aggr_field)
+ anon_aggr_field = hash_map::create_ggc ();
+ if (anon_aggr_field->put (TREE_TYPE (decl), decl))
+ gcc_unreachable ();
+}
+
if (TREE_CODE (decl) == USING_DECL)
/* For now, ignore class-scope USING_DECLS, so that debugging
backends do not see them. */
if you think the 1:1 relationship is sound then I can try finding an
unused field in lang_type to record the FIELD_DECL used for an
ANON_AGGR_TYPE_P. I guess any of the method/inheritance related
members could be re-purposed (typeinfo_var for example, accesses are
in suitably special places that shouldn't show up for ANON_AGGR_TYPE_P)
I did wonder if we'll have different FIELD_DECLs for as-base or other
weird record variants that somehow get automatically generated as
copies from the same type (and where the FIELD_DECL would be at different
offset). But at least test coverage showed up
nothing... and I don't know enough C++ to think of how to provoke it
to break.
So, mine if proceeding with adding a ANON_AGGR_TYPE_FIELD mapping to
lang_type->typeinfo_var and setting it in finish_member_declaration
plus ditching lookup_anon_field is OK.
Jason?
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228
--- Comment #4 from Richard Biener ---
I think there must be also a 1:1 correspondence to anon type and its single use
FIELD_DECL thus building a back-chain via DECL_CONTEXT and a new
ANON_AGGR_TYPE_FIELD should be possible.
At least I failed to do sth like
typedef struct { int i; } T;
struct X {
T;
};
struct Y {
T;
};
aka use the same aggregate type anonymously from two contexts.
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228 --- Comment #3 from Richard Biener --- The odd thing is of course that name lookup must already have found MEMBER and thus visited the path to it. It would just need to record that :/
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228
--- Comment #2 from Richard Biener ---
For the PR101555 testcase if you can trust callgrind we get 4000 times
into build_class_member_access_expr and recurse 3000 times which means
on average we have two nested anon aggregates. But then the
lookup_anon_field calls end up recursing 49000 times on the toplevel
and nearly 3 million times from recursive invocations.
So something is clearly at odds here and maybe the issue in the description
is not the one at hand for the testcase but it should be possible to
write a testcase with a deep nesting of anon aggregates running into the
issue in the description.
The following illustrates it:
struct X {
struct {
struct {
struct {
struct {
struct {
struct {
struct {
int i;
};
};
};
};
};
};
};
};
int foo (struct X *p)
{
return p->i;
}
The testcase in PR101555 has
class Vara___024root {
...
struct {
struct {
... 60 members ...
};
struct {
... 60 members ...
};
... repeat 100 times ...
};
... repeat 100 times ...
};
so two levels deep but at each depth 100 anon aggregates :/ (most of
the actual members are never used)
[Bug c++/102228] lookup_anon_field is quadratic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102228 Richard Biener changed: What|Removed |Added CC||jason at gcc dot gnu.org Keywords||compile-time-hog --- Comment #1 from Richard Biener --- The only other caller of lookup_anon_field is cplus_expand_constant for the PTRMEM_CST case which looks like it wouldn't handle nested anon aggregates at all (maybe anon aggregates can only be at zero offset?). If it weren't for this use some brute-force refactoring should be possible without knowing as to what extent all the bells and whistles from build_class_member_access_expr are necessary for the anon aggregate COMPONENT_REFs.
