[committed, gomp4] Rewrite virtuals into lcssa in transform_to_exit_first_loop_alt

[committed, gomp4] Rewrite virtuals into lcssa in transform_to_exit_first_loop_alt

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 769 bytes --]

Hi,

transform_to_exit_first_loop contains the following comment:
...
   /* Make sure that we have phi nodes on exit for all loop header phis
      (create_parallel_loop requires that).  */
...

I ran into a problem where after transform_to_exit_first_loop_alt this 
property does not hold for virtuals, and we run into trouble in 
create_parallel_loop.

The patch ensures that the property holds at the start of 
transform_to_exit_first_loop_alt, which has as effect that:
- we simplify transform_to_exit_first_loop_alt a bit, and
- since the property is kept by transform_to_exit_first_loop_alt,
   the property will be valid after transform_to_exit_first_loop_alt.

Bootstrapped and reg-tested on x86_64.

Committed to gomp-4_0-branch.

OK for trunk?

Thanks,
- Tom

[-- Attachment #2: 0002-Rewrite-virtuals-into-lcssa-in-transform_to_exit_fir.patch --]
[-- Type: text/x-patch, Size: 4737 bytes --]

Rewrite virtuals into lcssa in transform_to_exit_first_loop_alt

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/tree-parloops.c | 92 +++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 76 insertions(+), 16 deletions(-)

diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index 678e458..0661b78 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -1526,6 +1526,74 @@ replace_uses_in_bbs_by (tree name, tree val, bitmap bbs)
     }
 }
 
+/* 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.  */
+
+static void
+rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
+{
+  gphi *phi;
+  edge exit = single_dom_exit (loop);
+
+  phi = NULL;
+  for (gphi_iterator gsi = gsi_start_phis (loop->header);
+       !gsi_end_p (gsi);
+       gsi_next (&gsi))
+    {
+      if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
+	{
+	  phi = gsi.phi ();
+	  break;
+	}
+    }
+
+  if (phi == NULL)
+    return;
+
+  tree final_loop = PHI_ARG_DEF_FROM_EDGE (phi, single_succ_edge (loop->latch));
+
+  phi = NULL;
+  for (gphi_iterator gsi = gsi_start_phis (exit->dest);
+       !gsi_end_p (gsi);
+       gsi_next (&gsi))
+    {
+      if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
+	{
+	  phi = gsi.phi ();
+	  break;
+	}
+    }
+
+  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);
+
+  /* Gather the bbs dominated by the exit block.  */
+  bitmap exit_dominated = BITMAP_ALLOC (NULL);
+  bitmap_set_bit (exit_dominated, exit->dest->index);
+  vec<basic_block> exit_dominated_vec
+    = get_dominated_by (CDI_DOMINATORS, exit->dest);
+
+  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 ();
+
+  replace_uses_in_bbs_by (final_loop, res_new, exit_dominated);
+
+  add_phi_arg (nphi, final_loop, exit, UNKNOWN_LOCATION);
+
+  BITMAP_FREE (exit_dominated);
+}
+
 /* Do transformation from:
 
      <bb preheader>:
@@ -1646,18 +1714,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);
@@ -1690,6 +1751,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++)
@@ -1707,10 +1769,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)
@@ -1725,7 +1786,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);
-- 
1.9.1

Re: [committed, gomp4] Rewrite virtuals into lcssa in transform_to_exit_first_loop_alt

[Richard Biener]

On Thu, Jun 18, 2015 at 9:25 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Hi,
>
> transform_to_exit_first_loop contains the following comment:
> ...
>   /* Make sure that we have phi nodes on exit for all loop header phis
>      (create_parallel_loop requires that).  */
> ...
>
> I ran into a problem where after transform_to_exit_first_loop_alt this
> property does not hold for virtuals, and we run into trouble in
> create_parallel_loop.
>
> The patch ensures that the property holds at the start of
> transform_to_exit_first_loop_alt, which has as effect that:
> - we simplify transform_to_exit_first_loop_alt a bit, and
> - since the property is kept by transform_to_exit_first_loop_alt,
>   the property will be valid after transform_to_exit_first_loop_alt.
>
> Bootstrapped and reg-tested on x86_64.
>
> Committed to gomp-4_0-branch.
>
> OK for trunk?

