From patchwork Mon Aug 31 10:32:33 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 512427 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47E7E1401CD for ; Mon, 31 Aug 2015 20:33:00 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=p5V8Gv/N; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; q=dns; s=default; b=LDDIdUTrkQGxGHWH7 /742xKYHDM8mGuxgoiC91/wOpW/lMdekNsSR8jD6zz/QeMt4xIaDpEXWr/lTXAZa /vzI1KsZOPmCIQ+vW4zHlwZg0vUjVs2Qya9YIoXcZev4I2rpeWIwCGKtdus5xs5W kayroRAW0ipKEmN014K5Ybft+o= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:cc:subject:references :in-reply-to:content-type; s=default; bh=fTpU0QQg0mbRCSLjhTaDQJQ mYbA=; b=p5V8Gv/NHxf3Exve//jhPqKtc09nGWgmGvP4QnwMUtUjqQ9aKqqCkgl ZWgOBDjyTZPU183Xf/i6NhpqY2QJ+u2+ElEOIb4zEs1/sy5cSR2cv1DwVPm6tn9J vhZ3LqKvjyMAvg3rdXA/DXuwFn9eIO5tbfxCffbhM1UpQDvTBASg= Received: (qmail 122156 invoked by alias); 31 Aug 2015 10:32:53 -0000 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 Received: (qmail 122144 invoked by uid 89); 31 Aug 2015 10:32:52 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.0 required=5.0 tests=AWL, BAYES_50, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: relay1.mentorg.com Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 31 Aug 2015 10:32:50 +0000 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-FEM-01.mgc.mentorg.com) by relay1.mentorg.com with esmtp id 1ZWMOL-0006Dt-Ca from Tom_deVries@mentor.com ; Mon, 31 Aug 2015 03:32:45 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.3.224.2; Mon, 31 Aug 2015 11:32:42 +0100 Message-ID: <55E42D41.9070703@mentor.com> Date: Mon, 31 Aug 2015 12:32:33 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.8.0 MIME-Version: 1.0 To: Richard Biener CC: GCC Patches Subject: Re: [PING][PATCH, 1/2] Merge rewrite_virtuals_into_loop_closed_ssa from gomp4 branch References: <558BB0DE.6090700@mentor.com> <559A5498.8030206@mentor.com> <559BF70D.9050201@mentor.com> <559E53F9.4030805@mentor.com> <55AD1D4C.30404@mentor.com> In-Reply-To: On 23/07/15 15:44, Richard Biener wrote: > On Mon, 20 Jul 2015, Tom de Vries wrote: > >> On 09/07/15 13:04, Richard Biener wrote: >>> On Thu, 9 Jul 2015, Tom de Vries wrote: >>> >>>> On 07/07/15 17:58, Tom de Vries wrote: >>>>>> If you can >>>>>> handle one exit edge I also can't see the difficulty in handling >>>>>> all exit edges. >>>>>> >>>>> >>>>> Agreed, that doesn't look to complicated. I could call >>>>> rewrite_virtuals_into_loop_closed_ssa for all loops in >>>>> rewrite_virtuals_into_loop_closed_ssa, to get non-single_dom_exit loops >>>>> exercising the code, and fix what breaks. >>>> >>>> Hmm, I just realised, it's more complicated than I thought. >>>> >>>> In loops with single_dom_exit, the exit dominates the uses outside the >>>> loop, >>>> so I can replace the uses of the def with the uses of the exit phi result. >>>> >>>> If !single_dom_exit, the exit(s) may not dominate all uses, and I need to >>>> insert non-loop-exit phi nodes to deal with that. >>> >>> Yes. This is why I originally suggested to amend the regular >>> loop-close-SSA rewriting code. >>> >> >> This patch renames rewrite_into_loop_closed_ssa to >> rewrite_into_loop_closed_ssa_1, and adds arguments: >> - a loop argument, to limit the defs for which the uses are >> rewritten >> - a use_flags argument, to determine the type of uses rewritten: >> SSA_OP_USE/SSA_OP_VIRTUAL_USES/SSA_OP_ALL_USES >> >> The original rewrite_into_loop_closed_ssa is reimplemented using >> rewrite_into_loop_closed_ssa_1. >> >> And the !single_dom_exit case of rewrite_into_loop_closed_ssa is implemented >> using rewrite_into_loop_closed_ssa_1. [ The patch was tested as attached, >> always using rewrite_into_loop_closed_ssa_1, otherwise it would not be >> triggered. ] >> >> Bootstrapped and reg-tested on x86_64. >> >> Is this sort of what you had in mind? > > Yes. New functions need a comment Done. > and instead of iterating over > all function BBs and checking bb->loop_father please use > get_loop_body (). > Done. > Of course in the final version #if 0 stuff shouldn't remain. Done. > What's > the cost difference of removing the single_dom_exit special-case? > I'm not sure. But, in order to avoid having unexercised code, I removed the single_dom_exit special-case in this patch. I think the code is not called often enough to have an impact in speed. And if we want the single_dom_exit special case, we should probably add it generically, rather than having it just for virtuals as it is done now. Bootstrapped and reg-tested on x86_64. OK for trunk? Thanks, - Tom Reimplement rewrite_virtuals_into_loop_closed_ssa 2015-08-31 Tom de Vries * tree-ssa-loop-manip.c (find_uses_to_rename_stmt) (find_uses_to_rename_bb, find_uses_to_rename): Add and handle use_flags parameter. (find_uses_to_rename_def, find_uses_to_rename_in_loop): New function. (rewrite_into_loop_closed_ssa_1): New function, factored out of ... (rewrite_into_loop_closed_ssa): ... here. (replace_uses_in_dominated_bbs): Remove function. (rewrite_virtuals_into_loop_closed_ssa): Reimplement using rewrite_into_loop_closed_ssa_1. --- gcc/tree-ssa-loop-manip.c | 226 ++++++++++++++++++++++++++++++++-------------- 1 file changed, 160 insertions(+), 66 deletions(-) diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index 5c13d4b..fb7ba48 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -403,12 +403,13 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, bitmap_set_bit (use_blocks[ver], bb->index); } -/* For uses in STMT, mark names that are used outside of the loop they are - defined to rewrite. Record the set of blocks in which the ssa names are used - to USE_BLOCKS and the ssa names themselves to NEED_PHIS. */ +/* For uses matching USE_FLAGS in STMT, mark names that are used outside of the + loop they are defined to rewrite. Record the set of blocks in which the ssa + names are used to USE_BLOCKS, and the ssa names themselves to NEED_PHIS. */ static void -find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis) +find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis, + int use_flags) { ssa_op_iter iter; tree var; @@ -417,42 +418,59 @@ find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis) if (is_gimple_debug (stmt)) return; - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) - find_uses_to_rename_use (bb, var, use_blocks, need_phis); + /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows SSA_OP_VIRTUAL_USES + only. */ + if (use_flags == SSA_OP_VIRTUAL_USES) + { + tree vuse = gimple_vuse (stmt); + if (vuse != NULL_TREE) + find_uses_to_rename_use (bb, gimple_vuse (stmt), use_blocks, need_phis); + } + else + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, use_flags) + find_uses_to_rename_use (bb, var, use_blocks, need_phis); } -/* Marks names that are used in BB and outside of the loop they are defined in - for rewrite. Records the set of blocks in which the ssa names are used to - USE_BLOCKS. Record the SSA names that will need exit PHIs in NEED_PHIS. */ +/* Marks names matching USE_FLAGS that are used in BB and outside of the loop + they are defined in for rewrite. Records the set of blocks in which the ssa + names are used to USE_BLOCKS. Record the SSA names that will + need exit PHIs in NEED_PHIS. */ static void -find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) +find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis, + int use_flags) { edge e; edge_iterator ei; + bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0; + bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0; FOR_EACH_EDGE (e, ei, bb->succs) for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) { gphi *phi = bsi.phi (); - if (! virtual_operand_p (gimple_phi_result (phi))) + bool virtual_p = virtual_operand_p (gimple_phi_result (phi)); + if ((virtual_p && do_virtuals) + || (!virtual_p && do_nonvirtuals)) find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), use_blocks, need_phis); } for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis); + find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis, + use_flags); } -/* Marks names that are used outside of the loop they are defined in for - rewrite. Records the set of blocks in which the ssa names are used to - USE_BLOCKS. Record the SSA names that will need exit PHIs in NEED_PHIS. If - CHANGED_BBS is not NULL, scan only blocks in this set. */ +/* Marks names matching USE_FLAGS that are used outside of the loop they are + defined in for rewrite. Records the set of blocks in which the ssa names are + used to USE_BLOCKS. Record the SSA names that will need exit PHIs in + NEED_PHIS. If CHANGED_BBS is not NULL, scan only blocks in this set. */ static void -find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) +find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis, + int use_flags) { basic_block bb; unsigned index; @@ -460,10 +478,96 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) if (changed_bbs) EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) - find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks, need_phis); + find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks, + need_phis, use_flags); else FOR_EACH_BB_FN (bb, cfun) - find_uses_to_rename_bb (bb, use_blocks, need_phis); + find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags); +} + +/* Mark uses of DEF that are used outside of the loop they are defined in for + rewrite. Record the set of blocks in which the ssa names are used to + USE_BLOCKS. Record the SSA names that will need exit PHIs in NEED_PHIS. */ + +static void +find_uses_to_rename_def (tree def, bitmap *use_blocks, bitmap need_phis) +{ + gimple use_stmt; + imm_use_iterator imm_iter; + + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) + { + basic_block use_bb = gimple_bb (use_stmt); + + use_operand_p use_p; + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + { + if (gimple_code (use_stmt) == GIMPLE_PHI) + { + edge e = gimple_phi_arg_edge (as_a (use_stmt), + PHI_ARG_INDEX_FROM_USE (use_p)); + use_bb = e->src; + } + find_uses_to_rename_use (use_bb, USE_FROM_PTR (use_p), use_blocks, + need_phis); + } + } +} + +/* Marks names matching USE_FLAGS that are defined in LOOP and used outside of + it for rewrite. Records the set of blocks in which the ssa names are used to + USE_BLOCKS. Record the SSA names that will need exit PHIs in NEED_PHIS. */ + +static void +find_uses_to_rename_in_loop (struct loop *loop, bitmap *use_blocks, + bitmap need_phis, int use_flags) +{ + bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0; + bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0; + int def_flags = ((do_virtuals ? SSA_OP_VIRTUAL_DEFS : 0) + | (do_nonvirtuals ? SSA_OP_DEF : 0)); + + + basic_block *bbs = get_loop_body (loop); + + for (unsigned int i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + + for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); + gsi_next (&bsi)) + { + gphi *phi = bsi.phi (); + tree res = gimple_phi_result (phi); + bool virtual_p = virtual_operand_p (res); + if ((virtual_p && do_virtuals) + || (!virtual_p && do_nonvirtuals)) + find_uses_to_rename_def (res, use_blocks, need_phis); + } + + for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); + gsi_next (&bsi)) + { + gimple stmt = gsi_stmt (bsi); + /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows + SSA_OP_VIRTUAL_DEFS only. */ + if (def_flags == SSA_OP_VIRTUAL_DEFS) + { + tree vdef = gimple_vdef (stmt); + if (vdef != NULL) + find_uses_to_rename_def (vdef, use_blocks, need_phis); + } + else + { + tree var; + ssa_op_iter iter; + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, def_flags) + find_uses_to_rename_def (var, use_blocks, need_phis); + } + } + } + + XDELETEVEC (bbs); } /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra @@ -495,14 +599,19 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) is not well-behaved, while the second one is an induction variable with base 99 and step 1. - If CHANGED_BBS is not NULL, we look for uses outside loops only in - the basic blocks in this set. + If LOOP is non-null, only rewrite uses that have defs in LOOP. Otherwise, + if CHANGED_BBS is not NULL, we look for uses outside loops only in the + basic blocks in this set. + + USE_FLAGS allows us to specify whether we want virtual, non-virtual or + both variables rewritten. UPDATE_FLAG is used in the call to update_ssa. See TODO_update_ssa* for documentation. */ void -rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) +rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag, + int use_flags, struct loop *loop) { bitmap *use_blocks; bitmap names_to_rename; @@ -513,7 +622,14 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) /* If the pass has caused the SSA form to be out-of-date, update it now. */ - update_ssa (update_flag); + if (update_flag == 0) + { +#ifdef ENABLE_CHECKING + verify_ssa (true, true); +#endif + } + else + update_ssa (update_flag); bitmap_obstack_initialize (&loop_renamer_obstack); @@ -524,8 +640,17 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) in NAMES_TO_RENAME. */ use_blocks = XNEWVEC (bitmap, num_ssa_names); - /* Find the uses outside loops. */ - find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); + if (loop != NULL) + { + gcc_assert (changed_bbs == NULL); + find_uses_to_rename_in_loop (loop, use_blocks, names_to_rename, + use_flags); + } + else + { + gcc_assert (loop == NULL); + find_uses_to_rename (changed_bbs, use_blocks, names_to_rename, use_flags); + } if (!bitmap_empty_p (names_to_rename)) { @@ -549,55 +674,24 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) free (use_blocks); } -/* Replace uses of OLD_VAL with NEW_VAL in bbs dominated by BB. */ +/* Rewrites the non-virtual defs and uses into a loop closed ssa form. If + CHANGED_BBS is not NULL, we look for uses outside loops only in the basic + blocks in this set. UPDATE_FLAG is used in the call to update_ssa. See + TODO_update_ssa* for documentation. */ -static void -replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb) +void +rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) { - gimple use_stmt; - imm_use_iterator imm_iter; - - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_val) - { - if (!dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb)) - continue; - - use_operand_p use_p; - FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) - SET_USE (use_p, new_val); - } + rewrite_into_loop_closed_ssa_1 (changed_bbs, update_flag, SSA_OP_USE, NULL); } -/* Ensure a virtual phi is present in the exit block, if LOOP contains a vdef. - In other words, ensure loop-closed ssa normal form for virtuals. Handles - only loops with a single exit that dominates the latch. */ +/* Rewrites virtual defs and uses with def in LOOP into loop closed ssa + form. */ void rewrite_virtuals_into_loop_closed_ssa (struct loop *loop) { - gphi *phi; - /* TODO: Handle !single_dom_exit loops. */ - edge exit = single_dom_exit (loop); - gcc_assert (exit != NULL); - - phi = get_virtual_phi (loop->header); - if (phi == NULL) - return; - - tree final_loop = PHI_ARG_DEF_FROM_EDGE (phi, single_succ_edge (loop->latch)); - - phi = get_virtual_phi (exit->dest); - if (phi != NULL) - { - tree final_exit = PHI_ARG_DEF_FROM_EDGE (phi, exit); - gcc_assert (operand_equal_p (final_loop, final_exit, 0)); - return; - } - - tree res_new = copy_ssa_name (final_loop, NULL); - gphi *nphi = create_phi_node (res_new, exit->dest); - replace_uses_in_dominated_bbs (final_loop, res_new, exit->dest); - add_phi_arg (nphi, final_loop, exit, UNKNOWN_LOCATION); + rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_VIRTUAL_USES, loop); } /* Check invariants of the loop closed ssa form for the USE in BB. */ -- 1.9.1