[PING,1/2] Merge rewrite_virtuals_into_loop_closed_ssa from gomp4 branch

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
>>>
>>
>>
>

[PING,1/2] Merge rewrite_virtuals_into_loop_closed_ssa from gomp4 branch

Commit Message

Comments

Patch