[patch] gcc-4.1.1-bug154079.patch

gcc-4.1.1-bug154079.patch (text/plain), 29.32 KB, created by Ryan Hill (RETIRED) on 2006-11-12 00:40:30 UTC

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 115708)
+++ gcc/tree-vrp.c	(revision 115709)
@@ -1760,7 +1760,7 @@
 			tree var)
 {
   tree init, step, chrec;
-  bool init_is_max, unknown_max;
+  enum ev_direction dir;
 
   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
      better opportunities than a regular range, but I'm not sure.  */
@@ -1780,11 +1780,14 @@
       || !is_gimple_min_invariant (step))
     return;
 
-  /* Do not adjust ranges when chrec may wrap.  */
-  if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
-			     cfg_loops->parray[CHREC_VARIABLE (chrec)],
-			     &init_is_max, &unknown_max)
-      || unknown_max)
+  dir = scev_direction (chrec);
+  if (/* Do not adjust ranges if we do not know whether the iv increases
+	 or decreases,  ... */
+      dir == EV_DIR_UNKNOWN
+      /* ... or if it may wrap.  */
+      || scev_probably_wraps_p (init, step, stmt,
+				cfg_loops->parray[CHREC_VARIABLE (chrec)],
+				true))
     return;
 
   if (!POINTER_TYPE_P (TREE_TYPE (init))
@@ -1792,7 +1795,7 @@
     {
       /* For VARYING or UNDEFINED ranges, just about anything we get
 	 from scalar evolutions should be better.  */
-      if (init_is_max)
+      if (dir == EV_DIR_DECREASES)
 	set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)),
 	                 init, vr->equiv);
       else
@@ -1804,7 +1807,7 @@
       tree min = vr->min;
       tree max = vr->max;
 
-      if (init_is_max)
+      if (dir == EV_DIR_DECREASES)
 	{
 	  /* INIT is the maximum value.  If INIT is lower than VR->MAX
 	     but no smaller than VR->MIN, set VR->MAX to INIT.  */
Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c	(revision 115708)
+++ gcc/tree-ssa-loop-niter.c	(revision 115709)
@@ -1664,33 +1664,6 @@
     }
 }
 
-/* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
-   If neither of these relations can be proved, returns 2.  */
-
-static int
-compare_trees (tree a, tree b)
-{
-  tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
-  tree type;
-
-  if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
-    type = typea;
-  else
-    type = typeb;
-
-  a = fold_convert (type, a);
-  b = fold_convert (type, b);
-
-  if (nonzero_p (fold_binary (EQ_EXPR, boolean_type_node, a, b)))
-    return 0;
-  if (nonzero_p (fold_binary (LT_EXPR, boolean_type_node, a, b)))
-    return 1;
-  if (nonzero_p (fold_binary (GT_EXPR, boolean_type_node, a, b)))
-    return -1;
-
-  return 2;
-}
-
 /* Returns true if statement S1 dominates statement S2.  */
 
 static bool
@@ -1785,123 +1758,19 @@
   return false;
 }
 
-/* Checks whether it is correct to count the induction variable BASE +
-   STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
-   numbers of iterations of a LOOP.  If it is possible, return the
-   value of step of the induction variable in the NEW_TYPE, otherwise
-   return NULL_TREE.  */
+/* Returns true if the arithmetics in TYPE can be assumed not to wrap.  */
 
