Attachment #101714 for bug #154079

View | Details | Raw Unified | Return to bug 154079
Collapse All | Expand All

Lines 1760-1766 Link Here

(-)gcc/tree-vrp.c (-8 / +11 lines)
1760	tree var)	1760	tree var)
1761	{	1761	{
1762	tree init, step, chrec;	1762	tree init, step, chrec;
1763	bool init_is_max, unknown_max;	1763	enum ev_direction dir;
1764		1764
1765	/* TODO. Don't adjust anti-ranges. An anti-range may provide	1765	/* TODO. Don't adjust anti-ranges. An anti-range may provide
1766	better opportunities than a regular range, but I'm not sure. */	1766	better opportunities than a regular range, but I'm not sure. */
Lines 1780-1790 Link Here
1780	\|\| !is_gimple_min_invariant (step))	1780	\|\| !is_gimple_min_invariant (step))
1781	return;	1781	return;
1782		1782
1783	/* Do not adjust ranges when chrec may wrap. */	1783	dir = scev_direction (chrec);
1784	if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,	1784	if (/* Do not adjust ranges if we do not know whether the iv increases
1785	cfg_loops->parray[CHREC_VARIABLE (chrec)],	1785	or decreases, ... */
1786	&init_is_max, &unknown_max)	1786	dir == EV_DIR_UNKNOWN
1787	\|\| unknown_max)	1787	/* ... or if it may wrap. */
		1788	\|\| scev_probably_wraps_p (init, step, stmt,
		1789	cfg_loops->parray[CHREC_VARIABLE (chrec)],
		1790	true))
1788	return;	1791	return;
1789		1792
1790	if (!POINTER_TYPE_P (TREE_TYPE (init))	1793	if (!POINTER_TYPE_P (TREE_TYPE (init))
Lines 1792-1798 Link Here
1792	{	1795	{
1793	/* For VARYING or UNDEFINED ranges, just about anything we get	1796	/* For VARYING or UNDEFINED ranges, just about anything we get
1794	from scalar evolutions should be better. */	1797	from scalar evolutions should be better. */
1795	if (init_is_max)	1798	if (dir == EV_DIR_DECREASES)
1796	set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)),	1799	set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)),
1797	init, vr->equiv);	1800	init, vr->equiv);
1798	else	1801	else
Lines 1804-1810 Link Here
1804	tree min = vr->min;	1807	tree min = vr->min;
1805	tree max = vr->max;	1808	tree max = vr->max;
1806		1809
1807	if (init_is_max)	1810	if (dir == EV_DIR_DECREASES)
1808	{	1811	{
1809	/* INIT is the maximum value. If INIT is lower than VR->MAX	1812	/* INIT is the maximum value. If INIT is lower than VR->MAX
1810	but no smaller than VR->MIN, set VR->MAX to INIT. */	1813	but no smaller than VR->MIN, set VR->MAX to INIT. */




    }
}

/* 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

  return false;
}

/* Returns true if the arithmetics in TYPE can be assumed not to wrap.  */
   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.  */

bool
nowrap_type_p (tree type)
		       tree at_stmt)
{
  if (!flag_wrapv
      && INTEGRAL_TYPE_P (type)
      && !TYPE_UNSIGNED (type))
    return true;

  if (POINTER_TYPE_P (type))
    return true;
     keep the values of the induction variable unchanged: 100, 84, 68,
     ...

     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;
}


   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 base, tree step, 
		       tree at_stmt, struct loop *loop,
		       bool use_oveflow_semantics)
{
  struct nb_iter_bound *bound;
  tree delta, step_abs;
  tree unsigned_type, valid_niter;
  tree type = TREE_TYPE (step);
  int cps, cpsps;

  /* FIXME: We really need something like
     http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
     committed.

     We used to test for the following situation that frequently appears
     during address arithmetics:
     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:
	 
       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);

     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.  */
	  return false;
	}
    }

  if (chrec_contains_undetermined (base)
      || chrec_contains_undetermined (step)
      || TREE_CODE (step) != INTEGER_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)
    return true;

  if (zero_p (step))
    return false;
    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 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;
	step_abs = fold_build1 (NEGATE_EXPR, type, step);
	*init_is_max = true;
	break;
      }

  /* 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);

  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));
    }
  else
  /* 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)
    {
      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);
	  && (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;
	    }
	}
    }

  /* 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);


  /* 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

Lines 2113-2118 Link Here

(-)gcc/tree-scalar-evolution.c (+6 lines)
2113	if (op0 == TREE_OPERAND (chrec, 0))	2113	if (op0 == TREE_OPERAND (chrec, 0))
2114	return chrec;	2114	return chrec;
2115		2115
		2116	/* If we used chrec_convert_aggressive, we can no longer assume that
		2117	signed chrecs do not overflow, as chrec_convert does, so avoid
		2118	calling it in that case. */
		2119	if (flags & FOLD_CONVERSIONS)
		2120	return fold_convert (TREE_TYPE (chrec), op0);
		2121
