Patchwork 03/03: Keep dominance info up to date

login
register
mail settings
Submitter Andrey Belevantsev
Date Oct. 4, 2010, 3:45 p.m.
Message ID <4CA9F69F.6040407@ispras.ru>
Download mbox | patch
Permalink /patch/66706/
State New
Headers show

Comments

Andrey Belevantsev - Oct. 4, 2010, 3:45 p.m.
Hello,

This main patch uses set_immediate_dominator and iterate_fix_dominators 
when updating control flow in selective scheduler.  The difficulty I had is 
that when an unreachable block may be created, you need to defer the update 
until the block is removed, so sometimes we avoid updating dominance info 
in sel_redirect_edge_and_branch and postpone it to maybe_tidy_empty_bb 
instead.  I will add testcase from PR 43603, and I need to minimize one 
from PR 44233.

Bootstrapped with the other two patches, testing is in progress.  Ok for 
trunk if it succeeds?  Ok for 4.5/4.4 after a week or two?

Andrey

	2010-10-04  Andrey Belevantsev  <abel@ispras.ru>

	PR target/43603
	PR target/44233

	* haifa-sched.c (sched_create_recovery_edges): Update
	dominator info.
	* sel-sched-ir.c (maybe_tidy_empty_bb): Update dominator info
	after deleting an empty block.
	(sel_remove_bb): Update dominator info after removing a block.
	(sel_redirect_edge_and_branch_force): Assert that no unreachable
	blocks will be created.  Update dominator info.
	(sel_redirect_edge_and_branch): Update dominator info when
	basic blocks do not become unreachable.
	(sel_remove_loop_preheader): Update dominator info.
Andrey Belevantsev - Oct. 22, 2010, 7:51 a.m.
Ping.  http://gcc.gnu.org/ml/gcc-patches/2010-10/msg00206.html
Andrey

