Patchwork [PING] PR 43603: Keep dominance info up to date

login
register
mail settings
Submitter Andrey Belevantsev
Date Dec. 7, 2010, 3:30 p.m.
Message ID <4CFE5329.1010100@ispras.ru>
Download mbox | patch
Permalink /patch/74557/
State New
Headers show

Comments

Andrey Belevantsev - Dec. 7, 2010, 3:30 p.m.
Hello,

On 09.11.2010 20:31, Andrey Belevantsev wrote:
> 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.
>>>

Ping^3.  The patch is slightly updated (attached) as now Alexander has 
slightly changed maybe_tidy_empty_bb, and the verify_dominators call has 
moved to tidy_control_flow.  There are 4 PRs about this problem now (43603, 
44233, 46384, 46640), all of those are fixed with the patch.  I will 
minimize two of the larger test cases this week.

Ok for trunk?

Andrey

2010-12-07  Andrey Belevantsev <abel@ispras.ru>

     PR target/43603

     * 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.
     (tidy_control_flow): Also verify dominators.
     (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.
Vladimir Makarov - Dec. 7, 2010, 4:16 p.m.
On 12/07/2010 10:30 AM, Andrey Belevantsev wrote:
> Hello,
>
> On 09.11.2010 20:31, Andrey Belevantsev wrote:
>> 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.
>>>>
>
> Ping^3.

Sorry for that, Andrey.  I thought somebody else already reviewed it.

>   The patch is slightly updated (attached) as now Alexander has 
> slightly changed maybe_tidy_empty_bb, and the verify_dominators call 
> has moved to tidy_control_flow. 

> There are 4 PRs about this problem now (43603, 44233, 46384, 46640), 
> all of those are fixed with the patch.  I will minimize two of the 
> larger test cases this week.
Please, do it.
>
> Ok for trunk?

Yes, thanks.

>
> 2010-12-07  Andrey Belevantsev <abel@ispras.ru>
>
>     PR target/43603
>
>     * 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.
>     (tidy_control_flow): Also verify dominators.
>     (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 a22baf9..bd3b84c 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -4467,6 +4467,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 2696882..e1c6876 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -3571,6 +3571,7 @@  static bool
 maybe_tidy_empty_bb (basic_block bb)
 {
   basic_block succ_bb, pred_bb;
+  VEC (basic_block, heap) *dom_bbs;
   edge e;
   edge_iterator ei;
   bool rescan_p;
@@ -3606,6 +3607,7 @@  maybe_tidy_empty_bb (basic_block bb)
   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)
@@ -3619,7 +3621,14 @@  maybe_tidy_empty_bb (basic_block bb)
           if (!(e->flags & EDGE_FALLTHRU))
             {
 	      /* We can not invalidate computed topological order by moving
-	         the edge destination block (E->SUCC) along a fallthru edge.  */
+	         the edge destination block (E->SUCC) along a fallthru edge.
+
+		 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);
               sel_redirect_edge_and_branch (e, succ_bb);
               rescan_p = true;
               break;
@@ -3656,6 +3665,13 @@  maybe_tidy_empty_bb (basic_block bb)
       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);
+    }
+
   return true;
 }
 
@@ -3740,6 +3756,7 @@  tidy_control_flow (basic_block xbb, bool full_tidying)
 
 #ifdef ENABLE_CHECKING
   verify_backedges ();
+  verify_dominators (CDI_DOMINATORS);
 #endif
 
   return changed;
@@ -5075,7 +5092,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));
 }
@@ -5410,12 +5432,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);
@@ -5432,6 +5457,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
@@ -5440,11 +5469,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
@@ -5475,6 +5505,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;
 }
 
@@ -6201,6 +6240,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);