[3/5,P1,tree-optimization/71437] Remove ASSERT_EXPR handling from core of threader

Submitted by Jeff Law on March 16, 2017, 7:15 p.m.

Details

Message ID 3afbd7d2-6c22-72ee-7fce-5eaae30efe87@redhat.com
State New
Headers show

Commit Message

Jeff Law March 16, 2017, 7:15 p.m.
For reference the ppc64 bootstrap & regression testing of patches #1 and 
#2 turned up no issues.


This patch removes ASSERT_EXPR handling from the core of the jump 
threader.  10+ years after its introduction it's painfully obvious 
"handle_dominating_asserts" was a bad idea.

The good news is we can mostly just move that code into the VRP callback 
and adjust the function signatures & call points accordingly.  We lose 
the handle_dominating_asserts parameter in many places and gain a basic 
block parameter to the simplification callbacks.

There's two places in the threader where we had code which was 
conditional on handle_dominating_asserts, but which did something other 
than just calling lhs_of_dominating_assert.  Those two hunks of code are 
now unconditionally executed.  This leads to additional jump threads 
being found in DOM.

Overall this is both a cleanup and a requirement to solve 71437.  I 
found there are times when we want the original SSA_NAMEs in the 
simplification callbacks and other times when we want the lhs of a 
dominating assert.  The former when we're going to look up things in the 
hash tables in the hopes of finding a simpler form of the expression (ie 
a constant).  The latter when we're actually using VRP data to simplify 
an expression.

The good news is that by passing the original SSA_NAME to the 
simplification callback, we allow that callback to first query the 
expression table with the raw name, then get a dominating assert prior 
to querying VRP data.

Bootstrapped and regression tested on top of patches #1-#2 of this kit 
on x86_64-linux-gnu.  Installing on the trunk momentarily.



Jeff
PR tree-optimization/71437
	* tree-ssa-dom.c (pfn_simplify): Add basic_block argument.  All
	callers changed.
	(simplify_stmt_for_jump_threading): Add basic_block argument.  All
	callers changed.
	(lhs_of_dominating_assert): Moved from here into tree-vrp.c.
	(dom_opt_dom_walker::thread_across_edge): Remove 
	handle_dominating_asserts argument.  All callers changed.
	(record_temporary_equivalences_from_stmts_at_dest): Corresponding
	changes.  Remove calls to lhs_of_dominating_assert.  Other
	uses of handle_dominating_asserts turn into unconditional code
	(simplify_control_stmt_condition_1): Likewise.
	(simplify_control_stmt_condition): Likewise.
	(thread_through_normal_block, thread_across_edge): Likewise.
	* tree-ssa-threadedge.h (thread_across_edge): Corresponding changes.
	* tree-vrp.c (lhs_of_dominating_assert): Move here.  Return original
	object if it is not an SSA_NAME.
	(simplify_stmt_for_jump_threading): Call lhs_of_dominating_assert
	before calling into the VRP specific simplifiers.
	(identify_jump_threads): Remove handle_dominating_asserts
	argument.

Patch hide | download patch | download mbox

diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index dc736e3..2bedafc 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -756,7 +756,8 @@  make_pass_dominator (gcc::context *ctxt)
 static tree
 simplify_stmt_for_jump_threading (gimple *stmt,
 				  gimple *within_stmt ATTRIBUTE_UNUSED,
-				  class avail_exprs_stack *avail_exprs_stack)
+				  class avail_exprs_stack *avail_exprs_stack,
+				  basic_block bb ATTRIBUTE_UNUSED)
 {
   return avail_exprs_stack->lookup_avail_expr (stmt, false, true);
 }
@@ -939,7 +940,7 @@  dom_opt_dom_walker::thread_across_edge (edge e)
 
   /* With all the edge equivalences in the tables, go ahead and attempt
      to thread through E->dest.  */
