[v3] MATCH: Add simplification for MAX<a&CST0, a&CST1> and MIN<a&CST0, a&CST1> to match.pd [PR109878]
Commit Message
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
The v2 of the patch has been approved. Patch link:
https://gcc.gnu.org/pipermail/gcc-patches/2024-July/657801.html
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 <eikansh.gupta@oss.qualcomm.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
Comments
On Wed, May 6, 2026 at 5:43 AM Eikansh Gupta
<eikansh.gupta@oss.qualcomm.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
>
> The v2 of the patch has been approved. Patch link:
> https://gcc.gnu.org/pipermail/gcc-patches/2024-July/657801.html
Pushed now after a bootstrap/test on x86_64-linux-gnu.
With a slightly fixed up changelog part of the commit message.
Thanks,
Andrea
>
> 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 <eikansh.gupta@oss.qualcomm.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 7db8ce7580f..2333fb72fd2 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -5052,6 +5052,32 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> (if (!HONOR_NANS (@0))
> (neeq @0 @1))))
>
> +/* 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.34.1
>
@@ -5052,6 +5052,32 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (!HONOR_NANS (@0))
(neeq @0 @1))))
+/* 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)
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */