[2/2,V3] Use post-dom info to update if/switch predicate (PR ipa/91089)
diff mbox series

Message ID BYAPR01MB48690113E7A250FD7B343006F78C0@BYAPR01MB4869.prod.exchangelabs.com
State New
Headers show
Series
  • [1/2,V3] Setup predicate for switch default case in IPA (PR ipa/91089)
Related show

Commit Message

Feng Xue OS Sept. 16, 2019, 10:16 a.m. UTC
This one is split from original patch.

Feng
---

Comments

Jan Hubicka Sept. 16, 2019, 3:05 p.m. UTC | #1
> This one is split from original patch.

This patch is also OK (modulo the changelog entry and testing). Please
wait with comitting this for bit over a day after commiting the first so
the periodic benchmarks picks each change differently.

Thanks,
Honza
> 
> Feng
> ---
> diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
> index 1bf1806eaf8..5423756d275 100644
> --- a/gcc/ipa-fnsummary.c
> +++ b/gcc/ipa-fnsummary.c
> @@ -1197,8 +1197,14 @@ set_cond_stmt_execution_predicate (struct ipa_func_body_info *fbi,
>  				      ? code : inverted_code);
>  	  /* invert_tree_comparison will return ERROR_MARK on FP
>  	     comparsions that are not EQ/NE instead of returning proper
> -	     unordered one.  Be sure it is not confused with NON_CONSTANT.  */
> -	  if (this_code != ERROR_MARK)
> +	     unordered one.  Be sure it is not confused with NON_CONSTANT.
> +
> +	     And if the edge's target is the final block of diamond CFG graph
> +	     of this conditional statement, we do not need to compute
> +	     predicate for the edge because the final block's predicate must
> +	     be at least as that of the first block of the statement.  */
> +	  if (this_code != ERROR_MARK
> +	      && !dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest))
>  	    {
>  	      predicate p
>  		= add_condition (summary, index, size, &aggpos, this_code,
> @@ -1282,6 +1288,14 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
>        *(predicate *) e->aux = false;
>      }
>  
> +  e = gimple_switch_edge (cfun, last, 0);
> +  /* Set BOUND_COUNT to maximum count to bypass computing predicate for
> +     default case if its target basic block is in convergence point of all
> +     switch cases, which can be determined by checking whether it
> +     post-dominates the switch statement.  */
> +  if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest))
> +    bound_count = INT_MAX;
> +
>    n = gimple_switch_num_labels (last);
>    for (case_idx = 1; case_idx < n; ++case_idx)
>      {
> @@ -1293,7 +1307,12 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
>        min = CASE_LOW (cl);
>        max = CASE_HIGH (cl);
>  
> -      if (!max)
> +      /* The case's target basic block is in convergence point of all switch
> +	 cases, its predicate should be at least as that of the switch
> +	 statement.  */
> +      if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest))
> +	p = true;
> +      else if (!max)
>  	p = add_condition (summary, index, size, &aggpos, EQ_EXPR,
>  			   unshare_expr_without_location (min));
>        else
> @@ -1463,10 +1482,10 @@ compute_bb_predicates (struct ipa_func_body_info *fbi,
>  		    break;
>  		}
>  	    }
> -	  if (p == false)
> -	    gcc_checking_assert (!bb->aux);
> -	  else
> +	  if (p != false)
>  	    {
> +	      basic_block pdom_bb;
> +
>  	      if (!bb->aux)
>  		{
>  		  done = false;
> @@ -1485,6 +1504,34 @@ compute_bb_predicates (struct ipa_func_body_info *fbi,
>  		      *((predicate *) bb->aux) = p;
>  		    }
>  		}
> +
> +	      /* For switch/if statement, we can OR-combine predicates of all
> +		 its cases/branches to get predicate for basic block in their
> +		 convergence point, but sometimes this will generate very
> +		 complicated predicate.  Actually, we can get simplified
> +		 predicate in another way by using the fact that predicate
> +		 for a basic block must also hold true for its post dominators.
> +		 To be specific, basic block in convergence point of
> +		 conditional statement should include predicate of the
> +		 statement.  */
> +	      pdom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
> +	      if (pdom_bb == EXIT_BLOCK_PTR_FOR_FN (my_function) || !pdom_bb)
> +		;
> +	      else if (!pdom_bb->aux)
> +		{
> +		  done = false;
> +		  pdom_bb->aux = edge_predicate_pool.allocate ();
> +		  *((predicate *) pdom_bb->aux) = p;
> +		}
> +	      else if (p != *(predicate *) pdom_bb->aux)
> +		{
> +		  p = p.or_with (summary->conds, *(predicate *)pdom_bb->aux);
> +		  if (p != *(predicate *) pdom_bb->aux)
> +		    {
> +		      done = false;
> +		      *((predicate *) pdom_bb->aux) = p;
> +		    }
> +		}
>  	    }
>  	}
>      }
> @@ -2089,6 +2136,7 @@ analyze_function_body (struct cgraph_node *node, bool early)
>    if (opt_for_fn (node->decl, optimize))
>      {
>        calculate_dominance_info (CDI_DOMINATORS);
> +      calculate_dominance_info (CDI_POST_DOMINATORS);
>        if (!early)
>          loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
>        else
> @@ -2469,6 +2517,7 @@ analyze_function_body (struct cgraph_node *node, bool early)
>        else if (!ipa_edge_args_sum)
>  	ipa_free_all_node_params ();
>        free_dominance_info (CDI_DOMINATORS);
> +      free_dominance_info (CDI_POST_DOMINATORS);
>      }
>    if (dump_file)
>      {
> diff --git a/gcc/testsuite/gcc.dg/ipa/pr91089.c b/gcc/testsuite/gcc.dg/ipa/pr91089.c
> index e9e206fc24d..92b5550aa76 100644
> --- a/gcc/testsuite/gcc.dg/ipa/pr91089.c
> +++ b/gcc/testsuite/gcc.dg/ipa/pr91089.c
> @@ -41,6 +41,52 @@ int callee (int i)
>    return data += i;
>  }
>  
> +int fn2 ();
> +
> +int callee_complex_predicate (int i)
> +{
> +  switch (i )
> +    {
> +      case 0:
> +	fn ();
> +	fn ();
> +	fn ();
> +      case 1:
> +	fn ();
> +	fn ();
> +      case -1:
> +	fn ();
> +      case -2:
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	fn ();
> +	data += i;
> +	break;
> +    }
> +
> +  if (i == 1000)
> +    {
> +      int j;
> +
> +      for (j = 0; j < 100; j++)
> +	fn2 ();
> +    }
> +  return i + 3;
> +}
> +
>  int caller ()
>  {
>    return callee (-127) +
> @@ -60,3 +106,4 @@ int caller ()
>  /* { dg-final { scan-ipa-dump "op0 != 0"   "fnsummary" } } */
>  /* { dg-final { scan-ipa-dump "op0 < 5"    "fnsummary" } } */
>  /* { dg-final { scan-ipa-dump "op0 > 7"    "fnsummary" } } */
> +/* { dg-final { scan-ipa-dump "loop depth: 1 .+ time:\[ \]*\[0-9\]+ predicate: \\(op0 == 1000\\)" "fnsummary" } } */
> -- 
> 2.17.1
Feng Xue OS Sept. 17, 2019, 1:54 p.m. UTC | #2
> This patch is also OK (modulo the changelog entry and testing). Please
> wait with comitting this for bit over a day after commiting the first so
> the periodic benchmarks picks each change differently.

Understood. Thanks for this.

Feng

Patch
diff mbox series

diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index 1bf1806eaf8..5423756d275 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -1197,8 +1197,14 @@  set_cond_stmt_execution_predicate (struct ipa_func_body_info *fbi,
 				      ? code : inverted_code);
 	  /* invert_tree_comparison will return ERROR_MARK on FP
 	     comparsions that are not EQ/NE instead of returning proper
-	     unordered one.  Be sure it is not confused with NON_CONSTANT.  */
-	  if (this_code != ERROR_MARK)
+	     unordered one.  Be sure it is not confused with NON_CONSTANT.
+
+	     And if the edge's target is the final block of diamond CFG graph
+	     of this conditional statement, we do not need to compute
+	     predicate for the edge because the final block's predicate must
+	     be at least as that of the first block of the statement.  */
+	  if (this_code != ERROR_MARK
+	      && !dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest))
 	    {
 	      predicate p
 		= add_condition (summary, index, size, &aggpos, this_code,
@@ -1282,6 +1288,14 @@  set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
       *(predicate *) e->aux = false;
     }
 
+  e = gimple_switch_edge (cfun, last, 0);
+  /* Set BOUND_COUNT to maximum count to bypass computing predicate for
+     default case if its target basic block is in convergence point of all
+     switch cases, which can be determined by checking whether it
+     post-dominates the switch statement.  */
+  if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest))
+    bound_count = INT_MAX;
+
   n = gimple_switch_num_labels (last);
   for (case_idx = 1; case_idx < n; ++case_idx)
     {
@@ -1293,7 +1307,12 @@  set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
       min = CASE_LOW (cl);
       max = CASE_HIGH (cl);
 
-      if (!max)
+      /* The case's target basic block is in convergence point of all switch
+	 cases, its predicate should be at least as that of the switch
+	 statement.  */
+      if (dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest))
+	p = true;
+      else if (!max)
 	p = add_condition (summary, index, size, &aggpos, EQ_EXPR,
 			   unshare_expr_without_location (min));
       else
