public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH 0/3] Rework early return and hot/cold label predictors
@ 2017-06-06  9:05 marxin
  2017-06-06  9:05 ` [PATCH 3/3] Rework cold and hot label attributes in predict.c marxin
                   ` (3 more replies)
  0 siblings, 4 replies; 29+ messages in thread
From: marxin @ 2017-06-06  9:05 UTC (permalink / raw)
  To: gcc-patches; +Cc: hubicka

Hello.

As mentioned in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79489#c1
early-return predictors is currenty not much precise. I decided to
come up with GIMPLE_PREDICT statement that I put early and thus
more precise numbers can be seen.

For SPEC 2017 we can improve the predictor from:
HEURISTICS                               BRANCHES  (REL)  BR. HITRATE            HITRATE       COVERAGE COVERAGE  (REL)  predict.def  (REL)
early return (on trees)                     17804  11.7%       63.54%   55.14% /  85.46%    38154989508   38.15G   5.4%          54%   1.1%

to:

early return (on trees)                      3692   4.1%       79.55%   66.22% /  76.14%    15778842701   15.78G   2.4%          66%   0.2%

For tests I had to change couple of tailrecursion tests, where recursion
happens in tailr2 pass. It's not done in tailr1 due to GIMPLE_PREDICT
statement.

Apart from that I would like to add a sanity unit tests for values
of predictors. And finally, I was asked by Honza to transform cold/hot
label predictors to GIMPLE_PREDICT as well.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Ready to be installed?
Martin

marxin (3):
  Come up with selftests for predict.c.
  Make early return predictor more precise.
  Rework cold and hot label attributes in predict.c.

 gcc/gimple-low.c                                |   3 +
 gcc/gimple-predict.h                            |   8 ++
 gcc/gimplify.c                                  |  26 +++++-
 gcc/predict.c                                   | 103 +++++++++---------------
 gcc/predict.def                                 |  15 +---
 gcc/selftest-run-tests.c                        |   1 +
 gcc/selftest.h                                  |   1 +
 gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c  |   4 +-
 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 ++
 12 files changed, 95 insertions(+), 85 deletions(-)

-- 
2.13.0

^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH 2/3] Make early return predictor more precise.
  2017-06-06  9:05 [PATCH 0/3] Rework early return and hot/cold label predictors marxin
  2017-06-06  9:05 ` [PATCH 3/3] Rework cold and hot label attributes in predict.c marxin
@ 2017-06-06  9:05 ` marxin
  2017-06-09 14:08   ` Jan Hubicka
  2017-06-06  9:05 ` [PATCH 1/3] Come up with selftests for predict.c marxin
  2017-06-21 13:06 ` [PATCH 4/N] Recover GOTO predictor Martin Liška
  3 siblings, 1 reply; 29+ messages in thread
From: marxin @ 2017-06-06  9:05 UTC (permalink / raw)
  To: gcc-patches; +Cc: hubicka

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


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH 1/3] Come up with selftests for predict.c.
  2017-06-06  9:05 [PATCH 0/3] Rework early return and hot/cold label predictors marxin
  2017-06-06  9:05 ` [PATCH 3/3] Rework cold and hot label attributes in predict.c marxin
  2017-06-06  9:05 ` [PATCH 2/3] Make early return predictor more precise marxin
@ 2017-06-06  9:05 ` marxin
  2017-06-06 10:44   ` David Malcolm
  2017-06-21 13:06 ` [PATCH 4/N] Recover GOTO predictor Martin Liška
  3 siblings, 1 reply; 29+ messages in thread
From: marxin @ 2017-06-06  9:05 UTC (permalink / raw)
  To: gcc-patches; +Cc: hubicka

gcc/ChangeLog:

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

	* predict.c (struct branch_predictor): New struct.
	(test_prediction_value_range): New test.
	(predict_tests_c_tests): New function.
	* selftest-run-tests.c (selftest::run_tests): Run the function.
	* selftest.h: Declare new tests.
---
 gcc/predict.c            | 39 +++++++++++++++++++++++++++++++++++++++
 gcc/selftest-run-tests.c |  1 +
 gcc/selftest.h           |  1 +
 3 files changed, 41 insertions(+)

diff --git a/gcc/predict.c b/gcc/predict.c
index ac35fa41129..ea445e94e46 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -57,6 +57,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "ipa-utils.h"
 #include "gimple-pretty-print.h"
+#include "selftest.h"
 
 /* Enum with reasons why a predictor is ignored.  */
 
@@ -3803,3 +3804,41 @@ force_edge_cold (edge e, bool impossible)
 		 impossible ? "impossible" : "cold");
     }
 }
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Test that value range of predictor values defined in predict.def is
+   within range [51, 100].  */
+
+struct branch_predictor
+{
+  const char *name;
+  unsigned probability;
+};
+
+#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
+
+static void
+test_prediction_value_range ()
+{
+  branch_predictor predictors[] = {
+#include "predict.def"
+    {NULL, -1}
+  };
+
+  for (unsigned i = 0; predictors[i].name != NULL; i++)
+    ASSERT_TRUE (100 * predictors[i].probability / REG_BR_PROB_BASE > 50);
+}
+
+/* Run all of the selfests within this file.  */
+
+void
+predict_tests_c_tests ()
+{
+  test_prediction_value_range ();
+}
+
+} // namespace selftest
+#endif /* CHECKING_P.  */
diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
index f62bc72b072..af511a47681 100644
--- a/gcc/selftest-run-tests.c
+++ b/gcc/selftest-run-tests.c
@@ -92,6 +92,7 @@ selftest::run_tests ()
     targetm.run_target_selftests ();
 
   store_merging_c_tests ();
+  predict_tests_c_tests ();
 
   /* Run any lang-specific selftests.  */
   lang_hooks.run_lang_selftests ();
diff --git a/gcc/selftest.h b/gcc/selftest.h
index dad53e9fe09..e84b309359d 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -196,6 +196,7 @@ extern void tree_c_tests ();
 extern void tree_cfg_c_tests ();
 extern void vec_c_tests ();
 extern void wide_int_cc_tests ();
+extern void predict_tests_c_tests ();
 
 extern int num_passes;
 
-- 
2.13.0


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH 3/3] Rework cold and hot label attributes in predict.c.
  2017-06-06  9:05 [PATCH 0/3] Rework early return and hot/cold label predictors marxin
@ 2017-06-06  9:05 ` marxin
  2017-06-09 14:04   ` Jan Hubicka
  2017-06-06  9:05 ` [PATCH 2/3] Make early return predictor more precise marxin
                   ` (2 subsequent siblings)
  3 siblings, 1 reply; 29+ messages in thread
From: marxin @ 2017-06-06  9:05 UTC (permalink / raw)
  To: gcc-patches; +Cc: hubicka

gcc/ChangeLog:

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

	* gimplify.c (gimplify_label_expr): Insert GIMPLE_PREDICT
	statements on cold and hot labels.
	* predict.c (tree_estimate_probability_bb): Remove the
	prediction from this place.

gcc/testsuite/ChangeLog:

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

	* gcc.dg/tree-ssa/attr-hotcold-2.c: Update scanned patterns.
---
 gcc/gimplify.c                                 | 10 +++++++++-
 gcc/predict.c                                  | 23 -----------------------
 gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c |  4 ++--
 3 files changed, 11 insertions(+), 26 deletions(-)

diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index f192a891a8c..b2818e2465f 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -2356,10 +2356,18 @@ gimplify_label_expr (tree *expr_p, gimple_seq *pre_p)
   gcc_assert (decl_function_context (LABEL_EXPR_LABEL (*expr_p))
 	      == current_function_decl);
 
-  glabel *label_stmt = gimple_build_label (LABEL_EXPR_LABEL (*expr_p));
+  tree label = LABEL_EXPR_LABEL (*expr_p);
+  glabel *label_stmt = gimple_build_label (label);
   gimple_set_location (label_stmt, EXPR_LOCATION (*expr_p));
   gimplify_seq_add_stmt (pre_p, label_stmt);
 
+  if (lookup_attribute ("cold", DECL_ATTRIBUTES (label)))
+    gimple_seq_add_stmt (pre_p, gimple_build_predict (PRED_COLD_LABEL,
+						      NOT_TAKEN));
+  else if (lookup_attribute ("hot", DECL_ATTRIBUTES (label)))
+    gimple_seq_add_stmt (pre_p, gimple_build_predict (PRED_HOT_LABEL,
+						      TAKEN));
+
   return GS_ALL_DONE;
 }
 
diff --git a/gcc/predict.c b/gcc/predict.c
index d561f27342d..419a4842f03 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2698,29 +2698,6 @@ tree_estimate_probability_bb (basic_block bb)
 
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
-      /* Predict edges to user labels with attributes.  */
-      if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
-	{
-	  gimple_stmt_iterator gi;
-	  for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
-	    {
-	      glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi));
-	      tree decl;
-
-	      if (!label_stmt)
-		break;
-	      decl = gimple_label_label (label_stmt);
-	      if (DECL_ARTIFICIAL (decl))
-		continue;
-
-	      /* Finally, we have a user-defined label.  */
-	      if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl)))
-		predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN);
-	      else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl)))
-		predict_edge_def (e, PRED_HOT_LABEL, 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/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
index 13d2916c47b..184dd10ddae 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
@@ -20,9 +20,9 @@ void f(int x, int y)
 
 /* { dg-final { scan-tree-dump-times "hot label heuristics" 1 "profile_estimate" } } */
 /* { dg-final { scan-tree-dump-times "cold label heuristics" 1 "profile_estimate" } } */
-/* { dg-final { scan-tree-dump-times "block 4, loop depth 0, count 0, freq \[1-4\]\[^0-9\]" 3 "profile_estimate" } } */
+/* { dg-final { scan-tree-dump "A \\\[0\\\..*\\\]" "profile_estimate" } } */
 
 /* Note: we're attempting to match some number > 6000, i.e. > 60%.
    The exact number ought to be tweekable without having to juggle
    the testcase around too much.  */
-/* { dg-final { scan-tree-dump-times "block 5, loop depth 0, count 0, freq \[6-9\]\[0-9\]\[0-9\]\[0-9\]" 3 "profile_estimate" } } */
+/* { dg-final { scan-tree-dump "B \\\[\[6-9\]\[0-9\]\\\..*\\\]" "profile_estimate" } } */
-- 
2.13.0

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 1/3] Come up with selftests for predict.c.
  2017-06-06  9:05 ` [PATCH 1/3] Come up with selftests for predict.c marxin
@ 2017-06-06 10:44   ` David Malcolm
  2017-06-08 12:30     ` Martin Liška
  0 siblings, 1 reply; 29+ messages in thread
From: David Malcolm @ 2017-06-06 10:44 UTC (permalink / raw)
  To: marxin, gcc-patches; +Cc: hubicka

On Tue, 2017-06-06 at 10:55 +0200, marxin wrote:

Some minor nits below.

> gcc/ChangeLog:
> 
> 2017-05-26  Martin Liska  <mliska@suse.cz>
> 
> 	* predict.c (struct branch_predictor): New struct.
> 	(test_prediction_value_range): New test.
> 	(predict_tests_c_tests): New function.
> 	* selftest-run-tests.c (selftest::run_tests): Run the function.
> 	* selftest.h: Declare new tests.
> ---
>  gcc/predict.c            | 39
> +++++++++++++++++++++++++++++++++++++++
>  gcc/selftest-run-tests.c |  1 +
>  gcc/selftest.h           |  1 +
>  3 files changed, 41 insertions(+)
> 
> diff --git a/gcc/predict.c b/gcc/predict.c
> index ac35fa41129..ea445e94e46 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-scalar-evolution.h"
>  #include "ipa-utils.h"
>  #include "gimple-pretty-print.h"
> +#include "selftest.h"
>  
>  /* Enum with reasons why a predictor is ignored.  */
>  
> @@ -3803,3 +3804,41 @@ force_edge_cold (edge e, bool impossible)
>  		 impossible ? "impossible" : "cold");
>      }
>  }
> +
> +#if CHECKING_P
> +
> +namespace selftest {
> +
> +/* Test that value range of predictor values defined in predict.def
> is
> +   within range [51, 100].  */
> +
> +struct branch_predictor
> +{
> +  const char *name;
> +  unsigned probability;
> +};
> +
> +#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
> +
> +static void
> +test_prediction_value_range ()
> +{
> +  branch_predictor predictors[] = {
> +#include "predict.def"
> +    {NULL, -1}
> +  };
> +
> +  for (unsigned i = 0; predictors[i].name != NULL; i++)
> +    ASSERT_TRUE (100 * predictors[i].probability / REG_BR_PROB_BASE
> > 50);

Minor nit: should there be a #undef DEF_PREDICTOR after the #include?

Minor nits: the comment says it verifies that things are in the range
51, 100.  Should it be >= 51 rather than > 50?  Should there be a test
that it's <= 100?  (I'm not familiar with the predict code, I just
noticed this when reading the comment).

> +}
> +
> +/* Run all of the selfests within this file.  */
> +
> +void
> +predict_tests_c_tests ()
> +{

Minor nit: to follow the pattern used in the other selftests, we've
been naming these "run all selftests within this file" functions after
the filename.  Given this is in predict.c, this should be
"predict_c_tests ()" to follow the pattern.

> +  test_prediction_value_range ();
> +}
> +
> +} // namespace selftest
> +#endif /* CHECKING_P.  */
> diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
> index f62bc72b072..af511a47681 100644
> --- a/gcc/selftest-run-tests.c
> +++ b/gcc/selftest-run-tests.c
> @@ -92,6 +92,7 @@ selftest::run_tests ()
>      targetm.run_target_selftests ();
>  
>    store_merging_c_tests ();
> +  predict_tests_c_tests ();

...and here.


>    /* Run any lang-specific selftests.  */
>    lang_hooks.run_lang_selftests ();
> diff --git a/gcc/selftest.h b/gcc/selftest.h
> index dad53e9fe09..e84b309359d 100644
> --- a/gcc/selftest.h
> +++ b/gcc/selftest.h
> @@ -196,6 +196,7 @@ extern void tree_c_tests ();
>  extern void tree_cfg_c_tests ();
>  extern void vec_c_tests ();
>  extern void wide_int_cc_tests ();
> +extern void predict_tests_c_tests ();

(etc)
 
>  extern int num_passes;

Thanks; hope this is constructive.
Dave

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 1/3] Come up with selftests for predict.c.
  2017-06-06 10:44   ` David Malcolm