-  ::thread_across_edge (m_dummy_cond, e, false,
+  ::thread_across_edge (m_dummy_cond, e,
 		        m_const_and_copies, m_avail_exprs_stack,
 		        simplify_stmt_for_jump_threading);
 
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 4949bfa..7f70b40 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -47,7 +47,9 @@  static int stmt_count;
 /* Array to record value-handles per SSA_NAME.  */
 vec<tree> ssa_name_values;
 
-typedef tree (pfn_simplify) (gimple *, gimple *, class avail_exprs_stack *);
+typedef tree (pfn_simplify) (gimple *, gimple *,
+			     class avail_exprs_stack *,
+			     basic_block);
 
 /* Set the value for the SSA name NAME to VALUE.  */
 
@@ -111,32 +113,6 @@  potentially_threadable_block (basic_block bb)
   return true;
 }
 
-/* Return the LHS of any ASSERT_EXPR where OP appears as the first
-   argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
-   BB.  If no such ASSERT_EXPR is found, return OP.  */
-
-static tree
-lhs_of_dominating_assert (tree op, basic_block bb, gimple *stmt)
-{
-  imm_use_iterator imm_iter;
-  gimple *use_stmt;
-  use_operand_p use_p;
-
-  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
-    {
-      use_stmt = USE_STMT (use_p);
-      if (use_stmt != stmt
-          && gimple_assign_single_p (use_stmt)
-          && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR
-          && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op
-	  && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt)))
-	{
-	  return gimple_assign_lhs (use_stmt);
-	}
-    }
-  return op;
-}
-
 /* Record temporary equivalences created by PHIs at the target of the
    edge E.  Record unwind information for the equivalences onto STACK.
 
@@ -357,7 +333,7 @@  record_temporary_equivalences_from_stmts_at_dest (edge e,
 		    SET_USE (use_p, tmp);
 		}
 
-	      cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
+	      cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src);
 
 	      /* Restore the statement's original uses/defs.  */
 	      i = 0;
@@ -380,7 +356,7 @@  record_temporary_equivalences_from_stmts_at_dest (edge e,
 static tree simplify_control_stmt_condition_1 (edge, gimple *,
 					       class avail_exprs_stack *,
 					       tree, enum tree_code, tree,
-					       gcond *, pfn_simplify, bool,
+					       gcond *, pfn_simplify,
 					       unsigned);
 
 /* Simplify the control statement at the end of the block E->dest.
@@ -402,8 +378,7 @@  simplify_control_stmt_condition (edge e,
 				 gimple *stmt,
 				 class avail_exprs_stack *avail_exprs_stack,
 				 gcond *dummy_cond,
-				 pfn_simplify simplify,
-				 bool handle_dominating_asserts)
+				 pfn_simplify simplify)
 {
   tree cond, cached_lhs;
   enum gimple_code code = gimple_code (stmt);
@@ -450,7 +425,6 @@  simplify_control_stmt_condition (edge e,
 	= simplify_control_stmt_condition_1 (e, stmt, avail_exprs_stack,
 					     op0, cond_code, op1,
 					     dummy_cond, simplify,
-					     handle_dominating_asserts,
 					     recursion_limit);
 
       /* If we were testing an integer/pointer against a constant, then
@@ -508,28 +482,24 @@  simplify_control_stmt_condition (edge e,
 	    }
 	}
 
-      /* If we're dominated by a suitable ASSERT_EXPR, then
-	 update CACHED_LHS appropriately.  */
-      if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME)
-	cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt);
-
       /* If we haven't simplified to an invariant yet, then use the
 	 pass specific callback to try and simplify it further.  */
       if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
 	{
-	  if (handle_dominating_asserts && code == GIMPLE_SWITCH)
+	  if (code == GIMPLE_SWITCH)
 	    {
-	      /* Replace the index operand of the GIMPLE_SWITCH with the
-		 dominating ASSERT_EXPR before handing it off to VRP.  If
-		 simplification is possible, the simplified value will be a
-		 CASE_LABEL_EXPR of the label that is proven to be taken.  */
+	      /* Replace the index operand of the GIMPLE_SWITCH with any LHS
+		 we found before handing off to VRP.  If simplification is
+	         possible, the simplified value will be a CASE_LABEL_EXPR of
+		 the label that is proven to be taken.  */
 	      gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
 	      gimple_switch_set_index (dummy_switch, cached_lhs);
-	      cached_lhs = (*simplify) (dummy_switch, stmt, avail_exprs_stack);
+	      cached_lhs = (*simplify) (dummy_switch, stmt,
+					avail_exprs_stack, e->src);
 	      ggc_free (dummy_switch);
 	    }
 	  else
-	    cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
+	    cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src);
 	}
 
       /* We couldn't find an invariant.  But, callers of this
@@ -555,7 +525,6 @@  simplify_control_stmt_condition_1 (edge e,
 				   tree op1,
 				   gcond *dummy_cond,
 				   pfn_simplify simplify,
-				   bool handle_dominating_asserts,
 				   unsigned limit)
 {
   if (limit == 0)
@@ -575,8 +544,7 @@  simplify_control_stmt_condition_1 (edge e,
      recurse into the LHS to see if there is a dominating ASSERT_EXPR
      of A or of B that makes this condition always true or always false
      along the edge E.  */
