/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000-2014 Free Software Foundation, Inc.
+ Copyright (C) 2000-2016 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "tree.h"
-#include "calls.h"
+#include "backend.h"
#include "rtl.h"
-#include "tm_p.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
-#include "insn-config.h"
-#include "regs.h"
-#include "flags.h"
-#include "function.h"
-#include "except.h"
-#include "diagnostic-core.h"
-#include "recog.h"
-#include "expr.h"
-#include "predict.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "emit-rtl.h"
+#include "cgraph.h"
#include "coverage.h"
+#include "diagnostic-core.h"
+#include "gimple-predict.h"
+#include "fold-const.h"
+#include "calls.h"
+#include "cfganal.h"
+#include "profile.h"
#include "sreal.h"
#include "params.h"
-#include "target.h"
#include "cfgloop.h"
-#include "hash-map.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
-#include "gimple-expr.h"
-#include "is-a.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"
/* 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;
static void combine_predictions_for_insn (rtx_insn *, basic_block);
maybe_hot_frequency_p (struct function *fun, int freq)
{
struct cgraph_node *node = cgraph_node::get (fun->decl);
- if (!profile_info || !flag_branch_probabilities)
+ if (!profile_info
+ || !opt_for_fn (fun->decl, flag_branch_probabilities))
{
if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
return false;
/* 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 (fun && profile_status_for_fn (fun) != PROFILE_READ)
return maybe_hot_frequency_p (fun, bb->frequency);
}
-/* Return true if the call can be hot. */
-
-bool
-cgraph_edge::maybe_hot_p (void)
-{
- if (profile_info && flag_branch_probabilities
- && !maybe_hot_count_p (NULL, count))
- return false;
- if (caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
- || (callee
- && callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED))
- return false;
- if (caller->frequency > NODE_FREQUENCY_UNLIKELY_EXECUTED
- && (callee
- && callee->frequency <= NODE_FREQUENCY_EXECUTED_ONCE))
- return false;
- if (optimize_size)
- return false;
- if (caller->frequency == NODE_FREQUENCY_HOT)
- return true;
- if (caller->frequency == NODE_FREQUENCY_EXECUTED_ONCE
- && frequency < CGRAPH_FREQ_BASE * 3 / 2)
- return false;
- if (flag_guess_branch_prob)
- {
- if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0
- || 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. */
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. */
gcov_type count, int frequency)
{
gcc_checking_assert (fun);
- if (profile_status_for_fn (cfun) == PROFILE_READ)
+ 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 (cfun)->frequency)
+ if (!ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency)
return false;
- if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
+ 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 (cfun)->count < REG_BR_PROB_BASE *
+ 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 (cfun)->count *
+ = frequency * ENTRY_BLOCK_PTR_FOR_FN (fun)->count *
unlikely_count_fraction;
computed_count = RDIV (scaled_count,
- ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency);
+ ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
}
else
{
- computed_count = RDIV (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count,
- ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency);
+ 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 true;
}
- if ((!profile_info || !flag_branch_probabilities)
+ if ((!profile_info || !(opt_for_fn (fun->decl, flag_branch_probabilities)))
&& (cgraph_node::get (fun->decl)->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED))
return true;
return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e));
}
-/* Return true if function should be optimized for size. */
-
-bool
-cgraph_node::optimize_for_size_p (void)
-{
- if (optimize_size)
- return true;
- if (frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
- return true;
- else
- return false;
-}
-
/* 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 optimize_size;
cgraph_node *n = cgraph_node::get (fun->decl);
return n && n->optimize_for_size_p ();
}
return !optimize_function_for_size_p (fun);
}
+/* Return the optimization type that should be used for the function FUN. */
+
+optimization_type
+function_optimization_type (struct function *fun)
+{
+ return (optimize_function_for_speed_p (fun)
+ ? OPTIMIZE_FOR_SPEED
+ : OPTIMIZE_FOR_SIZE);
+}
+
/* Return TRUE when BB should be optimized for size. */
bool
return !optimize_bb_for_size_p (bb);
}
+/* Return the optimization type that should be used for block BB. */
+
+optimization_type
+bb_optimization_type (const_basic_block bb)
+{
+ return (optimize_bb_for_speed_p (bb)
+ ? OPTIMIZE_FOR_SPEED
+ : OPTIMIZE_FOR_SIZE);
+}
+
/* Return TRUE when BB should be optimized for size. */
bool
if (bb->count)
{
- fprintf (file, " exec %"PRId64, bb->count);
+ fprintf (file, " exec %" PRId64, bb->count);
if (e)
{
- fprintf (file, " hit %"PRId64, e->count);
+ fprintf (file, " hit %" PRId64, e->count);
fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
}
}
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,
tree *loop_step,
static bool
expr_coherent_p (tree t1, tree t2)
{
- gimple stmt;
+ gimple *stmt;
tree ssa_name_1 = NULL;
tree ssa_name_2 = NULL;
enum tree_code loop_bound_code,
int loop_bound_step)
{
- gimple stmt;
+ gimple *stmt;
tree compare_var, compare_base;
enum tree_code compare_code;
tree compare_step_var;
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_var,
&compare_base))
{
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++)
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 = exits.length ();
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,
expr_expected_value_1 (tree type, tree op0, enum tree_code code,
tree op1, bitmap visited, enum br_predictor *predictor)
{
- gimple def;
+ gimple *def;
if (predictor)
*predictor = PRED_UNCONDITIONAL;
static void
tree_predict_by_opcode (basic_block bb)
{
- gimple stmt = last_stmt (bb);
+ gimple *stmt = last_stmt (bb);
edge then_edge;
tree op0, op1;
tree type;
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;
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);
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple stmt = gsi_stmt (gsi);
+ gimple *stmt = gsi_stmt (gsi);
tree decl;
if (is_gimple_call (stmt))
}
}
-#ifdef ENABLE_CHECKING
-
/* Callback for hash_map::traverse, asserts that the pointer map is
empty. */
gcc_assert (!value);
return false;
}
-#endif
/* Predict branch probabilities and estimate profile for basic block BB. */
{
edge e;
edge_iterator ei;
- gimple last;
+ gimple *last;
FOR_EACH_EDGE (e, ei, bb->succs)
{
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;
for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
gsi_next (&bi))
{
- gimple stmt = gsi_stmt (bi);
+ gimple *stmt = gsi_stmt (bi);
if (is_gimple_call (stmt)
/* Constant and pure calls are hardly used to signalize
something exceptional. */
FOR_EACH_BB_FN (bb, cfun)
combine_predictions_for_bb (bb);
-#ifdef ENABLE_CHECKING
- bb_predictions->traverse<void *, assert_is_empty> (NULL);
-#endif
+ if (flag_checking)
+ bb_predictions->traverse<void *, assert_is_empty> (NULL);
+
delete bb_predictions;
bb_predictions = NULL;
};
#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.
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;
/* Compute frequency of basic block. */
if (bb != head)
{
-#ifdef ENABLE_CHECKING
- FOR_EACH_EDGE (e, ei, bb->preds)
- gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
- || (e->flags & EDGE_DFS_BACK));
-#endif
+ if (flag_checking)
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
+ || (e->flags & EDGE_DFS_BACK));
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. */
/* 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 (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
+ 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)
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 ();
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;
}
}
to outermost to examine frequencies for back edges. */
estimate_loops ();
- memcpy (&freq_max, &real_zero, sizeof (real_zero));
+ freq_max = 0;
FOR_EACH_BB_FN (bb, cfun)
- if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
- memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
+ if (freq_max < BLOCK_INFO (bb)->frequency)
+ freq_max = BLOCK_INFO (bb)->frequency;
- sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
+ 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 ();
{
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);
pass_strip_predict_hints::execute (function *fun)
{
basic_block bb;
- gimple ass_stmt;
+ 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);
+ gimple *stmt = gsi_stmt (bi);
if (gimple_code (stmt) == GIMPLE_PREDICT)
{
count_max = MAX (bb->count, count_max);
if (profile_status_for_fn (cfun) == PROFILE_GUESSED
- || (profile_status_for_fn (cfun) == PROFILE_READ && count_max < REG_BR_PROB_BASE/10))
+ || (!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 ();
projects / gcc.git / blobdiff