[PATCH] Avoid more irreducible loops in FSM threader

	* tree-ssa-threadupdate.c (valid_jump_thread_path): Also detect
	cases where the loop latch edge is in the middle of an FSM
	path.

	* gcc.dg/tree-ssa/ssa-thread-11.c: Verify that we do not have
	irreducible loops in the CFG.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@229685 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 21 insertions, 12 deletions

diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 511433aa76a..68650e598fe 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2547,29 +2547,38 @@ valid_jump_thread_path (vec<jump_thread_edge *> *path)
 {
   unsigned len = path->length ();
   bool multiway_branch = false;
+  bool threaded_through_latch = false;
 
   /* 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)
+      edge e = (*path)[j]->e;
+      struct loop *loop = e->dest->loop_father;
+
+      if (e->dest != (*path)[j+1]->e->src)
         return false;
-      gimple *last = last_stmt ((*path)[j]->e->dest);
+
+      /* If we're threading through the loop latch back into the
+	 same loop and the destination does not dominate the loop
+	 latch, then this thread would create an irreducible loop.  */
+      if (loop->latch
+	  && loop_latch_edge (loop) == e
+	  && loop == path->last()->e->dest->loop_father
+	  && (determine_bb_domination_status (loop, path->last ()->e->dest)
+	       == DOMST_NONDOMINATING))
+	threaded_through_latch = true;
+
+      gimple *last = last_stmt (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
+  /* If we are trying to thread through the loop latch to a block in the
+     loop 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))
+  if (!multiway_branch && threaded_through_latch)
     return false;
 
   return true;