Re: [patch] Fix some pessimizations due to fixes for PRs 27144 and 27639

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> Unfortunately, this patch causes a regression of builtins-14.c on (at
> least) i686-pc-linux-gnu.  The problem is that the compiler miscompiles
> itself, incorrectly optimizing the loop in real.c:div_significands.
> Because you claim to have bootstrapped and regression tested on
> i686, I supect that it wasn't the bootstrapped compiler that you
> used for regression testing [a stage1 compiler regtests fine].

here is the fix.  The problem was that we assumed that if
0 <= x <= bound, cst >= 0, and x - cst >= 0, then
x - cst <= bound - cst.  This is true in signed types,
however, for the unsigned ones, we must also know that x >= cst,
otherwise the subtraction overflows.

Bootstrapped & regtested on i686, x86_64 and ppc.

Zdenek

	* tree-ssa-loop-niter.c (implies_ge_p): New function.
	(derive_constant_upper_bound): Handle OP0 - CST in unsigned types
	correctly.

Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 114758)
--- tree-ssa-loop-niter.c	(working copy)
*************** implies_nonnegative_p (tree cond, tree v
*** 1491,1496 ****
--- 1491,1514 ----
    return nonzero_p (compare);
  }
  
+ /* Returns true if we can prove that COND ==> A >= B.  */
+ 
+ static bool
+ implies_ge_p (tree cond, tree a, tree b)
+ {
+   tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b);
+ 
+   if (nonzero_p (compare))
+     return true;
+ 
+   if (nonzero_p (cond))
+     return false;
+ 
+   compare = tree_simplify_using_condition_1 (cond, compare);
+ 
+   return nonzero_p (compare);
+ }
+ 
  /* Returns a constant upper bound on the value of expression VAL.  VAL
     is considered to be unsigned.  If its type is signed, its value must
     be nonnegative.
*************** derive_constant_upper_bound (tree val, t
*** 1554,1561 ****
  	  || !implies_nonnegative_p (additional, op0))
  	return max;
  
!       /* Canonicalize to OP0 - CST.  */
        cst = tree_to_double_int (op1);
        if (TREE_CODE (val) == PLUS_EXPR)
  	cst = double_int_neg (cst);
  
--- 1572,1582 ----
  	  || !implies_nonnegative_p (additional, op0))
  	return max;
  
!       /* Canonicalize to OP0 - CST.  Consider CST to be signed, in order to
! 	 choose the most logical way how to treat this constant regardless
! 	 of the signedness of the type.  */
        cst = tree_to_double_int (op1);
+       cst = double_int_sext (cst, TYPE_PRECISION (type));
        if (TREE_CODE (val) == PLUS_EXPR)
  	cst = double_int_neg (cst);
  
*************** derive_constant_upper_bound (tree val, t
*** 1568,1574 ****
  	  if (double_int_negative_p (cst))
  	    return max;;
  
! 	  /* Case OP0 + CST.  We need to check that
  	     BND <= MAX (type) - CST.  */
  
  	  mmax = double_int_add (max, double_int_neg (cst));
--- 1589,1595 ----
  	  if (double_int_negative_p (cst))
  	    return max;;
  
! 	  /* OP0 + CST.  We need to check that
  	     BND <= MAX (type) - CST.  */
  
  	  mmax = double_int_add (max, double_int_neg (cst));
*************** derive_constant_upper_bound (tree val, t
*** 1579,1587 ****
--- 1600,1626 ----
  	}
        else
  	{
+ 	  /* OP0 - CST, where CST >= 0.
+ 
+ 	     If TYPE is signed, we have already verified that OP0 >= 0, and we
+ 	     know that the result is nonnegative.  This implies that
+ 	     VAL <= BND - CST.
+ 
+ 	     If TYPE is unsigned, we must additionally know that OP0 >= CST,
+ 	     otherwise the operation underflows.
+ 	   */
+ 
+ 	  /* This should only happen if the type is unsigned; however, for
+ 	     programs that use overflowing signed arithmetics even with
+ 	     -fno-wrapv, we may get here for signed types as well.  */
  	  if (double_int_ucmp (bnd, cst) < 0)
  	    return max;
  
+ 	  if (TYPE_UNSIGNED (type)
+ 	      && !implies_ge_p (additional,
+ 				op0, double_int_to_tree (type, cst)))
+ 	    return max;
+ 
  	  bnd = double_int_add (bnd, double_int_neg (cst));
  	}