/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000-2018 Free Software Foundation, Inc.
+ Copyright (C) 2000-2019 Free Software Foundation, Inc.
This file is part of GCC.
enum predictor_reason, edge);
static void predict_paths_leading_to (basic_block, enum br_predictor,
enum prediction,
- struct loop *in_loop = NULL);
+ class loop *in_loop = NULL);
static void predict_paths_leading_to_edge (edge, enum br_predictor,
enum prediction,
- struct loop *in_loop = NULL);
+ class 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);
+static void determine_unlikely_bbs ();
/* Information we hold about each branch predictor.
Filled using information from predict.def. */
gcov_type
get_hot_bb_threshold ()
{
- gcov_working_set_t *ws;
if (min_count == -1)
{
- ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE));
- gcc_assert (ws);
- min_count = ws->min_counter;
+ const int hot_frac = PARAM_VALUE (HOT_BB_COUNT_FRACTION);
+ const gcov_type min_hot_count
+ = hot_frac
+ ? profile_info->sum_max / hot_frac
+ : (gcov_type)profile_count::max_count;
+ set_hot_bb_threshold (min_hot_count);
+ if (dump_file)
+ fprintf (dump_file, "Setting hotness threshold to %" PRId64 ".\n",
+ min_hot_count);
}
return min_count;
}
min_count = min;
}
-/* Return TRUE if frequency FREQ is considered to be hot. */
+/* Return TRUE if COUNT is considered to be hot in function FUN. */
bool
maybe_hot_count_p (struct function *fun, profile_count count)
if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
&& count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
return false;
- if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
- return false;
if (count.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION), 1)
< ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
return false;
return (count.to_gcov_type () >= get_hot_bb_threshold ());
}
-/* Return true in case BB can be CPU intensive and should be optimized
- for maximal performance. */
+/* Return true if basic block BB of function FUN can be CPU intensive
+ and should thus be optimized for maximum performance. */
bool
maybe_hot_bb_p (struct function *fun, const_basic_block bb)
return maybe_hot_count_p (fun, bb->count);
}
-/* Return true in case BB can be CPU intensive and should be optimized
- for maximal performance. */
+/* Return true if edge E can be CPU intensive and should thus be optimized
+ for maximum performance. */
bool
maybe_hot_edge_p (edge e)
return maybe_hot_count_p (cfun, e->count ());
}
-/* Return true if profile COUNT and FREQUENCY, or function FUN static
- node frequency reflects never being executed. */
+/* Return true if COUNT is considered to be never executed in function FUN
+ or if function FUN is considered so in the static profile. */
static bool
-probably_never_executed (struct function *fun,
- profile_count count)
+probably_never_executed (struct function *fun, profile_count count)
{
gcc_checking_assert (fun);
if (count.ipa () == profile_count::zero ())
desirable. */
if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
{
- int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
- if (count.apply_scale (unlikely_count_fraction, 1) >= profile_info->runs)
+ const int unlikely_frac = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
+ if (count.apply_scale (unlikely_frac, 1) >= profile_info->runs)
return false;
return true;
}
return false;
}
-
-/* Return true in case BB is probably never executed. */
+/* Return true if basic block BB of function FUN is probably never executed. */
bool
probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
return probably_never_executed (fun, bb->count);
}
-
-/* Return true if E is unlikely executed for obvious reasons. */
+/* Return true if edge E is unlikely executed for obvious reasons. */
static bool
unlikely_executed_edge_p (edge e)
|| (e->flags & (EDGE_EH | EDGE_FAKE));
}
-/* Return true in case edge E is probably never executed. */
+/* Return true if edge E of function FUN is probably never executed. */
bool
probably_never_executed_edge_p (struct function *fun, edge e)
return probably_never_executed (fun, e->count ());
}
-/* Return true when current function should always be optimized for size. */
+/* Return true if function FUN should always be optimized for size. */
bool
optimize_function_for_size_p (struct function *fun)
return n && n->optimize_for_size_p ();
}
-/* Return true when current function should always be optimized for speed. */
+/* Return true if function FUN should always be optimized for speed. */
bool
optimize_function_for_speed_p (struct function *fun)
return !optimize_function_for_size_p (fun);
}
-/* Return the optimization type that should be used for the function FUN. */
+/* Return the optimization type that should be used for function FUN. */
optimization_type
function_optimization_type (struct function *fun)
: OPTIMIZE_FOR_SIZE);
}
-/* Return TRUE when BB should be optimized for size. */
+/* Return TRUE if basic block BB should be optimized for size. */
bool
optimize_bb_for_size_p (const_basic_block bb)
|| (bb && !maybe_hot_bb_p (cfun, bb)));
}
-/* Return TRUE when BB should be optimized for speed. */
+/* Return TRUE if basic block BB should be optimized for speed. */
bool
optimize_bb_for_speed_p (const_basic_block bb)
return !optimize_bb_for_size_p (bb);
}
-/* Return the optimization type that should be used for block BB. */
+/* Return the optimization type that should be used for basic block BB. */
optimization_type
bb_optimization_type (const_basic_block bb)
: OPTIMIZE_FOR_SIZE);
}
-/* Return TRUE when BB should be optimized for size. */
+/* Return TRUE if edge E should be optimized for size. */
bool
optimize_edge_for_size_p (edge e)
return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
}
-/* Return TRUE when BB should be optimized for speed. */
+/* Return TRUE if edge E should be optimized for speed. */
bool
optimize_edge_for_speed_p (edge e)
return !optimize_edge_for_size_p (e);
}
-/* Return TRUE when BB should be optimized for size. */
+/* Return TRUE if the current function is optimized for size. */
bool
optimize_insn_for_size_p (void)
return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
}
-/* Return TRUE when BB should be optimized for speed. */
+/* Return TRUE if the current function is optimized for speed. */
bool
optimize_insn_for_speed_p (void)
return !optimize_insn_for_size_p ();
}
-/* Return TRUE when LOOP should be optimized for size. */
+/* Return TRUE if LOOP should be optimized for size. */
bool
-optimize_loop_for_size_p (struct loop *loop)
+optimize_loop_for_size_p (class loop *loop)
{
return optimize_bb_for_size_p (loop->header);
}
-/* Return TRUE when LOOP should be optimized for speed. */
+/* Return TRUE if LOOP should be optimized for speed. */
bool
-optimize_loop_for_speed_p (struct loop *loop)
+optimize_loop_for_speed_p (class loop *loop)
{
return optimize_bb_for_speed_p (loop->header);
}
-/* Return TRUE when LOOP nest should be optimized for speed. */
+/* Return TRUE if nest rooted at LOOP should be optimized for speed. */
bool
-optimize_loop_nest_for_speed_p (struct loop *loop)
+optimize_loop_nest_for_speed_p (class loop *loop)
{
- struct loop *l = loop;
+ class loop *l = loop;
if (optimize_loop_for_speed_p (loop))
return true;
l = loop->inner;
return false;
}
-/* Return TRUE when LOOP nest should be optimized for size. */
+/* Return TRUE if nest rooted at LOOP should be optimized for size. */
bool
-optimize_loop_nest_for_size_p (struct loop *loop)
+optimize_loop_nest_for_size_p (class loop *loop)
{
return !optimize_loop_nest_for_speed_p (loop);
}
-/* Return true when edge E is likely to be well predictable by branch
+/* Return true if edge E is likely to be well predictable by branch
predictor. */
bool
return false;
}
-/* We can not predict the probabilities of outgoing edges of bb. Set them
+/* We cannot predict the probabilities of outgoing edges of bb. Set them
evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
even probability for all edges not mentioned in the set. These edges
- are given PROB_VERY_UNLIKELY probability. */
+ are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
+ if we have exactly one likely edge, make the other edges predicted
+ as not probable. */
static void
set_even_probabilities (basic_block bb,
- hash_set<edge> *unlikely_edges = NULL)
+ hash_set<edge> *unlikely_edges = NULL,
+ hash_set<edge_prediction *> *likely_edges = NULL)
{
unsigned nedges = 0, unlikely_count = 0;
edge e = NULL;
all -= e->probability;
else if (!unlikely_executed_edge_p (e))
{
- nedges ++;
+ nedges++;
if (unlikely_edges != NULL && unlikely_edges->contains (e))
{
all -= profile_probability::very_unlikely ();
}
/* Make the distribution even if all edges are unlikely. */
+ unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
if (unlikely_count == nedges)
{
unlikely_edges = NULL;
unlikely_count = 0;
}
- unsigned c = nedges - unlikely_count;
+ /* If we have one likely edge, then use its probability and distribute
+ remaining probabilities as even. */
+ if (likely_count == 1)
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->probability.initialized_p ())
+ ;
+ else if (!unlikely_executed_edge_p (e))
+ {
+ edge_prediction *prediction = *likely_edges->begin ();
+ int p = prediction->ep_probability;
+ profile_probability prob
+ = profile_probability::from_reg_br_prob_base (p);
+
+ if (prediction->ep_edge == e)
+ e->probability = prob;
+ else if (unlikely_edges != NULL && unlikely_edges->contains (e))
+ e->probability = profile_probability::very_unlikely ();
+ else
+ {
+ profile_probability remainder = prob.invert ();
+ remainder -= profile_probability::very_unlikely ()
+ .apply_scale (unlikely_count, 1);
+ int count = nedges - unlikely_count - 1;
+ gcc_assert (count >= 0);
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->probability.initialized_p ())
- ;
- else if (!unlikely_executed_edge_p (e))
- {
- if (unlikely_edges != NULL && unlikely_edges->contains (e))
- e->probability = profile_probability::very_unlikely ();
+ e->probability = remainder.apply_scale (1, count);
+ }
+ }
else
- e->probability = all.apply_scale (1, c).guessed ();
- }
- else
- e->probability = profile_probability::never ();
+ e->probability = profile_probability::never ();
+ }
+ else
+ {
+ /* Make all unlikely edges unlikely and the rest will have even
+ probability. */
+ unsigned scale = nedges - unlikely_count;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->probability.initialized_p ())
+ ;
+ else if (!unlikely_executed_edge_p (e))
+ {
+ if (unlikely_edges != NULL && unlikely_edges->contains (e))
+ e->probability = profile_probability::very_unlikely ();
+ else
+ e->probability = all.apply_scale (1, scale);
+ }
+ else
+ e->probability = profile_probability::never ();
+ }
}
/* Add REG_BR_PROB note to JUMP with PROB. */
if (nedges != 2)
{
hash_set<edge> unlikely_edges (4);
+ hash_set<edge_prediction *> likely_edges (4);
/* Identify all edges that have a probability close to very unlikely.
Doing the approach for very unlikely doesn't worth for doing as
edge_prediction **preds = bb_predictions->get (bb);
if (preds)
for (pred = *preds; pred; pred = pred->ep_next)
- if (pred->ep_probability <= PROB_VERY_UNLIKELY)
- unlikely_edges.add (pred->ep_edge);
+ {
+ if (pred->ep_probability <= PROB_VERY_UNLIKELY
+ || pred->ep_predictor == PRED_COLD_LABEL)
+ unlikely_edges.add (pred->ep_edge);
+ else if (pred->ep_probability >= PROB_VERY_LIKELY
+ || pred->ep_predictor == PRED_BUILTIN_EXPECT
+ || pred->ep_predictor == PRED_HOT_LABEL)
+ likely_edges.add (pred);
+ }
+
+ /* It can happen that an edge is both in likely_edges and unlikely_edges.
+ Clear both sets in that situation. */
+ for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
+ it != likely_edges.end (); ++it)
+ if (unlikely_edges.contains ((*it)->ep_edge))
+ {
+ likely_edges.empty ();
+ unlikely_edges.empty ();
+ break;
+ }
if (!dry_run)
- set_even_probabilities (bb, &unlikely_edges);
+ set_even_probabilities (bb, &unlikely_edges, &likely_edges);
clear_bb_predictions (bb);
if (dump_file)
{
fprintf (dump_file, "Predictions for bb %i\n", bb->index);
- if (unlikely_edges.elements () == 0)
+ if (unlikely_edges.is_empty ())
fprintf (dump_file,
"%i edges in bb %i predicted to even probabilities\n",
nedges, bb->index);
Otherwise return false and set LOOP_INVAIANT to NULL. */
static bool
-is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
+is_comparison_with_loop_invariant_p (gcond *stmt, class loop *loop,
tree *loop_invariant,
enum tree_code *compare_code,
tree *loop_step,
In this loop, we will predict the branch inside the loop to be taken. */
static void
-predict_iv_comparison (struct loop *loop, basic_block bb,
+predict_iv_comparison (class loop *loop, basic_block bb,
tree loop_bound_var,
tree loop_iv_base_var,
enum tree_code loop_bound_code,
static void
predict_loops (void)
{
- struct loop *loop;
+ class loop *loop;
basic_block bb;
- hash_set <struct loop *> with_recursion(10);
+ hash_set <class loop *> with_recursion(10);
FOR_EACH_BB_FN (bb, cfun)
{
basic_block bb, *bbs;
unsigned j, n_exits = 0;
vec<edge> exits;
- struct tree_niter_desc niter_desc;
+ class tree_niter_desc niter_desc;
edge ex;
- struct nb_iter_bound *nb_iter;
+ class nb_iter_bound *nb_iter;
enum tree_code loop_bound_code = ERROR_MARK;
tree loop_bound_step = NULL;
tree loop_bound_var = NULL;
if (arg == PHI_RESULT (def))
continue;
+ HOST_WIDE_INT probability2;
new_val = expr_expected_value (arg, visited, &predictor2,
- probability);
+ &probability2);
/* It is difficult to combine value predictors. Simply assume
that later predictor is weaker and take its prediction. */
if (*predictor < predictor2)
- *predictor = predictor2;
+ {
+ *predictor = predictor2;
+ *probability = probability2;
+ }
if (!new_val)
return NULL;
if (!val)
return NULL;
}
- if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW (decl))
+ if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
{
if (predictor)
*predictor = PRED_MALLOC_NONNULL;
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);
+ tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
+ MULT_EXPR, t, prob, base);
+ if (TREE_CODE (r) != REAL_CST)
+ {
+ error_at (gimple_location (def),
+ "probability %qE must be "
+ "constant floating-point expression", prob);
+ return NULL;
+ }
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;
}
+ else
+ error_at (gimple_location (def),
+ "probability %qE is outside "
+ "the range [0.0, 1.0]", prob);
+
return gimple_call_arg (def, 1);
}
enum br_predictor predictor;
HOST_WIDE_INT probability;
- if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+ if (!stmt)
+ return;
+
+ if (gswitch *sw = dyn_cast <gswitch *> (stmt))
+ {
+ tree index = gimple_switch_index (sw);
+ tree val = expr_expected_value (index, auto_bitmap (),
+ &predictor, &probability);
+ if (val && TREE_CODE (val) == INTEGER_CST)
+ {
+ edge e = find_taken_edge_switch_expr (sw, val);
+ if (predictor == PRED_BUILTIN_EXPECT)
+ {
+ int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
+ gcc_assert (percent >= 0 && percent <= 100);
+ predict_edge (e, PRED_BUILTIN_EXPECT,
+ HITRATE (percent));
+ }
+ else
+ predict_edge_def (e, predictor, TAKEN);
+ }
+ }
+
+ if (gimple_code (stmt) != GIMPLE_COND)
return;
FOR_EACH_EDGE (then_edge, ei, bb->succs)
if (then_edge->flags & EDGE_TRUE_VALUE)
preheaders. */
create_preheaders (CP_SIMPLE_PREHEADERS);
calculate_dominance_info (CDI_POST_DOMINATORS);
+ /* Decide which edges are known to be unlikely. This improves later
+ branch prediction. */
+ determine_unlikely_bbs ();
bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
tree_bb_level_predictions ();
predict_paths_for_bb (basic_block cur, basic_block bb,
enum br_predictor pred,
enum prediction taken,
- bitmap visited, struct loop *in_loop = NULL)
+ bitmap visited, class loop *in_loop = NULL)
{
edge e;
edge_iterator ei;
static void
predict_paths_leading_to (basic_block bb, enum br_predictor pred,
- enum prediction taken, struct loop *in_loop)
+ enum prediction taken, class loop *in_loop)
{
predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
}
static void
predict_paths_leading_to_edge (edge e, enum br_predictor pred,
- enum prediction taken, struct loop *in_loop)
+ enum prediction taken, class loop *in_loop)
{
bool has_nonloop_edge = false;
edge_iterator ei;
/* This is used to carry information about basic blocks. It is
attached to the AUX field of the standard CFG block. */
-struct block_info
+class block_info
{
+public:
/* Estimated frequency of execution of basic_block. */
sreal frequency;
};
/* Similar information for edges. */
-struct edge_prob_info
+class edge_prob_info
{
+public:
/* In case edge is a loopback edge, the probability edge will be reached
in case header is. Estimated number of iterations of the loop can be
then computed as 1 / (1 - back_edge_prob). */
/* Estimate frequencies in loops at same nest level. */
static void
-estimate_loops_at_level (struct loop *first_loop)
+estimate_loops_at_level (class loop *first_loop)
{
- struct loop *loop;
+ class loop *loop;
for (loop = first_loop; loop; loop = loop->next)
{
void
handle_missing_profiles (void)
{
+ const int unlikely_frac = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
struct cgraph_node *node;
- int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
auto_vec<struct cgraph_node *, 64> worklist;
/* See if 0 count function has non-0 count callers. In this case we
if (call_count > 0
&& fn && fn->cfg
- && (call_count.apply_scale (unlikely_count_fraction, 1)
- >= profile_info->runs))
+ && call_count.apply_scale (unlikely_frac, 1) >= profile_info->runs)
{
drop_profile (node, call_count);
worklist.safe_push (node);
}
/* Finally all edges from non-0 regions to 0 are unlikely. */
FOR_ALL_BB_FN (bb, cfun)
- if (!(bb->count == profile_count::zero ()))
+ {
+ if (!(bb->count == profile_count::zero ()))
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->probability == profile_probability::never ())
+ && e->dest->count == profile_count::zero ())
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Edge %i->%i is unlikely because "
+ "it enters unlikely block\n",
+ bb->index, e->dest->index);
+ e->probability = profile_probability::never ();
+ }
+
+ edge other = NULL;
+
FOR_EACH_EDGE (e, ei, bb->succs)
- if (!(e->probability == profile_probability::never ())
- && e->dest->count == profile_count::zero ())
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Edge %i->%i is unlikely because "
- "it enters unlikely block\n",
- bb->index, e->dest->index);
- e->probability = profile_probability::never ();
- }
+ if (e->probability == profile_probability::never ())
+ ;
+ else if (other)
+ {
+ other = NULL;
+ break;
+ }
+ else
+ other = e;
+ if (other
+ && !(other->probability == profile_probability::always ()))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Edge %i->%i is locally likely\n",
+ bb->index, other->dest->index);
+ other->probability = profile_probability::always ();
+ }
+ }
if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
cgraph_node::get (current_function_decl)->count = profile_count::zero ();
}
profile_status_for_fn (fun) = PROFILE_GUESSED;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- struct loop *loop;
+ class loop *loop;
FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
if (loop->header->count.initialized_p ())
fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
tree fndecl = gimple_call_fndecl (stmt);
if (!early
- && ((DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
+ && ((fndecl != NULL_TREE
+ && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
&& gimple_call_num_args (stmt) == 2)
- || (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
- BUILT_IN_EXPECT_WITH_PROBABILITY)
+ || (fndecl != NULL_TREE
+ && fndecl_built_in_p (fndecl,
+ BUILT_IN_EXPECT_WITH_PROBABILITY)
&& gimple_call_num_args (stmt) == 3)
|| (gimple_call_internal_p (stmt)
&& gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
we are not 100% sure.
This function locally updates profile without attempt to keep global
- consistency which can not be reached in full generality without full profile
+ consistency which cannot be reached in full generality without full profile
rebuild from probabilities alone. Doing so is not necessarily a good idea
because frequencies and counts may be more realistic then probabilities.
{
if (impossible)
e->probability = profile_probability::never ();
- /* If BB has some edges out that are not impossible, we can not
+ /* If BB has some edges out that are not impossible, we cannot
assume that BB itself is. */
impossible = false;
}
projects / thirdparty / gcc.git / blobdiff