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

7 files changed, 180 insertions, 62 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 203873e..acb109e 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,19 @@
+2007-02-04  Zdenek Dvorak <dvorakz@suse.cz>
+
+	* 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.
+
 2007-02-05  Jan Hubicka  <jh@suse.cz>
 
 	PR middle-end/30696
diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
index d6a981d..d65cce9 100644
--- a/gcc/cfghooks.c
+++ b/gcc/cfghooks.c
@@ -318,6 +318,48 @@ redirect_edge_and_branch (edge e, basic_block dest)
   return ret;
 }
 
+/* Returns true if it is possible to remove the edge E by redirecting it
+   to the destination of the other edge going from its source.  */
+
+bool
+can_remove_branch_p (edge e)
+{
+  if (!cfg_hooks->can_remove_branch_p)
+    internal_error ("%s does not support can_remove_branch_p",
+		    cfg_hooks->name);
+
+  if (EDGE_COUNT (e->src->succs) != 2)
+    return false;
+
+  return cfg_hooks->can_remove_branch_p (e);
+}
+
+/* Removes E, by redirecting it to the destination of the other edge going
+   from its source.  Can_remove_branch_p must be true for E, hence this
+   operation cannot fail.  */
+
+void
+remove_branch (edge e)
+{
+  edge other;
+  basic_block src = e->src;
+  int irr;
+
+  gcc_assert (EDGE_COUNT (e->src->succs) == 2);
+
+  other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
+  irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
+
+  if (current_loops != NULL)
+    rescan_loop_exit (e, false, true);
+
+  e = redirect_edge_and_branch (e, other->dest);
+  gcc_assert (e != NULL);
+
+  e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+  e->flags |= irr;
+}
+
 /* Redirect the edge E to basic block DEST even if it requires creating
    of a new basic block; then it returns the newly created basic block.
    Aborts when redirection is impossible.  */
diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h
index fb6264d..bd7d1b3 100644
--- a/gcc/cfghooks.h
+++ b/gcc/cfghooks.h
@@ -47,6 +47,10 @@ struct cfg_hooks
      not be abnormal.  */
   basic_block (*redirect_edge_and_branch_force) (edge, basic_block);
 
+  /* Returns true if it is possible to remove the edge by redirecting it
+     to the destination of the other edge going from its source.  */
+  bool (*can_remove_branch_p) (edge);
+
   /* Remove statements corresponding to a given basic block.  */
   void (*delete_basic_block) (basic_block);
 
@@ -138,6 +142,8 @@ extern void verify_flow_info (void);
 extern void dump_bb (basic_block, FILE *, int);
 extern edge redirect_edge_and_branch (edge, basic_block);
 extern basic_block redirect_edge_and_branch_force (edge, basic_block);
+extern bool can_remove_branch_p (edge);
+extern void remove_branch (edge);
 extern edge split_block (basic_block, void *);
 extern edge split_block_after_labels (basic_block);
 extern bool move_block_after (basic_block, basic_block);
diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 74f7b07..8e5f4c2 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -35,7 +35,6 @@ static void duplicate_subloops (struct loop *, struct loop *);
 static void copy_loops_to (struct loop **, int,
 			   struct loop *);
 static void loop_redirect_edge (edge, basic_block);
-static bool loop_delete_branch_edge (edge, int);
 static void remove_bbs (basic_block *, int);
 static bool rpe_enum_p (basic_block, void *);
 static int find_path (edge, basic_block **);
@@ -283,10 +282,10 @@ remove_path (edge e)
   basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
   int i, nrem, n_bord_bbs, n_dom_bbs, nreml;
   sbitmap seen;
-  bool deleted, irred_invalidated = false;
+  bool irred_invalidated = false;
   struct loop **deleted_loop;
 
-  if (!loop_delete_branch_edge (e, 0))
+  if (!can_remove_branch_p (e))
     return false;
 
   /* Keep track of whether we need to update information about irreducible
@@ -341,8 +340,7 @@ remove_path (edge e)
 
   /* Remove the path.  */
   from = e->src;
-  deleted = loop_delete_branch_edge (e, 1);
-  gcc_assert (deleted);
+  remove_branch (e);
   dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
 
   /* Cancel loops contained in the path.  */
