This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] Fix tree-optimization/22236 wrong code for casts and scev


Here is a patch that fixes PR22236.  The fix for the PR can be reduced
to the few lines in chrec_convert that check for non wrapping ivs.

The analyzer now has to extract more information for completing the
proofs of non wrapping ivs.  A big part of the patch teaches the
compiler how to extract loop bounds from signed non wrapping ivs, and
that ivs used for constructing pointers do not wrap.

Thanks to Daniel for the offline discussion.  Daniel also wanted to
point out that a part of my patch would not be needed if his patch
"Add ability to have ARRAY_REF on pointers" is reviewed and committed.
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html
Please review his patch ;-)

The following patch was bootstrapped and tested on x86_64-linux.
Okay for mainline?

Sebastian

	* tree-cfg.c (print_pred_bbs, print_succ_bbs): Correctly print
	successors and predecessors.
	* tree-chrec.c (chrec_fold_plus_1, chrec_fold_multiply,
	chrec_evaluate): Don't pass REAL_CSTs to fold.
	(chrec_convert): Before converting, check that sequences don't wrap.
	* tree-data-ref.c (compute_estimated_nb_iterations): Moved ...
	(analyze_array): Extern.
	(find_data_references_in_loop): Remove call to
	compute_estimated_nb_iterations.
	* tree-data-ref.h (analyze_array): Declared.
	* tree-flow-inline.h (single_ssa_tree_operand, single_ssa_use_operand,
	single_ssa_def_operand, zero_ssa_operands): Fix documentation.
	* tree-flow.h (scev_probably_wraps_p): Declare with an extra parameter.
	* tree-scalar-evolution.c (instantiate_parameters_1): Factor entry 
	condition.
	* tree-ssa-loop-ivcanon.c: Fix documentation.
	* tree-ssa-loop-ivopts.c (idx_find_step): Add a fixme note.
	* tree-ssa-loop-niter.c (compute_estimated_nb_iterations): ... here.
	(infer_loop_bounds_from_undefined): New.
	(estimate_numbers_of_iterations_loop): Use
	infer_loop_bounds_from_undefined.
	(used_in_pointer_arithmetic_p): New.
	(scev_probably_wraps_p): Pass an extra parameter.  Call
	used_in_pointer_arithmetic_p.  Check that AT_STMT is not null.
	(convert_step): Fix documentation.
	* tree-vrp.c (adjust_range_with_scev): Call instantiate_parameters.
	Use initial_condition_in_loop_num and evolution_part_in_loop_num
	instead of CHREC_LEFT and CHREC_RIGHT.  Adjust the call to
	scev_probably_wraps_p.

