re PR tree-optimization/55964 (Segmentation fault with -O -ftree-loop-distribution -funswitch-loops)

2013-01-16  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/55964
	* tree-flow.h (rename_variables_in_loop): Remove.
	(rename_variables_in_bb): Likewise.
	* tree-loop-distribution.c (update_phis_for_loop_copy): Remove.
	(copy_loop_before): Adjust and delete update-ssa status.
	* tree-vect-loop-manip.c (rename_variables_in_bb): Make static.
	(rename_variables_in_bb): Likewise.  Properly walk over
	predecessors.
	(rename_variables_in_loop): Remove.
	(slpeel_update_phis_for_duplicate_loop): Likewise.
	(slpeel_tree_duplicate_loop_to_edge_cfg): Handle nested loops,
	use available cfg machinery instead of duplicating it.
	Update PHI nodes and perform poor-mans SSA update here.
	(slpeel_tree_peel_loop_to_edge): Adjust.

	* gcc.dg/torture/pr55964.c: New testcase.

From-SVN: r195239

1 files changed, 53 insertions, 188 deletions

diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c
index 6b6e130..8e589de 100644
--- a/gcc/tree-vect-loop-manip.c
+++ b/gcc/tree-vect-loop-manip.c
@@ -67,7 +67,7 @@ rename_use_op (use_operand_p op_p)
 
 /* Renames the variables in basic block BB.  */
 
-void
+static void
 rename_variables_in_bb (basic_block bb)
 {
   gimple_stmt_iterator gsi;
@@ -85,32 +85,16 @@ rename_variables_in_bb (basic_block bb)
 	rename_use_op (use_p);
     }
 
-  FOR_EACH_EDGE (e, ei, bb->succs)
+  FOR_EACH_EDGE (e, ei, bb->preds)
     {
-      if (!flow_bb_inside_loop_p (loop, e->dest))
+      if (!flow_bb_inside_loop_p (loop, e->src))
 	continue;
-      for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
+      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e));
     }
 }
 
 
-/* Renames variables in new generated LOOP.  */
-
-void
-rename_variables_in_loop (struct loop *loop)
-{
-  unsigned i;
-  basic_block *bbs;
-
-  bbs = get_loop_body (loop);
-
-  for (i = 0; i < loop->num_nodes; i++)
-    rename_variables_in_bb (bbs[i]);
-
-  free (bbs);
-}
-
 typedef struct
 {
   tree from, to;
@@ -234,101 +218,6 @@ adjust_phi_and_debug_stmts (gimple update_phi, edge e, tree new_def)
 }
 
 
