[Committed] PR24427: Folding (X&C1)|C2 and (X|C1)&C2

[Roger Sayle <roger at eyesopen dot com>]

The following patch resolves PR middle-end/24427 by implementing several
constant folding transformations of bitwise-AND and bitwise-OR of a
constant combinations.

With this patch we now canonicalize (X|C1)&C2 as (X&C3)|C4 where we
always perform the bitwise-AND first, followed by the IOR.  This
allows later optimizers to see the BIT_IOR_EXPR outermost, and imply
non-zeroness.  Additionally, the patch implements several further
optimizations such as "(X & 1) | 1" -> "(X,1)" and "(X & ~1) | 1" ->
"X | 1".  Finally, as a canonicalization step, BIT_AND_EXPR's constant
is simplified to the constant with the fewest set bits.  This converts
"(X & 6) | 2" into the equalivalent "(X & 4) | 2".  This should help
code generation on some platforms.

For example,

unsigned int foo(unsigned int x)
{
  return (((x | 1) & ~2) | 4) & ~8;
}

now becomes:

  return x & 0fffffff0 | 5;


The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all default languages including Ada, and regression
tested with a top-level "make -k check" with no new failures.

Committed to mainline as revision 110918.



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

	PR middle-end/24427
	* fold-const.c (fold_binary) <BIT_IOR_EXPR>: Transform (X&C1)|C2
	into (X,C2) if C1 is a subset of the bits of C2.  Transform
	(X&C1)|C2 into X|C2 if C1|C2 == ~0.  Canonicalize (X&C1)|C2 as
	(X&(C1&~C2))|C2.
	<BIT_AND_EXPR>: Canonicalize (X|C1)&C2 as (X&C2)|(C1&C2).

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


Index: fold-const.c
===================================================================
*** fold-const.c	(revision 110873)
--- fold-const.c	(working copy)
*************** fold_binary (enum tree_code code, tree t
*** 8114,8119 ****
--- 8114,8166 ----
  	  return omit_one_operand (type, t1, arg0);
  	}

+       /* Canonicalize (X & C1) | C2.  */
+       if (TREE_CODE (arg0) == BIT_AND_EXPR
+ 	  && TREE_CODE (arg1) == INTEGER_CST
+ 	  && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
+ 	{
+ 	  unsigned HOST_WIDE_INT hi1, lo1, hi2, lo2, mlo, mhi;
+ 	  int width = TYPE_PRECISION (type);
+ 	  hi1 = TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1));
+ 	  lo1 = TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1));
+ 	  hi2 = TREE_INT_CST_HIGH (arg1);
+ 	  lo2 = TREE_INT_CST_LOW (arg1);
+
+ 	  /* If (C1&C2) == C1, then (X&C1)|C2 becomes (X,C2).  */
+ 	  if ((hi1 & hi2) == hi1 && (lo1 & lo2) == lo1)
+ 	    return omit_one_operand (type, arg1, TREE_OPERAND (arg0, 0));
+
+ 	  if (width > HOST_BITS_PER_WIDE_INT)
+ 	    {
+ 	      mhi = (unsigned HOST_WIDE_INT) -1
+ 		    >> (2 * HOST_BITS_PER_WIDE_INT - width);
+ 	      mlo = -1;
+ 	    }
+ 	  else
+ 	    {
+ 	      mhi = 0;
+ 	      mlo = (unsigned HOST_WIDE_INT) -1
+ 		    >> (HOST_BITS_PER_WIDE_INT - width);
+ 	    }
+
+ 	  /* If (C1|C2) == ~0 then (X&C1)|C2 becomes X|C2.  */
+ 	  if ((~(hi1 | hi2) & mhi) == 0 && (~(lo1 | lo2) & mlo) == 0)
+ 	    return fold_build2 (BIT_IOR_EXPR, type,
+ 				TREE_OPERAND (arg0, 0), arg1);
+
+ 	  /* Minimize the number of bits set in C1, i.e. C1 := C1 & ~C2.  */
+ 	  hi1 &= mhi;
+ 	  lo1 &= mlo;
+ 	  if ((hi1 & ~hi2) != hi1 || (lo1 & ~lo2) != lo1)
+ 	    return fold_build2 (BIT_IOR_EXPR, type,
+ 				fold_build2 (BIT_AND_EXPR, type,
+ 					     TREE_OPERAND (arg0, 0),
+ 					     build_int_cst_wide (type,
+ 								 lo1 & ~lo2,
+ 								 hi1 & ~hi2)),
+ 				arg1);
+ 	}
+
        t1 = distribute_bit_expr (code, type, arg0, arg1);
        if (t1 != NULL_TREE)
  	return t1;
*************** fold_binary (enum tree_code code, tree t
*** 8256,8261 ****
--- 8303,8318 ----
  	  && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
  	return omit_one_operand (type, integer_zero_node, arg0);

+       /* Canonicalize (X | C1) & C2 as (X & C2) | (C1 & C2).  */
+       if (TREE_CODE (arg0) == BIT_IOR_EXPR
+ 	  && TREE_CODE (arg1) == INTEGER_CST
+ 	  && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
+ 	return fold_build2 (BIT_IOR_EXPR, type,
+ 			    fold_build2 (BIT_AND_EXPR, type,
+ 					 TREE_OPERAND (arg0, 0), arg1),
+ 			    fold_build2 (BIT_AND_EXPR, type,
+ 					 TREE_OPERAND (arg0, 1), arg1));
+
        t1 = distribute_bit_expr (code, type, arg0, arg1);
        if (t1 != NULL_TREE)
  	return t1;

/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-original" } */

unsigned int test1(unsigned int a)
{
  return (a & 1) | 1;
}

int test2(int b)
{
  return (b & 1) | 1;
}

unsigned int test3(unsigned int c)
{
  return (c | 1) & 1;
}

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

unsigned int test5(unsigned int e)
{
  return (e | 4) & 6;
}

int test6(int f)
{
  return (f | 4) & 6;
}

unsigned int test7(unsigned int g)
{
  return (g & -2) | 1;
}

int test8(int h)
{
  return (h & -2) | 1;
}

unsigned int test9(unsigned int i)
{
  return (i & 3) | 1;
}

int test10(int j)
{
  return (j & 3) | 1;
}

/* { dg-final { scan-tree-dump-times "a \& 1 \\| 1" 0 "original" } } */
/* { dg-final { scan-tree-dump-times "b \& 1 \\| 1" 0 "original" } } */
/* { dg-final { scan-tree-dump-times "\\(c \\| 1\\) \& 1" 0 "original" } } */
/* { dg-final { scan-tree-dump-times "\\(d \\| 1\\) \& 1" 0 "original" } } */
/* { dg-final { scan-tree-dump-times "e \& 2 \\| 4" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "f \& 2 \\| 4" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "g \\| 1" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "h \\| 1" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "i \& 2 \\| 1" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "j \& 2 \\| 1" 1 "original" } } */
/* { dg-final { cleanup-tree-dump "original" } } */


Roger
--