[PATCH] Make jump thread path carry more information

[Jeff Law <law at redhat dot com>]

This patch conveys information about the blocks/edges in a jump 
threading path.  Of particular interest is information about the source 
block in each edge of the path -- the nature of the block determines our 
copy strategy (empty -- no copy, normal copy, joiner copy).

Rather than rediscover the nature of those blocks during the CFG/SSA 
graph updating, it's easier to just attach the information to each edge 
in the path.  That's precisely what this patch does.

The SSA/CFG updating code isn't making much use of this yet, that's a 
follow-on change.  This change is strictly designed to get the 
information into the updating code.


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




diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 5adbaeb..8871aca 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,26 @@
+2013-09-25  Jeff Law  <law@redhat.com>
+
+	* tree-flow.h (thread_through_all_blocks): Prototype moved into
+	tree-ssa-threadupdate.h.
+	(register_jump_thread): Similarly.
+	* tree-ssa-threadupdate.h: New header file.
+	* tree-ssa-dom.c: Include tree-ssa-threadupdate.h.
+	* tree-vrp.c: Likewise.
+	* tree-ssa-threadedge.c: Include tree-ssa-threadupdate.h.
+	(thread_around_empty_blocks): Change type of path vector argument to
+	an edge,type pair from just an edge.  Initialize both elements when
+	appending to a jump threading path.  Tweak references to elements
+	appropriately.
+	(thread_across_edge): Similarly.  Release memory for the elements
+	as needed.
+	* tree-ssa-threadupdate.c: Include tree-ssa-threadupdate.h.
+	(dump_jump_thread_path): New function broken out from
+	register_jump_thread.
+	(register_jump_thread): Use dump_jump_thread_path.  Change type of
+	path vector entries.  Search the path for NULL edges and dump
+	the path if one is found.  Tweak the conversion of path to 3-edge
+	form to use the block copy type information embedded in the path.
+
 2013-09-25  Yvan Roux  <yvan.roux@linaro.org>
 
 	* lra.c (update_inc_notes): Remove all REG_DEAD and REG_UNUSED notes.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 634e747..a264056 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,6 @@
+2013-09-25  Jeff Law  <law@redhat.com>
+
+	* gcc.dg/tree-ssa/ssa-dom-thread-3.c: Update expected output.
 2013-09-25  Tobias Burnus  <burnus@net-b.de>
 
 	PR fortran/58436
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
index d2a1fbb..222a97b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
@@ -43,7 +43,6 @@ expand_one_var (tree var, unsigned char toplevel, unsigned char really_expand)
 }
 /* We should thread the jump, through an intermediate block.  */
 /* { dg-final { scan-tree-dump-times "Threaded" 1 "dom1"} } */
-/* { dg-final { scan-tree-dump-times "Registering jump thread .through joiner block.: \\(.*\\);  \\(.*\\);  \\(.*\\);" 1 "dom1"} } */
-
+/* { dg-final { scan-tree-dump-times "Registering jump thread: \\(.*\\) incoming edge;  \\(.*\\) joiner;  \\(.*\\) nocopy;" 1 "dom1"} } */
 /* { dg-final { cleanup-tree-dump "dom1" } } */
 
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 2f64abc..ee69179 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -641,10 +641,6 @@ bool multiplier_allowed_in_address_p (HOST_WIDE_INT, enum machine_mode,
 				      addr_space_t);
 bool may_be_nonaddressable_p (tree expr);
 
-/* In tree-ssa-threadupdate.c.  */
-extern bool thread_through_all_blocks (bool);
-extern void register_jump_thread (vec<edge>, bool);
-
 /* In gimplify.c  */
 tree force_gimple_operand_1 (tree, gimple_seq *, gimple_predicate, tree);
 tree force_gimple_operand (tree, gimple_seq *, bool, tree);
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index f0cc0ee..81119c3 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "domwalk.h"
 #include "tree-pass.h"
 #include "tree-ssa-propagate.h"
+#include "tree-ssa-threadupdate.h"
 #include "langhooks.h"
 #include "params.h"
 
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 2ca56342..467d982 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -32,6 +32,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "dumpfile.h"
 #include "tree-ssa.h"
 #include "tree-ssa-propagate.h"
+#include "tree-ssa-threadupdate.h"
 #include "langhooks.h"
 #include "params.h"
 
