From patchwork Mon May 30 12:26:46 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 97910 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 69E40B6F72 for ; Mon, 30 May 2011 22:30:25 +1000 (EST) Received: (qmail 23362 invoked by alias); 30 May 2011 12:30:23 -0000 Received: (qmail 23343 invoked by uid 22791); 30 May 2011 12:30:21 -0000 X-SWARE-Spam-Status: No, hits=-5.7 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_TM, T_RP_MATCHES_RCVD, T_TVD_MIME_NO_HEADERS X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 30 May 2011 12:30:03 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p4UCU3wJ005948 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 30 May 2011 08:30:03 -0400 Received: from freie.oliva.athome.lsd.ic.unicamp.br (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id p4UCTs6H003092 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 30 May 2011 08:30:02 -0400 Received: from livre.localdomain (livre-to-gw.oliva.athome.lsd.ic.unicamp.br [172.31.160.19]) by freie.oliva.athome.lsd.ic.unicamp.br (8.14.4/8.14.4) with ESMTP id p4UCTr6O014397 for ; Mon, 30 May 2011 09:29:53 -0300 Received: from livre.localdomain (aoliva@localhost.localdomain [127.0.0.1]) by livre.localdomain (8.14.3/8.14.3/Debian-5+lenny1) with ESMTP id p4UCQmAQ029015; Mon, 30 May 2011 09:26:48 -0300 Received: (from aoliva@localhost) by livre.localdomain (8.14.3/8.14.3/Submit) id p4UCQlDh029013; Mon, 30 May 2011 09:26:47 -0300 From: Alexandre Oliva To: gcc-patches@gcc.gnu.org Subject: Re: [PR48866] three alternative fixes References: Date: Mon, 30 May 2011 09:26:46 -0300 In-Reply-To: (Alexandre Oliva's message of "Mon, 30 May 2011 08:17:48 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) MIME-Version: 1.0 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 May 30, 2011, Alexandre Oliva wrote: > 3. expand dominators before dominated blocks, so that DEFs of > replaceable SSA names are expanded before their uses. Expand them when > they're encountered, but not requiring a REG as a result. Save the RTL > expression that results from the expansion for use in debug insns and at > the non-debug use. This patch addresses some of the problems in 2, avoiding expanding code out of order within a block, and (hopefully) ensuring that, expanding dominators before dominatedblocks, DEFs are expanded before USEs. There is a theoretical possibility that a USE may be expanded before a DEF, depending on internal details of out-of-ssa, but should this ever happen, we'll get a failed assertion, and then disabling TER will work around the problem. Since no special handling of force_reg is required and we don't reorder code, we don't need placeholders, and can record only the value expansion of replaceable DEFs for their uses, debug or not. Nevertheless, we expand each BB into a separate sequence, and then re-emit the blocks into a single sequence in the original order. This is a bit risky, as the logic of block expansion is modified, more so because the blocks created during expansion don't get separate sequences and require special handling, and other (unreachable?) blocks need to be expanded in a separate loop. This is the sort of code we get with this patch: ;; x_ = ****y_; (actually a sequence of replaceable gimple assignments) (set (reg) (mem (reg y_))) (set (reg) (mem (reg...))) (set (reg) (mem (reg...))) ;; debug x => x_ (debug_insn (var_location x (mem (reg)))) [...] ;; ? = x_ + 1; (set (reg x_) (mem (reg...))) (set (reg ?) (plus (reg x_) (const_int 1))) Note that the debug_insn binds to a computed expression, although that same expression is later stored in a register. This is slightly undesirable from a debug information POV, but it's probably something we can live with. No regressions in a regstrap on x86_64-linux-gnu and i686-linux-gnu. for gcc/ChangeLog from Alexandre Oliva PR debug/48866 * cfgexpand.c (def_expansions): New. (def_expansion_recent_tree, def_expansion_recent_rtx): New. (def_expansions_init, def_expansions_fini): New. (def_has_expansion_ptr, def_get_expansion_ptr): New. (expand_debug_expr): Use recorded expansion if available. (expand_gimple_basic_block): Prepare to record expansion of replaceable defs. Change return type to void. (gimple_expand_cfg): Initialize and finalize expansions cache. Expand dominator blocks before dominated. * expr.c (expand_expr_real_1): Use recorded expansion of replaceable defs. * expr.h (def_has_expansion_ptr): Declare. Index: gcc/cfgexpand.c =================================================================== --- gcc/cfgexpand.c.orig 2011-05-28 07:11:12.132275336 -0300 +++ gcc/cfgexpand.c 2011-05-28 07:19:55.128377121 -0300 @@ -2337,6 +2337,55 @@ convert_debug_memory_address (enum machi return x; } +/* Map replaceable SSA_NAMEs to their RTL expansions. */ +static struct pointer_map_t *def_expansions; + +/* Initialize the def_expansions data structure. This is to be called + before expansion of a function starts. */ + +static void +def_expansions_init (void) +{ + gcc_checking_assert (!def_expansions); + def_expansions = pointer_map_create (); +} + +/* Finalize the def_expansions data structure. This is to be called + at the end of the expansion of a function. */ + +static void +def_expansions_fini (void) +{ + gcc_checking_assert (def_expansions); + pointer_map_destroy (def_expansions); + def_expansions = NULL; +} + +/* Return NULL if no expansion is registered for EXP, or a pointer to + the rtx expanded from it otherwise. EXP must be a replaceable + SSA_NAME. */ + +void *const * +def_has_expansion_ptr (tree exp) +{ + gcc_checking_assert (def_expansions); + gcc_checking_assert (TREE_CODE (exp) == SSA_NAME); + gcc_checking_assert (bitmap_bit_p (SA.values, SSA_NAME_VERSION (exp))); + return pointer_map_contains (def_expansions, exp); +} + +/* Return a pointer to the rtx expanded from EXP. EXP must be a + replaceable SSA_NAME. */ + +static void ** +def_get_expansion_ptr (tree exp) +{ + gcc_checking_assert (def_expansions); + gcc_checking_assert (TREE_CODE (exp) == SSA_NAME); + gcc_checking_assert (bitmap_bit_p (SA.values, SSA_NAME_VERSION (exp))); + return pointer_map_insert (def_expansions, exp); +} + /* Return an RTX equivalent to the value of the tree expression EXP. */ @@ -3131,7 +3180,16 @@ expand_debug_expr (tree exp) gimple g = get_gimple_for_ssa_name (exp); if (g) { - op0 = expand_debug_expr (gimple_assign_rhs_to_tree (g)); + void *const *xp = def_has_expansion_ptr (exp); + + if (xp) + op0 = (rtx) *xp; + else + op0 = NULL; + + if (!op0) + op0 = expand_debug_expr (gimple_assign_rhs_to_tree (g)); + if (!op0) return NULL; } @@ -3346,7 +3404,7 @@ expand_debug_locations (void) /* Expand basic block BB from GIMPLE trees to RTL. */ -static basic_block +static void expand_gimple_basic_block (basic_block bb) { gimple_stmt_iterator gsi; @@ -3539,7 +3597,7 @@ expand_gimple_basic_block (basic_block b { new_bb = expand_gimple_cond (bb, stmt); if (new_bb) - return new_bb; + return; } else if (gimple_debug_bind_p (stmt)) { @@ -3613,25 +3671,43 @@ expand_gimple_basic_block (basic_block b if (can_fallthru) bb = new_bb; else - return new_bb; + return; } } else { + void **xp = NULL; def_operand_p def_p; def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); - if (def_p != NULL) + /* Ignore this stmt if it is in the list of + replaceable expressions. */ + if (def_p != NULL + && SA.values + && bitmap_bit_p (SA.values, + SSA_NAME_VERSION (DEF_FROM_PTR (def_p)))) { - /* Ignore this stmt if it is in the list of - replaceable expressions. */ - if (SA.values - && bitmap_bit_p (SA.values, - SSA_NAME_VERSION (DEF_FROM_PTR (def_p)))) - continue; + tree def = DEF_FROM_PTR (def_p); + gimple g = get_gimple_for_ssa_name (def); + rtx retval; + + last = get_last_insn (); + + retval = expand_expr (gimple_assign_rhs_to_tree (g), + NULL_RTX, VOIDmode, EXPAND_SUM); + + xp = def_get_expansion_ptr (def); + gcc_checking_assert (!*xp); + *xp = retval; } - last = expand_gimple_stmt (stmt); + else + last = expand_gimple_stmt (stmt); maybe_dump_rtl_for_gimple_stmt (stmt, last); + if (xp && dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\n=> "); + print_rtl (dump_file, (rtx) *xp); + } } } } @@ -3680,10 +3756,9 @@ expand_gimple_basic_block (basic_block b update_bb_for_insn (bb); - return bb; + return; } - /* Create a basic block for initialization code. */ static basic_block @@ -3969,6 +4044,9 @@ gimple_expand_cfg (void) edge e; rtx var_seq; unsigned i; + VEC (basic_block, heap) *h; + int nblocks; + timevar_push (TV_OUT_OF_SSA); rewrite_out_of_ssa (&SA); @@ -4112,11 +4190,41 @@ gimple_expand_cfg (void) e->flags &= ~EDGE_EXECUTABLE; lab_rtx_for_bb = pointer_map_create (); + def_expansions_init (); + + /* Expand dominators before dominated blocks, so that replaceable + DEFs are always expanded before their uses. */ + nblocks = last_basic_block; + blocks = sbitmap_alloc (nblocks); + sbitmap_zero (blocks); + + h = get_all_dominated_blocks (CDI_DOMINATORS, init_block->next_bb); + + FOR_EACH_VEC_ELT (basic_block, h, i, bb) + { + gcc_checking_assert (bb->index < nblocks); + SET_BIT (blocks, bb->index); + + start_sequence (); + emit_note (NOTE_INSN_DELETED); + expand_gimple_basic_block (bb); + end_sequence (); + } + + VEC_free (basic_block, heap, h); + FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb) - bb = expand_gimple_basic_block (bb); + if (bb->index >= nblocks) + continue; + else if (TEST_BIT (blocks, bb->index)) + emit_insn (BB_HEAD (bb)); + else + expand_gimple_basic_block (bb); + sbitmap_free (blocks); if (MAY_HAVE_DEBUG_INSNS) expand_debug_locations (); + def_expansions_fini (); execute_free_datastructures (); timevar_push (TV_OUT_OF_SSA); Index: gcc/expr.c =================================================================== --- gcc/expr.c.orig 2011-05-28 07:11:12.139275310 -0300 +++ gcc/expr.c 2011-05-28 07:11:14.895265175 -0300 @@ -8424,10 +8424,21 @@ expand_expr_real_1 (tree exp, rtx target && !SSA_NAME_IS_DEFAULT_DEF (exp) && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp))) && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp))) - g = SSA_NAME_DEF_STMT (exp); + { + g = SSA_NAME_DEF_STMT (exp); + if (g) + return expand_expr_real (gimple_assign_rhs_to_tree (g), + target, tmode, modifier, NULL); + } if (g) - return expand_expr_real (gimple_assign_rhs_to_tree (g), target, tmode, - modifier, NULL); + { + void *const *xp = def_has_expansion_ptr (exp); + rtx retval = (rtx) *xp; + + gcc_assert (retval); + + return retval; + } ssa_name = exp; decl_rtl = get_rtx_for_ssa_name (ssa_name); Index: gcc/expr.h =================================================================== --- gcc/expr.h.orig 2011-05-28 07:11:12.147275281 -0300 +++ gcc/expr.h 2011-05-28 07:16:13.428175792 -0300 @@ -693,4 +693,7 @@ extern tree build_libfunc_function (cons /* Get the personality libfunc for a function decl. */ rtx get_personality_function (tree); +/* In cfgexpand.c. */ +void *const *def_has_expansion_ptr (tree); + #endif /* GCC_EXPR_H */