[PATCH] match.pd: Add new division pattern [PR104992]

[PATCH] match.pd: Add new division pattern [PR104992]

[Sam Feifer]

This patch fixes a missed optimization in match.pd. It takes the pattern, x / y * y == x, and optimizes it to x % y == 0. This produces fewer instructions.

There are also tests for the optimizations to be added to the test suite.

Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?

	PR tree-optimization/104992

gcc/ChangeLog:

	* match.pd x / y * y == x: New simplification.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr104992-1.c: New test.
	* gcc.dg/pr104992.c: New test.
---
 gcc/match.pd                      |  5 +++++
 gcc/testsuite/gcc.dg/pr104992-1.c | 30 ++++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/pr104992.c   | 35 +++++++++++++++++++++++++++++++
 3 files changed, 70 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr104992-1.c
 create mode 100644 gcc/testsuite/gcc.dg/pr104992.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 9736393061a..f7ab2174b8a 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -8054,3 +8054,8 @@ and,
       (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
         (bit_and @0 @1)
       (cond (le @0 @1) @0 (bit_and @0 @1))))))
+
+/* x / y * y == x -> x % y == 0.  */
+(simplify
+  (eq (mult (trunc_div @0 @1) @1) @0)
+  (eq (trunc_mod @0 @1) { build_zero_cst TREE_TYPE(@0); }))
diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c b/gcc/testsuite/gcc.dg/pr104992-1.c
new file mode 100644
index 00000000000..a80e5e180ce
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr104992-1.c
@@ -0,0 +1,30 @@
+/* PR tree-optimization/104992 */
+/* { dg-do run } */
+/* { dg-options "-O2"} */
+
+#include "pr104992.c"
+
+int main () {
+
+    /* Should be true.  */
+    if (!foo(6, 3)
+        || !bar(12, 2)
+        || !baz(34, 17)
+        || !qux(50, 10)
+        || !fred(16, 8)
+        || !baz(-9, 3)
+        || !baz(9, -3)
+        || !baz(-9, -3)
+        ) {
+            __builtin_abort();
+         }
+    
+    /* Should be false.  */
+    if (foo(5, 30)
+        || bar(72, 27)
+        || baz(42, 15)) {
+            __builtin_abort();
+        }
+    
+    return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/pr104992.c b/gcc/testsuite/gcc.dg/pr104992.c
new file mode 100644
index 00000000000..b4b0ca53118
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr104992.c
@@ -0,0 +1,35 @@
+/* PR tree-optimization/104992 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Form from PR.  */
+__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
+{
+    return x / y * y == x;
+}
+
+__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
+    return x == x / y * y;
+}
+
+/* Signed test case.  */
+__attribute__((noipa)) unsigned baz (int x, int y) {
+    return x / y * y == x;
+}
+
+/* Changed order.  */
+__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
+    return y * (x / y) == x;
+}
+
+/* Wrong order.  */
+__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
+    return y * x / y == x;
+}
+
+/* Wrong pattern.  */
+__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y, unsigned z) {
+    return x / y * z == x;
+}
+
+/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */

base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
-- 
2.31.1

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Andrew Pinski]

On Mon, Jul 25, 2022 at 12:37 PM Sam Feifer via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This patch fixes a missed optimization in match.pd. It takes the pattern, x / y * y == x, and optimizes it to x % y == 0. This produces fewer instructions.
>
> There are also tests for the optimizations to be added to the test suite.
>
> Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?
>
>         PR tree-optimization/104992
>
> gcc/ChangeLog:
>
>         * match.pd x / y * y == x: New simplification.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/pr104992-1.c: New test.
>         * gcc.dg/pr104992.c: New test.
> ---
>  gcc/match.pd                      |  5 +++++
>  gcc/testsuite/gcc.dg/pr104992-1.c | 30 ++++++++++++++++++++++++++
>  gcc/testsuite/gcc.dg/pr104992.c   | 35 +++++++++++++++++++++++++++++++
>  3 files changed, 70 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/pr104992-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/pr104992.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 9736393061a..f7ab2174b8a 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -8054,3 +8054,8 @@ and,
>        (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
>          (bit_and @0 @1)
>        (cond (le @0 @1) @0 (bit_and @0 @1))))))
> +
> +/* x / y * y == x -> x % y == 0.  */
> +(simplify
> +  (eq (mult (trunc_div @0 @1) @1) @0)
> +  (eq (trunc_mod @0 @1) { build_zero_cst TREE_TYPE(@0); }))

I suspect for eq and mult you might want to add :c to them even though
in your testcase you don't need them, you might be able to get it via
using different statements and looking at the forwprop gimple dump.
Also, did you send the wrong patch as it looks like the function call
to build_zero_cst has been eaten ... (or is it just because TREE_TYPE
has parentheses inside the macro and it just accidently works :)).

You might also want to make sure it does the right thing for vector
types and complex types (yes both are valid for trunc_div still).

Thanks,
Andrew Pinski

> diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c b/gcc/testsuite/gcc.dg/pr104992-1.c
> new file mode 100644
> index 00000000000..a80e5e180ce
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
> @@ -0,0 +1,30 @@
> +/* PR tree-optimization/104992 */
> +/* { dg-do run } */
> +/* { dg-options "-O2"} */
> +
> +#include "pr104992.c"
> +
> +int main () {
> +
> +    /* Should be true.  */
> +    if (!foo(6, 3)
> +        || !bar(12, 2)
> +        || !baz(34, 17)
> +        || !qux(50, 10)
> +        || !fred(16, 8)
> +        || !baz(-9, 3)
> +        || !baz(9, -3)
> +        || !baz(-9, -3)
> +        ) {
> +            __builtin_abort();
> +         }
> +
> +    /* Should be false.  */
> +    if (foo(5, 30)
> +        || bar(72, 27)
> +        || baz(42, 15)) {
> +            __builtin_abort();
> +        }
> +
> +    return 0;
> +}
> diff --git a/gcc/testsuite/gcc.dg/pr104992.c b/gcc/testsuite/gcc.dg/pr104992.c
> new file mode 100644
> index 00000000000..b4b0ca53118
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr104992.c
> @@ -0,0 +1,35 @@
> +/* PR tree-optimization/104992 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* Form from PR.  */
> +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
> +{
> +    return x / y * y == x;
> +}
> +
> +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
> +    return x == x / y * y;
> +}
> +
> +/* Signed test case.  */
> +__attribute__((noipa)) unsigned baz (int x, int y) {
> +    return x / y * y == x;
> +}
> +
> +/* Changed order.  */
> +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
> +    return y * (x / y) == x;
> +}
> +
> +/* Wrong order.  */
> +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
> +    return y * x / y == x;
> +}
> +
> +/* Wrong pattern.  */
> +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y, unsigned z) {
> +    return x / y * z == x;
> +}
> +
> +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
>
> base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
> --
> 2.31.1
>

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Sam Feifer]

