[PING][PATCH, 1/2] Merge rewrite_virtuals_into_loop_closed_ssa from gomp4 branch
Tom de Vries
Tom_deVries@mentor.com
Tue Jul 7 15:58:00 GMT 2015
On 06/07/15 15:44, Richard Biener wrote:
> 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<tom@codesourcery.com>
>>>
>>> merge from gomp4 branch:
>>> 2015-06-24 Tom de Vries<tom@codesourcery.com>
>>>
>>> * 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<tom@codesourcery.com>
>>>
>>> * 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.
>
Dropped bitmap_get_dominated_by per comment below.
>>> /* Returns the list of basic blocks immediately dominated by BB, in the
>>> direction DIR. */
>>> vec<basic_block>
>>> 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<basic_block> get_dominated_by (enum cdi_direction,
>>> basic_block);
>>> extern vec<basic_block> 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:
>>>
>>> <bb preheader>:
>>> @@ -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<basic_block> 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<edge_var_map> *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
Done.
A lot of calls to mark_virtual_phi_result_for_renaming look like they
could be rewritten using get_virtual_phi.
> (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?
Indeed. Documented constraint and added assert.
> 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.
>>> +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).
>
Hmm, you're right. It's confusing that get_dominated_by returns only
immediate dominated rather than all dominated, a better name could be:
- get_immediate_dominated_by, or
- get_imm_dominated_by, or
- get_idominated_by.
Updated patch to use regular dominance check.
Bootstrapped reg-tested on x86_64.
Committed to trunk as attached.
Thanks,
- Tom
> 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
>>>
>>
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Add-rewrite_virtuals_into_loop_closed_ssa.patch
Type: text/x-patch
Size: 7437 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150707/c3849074/attachment.bin>
More information about the Gcc-patches
mailing list