match.pd: Optimize (x & y) == x into (x & ~y) == 0 [PR94589]

Message ID 20210511073405.GE1179226@tucnak
State New
Headers show
Series
  • match.pd: Optimize (x & y) == x into (x & ~y) == 0 [PR94589]
Related show

Commit Message

H.J. Lu via Gcc-patches May 11, 2021, 7:34 a.m.
On Thu, May 06, 2021 at 09:42:41PM +0200, Marc Glisse wrote:
> We can probably do it in 2 steps, first something like

> 

> (for cmp (eq ne)

>  (simplify

>   (cmp (bit_and:c @0 @1) @0)

>   (cmp (@0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); })))

> 

> to get rid of the double use, and then simplify X&C==0 to X<=~C if C is a

> mask 111...000 (I thought we already had a function to detect such masks, or

> the 000...111, but I can't find them anymore).


Ok, here is the first step then.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Or should it have cmp:c too given that == and != are commutative too?

2021-05-11  Jakub Jelinek  <jakub@redhat.com>
	    Marc Glisse  <marc.glisse@inria.fr>

	PR tree-optimization/94589
	* match.pd ((X & Y) == Y -> (X & ~Y) == 0,
	(X | Y) == Y -> (X & ~Y) == 0): New GIMPLE simplifications.

	* gcc.dg/tree-ssa/pr94589-1.c: New test.



	Jakub

Comments

Marc Glisse May 11, 2021, 8:11 a.m. | #1
On Tue, 11 May 2021, Jakub Jelinek via Gcc-patches wrote:

> On Thu, May 06, 2021 at 09:42:41PM +0200, Marc Glisse wrote:

>> We can probably do it in 2 steps, first something like

>>

>> (for cmp (eq ne)

>>  (simplify

>>   (cmp (bit_and:c @0 @1) @0)

>>   (cmp (@0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); })))

>>

>> to get rid of the double use, and then simplify X&C==0 to X<=~C if C is a

>> mask 111...000 (I thought we already had a function to detect such masks, or

>> the 000...111, but I can't find them anymore).

>

> Ok, here is the first step then.

> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

>

> Or should it have cmp:c too given that == and != are commutative too?


Ah, yes, you are right, good point on the cmp:c, thank you.

> 2021-05-11  Jakub Jelinek  <jakub@redhat.com>

> 	    Marc Glisse  <marc.glisse@inria.fr>

>

> 	PR tree-optimization/94589

> 	* match.pd ((X & Y) == Y -> (X & ~Y) == 0,

                                ^

X?

> 	(X | Y) == Y -> (X & ~Y) == 0): New GIMPLE simplifications.

>

> 	* gcc.dg/tree-ssa/pr94589-1.c: New test.

>

> --- gcc/match.pd.jj	2021-04-27 14:46:56.583716888 +0200

> +++ gcc/match.pd	2021-05-10 22:31:49.726870421 +0200

> @@ -4764,6 +4764,18 @@ (define_operator_list COND_TERNARY

>   (cmp:c (bit_xor:c @0 @1) @0)

>   (cmp @1 { build_zero_cst (TREE_TYPE (@1)); }))

>

> +#if GIMPLE

> + /* (X & Y) == X becomes (X & ~Y) == 0.  */

> + (simplify

> +  (cmp (bit_and:c @0 @1) @0)

> +  (cmp (bit_and @0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); }))

> +

> + /* (X | Y) == Y becomes (X & ~Y) == 0.  */

> + (simplify

> +  (cmp (bit_ior:c @0 @1) @1)

> +  (cmp (bit_and @0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); }))

> +#endif

> +

>  /* (X ^ C1) op C2 can be rewritten as X op (C1 ^ C2).  */

>  (simplify

>   (cmp (convert?@3 (bit_xor @0 INTEGER_CST@1)) INTEGER_CST@2)

> --- gcc/testsuite/gcc.dg/tree-ssa/pr94589-1.c.jj	2021-05-10 22:36:10.574130179 +0200

> +++ gcc/testsuite/gcc.dg/tree-ssa/pr94589-1.c	2021-05-10 22:36:17.789054362 +0200

> @@ -0,0 +1,21 @@

> +/* PR tree-optimization/94589 */

> +/* { dg-do compile } */

> +/* { dg-options "-O2 -fdump-tree-optimized" } */

> +

> +int

> +foo (int x)

> +{

> +  return (x & 23) == x;

> +/* { dg-final { scan-tree-dump " & -24;" "optimized" } } */

> +/* { dg-final { scan-tree-dump-not " & 23;" "optimized" } } */

> +/* { dg-final { scan-tree-dump " == 0" "optimized" } } */

> +}

> +

> +int

> +bar (int x)

> +{

> +  return (x | 137) != 137;

> +/* { dg-final { scan-tree-dump " & -138;" "optimized" } } */

> +/* { dg-final { scan-tree-dump-not " \\| 137;" "optimized" } } */

> +/* { dg-final { scan-tree-dump " != 0" "optimized" } } */

> +}

>

>

> 	Jakub


-- 
Marc Glisse
Richard Biener May 11, 2021, 8:20 a.m. | #2
On Tue, 11 May 2021, Jakub Jelinek wrote:

> On Thu, May 06, 2021 at 09:42:41PM +0200, Marc Glisse wrote:

> > We can probably do it in 2 steps, first something like

> > 

> > (for cmp (eq ne)

> >  (simplify

> >   (cmp (bit_and:c @0 @1) @0)

> >   (cmp (@0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); })))

