From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 39101 invoked by alias); 6 Jul 2015 13:44:19 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 39090 invoked by uid 89); 6 Jul 2015 13:44:19 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_50,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD autolearn=no version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Mon, 06 Jul 2015 13:44:17 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id B3FEBAAC1; Mon, 6 Jul 2015 13:44:13 +0000 (UTC) Date: Mon, 06 Jul 2015 13:44:00 -0000 From: Richard Biener To: Tom de Vries cc: GCC Patches Subject: Re: [PING][PATCH, 1/2] Merge rewrite_virtuals_into_loop_closed_ssa from gomp4 branch In-Reply-To: <559A5498.8030206@mentor.com> Message-ID: References: <558BB0DE.6090700@mentor.com> <559A5498.8030206@mentor.com> User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2015-07/txt/msg00343.txt.bz2 On Mon, 6 Jul 2015, Tom de Vries wrote: > On 25/06/15 09:42, Tom de Vries wrote: > > 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? > > > > Ping. > > Thanks, > - Tom > > > > 0001-Merge-rewrite_virtuals_into_loop_closed_ssa-from-gom.patch > > > > > > 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); > > +} > > + Isn't a immediate_dominated_by_p () predicate better? It's very cheap to compute compared to allocating / populating and querying a bitmap. > > /* 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; > > +} Please add this to tree-cfg.[ch] instead, there are multiple places in GCC that would benefit from it (I even considered a special ordering constraint on the PHI seq to make this cheap). > > +/* 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. */ This lacks documentation of the constrains on LOOP - namely that it only rewrites a single exit and only if that exit dominates the latch. Apart from documenting it should also assert if you use it on other loops. Otherwise it's quite useless, no? If you can handle one exit edge I also can't see the difficulty in handling all exit edges. > > +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); How can you get away with only updating uses in blocks that are immediately dominated by this one? Consider --exit--> if (foo) { ... } else { .... } -> ... -> if (foo) {...} -> vuse so I belive you have to use a regular dominance check (and get rid of the bitmap anyway, see above). Thanks, Richard. > > + 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 > > > > -- Richard Biener SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)