/* 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)
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);
}
if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
return true;
if (flag_guess_branch_prob
- && edge->frequency < (CGRAPH_FREQ_MAX
- / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
+ && edge->frequency <= (CGRAPH_FREQ_BASE
+ / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
return false;
return true;
}
bool
maybe_hot_edge_p (edge e)
{
- if (profile_info && flag_branch_probabilities
- && (e->count
- < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
- 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 cold and should be optimized for size. */
-
-bool
-probably_cold_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 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;
-}
-
/* Return true in case BB is probably never executed. */
bool
probably_never_executed_bb_p (const_basic_block bb)
optimize_function_for_size_p (struct function *fun)
{
return (optimize_size
- || fun->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. */
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))
loop_iterator li;
struct loop *loop;
- scev_initialize ();
-
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
FOR_EACH_LOOP (li, loop, 0)
/* Free basic blocks from get_loop_body. */
free (bbs);
}
-
- scev_finalize ();
}
/* Attempt to predict probabilities of BB outgoing edges using local
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 ();
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);
}
#endif
-/* Predict branch probabilities and estimate profile of the tree CFG. */
-static unsigned int
+/* Predict branch probabilities and estimate profile for basic block BB. */
+
+static void
+tree_estimate_probability_bb (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+ gimple last;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ /* Predict early returns to be probable, as we've already taken
+ care for error returns and other cases are often used for
+ fast paths through function.
+
+ Since we've already removed the return statements, we are
+ looking for CFG like:
+
+ if (conditional)
+ {
+ ..
+ goto return_block
+ }
+ some other blocks
+ return_block:
+ return_stmt. */
+ if (e->dest != bb->next_bb
+ && e->dest != EXIT_BLOCK_PTR
+ && single_succ_p (e->dest)
+ && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
+ && (last = last_stmt (e->dest)) != NULL
+ && gimple_code (last) == GIMPLE_RETURN)
+ {
+ edge e1;
+ edge_iterator ei1;
+
+ if (single_succ_p (bb))
+ {
+ FOR_EACH_EDGE (e1, ei1, bb->preds)
+ if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
+ && !predicted_by_p (e1->src, PRED_CONST_RETURN)
+ && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
+ predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
+ }
+ else
+ if (!predicted_by_p (e->src, PRED_NULL_RETURN)
+ && !predicted_by_p (e->src, PRED_CONST_RETURN)
+ && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
+ predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
+ }
+
+ /* Look for block we are guarding (ie we dominate it,
+ but it doesn't postdominate us). */
+ if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
+ && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
+ && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
+ {
+ gimple_stmt_iterator bi;
+
+ /* The call heuristic claims that a guarded function call
+ is improbable. This is because such calls are often used
+ to signal exceptional situations such as printing error
+ messages. */
+ for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
+ gsi_next (&bi))
+ {
+ gimple stmt = gsi_stmt (bi);
+ if (is_gimple_call (stmt)
+ /* Constant and pure calls are hardly used to signalize
+ something exceptional. */
+ && gimple_has_side_effects (stmt))
+ {
+ predict_edge_def (e, PRED_CALL, NOT_TAKEN);
+ break;
+ }
+ }
+ }
+ }
+ tree_predict_by_opcode (bb);
+}
+
+/* Predict branch probabilities and estimate profile of the tree CFG.
+ This function can be called from the loop optimizers to recompute
+ the profile information. */
+
+void
tree_estimate_probability (void)
{
basic_block bb;
- loop_optimizer_init (0);
- if (dump_file && (dump_flags & TDF_DETAILS))
- flow_loops_dump (dump_file, NULL, 0);
-
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
/* We use loop_niter_by_eval, which requires that the loops have
bb_predictions = pointer_map_create ();
tree_bb_level_predictions ();
-
- mark_irreducible_loops ();
record_loop_exits ();
+
if (number_of_loops () > 1)
predict_loops ();
FOR_EACH_BB (bb)
- {
- edge e;
- edge_iterator ei;
+ tree_estimate_probability_bb (bb);
- FOR_EACH_EDGE (e, ei, bb->succs)
- {
- /* Predict early returns to be probable, as we've already taken
- care for error returns and other cases are often used for
- fast paths through function.
-
- Since we've already removed the return statements, we are
- looking for CFG like:
-
- if (conditional)
- {
- ..
- goto return_block
- }
- some other blocks
- return_block:
- return_stmt. */
- if (e->dest != bb->next_bb
- && 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)
- {
- edge e1;
- edge_iterator ei1;
-
- if (single_succ_p (bb))
- {
- FOR_EACH_EDGE (e1, ei1, bb->preds)
- if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
- && !predicted_by_p (e1->src, PRED_CONST_RETURN)
- && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
- predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
- }
- else
- if (!predicted_by_p (e->src, PRED_NULL_RETURN)
- && !predicted_by_p (e->src, PRED_CONST_RETURN)
- && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
- predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
- }
-
- /* Look for block we are guarding (ie we dominate it,
- but it doesn't postdominate us). */
- if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
- && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
- && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
- {
- gimple_stmt_iterator bi;
-
- /* The call heuristic claims that a guarded function call
- is improbable. This is because such calls are often used
- to signal exceptional situations such as printing error
- messages. */
- for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
- gsi_next (&bi))
- {
- gimple stmt = gsi_stmt (bi);
- if (is_gimple_call (stmt)
- /* Constant and pure calls are hardly used to signalize
- something exceptional. */
- && gimple_has_side_effects (stmt))
- {
- predict_edge_def (e, PRED_CALL, NOT_TAKEN);
- break;
- }
- }
- }
- }
- tree_predict_by_opcode (bb);
- }
FOR_EACH_BB (bb)
combine_predictions_for_bb (bb);
estimate_bb_frequencies ();
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
+}
+
+/* Predict branch probabilities and estimate profile of the tree CFG.
+ This is the driver function for PASS_PROFILE. */
+
+static unsigned int
+tree_estimate_probability_driver (void)
+{
+ unsigned nb_loops;
+
+ loop_optimizer_init (0);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ flow_loops_dump (dump_file, NULL, 0);
+
+ mark_irreducible_loops ();
+
+ nb_loops = number_of_loops ();
+ if (nb_loops > 1)
+ scev_initialize ();
+
+ tree_estimate_probability ();
+
+ if (nb_loops > 1)
+ scev_finalize ();
+
loop_optimizer_finalize ();
if (dump_file && (dump_flags & TDF_DETAILS))
gimple_dump_cfg (dump_file, dump_flags);
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;
}
GIMPLE_PASS,
"profile", /* name */
gate_estimate_probability, /* gate */
- tree_estimate_probability, /* execute */
+ tree_estimate_probability_driver, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
{
{
GIMPLE_PASS,
- "", /* name */
+ NULL, /* name */
NULL, /* gate */
strip_predict_hints, /* execute */
NULL, /* sub */
OSDN Git Service