> I suspect for eq and mult you might want to add :c to them even though
> in your testcase you don't need them, you might be able to get it via
> using different statements and looking at the forwprop gimple dump.
> Also, did you send the wrong patch as it looks like the function call
> to build_zero_cst has been eaten ... (or is it just because TREE_TYPE
> has parentheses inside the macro and it just accidently works :)).
>

I got lucky and it works without parentheses :). I just added them in for
readability.

You might also want to make sure it does the right thing for vector
> types and complex types (yes both are valid for trunc_div still).
>
>
I made a vector test case, but it's giving me errors when using " == "
between two vectors. I'm running it with the C++ front end and it's saying
the return value cannot be converted. Any tips for this?

I'm not sure exactly what you mean by "complex types" in terms of testing
this patch. Could I get an example?

Thanks
-Sam

Thanks,
> Andrew Pinski
>
> > diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c
> b/gcc/testsuite/gcc.dg/pr104992-1.c
> > new file mode 100644
> > index 00000000000..a80e5e180ce
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
> > @@ -0,0 +1,30 @@
> > +/* PR tree-optimization/104992 */
> > +/* { dg-do run } */
> > +/* { dg-options "-O2"} */
> > +
> > +#include "pr104992.c"
> > +
> > +int main () {
> > +
> > +    /* Should be true.  */
> > +    if (!foo(6, 3)
> > +        || !bar(12, 2)
> > +        || !baz(34, 17)
> > +        || !qux(50, 10)
> > +        || !fred(16, 8)
> > +        || !baz(-9, 3)
> > +        || !baz(9, -3)
> > +        || !baz(-9, -3)
> > +        ) {
> > +            __builtin_abort();
> > +         }
> > +
> > +    /* Should be false.  */
> > +    if (foo(5, 30)
> > +        || bar(72, 27)
> > +        || baz(42, 15)) {
> > +            __builtin_abort();
> > +        }
> > +
> > +    return 0;
> > +}
> > diff --git a/gcc/testsuite/gcc.dg/pr104992.c
> b/gcc/testsuite/gcc.dg/pr104992.c
> > new file mode 100644
> > index 00000000000..b4b0ca53118
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/pr104992.c
> > @@ -0,0 +1,35 @@
> > +/* PR tree-optimization/104992 */
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +
> > +/* Form from PR.  */
> > +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
> > +{
> > +    return x / y * y == x;
> > +}
> > +
> > +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
> > +    return x == x / y * y;
> > +}
> > +
> > +/* Signed test case.  */
> > +__attribute__((noipa)) unsigned baz (int x, int y) {
> > +    return x / y * y == x;
> > +}
> > +
> > +/* Changed order.  */
> > +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
> > +    return y * (x / y) == x;
> > +}
> > +
> > +/* Wrong order.  */
> > +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
> > +    return y * x / y == x;
> > +}
> > +
> > +/* Wrong pattern.  */
> > +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y, unsigned
> z) {
> > +    return x / y * z == x;
> > +}
> > +
> > +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
> >
> > base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
> > --
> > 2.31.1
> >
>
>

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Andrew Pinski]

On Mon, Jul 25, 2022 at 1:59 PM Sam Feifer <sfeifer@redhat.com> wrote:
>
>
>> I suspect for eq and mult you might want to add :c to them even though
>> in your testcase you don't need them, you might be able to get it via
>> using different statements and looking at the forwprop gimple dump.
>> Also, did you send the wrong patch as it looks like the function call
>> to build_zero_cst has been eaten ... (or is it just because TREE_TYPE
>> has parentheses inside the macro and it just accidently works :)).
>
>
> I got lucky and it works without parentheses :). I just added them in for readability.
>
>> You might also want to make sure it does the right thing for vector
>> types and complex types (yes both are valid for trunc_div still).
>>
>
> I made a vector test case, but it's giving me errors when using " == " between two vectors. I'm running it with the C++ front end and it's saying the return value cannot be converted. Any tips for this?
>
> I'm not sure exactly what you mean by "complex types" in terms of testing this patch. Could I get an example?

int f(_Complex int x, _Complex int y)
{
  return x == x / y * y;
}

For vector try (which works for both the C and C++ front-end):
#define vector __attribute__((vector_size(4*sizeof(int)) ))
vector int f(vector int x, vector int y)
{
  return x == x / y * y;
}

That is for the vector case, == still returns a vector type.

Thanks,
Andrew Pinski

>
> Thanks
> -Sam
>
>> Thanks,
>> Andrew Pinski
>>
>> > diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c b/gcc/testsuite/gcc.dg/pr104992-1.c
>> > new file mode 100644
>> > index 00000000000..a80e5e180ce
>> > --- /dev/null
>> > +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
>> > @@ -0,0 +1,30 @@
>> > +/* PR tree-optimization/104992 */
>> > +/* { dg-do run } */
>> > +/* { dg-options "-O2"} */
>> > +
>> > +#include "pr104992.c"
>> > +
>> > +int main () {
>> > +
>> > +    /* Should be true.  */
>> > +    if (!foo(6, 3)
>> > +        || !bar(12, 2)
>> > +        || !baz(34, 17)
>> > +        || !qux(50, 10)
>> > +        || !fred(16, 8)
>> > +        || !baz(-9, 3)
>> > +        || !baz(9, -3)
>> > +        || !baz(-9, -3)
>> > +        ) {
>> > +            __builtin_abort();
>> > +         }
>> > +
>> > +    /* Should be false.  */
>> > +    if (foo(5, 30)
>> > +        || bar(72, 27)
>> > +        || baz(42, 15)) {
>> > +            __builtin_abort();
>> > +        }
>> > +
>> > +    return 0;
>> > +}
>> > diff --git a/gcc/testsuite/gcc.dg/pr104992.c b/gcc/testsuite/gcc.dg/pr104992.c
>> > new file mode 100644
>> > index 00000000000..b4b0ca53118
>> > --- /dev/null
>> > +++ b/gcc/testsuite/gcc.dg/pr104992.c
>> > @@ -0,0 +1,35 @@
>> > +/* PR tree-optimization/104992 */
>> > +/* { dg-do compile } */
>> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> > +
>> > +/* Form from PR.  */
>> > +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
>> > +{
>> > +    return x / y * y == x;
>> > +}
>> > +
>> > +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
>> > +    return x == x / y * y;
>> > +}
>> > +
>> > +/* Signed test case.  */
>> > +__attribute__((noipa)) unsigned baz (int x, int y) {
>> > +    return x / y * y == x;
>> > +}
>> > +
>> > +/* Changed order.  */
>> > +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
>> > +    return y * (x / y) == x;
>> > +}
>> > +
>> > +/* Wrong order.  */
>> > +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
>> > +    return y * x / y == x;
>> > +}
>> > +
>> > +/* Wrong pattern.  */
>> > +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y, unsigned z) {
>> > +    return x / y * z == x;
>> > +}
>> > +
>> > +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
>> >
>> > base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
>> > --
>> > 2.31.1
>> >
>>

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Sam Feifer]