-static tree
-convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
-		       tree at_stmt)
+bool
+nowrap_type_p (tree type)
 {
-  struct nb_iter_bound *bound;
-  tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
-  tree delta, step_abs;
-  tree unsigned_type, valid_niter;
+  if (!flag_wrapv
+      && INTEGRAL_TYPE_P (type)
+      && !TYPE_UNSIGNED (type))
+    return true;
 
-  /* Compute the new step.  For example, {(uchar) 100, +, (uchar) 240}
-     is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
-     keep the values of the induction variable unchanged: 100, 84, 68,
-     ...
+  if (POINTER_TYPE_P (type))
+    return true;
 
-     Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
-     to {(uint)100, +, (uint)3}.  
-
-     Before returning the new step, verify that the number of
-     iterations is less than DELTA / STEP_ABS (i.e. in the previous
-     example (256 - 100) / 3) such that the iv does not wrap (in which
-     case the operations are too difficult to be represented and
-     handled: the values of the iv should be taken modulo 256 in the
-     wider type; this is not implemented).  */
-  base_in_new_type = fold_convert (new_type, base);
-  base_plus_step_in_new_type = 
-    fold_convert (new_type,
-		  fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
-  step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
-				  base_plus_step_in_new_type,
-				  base_in_new_type);
-
-  if (TREE_CODE (step_in_new_type) != INTEGER_CST)
-    return NULL_TREE;
-
-  switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
-    {
-    case -1:
-      {
-	tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
-	delta = fold_build2 (MINUS_EXPR, new_type, extreme,
-			     base_in_new_type);
-	step_abs = step_in_new_type;
-	break;
-      }
-
-    case 1:
-      {
-	tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
-	delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
-			     extreme);
-	step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
-	break;
-      }
-
-    case 0:
-      return step_in_new_type;
-
-    default:
-      return NULL_TREE;
-    }
-
-  unsigned_type = unsigned_type_for (new_type);
-  delta = fold_convert (unsigned_type, delta);
-  step_abs = fold_convert (unsigned_type, step_abs);
-  valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
-			     delta, step_abs);
-
-  estimate_numbers_of_iterations_loop (loop);
-  for (bound = loop->bounds; bound; bound = bound->next)
-    if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
-      return step_in_new_type;
-
-  /* Fail when the loop has no bound estimations, or when no bound can
-     be used for verifying the conversion.  */
-  return NULL_TREE;
-}
-
-/* Returns true when VAR is used in pointer arithmetics.  DEPTH is
-   used for limiting the search.  */
-
-static bool
-used_in_pointer_arithmetic_p (tree var, int depth)
-{
-  use_operand_p use_p;
-  imm_use_iterator iter;
-
-  if (depth == 0
-      || TREE_CODE (var) != SSA_NAME
-      || !has_single_use (var))
-    return false;
-
-  FOR_EACH_IMM_USE_FAST (use_p, iter, var)
-    {
-      tree stmt = USE_STMT (use_p);
-
-      if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
-	{
-	  tree rhs = TREE_OPERAND (stmt, 1);
-
-	  if (TREE_CODE (rhs) == NOP_EXPR
-	      || TREE_CODE (rhs) == CONVERT_EXPR)
-	    {
-	      if (POINTER_TYPE_P (TREE_TYPE (rhs)))
-		return true;
-	      return false;
-	    }
-	  else
-	    return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt, 0),
-						 depth - 1);
-	}
-    }
   return false;
 }
 
@@ -1910,156 +1779,72 @@
    enough with respect to the step and initial condition in order to
    keep the evolution confined in TYPEs bounds.  Return true when the
    iv is known to overflow or when the property is not computable.
+ 
+   USE_OVERFLOW_SEMANTICS is true if this function should assume that
+   the rules for overflow of the given language apply (e.g., that signed
+   arithmetics in C does not overflow).  */
 
-   Initialize INIT_IS_MAX to true when the evolution goes from
-   INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
-   When this property cannot be determined, UNKNOWN_MAX is set to
-   true.  */
-
 bool