@@ -1463,10 +1482,10 @@  compute_bb_predicates (struct ipa_func_body_info *fbi,
 		    break;
 		}
 	    }
-	  if (p == false)
-	    gcc_checking_assert (!bb->aux);
-	  else
+	  if (p != false)
 	    {
+	      basic_block pdom_bb;
+
 	      if (!bb->aux)
 		{
 		  done = false;
@@ -1485,6 +1504,34 @@  compute_bb_predicates (struct ipa_func_body_info *fbi,
 		      *((predicate *) bb->aux) = p;
 		    }
 		}
+
+	      /* For switch/if statement, we can OR-combine predicates of all
+		 its cases/branches to get predicate for basic block in their
+		 convergence point, but sometimes this will generate very
+		 complicated predicate.  Actually, we can get simplified
+		 predicate in another way by using the fact that predicate
+		 for a basic block must also hold true for its post dominators.
+		 To be specific, basic block in convergence point of
+		 conditional statement should include predicate of the
+		 statement.  */
+	      pdom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
+	      if (pdom_bb == EXIT_BLOCK_PTR_FOR_FN (my_function) || !pdom_bb)
+		;
+	      else if (!pdom_bb->aux)
+		{
+		  done = false;
+		  pdom_bb->aux = edge_predicate_pool.allocate ();
+		  *((predicate *) pdom_bb->aux) = p;
+		}
+	      else if (p != *(predicate *) pdom_bb->aux)
+		{
+		  p = p.or_with (summary->conds, *(predicate *)pdom_bb->aux);
+		  if (p != *(predicate *) pdom_bb->aux)
+		    {
+		      done = false;
+		      *((predicate *) pdom_bb->aux) = p;
+		    }
+		}
 	    }
 	}
     }
