[PATCH] Fix PR c/5430

["Eric Botcazou" <ebotcazou at libertysurf dot fr>]

Hello,

This is a regression from 2.95.3, except for testcase #2 below which also fails
with 2.95.3 (but not with 2.91.66). The multiplicative folding code is fooled by
the mix between signed variables and unsigned constants, e.g:

 int my_int = 924;
 unsigned int result;
 result =  ((my_int*2 + 4) - 8U) / 2;

doesn't return the correct result (922) but a big value (roughly INT_MAX).

The additive folding code splits the first sub-expression into:

 my_int*2 + 4 + (-8)U = my_int*2 + 4 + 4294967286U
                      = my_int*2 + 4294967290U

which is then simplified by 2 and gives: my_int + 2147483645U.

The proposed fix is to preserve the minus expression if needed:

 my_int*2 + 4 - 8U = my_int*2 - 4U

which is then simplified by 2 and gives: my_int - 2U.

The bug doesn't occur if my_int is itself unsigned because the 2 is not
folded in this case.

Bootstrapped/regtested (C/C++) on i586-pc-linux-gnu.


2002-04-05  Eric Botcazou <ebotcazou@multimania.com>

 PR c/5430
 *fold-const.c (split_tree): Add MINUS_LITP parameter.
 Separate added literals from substracted literals.
 (associate_trees): Don't convert MINUS_EXPR into
 PLUS_EXPR.
 (fold) [associate]: Preserve MINUS_EXPR if needed.


*** gcc/fold-const.c.orig Fri Apr  5 01:13:21 2002
--- gcc/fold-const.c Fri Apr  5 01:40:24 2002
***************
*** 64,70 ****
  #endif
  static tree negate_expr  PARAMS ((tree));
  static tree split_tree  PARAMS ((tree, enum tree_code, tree *, tree *,
!       int));
  static tree associate_trees PARAMS ((tree, tree, enum tree_code, tree));
  static tree int_const_binop PARAMS ((enum tree_code, tree, tree, int));
  static void const_binop_1 PARAMS ((PTR));
--- 64,70 ----
  #endif
  static tree negate_expr  PARAMS ((tree));
  static tree split_tree  PARAMS ((tree, enum tree_code, tree *, tree *,
!       tree *, int));
  static tree associate_trees PARAMS ((tree, tree, enum tree_code, tree));
  static tree int_const_binop PARAMS ((enum tree_code, tree, tree, int));
  static void const_binop_1 PARAMS ((PTR));
***************
*** 1389,1401 ****
     combined with CODE to make IN.  "constant" means an expression with
     TREE_CONSTANT but that isn't an actual constant.  CODE must be a
     commutative arithmetic operation.  Store the constant part into *CONP,
!    the literal in &LITP and return the variable part.  If a part isn't
     present, set it to null.  If the tree does not decompose in this way,
     return the entire tree as the variable part and the other parts as null.
  
     If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.  In that
!    case, we negate an operand that was subtracted.  If NEGATE_P is true, we
!    are negating all of IN.
  
     If IN is itself a literal or constant, return it as appropriate.
  
--- 1389,1404 ----
     combined with CODE to make IN.  "constant" means an expression with
     TREE_CONSTANT but that isn't an actual constant.  CODE must be a
     commutative arithmetic operation.  Store the constant part into *CONP,
!    the literal in *LITP and return the variable part.  If a part isn't
     present, set it to null.  If the tree does not decompose in this way,
     return the entire tree as the variable part and the other parts as null.
  
     If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.  In that
!    case, we negate an operand that was subtracted, except if it is a
!    literal for which we use *MINUS_LITP instead.
! 
!    If NEGATE_P is true, we are negating all of IN, except again a literal
!    for which we use *MINUS_LITP instead.
  
     If IN is itself a literal or constant, return it as appropriate.
  
***************
*** 1403,1418 ****
     same type as IN, but they will have the same signedness and mode.  */
  
  static tree
! split_tree (in, code, conp, litp, negate_p)
       tree in;
       enum tree_code code;
