[patch] fold-const.c: Don't transform X & C into (X >> C') & 1 in fold_binary.

[Kazu Hirata]

Hi,

Attached is a patch to teach fold_binary not to transform

  X & C

into

  (X >> C) & 1.

Note that fold_single_bit_test, a subroutine of fold_binary,
transforms

  int a = ...;
  if (a & 4)

into

  a.0_2 = (unsigned int) a_1;
  D.1236_3 = a.0_2 >> 2;
  D.1237_4 = (int) D.1236_3;
  D.1238_5 = D.1237_4 & 1;
  if (D.1238_5 != 0) goto <L0>; else goto <L1>;

which is pretty long.  The patch disables this transformation for
fold.  In the above example, we would instead have

  D.1235_2 = a_1 & 4;
  if (D.1235_2 != 0) goto <L0>; else goto <L1>;

AFAICT, it does not matter whether we do this transformation or not as
far as conditional branches are concerned.  Combine canonicalizes a
single bit test into zero_extract regardless of whether we have

  a & 4

or

  (a >> 2) & 1

Also the transformation does not matter for a store flag operation
because do_store_flag calls fold_single_bit_test to transform

  var = (a & 4) != 0;

into

  var = (a >> 2) & 1;

So all in all, the "SHIFT and AND" form seems to do nothing but take
up a lot of statements during tree optimizations.

The patch factors out a part of fold_single_bit_test that transforms
(x & SIGNBIT) != 0 into x < 0.  With this patch, fold_binary calls the
new function fold_single_bit_test_into_sign_test instead of
fold_single_bit_test.

Roger agreed that it was a good idea to disable this transformation in
fold, but I would like to know what others think as well.  Jeff?
Richard?

IIRC, do_jump contains code to reverse the effect of
fold_single_bit_test.  If this patch is approved, I am planning to
adjust that code as a follow-up patch.

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2005-04-20  Kazu Hirata  <kazu@cs.umass.edu>

	* fold-const.c (fold_single_bit_test_into_sign_test): New,
	split out from ...
	(fold_single_bit_test): ... here.
	(fold_binary): Call fold_single_bit_test_into_sign_test
	instead of fold_single_bit_test.

Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.565
diff -c -d -p -r1.565 fold-const.c
*** fold-const.c	20 Apr 2005 02:31:21 -0000	1.565
--- fold-const.c	20 Apr 2005 03:57:35 -0000
*************** fold_div_compare (enum tree_code code, t
*** 5929,5958 ****
  
  
  /* If CODE with arguments ARG0 and ARG1 represents a single bit
!    equality/inequality test, then return a simplified form of
!    the test using shifts and logical operations.  Otherwise return
!    NULL.  TYPE is the desired result type.  */
  
! tree
! fold_single_bit_test (enum tree_code code, tree arg0, tree arg1,
! 		      tree result_type)
  {
    /* If this is testing a single bit, we can optimize the test.  */
    if ((code == NE_EXPR || code == EQ_EXPR)
        && TREE_CODE (arg0) == BIT_AND_EXPR && integer_zerop (arg1)
        && integer_pow2p (TREE_OPERAND (arg0, 1)))
      {
-       tree inner = TREE_OPERAND (arg0, 0);
-       tree type = TREE_TYPE (arg0);
-       int bitnum = tree_log2 (TREE_OPERAND (arg0, 1));
-       enum machine_mode operand_mode = TYPE_MODE (type);
-       int ops_unsigned;
-       tree signed_type, unsigned_type, intermediate_type;
-       tree arg00;
- 
        /* If we have (A & C) != 0 where C is the sign bit of A, convert
  	 this into A < 0.  Similarly for (A & C) == 0 into A >= 0.  */
!       arg00 = sign_bit_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1));
        if (arg00 != NULL_TREE
  	  /* This is only a win if casting to a signed type is cheap,
  	     i.e. when arg00's type is not a partial mode.  */
--- 5929,5951 ----
  
  
  /* If CODE with arguments ARG0 and ARG1 represents a single bit
!    equality/inequality test, then return a simplified form of the test
!    using a sign testing.  Otherwise return NULL.  TYPE is the desired
!    result type.  */
  
! static tree
! fold_single_bit_test_into_sign_test (enum tree_code code, tree arg0, tree arg1,
! 				     tree result_type)
  {
    /* If this is testing a single bit, we can optimize the test.  */
    if ((code == NE_EXPR || code == EQ_EXPR)
        && TREE_CODE (arg0) == BIT_AND_EXPR && integer_zerop (arg1)
        && integer_pow2p (TREE_OPERAND (arg0, 1)))
      {
        /* If we have (A & C) != 0 where C is the sign bit of A, convert
  	 this into A < 0.  Similarly for (A & C) == 0 into A >= 0.  */
!       tree arg00 = sign_bit_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1));
! 
        if (arg00 != NULL_TREE
  	  /* This is only a win if casting to a signed type is cheap,
  	     i.e. when arg00's type is not a partial mode.  */
*************** fold_single_bit_test (enum tree_code cod
*** 5964,5969 ****
--- 5957,5995 ----
  			      result_type, fold_convert (stype, arg00),
  			      fold_convert (stype, integer_zero_node));
  	}
+     }
+ 
+   return NULL_TREE;
+ }
+ 
+ /* If CODE with arguments ARG0 and ARG1 represents a single bit
+    equality/inequality test, then return a simplified form of
+    the test using shifts and logical operations.  Otherwise return
+    NULL.  TYPE is the desired result type.  */
+ 
+ tree
+ fold_single_bit_test (enum tree_code code, tree arg0, tree arg1,
+ 		      tree result_type)
+ {
+   /* If this is testing a single bit, we can optimize the test.  */
+   if ((code == NE_EXPR || code == EQ_EXPR)
+       && TREE_CODE (arg0) == BIT_AND_EXPR && integer_zerop (arg1)
+       && integer_pow2p (TREE_OPERAND (arg0, 1)))
+     {
+       tree inner = TREE_OPERAND (arg0, 0);
+       tree type = TREE_TYPE (arg0);
+       int bitnum = tree_log2 (TREE_OPERAND (arg0, 1));
+       enum machine_mode operand_mode = TYPE_MODE (type);
+       int ops_unsigned;
+       tree signed_type, unsigned_type, intermediate_type;
+       tree tem;
+ 
+       /* First, see if we can fold the single bit test into a sign-bit
+ 	 test.  */
+       tem = fold_single_bit_test_into_sign_test (code, arg0, arg1,
+ 						 result_type);
+       if (tem)
+ 	return tem;
  
        /* Otherwise we have (A & C) != 0 where C is a single bit,
  	 convert that into ((A >> C2) & 1).  Where C2 = log2(C).
*************** fold_binary (enum tree_code code, tree t
*** 9433,9441 ****
  			    arg0, fold_convert (TREE_TYPE (arg0),
  						integer_zero_node));
  
!       /* If we have (A & C) != 0 or (A & C) == 0 and C is a power of
! 	 2, then fold the expression into shifts and logical operations.  */
!       tem = fold_single_bit_test (code, arg0, arg1, type);
        if (tem)
  	return tem;
  
--- 9459,9467 ----
  			    arg0, fold_convert (TREE_TYPE (arg0),
  						integer_zero_node));
  
!       /* If we have (A & C) != 0 or (A & C) == 0 and C is the sign
! 	 bit, then fold the expression into A < 0 or A >= 0.  */
!       tem = fold_single_bit_test_into_sign_test (code, arg0, arg1, type);
        if (tem)
  	return tem;