[COMMITTED] PR tree-optimization/106114 - Don't use gori dependencies to optimize.

[COMMITTED] PR tree-optimization/106114 - Don't use gori dependencies to optimize.

[Andrew MacLeod]

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

The routine which tried to fold and's and or's using relations was using 
the dependency cache as a shortcut to determine if there were 2 ssa 
names on the feeding expressions, and assuming that was correct.

ie

   _16 = a.0_1 < -117;
   _17 = a.0_1 >= -83;
   _18 = _16 | _17;

the dependency cache indicates that a.0_1 is "ssa1" dependency for _16 
and also for _17.  we dont have to scan the statement, so temporal out 
of date info is very quick.

Its also not meant to reflect that actual statement.. ie, it can get out 
of date.  Not is a way that makes anything incorrect, but in a way that 
may possibly result in a  either a missed opportunity or slightly more 
work when statements are being rewritten on the fly..  ie  DOM rewrites 
that to:

   _16 = a.1_15 < -117;
   _17 = a.1_15 >= -83;
   _18 = _16 | _17;

When fold_using_range is later invoked, a.1_15 is added a dependency to 
_16 and _17,  not attempting to understand that its a replacement, we 
simply now think that both a.0_1 and a.1_15 are dependencies.  so if 
either one becomes out of date, then ranger will recalculate _16 and/or _17

fold_using_range::relation_fold_and_or was using thet dependency cache 
as if it represent the operands of the statement accurately... so after 
the DOM rewrite, it thought that there were 2 operands on the _16 and 
_17 expression, the 2 dependencies in the cache, misconstruing it as

   _16 = a.0_1_ < a.1_15;
   _17 = a.0_1 >= a.1_15;
   _18 = _16 | _17;

Thus it thought is could fold it away.


The dependency cache shortcut should NOT be used for optimizations.   
THis patch correct the problem, and simply looks at the 2 operands of 
the feeding instructions.

bootstrapped on build-x86_64-pc-linux-gnu with no regressions. Pushed.

This is less likely to occur in GCC12 since there is less IL change on 
the fly, but it should be safe to make this change just in case.  OK for 
GCC12?

Andrew

PS. and yes, it fixes the other 2 testcases as well.

[-- Attachment #2: 0001-Don-t-use-gori-depedencies-to-optimize.patch --]
[-- Type: text/x-patch, Size: 3571 bytes --]

From c11461be4e5f3107d32187f2df9e5d4ec3f7b0d7 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Wed, 29 Jun 2022 13:34:05 -0400
Subject: [PATCH] Don't use gori depedencies to optimize.

  The routine fold_using_range::relation_fold_and_or needs to veriyf that both
operands of 2 stmts are the same, and uses GORIs dependency cache for this.
This cache cannot be counted on to reflect the current contents of a
stmt, expecially in the presence of an IL changing pass.  Instead, look at the
statement operands.

	PR tree-optimization/106114
	gcc/
	* gimple-range-fold.cc (fold_using_range::relation_fold_and_or): Check
	statement operands instead of GORI cache.
	testsuite/
	* gcc.dg/pr106114.c: New.
---
 gcc/gimple-range-fold.cc        | 30 +++++++++++++++++-------------
 gcc/testsuite/gcc.dg/pr106114.c | 14 ++++++++++++++
 2 files changed, 31 insertions(+), 13 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr106114.c

diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 2a8c66e0c05..0f815b50b9a 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -1397,14 +1397,25 @@ fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
   // Ideally we search dependencies for common names, and see what pops out.
   // until then, simply try to resolve direct dependencies.
 
-  // Both names will need to have 2 direct dependencies.
-  tree ssa1_dep2 = src.gori ()->depend2 (ssa1);
-  tree ssa2_dep2 = src.gori ()->depend2 (ssa2);
-  if (!ssa1_dep2 || !ssa2_dep2)
+  gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1);
+  gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2);
+
+  range_op_handler handler1 (SSA_NAME_DEF_STMT (ssa1));
+  range_op_handler handler2 (SSA_NAME_DEF_STMT (ssa2));
+
+  // If either handler is not present, no relation can be found.
+  if (!handler1 || !handler2)
+    return;
+
+  // Both stmts will need to have 2 ssa names in the stmt.
+  tree ssa1_dep1 = gimple_range_ssa_p (gimple_range_operand1 (ssa1_stmt));
+  tree ssa1_dep2 = gimple_range_ssa_p (gimple_range_operand2 (ssa1_stmt));
+  tree ssa2_dep1 = gimple_range_ssa_p (gimple_range_operand1 (ssa2_stmt));
+  tree ssa2_dep2 = gimple_range_ssa_p (gimple_range_operand2 (ssa2_stmt));
+
+  if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
     return;
 
