Message ID | d657f8bb-ee3f-ad73-1c54-84c2dc1f71aa@gmail.com |
---|---|
State | New |
Headers | show |
Series | avoid recomputing PHI results after failure (PR 104203) | expand |
On Mon, Jan 24, 2022 at 11:55 PM Martin Sebor <msebor@gmail.com> wrote: > > The pointer_query algorithm fails when it's unable to determine > the provenance of an pointer SSA variable. A failure prevents it > from making a record of the variable in the cache. Although this > doesn't happen often, one common cause of failures is PHI nodes: > e.g., because one of its arguments references the PHI itself, or > an undefined variable. Because a failed SSA_NAME isn't added to > the cache, the computation that led up to its failure is repeated > on each interesting use of the variable. This is computationally > wasteful and can cause excessive CPU usage in pathological cases > like in the test case in PR 104203. > > To avoid the problem the attached patch changes the logic for PHI > arguments and nodes to cache the most conservative result on such > a failure. It treats such a pointer as pointing into the middle > of an object of maximum size (same as under some other conditions). > > In addition, the patch also adds a new timer variable to > the warn_access pass to make these problems easier in the future > to track down. LGTM. > There are a number of other conditions under which point_query > fails. Even though the same approach could be used to replace > all those, I did not make the change in this patch. It's probably worth fixing them. Btw, I wonder whether caching fails as true fails would work as well though caching a conservative answer of course is fine. > Tested on x86_64-linux. > > Martin > > PS This solution relies on the pointer_query instance having caching > enabled. Two warning passes run without a cache: -Warray-bounds in > VRP and -Wrestrict in the wrestrict pass. I can look into enabling > it for GCC 12 if there's concern that they might be impacted. Please. There is IMHO no reason to not use the cache - for PHIs you can run into the same PHI arg def from multiple edges and thus you'll do unnecessary work even when you just do a single query for the toplevel API. Richard.
On 1/25/22 04:15, Richard Biener wrote: > On Mon, Jan 24, 2022 at 11:55 PM Martin Sebor <msebor@gmail.com> wrote: >> >> The pointer_query algorithm fails when it's unable to determine >> the provenance of an pointer SSA variable. A failure prevents it >> from making a record of the variable in the cache. Although this >> doesn't happen often, one common cause of failures is PHI nodes: >> e.g., because one of its arguments references the PHI itself, or >> an undefined variable. Because a failed SSA_NAME isn't added to >> the cache, the computation that led up to its failure is repeated >> on each interesting use of the variable. This is computationally >> wasteful and can cause excessive CPU usage in pathological cases >> like in the test case in PR 104203. >> >> To avoid the problem the attached patch changes the logic for PHI >> arguments and nodes to cache the most conservative result on such >> a failure. It treats such a pointer as pointing into the middle >> of an object of maximum size (same as under some other conditions). >> >> In addition, the patch also adds a new timer variable to >> the warn_access pass to make these problems easier in the future >> to track down. > > LGTM. Committed in r12-6869. > >> There are a number of other conditions under which point_query >> fails. Even though the same approach could be used to replace >> all those, I did not make the change in this patch. > > It's probably worth fixing them. Btw, I wonder whether caching > fails as true fails would work as well though caching a conservative > answer of course is fine. That's another approach: add a bitset and set a bit for each SSA variable for which the lookup failed (or didn't find anything interesting). It would save space in the cache. I didn't use it because it would require more churn in the code, but it's something to consider in the future (the cache itself could stand to be further split up, with pointer offsets in one and sizes in another). > >> Tested on x86_64-linux. >> >> Martin >> >> PS This solution relies on the pointer_query instance having caching >> enabled. Two warning passes run without a cache: -Warray-bounds in >> VRP and -Wrestrict in the wrestrict pass. I can look into enabling >> it for GCC 12 if there's concern that they might be impacted. > > Please. There is IMHO no reason to not use the cache - for PHIs > you can run into the same PHI arg def from multiple edges and thus > you'll do unnecessary work even when you just do a single query > for the toplevel API. Let me post a patch with that. Martin > > Richard.
PR tree-optimization/104203 - huge compile-time regression in pointer_query gcc/ChangeLog: PR tree-optimization/104203 * gimple-ssa-warn-access.cc (pass_data pass_data_waccess): Use TV_WARN_ACCESS. * pointer-query.cc (access_ref::merge_ref): Change return type. Convert failure to a conservative success. (access_ref::get_ref): Adjust to the change above. Short-circuit PHI evaluation after first failure turned into conservative success. * pointer-query.h (access_ref::merge_ref): Change return type. * timevar.def (TV_WARN_ACCESS): New timer variable. diff --git a/gcc/pointer-query.cc b/gcc/pointer-query.cc index a61ac8968f5..b092ef4fbdc 100644 --- a/gcc/pointer-query.cc +++ b/gcc/pointer-query.cc @@ -629,7 +629,7 @@ access_ref::phi () const ARG refers to the null pointer. Return true on success and false on failure. */ -bool +void access_ref::merge_ref (vec<access_ref> *all_refs, tree arg, gimple *stmt, int ostype, bool skip_null, ssa_name_limit_t &snlim, pointer_query &qry) @@ -637,8 +637,16 @@ access_ref::merge_ref (vec<access_ref> *all_refs, tree arg, gimple *stmt, access_ref aref; if (!compute_objsize_r (arg, stmt, false, ostype, &aref, snlim, &qry) || aref.sizrng[0] < 0) - /* This may be a PHI with all null pointer arguments. */ - return false; + { + /* This may be a PHI with all null pointer arguments. Handle it + conservatively by setting all properties to the most permissive + values. */ + base0 = false; + offrng[0] = offrng[1] = 0; + add_max_offset (); + set_max_size_range (); + return; + } if (all_refs) { @@ -675,13 +683,13 @@ access_ref::merge_ref (vec<access_ref> *all_refs, tree arg, gimple *stmt, if (arg_known_size) sizrng[0] = aref.sizrng[0]; - return true; + return; } /* Disregard null pointers in PHIs with two or more arguments. TODO: Handle this better! */ if (nullp) - return true; + return; const bool known_size = (sizrng[0] != 0 || sizrng[1] != maxobjsize); @@ -717,7 +725,7 @@ access_ref::merge_ref (vec<access_ref> *all_refs, tree arg, gimple *stmt, sizrng[0] = minsize; parmarray = merged_parmarray; - return true; + return; } /* Determine and return the largest object to which *THIS refers. If @@ -755,14 +763,12 @@ access_ref::get_ref (vec<access_ref> *all_refs, access_ref aref; tree arg1 = gimple_assign_rhs1 (def_stmt); - if (!aref.merge_ref (all_refs, arg1, def_stmt, ostype, false, - *psnlim, *qry)) - return NULL_TREE; + aref.merge_ref (all_refs, arg1, def_stmt, ostype, false, + *psnlim, *qry); tree arg2 = gimple_assign_rhs2 (def_stmt); - if (!aref.merge_ref (all_refs, arg2, def_stmt, ostype, false, - *psnlim, *qry)) - return NULL_TREE; + aref.merge_ref (all_refs, arg2, def_stmt, ostype, false, + *psnlim, *qry); if (pref && pref != this) { @@ -801,16 +807,24 @@ access_ref::get_ref (vec<access_ref> *all_refs, phi_ref = *pref; } + const offset_int maxobjsize = wi::to_offset (max_object_size ()); const unsigned nargs = gimple_phi_num_args (phi_stmt); for (unsigned i = 0; i < nargs; ++i) { access_ref phi_arg_ref; bool skip_null = i || i + 1 < nargs; tree arg = gimple_phi_arg_def (phi_stmt, i); - if (!phi_ref.merge_ref (all_refs, arg, phi_stmt, ostype, skip_null, - *psnlim, *qry)) - return NULL_TREE; + phi_ref.merge_ref (all_refs, arg, phi_stmt, ostype, skip_null, + *psnlim, *qry); + + if (!phi_ref.base0 + && phi_ref.sizrng[0] == 0 + && phi_ref.sizrng[1] >= maxobjsize) + /* When an argument results in the most permissive result, + the remaining arguments cannot constrain it. Short-circuit + the evaluation. */ + break; } if (phi_ref.sizrng[0] < 0) /* A helper of compute_objsize_r() to determine the size from an assignment diff --git a/gcc/pointer-query.h b/gcc/pointer-query.h index 7dc965bd150..dbdcd593b79 100644 --- a/gcc/pointer-query.h +++ b/gcc/pointer-query.h @@ -67,7 +67,7 @@ struct access_ref gphi *phi () const; /* Merge the result for a pointer with *THIS. */ - bool merge_ref (vec<access_ref> *all_refs, tree, gimple *, int, bool, + void merge_ref (vec<access_ref> *all_refs, tree, gimple *, int, bool, ssa_name_limit_t &, pointer_query &); /* Return the object to which REF refers. */ diff --git a/gcc/timevar.def b/gcc/timevar.def index c239e8e4592..2dae5e1c760 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -307,6 +307,7 @@ DEFTIMEVAR (TV_TREE_UBSAN , "tree ubsan") DEFTIMEVAR (TV_INITIALIZE_RTL , "initialize rtl") DEFTIMEVAR (TV_GIMPLE_LADDRESS , "address lowering") DEFTIMEVAR (TV_TREE_LOOP_IFCVT , "tree loop if-conversion") +DEFTIMEVAR (TV_WARN_ACCESS , "access analysis") /* Everything else in rest_of_compilation not included above. */ DEFTIMEVAR (TV_EARLY_LOCAL , "early local passes") diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc index 8bc33eeb6fa..afcf0f71bec 100644 --- a/gcc/gimple-ssa-warn-access.cc +++ b/gcc/gimple-ssa-warn-access.cc @@ -2053,7 +2053,7 @@ const pass_data pass_data_waccess = { GIMPLE_PASS, "waccess", OPTGROUP_NONE, - TV_NONE, + TV_WARN_ACCESS, /* timer variable */ PROP_cfg, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */