[PATCH 2/3] Make early return predictor more precise.

marxin mliska@suse.cz
Tue Jun 6 09:05:00 GMT 2017


gcc/ChangeLog:

2017-05-26  Martin Liska  <mliska@suse.cz>

	PR tree-optimization/79489
	* gimplify.c (maybe_add_early_return_predict_stmt): New
	function.
	(gimplify_return_expr): Call the function.
	* predict.c (tree_estimate_probability_bb): Remove handling
	of early return.
	* predict.def: Update comment about early return predictor.
	* gimple-predict.h (is_gimple_predict): New function.
	* tree-inline.c (remap_gimple_stmt): Do not copy early return
	predictors during inlining.
	* predict.def: Change default value of early return to 66.

gcc/testsuite/ChangeLog:

2017-05-31  Martin Liska  <mliska@suse.cz>

	PR tree-optimization/79489
	* gcc.dg/tree-ssa/tailrecursion-1.c: Change tail1 to tailr2.
	* gcc.dg/tree-ssa/tailrecursion-2.c: Likewise.
	* gcc.dg/tree-ssa/tailrecursion-6.c: Likewise.
---
 gcc/gimple-low.c                                |  3 ++
 gcc/gimple-predict.h                            |  8 +++++
 gcc/gimplify.c                                  | 16 ++++++++++
 gcc/predict.c                                   | 41 -------------------------
 gcc/predict.def                                 | 15 ++-------
 gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-1.c |  4 +--
 gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-2.c |  4 +--
 gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c |  4 +--
 gcc/tree-inline.c                               |  7 +++++
 9 files changed, 43 insertions(+), 59 deletions(-)

diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
index 619b9d7bfb1..a56a7b87b88 100644
--- a/gcc/gimple-low.c
+++ b/gcc/gimple-low.c
@@ -30,6 +30,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "calls.h"
 #include "gimple-iterator.h"
 #include "gimple-low.h"
+#include "predict.h"
+#include "gimple-predict.h"
 
 /* The differences between High GIMPLE and Low GIMPLE are the
    following:
@@ -684,6 +686,7 @@ lower_gimple_return (gimple_stmt_iterator *gsi, struct lower_data *data)
   /* When not optimizing, make sure user returns are preserved.  */
   if (!optimize && gimple_has_location (stmt))
     DECL_ARTIFICIAL (tmp_rs.label) = 0;
+
   t = gimple_build_goto (tmp_rs.label);
   gimple_set_location (t, gimple_location (stmt));
   gimple_set_block (t, gimple_block (stmt));
diff --git a/gcc/gimple-predict.h b/gcc/gimple-predict.h
index ba58e12e9e9..0e6c2e1ea01 100644
--- a/gcc/gimple-predict.h
+++ b/gcc/gimple-predict.h
@@ -80,4 +80,12 @@ gimple_build_predict (enum br_predictor predictor, enum prediction outcome)
   return p;
 }
 
+/* Return true if GS is a GIMPLE_PREDICT statement.  */
+
+static inline bool
+is_gimple_predict (const gimple *gs)
+{
+  return gimple_code (gs) == GIMPLE_PREDICT;
+}
+
 #endif  /* GCC_GIMPLE_PREDICT_H */
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index 2c7fc9fabd1..f192a891a8c 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -1428,6 +1428,20 @@ gimplify_bind_expr (tree *expr_p, gimple_seq *pre_p)
   return GS_ALL_DONE;
 }
 