>
> int f(_Complex int x, _Complex int y)
> {
>   return x == x / y * y;
> }
>

After some research about mod with complex types, I found that the binary
mod operation does not work with complex types. If so, the complex test
case should not be simplified. Is this correct?

I should also note that the above function, f, causes a segmentation fault.
I can only get a function with complex types to compile by breaking up the
operations like I would in a forward propagation test case. When I do this,
it does not simplify into mod, which I think is right.

Thanks
-Sam


> For vector try (which works for both the C and C++ front-end):
> #define vector __attribute__((vector_size(4*sizeof(int)) ))
> vector int f(vector int x, vector int y)
> {
>   return x == x / y * y;
> }
>
> That is for the vector case, == still returns a vector type.
>
> Thanks,
> Andrew Pinski
>
> >
> > Thanks
> > -Sam
> >
> >> Thanks,
> >> Andrew Pinski
> >>
> >> > diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c
> b/gcc/testsuite/gcc.dg/pr104992-1.c
> >> > new file mode 100644
> >> > index 00000000000..a80e5e180ce
> >> > --- /dev/null
> >> > +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
> >> > @@ -0,0 +1,30 @@
> >> > +/* PR tree-optimization/104992 */
> >> > +/* { dg-do run } */
> >> > +/* { dg-options "-O2"} */
> >> > +
> >> > +#include "pr104992.c"
> >> > +
> >> > +int main () {
> >> > +
> >> > +    /* Should be true.  */
> >> > +    if (!foo(6, 3)
> >> > +        || !bar(12, 2)
> >> > +        || !baz(34, 17)
> >> > +        || !qux(50, 10)
> >> > +        || !fred(16, 8)
> >> > +        || !baz(-9, 3)
> >> > +        || !baz(9, -3)
> >> > +        || !baz(-9, -3)
> >> > +        ) {
> >> > +            __builtin_abort();
> >> > +         }
> >> > +
> >> > +    /* Should be false.  */
> >> > +    if (foo(5, 30)
> >> > +        || bar(72, 27)
> >> > +        || baz(42, 15)) {
> >> > +            __builtin_abort();
> >> > +        }
> >> > +
> >> > +    return 0;
> >> > +}
> >> > diff --git a/gcc/testsuite/gcc.dg/pr104992.c
> b/gcc/testsuite/gcc.dg/pr104992.c
> >> > new file mode 100644
> >> > index 00000000000..b4b0ca53118
> >> > --- /dev/null
> >> > +++ b/gcc/testsuite/gcc.dg/pr104992.c
> >> > @@ -0,0 +1,35 @@
> >> > +/* PR tree-optimization/104992 */
> >> > +/* { dg-do compile } */
> >> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> >> > +
> >> > +/* Form from PR.  */
> >> > +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
> >> > +{
> >> > +    return x / y * y == x;
> >> > +}
> >> > +
> >> > +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
> >> > +    return x == x / y * y;
> >> > +}
> >> > +
> >> > +/* Signed test case.  */
> >> > +__attribute__((noipa)) unsigned baz (int x, int y) {
> >> > +    return x / y * y == x;
> >> > +}
> >> > +
> >> > +/* Changed order.  */
> >> > +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
> >> > +    return y * (x / y) == x;
> >> > +}
> >> > +
> >> > +/* Wrong order.  */
> >> > +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
> >> > +    return y * x / y == x;
> >> > +}
> >> > +
> >> > +/* Wrong pattern.  */
> >> > +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y,
> unsigned z) {
> >> > +    return x / y * z == x;
> >> > +}
> >> > +
> >> > +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
> >> >
> >> > base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
> >> > --
> >> > 2.31.1
> >> >
> >>
>
>

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Richard Biener]

On Tue, Jul 26, 2022 at 4:32 PM Sam Feifer via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> >
> > int f(_Complex int x, _Complex int y)
> > {
> >   return x == x / y * y;
> > }
> >
>
> After some research about mod with complex types, I found that the binary
> mod operation does not work with complex types. If so, the complex test
> case should not be simplified. Is this correct?
>
> I should also note that the above function, f, causes a segmentation fault.
> I can only get a function with complex types to compile by breaking up the
> operations like I would in a forward propagation test case. When I do this,
> it does not simplify into mod, which I think is right.

_Complex int are strange beasts, I'd simply avoid the transform for them.

Can you please move the pattern next to the existing div/mod patterns,
like after the related

/* Simplify (A / B) * B + (A % B) -> A.  */
(for div (trunc_div ceil_div floor_div round_div)
     mod (trunc_mod ceil_mod floor_mod round_mod)
  (simplify
   (plus:c (mult:c (div @0 @1) @1) (mod @0 @1))
   @0))

pattern?

+/* x / y * y == x -> x % y == 0.  */
+(simplify
+  (eq (mult (trunc_div @0 @1) @1) @0)
+  (eq (trunc_mod @0 @1) { build_zero_cst TREE_TYPE(@0); }))

there are parens missing around the TREE_TYPE (@0), how did you test
the patch?  You probably want :s on the trunc_div and as Andrew said
:c on the eq and the mult.

Richard.

