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][PR tree-optimization/78856] Invalidate cached iteration information when threading across multiple loop headers



So as noted in the BZ comments the jump threading code has code that detects when a jump threading path wants to cross multiple loop headers and truncates the jump threading path in that case.

What we should have done instead is invalidate the cached loop information.

Additionally, this BZ shows that just looking at loop headers is not sufficient -- we might cross from a reducible to an irreducible region which is equivalent to crossing into another loop in that we need to invalidate the cached loop iteration information.

What's so damn funny here is that eventually we take nested loops and irreducible regions, thread various edges and end up with a nice natural loop and no irreducible regions in the end :-) But the cached iteration information is still bogus.

Anyway, this patch corrects both issues. It treats moving between an reducible and irreducible region as crossing a loop header and it invalidates the cached iteration information rather than truncating the jump thread path.

Bootstrapped and regression tested on x86_64-linux-gnu. That compiler was also used to build all the configurations in config-list.mk.

Installing on the trunk. I could be convinced to install on the gcc-6 branch as well since it's affected by the same problem.

Jeff

commit 93e3964a4664350446eefe786e3b73eb41d99036
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Wed Jan 4 05:31:23 2017 +0000

    	PR tree-optimizatin/78856
    	* tree-ssa-threadupdate.c: Include tree-vectorizer.h.
    	(mark_threaded_blocks): Remove code to truncate thread paths that
    	cross multiple loop headers.  Instead invalidate the cached loop
    	iteration information and handle case of a thread path walking
    	into an irreducible region.
    
    	PR tree-optimization/78856
    	* gcc.c-torture/execute/pr78856.c: New test.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@244045 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3114e02..6b2888f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2017-01-03  Jeff Law  <law@redhat.com>
+
+	PR tree-optimizatin/78856
+	* tree-ssa-threadupdate.c: Include tree-vectorizer.h.
+	(mark_threaded_blocks): Remove code to truncate thread paths that
+	cross multiple loop headers.  Instead invalidate the cached loop
+	iteration information and handle case of a thread path walking
+	into an irreducible region.
+
 2016-12-30  Michael Meissner  <meissner@linux.vnet.ibm.com>
 
 	PR target/78900
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index cd2a065..cadfbc9 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2017-01-03  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/78856
+	* gcc.c-torture/execute/pr78856.c: New test.
+
 2017-01-03  Michael Meissner  <meissner@linux.vnet.ibm.com>
 
 	PR target/78953
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr78856.c b/gcc/testsuite/gcc.c-torture/execute/pr78856.c
new file mode 100644
index 0000000..80f2317
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr78856.c
@@ -0,0 +1,25 @@
+extern void exit (int);
+
+int a, b, c, d, e, f[3]; 
+
+int main() 
+{
+  while (d)
+    while (1)
+      ;
+  int g = 0, h, i = 0;
+  for (; g < 21; g += 9) 
+    {
+      int j = 1;
+      for (h = 0; h < 3; h++)
+	f[h] = 1;
+      for (; j < 10; j++) {
+	d = i && (b ? 0 : c); 
+	i = 1;
+	if (g)
+	  a = e;
+      }
+  }
+  exit (0);
+}
+
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index adbb6e0..2da93a8 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "cfgloop.h"
 #include "dbgcnt.h"
 #include "tree-cfg.h"
+#include "tree-vectorizer.h"
 
 /* Given a block B, update the CFG and SSA graph to reflect redirecting
    one or more in-edges to B to instead reach the destination of an
@@ -2084,10 +2085,8 @@ mark_threaded_blocks (bitmap threaded_blocks)
   /* 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.  */
+     that invalidate the cached loop iteration information.  So we must
+     detect that case and wipe the cached information.  */
   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
     {
       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
@@ -2102,26 +2101,16 @@ mark_threaded_blocks (bitmap threaded_blocks)
 		   i++)
 		{
 		  basic_block dest = (*path)[i]->e->dest;
+		  basic_block src = (*path)[i]->e->src;
 		  crossed_headers += (dest == dest->loop_father->header);
+		  /* If we step from a block outside an irreducible region
+		     to a block inside an irreducible region, then we have
+		     crossed into a loop.  */
+		  crossed_headers += ((src->flags & BB_IRREDUCIBLE_LOOP)
+				      != (dest->flags & BB_IRREDUCIBLE_LOOP));
 		  if (crossed_headers > 1)
 		    {
-		      /* 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))
-			{
-			  delete_jump_thread_path (path);
-			  e->aux = NULL;
-			}
+		      vect_free_loop_info_assumptions (dest->loop_father);
 		      break;
 		    }
 		}

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