!      tree *conp, *litp;
       int negate_p;
  {
    tree var = 0;
  
    *conp = 0;
    *litp = 0;
  
    /* Strip any conversions that don't change the machine mode or signedness.  */
    STRIP_SIGN_NOPS (in);
--- 1406,1422 ----
     same type as IN, but they will have the same signedness and mode.  */
  
  static tree
! split_tree (in, code, conp, litp, minus_litp, negate_p)
       tree in;
       enum tree_code code;
!      tree *conp, *litp, *minus_litp;
       int negate_p;
  {
    tree var = 0;
  
    *conp = 0;
    *litp = 0;
+   *minus_litp = 0;
  
    /* Strip any conversions that don't change the machine mode or signedness.  */
    STRIP_SIGN_NOPS (in);
***************
*** 1454,1460 ****
   var = op1, neg_var_p = neg1_p;
  
        /* Now do any needed negations.  */
!       if (neg_litp_p) *litp = negate_expr (*litp);
        if (neg_conp_p) *conp = negate_expr (*conp);
        if (neg_var_p) var = negate_expr (var);
      }
--- 1458,1464 ----
   var = op1, neg_var_p = neg1_p;
  
        /* Now do any needed negations.  */
!       if (neg_litp_p) *minus_litp = *litp, *litp = 0;
        if (neg_conp_p) *conp = negate_expr (*conp);
        if (neg_var_p) var = negate_expr (var);
      }
***************
*** 1465,1473 ****
  
    if (negate_p)
      {
!       var = negate_expr (var);
        *conp = negate_expr (*conp);
!       *litp = negate_expr (*litp);
      }
  
    return var;
--- 1469,1480 ----
  
    if (negate_p)
      {
!       if (*litp)
!  *minus_litp = *litp, *litp = 0;
!       else if (*minus_litp)
!  *litp = *minus_litp, *minus_litp = 0;
        *conp = negate_expr (*conp);
!       var = negate_expr (var);
      }
  
    return var;
***************
*** 1475,1483 ****
  
  /* Re-associate trees split by the above function.  T1 and T2 are either
     expressions to associate or null.  Return the new expression, if any.  If
!    we build an operation, do it in TYPE and with CODE, except if CODE is a
!    MINUS_EXPR, in which case we use PLUS_EXPR since split_tree will already
!    have taken care of the negations.  */
  
  static tree
  associate_trees (t1, t2, code, type)
--- 1482,1488 ----
  
  /* Re-associate trees split by the above function.  T1 and T2 are either
     expressions to associate or null.  Return the new expression, if any.  If
!    we build an operation, do it in TYPE and with CODE.  */
  
  static tree
  associate_trees (t1, t2, code, type)
***************
*** 1490,1498 ****
    else if (t2 == 0)
      return t1;
  
-   if (code == MINUS_EXPR)
-     code = PLUS_EXPR;
- 
    /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
       try to fold this since we will have infinite recursion.  But do
       deal with any NEGATE_EXPRs.  */
--- 1495,1500 ----
***************
*** 4463,4470 ****
     other operations already in T.  WIDE_TYPE, if non-null, is a type that
     should be used for the computation if wider than our type.
  
!    For example, if we are dividing (X * 8) + (Y + 16) by 4, we can return
!    (X * 2) + (Y + 4).  We must, however, be assured that either the original
     expression would not overflow or that overflow is undefined for the type
     in the language in question.
  
--- 4465,4472 ----
     other operations already in T.  WIDE_TYPE, if non-null, is a type that
     should be used for the computation if wider than our type.
  
!    For example, if we are dividing (X * 8) + (Y * 16) by 4, we can return
!    (X * 2) + (Y * 4).  We must, however, be assured that either the original
     expression would not overflow or that overflow is undefined for the type
     in the language in question.
  
