* [PATCH] Introduce __builtin_expect_with_probability (PR target/83610).
@ 2018-07-24 7:22 Martin Liška
2018-07-31 9:24 ` Jan Hubicka
0 siblings, 1 reply; 6+ messages in thread
From: Martin Liška @ 2018-07-24 7:22 UTC (permalink / raw)
To: gcc-patches; +Cc: Jan Hubicka
[-- Attachment #1: Type: text/plain, Size: 2279 bytes --]
Hi.
This is implementation of new built-in that can be used for more fine
tweaking of probability. Micro benchmark is attached as part of the PR.
Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
Ready to be installed?
Martin
gcc/ChangeLog:
2018-07-24 Martin Liska <mliska@suse.cz>
PR target/83610
* builtin-types.def (BT_FN_LONG_LONG_LONG_LONG): New type.
* builtins.c (expand_builtin_expect_with_probability):
New function.
(expand_builtin): Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
(build_builtin_expect_predicate): Likewise.
(fold_builtin_expect): Likewise.
(fold_builtin_2): Likewise.
(fold_builtin_3): Likewise.
* builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY): Define new
builtin.
* builtins.h (fold_builtin_expect): Add new argument
(probability).
* doc/extend.texi: Document the new builtin.
* doc/invoke.texi: Likewise.
* gimple-fold.c (gimple_fold_call): Pass new argument.
* ipa-fnsummary.c (find_foldable_builtin_expect):
Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
* predict.c (expr_expected_value): Add new out argument which
is probability.
(expr_expected_value_1): Likewise.
(tree_predict_by_opcode): Predict edge based on
provided probability.
(pass_strip_predict_hints::execute): Use newly added
DECL_BUILT_IN_P macro.
* predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY):
Define new predictor.
* tree.h (DECL_BUILT_IN_P): Define.
gcc/testsuite/ChangeLog:
2018-07-24 Martin Liska <mliska@suse.cz>
* gcc.dg/predict-16.c: New test.
---
gcc/builtin-types.def | 2 +
gcc/builtins.c | 65 ++++++++++++++++++++++++-------
gcc/builtins.def | 1 +
gcc/builtins.h | 2 +-
gcc/doc/extend.texi | 8 ++++
gcc/doc/invoke.texi | 3 ++
gcc/gimple-fold.c | 3 +-
gcc/ipa-fnsummary.c | 1 +
gcc/predict.c | 61 ++++++++++++++++++++++-------
gcc/predict.def | 5 +++
gcc/testsuite/gcc.dg/predict-16.c | 13 +++++++
gcc/tree.h | 6 +++
12 files changed, 140 insertions(+), 30 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
[-- Attachment #2: 0001-Introduce-__builtin_expect_with_probability-PR-targe.patch --]
[-- Type: text/x-patch, Size: 18526 bytes --]
diff --git a/gcc/builtin-types.def b/gcc/builtin-types.def
index b01095c420f..6e87bcbbf1d 100644
--- a/gcc/builtin-types.def
+++ b/gcc/builtin-types.def
@@ -531,6 +531,8 @@ DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_ULONG_ULONG,
BT_ULONG, BT_ULONG, BT_ULONG, BT_ULONG)
DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_UINT_UINT,
BT_LONG, BT_LONG, BT_UINT, BT_UINT)
+DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_LONG_LONG,
+ BT_LONG, BT_LONG, BT_LONG, BT_LONG)
DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_UINT_UINT,
BT_ULONG, BT_ULONG, BT_UINT, BT_UINT)
DEF_FUNCTION_TYPE_3 (BT_FN_STRING_CONST_STRING_CONST_STRING_INT,
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 539a6d17688..29d77d3d83b 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -148,6 +148,7 @@ static rtx expand_builtin_unop (machine_mode, tree, rtx, rtx, optab);
static rtx expand_builtin_frame_address (tree, tree);
static tree stabilize_va_list_loc (location_t, tree, int);
static rtx expand_builtin_expect (tree, rtx);
+static rtx expand_builtin_expect_with_probability (tree, rtx);
static tree fold_builtin_constant_p (tree);
static tree fold_builtin_classify_type (tree);
static tree fold_builtin_strlen (location_t, tree, tree);
@@ -5237,6 +5238,27 @@ expand_builtin_expect (tree exp, rtx target)
return target;
}
+/* Expand a call to __builtin_expect_with_probability. We just return our
+ argument as the builtin_expect semantic should've been already executed by
+ tree branch prediction pass. */
+
+static rtx
+expand_builtin_expect_with_probability (tree exp, rtx target)
+{
+ tree arg;
+
+ if (call_expr_nargs (exp) < 3)
+ return const0_rtx;
+ arg = CALL_EXPR_ARG (exp, 0);
+
+ target = expand_expr (arg, target, VOIDmode, EXPAND_NORMAL);
+ /* When guessing was done, the hints should be already stripped away. */
+ gcc_assert (!flag_guess_branch_prob
+ || optimize == 0 || seen_error ());
+ return target;
+}
+
+
/* Expand a call to __builtin_assume_aligned. We just return our first
argument as the builtin_assume_aligned semantic should've been already
executed by CCP. */
@@ -7494,6 +7516,8 @@ expand_builtin (tree exp, rtx target, rtx subtarget, machine_mode mode,
return expand_builtin_va_copy (exp);
case BUILT_IN_EXPECT:
return expand_builtin_expect (exp, target);
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ return expand_builtin_expect_with_probability (exp, target);
case BUILT_IN_ASSUME_ALIGNED:
return expand_builtin_assume_aligned (exp, target);
case BUILT_IN_PREFETCH:
@@ -8134,16 +8158,20 @@ fold_builtin_constant_p (tree arg)
return NULL_TREE;
}
-/* Create builtin_expect with PRED and EXPECTED as its arguments and
- return it as a truthvalue. */
+/* Create builtin_expect or builtin_expect_with_probability
+ with PRED and EXPECTED as its arguments and return it as a truthvalue.
+ Fortran FE can also produce builtin_expect with PREDICTOR as third argument.
+ builtin_expect_with_probability instead uses third argument as PROBABILITY
+ value. */
static tree
build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
- tree predictor)
+ tree predictor, tree probability)
{
tree fn, arg_types, pred_type, expected_type, call_expr, ret_type;
- fn = builtin_decl_explicit (BUILT_IN_EXPECT);
+ fn = builtin_decl_explicit (probability == NULL_TREE ? BUILT_IN_EXPECT
+ : BUILT_IN_EXPECT_WITH_PROBABILITY);
arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
ret_type = TREE_TYPE (TREE_TYPE (fn));
pred_type = TREE_VALUE (arg_types);
@@ -8151,18 +8179,23 @@ build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
pred = fold_convert_loc (loc, pred_type, pred);
expected = fold_convert_loc (loc, expected_type, expected);
- call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
- predictor);
+
+ if (probability)
+ call_expr = build_call_expr_loc (loc, fn, 3, pred, expected, probability);
+ else
+ call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
+ predictor);
return build2 (NE_EXPR, TREE_TYPE (pred), call_expr,
build_int_cst (ret_type, 0));
}
-/* Fold a call to builtin_expect with arguments ARG0 and ARG1. Return
+/* Fold a call to builtin_expect with arguments ARG0, ARG1, ARG2, ARG3. Return
NULL_TREE if no simplification is possible. */
tree
-fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
+fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2,
+ tree arg3)
{
tree inner, fndecl, inner_arg0;
enum tree_code code;
@@ -8186,8 +8219,9 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
if (TREE_CODE (inner) == CALL_EXPR
&& (fndecl = get_callee_fndecl (inner))
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT)
+ && (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
+ || DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
+ BUILT_IN_EXPECT_WITH_PROBABILITY)))
return arg0;
inner = inner_arg0;
@@ -8198,8 +8232,8 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
tree op1 = TREE_OPERAND (inner, 1);
arg1 = save_expr (arg1);
- op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2);
- op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2);
+ op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2, arg3);
+ op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2, arg3);
inner = build2 (code, TREE_TYPE (inner), op0, op1);
return fold_convert_loc (loc, TREE_TYPE (arg0), inner);
@@ -9295,7 +9329,7 @@ fold_builtin_2 (location_t loc, tree fndecl, tree arg0, tree arg1)
return fold_builtin_strpbrk (loc, arg0, arg1, type);
case BUILT_IN_EXPECT:
- return fold_builtin_expect (loc, arg0, arg1, NULL_TREE);
+ return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, NULL_TREE);
case BUILT_IN_ISGREATER:
return fold_builtin_unordered_cmp (loc, fndecl,
@@ -9373,7 +9407,10 @@ fold_builtin_3 (location_t loc, tree fndecl,
return fold_builtin_memcmp (loc, arg0, arg1, arg2);
case BUILT_IN_EXPECT:
- return fold_builtin_expect (loc, arg0, arg1, arg2);
+ return fold_builtin_expect (loc, arg0, arg1, arg2, NULL_TREE);
+
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, arg2);
case BUILT_IN_ADD_OVERFLOW:
case BUILT_IN_SUB_OVERFLOW:
diff --git a/gcc/builtins.def b/gcc/builtins.def
index aacbd513a16..683a07e18fa 100644
--- a/gcc/builtins.def
+++ b/gcc/builtins.def
@@ -848,6 +848,7 @@ DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVP, "execvp", BT_FN_INT_CONST_STRING_PT
DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVE, "execve", BT_FN_INT_CONST_STRING_PTR_CONST_STRING_PTR_CONST_STRING, ATTR_NOTHROW_LIST)
DEF_LIB_BUILTIN (BUILT_IN_EXIT, "exit", BT_FN_VOID_INT, ATTR_NORETURN_NOTHROW_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXPECT, "expect", BT_FN_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_EXPECT_WITH_PROBABILITY, "expect_with_probability", BT_FN_LONG_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_ASSUME_ALIGNED, "assume_aligned", BT_FN_PTR_CONST_PTR_SIZE_VAR, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXTEND_POINTER, "extend_pointer", BT_FN_UNWINDWORD_PTR, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXTRACT_RETURN_ADDR, "extract_return_addr", BT_FN_PTR_PTR, ATTR_LEAF_LIST)
diff --git a/gcc/builtins.h b/gcc/builtins.h
index c9229049e21..3662ebcd98f 100644
--- a/gcc/builtins.h
+++ b/gcc/builtins.h
@@ -76,7 +76,7 @@ extern void expand_ifn_atomic_compare_exchange (gcall *);
extern rtx expand_builtin (tree, rtx, rtx, machine_mode, int);
extern rtx expand_builtin_with_bounds (tree, rtx, rtx, machine_mode, int);
extern enum built_in_function builtin_mathfn_code (const_tree);
-extern tree fold_builtin_expect (location_t, tree, tree, tree);
+extern tree fold_builtin_expect (location_t, tree, tree, tree, tree);
extern bool avoid_folding_inline_builtin (tree);
extern tree fold_call_expr (location_t, tree, bool);
extern tree fold_builtin_call_array (location_t, tree, tree, int, tree *);
diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
index 7b471ec40f7..8567b24f873 100644
--- a/gcc/doc/extend.texi
+++ b/gcc/doc/extend.texi
@@ -11852,6 +11852,14 @@ if (__builtin_expect (ptr != NULL, 1))
when testing pointer or floating-point values.
@end deftypefn
+@deftypefn {Built-in Function} long __builtin_expect_with_probability
+(long @var{exp}, long @var{c}, long @var{probability})
+
+The built-in has same semantics as @code{__builtin_expect_with_probability},
+but user can provide expected probability (in percent) for value of @var{exp}.
+Valid values of @var{probability} argument are in inclusive range 0 and 100.
+@end deftypefn
+
@deftypefn {Built-in Function} void __builtin_trap (void)
This function causes the program to exit abnormally. GCC implements
this function by using a target-dependent mechanism (such as
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 1dcdfb51c47..edc46a3be95 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -9209,6 +9209,9 @@ between the heuristics and @code{__builtin_expect} can be complex, and in
some cases, it may be useful to disable the heuristics so that the effects
of @code{__builtin_expect} are easier to understand.
+It is also possible to specify expected probability of the expression
+with @code{__builtin_expect_with_probability} built-in function.
+
The default is @option{-fguess-branch-probability} at levels
@option{-O}, @option{-O2}, @option{-O3}, @option{-Os}.
diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index 027ca4da97c..ea441797214 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -4166,7 +4166,8 @@ gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
result = fold_builtin_expect (gimple_location (stmt),
gimple_call_arg (stmt, 0),
gimple_call_arg (stmt, 1),
- gimple_call_arg (stmt, 2));
+ gimple_call_arg (stmt, 2),
+ NULL_TREE);
break;
case IFN_UBSAN_OBJECT_SIZE:
{
diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index c99718a265f..a8fc2c2df9a 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -1851,6 +1851,7 @@ find_foldable_builtin_expect (basic_block bb)
{
gimple *stmt = gsi_stmt (bsi);
if (gimple_call_builtin_p (stmt, BUILT_IN_EXPECT)
+ || gimple_call_builtin_p (stmt, BUILT_IN_EXPECT_WITH_PROBABILITY)
|| gimple_call_internal_p (stmt, IFN_BUILTIN_EXPECT))
{
tree var = gimple_call_lhs (stmt);
diff --git a/gcc/predict.c b/gcc/predict.c
index 65e088fb8df..73e2a0fd2ed 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2262,13 +2262,15 @@ guess_outgoing_edge_probabilities (basic_block bb)
combine_predictions_for_insn (BB_END (bb), bb);
}
\f
-static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
+static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
+ tree *probability);
/* Helper function for expr_expected_value. */
static tree
expr_expected_value_1 (tree type, tree op0, enum tree_code code,
- tree op1, bitmap visited, enum br_predictor *predictor)
+ tree op1, bitmap visited, enum br_predictor *predictor,
+ tree *probability)
{
gimple *def;
@@ -2329,7 +2331,8 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
if (arg == PHI_RESULT (def))
continue;
- new_val = expr_expected_value (arg, visited, &predictor2);
+ new_val = expr_expected_value (arg, visited, &predictor2,
+ probability);
/* It is difficult to combine value predictors. Simply assume
that later predictor is weaker and take its prediction. */
@@ -2353,7 +2356,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
gimple_assign_rhs1 (def),
gimple_assign_rhs_code (def),
gimple_assign_rhs2 (def),
- visited, predictor);
+ visited, predictor, NULL);
}
if (is_gimple_call (def))
@@ -2395,6 +2398,21 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
*predictor = PRED_BUILTIN_EXPECT;
return gimple_call_arg (def, 1);
}
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ {
+ tree val;
+ if (gimple_call_num_args (def) != 3)
+ return NULL;
+ val = gimple_call_arg (def, 0);
+ if (TREE_CONSTANT (val))
+ return val;
+ if (predictor)
+ {
+ *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
+ *probability = gimple_call_arg (def, 2);
+ }
+ return gimple_call_arg (def, 1);
+ }
case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
@@ -2426,10 +2444,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
{
tree res;
enum br_predictor predictor2;
- op0 = expr_expected_value (op0, visited, predictor);
+ op0 = expr_expected_value (op0, visited, predictor, probability);
if (!op0)
return NULL;
- op1 = expr_expected_value (op1, visited, &predictor2);
+ op1 = expr_expected_value (op1, visited, &predictor2, probability);
if (predictor && *predictor < predictor2)
*predictor = predictor2;
if (!op1)
@@ -2442,7 +2460,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
{
tree res;
- op0 = expr_expected_value (op0, visited, predictor);
+ op0 = expr_expected_value (op0, visited, predictor, probability);
if (!op0)
return NULL;
res = fold_build1 (code, type, op0);
@@ -2463,7 +2481,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
static tree
expr_expected_value (tree expr, bitmap visited,
- enum br_predictor *predictor)
+ enum br_predictor *predictor, tree *probability)
{
enum tree_code code;
tree op0, op1;
@@ -2477,7 +2495,8 @@ expr_expected_value (tree expr, bitmap visited,
extract_ops_from_tree (expr, &code, &op0, &op1);
return expr_expected_value_1 (TREE_TYPE (expr),
- op0, code, op1, visited, predictor);
+ op0, code, op1, visited, predictor,
+ probability);
}
\f
/* Predict using opcode of the last statement in basic block. */
@@ -2488,7 +2507,7 @@ tree_predict_by_opcode (basic_block bb)
edge then_edge;
tree op0, op1;
tree type;
- tree val;
+ tree val, probability;
enum tree_code cmp;
edge_iterator ei;
enum br_predictor predictor;
@@ -2503,7 +2522,7 @@ tree_predict_by_opcode (basic_block bb)
cmp = gimple_cond_code (stmt);
type = TREE_TYPE (op0);
val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
- &predictor);
+ &predictor, &probability);
if (val && TREE_CODE (val) == INTEGER_CST)
{
if (predictor == PRED_BUILTIN_EXPECT)
@@ -2515,6 +2534,19 @@ tree_predict_by_opcode (basic_block bb)
percent = 100 - percent;
predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
}
+ else if (predictor == PRED_BUILTIN_EXPECT_WITH_PROBABILITY)
+ {
+ if (!tree_fits_uhwi_p (probability))
+ return;
+
+ unsigned percent = tree_to_uhwi (probability);
+ if (integer_zerop (val))
+ percent = 100 - percent;
+ if (percent > 100)
+ return;
+ predict_edge (then_edge, PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
+ HITRATE (percent));
+ }
else
predict_edge_def (then_edge, predictor,
integer_zerop (val) ? NOT_TAKEN : TAKEN);
@@ -3927,10 +3959,11 @@ pass_strip_predict_hints::execute (function *fun)
{
tree fndecl = gimple_call_fndecl (stmt);
- if ((fndecl
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
+ if ((DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
&& gimple_call_num_args (stmt) == 2)
+ || (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
+ BUILT_IN_EXPECT_WITH_PROBABILITY)
+ && gimple_call_num_args (stmt) == 3)
|| (gimple_call_internal_p (stmt)
&& gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
{
diff --git a/gcc/predict.def b/gcc/predict.def
index 4ed97ed165c..b929d4c37db 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -69,6 +69,11 @@ DEF_PREDICTOR (PRED_COMPARE_AND_SWAP, "compare and swap", PROB_VERY_LIKELY,
DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY,
PRED_FLAG_FIRST_MATCH)
+/* Hints provided by user via __builtin_expect_with_probability. */
+DEF_PREDICTOR (PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
+ "__builtin_expect_with_probability", PROB_UNINITIALIZED,
+ PRED_FLAG_FIRST_MATCH)
+
/* Use number of loop iterations guessed by the contents of the loop. */
DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
diff --git a/gcc/testsuite/gcc.dg/predict-16.c b/gcc/testsuite/gcc.dg/predict-16.c
new file mode 100644
index 00000000000..043f154f19f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-16.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+void foo (int base)
+{
+ if (__builtin_expect_with_probability (base == 100, 1, 99))
+ global++;
+}
+
+/* { dg-final { scan-tree-dump "first match heuristics: 99.0%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 99.0%" "profile_estimate"} } */
diff --git a/gcc/tree.h b/gcc/tree.h
index 70ac78130c0..ae00e6e4035 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -3008,6 +3008,12 @@ extern vec<tree, va_gc> **decl_debug_args_insert (tree);
#define DECL_BUILT_IN_CLASS(NODE) \
(FUNCTION_DECL_CHECK (NODE)->function_decl.built_in_class)
+/* For a function declaration, return true if NODE is non-null and it is
+ a builtin of a CLASS with requested NAME. */
+#define DECL_BUILT_IN_P(NODE, CLASS, NAME) \
+ (NODE != NULL_TREE && DECL_BUILT_IN_CLASS (NODE) == CLASS \
+ && DECL_FUNCTION_CODE (NODE) == NAME)
+
/* In FUNCTION_DECL, a chain of ..._DECL nodes. */
#define DECL_ARGUMENTS(NODE) \
(FUNCTION_DECL_CHECK (NODE)->function_decl.arguments)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Introduce __builtin_expect_with_probability (PR target/83610).
2018-07-24 7:22 [PATCH] Introduce __builtin_expect_with_probability (PR target/83610) Martin Liška
@ 2018-07-31 9:24 ` Jan Hubicka
2018-08-01 12:21 ` Martin Liška
0 siblings, 1 reply; 6+ messages in thread
From: Jan Hubicka @ 2018-07-31 9:24 UTC (permalink / raw)
To: Martin Liška; +Cc: gcc-patches
> Hi.
>
> This is implementation of new built-in that can be used for more fine
> tweaking of probability. Micro benchmark is attached as part of the PR.
>
> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>
> Ready to be installed?
It reasonale to me to add the fature. Years ago I made similar patch and at
that time it did not go in based on argumentation that programers are not good
on guessing probabilities and this is too much of fine control while it should
be done by profile feedback.
However I guess it is better to have way to specify probability than tweak with
--param that controls the builtin_expect outcome globally.
What I think would be useful is to tie this to the code giving loop trip
estimate. If you know that the loop iterates 100 times at the average, you
can specify probability 1%. For this it seems to me more sensible to have
the percentage parameter to be double rather than long so one can specify larger
trip counts this way.
Honza
> Martin
>
> gcc/ChangeLog:
>
> 2018-07-24 Martin Liska <mliska@suse.cz>
>
> PR target/83610
> * builtin-types.def (BT_FN_LONG_LONG_LONG_LONG): New type.
> * builtins.c (expand_builtin_expect_with_probability):
> New function.
> (expand_builtin): Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
> (build_builtin_expect_predicate): Likewise.
> (fold_builtin_expect): Likewise.
> (fold_builtin_2): Likewise.
> (fold_builtin_3): Likewise.
> * builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY): Define new
> builtin.
> * builtins.h (fold_builtin_expect): Add new argument
> (probability).
> * doc/extend.texi: Document the new builtin.
> * doc/invoke.texi: Likewise.
> * gimple-fold.c (gimple_fold_call): Pass new argument.
> * ipa-fnsummary.c (find_foldable_builtin_expect):
> Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
> * predict.c (expr_expected_value): Add new out argument which
> is probability.
> (expr_expected_value_1): Likewise.
> (tree_predict_by_opcode): Predict edge based on
> provided probability.
> (pass_strip_predict_hints::execute): Use newly added
> DECL_BUILT_IN_P macro.
> * predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY):
> Define new predictor.
> * tree.h (DECL_BUILT_IN_P): Define.
>
> gcc/testsuite/ChangeLog:
>
> 2018-07-24 Martin Liska <mliska@suse.cz>
>
> * gcc.dg/predict-16.c: New test.
> ---
> gcc/builtin-types.def | 2 +
> gcc/builtins.c | 65 ++++++++++++++++++++++++-------
> gcc/builtins.def | 1 +
> gcc/builtins.h | 2 +-
> gcc/doc/extend.texi | 8 ++++
> gcc/doc/invoke.texi | 3 ++
> gcc/gimple-fold.c | 3 +-
> gcc/ipa-fnsummary.c | 1 +
> gcc/predict.c | 61 ++++++++++++++++++++++-------
> gcc/predict.def | 5 +++
> gcc/testsuite/gcc.dg/predict-16.c | 13 +++++++
> gcc/tree.h | 6 +++
> 12 files changed, 140 insertions(+), 30 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
>
>
> diff --git a/gcc/builtin-types.def b/gcc/builtin-types.def
> index b01095c420f..6e87bcbbf1d 100644
> --- a/gcc/builtin-types.def
> +++ b/gcc/builtin-types.def
> @@ -531,6 +531,8 @@ DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_ULONG_ULONG,
> BT_ULONG, BT_ULONG, BT_ULONG, BT_ULONG)
> DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_UINT_UINT,
> BT_LONG, BT_LONG, BT_UINT, BT_UINT)
> +DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_LONG_LONG,
> + BT_LONG, BT_LONG, BT_LONG, BT_LONG)
> DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_UINT_UINT,
> BT_ULONG, BT_ULONG, BT_UINT, BT_UINT)
> DEF_FUNCTION_TYPE_3 (BT_FN_STRING_CONST_STRING_CONST_STRING_INT,
> diff --git a/gcc/builtins.c b/gcc/builtins.c
> index 539a6d17688..29d77d3d83b 100644
> --- a/gcc/builtins.c
> +++ b/gcc/builtins.c
> @@ -148,6 +148,7 @@ static rtx expand_builtin_unop (machine_mode, tree, rtx, rtx, optab);
> static rtx expand_builtin_frame_address (tree, tree);
> static tree stabilize_va_list_loc (location_t, tree, int);
> static rtx expand_builtin_expect (tree, rtx);
> +static rtx expand_builtin_expect_with_probability (tree, rtx);
> static tree fold_builtin_constant_p (tree);
> static tree fold_builtin_classify_type (tree);
> static tree fold_builtin_strlen (location_t, tree, tree);
> @@ -5237,6 +5238,27 @@ expand_builtin_expect (tree exp, rtx target)
> return target;
> }
>
> +/* Expand a call to __builtin_expect_with_probability. We just return our
> + argument as the builtin_expect semantic should've been already executed by
> + tree branch prediction pass. */
> +
> +static rtx
> +expand_builtin_expect_with_probability (tree exp, rtx target)
> +{
> + tree arg;
> +
> + if (call_expr_nargs (exp) < 3)
> + return const0_rtx;
> + arg = CALL_EXPR_ARG (exp, 0);
> +
> + target = expand_expr (arg, target, VOIDmode, EXPAND_NORMAL);
> + /* When guessing was done, the hints should be already stripped away. */
> + gcc_assert (!flag_guess_branch_prob
> + || optimize == 0 || seen_error ());
> + return target;
> +}
> +
> +
> /* Expand a call to __builtin_assume_aligned. We just return our first
> argument as the builtin_assume_aligned semantic should've been already
> executed by CCP. */
> @@ -7494,6 +7516,8 @@ expand_builtin (tree exp, rtx target, rtx subtarget, machine_mode mode,
> return expand_builtin_va_copy (exp);
> case BUILT_IN_EXPECT:
> return expand_builtin_expect (exp, target);
> + case BUILT_IN_EXPECT_WITH_PROBABILITY:
> + return expand_builtin_expect_with_probability (exp, target);
> case BUILT_IN_ASSUME_ALIGNED:
> return expand_builtin_assume_aligned (exp, target);
> case BUILT_IN_PREFETCH:
> @@ -8134,16 +8158,20 @@ fold_builtin_constant_p (tree arg)
> return NULL_TREE;
> }
>
> -/* Create builtin_expect with PRED and EXPECTED as its arguments and
> - return it as a truthvalue. */
> +/* Create builtin_expect or builtin_expect_with_probability
> + with PRED and EXPECTED as its arguments and return it as a truthvalue.
> + Fortran FE can also produce builtin_expect with PREDICTOR as third argument.
> + builtin_expect_with_probability instead uses third argument as PROBABILITY
> + value. */
>
> static tree
> build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
> - tree predictor)
> + tree predictor, tree probability)
> {
> tree fn, arg_types, pred_type, expected_type, call_expr, ret_type;
>
> - fn = builtin_decl_explicit (BUILT_IN_EXPECT);
> + fn = builtin_decl_explicit (probability == NULL_TREE ? BUILT_IN_EXPECT
> + : BUILT_IN_EXPECT_WITH_PROBABILITY);
> arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
> ret_type = TREE_TYPE (TREE_TYPE (fn));
> pred_type = TREE_VALUE (arg_types);
> @@ -8151,18 +8179,23 @@ build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
>
> pred = fold_convert_loc (loc, pred_type, pred);
> expected = fold_convert_loc (loc, expected_type, expected);
> - call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
> - predictor);
> +
> + if (probability)
> + call_expr = build_call_expr_loc (loc, fn, 3, pred, expected, probability);
> + else
> + call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
> + predictor);
>
> return build2 (NE_EXPR, TREE_TYPE (pred), call_expr,
> build_int_cst (ret_type, 0));
> }
>
> -/* Fold a call to builtin_expect with arguments ARG0 and ARG1. Return
> +/* Fold a call to builtin_expect with arguments ARG0, ARG1, ARG2, ARG3. Return
> NULL_TREE if no simplification is possible. */
>
> tree
> -fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
> +fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2,
> + tree arg3)
> {
> tree inner, fndecl, inner_arg0;
> enum tree_code code;
> @@ -8186,8 +8219,9 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
>
> if (TREE_CODE (inner) == CALL_EXPR
> && (fndecl = get_callee_fndecl (inner))
> - && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
> - && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT)
> + && (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
> + || DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
> + BUILT_IN_EXPECT_WITH_PROBABILITY)))
> return arg0;
>
> inner = inner_arg0;
> @@ -8198,8 +8232,8 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
> tree op1 = TREE_OPERAND (inner, 1);
> arg1 = save_expr (arg1);
>
> - op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2);
> - op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2);
> + op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2, arg3);
> + op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2, arg3);
> inner = build2 (code, TREE_TYPE (inner), op0, op1);
>
> return fold_convert_loc (loc, TREE_TYPE (arg0), inner);
> @@ -9295,7 +9329,7 @@ fold_builtin_2 (location_t loc, tree fndecl, tree arg0, tree arg1)
> return fold_builtin_strpbrk (loc, arg0, arg1, type);
>
> case BUILT_IN_EXPECT:
> - return fold_builtin_expect (loc, arg0, arg1, NULL_TREE);
> + return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, NULL_TREE);
>
> case BUILT_IN_ISGREATER:
> return fold_builtin_unordered_cmp (loc, fndecl,
> @@ -9373,7 +9407,10 @@ fold_builtin_3 (location_t loc, tree fndecl,
> return fold_builtin_memcmp (loc, arg0, arg1, arg2);
>
> case BUILT_IN_EXPECT:
> - return fold_builtin_expect (loc, arg0, arg1, arg2);
> + return fold_builtin_expect (loc, arg0, arg1, arg2, NULL_TREE);
> +
> + case BUILT_IN_EXPECT_WITH_PROBABILITY:
> + return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, arg2);
>
> case BUILT_IN_ADD_OVERFLOW:
> case BUILT_IN_SUB_OVERFLOW:
> diff --git a/gcc/builtins.def b/gcc/builtins.def
> index aacbd513a16..683a07e18fa 100644
> --- a/gcc/builtins.def
> +++ b/gcc/builtins.def
> @@ -848,6 +848,7 @@ DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVP, "execvp", BT_FN_INT_CONST_STRING_PT
> DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVE, "execve", BT_FN_INT_CONST_STRING_PTR_CONST_STRING_PTR_CONST_STRING, ATTR_NOTHROW_LIST)
> DEF_LIB_BUILTIN (BUILT_IN_EXIT, "exit", BT_FN_VOID_INT, ATTR_NORETURN_NOTHROW_LIST)
> DEF_GCC_BUILTIN (BUILT_IN_EXPECT, "expect", BT_FN_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
> +DEF_GCC_BUILTIN (BUILT_IN_EXPECT_WITH_PROBABILITY, "expect_with_probability", BT_FN_LONG_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
> DEF_GCC_BUILTIN (BUILT_IN_ASSUME_ALIGNED, "assume_aligned", BT_FN_PTR_CONST_PTR_SIZE_VAR, ATTR_CONST_NOTHROW_LEAF_LIST)
> DEF_GCC_BUILTIN (BUILT_IN_EXTEND_POINTER, "extend_pointer", BT_FN_UNWINDWORD_PTR, ATTR_CONST_NOTHROW_LEAF_LIST)
> DEF_GCC_BUILTIN (BUILT_IN_EXTRACT_RETURN_ADDR, "extract_return_addr", BT_FN_PTR_PTR, ATTR_LEAF_LIST)
> diff --git a/gcc/builtins.h b/gcc/builtins.h
> index c9229049e21..3662ebcd98f 100644
> --- a/gcc/builtins.h
> +++ b/gcc/builtins.h
> @@ -76,7 +76,7 @@ extern void expand_ifn_atomic_compare_exchange (gcall *);
> extern rtx expand_builtin (tree, rtx, rtx, machine_mode, int);
> extern rtx expand_builtin_with_bounds (tree, rtx, rtx, machine_mode, int);
> extern enum built_in_function builtin_mathfn_code (const_tree);
> -extern tree fold_builtin_expect (location_t, tree, tree, tree);
> +extern tree fold_builtin_expect (location_t, tree, tree, tree, tree);
> extern bool avoid_folding_inline_builtin (tree);
> extern tree fold_call_expr (location_t, tree, bool);
> extern tree fold_builtin_call_array (location_t, tree, tree, int, tree *);
> diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
> index 7b471ec40f7..8567b24f873 100644
> --- a/gcc/doc/extend.texi
> +++ b/gcc/doc/extend.texi
> @@ -11852,6 +11852,14 @@ if (__builtin_expect (ptr != NULL, 1))
> when testing pointer or floating-point values.
> @end deftypefn
>
> +@deftypefn {Built-in Function} long __builtin_expect_with_probability
> +(long @var{exp}, long @var{c}, long @var{probability})
> +
> +The built-in has same semantics as @code{__builtin_expect_with_probability},
> +but user can provide expected probability (in percent) for value of @var{exp}.
> +Valid values of @var{probability} argument are in inclusive range 0 and 100.
> +@end deftypefn
> +
> @deftypefn {Built-in Function} void __builtin_trap (void)
> This function causes the program to exit abnormally. GCC implements
> this function by using a target-dependent mechanism (such as
> diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
> index 1dcdfb51c47..edc46a3be95 100644
> --- a/gcc/doc/invoke.texi
> +++ b/gcc/doc/invoke.texi
> @@ -9209,6 +9209,9 @@ between the heuristics and @code{__builtin_expect} can be complex, and in
> some cases, it may be useful to disable the heuristics so that the effects
> of @code{__builtin_expect} are easier to understand.
>
> +It is also possible to specify expected probability of the expression
> +with @code{__builtin_expect_with_probability} built-in function.
> +
> The default is @option{-fguess-branch-probability} at levels
> @option{-O}, @option{-O2}, @option{-O3}, @option{-Os}.
>
> diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
> index 027ca4da97c..ea441797214 100644
> --- a/gcc/gimple-fold.c
> +++ b/gcc/gimple-fold.c
> @@ -4166,7 +4166,8 @@ gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
> result = fold_builtin_expect (gimple_location (stmt),
> gimple_call_arg (stmt, 0),
> gimple_call_arg (stmt, 1),
> - gimple_call_arg (stmt, 2));
> + gimple_call_arg (stmt, 2),
> + NULL_TREE);
> break;
> case IFN_UBSAN_OBJECT_SIZE:
> {
> diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
> index c99718a265f..a8fc2c2df9a 100644
> --- a/gcc/ipa-fnsummary.c
> +++ b/gcc/ipa-fnsummary.c
> @@ -1851,6 +1851,7 @@ find_foldable_builtin_expect (basic_block bb)
> {
> gimple *stmt = gsi_stmt (bsi);
> if (gimple_call_builtin_p (stmt, BUILT_IN_EXPECT)
> + || gimple_call_builtin_p (stmt, BUILT_IN_EXPECT_WITH_PROBABILITY)
> || gimple_call_internal_p (stmt, IFN_BUILTIN_EXPECT))
> {
> tree var = gimple_call_lhs (stmt);
> diff --git a/gcc/predict.c b/gcc/predict.c
> index 65e088fb8df..73e2a0fd2ed 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -2262,13 +2262,15 @@ guess_outgoing_edge_probabilities (basic_block bb)
> combine_predictions_for_insn (BB_END (bb), bb);
> }
> \f
> -static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
> +static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
> + tree *probability);
>
> /* Helper function for expr_expected_value. */
>
> static tree
> expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> - tree op1, bitmap visited, enum br_predictor *predictor)
> + tree op1, bitmap visited, enum br_predictor *predictor,
> + tree *probability)
> {
> gimple *def;
>
> @@ -2329,7 +2331,8 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> if (arg == PHI_RESULT (def))
> continue;
>
> - new_val = expr_expected_value (arg, visited, &predictor2);
> + new_val = expr_expected_value (arg, visited, &predictor2,
> + probability);
>
> /* It is difficult to combine value predictors. Simply assume
> that later predictor is weaker and take its prediction. */
> @@ -2353,7 +2356,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> gimple_assign_rhs1 (def),
> gimple_assign_rhs_code (def),
> gimple_assign_rhs2 (def),
> - visited, predictor);
> + visited, predictor, NULL);
> }
>
> if (is_gimple_call (def))
> @@ -2395,6 +2398,21 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> *predictor = PRED_BUILTIN_EXPECT;
> return gimple_call_arg (def, 1);
> }
> + case BUILT_IN_EXPECT_WITH_PROBABILITY:
> + {
> + tree val;
> + if (gimple_call_num_args (def) != 3)
> + return NULL;
> + val = gimple_call_arg (def, 0);
> + if (TREE_CONSTANT (val))
> + return val;
> + if (predictor)
> + {
> + *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
> + *probability = gimple_call_arg (def, 2);
> + }
> + return gimple_call_arg (def, 1);
> + }
>
> case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
> case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
> @@ -2426,10 +2444,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> {
> tree res;
> enum br_predictor predictor2;
> - op0 = expr_expected_value (op0, visited, predictor);
> + op0 = expr_expected_value (op0, visited, predictor, probability);
> if (!op0)
> return NULL;
> - op1 = expr_expected_value (op1, visited, &predictor2);
> + op1 = expr_expected_value (op1, visited, &predictor2, probability);
> if (predictor && *predictor < predictor2)
> *predictor = predictor2;
> if (!op1)
> @@ -2442,7 +2460,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
> {
> tree res;
> - op0 = expr_expected_value (op0, visited, predictor);
> + op0 = expr_expected_value (op0, visited, predictor, probability);
> if (!op0)
> return NULL;
> res = fold_build1 (code, type, op0);
> @@ -2463,7 +2481,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>
> static tree
> expr_expected_value (tree expr, bitmap visited,
> - enum br_predictor *predictor)
> + enum br_predictor *predictor, tree *probability)
> {
> enum tree_code code;
> tree op0, op1;
> @@ -2477,7 +2495,8 @@ expr_expected_value (tree expr, bitmap visited,
>
> extract_ops_from_tree (expr, &code, &op0, &op1);
> return expr_expected_value_1 (TREE_TYPE (expr),
> - op0, code, op1, visited, predictor);
> + op0, code, op1, visited, predictor,
> + probability);
> }
> \f
> /* Predict using opcode of the last statement in basic block. */
> @@ -2488,7 +2507,7 @@ tree_predict_by_opcode (basic_block bb)
> edge then_edge;
> tree op0, op1;
> tree type;
> - tree val;
> + tree val, probability;
> enum tree_code cmp;
> edge_iterator ei;
> enum br_predictor predictor;
> @@ -2503,7 +2522,7 @@ tree_predict_by_opcode (basic_block bb)
> cmp = gimple_cond_code (stmt);
> type = TREE_TYPE (op0);
> val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
> - &predictor);
> + &predictor, &probability);
> if (val && TREE_CODE (val) == INTEGER_CST)
> {
> if (predictor == PRED_BUILTIN_EXPECT)
> @@ -2515,6 +2534,19 @@ tree_predict_by_opcode (basic_block bb)
> percent = 100 - percent;
> predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
> }
> + else if (predictor == PRED_BUILTIN_EXPECT_WITH_PROBABILITY)
> + {
> + if (!tree_fits_uhwi_p (probability))
> + return;
> +
> + unsigned percent = tree_to_uhwi (probability);
> + if (integer_zerop (val))
> + percent = 100 - percent;
> + if (percent > 100)
> + return;
> + predict_edge (then_edge, PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
> + HITRATE (percent));
> + }
> else
> predict_edge_def (then_edge, predictor,
> integer_zerop (val) ? NOT_TAKEN : TAKEN);
> @@ -3927,10 +3959,11 @@ pass_strip_predict_hints::execute (function *fun)
> {
> tree fndecl = gimple_call_fndecl (stmt);
>
> - if ((fndecl
> - && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
> - && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
> + if ((DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
> && gimple_call_num_args (stmt) == 2)
> + || (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
> + BUILT_IN_EXPECT_WITH_PROBABILITY)
> + && gimple_call_num_args (stmt) == 3)
> || (gimple_call_internal_p (stmt)
> && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
> {
> diff --git a/gcc/predict.def b/gcc/predict.def
> index 4ed97ed165c..b929d4c37db 100644
> --- a/gcc/predict.def
> +++ b/gcc/predict.def
> @@ -69,6 +69,11 @@ DEF_PREDICTOR (PRED_COMPARE_AND_SWAP, "compare and swap", PROB_VERY_LIKELY,
> DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY,
> PRED_FLAG_FIRST_MATCH)
>
> +/* Hints provided by user via __builtin_expect_with_probability. */
> +DEF_PREDICTOR (PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
> + "__builtin_expect_with_probability", PROB_UNINITIALIZED,
> + PRED_FLAG_FIRST_MATCH)
> +
> /* Use number of loop iterations guessed by the contents of the loop. */
> DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
> PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
> diff --git a/gcc/testsuite/gcc.dg/predict-16.c b/gcc/testsuite/gcc.dg/predict-16.c
> new file mode 100644
> index 00000000000..043f154f19f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/predict-16.c
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
> +
> +extern int global;
> +
> +void foo (int base)
> +{
> + if (__builtin_expect_with_probability (base == 100, 1, 99))
> + global++;
> +}
> +
> +/* { dg-final { scan-tree-dump "first match heuristics: 99.0%" "profile_estimate"} } */
> +/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 99.0%" "profile_estimate"} } */
> diff --git a/gcc/tree.h b/gcc/tree.h
> index 70ac78130c0..ae00e6e4035 100644
> --- a/gcc/tree.h
> +++ b/gcc/tree.h
> @@ -3008,6 +3008,12 @@ extern vec<tree, va_gc> **decl_debug_args_insert (tree);
> #define DECL_BUILT_IN_CLASS(NODE) \
> (FUNCTION_DECL_CHECK (NODE)->function_decl.built_in_class)
>
> +/* For a function declaration, return true if NODE is non-null and it is
> + a builtin of a CLASS with requested NAME. */
> +#define DECL_BUILT_IN_P(NODE, CLASS, NAME) \
> + (NODE != NULL_TREE && DECL_BUILT_IN_CLASS (NODE) == CLASS \
> + && DECL_FUNCTION_CODE (NODE) == NAME)
> +
> /* In FUNCTION_DECL, a chain of ..._DECL nodes. */
> #define DECL_ARGUMENTS(NODE) \
> (FUNCTION_DECL_CHECK (NODE)->function_decl.arguments)
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Introduce __builtin_expect_with_probability (PR target/83610).
2018-07-31 9:24 ` Jan Hubicka
@ 2018-08-01 12:21 ` Martin Liška
2018-08-07 12:23 ` Jan Hubicka
0 siblings, 1 reply; 6+ messages in thread
From: Martin Liška @ 2018-08-01 12:21 UTC (permalink / raw)
To: Jan Hubicka; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 23301 bytes --]
On 07/31/2018 11:24 AM, Jan Hubicka wrote:
>> Hi.
>>
>> This is implementation of new built-in that can be used for more fine
>> tweaking of probability. Micro benchmark is attached as part of the PR.
>>
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Ready to be installed?
>
> It reasonale to me to add the fature. Years ago I made similar patch and at
> that time it did not go in based on argumentation that programers are not good
> on guessing probabilities and this is too much of fine control while it should
> be done by profile feedback.
>
> However I guess it is better to have way to specify probability than tweak with
> --param that controls the builtin_expect outcome globally.
Agree with that, that's why I implemented that.
>
> What I think would be useful is to tie this to the code giving loop trip
> estimate. If you know that the loop iterates 100 times at the average, you
> can specify probability 1%. For this it seems to me more sensible to have
> the percentage parameter to be double rather than long so one can specify larger
> trip counts this way.
Makes fully sense, please take a look at attached updated patch.
Martin
>
> Honza
>
>
>> Martin
>>
>> gcc/ChangeLog:
>>
>> 2018-07-24 Martin Liska <mliska@suse.cz>
>>
>> PR target/83610
>> * builtin-types.def (BT_FN_LONG_LONG_LONG_LONG): New type.
>> * builtins.c (expand_builtin_expect_with_probability):
>> New function.
>> (expand_builtin): Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
>> (build_builtin_expect_predicate): Likewise.
>> (fold_builtin_expect): Likewise.
>> (fold_builtin_2): Likewise.
>> (fold_builtin_3): Likewise.
>> * builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY): Define new
>> builtin.
>> * builtins.h (fold_builtin_expect): Add new argument
>> (probability).
>> * doc/extend.texi: Document the new builtin.
>> * doc/invoke.texi: Likewise.
>> * gimple-fold.c (gimple_fold_call): Pass new argument.
>> * ipa-fnsummary.c (find_foldable_builtin_expect):
>> Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
>> * predict.c (expr_expected_value): Add new out argument which
>> is probability.
>> (expr_expected_value_1): Likewise.
>> (tree_predict_by_opcode): Predict edge based on
>> provided probability.
>> (pass_strip_predict_hints::execute): Use newly added
>> DECL_BUILT_IN_P macro.
>> * predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY):
>> Define new predictor.
>> * tree.h (DECL_BUILT_IN_P): Define.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2018-07-24 Martin Liska <mliska@suse.cz>
>>
>> * gcc.dg/predict-16.c: New test.
>> ---
>> gcc/builtin-types.def | 2 +
>> gcc/builtins.c | 65 ++++++++++++++++++++++++-------
>> gcc/builtins.def | 1 +
>> gcc/builtins.h | 2 +-
>> gcc/doc/extend.texi | 8 ++++
>> gcc/doc/invoke.texi | 3 ++
>> gcc/gimple-fold.c | 3 +-
>> gcc/ipa-fnsummary.c | 1 +
>> gcc/predict.c | 61 ++++++++++++++++++++++-------
>> gcc/predict.def | 5 +++
>> gcc/testsuite/gcc.dg/predict-16.c | 13 +++++++
>> gcc/tree.h | 6 +++
>> 12 files changed, 140 insertions(+), 30 deletions(-)
>> create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
>>
>>
>
>> diff --git a/gcc/builtin-types.def b/gcc/builtin-types.def
>> index b01095c420f..6e87bcbbf1d 100644
>> --- a/gcc/builtin-types.def
>> +++ b/gcc/builtin-types.def
>> @@ -531,6 +531,8 @@ DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_ULONG_ULONG,
>> BT_ULONG, BT_ULONG, BT_ULONG, BT_ULONG)
>> DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_UINT_UINT,
>> BT_LONG, BT_LONG, BT_UINT, BT_UINT)
>> +DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_LONG_LONG,
>> + BT_LONG, BT_LONG, BT_LONG, BT_LONG)
>> DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_UINT_UINT,
>> BT_ULONG, BT_ULONG, BT_UINT, BT_UINT)
>> DEF_FUNCTION_TYPE_3 (BT_FN_STRING_CONST_STRING_CONST_STRING_INT,
>> diff --git a/gcc/builtins.c b/gcc/builtins.c
>> index 539a6d17688..29d77d3d83b 100644
>> --- a/gcc/builtins.c
>> +++ b/gcc/builtins.c
>> @@ -148,6 +148,7 @@ static rtx expand_builtin_unop (machine_mode, tree, rtx, rtx, optab);
>> static rtx expand_builtin_frame_address (tree, tree);
>> static tree stabilize_va_list_loc (location_t, tree, int);
>> static rtx expand_builtin_expect (tree, rtx);
>> +static rtx expand_builtin_expect_with_probability (tree, rtx);
>> static tree fold_builtin_constant_p (tree);
>> static tree fold_builtin_classify_type (tree);
>> static tree fold_builtin_strlen (location_t, tree, tree);
>> @@ -5237,6 +5238,27 @@ expand_builtin_expect (tree exp, rtx target)
>> return target;
>> }
>>
>> +/* Expand a call to __builtin_expect_with_probability. We just return our
>> + argument as the builtin_expect semantic should've been already executed by
>> + tree branch prediction pass. */
>> +
>> +static rtx
>> +expand_builtin_expect_with_probability (tree exp, rtx target)
>> +{
>> + tree arg;
>> +
>> + if (call_expr_nargs (exp) < 3)
>> + return const0_rtx;
>> + arg = CALL_EXPR_ARG (exp, 0);
>> +
>> + target = expand_expr (arg, target, VOIDmode, EXPAND_NORMAL);
>> + /* When guessing was done, the hints should be already stripped away. */
>> + gcc_assert (!flag_guess_branch_prob
>> + || optimize == 0 || seen_error ());
>> + return target;
>> +}
>> +
>> +
>> /* Expand a call to __builtin_assume_aligned. We just return our first
>> argument as the builtin_assume_aligned semantic should've been already
>> executed by CCP. */
>> @@ -7494,6 +7516,8 @@ expand_builtin (tree exp, rtx target, rtx subtarget, machine_mode mode,
>> return expand_builtin_va_copy (exp);
>> case BUILT_IN_EXPECT:
>> return expand_builtin_expect (exp, target);
>> + case BUILT_IN_EXPECT_WITH_PROBABILITY:
>> + return expand_builtin_expect_with_probability (exp, target);
>> case BUILT_IN_ASSUME_ALIGNED:
>> return expand_builtin_assume_aligned (exp, target);
>> case BUILT_IN_PREFETCH:
>> @@ -8134,16 +8158,20 @@ fold_builtin_constant_p (tree arg)
>> return NULL_TREE;
>> }
>>
>> -/* Create builtin_expect with PRED and EXPECTED as its arguments and
>> - return it as a truthvalue. */
>> +/* Create builtin_expect or builtin_expect_with_probability
>> + with PRED and EXPECTED as its arguments and return it as a truthvalue.
>> + Fortran FE can also produce builtin_expect with PREDICTOR as third argument.
>> + builtin_expect_with_probability instead uses third argument as PROBABILITY
>> + value. */
>>
>> static tree
>> build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
>> - tree predictor)
>> + tree predictor, tree probability)
>> {
>> tree fn, arg_types, pred_type, expected_type, call_expr, ret_type;
>>
>> - fn = builtin_decl_explicit (BUILT_IN_EXPECT);
>> + fn = builtin_decl_explicit (probability == NULL_TREE ? BUILT_IN_EXPECT
>> + : BUILT_IN_EXPECT_WITH_PROBABILITY);
>> arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
>> ret_type = TREE_TYPE (TREE_TYPE (fn));
>> pred_type = TREE_VALUE (arg_types);
>> @@ -8151,18 +8179,23 @@ build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
>>
>> pred = fold_convert_loc (loc, pred_type, pred);
>> expected = fold_convert_loc (loc, expected_type, expected);
>> - call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
>> - predictor);
>> +
>> + if (probability)
>> + call_expr = build_call_expr_loc (loc, fn, 3, pred, expected, probability);
>> + else
>> + call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
>> + predictor);
>>
>> return build2 (NE_EXPR, TREE_TYPE (pred), call_expr,
>> build_int_cst (ret_type, 0));
>> }
>>
>> -/* Fold a call to builtin_expect with arguments ARG0 and ARG1. Return
>> +/* Fold a call to builtin_expect with arguments ARG0, ARG1, ARG2, ARG3. Return
>> NULL_TREE if no simplification is possible. */
>>
>> tree
>> -fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
>> +fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2,
>> + tree arg3)
>> {
>> tree inner, fndecl, inner_arg0;
>> enum tree_code code;
>> @@ -8186,8 +8219,9 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
>>
>> if (TREE_CODE (inner) == CALL_EXPR
>> && (fndecl = get_callee_fndecl (inner))
>> - && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
>> - && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT)
>> + && (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
>> + || DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
>> + BUILT_IN_EXPECT_WITH_PROBABILITY)))
>> return arg0;
>>
>> inner = inner_arg0;
>> @@ -8198,8 +8232,8 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
>> tree op1 = TREE_OPERAND (inner, 1);
>> arg1 = save_expr (arg1);
>>
>> - op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2);
>> - op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2);
>> + op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2, arg3);
>> + op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2, arg3);
>> inner = build2 (code, TREE_TYPE (inner), op0, op1);
>>
>> return fold_convert_loc (loc, TREE_TYPE (arg0), inner);
>> @@ -9295,7 +9329,7 @@ fold_builtin_2 (location_t loc, tree fndecl, tree arg0, tree arg1)
>> return fold_builtin_strpbrk (loc, arg0, arg1, type);
>>
>> case BUILT_IN_EXPECT:
>> - return fold_builtin_expect (loc, arg0, arg1, NULL_TREE);
>> + return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, NULL_TREE);
>>
>> case BUILT_IN_ISGREATER:
>> return fold_builtin_unordered_cmp (loc, fndecl,
>> @@ -9373,7 +9407,10 @@ fold_builtin_3 (location_t loc, tree fndecl,
>> return fold_builtin_memcmp (loc, arg0, arg1, arg2);
>>
>> case BUILT_IN_EXPECT:
>> - return fold_builtin_expect (loc, arg0, arg1, arg2);
>> + return fold_builtin_expect (loc, arg0, arg1, arg2, NULL_TREE);
>> +
>> + case BUILT_IN_EXPECT_WITH_PROBABILITY:
>> + return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, arg2);
>>
>> case BUILT_IN_ADD_OVERFLOW:
>> case BUILT_IN_SUB_OVERFLOW:
>> diff --git a/gcc/builtins.def b/gcc/builtins.def
>> index aacbd513a16..683a07e18fa 100644
>> --- a/gcc/builtins.def
>> +++ b/gcc/builtins.def
>> @@ -848,6 +848,7 @@ DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVP, "execvp", BT_FN_INT_CONST_STRING_PT
>> DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVE, "execve", BT_FN_INT_CONST_STRING_PTR_CONST_STRING_PTR_CONST_STRING, ATTR_NOTHROW_LIST)
>> DEF_LIB_BUILTIN (BUILT_IN_EXIT, "exit", BT_FN_VOID_INT, ATTR_NORETURN_NOTHROW_LIST)
>> DEF_GCC_BUILTIN (BUILT_IN_EXPECT, "expect", BT_FN_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
>> +DEF_GCC_BUILTIN (BUILT_IN_EXPECT_WITH_PROBABILITY, "expect_with_probability", BT_FN_LONG_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
>> DEF_GCC_BUILTIN (BUILT_IN_ASSUME_ALIGNED, "assume_aligned", BT_FN_PTR_CONST_PTR_SIZE_VAR, ATTR_CONST_NOTHROW_LEAF_LIST)
>> DEF_GCC_BUILTIN (BUILT_IN_EXTEND_POINTER, "extend_pointer", BT_FN_UNWINDWORD_PTR, ATTR_CONST_NOTHROW_LEAF_LIST)
>> DEF_GCC_BUILTIN (BUILT_IN_EXTRACT_RETURN_ADDR, "extract_return_addr", BT_FN_PTR_PTR, ATTR_LEAF_LIST)
>> diff --git a/gcc/builtins.h b/gcc/builtins.h
>> index c9229049e21..3662ebcd98f 100644
>> --- a/gcc/builtins.h
>> +++ b/gcc/builtins.h
>> @@ -76,7 +76,7 @@ extern void expand_ifn_atomic_compare_exchange (gcall *);
>> extern rtx expand_builtin (tree, rtx, rtx, machine_mode, int);
>> extern rtx expand_builtin_with_bounds (tree, rtx, rtx, machine_mode, int);
>> extern enum built_in_function builtin_mathfn_code (const_tree);
>> -extern tree fold_builtin_expect (location_t, tree, tree, tree);
>> +extern tree fold_builtin_expect (location_t, tree, tree, tree, tree);
>> extern bool avoid_folding_inline_builtin (tree);
>> extern tree fold_call_expr (location_t, tree, bool);
>> extern tree fold_builtin_call_array (location_t, tree, tree, int, tree *);
>> diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
>> index 7b471ec40f7..8567b24f873 100644
>> --- a/gcc/doc/extend.texi
>> +++ b/gcc/doc/extend.texi
>> @@ -11852,6 +11852,14 @@ if (__builtin_expect (ptr != NULL, 1))
>> when testing pointer or floating-point values.
>> @end deftypefn
>>
>> +@deftypefn {Built-in Function} long __builtin_expect_with_probability
>> +(long @var{exp}, long @var{c}, long @var{probability})
>> +
>> +The built-in has same semantics as @code{__builtin_expect_with_probability},
>> +but user can provide expected probability (in percent) for value of @var{exp}.
>> +Valid values of @var{probability} argument are in inclusive range 0 and 100.
>> +@end deftypefn
>> +
>> @deftypefn {Built-in Function} void __builtin_trap (void)
>> This function causes the program to exit abnormally. GCC implements
>> this function by using a target-dependent mechanism (such as
>> diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
>> index 1dcdfb51c47..edc46a3be95 100644
>> --- a/gcc/doc/invoke.texi
>> +++ b/gcc/doc/invoke.texi
>> @@ -9209,6 +9209,9 @@ between the heuristics and @code{__builtin_expect} can be complex, and in
>> some cases, it may be useful to disable the heuristics so that the effects
>> of @code{__builtin_expect} are easier to understand.
>>
>> +It is also possible to specify expected probability of the expression
>> +with @code{__builtin_expect_with_probability} built-in function.
>> +
>> The default is @option{-fguess-branch-probability} at levels
>> @option{-O}, @option{-O2}, @option{-O3}, @option{-Os}.
>>
>> diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
>> index 027ca4da97c..ea441797214 100644
>> --- a/gcc/gimple-fold.c
>> +++ b/gcc/gimple-fold.c
>> @@ -4166,7 +4166,8 @@ gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
>> result = fold_builtin_expect (gimple_location (stmt),
>> gimple_call_arg (stmt, 0),
>> gimple_call_arg (stmt, 1),
>> - gimple_call_arg (stmt, 2));
>> + gimple_call_arg (stmt, 2),
>> + NULL_TREE);
>> break;
>> case IFN_UBSAN_OBJECT_SIZE:
>> {
>> diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
>> index c99718a265f..a8fc2c2df9a 100644
>> --- a/gcc/ipa-fnsummary.c
>> +++ b/gcc/ipa-fnsummary.c
>> @@ -1851,6 +1851,7 @@ find_foldable_builtin_expect (basic_block bb)
>> {
>> gimple *stmt = gsi_stmt (bsi);
>> if (gimple_call_builtin_p (stmt, BUILT_IN_EXPECT)
>> + || gimple_call_builtin_p (stmt, BUILT_IN_EXPECT_WITH_PROBABILITY)
>> || gimple_call_internal_p (stmt, IFN_BUILTIN_EXPECT))
>> {
>> tree var = gimple_call_lhs (stmt);
>> diff --git a/gcc/predict.c b/gcc/predict.c
>> index 65e088fb8df..73e2a0fd2ed 100644
>> --- a/gcc/predict.c
>> +++ b/gcc/predict.c
>> @@ -2262,13 +2262,15 @@ guess_outgoing_edge_probabilities (basic_block bb)
>> combine_predictions_for_insn (BB_END (bb), bb);
>> }
>> \f
>> -static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
>> +static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
>> + tree *probability);
>>
>> /* Helper function for expr_expected_value. */
>>
>> static tree
>> expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>> - tree op1, bitmap visited, enum br_predictor *predictor)
>> + tree op1, bitmap visited, enum br_predictor *predictor,
>> + tree *probability)
>> {
>> gimple *def;
>>
>> @@ -2329,7 +2331,8 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>> if (arg == PHI_RESULT (def))
>> continue;
>>
>> - new_val = expr_expected_value (arg, visited, &predictor2);
>> + new_val = expr_expected_value (arg, visited, &predictor2,
>> + probability);
>>
>> /* It is difficult to combine value predictors. Simply assume
>> that later predictor is weaker and take its prediction. */
>> @@ -2353,7 +2356,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>> gimple_assign_rhs1 (def),
>> gimple_assign_rhs_code (def),
>> gimple_assign_rhs2 (def),
>> - visited, predictor);
>> + visited, predictor, NULL);
>> }
>>
>> if (is_gimple_call (def))
>> @@ -2395,6 +2398,21 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>> *predictor = PRED_BUILTIN_EXPECT;
>> return gimple_call_arg (def, 1);
>> }
>> + case BUILT_IN_EXPECT_WITH_PROBABILITY:
>> + {
>> + tree val;
>> + if (gimple_call_num_args (def) != 3)
>> + return NULL;
>> + val = gimple_call_arg (def, 0);
>> + if (TREE_CONSTANT (val))
>> + return val;
>> + if (predictor)
>> + {
>> + *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
>> + *probability = gimple_call_arg (def, 2);
>> + }
>> + return gimple_call_arg (def, 1);
>> + }
>>
>> case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
>> case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
>> @@ -2426,10 +2444,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>> {
>> tree res;
>> enum br_predictor predictor2;
>> - op0 = expr_expected_value (op0, visited, predictor);
>> + op0 = expr_expected_value (op0, visited, predictor, probability);
>> if (!op0)
>> return NULL;
>> - op1 = expr_expected_value (op1, visited, &predictor2);
>> + op1 = expr_expected_value (op1, visited, &predictor2, probability);
>> if (predictor && *predictor < predictor2)
>> *predictor = predictor2;
>> if (!op1)
>> @@ -2442,7 +2460,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>> if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
>> {
>> tree res;
>> - op0 = expr_expected_value (op0, visited, predictor);
>> + op0 = expr_expected_value (op0, visited, predictor, probability);
>> if (!op0)
>> return NULL;
>> res = fold_build1 (code, type, op0);
>> @@ -2463,7 +2481,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>>
>> static tree
>> expr_expected_value (tree expr, bitmap visited,
>> - enum br_predictor *predictor)
>> + enum br_predictor *predictor, tree *probability)
>> {
>> enum tree_code code;
>> tree op0, op1;
>> @@ -2477,7 +2495,8 @@ expr_expected_value (tree expr, bitmap visited,
>>
>> extract_ops_from_tree (expr, &code, &op0, &op1);
>> return expr_expected_value_1 (TREE_TYPE (expr),
>> - op0, code, op1, visited, predictor);
>> + op0, code, op1, visited, predictor,
>> + probability);
>> }
>> \f
>> /* Predict using opcode of the last statement in basic block. */
>> @@ -2488,7 +2507,7 @@ tree_predict_by_opcode (basic_block bb)
>> edge then_edge;
>> tree op0, op1;
>> tree type;
>> - tree val;
>> + tree val, probability;
>> enum tree_code cmp;
>> edge_iterator ei;
>> enum br_predictor predictor;
>> @@ -2503,7 +2522,7 @@ tree_predict_by_opcode (basic_block bb)
>> cmp = gimple_cond_code (stmt);
>> type = TREE_TYPE (op0);
>> val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
>> - &predictor);
>> + &predictor, &probability);
>> if (val && TREE_CODE (val) == INTEGER_CST)
>> {
>> if (predictor == PRED_BUILTIN_EXPECT)
>> @@ -2515,6 +2534,19 @@ tree_predict_by_opcode (basic_block bb)
>> percent = 100 - percent;
>> predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
>> }
>> + else if (predictor == PRED_BUILTIN_EXPECT_WITH_PROBABILITY)
>> + {
>> + if (!tree_fits_uhwi_p (probability))
>> + return;
>> +
>> + unsigned percent = tree_to_uhwi (probability);
>> + if (integer_zerop (val))
>> + percent = 100 - percent;
>> + if (percent > 100)
>> + return;
>> + predict_edge (then_edge, PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
>> + HITRATE (percent));
>> + }
>> else
>> predict_edge_def (then_edge, predictor,
>> integer_zerop (val) ? NOT_TAKEN : TAKEN);
>> @@ -3927,10 +3959,11 @@ pass_strip_predict_hints::execute (function *fun)
>> {
>> tree fndecl = gimple_call_fndecl (stmt);
>>
>> - if ((fndecl
>> - && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
>> - && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
>> + if ((DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
>> && gimple_call_num_args (stmt) == 2)
>> + || (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
>> + BUILT_IN_EXPECT_WITH_PROBABILITY)
>> + && gimple_call_num_args (stmt) == 3)
>> || (gimple_call_internal_p (stmt)
>> && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
>> {
>> diff --git a/gcc/predict.def b/gcc/predict.def
>> index 4ed97ed165c..b929d4c37db 100644
>> --- a/gcc/predict.def
>> +++ b/gcc/predict.def
>> @@ -69,6 +69,11 @@ DEF_PREDICTOR (PRED_COMPARE_AND_SWAP, "compare and swap", PROB_VERY_LIKELY,
>> DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY,
>> PRED_FLAG_FIRST_MATCH)
>>
>> +/* Hints provided by user via __builtin_expect_with_probability. */
>> +DEF_PREDICTOR (PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
>> + "__builtin_expect_with_probability", PROB_UNINITIALIZED,
>> + PRED_FLAG_FIRST_MATCH)
>> +
>> /* Use number of loop iterations guessed by the contents of the loop. */
>> DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
>> PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
>> diff --git a/gcc/testsuite/gcc.dg/predict-16.c b/gcc/testsuite/gcc.dg/predict-16.c
>> new file mode 100644
>> index 00000000000..043f154f19f
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/predict-16.c
>> @@ -0,0 +1,13 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
>> +
>> +extern int global;
>> +
>> +void foo (int base)
>> +{
>> + if (__builtin_expect_with_probability (base == 100, 1, 99))
>> + global++;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump "first match heuristics: 99.0%" "profile_estimate"} } */
>> +/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 99.0%" "profile_estimate"} } */
>> diff --git a/gcc/tree.h b/gcc/tree.h
>> index 70ac78130c0..ae00e6e4035 100644
>> --- a/gcc/tree.h
>> +++ b/gcc/tree.h
>> @@ -3008,6 +3008,12 @@ extern vec<tree, va_gc> **decl_debug_args_insert (tree);
>> #define DECL_BUILT_IN_CLASS(NODE) \
>> (FUNCTION_DECL_CHECK (NODE)->function_decl.built_in_class)
>>
>> +/* For a function declaration, return true if NODE is non-null and it is
>> + a builtin of a CLASS with requested NAME. */
>> +#define DECL_BUILT_IN_P(NODE, CLASS, NAME) \
>> + (NODE != NULL_TREE && DECL_BUILT_IN_CLASS (NODE) == CLASS \
>> + && DECL_FUNCTION_CODE (NODE) == NAME)
>> +
>> /* In FUNCTION_DECL, a chain of ..._DECL nodes. */
>> #define DECL_ARGUMENTS(NODE) \
>> (FUNCTION_DECL_CHECK (NODE)->function_decl.arguments)
>>
>
[-- Attachment #2: 0001-Introduce-__builtin_expect_with_probability-PR-targe.patch --]
[-- Type: text/x-patch, Size: 22003 bytes --]
From 6e59bf3acfa83dbde1af80678aa69a917cdbcecd Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Mon, 23 Jul 2018 16:03:19 +0200
Subject: [PATCH] Introduce __builtin_expect_with_probability (PR
target/83610).
gcc/ChangeLog:
2018-07-24 Martin Liska <mliska@suse.cz>
PR target/83610
* builtin-types.def (BT_FN_LONG_LONG_LONG_DOUBLE): New type.
* builtins.c (expand_builtin_expect_with_probability):
New function.
(expand_builtin): Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
(build_builtin_expect_predicate): Likewise.
(fold_builtin_expect): Likewise.
(fold_builtin_2): Likewise.
(fold_builtin_3): Likewise.
* builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY): Define new
builtin.
* builtins.h (fold_builtin_expect): Add new argument
(probability).
* doc/extend.texi: Document the new builtin.
* doc/invoke.texi: Likewise.
* gimple-fold.c (gimple_fold_call): Pass new argument.
* ipa-fnsummary.c (find_foldable_builtin_expect):
Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
* predict.c (expr_expected_value): Add new out argument which
is probability.
(expr_expected_value_1): Likewise.
(tree_predict_by_opcode): Predict edge based on
provided probability.
(pass_strip_predict_hints::execute): Use newly added
DECL_BUILT_IN_P macro.
* predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY):
Define new predictor.
* tree.h (DECL_BUILT_IN_P): Define.
gcc/testsuite/ChangeLog:
2018-07-24 Martin Liska <mliska@suse.cz>
* gcc.dg/predict-16.c: New test.
* gcc.dg/predict-17.c: New test.
---
gcc/builtin-types.def | 2 +
gcc/builtins.c | 65 ++++++++++++++++++++++-------
gcc/builtins.def | 1 +
gcc/builtins.h | 2 +-
gcc/doc/extend.texi | 9 ++++
gcc/doc/invoke.texi | 3 ++
gcc/gimple-fold.c | 3 +-
gcc/ipa-fnsummary.c | 1 +
gcc/predict.c | 68 ++++++++++++++++++++++++-------
gcc/predict.def | 5 +++
gcc/testsuite/gcc.dg/predict-16.c | 13 ++++++
gcc/testsuite/gcc.dg/predict-17.c | 13 ++++++
gcc/tree.h | 6 +++
13 files changed, 160 insertions(+), 31 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
create mode 100644 gcc/testsuite/gcc.dg/predict-17.c
diff --git a/gcc/builtin-types.def b/gcc/builtin-types.def
index 70fae35ce72..f13da6a188c 100644
--- a/gcc/builtin-types.def
+++ b/gcc/builtin-types.def
@@ -531,6 +531,8 @@ DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_ULONG_ULONG,
BT_ULONG, BT_ULONG, BT_ULONG, BT_ULONG)
DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_UINT_UINT,
BT_LONG, BT_LONG, BT_UINT, BT_UINT)
+DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_LONG_DOUBLE,
+ BT_LONG, BT_LONG, BT_LONG, BT_DOUBLE)
DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_UINT_UINT,
BT_ULONG, BT_ULONG, BT_UINT, BT_UINT)
DEF_FUNCTION_TYPE_3 (BT_FN_STRING_CONST_STRING_CONST_STRING_INT,
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 39611de7021..867d153d798 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -148,6 +148,7 @@ static rtx expand_builtin_unop (machine_mode, tree, rtx, rtx, optab);
static rtx expand_builtin_frame_address (tree, tree);
static tree stabilize_va_list_loc (location_t, tree, int);
static rtx expand_builtin_expect (tree, rtx);
+static rtx expand_builtin_expect_with_probability (tree, rtx);
static tree fold_builtin_constant_p (tree);
static tree fold_builtin_classify_type (tree);
static tree fold_builtin_strlen (location_t, tree, tree);
@@ -5251,6 +5252,27 @@ expand_builtin_expect (tree exp, rtx target)
return target;
}
+/* Expand a call to __builtin_expect_with_probability. We just return our
+ argument as the builtin_expect semantic should've been already executed by
+ tree branch prediction pass. */
+
+static rtx
+expand_builtin_expect_with_probability (tree exp, rtx target)
+{
+ tree arg;
+
+ if (call_expr_nargs (exp) < 3)
+ return const0_rtx;
+ arg = CALL_EXPR_ARG (exp, 0);
+
+ target = expand_expr (arg, target, VOIDmode, EXPAND_NORMAL);
+ /* When guessing was done, the hints should be already stripped away. */
+ gcc_assert (!flag_guess_branch_prob
+ || optimize == 0 || seen_error ());
+ return target;
+}
+
+
/* Expand a call to __builtin_assume_aligned. We just return our first
argument as the builtin_assume_aligned semantic should've been already
executed by CCP. */
@@ -7562,6 +7584,8 @@ expand_builtin (tree exp, rtx target, rtx subtarget, machine_mode mode,
return expand_builtin_va_copy (exp);
case BUILT_IN_EXPECT:
return expand_builtin_expect (exp, target);
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ return expand_builtin_expect_with_probability (exp, target);
case BUILT_IN_ASSUME_ALIGNED:
return expand_builtin_assume_aligned (exp, target);
case BUILT_IN_PREFETCH:
@@ -8213,16 +8237,20 @@ fold_builtin_constant_p (tree arg)
return NULL_TREE;
}
-/* Create builtin_expect with PRED and EXPECTED as its arguments and
- return it as a truthvalue. */
+/* Create builtin_expect or builtin_expect_with_probability
+ with PRED and EXPECTED as its arguments and return it as a truthvalue.
+ Fortran FE can also produce builtin_expect with PREDICTOR as third argument.
+ builtin_expect_with_probability instead uses third argument as PROBABILITY
+ value. */
static tree
build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
- tree predictor)
+ tree predictor, tree probability)
{
tree fn, arg_types, pred_type, expected_type, call_expr, ret_type;
- fn = builtin_decl_explicit (BUILT_IN_EXPECT);
+ fn = builtin_decl_explicit (probability == NULL_TREE ? BUILT_IN_EXPECT
+ : BUILT_IN_EXPECT_WITH_PROBABILITY);
arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
ret_type = TREE_TYPE (TREE_TYPE (fn));
pred_type = TREE_VALUE (arg_types);
@@ -8230,18 +8258,23 @@ build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
pred = fold_convert_loc (loc, pred_type, pred);
expected = fold_convert_loc (loc, expected_type, expected);
- call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
- predictor);
+
+ if (probability)
+ call_expr = build_call_expr_loc (loc, fn, 3, pred, expected, probability);
+ else
+ call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
+ predictor);
return build2 (NE_EXPR, TREE_TYPE (pred), call_expr,
build_int_cst (ret_type, 0));
}
-/* Fold a call to builtin_expect with arguments ARG0 and ARG1. Return
+/* Fold a call to builtin_expect with arguments ARG0, ARG1, ARG2, ARG3. Return
NULL_TREE if no simplification is possible. */
tree
-fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
+fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2,
+ tree arg3)
{
tree inner, fndecl, inner_arg0;
enum tree_code code;
@@ -8265,8 +8298,9 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
if (TREE_CODE (inner) == CALL_EXPR
&& (fndecl = get_callee_fndecl (inner))
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT)
+ && (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
+ || DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
+ BUILT_IN_EXPECT_WITH_PROBABILITY)))
return arg0;
inner = inner_arg0;
@@ -8277,8 +8311,8 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
tree op1 = TREE_OPERAND (inner, 1);
arg1 = save_expr (arg1);
- op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2);
- op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2);
+ op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2, arg3);
+ op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2, arg3);
inner = build2 (code, TREE_TYPE (inner), op0, op1);
return fold_convert_loc (loc, TREE_TYPE (arg0), inner);
@@ -9374,7 +9408,7 @@ fold_builtin_2 (location_t loc, tree fndecl, tree arg0, tree arg1)
return fold_builtin_strpbrk (loc, arg0, arg1, type);
case BUILT_IN_EXPECT:
- return fold_builtin_expect (loc, arg0, arg1, NULL_TREE);
+ return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, NULL_TREE);
case BUILT_IN_ISGREATER:
return fold_builtin_unordered_cmp (loc, fndecl,
@@ -9452,7 +9486,10 @@ fold_builtin_3 (location_t loc, tree fndecl,
return fold_builtin_memcmp (loc, arg0, arg1, arg2);
case BUILT_IN_EXPECT:
- return fold_builtin_expect (loc, arg0, arg1, arg2);
+ return fold_builtin_expect (loc, arg0, arg1, arg2, NULL_TREE);
+
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, arg2);
case BUILT_IN_ADD_OVERFLOW:
case BUILT_IN_SUB_OVERFLOW:
diff --git a/gcc/builtins.def b/gcc/builtins.def
index ad90d4458a1..ef89729fd0c 100644
--- a/gcc/builtins.def
+++ b/gcc/builtins.def
@@ -848,6 +848,7 @@ DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVP, "execvp", BT_FN_INT_CONST_STRING_PT
DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVE, "execve", BT_FN_INT_CONST_STRING_PTR_CONST_STRING_PTR_CONST_STRING, ATTR_NOTHROW_LIST)
DEF_LIB_BUILTIN (BUILT_IN_EXIT, "exit", BT_FN_VOID_INT, ATTR_NORETURN_NOTHROW_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXPECT, "expect", BT_FN_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_EXPECT_WITH_PROBABILITY, "expect_with_probability", BT_FN_LONG_LONG_LONG_DOUBLE, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_ASSUME_ALIGNED, "assume_aligned", BT_FN_PTR_CONST_PTR_SIZE_VAR, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXTEND_POINTER, "extend_pointer", BT_FN_UNWINDWORD_PTR, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXTRACT_RETURN_ADDR, "extract_return_addr", BT_FN_PTR_PTR, ATTR_LEAF_LIST)
diff --git a/gcc/builtins.h b/gcc/builtins.h
index 2e0a2f95379..1113bd37f1b 100644
--- a/gcc/builtins.h
+++ b/gcc/builtins.h
@@ -77,7 +77,7 @@ extern void expand_ifn_atomic_compare_exchange (gcall *);
extern rtx expand_builtin (tree, rtx, rtx, machine_mode, int);
extern rtx expand_builtin_with_bounds (tree, rtx, rtx, machine_mode, int);
extern enum built_in_function builtin_mathfn_code (const_tree);
-extern tree fold_builtin_expect (location_t, tree, tree, tree);
+extern tree fold_builtin_expect (location_t, tree, tree, tree, tree);
extern bool avoid_folding_inline_builtin (tree);
extern tree fold_call_expr (location_t, tree, bool);
extern tree fold_builtin_call_array (location_t, tree, tree, int, tree *);
diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
index bf465d7b93c..392cf0d5634 100644
--- a/gcc/doc/extend.texi
+++ b/gcc/doc/extend.texi
@@ -11954,6 +11954,15 @@ if (__builtin_expect (ptr != NULL, 1))
when testing pointer or floating-point values.
@end deftypefn
+@deftypefn {Built-in Function} long __builtin_expect_with_probability
+(long @var{exp}, long @var{c}, long @var{probability})
+
+The built-in has same semantics as @code{__builtin_expect_with_probability},
+but user can provide expected probability (in percent) for value of @var{exp}.
+Last argument @var{probability} is of flaot type and valid values
+are in inclusive range 0.0f and 1.0f.
+@end deftypefn
+
@deftypefn {Built-in Function} void __builtin_trap (void)
This function causes the program to exit abnormally. GCC implements
this function by using a target-dependent mechanism (such as
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 6047d82065a..bbc024ec1ea 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -9210,6 +9210,9 @@ between the heuristics and @code{__builtin_expect} can be complex, and in
some cases, it may be useful to disable the heuristics so that the effects
of @code{__builtin_expect} are easier to understand.
+It is also possible to specify expected probability of the expression
+with @code{__builtin_expect_with_probability} built-in function.
+
The default is @option{-fguess-branch-probability} at levels
@option{-O}, @option{-O2}, @option{-O3}, @option{-Os}.
diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index c3fa57064c2..0bdb559eadc 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -4156,7 +4156,8 @@ gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
result = fold_builtin_expect (gimple_location (stmt),
gimple_call_arg (stmt, 0),
gimple_call_arg (stmt, 1),
- gimple_call_arg (stmt, 2));
+ gimple_call_arg (stmt, 2),
+ NULL_TREE);
break;
case IFN_UBSAN_OBJECT_SIZE:
{
diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index c99718a265f..a8fc2c2df9a 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -1851,6 +1851,7 @@ find_foldable_builtin_expect (basic_block bb)
{
gimple *stmt = gsi_stmt (bsi);
if (gimple_call_builtin_p (stmt, BUILT_IN_EXPECT)
+ || gimple_call_builtin_p (stmt, BUILT_IN_EXPECT_WITH_PROBABILITY)
|| gimple_call_internal_p (stmt, IFN_BUILTIN_EXPECT))
{
tree var = gimple_call_lhs (stmt);
diff --git a/gcc/predict.c b/gcc/predict.c
index 65e088fb8df..779f656238f 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2262,13 +2262,15 @@ guess_outgoing_edge_probabilities (basic_block bb)
combine_predictions_for_insn (BB_END (bb), bb);
}
\f
-static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
+static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
+ tree *probability);
/* Helper function for expr_expected_value. */
static tree
expr_expected_value_1 (tree type, tree op0, enum tree_code code,
- tree op1, bitmap visited, enum br_predictor *predictor)
+ tree op1, bitmap visited, enum br_predictor *predictor,
+ tree *probability)
{
gimple *def;
@@ -2329,7 +2331,8 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
if (arg == PHI_RESULT (def))
continue;
- new_val = expr_expected_value (arg, visited, &predictor2);
+ new_val = expr_expected_value (arg, visited, &predictor2,
+ probability);
/* It is difficult to combine value predictors. Simply assume
that later predictor is weaker and take its prediction. */
@@ -2353,7 +2356,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
gimple_assign_rhs1 (def),
gimple_assign_rhs_code (def),
gimple_assign_rhs2 (def),
- visited, predictor);
+ visited, predictor, NULL);
}
if (is_gimple_call (def))
@@ -2395,6 +2398,21 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
*predictor = PRED_BUILTIN_EXPECT;
return gimple_call_arg (def, 1);
}
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ {
+ tree val;
+ if (gimple_call_num_args (def) != 3)
+ return NULL;
+ val = gimple_call_arg (def, 0);
+ if (TREE_CONSTANT (val))
+ return val;
+ if (predictor)
+ {
+ *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
+ *probability = gimple_call_arg (def, 2);
+ }
+ return gimple_call_arg (def, 1);
+ }
case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
@@ -2426,10 +2444,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
{
tree res;
enum br_predictor predictor2;
- op0 = expr_expected_value (op0, visited, predictor);
+ op0 = expr_expected_value (op0, visited, predictor, probability);
if (!op0)
return NULL;
- op1 = expr_expected_value (op1, visited, &predictor2);
+ op1 = expr_expected_value (op1, visited, &predictor2, probability);
if (predictor && *predictor < predictor2)
*predictor = predictor2;
if (!op1)
@@ -2442,7 +2460,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
{
tree res;
- op0 = expr_expected_value (op0, visited, predictor);
+ op0 = expr_expected_value (op0, visited, predictor, probability);
if (!op0)
return NULL;
res = fold_build1 (code, type, op0);
@@ -2463,7 +2481,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
static tree
expr_expected_value (tree expr, bitmap visited,
- enum br_predictor *predictor)
+ enum br_predictor *predictor, tree *probability)
{
enum tree_code code;
tree op0, op1;
@@ -2477,7 +2495,8 @@ expr_expected_value (tree expr, bitmap visited,
extract_ops_from_tree (expr, &code, &op0, &op1);
return expr_expected_value_1 (TREE_TYPE (expr),
- op0, code, op1, visited, predictor);
+ op0, code, op1, visited, predictor,
+ probability);
}
\f
/* Predict using opcode of the last statement in basic block. */
@@ -2488,7 +2507,7 @@ tree_predict_by_opcode (basic_block bb)
edge then_edge;
tree op0, op1;
tree type;
- tree val;
+ tree val, probability;
enum tree_code cmp;
edge_iterator ei;
enum br_predictor predictor;
@@ -2503,8 +2522,8 @@ tree_predict_by_opcode (basic_block bb)
cmp = gimple_cond_code (stmt);
type = TREE_TYPE (op0);
val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
- &predictor);
- if (val && TREE_CODE (val) == INTEGER_CST)
+ &predictor, &probability);
+ if (val && (TREE_CODE (val) == INTEGER_CST || TREE_CODE (val) == REAL_CST))
{
if (predictor == PRED_BUILTIN_EXPECT)
{
@@ -2515,6 +2534,24 @@ tree_predict_by_opcode (basic_block bb)
percent = 100 - percent;
predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
}
+ else if (predictor == PRED_BUILTIN_EXPECT_WITH_PROBABILITY)
+ {
+ if (TREE_CODE (probability) != REAL_CST)
+ return;
+
+ /* Compute final probability as probability * REG_BR_PROB_BASE. */
+ tree t = TREE_TYPE (probability);
+ tree base = build_int_cst (integer_type_node, REG_BR_PROB_BASE);
+ base = build_real_from_int_cst (t, base);
+ tree r = fold_build2 (MULT_EXPR, t, probability, base);
+ HOST_WIDE_INT prob = real_to_integer (TREE_REAL_CST_PTR (r));
+
+ if (integer_zerop (val))
+ prob = REG_BR_PROB_BASE - prob;
+ if (prob > REG_BR_PROB_BASE || prob < 0)
+ return;
+ predict_edge (then_edge, PRED_BUILTIN_EXPECT_WITH_PROBABILITY, prob);
+ }
else
predict_edge_def (then_edge, predictor,
integer_zerop (val) ? NOT_TAKEN : TAKEN);
@@ -3927,10 +3964,11 @@ pass_strip_predict_hints::execute (function *fun)
{
tree fndecl = gimple_call_fndecl (stmt);
- if ((fndecl
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
+ if ((DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
&& gimple_call_num_args (stmt) == 2)
+ || (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
+ BUILT_IN_EXPECT_WITH_PROBABILITY)
+ && gimple_call_num_args (stmt) == 3)
|| (gimple_call_internal_p (stmt)
&& gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
{
diff --git a/gcc/predict.def b/gcc/predict.def
index 4ed97ed165c..b929d4c37db 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -69,6 +69,11 @@ DEF_PREDICTOR (PRED_COMPARE_AND_SWAP, "compare and swap", PROB_VERY_LIKELY,
DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY,
PRED_FLAG_FIRST_MATCH)
+/* Hints provided by user via __builtin_expect_with_probability. */
+DEF_PREDICTOR (PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
+ "__builtin_expect_with_probability", PROB_UNINITIALIZED,
+ PRED_FLAG_FIRST_MATCH)
+
/* Use number of loop iterations guessed by the contents of the loop. */
DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
diff --git a/gcc/testsuite/gcc.dg/predict-16.c b/gcc/testsuite/gcc.dg/predict-16.c
new file mode 100644
index 00000000000..2682dba18d9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-16.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+void foo (int base)
+{
+ if (__builtin_expect_with_probability (base == 100, 1, 0.001f))
+ global++;
+}
+
+/* { dg-final { scan-tree-dump "first match heuristics: 0.1%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 0.1%" "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/predict-17.c b/gcc/testsuite/gcc.dg/predict-17.c
new file mode 100644
index 00000000000..78a868367d4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-17.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+void foo (int base)
+{
+ for (int i = 0; __builtin_expect_with_probability (i < base, 1, 0.05f); i++)
+ global++;
+}
+
+/* { dg-final { scan-tree-dump "first match heuristics: 5.0%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 5.0%" "profile_estimate"} } */
diff --git a/gcc/tree.h b/gcc/tree.h
index 7bed03553b2..648e9e2a3c4 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -3008,6 +3008,12 @@ extern vec<tree, va_gc> **decl_debug_args_insert (tree);
#define DECL_BUILT_IN_CLASS(NODE) \
(FUNCTION_DECL_CHECK (NODE)->function_decl.built_in_class)
+/* For a function declaration, return true if NODE is non-null and it is
+ a builtin of a CLASS with requested NAME. */
+#define DECL_BUILT_IN_P(NODE, CLASS, NAME) \
+ (NODE != NULL_TREE && DECL_BUILT_IN_CLASS (NODE) == CLASS \
+ && DECL_FUNCTION_CODE (NODE) == NAME)
+
/* In FUNCTION_DECL, a chain of ..._DECL nodes. */
#define DECL_ARGUMENTS(NODE) \
(FUNCTION_DECL_CHECK (NODE)->function_decl.arguments)
--
2.18.0
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Introduce __builtin_expect_with_probability (PR target/83610).
2018-08-01 12:21 ` Martin Liška
@ 2018-08-07 12:23 ` Jan Hubicka
2018-08-09 10:24 ` Martin Liška
0 siblings, 1 reply; 6+ messages in thread
From: Jan Hubicka @ 2018-08-07 12:23 UTC (permalink / raw)
To: Martin Liška; +Cc: gcc-patches
> 2018-07-24 Martin Liska <mliska@suse.cz>
>
> PR target/83610
> * builtin-types.def (BT_FN_LONG_LONG_LONG_DOUBLE): New type.
> * builtins.c (expand_builtin_expect_with_probability):
> New function.
> (expand_builtin): Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
> (build_builtin_expect_predicate): Likewise.
> (fold_builtin_expect): Likewise.
> (fold_builtin_2): Likewise.
> (fold_builtin_3): Likewise.
> * builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY): Define new
> builtin.
> * builtins.h (fold_builtin_expect): Add new argument
> (probability).
> * doc/extend.texi: Document the new builtin.
> * doc/invoke.texi: Likewise.
> * gimple-fold.c (gimple_fold_call): Pass new argument.
> * ipa-fnsummary.c (find_foldable_builtin_expect):
> Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
> * predict.c (expr_expected_value): Add new out argument which
> is probability.
> (expr_expected_value_1): Likewise.
> (tree_predict_by_opcode): Predict edge based on
> provided probability.
> (pass_strip_predict_hints::execute): Use newly added
> DECL_BUILT_IN_P macro.
> * predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY):
> Define new predictor.
> * tree.h (DECL_BUILT_IN_P): Define.
>
> gcc/testsuite/ChangeLog:
>
> 2018-07-24 Martin Liska <mliska@suse.cz>
>
> * gcc.dg/predict-16.c: New test.
> * gcc.dg/predict-17.c: New test.
OK
> +@deftypefn {Built-in Function} long __builtin_expect_with_probability
> +(long @var{exp}, long @var{c}, long @var{probability})
> +
> +The built-in has same semantics as @code{__builtin_expect_with_probability},
> +but user can provide expected probability (in percent) for value of @var{exp}.
> +Last argument @var{probability} is of flaot type and valid values
flaot->float :)
> @@ -2426,10 +2444,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
> {
> tree res;
> enum br_predictor predictor2;
> - op0 = expr_expected_value (op0, visited, predictor);
> + op0 = expr_expected_value (op0, visited, predictor, probability);
> if (!op0)
> return NULL;
> - op1 = expr_expected_value (op1, visited, &predictor2);
> + op1 = expr_expected_value (op1, visited, &predictor2, probability);
> if (predictor && *predictor < predictor2)
> *predictor = predictor2;
> if (!op1)
Here you need to combine probabilities together.
I would probably convert it early into profile_probability type (at the time
builtin is handled) because then combination is better defined.
If probability is known only over one path I guess you will need to turn
predictor into probability and then do the combination. The predictor combining
logic simply takes the weaker one (assumes that they are all first match), perhaps
with probability one can just combine probabilties and throw away predictor info
in this case.
It would be still very nice to arrange loop code to set loop->nb_iterations_estimate
accordingly in this case. That would be useful for loop opts as reliable hint that
number of iterations is about that much.
Honza
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Introduce __builtin_expect_with_probability (PR target/83610).
2018-08-07 12:23 ` Jan Hubicka
@ 2018-08-09 10:24 ` Martin Liška
2018-08-09 12:55 ` Jan Hubicka
0 siblings, 1 reply; 6+ messages in thread
From: Martin Liška @ 2018-08-09 10:24 UTC (permalink / raw)
To: Jan Hubicka; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 3337 bytes --]
On 08/07/2018 02:23 PM, Jan Hubicka wrote:
>> 2018-07-24 Martin Liska <mliska@suse.cz>
>>
>> PR target/83610
>> * builtin-types.def (BT_FN_LONG_LONG_LONG_DOUBLE): New type.
>> * builtins.c (expand_builtin_expect_with_probability):
>> New function.
>> (expand_builtin): Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
>> (build_builtin_expect_predicate): Likewise.
>> (fold_builtin_expect): Likewise.
>> (fold_builtin_2): Likewise.
>> (fold_builtin_3): Likewise.
>> * builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY): Define new
>> builtin.
>> * builtins.h (fold_builtin_expect): Add new argument
>> (probability).
>> * doc/extend.texi: Document the new builtin.
>> * doc/invoke.texi: Likewise.
>> * gimple-fold.c (gimple_fold_call): Pass new argument.
>> * ipa-fnsummary.c (find_foldable_builtin_expect):
>> Handle also BUILT_IN_EXPECT_WITH_PROBABILITY.
>> * predict.c (expr_expected_value): Add new out argument which
>> is probability.
>> (expr_expected_value_1): Likewise.
>> (tree_predict_by_opcode): Predict edge based on
>> provided probability.
>> (pass_strip_predict_hints::execute): Use newly added
>> DECL_BUILT_IN_P macro.
>> * predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY):
>> Define new predictor.
>> * tree.h (DECL_BUILT_IN_P): Define.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2018-07-24 Martin Liska <mliska@suse.cz>
>>
>> * gcc.dg/predict-16.c: New test.
>> * gcc.dg/predict-17.c: New test.
>
> OK
>> +@deftypefn {Built-in Function} long __builtin_expect_with_probability
>> +(long @var{exp}, long @var{c}, long @var{probability})
>> +
>> +The built-in has same semantics as @code{__builtin_expect_with_probability},
>> +but user can provide expected probability (in percent) for value of @var{exp}.
>> +Last argument @var{probability} is of flaot type and valid values
> flaot->float :)
Fixed.
>> @@ -2426,10 +2444,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
>> {
>> tree res;
>> enum br_predictor predictor2;
>> - op0 = expr_expected_value (op0, visited, predictor);
>> + op0 = expr_expected_value (op0, visited, predictor, probability);
>> if (!op0)
>> return NULL;
>> - op1 = expr_expected_value (op1, visited, &predictor2);
>> + op1 = expr_expected_value (op1, visited, &predictor2, probability);
>> if (predictor && *predictor < predictor2)
>> *predictor = predictor2;
>> if (!op1)
>
> Here you need to combine probabilities together.
>
> I would probably convert it early into profile_probability type (at the time
> builtin is handled) because then combination is better defined.
>
> If probability is known only over one path I guess you will need to turn
> predictor into probability and then do the combination. The predictor combining
> logic simply takes the weaker one (assumes that they are all first match), perhaps
> with probability one can just combine probabilties and throw away predictor info
> in this case.
Done that, I believe the code is now more readable.
Martin
>
> It would be still very nice to arrange loop code to set loop->nb_iterations_estimate
> accordingly in this case. That would be useful for loop opts as reliable hint that
> number of iterations is about that much.
>
> Honza
>
[-- Attachment #2: 0001-Introduce-__builtin_expect_with_probability-PR-targe.patch --]
[-- Type: text/x-patch, Size: 27777 bytes --]
From 5df1c861976479fcedee5d428f735645a1eee089 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Mon, 23 Jul 2018 16:03:19 +0200
Subject: [PATCH] Introduce __builtin_expect_with_probability (PR
target/83610).
gcc/ChangeLog:
2018-08-09 Martin Liska <mliska@suse.cz>
PR target/83610
* builtin-types.def (BT_FN_LONG_LONG_LONG_DOUBLE): Add new
function type.
* builtins.c (expand_builtin_expect_with_probability):
New function.
(expand_builtin_expect_with_probability): New function.
(build_builtin_expect_predicate): Add new argumnet probability
for BUILT_IN_EXPECT_WITH_PROBABILITY.
(fold_builtin_expect):
(fold_builtin_2):
(fold_builtin_3):
* builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY):
* builtins.h (fold_builtin_expect): Set new argument.
* doc/extend.texi: Document __builtin_expect_with_probability.
* doc/invoke.texi: Likewise.
* gimple-fold.c (gimple_fold_call): Pass new argument.
* ipa-fnsummary.c (find_foldable_builtin_expect): Handle
also BUILT_IN_EXPECT_WITH_PROBABILITY.
* predict.c (get_predictor_value): New function.
(expr_expected_value): Add new argument probability. Assume
that predictor and probability are always non-null.
(expr_expected_value_1): Likewise. For __builtin_expect and
__builtin_expect_with_probability set probability. Handle
combination in binary expressions.
(tree_predict_by_opcode): Simplify code by simply calling
get_predictor_value.
(pass_strip_predict_hints::execute): Add handling of
BUILT_IN_EXPECT_WITH_PROBABILITY.
* predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY): Add
new predictor.
* tree.h (DECL_BUILT_IN_P): New function.
gcc/testsuite/ChangeLog:
2018-08-09 Martin Liska <mliska@suse.cz>
PR target/83610
* gcc.dg/predict-17.c: New test.
* gcc.dg/predict-18.c: New test.
* gcc.dg/predict-19.c: New test.
---
gcc/builtin-types.def | 2 +
gcc/builtins.c | 65 ++++++++++---
gcc/builtins.def | 1 +
gcc/builtins.h | 2 +-
gcc/doc/extend.texi | 9 ++
gcc/doc/invoke.texi | 3 +
gcc/gimple-fold.c | 3 +-
gcc/ipa-fnsummary.c | 1 +
gcc/predict.c | 154 ++++++++++++++++++++----------
gcc/predict.def | 5 +
gcc/testsuite/gcc.dg/predict-17.c | 13 +++
gcc/testsuite/gcc.dg/predict-18.c | 31 ++++++
gcc/testsuite/gcc.dg/predict-19.c | 13 +++
gcc/tree.h | 6 ++
14 files changed, 244 insertions(+), 64 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/predict-17.c
create mode 100644 gcc/testsuite/gcc.dg/predict-18.c
create mode 100644 gcc/testsuite/gcc.dg/predict-19.c
diff --git a/gcc/builtin-types.def b/gcc/builtin-types.def
index 70fae35ce72..f13da6a188c 100644
--- a/gcc/builtin-types.def
+++ b/gcc/builtin-types.def
@@ -531,6 +531,8 @@ DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_ULONG_ULONG,
BT_ULONG, BT_ULONG, BT_ULONG, BT_ULONG)
DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_UINT_UINT,
BT_LONG, BT_LONG, BT_UINT, BT_UINT)
+DEF_FUNCTION_TYPE_3 (BT_FN_LONG_LONG_LONG_DOUBLE,
+ BT_LONG, BT_LONG, BT_LONG, BT_DOUBLE)
DEF_FUNCTION_TYPE_3 (BT_FN_ULONG_ULONG_UINT_UINT,
BT_ULONG, BT_ULONG, BT_UINT, BT_UINT)
DEF_FUNCTION_TYPE_3 (BT_FN_STRING_CONST_STRING_CONST_STRING_INT,
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 39611de7021..867d153d798 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -148,6 +148,7 @@ static rtx expand_builtin_unop (machine_mode, tree, rtx, rtx, optab);
static rtx expand_builtin_frame_address (tree, tree);
static tree stabilize_va_list_loc (location_t, tree, int);
static rtx expand_builtin_expect (tree, rtx);
+static rtx expand_builtin_expect_with_probability (tree, rtx);
static tree fold_builtin_constant_p (tree);
static tree fold_builtin_classify_type (tree);
static tree fold_builtin_strlen (location_t, tree, tree);
@@ -5251,6 +5252,27 @@ expand_builtin_expect (tree exp, rtx target)
return target;
}
+/* Expand a call to __builtin_expect_with_probability. We just return our
+ argument as the builtin_expect semantic should've been already executed by
+ tree branch prediction pass. */
+
+static rtx
+expand_builtin_expect_with_probability (tree exp, rtx target)
+{
+ tree arg;
+
+ if (call_expr_nargs (exp) < 3)
+ return const0_rtx;
+ arg = CALL_EXPR_ARG (exp, 0);
+
+ target = expand_expr (arg, target, VOIDmode, EXPAND_NORMAL);
+ /* When guessing was done, the hints should be already stripped away. */
+ gcc_assert (!flag_guess_branch_prob
+ || optimize == 0 || seen_error ());
+ return target;
+}
+
+
/* Expand a call to __builtin_assume_aligned. We just return our first
argument as the builtin_assume_aligned semantic should've been already
executed by CCP. */
@@ -7562,6 +7584,8 @@ expand_builtin (tree exp, rtx target, rtx subtarget, machine_mode mode,
return expand_builtin_va_copy (exp);
case BUILT_IN_EXPECT:
return expand_builtin_expect (exp, target);
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ return expand_builtin_expect_with_probability (exp, target);
case BUILT_IN_ASSUME_ALIGNED:
return expand_builtin_assume_aligned (exp, target);
case BUILT_IN_PREFETCH:
@@ -8213,16 +8237,20 @@ fold_builtin_constant_p (tree arg)
return NULL_TREE;
}
-/* Create builtin_expect with PRED and EXPECTED as its arguments and
- return it as a truthvalue. */
+/* Create builtin_expect or builtin_expect_with_probability
+ with PRED and EXPECTED as its arguments and return it as a truthvalue.
+ Fortran FE can also produce builtin_expect with PREDICTOR as third argument.
+ builtin_expect_with_probability instead uses third argument as PROBABILITY
+ value. */
static tree
build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
- tree predictor)
+ tree predictor, tree probability)
{
tree fn, arg_types, pred_type, expected_type, call_expr, ret_type;
- fn = builtin_decl_explicit (BUILT_IN_EXPECT);
+ fn = builtin_decl_explicit (probability == NULL_TREE ? BUILT_IN_EXPECT
+ : BUILT_IN_EXPECT_WITH_PROBABILITY);
arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
ret_type = TREE_TYPE (TREE_TYPE (fn));
pred_type = TREE_VALUE (arg_types);
@@ -8230,18 +8258,23 @@ build_builtin_expect_predicate (location_t loc, tree pred, tree expected,
pred = fold_convert_loc (loc, pred_type, pred);
expected = fold_convert_loc (loc, expected_type, expected);
- call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
- predictor);
+
+ if (probability)
+ call_expr = build_call_expr_loc (loc, fn, 3, pred, expected, probability);
+ else
+ call_expr = build_call_expr_loc (loc, fn, predictor ? 3 : 2, pred, expected,
+ predictor);
return build2 (NE_EXPR, TREE_TYPE (pred), call_expr,
build_int_cst (ret_type, 0));
}
-/* Fold a call to builtin_expect with arguments ARG0 and ARG1. Return
+/* Fold a call to builtin_expect with arguments ARG0, ARG1, ARG2, ARG3. Return
NULL_TREE if no simplification is possible. */
tree
-fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
+fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2,
+ tree arg3)
{
tree inner, fndecl, inner_arg0;
enum tree_code code;
@@ -8265,8 +8298,9 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
if (TREE_CODE (inner) == CALL_EXPR
&& (fndecl = get_callee_fndecl (inner))
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT)
+ && (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
+ || DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
+ BUILT_IN_EXPECT_WITH_PROBABILITY)))
return arg0;
inner = inner_arg0;
@@ -8277,8 +8311,8 @@ fold_builtin_expect (location_t loc, tree arg0, tree arg1, tree arg2)
tree op1 = TREE_OPERAND (inner, 1);
arg1 = save_expr (arg1);
- op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2);
- op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2);
+ op0 = build_builtin_expect_predicate (loc, op0, arg1, arg2, arg3);
+ op1 = build_builtin_expect_predicate (loc, op1, arg1, arg2, arg3);
inner = build2 (code, TREE_TYPE (inner), op0, op1);
return fold_convert_loc (loc, TREE_TYPE (arg0), inner);
@@ -9374,7 +9408,7 @@ fold_builtin_2 (location_t loc, tree fndecl, tree arg0, tree arg1)
return fold_builtin_strpbrk (loc, arg0, arg1, type);
case BUILT_IN_EXPECT:
- return fold_builtin_expect (loc, arg0, arg1, NULL_TREE);
+ return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, NULL_TREE);
case BUILT_IN_ISGREATER:
return fold_builtin_unordered_cmp (loc, fndecl,
@@ -9452,7 +9486,10 @@ fold_builtin_3 (location_t loc, tree fndecl,
return fold_builtin_memcmp (loc, arg0, arg1, arg2);
case BUILT_IN_EXPECT:
- return fold_builtin_expect (loc, arg0, arg1, arg2);
+ return fold_builtin_expect (loc, arg0, arg1, arg2, NULL_TREE);
+
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ return fold_builtin_expect (loc, arg0, arg1, NULL_TREE, arg2);
case BUILT_IN_ADD_OVERFLOW:
case BUILT_IN_SUB_OVERFLOW:
diff --git a/gcc/builtins.def b/gcc/builtins.def
index ad90d4458a1..ef89729fd0c 100644
--- a/gcc/builtins.def
+++ b/gcc/builtins.def
@@ -848,6 +848,7 @@ DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVP, "execvp", BT_FN_INT_CONST_STRING_PT
DEF_EXT_LIB_BUILTIN (BUILT_IN_EXECVE, "execve", BT_FN_INT_CONST_STRING_PTR_CONST_STRING_PTR_CONST_STRING, ATTR_NOTHROW_LIST)
DEF_LIB_BUILTIN (BUILT_IN_EXIT, "exit", BT_FN_VOID_INT, ATTR_NORETURN_NOTHROW_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXPECT, "expect", BT_FN_LONG_LONG_LONG, ATTR_CONST_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_EXPECT_WITH_PROBABILITY, "expect_with_probability", BT_FN_LONG_LONG_LONG_DOUBLE, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_ASSUME_ALIGNED, "assume_aligned", BT_FN_PTR_CONST_PTR_SIZE_VAR, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXTEND_POINTER, "extend_pointer", BT_FN_UNWINDWORD_PTR, ATTR_CONST_NOTHROW_LEAF_LIST)
DEF_GCC_BUILTIN (BUILT_IN_EXTRACT_RETURN_ADDR, "extract_return_addr", BT_FN_PTR_PTR, ATTR_LEAF_LIST)
diff --git a/gcc/builtins.h b/gcc/builtins.h
index 2e0a2f95379..1113bd37f1b 100644
--- a/gcc/builtins.h
+++ b/gcc/builtins.h
@@ -77,7 +77,7 @@ extern void expand_ifn_atomic_compare_exchange (gcall *);
extern rtx expand_builtin (tree, rtx, rtx, machine_mode, int);
extern rtx expand_builtin_with_bounds (tree, rtx, rtx, machine_mode, int);
extern enum built_in_function builtin_mathfn_code (const_tree);
-extern tree fold_builtin_expect (location_t, tree, tree, tree);
+extern tree fold_builtin_expect (location_t, tree, tree, tree, tree);
extern bool avoid_folding_inline_builtin (tree);
extern tree fold_call_expr (location_t, tree, bool);
extern tree fold_builtin_call_array (location_t, tree, tree, int, tree *);
diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
index 183ff1c6348..37911c19aba 100644
--- a/gcc/doc/extend.texi
+++ b/gcc/doc/extend.texi
@@ -11956,6 +11956,15 @@ if (__builtin_expect (ptr != NULL, 1))
when testing pointer or floating-point values.
@end deftypefn
+@deftypefn {Built-in Function} long __builtin_expect_with_probability
+(long @var{exp}, long @var{c}, long @var{probability})
+
+The built-in has same semantics as @code{__builtin_expect_with_probability},
+but user can provide expected probability (in percent) for value of @var{exp}.
+Last argument @var{probability} is of float type and valid values
+are in inclusive range 0.0f and 1.0f.
+@end deftypefn
+
@deftypefn {Built-in Function} void __builtin_trap (void)
This function causes the program to exit abnormally. GCC implements
this function by using a target-dependent mechanism (such as
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 438274e67f8..7c4b54ff4d0 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -9210,6 +9210,9 @@ between the heuristics and @code{__builtin_expect} can be complex, and in
some cases, it may be useful to disable the heuristics so that the effects
of @code{__builtin_expect} are easier to understand.
+It is also possible to specify expected probability of the expression
+with @code{__builtin_expect_with_probability} built-in function.
+
The default is @option{-fguess-branch-probability} at levels
@option{-O}, @option{-O2}, @option{-O3}, @option{-Os}.
diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index 506a296732c..42673b5e6c9 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -4155,7 +4155,8 @@ gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
result = fold_builtin_expect (gimple_location (stmt),
gimple_call_arg (stmt, 0),
gimple_call_arg (stmt, 1),
- gimple_call_arg (stmt, 2));
+ gimple_call_arg (stmt, 2),
+ NULL_TREE);
break;
case IFN_UBSAN_OBJECT_SIZE:
{
diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index c99718a265f..a8fc2c2df9a 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -1851,6 +1851,7 @@ find_foldable_builtin_expect (basic_block bb)
{
gimple *stmt = gsi_stmt (bsi);
if (gimple_call_builtin_p (stmt, BUILT_IN_EXPECT)
+ || gimple_call_builtin_p (stmt, BUILT_IN_EXPECT_WITH_PROBABILITY)
|| gimple_call_internal_p (stmt, IFN_BUILTIN_EXPECT))
{
tree var = gimple_call_lhs (stmt);
diff --git a/gcc/predict.c b/gcc/predict.c
index 96ae10f1319..9ffeb62e85f 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -92,6 +92,7 @@ static void predict_paths_leading_to_edge (edge, enum br_predictor,
enum prediction,
struct loop *in_loop = NULL);
static bool can_predict_insn_p (const rtx_insn *);
+static HOST_WIDE_INT get_predictor_value (br_predictor, HOST_WIDE_INT);
/* Information we hold about each branch predictor.
Filled using information from predict.def. */
@@ -2262,18 +2263,21 @@ guess_outgoing_edge_probabilities (basic_block bb)
combine_predictions_for_insn (BB_END (bb), bb);
}
\f
-static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
+static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
+ HOST_WIDE_INT *probability);
/* Helper function for expr_expected_value. */
static tree
expr_expected_value_1 (tree type, tree op0, enum tree_code code,
- tree op1, bitmap visited, enum br_predictor *predictor)
+ tree op1, bitmap visited, enum br_predictor *predictor,
+ HOST_WIDE_INT *probability)
{
gimple *def;
- if (predictor)
- *predictor = PRED_UNCONDITIONAL;
+ /* Reset returned probability value. */
+ *probability = -1;
+ *predictor = PRED_UNCONDITIONAL;
if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
{
@@ -2292,8 +2296,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
{
/* Assume that any given atomic operation has low contention,
and thus the compare-and-swap operation succeeds. */
- if (predictor)
- *predictor = PRED_COMPARE_AND_SWAP;
+ *predictor = PRED_COMPARE_AND_SWAP;
return build_one_cst (TREE_TYPE (op0));
}
}
@@ -2329,11 +2332,12 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
if (arg == PHI_RESULT (def))
continue;
- new_val = expr_expected_value (arg, visited, &predictor2);
+ new_val = expr_expected_value (arg, visited, &predictor2,
+ probability);
/* It is difficult to combine value predictors. Simply assume
that later predictor is weaker and take its prediction. */
- if (predictor && *predictor < predictor2)
+ if (*predictor < predictor2)
*predictor = predictor2;
if (!new_val)
return NULL;
@@ -2353,7 +2357,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
gimple_assign_rhs1 (def),
gimple_assign_rhs_code (def),
gimple_assign_rhs2 (def),
- visited, predictor);
+ visited, predictor, probability);
}
if (is_gimple_call (def))
@@ -2368,14 +2372,14 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
tree val = gimple_call_arg (def, 0);
if (TREE_CONSTANT (val))
return val;
- if (predictor)
- {
- tree val2 = gimple_call_arg (def, 2);
- gcc_assert (TREE_CODE (val2) == INTEGER_CST
- && tree_fits_uhwi_p (val2)
- && tree_to_uhwi (val2) < END_PREDICTORS);
- *predictor = (enum br_predictor) tree_to_uhwi (val2);
- }
+ tree val2 = gimple_call_arg (def, 2);
+ gcc_assert (TREE_CODE (val2) == INTEGER_CST
+ && tree_fits_uhwi_p (val2)
+ && tree_to_uhwi (val2) < END_PREDICTORS);
+ *predictor = (enum br_predictor) tree_to_uhwi (val2);
+ if (*predictor == PRED_BUILTIN_EXPECT)
+ *probability
+ = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY));
return gimple_call_arg (def, 1);
}
return NULL;
@@ -2399,8 +2403,34 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
val = gimple_call_arg (def, 0);
if (TREE_CONSTANT (val))
return val;
- if (predictor)
- *predictor = PRED_BUILTIN_EXPECT;
+ *predictor = PRED_BUILTIN_EXPECT;
+ *probability
+ = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY));
+ return gimple_call_arg (def, 1);
+ }
+ case BUILT_IN_EXPECT_WITH_PROBABILITY:
+ {
+ tree val;
+ if (gimple_call_num_args (def) != 3)
+ return NULL;
+ val = gimple_call_arg (def, 0);
+ if (TREE_CONSTANT (val))
+ return val;
+ /* Compute final probability as:
+ probability * REG_BR_PROB_BASE. */
+ tree prob = gimple_call_arg (def, 2);
+ tree t = TREE_TYPE (prob);
+ tree base = build_int_cst (integer_type_node,
+ REG_BR_PROB_BASE);
+ base = build_real_from_int_cst (t, base);
+ tree r = fold_build2 (MULT_EXPR, t, prob, base);
+ HOST_WIDE_INT probi
+ = real_to_integer (TREE_REAL_CST_PTR (r));
+ if (probi >= 0 && probi <= REG_BR_PROB_BASE)
+ {
+ *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
+ *probability = probi;
+ }
return gimple_call_arg (def, 1);
}
@@ -2419,8 +2449,7 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
/* Assume that any given atomic operation has low contention,
and thus the compare-and-swap operation succeeds. */
- if (predictor)
- *predictor = PRED_COMPARE_AND_SWAP;
+ *predictor = PRED_COMPARE_AND_SWAP;
return boolean_true_node;
case BUILT_IN_REALLOC:
if (predictor)
@@ -2438,23 +2467,37 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
{
tree res;
enum br_predictor predictor2;
- op0 = expr_expected_value (op0, visited, predictor);
+ HOST_WIDE_INT probability2;
+ op0 = expr_expected_value (op0, visited, predictor, probability);
if (!op0)
return NULL;
- op1 = expr_expected_value (op1, visited, &predictor2);
- if (predictor && *predictor < predictor2)
- *predictor = predictor2;
+ op1 = expr_expected_value (op1, visited, &predictor2, &probability2);
if (!op1)
return NULL;
res = fold_build2 (code, type, op0, op1);
- if (TREE_CONSTANT (res))
- return res;
+ if (TREE_CODE (res) == INTEGER_CST
+ && TREE_CODE (op0) == INTEGER_CST
+ && TREE_CODE (op1) == INTEGER_CST)
+ {
+ /* Combine binary predictions. */
+ if (*probability != -1 || probability2 != -1)
+ {
+ HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
+ HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
+ *probability = p1 * p2 / REG_BR_PROB_BASE;
+ }
+
+ if (*predictor < predictor2)
+ *predictor = predictor2;
+
+ return res;
+ }
return NULL;
}
if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
{
tree res;
- op0 = expr_expected_value (op0, visited, predictor);
+ op0 = expr_expected_value (op0, visited, predictor, probability);
if (!op0)
return NULL;
res = fold_build1 (code, type, op0);
@@ -2475,23 +2518,44 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
static tree
expr_expected_value (tree expr, bitmap visited,
- enum br_predictor *predictor)
+ enum br_predictor *predictor,
+ HOST_WIDE_INT *probability)
{
enum tree_code code;
tree op0, op1;
if (TREE_CONSTANT (expr))
{
- if (predictor)
- *predictor = PRED_UNCONDITIONAL;
+ *predictor = PRED_UNCONDITIONAL;
+ *probability = -1;
return expr;
}
extract_ops_from_tree (expr, &code, &op0, &op1);
return expr_expected_value_1 (TREE_TYPE (expr),
- op0, code, op1, visited, predictor);
+ op0, code, op1, visited, predictor,
+ probability);
}
\f
+
+/* Return probability of a PREDICTOR. If the predictor has variable
+ probability return passed PROBABILITY. */
+
+static HOST_WIDE_INT
+get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
+{
+ switch (predictor)
+ {
+ case PRED_BUILTIN_EXPECT:
+ case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
+ gcc_assert (probability != -1);
+ return probability;
+ default:
+ gcc_assert (probability == -1);
+ return predictor_info[(int) predictor].hitrate;
+ }
+}
+
/* Predict using opcode of the last statement in basic block. */
static void
tree_predict_by_opcode (basic_block bb)
@@ -2504,6 +2568,7 @@ tree_predict_by_opcode (basic_block bb)
enum tree_code cmp;
edge_iterator ei;
enum br_predictor predictor;
+ HOST_WIDE_INT probability;
if (!stmt || gimple_code (stmt) != GIMPLE_COND)
return;
@@ -2515,21 +2580,13 @@ tree_predict_by_opcode (basic_block bb)
cmp = gimple_cond_code (stmt);
type = TREE_TYPE (op0);
val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
- &predictor);
+ &predictor, &probability);
if (val && TREE_CODE (val) == INTEGER_CST)
{
- if (predictor == PRED_BUILTIN_EXPECT)
- {
- int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
-
- gcc_assert (percent >= 0 && percent <= 100);
- if (integer_zerop (val))
- percent = 100 - percent;
- predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
- }
- else
- predict_edge_def (then_edge, predictor,
- integer_zerop (val) ? NOT_TAKEN : TAKEN);
+ HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
+ if (integer_zerop (val))
+ prob = REG_BR_PROB_BASE - prob;
+ predict_edge (then_edge, predictor, prob);
}
/* Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
@@ -3939,10 +3996,11 @@ pass_strip_predict_hints::execute (function *fun)
{
tree fndecl = gimple_call_fndecl (stmt);
- if ((fndecl
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
+ if ((DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
&& gimple_call_num_args (stmt) == 2)
+ || (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
+ BUILT_IN_EXPECT_WITH_PROBABILITY)
+ && gimple_call_num_args (stmt) == 3)
|| (gimple_call_internal_p (stmt)
&& gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
{
diff --git a/gcc/predict.def b/gcc/predict.def
index 76e6590cc96..01aa81b5ed7 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -73,6 +73,11 @@ DEF_PREDICTOR (PRED_COMPARE_AND_SWAP, "compare and swap", PROB_VERY_LIKELY,
DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY,
PRED_FLAG_FIRST_MATCH)
+/* Hints provided by user via __builtin_expect_with_probability. */
+DEF_PREDICTOR (PRED_BUILTIN_EXPECT_WITH_PROBABILITY,
+ "__builtin_expect_with_probability", PROB_UNINITIALIZED,
+ PRED_FLAG_FIRST_MATCH)
+
/* Use number of loop iterations guessed by the contents of the loop. */
DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
PROB_UNINITIALIZED, PRED_FLAG_FIRST_MATCH)
diff --git a/gcc/testsuite/gcc.dg/predict-17.c b/gcc/testsuite/gcc.dg/predict-17.c
new file mode 100644
index 00000000000..5069aa47c8c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-17.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+void foo (int base)
+{
+ for (int i = 0; __builtin_expect_with_probability (i < base, 1, 0.05f); i++)
+ global++;
+}
+
+/* { dg-final { scan-tree-dump "first match heuristics: 5.00%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 5.00%" "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/predict-18.c b/gcc/testsuite/gcc.dg/predict-18.c
new file mode 100644
index 00000000000..0c93638a971
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-18.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int x;
+
+short v = 0;
+short expected = 0;
+short max = ~0;
+#define STRONG 0
+
+void foo (int a, int b)
+{
+ if (__builtin_expect_with_probability (a < b, 1, 0.6f) > __builtin_expect (b, 0))
+ global++;
+
+ if (__builtin_expect_with_probability (a < b, 1, 0.777f) > 0)
+ global++;
+
+ if (__builtin_expect_with_probability (a < b, 1, 0.99) == __atomic_compare_exchange_n (&v, &expected, max, STRONG , __ATOMIC_RELAXED, __ATOMIC_RELAXED))
+ global++;
+
+ if (__builtin_expect_with_probability (a < 10, 1, 0.9f) > __builtin_expect_with_probability (b, 0, 0.8f))
+ global++;
+}
+
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 54.00%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 77.70%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 98.96%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 71.99%" "profile_estimate"} } */
diff --git a/gcc/testsuite/gcc.dg/predict-19.c b/gcc/testsuite/gcc.dg/predict-19.c
new file mode 100644
index 00000000000..38ca25a1603
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-19.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+void foo (int base)
+{
+ if (__builtin_expect_with_probability (base == 100, 1, 0.001f))
+ global++;
+}
+
+/* { dg-final { scan-tree-dump "first match heuristics: 0.10%" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "__builtin_expect_with_probability heuristics of edge .*->.*: 0.10%" "profile_estimate"} } */
diff --git a/gcc/tree.h b/gcc/tree.h
index 7bed03553b2..648e9e2a3c4 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -3008,6 +3008,12 @@ extern vec<tree, va_gc> **decl_debug_args_insert (tree);
#define DECL_BUILT_IN_CLASS(NODE) \
(FUNCTION_DECL_CHECK (NODE)->function_decl.built_in_class)
+/* For a function declaration, return true if NODE is non-null and it is
+ a builtin of a CLASS with requested NAME. */
+#define DECL_BUILT_IN_P(NODE, CLASS, NAME) \
+ (NODE != NULL_TREE && DECL_BUILT_IN_CLASS (NODE) == CLASS \
+ && DECL_FUNCTION_CODE (NODE) == NAME)
+
/* In FUNCTION_DECL, a chain of ..._DECL nodes. */
#define DECL_ARGUMENTS(NODE) \
(FUNCTION_DECL_CHECK (NODE)->function_decl.arguments)
--
2.18.0
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Introduce __builtin_expect_with_probability (PR target/83610).
2018-08-09 10:24 ` Martin Liška
@ 2018-08-09 12:55 ` Jan Hubicka
0 siblings, 0 replies; 6+ messages in thread
From: Jan Hubicka @ 2018-08-09 12:55 UTC (permalink / raw)
To: Martin Liška; +Cc: gcc-patches
> gcc/ChangeLog:
>
> 2018-08-09 Martin Liska <mliska@suse.cz>
>
> PR target/83610
> * builtin-types.def (BT_FN_LONG_LONG_LONG_DOUBLE): Add new
> function type.
> * builtins.c (expand_builtin_expect_with_probability):
> New function.
> (expand_builtin_expect_with_probability): New function.
> (build_builtin_expect_predicate): Add new argumnet probability
> for BUILT_IN_EXPECT_WITH_PROBABILITY.
> (fold_builtin_expect):
> (fold_builtin_2):
> (fold_builtin_3):
> * builtins.def (BUILT_IN_EXPECT_WITH_PROBABILITY):
> * builtins.h (fold_builtin_expect): Set new argument.
> * doc/extend.texi: Document __builtin_expect_with_probability.
> * doc/invoke.texi: Likewise.
> * gimple-fold.c (gimple_fold_call): Pass new argument.
> * ipa-fnsummary.c (find_foldable_builtin_expect): Handle
> also BUILT_IN_EXPECT_WITH_PROBABILITY.
> * predict.c (get_predictor_value): New function.
> (expr_expected_value): Add new argument probability. Assume
> that predictor and probability are always non-null.
> (expr_expected_value_1): Likewise. For __builtin_expect and
> __builtin_expect_with_probability set probability. Handle
> combination in binary expressions.
> (tree_predict_by_opcode): Simplify code by simply calling
> get_predictor_value.
> (pass_strip_predict_hints::execute): Add handling of
> BUILT_IN_EXPECT_WITH_PROBABILITY.
> * predict.def (PRED_BUILTIN_EXPECT_WITH_PROBABILITY): Add
> new predictor.
> * tree.h (DECL_BUILT_IN_P): New function.
>
> gcc/testsuite/ChangeLog:
>
> 2018-08-09 Martin Liska <mliska@suse.cz>
>
> PR target/83610
> * gcc.dg/predict-17.c: New test.
> * gcc.dg/predict-18.c: New test.
> * gcc.dg/predict-19.c: New test.
> ---
> gcc/builtin-types.def | 2 +
> gcc/builtins.c | 65 ++++++++++---
> gcc/builtins.def | 1 +
> gcc/builtins.h | 2 +-
> gcc/doc/extend.texi | 9 ++
> gcc/doc/invoke.texi | 3 +
> gcc/gimple-fold.c | 3 +-
> gcc/ipa-fnsummary.c | 1 +
> gcc/predict.c | 154 ++++++++++++++++++++----------
> gcc/predict.def | 5 +
> gcc/testsuite/gcc.dg/predict-17.c | 13 +++
> gcc/testsuite/gcc.dg/predict-18.c | 31 ++++++
> gcc/testsuite/gcc.dg/predict-19.c | 13 +++
> gcc/tree.h | 6 ++
> 14 files changed, 244 insertions(+), 64 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/predict-17.c
> create mode 100644 gcc/testsuite/gcc.dg/predict-18.c
> create mode 100644 gcc/testsuite/gcc.dg/predict-19.c
>
> + if (TREE_CODE (res) == INTEGER_CST
> + && TREE_CODE (op0) == INTEGER_CST
> + && TREE_CODE (op1) == INTEGER_CST)
> + {
> + /* Combine binary predictions. */
> + if (*probability != -1 || probability2 != -1)
> + {
> + HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
> + HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
> + *probability = p1 * p2 / REG_BR_PROB_BASE;
I guess you want to use RDIV here. Eventually we want to move to profile_probability type
everywhere but I guess that can be done later.
OK,
thanks!
Honza
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2018-08-09 12:55 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-07-24 7:22 [PATCH] Introduce __builtin_expect_with_probability (PR target/83610) Martin Liška
2018-07-31 9:24 ` Jan Hubicka
2018-08-01 12:21 ` Martin Liška
2018-08-07 12:23 ` Jan Hubicka
2018-08-09 10:24 ` Martin Liška
2018-08-09 12:55 ` Jan Hubicka
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).