-  if (handle_dominating_asserts
-      && (cond_code == EQ_EXPR || cond_code == NE_EXPR)
+  if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
       && TREE_CODE (op0) == SSA_NAME
       && integer_zerop (op1))
     {
@@ -595,7 +563,6 @@  simplify_control_stmt_condition_1 (edge e,
 	    = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
 						 rhs1, NE_EXPR, op1,
 						 dummy_cond, simplify,
-						 handle_dominating_asserts,
 						 limit - 1);
 	  if (res1 == NULL_TREE)
 	    ;
@@ -623,7 +590,6 @@  simplify_control_stmt_condition_1 (edge e,
 	    = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
 						 rhs2, NE_EXPR, op1,
 						 dummy_cond, simplify,
-						 handle_dominating_asserts,
 						 limit - 1);
 	  if (res2 == NULL_TREE)
 	    ;
@@ -689,25 +655,12 @@  simplify_control_stmt_condition_1 (edge e,
 	    = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
 						 rhs1, new_cond, rhs2,
 						 dummy_cond, simplify,
-						 handle_dominating_asserts,
 						 limit - 1);
 	  if (res != NULL_TREE && is_gimple_min_invariant (res))
 	    return res;
 	}
     }
 
-  if (handle_dominating_asserts)
-    {
-      /* Now see if the operand was consumed by an ASSERT_EXPR
-	 which dominates E->src.  If so, we want to replace the
-	 operand with the LHS of the ASSERT_EXPR.  */
-      if (TREE_CODE (op0) == SSA_NAME)
-	op0 = lhs_of_dominating_assert (op0, e->src, stmt);
-
-      if (TREE_CODE (op1) == SSA_NAME)
-	op1 = lhs_of_dominating_assert (op1, e->src, stmt);
-    }
-
   gimple_cond_set_code (dummy_cond, cond_code);
   gimple_cond_set_lhs (dummy_cond, op0);
   gimple_cond_set_rhs (dummy_cond, op1);
@@ -728,7 +681,7 @@  simplify_control_stmt_condition_1 (edge e,
      then use the pass specific callback to simplify the condition.  */
   if (!res
       || !is_gimple_min_invariant (res))
-    res = (*simplify) (dummy_cond, stmt, avail_exprs_stack);
+    res = (*simplify) (dummy_cond, stmt, avail_exprs_stack, e->src);
 
   return res;
 }
@@ -868,8 +821,8 @@  propagate_threaded_block_debug_into (basic_block dest, basic_block src)
    returning TRUE from the toplevel call.   Otherwise do nothing and
    return false.
 
-   DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
-   try and simplify the condition at the end of TAKEN_EDGE->dest.
+   DUMMY_COND, SIMPLIFY are used to try and simplify the condition at the
+   end of TAKEN_EDGE->dest.
 
    The available expression table is referenced via AVAIL_EXPRS_STACK.  */
 
@@ -877,7 +830,6 @@  static bool
 thread_around_empty_blocks (edge taken_edge,
 			    gcond *dummy_cond,
 			    class avail_exprs_stack *avail_exprs_stack,
-			    bool handle_dominating_asserts,
 			    pfn_simplify simplify,
 			    bitmap visited,
 			    vec<jump_thread_edge *> *path)