> > 

> > to get rid of the double use, and then simplify X&C==0 to X<=~C if C is a

> > mask 111...000 (I thought we already had a function to detect such masks, or

> > the 000...111, but I can't find them anymore).

> 

> Ok, here is the first step then.

> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

> 

> Or should it have cmp:c too given that == and != are commutative too?


I think so.  OK with that change.

Richard.

> 2021-05-11  Jakub Jelinek  <jakub@redhat.com>

> 	    Marc Glisse  <marc.glisse@inria.fr>

> 

> 	PR tree-optimization/94589

> 	* match.pd ((X & Y) == Y -> (X & ~Y) == 0,

> 	(X | Y) == Y -> (X & ~Y) == 0): New GIMPLE simplifications.

> 

> 	* gcc.dg/tree-ssa/pr94589-1.c: New test.

> 

> --- gcc/match.pd.jj	2021-04-27 14:46:56.583716888 +0200

> +++ gcc/match.pd	2021-05-10 22:31:49.726870421 +0200

> @@ -4764,6 +4764,18 @@ (define_operator_list COND_TERNARY

>    (cmp:c (bit_xor:c @0 @1) @0)

>    (cmp @1 { build_zero_cst (TREE_TYPE (@1)); }))

>  

> +#if GIMPLE

> + /* (X & Y) == X becomes (X & ~Y) == 0.  */

> + (simplify

> +  (cmp (bit_and:c @0 @1) @0)

> +  (cmp (bit_and @0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); }))

> +

> + /* (X | Y) == Y becomes (X & ~Y) == 0.  */

> + (simplify

> +  (cmp (bit_ior:c @0 @1) @1)

> +  (cmp (bit_and @0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); }))

> +#endif

> +

>   /* (X ^ C1) op C2 can be rewritten as X op (C1 ^ C2).  */

>   (simplify

>    (cmp (convert?@3 (bit_xor @0 INTEGER_CST@1)) INTEGER_CST@2)

> --- gcc/testsuite/gcc.dg/tree-ssa/pr94589-1.c.jj	2021-05-10 22:36:10.574130179 +0200

> +++ gcc/testsuite/gcc.dg/tree-ssa/pr94589-1.c	2021-05-10 22:36:17.789054362 +0200

> @@ -0,0 +1,21 @@

> +/* PR tree-optimization/94589 */

> +/* { dg-do compile } */

> +/* { dg-options "-O2 -fdump-tree-optimized" } */

> +

> +int

> +foo (int x)

> +{

> +  return (x & 23) == x;

> +/* { dg-final { scan-tree-dump " & -24;" "optimized" } } */

> +/* { dg-final { scan-tree-dump-not " & 23;" "optimized" } } */

> +/* { dg-final { scan-tree-dump " == 0" "optimized" } } */

> +}

> +

> +int

> +bar (int x)

> +{

> +  return (x | 137) != 137;

> +/* { dg-final { scan-tree-dump " & -138;" "optimized" } } */

> +/* { dg-final { scan-tree-dump-not " \\| 137;" "optimized" } } */

> +/* { dg-final { scan-tree-dump " != 0" "optimized" } } */

> +}

> 

> 

> 	Jakub

> 

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Patch

--- gcc/match.pd.jj	2021-04-27 14:46:56.583716888 +0200
+++ gcc/match.pd	2021-05-10 22:31:49.726870421 +0200
@@ -4764,6 +4764,18 @@  (define_operator_list COND_TERNARY
   (cmp:c (bit_xor:c @0 @1) @0)
   (cmp @1 { build_zero_cst (TREE_TYPE (@1)); }))
 
+#if GIMPLE
+ /* (X & Y) == X becomes (X & ~Y) == 0.  */
+ (simplify
+  (cmp (bit_and:c @0 @1) @0)
+  (cmp (bit_and @0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); }))
+
+ /* (X | Y) == Y becomes (X & ~Y) == 0.  */
+ (simplify
+  (cmp (bit_ior:c @0 @1) @1)
+  (cmp (bit_and @0 (bit_not! @1)) { build_zero_cst (TREE_TYPE (@0)); }))
+#endif
+
  /* (X ^ C1) op C2 can be rewritten as X op (C1 ^ C2).  */
  (simplify
   (cmp (convert?@3 (bit_xor @0 INTEGER_CST@1)) INTEGER_CST@2)
--- gcc/testsuite/gcc.dg/tree-ssa/pr94589-1.c.jj	2021-05-10 22:36:10.574130179 +0200
+++ gcc/testsuite/gcc.dg/tree-ssa/pr94589-1.c	2021-05-10 22:36:17.789054362 +0200
@@ -0,0 +1,21 @@ 
+/* PR tree-optimization/94589 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (int x)
+{
+  return (x & 23) == x;
+/* { dg-final { scan-tree-dump " & -24;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not " & 23;" "optimized" } } */
+/* { dg-final { scan-tree-dump " == 0" "optimized" } } */
+}
+
+int
+bar (int x)
+{
+  return (x | 137) != 137;
+/* { dg-final { scan-tree-dump " & -138;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\| 137;" "optimized" } } */
+/* { dg-final { scan-tree-dump " != 0" "optimized" } } */
+}