@@ -2089,6 +2136,7 @@  analyze_function_body (struct cgraph_node *node, bool early)
   if (opt_for_fn (node->decl, optimize))
     {
       calculate_dominance_info (CDI_DOMINATORS);
+      calculate_dominance_info (CDI_POST_DOMINATORS);
       if (!early)
         loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
       else
@@ -2469,6 +2517,7 @@  analyze_function_body (struct cgraph_node *node, bool early)
       else if (!ipa_edge_args_sum)
 	ipa_free_all_node_params ();
       free_dominance_info (CDI_DOMINATORS);
+      free_dominance_info (CDI_POST_DOMINATORS);
     }
   if (dump_file)
     {
diff --git a/gcc/testsuite/gcc.dg/ipa/pr91089.c b/gcc/testsuite/gcc.dg/ipa/pr91089.c
index e9e206fc24d..92b5550aa76 100644
--- a/gcc/testsuite/gcc.dg/ipa/pr91089.c
+++ b/gcc/testsuite/gcc.dg/ipa/pr91089.c
@@ -41,6 +41,52 @@  int callee (int i)
   return data += i;
 }
 
+int fn2 ();
+
+int callee_complex_predicate (int i)
+{
+  switch (i )
+    {
+      case 0:
+	fn ();
+	fn ();
+	fn ();
+      case 1:
+	fn ();
+	fn ();
+      case -1:
+	fn ();
+      case -2:
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	fn ();
+	data += i;
+	break;
+    }
+
+  if (i == 1000)
+    {
+      int j;
+
+      for (j = 0; j < 100; j++)
+	fn2 ();
+    }
+  return i + 3;
+}
+
 int caller ()
 {
   return callee (-127) +
@@ -60,3 +106,4 @@  int caller ()
 /* { dg-final { scan-ipa-dump "op0 != 0"   "fnsummary" } } */
 /* { dg-final { scan-ipa-dump "op0 < 5"    "fnsummary" } } */
 /* { dg-final { scan-ipa-dump "op0 > 7"    "fnsummary" } } */
+/* { dg-final { scan-ipa-dump "loop depth: 1 .+ time:\[ \]*\[0-9\]+ predicate: \\(op0 == 1000\\)" "fnsummary" } } */