[PATCH] Avoid more irreducible loops in FSM threader

[Jeff Law <law@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 679 bytes --]



This moves the check for threading through the loop latch to a point 
where we check it on every edge in the jump threading path.  Thus 
catching cases where the loop latch is in the middle of the path.

This was spotted during analysis of Andreas's report that one of the new 
tests was failing on m68k crosses.

The initial naive implementation wouldn't allow us to thread through the 
latch then to a loop exit.  Thankfully the test suite caught that case 
and complained :-)

There's some chance this will improve the codesize issues, but it's not 
explicitly targeting those issues.

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

Jeff

[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 4198 bytes --]

commit 59c44a234873fc2cad816153f14444aceb01e4f8
Author: Jeff Law <law@redhat.com>
Date:   Mon Nov 2 16:23:02 2015 -0700

    [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.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3613a68..6a7d988 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2015-11-02  Jeff Law <jeff@redhat.com>
+
+	* tree-ssa-threadupdate.c (valid_jump_thread_path): Also detect
+	cases where the loop latch edge is in the middle of an FSM
+	path.
+
 2015-11-03  Tom de Vries  <tom@codesourcery.com>
 
 	* tree-ssa-structalias.c (make_restrict_var_constraints): Rename to ...
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index a86920a..3dc4edc 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2015-11-02  Jeff Law  <law@redhat.com>
+
+	* gcc.dg/tree-ssa/ssa-thread-11.c: Verify that we do not have
+	irreducible loops in the CFG.
+
 2015-11-02  Alan Lawrence  <alan.lawrence@arm.com>
 
 	Revert:
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
index 6a076e1..a729f56 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
@@ -1,5 +1,6 @@
 /* { dg-do compile { target { ! { logical_op_short_circuit || { m68k*-*-* mep*-*-* bfin*-*-* v850*-*-* moxie*-*-* m32c*-*-* fr30*-*-* mcore*-*-* frv-*-* h8300-*-* m32r-*-* mn10300-*-* msp430-*-* pdp11-*-* rl78-*-* rx-*-* vax-*-*} } } } } */
 /* { dg-options "-O2 -fdump-tree-vrp2-details" } */
+/* { dg-final { scan-tree-dump-not "IRREDUCIBLE_LOOP" "vrp2" } } */
 /* { dg-final { scan-tree-dump "FSM" "vrp2" } } */
 
 void abort (void);
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 511433a..68650e5 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;