2116	return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);	2122	return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2117		2123
2118	case SCEV_NOT_KNOWN:	2124	case SCEV_NOT_KNOWN:




    }
}

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

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;

  if (ct == type)
    return chrec;

  if (!evolution_function_is_affine_p (chrec))
    goto keep_cast;
      tree base, step;
      bool dummy;
      struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];

  loop = current_loops->parray[CHREC_VARIABLE (chrec)];
  base = CHREC_LEFT (chrec);
  step = CHREC_RIGHT (chrec);

  if (convert_affine_scev (loop, type, &base, &step, at_stmt,
			   use_overflow_semantics))
    return build_polynomial_chrec (loop->num, base, step);
	 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 we cannot propagate the cast inside the chrec, just keep the cast.  */
keep_cast:
 	{
	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;

  res = fold_convert (type, chrec);

  /* Don't propagate overflows.  */

  
  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;
}




2006-07-24  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/27795
	PR tree-optimization/27639
	PR tree-optimization/26719
	Backport from mainline
	2006-05-24  Zdenek Dvorak <dvorakz@suse.cz>

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

2006-07-24  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/28029
	Backport
	2006-02-15 Daniel Berlin  <dberlin@dberlin.org>




/* { dg-do compile } */
/* { dg-options "-O2 -std=c99" } */

char heap[50000];

int
main ()
{
  for (unsigned ix = sizeof (heap); ix--;)
    heap[ix] = ix;
  return 0;
}




/* 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" } } */

Line 0 Link Here

(-)gcc/testsuite/gcc.dg/pr26719.c (+21 lines)
	1	/* { dg-do compile } */
	2	/* { dg-do run } */
	3	/* { dg-options "-O2" } */
	4
	5	void abort (void);
	6
	7	int table[32][256];
	8
	9	int main(void)
	10	{
	11	int i, j;
	12
	13	for (i = 0; i < 32; i++)
	14	for (j = 0; j < 256; j++)
	15	table[i][j] = ((signed char)j) * i;
	16
	17	if (table[9][132] != -1116)
	18	abort ();
	19
	20	return 0;
	21	}




2006-07-24  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/27795
	PR tree-optimization/27639
	PR tree-optimization/26719
	Backport from mainline
	2006-05-24  Zdenek Dvorak <dvorakz@suse.cz>

	* gcc.dg/pr27639.c: New test.
	* gcc.dg/pr26719.c: New test.
	* gcc.dg/tree-ssa/scev-cast.c: New test.

2006-07-24  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/28029
	* gcc.dg/vect/pr28029.c: New testcase.





{
  struct ifs_ivopts_data *dta = data;
  struct iv *iv;
  tree step, iv_base, iv_step, lbound, off;
  struct loop *loop = dta->ivopts_data->current_loop;

  if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF

    /* The step for pointer arithmetics already is 1 byte.  */
    step = build_int_cst (sizetype, 1);

  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))
  if (!iv_step)
    {
      /* The index might wrap.  */
      return false;

Lines 735-743 Link Here

(-)gcc/tree-flow.h (-3 / +7 lines)
735	tree loop_niter_by_eval (struct loop *, edge);	735	tree loop_niter_by_eval (struct loop *, edge);
736	tree find_loop_niter_by_eval (struct loop , edge );	736	tree find_loop_niter_by_eval (struct loop , edge );
737	void estimate_numbers_of_iterations (struct loops *);	737	void estimate_numbers_of_iterations (struct loops *);
738	bool scev_probably_wraps_p (tree, tree, tree, tree, struct loop , bool ,	738	bool scev_probably_wraps_p (tree, tree, tree, struct loop *, bool);
739	bool *);	739	bool convert_affine_scev (struct loop , tree, tree , tree *, tree, bool);
740	tree convert_step (struct loop *, tree, tree, tree, tree);	740
		741	bool nowrap_type_p (tree);
		742	enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN};
		743	enum ev_direction scev_direction (tree);
		744
741	void free_numbers_of_iterations_estimates (struct loops *);	745	void free_numbers_of_iterations_estimates (struct loops *);
742	void free_numbers_of_iterations_estimates_loop (struct loop *);	746	void free_numbers_of_iterations_estimates_loop (struct loop *);
743	void rewrite_into_loop_closed_ssa (bitmap, unsigned);	747	void rewrite_into_loop_closed_ssa (bitmap, unsigned);

Return to bug 154079

Lines 1385-1391 Link Here

