tree-ssa-threadupdate.c (redirect_edges): Call create_edge_and_update_destination_phis as needed.

	* tree-ssa-threadupdate.c (redirect_edges): Call
	create_edge_and_update_destination_phis as needed.
	(create_edge_and_update_destination_phis): Accept new BB argument.
	All callers updated.
	(thread_block): Do not update the profile when threading around
	intermediate blocks.
	(thread_single_edge): Likewise.
	(determine_bb_domination_status): If BB is not a successor of the
	loop header, return NONDOMINATING.
	(register_jump_thread): Note when we register a jump thread around
	an intermediate block.
	* tree-ssa-threadedge.c (thread_around_empty_block): New function.
	(thread_across_edge): Use it.

	* gcc.dg/tree-ssa/ssa-dom-thread-3.c: New test.

From-SVN: r171622

5 files changed, 193 insertions, 12 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 70b6506..15500e4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,19 @@
+2011-03-28  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-threadupdate.c (redirect_edges): Call
+	create_edge_and_update_destination_phis as needed.
+	(create_edge_and_update_destination_phis): Accept new BB argument.
+	All callers updated.
+	(thread_block): Do not update the profile when threading around
+	intermediate blocks.
+	(thread_single_edge): Likewise.
+	(determine_bb_domination_status): If BB is not a successor of the
+	loop header, return NONDOMINATING.
+	(register_jump_thread): Note when we register a jump thread around
+	an intermediate block.
+	* tree-ssa-threadedge.c (thread_around_empty_block): New function.
+	(thread_across_edge): Use it.
+
 2011-03-28  Tristan Gingold  <gingold@adacore.com>
 
 	* config/ia64/ia64.c (ia64_promote_function_mode): Fix promotion
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index a6214b1..dec92ef 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2011-03-28  Jeff Law <law@redhat.com>
+
+	* gcc.dg/tree-ssa/ssa-dom-thread-3.c: New test.
+
 2011-03-28  Peter Bergner  <bergner@vnet.ibm.com>
 
 	* gcc.dg/stack-usage-1.c (SIZE): Provide proper values for __PPC64__
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
new file mode 100644
index 0000000..d851bf2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
@@ -0,0 +1,47 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-dom1-details" } */
+extern void abort (void) __attribute__ ((__noreturn__));
+union tree_node;
+typedef union tree_node *tree;
+enum tree_code
+{
+  VAR_DECL,
+  SSA_NAME,
+  MAX_TREE_CODES
+};
+extern unsigned char tree_contains_struct[MAX_TREE_CODES][64];
+struct tree_base
+{
+  enum tree_code code:16;
+};
+enum tree_node_structure_enum
+{
+  TS_DECL_COMMON
+};
+struct tree_ssa_name
+{
+  tree var;
+};
+union tree_node
+{
+  struct tree_base base;
+  struct tree_ssa_name ssa_name;
+};
+long
+expand_one_var (tree var, unsigned char toplevel, unsigned char really_expand)
+{
+  tree origvar = var;
+  var = var->ssa_name.var;
+  if (((enum tree_code) (origvar)->base.code) == SSA_NAME
+      && !((var->base.code != VAR_DECL)))
+    abort ();
+  if ((var->base.code) != VAR_DECL && ((origvar)->base.code) != SSA_NAME)
+    ;
+  else if (tree_contains_struct[(var->base.code)][(TS_DECL_COMMON)] != 1)
+    abort ();
+}
+/* We should thread the jump, through an intermediate block.  */
+/* { dg-final { scan-tree-dump-times "Threaded" 1 "dom1"} } */
+/* { dg-final { scan-tree-dump-times "one or more intermediate" 1 "dom1"} } */
+/* { dg-final { cleanup-tree-dump "dom1" } } */
+
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 020f6e7..1fee9bf 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -583,6 +583,76 @@ simplify_control_stmt_condition (edge e,
   return cached_lhs;
 }
 
