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