[PATCH] Do less (redudant) constant propagation during unrolling

[Richard Biener]

The following avoids constant propagating both on a loop and its
children.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

I'm going to remove the checking code I added before committing
(and I will of course re-test).

Richard.

2018-07-10  Richard Biener  <rguenther@suse.de>

	* tree-ssa-loop-ivcanon.c (tree_unroll_loops_completely_1):
	Rework father_bb setting in a way to avoid propagating constants
	multiple times on a loop body.

diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
index c951f17f9ba..4f6080b339f 100644
--- a/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -1378,20 +1378,53 @@ tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
   enum unroll_level ul;
   unsigned num = number_of_loops (cfun);
 
+  gcc_assert (bitmap_empty_p (father_bbs));
+
   /* Process inner loops first.  Don't walk loops added by the recursive
      calls because SSA form is not up-to-date.  They can be handled in the
      next iteration.  */
+  bitmap child_father_bbs = NULL;
   for (inner = loop->inner; inner != NULL; inner = inner->next)
     if ((unsigned) inner->num < num)
-      changed |= tree_unroll_loops_completely_1 (may_increase_size,
-						 unroll_outer, father_bbs,
-						 inner);
+      {
+	if (!child_father_bbs)
+	  child_father_bbs = BITMAP_ALLOC (NULL);
+	if (tree_unroll_loops_completely_1 (may_increase_size, unroll_outer,
+					    child_father_bbs, inner))
+	  {
+	    bitmap_ior_into (father_bbs, child_father_bbs);
+	    bitmap_clear (child_father_bbs);
+	    changed = true;
+	  }
+      }
+  if (child_father_bbs)
+    BITMAP_FREE (child_father_bbs);
 
   /* If we changed an inner loop we cannot process outer loops in this
      iteration because SSA form is not up-to-date.  Continue with
      siblings of outer loops instead.  */
   if (changed)
-    return true;
+    {
+      /* If we are recorded as father clear all other fathers that
+         are necessarily covered already to avoid redundant work.  */
+      if (bitmap_bit_p (father_bbs, loop->header->index))
+	{
+	  if (flag_checking)
+	    {
+	      bitmap_iterator bi;
+	      unsigned i;
+	      EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
+		{
+		  loop_p floop = BASIC_BLOCK_FOR_FN (cfun, i)->loop_father;
+		  gcc_assert (floop == loop
+			      || flow_loop_nested_p (loop, floop));
+		}
+	    }
+	  bitmap_clear (father_bbs);
+	  bitmap_set_bit (father_bbs, loop->header->index);
+	}
+      return true;
+    }
 
   /* Don't unroll #pragma omp simd loops until the vectorizer
      attempts to vectorize those.  */
@@ -1421,7 +1454,23 @@ tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
 	 computations; otherwise, the size might blow up before the
 	 iteration is complete and the IR eventually cleaned up.  */
       if (loop_outer (loop_father))
-	bitmap_set_bit (father_bbs, loop_father->header->index);
+	{
+	  /* Once we process our father we will have processed
+	     the fathers of our children as well, so avoid doing
+	     redundant work and clear fathers we've gathered sofar.  */
+	  if (flag_checking)
+	    {
+	      bitmap_iterator bi;
+	      unsigned i;
+	      EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
+		{
+		  loop_p floop = BASIC_BLOCK_FOR_FN (cfun, i)->loop_father;
+		  gcc_assert (flow_loop_nested_p (loop_father, floop));
+		}
+	    }
+	  bitmap_clear (father_bbs);
+	  bitmap_set_bit (father_bbs, loop_father->header->index);
+	}
 
       return true;
     }