+/* TAKEN_EDGE represents the an edge taken as a result of jump threading.
+   See if we can thread around TAKEN_EDGE->dest as well.  If so, return
+   the edge out of TAKEN_EDGE->dest that we can statically compute will be
+   traversed.
+
+   We are much more restrictive as to the contents of TAKEN_EDGE->dest
+   as the path isolation code in tree-ssa-threadupdate.c isn't prepared
+   to handle copying intermediate blocks on a threaded path. 
+
+   Long term a more consistent and structured approach to path isolation
+   would be a huge help.   */
+static edge
+thread_around_empty_block (edge taken_edge,
+			   gimple dummy_cond,
+			   bool handle_dominating_asserts,
+			   tree (*simplify) (gimple, gimple),
+			   bitmap visited)
+{
+  basic_block bb = taken_edge->dest;
+  gimple_stmt_iterator gsi;
+  gimple stmt;
+  tree cond;
+
+  /* This block must have a single predecessor (E->dest).  */
+  if (!single_pred_p (bb))
+    return NULL;
+
+  /* This block must have more than one successor.  */
+  if (single_succ_p (bb))
+    return NULL;
+
+  /* This block can have no PHI nodes.  This is overly conservative.  */
+  if (!gsi_end_p (gsi_start_phis (bb)))
+    return NULL;
+
+  /* Skip over DEBUG statements at the start of the block.  */
+  gsi = gsi_start_nondebug_bb (bb);
+
+  if (gsi_end_p (gsi))
+    return NULL;
+
+  /* This block can have no statements other than its control altering
+     statement.  This is overly conservative.  */
+  stmt = gsi_stmt (gsi);
+  if (gimple_code (stmt) != GIMPLE_COND
+      && gimple_code (stmt) != GIMPLE_GOTO
+      && gimple_code (stmt) != GIMPLE_SWITCH)
+    return NULL;
+
+  /* Extract and simplify the condition.  */
+  cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
+					  simplify, handle_dominating_asserts);
+
+  /* If the condition can be statically computed and we have not already
+     visited the destination edge, then add the taken edge to our thread
+     path.  */
+  if (cond && is_gimple_min_invariant (cond))
+    {
+      edge taken_edge = find_taken_edge (bb, cond);
+
+      if (bitmap_bit_p (visited, taken_edge->dest->index))
+	return NULL;
+      bitmap_set_bit (visited, taken_edge->dest->index);
+      return taken_edge;
+    }
+ 
+  return NULL;
+}
+      
+
 /* We are exiting E->src, see if E->dest ends with a conditional
    jump which has a known value when reached via E.
 
@@ -661,16 +731,44 @@ thread_across_edge (gimple dummy_cond,
       tree cond;
 
       /* Extract and simplify the condition.  */
-      cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, handle_dominating_asserts);
+      cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
+					      handle_dominating_asserts);
 
       if (cond && is_gimple_min_invariant (cond))
 	{
 	  edge taken_edge = find_taken_edge (e->dest, cond);
 	  basic_block dest = (taken_edge ? taken_edge->dest : NULL);
+	  bitmap visited;
+	  edge e2;
 
 	  if (dest == e->dest)
 	    goto fail;
 
+	  /* DEST could be null for a computed jump to an absolute
+	     address.  If DEST is not null, then see if we can thread
+	     through it as well, this helps capture secondary effects
+	     of threading without having to re-run DOM or VRP.  */
+	  if (dest)
+	    {
+	      /* We don't want to thread back to a block we have already
+ 		 visited.  This may be overly conservative.  */
+	      visited = BITMAP_ALLOC (NULL);
+	      bitmap_set_bit (visited, dest->index);
+	      bitmap_set_bit (visited, e->dest->index);
+	      do
+		{
+		  e2 = thread_around_empty_block (taken_edge,
+						  dummy_cond,
+						  handle_dominating_asserts,
+						  simplify,
+						  visited);
+		  if (e2)
+		    taken_edge = e2;
+		}
+	      while (e2);
+	      BITMAP_FREE (visited);
+	    }
+
 	  remove_temporary_equivalences (stack);
 	  register_jump_thread (e, taken_edge);
 	}
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 951f47e..efbc5ec 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -304,14 +304,15 @@ lookup_redirection_data (edge e, edge incoming_edge, enum insert_option insert)
    destination.  */
 
 static void