> Thanks
> -Sam
>
>
> > For vector try (which works for both the C and C++ front-end):
> > #define vector __attribute__((vector_size(4*sizeof(int)) ))
> > vector int f(vector int x, vector int y)
> > {
> >   return x == x / y * y;
> > }
> >
> > That is for the vector case, == still returns a vector type.
> >
> > Thanks,
> > Andrew Pinski
> >
> > >
> > > Thanks
> > > -Sam
> > >
> > >> Thanks,
> > >> Andrew Pinski
> > >>
> > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c
> > b/gcc/testsuite/gcc.dg/pr104992-1.c
> > >> > new file mode 100644
> > >> > index 00000000000..a80e5e180ce
> > >> > --- /dev/null
> > >> > +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
> > >> > @@ -0,0 +1,30 @@
> > >> > +/* PR tree-optimization/104992 */
> > >> > +/* { dg-do run } */
> > >> > +/* { dg-options "-O2"} */
> > >> > +
> > >> > +#include "pr104992.c"
> > >> > +
> > >> > +int main () {
> > >> > +
> > >> > +    /* Should be true.  */
> > >> > +    if (!foo(6, 3)
> > >> > +        || !bar(12, 2)
> > >> > +        || !baz(34, 17)
> > >> > +        || !qux(50, 10)
> > >> > +        || !fred(16, 8)
> > >> > +        || !baz(-9, 3)
> > >> > +        || !baz(9, -3)
> > >> > +        || !baz(-9, -3)
> > >> > +        ) {
> > >> > +            __builtin_abort();
> > >> > +         }
> > >> > +
> > >> > +    /* Should be false.  */
> > >> > +    if (foo(5, 30)
> > >> > +        || bar(72, 27)
> > >> > +        || baz(42, 15)) {
> > >> > +            __builtin_abort();
> > >> > +        }
> > >> > +
> > >> > +    return 0;
> > >> > +}
> > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992.c
> > b/gcc/testsuite/gcc.dg/pr104992.c
> > >> > new file mode 100644
> > >> > index 00000000000..b4b0ca53118
> > >> > --- /dev/null
> > >> > +++ b/gcc/testsuite/gcc.dg/pr104992.c
> > >> > @@ -0,0 +1,35 @@
> > >> > +/* PR tree-optimization/104992 */
> > >> > +/* { dg-do compile } */
> > >> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > >> > +
> > >> > +/* Form from PR.  */
> > >> > +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
> > >> > +{
> > >> > +    return x / y * y == x;
> > >> > +}
> > >> > +
> > >> > +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
> > >> > +    return x == x / y * y;
> > >> > +}
> > >> > +
> > >> > +/* Signed test case.  */
> > >> > +__attribute__((noipa)) unsigned baz (int x, int y) {
> > >> > +    return x / y * y == x;
> > >> > +}
> > >> > +
> > >> > +/* Changed order.  */
> > >> > +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
> > >> > +    return y * (x / y) == x;
> > >> > +}
> > >> > +
> > >> > +/* Wrong order.  */
> > >> > +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
> > >> > +    return y * x / y == x;
> > >> > +}
> > >> > +
> > >> > +/* Wrong pattern.  */
> > >> > +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y,
> > unsigned z) {
> > >> > +    return x / y * z == x;
> > >> > +}
> > >> > +
> > >> > +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
> > >> >
> > >> > base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
> > >> > --
> > >> > 2.31.1
> > >> >
> > >>
> >
> >

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Sam Feifer]

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

> _Complex int are strange beasts, I'd simply avoid the transform for them.
>
>
I added to the match.pd rule to not simplify if the operands are complex.
There is now a test case for complex types to make sure they do not
simplify. I had to move the "dg-do run" test to g++.dg to accommodate the
complex type function that is included (even though there isn't a runtime
test for complex types).

Can you please move the pattern next to the existing div/mod patterns,
> like after the related
>
>
done :)

/* Simplify (A / B) * B + (A % B) -> A.  */
> (for div (trunc_div ceil_div floor_div round_div)
>      mod (trunc_mod ceil_mod floor_mod round_mod)
>   (simplify
>    (plus:c (mult:c (div @0 @1) @1) (mod @0 @1))
>    @0))
>
> pattern?
>
> +/* x / y * y == x -> x % y == 0.  */
> +(simplify
> +  (eq (mult (trunc_div @0 @1) @1) @0)
> +  (eq (trunc_mod @0 @1) { build_zero_cst TREE_TYPE(@0); }))
>
> there are parens missing around the TREE_TYPE (@0), how did you test
> the patch?  You probably want :s on the trunc_div and as Andrew said
> :c on the eq and the mult.
>

I made those changes to the rule. The rule worked without the parentheses,
which is probably why I didn't notice they were missing. Attached is an
updated patch file.

Thanks
-Sam


