[PATCH][PR tree-optimization/68198] Avoid CFG explosion due to threading

[Jeff Law <law at redhat dot com>]

Jump threading inherently copies blocks on the jump threading path.  In 
the case of all FSM threads (and in one special case in the old 
threader), those copies have the same number of outgoing edges as the 
original block.  We don't see explosions in the old threader because 
it's just too weak to create enough of these situations.  But the FSM 
threader is a different story....

So if you have a jump threading path that passes through a block with a 
multi-way branch, but does not optimize the multi-way branch itself, 
copying can introduced many new edges in the CFG.

In the case of 68198, this resulted in tens of thousands of new edges in 
the CFG, which in turn caused a massive slowdown in later passes of the 
compiler.

The reality is if we have a multi-way branch in a jump threading path, 
but do not optimize the multi-way branch at the end of the path, then 
there it's likely we're not gaining much by optimizing that path (ie, 
the cost of the embedded multi-way branch dwarfs the gain of eliminating 
a single COND_EXPR at the end of the path).  So rather than explode the 
CFG, we simply don't allow that case to thread.

We accomplish this by distinguishing between multi-way branches at the 
end of a jump threading path (ie, those we optimize) vs multi-way 
branches that are elsewhere in the path (we pass through and thus have 
all those pesky outgoing edges).  When we have the latter without the 
former, then we disallow threading.

Bootstrapped and regression tested on x86_64-linux-gnu.  Installed on 
the trunk.

Jeff

commit c8516562e0fdd75144779bf566081a398564ddd4
Author: Jeff Law <law@redhat.com>
Date:   Wed Nov 18 17:31:05 2015 -0700

    [PATCH][PR tree-optimization/68198] Avoid CFG explosion due to threading
    
    	PR tree-optimization/68198
    	* tree-ssa-threadupdate.c (valid_jump_thread_path): Distinguish
    	between threading a multi-way branch and a thread path that contains
    	a multi-way branch.  Disallow the case where a path contains a
    	multi-way branch and does not thread a multi-way branch.
    	(thread_through_all_blocks): Update comment.
    
            PR tree-optimization/68198
    	* gcc.dg/tree-ssa/pr66752-3.c: Update expected output for VRP1.
    	* gcc.dg/tree-ssa/pr68198.c: New test.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4b788d3..26ddccc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2015-11-18  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/68198
+	* tree-ssa-threadupdate.c (valid_jump_thread_path): Distinguish
+	between threading a multi-way branch and a thread path that contains
+	a multi-way branch.  Disallow the case where a path contains a
+	multi-way branch and does not thread a multi-way branch.
+	(thread_through_all_blocks): Update comment.
+
 2015-11-18  Joseph Myers  <joseph@codesourcery.com>
 
 	PR c/65083
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 8109c33..48f536f 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2015-11-18  Jeff Law  <law@redhat.com>
+
+        PR tree-optimization/68198
+	* gcc.dg/tree-ssa/pr66752-3.c: Update expected output for VRP1.
+	* gcc.dg/tree-ssa/pr68198.c: New test.
+
 2015-11-18  Steven G. Kargl  <kargl@gcc.gnu.org>
 
 	PR fortran/59910
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c
index 577a489..1f27b1a 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c
@@ -32,8 +32,10 @@ foo (int N, int c, int b, int *a)
    pt--;
 }
 