-scev_probably_wraps_p (tree type, tree base, tree step, 
+scev_probably_wraps_p (tree base, tree step, 
 		       tree at_stmt, struct loop *loop,
-		       bool *init_is_max, bool *unknown_max)
+		       bool use_oveflow_semantics)
 {
   struct nb_iter_bound *bound;
   tree delta, step_abs;
   tree unsigned_type, valid_niter;
-  tree base_plus_step, bpsps;
-  int cps, cpsps;
+  tree type = TREE_TYPE (step);
 
-  /* FIXME: The following code will not be used anymore once
-     http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
-     committed.
+  /* FIXME: We really need something like
+     http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
 
-     If AT_STMT is a cast to unsigned that is later used for
-     referencing a memory location, it is followed by a pointer
-     conversion just after.  Because pointers do not wrap, the
-     sequences that reference the memory do not wrap either.  In the
-     following example, sequences corresponding to D_13 and to D_14
-     can be proved to not wrap because they are used for computing a
-     memory access:
+     We used to test for the following situation that frequently appears
+     during address arithmetics:
 	 
        D.1621_13 = (long unsigned intD.4) D.1620_12;
        D.1622_14 = D.1621_13 * 8;
        D.1623_15 = (doubleD.29 *) D.1622_14;
-  */
-  if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
-    {
-      tree op0 = TREE_OPERAND (at_stmt, 0);
-      tree op1 = TREE_OPERAND (at_stmt, 1);
-      tree type_op1 = TREE_TYPE (op1);
 
-      if ((TYPE_UNSIGNED (type_op1)
-	   && used_in_pointer_arithmetic_p (op0, 2))
-	  || POINTER_TYPE_P (type_op1))
-	{
-	  *unknown_max = true;
-	  return false;
-	}
-    }
+     And derived that the sequence corresponding to D_14
+     can be proved to not wrap because it is used for computing a
+     memory access; however, this is not really the case -- for example,
+     if D_12 = (unsigned char) [254,+,1], then D_14 has values
+     2032, 2040, 0, 8, ..., but the code is still legal.  */
 
   if (chrec_contains_undetermined (base)
       || chrec_contains_undetermined (step)
-      || TREE_CODE (base) == REAL_CST
-      || TREE_CODE (step) == REAL_CST)
-    {
-      *unknown_max = true;
-      return true;
-    }
-
-  *unknown_max = false;
-  base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
-  bpsps = fold_build2 (PLUS_EXPR, type, base_plus_step, step);
-  cps = compare_trees (base_plus_step, base);
-  cpsps = compare_trees (bpsps, base_plus_step);
-
-  /* Check that the sequence is not wrapping in the first step: it
-     should have the same monotonicity for the first two steps.  See
-     PR23410.  */
-  if (cps != cpsps)
+      || TREE_CODE (step) != INTEGER_CST)
     return true;
 
-  switch (cps)
-    {
-    case -1:
-      {
-	tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
-	delta = fold_build2 (MINUS_EXPR, type, extreme, base);
-	step_abs = step;
-	*init_is_max = false;
-	break;
-      }
+  if (zero_p (step))
+    return false;
 
-    case 1:
-      {
-	tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
-	delta = fold_build2 (MINUS_EXPR, type, base, extreme);
-	step_abs = fold_build1 (NEGATE_EXPR, type, step);
-	*init_is_max = true;
-	break;
-      }
+  /* If we can use the fact that signed and pointer arithmetics does not
+     wrap, we are done.  */
+  if (use_oveflow_semantics && nowrap_type_p (type))
+    return false;
 
-    case 0:
-      /* This means step is equal to 0.  This should not happen.  It
-	 could happen in convert step, but not here.  Safely answer
-	 don't know as in the default case.  */
+  /* Otherwise, compute the number of iterations before we reach the
+     bound of the type, and verify that the loop is exited before this
+     occurs.  */
+  unsigned_type = unsigned_type_for (type);
+  base = fold_convert (unsigned_type, base);
 
-    default:
-      *unknown_max = true;
-      return true;
+  if (tree_int_cst_sign_bit (step))
+    {
+      tree extreme = fold_convert (unsigned_type,
+				   lower_bound_in_type (type, type));
+      delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
+      step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
+			      fold_convert (unsigned_type, step));
     }
