Re: Optimization of offset computations

[Bernd Schmidt <bernds at pathia dot cygnus dot co dot uk>]

On Sat, 27 Nov 1999, Richard Kenner wrote:

> I checked in the following patch, which improves optimization on the types
> of trees often seen for offset computations when accessing complex
> structures (such as multiple-dimension arrays with variable bounds).
> 
> Sat Nov 27 08:38:26 1999  Richard Kenner  <kenner@vlsi1.ultra.nyu.edu>
> 
> 	* fold-const.c (negate_expr, associate_trees, extract_muldiv): New.
> 	(split_tree): Completely rework to make more general.
> 	(make_range, fold): Call negate_expr.
> 	(fold, case NEGATE_EXPR): Simplify -(a-b) is -ffast-math.
> 	(fold, associate): Call new split_tree and associate_trees.
> 	(fold, case MULT_EXPR, case *_{DIV,MOD}_EXPR): Call extract_muldiv.

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).

1. execute/931208-1.c

   We have in the source file
     unsigned long x, y = 1;
     x = ((y * 8192) - 216) / 16;
   This gets transformed to
     x = y * 512 - (216 / 16);
   which is off by one.  Distributive law doesn't apply for integer
   divisions.  It also doesn't apply for modulo operations; see below for
   a patch against the testcase to detect another misoptimization caused
   by this change.

2. execute/970217-1.c

   The source:
     sub (int i, int array[i++])
     {
       return i;
     }
   extract_muldiv is called while computing the type size for the array.
   We have a SAVE_EXPR that contains a postincrement (representing the
   number of elements), and extract_muldiv returns a newly made SAVE_EXPR.
   The problem is that both SAVE_EXPRs get evaluated, and I is incremented
   too often.

3. I don't have a testcase for this, but doesn't the NOP/CONVERT/NON_LVALUE
   case lack a final type conversion (the code seems to do something other
   than the comment indicates)?  I noticed this while debugging #2.

4. The handling of MIN/MAX is wrong.  There are at least two problems:
   multiplication/division by a negative value changes order of the min/max
   operands, and unsigned overflows aren't handled properly.
   See below for a (C++) testcase I made up (assuming 32 bit ints).

The patches below should fix these problems.

Hmm, it just occurs to me that the unsigned overflow problem could possibly
affect more than just the MIN/MAX case.  This may need more thought.

C standard question: is it legal to optimize

    unsigned int a = 65536;
    unsigned int b;

    {
         b = (a * 65536) / 8;
    }

to

    unsigned int a = 65536;
    unsigned int b;

    {
         b = (a * 8192);
    }


Bernd
         
	* fold-const.c (extract_muldiv): Delete SAVE_EXPR, MIN_EXPR, MAX_EXPR
	cases.
	In NOP_EXPR/CONVERT_EXPR/NON_LVALUE_EXPR cases, add missing
	conversion.
	In PLUS_EXPR, MINUS_EXPR cases, only apply distributive law for
	multiplications.

=================
* Testcase diff for #1:
--- 931208-1.c	Mon Nov 29 15:32:42 1999
+++ 931208-1.c	Mon Nov 29 16:02:06 1999
@@ -1,4 +1,4 @@
-f ()
+f1 ()
 {
   unsigned long x, y = 1;
 
@@ -6,9 +6,19 @@
   return x;
 }
 
+f2 ()
+{
+  unsigned long x, y = 1;
+
+  x = ((y * 8192) - 216) % 16;
+  return x;
+}
+
 main ()
 {
-  if (f () != 498)
+  if (f1 () != 498)
+    abort ();
+  if (f2 () != 8)
     abort ();
   exit (0);
 }

* Testcase for #4:
int f1 (int a, int b)
{
	return (a * 16 >? b * 16) / -8;
}

int f2 (unsigned int a)
{
	return (a * 65536 >? 16) / 8;
}

int main ()
{
  if (f2 (65536) != 2)
    abort ();
  if (f1 (-32, -16) != 32)
    abort ();
}

=================
Patches:

1.
diff -c -p -r1.86 fold-const.c
*** fold-const.c	1999/11/29 14:48:30	1.86
--- fold-const.c	1999/11/29 16:08:58
*************** extract_muldiv (t, c, code, wide_type)
*** 4274,4280 ****
    tree ctype = (wide_type != 0 && (GET_MODE_SIZE (TYPE_MODE (wide_type)) 
  				   > GET_MODE_SIZE (TYPE_MODE (type)))
  		? wide_type : type);
!   tree t1, t2;
    int same_p = tcode == code;
    int cancel_p
      = (code == MULT_EXPR && tcode == EXACT_DIV_EXPR)  || tcode == MULT_EXPR;