I once made virtual-operands loop-closed but then somehow I didn't get it
correct (I suppose I ran into the trap of the existing machinery using
update_ssa to update out-of-loop uses) and removed that capability again.

So instead of adding another limited machinery inside tree-parloops
can you instead
make it available from tree-ssa-loop-manip.c, eventually sharing some code?

Other passes would benefit from this as well and it could save some compile-time
as they wouldn't need to rewrite the virtual operands all the time.

Thanks,
Richard.

> Thanks,
> - Tom

Re: [committed, gomp4] Rewrite virtuals into lcssa in transform_to_exit_first_loop_alt

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 2769 bytes --]

On 18/06/15 13:38, Richard Biener wrote:
> On Thu, Jun 18, 2015 at 9:25 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> Hi,
>>
>> transform_to_exit_first_loop contains the following comment:
>> ...
>>    /* Make sure that we have phi nodes on exit for all loop header phis
>>       (create_parallel_loop requires that).  */
>> ...
>>
>> I ran into a problem where after transform_to_exit_first_loop_alt this
>> property does not hold for virtuals, and we run into trouble in
>> create_parallel_loop.
>>
>> The patch ensures that the property holds at the start of
>> transform_to_exit_first_loop_alt, which has as effect that:
>> - we simplify transform_to_exit_first_loop_alt a bit, and
>> - since the property is kept by transform_to_exit_first_loop_alt,
>>    the property will be valid after transform_to_exit_first_loop_alt.
>>
>> Bootstrapped and reg-tested on x86_64.
>>
>> Committed to gomp-4_0-branch.
>>
>> OK for trunk?
>
> I once made virtual-operands loop-closed

AFAICT, r190614, ...

> but then somehow I didn't get it
> correct (I suppose I ran into the trap of the existing machinery using
> update_ssa to update out-of-loop uses) and removed that capability again.
>

... and r195609. I guess not PR56150, but PR56113 is the related PR, see 
comment https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113#c17 ?

AFAICT from that PR, the problem was compilation speed, not a 
correctness problem?

[ confusingly, the rewrite_into_loop_closed_ssa comment still claims to 
update virtuals:
...
    1) Updating it during unrolling/peeling/versioning is trivial, since
       we do not need to care about the uses outside of the loop.
       The same applies to virtual operands which are also rewritten into
       loop closed SSA form.  Note that virtual operands are always live
       until function exit.
...
]

> So instead of adding another limited machinery inside tree-parloops
> can you instead
> make it available from tree-ssa-loop-manip.c, eventually sharing some code?
>
> Other passes would benefit from this as well and it could save some compile-time
> as they wouldn't need to rewrite the virtual operands all the time.
>

Attached untested patch series contains these patches:
1. Move rewrite_virtuals_into_loop_closed_ssa to tree-ssa-loop-manip.c
2. Add bitmap_get_dominated_by
3. Add replace_uses_in_dominated_bbs
4. Add get_virtual_phi

The last three patches split up the implementation of 
rewrite_virtuals_into_loop_closed_ssa in smaller, hopefully reusable bits.

OK for gomp-4_0-branch and trunk if testing succeeds?

I'm not sure what should be the next step. If you can point me to a use 
site in a pass that could benefit from using 
rewrite_virtuals_into_loop_closed_ssa, then I can try to take it from there.

Thanks,
- Tom