(-)gcc/tree-ssa-loop-ivopts.c (-7 / +6 lines)
1385	{	1385	{
1386	struct ifs_ivopts_data *dta = data;	1386	struct ifs_ivopts_data *dta = data;
1387	struct iv *iv;	1387	struct iv *iv;
1388	tree step, iv_step, lbound, off;	1388	tree step, iv_base, iv_step, lbound, off;
1389	struct loop *loop = dta->ivopts_data->current_loop;	1389	struct loop *loop = dta->ivopts_data->current_loop;
1390		1390
1391	if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF	1391	if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
Lines 1438-1449 Link Here
1438	/* The step for pointer arithmetics already is 1 byte. */	1438	/* The step for pointer arithmetics already is 1 byte. */
1439	step = build_int_cst (sizetype, 1);	1439	step = build_int_cst (sizetype, 1);
1440		1440
1441	/* FIXME: convert_step should not be used outside chrec_convert: fix	1441	iv_base = iv->base;
1442	this by calling chrec_convert. */	1442	iv_step = iv->step;
1443	iv_step = convert_step (dta->ivopts_data->current_loop,	1443	if (!convert_affine_scev (dta->ivopts_data->current_loop,
1444	sizetype, iv->base, iv->step, dta->stmt);	1444	sizetype, &iv_base, &iv_step, dta->stmt,
1445		1445	false))
1446	if (!iv_step)
1447	{	1446	{
1448	/* The index might wrap. */	1447	/* The index might wrap. */
1449	return false;	1448	return false;

Lines 1664-1696 Link Here

(-)gcc/tree-ssa-loop-niter.c (-291 / +49 lines)
1664	}	1664	}
1665	}	1665	}
1666		1666
1667	/* If A > B, returns -1. If A == B, returns 0. If A < B, returns 1.
1668	If neither of these relations can be proved, returns 2. */
1669
1670	static int
1671	compare_trees (tree a, tree b)
1672	{
1673	tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1674	tree type;
1675
1676	if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1677	type = typea;
1678	else
1679	type = typeb;
1680
1681	a = fold_convert (type, a);
1682	b = fold_convert (type, b);
1683
1684	if (nonzero_p (fold_binary (EQ_EXPR, boolean_type_node, a, b)))
1685	return 0;
1686	if (nonzero_p (fold_binary (LT_EXPR, boolean_type_node, a, b)))
1687	return 1;
1688	if (nonzero_p (fold_binary (GT_EXPR, boolean_type_node, a, b)))
1689	return -1;
1690
1691	return 2;
1692	}
1693
1694	/* Returns true if statement S1 dominates statement S2. */	1667	/* Returns true if statement S1 dominates statement S2. */
1695		1668
1696	static bool	1669	static bool
Lines 1785-1907 Link Here
1785	return false;	1758	return false;
1786	}	1759	}
1787		1760
1788	/* Checks whether it is correct to count the induction variable BASE +	1761	/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
1789	STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
1790	numbers of iterations of a LOOP. If it is possible, return the
1791	value of step of the induction variable in the NEW_TYPE, otherwise
1792	return NULL_TREE. */
1793		1762
1794	static tree	1763	bool
1795	convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,	1764	nowrap_type_p (tree type)
1796	tree at_stmt)
1797	{	1765	{
1798	struct nb_iter_bound *bound;	1766	if (!flag_wrapv
1799	tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;	1767	&& INTEGRAL_TYPE_P (type)
1800	tree delta, step_abs;	1768	&& !TYPE_UNSIGNED (type))
1801	tree unsigned_type, valid_niter;	1769	return true;
1802		1770
1803	/* Compute the new step. For example, {(uchar) 100, +, (uchar) 240}	1771	if (POINTER_TYPE_P (type))
1804	is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to	1772	return true;
1805	keep the values of the induction variable unchanged: 100, 84, 68,
1806	...
1807		1773
1808	Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
1809	to {(uint)100, +, (uint)3}.
1810
1811	Before returning the new step, verify that the number of
1812	iterations is less than DELTA / STEP_ABS (i.e. in the previous
1813	example (256 - 100) / 3) such that the iv does not wrap (in which
1814	case the operations are too difficult to be represented and
1815	handled: the values of the iv should be taken modulo 256 in the
1816	wider type; this is not implemented). */
1817	base_in_new_type = fold_convert (new_type, base);
1818	base_plus_step_in_new_type =
1819	fold_convert (new_type,
1820	fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
1821	step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
1822	base_plus_step_in_new_type,
1823	base_in_new_type);
1824
1825	if (TREE_CODE (step_in_new_type) != INTEGER_CST)
1826	return NULL_TREE;
1827
1828	switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
1829	{
1830	case -1:
1831	{
1832	tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
1833	delta = fold_build2 (MINUS_EXPR, new_type, extreme,
1834	base_in_new_type);
1835	step_abs = step_in_new_type;
1836	break;
1837	}
1838
1839	case 1:
1840	{
1841	tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
1842	delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
1843	extreme);
1844	step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
1845	break;
1846	}
1847
1848	case 0:
1849	return step_in_new_type;
1850
1851	default:
1852	return NULL_TREE;
1853	}
1854
1855	unsigned_type = unsigned_type_for (new_type);
1856	delta = fold_convert (unsigned_type, delta);
1857	step_abs = fold_convert (unsigned_type, step_abs);
1858	valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
1859	delta, step_abs);
1860
1861	estimate_numbers_of_iterations_loop (loop);
1862	for (bound = loop->bounds; bound; bound = bound->next)
1863	if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
1864	return step_in_new_type;
1865
1866	/* Fail when the loop has no bound estimations, or when no bound can
1867	be used for verifying the conversion. */
1868	return NULL_TREE;
1869	}
1870
1871	/* Returns true when VAR is used in pointer arithmetics. DEPTH is
1872	used for limiting the search. */
1873
1874	static bool
1875	used_in_pointer_arithmetic_p (tree var, int depth)
1876	{
1877	use_operand_p use_p;
1878	imm_use_iterator iter;
1879
1880	if (depth == 0
1881	\|\| TREE_CODE (var) != SSA_NAME
1882	\|\| !has_single_use (var))
1883	return false;
1884
1885	FOR_EACH_IMM_USE_FAST (use_p, iter, var)
1886	{
1887	tree stmt = USE_STMT (use_p);
1888
1889	if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
1890	{
1891	tree rhs = TREE_OPERAND (stmt, 1);
1892
1893	if (TREE_CODE (rhs) == NOP_EXPR
1894	\|\| TREE_CODE (rhs) == CONVERT_EXPR)
1895	{
1896	if (POINTER_TYPE_P (TREE_TYPE (rhs)))
1897	return true;
1898	return false;
1899	}
1900	else
1901	return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt, 0),
1902	depth - 1);
1903	}
1904	}
1905	return false;	1774	return false;
1906	}	1775	}
1907		1776
Lines 1910-2065 Link Here
1910	enough with respect to the step and initial condition in order to	1779	enough with respect to the step and initial condition in order to
1911	keep the evolution confined in TYPEs bounds. Return true when the	1780	keep the evolution confined in TYPEs bounds. Return true when the
1912	iv is known to overflow or when the property is not computable.	1781	iv is known to overflow or when the property is not computable.
		1782
		1783	USE_OVERFLOW_SEMANTICS is true if this function should assume that
		1784	the rules for overflow of the given language apply (e.g., that signed
		1785	arithmetics in C does not overflow). */