@ 2017-06-08 12:30     ` Martin Liška
  2017-06-08 13:09       ` David Malcolm
  2017-06-08 23:07       ` Jan Hubicka
  0 siblings, 2 replies; 29+ messages in thread
From: Martin Liška @ 2017-06-08 12:30 UTC (permalink / raw)
  To: David Malcolm, gcc-patches; +Cc: hubicka

[-- Attachment #1: Type: text/plain, Size: 3657 bytes --]

On 06/06/2017 12:44 PM, David Malcolm wrote:
> On Tue, 2017-06-06 at 10:55 +0200, marxin wrote:
> 
> Some minor nits below.
> 
>> gcc/ChangeLog:
>>
>> 2017-05-26  Martin Liska  <mliska@suse.cz>
>>
>> 	* predict.c (struct branch_predictor): New struct.
>> 	(test_prediction_value_range): New test.
>> 	(predict_tests_c_tests): New function.
>> 	* selftest-run-tests.c (selftest::run_tests): Run the function.
>> 	* selftest.h: Declare new tests.
>> ---
>>  gcc/predict.c            | 39
>> +++++++++++++++++++++++++++++++++++++++
>>  gcc/selftest-run-tests.c |  1 +
>>  gcc/selftest.h           |  1 +
>>  3 files changed, 41 insertions(+)
>>
>> diff --git a/gcc/predict.c b/gcc/predict.c
>> index ac35fa41129..ea445e94e46 100644
>> --- a/gcc/predict.c
>> +++ b/gcc/predict.c
>> @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3.  If not see
>>  #include "tree-scalar-evolution.h"
>>  #include "ipa-utils.h"
>>  #include "gimple-pretty-print.h"
>> +#include "selftest.h"
>>  
>>  /* Enum with reasons why a predictor is ignored.  */
>>  
>> @@ -3803,3 +3804,41 @@ force_edge_cold (edge e, bool impossible)
>>  		 impossible ? "impossible" : "cold");
>>      }
>>  }
>> +
>> +#if CHECKING_P
>> +
>> +namespace selftest {
>> +
>> +/* Test that value range of predictor values defined in predict.def
>> is
>> +   within range [51, 100].  */
>> +
>> +struct branch_predictor
>> +{
>> +  const char *name;
>> +  unsigned probability;
>> +};
>> +
>> +#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
>> +
>> +static void
>> +test_prediction_value_range ()
>> +{
>> +  branch_predictor predictors[] = {
>> +#include "predict.def"
>> +    {NULL, -1}
>> +  };
>> +
>> +  for (unsigned i = 0; predictors[i].name != NULL; i++)
>> +    ASSERT_TRUE (100 * predictors[i].probability / REG_BR_PROB_BASE
>>> 50);
> 
> Minor nit: should there be a #undef DEF_PREDICTOR after the #include?

Hello.

Yes, that should be undefined.

> 
> Minor nits: the comment says it verifies that things are in the range
> 51, 100.  Should it be >= 51 rather than > 50?  Should there be a test
> that it's <= 100?  (I'm not familiar with the predict code, I just
> noticed this when reading the comment).

Should be in range (50,100], fixed accordingly.

> 
>> +}
>> +
>> +/* Run all of the selfests within this file.  */
>> +
>> +void
>> +predict_tests_c_tests ()
>> +{
> 
> Minor nit: to follow the pattern used in the other selftests, we've
> been naming these "run all selftests within this file" functions after
> the filename.  Given this is in predict.c, this should be
> "predict_c_tests ()" to follow the pattern.

I followed your naming scheme.

Thanks for review,
Martin

> 
>> +  test_prediction_value_range ();
>> +}
>> +
>> +} // namespace selftest
>> +#endif /* CHECKING_P.  */
>> diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
>> index f62bc72b072..af511a47681 100644
>> --- a/gcc/selftest-run-tests.c
>> +++ b/gcc/selftest-run-tests.c
>> @@ -92,6 +92,7 @@ selftest::run_tests ()
>>      targetm.run_target_selftests ();
>>  
>>    store_merging_c_tests ();
>> +  predict_tests_c_tests ();
> 
> ...and here.
> 
> 
>>    /* Run any lang-specific selftests.  */
>>    lang_hooks.run_lang_selftests ();
>> diff --git a/gcc/selftest.h b/gcc/selftest.h
>> index dad53e9fe09..e84b309359d 100644
>> --- a/gcc/selftest.h
>> +++ b/gcc/selftest.h
>> @@ -196,6 +196,7 @@ extern void tree_c_tests ();
>>  extern void tree_cfg_c_tests ();
>>  extern void vec_c_tests ();
>>  extern void wide_int_cc_tests ();
>> +extern void predict_tests_c_tests ();
> 
> (etc)
>  
>>  extern int num_passes;
> 
> Thanks; hope this is constructive.
> Dave
> 


[-- Attachment #2: 0001-Come-up-with-selftests-for-predict.c-v2.patch --]
[-- Type: text/x-patch, Size: 2690 bytes --]

From 05d47c50fbc72fcf4f91e1cd923bf9453e13eddd Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Tue, 6 Jun 2017 10:55:10 +0200
Subject: [PATCH] Come up with selftests for predict.c.

gcc/ChangeLog:

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

	* predict.c (struct branch_predictor): New struct.
	(test_prediction_value_range): New test.
	(predict_c_tests): New function.
	* selftest-run-tests.c (selftest::run_tests): Run the function.
	* selftest.h: Declare new tests.
---
 gcc/predict.c            | 44 ++++++++++++++++++++++++++++++++++++++++++++
 gcc/selftest-run-tests.c |  1 +
 gcc/selftest.h           |  1 +
 3 files changed, 46 insertions(+)

diff --git a/gcc/predict.c b/gcc/predict.c
index ac35fa41129..5685012d491 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -57,6 +57,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "ipa-utils.h"
 #include "gimple-pretty-print.h"
+#include "selftest.h"
 
 /* Enum with reasons why a predictor is ignored.  */
 
@@ -3803,3 +3804,46 @@ force_edge_cold (edge e, bool impossible)
 		 impossible ? "impossible" : "cold");
     }
 }
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Test that value range of predictor values defined in predict.def is
+   within range (50, 100].  */
+
+struct branch_predictor
+{
+  const char *name;
+  unsigned probability;
+};
+
+#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
+
+static void
+test_prediction_value_range ()
+{
+  branch_predictor predictors[] = {
+#include "predict.def"
+    {NULL, -1}
+  };
+
+  for (unsigned i = 0; predictors[i].name != NULL; i++)
+    {
+      unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
+      ASSERT_TRUE (p > 50 && p <= 100);
+    }
+}
+
+#undef DEF_PREDICTOR
+
+/* Run all of the selfests within this file.  */
+
+void
+predict_c_tests ()
+{
+  test_prediction_value_range ();
+}
+
+} // namespace selftest
+#endif /* CHECKING_P.  */
diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
index f62bc72b072..30e476d14c5 100644
--- a/gcc/selftest-run-tests.c
+++ b/gcc/selftest-run-tests.c
@@ -92,6 +92,7 @@ selftest::run_tests ()
     targetm.run_target_selftests ();
 
   store_merging_c_tests ();
+  predict_c_tests ();
 
   /* Run any lang-specific selftests.  */
   lang_hooks.run_lang_selftests ();
diff --git a/gcc/selftest.h b/gcc/selftest.h
index dad53e9fe09..0572fefd281 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -196,6 +196,7 @@ extern void tree_c_tests ();
 extern void tree_cfg_c_tests ();
 extern void vec_c_tests ();
 extern void wide_int_cc_tests ();
+extern void predict_c_tests ();
 
 extern int num_passes;
 
-- 
2.13.0


^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 1/3] Come up with selftests for predict.c.
  2017-06-08 12:30     ` Martin Liška
@ 2017-06-08 13:09       ` David Malcolm
  2017-06-08 23:07       ` Jan Hubicka
  1 sibling, 0 replies; 29+ messages in thread
From: David Malcolm @ 2017-06-08 13:09 UTC (permalink / raw)
  To: Martin Liška, gcc-patches; +Cc: hubicka

On Thu, 2017-06-08 at 14:30 +0200, Martin Liška wrote:
> On 06/06/2017 12:44 PM, David Malcolm wrote:
> > On Tue, 2017-06-06 at 10:55 +0200, marxin wrote:
> > 
> > Some minor nits below.
> > 
> > > gcc/ChangeLog:
> > > 
> > > 2017-05-26  Martin Liska  <mliska@suse.cz>
> > > 
> > > 	* predict.c (struct branch_predictor): New struct.
> > > 	(test_prediction_value_range): New test.
> > > 	(predict_tests_c_tests): New function.
> > > 	* selftest-run-tests.c (selftest::run_tests): Run the function.
> > > 	* selftest.h: Declare new tests.
> > > ---
> > >  gcc/predict.c            | 39
> > > +++++++++++++++++++++++++++++++++++++++
> > >  gcc/selftest-run-tests.c |  1 +
> > >  gcc/selftest.h           |  1 +
> > >  3 files changed, 41 insertions(+)
> > > 
> > > diff --git a/gcc/predict.c b/gcc/predict.c
> > > index ac35fa41129..ea445e94e46 100644
> > > --- a/gcc/predict.c
> > > +++ b/gcc/predict.c
> > > @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3.  If not
> > > see
> > >  #include "tree-scalar-evolution.h"
> > >  #include "ipa-utils.h"
> > >  #include "gimple-pretty-print.h"
> > > +#include "selftest.h"
> > >  
> > >  /* Enum with reasons why a predictor is ignored.  */
> > >  
> > > @@ -3803,3 +3804,41 @@ force_edge_cold (edge e, bool impossible)
> > >  		 impossible ? "impossible" : "cold");
> > >      }
> > >  }
> > > +
> > > +#if CHECKING_P
> > > +
> > > +namespace selftest {
> > > +
> > > +/* Test that value range of predictor values defined in
> > > predict.def
> > > is
> > > +   within range [51, 100].  */
> > > +
> > > +struct branch_predictor
> > > +{
> > > +  const char *name;
> > > +  unsigned probability;
> > > +};
> > > +
> > > +#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME,
> > > HITRATE },
> > > +
> > > +static void
> > > +test_prediction_value_range ()
> > > +{
> > > +  branch_predictor predictors[] = {
> > > +#include "predict.def"
> > > +    {NULL, -1}
> > > +  };
> > > +
> > > +  for (unsigned i = 0; predictors[i].name != NULL; i++)
> > > +    ASSERT_TRUE (100 * predictors[i].probability /
> > > REG_BR_PROB_BASE
> > > > 50);
> > 
> > Minor nit: should there be a #undef DEF_PREDICTOR after the
> > #include?
> 
> Hello.
> 
> Yes, that should be undefined.
> 
> > 
> > Minor nits: the comment says it verifies that things are in the
> > range
> > 51, 100.  Should it be >= 51 rather than > 50?  Should there be a
> > test
> > that it's <= 100?  (I'm not familiar with the predict code, I just
> > noticed this when reading the comment).
> 
> Should be in range (50,100], fixed accordingly.
> 
> > 
> > > +}
> > > +
> > > +/* Run all of the selfests within this file.  */
> > > +
> > > +void
> > > +predict_tests_c_tests ()
> > > +{
> > 
> > Minor nit: to follow the pattern used in the other selftests, we've
> > been naming these "run all selftests within this file" functions
> > after
> > the filename.  Given this is in predict.c, this should be
> > "predict_c_tests ()" to follow the pattern.
> 
> I followed your naming scheme.
> 
> Thanks for review,
> Martin

Thanks for fixing these things; looks much better.

Note that I'm not technically a "reviewer" or "maintainer" for this
part of the compiler, so I can't formally approve the patch (I was just
pointing out some things I noticed).

Dave

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 1/3] Come up with selftests for predict.c.
  2017-06-08 12:30     ` Martin Liška
  2017-06-08 13:09       ` David Malcolm
@ 2017-06-08 23:07       ` Jan Hubicka
  1 sibling, 0 replies; 29+ messages in thread
From: Jan Hubicka @ 2017-06-08 23:07 UTC (permalink / raw)
  To: Martin Liška; +Cc: David Malcolm, gcc-patches

> On 06/06/2017 12:44 PM, David Malcolm wrote:
> > On Tue, 2017-06-06 at 10:55 +0200, marxin wrote:
> > 
> > Some minor nits below.
> > 
> >> gcc/ChangeLog:
> >>
> >> 2017-05-26  Martin Liska  <mliska@suse.cz>
> >>
> >> 	* predict.c (struct branch_predictor): New struct.
> >> 	(test_prediction_value_range): New test.
> >> 	(predict_tests_c_tests): New function.
> >> 	* selftest-run-tests.c (selftest::run_tests): Run the function.
> >> 	* selftest.h: Declare new tests.
Ok,
thanks (also do David for pointing out issues)
Honza

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 3/3] Rework cold and hot label attributes in predict.c.
  2017-06-06  9:05 ` [PATCH 3/3] Rework cold and hot label attributes in predict.c marxin
