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, 120 insertions, 2 deletions

diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index 58d9dd0..b5553d2 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -370,6 +370,63 @@ flow_loop_nodes_find (basic_block header, struct loop *loop)
   return num_nodes;
 }
 
+/* For each loop in the lOOPS tree that has just a single exit
+   record the exit edge.  */
+
+void
+mark_single_exit_loops (struct loops *loops)
+{
+  basic_block bb;
+  edge e;
+  struct loop *loop;
+  unsigned i;
+
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+      if (loop)
+	loop->single_exit = NULL;
+    }
+
+  FOR_EACH_BB (bb)
+    {
+      if (bb->loop_father == loops->tree_root)
+	continue;
+      for (e = bb->succ; e; e = e->succ_next)
+	{
+	  if (e->dest == EXIT_BLOCK_PTR)
+	    continue;
+
+	  if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+	    continue;
+
+	  for (loop = bb->loop_father;
+	       loop != e->dest->loop_father;
+	       loop = loop->outer)
+	    {
+	      /* If we have already seen an exit, mark this by the edge that
+		 surely does not occur as any exit.  */
+	      if (loop->single_exit)
+		loop->single_exit = ENTRY_BLOCK_PTR->succ;
+	      else
+		loop->single_exit = e;
+	    }
+	}
+    }
+
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+      if (!loop)
+	continue;
+
+      if (loop->single_exit == ENTRY_BLOCK_PTR->succ)
+	loop->single_exit = NULL;
+    }
+
+  loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
+}
+
 /* Find the root node of the loop pre-header extended basic block and
    the edges along the trace from the root node to the loop header.  */
 
@@ -1197,8 +1254,6 @@ verify_loop_structure (struct loops *loops)
 	}
     }
 
-  free (sizes);
-
   /* Check get_loop_body.  */
   for (i = 1; i < loops->num; i++)
     {
@@ -1319,8 +1374,71 @@ verify_loop_structure (struct loops *loops)
       free (irreds);
     }
 
+  /* Check the single_exit.  */
+  if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+    {
+      memset (sizes, 0, sizeof (unsigned) * loops->num);
+      FOR_EACH_BB (bb)
+	{
+	  if (bb->loop_father == loops->tree_root)
+	    continue;
+	  for (e = bb->succ; e; e = e->succ_next)
+	    {
+	      if (e->dest == EXIT_BLOCK_PTR)
+		continue;
+
+	      if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+		continue;
+
+	      for (loop = bb->loop_father;
+		   loop != e->dest->loop_father;
+		   loop = loop->outer)
+		{
+		  sizes[loop->num]++;
+		  if (loop->single_exit
+		      && loop->single_exit != e)
+		    {
+		      error ("Wrong single exit %d->%d recorded for loop %d.",
+			     loop->single_exit->src->index,
+			     loop->single_exit->dest->index,
+			     loop->num);
+		      error ("Right exit is %d->%d.",
+			     e->src->index, e->dest->index);
+		      err = 1;
+		    }
+		}
+	    }
+	}
+
+      for (i = 1; i < loops->num; i++)
+	{
+	  loop = loops->parray[i];
+	  if (!loop)
+	    continue;
+
+	  if (sizes[i] == 1
+	      && !loop->single_exit)
+	    {
+	      error ("Single exit not recorded for loop %d.", loop->num);
+	      err = 1;
+	    }
+
+	  if (sizes[i] != 1
+	      && loop->single_exit)
+	    {
+	      error ("Loop %d should not have single exit (%d -> %d).",
+		     loop->num,
+		     loop->single_exit->src->index,
+		     loop->single_exit->dest->index);
+	      err = 1;
+	    }
+	}
+    }
+
   if (err)
     abort ();
+
+  free (sizes);
 }
 
 /* Returns latch edge of LOOP.  */