[PATCH] Remove many restrictions for identifying jump threads across backedges

[Jeff Law <law at redhat dot com>]

There was a typo/thinko in the version I posted last night (reversed 
arguments to a bitmap_copy call) that I spotted this morning.  Those 
were some of the newer bits to get the maps reset after handling each 
successor of a joiner block.

So re-bootstrapped and re-regression tested on x86_64-unknown-linux-gnu. 
 Installed on the trunk.

Jeff

	* tree-ssa-threadedge.c (record_temporary_equivalence): Handle
	NULL for RHS, which we used to invalidate equivalences.
	(record_temporary_equivalences_from_phis): New bitmap arguments
	and a boolean indicating if we have passed a backedge.  If we
	have passed a backedge, then set the appropriate bit in the
	bitmaps for the SRC & DEST of PHIs creating equivalences.
	(invalidate_equivalences, dummy_simplify): New functions.
	(cond_arg_set_in_b): Remove.
	(record_temporary_equivalences_from_stmts_at_dest): New bitmap
	arguments and a boolean indicating if we have passed a backedge.
	If we have passed a backedge, then perform invalidations as
	needed.
	(thread_around_empty_blocks): If we have seen a backedge, then
	use the dummy simplify routine.
	(thread_through_normal_block): Likewise.  Pass bitmaps and
	backedge status to children.  Do not pessimize so much when
	traversing backedges in the CFG.
	(thread_across_edge): Manage the SRC_MAP/DST_MAP bitmaps.
	If we have seen a backedge, then use the dummy simplify routine.
	Do not pessimize so much when traversing backedges.

diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 7600d7b..ce161a8 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -170,7 +170,8 @@ record_temporary_equivalence (tree x, tree y, vec<tree> *stack)
 {
   tree prev_x = SSA_NAME_VALUE (x);
 
-  if (TREE_CODE (y) == SSA_NAME)
+  /* Y may be NULL if we are invalidating entries in the table.  */
+  if (y && TREE_CODE (y) == SSA_NAME)
     {
       tree tmp = SSA_NAME_VALUE (y);
       y = tmp ? tmp : y;
@@ -186,10 +187,16 @@ record_temporary_equivalence (tree x, tree y, vec<tree> *stack)
    edge E.  Record unwind information for the equivalences onto STACK.
 
    If a PHI which prevents threading is encountered, then return FALSE
-   indicating we should not thread this edge, else return TRUE.  */
+   indicating we should not thread this edge, else return TRUE. 
+
+   If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
+   of any equivalences recorded.  We use this to make invalidation after
+   traversing back edges less painful.  */
 
 static bool
-record_temporary_equivalences_from_phis (edge e, vec<tree> *stack)
+record_temporary_equivalences_from_phis (edge e, vec<tree> *stack,
+					 bool backedge_seen,
+					 bitmap src_map, bitmap dst_map)
 {
   gimple_stmt_iterator gsi;
 
@@ -217,6 +224,14 @@ record_temporary_equivalences_from_phis (edge e, vec<tree> *stack)
 	stmt_count++;
 
       record_temporary_equivalence (dst, src, stack);
+
+      /* If we have crossed a backedge, then start recording equivalences
+	 we might need to invalidate.  */
+      if (backedge_seen && TREE_CODE (src) == SSA_NAME)
+	{
+	  bitmap_set_bit (src_map, SSA_NAME_VERSION (src));
+	  bitmap_set_bit (dst_map, SSA_NAME_VERSION (dst));
+	}
     }
   return true;
 }
@@ -271,6 +286,34 @@ fold_assignment_stmt (gimple stmt)
     }
 }
 