[-- Attachment #2: 0001-Move-rewrite_virtuals_into_loop_closed_ssa-to-tree-s.patch --]
[-- Type: text/x-patch, Size: 6235 bytes --]

[PATCH 1/4] Move rewrite_virtuals_into_loop_closed_ssa to tree-ssa-loop-manip.c

2015-06-18  Tom de Vries  <tom@codesourcery.com>

	* 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.
---
 gcc/tree-parloops.c       | 87 -----------------------------------------------
 gcc/tree-ssa-loop-manip.c | 87 +++++++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-ssa-loop-manip.h |  1 +
 3 files changed, 88 insertions(+), 87 deletions(-)

diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index 0661b78..a9d8c2a 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -1507,93 +1507,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);
-    }
-}
-
-/* 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.  */
-
-static void
-rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
-{
-  gphi *phi;
-  edge exit = single_dom_exit (loop);
-
-  phi = NULL;
-  for (gphi_iterator gsi = gsi_start_phis (loop->header);
-       !gsi_end_p (gsi);
-       gsi_next (&gsi))
-    {
-      if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
-	{
-	  phi = gsi.phi ();
-	  break;
-	}
-    }
-
-  if (phi == NULL)
-    return;
-
-  tree final_loop = PHI_ARG_DEF_FROM_EDGE (phi, single_succ_edge (loop->latch));
-
-  phi = NULL;
-  for (gphi_iterator gsi = gsi_start_phis (exit->dest);
-       !gsi_end_p (gsi);
-       gsi_next (&gsi))
-    {
-      if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
-	{
-	  phi = gsi.phi ();
-	  break;
-	}
-    }
-
-  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);
-
-  /* Gather the bbs dominated by the exit block.  */
-  bitmap exit_dominated = BITMAP_ALLOC (NULL);
-  bitmap_set_bit (exit_dominated, exit->dest->index);
-  vec<basic_block> exit_dominated_vec
-    = get_dominated_by (CDI_DOMINATORS, exit->dest);
-
-  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 ();
-
-  replace_uses_in_bbs_by (final_loop, res_new, exit_dominated);
-
-  add_phi_arg (nphi, final_loop, exit, UNKNOWN_LOCATION);
-
-  BITMAP_FREE (exit_dominated);
-}
-
 /* Do transformation from:
 
      <bb preheader>:
diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index 228fac6..1150e6c 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -569,6 +569,93 @@ 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);
+    }
+}
+
+/* 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 = NULL;
+  for (gphi_iterator gsi = gsi_start_phis (loop->header);
+       !gsi_end_p (gsi);
+       gsi_next (&gsi))
+    {
+      if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
+	{
+	  phi = gsi.phi ();
+	  break;
+	}
+    }
+
+  if (phi == NULL)
+    return;
+
+  tree final_loop = PHI_ARG_DEF_FROM_EDGE (phi, single_succ_edge (loop->latch));
+
+  phi = NULL;
+  for (gphi_iterator gsi = gsi_start_phis (exit->dest);
+       !gsi_end_p (gsi);
+       gsi_next (&gsi))
+    {
+      if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
+	{
+	  phi = gsi.phi ();
+	  break;
+	}
+    }
+
+  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);
+
+  /* Gather the bbs dominated by the exit block.  */
+  bitmap exit_dominated = BITMAP_ALLOC (NULL);
+  bitmap_set_bit (exit_dominated, exit->dest->index);
+  vec<basic_block> exit_dominated_vec
+    = get_dominated_by (CDI_DOMINATORS, exit->dest);
+
+  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 ();
+
+  replace_uses_in_bbs_by (final_loop, res_new, exit_dominated);
+
+  add_phi_arg (nphi, final_loop, exit, UNKNOWN_LOCATION);
+
+  BITMAP_FREE (exit_dominated);
+}
+
 /* 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


[-- Attachment #3: 0002-Add-bitmap_get_dominated_by.patch --]
[-- Type: text/x-patch, Size: 2964 bytes --]

[PATCH 2/4] Add bitmap_get_dominated_by

2015-06-18  Tom de Vries  <tom@codesourcery.com>

	* 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.
---
 gcc/dominance.c           | 21 +++++++++++++++++++++
 gcc/dominance.h           |  1 +
 gcc/tree-ssa-loop-manip.c | 10 +---------
 3 files changed, 23 insertions(+), 9 deletions(-)

diff --git a/gcc/dominance.c b/gcc/dominance.c
index 09c8c90..4b35ec4 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -757,6 +757,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-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index 1150e6c..9c558ca 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -638,16 +638,8 @@ rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
 
   /* Gather the bbs dominated by the exit block.  */
   bitmap exit_dominated = BITMAP_ALLOC (NULL);
