Patchwork More threading cleanups

login
register
mail settings
Submitter Jeff Law
Date Oct. 23, 2013, 1:55 p.m.
Message ID <5267D562.5090900@redhat.com>
Download mbox | patch
Permalink /patch/285674/
State New
Headers show

Comments

Jeff Law - Oct. 23, 2013, 1:55 p.m.
During testing of the generalized FSA opt I ran into a case where we 
tried to thread through a joiner with abnormal outgoing edges.  Since we 
can't reliably clone the joiner and redirect just one of its outgoing 
edges in this case, we need to avoid even trying to thread through such 
blocks.

While looking at that I realized we don't need the code to filter out 
jump threading opportunities involving joiner blocks.  We can avoid the 
unnecessary duplication by first handling all the jump threads which do 
not require a joiner block, then handling the jump threads which do 
require a joiner block.

Finally, I was able to look at a dangling AUX field problem that I've 
seen a few times.  While I haven't seen it on the trunk, I believe it's 
just latent.  When we thread the latch edge to an exit edge, we clear 
loop->header.  If we had another thread path into that same loop from 
outside, the second thread path will be ignored because loop->header is 
NULL.  This leaves a dangling edge AUX field, which we need to clear.

All three issues are addressed by this patch.  Bootstrapped and 
regression tested on x86_64-unknown-linux-gnu.  Installed on the trunk.
commit 9e33df4427bf4e13c32d3296fcdc1ee1b1fd7bfa
Author: Jeff Law <law@redhat.com>
Date:   Wed Oct 23 07:53:46 2013 -0600

    	* tree-ssa-threadedge.c (thread_across_edge): Do not allow threading
    	through joiner blocks with abnormal outgoing edges.
    
    	* tree-ssa-threadupdate.c (thread_block_1): Renamed from thread_block.
    	Add parameter JOINERS, to allow/disallow threading through joiner
    	blocks.
    	(thread_block): New.  Call thread_block_1.
    	(mark_threaded_blocks): Remove code to filter out certain cases
    	of threading through joiner blocks.
    	(thread_through_all_blocks): Document how we can have a dangling
    	edge AUX field and clear it.