+/* Maybe add early return predict statement to PRE_P sequence.  */
+
+static void
+maybe_add_early_return_predict_stmt (gimple_seq *pre_p)
+{
+  /* If we are not in a conditional context, add PREDICT statement.  */
+  if (gimple_conditional_context ())
+    {
+      gimple *predict = gimple_build_predict (PRED_TREE_EARLY_RETURN,
+					      NOT_TAKEN);
+      gimplify_seq_add_stmt (pre_p, predict);
+    }
+}
+
 /* Gimplify a RETURN_EXPR.  If the expression to be returned is not a
    GIMPLE value, it is assigned to a new temporary and the statement is
    re-written to return the temporary.
@@ -1458,6 +1472,7 @@ gimplify_return_expr (tree stmt, gimple_seq *pre_p)
       || TREE_CODE (ret_expr) == RESULT_DECL
       || ret_expr == error_mark_node)
     {
+      maybe_add_early_return_predict_stmt (pre_p);
       greturn *ret = gimple_build_return (ret_expr);
       gimple_set_no_warning (ret, TREE_NO_WARNING (stmt));
       gimplify_seq_add_stmt (pre_p, ret);
@@ -1525,6 +1540,7 @@ gimplify_return_expr (tree stmt, gimple_seq *pre_p)
 
   gimplify_and_add (TREE_OPERAND (stmt, 0), pre_p);
 
+  maybe_add_early_return_predict_stmt (pre_p);
   ret = gimple_build_return (result);
   gimple_set_no_warning (ret, TREE_NO_WARNING (stmt));
   gimplify_seq_add_stmt (pre_p, ret);
diff --git a/gcc/predict.c b/gcc/predict.c
index ea445e94e46..d561f27342d 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2695,7 +2695,6 @@ tree_estimate_probability_bb (basic_block bb)
 {
   edge e;
   edge_iterator ei;
-  gimple *last;
 
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
@@ -2722,46 +2721,6 @@ tree_estimate_probability_bb (basic_block bb)
 	    }
 	}
 
-      /* Predict early returns to be probable, as we've already taken
-	 care for error returns and other cases are often used for
-	 fast paths through function.
-
-	 Since we've already removed the return statements, we are
-	 looking for CFG like:
-
-	 if (conditional)
-	 {
-	 ..
-	 goto return_block
-	 }
-	 some other blocks
-	 return_block:
-	 return_stmt.  */
-      if (e->dest != bb->next_bb
-	  && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
-	  && single_succ_p (e->dest)
-	  && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
-	  && (last = last_stmt (e->dest)) != NULL
-	  && gimple_code (last) == GIMPLE_RETURN)
-	{
-	  edge e1;
-	  edge_iterator ei1;
-
-	  if (single_succ_p (bb))
-	    {
-	      FOR_EACH_EDGE (e1, ei1, bb->preds)
-		if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
-		    && !predicted_by_p (e1->src, PRED_CONST_RETURN)
-		    && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
-		  predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
-	    }
-	  else
-	    if (!predicted_by_p (e->src, PRED_NULL_RETURN)
-		&& !predicted_by_p (e->src, PRED_CONST_RETURN)
-		&& !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
-	      predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
-	}
-
       /* Look for block we are guarding (ie we dominate it,
 	 but it doesn't postdominate us).  */
       if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
diff --git a/gcc/predict.def b/gcc/predict.def
index fcda6c48f11..f7b2bf7738c 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -128,18 +128,9 @@ DEF_PREDICTOR (PRED_POLYMORPHIC_CALL, "polymorphic call", HITRATE (59), 0)
    indefinitely.  */
 DEF_PREDICTOR (PRED_RECURSIVE_CALL, "recursive call", HITRATE (75), 0)
 
-/* Branch causing function to terminate is probably not taken. 
-   FIXME: early return currently predicts code:
-   int foo (int a)
-   {
-      if (a)
-	bar();
-      else
-	bar2();
-   }
-   even though there is no return statement involved.  We probably want to track
-   this from FE or retire the predictor.  */
-DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE (54), 0)
+/* Branch causing function to terminate is probably not taken.  */
+DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE (66),
+	       0)
 
 /* Branch containing goto is probably not taken.
    FIXME: Currently not used.  */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-1.c b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-1.c
index fd65c774daf..b3151da11a6 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-1.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr1-details" } */
+/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr2-details" } */
 int
 t(int a)
 {
@@ -8,4 +8,4 @@ t(int a)
 	else
 		return 0;
 }
-/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr1"} } */
+/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr2"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-2.c b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-2.c
index e982b0c2065..88b506befc2 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-2.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr1-details" } */
+/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr2-details" } */
 int
 t(char *a)
 {
@@ -9,4 +9,4 @@ t(char *a)
 	else
 		return 0;
 }
-/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr1"} } */
+/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr2"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c
index 38fa1042cbc..715d5d9ed65 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr1-details" } */
+/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr2-details" } */
 int
 foo (int a)
 {
@@ -8,4 +8,4 @@ foo (int a)
 	else
 		return 0;
 }
-/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr1"} } */
+/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr2"} } */
diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
index f3ec404ef09..3f3813cb062 100644
--- a/gcc/tree-inline.c
+++ b/gcc/tree-inline.c
@@ -1629,6 +1629,13 @@ remap_gimple_stmt (gimple *stmt, copy_body_data *id)
 	  gimple_seq_add_stmt (&stmts, copy);
 	  return stmts;
 	}
+      if (is_gimple_predict (stmt))
+	{
+	  /* Do not copy early return predictor that does not make sense
+	     after inlining.  */
+	  if (gimple_predict_predictor (stmt) == PRED_TREE_EARLY_RETURN)
+	    return stmts;
+	}
 
       /* Create a new deep copy of the statement.  */
       copy = gimple_copy (stmt);
-- 
2.13.0




More information about the Gcc-patches mailing list