-
-  /* If AT_STMT represents a cast operation, we may not be able to
-     take advantage of the undefinedness of signed type evolutions.
-
-     implement-c.texi states: "For conversion to a type of width
-     N, the value is reduced modulo 2^N to be within range of the
-     type;"
-
-     See PR 21959 for a test case.  Essentially, given a cast
-     operation
-     		unsigned char uc;
-		signed char sc;
-		...
-     		sc = (signed char) uc;
-		if (sc < 0)
-		  ...
-
-     where uc and sc have the scev {0, +, 1}, we would consider uc to
-     wrap around, but not sc, because it is of a signed type.  This
-     causes VRP to erroneously fold the predicate above because it
-     thinks that sc cannot be negative.  */
-  if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
+  else
     {
-      tree rhs = TREE_OPERAND (at_stmt, 1);
-      tree outer_t = TREE_TYPE (rhs);
-
-      if (!TYPE_UNSIGNED (outer_t)
-	  && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
-	{
-	  tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
-
-	  /* If the inner type is unsigned and its size and/or
-	     precision are smaller to that of the outer type, then the
-	     expression may wrap around.  */
-	  if (TYPE_UNSIGNED (inner_t)
-	      && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
-		  || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
-	    {
-	      *unknown_max = true;
-	      return true;
-	    }
-	}
+      tree extreme = fold_convert (unsigned_type,
+				   upper_bound_in_type (type, type));
+      delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
+      step_abs = fold_convert (unsigned_type, step);
     }
 
-  /* After having set INIT_IS_MAX, we can return false: when not using
-     wrapping arithmetic, signed types don't wrap.  */
-  if (!flag_wrapv && !TYPE_UNSIGNED (type))
-    return false;
-
-  unsigned_type = unsigned_type_for (type);
-  delta = fold_convert (unsigned_type, delta);
-  step_abs = fold_convert (unsigned_type, step_abs);
   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
 
   estimate_numbers_of_iterations_loop (loop);
@@ -2069,36 +1854,9 @@
 
   /* At this point we still don't have a proof that the iv does not
      overflow: give up.  */
-  *unknown_max = true;
   return true;
 }
 
-/* Return the conversion to NEW_TYPE of the STEP of an induction
-   variable BASE + STEP * I at AT_STMT.  When it fails, return
-   NULL_TREE.  */
-
-tree
-convert_step (struct loop *loop, tree new_type, tree base, tree step,
-	      tree at_stmt)
-{
-  tree base_type;
-
-  if (chrec_contains_undetermined (base)
-      || chrec_contains_undetermined (step))
-    return NULL_TREE;
-
-  base_type = TREE_TYPE (base);
-
-  /* When not using wrapping arithmetic, signed types don't wrap.  */
-  if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
-    return fold_convert (new_type, step);
-
-  if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
-    return convert_step_widening (loop, new_type, base, step, at_stmt);
-
-  return fold_convert (new_type, step);
-}
-
 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
 
 void
Index: gcc/tree-scalar-evolution.c
===================================================================
--- gcc/tree-scalar-evolution.c	(revision 115708)
+++ gcc/tree-scalar-evolution.c	(revision 115709)
@@ -2113,6 +2113,12 @@
       if (op0 == TREE_OPERAND (chrec, 0))
 	return chrec;
 
+      /* If we used chrec_convert_aggressive, we can no longer assume that
+	 signed chrecs do not overflow, as chrec_convert does, so avoid
+         calling it in that case.  */
+      if (flags & FOLD_CONVERSIONS)
+	return fold_convert (TREE_TYPE (chrec), op0);
+
       return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
 
     case SCEV_NOT_KNOWN:
Index: gcc/tree-chrec.c
===================================================================
--- gcc/tree-chrec.c	(revision 115708)
+++ gcc/tree-chrec.c	(revision 115709)
@@ -1082,6 +1082,103 @@
     }
 }
 
