From 01107f42aa24fd5d725ea5f5fd97c75b2d18fa38 Mon Sep 17 00:00:00 2001 From: marxin Date: Fri, 10 Aug 2018 09:43:06 +0000 Subject: [PATCH] Introduce __builtin_expect_with_probability (PR target/83610). 2018-08-10 Martin Liska 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. 2018-08-10 Martin Liska PR target/83610 * gcc.dg/predict-17.c: New test. * gcc.dg/predict-18.c: New test. * gcc.dg/predict-19.c: New test. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@263466 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 34 ++++++++ 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 | 162 ++++++++++++++++++++++++++------------ gcc/predict.def | 5 ++ gcc/testsuite/ChangeLog | 7 ++ 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 ++ 16 files changed, 289 insertions(+), 68 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/ChangeLog b/gcc/ChangeLog index 5edaf2414b6..28e44cf455d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,39 @@ 2018-08-10 Martin Liska + 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. + +2018-08-10 Martin Liska + PR tree-optimization/85799 * passes.def: Add argument for pass_strip_predict_hints. * predict.c (class pass_strip_predict_hints): Add new argument 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 eeec00998a9..130f6a671ce 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 0e9a9c3e2f7..d7fd0e17555 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -9218,6 +9218,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 abbafdae74a..3fbe3b704b3 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 = RDIV (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. @@ -3933,13 +3990,14 @@ strip_predict_hints (function *fun, bool early) { tree fndecl = gimple_call_fndecl (stmt); - if ((!early - && fndecl - && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL - && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT - && gimple_call_num_args (stmt) == 2) - || (gimple_call_internal_p (stmt) - && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)) + if (!early + && ((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))) { var = gimple_call_lhs (stmt); changed = true; diff --git a/gcc/predict.def b/gcc/predict.def index c0709aa6473..e2a56f95955 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/ChangeLog b/gcc/testsuite/ChangeLog index 8a2ed682f65..af9e9c17aa4 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,5 +1,12 @@ 2018-08-10 Martin Liska + PR target/83610 + * gcc.dg/predict-17.c: New test. + * gcc.dg/predict-18.c: New test. + * gcc.dg/predict-19.c: New test. + +2018-08-10 Martin Liska + PR tree-optimization/85799 * gcc.dg/pr85799.c: New test. 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 **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.11.4.GIT