1913		1786
1914	Initialize INIT_IS_MAX to true when the evolution goes from
1915	INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
1916	When this property cannot be determined, UNKNOWN_MAX is set to
1917	true. */
1918
1919	bool	1787	bool
1920	scev_probably_wraps_p (tree type, tree base, tree step,	1788	scev_probably_wraps_p (tree base, tree step,
1921	tree at_stmt, struct loop *loop,	1789	tree at_stmt, struct loop *loop,
1922	bool init_is_max, bool unknown_max)	1790	bool use_oveflow_semantics)
1923	{	1791	{
1924	struct nb_iter_bound *bound;	1792	struct nb_iter_bound *bound;
1925	tree delta, step_abs;	1793	tree delta, step_abs;
1926	tree unsigned_type, valid_niter;	1794	tree unsigned_type, valid_niter;
1927	tree base_plus_step, bpsps;	1795	tree type = TREE_TYPE (step);
1928	int cps, cpsps;
1929		1796
1930	/* FIXME: The following code will not be used anymore once	1797	/* FIXME: We really need something like
1931	http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is	1798	http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
1932	committed.
1933		1799
1934	If AT_STMT is a cast to unsigned that is later used for	1800	We used to test for the following situation that frequently appears
1935	referencing a memory location, it is followed by a pointer	1801	during address arithmetics:
1936	conversion just after. Because pointers do not wrap, the
1937	sequences that reference the memory do not wrap either. In the
1938	following example, sequences corresponding to D_13 and to D_14
1939	can be proved to not wrap because they are used for computing a
1940	memory access:
1941		1802
1942	D.1621_13 = (long unsigned intD.4) D.1620_12;	1803	D.1621_13 = (long unsigned intD.4) D.1620_12;
1943	D.1622_14 = D.1621_13 * 8;	1804	D.1622_14 = D.1621_13 * 8;
1944	D.1623_15 = (doubleD.29 *) D.1622_14;	1805	D.1623_15 = (doubleD.29 *) D.1622_14;
1945	*/
1946	if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1947	{
1948	tree op0 = TREE_OPERAND (at_stmt, 0);
1949	tree op1 = TREE_OPERAND (at_stmt, 1);
1950	tree type_op1 = TREE_TYPE (op1);
1951		1806
1952	if ((TYPE_UNSIGNED (type_op1)	1807	And derived that the sequence corresponding to D_14
1953	&& used_in_pointer_arithmetic_p (op0, 2))	1808	can be proved to not wrap because it is used for computing a
1954	\|\| POINTER_TYPE_P (type_op1))	1809	memory access; however, this is not really the case -- for example,
1955	{	1810	if D_12 = (unsigned char) [254,+,1], then D_14 has values
1956	*unknown_max = true;	1811	2032, 2040, 0, 8, ..., but the code is still legal. */
1957	return false;
1958	}
1959	}
1960		1812
1961	if (chrec_contains_undetermined (base)	1813	if (chrec_contains_undetermined (base)
1962	\|\| chrec_contains_undetermined (step)	1814	\|\| chrec_contains_undetermined (step)
1963	\|\| TREE_CODE (base) == REAL_CST	1815	\|\| TREE_CODE (step) != INTEGER_CST)
1964	\|\| TREE_CODE (step) == REAL_CST)
1965	{
1966	*unknown_max = true;
1967	return true;
1968	}
1969
1970	*unknown_max = false;
1971	base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
1972	bpsps = fold_build2 (PLUS_EXPR, type, base_plus_step, step);
1973	cps = compare_trees (base_plus_step, base);
1974	cpsps = compare_trees (bpsps, base_plus_step);
1975
1976	/* Check that the sequence is not wrapping in the first step: it
1977	should have the same monotonicity for the first two steps. See
1978	PR23410. */
1979	if (cps != cpsps)
1980	return true;	1816	return true;
1981		1817
1982	switch (cps)	1818	if (zero_p (step))
1983	{	1819	return false;
1984	case -1:
1985	{
1986	tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
1987	delta = fold_build2 (MINUS_EXPR, type, extreme, base);
1988	step_abs = step;
1989	*init_is_max = false;
1990	break;
1991	}
1992		1820
1993	case 1:	1821	/* If we can use the fact that signed and pointer arithmetics does not
1994	{	1822	wrap, we are done. */
1995	tree extreme = lower_bound_in_type (type, TREE_TYPE (base));	1823	if (use_oveflow_semantics && nowrap_type_p (type))
1996	delta = fold_build2 (MINUS_EXPR, type, base, extreme);	1824	return false;
1997	step_abs = fold_build1 (NEGATE_EXPR, type, step);
1998	*init_is_max = true;
1999	break;
2000	}
2001		1825
2002	case 0:	1826	/* Otherwise, compute the number of iterations before we reach the
2003	/* This means step is equal to 0. This should not happen. It	1827	bound of the type, and verify that the loop is exited before this
2004	could happen in convert step, but not here. Safely answer	1828	occurs. */
2005	don't know as in the default case. */	1829	unsigned_type = unsigned_type_for (type);
		1830	base = fold_convert (unsigned_type, base);
2006		1831
2007	default:	1832	if (tree_int_cst_sign_bit (step))
2008	*unknown_max = true;	1833	{
2009	return true;	1834	tree extreme = fold_convert (unsigned_type,
		1835	lower_bound_in_type (type, type));
		1836	delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
		1837	step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
		1838	fold_convert (unsigned_type, step));
2010	}	1839	}
2011		1840	else
2012	/* If AT_STMT represents a cast operation, we may not be able to
2013	take advantage of the undefinedness of signed type evolutions.
2014
2015	implement-c.texi states: "For conversion to a type of width
2016	N, the value is reduced modulo 2^N to be within range of the
2017	type;"
2018
2019	See PR 21959 for a test case. Essentially, given a cast
2020	operation
2021	unsigned char uc;
2022	signed char sc;
2023	...
2024	sc = (signed char) uc;
2025	if (sc < 0)
2026	...
2027
2028	where uc and sc have the scev {0, +, 1}, we would consider uc to
2029	wrap around, but not sc, because it is of a signed type. This
2030	causes VRP to erroneously fold the predicate above because it
2031	thinks that sc cannot be negative. */
2032	if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
2033	{	1841	{
2034	tree rhs = TREE_OPERAND (at_stmt, 1);	1842	tree extreme = fold_convert (unsigned_type,
2035	tree outer_t = TREE_TYPE (rhs);	1843	upper_bound_in_type (type, type));
2036		1844	delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2037	if (!TYPE_UNSIGNED (outer_t)	1845	step_abs = fold_convert (unsigned_type, step);
2038	&& (TREE_CODE (rhs) == NOP_EXPR \|\| TREE_CODE (rhs) == CONVERT_EXPR))
2039	{
2040	tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
2041
2042	/* If the inner type is unsigned and its size and/or
2043	precision are smaller to that of the outer type, then the
2044	expression may wrap around. */
2045	if (TYPE_UNSIGNED (inner_t)
2046	&& (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
2047	\|\| TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
2048	{
2049	*unknown_max = true;
2050	return true;
2051	}
2052	}
2053	}	1846	}
2054		1847
2055	/* After having set INIT_IS_MAX, we can return false: when not using
2056	wrapping arithmetic, signed types don't wrap. */
2057	if (!flag_wrapv && !TYPE_UNSIGNED (type))
2058	return false;
2059
2060	unsigned_type = unsigned_type_for (type);
2061	delta = fold_convert (unsigned_type, delta);
2062	step_abs = fold_convert (unsigned_type, step_abs);
2063	valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);	1848	valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
2064		1849
2065	estimate_numbers_of_iterations_loop (loop);	1850	estimate_numbers_of_iterations_loop (loop);
Lines 2069-2104 Link Here
2069		1854
2070	/* At this point we still don't have a proof that the iv does not	1855	/* At this point we still don't have a proof that the iv does not
2071	overflow: give up. */	1856	overflow: give up. */
2072	*unknown_max = true;
2073	return true;	1857	return true;
2074	}	1858	}
2075		1859
2076	/* Return the conversion to NEW_TYPE of the STEP of an induction
2077	variable BASE + STEP * I at AT_STMT. When it fails, return
2078	NULL_TREE. */
2079
2080	tree
2081	convert_step (struct loop *loop, tree new_type, tree base, tree step,
2082	tree at_stmt)
2083	{
2084	tree base_type;
2085
2086	if (chrec_contains_undetermined (base)
2087	\|\| chrec_contains_undetermined (step))
2088	return NULL_TREE;
2089
2090	base_type = TREE_TYPE (base);
2091
2092	/* When not using wrapping arithmetic, signed types don't wrap. */
2093	if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
2094	return fold_convert (new_type, step);
2095
2096	if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
2097	return convert_step_widening (loop, new_type, base, step, at_stmt);
2098
2099	return fold_convert (new_type, step);
2100	}
2101
2102	/* Frees the information on upper bounds on numbers of iterations of LOOP. */	1860	/* Frees the information on upper bounds on numbers of iterations of LOOP. */
2103		1861
2104	void	1862	void

