[RFA] [PR tree-optimization/71661] Fix forwarder removal when new loops are exposed

[Jeff Law]

Removal of forwarder blocks is a two step process.

First we build a worklist of potential forwarder blocks,  Then we 
iterate over that worklist attempting to remove each potential forwarder 
block in the worklist.

The code which builds the worklist is aware that we do not want to 
remove a forwarder that is a loop header and avoids putting such blocks 
into the worklist.

The problem is that removing a forwarder block may turn an irreducible 
region into a natural loop, which of course will have a loop header. 
But that loop header could not be recognized as such during the initial 
building of the worklist.

So as a result if removal of a forwarder block exposes a new loop and 
the header of that newly exposed loop appears to be a forwarder block, 
we may forward through the newly exposed loop header too.  That can 
squash two loops into a single loop, which invalidates the cached 
iteration information and other stuff which can in turn cause incorrect 
code generation (as seen by 71661).

There's two ways to address this problem.  First we could invalidate the 
cached loop info when this situation occurs.  Second, we could avoid 
forwarding through the newly exposed loop header.

The patch takes the latter approach.  Based on the CFG transformations 
for 71661, I think we're better off leaving the newly exposed loop alone 
-- we've exposed a nice simple loop nest, collapsing the nest into a 
single loop with multiple latch edges just seems wrong.

Bootstrapped and regression tested on x86_64-linux.gnu.  OK for the trunk?

Jeff
-------------- next part --------------
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 2b56878..33ee250 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2016-10-05  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/71661
+	* tree-cfgcleanup.c (remove_forwarder_block): Handle case when removal
+	of a forwarder exposes a new natural loop.
+	(remove_forwarder_block_with_phi): Likewise.
+
 2016-10-05  Martin Sebor  <msebor@redhat.com>
 
 	PR bootstrap/77819
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index fa1f310..3bba95d 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2016-10-05  Jeff Law  <law@redhat.com>
+
+        PR tree-optimization/71661
+	* gcc.dg/tree-ssa/pr71661.c: New test.
+
 2016-10-05  Richard Biener  <rguenther@suse.de>
 
 	PR middle-end/77826
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71661.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71661.c
new file mode 100644
index 0000000..c273ea1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71661.c
@@ -0,0 +1,31 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -fdisable-tree-ethread" } */
+
+extern void exit (int);
+
+int a, b;
+
+void
+fn1 ()
+{
+  unsigned c = 0;
+  int d;
+  b = a;
+  if (a < 0)
+    goto L1;
+  for (; a < 1; a++)
+    d = 0;
+  for (; d < 2; d++)
+    {
+      for (c = 0; c < 3; c++)
+      L1:
+        a = 2;
+    }
+}
+
+int
+main ()
+{
+  fn1 ();
+  exit (0);
+}
diff --git a/gcc/tree-cfgcleanup.c b/gcc/tree-cfgcleanup.c
index 6052872..e3cb8ee 100644
--- a/gcc/tree-cfgcleanup.c
+++ b/gcc/tree-cfgcleanup.c
@@ -418,6 +418,11 @@ remove_forwarder_block (basic_block bb)
   if (dest == bb)
     return false;
 
+  /* Removal of forwarders may expose new natural loops and thus
+     a block may turn into a loop header.  */
+  if (current_loops && bb_loop_header_p (bb))
+    return false;
+
   /* If the destination block consists of a nonlocal label or is a
      EH landing pad, do not merge it.  */
   label = first_stmt (dest);
@@ -840,6 +845,11 @@ remove_forwarder_block_with_phi (basic_block bb)
   if (dest == bb)
     return false;
 
+  /* Removal of forwarders may expose new natural loops and thus
+     a block may turn into a loop header.  */
+  if (current_loops && bb_loop_header_p (bb))
+    return false;
+
   /* If the destination block consists of a nonlocal label, do not
      merge it.  */
   label = first_stmt (dest);