| Message ID | 20240719171835.21598-1-quic_eikagupt@quicinc.com |
|---|---|
| State | New |
| Headers | show |
| Series | [v2] MATCH: Add simplification for MAX<a&CST0, a&CST1> and MIN<a&CST0, a&CST1> to match.pd [PR109878] | expand |
A few ideas in case you want to generalize the transformation (these are not requirements to get your patch in, and this is not a review): On Fri, 19 Jul 2024, Eikansh Gupta wrote: > --- a/gcc/match.pd > +++ b/gcc/match.pd > @@ -4321,6 +4321,32 @@ 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 (bit_and@3 @0 INTEGER_CST@1) (bit_and@4 @0 INTEGER_CST@2)) > + (if (TYPE_UNSIGNED (type) > + || (tree_int_cst_sgn (@1) == tree_int_cst_sgn (@2))) > + (with { auto andvalue = wi::to_wide (@1) & wi::to_wide (@2); } > + (if (andvalue == ((minmax == MIN_EXPR) > + ? wi::to_wide (@1) : wi::to_wide (@2))) > + @3 > + (if (andvalue == ((minmax != MIN_EXPR) > + ? wi::to_wide (@1) : wi::to_wide (@2))) > + @4)))))) Since max(a&1,a&3) is a&3, I think in the signed case we could also replace max(a&N,a&3) with a&3 if N is 1 | sign-bit (i.e. -1u/2+2). Indeed, either a>=0 and a&N is a&1, or a<0 and a&N < 0 <= a&3. > +/* min (a, a & CST) --> a & CST */ > +/* max (a, a & CST) --> a */ > +(for minmax (min max) > + (simplify > + (minmax @0 (bit_and@1 @0 INTEGER_CST@2)) Why do you require that @2 be a constant? > + (if (TYPE_UNSIGNED(type)) > + (if (minmax == MIN_EXPR) > + @1 > + @0)))) Do we already have the corresponding transformations for comparisons? a&b <= a --> true (if unsigned) etc Ideally, we would have **1** transformation for max(X,Y) that tries to fold X<=Y and if it folds to true then simplifies to Y. This way the transformations would only need to be written for comparisons, not minmax.
On Fri, Jul 19, 2024 at 7:19 PM Eikansh Gupta <quic_eikagupt@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&CST). > > 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 & CST) --> a & CST > max (a, a & CST) --> a OK. Richard. > PR tree-optimization/109878 > > gcc/ChangeLog: > > * match.pd min/max (a & CST0, a & CST1): New pattern. > min/max (a, a & CST): New pattern. > > gcc/testsuite/ChangeLog: > > * 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. > * gcc.dg/tree-ssa/pr109878.c: New test. > > Signed-off-by: Eikansh Gupta <quic_eikagupt@quicinc.com> > --- > gcc/match.pd | 26 +++++++++ > 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 | 42 ++++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/pr109878.c | 64 ++++++++++++++++++++++ > 5 files changed, 227 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 cf359b0ec0f..dbaff6ab3da 100644 > --- a/gcc/match.pd > +++ b/gcc/match.pd > @@ -4321,6 +4321,32 @@ 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 (bit_and@3 @0 INTEGER_CST@1) (bit_and@4 @0 INTEGER_CST@2)) > + (if (TYPE_UNSIGNED (type) > + || (tree_int_cst_sgn (@1) == tree_int_cst_sgn (@2))) > + (with { auto andvalue = wi::to_wide (@1) & wi::to_wide (@2); } > + (if (andvalue == ((minmax == MIN_EXPR) > + ? wi::to_wide (@1) : wi::to_wide (@2))) > + @3 > + (if (andvalue == ((minmax != MIN_EXPR) > + ? wi::to_wide (@1) : wi::to_wide (@2))) > + @4)))))) > + > +/* min (a, a & CST) --> a & CST */ > +/* max (a, a & CST) --> a */ > +(for minmax (min max) > + (simplify > + (minmax @0 (bit_and@1 @0 INTEGER_CST@2)) > + (if (TYPE_UNSIGNED(type)) > + (if (minmax == MIN_EXPR) > + @1 > + @0)))) > + > /* 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..1503dcde1cb > --- /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..65966e1ebf3 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c > @@ -0,0 +1,42 @@ > +/* PR tree-optimization/109878 */ > +/* { dg-do compile } */ > +/* { dg-options "-O1 -fdump-tree-optimized" } */ > + > +/* For unsigned types, min(a, a&CST) should be simplified to a&CST 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; > +} > + > +unsigned int min_2(unsigned int a, unsigned int b) { > + b = a & 3; > + if (b < a) > + return b; > + else > + return a; > +} > + > +/* For unsigned types, max(a, a&CST) 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; > +} > + > +unsigned int max_2(unsigned int a, unsigned int b) { > + b = a & 3; > + 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 >
diff --git a/gcc/match.pd b/gcc/match.pd index cf359b0ec0f..dbaff6ab3da 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -4321,6 +4321,32 @@ 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 (bit_and@3 @0 INTEGER_CST@1) (bit_and@4 @0 INTEGER_CST@2)) + (if (TYPE_UNSIGNED (type) + || (tree_int_cst_sgn (@1) == tree_int_cst_sgn (@2))) + (with { auto andvalue = wi::to_wide (@1) & wi::to_wide (@2); } + (if (andvalue == ((minmax == MIN_EXPR) + ? wi::to_wide (@1) : wi::to_wide (@2))) + @3 + (if (andvalue == ((minmax != MIN_EXPR) + ? wi::to_wide (@1) : wi::to_wide (@2))) + @4)))))) + +/* min (a, a & CST) --> a & CST */ +/* max (a, a & CST) --> a */ +(for minmax (min max) + (simplify + (minmax @0 (bit_and@1 @0 INTEGER_CST@2)) + (if (TYPE_UNSIGNED(type)) + (if (minmax == MIN_EXPR) + @1 + @0)))) + /* 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..1503dcde1cb --- /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..65966e1ebf3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c @@ -0,0 +1,42 @@ +/* PR tree-optimization/109878 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-optimized" } */ + +/* For unsigned types, min(a, a&CST) should be simplified to a&CST 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; +} + +unsigned int min_2(unsigned int a, unsigned int b) { + b = a & 3; + if (b < a) + return b; + else + return a; +} + +/* For unsigned types, max(a, a&CST) 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; +} + +unsigned int max_2(unsigned int a, unsigned int b) { + b = a & 3; + 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" } } */
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&CST). 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 & CST) --> a & CST max (a, a & CST) --> a PR tree-optimization/109878 gcc/ChangeLog: * match.pd min/max (a & CST0, a & CST1): New pattern. min/max (a, a & CST): New pattern. gcc/testsuite/ChangeLog: * 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. * gcc.dg/tree-ssa/pr109878.c: New test. Signed-off-by: Eikansh Gupta <quic_eikagupt@quicinc.com> --- gcc/match.pd | 26 +++++++++ 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 | 42 ++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr109878.c | 64 ++++++++++++++++++++++ 5 files changed, 227 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