On Fri, Jul 19, 2024 at 7:19 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&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_eikag...@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
>
