From 82ff7e3426ea926d090777173977f8bedd086816 Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Fri, 30 Oct 2020 13:32:32 +0100
Subject: [PATCH] tree-optimization/97623 - avoid excessive insert iteration
 for hoisting

This avoids requiring insert iteration for back-to-back hoisting
opportunities as seen in the added testcase.  For the PR at hand
this halves the number of insert iterations retaining only
the hard to avoid PRE / hoist insert back-to-backs.

2020-10-30  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/97623
	* tree-ssa-pre.c (insert): First do hoist insertion in
	a backward walk.

	* gcc.dg/tree-ssa/ssa-hoist-7.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-hoist-7.c | 54 +++++++++++++++++++++
 gcc/tree-ssa-pre.c                          | 13 +++--
 2 files changed, 63 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-hoist-7.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-hoist-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-hoist-7.c
new file mode 100644
index 00000000000..ce9cec61668
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-hoist-7.c
@@ -0,0 +1,54 @@
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+
+void baz();
+int tem;
+void foo (int a, int b, int c, int d, int e, int x, int y, int z)
+{
+  if (a)
+    {
+      if (b)
+        {
+          if (c)
+            {
+	      if (d)
+		{
+		  if (e)
+		    {
+		      tem = x + y;
+		    }
+		  else
+		    {
+		      if (z) baz ();
+		      tem = x + y;
+		    }
+		}
+	      else
+		{
+		  if (z) baz ();
+		  tem = x + y;
+		}
+	    }
+          else
+            {
+              if (z) baz ();
+              tem = x + y;
+            }
+        }
+      else
+        {
+          if (z) baz ();
+          tem = x + y;
+        }
+    }
+  else
+    {
+      if (z) baz ();
+      tem = x + y;
+    }
+}
+
+/* Now inserting x + y five times is unnecessary but the cascading
+   cannot be avoided with the simple-minded dataflow.  But make sure
+   we do the insertions all in the first iteration.  */
+/* { dg-final { scan-tree-dump "insert iterations == 2" "pre" } } */
+/* { dg-final { scan-tree-dump "HOIST inserted: 5" "pre" } } */
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index bcef9720095..091ecb39bb6 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3646,6 +3646,15 @@ insert (void)
 	fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
 
       changed = false;
+      /* Insert expressions for hoisting.  Do a backward walk here since
+	 inserting into BLOCK exposes new opportunities in its predecessors.  */
+      if (flag_code_hoisting)
+	for (int idx = rpo_num - 1; idx >= 0; --idx)
+	  {
+	    basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
+	    if (EDGE_COUNT (block->succs) >= 2)
+	      changed |= do_hoist_insertion (block);
+	  }
       for (int idx = 0; idx < rpo_num; ++idx)
 	{
 	  basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
@@ -3680,10 +3689,6 @@ insert (void)
 		  if (do_partial_partial)
 		    changed |= do_pre_partial_partial_insertion (block, dom);
 		}
-
-	      /* Insert expressions for hoisting.  */
-	      if (flag_code_hoisting && EDGE_COUNT (block->succs) >= 2)
-		changed |= do_hoist_insertion (block);
 	    }
 	}
 
-- 
2.30.2