From patchwork Mon Jul 20 16:09:48 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: 497781 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 CAB19140778 for ; Tue, 21 Jul 2015 02:10:13 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=PfZ1tBck; 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=IuEiOeb9m9i4ODpRh i2Jy7+gK0OwOv+upysfYpHQmvl9kXJwoRzMR3mo0a6QlMLne63Ls3NKJfd1QlHxj cXyp9YT2H5tiU4YdyjyVXuxJCDg0rfE7bmHxV4waxy8gVEy/LEcMWS7fWDyLv6ss 37lGUtQWMcY8NiQh3PQAKtSK58= 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=9K951DaT4+MliyBUhz0KRLI xiu8=; b=PfZ1tBckRxYkYM2ImgT4r2MXKvnoJgyYk7UEklo79sjNY/rvkSl7JM9 qoBpK/8dhlIY/RfflmY1pjcDBunaYdVrEPoK6PMSDDtCk5b+YMg+dnlW0purP8mJ bn9s5G/PMECTdmixPLKCtyA0pfRkHPjigdjVZUmk8fuyHB0b3MwM= Received: (qmail 9208 invoked by alias); 20 Jul 2015 16:10:05 -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 9198 invoked by uid 89); 20 Jul 2015 16:10:04 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL, BAYES_00, 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, 20 Jul 2015 16:10:02 +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 1ZHDde-0003ZI-5p from Tom_deVries@mentor.com ; Mon, 20 Jul 2015 09:09:58 -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, 20 Jul 2015 17:09:56 +0100 Message-ID: <55AD1D4C.30404@mentor.com> Date: Mon, 20 Jul 2015 18:09:48 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.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> In-Reply-To: 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? Thanks, - Tom Implement rewrite_virtuals_into_loop_closed_ssa for !single_dom_exit --- gcc/tree-ssa-loop-manip.c | 146 ++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 129 insertions(+), 17 deletions(-) diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index cb762df..2b085df 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -407,7 +407,8 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, 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; @@ -416,8 +417,16 @@ 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); + /* 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 @@ -426,24 +435,30 @@ find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis) 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 @@ -452,7 +467,8 @@ find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) 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 +476,76 @@ 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); +} + +static void +find_uses_to_rename_def (basic_block def_bb, 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) + { + use_operand_p use_p; + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + find_uses_to_rename_use (def_bb, USE_FROM_PTR (use_p), use_blocks, + need_phis); + } +} + +static void +find_uses_to_rename_in_loop (struct loop *loop, bitmap *use_blocks, + bitmap need_phis, int use_flags) +{ + basic_block bb; + + 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)); + + + FOR_EACH_BB_FN (bb, cfun) + { + if (bb->loop_father != loop) + continue; + + 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 (bb, 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); + /* 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 (bb, 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 (bb, var, use_blocks, need_phis); + } + } + } } /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra @@ -502,7 +584,8 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) 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 +596,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 +614,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,6 +648,12 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) free (use_blocks); } +void +rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) +{ + rewrite_into_loop_closed_ssa_1 (changed_bbs, update_flag, SSA_OP_USE, NULL); +} + /* Replace uses of OLD_VAL with NEW_VAL in bbs dominated by BB. */ static void @@ -569,16 +674,23 @@ replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb) } /* 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. */ + In other words, ensure loop-closed ssa normal form for virtuals. */ 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); + +#if 0 + if (exit == NULL) +#else + if (true || exit == NULL) +#endif + { + rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_VIRTUAL_USES, loop); + return; + } phi = get_virtual_phi (loop->header); if (phi == NULL) -- 1.9.1