[patch] Remove dead branches in unrolling/unswitching on trees

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

at the moment, the unreachable edges created during loop unrolling and
unswitching on trees are preserved and they are only removed during the
next cfg cleanup.  This simplifies the implementation of the loop manipulation
functions a bit, however it also complicates and restricts their usage;
for example

-- for code like

   for (i = 0; i < 2; i++)
     for (j = 0; j < 2; j++)
       a[i][j] = 0;

   we would definitely like to completely unroll both loops.  However, at
   the moment we only unroll the innermost one, and since we do not cancel
   it immediately and we do not unroll non-innermost loops, we do not try
   to unroll the outer loop,

-- I have several testcases that need the invariant motion to be
   interleaved with loop unswitching to optimize them fully, however,
   if we do not remove the dead branches immediately during loop unswitching,
   we do not expose the new opportunities for invariant motion.

The patch below is the first step towards removing the dead branches
directly during the loop transformations on trees.  It creates the new cfghook
necessary to test whether a branch can be removed, and to remove it.
To test this change, I have also included removing edges in
tree-ssa-loop-manip.c:tree_transform_and_unroll_loop (I will send the
changes for other places in separate patches).

Bootstrapped & regtested on i686.  I need an approval for the parts of the
patch outside of the loop optimizer (the cfghooks changes).

Zdenek

	* 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.

Index: cfgloopmanip.c
===================================================================
*** cfgloopmanip.c	(revision 120796)
--- cfgloopmanip.c	(working copy)
*************** static void duplicate_subloops (struct l
*** 35,41 ****
  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 **);
--- 35,40 ----
*************** remove_path (edge e)
*** 283,292 ****
    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;
    struct loop **deleted_loop;
  
!   if (!loop_delete_branch_edge (e, 0))
      return false;
  
    /* Keep track of whether we need to update information about irreducible
--- 282,291 ----
    basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
    int i, nrem, n_bord_bbs, n_dom_bbs, nreml;
    sbitmap seen;
!   bool irred_invalidated = false;
    struct loop **deleted_loop;
  
!   if (!can_remove_branch_p (e))
      return false;
  
    /* Keep track of whether we need to update information about irreducible
*************** remove_path (edge e)
*** 341,348 ****
  
    /* Remove the path.  */
    from = e->src;
!   deleted = loop_delete_branch_edge (e, 1);
!   gcc_assert (deleted);
    dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
  
    /* Cancel loops contained in the path.  */
--- 340,346 ----
  
    /* Remove the path.  */
    from = e->src;
!   remove_branch (e);
    dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
  
    /* Cancel loops contained in the path.  */
*************** loop_redirect_edge (edge e, basic_block 
*** 698,742 ****
    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)
--- 696,701 ----
Index: tree-ssa-loop-manip.c
===================================================================
*** tree-ssa-loop-manip.c	(revision 120796)
--- tree-ssa-loop-manip.c	(working copy)
*************** determine_exit_conditions (struct loop *
*** 755,760 ****
--- 755,783 ----
    *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.
  
*************** tree_transform_and_unroll_loop (struct l
*** 818,838 ****
  				transform_callback transform,
  				void *data)
  {
!   tree dont_exit, 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;
    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 irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
    sbitmap wont_exit;
  
    est_niter = expected_loop_iterations (loop);
    determine_exit_conditions (loop, desc, factor,
--- 841,862 ----
  				transform_callback transform,
  				void *data)
  {
!   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, 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, 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,
*************** tree_transform_and_unroll_loop (struct l
*** 881,894 ****
  	new_est_niter = 5;
      }
  
!   /* Prepare the cfg and update the phi nodes.  */
    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.  */
    bsi = bsi_last (exit_bb);
    exit_if = build_if_stmt (boolean_true_node,
  			   tree_block_label (loop->latch),
--- 905,924 ----
  	new_est_niter = 5;
      }
  
!   /* 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);
  
!   /* 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),
*************** tree_transform_and_unroll_loop (struct l
*** 896,905 ****
    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;
    new_nonexit = single_pred_edge (loop->latch);
    new_nonexit->flags = EDGE_TRUE_VALUE;
  
    old_entry = loop_preheader_edge (loop);
    new_entry = loop_preheader_edge (new_loop);
--- 926,945 ----
    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);
! 
!   /* 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);
*************** tree_transform_and_unroll_loop (struct l
*** 937,961 ****
        SET_USE (op, new_init);
      }
  
    /* 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);
!       
    wont_exit = sbitmap_alloc (factor);
    sbitmap_ones (wont_exit);
    ok = tree_duplicate_loop_to_header_edge
  	  (loop, loop_latch_edge (loop), factor - 1,
! 	   wont_exit, exit, NULL, DLTHE_FLAG_UPDATE_FREQ);
    free (wont_exit);
    gcc_assert (ok);
    update_ssa (TODO_update_ssa);
  
    /* Ensure that the frequencies in the loop match the new estimated
--- 977,1006 ----
        SET_USE (op, new_init);
      }
  
+   remove_path (exit);
+ 
    /* Transform the loop.  */
    if (transform)
      (*transform) (loop, data);
  
!   /* 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, 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
*************** tree_transform_and_unroll_loop (struct l
*** 975,983 ****
    rest->frequency += EDGE_FREQUENCY (new_exit);
  
    new_nonexit = single_pred_edge (loop->latch);
    new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
    scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
! 			     REG_BR_PROB_BASE);
  
    /* Finally create the new counter for number of iterations and add the new
       exit instruction.  */
--- 1020,1032 ----
    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,
! 			     prob);
  
    /* Finally create the new counter for number of iterations and add the new
       exit instruction.  */
Index: cfghooks.c
===================================================================
*** cfghooks.c	(revision 120796)
--- cfghooks.c	(working copy)
*************** redirect_edge_and_branch (edge e, basic_
*** 318,323 ****
--- 318,365 ----
    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.  */
Index: cfghooks.h
===================================================================
*** cfghooks.h	(revision 120796)
--- cfghooks.h	(working copy)
*************** struct cfg_hooks
*** 47,52 ****
--- 47,56 ----
       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);
  
*************** extern void verify_flow_info (void);
*** 138,143 ****
--- 142,149 ----
  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);
Index: tree-cfg.c
===================================================================
*** tree-cfg.c	(revision 120796)
--- tree-cfg.c	(working copy)
*************** tree_redirect_edge_and_branch (edge e, b
*** 4222,4227 ****
--- 4222,4238 ----
    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.  */
  
*************** struct cfg_hooks tree_cfg_hooks = {
*** 5617,5622 ****
--- 5628,5634 ----
    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  */
Index: cfgrtl.c
===================================================================
*** cfgrtl.c	(revision 120796)
--- cfgrtl.c	(working copy)
*************** insert_insn_end_bb_new (rtx pat, basic_b
*** 2961,2966 ****
--- 2961,2998 ----
    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",
*************** struct cfg_hooks rtl_cfg_hooks = {
*** 2969,2974 ****
--- 3001,3007 ----
    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,
*************** struct cfg_hooks cfg_layout_rtl_cfg_hook
*** 3012,3017 ****
--- 3045,3051 ----
    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,