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<t...@codesourcery.com>
merge from gomp4 branch:
2015-06-24 Tom de Vries<t...@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<t...@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
Add rewrite_virtuals_into_loop_closed_ssa
2015-07-07 Tom de Vries <t...@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