> Richard.
>
> > Thanks
> > -Sam
> >
> >
> > > For vector try (which works for both the C and C++ front-end):
> > > #define vector __attribute__((vector_size(4*sizeof(int)) ))
> > > vector int f(vector int x, vector int y)
> > > {
> > >   return x == x / y * y;
> > > }
> > >
> > > That is for the vector case, == still returns a vector type.
> > >
> > > Thanks,
> > > Andrew Pinski
> > >
> > > >
> > > > Thanks
> > > > -Sam
> > > >
> > > >> Thanks,
> > > >> Andrew Pinski
> > > >>
> > > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c
> > > b/gcc/testsuite/gcc.dg/pr104992-1.c
> > > >> > new file mode 100644
> > > >> > index 00000000000..a80e5e180ce
> > > >> > --- /dev/null
> > > >> > +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
> > > >> > @@ -0,0 +1,30 @@
> > > >> > +/* PR tree-optimization/104992 */
> > > >> > +/* { dg-do run } */
> > > >> > +/* { dg-options "-O2"} */
> > > >> > +
> > > >> > +#include "pr104992.c"
> > > >> > +
> > > >> > +int main () {
> > > >> > +
> > > >> > +    /* Should be true.  */
> > > >> > +    if (!foo(6, 3)
> > > >> > +        || !bar(12, 2)
> > > >> > +        || !baz(34, 17)
> > > >> > +        || !qux(50, 10)
> > > >> > +        || !fred(16, 8)
> > > >> > +        || !baz(-9, 3)
> > > >> > +        || !baz(9, -3)
> > > >> > +        || !baz(-9, -3)
> > > >> > +        ) {
> > > >> > +            __builtin_abort();
> > > >> > +         }
> > > >> > +
> > > >> > +    /* Should be false.  */
> > > >> > +    if (foo(5, 30)
> > > >> > +        || bar(72, 27)
> > > >> > +        || baz(42, 15)) {
> > > >> > +            __builtin_abort();
> > > >> > +        }
> > > >> > +
> > > >> > +    return 0;
> > > >> > +}
> > > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992.c
> > > b/gcc/testsuite/gcc.dg/pr104992.c
> > > >> > new file mode 100644
> > > >> > index 00000000000..b4b0ca53118
> > > >> > --- /dev/null
> > > >> > +++ b/gcc/testsuite/gcc.dg/pr104992.c
> > > >> > @@ -0,0 +1,35 @@
> > > >> > +/* PR tree-optimization/104992 */
> > > >> > +/* { dg-do compile } */
> > > >> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > > >> > +
> > > >> > +/* Form from PR.  */
> > > >> > +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
> > > >> > +{
> > > >> > +    return x / y * y == x;
> > > >> > +}
> > > >> > +
> > > >> > +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
> > > >> > +    return x == x / y * y;
> > > >> > +}
> > > >> > +
> > > >> > +/* Signed test case.  */
> > > >> > +__attribute__((noipa)) unsigned baz (int x, int y) {
> > > >> > +    return x / y * y == x;
> > > >> > +}
> > > >> > +
> > > >> > +/* Changed order.  */
> > > >> > +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
> > > >> > +    return y * (x / y) == x;
> > > >> > +}
> > > >> > +
> > > >> > +/* Wrong order.  */
> > > >> > +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
> > > >> > +    return y * x / y == x;
> > > >> > +}
> > > >> > +
> > > >> > +/* Wrong pattern.  */
> > > >> > +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y,
> > > unsigned z) {
> > > >> > +    return x / y * z == x;
> > > >> > +}
> > > >> > +
> > > >> > +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
> > > >> >
> > > >> > base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
> > > >> > --
> > > >> > 2.31.1
> > > >> >
> > > >>
> > >
> > >
>
>

[-- Attachment #2: 0001-match.pd-Add-new-division-pattern-PR104992.patch --]
[-- Type: text/x-patch, Size: 4172 bytes --]

From bdcfd7b85e95ec9a649c8083c4fbc1bfb88cea88 Mon Sep 17 00:00:00 2001
From: Sam Feifer <sfeifer@redhat.com>
Date: Wed, 27 Jul 2022 15:37:39 -0400
Subject: [PATCH] match.pd: Add new division pattern [PR104992]

This patch fixes a missed optimization in match.pd. It takes the pattern, x / y * y == x, and optimizes it to x % y == 0. This produces fewer instructions. This simplification does not happen for complex types.

There are also tests for the optimizations to be added to the test suite.

Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?

	PR tree-optimization/104992

gcc/ChangeLog:

	* match.pd x / y * y == x: New simplification.

gcc/testsuite/ChangeLog:

	* g++.dg/pr104992-1.C: New test.
	* gcc.dg/pr104992.c: New test.
---
 gcc/match.pd                      |  7 ++++
 gcc/testsuite/g++.dg/pr104992-1.C | 30 ++++++++++++++++
 gcc/testsuite/gcc.dg/pr104992.c   | 57 +++++++++++++++++++++++++++++++
 3 files changed, 94 insertions(+)
 create mode 100644 gcc/testsuite/g++.dg/pr104992-1.C
 create mode 100644 gcc/testsuite/gcc.dg/pr104992.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 9736393061a..1442e4cf8dc 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3981,6 +3981,13 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (plus:c (mult:c (div @0 @1) @1) (mod @0 @1))
    @0))
 
+/* x / y * y == x -> x % y == 0.  */
+(simplify
+  (eq:c (mult:c (trunc_div:s @0 @1) @1) @0)
+  (if (TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE
+       && TREE_CODE (TREE_TYPE (@1)) != COMPLEX_TYPE)
+    (eq (trunc_mod @0 @1) { build_zero_cst (TREE_TYPE(@0)); })))
+
 /* ((X /[ex] A) +- B) * A  -->  X +- A * B.  */
 (for op (plus minus)
  (simplify
diff --git a/gcc/testsuite/g++.dg/pr104992-1.C b/gcc/testsuite/g++.dg/pr104992-1.C
new file mode 100644
index 00000000000..f5696b245ac
--- /dev/null
+++ b/gcc/testsuite/g++.dg/pr104992-1.C
@@ -0,0 +1,30 @@
+/* PR tree-optimization/104992 */
+/* { dg-do run } */
+/* { dg-options "-O2"} */
+
+#include "../gcc.dg/pr104992.c"
+
+int main () {
+
+    /* Should be true.  */
+    if (!foo(6, 3)
+        || !bar(12, 2)
+        || !baz(34, 17)
+        || !qux(50, 10)
+        || !fred(16, 8)
+        || !baz(-9, 3)
+        || !baz(9, -3)
+        || !baz(-9, -3)
+        ) {
+            __builtin_abort();
+         }
+    
+    /* Should be false.  */
+    if (foo(5, 30)
+        || bar(72, 27)
+        || baz(42, 15)) {
+            __builtin_abort();
+        }
+    
+    return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/pr104992.c b/gcc/testsuite/gcc.dg/pr104992.c
new file mode 100644
index 00000000000..b9d91a13ad8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr104992.c
@@ -0,0 +1,57 @@
+/* PR tree-optimization/104992 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#define vector __attribute__((vector_size(4*sizeof(int))))
+
+/* Form from PR.  */
+__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
+{
+    return x / y * y == x;
+}
+
+__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
+    return x == x / y * y;
+}
+
+/* Signed test case.  */
+__attribute__((noipa)) unsigned baz (int x, int y) {
+    return x / y * y == x;
+}
+
+/* Changed order.  */
+__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
+    return y * (x / y) == x;
+}
+
+/* Test for forward propogation.  */
+__attribute__((noipa)) unsigned corge(unsigned x, unsigned y) {
+    int z = x / y;
+    int q = z * y;
+    return q == x; 
+}
+
+/* Test vector case.  */
+__attribute__((noipa)) vector int thud(vector int x, vector int y) {
+    return x / y * y == x;
+}
+
+/* Complex type should not simplify because mod is different.  */
+__attribute__((noipa)) int goo(_Complex int x, _Complex int y)
+{
+    _Complex int z = x / y;
+    _Complex int q = z * y;
+    return q == x; 
+}
+
+/* Wrong order.  */
+__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
+    return y * x / y == x;
+}
+
+/* Wrong pattern.  */
+__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y, unsigned z) {
+    return x / y * z == x;
+}
+
+/* { dg-final {scan-tree-dump-times " % " 9 "optimized" } } */

