[PATCH][PR tree-optimization/67816] Fix jump threading when DOM removes conditionals in jump threading path

	PR tree-optimization/67816
	* tree-ssa-threadupdate.h (remove_jump_threads_including): Renamed
	from remove_jump_threads_starting_at.  Accept an edge rather than
	a basic block.
	* tree-ssa-threadupdate.c (removed_edges): New hash table.
	(remove_jump_threads_including): Note edges that get removed from
	the CFG for later pruning of jump threading paths including them.
	(thread_through_all_blocks): Remove paths which include edges that
	have been removed.
	* tree-ssa-dom.c (optimize_stmt): Call remove_jump_threads_including
	on each outgoing edges when optimizing away a control statement.

	* gcc.c-torture/compile/pr67816.c: New test.

From-SVN: r228559

6 files changed, 97 insertions, 26 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 732b3d1..db6f1b6 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2015-10-06  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/67816
+	* tree-ssa-threadupdate.h (remove_jump_threads_including): Renamed
+	from remove_jump_threads_starting_at.  Accept an edge rather than
+	a basic block.
+	* tree-ssa-threadupdate.c (removed_edges): New hash table.
+	(remove_jump_threads_including): Note edges that get removed from
+	the CFG for later pruning of jump threading paths including them.
+	(thread_through_all_blocks): Remove paths which include edges that
+	have been removed.
+	* tree-ssa-dom.c (optimize_stmt): Call remove_jump_threads_including
+	on each outgoing edges when optimizing away a control statement.
+
 2015-10-06  Trevor Saunders  <tbsaunde+gcc@tbsaunde.org>
 
 	* reorg.c (emit_delay_sequence): Store list of delay slot insns
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 4ec4743..1882fbd 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2015-10-06  Jeff Law  <law@redhat.com>
+
+	* gcc.c-torture/compile/pr67816.c: New test.
+
 2015-10-07  Kugan Vivekanandarajah  <kuganv@linaro.org>
 
 	* gcc.target/aarch64/get_lane_f16_1.c: New test.
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr67816.c b/gcc/testsuite/gcc.c-torture/compile/pr67816.c
new file mode 100644
index 0000000..c3db3a3
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr67816.c
@@ -0,0 +1,19 @@
+int a, c, d, e;
+int b[10];
+void fn1() {
+  int i, f = 0;
+  for (;;) {
+    i = 0;
+    for (; i < a; i++)
+      if (c) {
+        if (b[i])
+          f = 1;
+      } else if (b[i])
+        f = 0;
+    if (f)
+      d++;
+    while (e)
+      ;
+  }
+}
+
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index c226da5..941087d 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -1840,8 +1840,13 @@ optimize_stmt (basic_block bb, gimple_stmt_iterator si,
 	  edge taken_edge = find_taken_edge (bb, val);
 	  if (taken_edge)
 	    {
-	      /* Delete threads that start at BB.  */
-	      remove_jump_threads_starting_at (bb);
+
+	      /* We need to remove any queued jump threads that
+		 reference outgoing edges from this block.  */
+	      edge_iterator ei;
+	      edge e;
+	      FOR_EACH_EDGE (e, ei, bb->succs)
+		remove_jump_threads_including (e);
 
 	      /* If BB is in a loop, then removing an outgoing edge from BB
 		 may cause BB to move outside the loop, changes in the
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 4a147bb..26b199b 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -215,6 +215,18 @@ redirection_data::equal (const redirection_data *p1, const redirection_data *p2)
   return true;
 }
 
+/* Rather than search all the edges in jump thread paths each time
+   DOM is able to simply if control statement, we build a hash table
+   with the deleted edges.  We only care about the address of the edge,
+   not its contents.  */
+struct removed_edges : nofree_ptr_hash<edge_def>
+{
+  static hashval_t hash (edge e) { return htab_hash_pointer (e); }
+  static bool equal (edge e1, edge e2) { return e1 == e2; }
+};
+
+static hash_table<removed_edges> *removed_edges;
+
 /* Data structure of information to pass to hash table traversal routines.  */
 struct ssa_local_info_t
 {
@@ -2539,35 +2551,23 @@ valid_jump_thread_path (vec<jump_thread_edge *> *path)
   return true;
 }
 
-/* Remove any queued jump threads that start at BB.  */
+/* Remove any queued jump threads that include edge E.
+
+   We don't actually remove them here, just record the edges into ax
+   hash table.  That way we can do the search once per iteration of
+   DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR.  */
 
 void
-remove_jump_threads_starting_at (basic_block bb)
+remove_jump_threads_including (edge_def *e)
 {
   if (!paths.exists ())
     return;
 
-  for (unsigned i = 0; i < paths.length ();)
-    {
-      vec<jump_thread_edge *> *path = paths[i];
+  if (!removed_edges)
+    removed_edges = new hash_table<struct removed_edges> (17);
 
-      /* Sadly, FSM jump threads have a slightly different
-	 representation than the rest of the jump threads.  */
-      if ((*path)[0]->type == EDGE_FSM_THREAD
-	  && (*path)[0]->e->src == bb)
-	{
-	  delete_jump_thread_path (path);
-	  paths.unordered_remove (i);
-	}
-      else if ((*path)[0]->type != EDGE_FSM_THREAD
-	       && (*path)[0]->e->dest == bb)
-	{
-	  delete_jump_thread_path (path);
-	  paths.unordered_remove (i);
-	}
-      else
-	i++;
-    }
+  edge *slot = removed_edges->find_slot (e, INSERT);
+  *slot = e;
 }
 
 /* Walk through all blocks and thread incoming edges to the appropriate
@@ -2591,11 +2591,37 @@ thread_through_all_blocks (bool may_peel_loop_headers)
   struct loop *loop;
 
   if (!paths.exists ())
-    return false;
+    {
+      retval = false;
+      goto out;
+    }
 
   threaded_blocks = BITMAP_ALLOC (NULL);
   memset (&thread_stats, 0, sizeof (thread_stats));
 
+  /* Remove any paths that referenced removed edges.  */
+  if (removed_edges)
+    for (i = 0; i < paths.length (); )
+      {
+	unsigned int j;
+	vec<jump_thread_edge *> *path = paths[i];
+
+	for (j = 0; j < path->length (); j++)
+	  {
+	    edge e = (*path)[j]->e;
+	    if (removed_edges->find_slot (e, NO_INSERT))
+	      break;
+	  }
+
+	if (j != path->length ())
+	  {
+	    delete_jump_thread_path (path);
+	    paths.unordered_remove (i);
+	    continue;
+	  }
+	i++;
+      }
+
   /* Jump-thread all FSM threads before other jump-threads.  */
   for (i = 0; i < paths.length ();)
     {
@@ -2778,6 +2804,9 @@ thread_through_all_blocks (bool may_peel_loop_headers)
   if (retval)
     loops_state_set (LOOPS_NEED_FIXUP);
 
+ out:
+  delete removed_edges;
+  removed_edges = NULL;
   return retval;
 }
 
diff --git a/gcc/tree-ssa-threadupdate.h b/gcc/tree-ssa-threadupdate.h
index 30428e8..984b6c4 100644
--- a/gcc/tree-ssa-threadupdate.h
+++ b/gcc/tree-ssa-threadupdate.h
@@ -43,7 +43,7 @@ public:
 };
 
 extern void register_jump_thread (vec <class jump_thread_edge *> *);
-extern void remove_jump_threads_starting_at (basic_block);
+extern void remove_jump_threads_including (edge);
 extern void delete_jump_thread_path (vec <class jump_thread_edge *> *);
 extern void remove_ctrl_stmt_and_useless_edges (basic_block, basic_block);
 #endif