@ 2017-06-09 14:04   ` Jan Hubicka
  0 siblings, 0 replies; 29+ messages in thread
From: Jan Hubicka @ 2017-06-09 14:04 UTC (permalink / raw)
  To: marxin; +Cc: gcc-patches

> gcc/ChangeLog:
> 
> 2017-05-26  Martin Liska  <mliska@suse.cz>
> 
> 	* gimplify.c (gimplify_label_expr): Insert GIMPLE_PREDICT
> 	statements on cold and hot labels.
> 	* predict.c (tree_estimate_probability_bb): Remove the
> 	prediction from this place.
> 
> gcc/testsuite/ChangeLog:
> 
> 2017-05-31  Martin Liska  <mliska@suse.cz>
> 
> 	* gcc.dg/tree-ssa/attr-hotcold-2.c: Update scanned patterns.

OK,
thanks!
Honza
> ---
>  gcc/gimplify.c                                 | 10 +++++++++-
>  gcc/predict.c                                  | 23 -----------------------
> 
>  gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c |  4 ++--
>  3 files changed, 11 insertions(+), 26 deletions(-)
> 
> diff --git a/gcc/gimplify.c b/gcc/gimplify.c
> index f192a891a8c..b2818e2465f 100644
> --- a/gcc/gimplify.c
> +++ b/gcc/gimplify.c
> @@ -2356,10 +2356,18 @@ gimplify_label_expr (tree *expr_p, gimple_seq *pre_p)
>    gcc_assert (decl_function_context (LABEL_EXPR_LABEL (*expr_p))
>  	      == current_function_decl);
>  
> -  glabel *label_stmt = gimple_build_label (LABEL_EXPR_LABEL (*expr_p));
> +  tree label = LABEL_EXPR_LABEL (*expr_p);
> +  glabel *label_stmt = gimple_build_label (label);
>    gimple_set_location (label_stmt, EXPR_LOCATION (*expr_p));
>    gimplify_seq_add_stmt (pre_p, label_stmt);
>  
> +  if (lookup_attribute ("cold", DECL_ATTRIBUTES (label)))
> +    gimple_seq_add_stmt (pre_p, gimple_build_predict (PRED_COLD_LABEL,
> +						      NOT_TAKEN));
> +  else if (lookup_attribute ("hot", DECL_ATTRIBUTES (label)))
> +    gimple_seq_add_stmt (pre_p, gimple_build_predict (PRED_HOT_LABEL,
> +						      TAKEN));
> +
>    return GS_ALL_DONE;
>  }
>  
> diff --git a/gcc/predict.c b/gcc/predict.c
> index d561f27342d..419a4842f03 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -2698,29 +2698,6 @@ tree_estimate_probability_bb (basic_block bb)
>  
>    FOR_EACH_EDGE (e, ei, bb->succs)
>      {
> -      /* Predict edges to user labels with attributes.  */
> -      if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
> -	{
> -	  gimple_stmt_iterator gi;
> -	  for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
> -	    {
> -	      glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi));
> -	      tree decl;
> -
> -	      if (!label_stmt)
> -		break;
> -	      decl = gimple_label_label (label_stmt);
> -	      if (DECL_ARTIFICIAL (decl))
> -		continue;
> -
> -	      /* Finally, we have a user-defined label.  */
> -	      if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl)))
> -		predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN);
> -	      else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl)))
> -		predict_edge_def (e, PRED_HOT_LABEL, 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/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
> index 13d2916c47b..184dd10ddae 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
> @@ -20,9 +20,9 @@ void f(int x, int y)
>  
>  /* { dg-final { scan-tree-dump-times "hot label heuristics" 1 "profile_estimate" } } */
>  /* { dg-final { scan-tree-dump-times "cold label heuristics" 1 "profile_estimate" } } */
> -/* { dg-final { scan-tree-dump-times "block 4, loop depth 0, count 0, freq \[1-4\]\[^0-9\]" 3 "profile_estimate" } } */
> +/* { dg-final { scan-tree-dump "A \\\[0\\\..*\\\]" "profile_estimate" } } */
>  
>  /* Note: we're attempting to match some number > 6000, i.e. > 60%.
>     The exact number ought to be tweekable without having to juggle
>     the testcase around too much.  */
> -/* { dg-final { scan-tree-dump-times "block 5, loop depth 0, count 0, freq \[6-9\]\[0-9\]\[0-9\]\[0-9\]" 3 "profile_estimate" } } */
> +/* { dg-final { scan-tree-dump "B \\\[\[6-9\]\[0-9\]\\\..*\\\]" "profile_estimate" } } */
> -- 
> 2.13.0

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-06  9:05 ` [PATCH 2/3] Make early return predictor more precise marxin
@ 2017-06-09 14:08   ` Jan Hubicka
  2017-06-13 10:59     ` Martin Liška
  0 siblings, 1 reply; 29+ messages in thread
From: Jan Hubicka @ 2017-06-09 14:08 UTC (permalink / raw)
  To: marxin; +Cc: gcc-patches

> 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.

Thanks for working on this.
Doing tail recursion early is quite useful.  Can't we make the pass to
skip predict statements in analysis similar was as debug statements are
skipped?
> 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;
> +	}

I am also not quite sure about this one.  The code was still structured in a way
there was early return in the inlined function, so we may still assume that 
the heuristic works for it?

Where did you found this case?
Honza
>  
>        /* Create a new deep copy of the statement.  */
>        copy = gimple_copy (stmt);
> -- 
> 2.13.0
> 

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-09 14:08   ` Jan Hubicka
@ 2017-06-13 10:59     ` Martin Liška
  2017-06-19 11:11       ` Jan Hubicka
  0 siblings, 1 reply; 29+ messages in thread
From: Martin Liška @ 2017-06-13 10:59 UTC (permalink / raw)
  To: Jan Hubicka; +Cc: gcc-patches

On 06/09/2017 04:08 PM, Jan Hubicka wrote:
>> 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.
> 
> Thanks for working on this.
> Doing tail recursion early is quite useful.  Can't we make the pass to
> skip predict statements in analysis similar was as debug statements are
> skipped?

Hi.

Yes, this was easy to fix, skipping here helps.

>> 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;
>> +	}
> 
> I am also not quite sure about this one.  The code was still structured in a way
> there was early return in the inlined function, so we may still assume that 
> the heuristic works for it?

Ok, you're right that we can preserve the predictor. However, let's consider following test-case:

static
int baz(int a)
{
  if (a == 1)
    return 1;

  return 0;
}

  
static
int bar(int a)
{
  if (a == 1)
    return baz(a);

  return 0;
}
  
static
int foo(int a)
{
  if (a == 1)
    return bar(a);

  return 12;
}

int main(int argc, char **argv)
{
  return foo(argc);
}

There after einline we have:

main (int argc, char * * argv)
{
  int D.1832;
  int _3;
  int _4;

  <bb 2> [100.00%]:
  if (argc_2(D) == 1)
    goto <bb 3>; [37.13%]
  else
    goto <bb 4>; [62.87%]

  <bb 3> [37.13%]:
  // predicted unlikely by early return (on trees) predictor.
  // predicted unlikely by early return (on trees) predictor.
  // predicted unlikely by early return (on trees) predictor.

  <bb 4> [100.00%]:
  # _3 = PHI <12(2), 1(3)>
  _5 = _3;
  _4 = _5;
  return _4;

}

I'm thinking what's the best place to merge all the predictor
statements?

Thanks,
Martin

> 
> Where did you found this case?
> Honza
>>  
>>        /* Create a new deep copy of the statement.  */
>>        copy = gimple_copy (stmt);
>> -- 
>> 2.13.0
>>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-13 10:59     ` Martin Liška
@ 2017-06-19 11:11       ` Jan Hubicka
  2017-06-20 12:13         ` Martin Liška
  0 siblings, 1 reply; 29+ messages in thread
From: Jan Hubicka @ 2017-06-19 11:11 UTC (permalink / raw)
  To: Martin Liška; +Cc: gcc-patches

> Ok, you're right that we can preserve the predictor. However, let's consider following test-case:
> 
> static
> int baz(int a)
> {
>   if (a == 1)
>     return 1;
> 
>   return 0;
> }
> 
>   
> static
> int bar(int a)
> {
>   if (a == 1)
>     return baz(a);
> 
>   return 0;
> }
>   
> static
> int foo(int a)
> {
>   if (a == 1)
>     return bar(a);
> 
>   return 12;
> }
> 
> int main(int argc, char **argv)
> {
>   return foo(argc);
> }
> 
> There after einline we have:
> 
> main (int argc, char * * argv)
> {
>   int D.1832;
>   int _3;
>   int _4;
> 
>   <bb 2> [100.00%]:
>   if (argc_2(D) == 1)
>     goto <bb 3>; [37.13%]
>   else
>     goto <bb 4>; [62.87%]
> 
>   <bb 3> [37.13%]:
>   // predicted unlikely by early return (on trees) predictor.
>   // predicted unlikely by early return (on trees) predictor.
>   // predicted unlikely by early return (on trees) predictor.
> 
>   <bb 4> [100.00%]:
>   # _3 = PHI <12(2), 1(3)>
>   _5 = _3;
>   _4 = _5;
>   return _4;
> 
> }
> 
> I'm thinking what's the best place to merge all the predictor
> statements?

I wonder if we need to - predictors are relatively short lived.
In fact they do not need to hit IPA passes but they do as at a time
I was implementing them I was worrying about introducing yet another
global IPA pass to remove them (we can't do during early inlining
because we want to reuse them after inlining).

I would just move pass_strip_predict_hints pre-IPA and not worry about
them chaining.

There is problem that after inlining the prediction may expand its scope
and predict branch that it outside of the original function body,
but I do not see very easy solution for that besides not re-doing
prediction (we could also copy probabilities from the inlined function
when they exists and honnor them in the outer function. I am not sure
that is going to improve prediction quality though - extra context
is probably useful)