-  tree ssa1_dep1 = src.gori ()->depend1 (ssa1);
-  tree ssa2_dep1 = src.gori ()->depend1 (ssa2);
   // Make sure they are the same dependencies, and detect the order of the
   // relationship.
   bool reverse_op2 = true;
@@ -1413,13 +1424,6 @@ fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
   else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1)
     return;
 
-  range_op_handler handler1 (SSA_NAME_DEF_STMT (ssa1));
-  range_op_handler handler2 (SSA_NAME_DEF_STMT (ssa2));
-
-  // If either handler is not present, no relation is found.
-  if (!handler1 || !handler2)
-    return;
-
   int_range<2> bool_one (boolean_true_node, boolean_true_node);
 
   relation_kind relation1 = handler1.op1_op2_relation (bool_one);
diff --git a/gcc/testsuite/gcc.dg/pr106114.c b/gcc/testsuite/gcc.dg/pr106114.c
new file mode 100644
index 00000000000..64c8b8d390a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr106114.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom2" } */
+
+int printf(const char *, ...);
+char a = 139, b;
+int main() {
+  char c = 173;
+  b = a;
+  while (c <= a || a < -117)
+    c = printf("0\n");
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times  "if" 2 "dom2" } }  */
-- 
2.17.2

Re: [COMMITTED] PR tree-optimization/106114 - Don't use gori dependencies to optimize.

[Richard Biener]

> Am 30.06.2022 um 03:43 schrieb Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org>:
> 
> The routine which tried to fold and's and or's using relations was using the dependency cache as a shortcut to determine if there were 2 ssa names on the feeding expressions, and assuming that was correct.
> 
> ie
> 
>   _16 = a.0_1 < -117;
>   _17 = a.0_1 >= -83;
>   _18 = _16 | _17;
> 
> the dependency cache indicates that a.0_1 is "ssa1" dependency for _16 and also for _17.  we dont have to scan the statement, so temporal out of date info is very quick.
> 
> Its also not meant to reflect that actual statement.. ie, it can get out of date.  Not is a way that makes anything incorrect, but in a way that may possibly result in a  either a missed opportunity or slightly more work when statements are being rewritten on the fly..  ie  DOM rewrites that to:
> 
>   _16 = a.1_15 < -117;
>   _17 = a.1_15 >= -83;
>   _18 = _16 | _17;
> 
> When fold_using_range is later invoked, a.1_15 is added a dependency to _16 and _17,  not attempting to understand that its a replacement, we simply now think that both a.0_1 and a.1_15 are dependencies.  so if either one becomes out of date, then ranger will recalculate _16 and/or _17
> 
> fold_using_range::relation_fold_and_or was using thet dependency cache as if it represent the operands of the statement accurately... so after the DOM rewrite, it thought that there were 2 operands on the _16 and _17 expression, the 2 dependencies in the cache, misconstruing it as
> 
>   _16 = a.0_1_ < a.1_15;
>   _17 = a.0_1 >= a.1_15;
>   _18 = _16 | _17;
> 
> Thus it thought is could fold it away.
> 
> 
> The dependency cache shortcut should NOT be used for optimizations.   THis patch correct the problem, and simply looks at the 2 operands of the feeding instructions.
> 
> bootstrapped on build-x86_64-pc-linux-gnu with no regressions. Pushed.
> 
> This is less likely to occur in GCC12 since there is less IL change on the fly, but it should be safe to make this change just in case.  OK for GCC12?

Ok for gcc12

Richard 


> Andrew
> 
> PS. and yes, it fixes the other 2 testcases as well.
> <0001-Don-t-use-gori-depedencies-to-optimize.patch>

[COMMITTED] [GCC12] PR tree-optimization/106114 - Don't use gori dependencies to optimize.

[Andrew MacLeod]

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


Applied slight tweak to the patch for the gcc12 branch.

botstrapped and no regressions on x86_64-pc-linux-gnu.  Pushed.

Andrew

-------- Forwarded Message --------
Subject: 	[COMMITTED] PR tree-optimization/106114 - Don't use gori 
dependencies to optimize.
Date: 	Wed, 29 Jun 2022 21:40:44 -0400
From: 	Andrew MacLeod <amacleod@redhat.com>
To: 	gcc-patches <gcc-patches@gcc.gnu.org>
CC: 	Aldy Hernandez <aldyh@redhat.com>



The routine which tried to fold and's and or's using relations was using 
the dependency cache as a shortcut to determine if there were 2 ssa 
names on the feeding expressions, and assuming that was correct.

ie

   _16 = a.0_1 < -117;
   _17 = a.0_1 >= -83;
   _18 = _16 | _17;

the dependency cache indicates that a.0_1 is "ssa1" dependency for _16 
and also for _17.  we dont have to scan the statement, so temporal out 
of date info is very quick.