+  bitmap_get_dominated_by (CDI_DOMINATORS, exit->dest, exit_dominated);
   bitmap_set_bit (exit_dominated, exit->dest->index);
-  vec<basic_block> exit_dominated_vec
-    = get_dominated_by (CDI_DOMINATORS, exit->dest);
-
-  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 ();
 
   replace_uses_in_bbs_by (final_loop, res_new, exit_dominated);
 
-- 
1.9.1


[-- Attachment #4: 0003-Add-replace_uses_in_dominated_bbs.patch --]
[-- Type: text/x-patch, Size: 1890 bytes --]

[PATCH 3/4] Add replace_uses_in_dominated_bbs

2015-06-18  Tom de Vries  <tom@codesourcery.com>

	* tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs): Factor out
	of ...
	(rewrite_virtuals_into_loop_closed_ssa): ... here.
---
 gcc/tree-ssa-loop-manip.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index 9c558ca..0d2c972 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -588,6 +588,21 @@ replace_uses_in_bbs_by (tree name, tree val, bitmap bbs)
     }
 }
 
+/* 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);
+}
+
 /* 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.  */
 
@@ -635,17 +650,8 @@ rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
 
   tree res_new = copy_ssa_name (final_loop, NULL);
   gphi *nphi = create_phi_node (res_new, exit->dest);
-
-  /* Gather the bbs dominated by the exit block.  */
-  bitmap exit_dominated = BITMAP_ALLOC (NULL);
-  bitmap_get_dominated_by (CDI_DOMINATORS, exit->dest, exit_dominated);
-  bitmap_set_bit (exit_dominated, exit->dest->index);
-
-  replace_uses_in_bbs_by (final_loop, res_new, exit_dominated);
-
+  replace_uses_in_dominated_bbs (final_loop, res_new, exit->dest);
   add_phi_arg (nphi, final_loop, exit, UNKNOWN_LOCATION);
-
-  BITMAP_FREE (exit_dominated);
 }
 
 /* Check invariants of the loop closed ssa form for the USE in BB.  */
-- 
1.9.1


[-- Attachment #5: 0004-Add-get_virtual_phi.patch --]
[-- Type: text/x-patch, Size: 2123 bytes --]

[PATCH 4/4] Add get_virtual_phi

2015-06-18  Tom de Vries  <tom@codesourcery.com>

	* tree-ssa-loop-manip.c (get_virtual_phi): Factor out of ...
	(rewrite_virtuals_into_loop_closed_ssa): ... here.
---
 gcc/tree-ssa-loop-manip.c | 39 +++++++++++++++++++--------------------
 1 file changed, 19 insertions(+), 20 deletions(-)

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index 0d2c972..44c14df 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -603,44 +603,43 @@ replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb)
   BITMAP_FREE (dominated);
 }
 
-/* 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.  */
+/* Return the virtual phi in BB.  */
 
-void
-rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
+static gphi *
+get_virtual_phi (basic_block bb)
 {
   gphi *phi;
-  edge exit = single_dom_exit (loop);
 
   phi = NULL;
-  for (gphi_iterator gsi = gsi_start_phis (loop->header);
+  for (gphi_iterator gsi = gsi_start_phis (bb);
        !gsi_end_p (gsi);
        gsi_next (&gsi))
     {
       if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
 	{
-	  phi = gsi.phi ();
-	  break;
+	  return gsi.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 = NULL;
-  for (gphi_iterator gsi = gsi_start_phis (exit->dest);
-       !gsi_end_p (gsi);
-       gsi_next (&gsi))
-    {
-      if (virtual_operand_p (PHI_RESULT (gsi.phi ())))
-	{
-	  phi = gsi.phi ();
-	  break;
-	}
-    }
-
+  phi = get_virtual_phi (exit->dest);
   if (phi != NULL)
     {
       tree final_exit = PHI_ARG_DEF_FROM_EDGE (phi, exit);
-- 
1.9.1