PR rtl-optimization/26244 (incorrect shift optimization)

[Roger Sayle]

Hi Dave,

On Wed, 2 Aug 2006, John David Anglin wrote:
> I came to the conclusion that this was a useful optimization
> but that one has to be very careful about the semantics when
> associating shifts.

Ok, I think I'm now clear on exactly what the intented semantics of
RTL shifts are.  The middle-end handles RTL shifts with negative
shift counts and shift counts larger than the mode, exactly like
it handles overflow with -ftrapv, or zero divisors.  It preserves
the instruction as written, and ignores it in optimizations.  This
is the correct thing to do with most undefined/backend specified
behaviour.

The exception is SHIFT_COUNT_TRUNCATED targets where the problematic
shifts are treated as implicitly unsigned and ANDed with width - 1,
i.e. taken modulo GET_MODE_BITSIZE (mode).  If you look at all (both)
references to SHIFT_COUNT_TRUNCATED in simplify-rtx.c you'll see it
follows these rules, and doesn't attempting to evaluate "2 << -1" at
compile-time.


So I think the correct thing to do, is follow this prescribed logic
in cse.c.  If we CSE a negative constant, we either skip attempts
to associate it on !SHIFT_COUNT_TRUNCATED targets, or canonicalize
the result to be 0 <= new_const < GET_MODE_BITSIZE to avoid introducing
any new undefined behaviour.

So I think the correct solution is something like the patch below:
My apologies for the minor reformatting clean-ups, force of habit.


Index: cse.c
===================================================================
*** cse.c	(revision 115896)
--- cse.c	(working copy)
*************** fold_rtx (rtx x, rtx insn)
*** 4267,4282 ****
  	      enum rtx_code associate_code;
  	      rtx new_const;

! 	      if (y == 0
! 		  || 0 == (inner_const
! 			   = equiv_constant (fold_rtx (XEXP (y, 1), 0)))
! 		  || GET_CODE (inner_const) != CONST_INT
! 		  /* If we have compiled a statement like
! 		     "if (x == (x & mask1))", and now are looking at
! 		     "x & mask2", we will have a case where the first operand
! 		     of Y is the same as our first operand.  Unless we detect
! 		     this case, an infinite loop will result.  */
! 		  || XEXP (y, 0) == folded_arg0)
  		break;

  	      /* Don't associate these operations if they are a PLUS with the
--- 4267,4295 ----
  	      enum rtx_code associate_code;
  	      rtx new_const;

! 	      if (is_shift
! 		  && (INTVAL (const_arg1) >= GET_MODE_BITSIZE (mode)
! 		      || INTVAL (const_arg1) < 0))
! 		{
! 		  if (SHIFT_COUNT_TRUNCATED)
! 		    const_arg1 = GEN_INT (INTVAL (const_arg1)
! 					  & (GET_MODE_BITSIZE (mode) - 1));
! 		  else
! 		    break;
! 		}
!
! 	      if (y == 0)
! 		break;
! 	      inner_const = equiv_constant (fold_rtx (XEXP (y, 1), 0)));
! 	      if (!inner_const || GET_CODE (inner_const) != CONST_INT)
! 		break;
!
! 	      /* If we have compiled a statement like
! 		 "if (x == (x & mask1))", and now are looking at
! 		 "x & mask2", we will have a case where the first operand
! 		 of Y is the same as our first operand.  Unless we detect
! 		 this case, an infinite loop will result.  */
! 	      if (XEXP (y, 0) == folded_arg0)
  		break;

  	      /* Don't associate these operations if they are a PLUS with the
*************** fold_rtx (rtx x, rtx insn)
*** 4295,4300 ****
--- 4308,4324 ----
  			  && exact_log2 (- INTVAL (const_arg1)) >= 0)))
  		break;

+ 	      if (is_shift
+ 		  && (INTVAL (inner_const) >= GET_MODE_BITSIZE (mode)
+ 		      || INTVAL (inner_const) < 0))
+ 		{
+ 		  if (SHIFT_COUNT_TRUNCATED)
+ 		    inner_const = GEN_INT (INTVAL (inner_const)
+ 					   & (GET_MODE_BITSIZE (mode) - 1));
+ 		  else
+ 		    break;
+ 		}
+
  	      /* Compute the code used to compose the constants.  For example,
  		 A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS.  */

*************** fold_rtx (rtx x, rtx insn)
*** 4312,4324 ****
  		 shift on a machine that does a sign-extend as a pair
  		 of shifts.  */

! 	      if (is_shift && GET_CODE (new_const) == CONST_INT
  		  && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
  		{
  		  /* As an exception, we can turn an ASHIFTRT of this
  		     form into a shift of the number of bits - 1.  */
  		  if (code == ASHIFTRT)
  		    new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
  		  else
  		    break;
  		}
--- 4336,4351 ----
  		 shift on a machine that does a sign-extend as a pair
  		 of shifts.  */

! 	      if (is_shift
! 		  && GET_CODE (new_const) == CONST_INT
  		  && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
  		{
  		  /* As an exception, we can turn an ASHIFTRT of this
  		     form into a shift of the number of bits - 1.  */
  		  if (code == ASHIFTRT)
  		    new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
+ 		  else if (!side_effects_p (XEXP (y, 0)))
+ 		    return CONST0_RTX (mode);
  		  else
  		    break;
  		}



Unfortunately, I'm still building on my PA box, and its unlikely I'll
have the result by the time I have to go.  But what do you think of
the above approach.  Could you confirm that it fixes the failure you're
seeing?  [My apologies if it doesn't actually compile due to typos,
but it expresses the intent].

Thanks in advance,

Roger
--