Simplify X * C1 == C2 with undefined overflow

Message ID alpine.DEB.2.23.453.2008010906360.6853@stedding.saclay.inria.fr
State New
Headers show
Series
  • Simplify X * C1 == C2 with undefined overflow
Related show

Commit Message

Marc Glisse Aug. 1, 2020, 7:28 a.m.
Hello,

this transformation is quite straightforward, without overflow, 3*X==15 is 
the same as X==5 and 3*X==5 cannot happen. Adding a single_use restriction 
for the first case didn't seem necessary, although of course it can 
slightly increase register pressure in some cases.

Bootstrap+regtest on x86_64-pc-linux-gnu.

2020-08-03  Marc Glisse  <marc.glisse@inria.fr>

  	PR tree-optimization/95433
  	* match.pd (X * C1 == C2): New transformation.

  	* gcc.c-torture/execute/pr23135.c: Add -fwrapv to avoid
 	undefined behavior.
  	* gcc.dg/tree-ssa/pr95433.c: New file.

-- 
Marc Glisse

Comments

David Malcolm via Gcc-patches Aug. 3, 2020, 8:51 a.m. | #1
On Sat, Aug 1, 2020 at 9:29 AM Marc Glisse <marc.glisse@inria.fr> wrote:
>

> Hello,

>

> this transformation is quite straightforward, without overflow, 3*X==15 is

> the same as X==5 and 3*X==5 cannot happen. Adding a single_use restriction

> for the first case didn't seem necessary, although of course it can

> slightly increase register pressure in some cases.

>

> Bootstrap+regtest on x86_64-pc-linux-gnu.


OK with using constant_boolean_node (cmp == NE_EXPR, type).

ISTR we had the x * 0 == CST simplification somewhere
but maybe it was x * y == 0 ...  ah, yes:

/* Transform comparisons of the form X * C1 CMP 0 to X CMP 0 in the
   signed arithmetic case.  That form is created by the compiler
   often enough for folding it to be of value.  One example is in
   computing loop trip counts after Operator Strength Reduction.  */
(for cmp (simple_comparison)
     scmp (swapped_simple_comparison)
 (simplify
  (cmp (mult@3 @0 INTEGER_CST@1) integer_zerop@2)

As it is placed after your pattern it will be never matched I think
(but we don't warn because of INTEGER_CST vs. integer_zerop).

But I think your pattern subsumes it besides of the X * 0 == 0
compare - oh, and the other pattern also handles relational compares
(those will still trigger).

Maybe place the patterns next to each other?  Also see whether
moving yours after the above will cease the testcases to be handled
because it's no longer matched - if not this might be the better
order.

Richard.

> 2020-08-03  Marc Glisse  <marc.glisse@inria.fr>

>

>         PR tree-optimization/95433

>         * match.pd (X * C1 == C2): New transformation.

>

>         * gcc.c-torture/execute/pr23135.c: Add -fwrapv to avoid

>         undefined behavior.

>         * gcc.dg/tree-ssa/pr95433.c: New file.

>

> --

> Marc Glisse
Marc Glisse Aug. 4, 2020, 3:38 p.m. | #2
On Mon, 3 Aug 2020, Richard Biener wrote:

> On Sat, Aug 1, 2020 at 9:29 AM Marc Glisse <marc.glisse@inria.fr> wrote:

>>

>> Hello,

>>

>> this transformation is quite straightforward, without overflow, 3*X==15 is

>> the same as X==5 and 3*X==5 cannot happen. Adding a single_use restriction

>> for the first case didn't seem necessary, although of course it can

>> slightly increase register pressure in some cases.

>>

>> Bootstrap+regtest on x86_64-pc-linux-gnu.

>

> OK with using constant_boolean_node (cmp == NE_EXPR, type).

>

> ISTR we had the x * 0 == CST simplification somewhere

> but maybe it was x * y == 0 ...  ah, yes:

>

> /* Transform comparisons of the form X * C1 CMP 0 to X CMP 0 in the

>   signed arithmetic case.  That form is created by the compiler

>   often enough for folding it to be of value.  One example is in

>   computing loop trip counts after Operator Strength Reduction.  */

> (for cmp (simple_comparison)

>     scmp (swapped_simple_comparison)

> (simplify

>  (cmp (mult@3 @0 INTEGER_CST@1) integer_zerop@2)

>

> As it is placed after your pattern it will be never matched I think

> (but we don't warn because of INTEGER_CST vs. integer_zerop).

>

> But I think your pattern subsumes it besides of the X * 0 == 0

> compare - oh, and the other pattern also handles relational compares

> (those will still trigger).

>

> Maybe place the patterns next to each other?  Also see whether

> moving yours after the above will cease the testcases to be handled

> because it's no longer matched - if not this might be the better

> order.


I moved it after, it still works, so I pushed the patch. Note that the 
other transformation has a single_use restriction, while this one doesn't, 
that's not very consistent, but also hopefully not so important...

-- 
Marc Glisse

Patch

diff --git a/gcc/match.pd b/gcc/match.pd
index a052c9e3dbc..78fd8cf5d9e 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1578,6 +1578,20 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	&& wi::neg_p (wi::to_wide (@1), TYPE_SIGN (TREE_TYPE (@1))))
     (cmp @2 @0))))))
 
+/* For integral types with undefined overflow fold
+   x * C1 == C2 into x == C2 / C1 or false.  */
+(for cmp (eq ne)
+ (simplify
+  (cmp (mult @0 INTEGER_CST@1) INTEGER_CST@2)
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
+       && wi::to_wide (@1) != 0)
+   (with { widest_int quot; }
+    (if (wi::multiple_of_p (wi::to_widest (@2), wi::to_widest (@1),
+			    TYPE_SIGN (TREE_TYPE (@0)), &quot))
+     (cmp @0 { wide_int_to_tree (TREE_TYPE (@0), quot); })
+     { build_int_cst (type, cmp == NE_EXPR); })))))
+
 /* (X - 1U) <= INT_MAX-1U into (int) X > 0.  */
 (for cmp (le gt)
      icmp (gt le)
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr23135.c b/gcc/testsuite/gcc.c-torture/execute/pr23135.c
index e740ff52874..ef9b7efc9c4 100644
--- a/gcc/testsuite/gcc.c-torture/execute/pr23135.c
+++ b/gcc/testsuite/gcc.c-torture/execute/pr23135.c
@@ -1,7 +1,7 @@ 
 /* Based on execute/simd-1.c, modified by joern.rennecke@st.com to
    trigger a reload bug.  Verified for gcc mainline from 20050722 13:00 UTC
    for sh-elf -m4 -O2.  */
-/* { dg-options "-Wno-psabi" } */
+/* { dg-options "-Wno-psabi -fwrapv" } */
 /* { dg-add-options stack_size } */
 
 #ifndef STACK_SIZE
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr95433.c b/gcc/testsuite/gcc.dg/tree-ssa/pr95433.c
new file mode 100644
index 00000000000..4e161ee26cc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr95433.c
@@ -0,0 +1,8 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+int f(int x){return x*7==17;}
+int g(int x){return x*3==15;}
+
+/* { dg-final { scan-tree-dump "return 0;" "optimized" } } */
+/* { dg-final { scan-tree-dump "== 5;" "optimized" } } */