Thanks,
Honza
> 
> Thanks,
> Martin
> 
> > 
> > Where did you found this case?
> > Honza
> >>  
> >>        /* Create a new deep copy of the statement.  */
> >>        copy = gimple_copy (stmt);
> >> -- 
> >> 2.13.0
> >>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-19 11:11       ` Jan Hubicka
@ 2017-06-20 12:13         ` Martin Liška
  2017-06-21  8:27           ` Jan Hubicka
  0 siblings, 1 reply; 29+ messages in thread
From: Martin Liška @ 2017-06-20 12:13 UTC (permalink / raw)
  To: Jan Hubicka; +Cc: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 3507 bytes --]

On 06/19/2017 01:11 PM, Jan Hubicka wrote:
>> Ok, you're right that we can preserve the predictor. However, let's consider following test-case:
>>
>> static
>> int baz(int a)
>> {
>>   if (a == 1)
>>     return 1;
>>
>>   return 0;
>> }
>>
>>   
>> static
>> int bar(int a)
>> {
>>   if (a == 1)
>>     return baz(a);
>>
>>   return 0;
>> }
>>   
>> static
>> int foo(int a)
>> {
>>   if (a == 1)
>>     return bar(a);
>>
>>   return 12;
>> }
>>
>> int main(int argc, char **argv)
>> {
>>   return foo(argc);
>> }
>>
>> There after einline we have:
>>
>> main (int argc, char * * argv)
>> {
>>   int D.1832;
>>   int _3;
>>   int _4;
>>
>>   <bb 2> [100.00%]:
>>   if (argc_2(D) == 1)
>>     goto <bb 3>; [37.13%]
>>   else
>>     goto <bb 4>; [62.87%]
>>
>>   <bb 3> [37.13%]:
>>   // predicted unlikely by early return (on trees) predictor.
>>   // predicted unlikely by early return (on trees) predictor.
>>   // predicted unlikely by early return (on trees) predictor.
>>
>>   <bb 4> [100.00%]:
>>   # _3 = PHI <12(2), 1(3)>
>>   _5 = _3;
>>   _4 = _5;
>>   return _4;
>>
>> }
>>
>> I'm thinking what's the best place to merge all the predictor
>> statements?
> 
> I wonder if we need to - predictors are relatively short lived.
> In fact they do not need to hit IPA passes but they do as at a time
> I was implementing them I was worrying about introducing yet another
> global IPA pass to remove them (we can't do during early inlining
> because we want to reuse them after inlining).

Ok, so I fixed that in the described way. There's one remaining fallout of:
gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c

Where a fnsplit is properly done, but then it's again inlined:

Considering split_me.part.0/5 with 23 size
 to be inlined into test/2 in unknown:0
 Estimated badness is -0.000001, frequency 0.33.
 Inlined split_me.part.0 into test which now has time 50.300000 and size 44, net change of +17.

Considering split_me.part.0/5 with 23 size
 to be inlined into test/2 in unknown:0
 Estimated badness is -0.000001, frequency 0.33.
 Inlined split_me.part.0 into test which now has time 70.760000 and size 61, net change of +17.

Considering split_me.part.0/5 with 23 size
 to be inlined into test/2 in unknown:0
 Estimated badness is -0.000001, frequency 0.33.
 Inlined split_me.part.0 into test which now has time 91.220000 and size 78, net change of +17.

Considering split_me.part.0/5 with 23 size
 to be inlined into test/2 in unknown:0
 Estimated badness is -0.000001, frequency 0.33.
 Inlined split_me.part.0 into test which now has time 111.680000 and size 95, net change of +17.
Unit growth for small function inlining: 61->129 (111%)

...

Any hint how to block the IPA inlining?

Sending new version of patch.
Martin

> 
> I would just move pass_strip_predict_hints pre-IPA and not worry about
> them chaining.
> 
> There is problem that after inlining the prediction may expand its scope
> and predict branch that it outside of the original function body,
> but I do not see very easy solution for that besides not re-doing
> prediction (we could also copy probabilities from the inlined function
> when they exists and honnor them in the outer function. I am not sure
> that is going to improve prediction quality though - extra context
> is probably useful)
> 
> Thanks,
> Honza
>>
>> Thanks,
>> Martin
>>
>>>
>>> Where did you found this case?
>>> Honza
>>>>  
>>>>        /* Create a new deep copy of the statement.  */
>>>>        copy = gimple_copy (stmt);
>>>> -- 
>>>> 2.13.0
>>>>


[-- Attachment #2: 0001-Make-early-return-predictor-more-precise.patch --]
[-- Type: text/x-patch, Size: 7555 bytes --]

From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Tue, 6 Jun 2017 10:55:18 +0200
Subject: [PATCH 1/2] Make early return predictor more precise.

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.
	* predict.def: Change default value of early return to 66.
	* tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
	statements.
	* passes.def: Put pass_strip_predict_hints to the beginning of
	IPA passes.
---
 gcc/gimple-low.c     |  2 ++
 gcc/gimple-predict.h |  8 ++++++++
 gcc/gimplify.c       | 16 ++++++++++++++++
 gcc/passes.def       |  1 +
 gcc/predict.c        | 41 -----------------------------------------
 gcc/predict.def      | 15 +++------------
 gcc/tree-tailcall.c  |  2 ++
 7 files changed, 32 insertions(+), 53 deletions(-)

diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
index 619b9d7bfb1..4ea6c3532f3 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:
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 9af95a28704..1c6e1591953 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/passes.def b/gcc/passes.def
index c14f6b9f63c..316e19d12e3 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -107,6 +107,7 @@ along with GCC; see the file COPYING3.  If not see
 	     early optimizations again.  It is thus good idea to do this
 	      late.  */
 	  NEXT_PASS (pass_split_functions);
+	  NEXT_PASS (pass_strip_predict_hints);
       POP_INSERT_PASSES ()
       NEXT_PASS (pass_release_ssa_names);
       NEXT_PASS (pass_rebuild_cgraph_edges);
diff --git a/gcc/predict.c b/gcc/predict.c
index 60d1a094d10..790be9fbf16 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2739,7 +2739,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
 {
   edge e;
   edge_iterator ei;
-  gimple *last;
 
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
@@ -2766,46 +2765,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
 	    }
 	}
 
-      /* 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/tree-tailcall.c b/gcc/tree-tailcall.c
index b7053387e91..6aa9a56462e 100644
--- a/gcc/tree-tailcall.c
+++ b/gcc/tree-tailcall.c
@@ -421,6 +421,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
       if (gimple_code (stmt) == GIMPLE_LABEL
 	  || gimple_code (stmt) == GIMPLE_RETURN
 	  || gimple_code (stmt) == GIMPLE_NOP
+	  || gimple_code (stmt) == GIMPLE_PREDICT
 	  || gimple_clobber_p (stmt)
 	  || is_gimple_debug (stmt))
 	continue;
@@ -555,6 +556,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
 
       if (gimple_code (stmt) == GIMPLE_LABEL
 	  || gimple_code (stmt) == GIMPLE_NOP
+	  || gimple_code (stmt) == GIMPLE_PREDICT
 	  || gimple_clobber_p (stmt)
 	  || is_gimple_debug (stmt))
 	continue;
-- 
2.13.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-20 12:13         ` Martin Liška
@ 2017-06-21  8:27           ` Jan Hubicka
  2017-06-21 12:50             ` Martin Liška
  0 siblings, 1 reply; 29+ messages in thread
From: Jan Hubicka @ 2017-06-21  8:27 UTC (permalink / raw)
  To: Martin Liška; +Cc: gcc-patches

> 
> Ok, so I fixed that in the described way. There's one remaining fallout of:
> gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
> 
> Where a fnsplit is properly done, but then it's again inlined:
> 
> Considering split_me.part.0/5 with 23 size
>  to be inlined into test/2 in unknown:0
>  Estimated badness is -0.000001, frequency 0.33.
>  Inlined split_me.part.0 into test which now has time 50.300000 and size 44, net change of +17.
> 
> Considering split_me.part.0/5 with 23 size
>  to be inlined into test/2 in unknown:0
>  Estimated badness is -0.000001, frequency 0.33.
>  Inlined split_me.part.0 into test which now has time 70.760000 and size 61, net change of +17.
> 
> Considering split_me.part.0/5 with 23 size
>  to be inlined into test/2 in unknown:0
>  Estimated badness is -0.000001, frequency 0.33.
>  Inlined split_me.part.0 into test which now has time 91.220000 and size 78, net change of +17.
> 
> Considering split_me.part.0/5 with 23 size
>  to be inlined into test/2 in unknown:0
>  Estimated badness is -0.000001, frequency 0.33.
>  Inlined split_me.part.0 into test which now has time 111.680000 and size 95, net change of +17.
> Unit growth for small function inlining: 61->129 (111%)
> 
> ...
> 
> Any hint how to block the IPA inlining?

I guess you only want to make cold part of split_me bigger or
just use --param to reduce growth for auto inlining.

How the patch reduces split_me_part considerably?
Honza
> 
> Sending new version of patch.
> Martin
> 
> > 
> > I would just move pass_strip_predict_hints pre-IPA and not worry about
> > them chaining.
> > 
> > There is problem that after inlining the prediction may expand its scope
> > and predict branch that it outside of the original function body,
> > but I do not see very easy solution for that besides not re-doing
> > prediction (we could also copy probabilities from the inlined function
> > when they exists and honnor them in the outer function. I am not sure
> > that is going to improve prediction quality though - extra context
> > is probably useful)
> > 
> > Thanks,
> > Honza
> >>
> >> Thanks,
> >> Martin
> >>
> >>>
> >>> Where did you found this case?
> >>> Honza
> >>>>  
> >>>>        /* Create a new deep copy of the statement.  */
> >>>>        copy = gimple_copy (stmt);
> >>>> -- 
> >>>> 2.13.0
> >>>>
> 

