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(-)
@@ -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