This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] FIx pr58640



The problem shown by pr58640 is the more aggressive jump threading is recording a jump threading opportunity that crosses through two loop headers.

The updating code is not prepared to update the CFG and loop structures in that situation. The net result is we have two latch edges for a particular loop. This causes the full unrolling code to go a bit nuts with a particular block is considered unreachable and has no outgoing edges. It is (of course) reachable and falling off the end of the block results in bad things happening.

The easiest fix would be to simply cancel the jump threading request entirely. However, we can do better by merely truncating the request immediately prior to crossing the second loop entry point.

In fact, the code we generate for pr58640 is considerably better when we truncate the path rather than eliminating the jump threading request entirely.

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

commit 7aec1a83e5c18ddb0f053b28f62a1c242ab9e477
Author: Jeff Law <law@redhat.com>
Date:   Fri Oct 11 14:24:11 2013 -0600

    	PR tree-optimization/58640
    	* tree-ssa-threadupdate.c (mark_threaded_blocks): Truncate jump threading
    	paths that cross over two loop entry points.
    
    	* gcc.c-torture/execute/pr58640.c: New test.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 41e29dc..9f4e297 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2013-10-11  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/58640
+	* tree-ssa-threadupdate.c (mark_threaded_blocks): Truncate jump threading
+	paths that cross over two loop entry points.
+
 2013-10-11  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
 
 	* config/rs6000/vsx.md (*vsx_le_perm_load_v2di): Generalize to
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 87ff2a7..bb2ede4 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2013-10-11  Jeff Law  <law@redhat.com>
+
+	* gcc.c-torture/execute/pr58640.c: New test.
+
 2013-10-11  Paolo Carlini  <paolo.carlini@oracle.com>
 
 	PR c++/58633
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr58640.c b/gcc/testsuite/gcc.c-torture/execute/pr58640.c
new file mode 100644
index 0000000..7786b8d
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr58640.c
@@ -0,0 +1,32 @@
+int a, b, c, d = 1, e;
+
+static signed char
+foo ()
+{
+  int f, g = a;
+
+  for (f = 1; f < 3; f++)
+    for (; b < 1; b++)
+      {
+        if (d)
+          for (c = 0; c < 4; c++)
+            for (f = 0; f < 3; f++)
+              {
+                for (e = 0; e < 1; e++)
+                  a = g;
+                if (f)
+                  break;
+              }
+        else if (f)
+          continue;
+        return 0;
+      }
+  return 0;
+}
+
+int
+main ()
+{
+  foo ();
+  exit (0);
+}
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 2adea1b..3e34567 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -1354,6 +1354,68 @@ mark_threaded_blocks (bitmap threaded_blocks)
   else
     bitmap_copy (threaded_blocks, tmp);
 
+  /* Look for jump threading paths which cross multiple loop headers.
+
+     The code to thread through loop headers will change the CFG in ways
+     that break assumptions made by the loop optimization code.
+
+     We don't want to blindly cancel the requests.  We can instead do better
+     by trimming off the end of the jump thread path.  */
+  EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
+    {
+      basic_block bb = BASIC_BLOCK (i);
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  if (e->aux)
+	    {
+	      vec<jump_thread_edge *> *path = THREAD_PATH (e);
+
+	      /* Basically we're looking for a situation where we can see
+	  	 3 or more loop structures on a jump threading path.  */
+
+	      struct loop *first_father = (*path)[0]->e->src->loop_father;
+	      struct loop *second_father = NULL;
+	      for (unsigned int i = 0; i < path->length (); i++)
+		{
+		  /* See if this is a loop father we have not seen before.  */
+		  if ((*path)[i]->e->dest->loop_father != first_father
+		      && (*path)[i]->e->dest->loop_father != second_father)
+		    {
+		      /* We've already seen two loop fathers, so we
+			 need to trim this jump threading path.  */
+		      if (second_father != NULL)
+			{
+			  /* Trim from entry I onwards.  */
+			  for (unsigned int j = i; j < path->length (); j++)
+			    delete (*path)[j];
+			  path->truncate (i);
+
+			  /* Now that we've truncated the path, make sure
+			     what's left is still valid.   We need at least
+			     two edges on the path and the last edge can not
+			     be a joiner.  This should never happen, but let's
+			     be safe.  */
+			  if (path->length () < 2
+			      || (path->last ()->type
+				  == EDGE_COPY_SRC_JOINER_BLOCK))
+			    {
+			      for (unsigned int i = 0; i < path->length (); i++)
+				delete (*path)[i];
+			      path->release ();
+			      e->aux = NULL;
+			    }
+			  break;
+			}
+		      else
+			{
+			  second_father = (*path)[i]->e->dest->loop_father;
+			}
+		    }
+		}
+	    }
+	}
+    }
+
   BITMAP_FREE (tmp);
 }
 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]