[PATCH] PR18002: Undo fold_single_bit_test in do_jump

Roger Sayle roger@eyesopen.com
Thu Dec 9 03:07:00 GMT 2004


The following patch resolves both PR target/18002 and the major
part of PR middle-end/18424, which are code quality regressions
on both mainline and the 3.4 branch.

The issue concerns the code generated for expressions such as
"if (x & C)" where C is a power-of-two.  The trickiness with
trees such as "(x & C) != 0" is that the code we generate for
them depends upon the context in which its used.  For control
flow instructions its better to use a bitwise-AND of the constant
C, however if the tree's value is assigned to a variable its
best to implement this as "var = (x >> C') & 1" which doesn't
require any conditional jumps, and is therefore preferable to
"var = (x & C) ? 1 : 0".

To achieve this context dependent RTL expansion, we rely on the
fact that control-flow expressions are handled in do_jump, but
normal rvalue expressions are handled in expand_expr.  The
middle-end canonicalizes "(x & C) != 0" into "(x >> C') & 1",
which expands naturally through expand_expr, but is specially
recognized in do_jump which converts it into the optimal form
for jumping code.

The regression is that we are currently failing to recognize
all of the possible forms of these canonicalized expressions,
probably due to changes/improvements in constant folding.

The fix below is to improve do_jump's pattern matching, to
handle both the type conversions that may have been pushed down
through the BIT_AND_EXPR, but also the BIT_XOR_EXPR that
results from canonicalizing "(x & C) == 0".  For example,
in the testcase attached to bugzilla PR middle-end/18424

(int)(((long)x & C) == 0)

is transformed by fold_single_bit_test into

(int)(((long)x >> C') ^ 1) & 1

which requires the changes/improvements below.


Also included in this patch, though perhaps not obvious from the
code, is a subtle latent bug-fix.  In the original code, we used
build2(LSHIFT_EXPR, argtype, one, shift) to construct the
constant "1 << INTVAL(shift)".  The mistake in this code is
that "one" may have narrower width than argtype, which can
result in a truncation.  This appears to have affected 3.3.1
where on AVR (with 16bit ints and 32bit longs) the routine

int foo(int a)
{
  return (a & (1L << 23)) ? 1 : 2;
}

was being misoptimized to "return 2".  The hidden-bug is
that "a" should be sign extended to a long prior to the
AND, in which case, bit 23 is conditional on the sign bit
of a.  The correct code is therefore:

int foo(int a)
{
  return (a < 0) ? 1 : 2;
}



The following patch has been tested on i686-pc-linux-gnu with a
full "make bootstrap", and regression tested with a top-level
"make -k check" with no new failures.  It's also been tested
with a cross-compiler to avr-elf, confirming that we now generate
significantly better code PR18002 and PR18424.

Ok for mainline and the gcc-3_4-branch?



2004-12-08  Roger Sayle  <roger@eyesopen.com>

	PR target/18002
	PR middle-end/18424
	* dojump.c (do_jump): When attempting to reverse the effects of
	fold_single_bit_test, we need to STRIP_NOPS and narrowing type
	conversions, and handle BIT_XOR_EXPR that's used to invert the
	sense of the single bit test.


Index: dojump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/dojump.c,v
retrieving revision 1.32
diff -c -3 -p -r1.32 dojump.c
*** dojump.c	24 Nov 2004 19:44:58 -0000	1.32
--- dojump.c	8 Dec 2004 21:24:10 -0000
*************** do_jump (tree exp, rtx if_false_label, r
*** 218,241 ****
        /* fold_single_bit_test() converts (X & (1 << C)) into (X >> C) & 1.
  	 See if the former is preferred for jump tests and restore it
  	 if so.  */
!       if (TREE_CODE (TREE_OPERAND (exp, 0)) == RSHIFT_EXPR
! 	  && integer_onep (TREE_OPERAND (exp, 1)))
  	{
! 	  tree arg = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
! 	  tree shift = TREE_OPERAND (TREE_OPERAND (exp, 0), 1);
! 	  tree one = TREE_OPERAND (exp, 1);
! 	  tree argtype = TREE_TYPE (arg);
! 	  if (TREE_CODE (shift) == INTEGER_CST
! 	      && compare_tree_int (shift, 0) > 0
! 	      && compare_tree_int (shift, HOST_BITS_PER_WIDE_INT) < 0
! 	      && prefer_and_bit_test (TYPE_MODE (argtype),
! 				      TREE_INT_CST_LOW (shift)))
  	    {
! 	      do_jump (build2 (BIT_AND_EXPR, argtype, arg,
! 			       fold (build2 (LSHIFT_EXPR, argtype,
! 					     one, shift))),
! 		       if_false_label, if_true_label);
! 	      break;
  	    }
  	}

--- 218,269 ----
        /* fold_single_bit_test() converts (X & (1 << C)) into (X >> C) & 1.
  	 See if the former is preferred for jump tests and restore it
  	 if so.  */
!       if (integer_onep (TREE_OPERAND (exp, 1)))
  	{
! 	  tree exp0 = TREE_OPERAND (exp, 0);
! 	  rtx set_label, clr_label;
!
! 	  /* Strip narrowing integral type conversions.  */
! 	  while ((TREE_CODE (exp0) == NOP_EXPR
! 		  || TREE_CODE (exp0) == CONVERT_EXPR
! 		  || TREE_CODE (exp0) == NON_LVALUE_EXPR)
! 		 && TREE_OPERAND (exp0, 0) != error_mark_node
! 		 && TYPE_PRECISION (TREE_TYPE (exp0))
! 		    <= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp0, 0))))
! 	    exp0 = TREE_OPERAND (exp0, 0);
!
! 	  /* "exp0 ^ 1" inverts the sense of the single bit test.  */
! 	  if (TREE_CODE (exp0) == BIT_XOR_EXPR
! 	      && integer_onep (TREE_OPERAND (exp0, 1)))
! 	    {
! 	      exp0 = TREE_OPERAND (exp0, 0);
! 	      clr_label = if_true_label;
! 	      set_label = if_false_label;
! 	    }
! 	  else
! 	    {
! 	      clr_label = if_false_label;
! 	      set_label = if_true_label;
! 	    }
!
! 	  if (TREE_CODE (exp0) == RSHIFT_EXPR)
  	    {
! 	      tree arg = TREE_OPERAND (exp0, 0);
! 	      tree shift = TREE_OPERAND (exp0, 1);
! 	      tree argtype = TREE_TYPE (arg);
! 	      if (TREE_CODE (shift) == INTEGER_CST
! 		  && compare_tree_int (shift, 0) >= 0
! 		  && compare_tree_int (shift, HOST_BITS_PER_WIDE_INT) < 0
! 		  && prefer_and_bit_test (TYPE_MODE (argtype),
! 					  TREE_INT_CST_LOW (shift)))
! 		{
! 		  HOST_WIDE_INT mask = (HOST_WIDE_INT) 1
! 				       << TREE_INT_CST_LOW (shift);
! 		  do_jump (build2 (BIT_AND_EXPR, argtype, arg,
! 				   build_int_cst_type (argtype, mask)),
! 			   clr_label, set_label);
! 		  break;
! 		}
  	    }
  	}


Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833



More information about the Gcc-patches mailing list