Re: [PATCH] avoid recomputing PHI results after failure (PR 104203)
On 1/25/22 04:15, Richard Biener wrote: On Mon, Jan 24, 2022 at 11:55 PM Martin Sebor 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.
Re: [PATCH] avoid recomputing PHI results after failure (PR 104203)
On Mon, Jan 24, 2022 at 11:55 PM Martin Sebor 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.
[PATCH] avoid recomputing PHI results after failure (PR 104203)
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.
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.
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.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 *all_refs, tree arg, gimple *stmt,
int ostype, bool skip_null,
ssa_name_limit_t , pointer_query )
@@ -637,8 +637,16 @@ access_ref::merge_ref (vec *all_refs, tree arg, gimple *stmt,
access_ref aref;
if (!compute_objsize_r (arg, stmt, false, ostype, , snlim, )
|| 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 *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 *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 *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 *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);
+
+
