From patchwork Tue Dec 7 15:30:49 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrey Belevantsev X-Patchwork-Id: 74557 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 2048BB70AA for ; Wed, 8 Dec 2010 02:31:19 +1100 (EST) Received: (qmail 2133 invoked by alias); 7 Dec 2010 15:31:03 -0000 Received: (qmail 2089 invoked by uid 22791); 7 Dec 2010 15:30:58 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, FSL_RU_URL, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp.ispras.ru (HELO smtp.ispras.ru) (83.149.198.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 07 Dec 2010 15:30:51 +0000 Received: from [10.10.3.52] (unknown [83.149.198.236]) by smtp.ispras.ru (Postfix) with ESMTP id E9FB05D40ED; Tue, 7 Dec 2010 18:25:19 +0300 (MSK) Message-ID: <4CFE5329.1010100@ispras.ru> Date: Tue, 07 Dec 2010 18:30:49 +0300 From: Andrey Belevantsev User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.12) Gecko/20101027 Thunderbird/3.1.6 MIME-Version: 1.0 To: GCC Patches CC: "Vladimir N. Makarov" Subject: [PATCH] [PING] PR 43603: Keep dominance info up to date References: <4CA9F3DB.40700@ispras.ru> <4CA9F69F.6040407@ispras.ru> <4CC1427E.7040005@ispras.ru> <4CD9858C.8060800@ispras.ru> In-Reply-To: <4CD9858C.8060800@ispras.ru> X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 >>> >>> 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 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. 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);