Message ID | nycvar.YFH.7.76.2001140929340.5566@zhemvz.fhfr.qr |
---|---|
State | New |
Headers | show |
Series | [1/2] PR middle-end/93246 - missing alias subsets | expand |
On Tue, 14 Jan 2020, Richard Biener wrote: > When an alias-set is an already existing subset there is no need > to re-record its children as childs of the parent. > > I noticed this when doing 1/2 as trivial opportunity to squeeze > back some performance for the non-caching recursion I added. The > whole thing is still quadratic in the depth of the structure, of course. > > Bootstrapped and tested on x86_64-unknown-linux-gnu. > > Since I'm curious I'll test a variant which checks the children > are actually recorded before pushing this ... (OK, maybe I shouldn't > do this...) So I did it. It works but for FAIL: gnat.dg/interface2.adb 3 blank line(s) in output FAIL: gnat.dg/interface2.adb (test for excess errors) UNRESOLVED: gnat.dg/interface2.adb compilation failed to produce executable FAIL: gnat.dg/predicate2_main.adb 3 blank line(s) in output FAIL: gnat.dg/predicate2_main.adb (test for excess errors) which ICE with the adjusted patch below. Ada calls record_component_aliases itself and eventually too early when some types are not yet complete? Which would also mean that subsets could be failed to recorded properly. So I'm still inclined to go with the original non-checking patch unless Eric tells me I'm completely wrong and there isn't a latent issue in the Ada frontend. Thanks, Richard. diff --git a/gcc/alias.c b/gcc/alias.c index 336af4e52a7..0eae5386444 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -1164,10 +1164,15 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) superset_entry->has_zero_child = 1; else { - subset_entry = get_alias_set_entry (subset); if (!superset_entry->children) superset_entry->children = hash_map<alias_set_hash, int>::create_ggc (64); + + /* Enter the SUBSET itself as a child of the SUPERSET. If it was + already there we're done. */ + bool present = superset_entry->children->put (subset, 0); + + subset_entry = get_alias_set_entry (subset); /* If there is an entry for the subset, enter all of its children (if they are not already present) as children of the SUPERSET. */ if (subset_entry) @@ -1182,12 +1187,12 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) hash_map<alias_set_hash, int>::iterator iter = subset_entry->children->begin (); for (; iter != subset_entry->children->end (); ++iter) - superset_entry->children->put ((*iter).first, (*iter).second); + { + bool cpresent = superset_entry->children->put ((*iter).first, (*iter).second); + gcc_assert (!present || cpresent); + } } } - - /* Enter the SUBSET itself as a child of the SUPERSET. */ - superset_entry->children->put (subset, 0); } }
On Tue, 14 Jan 2020, Richard Biener wrote: > On Tue, 14 Jan 2020, Richard Biener wrote: > > > When an alias-set is an already existing subset there is no need > > to re-record its children as childs of the parent. > > > > I noticed this when doing 1/2 as trivial opportunity to squeeze > > back some performance for the non-caching recursion I added. The > > whole thing is still quadratic in the depth of the structure, of course. > > > > Bootstrapped and tested on x86_64-unknown-linux-gnu. > > > > Since I'm curious I'll test a variant which checks the children > > are actually recorded before pushing this ... (OK, maybe I shouldn't > > do this...) > > So I did it. It works but for > > FAIL: gnat.dg/interface2.adb 3 blank line(s) in output > FAIL: gnat.dg/interface2.adb (test for excess errors) > UNRESOLVED: gnat.dg/interface2.adb compilation failed to produce > executable > FAIL: gnat.dg/predicate2_main.adb 3 blank line(s) in output > FAIL: gnat.dg/predicate2_main.adb (test for excess errors) > > which ICE with the adjusted patch below. Ada calls > record_component_aliases itself and eventually too early when > some types are not yet complete? Which would also mean that > subsets could be failed to recorded properly. > > So I'm still inclined to go with the original non-checking patch > unless Eric tells me I'm completely wrong and there isn't a > latent issue in the Ada frontend. Btw, all the dance the Ada FE performs in relate_alias_sets isn't going to work with LTO unless it is no longer necessary anyways. Oh, and we miss libbacktrace support for GNAT bug boxes, for the above I'd like to know whether its from record_component_aliases calls or calls of record_alias_subset. Richard. > diff --git a/gcc/alias.c b/gcc/alias.c > index 336af4e52a7..0eae5386444 100644 > --- a/gcc/alias.c > +++ b/gcc/alias.c > @@ -1164,10 +1164,15 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) > superset_entry->has_zero_child = 1; > else > { > - subset_entry = get_alias_set_entry (subset); > if (!superset_entry->children) > superset_entry->children > = hash_map<alias_set_hash, int>::create_ggc (64); > + > + /* Enter the SUBSET itself as a child of the SUPERSET. If it was > + already there we're done. */ > + bool present = superset_entry->children->put (subset, 0); > + > + subset_entry = get_alias_set_entry (subset); > /* If there is an entry for the subset, enter all of its children > (if they are not already present) as children of the SUPERSET. */ > if (subset_entry) > @@ -1182,12 +1187,12 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) > hash_map<alias_set_hash, int>::iterator iter > = subset_entry->children->begin (); > for (; iter != subset_entry->children->end (); ++iter) > - superset_entry->children->put ((*iter).first, (*iter).second); > + { > + bool cpresent = superset_entry->children->put ((*iter).first, (*iter).second); > + gcc_assert (!present || cpresent); > + } > } > } > - > - /* Enter the SUBSET itself as a child of the SUPERSET. */ > - superset_entry->children->put (subset, 0); > } > } > >
On Tue, 14 Jan 2020, Richard Biener wrote: > On Tue, 14 Jan 2020, Richard Biener wrote: > > > On Tue, 14 Jan 2020, Richard Biener wrote: > > > > > When an alias-set is an already existing subset there is no need > > > to re-record its children as childs of the parent. > > > > > > I noticed this when doing 1/2 as trivial opportunity to squeeze > > > back some performance for the non-caching recursion I added. The > > > whole thing is still quadratic in the depth of the structure, of course. > > > > > > Bootstrapped and tested on x86_64-unknown-linux-gnu. > > > > > > Since I'm curious I'll test a variant which checks the children > > > are actually recorded before pushing this ... (OK, maybe I shouldn't > > > do this...) > > > > So I did it. It works but for > > > > FAIL: gnat.dg/interface2.adb 3 blank line(s) in output > > FAIL: gnat.dg/interface2.adb (test for excess errors) > > UNRESOLVED: gnat.dg/interface2.adb compilation failed to produce > > executable > > FAIL: gnat.dg/predicate2_main.adb 3 blank line(s) in output > > FAIL: gnat.dg/predicate2_main.adb (test for excess errors) > > > > which ICE with the adjusted patch below. Ada calls > > record_component_aliases itself and eventually too early when > > some types are not yet complete? Which would also mean that > > subsets could be failed to recorded properly. > > > > So I'm still inclined to go with the original non-checking patch > > unless Eric tells me I'm completely wrong and there isn't a > > latent issue in the Ada frontend. > > Btw, all the dance the Ada FE performs in relate_alias_sets isn't > going to work with LTO unless it is no longer necessary anyways. > > Oh, and we miss libbacktrace support for GNAT bug boxes, for the > above I'd like to know whether its from record_component_aliases > calls or calls of record_alias_subset. And if I delay checking until we actually look for subsets (alias_sets_conflict or alias_set_subset_of), verifying we collected all subsets that fails when building the RTS, for example when building g-awk.adb. The patch below does that verification, it doesn't actually look for a case where the final answer of those predicates is wrong though. It seems that Ada is the only frontend affected by this "bug" so I pushed the original change. Richard. diff --git a/gcc/alias.c b/gcc/alias.c index 9629b5a9f48..ffb2af9b34f 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -154,7 +154,7 @@ static int base_alias_check (rtx, rtx, rtx, rtx, machine_mode, machine_mode); static rtx find_base_value (rtx); static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx); -static alias_set_entry *get_alias_set_entry (alias_set_type); +static alias_set_entry *get_alias_set_entry (alias_set_type, bool = false); static tree decl_for_component_ref (tree); static int write_dependence_p (const_rtx, const_rtx, machine_mode, rtx, @@ -372,9 +372,37 @@ rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p) such an entry, or NULL otherwise. */ static inline alias_set_entry * -get_alias_set_entry (alias_set_type alias_set) +get_alias_set_entry (alias_set_type alias_set, bool check) { - return (*alias_sets)[alias_set]; + alias_set_entry *e = (*alias_sets)[alias_set]; + if (check && e && e->children) + { + bitmap_obstack_initialize (NULL); + auto_vec<alias_set_type> worklist; + auto_bitmap visited; + hash_map<alias_set_hash, int>::iterator iter + = e->children->begin (); + for (; iter != e->children->end (); ++iter) + worklist.safe_push ((*iter).first); + while (!worklist.is_empty ()) + { + alias_set_type subset = worklist.pop (); + if (!bitmap_set_bit (visited, subset)) + continue; + alias_set_entry *se = (*alias_sets)[subset]; + if (se && se->children) + for (iter = se->children->begin (); + iter != se->children->end (); ++iter) + { + if ((*iter).first == alias_set) + continue; + gcc_assert (e->children->get ((*iter).first) != NULL); + worklist.safe_push ((*iter).first); + } + } + bitmap_obstack_release (NULL); + } + return e; } /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that @@ -404,7 +432,7 @@ alias_set_subset_of (alias_set_type set1, alias_set_type set2) return true; /* Check if set1 is a subset of set2. */ - ase2 = get_alias_set_entry (set2); + ase2 = get_alias_set_entry (set2, true); if (ase2 != 0 && (ase2->has_zero_child || (ase2->children && ase2->children->get (set1)))) @@ -433,7 +461,7 @@ alias_set_subset_of (alias_set_type set1, alias_set_type set2) get_alias_set for more details. */ if (ase2 && ase2->has_pointer) { - alias_set_entry *ase1 = get_alias_set_entry (set1); + alias_set_entry *ase1 = get_alias_set_entry (set1, true); if (ase1 && ase1->is_pointer) { @@ -465,7 +493,7 @@ alias_sets_conflict_p (alias_set_type set1, alias_set_type set2) return 1; /* See if the first alias set is a subset of the second. */ - ase1 = get_alias_set_entry (set1); + ase1 = get_alias_set_entry (set1, true); if (ase1 != 0 && ase1->children && ase1->children->get (set2)) { @@ -474,7 +502,7 @@ alias_sets_conflict_p (alias_set_type set1, alias_set_type set2) } /* Now do the same, but with the alias sets reversed. */ - ase2 = get_alias_set_entry (set2); + ase2 = get_alias_set_entry (set2, true); if (ase2 != 0 && ase2->children && ase2->children->get (set1)) { @@ -1164,10 +1192,16 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) superset_entry->has_zero_child = 1; else { - subset_entry = get_alias_set_entry (subset); if (!superset_entry->children) superset_entry->children = hash_map<alias_set_hash, int>::create_ggc (64); + + /* Enter the SUBSET itself as a child of the SUPERSET. If it was + already there we're done. */ + if (superset_entry->children->put (subset, 0)) + return; + + subset_entry = get_alias_set_entry (subset); /* If there is an entry for the subset, enter all of its children (if they are not already present) as children of the SUPERSET. */ if (subset_entry) @@ -1182,12 +1216,13 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) hash_map<alias_set_hash, int>::iterator iter = subset_entry->children->begin (); for (; iter != subset_entry->children->end (); ++iter) - superset_entry->children->put ((*iter).first, (*iter).second); + /* It is possible in complex type situations for both sets + to be the same, in which case we can ignore this + operation. */ + if ((*iter).first != superset) + superset_entry->children->put ((*iter).first, (*iter).second); } } - - /* Enter the SUBSET itself as a child of the SUPERSET. */ - superset_entry->children->put (subset, 0); } }
diff --git a/gcc/alias.c b/gcc/alias.c index 9629b5a9f48..3794f9b6a9e 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -1164,10 +1164,16 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) superset_entry->has_zero_child = 1; else { - subset_entry = get_alias_set_entry (subset); if (!superset_entry->children) superset_entry->children = hash_map<alias_set_hash, int>::create_ggc (64); + + /* Enter the SUBSET itself as a child of the SUPERSET. If it was + already there we're done. */ + if (superset_entry->children->put (subset, 0)) + return; + + subset_entry = get_alias_set_entry (subset); /* If there is an entry for the subset, enter all of its children (if they are not already present) as children of the SUPERSET. */ if (subset_entry) @@ -1185,9 +1191,6 @@ record_alias_subset (alias_set_type superset, alias_set_type subset) superset_entry->children->put ((*iter).first, (*iter).second); } } - - /* Enter the SUBSET itself as a child of the SUPERSET. */ - superset_entry->children->put (subset, 0); } }