[Committed] Canonicalize "even" tests as (X & 1) == 0.

[Roger Sayle]

This patch (which is related to but independent of another PR resolving
patch) teaches fold to canonicalize tests that the least significant
of an integer is zero as "(X & 1) == 0".  The new test case below
shows several ways this idiom is implemented in C and checks that
they all generate the same gimple.

The following patch has been tested on x86_64-unknown-linux-gnu with
a full "make bootstrap", and regression tested with a top-level
"make -k check" with no new failures.

Committed to mainline as revision 111454.



2006-02-26  Roger Sayle  <roger@eyesopen.com>

	* fold-const.c (fold_binary) <BIT_XOR_EXPR>: Fold (X & 1) ^ 1 as
	(X & 1) == 0.
	<BIT_AND_EXPR>: Fold (X ^ 1) & 1 and ~X & 1 as (X & 1) == 0.

	* gcc.dg/fold-even-1.c: New test case.


Index: fold-const.c
===================================================================
*** fold-const.c	(revision 111443)
--- fold-const.c	(working copy)
*************** fold_binary (enum tree_code code, tree t
*** 8740,8745 ****
--- 8740,8752 ----
  			    fold_convert (type, TREE_OPERAND (arg0, 0)),
  			    fold_convert (type, TREE_OPERAND (arg1, 0)));

+       /* Fold (X & 1) ^ 1 as (X & 1) == 0.  */
+       if (TREE_CODE (arg0) == BIT_AND_EXPR
+ 	  && integer_onep (TREE_OPERAND (arg0, 1))
+ 	  && integer_onep (arg1))
+ 	return fold_build2 (EQ_EXPR, type, arg0,
+ 			    build_int_cst (TREE_TYPE (arg0), 0));
+
        /* See if this can be simplified into a rotate first.  If that
  	 is unsuccessful continue in the association code.  */
        goto bit_rotate;
*************** fold_binary (enum tree_code code, tree t
*** 8792,8797 ****
--- 8799,8826 ----
  	  && reorder_operands_p (arg0, TREE_OPERAND (arg1, 0)))
  	return omit_one_operand (type, arg0, TREE_OPERAND (arg1, 0));

+       /* Fold (X ^ 1) & 1 as (X & 1) == 0.  */
+       if (TREE_CODE (arg0) == BIT_XOR_EXPR
+ 	  && integer_onep (TREE_OPERAND (arg0, 1))
+ 	  && integer_onep (arg1))
+ 	{
+ 	  tem = TREE_OPERAND (arg0, 0);
+ 	  return fold_build2 (EQ_EXPR, type,
+ 			      fold_build2 (BIT_AND_EXPR, TREE_TYPE (tem), tem,
+ 					   build_int_cst (TREE_TYPE (tem), 1)),
+ 			      build_int_cst (TREE_TYPE (tem), 0));
+ 	}
+       /* Fold ~X & 1 as (X & 1) == 0.  */
+       if (TREE_CODE (arg0) == BIT_NOT_EXPR
+ 	  && integer_onep (arg1))
+ 	{
+ 	  tem = TREE_OPERAND (arg0, 0);
+ 	  return fold_build2 (EQ_EXPR, type,
+ 			      fold_build2 (BIT_AND_EXPR, TREE_TYPE (tem), tem,
+ 					   build_int_cst (TREE_TYPE (tem), 1)),
+ 			      build_int_cst (TREE_TYPE (tem), 0));
+ 	}
+
        t1 = distribute_bit_expr (code, type, arg0, arg1);
        if (t1 != NULL_TREE)
  	return t1;


/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-original" } */
int test1(int a)
{
  return !(a & 1);
}

int test2(int b)
{
  return (b & 1) == 0;
}

int test3(int c)
{
  return (c & 1) ^ 1;
}

int test4(int d)
{
  return (d ^ 1) & 1;
}

int test5(int e)
{
  return ~e & 1;
}

/* { dg-final { scan-tree-dump-times "\\(a \& 1\\) == 0" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "\\(b \& 1\\) == 0" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "\\(c \& 1\\) == 0" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "\\(d \& 1\\) == 0" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "\\(e \& 1\\) == 0" 1 "original" } } */
/* { dg-final { cleanup-tree-dump "original" } } */


Roger
--