From patchwork Thu Jun 25 07:42:22 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: 488308 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 14D161402C3 for ; Thu, 25 Jun 2015 17:42:50 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=rIb4+EDb; 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:content-type; q=dns; s=default; b=vTNNCnBWeo1lrEPo1CUjRyveK9tUTgjPPUCISS28Inj Chcwt532TzRAy6BCwevvRoyszljSbgwsg3hIfJ5kXxMy1GHNmSz5rIUj3M1pCPcu rr66QzeJRhk1o7sQMVNYvNw02vvsniZSlRtz5ZCxL1ucwoZckkZ9eFAgCQv9eHHI = 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:content-type; s=default; bh=jFV4pZ36ZGyBKsUcvACGkkh0RK0=; b=rIb4+EDb7NTqKYQI5 ert3fPcYkfM4dH8Fb/+1BwSoWoICYn3BAGuE//sv3A1IpqdKUSZeJ4F8n+wkPIc9 jueCS+VJt3l2/zCYBy5RvHJJ2zQO/DlP1L+kXXdUlttwYmtsdDBsVQvaFQN0N2BD hjYk44IziDhjzVRvTQY+UdBbVc= Received: (qmail 86575 invoked by alias); 25 Jun 2015 07:42:42 -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 86564 invoked by uid 89); 25 Jun 2015 07:42:40 -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; Thu, 25 Jun 2015 07:42:38 +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 1Z81nu-00024d-DA from Tom_deVries@mentor.com ; Thu, 25 Jun 2015 00:42:34 -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; Thu, 25 Jun 2015 08:42:32 +0100 Message-ID: <558BB0DE.6090700@mentor.com> Date: Thu, 25 Jun 2015 09:42:22 +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: [PATCH, 1/2] Merge rewrite_virtuals_into_loop_closed_ssa from gomp4 branch Hi, this patch merges rewrite_virtuals_into_loop_closed_ssa (originally submitted here: https://gcc.gnu.org/ml/gcc-patches/2015-06/msg01236.html ) to trunk. Bootstrapped and reg-tested on x86_64. OK for trunk? Thanks, - Tom Merge rewrite_virtuals_into_loop_closed_ssa from gomp4 branch 2015-06-24 Tom de Vries merge from gomp4 branch: 2015-06-24 Tom de Vries * tree-ssa-loop-manip.c (get_virtual_phi): Factor out of ... (rewrite_virtuals_into_loop_closed_ssa): ... here. * tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs): Factor out of ... (rewrite_virtuals_into_loop_closed_ssa): ... here. * dominance.c (bitmap_get_dominated_by): New function. * dominance.h (bitmap_get_dominated_by): Declare. * tree-ssa-loop-manip.c (rewrite_virtuals_into_loop_closed_ssa): Use bitmap_get_dominated_by. * tree-parloops.c (replace_uses_in_bbs_by) (rewrite_virtuals_into_loop_closed_ssa): Move to ... * tree-ssa-loop-manip.c: here. * tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa): Declare. 2015-06-18 Tom de Vries * tree-parloops.c (rewrite_virtuals_into_loop_closed_ssa): New function. (transform_to_exit_first_loop_alt): Use rewrite_virtuals_into_loop_closed_ssa. --- gcc/dominance.c | 21 ++++++++++++ gcc/dominance.h | 1 + gcc/tree-parloops.c | 43 +++++-------------------- gcc/tree-ssa-loop-manip.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++ gcc/tree-ssa-loop-manip.h | 1 + 5 files changed, 112 insertions(+), 35 deletions(-) diff --git a/gcc/dominance.c b/gcc/dominance.c index 9c66ca2..9b52d79 100644 --- a/gcc/dominance.c +++ b/gcc/dominance.c @@ -753,6 +753,27 @@ set_immediate_dominator (enum cdi_direction dir, basic_block bb, dom_computed[dir_index] = DOM_NO_FAST_QUERY; } +/* Returns in BBS the list of basic blocks immediately dominated by BB, in the + direction DIR. As get_dominated_by, but returns result as a bitmap. */ + +void +bitmap_get_dominated_by (enum cdi_direction dir, basic_block bb, bitmap bbs) +{ + unsigned int dir_index = dom_convert_dir_to_idx (dir); + struct et_node *node = bb->dom[dir_index], *son = node->son, *ason; + + bitmap_clear (bbs); + + gcc_checking_assert (dom_computed[dir_index]); + + if (!son) + return; + + bitmap_set_bit (bbs, ((basic_block) son->data)->index); + for (ason = son->right; ason != son; ason = ason->right) + bitmap_set_bit (bbs, ((basic_block) son->data)->index); +} + /* Returns the list of basic blocks immediately dominated by BB, in the direction DIR. */ vec diff --git a/gcc/dominance.h b/gcc/dominance.h index 37e138b..0a1a13e 100644 --- a/gcc/dominance.h +++ b/gcc/dominance.h @@ -41,6 +41,7 @@ extern void free_dominance_info (enum cdi_direction); extern basic_block get_immediate_dominator (enum cdi_direction, basic_block); extern void set_immediate_dominator (enum cdi_direction, basic_block, basic_block); +extern void bitmap_get_dominated_by (enum cdi_direction, basic_block, bitmap); extern vec get_dominated_by (enum cdi_direction, basic_block); extern vec get_dominated_by_region (enum cdi_direction, basic_block *, diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c index e582fe7..df7c351 100644 --- a/gcc/tree-parloops.c +++ b/gcc/tree-parloops.c @@ -1498,25 +1498,6 @@ replace_uses_in_bb_by (tree name, tree val, basic_block bb) } } -/* Replace uses of NAME by VAL in blocks BBS. */ - -static void -replace_uses_in_bbs_by (tree name, tree val, bitmap bbs) -{ - gimple use_stmt; - imm_use_iterator imm_iter; - - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name) - { - if (!bitmap_bit_p (bbs, gimple_bb (use_stmt)->index)) - continue; - - use_operand_p use_p; - FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) - SET_USE (use_p, val); - } -} - /* Do transformation from: : @@ -1637,18 +1618,11 @@ transform_to_exit_first_loop_alt (struct loop *loop, tree control = gimple_cond_lhs (cond_stmt); edge e; - /* Gather the bbs dominated by the exit block. */ - bitmap exit_dominated = BITMAP_ALLOC (NULL); - bitmap_set_bit (exit_dominated, exit_block->index); - vec exit_dominated_vec - = get_dominated_by (CDI_DOMINATORS, exit_block); - - int i; - basic_block dom_bb; - FOR_EACH_VEC_ELT (exit_dominated_vec, i, dom_bb) - bitmap_set_bit (exit_dominated, dom_bb->index); - - exit_dominated_vec.release (); + /* Rewriting virtuals into loop-closed ssa normal form makes this + transformation simpler. It also ensures that the virtuals are in + loop-closed ssa normal from after the transformation, which is required by + create_parallel_loop. */ + rewrite_virtuals_into_loop_closed_ssa (loop); /* Create the new_header block. */ basic_block new_header = split_block_before_cond_jump (exit->src); @@ -1681,6 +1655,7 @@ transform_to_exit_first_loop_alt (struct loop *loop, vec *v = redirect_edge_var_map_vector (post_inc_edge); edge_var_map *vm; gphi_iterator gsi; + int i; for (gsi = gsi_start_phis (header), i = 0; !gsi_end_p (gsi) && v->iterate (i, &vm); gsi_next (&gsi), i++) @@ -1698,10 +1673,9 @@ transform_to_exit_first_loop_alt (struct loop *loop, /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */ add_phi_arg (phi, res_c, post_cond_edge, UNKNOWN_LOCATION); - /* Replace sum_b with sum_c in exit phi. Loop-closed ssa does not hold - for virtuals, so we cannot get away with exit_block only. */ + /* Replace sum_b with sum_c in exit phi. */ tree res_b = redirect_edge_var_map_def (vm); - replace_uses_in_bbs_by (res_b, res_c, exit_dominated); + replace_uses_in_bb_by (res_b, res_c, exit_block); struct reduction_info *red = reduction_phi (reduction_list, phi); gcc_assert (virtual_operand_p (res_a) @@ -1716,7 +1690,6 @@ transform_to_exit_first_loop_alt (struct loop *loop, } } gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm)); - BITMAP_FREE (exit_dominated); /* Set the preheader argument of the new phis to ivtmp/sum_init. */ flush_pending_stmts (entry); diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index 29f701c..d8ab013 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -560,6 +560,87 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) free (use_blocks); } +/* Replace uses of NAME by VAL in blocks BBS. */ + +static void +replace_uses_in_bbs_by (tree name, tree val, bitmap bbs) +{ + gimple use_stmt; + imm_use_iterator imm_iter; + + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name) + { + if (!bitmap_bit_p (bbs, gimple_bb (use_stmt)->index)) + continue; + + use_operand_p use_p; + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + SET_USE (use_p, val); + } +} + +/* Replace uses of OLD_VAL with NEW_VAL in bbs dominated by BB. */ + +static void +replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb) +{ + bitmap dominated = BITMAP_ALLOC (NULL); + + bitmap_get_dominated_by (CDI_DOMINATORS, bb, dominated); + bitmap_set_bit (dominated, bb->index); + + replace_uses_in_bbs_by (old_val, new_val, dominated); + + BITMAP_FREE (dominated); +} + +/* Return the virtual phi in BB. */ + +static gphi * +get_virtual_phi (basic_block bb) +{ + for (gphi_iterator gsi = gsi_start_phis (bb); + !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + + if (virtual_operand_p (PHI_RESULT (phi))) + return phi; + } + + return 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. */ + +void +rewrite_virtuals_into_loop_closed_ssa (struct loop *loop) +{ + gphi *phi; + edge exit = single_dom_exit (loop); + + 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); +} + /* Check invariants of the loop closed ssa form for the USE in BB. */ static void diff --git a/gcc/tree-ssa-loop-manip.h b/gcc/tree-ssa-loop-manip.h index ad0c381..9285718 100644 --- a/gcc/tree-ssa-loop-manip.h +++ b/gcc/tree-ssa-loop-manip.h @@ -25,6 +25,7 @@ typedef void (*transform_callback)(struct loop *, void *); extern void create_iv (tree, tree, tree, struct loop *, gimple_stmt_iterator *, bool, tree *, tree *); extern void rewrite_into_loop_closed_ssa (bitmap, unsigned); +extern void rewrite_virtuals_into_loop_closed_ssa (struct loop *); extern void verify_loop_closed_ssa (bool); extern basic_block split_loop_exit_edge (edge); extern basic_block ip_end_pos (struct loop *); -- 1.9.1