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

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

[Tom de Vries]

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

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

[-- Attachment #2: 0001-Merge-rewrite_virtuals_into_loop_closed_ssa-from-gom.patch --]
[-- Type: text/x-patch, Size: 9066 bytes --]

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

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

[Tom de Vries]

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
>

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

[Richard Biener]

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

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)

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

[Tom de Vries]

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

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


[-- Attachment #2: 0001-Add-rewrite_virtuals_into_loop_closed_ssa.patch --]
[-- Type: text/x-patch, Size: 7437 bytes --]

Add rewrite_virtuals_into_loop_closed_ssa

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

	* tree-cfg.c (get_virtual_phi): New function.
	* tree-cfg.h (get_virtual_phi): Declare.
	* tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs)
	(rewrite_virtuals_into_loop_closed_ssa): New function.
	* tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa):
	Declare.
	* tree-parloops.c (replace_uses_in_bbs_by): Remove.
	(transform_to_exit_first_loop_alt): Use
	rewrite_virtuals_into_loop_closed_ssa.
---
 gcc/tree-cfg.c            | 17 ++++++++++++++++
 gcc/tree-cfg.h            |  1 +
 gcc/tree-parloops.c       | 43 ++++++++-------------------------------
 gcc/tree-ssa-loop-manip.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-ssa-loop-manip.h |  1 +
 5 files changed, 78 insertions(+), 35 deletions(-)

diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 94ed957..3ab3ab4 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -2623,6 +2623,23 @@ delete_tree_cfg_annotations (void)
   vec_free (label_to_block_map_for_fn (cfun));
 }
 
+/* Return the virtual phi in BB.  */
+
+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;
+}
 
 /* Return the first statement in basic block BB.  */
 
diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
index 2fc1e88..af58c80 100644
--- a/gcc/tree-cfg.h
+++ b/gcc/tree-cfg.h
@@ -59,6 +59,7 @@ extern bool simple_goto_p (gimple);
 extern bool stmt_ends_bb_p (gimple);
 extern bool assert_unreachable_fallthru_edge_p (edge);
 extern void delete_tree_cfg_annotations (void);
+extern gphi *get_virtual_phi (basic_block);
 extern gimple first_stmt (basic_block);
 extern gimple last_stmt (basic_block);
 extern gimple last_and_only_stmt (basic_block);
diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index 21ed17b..4a2757d 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -1492,25 +1492,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>:
@@ -1631,18 +1612,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);
@@ -1675,6 +1649,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++)
@@ -1692,10 +1667,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)
@@ -1710,7 +1684,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 a72b779..3fbb456 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -560,6 +560,57 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
   free (use_blocks);
 }
 