+static tree chrec_convert_1 (tree, tree, tree, bool);
+
+/* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
+   the scev corresponds to.  AT_STMT is the statement at that the scev is
+   evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
+   the rules for overflow of the given language apply (e.g., that signed
+   arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
+   tests, but also to enforce that the result follows them.  Returns true if the
+   conversion succeeded, false otherwise.  */
+
+bool
+convert_affine_scev (struct loop *loop, tree type,
+		     tree *base, tree *step, tree at_stmt,
+		     bool use_overflow_semantics)
+{
+  tree ct = TREE_TYPE (*step);
+  bool enforce_overflow_semantics;
+  bool must_check_src_overflow, must_check_rslt_overflow;
+  tree new_base, new_step;
+
+  /* In general,
+     (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
+     but we must check some assumptions.
+     
+     1) If [BASE, +, STEP] wraps, the equation is not valid when precision
+        of CT is smaller than the precision of TYPE.  For example, when we
+	cast unsigned char [254, +, 1] to unsigned, the values on left side
+	are 254, 255, 0, 1, ..., but those on the right side are
+	254, 255, 256, 257, ...
+     2) In case that we must also preserve the fact that signed ivs do not
+        overflow, we must additionally check that the new iv does not wrap.
+	For example, unsigned char [125, +, 1] casted to signed char could
+	become a wrapping variable with values 125, 126, 127, -128, -127, ...,
+	which would confuse optimizers that assume that this does not
+	happen.  */
+  must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
+
+  enforce_overflow_semantics = (use_overflow_semantics
+				&& nowrap_type_p (type));
+  if (enforce_overflow_semantics)
+    {
+      /* We can avoid checking whether the result overflows in the following
+	 cases:
+
+	 -- must_check_src_overflow is true, and the range of TYPE is superset
+	    of the range of CT -- i.e., in all cases except if CT signed and
+	    TYPE unsigned.
+         -- both CT and TYPE have the same precision and signedness.  */
+      if (must_check_src_overflow)
+	{
+	  if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
+	    must_check_rslt_overflow = true;
+	  else
+	    must_check_rslt_overflow = false;
+	}
+      else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
+	       && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
+	must_check_rslt_overflow = false;
+      else
+	must_check_rslt_overflow = true;
+    }
+  else
+    must_check_rslt_overflow = false;
+
+  if (must_check_src_overflow
+      && scev_probably_wraps_p (*base, *step, at_stmt, loop,
+				use_overflow_semantics))
+    return false;
+
+  new_base = chrec_convert_1 (type, *base, at_stmt,
+			      use_overflow_semantics);
+  /* The step must be sign extended, regardless of the signedness
+     of CT and TYPE.  This only needs to be handled specially when
+     CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
+     (with values 100, 99, 98, ...) from becoming signed or unsigned
+     [100, +, 255] with values 100, 355, ...; the sign-extension is 
+     performed by default when CT is signed.  */
+  new_step = *step;
+  if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
+    new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
+				use_overflow_semantics);
+  new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
+
+  if (automatically_generated_chrec_p (new_base)
+      || automatically_generated_chrec_p (new_step))
+    return false;
+
+  if (must_check_rslt_overflow
+      /* Note that in this case we cannot use the fact that signed variables
+	 do not overflow, as this is what we are verifying for the new iv.  */
+      && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
+    return false;
+
+  *base = new_base;
+  *step = new_step;
+  return true;
+}
 
 
 /* Convert CHREC to TYPE.  When the analyzer knows the context in
@@ -1111,7 +1208,28 @@
 tree 
 chrec_convert (tree type, tree chrec, tree at_stmt)
 {
+  return chrec_convert_1 (type, chrec, at_stmt, true);
+}
+
+/* Convert CHREC to TYPE.  When the analyzer knows the context in
+   which the CHREC is built, it sets AT_STMT to the statement that
+   contains the definition of the analyzed variable, otherwise the
+   conversion is less accurate: the information is used for
+   determining a more accurate estimation of the number of iterations.
+   By default AT_STMT could be safely set to NULL_TREE.
+ 
+   USE_OVERFLOW_SEMANTICS is true if this function should assume that
+   the rules for overflow of the given language apply (e.g., that signed
+   arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
+   tests, but also to enforce that the result follows them.  */
+
+static tree 
+chrec_convert_1 (tree type, tree chrec, tree at_stmt,
+		 bool use_overflow_semantics)
+{
   tree ct, res;
+  tree base, step;
+  struct loop *loop;
 
   if (automatically_generated_chrec_p (chrec))
     return chrec;
@@ -1120,56 +1238,19 @@
   if (ct == type)
     return chrec;
 
-  if (evolution_function_is_affine_p (chrec))
-    {
-      tree base, step;
-      bool dummy;
-      struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];
+  if (!evolution_function_is_affine_p (chrec))
+    goto keep_cast;
 
-      base = instantiate_parameters (loop, CHREC_LEFT (chrec));
-      step = instantiate_parameters (loop, CHREC_RIGHT (chrec));
+  loop = current_loops->parray[CHREC_VARIABLE (chrec)];
+  base = CHREC_LEFT (chrec);
+  step = CHREC_RIGHT (chrec);
 
-      /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
-	 when it is not possible to prove that the scev does not wrap.
-	 See PR22236, where a sequence 1, 2, ..., 255 has to be
-	 converted to signed char, but this would wrap: 
-	 1, 2, ..., 127, -128, ...  The result should not be
-	 {(schar)1, +, (schar)1}_x, but instead, we should keep the
-	 conversion: (schar) {(uchar)1, +, (uchar)1}_x.  */
-      if (scev_probably_wraps_p (type, base, step, at_stmt, loop,
-				 &dummy, &dummy))
-	goto failed_to_convert;
+  if (convert_affine_scev (loop, type, &base, &step, at_stmt,
+			   use_overflow_semantics))
+    return build_polynomial_chrec (loop->num, base, step);
 
-      step = convert_step (loop, type, base, step, at_stmt);
-      if (!step)
- 	{
-	failed_to_convert:;
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, "(failed conversion:");
-	      fprintf (dump_file, "\n  type: ");
-	      print_generic_expr (dump_file, type, 0);
-	      fprintf (dump_file, "\n  base: ");
-	      print_generic_expr (dump_file, base, 0);
-	      fprintf (dump_file, "\n  step: ");
-	      print_generic_expr (dump_file, step, 0);
-	      fprintf (dump_file, "\n  estimated_nb_iterations: ");
-	      print_generic_expr (dump_file, loop->estimated_nb_iterations, 0);
-	      fprintf (dump_file, "\n)\n");
-	    }
-
-	  return fold_convert (type, chrec);
-	}
-
-      return build_polynomial_chrec (CHREC_VARIABLE (chrec),
- 				     chrec_convert (type, CHREC_LEFT (chrec),
- 						    at_stmt),
- 				     step);
-    }
-
-  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
-    return chrec_dont_know;
-
+  /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
+keep_cast:
   res = fold_convert (type, chrec);
 
   /* Don't propagate overflows.  */