Its also not meant to reflect that actual statement.. ie, it can get out 
of date.  Not is a way that makes anything incorrect, but in a way that 
may possibly result in a  either a missed opportunity or slightly more 
work when statements are being rewritten on the fly..  ie  DOM rewrites 
that to:

   _16 = a.1_15 < -117;
   _17 = a.1_15 >= -83;
   _18 = _16 | _17;

When fold_using_range is later invoked, a.1_15 is added a dependency to 
_16 and _17,  not attempting to understand that its a replacement, we 
simply now think that both a.0_1 and a.1_15 are dependencies.  so if 
either one becomes out of date, then ranger will recalculate _16 and/or _17

fold_using_range::relation_fold_and_or was using thet dependency cache 
as if it represent the operands of the statement accurately... so after 
the DOM rewrite, it thought that there were 2 operands on the _16 and 
_17 expression, the 2 dependencies in the cache, misconstruing it as

   _16 = a.0_1_ < a.1_15;
   _17 = a.0_1 >= a.1_15;
   _18 = _16 | _17;

Thus it thought is could fold it away.


The dependency cache shortcut should NOT be used for optimizations.   
THis patch correct the problem, and simply looks at the 2 operands of 
the feeding instructions.

bootstrapped on build-x86_64-pc-linux-gnu with no regressions. Pushed.

This is less likely to occur in GCC12 since there is less IL change on 
the fly, but it should be safe to make this change just in case.  OK for 
GCC12?

Andrew

PS. and yes, it fixes the other 2 testcases as well.

[-- Attachment #2: 106114.diff --]
[-- Type: text/x-patch, Size: 3483 bytes --]

commit d4738cbb02e201c031a2a44d8bc10d3e17d987dc
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Jul 4 11:21:34 2022 -0400

    Don't use gori depedencies to optimize.
    
      The routine fold_using_range::relation_fold_and_or needs to verify that both
    operands of 2 stmts are the same, and uses GORIs dependency cache for this.
    This cache cannot be counted on to reflect the current contents of a
    stmt, expecially in the presence of an IL changing pass.  Instead, look at the
    statement operands.
    
            PR tree-optimization/106114
            gcc/
            * gimple-range-fold.cc (fold_using_range::relation_fold_and_or): Check
            statement operands instead of GORI cache.
            gcc/testsuite/
            * gcc.dg/pr106114.c: New.

diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index dfacf6f14dc..7f03911e1c9 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -1374,14 +1374,25 @@ fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
   // Ideally we search dependencies for common names, and see what pops out.
   // until then, simply try to resolve direct dependencies.
 
-  // Both names will need to have 2 direct dependencies.
-  tree ssa1_dep2 = src.gori ()->depend2 (ssa1);
-  tree ssa2_dep2 = src.gori ()->depend2 (ssa2);
-  if (!ssa1_dep2 || !ssa2_dep2)
+  gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1);
+  gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2);
+
+  range_operator *handler1 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa1));
+  range_operator *handler2 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa2));
+
+  // If either handler is not present, no relation can be found.
+  if (!handler1 || !handler2)
+    return;
+
+  // Both stmts will need to have 2 ssa names in the stmt.
+  tree ssa1_dep1 = gimple_range_ssa_p (gimple_range_operand1 (ssa1_stmt));
+  tree ssa1_dep2 = gimple_range_ssa_p (gimple_range_operand2 (ssa1_stmt));
+  tree ssa2_dep1 = gimple_range_ssa_p (gimple_range_operand1 (ssa2_stmt));
+  tree ssa2_dep2 = gimple_range_ssa_p (gimple_range_operand2 (ssa2_stmt));
+
+  if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
     return;
 
-  tree ssa1_dep1 = src.gori ()->depend1 (ssa1);
-  tree ssa2_dep1 = src.gori ()->depend1 (ssa2);
   // Make sure they are the same dependencies, and detect the order of the
   // relationship.
   bool reverse_op2 = true;
@@ -1390,13 +1401,6 @@ fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
   else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1)
     return;
 
-  range_operator *handler1 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa1));
-  range_operator *handler2 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa2));
-
-  // If either handler is not present, no relation is found.
-  if (!handler1 || !handler2)
-    return;
-
   int_range<2> bool_one (boolean_true_node, boolean_true_node);
 
   relation_kind relation1 = handler1->op1_op2_relation (bool_one);
diff --git a/gcc/testsuite/gcc.dg/pr106114.c b/gcc/testsuite/gcc.dg/pr106114.c
new file mode 100644
index 00000000000..64c8b8d390a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr106114.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom2" } */
+
+int printf(const char *, ...);
+char a = 139, b;
+int main() {
+  char c = 173;
+  b = a;
+  while (c <= a || a < -117)
+    c = printf("0\n");
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times  "if" 2 "dom2" } }  */