+/* 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)
+{
+  gimple use_stmt;
+  imm_use_iterator imm_iter;
+
+  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_val)
+    {
+      if (!dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb))
+	  continue;
+
+      use_operand_p use_p;
+      FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
+	SET_USE (use_p, new_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.  Handles
+   only loops with a single exit that dominates the latch.  */
+
+void
+rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
+{
+  gphi *phi;
+  /* TODO: Handle !single_dom_exit loops.  */
+  edge exit = single_dom_exit (loop);
+  gcc_assert (exit != NULL);
+
+  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

[gomp4, committed] Add rewrite_virtuals_into_loop_closed_ssa

[Tom de Vries]

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

On 07/07/15 17:58, Tom de Vries wrote:
> Bootstrapped reg-tested on x86_64.
>
> Committed to trunk as attached.
>

Reverted related patches on gomp-4_0-branch, and committed this patch 
instead.

Thanks,
- Tom

>>
>>>> +  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
>>>>
>>>
>>>
>>
>
>
> 0001-Add-rewrite_virtuals_into_loop_closed_ssa.patch
>
>
> Add rewrite_virtuals_into_loop_closed_ssa
>
> 2015-07-07  Tom de Vries<tom@codesourcery.com>
>
> 	* tree-cfg.c (get_virtual_phi): New function.
> 	* tree-cfg.h (get_virtual_phi): Declare.
> 	* tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs)
> 	(rewrite_virtuals_into_loop_closed_ssa): New function.
> 	* tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa):
> 	Declare.
> 	* tree-parloops.c (replace_uses_in_bbs_by): Remove.
> 	(transform_to_exit_first_loop_alt): Use
> 	rewrite_virtuals_into_loop_closed_ssa.
> ---
>   gcc/tree-cfg.c            | 17 ++++++++++++++++
>   gcc/tree-cfg.h            |  1 +
>   gcc/tree-parloops.c       | 43 ++++++++-------------------------------
>   gcc/tree-ssa-loop-manip.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++
>   gcc/tree-ssa-loop-manip.h |  1 +
>   5 files changed, 78 insertions(+), 35 deletions(-)
>
> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
> index 94ed957..3ab3ab4 100644
> --- a/gcc/tree-cfg.c
> +++ b/gcc/tree-cfg.c
> @@ -2623,6 +2623,23 @@ delete_tree_cfg_annotations (void)
>     vec_free (label_to_block_map_for_fn (cfun));
>   }
>
> +/* Return the virtual phi in BB.  */
> +
> +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;
> +}
>
>   /* Return the first statement in basic block BB.  */
>
> diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
> index 2fc1e88..af58c80 100644
> --- a/gcc/tree-cfg.h
> +++ b/gcc/tree-cfg.h
> @@ -59,6 +59,7 @@ extern bool simple_goto_p (gimple);
>   extern bool stmt_ends_bb_p (gimple);
>   extern bool assert_unreachable_fallthru_edge_p (edge);
>   extern void delete_tree_cfg_annotations (void);
> +extern gphi *get_virtual_phi (basic_block);
>   extern gimple first_stmt (basic_block);
>   extern gimple last_stmt (basic_block);
>   extern gimple last_and_only_stmt (basic_block);
> diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
> index 21ed17b..4a2757d 100644
> --- a/gcc/tree-parloops.c
> +++ b/gcc/tree-parloops.c
> @@ -1492,25 +1492,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>:
> @@ -1631,18 +1612,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);
> @@ -1675,6 +1649,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++)
> @@ -1692,10 +1667,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)
> @@ -1710,7 +1684,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 a72b779..3fbb456 100644
> --- a/gcc/tree-ssa-loop-manip.c
> +++ b/gcc/tree-ssa-loop-manip.c
> @@ -560,6 +560,57 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
>     free (use_blocks);
>   }
>
> +/* 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)
> +{
> +  gimple use_stmt;
> +  imm_use_iterator imm_iter;
> +
> +  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_val)
> +    {
> +      if (!dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb))
> +	  continue;
> +
> +      use_operand_p use_p;
> +      FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
> +	SET_USE (use_p, new_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.  Handles
> +   only loops with a single exit that dominates the latch.  */
> +
> +void
> +rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
> +{
> +  gphi *phi;
> +  /* TODO: Handle !single_dom_exit loops.  */
> +  edge exit = single_dom_exit (loop);
> +  gcc_assert (exit != NULL);
> +
> +  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

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

[Richard Biener]

On Tue, 7 Jul 2015, Tom de Vries wrote:

> On 06/07/15 15:44, Richard Biener wrote:
> > 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.

Yeah - patches to make use of get_virtual_phi are pre-approved if they
look obvious enough.

Richard.

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

[Jeff Law]

On 07/07/2015 09:58 AM, Tom de Vries wrote:
[Big snip]
>
>
> 0001-Add-rewrite_virtuals_into_loop_closed_ssa.patch
>
>
> Add rewrite_virtuals_into_loop_closed_ssa
>
> 2015-07-07  Tom de Vries<tom@codesourcery.com>
>
> 	* tree-cfg.c (get_virtual_phi): New function.
> 	* tree-cfg.h (get_virtual_phi): Declare.
> 	* tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs)
> 	(rewrite_virtuals_into_loop_closed_ssa): New function.
> 	* tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa):
> 	Declare.
> 	* tree-parloops.c (replace_uses_in_bbs_by): Remove.
> 	(transform_to_exit_first_loop_alt): Use
> 	rewrite_virtuals_into_loop_closed_ssa.
So how is the testcase in 56113 affected by this change (compile-time 
and memory usage?)  I didn't see any discussion of that in the thread 
from June.


Jeff

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

[Tom de Vries]

On 09/07/15 05:33, Jeff Law wrote:
> On 07/07/2015 09:58 AM, Tom de Vries wrote:
> [Big snip]
>>
>>
>> 0001-Add-rewrite_virtuals_into_loop_closed_ssa.patch
>>
>>
>> Add rewrite_virtuals_into_loop_closed_ssa
>>
>> 2015-07-07  Tom de Vries<tom@codesourcery.com>
>>
>>     * tree-cfg.c (get_virtual_phi): New function.
>>     * tree-cfg.h (get_virtual_phi): Declare.
>>     * tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs)
>>     (rewrite_virtuals_into_loop_closed_ssa): New function.
>>     * tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa):
>>     Declare.
>>     * tree-parloops.c (replace_uses_in_bbs_by): Remove.
>>     (transform_to_exit_first_loop_alt): Use
>>     rewrite_virtuals_into_loop_closed_ssa.

> So how is the testcase in 56113 affected by this change (compile-time
> and memory usage?)  I didn't see any discussion of that in the thread
> from June.
>

Hi Jeff,

rewrite_virtuals_into_loop_closed_ssa is only active for loops that are 
transformed by parloops (which is off by default).

The example in PR56113 at n == 1000 only contains one loop, with 
!single_dom_exit, so if parloops is switched on, it doesn't transform 
the loop.

Thanks,
- Tom

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

[Tom de Vries]

On 07/07/15 17:58, Tom de Vries wrote:
>> 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.

Hmm, I just realised, it's more complicated than I thought.

In loops with single_dom_exit, the exit dominates the uses outside the 
loop, so I can replace the uses of the def with the uses of the exit phi 
result.