Lines 1082-1087 Link Here

(-)gcc/tree-chrec.c (-47 / +150 lines)
1082	}	1082	}
1083	}	1083	}
1084		1084
		1085	static tree chrec_convert_1 (tree, tree, tree, bool);
		1086
		1087	/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
		1088	the scev corresponds to. AT_STMT is the statement at that the scev is
		1089	evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
		1090	the rules for overflow of the given language apply (e.g., that signed
		1091	arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
		1092	tests, but also to enforce that the result follows them. Returns true if the
		1093	conversion succeeded, false otherwise. */
		1094
		1095	bool
		1096	convert_affine_scev (struct loop *loop, tree type,
		1097	tree base, tree step, tree at_stmt,
		1098	bool use_overflow_semantics)
		1099	{
		1100	tree ct = TREE_TYPE (*step);
		1101	bool enforce_overflow_semantics;
		1102	bool must_check_src_overflow, must_check_rslt_overflow;
		1103	tree new_base, new_step;
		1104
		1105	/* In general,
		1106	(TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
		1107	but we must check some assumptions.
		1108
		1109	1) If [BASE, +, STEP] wraps, the equation is not valid when precision
		1110	of CT is smaller than the precision of TYPE. For example, when we
		1111	cast unsigned char [254, +, 1] to unsigned, the values on left side
		1112	are 254, 255, 0, 1, ..., but those on the right side are
		1113	254, 255, 256, 257, ...
		1114	2) In case that we must also preserve the fact that signed ivs do not
		1115	overflow, we must additionally check that the new iv does not wrap.
		1116	For example, unsigned char [125, +, 1] casted to signed char could
		1117	become a wrapping variable with values 125, 126, 127, -128, -127, ...,
		1118	which would confuse optimizers that assume that this does not
		1119	happen. */
		1120	must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
		1121
		1122	enforce_overflow_semantics = (use_overflow_semantics
		1123	&& nowrap_type_p (type));
		1124	if (enforce_overflow_semantics)
		1125	{
		1126	/* We can avoid checking whether the result overflows in the following
		1127	cases:
		1128
		1129	-- must_check_src_overflow is true, and the range of TYPE is superset
		1130	of the range of CT -- i.e., in all cases except if CT signed and
		1131	TYPE unsigned.
		1132	-- both CT and TYPE have the same precision and signedness. */
		1133	if (must_check_src_overflow)
		1134	{
		1135	if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
		1136	must_check_rslt_overflow = true;
		1137	else
		1138	must_check_rslt_overflow = false;
		1139	}
		1140	else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
		1141	&& TYPE_PRECISION (ct) == TYPE_PRECISION (type))
		1142	must_check_rslt_overflow = false;
		1143	else
		1144	must_check_rslt_overflow = true;
		1145	}
		1146	else
		1147	must_check_rslt_overflow = false;
		1148
1149	if (must_check_src_overflow
1150	&& scev_probably_wraps_p (base, step, at_stmt, loop,
1151	use_overflow_semantics))
1152	return false;
1153
1154	new_base = chrec_convert_1 (type, *base, at_stmt,
1155	use_overflow_semantics);
1156	/* The step must be sign extended, regardless of the signedness
1157	of CT and TYPE. This only needs to be handled specially when
1158	CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1159	(with values 100, 99, 98, ...) from becoming signed or unsigned
1160	[100, +, 255] with values 100, 355, ...; the sign-extension is
1161	performed by default when CT is signed. */
1162	new_step = *step;
1163	if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1164	new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1165	use_overflow_semantics);
1166	new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
1167
1168	if (automatically_generated_chrec_p (new_base)
1169	\|\| automatically_generated_chrec_p (new_step))
1170	return false;
1171
1172	if (must_check_rslt_overflow
1173	/* Note that in this case we cannot use the fact that signed variables
1174	do not overflow, as this is what we are verifying for the new iv. */
1175	&& scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1176	return false;
1177
1178	*base = new_base;
1179	*step = new_step;
1180	return true;
1181	}
1085		1182
1086		1183
1087	/* Convert CHREC to TYPE. When the analyzer knows the context in	1184	/* Convert CHREC to TYPE. When the analyzer knows the context in
Lines 1111-1117 Link Here
1111	tree	1208	tree
1112	chrec_convert (tree type, tree chrec, tree at_stmt)	1209	chrec_convert (tree type, tree chrec, tree at_stmt)
1113	{	1210	{
		1211	return chrec_convert_1 (type, chrec, at_stmt, true);
		1212	}
		1213
		1214	/* Convert CHREC to TYPE. When the analyzer knows the context in
		1215	which the CHREC is built, it sets AT_STMT to the statement that
		1216	contains the definition of the analyzed variable, otherwise the
		1217	conversion is less accurate: the information is used for
		1218	determining a more accurate estimation of the number of iterations.
		1219	By default AT_STMT could be safely set to NULL_TREE.
		1220
		1221	USE_OVERFLOW_SEMANTICS is true if this function should assume that
		1222	the rules for overflow of the given language apply (e.g., that signed
		1223	arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
		1224	tests, but also to enforce that the result follows them. */
		1225
		1226	static tree
		1227	chrec_convert_1 (tree type, tree chrec, tree at_stmt,
		1228	bool use_overflow_semantics)
		1229	{
1114	tree ct, res;	1230	tree ct, res;
		1231	tree base, step;
		1232	struct loop *loop;
1115		1233
1116	if (automatically_generated_chrec_p (chrec))	1234	if (automatically_generated_chrec_p (chrec))
1117	return chrec;	1235	return chrec;
Lines 1120-1175 Link Here
1120	if (ct == type)	1238	if (ct == type)
1121	return chrec;	1239	return chrec;
1122		1240
1123	if (evolution_function_is_affine_p (chrec))	1241	if (!evolution_function_is_affine_p (chrec))
1124	{	1242	goto keep_cast;
1125	tree base, step;
1126	bool dummy;
1127	struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];
1128		1243
1129	base = instantiate_parameters (loop, CHREC_LEFT (chrec));	1244	loop = current_loops->parray[CHREC_VARIABLE (chrec)];
1130	step = instantiate_parameters (loop, CHREC_RIGHT (chrec));	1245	base = CHREC_LEFT (chrec);
		1246	step = CHREC_RIGHT (chrec);
1131		1247
1132	/* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x	1248	if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1133	when it is not possible to prove that the scev does not wrap.	1249	use_overflow_semantics))
1134	See PR22236, where a sequence 1, 2, ..., 255 has to be	1250	return build_polynomial_chrec (loop->num, base, step);
1135	converted to signed char, but this would wrap:
1136	1, 2, ..., 127, -128, ... The result should not be
1137	{(schar)1, +, (schar)1}_x, but instead, we should keep the
1138	conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
1139	if (scev_probably_wraps_p (type, base, step, at_stmt, loop,
1140	&dummy, &dummy))
1141	goto failed_to_convert;
1142		1251
1143	step = convert_step (loop, type, base, step, at_stmt);	1252	/* If we cannot propagate the cast inside the chrec, just keep the cast. */
1144	if (!step)	1253	keep_cast:
1145	{
1146	failed_to_convert:;
1147	if (dump_file && (dump_flags & TDF_DETAILS))
1148	{
1149	fprintf (dump_file, "(failed conversion:");
1150	fprintf (dump_file, "\n type: ");
1151	print_generic_expr (dump_file, type, 0);
1152	fprintf (dump_file, "\n base: ");
1153	print_generic_expr (dump_file, base, 0);
1154	fprintf (dump_file, "\n step: ");
1155	print_generic_expr (dump_file, step, 0);
1156	fprintf (dump_file, "\n estimated_nb_iterations: ");
1157	print_generic_expr (dump_file, loop->estimated_nb_iterations, 0);
1158	fprintf (dump_file, "\n)\n");
1159	}
1160
1161	return fold_convert (type, chrec);
1162	}
1163
1164	return build_polynomial_chrec (CHREC_VARIABLE (chrec),
1165	chrec_convert (type, CHREC_LEFT (chrec),
1166	at_stmt),
1167	step);
1168	}
1169
1170	if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1171	return chrec_dont_know;
1172
1173	res = fold_convert (type, chrec);	1254	res = fold_convert (type, chrec);
1174		1255
1175	/* Don't propagate overflows. */	1256	/* Don't propagate overflows. */
Lines 1232-1234 Link Here
1232		1313
1233	return TREE_TYPE (chrec);	1314	return TREE_TYPE (chrec);
1234	}	1315	}
		1316
		1317	/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
		1318	EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
		1319	which of these cases happens. */
		1320
		1321	enum ev_direction
		1322	scev_direction (tree chrec)
		1323	{
		1324	tree step;
		1325
		1326	if (!evolution_function_is_affine_p (chrec))
		1327	return EV_DIR_UNKNOWN;
		1328
		1329	step = CHREC_RIGHT (chrec);
		1330	if (TREE_CODE (step) != INTEGER_CST)
		1331	return EV_DIR_UNKNOWN;
		1332
		1333	if (tree_int_cst_sign_bit (step))
		1334	return EV_DIR_DECREASES;
		1335	else
		1336	return EV_DIR_GROWS;
		1337	}

