On Thu, Jul 18, 2024 at 6:25 AM Richard Biener
<richard.guent...@gmail.com> wrote:
>
> On Wed, Jul 17, 2024 at 1:29 PM Eikansh Gupta <quic_eikag...@quicinc.com>
> wrote:
> >
> > Min and max could be optimized if both operands are defined by
> > (same) variable restricted by an and(&). For signed types,
> > optimization can be done when both constant have same sign bit.
> > The patch also adds optimization for specific case of min/max(a, a&1).
> >
> > This patch adds match pattern for:
> >
> > max (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST1
> > min (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST0
> > min (a, a & 1) --> a & 1
> > max (a, a & 1) --> a
> >
> > PR tree-optimization/109878
> >
> > gcc/ChangeLog:
> >
> > * match.pd min/max (a & CST0, a & CST1): New pattern.
> > min/max (a, a & 1): New pattern.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/pr109878.c: New test.
> > * gcc.dg/tree-ssa/pr109878-1.c: New test.
> > * gcc.dg/tree-ssa/pr109878-2.c: New test.
> > * gcc.dg/tree-ssa/pr109878-3.c: New test.
> >
> > Signed-off-by: Eikansh Gupta <quic_eikag...@quicinc.com>
> > ---
> > gcc/match.pd | 22 ++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c | 64 ++++++++++++++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c | 31 +++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c | 26 +++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/pr109878.c | 64 ++++++++++++++++++++++
> > 5 files changed, 207 insertions(+)
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878.c
> >
> > diff --git a/gcc/match.pd b/gcc/match.pd
> > index 24a0bbead3e..029ec0b487f 100644
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -4310,6 +4310,28 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> > @0
> > @2)))
> >
> > +/* min (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST0 */
> > +/* max (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST1 */
> > +/* If signed a, then both the constants should have same sign. */
> > +(for minmax (min max)
> > + (simplify
> > + (minmax:c (bit_and@3 @0 INTEGER_CST@1) (bit_and@4 @0 INTEGER_CST@2))
>
> The :c on minmax looks unnecessary
It is necessary but only because of the way the result is used.
Eikansh is rewriting the patch to be able to remove the :c here
though.
>
> OK with removing that.
>
> Richard.
>
> > + (if (TYPE_UNSIGNED (type)
> > + || ((tree_int_cst_sgn (@1) <= 0) == (tree_int_cst_sgn (@2) <= 0)))
> > + (if ((wi::to_wide (@1) & wi::to_wide (@2))
> > + == ((minmax == MIN_EXPR) ? wi::to_wide (@1) : wi::to_wide (@2)))
> > + @3))))
> > +
> > +/* min (a, a & 1) --> a & 1 */
> > +/* max (a, a & 1) --> a */
> > +(for minmax (min max)
> > + (simplify
> > + (minmax:c @0 (bit_and@1 @0 integer_onep))
> > + (if (TYPE_UNSIGNED(type))
> > + (if (minmax == MIN_EXPR)
> > + @1
> > + @0))))
We also noticed that this can be done with any constant and not just
`1` . Eikansh will post a new patch soon.
Thanks,
Andrew Pinski
> > +
> > /* Simplify min (&var[off0], &var[off1]) etc. depending on whether
> > the addresses are known to be less, equal or greater. */
> > (for minmax (min max)
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c
> > new file mode 100644
> > index 00000000000..509e59adea1
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c
> > @@ -0,0 +1,64 @@
> > +/* PR tree-optimization/109878 */
> > +/* { dg-do compile } */
> > +/* { dg-options "-O1 -fdump-tree-optimized" } */
> > +
> > +/* All the constant pair <cst0, cst1> used here satisfy the condition:
> > + (cst0 & cst1 == cst0) || (cst0 & cst1 == cst1).
> > + If the above condition is true, then MIN_EXPR is not needed. */
> > +int min_and(int a, int b) {
> > + b = a & 3;
> > + a = a & 1;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +int min_and1(int a, int b) {
> > + b = a & 3;
> > + a = a & 15;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +int min_and2(int a, int b) {
> > + b = a & -7;
> > + a = a & -3;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +int min_and3(int a, int b) {
> > + b = a & -5;
> > + a = a & -13;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* When constants are of opposite signs, the simplification will only
> > + work for unsigned types. */
> > +unsigned int min_and4(unsigned int a, unsigned int b) {
> > + b = a & 3;
> > + a = a & -5;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +unsigned int min_and5(unsigned int a, unsigned int b) {
> > + b = a & -3;
> > + a = a & 5;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not " MIN_EXPR " "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c
> > new file mode 100644
> > index 00000000000..62846d5d784
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c
> > @@ -0,0 +1,31 @@
> > +/* PR tree-optimization/109878 */
> > +/* { dg-do compile } */
> > +/* { dg-options "-O1 -fdump-tree-optimized" } */
> > +
> > +/* The testcases here should not get optimized with the patch.
> > + For constant pair <cst0, cst1> the condition:
> > + (cst0 & cst1 == cst0) || (cst0 & cst1 == cst1)
> > + is false for the constants used here. */
> > +int max_and(int a, int b) {
> > +
> > + b = a & 3;
> > + a = a & 5;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* The constants in this function satisfy the condition but a is signed.
> > + For signed types both the constants should have same sign. */
> > +int min_and(int a, int b) {
> > + b = a & 1;
> > + a = a & -3;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump " MIN_EXPR " "optimized" } } */
> > +/* { dg-final { scan-tree-dump " MAX_EXPR " "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c
> > new file mode 100644
> > index 00000000000..c0b79ae4096
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c
> > @@ -0,0 +1,26 @@
> > +/* PR tree-optimization/109878 */
> > +/* { dg-do compile } */
> > +/* { dg-options "-O1 -fdump-tree-optimized" } */
> > +
> > +/* For unsigned types, min(a, a&1) should be simplified to a&1 and
> > + should not generate MIN_EXPR. */
> > +unsigned int min_1(unsigned int a, unsigned int b) {
> > + b = a & 1;
> > + if (b < a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* For unsigned types, max(a, a&1) should be simplified to a and
> > + should not generate MAX_EXPR. */
> > +unsigned int max_1(unsigned int a, unsigned int b) {
> > + b = a & 1;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not " MIN_EXPR " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " MAX_EXPR " "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/pr109878.c
> > new file mode 100644
> > index 00000000000..6f13bafcf14
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878.c
> > @@ -0,0 +1,64 @@
> > +/* PR tree-optimization/109878 */
> > +/* { dg-do compile } */
> > +/* { dg-options "-O1 -fdump-tree-optimized" } */
> > +
> > +/* All the constant pair <cst0, cst1> used here satisfy the condition:
> > + (cst0 & cst1 == cst0) || (cst0 & cst1 == cst1).
> > + If the above condition is true, then MAX_EXPR is not needed. */
> > +int max_and(int a, int b) {
> > + b = a & 3;
> > + a = a & 1;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +int max_and1(int a, int b) {
> > + b = a & 3;
> > + a = a & 15;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +int max_and2(int a, int b) {
> > + b = a & -7;
> > + a = a & -3;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +int max_and3(int a, int b) {
> > + b = a & -5;
> > + a = a & -13;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* When constants are of opposite signs, the simplification will only
> > + work for unsigned types. */
> > +unsigned int max_and4(unsigned int a, unsigned int b) {
> > + b = a & 3;
> > + a = a & -5;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +unsigned int max_and5(unsigned int a, unsigned int b) {
> > + b = a & -3;
> > + a = a & 5;
> > + if (b > a)
> > + return b;
> > + else
> > + return a;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not " MAX_EXPR " "optimized" } } */
> > --
> > 2.17.1
> >