> >From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
> From: marxin <mliska@suse.cz>
> Date: Tue, 6 Jun 2017 10:55:18 +0200
> Subject: [PATCH 1/2] Make early return predictor more precise.
> 
> 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.
> 	* predict.def: Change default value of early return to 66.
> 	* tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
> 	statements.
> 	* passes.def: Put pass_strip_predict_hints to the beginning of
> 	IPA passes.
> ---
>  gcc/gimple-low.c     |  2 ++
>  gcc/gimple-predict.h |  8 ++++++++
>  gcc/gimplify.c       | 16 ++++++++++++++++
>  gcc/passes.def       |  1 +
>  gcc/predict.c        | 41 -----------------------------------------
>  gcc/predict.def      | 15 +++------------
>  gcc/tree-tailcall.c  |  2 ++
>  7 files changed, 32 insertions(+), 53 deletions(-)
> 
> diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
> index 619b9d7bfb1..4ea6c3532f3 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:
> 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 9af95a28704..1c6e1591953 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/passes.def b/gcc/passes.def
> index c14f6b9f63c..316e19d12e3 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
> @@ -107,6 +107,7 @@ along with GCC; see the file COPYING3.  If not see
>  	     early optimizations again.  It is thus good idea to do this
>  	      late.  */
>  	  NEXT_PASS (pass_split_functions);
> +	  NEXT_PASS (pass_strip_predict_hints);
>        POP_INSERT_PASSES ()
>        NEXT_PASS (pass_release_ssa_names);
>        NEXT_PASS (pass_rebuild_cgraph_edges);
> diff --git a/gcc/predict.c b/gcc/predict.c
> index 60d1a094d10..790be9fbf16 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -2739,7 +2739,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
>  {
>    edge e;
>    edge_iterator ei;
> -  gimple *last;
>  
>    FOR_EACH_EDGE (e, ei, bb->succs)
>      {
> @@ -2766,46 +2765,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
>  	    }
>  	}
>  
> -      /* 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/tree-tailcall.c b/gcc/tree-tailcall.c
> index b7053387e91..6aa9a56462e 100644
> --- a/gcc/tree-tailcall.c
> +++ b/gcc/tree-tailcall.c
> @@ -421,6 +421,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
>        if (gimple_code (stmt) == GIMPLE_LABEL
>  	  || gimple_code (stmt) == GIMPLE_RETURN
>  	  || gimple_code (stmt) == GIMPLE_NOP
> +	  || gimple_code (stmt) == GIMPLE_PREDICT
>  	  || gimple_clobber_p (stmt)
>  	  || is_gimple_debug (stmt))
>  	continue;
> @@ -555,6 +556,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
>  
>        if (gimple_code (stmt) == GIMPLE_LABEL
>  	  || gimple_code (stmt) == GIMPLE_NOP
> +	  || gimple_code (stmt) == GIMPLE_PREDICT
>  	  || gimple_clobber_p (stmt)
>  	  || is_gimple_debug (stmt))
>  	continue;
> -- 
> 2.13.1
> 

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-21  8:27           ` Jan Hubicka
@ 2017-06-21 12:50             ` Martin Liška
  2017-06-22 10:48               ` [PATCH] Fix ipa-split-5.c test-case Martin Liška
  2017-06-22 14:14               ` [PATCH 2/3] Make early return predictor more precise Christophe Lyon
  0 siblings, 2 replies; 29+ messages in thread
From: Martin Liška @ 2017-06-21 12:50 UTC (permalink / raw)
  To: Jan Hubicka; +Cc: gcc-patches

On 06/21/2017 10:26 AM, Jan Hubicka wrote:
>>
>> Ok, so I fixed that in the described way. There's one remaining fallout of:
>> gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
>>
>> Where a fnsplit is properly done, but then it's again inlined:
>>
>> Considering split_me.part.0/5 with 23 size
>>  to be inlined into test/2 in unknown:0
>>  Estimated badness is -0.000001, frequency 0.33.
>>  Inlined split_me.part.0 into test which now has time 50.300000 and size 44, net change of +17.
>>
>> Considering split_me.part.0/5 with 23 size
>>  to be inlined into test/2 in unknown:0
>>  Estimated badness is -0.000001, frequency 0.33.
>>  Inlined split_me.part.0 into test which now has time 70.760000 and size 61, net change of +17.
>>
>> Considering split_me.part.0/5 with 23 size
>>  to be inlined into test/2 in unknown:0
>>  Estimated badness is -0.000001, frequency 0.33.
>>  Inlined split_me.part.0 into test which now has time 91.220000 and size 78, net change of +17.
>>
>> Considering split_me.part.0/5 with 23 size
>>  to be inlined into test/2 in unknown:0
>>  Estimated badness is -0.000001, frequency 0.33.
>>  Inlined split_me.part.0 into test which now has time 111.680000 and size 95, net change of +17.
>> Unit growth for small function inlining: 61->129 (111%)
>>
>> ...
>>
>> Any hint how to block the IPA inlining?
> 
> I guess you only want to make cold part of split_me bigger or
> just use --param to reduce growth for auto inlining.
> 
> How the patch reduces split_me_part considerably?
> Honza

Well, I probably overlooked test results, test works fine.

I'm going to install the patch.

Martin

>>
>> Sending new version of patch.
>> Martin
>>
>>>
>>> I would just move pass_strip_predict_hints pre-IPA and not worry about
>>> them chaining.
>>>
>>> There is problem that after inlining the prediction may expand its scope
>>> and predict branch that it outside of the original function body,
>>> but I do not see very easy solution for that besides not re-doing
>>> prediction (we could also copy probabilities from the inlined function
>>> when they exists and honnor them in the outer function. I am not sure
>>> that is going to improve prediction quality though - extra context
>>> is probably useful)
>>>
>>> Thanks,
>>> Honza
>>>>
>>>> Thanks,
>>>> Martin
>>>>
>>>>>
>>>>> Where did you found this case?
>>>>> Honza
>>>>>>  
>>>>>>        /* Create a new deep copy of the statement.  */
>>>>>>        copy = gimple_copy (stmt);
>>>>>> -- 
>>>>>> 2.13.0
>>>>>>
>>
> 
>> >From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
>> From: marxin <mliska@suse.cz>
>> Date: Tue, 6 Jun 2017 10:55:18 +0200
>> Subject: [PATCH 1/2] Make early return predictor more precise.
>>
>> 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.
>> 	* predict.def: Change default value of early return to 66.
>> 	* tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
>> 	statements.
>> 	* passes.def: Put pass_strip_predict_hints to the beginning of
>> 	IPA passes.
>> ---
>>  gcc/gimple-low.c     |  2 ++
>>  gcc/gimple-predict.h |  8 ++++++++
>>  gcc/gimplify.c       | 16 ++++++++++++++++
>>  gcc/passes.def       |  1 +
>>  gcc/predict.c        | 41 -----------------------------------------
>>  gcc/predict.def      | 15 +++------------
>>  gcc/tree-tailcall.c  |  2 ++
>>  7 files changed, 32 insertions(+), 53 deletions(-)
>>
>> diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
>> index 619b9d7bfb1..4ea6c3532f3 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:
>> 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 9af95a28704..1c6e1591953 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/passes.def b/gcc/passes.def
>> index c14f6b9f63c..316e19d12e3 100644
>> --- a/gcc/passes.def
>> +++ b/gcc/passes.def
>> @@ -107,6 +107,7 @@ along with GCC; see the file COPYING3.  If not see
>>  	     early optimizations again.  It is thus good idea to do this
>>  	      late.  */
>>  	  NEXT_PASS (pass_split_functions);
>> +	  NEXT_PASS (pass_strip_predict_hints);
>>        POP_INSERT_PASSES ()
>>        NEXT_PASS (pass_release_ssa_names);
>>        NEXT_PASS (pass_rebuild_cgraph_edges);
>> diff --git a/gcc/predict.c b/gcc/predict.c
>> index 60d1a094d10..790be9fbf16 100644
>> --- a/gcc/predict.c
>> +++ b/gcc/predict.c
>> @@ -2739,7 +2739,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
>>  {
>>    edge e;
>>    edge_iterator ei;
>> -  gimple *last;
>>  
>>    FOR_EACH_EDGE (e, ei, bb->succs)
>>      {
>> @@ -2766,46 +2765,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
>>  	    }
>>  	}
>>  
>> -      /* 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/tree-tailcall.c b/gcc/tree-tailcall.c
>> index b7053387e91..6aa9a56462e 100644
>> --- a/gcc/tree-tailcall.c
>> +++ b/gcc/tree-tailcall.c
>> @@ -421,6 +421,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
>>        if (gimple_code (stmt) == GIMPLE_LABEL
>>  	  || gimple_code (stmt) == GIMPLE_RETURN
>>  	  || gimple_code (stmt) == GIMPLE_NOP
>> +	  || gimple_code (stmt) == GIMPLE_PREDICT
>>  	  || gimple_clobber_p (stmt)
>>  	  || is_gimple_debug (stmt))
>>  	continue;
>> @@ -555,6 +556,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
>>  
>>        if (gimple_code (stmt) == GIMPLE_LABEL
>>  	  || gimple_code (stmt) == GIMPLE_NOP
>> +	  || gimple_code (stmt) == GIMPLE_PREDICT
>>  	  || gimple_clobber_p (stmt)
>>  	  || is_gimple_debug (stmt))
>>  	continue;
>> -- 
>> 2.13.1
>>
> 

^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH 4/N] Recover GOTO predictor.
  2017-06-06  9:05 [PATCH 0/3] Rework early return and hot/cold label predictors marxin
                   ` (2 preceding siblings ...)
  2017-06-06  9:05 ` [PATCH 1/3] Come up with selftests for predict.c marxin
@ 2017-06-21 13:06 ` Martin Liška
  2017-06-21 13:09   ` Martin Liška
  2017-06-22 10:27   ` Richard Biener
  3 siblings, 2 replies; 29+ messages in thread
From: Martin Liška @ 2017-06-21 13:06 UTC (permalink / raw)
  To: gcc-patches; +Cc: hubicka, ppalka, Richard Biener

[-- Attachment #1: Type: text/plain, Size: 449 bytes --]

Hello.

There's one additional predictor enhancement that is GOTO predict that
used to working. Following patch adds expect statement for C and C++ family
languages.

There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
appears just once. Adding Richi and Patrick who can probably help how to fix the
test-case.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Ready to be installed?
Martin

[-- Attachment #2: vrp24.c.104t.vrp1 --]
[-- Type: text/plain, Size: 9386 bytes --]


;; Function sss (sss, funcdef_no=0, decl_uid=1811, cgraph_uid=0, symbol_order=0)

;; 3 loops found
;;
;; Loop 0
;;  header 0, latch 1
;;  depth 0, outer -1
;;  nodes: 0 1 2 3 4 5 6 7 8 9 10 11 12
;; 2 succs { 10 3 }
;; 3 succs { 4 8 }
;; 4 succs { 10 5 }
;; 5 succs { 12 }
;; 6 succs { 7 }
;; 7 succs { 9 }
;; 8 succs { 12 }
;; 9 succs { 12 }
;; 10 succs { 6 11 }
;; 11 succs { 9 }
;; 12 succs { 1 }

SSA form after inserting ASSERT_EXPRs
sss (struct rtx_def * insn, int code1, int code2, int code3)
{
  int D1544;
  int n_sets;
  struct rtx_def * body;
  _Bool D1562;

  <bb 2> [100.00%] [count: INV]:
  body_5 = insn_4(D)->u.fld[5].rt_rtx;
  D1544_6 = body_5->code;
  if (D1544_6 == 55)
    goto <bb 10> (L7); [34.00%] [count: INV]
  else
    goto <bb 3>; [66.00%] [count: INV]

  <bb 3> [66.00%] [count: INV]:
  if (code3_7(D) == 99)
    goto <bb 4>; [34.00%] [count: INV]
  else
    goto <bb 8>; [66.00%] [count: INV]

  <bb 4> [22.44%] [count: INV]:
  D1562_9 = code1_8(D) == 10;
  n_sets_10 = (int) D1562_9;
  if (n_sets_10 > 0)
    goto <bb 10> (L7); [64.00%] [count: INV]
  else
    goto <bb 5>; [36.00%] [count: INV]

  <bb 5> [8.10%] [count: INV]:
  # n_sets_1 = PHI <0(4)>
  goto <bb 12> (L16); [100.00%] [count: INV]

  <bb 6> [9.79%] [count: INV]:
  arf ();

  <bb 7> [9.82%] [count: INV]:
  # n_sets_19 = PHI <1(6)>
  goto <bb 9>; [100.00%] [count: INV]

  <bb 8> [43.56%] [count: INV]:
  # n_sets_21 = PHI <0(3)>
  goto <bb 12> (L16); [100.00%] [count: INV]

  <bb 9> [46.68%] [count: INV]:
  frob ();
  goto <bb 12> (L16); [100.00%] [count: INV]

L7 [48.36%] [count: INV]:
  if (code2_12(D) == 42)
    goto <bb 6>; [20.24%] [count: INV]
  else
    goto <bb 11>; [79.76%] [count: INV]

  <bb 11> [38.61%] [count: INV]:
  # n_sets_17 = PHI <1(10)>
  goto <bb 9>; [100.00%] [count: INV]

L16 [100.00%] [count: INV]:
  return;

}


Immediate_uses: 

n_sets_1 : --> no uses.

.MEM_2 : --> single use.
# VUSE <.MEM_2>
return;

.MEM_3(D) : -->6 uses.
.MEM_22 = PHI <.MEM_3(D)(3)>
.MEM_18 = PHI <.MEM_3(D)(10)>
.MEM_16 = PHI <.MEM_3(D)(4)>
# .MEM_13 = VDEF <.MEM_3(D)>
arf ();
# VUSE <.MEM_3(D)>
D1544_6 = body_5->code;
# VUSE <.MEM_3(D)>
body_5 = insn_4(D)->u.fld[5].rt_rtx;

insn_4(D) : --> single use.
body_5 = insn_4(D)->u.fld[5].rt_rtx;

body_5 : --> single use.
D1544_6 = body_5->code;

D1544_6 : --> single use.
if (D1544_6 == 55)

code3_7(D) : --> single use.
if (code3_7(D) == 99)

code1_8(D) : --> single use.
D1562_9 = code1_8(D) == 10;

D1562_9 : --> single use.
n_sets_10 = (int) D1562_9;

n_sets_10 : --> single use.
if (n_sets_10 > 0)

code2_12(D) : --> single use.
if (code2_12(D) == 42)

.MEM_13 : --> single use.
.MEM_20 = PHI <.MEM_13(6)>

.MEM_14 : --> single use.
.MEM_2 = PHI <.MEM_14(9), .MEM_22(8), .MEM_16(5)>

.MEM_16 : --> single use.
.MEM_2 = PHI <.MEM_14(9), .MEM_22(8), .MEM_16(5)>

n_sets_17 : --> no uses.

.MEM_18 : --> single use.
.MEM_23 = PHI <.MEM_20(7), .MEM_18(11)>

n_sets_19 : --> no uses.

.MEM_20 : --> single use.
.MEM_23 = PHI <.MEM_20(7), .MEM_18(11)>

n_sets_21 : --> no uses.

.MEM_22 : --> single use.
.MEM_2 = PHI <.MEM_14(9), .MEM_22(8), .MEM_16(5)>

.MEM_23 : --> single use.
# .MEM_14 = VDEF <.MEM_23>
frob ();

Adding destination of edge (0 -> 2) to worklist

Simulating block 2

Visiting statement:
if (D1544_6 == 55)

Visiting conditional with predicate: if (D1544_6 == 55)

With known ranges
	D1544_6: VARYING

Predicate evaluates to: DON'T KNOW
Adding destination of edge (2 -> 10) to worklist
Adding destination of edge (2 -> 3) to worklist

Simulating block 3

Visiting statement:
if (code3_7(D) == 99)

Visiting conditional with predicate: if (code3_7(D) == 99)

With known ranges
	code3_7(D): []

Predicate evaluates to: DON'T KNOW
Adding destination of edge (3 -> 4) to worklist
Adding destination of edge (3 -> 8) to worklist

Simulating block 8

Visiting PHI node: n_sets_21 = PHI <0(3)>
    Argument #0 (3 -> 8 executable)
	0: [0, 0]
Intersecting
  [0, 0]
and
  [0, 1]
to
  [0, 0]
Found new range for n_sets_21: [0, 0]
marking stmt to be not simulated again
Adding destination of edge (8 -> 12) to worklist

Simulating block 4

Visiting statement:
D1562_9 = code1_8(D) == 10;
Intersecting
  [0, +INF]
and
  [0, +INF]
to
  [0, +INF]
Found new range for D1562_9: [0, +INF]
marking stmt to be not simulated again

Visiting statement:
n_sets_10 = (int) D1562_9;
Intersecting
  [0, 1]
and
  [0, 1]
to
  [0, 1]
Found new range for n_sets_10: [0, 1]
marking stmt to be not simulated again

Visiting statement:
if (n_sets_10 > 0)

Visiting conditional with predicate: if (n_sets_10 > 0)

With known ranges
	n_sets_10: [0, 1]

Predicate evaluates to: DON'T KNOW
Adding destination of edge (4 -> 10) to worklist
Adding destination of edge (4 -> 5) to worklist

Simulating block 5

Visiting PHI node: n_sets_1 = PHI <0(4)>
    Argument #0 (4 -> 5 executable)
	0: [0, 0]
Intersecting
  [0, 0]
and
  [0, 1]
to
  [0, 0]
Found new range for n_sets_1: [0, 0]
marking stmt to be not simulated again
Adding destination of edge (5 -> 12) to worklist

Simulating block 10

Visiting statement:
if (code2_12(D) == 42)

Visiting conditional with predicate: if (code2_12(D) == 42)

With known ranges
	code2_12(D): []

Predicate evaluates to: DON'T KNOW
Adding destination of edge (10 -> 6) to worklist
Adding destination of edge (10 -> 11) to worklist

Simulating block 11

Visiting PHI node: n_sets_17 = PHI <1(10)>
    Argument #0 (10 -> 11 executable)
	1: [1, 1]
Intersecting
  [1, 1]
and
  [0, 1]
to
  [1, 1]
Found new range for n_sets_17: [1, 1]
marking stmt to be not simulated again
Adding destination of edge (11 -> 9) to worklist

Simulating block 6
Adding destination of edge (6 -> 7) to worklist

Simulating block 7

Visiting PHI node: n_sets_19 = PHI <1(6)>
    Argument #0 (6 -> 7 executable)
	1: [1, 1]
Intersecting
  [1, 1]
and
  [0, 1]
to
  [1, 1]
Found new range for n_sets_19: [1, 1]
marking stmt to be not simulated again
Adding destination of edge (7 -> 9) to worklist

Simulating block 9
Adding destination of edge (9 -> 12) to worklist

Simulating block 12

Visiting statement:
return;

Value ranges after VRP:

n_sets_1: [0, 0]
.MEM_2: VARYING
body_5: VARYING
D1544_6: VARYING
code3_7(D): VARYING
code1_8(D): VARYING
D1562_9: [0, +INF]
n_sets_10: [0, 1]
code2_12(D): VARYING
.MEM_16: VARYING
n_sets_17: [1, 1]
.MEM_18: VARYING
n_sets_19: [1, 1]
.MEM_20: VARYING
n_sets_21: [0, 0]
.MEM_22: VARYING
.MEM_23: VARYING



Substituting values and folding statements

Folding statement: body_5 = insn_4(D)->u.fld[5].rt_rtx;
Not folded
Folding statement: D1544_6 = body_5->code;
Not folded
Folding statement: if (D1544_6 == 55)
Not folded
Folding statement: if (code3_7(D) == 99)
Not folded
Folding statement: D1562_9 = code1_8(D) == 10;
Not folded
Folding statement: n_sets_10 = (int) D1562_9;
Not folded
Folding statement: if (n_sets_10 > 0)
Simplified relational if (n_sets_10 > 0)
 into if (n_sets_10 == 1)

Folded into: if (n_sets_10 == 1)

Folding statement: L7 [48.36%] [count: INV]:
Not folded
Folding statement: if (code2_12(D) == 42)
Not folded
Folding statement: arf ();
Not folded
Folding statement: frob ();
Not folded
Folding statement: L16 [100.00%] [count: INV]:
Not folded
Folding statement: return;
Not folded
Removing dead stmt n_sets_19 = PHI <1(6)>

Removing dead stmt n_sets_17 = PHI <1(10)>

Removing dead stmt n_sets_1 = PHI <0(4)>

Removing dead stmt n_sets_21 = PHI <0(3)>

LKUP STMT code2_12(D) eq_expr 42
0>>> COPY .MEM_18 = .MEM_3(D)
<<<< COPY .MEM_18 = .MEM_3(D)
0>>> COPY .MEM_16 = .MEM_3(D)
0>>> COPY .MEM_2 = .MEM_3(D)
<<<< COPY .MEM_2 = .MEM_3(D)
<<<< COPY .MEM_16 = .MEM_3(D)
0>>> COPY .MEM_22 = .MEM_3(D)
0>>> COPY .MEM_2 = .MEM_3(D)
<<<< COPY .MEM_2 = .MEM_3(D)
<<<< COPY .MEM_22 = .MEM_3(D)
0>>> COPY .MEM_20 = .MEM_13
0>>> COPY .MEM_23 = .MEM_13
<<<< COPY .MEM_23 = .MEM_13
<<<< COPY .MEM_20 = .MEM_13
0>>> COPY .MEM_18 = .MEM_3(D)
0>>> COPY .MEM_23 = .MEM_3(D)
<<<< COPY .MEM_23 = .MEM_3(D)
<<<< COPY .MEM_18 = .MEM_3(D)
LKUP STMT code2_12(D) eq_expr 42
0>>> COPY .MEM_18 = .MEM_3(D)
<<<< COPY .MEM_18 = .MEM_3(D)
Folded into: if (D1562_9 == 1)

Merging blocks 6 and 7
fix_loop_structure: fixing up loops for function
sss (struct rtx_def * insn, int code1, int code2, int code3)
{
  int D1544;
  int n_sets;
  struct rtx_def * body;
  _Bool D1562;

  <bb 2> [100.00%] [count: INV]:
  body_5 = insn_4(D)->u.fld[5].rt_rtx;
  D1544_6 = body_5->code;
  if (D1544_6 == 55)
    goto <bb 9> (L7); [34.00%] [count: INV]
  else
    goto <bb 3>; [66.00%] [count: INV]

  <bb 3> [66.00%] [count: INV]:
  if (code3_7(D) == 99)
    goto <bb 4>; [34.00%] [count: INV]
  else
    goto <bb 7>; [66.00%] [count: INV]

  <bb 4> [22.44%] [count: INV]:
  D1562_9 = code1_8(D) == 10;
  n_sets_10 = (int) D1562_9;
  if (D1562_9 == 1)
    goto <bb 9> (L7); [64.00%] [count: INV]
  else
    goto <bb 5>; [36.00%] [count: INV]

  <bb 5> [8.10%] [count: INV]:
  goto <bb 11> (L16); [100.00%] [count: INV]

  <bb 6> [9.82%] [count: INV]:
  arf ();
  goto <bb 8>; [100.00%] [count: INV]

  <bb 7> [43.56%] [count: INV]:
  goto <bb 11> (L16); [100.00%] [count: INV]

  <bb 8> [46.68%] [count: INV]:
  frob ();
  goto <bb 11> (L16); [100.00%] [count: INV]

L7 [48.36%] [count: INV]:
  if (code2_12(D) == 42)
    goto <bb 6>; [20.24%] [count: INV]
  else
    goto <bb 10>; [79.76%] [count: INV]

  <bb 10> [38.61%] [count: INV]:
  goto <bb 8>; [100.00%] [count: INV]

L16 [100.00%] [count: INV]:
  return;

}



[-- Attachment #3: 0001-Recover-GOTO-predictor.patch --]
[-- Type: text/x-patch, Size: 6801 bytes --]

From 4963172e22489a83caa866854386b6d8b5a62f7a Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Mon, 19 Jun 2017 15:44:34 +0200
Subject: [PATCH] Recover GOTO predictor.

gcc/c/ChangeLog:

2017-06-21  Jan Hubicka <hubicka@ucw.cz>
	    Martin Liska  <mliska@suse.cz>

	* c-typeck.c (c_finish_goto_label): Build gimple predict
	stament.

gcc/ChangeLog:

2017-06-21  Jan Hubicka <hubicka@ucw.cz>
	    Martin Liska  <mliska@suse.cz>

	* predict.def: Remove old comment and adjust probability.
	* gimplify.c (should_warn_for_implicit_fallthrough): Ignore
	PREDICT statements.

gcc/testsuite/ChangeLog:

2017-06-21  Jan Hubicka <hubicka@ucw.cz>
	    Martin Liska  <mliska@suse.cz>

	* gcc.dg/predict-15.c: New test.
	* gcc.dg/tree-ssa/attr-hotcold-2.c: Update the test-case.

gcc/cp/ChangeLog:

2017-06-21  Jan Hubicka <hubicka@ucw.cz>
	    Martin Liska  <mliska@suse.cz>

	* pt.c (tsubst_copy): Copy PREDICT_EXPR.
	* semantics.c (finish_goto_stmt): Build gimple predict
	stament.
	* constexpr.c (potential_constant_expression_1): Handle
	PREDICT_EXPR.
---
 gcc/c/c-typeck.c                               |  1 +
 gcc/cp/constexpr.c                             |  1 +
 gcc/cp/pt.c                                    |  2 ++
 gcc/cp/semantics.c                             |  2 ++
 gcc/gimplify.c                                 |  4 +++-
 gcc/predict.def                                |  5 ++---
 gcc/testsuite/gcc.dg/predict-15.c              | 17 +++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c | 13 ++++++-------
 8 files changed, 34 insertions(+), 11 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/predict-15.c

diff --git a/gcc/c/c-typeck.c b/gcc/c/c-typeck.c
index 4d067e96dd3..c677c3e9ff5 100644
--- a/gcc/c/c-typeck.c
+++ b/gcc/c/c-typeck.c
@@ -9824,6 +9824,7 @@ c_finish_goto_label (location_t loc, tree label)
     return NULL_TREE;
   TREE_USED (decl) = 1;
   {
+    add_stmt (build_predict_expr (PRED_GOTO, NOT_TAKEN));
     tree t = build1 (GOTO_EXPR, void_type_node, decl);
     SET_EXPR_LOCATION (t, loc);
     return add_stmt (t);
diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 5a574524866..788e02d7372 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -5784,6 +5784,7 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict,
 
     case CLEANUP_STMT:
     case EMPTY_CLASS_EXPR:
+    case PREDICT_EXPR:
       return false;
 
     case GOTO_EXPR:
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 69ca9291960..445b46da2de 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -15111,6 +15111,8 @@ tsubst_copy (tree t, tree args, tsubst_flags_t complain, tree in_decl)
       return tsubst_binary_left_fold (t, args, complain, in_decl);
     case BINARY_RIGHT_FOLD_EXPR:
       return tsubst_binary_right_fold (t, args, complain, in_decl);
+    case PREDICT_EXPR:
+      return t;
 
     default:
       /* We shouldn't get here, but keep going if !flag_checking.  */
diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index 5fe772a49e3..a5fcc7b2c63 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "omp-general.h"
 #include "convert.h"
 #include "gomp-constants.h"
+#include "predict.h"
 
 /* There routines provide a modular interface to perform many parsing
    operations.  They may therefore be used during actual parsing, or
@@ -630,6 +631,7 @@ finish_goto_stmt (tree destination)
 
   check_goto (destination);
 
+  add_stmt (build_predict_expr (PRED_GOTO, NOT_TAKEN));
   return add_stmt (build_stmt (input_location, GOTO_EXPR, destination));
 }
 
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index f45d3bfd13a..0ea8d4ea07b 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -2042,7 +2042,9 @@ should_warn_for_implicit_fallthrough (gimple_stmt_iterator *gsi_p, tree label)
   gsi = *gsi_p;
 
   /* Skip all immediately following labels.  */
-  while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
+  while (!gsi_end_p (gsi)
+	 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL
+	     || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
     gsi_next (&gsi);
 
   /* { ... something; default:; } */
diff --git a/gcc/predict.def b/gcc/predict.def
index f7b2bf7738c..326c39ae4c9 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -132,9 +132,8 @@ DEF_PREDICTOR (PRED_RECURSIVE_CALL, "recursive call", HITRATE (75), 0)
 DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE (66),
 	       0)
 
-/* Branch containing goto is probably not taken.
-   FIXME: Currently not used.  */
-DEF_PREDICTOR (PRED_GOTO, "goto", HITRATE (70), 0)
+/* Branch containing goto is probably not taken.  */
+DEF_PREDICTOR (PRED_GOTO, "goto", HITRATE (66), 0)
 
 /* Branch ending with return constant is probably not taken.  */
 DEF_PREDICTOR (PRED_CONST_RETURN, "const return", HITRATE (69), 0)
diff --git a/gcc/testsuite/gcc.dg/predict-15.c b/gcc/testsuite/gcc.dg/predict-15.c
new file mode 100644
index 00000000000..2a8c3ea8597
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-15.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+int main(int argc, char **argv)
+{
+  if (argc == 123)
+    goto exit;
+  else
+    {
+      return 0;
+    }
+
+exit:
+  return 1;
+}
+
+/* { dg-final { scan-tree-dump "goto heuristics of edge" "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
index 184dd10ddae..d5999e1bf6f 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
@@ -1,8 +1,7 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-profile_estimate-blocks-details" } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
 
-void g(void);
-void h(void);
+int v1, v2;
 void f(int x, int y)
 {
   if (x) goto A;
@@ -10,19 +9,19 @@ void f(int x, int y)
   return;
 
  A: __attribute__((cold))
-  g();
+  v1 = x;
   return;
 
  B: __attribute__((hot))
-  h();
+  v2 = y;
   return;
 }
 
 /* { dg-final { scan-tree-dump-times "hot label heuristics" 1 "profile_estimate" } } */
 /* { dg-final { scan-tree-dump-times "cold label heuristics" 1 "profile_estimate" } } */
-/* { dg-final { scan-tree-dump "A \\\[0\\\..*\\\]" "profile_estimate" } } */
+/* { dg-final { scan-tree-dump "combined heuristics: 0\\\..*" "profile_estimate" } } */
 
 /* Note: we're attempting to match some number > 6000, i.e. > 60%.
    The exact number ought to be tweekable without having to juggle
    the testcase around too much.  */
-/* { dg-final { scan-tree-dump "B \\\[\[6-9\]\[0-9\]\\\..*\\\]" "profile_estimate" } } */
+/* { dg-final { scan-tree-dump "combined heuristics: \[6-9\]\[0-9\]\\\..*" "profile_estimate" } } */
-- 
2.13.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-21 13:06 ` [PATCH 4/N] Recover GOTO predictor Martin Liška
@ 2017-06-21 13:09   ` Martin Liška
  2017-06-22 10:27   ` Richard Biener
  1 sibling, 0 replies; 29+ messages in thread
From: Martin Liška @ 2017-06-21 13:09 UTC (permalink / raw)
  To: gcc-patches; +Cc: hubicka, ppalka, Richard Biener

On 06/21/2017 03:06 PM, Martin Liška wrote:
> Hello.
> 
> There's one additional predictor enhancement that is GOTO predict that
> used to working. Following patch adds expect statement for C and C++ family
> languages.
> 
> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
> appears just once. Adding Richi and Patrick who can probably help how to fix the
> test-case.
> 
> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
> 
> Ready to be installed?
> Martin
> 

And I forgot to mention hitrate on SPEC2017:

HEURISTICS                               BRANCHES  (REL)  BR. HITRATE            HITRATE       COVERAGE COVERAGE  (REL)  predict.def  (REL)
goto                                          622   1.0%       64.31%   65.92% /  83.70%      725127790  725.13M   0.1%

Which says it's quite rare predictor, but with quite nice hitrate.

Martin

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-21 13:06 ` [PATCH 4/N] Recover GOTO predictor Martin Liška
  2017-06-21 13:09   ` Martin Liška
@ 2017-06-22 10:27   ` Richard Biener
  2017-06-22 10:57     ` Martin Liška
  2017-06-30 13:48     ` Martin Liška
  1 sibling, 2 replies; 29+ messages in thread
From: Richard Biener @ 2017-06-22 10:27 UTC (permalink / raw)
  To: Martin Liška; +Cc: GCC Patches, Jan Hubicka, ppalka

On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
> Hello.
>
> There's one additional predictor enhancement that is GOTO predict that
> used to working. Following patch adds expect statement for C and C++ family
> languages.
>
> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
> appears just once. Adding Richi and Patrick who can probably help how to fix the
> test-case.

Happens to be optimized better now, there's only one predicate to simplify
left in the IL input to VRP1.  I suggest to change it to match 1 times and add
-fdump-tree-optimized to dg-options and

/* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */

to verify we have 3 conditions left.

> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>
> Ready to be installed?
> Martin