@@ -1232,3 +1313,25 @@
   
   return TREE_TYPE (chrec);
 }
+
+/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
+   EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
+   which of these cases happens.  */
+
+enum ev_direction
+scev_direction (tree chrec)
+{
+  tree step;
+
+  if (!evolution_function_is_affine_p (chrec))
+    return EV_DIR_UNKNOWN;
+
+  step = CHREC_RIGHT (chrec);
+  if (TREE_CODE (step) != INTEGER_CST)
+    return EV_DIR_UNKNOWN;
+
+  if (tree_int_cst_sign_bit (step))
+    return EV_DIR_DECREASES;
+  else
+    return EV_DIR_GROWS;
+}
Index: gcc/ChangeLog
===================================================================
--- gcc/ChangeLog	(revision 115708)
+++ gcc/ChangeLog	(revision 115709)
@@ -1,5 +1,30 @@
 2006-07-24  Richard Guenther  <[e-mail]>
 
+	PR tree-optimization/27795
+	PR tree-optimization/27639
+	PR tree-optimization/26719
+	Backport from mainline
+	2006-05-24  Zdenek Dvorak <[e-mail]>
+
+	* tree-vrp.c (adjust_range_with_scev): Use scev_direction and adjust
+	call to scev_probably_wraps_p.
+	* tree-ssa-loop-niter.c (compare_trees, convert_step_widening,
+	used_in_pointer_arithmetic_p, convert_step): Removed.
+	(nowrap_type_p): New function.
+	(scev_probably_wraps_p): Rewritten.
+	* tree-scalar-evolution.c (instantiate_parameters_1): Do not call
+	chrec_convert if chrec_convert_aggressive might have been used.
+	* tree-chrec.c (convert_affine_scev, chrec_convert_1,
+	scev_direction): New functions.
+	(chrec_convert): Changed to a wrapper over chrec_convert_1.
+	* tree-ssa-loop-ivopts.c (idx_find_step): Use convert_affine_scev
+	instead of convert_step.
+	* tree-flow.h (scev_probably_wraps_p): Declaration changed.
+	(convert_step): Declaration removed.
+	(convert_affine_scev, nowrap_type_p, scev_direction): Declare.
+
[phone]  Richard Guenther  <[e-mail]>
+
 	PR tree-optimization/28029
 	Backport
 	2006-02-15 Daniel Berlin  <[e-mail]>
