Add (1 << A) & 1) folding (PR middle-end/64309)

As discussed in the PR, this adds folding of (1 << A) & 1) if in
a eq/ne comparison.  The assembly diff on my x86_64 box is

 	movq	%rsp, %rbp
 	.cfi_def_cfa_register 6
 	movl	%edi, -4(%rbp)
-	movl	-4(%rbp), %eax
-	movl	$1, %edx
-	movl	%eax, %ecx
-	sarl	%cl, %edx
-	movl	%edx, %eax
-	andl	$1, %eax
-	testl	%eax, %eax
-	setne	%al
+	cmpl	$0, -4(%rbp)
+	sete	%al
 	movzbl	%al, %eax
 	popq	%rbp
 	.cfi_def_cfa 7, 8

Since this removes a shift, I was afraid that it could regress ubsan
sanitization, but luckily that is not the case and the shift diagnostics
seems to be intact.

It triggers several times during the bootstrap.

Bootstrapped/regtested on x86_64-linux + ppc64-linux, ok for trunk?

2014-12-16  Marek Polacek  <polacek@redhat.com>

	PR middle-end/64309
	* match.pd: Add ((1 << A) & 1) != 0 -> A == 0 and
	((1 << A) & 1) == 0 -> A != 0.

	* gcc.dg/pr64309.c: New test.


	Marek

On Tue, 16 Dec 2014, Marek Polacek wrote:

> As discussed in the PR, this adds folding of (1 << A) & 1) if in
> a eq/ne comparison.  The assembly diff on my x86_64 box is
> 
>  	movq	%rsp, %rbp
>  	.cfi_def_cfa_register 6
>  	movl	%edi, -4(%rbp)
> -	movl	-4(%rbp), %eax
> -	movl	$1, %edx
> -	movl	%eax, %ecx
> -	sarl	%cl, %edx
> -	movl	%edx, %eax
> -	andl	$1, %eax
> -	testl	%eax, %eax
> -	setne	%al
> +	cmpl	$0, -4(%rbp)
> +	sete	%al
>  	movzbl	%al, %eax
>  	popq	%rbp
>  	.cfi_def_cfa 7, 8
> 
> Since this removes a shift, I was afraid that it could regress ubsan
> sanitization, but luckily that is not the case and the shift diagnostics
> seems to be intact.
> 
> It triggers several times during the bootstrap.
> 
> Bootstrapped/regtested on x86_64-linux + ppc64-linux, ok for trunk?
> 
> 2014-12-16  Marek Polacek  <polacek@redhat.com>
> 
> 	PR middle-end/64309
> 	* match.pd: Add ((1 << A) & 1) != 0 -> A == 0 and
> 	((1 << A) & 1) == 0 -> A != 0.
> 
> 	* gcc.dg/pr64309.c: New test.
> 
> diff --git gcc/match.pd gcc/match.pd
> index 083d65f..47b01eb 100644
> --- gcc/match.pd
> +++ gcc/match.pd
> @@ -599,6 +599,15 @@ along with GCC; see the file COPYING3.  If not see
>  			    build_int_cst (TREE_TYPE (@1),
>  					   element_precision (type)), @1); }))
>  
> +/* ((1 << A) & 1) != 0 -> A == 0 */
> +(simplify
> + (ne (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
> + (eq @0 { build_zero_cst (TREE_TYPE (@0)); }))
> +
> +/* ((1 << A) & 1) == 0 -> A != 0 */
> +(simplify
> + (eq (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
> + (ne @0 { build_zero_cst (TREE_TYPE (@0)); }))

You can use

(for cmp (ne eq)
     icmp (eq ne)
 (simplify
  (cmp (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
  (icmp @0 { build_zero_cst (TREE_TYPE (@0)); })))

to combine both patterns.  Btw, shoudln't it be (bit_and (...) 
integer_each_onep)?  I'm always unsure about the complex integer case
(maybe try a runtime testcase and see what happens - eventually we
just don't support bit operations on them...)

Thanks,
Richard.


>  /* Simplifications of conversions.  */
>  
> diff --git gcc/testsuite/gcc.dg/pr64309.c gcc/testsuite/gcc.dg/pr64309.c
> index e69de29..710a762 100644
> --- gcc/testsuite/gcc.dg/pr64309.c
> +++ gcc/testsuite/gcc.dg/pr64309.c
> @@ -0,0 +1,66 @@
> +/* PR middle-end/64309 */
> +/* { dg-do run } */
> +/* { dg-options "-fdump-tree-original" } */
> +
> +int
> +fn1 (int n)
> +{
> +  return ((1 << n) & 1) != 0;
> +}
> +
> +int
> +fn2 (int n)
> +{
> +  return (1 & (1 << n)) != 0;
> +}
> +
> +int
> +fn3 (int n)
> +{
> +  return ((1 << n) & 1) == 0;
> +}
> +
> +int
> +fn4 (int n)
> +{
> +  return (1 & (1 << n)) == 0;
> +}
> +
> +int
> +main (void)
> +{
> +  if (fn1 (0) != 1
> +      || fn1 (1) != 0
> +      || fn1 (2) != 0
> +      || fn1 (3) != 0
> +      || fn1 (4) != 0
> +      || fn1 (5) != 0)
> +    __builtin_abort ();
> +
> +  if (fn2 (0) != 1
> +      || fn2 (1) != 0
> +      || fn2 (2) != 0
> +      || fn2 (3) != 0
> +      || fn2 (4) != 0
> +      || fn2 (5) != 0)
> +    __builtin_abort ();
> +
> +  if (fn3 (0) != 0
> +      || fn3 (1) != 1
> +      || fn3 (2) != 1
> +      || fn3 (3) != 1
> +      || fn3 (4) != 1
> +      || fn3 (5) != 1)
> +    __builtin_abort ();
> +
> +  if (fn4 (0) != 0
> +      || fn4 (1) != 1
> +      || fn4 (2) != 1
> +      || fn4 (3) != 1
> +      || fn4 (4) != 1
> +      || fn4 (5) != 1)
> +    __builtin_abort ();
> +}
> +
> +/* { dg-final { scan-tree-dump-not "(<<|>>)" "original" } } */
> +/* { dg-final { cleanup-tree-dump "original" } } */
> 
> 	Marek
> 
>