* cfgloop.h (update_single_exits_after_duplication): Declare.

	(loopify, split_loop_bb): Declaration changed.
	* cfgloopmanip.c (split_loop_bb): Take void * as an argument instead
	of rtx.
	(loopify): Added redirect_all_edges argument.
	(update_single_exits_after_duplication): Export.
	* loop-unswitch.c (unswitch_loop): Changed due to loopify change.
	* tree-flow.h (tree_duplicate_loop_to_header_edge,
	tree_ssa_loop_version): Declare.
	* tree-ssa-loop-manip.c (copy_phi_node_args, rename_variables,
	set_phi_def_stmts, tree_duplicate_loop_to_header_edge,
	lv_adjust_loop_header_phi, lv_adjust_loop_entry_edge,
	lv_update_pending_stmts, tree_ssa_loop_version): New functions.

	* tree-ssa-loop-unswitch.c: New file.
	* Makefile.in (tree-ssa-loop-unswitch.o): Add.
	* timevar.def (TV_TREE_LOOP_UNSWITCH): New timevar.
	* tree-flow.h (tree_ssa_unswitch_loops): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add pass_unswitch.
	* tree-pass.h (pass_unswitch): Declare.
	* tree-ssa-loop.c (tree_ssa_loop_unswitch,
	gate_tree_ssa_loop_unswitch, pass_unswitch): New pass.
	* doc/passes.texi: Documen tree level loop unswitching.

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


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@87943 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 340 insertions, 0 deletions

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index e6ff8a80559..a06b3520753 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -506,3 +506,343 @@ standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
       *insert_after = false;
     }
 }
