/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2000-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "fold-const.h"
+#include "calls.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
+#include "predict.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
#include "basic-block.h"
#include "insn-config.h"
#include "regs.h"
#include "flags.h"
-#include "function.h"
+#include "profile.h"
#include "except.h"
#include "diagnostic-core.h"
#include "recog.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
-#include "predict.h"
#include "coverage.h"
#include "sreal.h"
#include "params.h"
#include "target.h"
#include "cfgloop.h"
-#include "tree-flow.h"
-#include "ggc.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "cgraph.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
#include "tree-pass.h"
#include "tree-scalar-evolution.h"
-#include "cfgloop.h"
-#include "pointer-set.h"
/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
-static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
+static sreal real_almost_one, real_br_prob_base,
real_inv_br_prob_base, real_one_half, real_bb_freq_max;
-/* 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 combine_predictions_for_insn (rtx_insn *, basic_block);
static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
-static bool can_predict_insn_p (const_rtx);
+static bool can_predict_insn_p (const rtx_insn *);
/* Information we hold about each branch predictor.
Filled using information from predict.def. */
static inline bool
maybe_hot_frequency_p (struct function *fun, int freq)
{
- struct cgraph_node *node = cgraph_get_node (fun->decl);
- if (!profile_info || !flag_branch_probabilities)
+ struct cgraph_node *node = cgraph_node::get (fun->decl);
+ if (!profile_info
+ || !opt_for_fn (fun->decl, flag_branch_probabilities))
{
if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
return false;
if (node->frequency == NODE_FREQUENCY_HOT)
return true;
}
- if (profile_status_for_function (fun) == PROFILE_ABSENT)
+ if (profile_status_for_fn (fun) == PROFILE_ABSENT)
return true;
if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
- && freq < (ENTRY_BLOCK_PTR_FOR_FUNCTION (fun)->frequency * 2 / 3))
+ && freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency * 2 / 3))
+ return false;
+ if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
return false;
- if (freq < (ENTRY_BLOCK_PTR_FOR_FUNCTION (fun)->frequency
+ if (freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
return false;
return true;
}
+static gcov_type min_count = -1;
+
+/* Determine the threshold for hot BB counts. */
+
+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;
+ }
+ return min_count;
+}
+
+/* Set the threshold for hot BB counts. */
+
+void
+set_hot_bb_threshold (gcov_type min)
+{
+ min_count = min;
+}
+
/* Return TRUE if frequency FREQ is considered to be hot. */
-static inline bool
+bool
maybe_hot_count_p (struct function *fun, gcov_type count)
{
- if (profile_status_for_function (fun) != PROFILE_READ)
+ if (fun && profile_status_for_fn (fun) != 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 (count >= get_hot_bb_threshold ());
}
/* Return true in case BB can be CPU intensive and should be optimized
maybe_hot_bb_p (struct function *fun, const_basic_block bb)
{
gcc_checking_assert (fun);
- if (profile_status_for_function (fun) == PROFILE_READ)
+ if (profile_status_for_fn (fun) == PROFILE_READ)
return maybe_hot_count_p (fun, bb->count);
return maybe_hot_frequency_p (fun, bb->frequency);
}
-/* Return true if the call can be hot. */
-
-bool
-cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
-{
- if (profile_info && flag_branch_probabilities
- && (edge->count
- <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
- return false;
- if (edge->caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
- || (edge->callee
- && edge->callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED))
- return false;
- if (edge->caller->frequency > NODE_FREQUENCY_UNLIKELY_EXECUTED
- && (edge->callee
- && edge->callee->frequency <= NODE_FREQUENCY_EXECUTED_ONCE))
- return false;
- if (optimize_size)
- return false;
- if (edge->caller->frequency == NODE_FREQUENCY_HOT)
- return true;
- if (edge->caller->frequency == NODE_FREQUENCY_EXECUTED_ONCE
- && edge->frequency < CGRAPH_FREQ_BASE * 3 / 2)
- 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)
+ if (profile_status_for_fn (cfun) == PROFILE_READ)
return maybe_hot_count_p (cfun, e->count);
return maybe_hot_frequency_p (cfun, EDGE_FREQUENCY (e));
}
+/* Return true if profile COUNT and FREQUENCY, or function FUN static
+ node frequency reflects never being executed. */
+
+static bool
+probably_never_executed (struct function *fun,
+ gcov_type count, int frequency)
+{
+ gcc_checking_assert (fun);
+ if (profile_status_for_fn (fun) == PROFILE_READ)
+ {
+ int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
+ if (count * unlikely_count_fraction >= profile_info->runs)
+ return false;
+ if (!frequency)
+ return true;
+ if (!ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency)
+ return false;
+ if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
+ {
+ gcov_type computed_count;
+ /* Check for possibility of overflow, in which case entry bb count
+ is large enough to do the division first without losing much
+ precision. */
+ if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count < REG_BR_PROB_BASE *
+ REG_BR_PROB_BASE)
+ {
+ gcov_type scaled_count
+ = frequency * ENTRY_BLOCK_PTR_FOR_FN (fun)->count *
+ unlikely_count_fraction;
+ computed_count = RDIV (scaled_count,
+ ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
+ }
+ else
+ {
+ computed_count = RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun)->count,
+ ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
+ computed_count *= frequency * unlikely_count_fraction;
+ }
+ if (computed_count >= profile_info->runs)
+ return false;
+ }
+ return true;
+ }
+ if ((!profile_info || !(opt_for_fn (fun->decl, flag_branch_probabilities)))
+ && (cgraph_node::get (fun->decl)->frequency
+ == NODE_FREQUENCY_UNLIKELY_EXECUTED))
+ return true;
+ return false;
+}
+
/* Return true in case BB is probably never executed. */
bool
probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
{
- gcc_checking_assert (fun);
- if (profile_info && flag_branch_probabilities)
- return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
- if ((!profile_info || !flag_branch_probabilities)
- && (cgraph_get_node (fun->decl)->frequency
- == NODE_FREQUENCY_UNLIKELY_EXECUTED))
- return true;
- return false;
+ return probably_never_executed (fun, bb->count, bb->frequency);
}
-/* Return true if NODE should be optimized for size. */
+
+/* Return true in case edge E is probably never executed. */
bool
-cgraph_optimize_for_size_p (struct cgraph_node *node)
+probably_never_executed_edge_p (struct function *fun, edge e)
{
- if (optimize_size)
- return true;
- if (node && (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED))
- return true;
- else
- return false;
+ return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e));
}
/* Return true when current function should always be optimized for size. */
bool
optimize_function_for_size_p (struct function *fun)
{
- if (optimize_size)
- return true;
if (!fun || !fun->decl)
- return false;
- return cgraph_optimize_for_size_p (cgraph_get_node (fun->decl));
+ return optimize_size;
+ cgraph_node *n = cgraph_node::get (fun->decl);
+ return n && n->optimize_for_size_p ();
}
/* Return true when current function should always be optimized for speed. */
bool
optimize_bb_for_size_p (const_basic_block bb)
{
- return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (cfun, bb);
+ return (optimize_function_for_size_p (cfun)
+ || (bb && !maybe_hot_bb_p (cfun, bb)));
}
/* Return TRUE when BB should be optimized for speed. */
bool
predictable_edge_p (edge e)
{
- if (profile_status == PROFILE_ABSENT)
+ if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
return false;
if ((e->probability
<= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
return false;
}
-/* This map contains for a basic block the list of predictions for the
- outgoing edges. */
-
-static struct pointer_map_t *bb_predictions;
-
/* Structure representing predictions in tree level. */
struct edge_prediction {
int ep_probability;
};
+/* This map contains for a basic block the list of predictions for the
+ outgoing edges. */
+
+static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
+
/* Return true if the one of outgoing edges is already predicted by
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);
+ edge_prediction **preds = bb_predictions->get (bb);
if (!preds)
return false;
- for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
+ for (i = *preds; i; i = i->ep_next)
if (i->ep_predictor == predictor)
return true;
return false;
static bool
probability_reliable_p (int prob)
{
- return (profile_status == PROFILE_READ
- || (profile_status == PROFILE_GUESSED
+ return (profile_status_for_fn (cfun) == PROFILE_READ
+ || (profile_status_for_fn (cfun) == PROFILE_GUESSED
&& (prob <= HITRATE (1) || prob >= HITRATE (99))));
}
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)));
+ return probability_reliable_p (XINT (note, 0));
}
static void
-predict_insn (rtx insn, enum br_predictor predictor, int probability)
+predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
{
gcc_assert (any_condjump_p (insn));
if (!flag_guess_branch_prob)
/* Predict insn by given predictor. */
void
-predict_insn_def (rtx insn, enum br_predictor predictor,
+predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
enum prediction taken)
{
int probability = predictor_info[(int) predictor].hitrate;
void
rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
{
- rtx last_insn;
+ rtx_insn *last_insn;
last_insn = BB_END (e->src);
/* We can store the branch prediction information only about
void
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)
+ gcc_assert (profile_status_for_fn (cfun) != PROFILE_GUESSED);
+ if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && EDGE_COUNT (e->src->succs) >
+ 1)
&& flag_guess_branch_prob && optimize)
{
struct edge_prediction *i = XNEW (struct edge_prediction);
- void **preds = pointer_map_insert (bb_predictions, e->src);
+ edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
- i->ep_next = (struct edge_prediction *) *preds;
- *preds = i;
+ i->ep_next = preds;
+ preds = i;
i->ep_probability = probability;
i->ep_predictor = predictor;
i->ep_edge = e;
void
remove_predictions_associated_with_edge (edge e)
{
- void **preds;
-
if (!bb_predictions)
return;
- preds = pointer_map_contains (bb_predictions, e->src);
+ edge_prediction **preds = bb_predictions->get (e->src);
if (preds)
{
- struct edge_prediction **prediction = (struct edge_prediction **) preds;
+ struct edge_prediction **prediction = preds;
struct edge_prediction *next;
while (*prediction)
static void
clear_bb_predictions (basic_block bb)
{
- void **preds = pointer_map_contains (bb_predictions, bb);
+ edge_prediction **preds = bb_predictions->get (bb);
struct edge_prediction *pred, *next;
if (!preds)
return;
- for (pred = (struct edge_prediction *) *preds; pred; pred = next)
+ for (pred = *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 (const_rtx insn)
+can_predict_insn_p (const rtx_insn *insn)
{
return (JUMP_P (insn)
&& any_condjump_p (insn)
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_BR_PROB)
- XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
+ XINT (note, 0) = REG_BR_PROB_BASE - XINT (note, 0);
else if (REG_NOTE_KIND (note) == REG_BR_PRED)
XEXP (XEXP (note, 0), 1)
= GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
if (bb->count)
{
- fprintf (file, " exec ");
- fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
+ fprintf (file, " exec %" PRId64, bb->count);
if (e)
{
- fprintf (file, " hit ");
- fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
+ fprintf (file, " hit %" PRId64, e->count);
fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
}
}
note if not already present. Remove now useless REG_BR_PRED notes. */
static void
-combine_predictions_for_insn (rtx insn, basic_block bb)
+combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
{
rtx prob_note;
rtx *pnote;
if (!prob_note)
{
- add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
+ add_int_reg_note (insn, REG_BR_PROB, combined_probability);
/* Save the prediction into CFG in case we are seeing non-degenerated
conditional jump. */
}
else if (!single_succ_p (bb))
{
- int prob = INTVAL (XEXP (prob_note, 0));
+ int prob = XINT (prob_note, 0);
BRANCH_EDGE (bb)->probability = prob;
FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
int nedges = 0;
edge e, first = NULL, second = NULL;
edge_iterator ei;
- void **preds;
FOR_EACH_EDGE (e, ei, bb->succs)
if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
if (dump_file)
fprintf (dump_file, "Predictions for bb %i\n", bb->index);
- preds = pointer_map_contains (bb_predictions, bb);
+ edge_prediction **preds = bb_predictions->get (bb);
if (preds)
{
/* We implement "first match" heuristics and use probability guessed
by predictor with smallest index. */
- for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
+ for (pred = *preds; pred; pred = pred->ep_next)
{
enum br_predictor predictor = pred->ep_predictor;
int probability = pred->ep_probability;
struct edge_prediction *pred2;
int prob = probability;
- for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
+ 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;
return NULL;
else if (TREE_CODE (t1) == SSA_NAME)
ret = t1;
- else if (host_integerp (t1, 0))
- value = tree_low_cst (t1, 0);
+ else if (tree_fits_shwi_p (t1))
+ value = tree_to_shwi (t1);
else
return NULL;
if (!t2)
return ret;
- else if (host_integerp (t2, 0))
- value = tree_low_cst (t2, 0);
+ else if (tree_fits_shwi_p (t2))
+ value = tree_to_shwi (t2);
else if (TREE_CODE (t2) == SSA_NAME)
{
if (ret)
Otherwise return false and set LOOP_INVAIANT to NULL. */
static bool
-is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
+is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
tree *loop_invariant,
enum tree_code *compare_code,
- int *loop_step,
+ tree *loop_step,
tree *loop_iv_base)
{
tree op0, op1, bound, base;
affine_iv iv0, iv1;
enum tree_code code;
- int step;
+ tree step;
code = gimple_cond_code (stmt);
*loop_invariant = NULL;
code = invert_tree_comparison (code, false);
bound = iv0.base;
base = iv1.base;
- if (host_integerp (iv1.step, 0))
- step = tree_low_cst (iv1.step, 0);
+ if (tree_fits_shwi_p (iv1.step))
+ step = iv1.step;
else
return false;
}
{
bound = iv1.base;
base = iv0.base;
- if (host_integerp (iv0.step, 0))
- step = tree_low_cst (iv0.step, 0);
+ if (tree_fits_shwi_p (iv0.step))
+ step = iv0.step;
else
return false;
}
gimple stmt;
tree compare_var, compare_base;
enum tree_code compare_code;
- int compare_step;
+ tree compare_step_var;
edge then_edge;
edge_iterator ei;
stmt = last_stmt (bb);
if (!stmt || gimple_code (stmt) != GIMPLE_COND)
return;
- if (!is_comparison_with_loop_invariant_p (stmt, loop, &compare_var,
+ if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
+ loop, &compare_var,
&compare_code,
- &compare_step,
+ &compare_step_var,
&compare_base))
return;
/* If loop bound, base and compare bound are all constants, we can
calculate the probability directly. */
- if (host_integerp (loop_bound_var, 0)
- && host_integerp (compare_var, 0)
- && host_integerp (compare_base, 0))
+ if (tree_fits_shwi_p (loop_bound_var)
+ && tree_fits_shwi_p (compare_var)
+ && tree_fits_shwi_p (compare_base))
{
int probability;
- HOST_WIDE_INT compare_count;
- HOST_WIDE_INT loop_bound = tree_low_cst (loop_bound_var, 0);
- HOST_WIDE_INT compare_bound = tree_low_cst (compare_var, 0);
- HOST_WIDE_INT base = tree_low_cst (compare_base, 0);
- HOST_WIDE_INT loop_count = (loop_bound - base) / compare_step;
-
- if ((compare_step > 0)
+ bool overflow, overall_overflow = false;
+ widest_int compare_count, tem;
+
+ /* (loop_bound - base) / compare_step */
+ tem = wi::sub (wi::to_widest (loop_bound_var),
+ wi::to_widest (compare_base), SIGNED, &overflow);
+ overall_overflow |= overflow;
+ widest_int loop_count = wi::div_trunc (tem,
+ wi::to_widest (compare_step_var),
+ SIGNED, &overflow);
+ overall_overflow |= overflow;
+
+ if (!wi::neg_p (wi::to_widest (compare_step_var))
^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
- compare_count = (loop_bound - compare_bound) / compare_step;
+ {
+ /* (loop_bound - compare_bound) / compare_step */
+ tem = wi::sub (wi::to_widest (loop_bound_var),
+ wi::to_widest (compare_var), SIGNED, &overflow);
+ overall_overflow |= overflow;
+ compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
+ SIGNED, &overflow);
+ overall_overflow |= overflow;
+ }
else
- compare_count = (compare_bound - base) / compare_step;
-
+ {
+ /* (compare_bound - base) / compare_step */
+ tem = wi::sub (wi::to_widest (compare_var),
+ wi::to_widest (compare_base), SIGNED, &overflow);
+ overall_overflow |= overflow;
+ compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
+ SIGNED, &overflow);
+ overall_overflow |= overflow;
+ }
if (compare_code == LE_EXPR || compare_code == GE_EXPR)
- compare_count ++;
+ ++compare_count;
if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
- loop_count ++;
- if (compare_count < 0)
- compare_count = 0;
- if (loop_count < 0)
- loop_count = 0;
-
+ ++loop_count;
+ if (wi::neg_p (compare_count))
+ compare_count = 0;
+ if (wi::neg_p (loop_count))
+ loop_count = 0;
if (loop_count == 0)
probability = 0;
- else if (compare_count > loop_count)
+ else if (wi::cmps (compare_count, loop_count) == 1)
probability = REG_BR_PROB_BASE;
else
- probability = (double) REG_BR_PROB_BASE * compare_count / loop_count;
- predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+ {
+ tem = compare_count * REG_BR_PROB_BASE;
+ tem = wi::udiv_trunc (tem, loop_count);
+ probability = tem.to_uhwi ();
+ }
+
+ if (!overall_overflow)
+ predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+
return;
}
{
unsigned i;
bool check_value_one;
- gimple phi_stmt;
+ gimple lhs_def_stmt;
+ gphi *phi_stmt;
tree cmp_rhs, cmp_lhs;
- gimple cmp_stmt = last_stmt (exit_edge->src);
+ gimple last;
+ gcond *cmp_stmt;
- if (!cmp_stmt || gimple_code (cmp_stmt) != GIMPLE_COND)
+ last = last_stmt (exit_edge->src);
+ if (!last)
return;
+ cmp_stmt = dyn_cast <gcond *> (last);
+ if (!cmp_stmt)
+ return;
+
cmp_rhs = gimple_cond_rhs (cmp_stmt);
cmp_lhs = gimple_cond_lhs (cmp_stmt);
if (!TREE_CONSTANT (cmp_rhs)
^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
- phi_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
- if (!phi_stmt || gimple_code (phi_stmt) != GIMPLE_PHI)
+ lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
+ if (!lhs_def_stmt)
+ return;
+
+ phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
+ if (!phi_stmt)
return;
for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
static void
predict_loops (void)
{
- loop_iterator li;
struct loop *loop;
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
- FOR_EACH_LOOP (li, loop, 0)
+ FOR_EACH_LOOP (loop, 0)
{
basic_block bb, *bbs;
unsigned j, n_exits;
- VEC (edge, heap) *exits;
+ vec<edge> exits;
struct tree_niter_desc niter_desc;
edge ex;
struct nb_iter_bound *nb_iter;
enum tree_code loop_bound_code = ERROR_MARK;
- int loop_bound_step = 0;
+ tree loop_bound_step = NULL;
tree loop_bound_var = NULL;
tree loop_iv_base = NULL;
- gimple stmt = NULL;
+ gcond *stmt = NULL;
exits = get_loop_exit_edges (loop);
- n_exits = VEC_length (edge, exits);
+ n_exits = exits.length ();
+ if (!n_exits)
+ {
+ exits.release ();
+ continue;
+ }
- FOR_EACH_VEC_ELT (edge, exits, j, ex)
+ FOR_EACH_VEC_ELT (exits, j, ex)
{
tree niter = NULL;
HOST_WIDE_INT nitercst;
predict_extra_loop_exits (ex);
- if (number_of_iterations_exit (loop, ex, &niter_desc, false))
+ if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
niter = niter_desc.niter;
if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
niter = loop_niter_by_eval (loop, ex);
if (TREE_CODE (niter) == INTEGER_CST)
{
- if (host_integerp (niter, 1)
- && compare_tree_int (niter, max-1) == -1)
- nitercst = tree_low_cst (niter, 1) + 1;
+ if (tree_fits_uhwi_p (niter)
+ && max
+ && compare_tree_int (niter, max - 1) == -1)
+ nitercst = tree_to_uhwi (niter) + 1;
else
nitercst = max;
predictor = PRED_LOOP_ITERATIONS;
else
continue;
+ /* If the prediction for number of iterations is zero, do not
+ predict the exit edges. */
+ if (nitercst == 0)
+ continue;
+
probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
predict_edge (ex, predictor, probability);
}
- VEC_free (edge, heap, exits);
+ exits.release ();
/* Find information about loop bound variables. */
for (nb_iter = loop->bounds; nb_iter;
if (nb_iter->stmt
&& gimple_code (nb_iter->stmt) == GIMPLE_COND)
{
- stmt = nb_iter->stmt;
+ stmt = as_a <gcond *> (nb_iter->stmt);
break;
}
if (!stmt && last_stmt (loop->header)
&& gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
- stmt = last_stmt (loop->header);
+ stmt = as_a <gcond *> (last_stmt (loop->header));
if (stmt)
is_comparison_with_loop_invariant_p (stmt, loop,
&loop_bound_var,
if (loop_bound_var)
predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
loop_bound_code,
- loop_bound_step);
+ tree_to_shwi (loop_bound_step));
}
/* Free basic blocks from get_loop_body. */
static void
bb_estimate_probability_locally (basic_block bb)
{
- rtx last_insn = BB_END (bb);
+ rtx_insn *last_insn = BB_END (bb);
rtx cond;
if (! can_predict_insn_p (last_insn))
combine_predictions_for_insn (BB_END (bb), bb);
}
\f
-static tree expr_expected_value (tree, bitmap);
+static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
/* Helper function for expr_expected_value. */
static tree
expr_expected_value_1 (tree type, tree op0, enum tree_code code,
- tree op1, bitmap visited)
+ tree op1, bitmap visited, enum br_predictor *predictor)
{
gimple def;
+ if (predictor)
+ *predictor = PRED_UNCONDITIONAL;
+
if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
{
if (TREE_CONSTANT (op0))
for (i = 0; i < n; i++)
{
tree arg = PHI_ARG_DEF (def, i);
+ enum br_predictor predictor2;
/* If this PHI has itself as an argument, we cannot
determine the string length of this argument. However,
if (arg == PHI_RESULT (def))
continue;
- new_val = expr_expected_value (arg, visited);
+ new_val = expr_expected_value (arg, visited, &predictor2);
+
+ /* It is difficult to combine value predictors. Simply assume
+ that later predictor is weaker and take its prediction. */
+ if (predictor && *predictor < predictor2)
+ *predictor = predictor2;
if (!new_val)
return NULL;
if (!val)
gimple_assign_rhs1 (def),
gimple_assign_rhs_code (def),
gimple_assign_rhs2 (def),
- visited);
+ visited, predictor);
}
if (is_gimple_call (def))
{
tree decl = gimple_call_fndecl (def);
if (!decl)
- return NULL;
+ {
+ if (gimple_call_internal_p (def)
+ && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
+ {
+ gcc_assert (gimple_call_num_args (def) == 3);
+ 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);
+ }
+ return gimple_call_arg (def, 1);
+ }
+ return NULL;
+ }
if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
switch (DECL_FUNCTION_CODE (decl))
{
val = gimple_call_arg (def, 0);
if (TREE_CONSTANT (val))
return val;
+ if (predictor)
+ *predictor = PRED_BUILTIN_EXPECT;
return gimple_call_arg (def, 1);
}
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;
return boolean_true_node;
+ default:
+ break;
}
}
if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
{
tree res;
- op0 = expr_expected_value (op0, visited);
+ enum br_predictor predictor2;
+ op0 = expr_expected_value (op0, visited, predictor);
if (!op0)
return NULL;
- op1 = expr_expected_value (op1, visited);
+ op1 = expr_expected_value (op1, visited, &predictor2);
+ if (predictor && *predictor < predictor2)
+ *predictor = predictor2;
if (!op1)
return NULL;
res = fold_build2 (code, type, op0, op1);
if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
{
tree res;
- op0 = expr_expected_value (op0, visited);
+ op0 = expr_expected_value (op0, visited, predictor);
if (!op0)
return NULL;
res = fold_build1 (code, type, op0);
implementation. */
static tree
-expr_expected_value (tree expr, bitmap visited)
+expr_expected_value (tree expr, bitmap visited,
+ enum br_predictor *predictor)
{
enum tree_code code;
tree op0, op1;
if (TREE_CONSTANT (expr))
- return expr;
+ {
+ if (predictor)
+ *predictor = PRED_UNCONDITIONAL;
+ 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 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)
- {
- gimple_stmt_iterator bi;
- for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
- {
- gimple stmt = gsi_stmt (bi);
-
- if (gimple_code (stmt) == GIMPLE_PREDICT)
- {
- 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);
- if (var)
- {
- ass_stmt
- = gimple_build_assign (var, gimple_call_arg (stmt, 0));
- gsi_replace (&bi, ass_stmt, true);
- }
- else
- {
- gsi_remove (&bi, true);
- continue;
- }
- }
- }
- gsi_next (&bi);
- }
- }
- return 0;
+ op0, code, op1, visited, predictor);
}
\f
/* Predict using opcode of the last statement in basic block. */
enum tree_code cmp;
bitmap visited;
edge_iterator ei;
+ enum br_predictor predictor;
if (!stmt || gimple_code (stmt) != GIMPLE_COND)
return;
cmp = gimple_cond_code (stmt);
type = TREE_TYPE (op0);
visited = BITMAP_ALLOC (NULL);
- val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
+ val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited,
+ &predictor);
BITMAP_FREE (visited);
- if (val)
+ if (val && TREE_CODE (val) == INTEGER_CST)
{
- if (integer_zerop (val))
- predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
+ 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, PRED_BUILTIN_EXPECT, TAKEN);
- return;
+ predict_edge (then_edge, predictor,
+ integer_zerop (val) ? NOT_TAKEN : TAKEN);
}
/* Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
static void
apply_return_prediction (void)
{
- gimple return_stmt = NULL;
+ greturn *return_stmt = NULL;
tree return_val;
edge e;
- gimple phi;
+ gphi *phi;
int phi_num_args, i;
enum br_predictor pred;
enum prediction direction;
edge_iterator ei;
- FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
{
- return_stmt = last_stmt (e->src);
- if (return_stmt
- && gimple_code (return_stmt) == GIMPLE_RETURN)
- break;
+ gimple last = last_stmt (e->src);
+ if (last
+ && gimple_code (last) == GIMPLE_RETURN)
+ {
+ return_stmt = as_a <greturn *> (last);
+ break;
+ }
}
if (!e)
return;
|| !SSA_NAME_DEF_STMT (return_val)
|| gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
return;
- phi = SSA_NAME_DEF_STMT (return_val);
+ phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
phi_num_args = gimple_phi_num_args (phi);
pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
edge e;
edge_iterator ei;
- FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
{
has_return_edges = true;
apply_return_prediction ();
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
gimple_stmt_iterator gsi;
#ifdef ENABLE_CHECKING
-/* Callback for pointer_map_traverse, asserts that the pointer map is
+/* Callback for hash_map::traverse, asserts that the pointer map is
empty. */
-static bool
-assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
- void *data ATTRIBUTE_UNUSED)
+bool
+assert_is_empty (const_basic_block const &, edge_prediction *const &value,
+ void *)
{
- gcc_assert (!*value);
+ gcc_assert (!value);
return false;
}
#endif
FOR_EACH_EDGE (e, ei, bb->succs)
{
/* Predict edges to user labels with attributes. */
- if (e->dest != EXIT_BLOCK_PTR)
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
{
gimple_stmt_iterator gi;
for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
{
- gimple stmt = gsi_stmt (gi);
+ glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi));
tree decl;
- if (gimple_code (stmt) != GIMPLE_LABEL)
+ if (!label_stmt)
break;
- decl = gimple_label_label (stmt);
+ decl = gimple_label_label (label_stmt);
if (DECL_ARTIFICIAL (decl))
continue;
return_block:
return_stmt. */
if (e->dest != bb->next_bb
- && e->dest != EXIT_BLOCK_PTR
+ && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
&& single_succ_p (e->dest)
- && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
+ && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
&& (last = last_stmt (e->dest)) != NULL
&& gimple_code (last) == GIMPLE_RETURN)
{
/* 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
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
&& dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
{
create_preheaders (CP_SIMPLE_PREHEADERS);
calculate_dominance_info (CDI_POST_DOMINATORS);
- bb_predictions = pointer_map_create ();
+ bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
tree_bb_level_predictions ();
record_loop_exits ();
- if (number_of_loops () > 1)
+ if (number_of_loops (cfun) > 1)
predict_loops ();
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
tree_estimate_probability_bb (bb);
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
combine_predictions_for_bb (bb);
#ifdef ENABLE_CHECKING
- pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
+ bb_predictions->traverse<void *, assert_is_empty> (NULL);
#endif
- pointer_map_destroy (bb_predictions);
+ delete bb_predictions;
bb_predictions = NULL;
- estimate_bb_frequencies ();
+ estimate_bb_frequencies (false);
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 (LOOPS_NORMAL);
- 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);
- if (profile_status == PROFILE_ABSENT)
- profile_status = PROFILE_GUESSED;
- return 0;
-}
\f
/* Predict edges to successors of CUR whose sources are not postdominated by
BB by PRED and recurse to all postdominators. */
/* This is used to carry information about basic blocks. It is
attached to the AUX field of the standard CFG block. */
-typedef struct block_info_def
+struct block_info
{
/* Estimated frequency of execution of basic_block. */
sreal frequency;
/* Number of predecessors we need to visit first. */
int npredecessors;
-} *block_info;
+};
/* Similar information for edges. */
-typedef struct edge_info_def
+struct edge_prob_info
{
/* 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
sreal back_edge_prob;
/* True if the edge is a loopback edge in the natural loop. */
unsigned int back_edge:1;
-} *edge_info;
+};
-#define BLOCK_INFO(B) ((block_info) (B)->aux)
-#define EDGE_INFO(E) ((edge_info) (E)->aux)
+#define BLOCK_INFO(B) ((block_info *) (B)->aux)
+#undef EDGE_INFO
+#define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
/* Helper function for estimate_bb_frequencies.
Propagate the frequencies in blocks marked in
edge_iterator ei;
int count = 0;
- bb = BASIC_BLOCK (i);
+ bb = BASIC_BLOCK_FOR_FN (cfun, i);
FOR_EACH_EDGE (e, ei, bb->preds)
{
}
BLOCK_INFO (bb)->npredecessors = count;
/* When function never returns, we will never process exit block. */
- if (!count && bb == EXIT_BLOCK_PTR)
+ if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
bb->count = bb->frequency = 0;
}
- memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
+ BLOCK_INFO (head)->frequency = 1;
last = head;
for (bb = head; bb; bb = nextbb)
{
edge_iterator ei;
- sreal cyclic_probability, frequency;
-
- memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
- memcpy (&frequency, &real_zero, sizeof (real_zero));
+ sreal cyclic_probability = 0;
+ sreal frequency = 0;
nextbb = BLOCK_INFO (bb)->next;
BLOCK_INFO (bb)->next = NULL;
FOR_EACH_EDGE (e, ei, bb->preds)
if (EDGE_INFO (e)->back_edge)
{
- sreal_add (&cyclic_probability, &cyclic_probability,
- &EDGE_INFO (e)->back_edge_prob);
+ cyclic_probability += EDGE_INFO (e)->back_edge_prob;
}
else if (!(e->flags & EDGE_DFS_BACK))
{
- sreal tmp;
-
/* frequency += (e->probability
* BLOCK_INFO (e->src)->frequency /
REG_BR_PROB_BASE); */
- sreal_init (&tmp, e->probability, 0);
- sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
- sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
- sreal_add (&frequency, &frequency, &tmp);
+ sreal tmp = e->probability;
+ tmp *= BLOCK_INFO (e->src)->frequency;
+ tmp *= real_inv_br_prob_base;
+ frequency += tmp;
}
- if (sreal_compare (&cyclic_probability, &real_zero) == 0)
+ if (cyclic_probability == 0)
{
- memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
- sizeof (frequency));
+ BLOCK_INFO (bb)->frequency = frequency;
}
else
{
- if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
- {
- memcpy (&cyclic_probability, &real_almost_one,
- sizeof (real_almost_one));
- }
+ if (cyclic_probability > real_almost_one)
+ cyclic_probability = real_almost_one;
/* BLOCK_INFO (bb)->frequency = frequency
/ (1 - cyclic_probability) */
- sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
- sreal_div (&BLOCK_INFO (bb)->frequency,
- &frequency, &cyclic_probability);
+ cyclic_probability = sreal (1) - cyclic_probability;
+ BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
}
}
e = find_edge (bb, head);
if (e)
{
- sreal tmp;
-
/* EDGE_INFO (e)->back_edge_prob
= ((e->probability * BLOCK_INFO (bb)->frequency)
/ REG_BR_PROB_BASE); */
- sreal_init (&tmp, e->probability, 0);
- sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
- sreal_mul (&EDGE_INFO (e)->back_edge_prob,
- &tmp, &real_inv_br_prob_base);
+ sreal tmp = e->probability;
+ tmp *= BLOCK_INFO (bb)->frequency;
+ EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
}
/* Propagate to successor blocks. */
}
}
-/* Estimate probabilities of loopback edges in loops at same nest level. */
+/* Estimate frequencies in loops at same nest level. */
static void
estimate_loops_at_level (struct loop *first_loop)
basic_block bb;
/* Start by estimating the frequencies in the loops. */
- if (number_of_loops () > 1)
+ if (number_of_loops (cfun) > 1)
estimate_loops_at_level (current_loops->tree_root->inner);
/* Now propagate the frequencies through all the blocks. */
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, cfun)
{
bitmap_set_bit (tovisit, bb->index);
}
- propagate_freq (ENTRY_BLOCK_PTR, tovisit);
+ propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
BITMAP_FREE (tovisit);
}
+/* Drop the profile for NODE to guessed, and update its frequency based on
+ whether it is expected to be hot given the CALL_COUNT. */
+
+static void
+drop_profile (struct cgraph_node *node, gcov_type call_count)
+{
+ struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
+ /* In the case where this was called by another function with a
+ dropped profile, call_count will be 0. Since there are no
+ non-zero call counts to this function, we don't know for sure
+ whether it is hot, and therefore it will be marked normal below. */
+ bool hot = maybe_hot_count_p (NULL, call_count);
+
+ if (dump_file)
+ fprintf (dump_file,
+ "Dropping 0 profile for %s/%i. %s based on calls.\n",
+ node->name (), node->order,
+ hot ? "Function is hot" : "Function is normal");
+ /* We only expect to miss profiles for functions that are reached
+ via non-zero call edges in cases where the function may have
+ been linked from another module or library (COMDATs and extern
+ templates). See the comments below for handle_missing_profiles.
+ Also, only warn in cases where the missing counts exceed the
+ number of training runs. In certain cases with an execv followed
+ by a no-return call the profile for the no-return call is not
+ dumped and there can be a mismatch. */
+ if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
+ && call_count > profile_info->runs)
+ {
+ if (flag_profile_correction)
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ "Missing counts for called function %s/%i\n",
+ node->name (), node->order);
+ }
+ else
+ warning (0, "Missing counts for called function %s/%i",
+ node->name (), node->order);
+ }
+
+ profile_status_for_fn (fn)
+ = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
+ node->frequency
+ = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
+}
+
+/* In the case of COMDAT routines, multiple object files will contain the same
+ function and the linker will select one for the binary. In that case
+ all the other copies from the profile instrument binary will be missing
+ profile counts. Look for cases where this happened, due to non-zero
+ call counts going to 0-count functions, and drop the profile to guessed
+ so that we can use the estimated probabilities and avoid optimizing only
+ for size.
+
+ The other case where the profile may be missing is when the routine
+ is not going to be emitted to the object file, e.g. for "extern template"
+ class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
+ all other cases of non-zero calls to 0-count functions. */
+
+void
+handle_missing_profiles (void)
+{
+ struct cgraph_node *node;
+ int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
+ vec<struct cgraph_node *> worklist;
+ worklist.create (64);
+
+ /* See if 0 count function has non-0 count callers. In this case we
+ lost some profile. Drop its function profile to PROFILE_GUESSED. */
+ FOR_EACH_DEFINED_FUNCTION (node)
+ {
+ struct cgraph_edge *e;
+ gcov_type call_count = 0;
+ gcov_type max_tp_first_run = 0;
+ struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
+
+ if (node->count)
+ continue;
+ for (e = node->callers; e; e = e->next_caller)
+ {
+ call_count += e->count;
+
+ if (e->caller->tp_first_run > max_tp_first_run)
+ max_tp_first_run = e->caller->tp_first_run;
+ }
+
+ /* If time profile is missing, let assign the maximum that comes from
+ caller functions. */
+ if (!node->tp_first_run && max_tp_first_run)
+ node->tp_first_run = max_tp_first_run + 1;
+
+ if (call_count
+ && fn && fn->cfg
+ && (call_count * unlikely_count_fraction >= profile_info->runs))
+ {
+ drop_profile (node, call_count);
+ worklist.safe_push (node);
+ }
+ }
+
+ /* Propagate the profile dropping to other 0-count COMDATs that are
+ potentially called by COMDATs we already dropped the profile on. */
+ while (worklist.length () > 0)
+ {
+ struct cgraph_edge *e;
+
+ node = worklist.pop ();
+ for (e = node->callees; e; e = e->next_caller)
+ {
+ struct cgraph_node *callee = e->callee;
+ struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
+
+ if (callee->count > 0)
+ continue;
+ if (DECL_COMDAT (callee->decl) && fn && fn->cfg
+ && profile_status_for_fn (fn) == PROFILE_READ)
+ {
+ drop_profile (node, 0);
+ worklist.safe_push (callee);
+ }
+ }
+ }
+ worklist.release ();
+}
+
/* Convert counts measured by profile driven feedback to frequencies.
Return nonzero iff there was any nonzero execution count. */
gcov_type count_max, true_count_max = 0;
basic_block bb;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ /* Don't overwrite the estimated frequencies when the profile for
+ the function is missing. We may drop this function PROFILE_GUESSED
+ later in drop_profile (). */
+ if (!flag_auto_profile && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
+ return 0;
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
true_count_max = MAX (bb->count, true_count_max);
count_max = MAX (true_count_max, 1);
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
return true_count_max;
/* Frequencies are out of range. This either means that function contains
internal loop executing more than BB_FREQ_MAX times or profile feedback
is available and function has not been executed at all. */
- if (ENTRY_BLOCK_PTR->frequency == 0)
+ if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency == 0)
return true;
/* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
- limit = ENTRY_BLOCK_PTR->frequency * threshold;
- FOR_EACH_BB (bb)
+ limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency * threshold;
+ FOR_EACH_BB_FN (bb, cfun)
{
- rtx insn;
+ rtx_insn *insn;
- for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
- insn = NEXT_INSN (insn))
+ FOR_BB_INSNS (bb, insn)
if (active_insn_p (insn))
{
sum += bb->frequency;
return false;
}
-/* Estimate basic blocks frequency by given branch probabilities. */
+/* Estimate and propagate basic block frequencies using the given branch
+ probabilities. If FORCE is true, the frequencies are used to estimate
+ the counts even when there are already non-zero profile counts. */
void
-estimate_bb_frequencies (void)
+estimate_bb_frequencies (bool force)
{
basic_block bb;
sreal freq_max;
- if (profile_status != PROFILE_READ || !counts_to_freqs ())
+ if (force || profile_status_for_fn (cfun) != PROFILE_READ || !counts_to_freqs ())
{
static int real_values_initialized = 0;
if (!real_values_initialized)
{
real_values_initialized = 1;
- sreal_init (&real_zero, 0, 0);
- sreal_init (&real_one, 1, 0);
- sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
- sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
- sreal_init (&real_one_half, 1, -1);
- sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
- sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
+ real_br_prob_base = REG_BR_PROB_BASE;
+ real_bb_freq_max = BB_FREQ_MAX;
+ real_one_half = sreal (1, -1);
+ real_inv_br_prob_base = sreal (1) / real_br_prob_base;
+ real_almost_one = sreal (1) - real_inv_br_prob_base;
}
mark_dfs_back_edges ();
- single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
+ single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
+ REG_BR_PROB_BASE;
/* Set up block info for each basic block. */
- alloc_aux_for_blocks (sizeof (struct block_info_def));
- alloc_aux_for_edges (sizeof (struct edge_info_def));
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ alloc_aux_for_blocks (sizeof (block_info));
+ alloc_aux_for_edges (sizeof (edge_prob_info));
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
- sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
- sreal_mul (&EDGE_INFO (e)->back_edge_prob,
- &EDGE_INFO (e)->back_edge_prob,
- &real_inv_br_prob_base);
+ EDGE_INFO (e)->back_edge_prob = e->probability;
+ EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
}
}
- /* First compute probabilities locally for each loop from innermost
- to outermost to examine probabilities for back edges. */
+ /* First compute frequencies locally for each loop from innermost
+ to outermost to examine frequencies for back edges. */
estimate_loops ();
- memcpy (&freq_max, &real_zero, sizeof (real_zero));
- FOR_EACH_BB (bb)
- if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
- memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
+ freq_max = 0;
+ FOR_EACH_BB_FN (bb, cfun)
+ if (freq_max < BLOCK_INFO (bb)->frequency)
+ freq_max = BLOCK_INFO (bb)->frequency;
- sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ freq_max = real_bb_freq_max / freq_max;
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
{
- sreal tmp;
-
- sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
- sreal_add (&tmp, &tmp, &real_one_half);
- bb->frequency = sreal_to_int (&tmp);
+ sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
+ bb->frequency = tmp.to_int ();
}
free_aux_for_blocks ();
compute_function_frequency (void)
{
basic_block bb;
- struct cgraph_node *node = cgraph_get_node (current_function_decl);
+ struct cgraph_node *node = cgraph_node::get (current_function_decl);
+
if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
|| MAIN_NAME_P (DECL_NAME (current_function_decl)))
node->only_called_at_startup = true;
if (DECL_STATIC_DESTRUCTOR (current_function_decl))
node->only_called_at_exit = true;
- if (!profile_info || !flag_branch_probabilities)
+ if (profile_status_for_fn (cfun) != PROFILE_READ)
{
int flags = flags_from_decl_or_type (current_function_decl);
if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
return;
}
- node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
- FOR_EACH_BB (bb)
+
+ /* Only first time try to drop function into unlikely executed.
+ After inlining the roundoff errors may confuse us.
+ Ipa-profile pass will drop functions only called from unlikely
+ functions to unlikely and that is most of what we care about. */
+ if (!cfun->after_inlining)
+ node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
+ FOR_EACH_BB_FN (bb, cfun)
{
if (maybe_hot_bb_p (cfun, bb))
{
}
}
-static bool
-gate_estimate_probability (void)
-{
- return flag_guess_branch_prob;
-}
-
/* Build PREDICT_EXPR. */
tree
build_predict_expr (enum br_predictor predictor, enum prediction taken)
return predictor_info[predictor].name;
}
-struct gimple_opt_pass pass_profile =
-{
- {
- GIMPLE_PASS,
- "profile_estimate", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_estimate_probability, /* gate */
- 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 */
- }
+/* Predict branch probabilities and estimate profile of the tree CFG. */
+
+namespace {
+
+const pass_data pass_data_profile =
+{
+ GIMPLE_PASS, /* type */
+ "profile_estimate", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_BRANCH_PROB, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
};
-struct gimple_opt_pass pass_strip_predict_hints =
-{
- {
- GIMPLE_PASS,
- "*strip_predict_hints", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- 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 */
- }
+class pass_profile : public gimple_opt_pass
+{
+public:
+ pass_profile (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_profile, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_guess_branch_prob; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_profile
+
+unsigned int
+pass_profile::execute (function *fun)
+{
+ unsigned nb_loops;
+
+ if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
+ return 0;
+
+ loop_optimizer_init (LOOPS_NORMAL);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ flow_loops_dump (dump_file, NULL, 0);
+
+ mark_irreducible_loops ();
+
+ nb_loops = number_of_loops (fun);
+ 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);
+ if (profile_status_for_fn (fun) == PROFILE_ABSENT)
+ profile_status_for_fn (fun) = PROFILE_GUESSED;
+ return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_profile (gcc::context *ctxt)
+{
+ return new pass_profile (ctxt);
+}
+
+namespace {
+
+const pass_data pass_data_strip_predict_hints =
+{
+ GIMPLE_PASS, /* type */
+ "*strip_predict_hints", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_BRANCH_PROB, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
};
+class pass_strip_predict_hints : public gimple_opt_pass
+{
+public:
+ pass_strip_predict_hints (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
+ virtual unsigned int execute (function *);
+
+}; // class pass_strip_predict_hints
+
+/* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
+ we no longer need. */
+unsigned int
+pass_strip_predict_hints::execute (function *fun)
+{
+ basic_block bb;
+ gimple ass_stmt;
+ tree var;
+
+ FOR_EACH_BB_FN (bb, fun)
+ {
+ gimple_stmt_iterator bi;
+ for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
+ {
+ gimple stmt = gsi_stmt (bi);
+
+ if (gimple_code (stmt) == GIMPLE_PREDICT)
+ {
+ gsi_remove (&bi, true);
+ continue;
+ }
+ else if (is_gimple_call (stmt))
+ {
+ 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)
+ || (gimple_call_internal_p (stmt)
+ && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
+ {
+ var = gimple_call_lhs (stmt);
+ if (var)
+ {
+ ass_stmt
+ = gimple_build_assign (var, gimple_call_arg (stmt, 0));
+ gsi_replace (&bi, ass_stmt, true);
+ }
+ else
+ {
+ gsi_remove (&bi, true);
+ continue;
+ }
+ }
+ }
+ gsi_next (&bi);
+ }
+ }
+ return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_strip_predict_hints (gcc::context *ctxt)
+{
+ return new pass_strip_predict_hints (ctxt);
+}
+
/* Rebuild function frequencies. Passes are in general expected to
maintain profile by hand, however in some cases this is not possible:
for example when inlining several functions with loops freuqencies might run
rebuild_frequencies (void)
{
timevar_push (TV_REBUILD_FREQUENCIES);
- if (profile_status == PROFILE_GUESSED)
+
+ /* When the max bb count in the function is small, there is a higher
+ chance that there were truncation errors in the integer scaling
+ of counts by inlining and other optimizations. This could lead
+ to incorrect classification of code as being cold when it isn't.
+ In that case, force the estimation of bb counts/frequencies from the
+ branch probabilities, rather than computing frequencies from counts,
+ which may also lead to frequencies incorrectly reduced to 0. There
+ is less precision in the probabilities, so we only do this for small
+ max counts. */
+ gcov_type count_max = 0;
+ basic_block bb;
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
+ count_max = MAX (bb->count, count_max);
+
+ if (profile_status_for_fn (cfun) == PROFILE_GUESSED
+ || (!flag_auto_profile && profile_status_for_fn (cfun) == PROFILE_READ
+ && count_max < REG_BR_PROB_BASE/10))
{
loop_optimizer_init (0);
add_noreturn_fake_exit_edges ();
mark_irreducible_loops ();
connect_infinite_loops_to_exit ();
- estimate_bb_frequencies ();
+ estimate_bb_frequencies (true);
remove_fake_exit_edges ();
loop_optimizer_finalize ();
}
- else if (profile_status == PROFILE_READ)
+ else if (profile_status_for_fn (cfun) == PROFILE_READ)
counts_to_freqs ();
else
gcc_unreachable ();
projects / gcc.git / blobdiff