If !single_dom_exit, the exit(s) may not dominate all uses, and I need 
to insert non-loop-exit phi nodes to deal with that.

Thanks,
- Tom

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

[Richard Biener]

On Thu, 9 Jul 2015, Tom de Vries wrote:

> On 07/07/15 17:58, Tom de Vries wrote:
> > > 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.
> 
> Hmm, I just realised, it's more complicated than I thought.
> 
> In loops with single_dom_exit, the exit dominates the uses outside the loop,
> so I can replace the uses of the def with the uses of the exit phi result.
> 
> If !single_dom_exit, the exit(s) may not dominate all uses, and I need to
> insert non-loop-exit phi nodes to deal with that.

Yes.  This is why I originally suggested to amend the regular
loop-close-SSA rewriting code.

Richard.

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

[Jeff Law]

On 07/09/2015 03:19 AM, Tom de Vries wrote:
> On 09/07/15 05:33, Jeff Law wrote:
>> On 07/07/2015 09:58 AM, Tom de Vries wrote:
>> [Big snip]
>>>
>>>
>>> 0001-Add-rewrite_virtuals_into_loop_closed_ssa.patch
>>>
>>>
>>> Add rewrite_virtuals_into_loop_closed_ssa
>>>
>>> 2015-07-07  Tom de Vries<tom@codesourcery.com>
>>>
>>>     * tree-cfg.c (get_virtual_phi): New function.
>>>     * tree-cfg.h (get_virtual_phi): Declare.
>>>     * tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs)
>>>     (rewrite_virtuals_into_loop_closed_ssa): New function.
>>>     * tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa):
>>>     Declare.
>>>     * tree-parloops.c (replace_uses_in_bbs_by): Remove.
>>>     (transform_to_exit_first_loop_alt): Use
>>>     rewrite_virtuals_into_loop_closed_ssa.
>
>> So how is the testcase in 56113 affected by this change (compile-time
>> and memory usage?)  I didn't see any discussion of that in the thread
>> from June.
>>
>
> Hi Jeff,
>
> rewrite_virtuals_into_loop_closed_ssa is only active for loops that are
> transformed by parloops (which is off by default).
>
> The example in PR56113 at n == 1000 only contains one loop, with
> !single_dom_exit, so if parloops is switched on, it doesn't transform
> the loop.
Opps.  Nevermind, obviously not appropriate since you're not rewriting 
into LCSSA in the general case, just those transformed by parloops ;-)

jeff

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

[Tom de Vries]

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

On 09/07/15 13:04, Richard Biener wrote:
> On Thu, 9 Jul 2015, Tom de Vries wrote:
>
>> On 07/07/15 17:58, Tom de Vries wrote:
>>>> 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.
>>
>> Hmm, I just realised, it's more complicated than I thought.
>>
>> In loops with single_dom_exit, the exit dominates the uses outside the loop,
>> so I can replace the uses of the def with the uses of the exit phi result.
>>
>> If !single_dom_exit, the exit(s) may not dominate all uses, and I need to
>> insert non-loop-exit phi nodes to deal with that.
>
> Yes.  This is why I originally suggested to amend the regular
> loop-close-SSA rewriting code.
>

This patch renames rewrite_into_loop_closed_ssa to 
rewrite_into_loop_closed_ssa_1, and adds arguments:
- a loop argument, to limit the defs for which the uses are
   rewritten
- a use_flags argument, to determine the type of uses rewritten:
   SSA_OP_USE/SSA_OP_VIRTUAL_USES/SSA_OP_ALL_USES

The original rewrite_into_loop_closed_ssa is reimplemented using 
rewrite_into_loop_closed_ssa_1.

And the !single_dom_exit case of rewrite_into_loop_closed_ssa is 
implemented using rewrite_into_loop_closed_ssa_1. [ The patch was tested 
as attached, always using rewrite_into_loop_closed_ssa_1, otherwise it 
would not be triggered. ]

Bootstrapped and reg-tested on x86_64.

Is this sort of what you had in mind?

Thanks,
- Tom


[-- Attachment #2: 0001-Implement-rewrite_virtuals_into_loop_closed_ssa-for-.patch --]
[-- Type: text/x-patch, Size: 8207 bytes --]

Implement rewrite_virtuals_into_loop_closed_ssa for !single_dom_exit

---
 gcc/tree-ssa-loop-manip.c | 146 ++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 129 insertions(+), 17 deletions(-)

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index cb762df..2b085df 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -407,7 +407,8 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
    NEED_PHIS.  */
 
 static void
-find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis)
+find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis,
+			  int use_flags)
 {
   ssa_op_iter iter;
   tree var;
@@ -416,8 +417,16 @@ find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis)
   if (is_gimple_debug (stmt))
     return;
 