@@ -698,45 +696,6 @@ loop_redirect_edge (edge e, basic_block dest)
   redirect_edge_and_branch_force (e, dest);
 }
 
-/* Deletes edge E from a branch if possible.  Unless REALLY_DELETE is set,
-   just test whether it is possible to remove the edge.  */
-static bool
-loop_delete_branch_edge (edge e, int really_delete)
-{
-  basic_block src = e->src;
-  basic_block newdest;
-  int irr;
-  edge snd;
-
-  gcc_assert (EDGE_COUNT (src->succs) > 1);
-
-  /* Cannot handle more than two exit edges.  */
-  if (EDGE_COUNT (src->succs) > 2)
-    return false;
-  /* And it must be just a simple branch.  */
-  if (!any_condjump_p (BB_END (src)))
-    return false;
-
-  snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0);
-  newdest = snd->dest;
-  if (newdest == EXIT_BLOCK_PTR)
-    return false;
-
-  /* Hopefully the above conditions should suffice.  */
-  if (!really_delete)
-    return true;
-
-  /* Redirecting behaves wrongly wrto this flag.  */
-  irr = snd->flags & EDGE_IRREDUCIBLE_LOOP;
-
-  if (!redirect_edge_and_branch (e, newdest))
-    return false;
-  single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
-  single_succ_edge (src)->flags |= irr;
-
-  return true;
-}
-
 /* Check whether LOOP's body can be duplicated.  */
 bool
 can_duplicate_loop_p (struct loop *loop)
diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c
index 4424621..1eb75ab 100644
--- a/gcc/cfgrtl.c
+++ b/gcc/cfgrtl.c
@@ -2977,6 +2977,38 @@ insert_insn_end_bb_new (rtx pat, basic_block bb)
   return new_insn;
 }
 
+/* Returns true if it is possible to remove edge E by redirecting
+   it to the destination of the other edge from E->src.  */
+
+static bool
+rtl_can_remove_branch_p (edge e)
+{
+  basic_block src = e->src;
+  basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
+  rtx insn = BB_END (src), set;
+
+  /* The conditions are taken from try_redirect_by_replacing_jump.  */
+  if (target == EXIT_BLOCK_PTR)
+    return false;
+
+  if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
+    return false;
+
+  if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
+      || BB_PARTITION (src) != BB_PARTITION (target))
+    return false;
+
+  if (!onlyjump_p (insn)
+      || tablejump_p (insn, NULL, NULL))
+    return false;
+
+  set = single_set (insn);
+  if (!set || side_effects_p (set))
+    return false;
+
+  return true;
+}
+
 /* Implementation of CFG manipulation for linearized RTL.  */
 struct cfg_hooks rtl_cfg_hooks = {
   "rtl",
@@ -2985,6 +3017,7 @@ struct cfg_hooks rtl_cfg_hooks = {
   rtl_create_basic_block,
   rtl_redirect_edge_and_branch,
   rtl_redirect_edge_and_branch_force,
+  rtl_can_remove_branch_p,
   rtl_delete_block,
   rtl_split_block,
   rtl_move_block_after,
@@ -3028,6 +3061,7 @@ struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
   cfg_layout_create_basic_block,
   cfg_layout_redirect_edge_and_branch,
   cfg_layout_redirect_edge_and_branch_force,
+  rtl_can_remove_branch_p,
   cfg_layout_delete_block,
   cfg_layout_split_block,
   rtl_move_block_after,
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index e9111d9..6f49205 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -4219,6 +4219,17 @@ tree_redirect_edge_and_branch (edge e, basic_block dest)
   return e;
 }
 
+/* Returns true if it is possible to remove edge E by redirecting
+   it to the destination of the other edge from E->src.  */
+
+static bool
+tree_can_remove_branch_p (edge e)
+{
+  if (e->flags & EDGE_ABNORMAL)
+    return false;
+
+  return true;
+}
 
 /* Simple wrapper, as we can always redirect fallthru edges.  */
 
@@ -5614,6 +5625,7 @@ struct cfg_hooks tree_cfg_hooks = {
   create_bb,			/* create_basic_block  */
   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
+  tree_can_remove_branch_p,	/* can_remove_branch_p  */
   remove_bb,			/* delete_basic_block  */
   tree_split_block,		/* split_block  */
   tree_move_block_after,	/* move_block_after  */
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.  */