[PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch

[Jeff Law <law at redhat dot com>]

If I hack up GCC's old jump threader to avoid threading across backedges 
and instead let the FSM threader handle that case, then we end up with 
cases where the FSM threader creates irreducible loops with marginal 
benefit.

This can be seen in ssa-dom-thread-2{d,e,f}.c.

We've long avoided such threads in the old jump threader.  We generally 
want to avoid them in the FSM threader as well.  The only case where 
we're going to allow them is when we're able to eliminate a multi-way 
branch from the loop.

Bootstrapped and regression tested on x86_64-linux-gnu.  Also tested the 
above mentioned testcases with my hacked up compiler.

Installed on the trunk.

Jeff

commit 518690952b62c1d38b89cdbef0490a7d11f06c40
Author: Jeff Law <law@redhat.com>
Date:   Mon Oct 19 10:23:26 2015 -0600

    [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch
    
    	* tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths
    	that create irreducible loops unless the path elimiantes a multiway
    	branch.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 89a42c1..ff3d3fc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2015-10-19  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths
+	that create irreducible loops unless the path elimiantes a multiway
+	branch.
+
 2015-10-19  Richard Biener  <rguenther@suse.de>
 
 	PR tree-optimization/67975
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 5632a88..8e3437a 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2553,11 +2553,31 @@ static bool
 valid_jump_thread_path (vec<jump_thread_edge *> *path)
 {
   unsigned len = path->length ();
+  bool multiway_branch = false;
 
-  /* Check that the path is connected.  */
+  /* Check that the path is connected and see if there's a multi-way
+     branch on the path.  */
   for (unsigned int j = 0; j < len - 1; j++)
-    if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
-      return false;
+    {
+      if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
+        return false;
+      gimple *last = last_stmt ((*path)[j]->e->dest);
+      multiway_branch |= (last && gimple_code (last) == GIMPLE_SWITCH);
+    }
+
+  /* If we are trying to thread the loop latch to a block that does
+     not dominate the loop latch, then that will create an 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.  */
+  edge e = (*path)[0]->e;
+  struct loop *loop = e->dest->loop_father;
+  if (!multiway_branch
+      && loop->latch
+      && loop_latch_edge (loop) == e
+      && (determine_bb_domination_status (loop, path->last ()->e->dest)
+	  == DOMST_NONDOMINATING))
+    return false;
 
   return true;
 }
@@ -2650,7 +2670,9 @@ thread_through_all_blocks (bool may_peel_loop_headers)
       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.  */
+	     invalidated the current path or the requested jump
+	     thread might create irreducible loops which should
+	     generally be avoided.  */
 	  || !valid_jump_thread_path (path))
 	{
 	  /* Remove invalid FSM jump-thread paths.  */