-/* There are 3 FSM jump threading opportunities.  */
-/* { dg-final { scan-tree-dump-times "FSM" 3 "vrp1"} } */
+/* There are 3 FSM jump threading opportunities, one of which will
+   get cancelled.  */
+/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "vrp1"} } */
+/* { dg-final { scan-tree-dump-times "Cancelling FSM" 1 "vrp1"} } */
 
 /* There should be no assignments or references to FLAG.  */
 /* { dg-final { scan-tree-dump-not "flag" "optimized"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c
new file mode 100644
index 0000000..ddd3c76
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+
+extern void abort (void);
+
+typedef union tree_node *tree;
+union tree_node
+{
+  int code;
+  tree chain;
+  int omp_code;
+}
+bitmap_head;
+
+extern int c_omp_predetermined_sharing (tree);
+
+tree
+c_finish_omp_clauses (tree clauses)
+{
+  tree c, t, *pc = &clauses;
+  for (pc = &clauses, c = clauses; c; c = *pc)
+    {
+      unsigned char remove = 0;
+      switch (((c->omp_code)))
+	{
+	case 1:
+	  if (t->code != 42)
+	    remove = 1;
+	  switch (c_omp_predetermined_sharing (t))
+	    {
+	    case 2:
+	      abort ();
+	    }
+	}
+      if (remove)
+	*pc = c->chain;
+    }
+}
+
+/* There are 3 FSM jump threading opportunities, two of which will
+  get cancelled.  */
+/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "vrp1"} } */
+/* { dg-final { scan-tree-dump-times "Cancelling FSM" 2 "vrp1"} } */
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index c527206..3dd0e4f 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2370,11 +2370,13 @@ static bool
 valid_jump_thread_path (vec<jump_thread_edge *> *path)
 {
   unsigned len = path->length ();
-  bool multiway_branch = false;
+  bool threaded_multiway_branch = false;
+  bool multiway_branch_in_path = false;
   bool threaded_through_latch = false;
 
   /* Check that the path is connected and see if there's a multi-way
-     branch on the path.  */
+     branch on the path and whether or not a multi-way branch
+     is threaded.  */
   for (unsigned int j = 0; j < len - 1; j++)
     {
       edge e = (*path)[j]->e;
@@ -2394,7 +2396,12 @@ valid_jump_thread_path (vec<jump_thread_edge *> *path)
 	threaded_through_latch = true;
 
       gimple *last = last_stmt (e->dest);
-      multiway_branch |= (last && gimple_code (last) == GIMPLE_SWITCH);
+      if (j == len - 2)
+	threaded_multiway_branch
+	  |= (last && gimple_code (last) == GIMPLE_SWITCH);
+      else
+	multiway_branch_in_path
+	  |= (last && gimple_code (last) == GIMPLE_SWITCH);
     }
 
   /* If we are trying to thread through the loop latch to a block in the
@@ -2402,8 +2409,33 @@ valid_jump_thread_path (vec<jump_thread_edge *> *path)
      irreducible loop.  We avoid that unless the jump thread has a multi-way
      branch, in which case we have deemed it worth losing other
      loop optimizations later if we can eliminate the multi-way branch.  */
-  if (!multiway_branch && threaded_through_latch)
-    return false;
+  if (!threaded_multiway_branch && threaded_through_latch)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file,
+		   "Thread through latch without threading a multiway "
+		   "branch.\n");
+	  dump_jump_thread_path (dump_file, *path, false);
+	}
+      return false;
+    }
+
+  /* When there is a multi-way branch on the path, then threading can
+     explode the CFG due to duplicating the edges for that multi-way
+     branch.  So like above, only allow a multi-way branch on the path
+     if we actually thread a multi-way branch.  */
+  if (!threaded_multiway_branch && multiway_branch_in_path)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file,
+		   "Thread through multiway branch without threading "
+		   "a multiway branch.\n");
+	  dump_jump_thread_path (dump_file, *path, false);
+	}
+      return false;
+    }
 
   return true;
 }
@@ -2494,11 +2526,8 @@ thread_through_all_blocks (bool may_peel_loop_headers)
 
       /* Do not jump-thread twice from the same block.  */
       if (bitmap_bit_p (threaded_blocks, entry->src->index)
-	  /* Verify that the jump thread path is still valid: a
-	     previous jump-thread may have changed the CFG, and
-	     invalidated the current path or the requested jump
-	     thread might create irreducible loops which should
-	     generally be avoided.  */
+	  /* We may not want to realize this jump thread path
+	     for various reasons.  So check it first.  */
 	  || !valid_jump_thread_path (path))
 	{
 	  /* Remove invalid FSM jump-thread paths.  */