base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
-- 
2.31.1

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Richard Biener]

On Wed, Jul 27, 2022 at 9:57 PM Sam Feifer <sfeifer@redhat.com> wrote:
>
>
>> _Complex int are strange beasts, I'd simply avoid the transform for them.
>>
>
> I added to the match.pd rule to not simplify if the operands are complex. There is now a test case for complex types to make sure they do not simplify. I had to move the "dg-do run" test to g++.dg to accommodate the complex type function that is included (even though there isn't a runtime test for complex types).
>
>> Can you please move the pattern next to the existing div/mod patterns,
>> like after the related
>>
>
> done :)
>
>> /* Simplify (A / B) * B + (A % B) -> A.  */
>> (for div (trunc_div ceil_div floor_div round_div)
>>      mod (trunc_mod ceil_mod floor_mod round_mod)
>>   (simplify
>>    (plus:c (mult:c (div @0 @1) @1) (mod @0 @1))
>>    @0))
>>
>> pattern?
>>
>> +/* x / y * y == x -> x % y == 0.  */
>> +(simplify
>> +  (eq (mult (trunc_div @0 @1) @1) @0)
>> +  (eq (trunc_mod @0 @1) { build_zero_cst TREE_TYPE(@0); }))
>>
>> there are parens missing around the TREE_TYPE (@0), how did you test
>> the patch?  You probably want :s on the trunc_div and as Andrew said
>> :c on the eq and the mult.
>
>
> I made those changes to the rule. The rule worked without the parentheses, which is probably why I didn't notice they were missing. Attached is an updated patch file.

+/* x / y * y == x -> x % y == 0.  */
+(simplify
+  (eq:c (mult:c (trunc_div:s @0 @1) @1) @0)
+  (if (TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE
+       && TREE_CODE (TREE_TYPE (@1)) != COMPLEX_TYPE)

Testing this only for @0 is enough, we don't allow mixed types for
trunc_div or mult.

+    (eq (trunc_mod @0 @1) { build_zero_cst (TREE_TYPE(@0)); })))

space before (@0) in 'TREE_TYPE(@0)'

OK with those changes.

Thanks,
Richard.



> Thanks
> -Sam
>
>>
>> Richard.
>>
>> > Thanks
>> > -Sam
>> >
>> >
>> > > For vector try (which works for both the C and C++ front-end):
>> > > #define vector __attribute__((vector_size(4*sizeof(int)) ))
>> > > vector int f(vector int x, vector int y)
>> > > {
>> > >   return x == x / y * y;
>> > > }
>> > >
>> > > That is for the vector case, == still returns a vector type.
>> > >
>> > > Thanks,
>> > > Andrew Pinski
>> > >
>> > > >
>> > > > Thanks
>> > > > -Sam
>> > > >
>> > > >> Thanks,
>> > > >> Andrew Pinski
>> > > >>
>> > > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c
>> > > b/gcc/testsuite/gcc.dg/pr104992-1.c
>> > > >> > new file mode 100644
>> > > >> > index 00000000000..a80e5e180ce
>> > > >> > --- /dev/null
>> > > >> > +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
>> > > >> > @@ -0,0 +1,30 @@
>> > > >> > +/* PR tree-optimization/104992 */
>> > > >> > +/* { dg-do run } */
>> > > >> > +/* { dg-options "-O2"} */
>> > > >> > +
>> > > >> > +#include "pr104992.c"
>> > > >> > +
>> > > >> > +int main () {
>> > > >> > +
>> > > >> > +    /* Should be true.  */
>> > > >> > +    if (!foo(6, 3)
>> > > >> > +        || !bar(12, 2)
>> > > >> > +        || !baz(34, 17)
>> > > >> > +        || !qux(50, 10)
>> > > >> > +        || !fred(16, 8)
>> > > >> > +        || !baz(-9, 3)
>> > > >> > +        || !baz(9, -3)
>> > > >> > +        || !baz(-9, -3)
>> > > >> > +        ) {
>> > > >> > +            __builtin_abort();
>> > > >> > +         }
>> > > >> > +
>> > > >> > +    /* Should be false.  */
>> > > >> > +    if (foo(5, 30)
>> > > >> > +        || bar(72, 27)
>> > > >> > +        || baz(42, 15)) {
>> > > >> > +            __builtin_abort();
>> > > >> > +        }
>> > > >> > +
>> > > >> > +    return 0;
>> > > >> > +}
>> > > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992.c
>> > > b/gcc/testsuite/gcc.dg/pr104992.c
>> > > >> > new file mode 100644
>> > > >> > index 00000000000..b4b0ca53118
>> > > >> > --- /dev/null
>> > > >> > +++ b/gcc/testsuite/gcc.dg/pr104992.c
>> > > >> > @@ -0,0 +1,35 @@
>> > > >> > +/* PR tree-optimization/104992 */
>> > > >> > +/* { dg-do compile } */
>> > > >> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> > > >> > +
>> > > >> > +/* Form from PR.  */
>> > > >> > +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
>> > > >> > +{
>> > > >> > +    return x / y * y == x;
>> > > >> > +}
>> > > >> > +
>> > > >> > +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
>> > > >> > +    return x == x / y * y;
>> > > >> > +}
>> > > >> > +
>> > > >> > +/* Signed test case.  */
>> > > >> > +__attribute__((noipa)) unsigned baz (int x, int y) {
>> > > >> > +    return x / y * y == x;
>> > > >> > +}
>> > > >> > +
>> > > >> > +/* Changed order.  */
>> > > >> > +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
>> > > >> > +    return y * (x / y) == x;
>> > > >> > +}
>> > > >> > +
>> > > >> > +/* Wrong order.  */
>> > > >> > +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
>> > > >> > +    return y * x / y == x;
>> > > >> > +}
>> > > >> > +
>> > > >> > +/* Wrong pattern.  */
>> > > >> > +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y,
>> > > unsigned z) {
>> > > >> > +    return x / y * z == x;
>> > > >> > +}
>> > > >> > +
>> > > >> > +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
>> > > >> >
>> > > >> > base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
>> > > >> > --
>> > > >> > 2.31.1
>> > > >> >
>> > > >>
>> > >
>> > >
>>