--- 4274,4280 ----
    tree ctype = (wide_type != 0 && (GET_MODE_SIZE (TYPE_MODE (wide_type)) 
  				   > GET_MODE_SIZE (TYPE_MODE (type)))
  		? wide_type : type);
!   tree t1, t2, t3;
    int same_p = tcode == code;
    int cancel_p
      = (code == MULT_EXPR && tcode == EXACT_DIV_EXPR)  || tcode == MULT_EXPR;
*************** extract_muldiv (t, c, code, wide_type)
*** 4358,4395 ****
      case PLUS_EXPR:  case MINUS_EXPR:
        /* See if we can eliminate the operation on both sides.  If we can, we
  	 can return a new PLUS or MINUS.  If we can't, the only remaining
! 	 cases where we can do anything are if the second operand is a
! 	 constant.  */
        t1 = extract_muldiv (op0, c, code, wide_type);
        t2 = extract_muldiv (op1, c, code, wide_type);
        if (t1 != 0 && t2 != 0)
  	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;
  
      case MULT_EXPR:
        /* We have a special case here if we are doing something like
--- 4341,4374 ----
      case PLUS_EXPR:  case MINUS_EXPR:
        /* See if we can eliminate the operation on both sides.  If we can, we
  	 can return a new PLUS or MINUS.  If we can't, the only remaining
! 	 cases where we can do anything are if we are a multiplication and
!          the second operand is a constant.  */
        t1 = extract_muldiv (op0, c, code, wide_type);
        t2 = extract_muldiv (op1, c, code, wide_type);
        if (t1 != 0 && t2 != 0)
  	return fold (build (tcode, ctype, convert (ctype, t1),
  			    convert (ctype, t2)));
!       else if (TREE_CODE (op1) != INTEGER_CST || code != MULT_EXPR)
  	break;
  
+       /* Perform the operation on the code, and verify that this doesn't
+ 	 cause an overflow.  */
+       t3 = const_binop (code, convert (ctype, op1), convert (ctype, c), 0);
+       if (t3 == 0 || TREE_OVERFLOW (t3))
+ 	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)
! 	return fold (build (tcode, ctype, convert (ctype, t1), t3));
  
!       /* Apply the distributive law to commute the multiply and addition
  	 if the multiplication of the constants doesn't overflow. */
!       return fold (build (tcode, ctype, fold (build (code, ctype,
! 						     convert (ctype, op0),
! 						     convert (ctype, c))),
! 			  t3));
  
      case MULT_EXPR:
        /* We have a special case here if we are doing something like

2.
diff -c -p -r1.86 fold-const.c
*** fold-const.c	1999/11/29 14:48:30	1.86
--- fold-const.c	1999/11/29 16:08:58
*************** extract_muldiv (t, c, code, wide_type)
*** 4330,4344 ****
  		      TREE_OPERAND (t, 1));
        break;
  
-     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)))
- 	return save_expr (t1);
-       break;
- 
      case LSHIFT_EXPR:  case RSHIFT_EXPR:
        /* If the second operand is constant, this is a multiplication
  	 or floor division, by a power of two, so we can treat it that
--- 4330,4335 ----

3.
diff -c -p -r1.86 fold-const.c
*** fold-const.c	1999/11/29 14:48:30	1.86
--- fold-const.c	1999/11/29 16:08:58
*************** extract_muldiv (t, c, code, wide_type)
*** 4309,4315 ****
  	 our type.  */
        if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
  				     code == MULT_EXPR ? ctype : NULL_TREE)))
! 	return t1;
        break;
  
      case NEGATE_EXPR:  case ABS_EXPR:
--- 4309,4315 ----
  	 our type.  */
        if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
  				     code == MULT_EXPR ? ctype : NULL_TREE)))
! 	return convert (ctype, t1);
        break;
  
      case NEGATE_EXPR:  case ABS_EXPR:

4.
diff -c -p -r1.86 fold-const.c
*** fold-const.c	1999/11/29 14:48:30	1.86
--- fold-const.c	1999/11/29 16:08:58
*************** extract_muldiv (t, c, code, wide_type)
*** 4317,4330 ****
  	return fold (build1 (tcode, ctype, convert (ctype, t1)));
        break;
  
-     case MIN_EXPR:  case MAX_EXPR:
-       /* MIN (a, b) / 5 -> MIN (a / 5, b / 5)  */
-       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;
- 
      case WITH_RECORD_EXPR:
        if ((t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code, wide_type)) != 0)
  	return build (WITH_RECORD_EXPR, TREE_TYPE (t1), t1,
--- 4317,4322 ----