Index: gcc/testsuite/gcc.dg/pr27639.c
===================================================================
--- gcc/testsuite/gcc.dg/pr27639.c	(revision 0)
+++ gcc/testsuite/gcc.dg/pr27639.c	(revision 115709)
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -std=c99" } */
+
+char heap[50000];
+
+int
+main ()
+{
+  for (unsigned ix = sizeof (heap); ix--;)
+    heap[ix] = ix;
+  return 0;
+}
Index: gcc/testsuite/gcc.dg/tree-ssa/scev-cast.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/scev-cast.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/scev-cast.c	(revision 115709)
@@ -0,0 +1,26 @@
+/* A test for various conversions of chrecs.  */
+
+/* { dg-do compile { target i?86-*-* x86_64-*-* } } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void blas (char xxx);
+void blau (unsigned char xxx);
+
+void tst(void)
+{
+  unsigned i;
+
+  for (i = 0; i < 128; i++) /* This cast to char has to be preserved.  */
+    blas ((char) i);
+  for (i = 0; i < 127; i++) /* And this one does not.  */
+    blas ((char) i);
+  for (i = 0; i < 255; i++) /* This cast is not necessary.  */
+    blau ((unsigned char) i);
+  for (i = 0; i < 256; i++)
+    blau ((unsigned char) i); /* This one is necessary.  */
+}
+
+/* { dg-final { scan-tree-dump-times "\\(int\\) \\(unsigned char\\)" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\(int\\) \\(char\\)" 1 "optimized" } } */
+
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/pr26719.c
===================================================================
--- gcc/testsuite/gcc.dg/pr26719.c	(revision 0)
+++ gcc/testsuite/gcc.dg/pr26719.c	(revision 115709)
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+void abort (void);
+
+int table[32][256];
+
+int main(void)
+{
+  int i, j;
+
+  for (i = 0; i < 32; i++)
+    for (j = 0; j < 256; j++)
+      table[i][j] = ((signed char)j) * i;
+
+  if (table[9][132] != -1116)
+    abort ();
+
+  return 0;
+}
Index: gcc/testsuite/ChangeLog
===================================================================
--- gcc/testsuite/ChangeLog	(revision 115708)
+++ gcc/testsuite/ChangeLog	(revision 115709)
@@ -1,5 +1,17 @@
 2006-07-24  Richard Guenther  <[e-mail]>
 
+	PR tree-optimization/27795
+	PR tree-optimization/27639
+	PR tree-optimization/26719
+	Backport from mainline
+	2006-05-24  Zdenek Dvorak <[e-mail]>
+
+	* gcc.dg/pr27639.c: New test.
+	* gcc.dg/pr26719.c: New test.
+	* gcc.dg/tree-ssa/scev-cast.c: New test.
+
[phone]  Richard Guenther  <[e-mail]>
+
 	PR tree-optimization/28029
 	* gcc.dg/vect/pr28029.c: New testcase.
 
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 115708)
+++ gcc/tree-ssa-loop-ivopts.c	(revision 115709)
@@ -1385,7 +1385,7 @@
 {
   struct ifs_ivopts_data *dta = data;
   struct iv *iv;
-  tree step, iv_step, lbound, off;
+  tree step, iv_base, iv_step, lbound, off;
   struct loop *loop = dta->ivopts_data->current_loop;
 
   if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
@@ -1438,12 +1438,11 @@
     /* The step for pointer arithmetics already is 1 byte.  */
     step = build_int_cst (sizetype, 1);
 
-  /* FIXME: convert_step should not be used outside chrec_convert: fix
-     this by calling chrec_convert.  */
-  iv_step = convert_step (dta->ivopts_data->current_loop,
-			  sizetype, iv->base, iv->step, dta->stmt);
-
-  if (!iv_step)
+  iv_base = iv->base;
+  iv_step = iv->step;
+  if (!convert_affine_scev (dta->ivopts_data->current_loop,
+			    sizetype, &iv_base, &iv_step, dta->stmt,
+			    false))
     {
       /* The index might wrap.  */
       return false;
Index: gcc/tree-flow.h
===================================================================
--- gcc/tree-flow.h	(revision 115708)
+++ gcc/tree-flow.h	(revision 115709)
@@ -735,9 +735,13 @@
 tree loop_niter_by_eval (struct loop *, edge);
 tree find_loop_niter_by_eval (struct loop *, edge *);
 void estimate_numbers_of_iterations (struct loops *);
-bool scev_probably_wraps_p (tree, tree, tree, tree, struct loop *, bool *,
-			    bool *);
-tree convert_step (struct loop *, tree, tree, tree, tree);
+bool scev_probably_wraps_p (tree, tree, tree, struct loop *, bool);
+bool convert_affine_scev (struct loop *, tree, tree *, tree *, tree, bool);
+
+bool nowrap_type_p (tree);
+enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN};
+enum ev_direction scev_direction (tree);
+
 void free_numbers_of_iterations_estimates (struct loops *);
 void free_numbers_of_iterations_estimates_loop (struct loop *);
 void rewrite_into_loop_closed_ssa (bitmap, unsigned);