***************
*** 5680,5703 ****
     && (! FLOAT_TYPE_P (type)
         || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
   {
!    tree var0, con0, lit0, var1, con1, lit1;
  
     /* Split both trees into variables, constants, and literals.  Then
        associate each group together, the constants with literals,
        then the result with variables.  This increases the chances of
        literals being recombined later and of generating relocatable
        expressions for the sum of a constant and literal.  */
!    var0 = split_tree (arg0, code, &con0, &lit0, 0);
!    var1 = split_tree (arg1, code, &con1, &lit1, code == MINUS_EXPR);
  
     /* Only do something if we found more than two objects.  Otherwise,
        nothing has changed and we risk infinite recursion.  */
     if (2 < ((var0 != 0) + (var1 != 0) + (con0 != 0) + (con1 != 0)
!      + (lit0 != 0) + (lit1 != 0)))
       {
         var0 = associate_trees (var0, var1, code, type);
         con0 = associate_trees (con0, con1, code, type);
         lit0 = associate_trees (lit0, lit1, code, type);
         con0 = associate_trees (con0, lit0, code, type);
         return convert (type, associate_trees (var0, con0, code, type));
       }
--- 5682,5734 ----
     && (! FLOAT_TYPE_P (type)
         || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
   {
!    tree var0, con0, lit0, minus_lit0;
!    tree var1, con1, lit1, minus_lit1;
  
     /* Split both trees into variables, constants, and literals.  Then
        associate each group together, the constants with literals,
        then the result with variables.  This increases the chances of
        literals being recombined later and of generating relocatable
        expressions for the sum of a constant and literal.  */
!    var0 = split_tree (arg0, code, &con0, &lit0, &minus_lit0, 0);
!    var1 = split_tree (arg1, code, &con1, &lit1, &minus_lit1, code == MINUS_EXPR);
  
     /* Only do something if we found more than two objects.  Otherwise,
        nothing has changed and we risk infinite recursion.  */
     if (2 < ((var0 != 0) + (var1 != 0) + (con0 != 0) + (con1 != 0)
!      + (lit0 != 0) + (lit1 != 0) + (minus_lit0 != 0) + (minus_lit1 != 0)))
       {
+        /* Recombine MINUS_EXPR operands by using PLUS_EXPR. */
+        if (code == MINUS_EXPR)
+   code = PLUS_EXPR;
+ 
         var0 = associate_trees (var0, var1, code, type);
         con0 = associate_trees (con0, con1, code, type);
         lit0 = associate_trees (lit0, lit1, code, type);
+        minus_lit0 = associate_trees (minus_lit0, minus_lit1, code, type);
+ 
+        /* Preserve the MINUS_EXPR if the negative part of the literal is
+    greater than the positive part. Otherwise, the multiplicative
+    folding code (i.e extract_muldiv) may be fooled in case unsigned
+    constants are substracted, like in the following example:
+    ((integer*2 + 4) - 8U)/2.  */
+        if (minus_lit0)
+   {
+     if (lit0 == 0 || tree_int_cst_lt (lit0, minus_lit0))
+       {
+         minus_lit0 = associate_trees (minus_lit0, lit0, MINUS_EXPR, type);
+         if (con0 == 0)
+    return convert (type, associate_trees (var0, minus_lit0, MINUS_EXPR, type));
+         else
+    {
+      con0 = associate_trees (con0, minus_lit0, MINUS_EXPR, type);
+      return convert (type, associate_trees (var0, con0, PLUS_EXPR, type));
+    }
+       }
+     else
+       lit0 = associate_trees (lit0, minus_lit0, MINUS_EXPR, type);
+   }
+ 
         con0 = associate_trees (con0, lit0, code, type);
         return convert (type, associate_trees (var0, con0, code, type));
       }


/* PR c/5430 */
/* { dg-do run } */
/* { dg-options "" } */

/* Verify that the multiplicative folding code is not fooled
   by the mix between signed variables and unsigned constants. */

extern void abort (void);
extern void exit (int);

int main (void)
{
  int my_int = 924;
  unsigned int result;

  result = ((my_int*2 + 4) - 8U) / 2;
  if (result != 922U)
    abort();

  result = ((my_int*2 - 4U) + 2) / 2;
  if (result != 923U)
    abort();

  result = (((my_int + 2) * 2) - 8U - 4) / 2;
  if (result != 920U)
    abort();

  result = (((my_int + 2) * 2) - (8U + 4)) / 2;
  if (result != 920U)
    abort();

  result = ((my_int*4 + 2U) - 4U) / 2;
  if (result != 1847U)
    abort();

  exit(0);
}

--
Eric Botcazou
ebotcazou@multimania.com