@@ -753,7 +754,7 @@ thread_around_empty_blocks (edge taken_edge,
 			    bool handle_dominating_asserts,
 			    tree (*simplify) (gimple, gimple),
 			    bitmap visited,
-			    vec<edge> *path)
+			    vec<jump_thread_edge *> *path)
 {
   basic_block bb = taken_edge->dest;
   gimple_stmt_iterator gsi;
@@ -791,8 +792,10 @@ thread_around_empty_blocks (edge taken_edge,
 	  if ((taken_edge->flags & EDGE_DFS_BACK) == 0
 	      && !bitmap_bit_p (visited, taken_edge->dest->index))
 	    {
+	      jump_thread_edge *x
+		= new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+	      path->safe_push (x);
 	      bitmap_set_bit (visited, taken_edge->dest->index);
-	      path->safe_push (taken_edge);
 	      return thread_around_empty_blocks (taken_edge,
 						 dummy_cond,
 						 handle_dominating_asserts,
@@ -828,7 +831,11 @@ thread_around_empty_blocks (edge taken_edge,
       if (bitmap_bit_p (visited, taken_edge->dest->index))
 	return false;
       bitmap_set_bit (visited, taken_edge->dest->index);
-      path->safe_push (taken_edge);
+
+      jump_thread_edge *x
+	= new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+      path->safe_push (x);
+
       thread_around_empty_blocks (taken_edge,
 				  dummy_cond,
 				  handle_dominating_asserts,
@@ -922,9 +929,13 @@ thread_across_edge (gimple dummy_cond,
 	  if (dest == NULL || dest == e->dest)
 	    goto fail;
 
-	  vec<edge> path = vNULL;
-	  path.safe_push (e);
-	  path.safe_push (taken_edge);
+	  vec<jump_thread_edge *> path = vNULL;
+          jump_thread_edge *x
+	    = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
+	  path.safe_push (x);
+
+	  x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
+	  path.safe_push (x);
 
 	  /* See if we can thread through DEST as well, this helps capture
 	     secondary effects of threading without having to re-run DOM or
@@ -947,8 +958,11 @@ thread_across_edge (gimple dummy_cond,
 	    }
 
 	  remove_temporary_equivalences (stack);
-	  propagate_threaded_block_debug_into (path.last ()->dest, e->dest);
-	  register_jump_thread (path, false);
+	  propagate_threaded_block_debug_into (path.last ()->e->dest,
+					       e->dest);
+	  register_jump_thread (path);
+	  for (unsigned int i = 0; i < path.length (); i++)
+	    delete path[i];
 	  path.release ();
 	  return;
 	}
@@ -978,15 +992,18 @@ thread_across_edge (gimple dummy_cond,
 	bitmap_clear (visited);
 	bitmap_set_bit (visited, taken_edge->dest->index);
 	bitmap_set_bit (visited, e->dest->index);
-        vec<edge> path = vNULL;
+        vec<jump_thread_edge *> path = vNULL;
 
 	/* Record whether or not we were able to thread through a successor
 	   of E->dest.  */
-	path.safe_push (e);
-	path.safe_push (taken_edge);
+        jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
+	path.safe_push (x);
+
+        x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
+	path.safe_push (x);
 	found = false;
 	if ((e->flags & EDGE_DFS_BACK) == 0
-	    || ! cond_arg_set_in_bb (path.last (), e->dest))
+	    || ! cond_arg_set_in_bb (path.last ()->e, e->dest))
 	  found = thread_around_empty_blocks (taken_edge,
 					      dummy_cond,
 					      handle_dominating_asserts,
@@ -998,11 +1015,13 @@ thread_across_edge (gimple dummy_cond,
 	   record the jump threading opportunity.  */
 	if (found)
 	  {
-	    propagate_threaded_block_debug_into (path.last ()->dest,
+	    propagate_threaded_block_debug_into (path.last ()->e->dest,
 						 taken_edge->dest);
-	    register_jump_thread (path, true);
+	    register_jump_thread (path);
 	  }
 
+	for (unsigned int i = 0; i < path.length (); i++)
+	  delete path[i];
         path.release();
       }
     BITMAP_FREE (visited);
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index fd5234c..75273ca 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -27,6 +27,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "basic-block.h"
 #include "function.h"
 #include "tree-ssa.h"
+#include "tree-ssa-threadupdate.h"
 #include "dumpfile.h"
 #include "cfgloop.h"
 #include "hash-table.h"
@@ -1380,6 +1381,39 @@ thread_through_all_blocks (bool may_peel_loop_headers)
   return retval;
 }
 
+/* Dump a jump threading path, including annotations about each
+   edge in the path.  */
+
+static void
+dump_jump_thread_path (FILE *dump_file, vec<jump_thread_edge *> path)
+{
+  fprintf (dump_file,
+	   "  Registering jump thread: (%d, %d) incoming edge; ",
+	   path[0]->e->src->index, path[0]->e->dest->index);
+
+  for (unsigned int i = 1; i < path.length (); i++)
+    {
+      /* We can get paths with a NULL edge when the final destination
+	 of a jump thread turns out to be a constant address.  We dump
+	 those paths when debugging, so we have to be prepared for that
+	 possibility here.  */
+      if (path[i]->e == NULL)
+	continue;
+
+      if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+	fprintf (dump_file, " (%d, %d) joiner; ",
+		 path[i]->e->src->index, path[i]->e->dest->index);
+      if (path[i]->type == EDGE_COPY_SRC_BLOCK)
+       fprintf (dump_file, " (%d, %d) normal;",
+		 path[i]->e->src->index, path[i]->e->dest->index);
+      if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK)
+       fprintf (dump_file, " (%d, %d) nocopy;",
+		 path[i]->e->src->index, path[i]->e->dest->index);
+    }
+  fputc ('\n', dump_file);
+}
+
+
 /* Register a jump threading opportunity.  We queue up all the jump
    threading opportunities discovered by a pass and update the CFG
    and SSA form all at once.
@@ -1389,43 +1423,47 @@ thread_through_all_blocks (bool may_peel_loop_headers)
    after fixing the SSA graph.  */
 
 void
-register_jump_thread (vec<edge> path, bool through_joiner)
+register_jump_thread (vec<jump_thread_edge *> path)
 {
-  /* Convert PATH into 3 edge representation we've been using.  This
-     is temporary until we convert this file to use a path representation
-     throughout.  */
-  edge e = path[0];
-  edge e2 = path[1];
-  edge e3;
-
-  if (!through_joiner)
-    e3 = NULL;
-  else
-    e3 = path.last ();
+  /* First make sure there are no NULL outgoing edges on the jump threading
+     path.  That can happen for jumping to a constant address.  */
+  for (unsigned int i = 0; i < path.length (); i++)
+    if (path[i]->e == NULL)
+      {
+	if (dump_file && (dump_flags & TDF_DETAILS))
+	  {
+	    fprintf (dump_file,
+		     "Found NULL edge in jump threading path.  Cancelling jump thread:\n");
+	    dump_jump_thread_path (dump_file, path);
+	  }
+	return;
+      }
 
-  /* This can occur if we're jumping to a constant address or
-     or something similar.  Just get out now.  */
-  if (e2 == NULL)
-    return;
+  if (!threaded_edges.exists ())
+    threaded_edges.create (15);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
-    {
-      unsigned int i;
+    dump_jump_thread_path (dump_file, path);
 
-      fprintf (dump_file,
-	       "  Registering jump thread %s:",
-	       through_joiner ? "(through joiner block)" : "");
+  /* The first entry in the vector is always the start of the
+     jump threading path.  */
+  threaded_edges.safe_push (path[0]->e);
 
-      for (i = 0; i < path.length (); i++)
-	fprintf (dump_file, " (%d, %d); ",
-		 path[i]->src->index, path[i]->dest->index);
-      fputc ('\n', dump_file);
-    }
-    
-  if (!threaded_edges.exists ())
-    threaded_edges.create (15);
+  /* In our 3-edge representation, the joiner, if it exists is always the
+     2nd edge and the final block on the path is the 3rd edge.  If no
+     jointer exists, then the final block on the path is the 2nd edge
+     and the 3rd edge is NULL.
 
-  threaded_edges.safe_push (e);
-  threaded_edges.safe_push (e2);
-  threaded_edges.safe_push (e3);
+     With upcoming improvements, we're going to be holding onto the entire
+     path, so we'll be able to clean this wart up shortly.  */
+  if (path[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+    {
+      threaded_edges.safe_push (path[1]->e);
+      threaded_edges.safe_push (path.last ()->e);
+    }
+  else
+    {
+      threaded_edges.safe_push (path.last ()->e);
+      threaded_edges.safe_push (NULL);
+    }
 }
diff --git a/gcc/tree-ssa-threadupdate.h b/gcc/tree-ssa-threadupdate.h
new file mode 100644
index 0000000..723f5bb
--- /dev/null
+++ b/gcc/tree-ssa-threadupdate.h
@@ -0,0 +1,45 @@
+/* Communication between registering jump thread requests and
+   updating the SSA/CFG for jump threading. 
+   Copyright (C) 2013 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef _TREE_SSA_THREADUPDATE_H
+#define _TREE_SSA_THREADUPDATE_H 1
+
+/* In tree-ssa-threadupdate.c.  */
+extern bool thread_through_all_blocks (bool);
+enum jump_thread_edge_type
+{
+  EDGE_START_JUMP_THREAD,
+  EDGE_COPY_SRC_BLOCK,
+  EDGE_COPY_SRC_JOINER_BLOCK,
+  EDGE_NO_COPY_SRC_BLOCK
+};
+
+class jump_thread_edge
+{
+public:
+  jump_thread_edge (edge e, enum jump_thread_edge_type type)
+    : e (e), type (type) {}
+
+  edge e;
+  enum jump_thread_edge_type type;
+};
+
+extern void register_jump_thread (vec<class jump_thread_edge *>);
+#endif
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 0d50af7..1600724 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "tree-ssa-propagate.h"
 #include "tree-chrec.h"
+#include "tree-ssa-threadupdate.h"
 #include "gimple-fold.h"
 #include "expr.h"
 #include "optabs.h"