Lines 1-5 Link Here

(-)gcc/ChangeLog (+25 lines)
1	2006-07-24 Richard Guenther <rguenther@suse.de>	1	2006-07-24 Richard Guenther <rguenther@suse.de>
2		2
		3	PR tree-optimization/27795
		4	PR tree-optimization/27639
		5	PR tree-optimization/26719
		6	Backport from mainline
		7	2006-05-24 Zdenek Dvorak <dvorakz@suse.cz>
		8
		9	* tree-vrp.c (adjust_range_with_scev): Use scev_direction and adjust
		10	call to scev_probably_wraps_p.
		11	* tree-ssa-loop-niter.c (compare_trees, convert_step_widening,
		12	used_in_pointer_arithmetic_p, convert_step): Removed.
		13	(nowrap_type_p): New function.
		14	(scev_probably_wraps_p): Rewritten.
		15	* tree-scalar-evolution.c (instantiate_parameters_1): Do not call
		16	chrec_convert if chrec_convert_aggressive might have been used.
		17	* tree-chrec.c (convert_affine_scev, chrec_convert_1,
		18	scev_direction): New functions.
		19	(chrec_convert): Changed to a wrapper over chrec_convert_1.
		20	* tree-ssa-loop-ivopts.c (idx_find_step): Use convert_affine_scev
		21	instead of convert_step.
		22	* tree-flow.h (scev_probably_wraps_p): Declaration changed.
		23	(convert_step): Declaration removed.
		24	(convert_affine_scev, nowrap_type_p, scev_direction): Declare.
		25
		26	2006-07-24 Richard Guenther <rguenther@suse.de>
		27