@@ -928,7 +880,6 @@  thread_around_empty_blocks (edge taken_edge,
 	      return thread_around_empty_blocks (taken_edge,
 						 dummy_cond,
 						 avail_exprs_stack,
-						 handle_dominating_asserts,
 						 simplify,
 						 visited,
 						 path);
@@ -950,7 +901,7 @@  thread_around_empty_blocks (edge taken_edge,
   /* Extract and simplify the condition.  */
   cond = simplify_control_stmt_condition (taken_edge, stmt,
 					  avail_exprs_stack, dummy_cond,
-					  simplify, handle_dominating_asserts);
+					  simplify);
 
   /* If the condition can be statically computed and we have not already
      visited the destination edge, then add the taken edge to our thread
@@ -978,7 +929,6 @@  thread_around_empty_blocks (edge taken_edge,
       thread_around_empty_blocks (taken_edge,
 				  dummy_cond,
 				  avail_exprs_stack,
-				  handle_dominating_asserts,
 				  simplify,
 				  visited,
 				  path);
@@ -1004,10 +954,6 @@  thread_around_empty_blocks (edge taken_edge,
    DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
    to avoid allocating memory.
 
-   HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
-   the simplified condition with left-hand sides of ASSERT_EXPRs they are
-   used in.
-
    STACK is used to undo temporary equivalences created during the walk of
    E->dest.
 
@@ -1024,7 +970,6 @@  thread_around_empty_blocks (edge taken_edge,
 static int
 thread_through_normal_block (edge e,
 			     gcond *dummy_cond,
-			     bool handle_dominating_asserts,
 			     const_and_copies *const_and_copies,
 			     avail_exprs_stack *avail_exprs_stack,
 			     pfn_simplify simplify,
@@ -1032,8 +977,7 @@  thread_through_normal_block (edge e,
 			     bitmap visited)
 {
   /* We want to record any equivalences created by traversing E.  */
-  if (!handle_dominating_asserts)
-    record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
+  record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
 
   /* PHIs create temporary equivalences.
      Note that if we found a PHI that made the block non-threadable, then
@@ -1085,8 +1029,7 @@  thread_through_normal_block (edge e,
 
       /* Extract and simplify the condition.  */
       cond = simplify_control_stmt_condition (e, stmt, avail_exprs_stack,
-					      dummy_cond, simplify,
-					      handle_dominating_asserts);
+					      dummy_cond, simplify);
 
       if (!cond)
 	return 0;
