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