cfgloopmanip.c (loop_delete_branch_edge): Removed.

	* cfgloopmanip.c (loop_delete_branch_edge): Removed.
	(remove_path): Use can_remove_branch_p and remove_branch instead
	of loop_delete_branch_edge.
	* tree-ssa-loop-manip.c (scale_dominated_blocks_in_loop): New function.
	(tree_transform_and_unroll_loop): Remove dead branches immediately.
	Update profile using scale_dominated_blocks_in_loop.
	* cfghooks.c (can_remove_branch_p, remove_branch): New functions.
	* cfghooks.h (struct cfg_hooks): Add can_remove_branch_p.
	(can_remove_branch_p, remove_branch): Declare.
	* tree-cfg.c (tree_can_remove_branch_p): New function.
	(tree_cfg_hooks): Add tree_can_remove_branch_p.
	* cfgrtl.c (rtl_can_remove_branch_p): New function.
	(rtl_cfg_hooks, cfg_layout_rtl_cfg_hook): Add rtl_can_remove_branch_p.

From-SVN: r121583

1 files changed, 67 insertions, 18 deletions

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index d3d3e7e..6b220e9 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -756,6 +756,29 @@ determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
   *exit_bound = bound;
 }
 
+/* Scales the frequencies of all basic blocks in LOOP that are strictly
+   dominated by BB by NUM/DEN.  */
+
+static void
+scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb,
+				int num, int den)
+{
+  basic_block son;
+
+  if (den == 0)
+    return;
+
+  for (son = first_dom_son (CDI_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_DOMINATORS, son))
+    {
+      if (!flow_bb_inside_loop_p (loop, son))
+	continue;
+      scale_bbs_frequencies_int (&son, 1, num, den);
+      scale_dominated_blocks_in_loop (loop, son, num, den);
+    }
+}
+
 /* Unroll LOOP FACTOR times.  DESC describes number of iterations of LOOP.
    EXIT is the exit of the loop to that DESC corresponds.
 
@@ -819,21 +842,22 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
 				transform_callback transform,
 				void *data)
 {
-  tree dont_exit, exit_if, ctr_before, ctr_after;
+  tree  exit_if, ctr_before, ctr_after;
   tree enter_main_cond, exit_base, exit_step, exit_bound;
   enum tree_code exit_cmp;
   tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
   struct loop *new_loop;
   basic_block rest, exit_bb;
   edge old_entry, new_entry, old_latch, precond_edge, new_exit;
-  edge new_nonexit;
+  edge new_nonexit, e;
   block_stmt_iterator bsi;
   use_operand_p op;
   bool ok;
   unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h;
-  unsigned new_est_niter;
+  unsigned new_est_niter, i, prob;
   unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
   sbitmap wont_exit;
+  VEC (edge, heap) *to_remove = NULL;
 
   est_niter = expected_loop_iterations (loop);
   determine_exit_conditions (loop, desc, factor,
@@ -882,14 +906,20 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
 	new_est_niter = 5;
     }
 
-  /* Prepare the cfg and update the phi nodes.  */
+  /* Prepare the cfg and update the phi nodes.  Move the loop exit to the
+     loop latch (and make its condition dummy, for the moment).  */
   rest = loop_preheader_edge (new_loop)->src;
   precond_edge = single_pred_edge (rest);
   split_edge (loop_latch_edge (loop));
   exit_bb = single_pred (loop->latch);
 
-  /* For the moment, make it appear that the new exit edge cannot
-     be taken.  */
+  /* Since the exit edge will be removed, the frequency of all the blocks
+     in the loop that are dominated by it must be scaled by
+     1 / (1 - exit->probability).  */
+  scale_dominated_blocks_in_loop (loop, exit->src,
+				  REG_BR_PROB_BASE,
+				  REG_BR_PROB_BASE - exit->probability);
+
   bsi = bsi_last (exit_bb);
   exit_if = build_if_stmt (boolean_true_node,
 			   tree_block_label (loop->latch),
@@ -897,10 +927,20 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
   bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
   new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
   rescan_loop_exit (new_exit, true, false);
-  new_exit->count = 0;
-  new_exit->probability = 0;
+
+  /* Set the probability of new exit to the same of the old one.  Fix
+     the frequency of the latch block, by scaling it back by
+     1 - exit->probability.  */
+  new_exit->count = exit->count;
+  new_exit->probability = exit->probability;
   new_nonexit = single_pred_edge (loop->latch);
+  new_nonexit->probability = REG_BR_PROB_BASE - exit->probability;
   new_nonexit->flags = EDGE_TRUE_VALUE;
+  new_nonexit->count -= exit->count;
+  if (new_nonexit->count < 0)
+    new_nonexit->count = 0;
+  scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
+			     REG_BR_PROB_BASE);
 
   old_entry = loop_preheader_edge (loop);
   new_entry = loop_preheader_edge (new_loop);
@@ -938,25 +978,30 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
       SET_USE (op, new_init);
     }
 
+  remove_path (exit);
+
   /* Transform the loop.  */
   if (transform)
     (*transform) (loop, data);
 
-  /* Unroll the loop and remove the old exits.  */
-  dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
-	       ? boolean_false_node
-	       : boolean_true_node);
-  exit_if = last_stmt (exit->src);
-  COND_EXPR_COND (exit_if) = dont_exit;
-  update_stmt (exit_if);
-      
+  /* Unroll the loop and remove the exits in all iterations except for the
+     last one.  */
   wont_exit = sbitmap_alloc (factor);
   sbitmap_ones (wont_exit);
+  RESET_BIT (wont_exit, factor - 1);
+
   ok = tree_duplicate_loop_to_header_edge
 	  (loop, loop_latch_edge (loop), factor - 1,
-	   wont_exit, exit, NULL, DLTHE_FLAG_UPDATE_FREQ);
+	   wont_exit, new_exit, &to_remove, DLTHE_FLAG_UPDATE_FREQ);
   free (wont_exit);
   gcc_assert (ok);
+
+  for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
+    {
+      ok = remove_path (e);
+      gcc_assert (ok);
+    }
+  VEC_free (edge, heap, to_remove);
   update_ssa (TODO_update_ssa);
 
   /* Ensure that the frequencies in the loop match the new estimated
@@ -976,9 +1021,13 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
   rest->frequency += EDGE_FREQUENCY (new_exit);
 
   new_nonexit = single_pred_edge (loop->latch);
+  prob = new_nonexit->probability;
   new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
+  new_nonexit->count = exit_bb->count - new_exit->count;
+  if (new_nonexit->count < 0)
+    new_nonexit->count = 0;
   scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
-			     REG_BR_PROB_BASE);
+			     prob);
 
   /* Finally create the new counter for number of iterations and add the new
      exit instruction.  */