^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH] Fix ipa-split-5.c test-case.
  2017-06-21 12:50             ` Martin Liška
@ 2017-06-22 10:48               ` Martin Liška
  2017-06-22 14:14               ` [PATCH 2/3] Make early return predictor more precise Christophe Lyon
  1 sibling, 0 replies; 29+ messages in thread
From: Martin Liška @ 2017-06-22 10:48 UTC (permalink / raw)
  To: Jan Hubicka; +Cc: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 167 bytes --]

Hi.

There's a small fallout where I blow up a function in order to
suppress function inlining. Honza pre-approved the change, I'm
going to install the patch.

Martin

[-- Attachment #2: 0001-Fix-ipa-split-5.c-test-case.patch --]
[-- Type: text/x-patch, Size: 1436 bytes --]

From dc4f022b91913e25eaff2ddcaf4dfef0e44217a2 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Thu, 22 Jun 2017 12:45:55 +0200
Subject: [PATCH] Fix ipa-split-5.c test-case.

gcc/testsuite/ChangeLog:

2017-06-22  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-ssa/ipa-split-5.c: Make function bigger in order
	to not inline it.
---
 gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c b/gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
index 1278e6e275a..2d713d6f574 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
@@ -20,6 +20,23 @@ struct a split_me (int a)
       retval = make_me_big (a);
       retval = make_me_big (a);
       retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
+      retval = make_me_big (a);
       return retval;
     }
 }
-- 
2.13.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-22 10:27   ` Richard Biener
@ 2017-06-22 10:57     ` Martin Liška
  2017-06-22 11:47       ` Richard Biener
  2017-06-30 13:48     ` Martin Liška
  1 sibling, 1 reply; 29+ messages in thread
From: Martin Liška @ 2017-06-22 10:57 UTC (permalink / raw)
  To: Richard Biener; +Cc: GCC Patches, Jan Hubicka, ppalka

On 06/22/2017 12:27 PM, Richard Biener wrote:
> On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
>> Hello.
>>
>> There's one additional predictor enhancement that is GOTO predict that
>> used to working. Following patch adds expect statement for C and C++ family
>> languages.
>>
>> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
>> appears just once. Adding Richi and Patrick who can probably help how to fix the
>> test-case.
> 
> Happens to be optimized better now, there's only one predicate to simplify
> left in the IL input to VRP1.  I suggest to change it to match 1 times and add
> -fdump-tree-optimized to dg-options and
> 
> /* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */
> 
> to verify we have 3 conditions left.

Thanks for help.
What about the comment:

/* The first n_sets > 0 test can be simplfiied into n_sets == 1 since
   n_sets can only have the values [0, 1] as it's the result of a
   boolean operation.

   The second n_sets > 0 test can also be simplified into n_sets == 1
   as the only way to reach the tests is when n_sets <= 1 and the only
   value which satisfies both conditions is n_sets == 1.  */

I guess just only one can be valid? Or is it a different story now?

Martin

> 
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Ready to be installed?
>> Martin

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-22 10:57     ` Martin Liška
@ 2017-06-22 11:47       ` Richard Biener
  2017-06-30  9:24         ` Martin Liška
  0 siblings, 1 reply; 29+ messages in thread
From: Richard Biener @ 2017-06-22 11:47 UTC (permalink / raw)
  To: Martin Liška; +Cc: GCC Patches, Jan Hubicka, ppalka

On Thu, Jun 22, 2017 at 12:57 PM, Martin Liška <mliska@suse.cz> wrote:
> On 06/22/2017 12:27 PM, Richard Biener wrote:
>> On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
>>> Hello.
>>>
>>> There's one additional predictor enhancement that is GOTO predict that
>>> used to working. Following patch adds expect statement for C and C++ family
>>> languages.
>>>
>>> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
>>> appears just once. Adding Richi and Patrick who can probably help how to fix the
>>> test-case.
>>
>> Happens to be optimized better now, there's only one predicate to simplify
>> left in the IL input to VRP1.  I suggest to change it to match 1 times and add
>> -fdump-tree-optimized to dg-options and
>>
>> /* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */
>>
>> to verify we have 3 conditions left.
>
> Thanks for help.
> What about the comment:
>
> /* The first n_sets > 0 test can be simplfiied into n_sets == 1 since
>    n_sets can only have the values [0, 1] as it's the result of a
>    boolean operation.
>
>    The second n_sets > 0 test can also be simplified into n_sets == 1
>    as the only way to reach the tests is when n_sets <= 1 and the only
>    value which satisfies both conditions is n_sets == 1.  */
>
> I guess just only one can be valid? Or is it a different story now?

The 2nd one is handled by earlier jump-threading.

> Martin
>
>>
>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>>
>>> Ready to be installed?
>>> Martin
>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-21 12:50             ` Martin Liška
  2017-06-22 10:48               ` [PATCH] Fix ipa-split-5.c test-case Martin Liška
@ 2017-06-22 14:14               ` Christophe Lyon
  2017-06-23  7:03                 ` Martin Liška
  1 sibling, 1 reply; 29+ messages in thread
From: Christophe Lyon @ 2017-06-22 14:14 UTC (permalink / raw)
  To: Martin Liška; +Cc: Jan Hubicka, gcc-patches

Hi,


On 21 June 2017 at 14:50, Martin Liška <mliska@suse.cz> wrote:
> On 06/21/2017 10:26 AM, Jan Hubicka wrote:
>>>
>>> Ok, so I fixed that in the described way. There's one remaining fallout of:
>>> gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
>>>
>>> Where a fnsplit is properly done, but then it's again inlined:
>>>
>>> Considering split_me.part.0/5 with 23 size
>>>  to be inlined into test/2 in unknown:0
>>>  Estimated badness is -0.000001, frequency 0.33.
>>>  Inlined split_me.part.0 into test which now has time 50.300000 and size 44, net change of +17.
>>>
>>> Considering split_me.part.0/5 with 23 size
>>>  to be inlined into test/2 in unknown:0
>>>  Estimated badness is -0.000001, frequency 0.33.
>>>  Inlined split_me.part.0 into test which now has time 70.760000 and size 61, net change of +17.
>>>
>>> Considering split_me.part.0/5 with 23 size
>>>  to be inlined into test/2 in unknown:0
>>>  Estimated badness is -0.000001, frequency 0.33.
>>>  Inlined split_me.part.0 into test which now has time 91.220000 and size 78, net change of +17.
>>>
>>> Considering split_me.part.0/5 with 23 size
>>>  to be inlined into test/2 in unknown:0
>>>  Estimated badness is -0.000001, frequency 0.33.
>>>  Inlined split_me.part.0 into test which now has time 111.680000 and size 95, net change of +17.
>>> Unit growth for small function inlining: 61->129 (111%)
>>>
>>> ...
>>>
>>> Any hint how to block the IPA inlining?
>>
>> I guess you only want to make cold part of split_me bigger or
>> just use --param to reduce growth for auto inlining.
>>
>> How the patch reduces split_me_part considerably?
>> Honza
>
> Well, I probably overlooked test results, test works fine.
>
> I'm going to install the patch.
>

Since this commit (r249450), I have noticed a regression:
FAIL:    gcc.dg/tree-ssa/ipa-split-5.c scan-tree-dump optimized "part"
on aarch64/arm

Christophe


> Martin
>
>>>
>>> Sending new version of patch.
>>> Martin
>>>
>>>>
>>>> I would just move pass_strip_predict_hints pre-IPA and not worry about
>>>> them chaining.
>>>>
>>>> There is problem that after inlining the prediction may expand its scope
>>>> and predict branch that it outside of the original function body,
>>>> but I do not see very easy solution for that besides not re-doing
>>>> prediction (we could also copy probabilities from the inlined function
>>>> when they exists and honnor them in the outer function. I am not sure
>>>> that is going to improve prediction quality though - extra context
>>>> is probably useful)
>>>>
>>>> Thanks,
>>>> Honza
>>>>>
>>>>> Thanks,
>>>>> Martin
>>>>>
>>>>>>
>>>>>> Where did you found this case?
>>>>>> Honza
>>>>>>>
>>>>>>>        /* Create a new deep copy of the statement.  */
>>>>>>>        copy = gimple_copy (stmt);
>>>>>>> --
>>>>>>> 2.13.0
>>>>>>>
>>>
>>
>>> >From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
>>> From: marxin <mliska@suse.cz>
>>> Date: Tue, 6 Jun 2017 10:55:18 +0200
>>> Subject: [PATCH 1/2] Make early return predictor more precise.
>>>
>>> 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.
>>>      * predict.def: Change default value of early return to 66.
>>>      * tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
>>>      statements.
>>>      * passes.def: Put pass_strip_predict_hints to the beginning of
>>>      IPA passes.
>>> ---
>>>  gcc/gimple-low.c     |  2 ++
>>>  gcc/gimple-predict.h |  8 ++++++++
>>>  gcc/gimplify.c       | 16 ++++++++++++++++
>>>  gcc/passes.def       |  1 +
>>>  gcc/predict.c        | 41 -----------------------------------------
>>>  gcc/predict.def      | 15 +++------------
>>>  gcc/tree-tailcall.c  |  2 ++
>>>  7 files changed, 32 insertions(+), 53 deletions(-)
>>>
>>> diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
>>> index 619b9d7bfb1..4ea6c3532f3 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:
>>> 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 9af95a28704..1c6e1591953 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/passes.def b/gcc/passes.def
>>> index c14f6b9f63c..316e19d12e3 100644
>>> --- a/gcc/passes.def
>>> +++ b/gcc/passes.def
>>> @@ -107,6 +107,7 @@ along with GCC; see the file COPYING3.  If not see
>>>           early optimizations again.  It is thus good idea to do this
>>>            late.  */
>>>        NEXT_PASS (pass_split_functions);
>>> +      NEXT_PASS (pass_strip_predict_hints);
>>>        POP_INSERT_PASSES ()
>>>        NEXT_PASS (pass_release_ssa_names);
>>>        NEXT_PASS (pass_rebuild_cgraph_edges);
>>> diff --git a/gcc/predict.c b/gcc/predict.c
>>> index 60d1a094d10..790be9fbf16 100644
>>> --- a/gcc/predict.c
>>> +++ b/gcc/predict.c
>>> @@ -2739,7 +2739,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
>>>  {
>>>    edge e;
>>>    edge_iterator ei;
>>> -  gimple *last;
>>>
>>>    FOR_EACH_EDGE (e, ei, bb->succs)
>>>      {
>>> @@ -2766,46 +2765,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only)
>>>          }
>>>      }
>>>
>>> -      /* 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/tree-tailcall.c b/gcc/tree-tailcall.c
>>> index b7053387e91..6aa9a56462e 100644
>>> --- a/gcc/tree-tailcall.c
>>> +++ b/gcc/tree-tailcall.c
>>> @@ -421,6 +421,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
>>>        if (gimple_code (stmt) == GIMPLE_LABEL
>>>        || gimple_code (stmt) == GIMPLE_RETURN
>>>        || gimple_code (stmt) == GIMPLE_NOP
>>> +      || gimple_code (stmt) == GIMPLE_PREDICT
>>>        || gimple_clobber_p (stmt)
>>>        || is_gimple_debug (stmt))
>>>      continue;
>>> @@ -555,6 +556,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
>>>
>>>        if (gimple_code (stmt) == GIMPLE_LABEL
>>>        || gimple_code (stmt) == GIMPLE_NOP
>>> +      || gimple_code (stmt) == GIMPLE_PREDICT
>>>        || gimple_clobber_p (stmt)
>>>        || is_gimple_debug (stmt))
>>>      continue;
>>> --
>>> 2.13.1
>>>
>>
>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-22 14:14               ` [PATCH 2/3] Make early return predictor more precise Christophe Lyon
@ 2017-06-23  7:03                 ` Martin Liška
  2017-06-23  7:40                   ` Christophe Lyon
  0 siblings, 1 reply; 29+ messages in thread
From: Martin Liška @ 2017-06-23  7:03 UTC (permalink / raw)
  To: Christophe Lyon; +Cc: Jan Hubicka, gcc-patches

On 06/22/2017 04:14 PM, Christophe Lyon wrote:
> Since this commit (r249450), I have noticed a regression:
> FAIL:    gcc.dg/tree-ssa/ipa-split-5.c scan-tree-dump optimized "part"
> on aarch64/arm
> 
> Christophe

Hello.

I'm aware of the failure and I fixed that (hopefully) in r249503.
Can you please test that?

Thanks,
Martin

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 2/3] Make early return predictor more precise.
  2017-06-23  7:03                 ` Martin Liška
@ 2017-06-23  7:40                   ` Christophe Lyon
  0 siblings, 0 replies; 29+ messages in thread
From: Christophe Lyon @ 2017-06-23  7:40 UTC (permalink / raw)
  To: Martin Liška; +Cc: Jan Hubicka, gcc-patches

On 23 June 2017 at 09:03, Martin Liška <mliska@suse.cz> wrote:
> On 06/22/2017 04:14 PM, Christophe Lyon wrote:
>> Since this commit (r249450), I have noticed a regression:
>> FAIL:    gcc.dg/tree-ssa/ipa-split-5.c scan-tree-dump optimized "part"
>> on aarch64/arm
>>
>> Christophe
>
> Hello.
>
> I'm aware of the failure and I fixed that (hopefully) in r249503.
> Can you please test that?
>
Yes, I can confirm it's now OK. Thanks

> Thanks,
> Martin

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-22 11:47       ` Richard Biener
@ 2017-06-30  9:24         ` Martin Liška
  2017-06-30 12:37           ` Jan Hubicka
  0 siblings, 1 reply; 29+ messages in thread
From: Martin Liška @ 2017-06-30  9:24 UTC (permalink / raw)
  To: Richard Biener; +Cc: GCC Patches, Jan Hubicka, ppalka

PING^1

Can you please Honza give a formal approval for the patch?

Thanks,
Martin

On 06/22/2017 01:47 PM, Richard Biener wrote:
> On Thu, Jun 22, 2017 at 12:57 PM, Martin Liška <mliska@suse.cz> wrote:
>> On 06/22/2017 12:27 PM, Richard Biener wrote:
>>> On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
>>>> Hello.
>>>>
>>>> There's one additional predictor enhancement that is GOTO predict that
>>>> used to working. Following patch adds expect statement for C and C++ family
>>>> languages.
>>>>
>>>> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
>>>> appears just once. Adding Richi and Patrick who can probably help how to fix the
>>>> test-case.
>>>
>>> Happens to be optimized better now, there's only one predicate to simplify
>>> left in the IL input to VRP1.  I suggest to change it to match 1 times and add
>>> -fdump-tree-optimized to dg-options and
>>>
>>> /* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */
>>>
>>> to verify we have 3 conditions left.
>>
>> Thanks for help.
>> What about the comment:
>>
>> /* The first n_sets > 0 test can be simplfiied into n_sets == 1 since
>>    n_sets can only have the values [0, 1] as it's the result of a
>>    boolean operation.
>>
>>    The second n_sets > 0 test can also be simplified into n_sets == 1
>>    as the only way to reach the tests is when n_sets <= 1 and the only
>>    value which satisfies both conditions is n_sets == 1.  */
>>
>> I guess just only one can be valid? Or is it a different story now?
> 
> The 2nd one is handled by earlier jump-threading.
> 
>> Martin
>>
>>>
>>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>>>
>>>> Ready to be installed?
>>>> Martin
>>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-30  9:24         ` Martin Liška
@ 2017-06-30 12:37           ` Jan Hubicka
  0 siblings, 0 replies; 29+ messages in thread