+/* A new value has been assigned to LHS.  If necessary, invalidate any
+   equivalences that are no longer valid.  */
+static void
+invalidate_equivalences (tree lhs, vec<tree> *stack,
+			 bitmap src_map, bitmap dst_map)
+{
+  /* SRC_MAP contains the source SSA_NAMEs for equivalences created by PHI
+     nodes.  If an entry in SRC_MAP changes, there's some destination that
+     has been recorded as equivalent to the source and that equivalency
+     needs to be eliminated.  */
+  if (bitmap_bit_p (src_map, SSA_NAME_VERSION (lhs)))
+    {
+      unsigned int i;
+      bitmap_iterator bi;
+
+      /* We know that the LHS of STMT was used as the RHS in an equivalency
+	 created by a PHI.  All the LHS of such PHIs were recorded into DST_MAP.
+	 So we can iterate over them to see if any have the LHS of STMT as
+	 an equivalence, and if so, remove the equivalence as it is no longer
+	 valid.  */
+      EXECUTE_IF_SET_IN_BITMAP (dst_map, 0, i, bi)
+	{
+	  if (SSA_NAME_VALUE (ssa_name (i)) == lhs)
+	    record_temporary_equivalence (ssa_name (i), NULL_TREE, stack);
+	}
+    }
+}
+
 /* Try to simplify each statement in E->dest, ultimately leading to
    a simplification of the COND_EXPR at the end of E->dest.
 
@@ -292,7 +335,10 @@ static gimple
 record_temporary_equivalences_from_stmts_at_dest (edge e,
 						  vec<tree> *stack,
 						  tree (*simplify) (gimple,
-								    gimple))
+								    gimple),
+						  bool backedge_seen,
+						  bitmap src_map,
+						  bitmap dst_map)
 {
   gimple stmt = NULL;
   gimple_stmt_iterator gsi;
@@ -369,7 +415,15 @@ record_temporary_equivalences_from_stmts_at_dest (edge e,
 	  if (fndecl
 	      && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
 		  || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
-	    continue;
+	    {
+	      if (backedge_seen)
+		{
+		  tree lhs = gimple_get_lhs (stmt);
+		  record_temporary_equivalence (lhs, NULL_TREE, stack);
+		  invalidate_equivalences (lhs, stack, src_map, dst_map);
+		}
+	      continue;
+	    }
 	}
 
       /* At this point we have a statement which assigns an RHS to an
@@ -433,15 +487,36 @@ record_temporary_equivalences_from_stmts_at_dest (edge e,
 	}
 
       /* Record the context sensitive equivalence if we were able
-	 to simplify this statement.  */
+	 to simplify this statement. 
+
+	 If we have traversed a backedge at some point during threading,
+	 then always enter something here.  Either a real equivalence, 
+	 or a NULL_TREE equivalence which is effectively invalidation of
+	 prior equivalences.  */
       if (cached_lhs
 	  && (TREE_CODE (cached_lhs) == SSA_NAME
 	      || is_gimple_min_invariant (cached_lhs)))
 	record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs, stack);
+      else if (backedge_seen)
+	record_temporary_equivalence (gimple_get_lhs (stmt), NULL_TREE, stack);
+
+      if (backedge_seen)
+	invalidate_equivalences (gimple_get_lhs (stmt), stack,
+				 src_map, dst_map);
     }
   return stmt;
 }
 
+/* Once we have passed a backedge in the CFG when threading, we do not want to
+   utilize edge equivalences for simplification purpose.  They are no longer
+   necessarily valid.  We use this callback rather than the ones provided by
+   DOM/VRP to achieve that effect.  */
+static tree
+dummy_simplify (gimple stmt1 ATTRIBUTE_UNUSED, gimple stmt2 ATTRIBUTE_UNUSED)
+{
+  return NULL_TREE;
+}
+
 /* Simplify the control statement at the end of the block E->dest.
 
    To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
@@ -581,44 +656,6 @@ simplify_control_stmt_condition (edge e,
   return cached_lhs;
 }
 
-/* Return TRUE if the statement at the end of e->dest depends on
-   the output of any statement in BB.   Otherwise return FALSE.
-
-   This is used when we are threading a backedge and need to ensure
-   that temporary equivalences from BB do not affect the condition
-   in e->dest.  */
-
-static bool
-cond_arg_set_in_bb (edge e, basic_block bb)
-{
-  ssa_op_iter iter;
-  use_operand_p use_p;
-  gimple last = last_stmt (e->dest);
-
-  /* E->dest does not have to end with a control transferring
-     instruction.  This can occur when we try to extend a jump
-     threading opportunity deeper into the CFG.  In that case
-     it is safe for this check to return false.  */
-  if (!last)
-    return false;
-
-  if (gimple_code (last) != GIMPLE_COND
-      && gimple_code (last) != GIMPLE_GOTO
-      && gimple_code (last) != GIMPLE_SWITCH)
-    return false;
-
-  FOR_EACH_SSA_USE_OPERAND (use_p, last, iter, SSA_OP_USE | SSA_OP_VUSE)
-    {
-      tree use = USE_FROM_PTR (use_p);
-
-      if (TREE_CODE (use) == SSA_NAME
-	  && gimple_code (SSA_NAME_DEF_STMT (use)) != GIMPLE_PHI
-	  && gimple_bb (SSA_NAME_DEF_STMT (use)) == bb)
-	return true;
-    }
-  return false;
-}
-
 /* Copy debug stmts from DEST's chain of single predecessors up to
    SRC, so that we don't lose the bindings as PHI nodes are introduced
    when DEST gains new predecessors.  */
