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

[Tom de Vries <Tom_deVries at mentor dot com>]

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