On 04.10.2010 19:45, Andrey Belevantsev wrote:
> Hello,
>
> This main patch uses set_immediate_dominator and iterate_fix_dominators
> when updating control flow in selective scheduler. The difficulty I had is
> that when an unreachable block may be created, you need to defer the update
> until the block is removed, so sometimes we avoid updating dominance info
> in sel_redirect_edge_and_branch and postpone it to maybe_tidy_empty_bb
> instead. I will add testcase from PR 43603, and I need to minimize one from
> PR 44233.
>
> Bootstrapped with the other two patches, testing is in progress. Ok for
> trunk if it succeeds? Ok for 4.5/4.4 after a week or two?
>
> Andrey
>
> 2010-10-04 Andrey Belevantsev <abel@ispras.ru>
>
> PR target/43603
> PR target/44233
>
> * haifa-sched.c (sched_create_recovery_edges): Update
> dominator info.
> * sel-sched-ir.c (maybe_tidy_empty_bb): Update dominator info
> after deleting an empty block.
> (sel_remove_bb): Update dominator info after removing a block.
> (sel_redirect_edge_and_branch_force): Assert that no unreachable
> blocks will be created. Update dominator info.
> (sel_redirect_edge_and_branch): Update dominator info when
> basic blocks do not become unreachable.
> (sel_remove_loop_preheader): Update dominator info.
>
>
> 03-update.diff
>
>
> diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
> index 8d7149f..6bf526e 100644
> --- a/gcc/haifa-sched.c
> +++ b/gcc/haifa-sched.c
> @@ -4452,6 +4452,8 @@ sched_create_recovery_edges (basic_block first_bb, basic_block rec,
>       edge_flags = 0;
>
>     make_single_succ_edge (rec, second_bb, edge_flags);
> +  if (dom_info_available_p (CDI_DOMINATORS))
> +    set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
>   }
>
>   /* This function creates recovery code for INSN.  If MUTATE_P is nonzero,
> diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
> index 3146a26..72b4892 100644
> --- a/gcc/sel-sched-ir.c
> +++ b/gcc/sel-sched-ir.c
> @@ -3544,6 +3544,7 @@ static bool
>   maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
>   {
>     basic_block succ_bb, pred_bb;
> +  VEC (basic_block, heap) *dom_bbs;
>     edge e;
>     edge_iterator ei;
>     bool rescan_p;
> @@ -3579,6 +3580,7 @@ maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
>     succ_bb = single_succ (bb);
>     rescan_p = true;
>     pred_bb = NULL;
> +  dom_bbs = NULL;
>
>     /* Redirect all non-fallthru edges to the next bb.  */
>     while (rescan_p)
> @@ -3591,6 +3593,12 @@ maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
>
>             if (!(e->flags&  EDGE_FALLTHRU))
>               {
> +              /* We will update dominators here only when we'll get
> +                 an unreachable block when redirecting, otherwise
> +                 sel_redirect_edge_and_branch will take care of it.  */
> +              if (e->dest != bb
> +&&  single_pred_p (e->dest))
> +                VEC_safe_push (basic_block, heap, dom_bbs, e->dest);
>                 recompute_toporder_p |= sel_redirect_edge_and_branch (e, succ_bb);
>                 rescan_p = true;
>                 break;
> @@ -3610,11 +3618,20 @@ maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
>         remove_empty_bb (bb, true);
>       }
>
> +
> +  if (!VEC_empty (basic_block, dom_bbs))
> +    {
> +      VEC_safe_push (basic_block, heap, dom_bbs, succ_bb);
> +      iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
> +      VEC_free (basic_block, heap, dom_bbs);
> +    }
> +
>     if (recompute_toporder_p)
>       sel_recompute_toporder ();
>
>   #ifdef ENABLE_CHECKING
>     verify_backedges ();
> +  verify_dominators (CDI_DOMINATORS);
>   #endif
>
>     return true;
> @@ -5026,7 +5043,12 @@ sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
>     bitmap_clear_bit (blocks_to_reschedule, idx);
>
>     if (remove_from_cfg_p)
> -    delete_and_free_basic_block (bb);
> +    {
> +      basic_block succ = single_succ (bb);
> +      delete_and_free_basic_block (bb);
> +      set_immediate_dominator (CDI_DOMINATORS, succ,
> +                               recompute_dominator (CDI_DOMINATORS, succ));
> +    }
>
>     rgn_setup_region (CONTAINING_RGN (idx));
>   }
> @@ -5361,12 +5383,15 @@ sel_merge_blocks (basic_block a, basic_block b)
>   void
>   sel_redirect_edge_and_branch_force (edge e, basic_block to)
>   {
> -  basic_block jump_bb, src;
> +  basic_block jump_bb, src, orig_dest = e->dest;
>     int prev_max_uid;
>     rtx jump;
>
> -  gcc_assert (!sel_bb_empty_p (e->src));
> -
> +  /* This function is now used only for bookkeeping code creation, where
> +     we'll never get the single pred of orig_dest block and thus will not
> +     hit unreachable blocks when updating dominator info.  */
> +  gcc_assert (!sel_bb_empty_p (e->src)
> +&&  !single_pred_p (orig_dest));
>     src = e->src;
>     prev_max_uid = get_max_uid ();
>     jump_bb = redirect_edge_and_branch_force (e, to);
> @@ -5383,6 +5408,10 @@ sel_redirect_edge_and_branch_force (edge e, basic_block to)
>     jump = find_new_jump (src, jump_bb, prev_max_uid);
>     if (jump)
>       sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
> +  set_immediate_dominator (CDI_DOMINATORS, to,
> +			   recompute_dominator (CDI_DOMINATORS, to));
> +  set_immediate_dominator (CDI_DOMINATORS, orig_dest,
> +			   recompute_dominator (CDI_DOMINATORS, orig_dest));
>   }
>
>   /* A wrapper for redirect_edge_and_branch.  Return TRUE if blocks connected by
> @@ -5391,11 +5420,12 @@ bool
>   sel_redirect_edge_and_branch (edge e, basic_block to)
>   {
>     bool latch_edge_p;
> -  basic_block src;
> +  basic_block src, orig_dest = e->dest;
>     int prev_max_uid;
>     rtx jump;
>     edge redirected;
>     bool recompute_toporder_p = false;
> +  bool maybe_unreachable = single_pred_p (orig_dest);
>
>     latch_edge_p = (pipelining_p
>                     &&  current_loop_nest
> @@ -5426,6 +5456,15 @@ sel_redirect_edge_and_branch (edge e, basic_block to)
>     if (jump)
>       sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
>
> +  /* Only update dominator info when we don't have unreachable blocks.
> +     Otherwise we'll update in maybe_tidy_empty_bb.  */
> +  if (!maybe_unreachable)
> +    {
> +      set_immediate_dominator (CDI_DOMINATORS, to,
> +                               recompute_dominator (CDI_DOMINATORS, to));
> +      set_immediate_dominator (CDI_DOMINATORS, orig_dest,
> +                               recompute_dominator (CDI_DOMINATORS, orig_dest));
> +    }
>     return recompute_toporder_p;
>   }
>
> @@ -6155,6 +6194,10 @@ sel_remove_loop_preheader (void)
>                     if (BB_END (prev_bb) == bb_note (prev_bb))
>                       free_data_sets (prev_bb);
>                   }
> +
> +              set_immediate_dominator (CDI_DOMINATORS, next_bb,
> +                                       recompute_dominator (CDI_DOMINATORS,
> +                                                            next_bb));
>               }
>           }
>         VEC_free (basic_block, heap, preheader_blocks);
Andrey Belevantsev - Nov. 9, 2010, 5:31 p.m.
Hello,