@@ -805,6 +842,8 @@ thread_around_empty_blocks (edge taken_edge,
 	      path->safe_push (x);
 	      bitmap_set_bit (visited, taken_edge->dest->index);
 	      *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
+	      if (*backedge_seen_p)
+		simplify = dummy_simplify;
 	      return thread_around_empty_blocks (taken_edge,
 						 dummy_cond,
 						 handle_dominating_asserts,
@@ -827,6 +866,13 @@ thread_around_empty_blocks (edge taken_edge,
       && gimple_code (stmt) != GIMPLE_SWITCH)
     return false;
 
+  /* If we have traversed a backedge, then we do not want to look
+     at certain expressions in the table that can not be relied upon.
+     Luckily the only code that looked at those expressions is the
+     SIMPLIFY callback, which we replace if we can no longer use it.  */
+  if (*backedge_seen_p)
+    simplify = dummy_simplify;
+
   /* Extract and simplify the condition.  */
   cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
 					  simplify, handle_dominating_asserts);
@@ -846,6 +892,8 @@ thread_around_empty_blocks (edge taken_edge,
 	= new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
       path->safe_push (x);
       *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
+      if (*backedge_seen_p)
+	simplify = dummy_simplify;
 
       thread_around_empty_blocks (taken_edge,
 				  dummy_cond,
@@ -896,24 +944,28 @@ thread_through_normal_block (edge e,
 			     tree (*simplify) (gimple, gimple),
 			     vec<jump_thread_edge *> *path,
 			     bitmap visited,
-			     bool *backedge_seen_p)
+			     bool *backedge_seen_p,
+			     bitmap src_map,
+			     bitmap dst_map)
 {
-  /* If we have crossed a backedge, then we want to verify that the COND_EXPR,
-     SWITCH_EXPR or GOTO_EXPR at the end of e->dest is not affected
-     by any statements in e->dest.  If it is affected, then it is not
-     safe to thread this edge.  */
-  if (*backedge_seen_p
-      && cond_arg_set_in_bb (e, e->dest))
-    return false;
+  /* If we have traversed a backedge, then we do not want to look
+     at certain expressions in the table that can not be relied upon.
+     Luckily the only code that looked at those expressions is the
+     SIMPLIFY callback, which we replace if we can no longer use it.  */
+  if (*backedge_seen_p)
+    simplify = dummy_simplify;
 
   /* PHIs create temporary equivalences.  */
-  if (!record_temporary_equivalences_from_phis (e, stack))
+  if (!record_temporary_equivalences_from_phis (e, stack, *backedge_seen_p,
+						src_map, dst_map))
     return false;
 
   /* Now walk each statement recording any context sensitive
      temporary equivalences we can detect.  */
   gimple stmt
-    = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify);
+    = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify,
+							*backedge_seen_p,
+							src_map, dst_map);
   if (!stmt)
     return false;
 
@@ -955,25 +1007,24 @@ thread_through_normal_block (edge e,
 	    = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
 	  path->safe_push (x);
 	  *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
+	  if (*backedge_seen_p)
+	    simplify = dummy_simplify;
 
 	  /* See if we can thread through DEST as well, this helps capture
 	     secondary effects of threading without having to re-run DOM or
-	     VRP.  */
-	  if (!*backedge_seen_p
-	      || ! cond_arg_set_in_bb (taken_edge, e->dest))
-	    {
-	      /* We don't want to thread back to a block we have already
- 		 visited.  This may be overly conservative.  */
-	      bitmap_set_bit (visited, dest->index);
-	      bitmap_set_bit (visited, e->dest->index);
-	      thread_around_empty_blocks (taken_edge,
-					  dummy_cond,
-					  handle_dominating_asserts,
-					  simplify,
-					  visited,
-					  path,
-					  backedge_seen_p);
-	    }
+	     VRP. 
+
+	     We don't want to thread back to a block we have already
+ 	     visited.  This may be overly conservative.  */
+	  bitmap_set_bit (visited, dest->index);
+	  bitmap_set_bit (visited, e->dest->index);
+	  thread_around_empty_blocks (taken_edge,
+				      dummy_cond,
+				      handle_dominating_asserts,
+				      simplify,
+				      visited,
+				      path,
+				      backedge_seen_p);
 	  return true;
 	}
     }