Re: [PATCH] match.pd: Add new division pattern [PR104992]

[Sam Feifer]

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

Here is the patch that I pushed. Thanks for the feedback.

Thanks
-Sam

On Thu, Jul 28, 2022 at 3:03 AM Richard Biener <richard.guenther@gmail.com>
wrote:

> On Wed, Jul 27, 2022 at 9:57 PM Sam Feifer <sfeifer@redhat.com> wrote:
> >
> >
> >> _Complex int are strange beasts, I'd simply avoid the transform for
> them.
> >>
> >
> > I added to the match.pd rule to not simplify if the operands are
> complex. There is now a test case for complex types to make sure they do
> not simplify. I had to move the "dg-do run" test to g++.dg to accommodate
> the complex type function that is included (even though there isn't a
> runtime test for complex types).
> >
> >> Can you please move the pattern next to the existing div/mod patterns,
> >> like after the related
> >>
> >
> > done :)
> >
> >> /* Simplify (A / B) * B + (A % B) -> A.  */
> >> (for div (trunc_div ceil_div floor_div round_div)
> >>      mod (trunc_mod ceil_mod floor_mod round_mod)
> >>   (simplify
> >>    (plus:c (mult:c (div @0 @1) @1) (mod @0 @1))
> >>    @0))
> >>
> >> pattern?
> >>
> >> +/* x / y * y == x -> x % y == 0.  */
> >> +(simplify
> >> +  (eq (mult (trunc_div @0 @1) @1) @0)
> >> +  (eq (trunc_mod @0 @1) { build_zero_cst TREE_TYPE(@0); }))
> >>
> >> there are parens missing around the TREE_TYPE (@0), how did you test
> >> the patch?  You probably want :s on the trunc_div and as Andrew said
> >> :c on the eq and the mult.
> >
> >
> > I made those changes to the rule. The rule worked without the
> parentheses, which is probably why I didn't notice they were missing.
> Attached is an updated patch file.
>
> +/* x / y * y == x -> x % y == 0.  */
> +(simplify
> +  (eq:c (mult:c (trunc_div:s @0 @1) @1) @0)
> +  (if (TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE
> +       && TREE_CODE (TREE_TYPE (@1)) != COMPLEX_TYPE)
>
> Testing this only for @0 is enough, we don't allow mixed types for
> trunc_div or mult.
>
> +    (eq (trunc_mod @0 @1) { build_zero_cst (TREE_TYPE(@0)); })))
>
> space before (@0) in 'TREE_TYPE(@0)'
>
> OK with those changes.
>
> Thanks,
> Richard.
>
>
>
> > Thanks
> > -Sam
> >
> >>
> >> Richard.
> >>
> >> > Thanks
> >> > -Sam
> >> >
> >> >
> >> > > For vector try (which works for both the C and C++ front-end):
> >> > > #define vector __attribute__((vector_size(4*sizeof(int)) ))
> >> > > vector int f(vector int x, vector int y)
> >> > > {
> >> > >   return x == x / y * y;
> >> > > }
> >> > >
> >> > > That is for the vector case, == still returns a vector type.
> >> > >
> >> > > Thanks,
> >> > > Andrew Pinski
> >> > >
> >> > > >
> >> > > > Thanks
> >> > > > -Sam
> >> > > >
> >> > > >> Thanks,
> >> > > >> Andrew Pinski
> >> > > >>
> >> > > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992-1.c
> >> > > b/gcc/testsuite/gcc.dg/pr104992-1.c
> >> > > >> > new file mode 100644
> >> > > >> > index 00000000000..a80e5e180ce
> >> > > >> > --- /dev/null
> >> > > >> > +++ b/gcc/testsuite/gcc.dg/pr104992-1.c
> >> > > >> > @@ -0,0 +1,30 @@
> >> > > >> > +/* PR tree-optimization/104992 */
> >> > > >> > +/* { dg-do run } */
> >> > > >> > +/* { dg-options "-O2"} */
> >> > > >> > +
> >> > > >> > +#include "pr104992.c"
> >> > > >> > +
> >> > > >> > +int main () {
> >> > > >> > +
> >> > > >> > +    /* Should be true.  */
> >> > > >> > +    if (!foo(6, 3)
> >> > > >> > +        || !bar(12, 2)
> >> > > >> > +        || !baz(34, 17)
> >> > > >> > +        || !qux(50, 10)
> >> > > >> > +        || !fred(16, 8)
> >> > > >> > +        || !baz(-9, 3)
> >> > > >> > +        || !baz(9, -3)
> >> > > >> > +        || !baz(-9, -3)
> >> > > >> > +        ) {
> >> > > >> > +            __builtin_abort();
> >> > > >> > +         }
> >> > > >> > +
> >> > > >> > +    /* Should be false.  */
> >> > > >> > +    if (foo(5, 30)
> >> > > >> > +        || bar(72, 27)
> >> > > >> > +        || baz(42, 15)) {
> >> > > >> > +            __builtin_abort();
> >> > > >> > +        }
> >> > > >> > +
> >> > > >> > +    return 0;
> >> > > >> > +}
> >> > > >> > diff --git a/gcc/testsuite/gcc.dg/pr104992.c
> >> > > b/gcc/testsuite/gcc.dg/pr104992.c
> >> > > >> > new file mode 100644
> >> > > >> > index 00000000000..b4b0ca53118
> >> > > >> > --- /dev/null
> >> > > >> > +++ b/gcc/testsuite/gcc.dg/pr104992.c
> >> > > >> > @@ -0,0 +1,35 @@
> >> > > >> > +/* PR tree-optimization/104992 */
> >> > > >> > +/* { dg-do compile } */
> >> > > >> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> >> > > >> > +
> >> > > >> > +/* Form from PR.  */
> >> > > >> > +__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
> >> > > >> > +{
> >> > > >> > +    return x / y * y == x;
> >> > > >> > +}
> >> > > >> > +
> >> > > >> > +__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
> >> > > >> > +    return x == x / y * y;
> >> > > >> > +}
> >> > > >> > +
> >> > > >> > +/* Signed test case.  */
> >> > > >> > +__attribute__((noipa)) unsigned baz (int x, int y) {
> >> > > >> > +    return x / y * y == x;
> >> > > >> > +}
> >> > > >> > +
> >> > > >> > +/* Changed order.  */
> >> > > >> > +__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
> >> > > >> > +    return y * (x / y) == x;
> >> > > >> > +}
> >> > > >> > +
> >> > > >> > +/* Wrong order.  */
> >> > > >> > +__attribute__((noipa)) unsigned fred (unsigned x, unsigned y)
> {
> >> > > >> > +    return y * x / y == x;
> >> > > >> > +}
> >> > > >> > +
> >> > > >> > +/* Wrong pattern.  */
> >> > > >> > +__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y,
> >> > > unsigned z) {
> >> > > >> > +    return x / y * z == x;
> >> > > >> > +}
> >> > > >> > +
> >> > > >> > +/* { dg-final {scan-tree-dump-times " % " 4 "optimized" } } */
> >> > > >> >
> >> > > >> > base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
> >> > > >> > --
> >> > > >> > 2.31.1
> >> > > >> >
> >> > > >>
> >> > >
> >> > >
> >>
>
>

