/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
Free Software Foundation, Inc.
This file is part of GCC.
static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
real_inv_br_prob_base, real_one_half, real_bb_freq_max;
-/* Random guesstimation given names. */
-#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 100 - 1)
+/* Random guesstimation given names.
+ PROV_VERY_UNLIKELY should be small enough so basic block predicted
+ by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
+#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
#define PROB_EVEN (REG_BR_PROB_BASE / 2)
#define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
#define PROB_ALWAYS (REG_BR_PROB_BASE)
#undef DEF_PREDICTOR
/* Return TRUE if frequency FREQ is considered to be hot. */
-static bool
+
+static inline bool
maybe_hot_frequency_p (int freq)
{
if (!profile_info || !flag_branch_probabilities)
if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
return true;
}
+ if (profile_status == PROFILE_ABSENT)
+ return true;
if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
return false;
return true;
}
+/* Return TRUE if frequency FREQ is considered to be hot. */
+
+static inline bool
+maybe_hot_count_p (gcov_type count)
+{
+ if (profile_status != PROFILE_READ)
+ return true;
+ /* Code executed at most once is not hot. */
+ if (profile_info->runs >= count)
+ return false;
+ return (count
+ > profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION));
+}
+
/* Return true in case BB can be CPU intensive and should be optimized
for maximal performance. */
bool
maybe_hot_bb_p (const_basic_block bb)
{
- if (profile_info && flag_branch_probabilities
- && (bb->count
- < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
- return false;
+ if (profile_status == PROFILE_READ)
+ return maybe_hot_count_p (bb->count);
return maybe_hot_frequency_p (bb->frequency);
}
-/* Return true in case BB can be CPU intensive and should be optimized
- for maximal performance. */
+/* Return true if the call can be hot. */
bool
-maybe_hot_edge_p (edge e)
+cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
{
if (profile_info && flag_branch_probabilities
- && (e->count
- < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
+ && (edge->count
+ <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
return false;
- return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
+ if (lookup_attribute ("cold", DECL_ATTRIBUTES (edge->callee->decl))
+ || lookup_attribute ("cold", DECL_ATTRIBUTES (edge->caller->decl)))
+ return false;
+ if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
+ return true;
+ if (flag_guess_branch_prob
+ && edge->frequency <= (CGRAPH_FREQ_BASE
+ / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
+ return false;
+ return true;
}
-/* Return true in case BB is cold and should be optimized for size. */
+/* Return true in case BB can be CPU intensive and should be optimized
+ for maximal performance. */
bool
-probably_cold_bb_p (const_basic_block bb)
+maybe_hot_edge_p (edge e)
{
- if (profile_info && flag_branch_probabilities
- && (bb->count
- < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
- return true;
- if ((!profile_info || !flag_branch_probabilities)
- && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
- return true;
- if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
- return true;
- return false;
+ if (profile_status == PROFILE_READ)
+ return maybe_hot_count_p (e->count);
+ return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
}
/* Return true in case BB is probably never executed. */
/* Return true when current function should always be optimized for size. */
-static bool
-always_optimize_for_size_p (void)
+bool
+optimize_function_for_size_p (struct function *fun)
{
return (optimize_size
- || cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED);
+ || (fun && (fun->function_frequency
+ == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)));
+}
+
+/* Return true when current function should always be optimized for speed. */
+
+bool
+optimize_function_for_speed_p (struct function *fun)
+{
+ return !optimize_function_for_size_p (fun);
}
/* Return TRUE when BB should be optimized for size. */
bool
-optimize_bb_for_size_p (basic_block bb)
+optimize_bb_for_size_p (const_basic_block bb)
{
- return always_optimize_for_size_p () || !maybe_hot_bb_p (bb);
+ return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
}
/* Return TRUE when BB should be optimized for speed. */
bool
-optimize_bb_for_speed_p (basic_block bb)
+optimize_bb_for_speed_p (const_basic_block bb)
{
return !optimize_bb_for_size_p (bb);
}
bool
optimize_edge_for_size_p (edge e)
{
- return always_optimize_for_size_p () || !maybe_hot_edge_p (e);
+ return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
}
/* Return TRUE when BB should be optimized for speed. */
bool
optimize_insn_for_size_p (void)
{
- return always_optimize_for_size_p () || !crtl->maybe_hot_insn_p;
+ return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
}
/* Return TRUE when BB should be optimized for speed. */
return !optimize_insn_for_size_p ();
}
+/* Return TRUE when LOOP should be optimized for size. */
+
+bool
+optimize_loop_for_size_p (struct loop *loop)
+{
+ return optimize_bb_for_size_p (loop->header);
+}
+
+/* Return TRUE when LOOP should be optimized for speed. */
+
+bool
+optimize_loop_for_speed_p (struct loop *loop)
+{
+ return optimize_bb_for_speed_p (loop->header);
+}
+
+/* Return TRUE when LOOP nest should be optimized for speed. */
+
+bool
+optimize_loop_nest_for_speed_p (struct loop *loop)
+{
+ struct loop *l = loop;
+ if (optimize_loop_for_speed_p (loop))
+ return true;
+ l = loop->inner;
+ while (l && l != loop)
+ {
+ if (optimize_loop_for_speed_p (l))
+ return true;
+ if (l->inner)
+ l = l->inner;
+ else if (l->next)
+ l = l->next;
+ else
+ {
+ while (l != loop && !l->next)
+ l = loop_outer (l);
+ if (l != loop)
+ l = l->next;
+ }
+ }
+ return false;
+}
+
+/* Return TRUE when LOOP nest should be optimized for size. */
+
+bool
+optimize_loop_nest_for_size_p (struct loop *loop)
+{
+ return !optimize_loop_nest_for_speed_p (loop);
+}
+
+/* Return true when edge E is likely to be well predictable by branch
+ predictor. */
+
+bool
+predictable_edge_p (edge e)
+{
+ if (profile_status == PROFILE_ABSENT)
+ return false;
+ if ((e->probability
+ <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
+ || (REG_BR_PROB_BASE - e->probability
+ <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
+ return true;
+ return false;
+}
+
+
/* Set RTL expansion for BB profile. */
void
rtx *pnote;
rtx note;
int best_probability = PROB_EVEN;
- int best_predictor = END_PREDICTORS;
+ enum br_predictor best_predictor = END_PREDICTORS;
int combined_probability = REG_BR_PROB_BASE / 2;
int d;
bool first_match = false;
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_BR_PRED)
{
- int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
+ enum br_predictor predictor = ((enum br_predictor)
+ INTVAL (XEXP (XEXP (note, 0), 0)));
int probability = INTVAL (XEXP (XEXP (note, 0), 1));
found = true;
{
if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
{
- int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
+ enum br_predictor predictor = ((enum br_predictor)
+ INTVAL (XEXP (XEXP (*pnote, 0), 0)));
int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
dump_prediction (dump_file, predictor, probability, bb,
combine_predictions_for_bb (basic_block bb)
{
int best_probability = PROB_EVEN;
- int best_predictor = END_PREDICTORS;
+ enum br_predictor best_predictor = END_PREDICTORS;
int combined_probability = REG_BR_PROB_BASE / 2;
int d;
bool first_match = false;
by predictor with smallest index. */
for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
{
- int predictor = pred->ep_predictor;
+ enum br_predictor predictor = pred->ep_predictor;
int probability = pred->ep_probability;
if (pred->ep_edge != first)
probability = REG_BR_PROB_BASE - probability;
found = true;
+ /* First match heuristics would be widly confused if we predicted
+ both directions. */
if (best_predictor > predictor)
- best_probability = probability, best_predictor = predictor;
+ {
+ struct edge_prediction *pred2;
+ int prob = probability;
+
+ for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
+ if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
+ {
+ int probability2 = pred->ep_probability;
+
+ if (pred2->ep_edge != first)
+ probability2 = REG_BR_PROB_BASE - probability2;
+
+ if ((probability < REG_BR_PROB_BASE / 2) !=
+ (probability2 < REG_BR_PROB_BASE / 2))
+ break;
+
+ /* If the same predictor later gave better result, go for it! */
+ if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
+ || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
+ prob = probability2;
+ }
+ if (!pred2)
+ best_probability = prob, best_predictor = predictor;
+ }
d = (combined_probability * probability
+ (REG_BR_PROB_BASE - combined_probability)
{
for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
{
- int predictor = pred->ep_predictor;
+ enum br_predictor predictor = pred->ep_predictor;
int probability = pred->ep_probability;
if (pred->ep_edge != EDGE_SUCC (bb, 0))
}
\f
-/* Get rid of all builtin_expect calls we no longer need. */
-static void
-strip_builtin_expect (void)
+/* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
+ we no longer need. */
+static unsigned int
+strip_predict_hints (void)
{
basic_block bb;
gimple ass_stmt;
FOR_EACH_BB (bb)
{
gimple_stmt_iterator bi;
- for (bi = gsi_start_bb (bb); !gsi_end_p (bi); gsi_next (&bi))
+ for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
{
gimple stmt = gsi_stmt (bi);
- tree fndecl;
-
- if (gimple_code (stmt) != GIMPLE_CALL)
- continue;
- fndecl = gimple_call_fndecl (stmt);
-
- if (fndecl
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
- && gimple_call_num_args (stmt) == 2)
+ if (gimple_code (stmt) == GIMPLE_PREDICT)
+ {
+ gsi_remove (&bi, true);
+ continue;
+ }
+ else if (gimple_code (stmt) == GIMPLE_CALL)
{
- var = gimple_call_lhs (stmt);
- ass_stmt = gimple_build_assign (var, gimple_call_arg (stmt, 0));
+ tree fndecl = gimple_call_fndecl (stmt);
+
+ if (fndecl
+ && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
+ && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
+ && gimple_call_num_args (stmt) == 2)
+ {
+ var = gimple_call_lhs (stmt);
+ ass_stmt = gimple_build_assign (var, gimple_call_arg (stmt, 0));
- gsi_replace (&bi, ass_stmt, true);
+ gsi_replace (&bi, ass_stmt, true);
+ }
}
+ gsi_next (&bi);
}
}
+ return 0;
}
\f
/* Predict using opcode of the last statement in basic block. */
tree_bb_level_predictions (void)
{
basic_block bb;
+ bool has_return_edges = false;
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+ if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
+ {
+ has_return_edges = true;
+ break;
+ }
apply_return_prediction ();
{
gimple_stmt_iterator gsi;
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
tree decl;
if (is_gimple_call (stmt))
{
- if (gimple_call_flags (stmt) & ECF_NORETURN)
+ if ((gimple_call_flags (stmt) & ECF_NORETURN)
+ && has_return_edges)
predict_paths_leading_to (bb, PRED_NORETURN,
NOT_TAKEN);
decl = gimple_call_fndecl (stmt);
{
predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
gimple_predict_outcome (stmt));
- gsi_remove (&gsi, true);
- continue;
+ /* Keep GIMPLE_PREDICT around so early inlining will propagate
+ hints to callers. */
}
-
- gsi_next (&gsi);
}
}
}
{
edge e;
edge_iterator ei;
+ gimple last;
FOR_EACH_EDGE (e, ei, bb->succs)
{
&& e->dest != EXIT_BLOCK_PTR
&& single_succ_p (e->dest)
&& single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
- && gimple_code (last_stmt (e->dest)) == GIMPLE_RETURN)
+ && (last = last_stmt (e->dest)) != NULL
+ && gimple_code (last) == GIMPLE_RETURN)
{
edge e1;
edge_iterator ei1;
pointer_map_destroy (bb_predictions);
bb_predictions = NULL;
- strip_builtin_expect ();
estimate_bb_frequencies ();
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
basic_block bb;
sreal freq_max;
- if (!flag_branch_probabilities || !counts_to_freqs ())
+ if (profile_status != PROFILE_READ || !counts_to_freqs ())
{
static int real_values_initialized = 0;
{
tree t = build1 (PREDICT_EXPR, void_type_node,
build_int_cst (NULL, predictor));
- PREDICT_EXPR_OUTCOME (t) = taken;
+ SET_PREDICT_EXPR_OUTCOME (t, taken);
return t;
}
TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
}
};
+
+struct gimple_opt_pass pass_strip_predict_hints =
+{
+ {
+ GIMPLE_PASS,
+ NULL, /* name */
+ NULL, /* gate */
+ strip_predict_hints, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_BRANCH_PROB, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ }
+};