Re: Optimization of offset computations

[kenner at vlsi1 dot ultra dot nyu dot edu (Richard Kenner)]

    This change introduced a couple of testsuite failures.  I've observed
    them on i586-linux, but I'm fairly certain they affect every target.
    (There are four patches below, numbered like the following
    explanations).

OK, I think I've fixed all but the potential overflow problems, which I
need to hear more about, since I thought all those cases were correct.

This is the patch I committed:

Mon Nov 29 16:56:42 1999  Richard Kenner  <kenner@vlsi1.ultra.nyu.edu>

	* fold-const.c (extract_muldiv, case {MIN,MAX}_EXPR): Reverse
	operation if C is negative.
	(extract_muldiv, case SAVE_EXPR): Supresss if arg has side effects.
	(extract_muldiv, case {PLUS,MINUS}_EXPR): Don't apply distributive
	law for some divisions if constant is negative and change other
	divisions to the opposite rounding.

*** fold-const.c.nov29	Sat Nov 27 05:29:12 1999
--- fold-const.c	Mon Nov 29 17:55:07 1999
*************** extract_muldiv (t, c, code, wide_type)
*** 4111,4116 ****
  
        /* Pass the constant down and see if we can make a simplification.  If
! 	 we can, replace this expression with a conversion of that result to
! 	 our type.  */
        if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
  				     code == MULT_EXPR ? ctype : NULL_TREE)))
--- 4111,4116 ----
  
        /* Pass the constant down and see if we can make a simplification.  If
! 	 we can, replace this expression with the inner simplification for
! 	 possible later conversion to our or some other type.  */
        if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
  				     code == MULT_EXPR ? ctype : NULL_TREE)))
*************** extract_muldiv (t, c, code, wide_type)
*** 4127,4132 ****
        if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0
  	  && (t2 = extract_muldiv (op1, c, code, wide_type)) != 0)
! 	return fold (build (tcode, ctype, convert (ctype, t1),
! 			    convert (ctype, t2)));
        break;
  
--- 4127,4137 ----
        if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0
  	  && (t2 = extract_muldiv (op1, c, code, wide_type)) != 0)
! 	{
! 	  if (tree_int_cst_sgn (c) < 0)
! 	    tcode = (tcode == MIN_EXPR ? MAX_EXPR : MIN_EXPR);
! 
! 	  return fold (build (tcode, ctype, convert (ctype, t1),
! 			      convert (ctype, t2)));
! 	}
        break;
  
*************** extract_muldiv (t, c, code, wide_type)
*** 4138,4144 ****
  
      case SAVE_EXPR:
!       /* If this has not been evaluated, we can see if we can do
! 	 something inside it and make a new one.  */
!       if (SAVE_EXPR_RTL (t) == 0
  	  && 0 != (t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code,
  					wide_type)))
--- 4143,4152 ----
  
      case SAVE_EXPR:
!       /* If this has not been evaluated and the operand has no side effects,
! 	 we can see if we can do something inside it and make a new one.
! 	 Note that this test is overly conservative since we can do this
! 	 if the only reason it had side effects is that it was another
! 	 similar SAVE_EXPR, but that isn't worth bothering with.  */
!       if (SAVE_EXPR_RTL (t) == 0 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (t, 0))
  	  && 0 != (t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code,
  					wide_type)))
*************** extract_muldiv (t, c, code, wide_type)
*** 4171,4197 ****
  	return fold (build (tcode, ctype, convert (ctype, t1),
  			    convert (ctype, t2)));
!       else if (TREE_CODE (op1) != INTEGER_CST)
  	break;
  
        /* If we were able to eliminate our operation from the first side,
! 	 apply our operation to the second side and reform the PLUS or
! 	 MINUS.  */
!       if (t1 != 0 && (TREE_CODE (t1) != code || code == MULT_EXPR)
! 	  && 0 != (t2 = const_binop (code, convert (ctype, op1),
! 				     convert (ctype, c), 0))
! 	  && ! TREE_OVERFLOW (t2))
! 	return fold (build (tcode, ctype, convert (ctype, t1), t2));
  
        /* The last case is if we are a multiply.  In that case, we can
  	 apply the distributive law to commute the multiply and addition
  	 if the multiplication of the constants doesn't overflow. */
!       if (code == MULT_EXPR
! 	  && 0 != (t1 = const_binop (code, convert (ctype, op1),
! 				     convert (ctype, c), 0))
! 	  && ! TREE_OVERFLOW (t1))
  	return fold (build (tcode, ctype, fold (build (code, ctype,
  						       convert (ctype, op0),
  						       convert (ctype, c))),
! 			    t1));
  
        break;
--- 4179,4226 ----
  	return fold (build (tcode, ctype, convert (ctype, t1),
  			    convert (ctype, t2)));
! 
!       /* If this was a subtraction, negate OP1 and set it to be an addition.
! 	 This simplifies the logic below.  */
!       if (tcode == MINUS_EXPR)
! 	tcode = PLUS_EXPR, op1 = negate_expr (op1);
! 
!       if (TREE_CODE (op1) != INTEGER_CST)
! 	break;
! 
!       /* If either OP1 or C are negative, this optimization is not safe for
! 	 some of the division and remainder types while for others we need
! 	 to change the code.  */
!       if (tree_int_cst_sgn (op1) < 0 || tree_int_cst_sgn (c) < 0)
! 	{
! 	  if (code == CEIL_DIV_EXPR)
! 	    code = FLOOR_DIV_EXPR;
! 	  else if (code == CEIL_MOD_EXPR)
! 	    code = FLOOR_MOD_EXPR;
! 	  else if (code == FLOOR_DIV_EXPR)
! 	    code = CEIL_DIV_EXPR;
! 	  else if (code == FLOOR_MOD_EXPR)
! 	    code = CEIL_MOD_EXPR;
! 	  else if (code != MULT_EXPR)
! 	    break;
! 	}
! 
!       /* Now do the operation and verify it doesn't overflow.  */
!       op1 = const_binop (code, convert (ctype, op1), convert (ctype, c), 0);
!       if (op1 == 0 || TREE_OVERFLOW (op1))
  	break;
  
        /* If we were able to eliminate our operation from the first side,
! 	 apply our operation to the second side and reform the PLUS.  */
!       if (t1 != 0 && (TREE_CODE (t1) != code || code == MULT_EXPR))
! 	return fold (build (tcode, ctype, convert (ctype, t1), op1));
  
        /* The last case is if we are a multiply.  In that case, we can
  	 apply the distributive law to commute the multiply and addition
  	 if the multiplication of the constants doesn't overflow. */
!       if (code == MULT_EXPR)
  	return fold (build (tcode, ctype, fold (build (code, ctype,
  						       convert (ctype, op0),
  						       convert (ctype, c))),
! 			    op1));
  
        break;