-  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
-    find_uses_to_rename_use (bb, var, use_blocks, need_phis);
+  /* Iterator does not allows SSA_OP_VIRTUAL_USES only.  */
+  if (use_flags == SSA_OP_VIRTUAL_USES)
+    {
+      tree vuse = gimple_vuse (stmt);
+      if (vuse != NULL_TREE)
+	find_uses_to_rename_use (bb, gimple_vuse (stmt), use_blocks, need_phis);
+    }
+  else
+    FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, use_flags)
+      find_uses_to_rename_use (bb, var, use_blocks, need_phis);
 }
 
 /* Marks names that are used in BB and outside of the loop they are
@@ -426,24 +435,30 @@ find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis)
    need exit PHIs in NEED_PHIS.  */
 
 static void
-find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
+find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis,
+			int use_flags)
 {
   edge e;
   edge_iterator ei;
+  bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
+  bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
 
   FOR_EACH_EDGE (e, ei, bb->succs)
     for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
 	 gsi_next (&bsi))
       {
         gphi *phi = bsi.phi ();
-	if (! virtual_operand_p (gimple_phi_result (phi)))
+	bool virtual_p = virtual_operand_p (gimple_phi_result (phi));
+	if ((virtual_p && do_virtuals)
+	    || (!virtual_p && do_nonvirtuals))
 	  find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
 				   use_blocks, need_phis);
       }
 
   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
        gsi_next (&bsi))
-    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis);
+    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis,
+			      use_flags);
 }
 
 /* Marks names that are used outside of the loop they are defined in
@@ -452,7 +467,8 @@ find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
    scan only blocks in this set.  */
 
 static void
-find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
+find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis,
+		     int use_flags)
 {
   basic_block bb;
   unsigned index;
@@ -460,10 +476,76 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
 
   if (changed_bbs)
     EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
-      find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks, need_phis);
+      find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks,
+			      need_phis, use_flags);
   else
     FOR_EACH_BB_FN (bb, cfun)
-      find_uses_to_rename_bb (bb, use_blocks, need_phis);
+      find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags);
+}
+
+static void
+find_uses_to_rename_def (basic_block def_bb, tree def, bitmap *use_blocks, bitmap need_phis)
+{
+  gimple use_stmt;
+  imm_use_iterator imm_iter;
+
+  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
+    {
+      use_operand_p use_p;
+      FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
+	find_uses_to_rename_use (def_bb, USE_FROM_PTR (use_p), use_blocks,
+				 need_phis);
+    }
+}
+
+static void
+find_uses_to_rename_in_loop (struct loop *loop, bitmap *use_blocks,
+			     bitmap need_phis, int use_flags)
+{
+  basic_block bb;
+
+  bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
+  bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
+  int def_flags = ((do_virtuals ? SSA_OP_VIRTUAL_DEFS : 0)
+		   | (do_nonvirtuals ? SSA_OP_DEF : 0));
+
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      if (bb->loop_father != loop)
+	continue;
+
+      for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
+	   gsi_next (&bsi))
+	{
+	  gphi *phi = bsi.phi ();
+	  tree res = gimple_phi_result (phi);
+	  bool virtual_p = virtual_operand_p (res);
+	  if ((virtual_p && do_virtuals)
+	      || (!virtual_p && do_nonvirtuals))
+	    find_uses_to_rename_def (bb, res, use_blocks, need_phis);
+      }
+
+      for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
+	   gsi_next (&bsi))
+	{
+	  gimple stmt = gsi_stmt (bsi);
+	  /* Iterator does not allows SSA_OP_VIRTUAL_DEFS only.  */
+	  if (def_flags == SSA_OP_VIRTUAL_DEFS)
+	    {
+	      tree vdef = gimple_vdef (stmt);
+	      if (vdef != NULL)
+		find_uses_to_rename_def (bb, vdef, use_blocks, need_phis);
+	    }
+	  else
+	    {
+	      tree var;
+	      ssa_op_iter iter;
+	      FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, def_flags)
+		find_uses_to_rename_def (bb, var, use_blocks, need_phis);
+	    }
+	}
+    }
 }
 
 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
@@ -502,7 +584,8 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
       TODO_update_ssa* for documentation.  */
 
 void
-rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
+rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
+				int use_flags, struct loop *loop)
 {
   bitmap *use_blocks;
   bitmap names_to_rename;
@@ -513,7 +596,14 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
 
   /* If the pass has caused the SSA form to be out-of-date, update it
      now.  */
-  update_ssa (update_flag);
+  if (update_flag == 0)
+    {
+#ifdef ENABLE_CHECKING
+      verify_ssa (true, true);
+#endif
+    }
+  else
+    update_ssa (update_flag);
 
   bitmap_obstack_initialize (&loop_renamer_obstack);
 
@@ -524,8 +614,17 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
      in NAMES_TO_RENAME.  */
   use_blocks = XNEWVEC (bitmap, num_ssa_names);
 
-  /* Find the uses outside loops.  */
-  find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
+  if (loop != NULL)
+    {
+      gcc_assert (changed_bbs == NULL);
+      find_uses_to_rename_in_loop (loop, use_blocks, names_to_rename,
+				   use_flags);
+    }
+  else
+    {
+      gcc_assert (loop == NULL);
+      find_uses_to_rename (changed_bbs, use_blocks, names_to_rename, use_flags);
+    }
 
   if (!bitmap_empty_p (names_to_rename))
     {
@@ -549,6 +648,12 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
   free (use_blocks);
 }
 
+void
+rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
+{
+  rewrite_into_loop_closed_ssa_1 (changed_bbs, update_flag, SSA_OP_USE, NULL);
+}
+
 /* Replace uses of OLD_VAL with NEW_VAL in bbs dominated by BB.  */
 
 static void
@@ -569,16 +674,23 @@ replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb)
 }
 
 /* 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.  Handles
-   only loops with a single exit that dominates the latch.  */
+   In other words, ensure loop-closed ssa normal form for virtuals.  */
 
 void
 rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
 {
   gphi *phi;
-  /* TODO: Handle !single_dom_exit loops.  */
   edge exit = single_dom_exit (loop);
-  gcc_assert (exit != NULL);
+
+#if 0
+  if (exit == NULL)
+#else
+  if (true || exit == NULL)
+#endif
+    {
+      rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_VIRTUAL_USES, loop);
+      return;
+    }
 
   phi = get_virtual_phi (loop->header);
   if (phi == NULL)
-- 
1.9.1

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

[Richard Biener]

On Mon, 20 Jul 2015, Tom de Vries wrote:

> On 09/07/15 13:04, Richard Biener wrote:
> > On Thu, 9 Jul 2015, Tom de Vries wrote:
> > 
> > > On 07/07/15 17:58, Tom de Vries wrote:
> > > > > 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.
> > > 
> > > Hmm, I just realised, it's more complicated than I thought.
> > > 
> > > In loops with single_dom_exit, the exit dominates the uses outside the
> > > loop,
> > > so I can replace the uses of the def with the uses of the exit phi result.
> > > 
> > > If !single_dom_exit, the exit(s) may not dominate all uses, and I need to
> > > insert non-loop-exit phi nodes to deal with that.
> > 
> > Yes.  This is why I originally suggested to amend the regular
> > loop-close-SSA rewriting code.
> > 
> 
> This patch renames rewrite_into_loop_closed_ssa to
> rewrite_into_loop_closed_ssa_1, and adds arguments:
> - a loop argument, to limit the defs for which the uses are
>   rewritten
> - a use_flags argument, to determine the type of uses rewritten:
>   SSA_OP_USE/SSA_OP_VIRTUAL_USES/SSA_OP_ALL_USES
> 
> The original rewrite_into_loop_closed_ssa is reimplemented using
> rewrite_into_loop_closed_ssa_1.
> 
> And the !single_dom_exit case of rewrite_into_loop_closed_ssa is implemented
> using rewrite_into_loop_closed_ssa_1. [ The patch was tested as attached,
> always using rewrite_into_loop_closed_ssa_1, otherwise it would not be
> triggered. ]
> 
> Bootstrapped and reg-tested on x86_64.
> 
> Is this sort of what you had in mind?

Yes.  New functions need a comment and instead of iterating over
all function BBs and checking bb->loop_father please use
get_loop_body ().

Of course in the final version #if 0 stuff shouldn't remain.  What's
the cost difference of removing the single_dom_exit special-case?

Thanks,
Richard.

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)

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

[Tom de Vries]

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

On 23/07/15 15:44, Richard Biener wrote:
> On Mon, 20 Jul 2015, Tom de Vries wrote:
>
>> On 09/07/15 13:04, Richard Biener wrote:
>>> On Thu, 9 Jul 2015, Tom de Vries wrote:
>>>
>>>> On 07/07/15 17:58, Tom de Vries wrote:
>>>>>> 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.
>>>>
>>>> Hmm, I just realised, it's more complicated than I thought.
>>>>
>>>> In loops with single_dom_exit, the exit dominates the uses outside the
>>>> loop,
>>>> so I can replace the uses of the def with the uses of the exit phi result.
>>>>
>>>> If !single_dom_exit, the exit(s) may not dominate all uses, and I need to
>>>> insert non-loop-exit phi nodes to deal with that.
>>>
>>> Yes.  This is why I originally suggested to amend the regular
>>> loop-close-SSA rewriting code.
>>>
>>
>> This patch renames rewrite_into_loop_closed_ssa to
>> rewrite_into_loop_closed_ssa_1, and adds arguments:
>> - a loop argument, to limit the defs for which the uses are
>>    rewritten
>> - a use_flags argument, to determine the type of uses rewritten:
>>    SSA_OP_USE/SSA_OP_VIRTUAL_USES/SSA_OP_ALL_USES
>>
>> The original rewrite_into_loop_closed_ssa is reimplemented using
>> rewrite_into_loop_closed_ssa_1.
>>
>> And the !single_dom_exit case of rewrite_into_loop_closed_ssa is implemented
>> using rewrite_into_loop_closed_ssa_1. [ The patch was tested as attached,
>> always using rewrite_into_loop_closed_ssa_1, otherwise it would not be
>> triggered. ]
>>
>> Bootstrapped and reg-tested on x86_64.
>>
>> Is this sort of what you had in mind?
>
> Yes.  New functions need a comment