From: Jan Hubicka @ 2017-06-30 12:37 UTC (permalink / raw)
  To: Martin Li?ka; +Cc: Richard Biener, GCC Patches, Jan Hubicka, ppalka

> PING^1
> 
> Can you please Honza give a formal approval for the patch?

OK,
thanks!
Honza
> 
> Thanks,
> Martin
> 
> On 06/22/2017 01:47 PM, Richard Biener wrote:
> > On Thu, Jun 22, 2017 at 12:57 PM, Martin Liška <mliska@suse.cz> wrote:
> >> On 06/22/2017 12:27 PM, Richard Biener wrote:
> >>> On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
> >>>> Hello.
> >>>>
> >>>> There's one additional predictor enhancement that is GOTO predict that
> >>>> used to working. Following patch adds expect statement for C and C++ family
> >>>> languages.
> >>>>
> >>>> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
> >>>> appears just once. Adding Richi and Patrick who can probably help how to fix the
> >>>> test-case.
> >>>
> >>> Happens to be optimized better now, there's only one predicate to simplify
> >>> left in the IL input to VRP1.  I suggest to change it to match 1 times and add
> >>> -fdump-tree-optimized to dg-options and
> >>>
> >>> /* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */
> >>>
> >>> to verify we have 3 conditions left.
> >>
> >> Thanks for help.
> >> What about the comment:
> >>
> >> /* The first n_sets > 0 test can be simplfiied into n_sets == 1 since
> >>    n_sets can only have the values [0, 1] as it's the result of a
> >>    boolean operation.
> >>
> >>    The second n_sets > 0 test can also be simplified into n_sets == 1
> >>    as the only way to reach the tests is when n_sets <= 1 and the only
> >>    value which satisfies both conditions is n_sets == 1.  */
> >>
> >> I guess just only one can be valid? Or is it a different story now?
> > 
> > The 2nd one is handled by earlier jump-threading.
> > 
> >> Martin
> >>
> >>>
> >>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
> >>>>
> >>>> Ready to be installed?
> >>>> Martin
> >>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-22 10:27   ` Richard Biener
  2017-06-22 10:57     ` Martin Liška
@ 2017-06-30 13:48     ` Martin Liška
  2017-07-31  7:47       ` Martin Liška
  1 sibling, 1 reply; 29+ messages in thread
From: Martin Liška @ 2017-06-30 13:48 UTC (permalink / raw)
  To: Richard Biener; +Cc: GCC Patches, Jan Hubicka, ppalka

On 06/22/2017 12:27 PM, Richard Biener wrote:
> On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
>> Hello.
>>
>> There's one additional predictor enhancement that is GOTO predict that
>> used to working. Following patch adds expect statement for C and C++ family
>> languages.
>>
>> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
>> appears just once. Adding Richi and Patrick who can probably help how to fix the
>> test-case.
> 
> Happens to be optimized better now, there's only one predicate to simplify
> left in the IL input to VRP1.  I suggest to change it to match 1 times and add
> -fdump-tree-optimized to dg-options and
> 
> /* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */
> 
> to verify we have 3 conditions left.

One small note, I see 4 conditions in optimized dump:

sss (struct rtx_def * insn, int code1, int code2, int code3)
{
  int D1544;
  struct rtx_def * body;
  _Bool D1562;

  <bb 2> [100.00%] [count: INV]:
  body_5 = insn_4(D)->u.fld[5].rt_rtx;
  D1544_6 = body_5->code;
  if (D1544_6 == 55)
    goto <bb 7> (L7); [34.00%] [count: INV]
  else
    goto <bb 3>; [66.00%] [count: INV]

  <bb 3> [66.00%] [count: INV]:
  if (code3_7(D) == 99)
    goto <bb 4>; [34.00%] [count: INV]
  else
    goto <bb 8> (L16); [66.00%] [count: INV]

  <bb 4> [22.44%] [count: INV]:
  D1562_9 = code1_8(D) == 10;
  if (D1562_9 == 1)
    goto <bb 7> (L7); [64.00%] [count: INV]
  else
    goto <bb 8> (L16); [36.00%] [count: INV]

  <bb 5> [9.82%] [count: INV]:
  arf ();

  <bb 6> [46.68%] [count: INV]:
  frob (); [tail call]
  goto <bb 8> (L16); [100.00%] [count: INV]

L7 [48.36%] [count: INV]:
  if (code2_12(D) == 42)
    goto <bb 5>; [20.24%] [count: INV]
  else
    goto <bb 6>; [79.76%] [count: INV]

L16 [100.00%] [count: INV]:
  return;

}

Is it a problem or adjusting to 4 is fine?

Martin

> 
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Ready to be installed?
>> Martin

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-06-30 13:48     ` Martin Liška
@ 2017-07-31  7:47       ` Martin Liška
  2017-07-31  8:55         ` Richard Biener
  0 siblings, 1 reply; 29+ messages in thread
From: Martin Liška @ 2017-07-31  7:47 UTC (permalink / raw)
  To: Richard Biener; +Cc: GCC Patches, Jan Hubicka, ppalka

Richi?

Thanks

On 06/30/2017 03:48 PM, Martin Liška wrote:
> On 06/22/2017 12:27 PM, Richard Biener wrote:
>> On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
>>> Hello.
>>>
>>> There's one additional predictor enhancement that is GOTO predict that
>>> used to working. Following patch adds expect statement for C and C++ family
>>> languages.
>>>
>>> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
>>> appears just once. Adding Richi and Patrick who can probably help how to fix the
>>> test-case.
>>
>> Happens to be optimized better now, there's only one predicate to simplify
>> left in the IL input to VRP1.  I suggest to change it to match 1 times and add
>> -fdump-tree-optimized to dg-options and
>>
>> /* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */
>>
>> to verify we have 3 conditions left.
> 
> One small note, I see 4 conditions in optimized dump:
> 
> sss (struct rtx_def * insn, int code1, int code2, int code3)
> {
>   int D1544;
>   struct rtx_def * body;
>   _Bool D1562;
> 
>   <bb 2> [100.00%] [count: INV]:
>   body_5 = insn_4(D)->u.fld[5].rt_rtx;
>   D1544_6 = body_5->code;
>   if (D1544_6 == 55)
>     goto <bb 7> (L7); [34.00%] [count: INV]
>   else
>     goto <bb 3>; [66.00%] [count: INV]
> 
>   <bb 3> [66.00%] [count: INV]:
>   if (code3_7(D) == 99)
>     goto <bb 4>; [34.00%] [count: INV]
>   else
>     goto <bb 8> (L16); [66.00%] [count: INV]
> 
>   <bb 4> [22.44%] [count: INV]:
>   D1562_9 = code1_8(D) == 10;
>   if (D1562_9 == 1)
>     goto <bb 7> (L7); [64.00%] [count: INV]
>   else
>     goto <bb 8> (L16); [36.00%] [count: INV]
> 
>   <bb 5> [9.82%] [count: INV]:
>   arf ();
> 
>   <bb 6> [46.68%] [count: INV]:
>   frob (); [tail call]
>   goto <bb 8> (L16); [100.00%] [count: INV]
> 
> L7 [48.36%] [count: INV]:
>   if (code2_12(D) == 42)
>     goto <bb 5>; [20.24%] [count: INV]
>   else
>     goto <bb 6>; [79.76%] [count: INV]
> 
> L16 [100.00%] [count: INV]:
>   return;
> 
> }
> 
> Is it a problem or adjusting to 4 is fine?
> 
> Martin
> 
>>
>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>>
>>> Ready to be installed?
>>> Martin
> 

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH 4/N] Recover GOTO predictor.
  2017-07-31  7:47       ` Martin Liška
@ 2017-07-31  8:55         ` Richard Biener
  0 siblings, 0 replies; 29+ messages in thread
From: Richard Biener @ 2017-07-31  8:55 UTC (permalink / raw)
  To: Martin Liška; +Cc: GCC Patches, Jan Hubicka, ppalka

On Mon, Jul 31, 2017 at 9:46 AM, Martin Liška <mliska@suse.cz> wrote:
> Richi?

4 is fine.

> Thanks
>
> On 06/30/2017 03:48 PM, Martin Liška wrote:
>> On 06/22/2017 12:27 PM, Richard Biener wrote:
>>> On Wed, Jun 21, 2017 at 3:06 PM, Martin Liška <mliska@suse.cz> wrote:
>>>> Hello.
>>>>
>>>> There's one additional predictor enhancement that is GOTO predict that
>>>> used to working. Following patch adds expect statement for C and C++ family
>>>> languages.
>>>>
>>>> There's one fallout which is vrp24.c test-case, where only 'Simplified relational'
>>>> appears just once. Adding Richi and Patrick who can probably help how to fix the
>>>> test-case.
>>>
>>> Happens to be optimized better now, there's only one predicate to simplify
>>> left in the IL input to VRP1.  I suggest to change it to match 1 times and add
>>> -fdump-tree-optimized to dg-options and
>>>
>>> /* { dg-final { scan-tree-dump-times "if " 3 "optimized" } } */
>>>
>>> to verify we have 3 conditions left.
>>
>> One small note, I see 4 conditions in optimized dump:
>>
>> sss (struct rtx_def * insn, int code1, int code2, int code3)
>> {
>>   int D1544;
>>   struct rtx_def * body;
>>   _Bool D1562;
>>
>>   <bb 2> [100.00%] [count: INV]:
>>   body_5 = insn_4(D)->u.fld[5].rt_rtx;
>>   D1544_6 = body_5->code;
>>   if (D1544_6 == 55)
>>     goto <bb 7> (L7); [34.00%] [count: INV]
>>   else
>>     goto <bb 3>; [66.00%] [count: INV]
>>
>>   <bb 3> [66.00%] [count: INV]:
>>   if (code3_7(D) == 99)
>>     goto <bb 4>; [34.00%] [count: INV]
>>   else
>>     goto <bb 8> (L16); [66.00%] [count: INV]
>>
>>   <bb 4> [22.44%] [count: INV]:
>>   D1562_9 = code1_8(D) == 10;
>>   if (D1562_9 == 1)
>>     goto <bb 7> (L7); [64.00%] [count: INV]
>>   else
>>     goto <bb 8> (L16); [36.00%] [count: INV]
>>
>>   <bb 5> [9.82%] [count: INV]:
>>   arf ();
>>
>>   <bb 6> [46.68%] [count: INV]:
>>   frob (); [tail call]
>>   goto <bb 8> (L16); [100.00%] [count: INV]
>>
>> L7 [48.36%] [count: INV]:
>>   if (code2_12(D) == 42)
>>     goto <bb 5>; [20.24%] [count: INV]
>>   else
>>     goto <bb 6>; [79.76%] [count: INV]
>>
>> L16 [100.00%] [count: INV]:
>>   return;
>>
>> }
>>
>> Is it a problem or adjusting to 4 is fine?
>>
>> Martin
>>
>>>
>>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>>>
>>>> Ready to be installed?
>>>> Martin
>>
>

^ permalink raw reply	[flat|nested] 29+ messages in thread

end of thread, other threads:[~2017-07-31  8:55 UTC | newest]

Thread overview: 29+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-06-06  9:05 [PATCH 0/3] Rework early return and hot/cold label predictors marxin
2017-06-06  9:05 ` [PATCH 3/3] Rework cold and hot label attributes in predict.c marxin
2017-06-09 14:04   ` Jan Hubicka
2017-06-06  9:05 ` [PATCH 2/3] Make early return predictor more precise marxin
2017-06-09 14:08   ` Jan Hubicka
2017-06-13 10:59     ` Martin Liška
2017-06-19 11:11       ` Jan Hubicka
2017-06-20 12:13         ` Martin Liška
2017-06-21  8:27           ` Jan Hubicka
2017-06-21 12:50             ` Martin Liška
2017-06-22 10:48               ` [PATCH] Fix ipa-split-5.c test-case Martin Liška
2017-06-22 14:14               ` [PATCH 2/3] Make early return predictor more precise Christophe Lyon
2017-06-23  7:03                 ` Martin Liška
2017-06-23  7:40                   ` Christophe Lyon
2017-06-06  9:05 ` [PATCH 1/3] Come up with selftests for predict.c marxin
2017-06-06 10:44   ` David Malcolm
2017-06-08 12:30     ` Martin Liška
2017-06-08 13:09       ` David Malcolm
2017-06-08 23:07       ` Jan Hubicka
2017-06-21 13:06 ` [PATCH 4/N] Recover GOTO predictor Martin Liška
2017-06-21 13:09   ` Martin Liška
2017-06-22 10:27   ` Richard Biener
2017-06-22 10:57     ` Martin Liška
2017-06-22 11:47       ` Richard Biener
2017-06-30  9:24         ` Martin Liška
2017-06-30 12:37           ` Jan Hubicka
2017-06-30 13:48     ` Martin Liška
2017-07-31  7:47       ` Martin Liška
2017-07-31  8:55         ` Richard Biener

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).