@@ -1015,6 +1066,8 @@ thread_across_edge (gimple dummy_cond,
 		    tree (*simplify) (gimple, gimple))
 {
   bitmap visited = BITMAP_ALLOC (NULL);
+  bitmap src_map = BITMAP_ALLOC (NULL);
+  bitmap dst_map = BITMAP_ALLOC (NULL);
   bool backedge_seen;
 
   stmt_count = 0;
@@ -1024,14 +1077,19 @@ thread_across_edge (gimple dummy_cond,
   bitmap_set_bit (visited, e->src->index);
   bitmap_set_bit (visited, e->dest->index);
   backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
+  if (backedge_seen)
+    simplify = dummy_simplify;
+
   if (thread_through_normal_block (e, dummy_cond, handle_dominating_asserts,
 				   stack, simplify, path, visited,
-				   &backedge_seen))
+				   &backedge_seen, src_map, dst_map))
     {
       propagate_threaded_block_debug_into (path->last ()->e->dest,
 					   e->dest);
       remove_temporary_equivalences (stack);
       BITMAP_FREE (visited);
+      BITMAP_FREE (src_map);
+      BITMAP_FREE (dst_map);
       register_jump_thread (path);
       return;
     }
@@ -1066,15 +1124,26 @@ thread_across_edge (gimple dummy_cond,
 	{
 	  remove_temporary_equivalences (stack);
 	  BITMAP_FREE (visited);
+	  BITMAP_FREE (src_map);
+	  BITMAP_FREE (dst_map);
 	  return;
 	}
 
+    /* We need to restore the state of the maps to this point each loop
+       iteration.  */
+    bitmap src_map_copy = BITMAP_ALLOC (NULL);
+    bitmap dst_map_copy = BITMAP_ALLOC (NULL);
+    bitmap_copy (src_map_copy, src_map);
+    bitmap_copy (dst_map_copy, dst_map);
+
     /* Look at each successor of E->dest to see if we can thread through it.  */
     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
       {
 	/* Push a fresh marker so we can unwind the equivalences created
 	   for each of E->dest's successors.  */
 	stack->safe_push (NULL_TREE);
+	bitmap_copy (src_map, src_map_copy);
+	bitmap_copy (dst_map, dst_map_copy);
      
 	/* Avoid threading to any block we have already visited.  */
 	bitmap_clear (visited);
@@ -1093,23 +1162,25 @@ thread_across_edge (gimple dummy_cond,
 	found = false;
 	backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0);
 	backedge_seen |= ((taken_edge->flags & EDGE_DFS_BACK) != 0);
-	if (!backedge_seen
-	    || ! cond_arg_set_in_bb (path->last ()->e, e->dest))
-	  found = thread_around_empty_blocks (taken_edge,
-					      dummy_cond,
-					      handle_dominating_asserts,
-					      simplify,
-					      visited,
-					      path,
-					      &backedge_seen);
-
-	if (!found
-	    && (!backedge_seen
-		|| ! cond_arg_set_in_bb (path->last ()->e, e->dest)))
+	if (backedge_seen)
+	  simplify = dummy_simplify;
+	found = thread_around_empty_blocks (taken_edge,
+					    dummy_cond,
+					    handle_dominating_asserts,
+					    simplify,
+					    visited,
+					    path,
+					    &backedge_seen);
+
+	if (backedge_seen)
+	  simplify = dummy_simplify;
+
+	if (!found)
 	  found = thread_through_normal_block (path->last ()->e, dummy_cond,
 					       handle_dominating_asserts,
 					       stack, simplify, path, visited,
-					       &backedge_seen);
+					       &backedge_seen,
+					       src_map, dst_map);
 
 	/* If we were able to thread through a successor of E->dest, then
 	   record the jump threading opportunity.  */
@@ -1128,6 +1199,10 @@ thread_across_edge (gimple dummy_cond,
 	remove_temporary_equivalences (stack);
       }
     BITMAP_FREE (visited);
+    BITMAP_FREE (src_map);
+    BITMAP_FREE (dst_map);
+    BITMAP_FREE (src_map_copy);
+    BITMAP_FREE (dst_map_copy);
   }
 
   remove_temporary_equivalences (stack);