Ping^2.  There is a duplication PR about this bug now (46384).  Testing was 
fine, I didn't mention it in the previous ping.

Andrey

On 22.10.2010 11:51, Andrey Belevantsev wrote:
> Ping. http://gcc.gnu.org/ml/gcc-patches/2010-10/msg00206.html
> Andrey
>
> On 04.10.2010 19:45, Andrey Belevantsev wrote:
>> Hello,
>>
>> This main patch uses set_immediate_dominator and iterate_fix_dominators
>> when updating control flow in selective scheduler. The difficulty I had is
>> that when an unreachable block may be created, you need to defer the update
>> until the block is removed, so sometimes we avoid updating dominance info
>> in sel_redirect_edge_and_branch and postpone it to maybe_tidy_empty_bb
>> instead. I will add testcase from PR 43603, and I need to minimize one from
>> PR 44233.
>>
>> Bootstrapped with the other two patches, testing is in progress. Ok for
>> trunk if it succeeds? Ok for 4.5/4.4 after a week or two?
>>
>> Andrey
>>
>> 2010-10-04 Andrey Belevantsev <abel@ispras.ru>
>>
>> PR target/43603
>> PR target/44233
>>
>> * haifa-sched.c (sched_create_recovery_edges): Update
>> dominator info.
>> * sel-sched-ir.c (maybe_tidy_empty_bb): Update dominator info
>> after deleting an empty block.
>> (sel_remove_bb): Update dominator info after removing a block.
>> (sel_redirect_edge_and_branch_force): Assert that no unreachable
>> blocks will be created. Update dominator info.
>> (sel_redirect_edge_and_branch): Update dominator info when
>> basic blocks do not become unreachable.
>> (sel_remove_loop_preheader): Update dominator info.
>>
>>

Patch

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index 8d7149f..6bf526e 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -4452,6 +4452,8 @@  sched_create_recovery_edges (basic_block first_bb, basic_block rec,
     edge_flags = 0;
 
   make_single_succ_edge (rec, second_bb, edge_flags);
+  if (dom_info_available_p (CDI_DOMINATORS))
+    set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
 }
 
 /* This function creates recovery code for INSN.  If MUTATE_P is nonzero,
diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index 3146a26..72b4892 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -3544,6 +3544,7 @@  static bool
 maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
 {
   basic_block succ_bb, pred_bb;
+  VEC (basic_block, heap) *dom_bbs;
   edge e;
   edge_iterator ei;
   bool rescan_p;
@@ -3579,6 +3580,7 @@  maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
   succ_bb = single_succ (bb);
   rescan_p = true;
   pred_bb = NULL;
+  dom_bbs = NULL;
 
   /* Redirect all non-fallthru edges to the next bb.  */
   while (rescan_p)
@@ -3591,6 +3593,12 @@  maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
 
           if (!(e->flags & EDGE_FALLTHRU))
             {
+              /* We will update dominators here only when we'll get
+                 an unreachable block when redirecting, otherwise
+                 sel_redirect_edge_and_branch will take care of it.  */
+              if (e->dest != bb
+                  && single_pred_p (e->dest))
+                VEC_safe_push (basic_block, heap, dom_bbs, e->dest);
               recompute_toporder_p |= sel_redirect_edge_and_branch (e, succ_bb);
               rescan_p = true;
               break;
@@ -3610,11 +3618,20 @@  maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
       remove_empty_bb (bb, true);
     }
 
