MATCH: Support `(a != (CST+1)) & (a > CST)` optimizations
Checks
Commit Message
Even though this is done via reassocation, match can support
these with a simple change to detect that the difference is just
one. This allows to optimize these earlier and even during phiopt
for an example.
This patch adds the following cases:
(a != (CST+1)) & (a > CST) -> a > (CST+1)
(a != (CST-1)) & (a < CST) -> a < (CST-1)
(a == (CST-1)) | (a >= CST) -> a >= (CST-1)
(a == (CST+1)) | (a <= CST) -> a <= (CST+1)
Canonicalizations of comparisons causes this case to show up more.
OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
PR tree-optimization/106164
gcc/ChangeLog:
* match.pd (`(X CMP1 CST1) AND/IOR (X CMP2 CST2)`):
Expand to support constants that are off by one.
gcc/testsuite/ChangeLog:
* gcc.dg/pr21643.c: Update test now that match does
the combing of the comparisons.
* gcc.dg/tree-ssa/cmpbit-5.c: New test.
* gcc.dg/tree-ssa/phi-opt-35.c: New test.
---
gcc/match.pd | 44 ++++++++++++++++++-
gcc/testsuite/gcc.dg/pr21643.c | 6 ++-
gcc/testsuite/gcc.dg/tree-ssa/cmpbit-5.c | 51 ++++++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/phi-opt-35.c | 13 ++++++
4 files changed, 111 insertions(+), 3 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cmpbit-5.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-35.c
Comments
On Thu, Sep 14, 2023 at 7:34 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Even though this is done via reassocation, match can support
> these with a simple change to detect that the difference is just
> one. This allows to optimize these earlier and even during phiopt
> for an example.
>
> This patch adds the following cases:
> (a != (CST+1)) & (a > CST) -> a > (CST+1)
> (a != (CST-1)) & (a < CST) -> a < (CST-1)
> (a == (CST-1)) | (a >= CST) -> a >= (CST-1)
> (a == (CST+1)) | (a <= CST) -> a <= (CST+1)
>
> Canonicalizations of comparisons causes this case to show up more.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
OK.
> PR tree-optimization/106164
>
> gcc/ChangeLog:
>
> * match.pd (`(X CMP1 CST1) AND/IOR (X CMP2 CST2)`):
> Expand to support constants that are off by one.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/pr21643.c: Update test now that match does
> the combing of the comparisons.
> * gcc.dg/tree-ssa/cmpbit-5.c: New test.
> * gcc.dg/tree-ssa/phi-opt-35.c: New test.
> ---
> gcc/match.pd | 44 ++++++++++++++++++-
> gcc/testsuite/gcc.dg/pr21643.c | 6 ++-
> gcc/testsuite/gcc.dg/tree-ssa/cmpbit-5.c | 51 ++++++++++++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/phi-opt-35.c | 13 ++++++
> 4 files changed, 111 insertions(+), 3 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cmpbit-5.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-35.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 7ecf5568599..07ffd831132 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2970,10 +2970,20 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> && operand_equal_p (@1, @2)))
> (with
> {
> + bool one_before = false;
> + bool one_after = false;
> int cmp = 0;
> if (TREE_CODE (@1) == INTEGER_CST
> && TREE_CODE (@2) == INTEGER_CST)
> - cmp = tree_int_cst_compare (@1, @2);
> + {
> + cmp = tree_int_cst_compare (@1, @2);
> + if (cmp < 0
> + && wi::to_wide (@1) == wi::to_wide (@2) - 1)
> + one_before = true;
> + if (cmp > 0
> + && wi::to_wide (@1) == wi::to_wide (@2) + 1)
> + one_after = true;
> + }
> bool val;
> switch (code2)
> {
> @@ -2998,6 +3008,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> && code2 == LE_EXPR
> && cmp == 0)
> (lt @0 @1))
> + /* (a != (b+1)) & (a > b) -> a > (b+1) */
> + (if (code1 == NE_EXPR
> + && code2 == GT_EXPR
> + && one_after)
> + (gt @0 @1))
> + /* (a != (b-1)) & (a < b) -> a < (b-1) */
> + (if (code1 == NE_EXPR
> + && code2 == LT_EXPR
> + && one_before)
> + (lt @0 @1))
> )
> )
> )
> @@ -3069,10 +3089,20 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> && operand_equal_p (@1, @2)))
> (with
> {
> + bool one_before = false;
> + bool one_after = false;
> int cmp = 0;
> if (TREE_CODE (@1) == INTEGER_CST
> && TREE_CODE (@2) == INTEGER_CST)
> - cmp = tree_int_cst_compare (@1, @2);
> + {
> + cmp = tree_int_cst_compare (@1, @2);
> + if (cmp < 0
> + && wi::to_wide (@1) == wi::to_wide (@2) - 1)
> + one_before = true;
> + if (cmp > 0
> + && wi::to_wide (@1) == wi::to_wide (@2) + 1)
> + one_after = true;
> + }
> bool val;
> switch (code2)
> {
> @@ -3097,6 +3127,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> && code2 == LT_EXPR
> && cmp == 0)
> (le @0 @1))
> + /* (a == (b-1)) | (a >= b) -> a >= (b-1) */
> + (if (code1 == EQ_EXPR
> + && code2 == GE_EXPR
> + && one_before)
> + (ge @0 @1))
> + /* (a == (b+1)) | (a <= b) -> a <= (b-1) */
> + (if (code1 == EQ_EXPR
> + && code2 == LE_EXPR
> + && one_after)
> + (le @0 @1))
> )
> )
> )
> diff --git a/gcc/testsuite/gcc.dg/pr21643.c b/gcc/testsuite/gcc.dg/pr21643.c
> index 4e7f93d351a..42517b5af1e 100644
> --- a/gcc/testsuite/gcc.dg/pr21643.c
> +++ b/gcc/testsuite/gcc.dg/pr21643.c
> @@ -86,4 +86,8 @@ f9 (unsigned char c)
> return 1;
> }
>
> -/* { dg-final { scan-tree-dump-times "Optimizing range tests c_\[0-9\]*.D. -.0, 31. and -.32, 32.\[\n\r\]* into" 6 "reassoc1" } } */
> +/* Note with match being able to simplify this, optimizing range tests is no longer needed here. */
> +/* Equivalence: _7 | _2 -> c_5(D) <= 32 */
> +/* old test: dg-final scan-tree-dump-times "Optimizing range tests c_\[0-9\]*.D. -.0, 31. and -.32, 32.\[\n\r\]* into" 6 "reassoc1" */
> +/* { dg-final { scan-tree-dump-times "Equivalence: _\[0-9\]+ \\\| _\[0-9\]+ -> c_\[0-9\]+.D. <= 32" 5 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Equivalence: _\[0-9\]+ \& _\[0-9\]+ -> c_\[0-9\]+.D. > 32" 1 "reassoc1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cmpbit-5.c b/gcc/testsuite/gcc.dg/tree-ssa/cmpbit-5.c
> new file mode 100644
> index 00000000000..d81a129825b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/cmpbit-5.c
> @@ -0,0 +1,51 @@
> +/* PR tree-optimization/106164 */
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-forwprop1-details" } */
> +
> +
> +int f(int a)
> +{
> + int c = a != 2;
> + int d = a >= 2;
> + return c & d;
> +}
> +int g(int b)
> +{
> + int c = b != -1;
> + int d = b <= -1;
> + return c & d;
> +}
> +
> +
> +int g_(int e)
> +{
> + int c = e != -2;
> + int d = e <= -2;
> + return c & d;
> +}
> +
> +int f1(int x)
> +{
> + int c = x == 2;
> + int d = x <= 1;
> + return c | d;
> +}
> +int g1(int y)
> +{
> + int c = y == -1;
> + int d = y > -1;
> + return c | d;
> +}
> +int g1_(int z)
> +{
> + int c = z == -2;
> + int d = z >= -1;
> + return c | d;
> +}
> +
> +/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = a_\[0-9\]+.D. > 2" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = b_\[0-9\]+.D. < -1" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = e_\[0-9\]+.D. < -2" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = x_\[0-9\]+.D. <= 2" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = y_\[0-9\]+.D. >= -1" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = z_\[0-9\]+.D. >= -2" "forwprop1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-35.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-35.c
> new file mode 100644
> index 00000000000..c52c64c5524
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-35.c
> @@ -0,0 +1,13 @@
> +/* PR tree-optimization/106164 */
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-phiopt2" } */
> +
> +_Bool f2(int a)
> +{
> + if (a != 2)
> + return a > 1;
> + return 0;
> +}
> +/* phiopt2 should be able to optimize this to `a > 2` via match and simplify */
> +/* { dg-final { scan-tree-dump "_\[0-9\]+ = a_\[0-9\]+.D. > 2" "phiopt2" } } */
> +/* { dg-final { scan-tree-dump-not "a_\[0-9\]+.D. != 2" "phiopt2" } } */
> --
> 2.31.1
>
@@ -2970,10 +2970,20 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& operand_equal_p (@1, @2)))
(with
{
+ bool one_before = false;
+ bool one_after = false;
int cmp = 0;
if (TREE_CODE (@1) == INTEGER_CST
&& TREE_CODE (@2) == INTEGER_CST)
- cmp = tree_int_cst_compare (@1, @2);
+ {
+ cmp = tree_int_cst_compare (@1, @2);
+ if (cmp < 0
+ && wi::to_wide (@1) == wi::to_wide (@2) - 1)
+ one_before = true;
+ if (cmp > 0
+ && wi::to_wide (@1) == wi::to_wide (@2) + 1)
+ one_after = true;
+ }
bool val;
switch (code2)
{
@@ -2998,6 +3008,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& code2 == LE_EXPR
&& cmp == 0)
(lt @0 @1))
+ /* (a != (b+1)) & (a > b) -> a > (b+1) */
+ (if (code1 == NE_EXPR
+ && code2 == GT_EXPR
+ && one_after)
+ (gt @0 @1))
+ /* (a != (b-1)) & (a < b) -> a < (b-1) */
+ (if (code1 == NE_EXPR
+ && code2 == LT_EXPR
+ && one_before)
+ (lt @0 @1))
)
)
)
@@ -3069,10 +3089,20 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& operand_equal_p (@1, @2)))
(with
{
+ bool one_before = false;
+ bool one_after = false;
int cmp = 0;
if (TREE_CODE (@1) == INTEGER_CST
&& TREE_CODE (@2) == INTEGER_CST)
- cmp = tree_int_cst_compare (@1, @2);
+ {
+ cmp = tree_int_cst_compare (@1, @2);
+ if (cmp < 0
+ && wi::to_wide (@1) == wi::to_wide (@2) - 1)
+ one_before = true;
+ if (cmp > 0
+ && wi::to_wide (@1) == wi::to_wide (@2) + 1)
+ one_after = true;
+ }
bool val;
switch (code2)
{
@@ -3097,6 +3127,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& code2 == LT_EXPR
&& cmp == 0)
(le @0 @1))
+ /* (a == (b-1)) | (a >= b) -> a >= (b-1) */
+ (if (code1 == EQ_EXPR
+ && code2 == GE_EXPR
+ && one_before)
+ (ge @0 @1))
+ /* (a == (b+1)) | (a <= b) -> a <= (b-1) */
+ (if (code1 == EQ_EXPR
+ && code2 == LE_EXPR
+ && one_after)
+ (le @0 @1))
)
)
)
@@ -86,4 +86,8 @@ f9 (unsigned char c)
return 1;
}
-/* { dg-final { scan-tree-dump-times "Optimizing range tests c_\[0-9\]*.D. -.0, 31. and -.32, 32.\[\n\r\]* into" 6 "reassoc1" } } */
+/* Note with match being able to simplify this, optimizing range tests is no longer needed here. */
+/* Equivalence: _7 | _2 -> c_5(D) <= 32 */
+/* old test: dg-final scan-tree-dump-times "Optimizing range tests c_\[0-9\]*.D. -.0, 31. and -.32, 32.\[\n\r\]* into" 6 "reassoc1" */
+/* { dg-final { scan-tree-dump-times "Equivalence: _\[0-9\]+ \\\| _\[0-9\]+ -> c_\[0-9\]+.D. <= 32" 5 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Equivalence: _\[0-9\]+ \& _\[0-9\]+ -> c_\[0-9\]+.D. > 32" 1 "reassoc1" } } */
new file mode 100644
@@ -0,0 +1,51 @@
+/* PR tree-optimization/106164 */
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-forwprop1-details" } */
+
+
+int f(int a)
+{
+ int c = a != 2;
+ int d = a >= 2;
+ return c & d;
+}
+int g(int b)
+{
+ int c = b != -1;
+ int d = b <= -1;
+ return c & d;
+}
+
+
+int g_(int e)
+{
+ int c = e != -2;
+ int d = e <= -2;
+ return c & d;
+}
+
+int f1(int x)
+{
+ int c = x == 2;
+ int d = x <= 1;
+ return c | d;
+}
+int g1(int y)
+{
+ int c = y == -1;
+ int d = y > -1;
+ return c | d;
+}
+int g1_(int z)
+{
+ int c = z == -2;
+ int d = z >= -1;
+ return c | d;
+}
+
+/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = a_\[0-9\]+.D. > 2" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = b_\[0-9\]+.D. < -1" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = e_\[0-9\]+.D. < -2" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = x_\[0-9\]+.D. <= 2" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = y_\[0-9\]+.D. >= -1" "forwprop1" } } */
+/* { dg-final { scan-tree-dump "gimple_simplified to _\[0-9\]+ = z_\[0-9\]+.D. >= -2" "forwprop1" } } */
new file mode 100644
@@ -0,0 +1,13 @@
+/* PR tree-optimization/106164 */
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-phiopt2" } */
+
+_Bool f2(int a)
+{
+ if (a != 2)
+ return a > 1;
+ return 0;
+}
+/* phiopt2 should be able to optimize this to `a > 2` via match and simplify */
+/* { dg-final { scan-tree-dump "_\[0-9\]+ = a_\[0-9\]+.D. > 2" "phiopt2" } } */
+/* { dg-final { scan-tree-dump-not "a_\[0-9\]+.D. != 2" "phiopt2" } } */