tree-optimization/99956 - improve loop interchange

When we apply store motion and DSE manually to the bwaves kernel
in gfortran.dg/pr81303.f loop interchange no longer happens because
the perfect nest considered covers outer loops we cannot analyze
strides for.  The following compensates for this by shrinking the
nest in this analysis which was already possible but on a too coarse
granularity.  It shares the shrinked nest with the rest of the DRs
so the complexity overhead should be negligible.

2021-04-07  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/99956
	* gimple-loop-interchange.cc (compute_access_stride):
	Try instantiating the access in a shallower loop nest
	if instantiating failed.
	(compute_access_strides): Pass adjustable loop_nest
	to compute_access_stride.

	* gfortran.dg/pr99956.f: New testcase.

1 files changed, 40 insertions, 28 deletions

diff --git a/gcc/gimple-loop-interchange.cc b/gcc/gimple-loop-interchange.cc
index f45b936..80f749b 100644
--- a/gcc/gimple-loop-interchange.cc
+++ b/gcc/gimple-loop-interchange.cc
@@ -1280,12 +1280,15 @@ tree_loop_interchange::move_code_to_inner_loop (class loop *outer,
 	   arr[i][j - 1][k] = 0;  */
 
 static void
-compute_access_stride (class loop *loop_nest, class loop *loop,
+compute_access_stride (class loop *&loop_nest, class loop *loop,
 		       data_reference_p dr)
 {
   vec<tree> *strides = new vec<tree> ();
-  basic_block bb = gimple_bb (DR_STMT (dr));
+  dr->aux = strides;
 
+  basic_block bb = gimple_bb (DR_STMT (dr));
+  if (!flow_bb_inside_loop_p (loop_nest, bb))
+    return;
   while (!flow_bb_inside_loop_p (loop, bb))
     {
       strides->safe_push (build_int_cst (sizetype, 0));
@@ -1313,39 +1316,47 @@ compute_access_stride (class loop *loop_nest, class loop *loop,
 	}
       /* Otherwise punt.  */
       else
-	{
-	  dr->aux = strides;
-	  return;
-	}
+	return;
     }
   tree scev_base = build_fold_addr_expr (ref);
   tree scev = analyze_scalar_evolution (loop, scev_base);
-  scev = instantiate_scev (loop_preheader_edge (loop_nest), loop, scev);
-  if (! chrec_contains_undetermined (scev))
+  if (chrec_contains_undetermined (scev))
+    return;
+
+  tree orig_scev = scev;
+  do
+    {
+      scev = instantiate_scev (loop_preheader_edge (loop_nest),
+			       loop, orig_scev);
+      if (! chrec_contains_undetermined (scev))
+	break;
+
+      /* If we couldn't instantiate for the desired nest, shrink it.  */
+      if (loop_nest == loop)
+	return;
+      loop_nest = loop_nest->inner;
+    } while (1);
+
+  tree sl = scev;
+  class loop *expected = loop;
+  while (TREE_CODE (sl) == POLYNOMIAL_CHREC)
     {
-      tree sl = scev;
-      class loop *expected = loop;
-      while (TREE_CODE (sl) == POLYNOMIAL_CHREC)
+      class loop *sl_loop = get_chrec_loop (sl);
+      while (sl_loop != expected)
 	{
-	  class loop *sl_loop = get_chrec_loop (sl);
-	  while (sl_loop != expected)
-	    {
-	      strides->safe_push (size_int (0));
-	      expected = loop_outer (expected);
-	    }
-	  strides->safe_push (CHREC_RIGHT (sl));
-	  sl = CHREC_LEFT (sl);
+	  strides->safe_push (size_int (0));
 	  expected = loop_outer (expected);
 	}
-      if (! tree_contains_chrecs (sl, NULL))
-	while (expected != loop_outer (loop_nest))
-	  {
-	    strides->safe_push (size_int (0));
-	    expected = loop_outer (expected);
-	  }
+      strides->safe_push (CHREC_RIGHT (sl));
+      sl = CHREC_LEFT (sl);
+      expected = loop_outer (expected);
     }
-
-  dr->aux = strides;
+  if (! tree_contains_chrecs (sl, NULL))
+    while (expected != loop_outer (loop_nest))
+      {
+	strides->safe_push (size_int (0));
+	expected = loop_outer (expected);
+      }
 }
 
 /* Given loop nest LOOP_NEST with innermost LOOP, the function computes
@@ -1363,9 +1374,10 @@ compute_access_strides (class loop *loop_nest, class loop *loop,
   data_reference_p dr;
   vec<tree> *stride;
 
+  class loop *interesting_loop_nest = loop_nest;
   for (i = 0; datarefs.iterate (i, &dr); ++i)
     {
-      compute_access_stride (loop_nest, loop, dr);
+      compute_access_stride (interesting_loop_nest, loop, dr);
       stride = DR_ACCESS_STRIDE (dr);
       if (stride->length () < num_loops)
 	{