-/* Update the PHI nodes of NEW_LOOP.
-
-   NEW_LOOP is a duplicate of ORIG_LOOP.
-   AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
-   AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
-   executes before it.  */
-
-static void
-slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
-				       struct loop *new_loop, bool after)
-{
-  tree new_ssa_name;
-  gimple phi_new, phi_orig;
-  tree def;
-  edge orig_loop_latch = loop_latch_edge (orig_loop);
-  edge orig_entry_e = loop_preheader_edge (orig_loop);
-  edge new_loop_exit_e = single_exit (new_loop);
-  edge new_loop_entry_e = loop_preheader_edge (new_loop);
-  edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
-  gimple_stmt_iterator gsi_new, gsi_orig;
-
-  /*
-     step 1. For each loop-header-phi:
-             Add the first phi argument for the phi in NEW_LOOP
-            (the one associated with the entry of NEW_LOOP)
-
-     step 2. For each loop-header-phi:
-             Add the second phi argument for the phi in NEW_LOOP
-            (the one associated with the latch of NEW_LOOP)
-
-     step 3. Update the phis in the successor block of NEW_LOOP.
-
-        case 1: NEW_LOOP was placed before ORIG_LOOP:
-                The successor block of NEW_LOOP is the header of ORIG_LOOP.
-                Updating the phis in the successor block can therefore be done
-                along with the scanning of the loop header phis, because the
-                header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
-                phi nodes, organized in the same order.
-
-        case 2: NEW_LOOP was placed after ORIG_LOOP:
-                The successor block of NEW_LOOP is the original exit block of
-                ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
-                We postpone updating these phis to a later stage (when
-                loop guards are added).
-   */
-
-
-  /* Scan the phis in the headers of the old and new loops
-     (they are organized in exactly the same order).  */
-
-  for (gsi_new = gsi_start_phis (new_loop->header),
-       gsi_orig = gsi_start_phis (orig_loop->header);
-       !gsi_end_p (gsi_new) && !gsi_end_p (gsi_orig);
-       gsi_next (&gsi_new), gsi_next (&gsi_orig))
-    {
-      source_location locus;
-      phi_new = gsi_stmt (gsi_new);
-      phi_orig = gsi_stmt (gsi_orig);
-
-      /* step 1.  */
-      def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
-      locus = gimple_phi_arg_location_from_edge (phi_orig, entry_arg_e);
-      add_phi_arg (phi_new, def, new_loop_entry_e, locus);
-
-      /* step 2.  */
-      def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
-      locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
-      if (TREE_CODE (def) != SSA_NAME)
-        continue;
-
-      new_ssa_name = get_current_def (def);
-      if (!new_ssa_name)
-	{
-	  /* This only happens if there are no definitions
-	     inside the loop. use the phi_result in this case.  */
-	  new_ssa_name = PHI_RESULT (phi_new);
-	}
-
-      /* An ordinary ssa name defined in the loop.  */
-      add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
-
-      /* Drop any debug references outside the loop, if they would
-	 become ill-formed SSA.  */
-      adjust_debug_stmts (def, NULL, single_exit (orig_loop)->dest);
-
-      /* step 3 (case 1).  */
-      if (!after)
-        {
-          gcc_assert (new_loop_exit_e == orig_entry_e);
-	  adjust_phi_and_debug_stmts (phi_orig, new_loop_exit_e, new_ssa_name);
-        }
-    }
-}
-
-
 /* Update PHI nodes for a guard of the LOOP.
 
    Input:
@@ -809,16 +698,15 @@ slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
   bool at_exit;
   bool was_imm_dom;
   basic_block exit_dest;
-  gimple phi;
-  tree phi_arg;
   edge exit, new_exit;
-  gimple_stmt_iterator gsi;
 
-  at_exit = (e == single_exit (loop));
+  exit = single_exit (loop);
+  at_exit = (e == exit);
   if (!at_exit && e != loop_preheader_edge (loop))
     return NULL;
 
-  bbs = get_loop_body (loop);
+  bbs = XNEWVEC (basic_block, loop->num_nodes + 1);
+  get_loop_body_with_size (loop, bbs, loop->num_nodes);
 
   /* Check whether duplication is possible.  */
   if (!can_copy_bbs_p (bbs, loop->num_nodes))
@@ -829,91 +717,71 @@ slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
 
   /* Generate new loop structure.  */
   new_loop = duplicate_loop (loop, loop_outer (loop));
-  if (!new_loop)
-    {
-      free (bbs);
-      return NULL;
-    }
+  duplicate_subloops (loop, new_loop);
 
-  exit_dest = single_exit (loop)->dest;
+  exit_dest = exit->dest;
   was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
 					  exit_dest) == loop->header ?
 		 true : false);
 
-  new_bbs = XNEWVEC (basic_block, loop->num_nodes);
+  /* Also copy the pre-header, this avoids jumping through hoops to
+     duplicate the loop entry PHI arguments.  Create an empty
+     pre-header unconditionally for this.  */
+  basic_block preheader = split_edge (loop_preheader_edge (loop));
+  edge entry_e = single_pred_edge (preheader);
+  bbs[loop->num_nodes] = preheader;
+  new_bbs = XNEWVEC (basic_block, loop->num_nodes + 1);
 