testsuite/gcc.dg/tree-ssa/pr22236.c: New testcase.
	

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.212
diff -d -u -p -r2.212 tree-cfg.c
--- tree-cfg.c	28 Jul 2005 07:41:22 -0000	2.212
+++ tree-cfg.c	1 Aug 2005 09:09:27 -0000
@@ -4478,7 +4478,7 @@ static void print_pred_bbs (FILE *, basi
 static void print_succ_bbs (FILE *, basic_block bb);
 
 
-/* Print the predecessors indexes of edge E on FILE.  */
+/* Print on FILE the indexes for the predecessors of basic_block BB.  */
 
 static void
 print_pred_bbs (FILE *file, basic_block bb)
@@ -4487,11 +4487,11 @@ print_pred_bbs (FILE *file, basic_block 
   edge_iterator ei;
 
   FOR_EACH_EDGE (e, ei, bb->preds)
-    fprintf (file, "bb_%d", e->src->index);
+    fprintf (file, "bb_%d ", e->src->index);
 }
 
 
-/* Print the successors indexes of edge E on FILE.  */
+/* Print on FILE the indexes for the successors of basic_block BB.  */
 
 static void
 print_succ_bbs (FILE *file, basic_block bb)
@@ -4500,7 +4500,7 @@ print_succ_bbs (FILE *file, basic_block 
   edge_iterator ei;
 
   FOR_EACH_EDGE (e, ei, bb->succs)
-    fprintf (file, "bb_%d", e->src->index);
+    fprintf (file, "bb_%d ", e->dest->index);
 }
 
 
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.22
diff -d -u -p -r2.22 tree-chrec.c
--- tree-chrec.c	13 Jul 2005 10:08:36 -0000	2.22
+++ tree-chrec.c	1 Aug 2005 09:09:27 -0000
@@ -291,7 +291,9 @@ chrec_fold_plus_1 (enum tree_code code, 
 	  {
 	    int size = 0;
 	    if ((tree_contains_chrecs (op0, &size)
-		 || tree_contains_chrecs (op1, &size))
+		 || tree_contains_chrecs (op1, &size)
+		 || TREE_CODE (op0) == REAL_CST
+		 || TREE_CODE (op1) == REAL_CST)
 		&& size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
 	      return build2 (code, type, op0, op1);
 	    else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
@@ -384,6 +386,9 @@ chrec_fold_multiply (tree type, 
 	    return op0;
 	  if (integer_zerop (op1))
 	    return build_int_cst_type (type, 0);
+	  if (TREE_CODE (op0) == REAL_CST
+	      || TREE_CODE (op1) == REAL_CST)
+	    return build2 (MULT_EXPR, type, op0, op1);
 	  return fold_build2 (MULT_EXPR, type, op0, op1);
 	}
     }
@@ -488,8 +493,7 @@ chrec_evaluate (unsigned var, tree chrec
       binomial_n_k = tree_fold_binomial (type, n, k);
       if (!binomial_n_k)
 	return chrec_dont_know;
-      arg1 = fold_build2 (MULT_EXPR, type,
-			  CHREC_LEFT (chrec), binomial_n_k);
+      arg1 = chrec_fold_multiply (type, CHREC_LEFT (chrec), binomial_n_k);
       return chrec_fold_plus (type, arg0, arg1);
     }
 
@@ -497,7 +501,7 @@ chrec_evaluate (unsigned var, tree chrec
   if (!binomial_n_k)
     return chrec_dont_know;
   
-  return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
+  return chrec_fold_multiply (type, chrec, binomial_n_k);
 }
 
 /* Evaluates "CHREC (X)" when the varying variable is VAR.  
@@ -1110,9 +1114,24 @@ chrec_convert (tree type, tree chrec, tr
 
   if (evolution_function_is_affine_p (chrec))
     {
-      tree step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)],
- 				type, CHREC_LEFT (chrec), CHREC_RIGHT (chrec),
- 				at_stmt);
+      tree step;
+      bool dummy;
+
+      /* 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, CHREC_LEFT (chrec), CHREC_RIGHT (chrec),
+				 at_stmt,
+				 current_loops->parray[CHREC_VARIABLE (chrec)],
+				 &dummy, &dummy))
+	return fold_convert (type, chrec);
+
+      step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)], type,
+			   CHREC_LEFT (chrec), CHREC_RIGHT (chrec), at_stmt);
       if (!step)
  	return fold_convert (type, chrec);
 
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.35
diff -d -u -p -r2.35 tree-data-ref.c
--- tree-data-ref.c	25 Jul 2005 12:04:49 -0000	2.35
+++ tree-data-ref.c	1 Aug 2005 09:09:27 -0000
@@ -731,23 +731,6 @@ dump_ddrs (FILE *file, varray_type ddrs)
 
 
 
-/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
-   approximation of the number of iterations for LOOP.  */
-
-static void
-compute_estimated_nb_iterations (struct loop *loop)
-{
-  struct nb_iter_bound *bound;
-  
-  for (bound = loop->bounds; bound; bound = bound->next)
-    if (TREE_CODE (bound->bound) == INTEGER_CST
-	/* Update only when there is no previous estimation.  */
-	&& (chrec_contains_undetermined (loop->estimated_nb_iterations)
-	    /* Or when the current estimation is smaller.  */
-	    || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
-      loop->estimated_nb_iterations = bound->bound;
-}
-
 /* Estimate the number of iterations from the size of the data and the
    access functions.  */
 
@@ -830,7 +813,7 @@ analyze_array_indexes (struct loop *loop
    set to true when REF is in the right hand side of an
    assignment.  */
 
-static struct data_reference *
+struct data_reference *
 analyze_array (tree stmt, tree ref, bool is_read)
 {
   struct data_reference *res;
@@ -3644,9 +3627,6 @@ find_data_references_in_loop (struct loo
 	  if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 	    loop->parallel_p = false;
 	}
-
-      if (chrec_contains_undetermined (loop->estimated_nb_iterations))
-	compute_estimated_nb_iterations (loop);
     }
 
   free (bbs);
Index: tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.h,v
retrieving revision 2.10
diff -d -u -p -r2.10 tree-data-ref.h
--- tree-data-ref.h	25 Jul 2005 12:04:49 -0000	2.10
+++ tree-data-ref.h	1 Aug 2005 09:09:27 -0000
@@ -264,6 +264,7 @@ extern void free_dependence_relation (st
 extern void free_dependence_relations (varray_type);
 extern void free_data_refs (varray_type);
 extern void compute_subscript_distance (struct data_dependence_relation *);
+extern struct data_reference *analyze_array (tree, tree, bool);
 
 
 
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.55
diff -d -u -p -r2.55 tree-flow-inline.h
--- tree-flow-inline.h	28 Jul 2005 16:29:52 -0000	2.55
+++ tree-flow-inline.h	1 Aug 2005 09:09:28 -0000
@@ -1191,7 +1191,7 @@ op_iter_init_must_and_may_def (ssa_op_it
 
 
 /* If there is a single operand in STMT matching FLAGS, return it.  Otherwise
-   return NULL.  PTR is the iterator to use.  */
+   return NULL.  */
 static inline tree
 single_ssa_tree_operand (tree stmt, int flags)
 {
@@ -1209,7 +1209,7 @@ single_ssa_tree_operand (tree stmt, int 
 
 
 /* If there is a single operand in STMT matching FLAGS, return it.  Otherwise
-   return NULL.  PTR is the iterator to use.  */
+   return NULL.  */
 static inline use_operand_p
 single_ssa_use_operand (tree stmt, int flags)
 {
@@ -1228,7 +1228,7 @@ single_ssa_use_operand (tree stmt, int f
 
 
 /* If there is a single operand in STMT matching FLAGS, return it.  Otherwise
-   return NULL.  PTR is the iterator to use.  */
+   return NULL.  */
 static inline def_operand_p
 single_ssa_def_operand (tree stmt, int flags)
 {
@@ -1246,7 +1246,7 @@ single_ssa_def_operand (tree stmt, int f
 
 
 /* If there is a single operand in STMT matching FLAGS, return it.  Otherwise
-   return NULL.  PTR is the iterator to use.  */
+   return NULL.  */
 static inline bool
 zero_ssa_operands (tree stmt, int flags)
 {
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.131
diff -d -u -p -r2.131 tree-flow.h
--- tree-flow.h	27 Jul 2005 13:26:53 -0000	2.131
+++ tree-flow.h	1 Aug 2005 09:09:28 -0000
@@ -728,7 +728,8 @@ tree find_loop_niter (struct loop *, edg
 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 scev_probably_wraps_p (tree, tree, tree, tree, struct loop *, bool *,
+			    bool *);
 tree convert_step (struct loop *, tree, tree, tree, tree);
 void free_numbers_of_iterations_estimates (struct loops *);
 void rewrite_into_loop_closed_ssa (bitmap, unsigned);
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.32
diff -d -u -p -r2.32 tree-scalar-evolution.c
--- tree-scalar-evolution.c	27 Jul 2005 13:26:54 -0000	2.32
+++ tree-scalar-evolution.c	1 Aug 2005 09:09:29 -0000
@@ -1937,11 +1937,8 @@ instantiate_parameters_1 (struct loop *l
   basic_block def_bb;
   struct loop *def_loop;
  
-  if (chrec == NULL_TREE
-      || automatically_generated_chrec_p (chrec))
-    return chrec;
- 
-  if (is_gimple_min_invariant (chrec))
+  if (automatically_generated_chrec_p (chrec)
+      || is_gimple_min_invariant (chrec))
     return chrec;
 
   switch (TREE_CODE (chrec))
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivcanon.c,v
retrieving revision 2.18
diff -d -u -p -r2.18 tree-ssa-loop-ivcanon.c
--- tree-ssa-loop-ivcanon.c	21 Jul 2005 07:24:10 -0000	2.18
+++ tree-ssa-loop-ivcanon.c	1 Aug 2005 09:09:30 -0000
@@ -252,7 +252,7 @@ try_unroll_loop_completely (struct loops
 }
 
 /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
-   tree.  CREATE_IV is true if we may create a new iv.  UL determines what
+   tree.  CREATE_IV is true if we may create a new iv.  UL determines 
    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
    to determine the number of iterations of a loop by direct evaluation. 
    Returns true if cfg is changed.  */
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.86
diff -d -u -p -r2.86 tree-ssa-loop-ivopts.c
--- tree-ssa-loop-ivopts.c	27 Jul 2005 13:26:55 -0000	2.86
+++ tree-ssa-loop-ivopts.c	1 Aug 2005 09:09:33 -0000
@@ -1443,6 +1443,8 @@ idx_find_step (tree base, tree *idx, voi
     /* 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);
 
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.34
diff -d -u -p -r2.34 tree-ssa-loop-niter.c
--- tree-ssa-loop-niter.c	27 Jul 2005 14:04:01 -0000	2.34
+++ tree-ssa-loop-niter.c	1 Aug 2005 09:09:33 -0000
@@ -1381,6 +1381,128 @@ record_estimate (struct loop *loop, tree
   loop->bounds = elt;
 }
 
+/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
+   approximation of the number of iterations for LOOP.  */
+
+static void
+compute_estimated_nb_iterations (struct loop *loop)
+{
+  struct nb_iter_bound *bound;
+  
+  for (bound = loop->bounds; bound; bound = bound->next)
+    if (TREE_CODE (bound->bound) == INTEGER_CST
+	/* Update only when there is no previous estimation.  */
+	&& (chrec_contains_undetermined (loop->estimated_nb_iterations)
+	    /* Or when the current estimation is smaller.  */
+	    || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
+      loop->estimated_nb_iterations = bound->bound;
+}
+
+/* The following analyzers are extracting informations on the bounds
+   of LOOP from the following undefined behaviors:
+
+   - data references should not access elements over the statically
+     allocated size,
+
+   - signed variables should not overflow when flag_wrapv is not set.
+*/
+
+static void
+infer_loop_bounds_from_undefined (struct loop *loop)
+{
+  unsigned i;
+  basic_block bb, *bbs;
+  block_stmt_iterator bsi;
+  
+  bbs = get_loop_body (loop);
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      bb = bbs[i];
+
+      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+        {
+	  tree stmt = bsi_stmt (bsi);
+
+	  switch (TREE_CODE (stmt))
+	    {
+	    case MODIFY_EXPR:
+	      {
+		tree op0 = TREE_OPERAND (stmt, 0);
+		tree op1 = TREE_OPERAND (stmt, 1);
+
+		/* For each array access, analyze its access function
+		   and record a bound on the loop iteration domain.  */
+		if (TREE_CODE (op1) == ARRAY_REF)
+		  analyze_array (stmt, op1, true);
+
+		if (TREE_CODE (op0) == ARRAY_REF)
+		  analyze_array (stmt, op0, false);
+
+		/* For each signed type variable in LOOP, analyze its
+		   scalar evolution and record a bound of the loop
+		   based on the type's ranges.  */
+		else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
+		  {
+		    tree init, step, diff, estimation;
+		    tree scev = instantiate_parameters 
+		      (loop, analyze_scalar_evolution (loop, op0));
+		    tree type = chrec_type (scev);
+		    tree utype;
+
+		    if (chrec_contains_undetermined (scev)
+			|| TYPE_UNSIGNED (type))
+		      break;
+
+		    init = initial_condition_in_loop_num (scev, loop->num);
+		    step = evolution_part_in_loop_num (scev, loop->num);
+
+		    if (init == NULL_TREE
+			|| step == NULL_TREE
+			|| TREE_CODE (init) != INTEGER_CST
+			|| TREE_CODE (step) != INTEGER_CST)
+		      break;
+
+		    utype = unsigned_type_for (type);
+		    if (tree_int_cst_lt (step, integer_zero_node))
+		      diff = fold (build2 (MINUS_EXPR, utype, init,
+					   TYPE_MIN_VALUE (type)));
+		    else
+		      diff = fold (build2 (MINUS_EXPR, utype,
+					   TYPE_MAX_VALUE (type), init));
+
+		    estimation = fold (build2 (CEIL_DIV_EXPR, utype, diff,
+					       step));
+		    record_estimate (loop, estimation, boolean_true_node, stmt);
+		  }
+
+		break;
+	      }
+
+	    case CALL_EXPR:
+	      {
+		tree args;
+
+		for (args = TREE_OPERAND (stmt, 1); args;
+		     args = TREE_CHAIN (args))
+		  if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF)
+		    analyze_array (stmt, TREE_VALUE (args), true);
+
+		break;
+	      }
+
+	    default:
+	      break;
+	    }
+	}
+
+      if (chrec_contains_undetermined (loop->estimated_nb_iterations))
+	compute_estimated_nb_iterations (loop);
+    }
+
+  free (bbs);
+}
+
 /* Records estimates on numbers of iterations of LOOP.  */
 
 static void
@@ -1419,14 +1541,8 @@ estimate_numbers_of_iterations_loop (str
     }
   free (exits);
   
-  /* Analyzes the bounds of arrays accessed in the loop.  */
   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
-    {
-      varray_type datarefs;
-      VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
-      find_data_references_in_loop (loop, &datarefs);
-      free_data_refs (datarefs);
-    }
+    infer_loop_bounds_from_undefined (loop);
 }
 
 /* Records estimates on numbers of iterations of LOOPS.  */
@@ -1643,6 +1759,43 @@ convert_step_widening (struct loop *loop
   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;
+}
+
 /* Return false only when the induction variable BASE + STEP * I is
    known to not overflow: i.e. when the number of iterations is small
    enough with respect to the step and initial condition in order to
@@ -1650,19 +1803,60 @@ convert_step_widening (struct loop *loop
    iv is known to overflow or when the property is not computable.
 
    Initialize INIT_IS_MAX to true when the evolution goes from
-   INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case, not
-   defined when the function returns true.  */
+   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, 
 		       tree at_stmt, struct loop *loop,
-		       bool *init_is_max)
+		       bool *init_is_max, bool *unknown_max)
 {
   struct nb_iter_bound *bound;
   tree delta, step_abs;
   tree unsigned_type, valid_niter;
-  tree base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
+  tree base_plus_step;
 
+  /* FIXME: The following code will not be used anymore once
+     http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
+     committed.
+
+     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:
+	 
+       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;
+	}
+    }
+
+  if (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);
   switch (compare_trees (base_plus_step, base))
     {
     case -1:
@@ -1689,6 +1883,7 @@ scev_probably_wraps_p (tree type, tree b
 	 don't know as in the default case.  */
 
     default:
+      *unknown_max = true;
       return true;
     }
 
@@ -1707,7 +1902,7 @@ scev_probably_wraps_p (tree type, tree b
      i_2 to wrap around, but not i.0_6, because it is of a signed
      type.  This causes VRP to erroneously fold the predicate above
      because it thinks that i.0_6 cannot be negative.  */
-  if (TREE_CODE (at_stmt) == MODIFY_EXPR)
+  if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
     {
       tree rhs = TREE_OPERAND (at_stmt, 1);
       tree outer_t = TREE_TYPE (rhs);
@@ -1723,7 +1918,10 @@ scev_probably_wraps_p (tree type, tree b
 	  if (TYPE_UNSIGNED (inner_t)
 	      && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
 		  || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
-	    return true;
+	    {
+	      *unknown_max = true;
+	      return true;
+	    }
 	}
     }
 
@@ -1744,11 +1942,13 @@ scev_probably_wraps_p (tree type, tree b
 
   /* 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.  */
+   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,
Index: tree-vect-analyze.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vect-analyze.c,v
retrieving revision 2.34
diff -d -u -p -r2.34 tree-vect-analyze.c
--- tree-vect-analyze.c	27 Jul 2005 15:19:16 -0000	2.34
+++ tree-vect-analyze.c	1 Aug 2005 09:09:34 -0000
@@ -1173,7 +1173,7 @@ vect_analyze_data_refs (loop_vec_info lo
       if (!dr || !DR_REF (dr))
         {
           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
-              fprintf (vect_dump, "not vectorized: unhandled data-ref ");
+	    fprintf (vect_dump, "not vectorized: unhandled data-ref ");
           return false;
         }
  
Index: tree-vrp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vrp.c,v
retrieving revision 2.47
diff -d -u -p -r2.47 tree-vrp.c
--- tree-vrp.c	29 Jul 2005 15:21:54 -0000	2.47
+++ tree-vrp.c	1 Aug 2005 09:09:35 -0000
@@ -1520,29 +1520,31 @@ adjust_range_with_scev (value_range_t *v
 			tree var)
 {
   tree init, step, chrec;
-  bool init_is_max;
+  bool init_is_max, unknown_max;
 
   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
      better opportunities than a regular range, but I'm not sure.  */
   if (vr->type == VR_ANTI_RANGE)
     return;
 
-  chrec = analyze_scalar_evolution (loop, var);
+  chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
     return;
 
-  init = CHREC_LEFT (chrec);
-  step = CHREC_RIGHT (chrec);
+  init = initial_condition_in_loop_num (chrec, loop->num);
+  step = evolution_part_in_loop_num (chrec, loop->num);
 
   /* If STEP is symbolic, we can't know whether INIT will be the
      minimum or maximum value in the range.  */
-  if (!is_gimple_min_invariant (step))
+  if (step == NULL_TREE
+      || !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))
+			     &init_is_max, &unknown_max)
+      || unknown_max)
     return;
 
   if (!POINTER_TYPE_P (TREE_TYPE (init))
Index: testsuite/gcc.dg/tree-ssa/pr22236.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/pr22236.c
diff -N testsuite/gcc.dg/tree-ssa/pr22236.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/pr22236.c	1 Aug 2005 09:09:41 -0000
@@ -0,0 +1,33 @@
+/* { dg-do run } */
+/* { dg-options "-O1 -fno-tree-vrp -fwrapv" } */
+
+/* PR tree-optimization/22236
+
+    Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x when
+    it is not possible to prove that the scev does not wrap.  
+
+    In this PR, 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 a linear scev {(schar)1, +, (schar)1}_x.
+    The conversion should be kept: (schar) {(uchar)1, +, (uchar)1}_x.
+ */
+
+void abort(void);
+
+static inline void
+foo (signed char a)
+{
+  int b = a - 0x7F;
+  if (b > 1)
+    abort();
+}
+
+int main()
+{
+  unsigned char b;
+  for(b = 0; b < 0xFF; b++)
+    foo (b);
+
+  return 0;
+}
+


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]