/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007
+ 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)
static void combine_predictions_for_insn (rtx, basic_block);
static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
-static void predict_paths_leading_to (basic_block, int *, enum br_predictor, enum prediction);
+static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
static void compute_function_frequency (void);
static void choose_function_section (void);
-static bool can_predict_insn_p (rtx);
+static bool can_predict_insn_p (const_rtx);
/* Information we hold about each branch predictor.
Filled using information from predict.def. */
};
#undef DEF_PREDICTOR
-/* Return true in case BB can be CPU intensive and should be optimized
- for maximal performance. */
+/* Return TRUE if frequency FREQ is considered to be hot. */
-bool
-maybe_hot_bb_p (basic_block bb)
+static inline bool
+maybe_hot_frequency_p (int freq)
{
- if (profile_info && flag_branch_probabilities
- && (bb->count
- < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
- return false;
if (!profile_info || !flag_branch_probabilities)
{
if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
return true;
}
- if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
+ if (profile_status == PROFILE_ABSENT)
+ return true;
+ if (freq < BB_FREQ_MAX / 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 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_status == PROFILE_READ)
+ return maybe_hot_count_p (bb->count);
+ return maybe_hot_frequency_p (bb->frequency);
+}
+
+/* Return true if the call can be hot. */
bool
-probably_cold_bb_p (basic_block bb)
+cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
{
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))
+ && (edge->count
+ <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
+ return false;
+ 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;
- return false;
+ 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 can be CPU intensive and should be optimized
+ for maximal performance. */
+
+bool
+maybe_hot_edge_p (edge e)
+{
+ 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. */
bool
-probably_never_executed_bb_p (basic_block bb)
+probably_never_executed_bb_p (const_basic_block bb)
{
if (profile_info && flag_branch_probabilities)
return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
return false;
}
+/* Return true when current function should always be optimized for size. */
+
+bool
+optimize_function_for_size_p (struct function *fun)
+{
+ return (optimize_size
+ || (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 (const_basic_block 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 (const_basic_block bb)
+{
+ return !optimize_bb_for_size_p (bb);
+}
+
+/* Return TRUE when BB 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. */
+
+bool
+optimize_edge_for_speed_p (edge e)
+{
+ return !optimize_edge_for_size_p (e);
+}
+
+/* Return TRUE when BB should be 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. */
+
+bool
+optimize_insn_for_speed_p (void)
+{
+ 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
+rtl_profile_for_bb (basic_block bb)
+{
+ crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
+}
+
+/* Set RTL expansion for edge profile. */
+
+void
+rtl_profile_for_edge (edge e)
+{
+ crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
+}
+
+/* Set RTL expansion to default mode (i.e. when profile info is not known). */
+void
+default_rtl_profile (void)
+{
+ crtl->maybe_hot_insn_p = true;
+}
+
/* Return true if the one of outgoing edges is already predicted by
PREDICTOR. */
bool
-rtl_predicted_by_p (basic_block bb, enum br_predictor predictor)
+rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
{
rtx note;
if (!INSN_P (BB_END (bb)))
PREDICTOR. */
bool
-tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
+gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
{
struct edge_prediction *i;
void **preds = pointer_map_contains (bb_predictions, bb);
if (!preds)
return false;
- for (i = *preds; i; i = i->ep_next)
+ for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
if (i->ep_predictor == predictor)
return true;
return false;
/* Same predicate as above, working on edges. */
bool
-edge_probability_reliable_p (edge e)
+edge_probability_reliable_p (const_edge e)
{
return probability_reliable_p (e->probability);
}
/* Same predicate as edge_probability_reliable_p, working on notes. */
bool
-br_prob_note_reliable_p (rtx note)
+br_prob_note_reliable_p (const_rtx note)
{
gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
return probability_reliable_p (INTVAL (XEXP (note, 0)));
if (!flag_guess_branch_prob)
return;
- REG_NOTES (insn)
- = gen_rtx_EXPR_LIST (REG_BR_PRED,
- gen_rtx_CONCAT (VOIDmode,
- GEN_INT ((int) predictor),
- GEN_INT ((int) probability)),
- REG_NOTES (insn));
+ add_reg_note (insn, REG_BR_PRED,
+ gen_rtx_CONCAT (VOIDmode,
+ GEN_INT ((int) predictor),
+ GEN_INT ((int) probability)));
}
/* Predict insn by given predictor. */
/* Predict edge E with the given PROBABILITY. */
void
-tree_predict_edge (edge e, enum br_predictor predictor, int probability)
+gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
{
gcc_assert (profile_status != PROFILE_GUESSED);
if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
struct edge_prediction *i = XNEW (struct edge_prediction);
void **preds = pointer_map_insert (bb_predictions, e->src);
- i->ep_next = *preds;
+ i->ep_next = (struct edge_prediction *) *preds;
*preds = i;
i->ep_probability = probability;
i->ep_predictor = predictor;
if (!preds)
return;
- for (pred = *preds; pred; pred = next)
+ for (pred = (struct edge_prediction *) *preds; pred; pred = next)
{
next = pred->ep_next;
free (pred);
At the moment we represent predictions only on conditional
jumps, not at computed jump or other complicated cases. */
static bool
-can_predict_insn_p (rtx insn)
+can_predict_insn_p (const_rtx insn)
{
return (JUMP_P (insn)
&& any_condjump_p (insn)
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,
if (!prob_note)
{
- REG_NOTES (insn)
- = gen_rtx_EXPR_LIST (REG_BR_PROB,
- GEN_INT (combined_probability), REG_NOTES (insn));
+ add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
/* Save the prediction into CFG in case we are seeing non-degenerated
conditional jump. */
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;
{
/* We implement "first match" heuristics and use probability guessed
by predictor with smallest index. */
- for (pred = *preds; pred; pred = pred->ep_next)
+ 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)
if (preds)
{
- for (pred = *preds; pred; pred = pred->ep_next)
+ 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
combine_predictions_for_insn (BB_END (bb), bb);
}
\f
-/* Return constant EXPR will likely have at execution time, NULL if unknown.
- The function is used by builtin_expect branch predictor so the evidence
- must come from this construct and additional possible constant folding.
-
- We may want to implement more involved value guess (such as value range
- propagation based prediction), but such tricks shall go to new
- implementation. */
+static tree expr_expected_value (tree, bitmap);
+
+/* Helper function for expr_expected_value. */
static tree
-expr_expected_value (tree expr, bitmap visited)
+expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
{
- if (TREE_CONSTANT (expr))
- return expr;
- else if (TREE_CODE (expr) == SSA_NAME)
+ gimple def;
+
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
{
- tree def = SSA_NAME_DEF_STMT (expr);
+ if (TREE_CONSTANT (op0))
+ return op0;
+
+ if (code != SSA_NAME)
+ return NULL_TREE;
+
+ def = SSA_NAME_DEF_STMT (op0);
/* If we were already here, break the infinite cycle. */
- if (bitmap_bit_p (visited, SSA_NAME_VERSION (expr)))
+ if (bitmap_bit_p (visited, SSA_NAME_VERSION (op0)))
return NULL;
- bitmap_set_bit (visited, SSA_NAME_VERSION (expr));
+ bitmap_set_bit (visited, SSA_NAME_VERSION (op0));
- if (TREE_CODE (def) == PHI_NODE)
+ if (gimple_code (def) == GIMPLE_PHI)
{
/* All the arguments of the PHI node must have the same constant
length. */
- int i;
+ int i, n = gimple_phi_num_args (def);
tree val = NULL, new_val;
- for (i = 0; i < PHI_NUM_ARGS (def); i++)
+ for (i = 0; i < n; i++)
{
tree arg = PHI_ARG_DEF (def, i);
}
return val;
}
- if (TREE_CODE (def) != GIMPLE_MODIFY_STMT
- || GIMPLE_STMT_OPERAND (def, 0) != expr)
- return NULL;
- return expr_expected_value (GIMPLE_STMT_OPERAND (def, 1), visited);
- }
- else if (TREE_CODE (expr) == CALL_EXPR)
- {
- tree decl = get_callee_fndecl (expr);
- if (!decl)
- return NULL;
- if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
+ if (is_gimple_assign (def))
{
- tree val;
+ if (gimple_assign_lhs (def) != op0)
+ return NULL;
+
+ return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
+ gimple_assign_rhs1 (def),
+ gimple_assign_rhs_code (def),
+ gimple_assign_rhs2 (def),
+ visited);
+ }
- if (call_expr_nargs (expr) != 2)
+ if (is_gimple_call (def))
+ {
+ tree decl = gimple_call_fndecl (def);
+ if (!decl)
return NULL;
- val = CALL_EXPR_ARG (expr, 0);
- if (TREE_CONSTANT (val))
- return val;
- return CALL_EXPR_ARG (expr, 1);
+ if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
+ && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
+ {
+ tree val;
+
+ if (gimple_call_num_args (def) != 2)
+ return NULL;
+ val = gimple_call_arg (def, 0);
+ if (TREE_CONSTANT (val))
+ return val;
+ return gimple_call_arg (def, 1);
+ }
}
+
+ return NULL;
}
- if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
+
+ if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
{
- tree op0, op1, res;
- op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
+ tree res;
+ op0 = expr_expected_value (op0, visited);
if (!op0)
return NULL;
- op1 = expr_expected_value (TREE_OPERAND (expr, 1), visited);
+ op1 = expr_expected_value (op1, visited);
if (!op1)
return NULL;
- res = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr), op0, op1);
+ res = fold_build2 (code, type, op0, op1);
if (TREE_CONSTANT (res))
return res;
return NULL;
}
- if (UNARY_CLASS_P (expr))
+ if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
{
- tree op0, res;
- op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
+ tree res;
+ op0 = expr_expected_value (op0, visited);
if (!op0)
return NULL;
- res = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), op0);
+ res = fold_build1 (code, type, op0);
if (TREE_CONSTANT (res))
return res;
return NULL;
}
return NULL;
}
+
+/* Return constant EXPR will likely have at execution time, NULL if unknown.
+ The function is used by builtin_expect branch predictor so the evidence
+ must come from this construct and additional possible constant folding.
+
+ We may want to implement more involved value guess (such as value range
+ propagation based prediction), but such tricks shall go to new
+ implementation. */
+
+static tree
+expr_expected_value (tree expr, bitmap visited)
+{
+ enum tree_code code;
+ tree op0, op1;
+
+ if (TREE_CONSTANT (expr))
+ return expr;
+
+ extract_ops_from_tree (expr, &code, &op0, &op1);
+ return expr_expected_value_1 (TREE_TYPE (expr),
+ op0, code, op1, visited);
+}
+
\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;
+ tree var;
+
FOR_EACH_BB (bb)
{
- block_stmt_iterator bi;
- for (bi = bsi_start (bb); !bsi_end_p (bi); bsi_next (&bi))
+ gimple_stmt_iterator bi;
+ for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
{
- tree stmt = bsi_stmt (bi);
- tree fndecl;
- tree call;
-
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && (call = GIMPLE_STMT_OPERAND (stmt, 1))
- && TREE_CODE (call) == CALL_EXPR
- && (fndecl = get_callee_fndecl (call))
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
- && call_expr_nargs (call) == 2)
+ gimple stmt = gsi_stmt (bi);
+
+ if (gimple_code (stmt) == GIMPLE_PREDICT)
{
- GIMPLE_STMT_OPERAND (stmt, 1) = CALL_EXPR_ARG (call, 0);
- update_stmt (stmt);
+ gsi_remove (&bi, true);
+ continue;
}
+ else if (gimple_code (stmt) == GIMPLE_CALL)
+ {
+ 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_next (&bi);
}
}
+ return 0;
}
\f
/* Predict using opcode of the last statement in basic block. */
static void
tree_predict_by_opcode (basic_block bb)
{
- tree stmt = last_stmt (bb);
+ gimple stmt = last_stmt (bb);
edge then_edge;
- tree cond;
- tree op0;
+ tree op0, op1;
tree type;
tree val;
+ enum tree_code cmp;
bitmap visited;
edge_iterator ei;
- if (!stmt || TREE_CODE (stmt) != COND_EXPR)
+ if (!stmt || gimple_code (stmt) != GIMPLE_COND)
return;
FOR_EACH_EDGE (then_edge, ei, bb->succs)
if (then_edge->flags & EDGE_TRUE_VALUE)
break;
- cond = TREE_OPERAND (stmt, 0);
- if (!COMPARISON_CLASS_P (cond))
- return;
- op0 = TREE_OPERAND (cond, 0);
+ op0 = gimple_cond_lhs (stmt);
+ op1 = gimple_cond_rhs (stmt);
+ cmp = gimple_cond_code (stmt);
type = TREE_TYPE (op0);
visited = BITMAP_ALLOC (NULL);
- val = expr_expected_value (cond, visited);
+ val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
BITMAP_FREE (visited);
if (val)
{
Similarly, a comparison ptr1 == ptr2 is predicted as false. */
if (POINTER_TYPE_P (type))
{
- if (TREE_CODE (cond) == EQ_EXPR)
+ if (cmp == EQ_EXPR)
predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
- else if (TREE_CODE (cond) == NE_EXPR)
+ else if (cmp == NE_EXPR)
predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
}
else
EQ tests are usually false and NE tests are usually true. Also,
most quantities are positive, so we can make the appropriate guesses
about signed comparisons against zero. */
- switch (TREE_CODE (cond))
+ switch (cmp)
{
case EQ_EXPR:
case UNEQ_EXPR:
;
/* Comparisons with 0 are often used for booleans and there is
nothing useful to predict about them. */
- else if (integer_zerop (op0)
- || integer_zerop (TREE_OPERAND (cond, 1)))
+ else if (integer_zerop (op0) || integer_zerop (op1))
;
else
predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
/* Comparisons with 0 are often used for booleans and there is
nothing useful to predict about them. */
else if (integer_zerop (op0)
- || integer_zerop (TREE_OPERAND (cond, 1)))
+ || integer_zerop (op1))
;
else
predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
case LE_EXPR:
case LT_EXPR:
- if (integer_zerop (TREE_OPERAND (cond, 1))
- || integer_onep (TREE_OPERAND (cond, 1))
- || integer_all_onesp (TREE_OPERAND (cond, 1))
- || real_zerop (TREE_OPERAND (cond, 1))
- || real_onep (TREE_OPERAND (cond, 1))
- || real_minus_onep (TREE_OPERAND (cond, 1)))
+ if (integer_zerop (op1)
+ || integer_onep (op1)
+ || integer_all_onesp (op1)
+ || real_zerop (op1)
+ || real_onep (op1)
+ || real_minus_onep (op1))
predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
break;
case GE_EXPR:
case GT_EXPR:
- if (integer_zerop (TREE_OPERAND (cond, 1))
- || integer_onep (TREE_OPERAND (cond, 1))
- || integer_all_onesp (TREE_OPERAND (cond, 1))
- || real_zerop (TREE_OPERAND (cond, 1))
- || real_onep (TREE_OPERAND (cond, 1))
- || real_minus_onep (TREE_OPERAND (cond, 1)))
+ if (integer_zerop (op1)
+ || integer_onep (op1)
+ || integer_all_onesp (op1)
+ || real_zerop (op1)
+ || real_onep (op1)
+ || real_minus_onep (op1))
predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
break;
}
/* Try to guess whether the value of return means error code. */
+
static enum br_predictor
return_prediction (tree val, enum prediction *prediction)
{
/* Find the basic block with return expression and look up for possible
return value trying to apply RETURN_PREDICTION heuristics. */
static void
-apply_return_prediction (int *heads)
+apply_return_prediction (void)
{
- tree return_stmt = NULL;
+ gimple return_stmt = NULL;
tree return_val;
edge e;
- tree phi;
+ gimple phi;
int phi_num_args, i;
enum br_predictor pred;
enum prediction direction;
{
return_stmt = last_stmt (e->src);
if (return_stmt
- && TREE_CODE (return_stmt) == RETURN_EXPR)
+ && gimple_code (return_stmt) == GIMPLE_RETURN)
break;
}
if (!e)
return;
- return_val = TREE_OPERAND (return_stmt, 0);
+ return_val = gimple_return_retval (return_stmt);
if (!return_val)
return;
- if (TREE_CODE (return_val) == GIMPLE_MODIFY_STMT)
- return_val = GIMPLE_STMT_OPERAND (return_val, 1);
if (TREE_CODE (return_val) != SSA_NAME
|| !SSA_NAME_DEF_STMT (return_val)
- || TREE_CODE (SSA_NAME_DEF_STMT (return_val)) != PHI_NODE)
+ || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
return;
- for (phi = SSA_NAME_DEF_STMT (return_val); phi; phi = PHI_CHAIN (phi))
- if (PHI_RESULT (phi) == return_val)
- break;
- if (!phi)
- return;
- phi_num_args = PHI_NUM_ARGS (phi);
+ phi = SSA_NAME_DEF_STMT (return_val);
+ phi_num_args = gimple_phi_num_args (phi);
pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
/* Avoid the degenerate case where all return values form the function
{
pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
if (pred != PRED_NO_PREDICTION)
- predict_paths_leading_to (PHI_ARG_EDGE (phi, i)->src, heads, pred,
+ predict_paths_leading_to (gimple_phi_arg_edge (phi, i)->src, pred,
direction);
}
}
tree_bb_level_predictions (void)
{
basic_block bb;
- int *heads;
+ bool has_return_edges = false;
+ edge e;
+ edge_iterator ei;
- heads = XCNEWVEC (int, last_basic_block);
- heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
+ 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 (heads);
+ apply_return_prediction ();
FOR_EACH_BB (bb)
{
- block_stmt_iterator bsi = bsi_last (bb);
+ gimple_stmt_iterator gsi;
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- tree stmt = bsi_stmt (bsi);
+ gimple stmt = gsi_stmt (gsi);
tree decl;
- switch (TREE_CODE (stmt))
+
+ if (is_gimple_call (stmt))
+ {
+ if ((gimple_call_flags (stmt) & ECF_NORETURN)
+ && has_return_edges)
+ predict_paths_leading_to (bb, PRED_NORETURN,
+ NOT_TAKEN);
+ decl = gimple_call_fndecl (stmt);
+ if (decl
+ && lookup_attribute ("cold",
+ DECL_ATTRIBUTES (decl)))
+ predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
+ NOT_TAKEN);
+ }
+ else if (gimple_code (stmt) == GIMPLE_PREDICT)
{
- case GIMPLE_MODIFY_STMT:
- if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR)
- {
- stmt = GIMPLE_STMT_OPERAND (stmt, 1);
- goto call_expr;
- }
- break;
- case CALL_EXPR:
-call_expr:;
- if (call_expr_flags (stmt) & ECF_NORETURN)
- predict_paths_leading_to (bb, heads, PRED_NORETURN,
- NOT_TAKEN);
- decl = get_callee_fndecl (stmt);
- if (decl
- && lookup_attribute ("cold",
- DECL_ATTRIBUTES (decl)))
- predict_paths_leading_to (bb, heads, PRED_COLD_FUNCTION,
- NOT_TAKEN);
- break;
- default:
- break;
+ predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
+ gimple_predict_outcome (stmt));
+ /* Keep GIMPLE_PREDICT around so early inlining will propagate
+ hints to callers. */
}
}
}
-
- free (heads);
}
#ifdef ENABLE_CHECKING
empty. */
static bool
-assert_is_empty (void *key ATTRIBUTE_UNUSED, void **value,
+assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
void *data ATTRIBUTE_UNUSED)
{
gcc_assert (!*value);
}
#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;
-
- 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
- && TREE_CODE (last_stmt (e->dest)) == RETURN_EXPR)
- {
- edge e1;
- edge_iterator ei1;
+ tree_estimate_probability_bb (bb);
- 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))
- {
- block_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 = bsi_start (e->dest); !bsi_end_p (bi);
- bsi_next (&bi))
- {
- tree stmt = bsi_stmt (bi);
- if ((TREE_CODE (stmt) == CALL_EXPR
- || (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1))
- == CALL_EXPR))
- /* Constant and pure calls are hardly used to signalize
- something exceptional. */
- && TREE_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);
pointer_map_destroy (bb_predictions);
bb_predictions = NULL;
- strip_builtin_expect ();
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))
- dump_tree_cfg (dump_file, dump_flags);
+ gimple_dump_cfg (dump_file, dump_flags);
if (profile_status == PROFILE_ABSENT)
profile_status = PROFILE_GUESSED;
return 0;
}
\f
-/* Sets branch probabilities according to PREDiction and
- FLAGS. HEADS[bb->index] should be index of basic block in that we
- need to alter branch predictions (i.e. the first of our dominators
- such that we do not post-dominate it) (but we fill this information
- on demand, so -1 may be there in case this was not needed yet). */
+/* Predict edges to successors of CUR whose sources are not postdominated by
+ BB by PRED and recurse to all postdominators. */
static void
-predict_paths_leading_to (basic_block bb, int *heads, enum br_predictor pred,
- enum prediction taken)
+predict_paths_for_bb (basic_block cur, basic_block bb,
+ enum br_predictor pred,
+ enum prediction taken)
{
edge e;
edge_iterator ei;
- int y;
+ basic_block son;
- if (heads[bb->index] == ENTRY_BLOCK)
+ /* We are looking for all edges forming edge cut induced by
+ set of all blocks postdominated by BB. */
+ FOR_EACH_EDGE (e, ei, cur->preds)
+ if (e->src->index >= NUM_FIXED_BLOCKS
+ && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
{
- /* This is first time we need this field in heads array; so
- find first dominator that we do not post-dominate (we are
- using already known members of heads array). */
- basic_block ai = bb;
- basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
- int head;
-
- while (heads[next_ai->index] == ENTRY_BLOCK)
- {
- if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
- break;
- heads[next_ai->index] = ai->index;
- ai = next_ai;
- next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
- }
- if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
- head = next_ai->index;
- else
- head = heads[next_ai->index];
- while (next_ai != bb)
- {
- next_ai = ai;
- ai = BASIC_BLOCK (heads[ai->index]);
- heads[next_ai->index] = head;
- }
+ gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
+ predict_edge_def (e, pred, taken);
}
- y = heads[bb->index];
+ for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
+ son;
+ son = next_dom_son (CDI_POST_DOMINATORS, son))
+ predict_paths_for_bb (son, bb, pred, taken);
+}
- /* Now find the edge that leads to our branch and aply the prediction. */
+/* Sets branch probabilities according to PREDiction and
+ FLAGS. */
- if (y == last_basic_block)
- return;
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (y)->succs)
- if (e->dest->index >= NUM_FIXED_BLOCKS
- && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
- predict_edge_def (e, pred, taken);
+static void
+predict_paths_leading_to (basic_block bb, enum br_predictor pred,
+ enum prediction taken)
+{
+ predict_paths_for_bb (bb, bb, pred, taken);
}
\f
/* This is used to carry information about basic blocks. It is
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;
return flag_guess_branch_prob;
}
-struct tree_opt_pass pass_profile =
+/* Build PREDICT_EXPR. */
+tree
+build_predict_expr (enum br_predictor predictor, enum prediction taken)
+{
+ tree t = build1 (PREDICT_EXPR, void_type_node,
+ build_int_cst (NULL, predictor));
+ SET_PREDICT_EXPR_OUTCOME (t, taken);
+ return t;
+}
+
+const char *
+predictor_name (enum br_predictor predictor)
{
+ return predictor_info[predictor].name;
+}
+
+struct gimple_opt_pass pass_profile =
+{
+ {
+ 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 */
+ 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 */
+ }
+};
+
+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 */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
- 0 /* letter */
+ TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ }
};