[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

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
>

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.

> >   /* 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 (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
> > 
> 
>