+
+  if (!VEC_empty (basic_block, dom_bbs))
+    {
+      VEC_safe_push (basic_block, heap, dom_bbs, succ_bb);
+      iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
+      VEC_free (basic_block, heap, dom_bbs);
+    }
+
   if (recompute_toporder_p)
     sel_recompute_toporder ();
 
 #ifdef ENABLE_CHECKING
   verify_backedges ();
+  verify_dominators (CDI_DOMINATORS);
 #endif
 
   return true;
@@ -5026,7 +5043,12 @@  sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
   bitmap_clear_bit (blocks_to_reschedule, idx);
 
   if (remove_from_cfg_p)
-    delete_and_free_basic_block (bb);
+    {
+      basic_block succ = single_succ (bb);
+      delete_and_free_basic_block (bb);
+      set_immediate_dominator (CDI_DOMINATORS, succ,
+                               recompute_dominator (CDI_DOMINATORS, succ));
+    }
 
   rgn_setup_region (CONTAINING_RGN (idx));
 }
@@ -5361,12 +5383,15 @@  sel_merge_blocks (basic_block a, basic_block b)
 void
 sel_redirect_edge_and_branch_force (edge e, basic_block to)
 {
-  basic_block jump_bb, src;
+  basic_block jump_bb, src, orig_dest = e->dest;
   int prev_max_uid;
   rtx jump;
 
-  gcc_assert (!sel_bb_empty_p (e->src));
-
+  /* This function is now used only for bookkeeping code creation, where
+     we'll never get the single pred of orig_dest block and thus will not
+     hit unreachable blocks when updating dominator info.  */
+  gcc_assert (!sel_bb_empty_p (e->src)
+              && !single_pred_p (orig_dest));
   src = e->src;
   prev_max_uid = get_max_uid ();
   jump_bb = redirect_edge_and_branch_force (e, to);
@@ -5383,6 +5408,10 @@  sel_redirect_edge_and_branch_force (edge e, basic_block to)
   jump = find_new_jump (src, jump_bb, prev_max_uid);
   if (jump)
     sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
+  set_immediate_dominator (CDI_DOMINATORS, to,
+			   recompute_dominator (CDI_DOMINATORS, to));
+  set_immediate_dominator (CDI_DOMINATORS, orig_dest,
+			   recompute_dominator (CDI_DOMINATORS, orig_dest));
 }
 
 /* A wrapper for redirect_edge_and_branch.  Return TRUE if blocks connected by
@@ -5391,11 +5420,12 @@  bool
 sel_redirect_edge_and_branch (edge e, basic_block to)
 {
   bool latch_edge_p;
-  basic_block src;
+  basic_block src, orig_dest = e->dest;
   int prev_max_uid;
   rtx jump;
   edge redirected;
   bool recompute_toporder_p = false;
+  bool maybe_unreachable = single_pred_p (orig_dest);
 
   latch_edge_p = (pipelining_p
                   && current_loop_nest
@@ -5426,6 +5456,15 @@  sel_redirect_edge_and_branch (edge e, basic_block to)
   if (jump)
     sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
 
+  /* Only update dominator info when we don't have unreachable blocks.
+     Otherwise we'll update in maybe_tidy_empty_bb.  */
+  if (!maybe_unreachable)
+    {
+      set_immediate_dominator (CDI_DOMINATORS, to,
+                               recompute_dominator (CDI_DOMINATORS, to));
+      set_immediate_dominator (CDI_DOMINATORS, orig_dest,
+                               recompute_dominator (CDI_DOMINATORS, orig_dest));
+    }
   return recompute_toporder_p;
 }
 
@@ -6155,6 +6194,10 @@  sel_remove_loop_preheader (void)
                   if (BB_END (prev_bb) == bb_note (prev_bb))
                     free_data_sets (prev_bb);
                 }
+
+              set_immediate_dominator (CDI_DOMINATORS, next_bb,
+                                       recompute_dominator (CDI_DOMINATORS,
+                                                            next_bb));
             }
         }
       VEC_free (basic_block, heap, preheader_blocks);