tree-ssa-loop-ivcanon.c: New file.

	* tree-ssa-loop-ivcanon.c: New file.
	* tree-ssa-loop-manip.c (create_iv): New function.
	* Makefile.in (tree-ssa-loop-ivcanon.o): Add.
	(tree-ssa-loop.o, tree-ssa-loop-manip.o): Add SCEV_H dependency.
	* cfgloop.c (mark_single_exit_loops): New function.
	(verify_loop_structure): Verify single-exit loops.
	* cfgloop.h (struct loop): Add single_exit field.
	(LOOPS_HAVE_MARKED_SINGLE_EXITS): New constant.
	(mark_single_exit_loops): Declare.
	(tree_num_loop_insns): Declare.
	* cfgloopmanip.c (update_single_exits_after_duplication): New function.
	(duplicate_loop_to_header_edge): Use it.
	* common.opt (fivcanon): New flag.
	* timevar.def (TV_TREE_LOOP_IVCANON, TV_COMPLETE_UNROLL): New timevars.
	* tree-cfg.c (tree_find_edge_insert_loc): Return newly created block.
	(bsi_commit_edge_inserts_1): Pass null to tree_find_edge_insert_loc.
	(bsi_insert_on_edge_immediate): New function.
	* tree-flow.h (bsi_insert_on_edge_immediate,
	canonicalize_induction_variables, tree_unroll_loops_completely,
	create_iv): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_iv_canon and pass_complete_unroll.
	* tree-pass.h (pass_iv_canon, pass_complete_unroll): Declare.
	* tree-scalar-evolution.c (get_loop_exit_condition,
	get_exit_conditions_rec, number_of_iterations_in_loop,
	scev_initialize): Use single_exit information.
	* tree-ssa-loop-niter.c (number_of_iterations_cond): Record
	missing assumptions.
	(loop_niter_by_eval):  Return number of iterations as unsigned
	int.
	* tree-ssa-loop.c (tree_ssa_loop_init): Mark single exit loops.
	(tree_ssa_loop_ivcanon, gate_tree_ssa_loop_ivcanon, pass_iv_canon,
	tree_complete_unroll, gate_tree_complete_unroll, pass_complete_unroll):
	New passes.
	(tree_ssa_loop_done): Call free_numbers_of_iterations_estimates.
	* tree-ssanames.c (make_ssa_name): Allow creating ssa name before
	the defining statement is ready.
	* tree-vectorizer.c (vect_create_iv_simple): Removed.
	(vect_create_index_for_array_ref, vect_transform_loop_bound):
	Use create_iv.
	(vect_transform_loop_bound): Use single_exit information.
	(vect_analyze_loop_form): Cleanup bogus tests.
	(vectorize_loops): Do not call flow_loop_scan.
	* tree.h (may_negate_without_overflow_p): Declare.
	* fold-const.c (may_negate_without_overflow_p): Split out from ...
	(negate_expr_p): ... this function.
	(tree_expr_nonzero_p): Handle overflowed constants correctly.
	* doc/invoke.texi (-fivcanon): Document.
	* doc/passes.texi: Document canonical induction variable creation.

	* gcc.dg/tree-ssa/loop-1.c: New test.

From-SVN: r86516

1 files changed, 37 insertions, 16 deletions

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 25fa071..ed6ae0f 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -865,14 +865,44 @@ negate_mathfn_p (enum built_in_function code)
   return false;
 }
 
+/* Check whether we may negate an integer constant T without causing
+   overflow.  */
+
+bool
+may_negate_without_overflow_p (tree t)
+{
+  unsigned HOST_WIDE_INT val;
+  unsigned int prec;
+  tree type;
+
+  if (TREE_CODE (t) != INTEGER_CST)
+    abort ();
+
+  type = TREE_TYPE (t);
+  if (TYPE_UNSIGNED (type))
+    return false;
+
+  prec = TYPE_PRECISION (type);
+  if (prec > HOST_BITS_PER_WIDE_INT)
+    {
+      if (TREE_INT_CST_LOW (t) != 0)
+	return true;
+      prec -= HOST_BITS_PER_WIDE_INT;
+      val = TREE_INT_CST_HIGH (t);
+    }
+  else
+    val = TREE_INT_CST_LOW (t);
+  if (prec < HOST_BITS_PER_WIDE_INT)
+    val &= ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
+  return val != ((unsigned HOST_WIDE_INT) 1 << (prec - 1));
+}
+
 /* Determine whether an expression T can be cheaply negated using
    the function negate_expr.  */
 
 static bool
 negate_expr_p (tree t)
 {
-  unsigned HOST_WIDE_INT val;
-  unsigned int prec;
   tree type;
 
   if (t == 0)
@@ -888,19 +918,7 @@ negate_expr_p (tree t)
 	return true;
 
       /* Check that -CST will not overflow type.  */
-      prec = TYPE_PRECISION (type);
-      if (prec > HOST_BITS_PER_WIDE_INT)
-	{
-	  if (TREE_INT_CST_LOW (t) != 0)
-	    return true;
-	  prec -= HOST_BITS_PER_WIDE_INT;
-	  val = TREE_INT_CST_HIGH (t);
-	}
-      else
-	val = TREE_INT_CST_LOW (t);
-      if (prec < HOST_BITS_PER_WIDE_INT)
-	val &= ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
-      return val != ((unsigned HOST_WIDE_INT) 1 << (prec - 1));
+      return may_negate_without_overflow_p (t);
 
     case REAL_CST:
     case NEGATE_EXPR:
@@ -9615,7 +9633,10 @@ tree_expr_nonzero_p (tree t)
 	return tree_expr_nonzero_p (TREE_OPERAND (t, 0));
 
     case INTEGER_CST:
-      return !integer_zerop (t);
+      /* We used to test for !integer_zerop here.  This does not work correctly
+	 if TREE_CONSTANT_OVERFLOW (t).  */
+      return (TREE_INT_CST_LOW (t) != 0
+	      || TREE_INT_CST_HIGH (t) != 0);
 
     case PLUS_EXPR:
       if (!TYPE_UNSIGNED (type) && !flag_wrapv)