Done.

> and instead of iterating over
> all function BBs and checking bb->loop_father please use
> get_loop_body ().
>

Done.

> Of course in the final version #if 0 stuff shouldn't remain.

Done.

> What's
> the cost difference of removing the single_dom_exit special-case?
>

I'm not sure. But, in order to avoid having unexercised code, I removed 
the single_dom_exit special-case in this patch. I think the code is not 
called often enough to have an impact in speed. And if we want the 
single_dom_exit special case, we should probably add it generically, 
rather than having it just for virtuals as it is done now.

Bootstrapped and reg-tested on x86_64.

OK for trunk?

Thanks,
- Tom



[-- Attachment #2: 0002-Reimplement-rewrite_virtuals_into_loop_closed_ssa.patch --]
[-- Type: text/x-patch, Size: 12415 bytes --]

Reimplement rewrite_virtuals_into_loop_closed_ssa

2015-08-31  Tom de Vries  <tom@codesourcery.com>

	* tree-ssa-loop-manip.c (find_uses_to_rename_stmt)
	(find_uses_to_rename_bb, find_uses_to_rename): Add and handle use_flags
	parameter.
	(find_uses_to_rename_def, find_uses_to_rename_in_loop): New function.
	(rewrite_into_loop_closed_ssa_1): New function, factored out of ...
	(rewrite_into_loop_closed_ssa): ... here.
	(replace_uses_in_dominated_bbs): Remove function.
	(rewrite_virtuals_into_loop_closed_ssa): Reimplement using
	rewrite_into_loop_closed_ssa_1.
---
 gcc/tree-ssa-loop-manip.c | 226 ++++++++++++++++++++++++++++++++--------------
 1 file changed, 160 insertions(+), 66 deletions(-)

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index 5c13d4b..fb7ba48 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -403,12 +403,13 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
   bitmap_set_bit (use_blocks[ver], bb->index);
 }
 
-/* For uses in STMT, mark names that are used outside of the loop they are
-   defined to rewrite.  Record the set of blocks in which the ssa names are used
-   to USE_BLOCKS and the ssa names themselves to NEED_PHIS.  */
+/* For uses matching USE_FLAGS in STMT, mark names that are used outside of the
+   loop they are defined to rewrite.  Record the set of blocks in which the ssa
+   names are used to USE_BLOCKS, and the ssa names themselves to NEED_PHIS.  */
 
 static void
-find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis)
+find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis,
+			  int use_flags)
 {
   ssa_op_iter iter;
   tree var;
@@ -417,42 +418,59 @@ find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis)
   if (is_gimple_debug (stmt))
     return;
 
-  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
-    find_uses_to_rename_use (bb, var, use_blocks, need_phis);
+  /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows SSA_OP_VIRTUAL_USES
+     only.  */
+  if (use_flags == SSA_OP_VIRTUAL_USES)
+    {
+      tree vuse = gimple_vuse (stmt);
+      if (vuse != NULL_TREE)
+	find_uses_to_rename_use (bb, gimple_vuse (stmt), use_blocks, need_phis);
+    }
+  else
+    FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, use_flags)
+      find_uses_to_rename_use (bb, var, use_blocks, need_phis);
 }
 
-/* Marks names that are used in BB and outside of the loop they are defined in
-   for rewrite.  Records the set of blocks in which the ssa names are used to
-   USE_BLOCKS.  Record the SSA names that will need exit PHIs in NEED_PHIS.  */
+/* Marks names matching USE_FLAGS that are used in BB and outside of the loop
+   they are defined in for rewrite.  Records the set of blocks in which the ssa
+   names are used to USE_BLOCKS.  Record the SSA names that will
+   need exit PHIs in NEED_PHIS.  */
 
 static void
-find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
+find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis,
+			int use_flags)
 {
   edge e;
   edge_iterator ei;
+  bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
+  bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
 
   FOR_EACH_EDGE (e, ei, bb->succs)
     for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
 	 gsi_next (&bsi))
       {
         gphi *phi = bsi.phi ();
-	if (! virtual_operand_p (gimple_phi_result (phi)))
+	bool virtual_p = virtual_operand_p (gimple_phi_result (phi));
+	if ((virtual_p && do_virtuals)
+	    || (!virtual_p && do_nonvirtuals))
 	  find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
 				   use_blocks, need_phis);
       }
 
   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
        gsi_next (&bsi))
-    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis);
+    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis,
+			      use_flags);
 }
 
-/* Marks names that are used outside of the loop they are defined in for
-   rewrite.  Records the set of blocks in which the ssa names are used to
-   USE_BLOCKS.  Record the SSA names that will need exit PHIs in NEED_PHIS.  If
-   CHANGED_BBS is not NULL, scan only blocks in this set.  */
+/* Marks names matching USE_FLAGS that are used outside of the loop they are
+   defined in for rewrite.  Records the set of blocks in which the ssa names are
+   used to USE_BLOCKS.  Record the SSA names that will need exit PHIs in
+   NEED_PHIS.  If CHANGED_BBS is not NULL, scan only blocks in this set.  */
 
 static void
