From patchwork Fri Jul 9 20:17:39 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Maxim Kuvyrkov X-Patchwork-Id: 58431 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 AD846B6EFF for ; Sat, 10 Jul 2010 06:18:10 +1000 (EST) Received: (qmail 13596 invoked by alias); 9 Jul 2010 20:18:05 -0000 Received: (qmail 13551 invoked by uid 22791); 9 Jul 2010 20:18:00 -0000 X-SWARE-Spam-Status: No, hits=0.9 required=5.0 tests=AWL, BAYES_00, KAM_STOCKTIP, TW_CF, TW_DB, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 09 Jul 2010 20:17:45 +0000 Received: (qmail 13729 invoked from network); 9 Jul 2010 20:17:42 -0000 Received: from unknown (HELO ?172.16.1.24?) (maxim@127.0.0.2) by mail.codesourcery.com with ESMTPA; 9 Jul 2010 20:17:42 -0000 Message-ID: <4C3783E3.4030501@codesourcery.com> Date: Sat, 10 Jul 2010 00:17:39 +0400 From: Maxim Kuvyrkov User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.2.4) Gecko/20100608 Thunderbird/3.1 MIME-Version: 1.0 To: Jeff Law CC: Steven Bosscher , gcc-patches Subject: Re: 0005-Search-all-dominated-blocks-for-expressions-to-hoist.patch References: <4C18F225.2040509@codesourcery.com> <4C18F491.2000406@codesourcery.com> <4C1FB369.4080006@redhat.com> <4C1FC91D.401@redhat.com> <4C20AB99.6080807@codesourcery.com> <4C225BA4.9070603@codesourcery.com> <4C237F81.9090807@codesourcery.com> <4C2B8911.9050806@redhat.com> <4C2B9B4D.6020500@codesourcery.com> <4C2CC3F4.2070707@redhat.com> <4C2E0F06.4040402@codesourcery.com> <4C34AE19.6000300@redhat.com> In-Reply-To: <4C34AE19.6000300@redhat.com> 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 On 7/7/10 8:40 PM, Jeff Law wrote: ... > Since there's no edge insertions with hoisting, the only potential > problem I can see is when the hoisted expression itself can trigger > traversal of an abnormal edge and the block we want to put the > expression does not have an edge to the handler. In that case we'd need > to add edges in the cfg and I don't see any compensation code in gcse.c > to deal with that case. I agree. > > Assuming that's the situation we need to avoid then we really need to > switch the pre-like code since it detects expressions which can cause > traversal of the abnormal edge much better. It's a fairly simple patch > since it just prunes some expressions from the local tables before > running the dataflow solver. The first of the attached patches replaces transpout with an additional check in determining if an expression is anticipatable. The second patch implements LCA approach to avoid hoisting expression too far up. As a side effect of implementation, it somewhat simplifies control flow of hoist_code. I really hope this is the last iteration on the one-line change this problem initially was :). Thanks, diff --git a/gcc/gcse.c b/gcc/gcse.c index 4f6dc83..9479304 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -470,7 +470,6 @@ static void mark_oprs_set (rtx); static void alloc_cprop_mem (int, int); static void free_cprop_mem (void); static void compute_transp (const_rtx, int, sbitmap *, int); -static void compute_transpout (void); static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *, struct hash_table_d *); static void compute_cprop_data (void); @@ -1357,6 +1356,27 @@ gcse_constant_p (const_rtx x) return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x)); } +/* Return true if INSN can cause abnormal control flow. */ + +static bool +causes_abnormal_control_flow_p (const_rtx insn) +{ + basic_block bb; + edge e; + edge_iterator ei; + + bb = BLOCK_FOR_INSN (insn); + + if (BB_END (bb) != insn) + return false; + + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->flags & EDGE_ABNORMAL) + return true; + + return false; +} + /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or expression one). */ @@ -1424,11 +1444,13 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) { /* An expression is not anticipatable if its operands are modified before this insn or if this is not the only SET in - this insn. The latter condition does not have to mean that + this insn. The latter conditions do not have to mean that SRC itself is not anticipatable, but we just will not be - able to handle code motion of insns with multiple sets. */ - int antic_p = oprs_anticipatable_p (src, insn) - && !multiple_sets (insn); + able to handle code motion of insns with multiple sets or + abnormal control flow. */ + int antic_p = (oprs_anticipatable_p (src, insn) + && !multiple_sets (insn) + && !causes_abnormal_control_flow_p (insn)); /* An expression is not available if its operands are subsequently modified, including this insn. It's also not available if this is a branch, because we can't insert @@ -3237,11 +3259,6 @@ bypass_conditional_jumps (void) /* Nonzero for expressions that are transparent in the block. */ static sbitmap *transp; -/* Nonzero for expressions that are transparent at the end of the block. - This is only zero for expressions killed by abnormal critical edge - created by a calls. */ -static sbitmap *transpout; - /* Nonzero for expressions that are computed (available) in the block. */ static sbitmap *comp; @@ -4097,52 +4114,6 @@ add_label_notes (rtx x, rtx insn) } } -/* Compute transparent outgoing information for each block. - - An expression is transparent to an edge unless it is killed by - the edge itself. This can only happen with abnormal control flow, - when the edge is traversed through a call. This happens with - non-local labels and exceptions. - - This would not be necessary if we split the edge. While this is - normally impossible for abnormal critical edges, with some effort - it should be possible with exception handling, since we still have - control over which handler should be invoked. But due to increased - EH table sizes, this may not be worthwhile. */ - -static void -compute_transpout (void) -{ - basic_block bb; - unsigned int i; - struct expr *expr; - - sbitmap_vector_ones (transpout, last_basic_block); - - FOR_EACH_BB (bb) - { - /* Note that flow inserted a nop at the end of basic blocks that - end in call instructions for reasons other than abnormal - control flow. */ - if (! CALL_P (BB_END (bb))) - continue; - - for (i = 0; i < expr_hash_table.size; i++) - for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash) - if (MEM_P (expr->expr)) - { - if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF - && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0))) - continue; - - /* ??? Optimally, we would use interprocedural alias - analysis to determine if this mem is actually killed - by this call. */ - RESET_BIT (transpout[bb->index], expr->bitmap_index); - } - } -} - /* Code Hoisting variables and subroutines. */ /* Very busy expressions. */ @@ -4171,7 +4142,6 @@ alloc_code_hoist_mem (int n_blocks, int n_exprs) hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs); hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs); hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs); - transpout = sbitmap_vector_alloc (n_blocks, n_exprs); } /* Free vars used for code hoisting analysis. */ @@ -4186,7 +4156,6 @@ free_code_hoist_mem (void) sbitmap_vector_free (hoist_vbein); sbitmap_vector_free (hoist_vbeout); sbitmap_vector_free (hoist_exprs); - sbitmap_vector_free (transpout); free_dominance_info (CDI_DOMINATORS); } @@ -4246,7 +4215,6 @@ static void compute_code_hoist_data (void) { compute_local_properties (transp, comp, antloc, &expr_hash_table); - compute_transpout (); compute_code_hoist_vbeinout (); calculate_dominance_info (CDI_DOMINATORS); if (dump_file)