-  exit = single_exit (loop);
-  copy_bbs (bbs, loop->num_nodes, new_bbs,
+  copy_bbs (bbs, loop->num_nodes + 1, new_bbs,
 	    &exit, 1, &new_exit, NULL,
 	    e->src);
+  basic_block new_preheader = new_bbs[loop->num_nodes];
 
-  /* Duplicating phi args at exit bbs as coming
-     also from exit of duplicated loop.  */
-  for (gsi = gsi_start_phis (exit_dest); !gsi_end_p (gsi); gsi_next (&gsi))
-    {
-      phi = gsi_stmt (gsi);
-      phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
-      if (phi_arg)
-	{
-	  edge new_loop_exit_edge;
-	  source_location locus;
-
-	  locus = gimple_phi_arg_location_from_edge (phi, single_exit (loop));
-	  if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
-	    new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
-	  else
-	    new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
-
-	  add_phi_arg (phi, phi_arg, new_loop_exit_edge, locus);
-	}
-    }
+  add_phi_args_after_copy (new_bbs, loop->num_nodes + 1, NULL);
 
   if (at_exit) /* Add the loop copy at exit.  */
     {
-      redirect_edge_and_branch_force (e, new_loop->header);
-      PENDING_STMT (e) = NULL;
-      set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
+      redirect_edge_and_branch_force (e, new_preheader);
+      flush_pending_stmts (e);
+      set_immediate_dominator (CDI_DOMINATORS, new_preheader, e->src);
       if (was_imm_dom)
 	set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
+
+      /* And remove the non-necessary forwarder again.  Keep the other
+         one so we have a proper pre-header for the loop at the exit edge.  */
+      redirect_edge_pred (single_succ_edge (preheader), single_pred (preheader));
+      delete_basic_block (preheader);
+      set_immediate_dominator (CDI_DOMINATORS, loop->header,
+			       loop_preheader_edge (loop)->src);
     }
   else /* Add the copy at entry.  */
     {
-      edge new_exit_e;
-      edge entry_e = loop_preheader_edge (loop);
-      basic_block preheader = entry_e->src;
-
-      if (!flow_bb_inside_loop_p (new_loop,
-				  EDGE_SUCC (new_loop->header, 0)->dest))
-        new_exit_e = EDGE_SUCC (new_loop->header, 0);
-      else
-	new_exit_e = EDGE_SUCC (new_loop->header, 1);
-
-      redirect_edge_and_branch_force (new_exit_e, loop->header);
-      PENDING_STMT (new_exit_e) = NULL;
-      set_immediate_dominator (CDI_DOMINATORS, loop->header,
-			       new_exit_e->src);
-
-      /* We have to add phi args to the loop->header here as coming
-	 from new_exit_e edge.  */
-      for (gsi = gsi_start_phis (loop->header);
-           !gsi_end_p (gsi);
-           gsi_next (&gsi))
-	{
-	  phi = gsi_stmt (gsi);
-	  phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
-	  if (phi_arg)
-	    add_phi_arg (phi, phi_arg, new_exit_e,
-			 gimple_phi_arg_location_from_edge (phi, entry_e));
-	}
-
-      redirect_edge_and_branch_force (entry_e, new_loop->header);
-      PENDING_STMT (entry_e) = NULL;
-      set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
+      redirect_edge_and_branch_force (entry_e, new_preheader);
+      flush_pending_stmts (entry_e);
+      set_immediate_dominator (CDI_DOMINATORS, new_preheader, entry_e->src);
+
+      redirect_edge_and_branch_force (new_exit, preheader);
+      flush_pending_stmts (new_exit);
+      set_immediate_dominator (CDI_DOMINATORS, preheader, new_exit->src);
+
+      /* And remove the non-necessary forwarder again.  Keep the other
+         one so we have a proper pre-header for the loop at the exit edge.  */
+      redirect_edge_pred (single_succ_edge (new_preheader), single_pred (new_preheader));
+      delete_basic_block (new_preheader);
+      set_immediate_dominator (CDI_DOMINATORS, new_loop->header,
+			       loop_preheader_edge (new_loop)->src);
     }
 
+  for (unsigned i = 0; i < loop->num_nodes+1; i++)
+    rename_variables_in_bb (new_bbs[i]);
+
   free (new_bbs);
   free (bbs);
 
+#ifdef ENABLE_CHECKING
+  verify_dominators (CDI_DOMINATORS);
+#endif
+
   return new_loop;
 }
 
@@ -1265,10 +1133,6 @@ slpeel_tree_peel_loop_to_edge (struct loop *loop,
       second_loop = loop;
     }
 
-  slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
-  rename_variables_in_loop (new_loop);
-
-
   /* 2.  Add the guard code in one of the following ways:
 
      2.a Add the guard that controls whether the first loop is executed.
@@ -1355,7 +1219,8 @@ slpeel_tree_peel_loop_to_edge (struct loop *loop,
   */
 
   bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
-  bb_before_second_loop = split_edge (single_exit (first_loop));
+  /* Loop copying insterted a forwarder block for us here.  */
+  bb_before_second_loop = single_exit (first_loop)->dest;
 
   probability_of_second_loop = (inverse_probability (first_guard_probability)
 			        + combine_probabilities (second_guard_probability,