Re: [PATCH] match.pd: Add new division pattern [PR104992]
gt; >> > + } > >> > > >> > + > >> > > >> > +/* 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 000..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 > >> > > >> > > >> > > >> > >> > > > >> > > > >> > > From fdabed7b0b37c02c8fb711e0d30938fae2a1ccd8 Mon Sep 17 00:00:00 2001 From: Sam Feifer 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 000..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 000..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
Re: [PATCH] match.pd: Add new division pattern [PR104992]
On Wed, Jul 27, 2022 at 9:57 PM Sam Feifer 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 000..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 000..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 /
Re: [PATCH] match.pd: Add new division pattern [PR104992]
> _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 000..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 000..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; > > > >
Re: [PATCH] match.pd: Add new division pattern [PR104992]
On Tue, Jul 26, 2022 at 4:32 PM Sam Feifer via Gcc-patches 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 000..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 000..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]
> > 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 000..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 000..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]
On Mon, Jul 25, 2022 at 1:59 PM Sam Feifer 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 000..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 000..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]
> 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 000..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 000..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]
On Mon, Jul 25, 2022 at 12:37 PM Sam Feifer via Gcc-patches 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 000..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 000..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 >
[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. 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 000..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 000..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