Patch

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 6132515..acd6620 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@ 
+2013-10-23  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-threadedge.c (thread_across_edge): Do not allow threading
+	through joiner blocks with abnormal outgoing edges.
+
+	* tree-ssa-threadupdate.c (thread_block_1): Renamed from thread_block.
+	Add parameter JOINERS, to allow/disallow threading through joiner
+	blocks.
+	(thread_block): New.  Call thread_block_1.
+	(mark_threaded_blocks): Remove code to filter out certain cases
+	of threading through joiner blocks.
+	(thread_through_all_blocks): Document how we can have a dangling
+	edge AUX field and clear it.
+
 2013-10-23  Ian Lance Taylor  <iant@google.com>
 
 	* doc/invoke.texi (Option Summary): Remove -fno-default-inline.
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index bbc4f9b..810908b 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -1040,6 +1040,16 @@  thread_across_edge (gimple dummy_cond,
     edge_iterator ei;
     bool found;
 
+    /* If E->dest has abnormal outgoing edges, then there's no guarantee
+       we can safely redirect any of the edges.  Just punt those cases.  */
+    FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
+      if (taken_edge->flags & EDGE_ABNORMAL)
+	{
+	  remove_temporary_equivalences (stack);
+	  BITMAP_FREE (visited);
+	  return;
+	}
+
     /* Look at each successor of E->dest to see if we can thread through it.  */
     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
       {
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index bde81a8..1027191 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -616,10 +616,12 @@  redirection_block_p (basic_block bb)
    the appropriate duplicate of BB.
 
    If NOLOOP_ONLY is true, we only perform the threading as long as it
-   does not affect the structure of the loops in a nontrivial way.  */
+   does not affect the structure of the loops in a nontrivial way. 
+
+   If JOINERS is true, then thread through joiner blocks as well.  */
 
 static bool
-thread_block (basic_block bb, bool noloop_only)
+thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
 {
   /* E is an incoming edge into BB that we may or may not want to
      redirect to a duplicate of BB.  */
@@ -642,7 +644,9 @@  thread_block (basic_block bb, bool noloop_only)
       e = loop_latch_edge (loop);
       vec<jump_thread_edge *> *path = THREAD_PATH (e);
 
-      if (path)
+      if (path
+	  && (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && joiners)
+	      || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && !joiners)))
 	{
 	  for (unsigned int i = 1; i < path->length (); i++)
 	    {
@@ -666,6 +670,11 @@  thread_block (basic_block bb, bool noloop_only)
 	continue;
 
       vec<jump_thread_edge *> *path = THREAD_PATH (e);
+
+      if (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && !joiners)
+	  || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && joiners))
+	continue;
+
       e2 = path->last ()->e;
       if (!e2 || noloop_only)
 	{
@@ -762,6 +771,24 @@  thread_block (basic_block bb, bool noloop_only)
   return local_info.jumps_threaded;
 }
 
+/* Wrapper for thread_block_1 so that we can first handle jump
+   thread paths which do not involve copying joiner blocks, then
+   handle jump thread paths which have joiner blocks.
+
+   By doing things this way we can be as aggressive as possible and
+   not worry that copying a joiner block will create a jump threading
+   opportunity.  */
+  
+static bool
+thread_block (basic_block bb, bool noloop_only)
+{
+  bool retval;
+  retval = thread_block_1 (bb, noloop_only, false);
+  retval |= thread_block_1 (bb, noloop_only, true);
+  return retval;
+}
+
+
 /* Threads edge E through E->dest to the edge THREAD_TARGET (E).  Returns the
    copy of E->dest created during threading, or E->dest if it was not necessary
    to copy it (E is its single predecessor).  */
@@ -1240,57 +1267,14 @@  mark_threaded_blocks (bitmap threaded_blocks)
   edge e;
   edge_iterator ei;
 
-  /* It is possible to have jump threads in which one is a subpath
-     of the other.  ie, (A, B), (B, C), (C, D) where B is a joiner
-     block and (B, C), (C, D) where no joiner block exists.
-
-     When this occurs ignore the jump thread request with the joiner
-     block.  It's totally subsumed by the simpler jump thread request.
-
-     This results in less block copying, simpler CFGs.  More importantly,
-     when we duplicate the joiner block, B, in this case we will create
-     a new threading opportunity that we wouldn't be able to optimize
-     until the next jump threading iteration.
-
-     So first convert the jump thread requests which do not require a
-     joiner block.  */
+  /* Move the jump threading requests from PATHS to each edge
+     which starts a jump thread path.  */
   for (i = 0; i < paths.length (); i++)
     {
       vec<jump_thread_edge *> *path = paths[i];
-
-      if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
-	{
-	  edge e = (*path)[0]->e;
-	  e->aux = (void *)path;
-	  bitmap_set_bit (tmp, e->dest->index);
-	}
-    }
-
-  /* Now iterate again, converting cases where we want to thread
-     through a joiner block, but only if no other edge on the path
-     already has a jump thread attached to it.  */
-  for (i = 0; i < paths.length (); i++)
-    {
-      vec<jump_thread_edge *> *path = paths[i];
-
-      
-      if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
-	{
-	  unsigned int j;
-
-	  for (j = 0; j < path->length (); j++)
-	    if ((*path)[j]->e->aux != NULL)
-	      break;
-
-	  /* If we iterated through the entire path without exiting the loop,
-	     then we are good to go, attach the path to the starting edge.  */
-	  if (j == path->length ())
-	    {
-	      edge e = (*path)[0]->e;
-	      e->aux = path;
-	      bitmap_set_bit (tmp, e->dest->index);
-	    }
-	}
+      edge e = (*path)[0]->e;
+      e->aux = (void *)path;
+      bitmap_set_bit (tmp, e->dest->index);
     }
 
   /* If we have a joiner block (J) which has two successors S1 and S2 and
@@ -1488,6 +1472,39 @@  thread_through_all_blocks (bool may_peel_loop_headers)
       retval |= thread_through_loop_header (loop, may_peel_loop_headers);
     }
 
+  /* Assume we had a jump thread path which went from the latch to the exit
+     and a path which goes from outside to inside the same loop.  
+
+     If the latch to exit was handled first, we will thread it and clear
+     loop->header.
+
+     The second path will be ignored by thread_block because we're going
+     through a loop header.  It will also be ignored by the loop above
+     because loop->header is NULL.
+
+     This results in the second path never being threaded.  The failure
+     mode is a dangling AUX field.
+
+     This is inherently a bit of a pain to fix, so we just walk all the
+     blocks and all the incoming edges to those blocks and clear their
+     AUX fields.  */
+  basic_block bb;
+  edge_iterator ei;
+  edge e;
+  FOR_EACH_BB (bb)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (e->aux)
+	  {
+	    vec<jump_thread_edge *> *path = THREAD_PATH (e);
+
+	    for (unsigned int i = 0; i < path->length (); i++)
+	      delete (*path)[i];
+	    path->release ();
+	    e->aux = NULL;
+ 	  }
+    }
+
   statistics_counter_event (cfun, "Jumps threaded",
 			    thread_stats.num_threaded_edges);