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.

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


base-commit: 633e9920589ddfaf2d6da1c24ce99b18a2638db4
  

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
>
  

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

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

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

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

> _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
> > > >> >
> > > >>
> > >
> > >
>
>
  

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

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