-create_edge_and_update_destination_phis (struct redirection_data *rd)
+create_edge_and_update_destination_phis (struct redirection_data *rd,
+					 basic_block bb)
 {
-  edge e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU);
+  edge e = make_edge (bb, rd->outgoing_edge->dest, EDGE_FALLTHRU);
   gimple_stmt_iterator gsi;
 
   rescan_loop_exit (e, true, false);
   e->probability = REG_BR_PROB_BASE;
-  e->count = rd->dup_block->count;
+  e->count = bb->count;
   e->aux = rd->outgoing_edge->aux;
 
   /* If there are any PHI nodes at the destination of the outgoing edge
@@ -359,7 +360,7 @@ create_duplicates (void **slot, void *data)
 
       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
          block.  */
-      create_edge_and_update_destination_phis (rd);
+      create_edge_and_update_destination_phis (rd, rd->dup_block);
     }
 
   /* Keep walking the hash table.  */
@@ -380,7 +381,7 @@ fixup_template_block (void **slot, void *data)
      and halt the hash table traversal.  */
   if (rd->dup_block && rd->dup_block == local_info->template_block)
     {
-      create_edge_and_update_destination_phis (rd);
+      create_edge_and_update_destination_phis (rd, rd->dup_block);
       return 0;
     }
 
@@ -443,6 +444,11 @@ redirect_edges (void **slot, void *data)
 	  remove_ctrl_stmt_and_useless_edges (local_info->bb,
 					      rd->outgoing_edge->dest);
 
+	  /* If we are threading beyond the immediate successors of
+	     the duplicate, then BB will have no edges, create one.  */
+	  if (EDGE_COUNT (local_info->bb->succs) == 0)
+	    create_edge_and_update_destination_phis (rd, local_info->bb);
+
 	  /* Fixup the flags on the single remaining edge.  */
 	  single_succ_edge (local_info->bb)->flags
 	    &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
@@ -565,8 +571,9 @@ thread_block (basic_block bb, bool noloop_only)
 	  continue;
 	}
 
-      update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
-				       e->count, (edge) e->aux);
+      if (e->dest == e2->src)
+	update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
+				         e->count, (edge) e->aux);
 
       /* Insert the outgoing edge into the hash table if it is not
 	 already in the hash table.  */
@@ -650,12 +657,13 @@ thread_single_edge (edge e)
     }
 
   /* Otherwise, we need to create a copy.  */
-  update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
+  if (e->dest == eto->src)
+    update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
 
   rd.outgoing_edge = eto;
 
   create_block_for_threading (bb, &rd);
-  create_edge_and_update_destination_phis (&rd);
+  create_edge_and_update_destination_phis (&rd, rd.dup_block);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
@@ -704,7 +712,9 @@ determine_bb_domination_status (struct loop *loop, basic_block bb)
   edge e;
 
 #ifdef ENABLE_CHECKING
-  /* This function assumes BB is a successor of LOOP->header.  */
+  /* This function assumes BB is a successor of LOOP->header.
+     If that is not the case return DOMST_NONDOMINATING which
+     is always safe.  */
     {
       bool ok = false;
 
@@ -717,7 +727,8 @@ determine_bb_domination_status (struct loop *loop, basic_block bb)
 	    }
 	}
 
-      gcc_assert (ok);
+      if (!ok)
+	return DOMST_NONDOMINATING;
     }
 #endif
 
@@ -1099,6 +1110,11 @@ register_jump_thread (edge e, edge e2)
   if (threaded_edges == NULL)
     threaded_edges = VEC_alloc (edge, heap, 10);
 
+  if (dump_file && (dump_flags & TDF_DETAILS)
+      && e->dest != e2->src)
+    fprintf (dump_file,
+	     "  Registering jump thread around one or more intermediate blocks\n");
+
   VEC_safe_push (edge, heap, threaded_edges, e);
   VEC_safe_push (edge, heap, threaded_edges, e2);
 }