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

[Tom de Vries <Tom_deVries@mentor.com>]

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);
> +}
> +
>   /* 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;
> +}
> +
> +/* 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
>