[-- Attachment #2: 0001-match.pd-Add-new-division-pattern-PR104992.patch --]
[-- Type: text/x-patch, Size: 4087 bytes --]

From fdabed7b0b37c02c8fb711e0d30938fae2a1ccd8 Mon Sep 17 00:00:00 2001
From: Sam Feifer <sfeifer@redhat.com>
Date: Fri, 29 Jul 2022 09:44:48 -0400
Subject: [PATCH] match.pd: Add new division pattern [PR104992]

This patch fixes a missed optimization in match.pd. It takes the pattern,
x / y * y == x, and optimizes it to x % y == 0. This produces fewer
instructions. This simplification does not happen for complex types.

This patch also adds tests for the optimization rule.

Bootstrapped/regtested on x86_64-pc-linux-gnu.

	PR tree-optimization/104992

gcc/ChangeLog:

	* match.pd (x / y * y == x): New simplification.

gcc/testsuite/ChangeLog:

	* g++.dg/pr104992-1.C: New test.
	* gcc.dg/pr104992.c: New test.
---
 gcc/match.pd                      |  6 ++++
 gcc/testsuite/g++.dg/pr104992-1.C | 30 ++++++++++++++++
 gcc/testsuite/gcc.dg/pr104992.c   | 57 +++++++++++++++++++++++++++++++
 3 files changed, 93 insertions(+)
 create mode 100644 gcc/testsuite/g++.dg/pr104992-1.C
 create mode 100644 gcc/testsuite/gcc.dg/pr104992.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 330c1db0c8e..562138a8034 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3982,6 +3982,12 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (plus:c (mult:c (div @0 @1) @1) (mod @0 @1))
    @0))
 
+/* x / y * y == x -> x % y == 0.  */
+(simplify
+  (eq:c (mult:c (trunc_div:s @0 @1) @1) @0)
+  (if (TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE)
+    (eq (trunc_mod @0 @1) { build_zero_cst (TREE_TYPE (@0)); })))
+
 /* ((X /[ex] A) +- B) * A  -->  X +- A * B.  */
 (for op (plus minus)
  (simplify
diff --git a/gcc/testsuite/g++.dg/pr104992-1.C b/gcc/testsuite/g++.dg/pr104992-1.C
new file mode 100644
index 00000000000..f5696b245ac
--- /dev/null
+++ b/gcc/testsuite/g++.dg/pr104992-1.C
@@ -0,0 +1,30 @@
+/* PR tree-optimization/104992 */
+/* { dg-do run } */
+/* { dg-options "-O2"} */
+
+#include "../gcc.dg/pr104992.c"
+
+int main () {
+
+    /* Should be true.  */
+    if (!foo(6, 3)
+        || !bar(12, 2)
+        || !baz(34, 17)
+        || !qux(50, 10)
+        || !fred(16, 8)
+        || !baz(-9, 3)
+        || !baz(9, -3)
+        || !baz(-9, -3)
+        ) {
+            __builtin_abort();
+         }
+    
+    /* Should be false.  */
+    if (foo(5, 30)
+        || bar(72, 27)
+        || baz(42, 15)) {
+            __builtin_abort();
+        }
+    
+    return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/pr104992.c b/gcc/testsuite/gcc.dg/pr104992.c
new file mode 100644
index 00000000000..b9d91a13ad8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr104992.c
@@ -0,0 +1,57 @@
+/* PR tree-optimization/104992 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#define vector __attribute__((vector_size(4*sizeof(int))))
+
+/* Form from PR.  */
+__attribute__((noipa)) unsigned foo(unsigned x, unsigned y)
+{
+    return x / y * y == x;
+}
+
+__attribute__((noipa)) unsigned bar(unsigned x, unsigned y) {
+    return x == x / y * y;
+}
+
+/* Signed test case.  */
+__attribute__((noipa)) unsigned baz (int x, int y) {
+    return x / y * y == x;
+}
+
+/* Changed order.  */
+__attribute__((noipa)) unsigned qux (unsigned x, unsigned y) {
+    return y * (x / y) == x;
+}
+
+/* Test for forward propogation.  */
+__attribute__((noipa)) unsigned corge(unsigned x, unsigned y) {
+    int z = x / y;
+    int q = z * y;
+    return q == x; 
+}
+
+/* Test vector case.  */
+__attribute__((noipa)) vector int thud(vector int x, vector int y) {
+    return x / y * y == x;
+}
+
+/* Complex type should not simplify because mod is different.  */
+__attribute__((noipa)) int goo(_Complex int x, _Complex int y)
+{
+    _Complex int z = x / y;
+    _Complex int q = z * y;
+    return q == x; 
+}
+
+/* Wrong order.  */
+__attribute__((noipa)) unsigned fred (unsigned x, unsigned y) {
+    return y * x / y == x;
+}
+
+/* Wrong pattern.  */
+__attribute__((noipa)) unsigned waldo (unsigned x, unsigned y, unsigned z) {
+    return x / y * z == x;
+}
+
+/* { dg-final {scan-tree-dump-times " % " 9 "optimized" } } */

base-commit: 6e0ca3fe88d8f98ba6b4009c9483e87afbcf4ee8
-- 
2.31.1