-find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
+find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis,
+		     int use_flags)
 {
   basic_block bb;
   unsigned index;
@@ -460,10 +478,96 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
 
   if (changed_bbs)
     EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
-      find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks, need_phis);
+      find_uses_to_rename_bb (BASIC_BLOCK_FOR_FN (cfun, index), use_blocks,
+			      need_phis, use_flags);
   else
     FOR_EACH_BB_FN (bb, cfun)
-      find_uses_to_rename_bb (bb, use_blocks, need_phis);
+      find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags);
+}
+
+/* Mark uses of DEF that are used outside of the loop they are defined in for
+   rewrite.  Record the set of blocks in which the ssa names are used to
+   USE_BLOCKS.  Record the SSA names that will need exit PHIs in NEED_PHIS.  */
+
+static void
+find_uses_to_rename_def (tree def, bitmap *use_blocks, bitmap need_phis)
+{
+  gimple use_stmt;
+  imm_use_iterator imm_iter;
+
+  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
+    {
+      basic_block use_bb = gimple_bb (use_stmt);
+
+      use_operand_p use_p;
+      FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
+	{
+	  if (gimple_code (use_stmt) == GIMPLE_PHI)
+	    {
+	      edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt),
+					    PHI_ARG_INDEX_FROM_USE (use_p));
+	      use_bb = e->src;
+	    }
+	  find_uses_to_rename_use (use_bb, USE_FROM_PTR (use_p), use_blocks,
+				   need_phis);
+	}
+    }
+}
+
+/* Marks names matching USE_FLAGS that are defined in LOOP and used outside of
+   it for rewrite.  Records the set of blocks in which the ssa names are used to
+   USE_BLOCKS.  Record the SSA names that will need exit PHIs in NEED_PHIS.  */
+
+static void
+find_uses_to_rename_in_loop (struct loop *loop, bitmap *use_blocks,
+			     bitmap need_phis, int use_flags)
+{
+  bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
+  bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
+  int def_flags = ((do_virtuals ? SSA_OP_VIRTUAL_DEFS : 0)
+		   | (do_nonvirtuals ? SSA_OP_DEF : 0));
+
+
+  basic_block *bbs = get_loop_body (loop);
+
+  for (unsigned int i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = bbs[i];
+
+      for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
+	   gsi_next (&bsi))
+	{
+	  gphi *phi = bsi.phi ();
+	  tree res = gimple_phi_result (phi);
+	  bool virtual_p = virtual_operand_p (res);
+	  if ((virtual_p && do_virtuals)
+	      || (!virtual_p && do_nonvirtuals))
+	    find_uses_to_rename_def (res, use_blocks, need_phis);
+      }
+
+      for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
+	   gsi_next (&bsi))
+	{
+	  gimple stmt = gsi_stmt (bsi);
+	  /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows
+	     SSA_OP_VIRTUAL_DEFS only.  */
+	  if (def_flags == SSA_OP_VIRTUAL_DEFS)
+	    {
+	      tree vdef = gimple_vdef (stmt);
+	      if (vdef != NULL)
+		find_uses_to_rename_def (vdef, use_blocks, need_phis);
+	    }
+	  else
+	    {
+	      tree var;
+	      ssa_op_iter iter;
+	      FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, def_flags)
+		find_uses_to_rename_def (var, use_blocks, need_phis);
+	    }
+	}
+    }
+
+  XDELETEVEC (bbs);
 }
 
 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
@@ -495,14 +599,19 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
       is not well-behaved, while the second one is an induction variable with
       base 99 and step 1.
 
-      If CHANGED_BBS is not NULL, we look for uses outside loops only in
-      the basic blocks in this set.
+      If LOOP is non-null, only rewrite uses that have defs in LOOP.  Otherwise,
+      if CHANGED_BBS is not NULL, we look for uses outside loops only in the
+      basic blocks in this set.
+
+      USE_FLAGS allows us to specify whether we want virtual, non-virtual or
+      both variables rewritten.
 
       UPDATE_FLAG is used in the call to update_ssa.  See
       TODO_update_ssa* for documentation.  */
 
 void
-rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
+rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
+				int use_flags, struct loop *loop)
 {
   bitmap *use_blocks;
   bitmap names_to_rename;
@@ -513,7 +622,14 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
 
   /* If the pass has caused the SSA form to be out-of-date, update it
      now.  */
-  update_ssa (update_flag);
+  if (update_flag == 0)
+    {
+#ifdef ENABLE_CHECKING
+      verify_ssa (true, true);
+#endif
+    }
+  else
+    update_ssa (update_flag);
 
   bitmap_obstack_initialize (&loop_renamer_obstack);
 
@@ -524,8 +640,17 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
      in NAMES_TO_RENAME.  */
   use_blocks = XNEWVEC (bitmap, num_ssa_names);
 
-  /* Find the uses outside loops.  */
-  find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
+  if (loop != NULL)
+    {
+      gcc_assert (changed_bbs == NULL);
+      find_uses_to_rename_in_loop (loop, use_blocks, names_to_rename,
+				   use_flags);
+    }
+  else
+    {
+      gcc_assert (loop == NULL);
+      find_uses_to_rename (changed_bbs, use_blocks, names_to_rename, use_flags);
+    }
 
   if (!bitmap_empty_p (names_to_rename))
     {
@@ -549,55 +674,24 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
   free (use_blocks);
 }
 
-/* Replace uses of OLD_VAL with NEW_VAL in bbs dominated by BB.  */
+/* Rewrites the non-virtual defs and uses into a loop closed ssa form.  If
+   CHANGED_BBS is not NULL, we look for uses outside loops only in the basic
+   blocks in this set.  UPDATE_FLAG is used in the call to update_ssa.  See
+   TODO_update_ssa* for documentation.  */
 
-static void
-replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb)
+void
+rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
 {
-  gimple use_stmt;
-  imm_use_iterator imm_iter;
-
-  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_val)
-    {
-      if (!dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb))
-	  continue;
-
-      use_operand_p use_p;
-      FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
-	SET_USE (use_p, new_val);
-    }
+  rewrite_into_loop_closed_ssa_1 (changed_bbs, update_flag, SSA_OP_USE, 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.  Handles
-   only loops with a single exit that dominates the latch.  */
+/* Rewrites virtual defs and uses with def in LOOP into loop closed ssa
+   form.  */
 
 void
 rewrite_virtuals_into_loop_closed_ssa (struct loop *loop)
 {
-  gphi *phi;
-  /* TODO: Handle !single_dom_exit loops.  */
-  edge exit = single_dom_exit (loop);
-  gcc_assert (exit != NULL);
-
-  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);
+  rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_VIRTUAL_USES, loop);
 }
 
 /* Check invariants of the loop closed ssa form for the USE in BB.  */
-- 
1.9.1

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

[Richard Biener]

On Mon, 31 Aug 2015, Tom de Vries wrote:

> On 23/07/15 15:44, Richard Biener wrote:
> > On Mon, 20 Jul 2015, Tom de Vries wrote:
> > 
> > > On 09/07/15 13:04, Richard Biener wrote:
> > > > On Thu, 9 Jul 2015, Tom de Vries wrote:
> > > > 
> > > > > On 07/07/15 17:58, Tom de Vries wrote:
> > > > > > > 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.
> > > > > 
> > > > > Hmm, I just realised, it's more complicated than I thought.
> > > > > 
> > > > > In loops with single_dom_exit, the exit dominates the uses outside the
> > > > > loop,
> > > > > so I can replace the uses of the def with the uses of the exit phi
> > > > > result.
> > > > > 
> > > > > If !single_dom_exit, the exit(s) may not dominate all uses, and I need
> > > > > to
> > > > > insert non-loop-exit phi nodes to deal with that.
> > > > 
> > > > Yes.  This is why I originally suggested to amend the regular
> > > > loop-close-SSA rewriting code.
> > > > 
> > > 
> > > This patch renames rewrite_into_loop_closed_ssa to
> > > rewrite_into_loop_closed_ssa_1, and adds arguments:
> > > - a loop argument, to limit the defs for which the uses are
> > >    rewritten
> > > - a use_flags argument, to determine the type of uses rewritten:
> > >    SSA_OP_USE/SSA_OP_VIRTUAL_USES/SSA_OP_ALL_USES
> > > 
> > > The original rewrite_into_loop_closed_ssa is reimplemented using
> > > rewrite_into_loop_closed_ssa_1.
> > > 
> > > And the !single_dom_exit case of rewrite_into_loop_closed_ssa is
> > > implemented
> > > using rewrite_into_loop_closed_ssa_1. [ The patch was tested as attached,
> > > always using rewrite_into_loop_closed_ssa_1, otherwise it would not be
> > > triggered. ]
> > > 
> > > Bootstrapped and reg-tested on x86_64.
> > > 
> > > Is this sort of what you had in mind?
> > 
> > Yes.  New functions need a comment
> 
> Done.
> 
> > and instead of iterating over
> > all function BBs and checking bb->loop_father please use
> > get_loop_body ().
> > 
> 
> Done.
> 
> > Of course in the final version #if 0 stuff shouldn't remain.
> 
> Done.
> 
> > What's
> > the cost difference of removing the single_dom_exit special-case?
> > 
> 
> I'm not sure. But, in order to avoid having unexercised code, I removed the
> single_dom_exit special-case in this patch. I think the code is not called
> often enough to have an impact in speed. And if we want the single_dom_exit
> special case, we should probably add it generically, rather than having it
> just for virtuals as it is done now.
> 
> Bootstrapped and reg-tested on x86_64.
> 
> OK for trunk?

Ok.

Thanks,
Richard.