diff mbox series

avoid recomputing PHI results after failure (PR 104203)

Message ID d657f8bb-ee3f-ad73-1c54-84c2dc1f71aa@gmail.com
State New
Headers
Series avoid recomputing PHI results after failure (PR 104203) |

Commit Message

Martin Sebor Jan. 24, 2022, 10:55 p.m. UTC 
  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.

Comments

Richard Biener Jan. 25, 2022, 11:15 a.m. UTC | #1 
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.
Martin Sebor Jan. 25, 2022, 9:26 p.m. UTC | #2 
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.
diff mbox series

Patch

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  */