On 08/07/2018 02:23 PM, Jan Hubicka wrote:
>> 2018-07-24 Martin Liska <mli...@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 <mli...@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
>
>From 5df1c861976479fcedee5d428f735645a1eee089 Mon Sep 17 00:00:00 2001
From: marxin <mli...@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 <mli...@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 <mli...@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);
}
-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);
}
+
+/* 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