+
+/* Copies phi node arguments for duplicated blocks.  The index of the first
+   duplicated block is FIRST_NEW_BLOCK.  */
+
+static void
+copy_phi_node_args (unsigned first_new_block)
+{
+  unsigned i;
+
+  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+    BASIC_BLOCK (i)->rbi->duplicated = 1;
+
+  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+    add_phi_args_after_copy_bb (BASIC_BLOCK (i));
+
+  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+    BASIC_BLOCK (i)->rbi->duplicated = 0;
+}
+
+/* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
+   FIRST_NEW_BLOCK is the first block in the copied area.   DEFINITIONS is
+   a bitmap of all ssa names defined inside the loop.  */
+
+static void
+rename_variables (unsigned first_new_block, bitmap definitions)
+{
+  unsigned i, copy_number = 0;
+  basic_block bb;
+  htab_t ssa_name_map = NULL;
+
+  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+    {
+      bb = BASIC_BLOCK (i);
+
+      /* We assume that first come all blocks from the first copy, then all
+	 blocks from the second copy, etc.  */
+      if (copy_number != (unsigned) bb->rbi->copy_number)
+	{
+	  allocate_ssa_names (definitions, &ssa_name_map);
+	  copy_number = bb->rbi->copy_number;
+	}
+
+      rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
+    }
+
+  htab_delete (ssa_name_map);
+}
+
+/* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB.  */
+
+static void
+set_phi_def_stmts (basic_block bb)
+{
+  tree phi;
+
+  for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+    SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
+}
+
+/* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
+   ssa.  In order to achieve this, only loops whose exits all lead to the same
+   location are handled.
+   
+   FIXME: we create some degenerate phi nodes that could be avoided by copy
+   propagating them instead.  Unfortunately this is not completely
+   straightforward due to problems with constant folding.  */
+
+bool
+tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
+				    struct loops *loops,
+				    unsigned int ndupl, sbitmap wont_exit,
+				    edge orig, edge *to_remove,
+				    unsigned int *n_to_remove, int flags)
+{
+  unsigned first_new_block;
+  basic_block bb;
+  unsigned i;
+  tree phi, arg, map, def;
+  bitmap definitions;
+
+  if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
+    return false;
+  if (!(loops->state & LOOPS_HAVE_PREHEADERS))
+    return false;
+
+#ifdef ENABLE_CHECKING
+  verify_loop_closed_ssa ();
+#endif
+
+  gcc_assert (!any_marked_for_rewrite_p ());
+
+  first_new_block = last_basic_block;
+  if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
+				      orig, to_remove, n_to_remove, flags))
+    return false;
+
+  /* Readd the removed phi args for e.  */
+  map = PENDING_STMT (e);
+  PENDING_STMT (e) = NULL;
+
+  for (phi = phi_nodes (e->dest), arg = map;
+       phi;
+       phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
+    {
+      def = TREE_VALUE (arg);
+      add_phi_arg (&phi, def, e);
+    }
+  gcc_assert (arg == NULL);
+
+  /* Copy the phi node arguments.  */
+  copy_phi_node_args (first_new_block);
+
+  /* Rename the variables.  */
+  definitions = marked_ssa_names ();
+  rename_variables (first_new_block, definitions);
+  unmark_all_for_rewrite ();
+  BITMAP_XFREE (definitions);
+
+  /* For some time we have the identical ssa names as results in multiple phi
+     nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
+     to the new copy.  This means that we cannot easily ensure that the ssa
+     names defined in those phis are pointing to the right one -- so just
+     recompute SSA_NAME_DEF_STMT for them.  */ 
+
+  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+    {
+      bb = BASIC_BLOCK (i);
+      set_phi_def_stmts (bb);
+      if (bb->rbi->copy_number == 1)
+  	set_phi_def_stmts (bb->rbi->original);
+    }
+
+  scev_reset ();
+#ifdef ENABLE_CHECKING
+  verify_loop_closed_ssa ();
+#endif
+
+  return true;
+}
+
+/*---------------------------------------------------------------------------
+  Loop versioning
+  ---------------------------------------------------------------------------*/
+ 
+/* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
+   of 'first'. Both of them are dominated by 'new_head' basic block. When
+   'new_head' was created by 'second's incoming edge it received phi arguments
+   on the edge by split_edge(). Later, additional edge 'e' was created to
+   connect 'new_head' and 'first'. Now this routine adds phi args on this 
+   additional edge 'e' that new_head to second edge received as part of edge 
+   splitting.
+*/
+
+static void
+lv_adjust_loop_header_phi (basic_block first, basic_block second,
+			   basic_block new_head, edge e)
+{
+  tree phi1, phi2;
+
+  /* Browse all 'second' basic block phi nodes and add phi args to
+     edge 'e' for 'first' head. PHI args are always in correct order.  */
+
+  for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); 
+       phi2 && phi1; 
+       phi2 = TREE_CHAIN (phi2),  phi1 = TREE_CHAIN (phi1))
+    {
+      int i;
+      for (i = 0; i < PHI_NUM_ARGS (phi2); i++)
+	{
+	  if (PHI_ARG_EDGE (phi2, i)->src == new_head)
+	    {
+	      tree def = PHI_ARG_DEF (phi2, i);
+	      add_phi_arg (&phi1, def, e);
+	    }
+	}
+    }
+}
+
+/* Adjust entry edge for lv.
+   
+  e is a incoming edge. 
+
+  --- edge e ---- > [second_head]
+
+  Split it and insert new conditional expression and adjust edges.
+   
+   --- edge e ---> [cond expr] ---> [first_head]
+                        |
+                        +---------> [second_head]
+
+*/
+   
+static basic_block
+lv_adjust_loop_entry_edge (basic_block first_head,
+			   basic_block second_head,
+			   edge e,
+			   tree cond_expr)
+{ 
+  block_stmt_iterator bsi;
+  basic_block new_head = NULL;
+  tree goto1 = NULL_TREE;
+  tree goto2 = NULL_TREE;
+  tree new_cond_expr = NULL_TREE;
+  edge e0, e1;
+
+  gcc_assert (e->dest == second_head);
+
+  /* Split edge 'e'. This will create a new basic block, where we can
+     insert conditional expr.  */
+  new_head = split_edge (e);
+
+  /* Build new conditional expr */
+  goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
+  goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
+  new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
+
+  /* Add new cond. in new head.  */ 
+  bsi = bsi_start (new_head); 
+  bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
+
+  /* Adjust edges appropriately to connect new head with first head
+     as well as second head.  */
+  e0 = new_head->succ;
+  e0->flags &= ~EDGE_FALLTHRU;
+  e0->flags |= EDGE_FALSE_VALUE;
+  e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
+  set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
+  set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
+
+  /* Adjust loop header phi nodes.  */
+  lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
+
+  return new_head;
+}
+
+/* Add phi args using PENDINT_STMT list.  */
+
+static void
+lv_update_pending_stmts (edge e)
+{
+  basic_block dest;
+  tree phi, arg, def;
+
+  if (!PENDING_STMT (e))
+    return;
+
+  dest = e->dest;
+
+  for (phi = phi_nodes (dest), arg = PENDING_STMT (e);
+       phi;
+       phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
+    {
+      def = TREE_VALUE (arg);
+      add_phi_arg (&phi, def, e);
+    }
+
+  PENDING_STMT (e) = NULL;
+}
+
+
+/* Main entry point for Loop Versioning transformation.
+   
+This transformation given a condition and a loop, creates
+-if (condition) { loop_copy1 } else { loop_copy2 },
+where loop_copy1 is the loop transformed in one way, and loop_copy2
+is the loop transformed in another way (or unchanged). 'condition'
+may be a run time test for things that were not resolved by static
+analysis (overlapping ranges (anti-aliasing), alignment, etc.).  */
+
+struct loop *
+tree_ssa_loop_version (struct loops *loops, struct loop * loop, 
+		       tree cond_expr, basic_block *condition_bb)
+{
+  edge entry, latch_edge, exit;
+  basic_block first_head, second_head;
+  int irred_flag;
+  struct loop *nloop;
+
+  /* CHECKME: Loop versioning does not handle nested loop at this point.  */
+  if (loop->inner)
+    return NULL;
+
+  /* Record entry and latch edges for the loop */
+  entry = loop_preheader_edge (loop);
+
+  /* Note down head of loop as first_head.  */
+  first_head = entry->dest;
+
+  /* Duplicate loop.  */
+  irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
+  entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+  if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
+					   NULL, NULL, NULL, NULL, 0))
+    {
+      entry->flags |= irred_flag;
+      return NULL;
+    }
+
+  /* After duplication entry edge now points to new loop head block.
+     Note down new head as second_head.  */
+  second_head = entry->dest;
+
+  /* Split loop entry edge and insert new block with cond expr.  */
+  *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry, 
+					    cond_expr); 
+
+  latch_edge = loop->latch->rbi->copy->succ;
+  nloop = loopify (loops, 
+		   latch_edge,
+		   loop->header->rbi->copy->pred,
+		   *condition_bb,
+		   false /* Do not redirect all edges.  */);
+
+  exit = loop->single_exit;
+  if (exit)
+    nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
+
+  /* loopify redirected latch_edge. Update its PENDING_STMTS.  */ 
+  lv_update_pending_stmts (latch_edge);
+
+  /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */ 
+  lv_update_pending_stmts (FALLTHRU_EDGE (*condition_bb));
+
+  /* Adjust irreducible flag.  */
+  if (irred_flag)
+    {
+      (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
+      loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+      loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+      (*condition_bb)->pred->flags |= EDGE_IRREDUCIBLE_LOOP;
+    }
+
+  /* At this point condition_bb is loop predheader with two successors, 
+     first_head and second_head.   Make sure that loop predheader has only 
+     one successor. */
+  loop_split_edge_with (loop_preheader_edge (loop), NULL);
+  loop_split_edge_with (loop_preheader_edge (nloop), NULL);
+
+  return nloop;
+}