@@ -1135,7 +1078,6 @@  thread_through_normal_block (edge e,
 	  thread_around_empty_blocks (taken_edge,
 				      dummy_cond,
 				      avail_exprs_stack,
-				      handle_dominating_asserts,
 				      simplify,
 				      visited,
 				      path);
@@ -1151,10 +1093,6 @@  thread_through_normal_block (edge e,
    DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
    to avoid allocating memory.
 
-   HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
-   the simplified condition with left-hand sides of ASSERT_EXPRs they are
-   used in.
-
    CONST_AND_COPIES is used to undo temporary equivalences created during the
    walk of E->dest.
 
@@ -1165,11 +1103,10 @@  thread_through_normal_block (edge e,
 void
 thread_across_edge (gcond *dummy_cond,
 		    edge e,
-		    bool handle_dominating_asserts,
 		    class const_and_copies *const_and_copies,
 		    class avail_exprs_stack *avail_exprs_stack,
 		    tree (*simplify) (gimple *, gimple *,
-				      class avail_exprs_stack *))
+				      class avail_exprs_stack *, basic_block))
 {
   bitmap visited = BITMAP_ALLOC (NULL);
 
@@ -1183,7 +1120,6 @@  thread_across_edge (gcond *dummy_cond,
   int threaded;
   if ((e->flags & EDGE_DFS_BACK) == 0)
     threaded = thread_through_normal_block (e, dummy_cond,
-					    handle_dominating_asserts,
 					    const_and_copies,
 					    avail_exprs_stack,
 					    simplify, path,
@@ -1281,14 +1217,12 @@  thread_across_edge (gcond *dummy_cond,
 	found = thread_around_empty_blocks (taken_edge,
 					    dummy_cond,
 					    avail_exprs_stack,
-					    handle_dominating_asserts,
 					    simplify,
 					    visited,
 					    path);
 
 	if (!found)
 	  found = thread_through_normal_block (path->last ()->e, dummy_cond,
-					       handle_dominating_asserts,
 					       const_and_copies,
 					       avail_exprs_stack,
 					       simplify, path,
diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h
index 70658c6..3516f14 100644
--- a/gcc/tree-ssa-threadedge.h
+++ b/gcc/tree-ssa-threadedge.h
@@ -30,10 +30,10 @@  extern void threadedge_initialize_values (void);
 extern void threadedge_finalize_values (void);
 extern bool potentially_threadable_block (basic_block);
 extern void propagate_threaded_block_debug_into (basic_block, basic_block);
-extern void thread_across_edge (gcond *, edge, bool,
+extern void thread_across_edge (gcond *, edge,
 				const_and_copies *,
 				avail_exprs_stack *,
 				tree (*) (gimple *, gimple *,
-					  avail_exprs_stack *));
+					  avail_exprs_stack *, basic_block));
 
 #endif /* GCC_TREE_SSA_THREADEDGE_H */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 2a4c764..82ef742 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10749,6 +10749,33 @@  vrp_fold_stmt (gimple_stmt_iterator *si)
 /* Unwindable const/copy equivalences.  */
 const_and_copies *equiv_stack;
 
+/* Return the LHS of any ASSERT_EXPR where OP appears as the first
+   argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
+   BB.  If no such ASSERT_EXPR is found, return OP.  */
+
+static tree
+lhs_of_dominating_assert (tree op, basic_block bb, gimple *stmt)
+{
+  imm_use_iterator imm_iter;
+  gimple *use_stmt;
+  use_operand_p use_p;
+
+  if (TREE_CODE (op) == SSA_NAME)
+    {
+      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
+	{
+	  use_stmt = USE_STMT (use_p);
+	  if (use_stmt != stmt
+	      && gimple_assign_single_p (use_stmt)
+	      && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR
+	      && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op
+	      && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt)))
+	    return gimple_assign_lhs (use_stmt);
+	}
+    }
+  return op;
+}
+
 /* A trivial wrapper so that we can present the generic jump threading
    code with a simple API for simplifying statements.  STMT is the
    statement we want to simplify, WITHIN_STMT provides the location
@@ -10756,13 +10783,20 @@  const_and_copies *equiv_stack;
 
 static tree
 simplify_stmt_for_jump_threading (gimple *stmt, gimple *within_stmt,
-    class avail_exprs_stack *avail_exprs_stack ATTRIBUTE_UNUSED)
+    class avail_exprs_stack *avail_exprs_stack ATTRIBUTE_UNUSED,
+    basic_block bb)
 {
   if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
-    return vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
-				     gimple_cond_lhs (cond_stmt),
-				     gimple_cond_rhs (cond_stmt),
-				     within_stmt);
+    {
+      tree op0 = gimple_cond_lhs (cond_stmt);
+      op0 = lhs_of_dominating_assert (op0, bb, stmt);
+
+      tree op1 = gimple_cond_rhs (cond_stmt);
+      op1 = lhs_of_dominating_assert (op1, bb, stmt);
+
+      return vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
+				       op0, op1, within_stmt);
+    }
 
   /* We simplify a switch statement by trying to determine which case label
      will be taken.  If we are successful then we return the corresponding
@@ -10773,6 +10807,8 @@  simplify_stmt_for_jump_threading (gimple *stmt, gimple *within_stmt,
       if (TREE_CODE (op) != SSA_NAME)
 	return NULL_TREE;
 
+      op = lhs_of_dominating_assert (op, bb, stmt);
+
       value_range *vr = get_value_range (op);
       if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
 	  || symbolic_range_p (vr))
@@ -10948,7 +10984,7 @@  identify_jump_threads (void)
 	      if (e->flags & (EDGE_IGNORE | EDGE_COMPLEX))
 		continue;
 
-	      thread_across_edge (dummy, e, true, equiv_stack, NULL,
+	      thread_across_edge (dummy, e, equiv_stack, NULL,
 				  simplify_stmt_for_jump_threading);
 	    }
 	}