From patchwork Sat Jul 17 16:41:22 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Maxim Kuvyrkov X-Patchwork-Id: 59142 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 C56FBB6F04 for ; Sun, 18 Jul 2010 02:41:37 +1000 (EST) Received: (qmail 26129 invoked by alias); 17 Jul 2010 16:41:34 -0000 Received: (qmail 26117 invoked by uid 22791); 17 Jul 2010 16:41:33 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL, BAYES_00, 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; Sat, 17 Jul 2010 16:41:27 +0000 Received: (qmail 14295 invoked from network); 17 Jul 2010 16:41:25 -0000 Received: from unknown (HELO ?172.16.1.24?) (maxim@127.0.0.2) by mail.codesourcery.com with ESMTPA; 17 Jul 2010 16:41:25 -0000 Message-ID: <4C41DD32.60503@codesourcery.com> Date: Sat, 17 Jul 2010 20:41:22 +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> <4C3783E3.4030501@codesourcery.com> <4C3E24E0.3090407@redhat.com> <4C3E2F3D.7020004@codesourcery.com> <4C3F31EA.4080305@redhat.com> <4C3F5FFF.6020409@codesourcery.com> <4C40A6F8.2030701@redhat.com> In-Reply-To: <4C40A6F8.2030701@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/16/10 10:37 PM, Jeff Law wrote: > On 07/15/10 13:22, Maxim Kuvyrkov wrote: >> On 7/15/10 8:06 PM, Jeff Law wrote: >> ... >>> ? See the e->flags & EDGE_ABNORMAL test prior to removing elements of >>> trapping_expr from antloc or transp. >> >> I missed that point that we should avoid emitting anything at the ends >> of basic blocks with abnormal edges. >> >> Is the attached patch OK? > Yes as long as it passes the usual bootstrap & regression test. Well, after the regtest I now know the exact purpose of transpout. It is to avoid moving memory references across calls that can clobber memory. Without the checks done in compute_transpout a memory reference can be moved along an abnormal edge and, when that happens, it gets placed /before/ the call. Similarly, we want to avoid hoisting potentially trapping expressions along abnormal edges as that would allow the trap to happen prematurely. Jeff, I'm sorry this is taking so long; would you please review this incarnation of the patch. Bootstrapped and tested on i686-linux (biarch) and arm-linux. Thanks, diff --git a/gcc/gcse.c b/gcc/gcse.c index e506d47..0d80fb2 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -468,7 +468,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); @@ -3172,11 +3171,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; @@ -3240,33 +3234,59 @@ free_pre_mem (void) pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL; } -/* Top level routine to do the dataflow analysis needed by PRE. */ +/* Remove certain expressions from anticipatable and transparent + sets of basic blocks that have incoming abnormal edge. + For PRE remove potentially trapping expressions to avoid placing + them on abnormal edges. For HOIST remove memory references that + can be clobbered by calls. */ static void -compute_pre_data (void) +prune_expressions (bool pre_p) { - sbitmap trapping_expr; - basic_block bb; + sbitmap prune_exprs; unsigned int ui; + basic_block bb; - compute_local_properties (transp, comp, antloc, &expr_hash_table); - sbitmap_vector_zero (ae_kill, last_basic_block); - - /* Collect expressions which might trap. */ - trapping_expr = sbitmap_alloc (expr_hash_table.n_elems); - sbitmap_zero (trapping_expr); + prune_exprs = sbitmap_alloc (expr_hash_table.n_elems); + sbitmap_zero (prune_exprs); for (ui = 0; ui < expr_hash_table.size; ui++) { struct expr *e; for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash) - if (may_trap_p (e->expr)) - SET_BIT (trapping_expr, e->bitmap_index); - } + { + /* Note potentially trapping expressions. */ + if (may_trap_p (e->expr)) + { + SET_BIT (prune_exprs, e->bitmap_index); + continue; + } - /* Compute ae_kill for each basic block using: + if (!pre_p && MEM_P (e->expr)) + /* Note memory references that can be clobbered by a call. + We do not split abnormal edges in HOIST, so would + a memory reference get hoisted along an abnormal edge, + it would be placed /before/ the call. Therefore, only + constant memory references can be hoisted along abnormal + edges. */ + { + if (GET_CODE (XEXP (e->expr, 0)) == SYMBOL_REF + && CONSTANT_POOL_ADDRESS_P (XEXP (e->expr, 0))) + continue; - ~(TRANSP | COMP) - */ + if (MEM_READONLY_P (e->expr) + && !MEM_VOLATILE_P (e->expr) + && MEM_NOTRAP_P (e->expr)) + /* Constant memory reference, e.g., a PIC address. */ + continue; + + /* ??? Optimally, we would use interprocedural alias + analysis to determine if this mem is actually killed + by this call. */ + + SET_BIT (prune_exprs, e->bitmap_index); + } + } + } FOR_EACH_BB (bb) { @@ -3274,17 +3294,43 @@ compute_pre_data (void) edge_iterator ei; /* If the current block is the destination of an abnormal edge, we - kill all trapping expressions because we won't be able to properly - place the instruction on the edge. So make them neither - anticipatable nor transparent. This is fairly conservative. */ + kill all trapping (for PRE) or memory (for HOIST) expressions + because we won't be able to properly place the instruction on + the edge. So make them neither anticipatable nor transparent. + This is fairly conservative. */ FOR_EACH_EDGE (e, ei, bb->preds) - if (e->flags & EDGE_ABNORMAL) + if ((e->flags & EDGE_ABNORMAL) + && (pre_p || CALL_P (BB_END (e->src)))) { - sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr); - sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr); + sbitmap_difference (antloc[bb->index], + antloc[bb->index], prune_exprs); + sbitmap_difference (transp[bb->index], + transp[bb->index], prune_exprs); break; } + } + + sbitmap_free (prune_exprs); +} + +/* Top level routine to do the dataflow analysis needed by PRE. */ +static void +compute_pre_data (void) +{ + basic_block bb; + + compute_local_properties (transp, comp, antloc, &expr_hash_table); + prune_expressions (true); + sbitmap_vector_zero (ae_kill, last_basic_block); + + /* Compute ae_kill for each basic block using: + + ~(TRANSP | COMP) + */ + + FOR_EACH_BB (bb) + { sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]); sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]); } @@ -3295,7 +3341,6 @@ compute_pre_data (void) antloc = NULL; sbitmap_vector_free (ae_kill); ae_kill = NULL; - sbitmap_free (trapping_expr); } /* PRE utilities */ @@ -4050,52 +4095,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. */ @@ -4124,7 +4123,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. */ @@ -4139,7 +4137,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); } @@ -4192,7 +4189,7 @@ static void compute_code_hoist_data (void) { compute_local_properties (transp, comp, antloc, &expr_hash_table); - compute_transpout (); + prune_expressions (false); compute_code_hoist_vbeinout (); calculate_dominance_info (CDI_DOMINATORS); if (dump_file) @@ -4294,8 +4291,7 @@ hoist_code (void) { int hoistable = 0; - if (TEST_BIT (hoist_vbeout[bb->index], i) - && TEST_BIT (transpout[bb->index], i)) + if (TEST_BIT (hoist_vbeout[bb->index], i)) { /* We've found a potentially hoistable expression, now we look at every block BB dominates to see if it