3	PR tree-optimization/28029	28	PR tree-optimization/28029
4	Backport	29	Backport
5	2006-02-15 Daniel Berlin <dberlin@dberlin.org>	30	2006-02-15 Daniel Berlin <dberlin@dberlin.org>

Line 0 Link Here

(-)gcc/testsuite/gcc.dg/pr27639.c (+12 lines)
	1	/* { dg-do compile } */
	2	/* { dg-options "-O2 -std=c99" } */
	3
	4	char heap[50000];
	5
	6	int
	7	main ()
	8	{
	9	for (unsigned ix = sizeof (heap); ix--;)
	10	heap[ix] = ix;
	11	return 0;
	12	}

Line 0 Link Here

(-)gcc/testsuite/gcc.dg/tree-ssa/scev-cast.c (+26 lines)
	1	/* A test for various conversions of chrecs. */
	2
	3	/* { dg-do compile { target i?86-- x86_64-- } } */
	4	/* { dg-options "-O2 -fdump-tree-optimized" } */
	5
	6	void blas (char xxx);
	7	void blau (unsigned char xxx);
	8
	9	void tst(void)
	10	{
	11	unsigned i;
	12
	13	for (i = 0; i < 128; i++) /* This cast to char has to be preserved. */
	14	blas ((char) i);
	15	for (i = 0; i < 127; i++) /* And this one does not. */
	16	blas ((char) i);
	17	for (i = 0; i < 255; i++) /* This cast is not necessary. */
	18	blau ((unsigned char) i);
	19	for (i = 0; i < 256; i++)
	20	blau ((unsigned char) i); /* This one is necessary. */
	21	}
	22
	23	/* { dg-final { scan-tree-dump-times "\\(int\\) \\(unsigned char\\)" 1 "optimized" } } */
	24	/* { dg-final { scan-tree-dump-times "\\(int\\) \\(char\\)" 1 "optimized" } } */
	25
	26	/* { dg-final { cleanup-tree-dump "optimized" } } */

Lines 1-5 Link Here

(-)gcc/testsuite/ChangeLog (+12 lines)
1	2006-07-24 Richard Guenther <rguenther@suse.de>	1	2006-07-24 Richard Guenther <rguenther@suse.de>
2		2
		3	PR tree-optimization/27795
		4	PR tree-optimization/27639
		5	PR tree-optimization/26719
		6	Backport from mainline
		7	2006-05-24 Zdenek Dvorak <dvorakz@suse.cz>
		8
		9	* gcc.dg/pr27639.c: New test.
		10	* gcc.dg/pr26719.c: New test.
		11	* gcc.dg/tree-ssa/scev-cast.c: New test.
		12
		13	2006-07-24 Richard Guenther <rguenther@suse.de>
		14
3	PR tree-optimization/28029	15	PR tree-optimization/28029
4	* gcc.dg/vect/pr28029.c: New testcase.	16	* gcc.dg/vect/pr28029.c: New testcase.
5		17