[COMMITTED] tree-optimization/115221 - Do not invoke SCEV if it will use a different range query.

[COMMITTED] tree-optimization/115221 - Do not invoke SCEV if it will use a different range query.

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 1053 bytes --]

The original patch causing the PR made  ranger's cache re-entrant to 
enable SCEV to use the current range_query when called from within ranger..

SCEV uses the currently active range query (via get_range_query()) for 
picking up values.  fold_using_range is the general purpose stmt folder 
many  components use, and it takes a range_query to use for folding.   
When propagating values in the cache, we need to ensure no new queries 
are invoked, and when the cache is propagating and calculating outgoing 
edges, it switches to a read only range_query which uses what it knows 
about global values to come up with best result using current state.

SCEV is unaware of what the caller is using for a range_query, so when 
attempting to fold a PHI node, it is re-invoking the current query 
during propagation which is undesired behavior.   This patch tells 
fold_using_range to not use SCEV if the range_query being used is not 
the same as the one SCEV is going to use.

Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.

Andrew

[-- Attachment #2: 115221.patch --]
[-- Type: text/x-patch, Size: 2775 bytes --]

From b814e390e7c87c14ce8d9cdea6c6cd127a4e6261 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 27 May 2024 11:00:57 -0400
Subject: [PATCH] Do not invoke SCEV if it will use a different range query.

SCEV always uses the current range_query object.
Ranger's cache uses a global value_query when propagating cache values to
avoid re-invoking ranger during simple vavhe propagations.
when folding a PHI value, SCEV can be invoked, and since it alwys uses
the current range_query object, when ranger is active this causes the
undesired re-invoking of ranger during cache propagation.

This patch checks to see if the fold_using_range specified range_query
object is the same as the one SCEV uses, and does not invoke SCEV if
they do not match.

	PR tree-optimization/115221
	gcc/
	* gimple-range-fold.cc (range_of_ssa_name_with_loop_info): Do
	not invoke SCEV is range_query's do not match.
	gcc/testsuite/
	* gcc.dg/pr115221.c: New.
---
 gcc/gimple-range-fold.cc        |  6 +++++-
 gcc/testsuite/gcc.dg/pr115221.c | 29 +++++++++++++++++++++++++++++
 2 files changed, 34 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr115221.c

diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index b3965b5ee50..98a4877ba18 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -1264,7 +1264,11 @@ fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name,
 						    fur_source &src)
 {
   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
-  if (!range_of_var_in_loop (r, name, l, phi, src.query ()))
+  // SCEV currently invokes get_range_query () for values.  If the query
+  // being passed in is not the same SCEV will use, do not invoke SCEV.
+  // This can be remove if/when SCEV uses a passed in range-query.
+  if (src.query () != get_range_query (cfun)
+      || !range_of_var_in_loop (r, name, l, phi, src.query ()))
     r.set_varying (TREE_TYPE (name));
 }
 
diff --git a/gcc/testsuite/gcc.dg/pr115221.c b/gcc/testsuite/gcc.dg/pr115221.c
new file mode 100644
index 00000000000..f139394e5c0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr115221.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+typedef unsigned uint32_t;
+int cde40_t;
+int offset;
+void aal_test_bit();
+uint32_t cde40_key_pol();
+long cde40_offset_check(uint32_t pos) {
+  cde40_key_pol();
+  if (cde40_t)
+    return (offset - 2) % (((pos == 3) ? 18 : 26)) != 0;
+  return 0;
+}
+void cde40_check_struct() {
+  uint32_t i, j, to_compare;
+  for (;; i++) {
+    cde40_offset_check(i);
+    if (to_compare == 0) {
+      if (i && cde40_key_pol())
+	;
+      to_compare = i;
+      continue;
+    }
+    j = to_compare;
+    for (; j < i; j++)
+      aal_test_bit();
+  }
+}
-- 
2.41.0

Re: [COMMITTED] tree-optimization/115221 - Do not invoke SCEV if it will use a different range query.

