Re: [parloops, PR83126], Use cached affine_ivs canonicalize_loop_ivs

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

On 03/12/2018 01:14 PM, Richard Biener wrote:
> On Thu, 22 Feb 2018, Tom de Vries wrote:
>
> > Hi,
> >
> > this patch fixes an ICE in the parloops pass.
> >
> > The ICE (when compiling the test-case in attached patch) follows from the fact
> > that here in gen_parallel_loop the call to canonicalize_loop_ivs fails to
> > "base all the induction variables in LOOP on a single control one":
> > ...
> >    /* Base all the induction variables in LOOP on a single control one.*/
> >    canonicalize_loop_ivs (loop, &nit, true);
> > ...
> >
> > This is caused by the fact that for one of the induction variables, simple_iv
> > no longer returns true (as was the case at the start of gen_parallel_loop).
> > This seems to be triggered by the fact that during loop_version we call
> > scev_reset (although I'm not sure why when recalculating scev info we're not
> > reaching the same conclusion as before).
> I guess the real reason is that canonicalize_loop_ivs calls
> create_iv first which in the parloop case with bump-in-latch true
> and then incrementally re-writes PHIs, eventually wrecking other
> PHIs SCEV.  In this case the 2nd PHIs evolution depends on the
> first one but the rewritten ones depend on the new IV already.
>
> So the better fix (maybe not 100% enough) would be to re-organize
> canonicalize_loop_ivs to first do analysis of all PHIs and then
> rewrite them all.

Focusing on the re-organize first, is this sort of what you had in mind?

Bootstrapped and reg-tested on x86_64.

Thanks,
- Tom

Split canonicalize_loop_ivs in analyze and rewrite parts

2018-03-21  Tom de Vries  <tom@codesourcery.com>

	* tree-ssa-loop-manip.c (rewrite_phi_with_iv): Remove loop parameter.
	Add iv parameter.  Move early-out tests ...
	(rewrite_all_phi_nodes_with_iv): ... here.  Remove loop argument and add
	iv argument to rewrite_phi_with_iv call.
	(get_all_phi_affine_ivs): New function.
	(canonicalize_loop_ivs): Call get_all_phi_affine_ivs and pass result as
	argument to rewrite_all_phi_nodes_with_iv.

---
 gcc/tree-ssa-loop-manip.c | 82 +++++++++++++++++++++++++++++++++++------------
 1 file changed, 61 insertions(+), 21 deletions(-)

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index bf425af..15a5795 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -43,6 +43,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "params.h"
 #include "tree-inline.h"
+#include "hash-map.h"
 
 /* All bitmaps for rewriting into loop-closed SSA go on this obstack,
    so that we can free them all at once.  */
@@ -1430,48 +1431,65 @@ tree_unroll_loop (struct loop *loop, unsigned factor,
    induction variable MAIN_IV and insert the generated code at GSI.  */
 
 static void
-rewrite_phi_with_iv (loop_p loop,
-		     gphi_iterator *psi,
+rewrite_phi_with_iv (gphi_iterator *psi,
 		     gimple_stmt_iterator *gsi,
-		     tree main_iv)
+		     tree main_iv, affine_iv *iv)
 {
-  affine_iv iv;
   gassign *stmt;
   gphi *phi = psi->phi ();
   tree atype, mtype, val, res = PHI_RESULT (phi);
 
-  if (virtual_operand_p (res) || res == main_iv)
-    {
-      gsi_next (psi);
-      return;
-    }
-
-  if (!simple_iv (loop, loop, res, &iv, true))
-    {
-      gsi_next (psi);
-      return;
-    }
-
   remove_phi_node (psi, false);
 
   atype = TREE_TYPE (res);
   mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
-  val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
+  val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv->step),
 		     fold_convert (mtype, main_iv));
   val = fold_build2 (POINTER_TYPE_P (atype)
 		     ? POINTER_PLUS_EXPR : PLUS_EXPR,
-		     atype, unshare_expr (iv.base), val);
+		     atype, unshare_expr (iv->base), val);
   val = force_gimple_operand_gsi (gsi, val, false, NULL_TREE, true,
 				  GSI_SAME_STMT);
   stmt = gimple_build_assign (res, val);
   gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
 }
 
+/* Return map of phi node result to affine_iv, for all phis in LOOPS.  */
+
+static void
+get_all_phi_affine_ivs (loop_p loop, hash_map<tree,affine_iv> *simple_ivs)
+{
+  unsigned i;
+  basic_block *bbs = get_loop_body_in_dom_order (loop);
+  gphi_iterator psi;
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = bbs[i];
+
+      if (bb->loop_father != loop)
+	continue;
+
+      for (psi = gsi_start_phis (bb); !gsi_end_p (psi);
+	   gsi_next (&psi))
+	{
+	  gphi *phi = psi.phi ();
+	  affine_iv iv;
+	  tree res = PHI_RESULT (phi);
+	  if (simple_iv (loop, loop, res, &iv, true))
+	    simple_ivs->put (res, iv);
+	}
+    }
+
+  free (bbs);
+}
+
 /* Rewrite all the phi nodes of LOOP in function of the main induction
    variable MAIN_IV.  */
 
 static void
-rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv)
+rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv,
+			       hash_map<tree,affine_iv> *simple_ivs)
 {
   unsigned i;
   basic_block *bbs = get_loop_body_in_dom_order (loop);
@@ -1486,7 +1504,25 @@ rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv)
 	continue;
 
       for (psi = gsi_start_phis (bb); !gsi_end_p (psi); )
-	rewrite_phi_with_iv (loop, &psi, &gsi, main_iv);
+	{
+	  affine_iv *iv;
+	  gphi *phi = psi.phi ();
+	  tree res = PHI_RESULT (phi);
+	  if (virtual_operand_p (res) || res == main_iv)
+	    {
+	      gsi_next (&psi);
+	      continue;
+	    }
+
+	  iv = simple_ivs->get (PHI_RESULT (phi));
+	  if (!iv)
+	    {
+	      gsi_next (&psi);
+	      continue;
+	    }
+
+	  rewrite_phi_with_iv (&psi, &gsi, main_iv, iv);
+	}
     }
 
   free (bbs);
@@ -1554,10 +1590,14 @@ canonicalize_loop_ivs (struct loop *loop, tree *nit, bool bump_in_latch)
     gsi = gsi_last_bb (loop->latch);
   else
     gsi = gsi_last_nondebug_bb (loop->header);
+
+  hash_map<tree,affine_iv> simple_ivs;
+  get_all_phi_affine_ivs (loop, &simple_ivs);
+
   create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE,
 	     loop, &gsi, bump_in_latch, &var_before, NULL);
 
-  rewrite_all_phi_nodes_with_iv (loop, var_before);
+  rewrite_all_phi_nodes_with_iv (loop, var_before, &simple_ivs);
 
   stmt = as_a <gcond *> (last_stmt (exit->src));
   /* Make the loop exit if the control condition is not satisfied.  */