[Richard Biener]

On Tue, May 28, 2024 at 8:57 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> The original patch causing the PR made  ranger's cache re-entrant to
> enable SCEV to use the current range_query when called from within ranger..
>
> SCEV uses the currently active range query (via get_range_query()) for
> picking up values.  fold_using_range is the general purpose stmt folder
> many  components use, and it takes a range_query to use for folding.
> When propagating values in the cache, we need to ensure no new queries
> are invoked, and when the cache is propagating and calculating outgoing
> edges, it switches to a read only range_query which uses what it knows
> about global values to come up with best result using current state.
>
> SCEV is unaware of what the caller is using for a range_query, so when
> attempting to fold a PHI node, it is re-invoking the current query
> during propagation which is undesired behavior.   This patch tells
> fold_using_range to not use SCEV if the range_query being used is not
> the same as the one SCEV is going to use.
>
> Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.

Can we dump a hint to an active dump-file if this happens?  I suppose it's
an unwanted situation, like the pass not setting the active ranger?  Sth
like

   if (src.query () != get_range_query (cfun)
       && dump_file)
    fprintf (dump_file, "Using a range query different from the
installed one\n");

(or better wording).

Btw, could we install src.query () as the global range query around the
relevant recursion or is the place around where we'd need to do this
not so clear-cut?

Richard.

> Andrew

Re: [COMMITTED] tree-optimization/115221 - Do not invoke SCEV if it will use a different range query.

[Andrew MacLeod]

On 5/29/24 03:19, Richard Biener wrote:
> On Tue, May 28, 2024 at 8:57 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>> The original patch causing the PR made  ranger's cache re-entrant to
>> enable SCEV to use the current range_query when called from within ranger..
>>
>> SCEV uses the currently active range query (via get_range_query()) for
>> picking up values.  fold_using_range is the general purpose stmt folder
>> many  components use, and it takes a range_query to use for folding.
>> When propagating values in the cache, we need to ensure no new queries
>> are invoked, and when the cache is propagating and calculating outgoing
>> edges, it switches to a read only range_query which uses what it knows
>> about global values to come up with best result using current state.
>>
>> SCEV is unaware of what the caller is using for a range_query, so when
>> attempting to fold a PHI node, it is re-invoking the current query
>> during propagation which is undesired behavior.   This patch tells
>> fold_using_range to not use SCEV if the range_query being used is not
>> the same as the one SCEV is going to use.
>>
>> Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.
> Can we dump a hint to an active dump-file if this happens?  I suppose it's
> an unwanted situation, like the pass not setting the active ranger?  Sth
> like
>
>     if (src.query () != get_range_query (cfun)
>         && dump_file)
>      fprintf (dump_file, "Using a range query different from the
> installed one\n");
>
> (or better wording).

Sure, I can add that info to the dump.   Its unlikely to happen in 
places other than from ranger's cache, but you never know.



> Btw, could we install src.query () as the global range query around the
> relevant recursion or is the place around where we'd need to do this
> not so clear-cut?

The problem is actually the other way around.  The relevant recursion 
location *is* using the global query to try to  prevent problems.  SCEV 
is not honoring the use of an alternative to a non-active range_query

So. An active ranger is the current range_query.  Cache propagation of a 
ssa-name happens when you ask for a range further down in the CFG than 
has been processed yet.  It walks the CFG between the last dominator 
which has a range calculated, (if any), filling in the on-entry cache 
with values for the name based on outgoing edge calculations.  it 
specifically uses only a global query to fold and evaluate the value of 
that name on edges along the way to ensure it doesnt trigger recursion 
with the the active ranger.  When propagating the cache for an SSA_NAME, 
it should finish the propagation and return the final value before it 
goes off to do any other activity.    Without this patch, when the cache 
processes a PHI node via fold_using_ranges(), the generic fold routine 
checks with SCEV and SCEV always uses get_range_query instead of a 
specific operand source...  which invokes the active ranger again :-P

So this patch is mostly to make sure that of we are going to invoke 
SCEV, we only invoke it when we are calling it with the same query. 
which is 99.9% of the time.    If a pass is only using the global range 
query, it'll still work fine because get_range_query () returns the 
global range query, and thats what SCEV will be using.   If a pass uses 
enable_ranger()  and itself uses get_range_query(), then SCEV will also 
work as expected.

Andrew

Re: [COMMITTED] tree-optimization/115221 - Do not invoke SCEV if it will use a different range query.

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 1898 bytes --]

On 5/29/24 03:19, Richard Biener wrote:
> On Tue, May 28, 2024 at 8:57 PM Andrew MacLeod<amacleod@redhat.com>  wrote:
>> The original patch causing the PR made  ranger's cache re-entrant to
>> enable SCEV to use the current range_query when called from within ranger..
>>
>> SCEV uses the currently active range query (via get_range_query()) for
>> picking up values.  fold_using_range is the general purpose stmt folder
>> many  components use, and it takes a range_query to use for folding.
>> When propagating values in the cache, we need to ensure no new queries
>> are invoked, and when the cache is propagating and calculating outgoing
>> edges, it switches to a read only range_query which uses what it knows
>> about global values to come up with best result using current state.
>>
>> SCEV is unaware of what the caller is using for a range_query, so when
>> attempting to fold a PHI node, it is re-invoking the current query
>> during propagation which is undesired behavior.   This patch tells
>> fold_using_range to not use SCEV if the range_query being used is not
>> the same as the one SCEV is going to use.
>>
>> Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.
> Can we dump a hint to an active dump-file if this happens?  I suppose it's
> an unwanted situation, like the pass not setting the active ranger?  Sth
> like
>
>     if (src.query () != get_range_query (cfun)
>         && dump_file)
>      fprintf (dump_file, "Using a range query different from the
> installed one\n");
>
> (or better wording).
>
> Btw, could we install src.query () as the global range query around the
> relevant recursion or is the place around where we'd need to do this
> not so clear-cut?
>
As requested, this patch will issues a message in the listing if we fail 
to execute SCEV under normal usage.

Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed.

Andrew

[-- Attachment #2: 0001-scev-query-mismatch-message.patch --]
[-- Type: text/x-patch, Size: 1781 bytes --]

From 3c4b0b16bcbc731e65ab8b2cf58429e24756728a Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Thu, 30 May 2024 09:40:46 -0400
Subject: [PATCH 1/2] scev query mismatch message

Add a message to the listing if SCEV is not invoked because of a
range_query mismatch

	* gimple-range-fold.cc (range_of_ssa_name_with_loop_info): Issue a
	message if SCEV is not invoked due to a mismatch.
---
 gcc/gimple-range-fold.cc | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 98a4877ba18..6037c29ce11 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -1267,9 +1267,18 @@ fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name,
   // SCEV currently invokes get_range_query () for values.  If the query
   // being passed in is not the same SCEV will use, do not invoke SCEV.
   // This can be remove if/when SCEV uses a passed in range-query.
-  if (src.query () != get_range_query (cfun)
-      || !range_of_var_in_loop (r, name, l, phi, src.query ()))
-    r.set_varying (TREE_TYPE (name));
+  if (src.query () != get_range_query (cfun))
+    {
+      r.set_varying (TREE_TYPE (name));
+      // Report the msmatch if SRC is not the global query.  The cache
+      // uses a global query and would provide numerous false positives.
+      if (dump_file && (dump_flags & TDF_DETAILS)
+	  && src.query () != get_global_range_query ())
+	fprintf (dump_file,
+	  "fold_using-range:: SCEV not invoked due to mismatched queries\n");
+    }
+  else if (!range_of_var_in_loop (r, name, l, phi, src.query ()))
+      r.set_varying (TREE_TYPE (name));
 }
 
 // -----------------------------------------------------------------------
-- 
2.45.0