GCC Middle and Back End API Reference
predict.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "ssa.h"
#include "memmodel.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 "cfgloop.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-scalar-evolution.h"
#include "ipa-utils.h"
#include "gimple-pretty-print.h"
#include "selftest.h"
#include "cfgrtl.h"
#include "stringpool.h"
#include "attribs.h"
#include "predict.def"
Include dependency graph for predict.cc:

Data Structures

struct  predictor_info
struct  edge_prediction
struct  predictor_hash
struct  predictor_hash_traits
class  block_info
class  edge_prob_info


#define HITRATE(VAL)   ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
#define BLOCK_INFO(B)   ((block_info *) (B)->aux)
#define EDGE_INFO(E)   ((edge_prob_info *) (E)->aux)




static void combine_predictions_for_insn (rtx_insn *, basic_block)
static void dump_prediction (FILE *, enum br_predictor, int, basic_block, enum predictor_reason, edge)
static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction, class loop *in_loop=NULL)
static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction, class loop *in_loop=NULL)
static bool can_predict_insn_p (const rtx_insn *)
static HOST_WIDE_INT get_predictor_value (br_predictor, HOST_WIDE_INT)
static void determine_unlikely_bbs ()
static void estimate_bb_frequencies ()
gcov_type get_hot_bb_threshold ()
void set_hot_bb_threshold (gcov_type min)
bool maybe_hot_count_p (struct function *fun, profile_count count)
bool maybe_hot_bb_p (struct function *fun, const_basic_block bb)
bool maybe_hot_edge_p (edge e)
static bool probably_never_executed (struct function *fun, profile_count count)
bool probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
static bool unlikely_executed_edge_p (edge e)
bool probably_never_executed_edge_p (struct function *fun, edge e)
optimize_size_level optimize_function_for_size_p (struct function *fun)
bool optimize_function_for_speed_p (struct function *fun)
optimization_type function_optimization_type (struct function *fun)
optimize_size_level optimize_bb_for_size_p (const_basic_block bb)
bool optimize_bb_for_speed_p (const_basic_block bb)
optimization_type bb_optimization_type (const_basic_block bb)
optimize_size_level optimize_edge_for_size_p (edge e)
bool optimize_edge_for_speed_p (edge e)
optimize_size_level optimize_insn_for_size_p (void)
bool optimize_insn_for_speed_p (void)
optimization_type insn_optimization_type ()
optimize_size_level optimize_loop_for_size_p (class loop *loop)
bool optimize_loop_for_speed_p (class loop *loop)
bool optimize_loop_nest_for_speed_p (class loop *loop)
optimize_size_level optimize_loop_nest_for_size_p (class loop *loop)
bool predictable_edge_p (edge e)
void rtl_profile_for_bb (basic_block bb)
void rtl_profile_for_edge (edge e)
void default_rtl_profile (void)
bool rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
bool gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
bool edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
bool edge_probability_reliable_p (const_edge e)
bool br_prob_note_reliable_p (const_rtx note)
static void predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
void predict_insn_def (rtx_insn *insn, enum br_predictor predictor, enum prediction taken)
void rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
void gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
static void filter_predictions (edge_prediction **preds, bool(*filter)(edge_prediction *, void *), void *data)
static bool not_equal_edge_p (edge_prediction *p, void *data)
void remove_predictions_associated_with_edge (edge e)
static void clear_bb_predictions (basic_block bb)
void predict_edge_def (edge e, enum br_predictor predictor, enum prediction taken)
void invert_br_probabilities (rtx insn)
static bool unlikely_executed_stmt_p (gimple *stmt)
static bool unlikely_executed_bb_p (basic_block bb)
static void set_even_probabilities (basic_block bb, hash_set< edge > *unlikely_edges=NULL, hash_set< edge_prediction * > *likely_edges=NULL)
void add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
static bool not_removed_prediction_p (edge_prediction *p, void *data)
static void prune_predictions_for_bb (basic_block bb)
static void combine_predictions_for_bb (basic_block bb, bool dry_run)
static tree strips_small_constant (tree t1, tree t2)
static tree get_base_value (tree t)
static bool is_comparison_with_loop_invariant_p (gcond *stmt, class loop *loop, tree *loop_invariant, enum tree_code *compare_code, tree *loop_step, tree *loop_iv_base)
static bool expr_coherent_p (tree t1, tree t2)
static bool predicted_by_loop_heuristics_p (basic_block bb)
static void predict_iv_comparison (class loop *loop, basic_block bb, tree loop_bound_var, tree loop_iv_base_var, enum tree_code loop_bound_code, int loop_bound_step)
static void predict_extra_loop_exits (class loop *loop, edge exit_edge)
static void predict_loops (void)
static void bb_estimate_probability_locally (basic_block bb)
void guess_outgoing_edge_probabilities (basic_block bb)
static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor, HOST_WIDE_INT *probability)
static tree expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited, enum br_predictor *predictor, HOST_WIDE_INT *probability)
static void tree_predict_by_opcode (basic_block bb)
static bool is_exit_with_zero_arg (const gimple *stmt)
static enum br_predictor return_prediction (tree val, enum prediction *prediction)
static int zero_one_minusone (gphi *phi, int limit)
static void apply_return_prediction (void)
static void tree_bb_level_predictions (void)
bool assert_is_empty (const_basic_block const &, edge_prediction *const &value, void *)
static void tree_estimate_probability_bb (basic_block bb, bool local_only)
void tree_estimate_probability (bool dry_run)
void tree_guess_outgoing_edge_probabilities (basic_block bb)
static bool not_loop_guard_equal_edge_p (edge_prediction *p, void *data)
static void maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
static void predict_paths_for_bb (basic_block cur, basic_block bb, enum br_predictor pred, enum prediction taken, bitmap visited, class loop *in_loop=NULL)
static void propagate_freq (basic_block head, bitmap tovisit, sreal max_cyclic_prob)
static void estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
static void estimate_loops (void)
static void drop_profile (struct cgraph_node *node, profile_count call_count)
void handle_missing_profiles (void)
bool update_max_bb_count (void)
bool expensive_function_p (int threshold)
void propagate_unlikely_bbs_forward (void)
void compute_function_frequency (void)
tree build_predict_expr (enum br_predictor predictor, enum prediction taken)
const char * predictor_name (enum br_predictor predictor)
gimple_opt_passmake_pass_profile (gcc::context *ctxt)
static bool strip_predictor_early (enum br_predictor pred)
unsigned int strip_predict_hints (function *fun, bool early)
gimple_opt_passmake_pass_strip_predict_hints (gcc::context *ctxt)
void rebuild_frequencies (void)
gimple_opt_passmake_pass_rebuild_frequencies (gcc::context *ctxt)
void report_predictor_hitrates (void)
void force_edge_cold (edge e, bool impossible)


static const char * reason_messages []
static const struct predictor_info predictor_info []
static gcov_type min_count = -1
static hash_map< const_basic_block, edge_prediction * > * bb_predictions

Macro Definition Documentation


#define BLOCK_INFO ( B)    ((block_info *) (B)->aux)





#define HITRATE ( VAL)    ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
Recompute hitrate in percent to our representation.   

Referenced by expr_expected_value_1(), predict_loops(), and tree_predict_by_opcode().


Use given predictor without Dempster-Shaffer theory if it matches
using first_match heuristics.   

Referenced by combine_predictions_for_bb(), and combine_predictions_for_insn().

Enumeration Type Documentation

◆ predictor_reason

Branch prediction routines for the GNU compiler.
   Copyright (C) 2000-2024 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see

[1] "Branch Prediction for Free"
    Ball and Larus; PLDI '93.
[2] "Static Branch Frequency and Program Profile Analysis"
    Wu and Larus; MICRO-27.
[3] "Corpus-based Static Branch Prediction"
    Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.   
Enum with reasons why a predictor is ignored.   

Function Documentation

◆ add_reg_br_prob_note()

◆ apply_return_prediction()

static void apply_return_prediction ( void )

◆ assert_is_empty()

bool assert_is_empty ( const_basic_block const & ,
edge_prediction *const & value,
void *  )
Callback for hash_map::traverse, asserts that the pointer map is

References gcc_assert.

Referenced by tree_estimate_probability(), and tree_guess_outgoing_edge_probabilities().

◆ bb_estimate_probability_locally()

static void bb_estimate_probability_locally ( basic_block bb)
Attempt to predict probabilities of BB outgoing edges using local

References BB_END, can_predict_insn_p(), COMPARISON_P, const0_rtx, const1_rtx, constm1_rtx, FLOAT_MODE_P, GET_CODE, get_condition(), GET_MODE, NOT_TAKEN, NULL, predict_insn_def(), REG_P, REG_POINTER, TAKEN, and XEXP.

Referenced by guess_outgoing_edge_probabilities().

◆ bb_optimization_type()

optimization_type bb_optimization_type ( const_basic_block bb)
Return the optimization type that should be used for basic block BB.   

References optimize_bb_for_speed_p(), OPTIMIZE_FOR_SIZE, and OPTIMIZE_FOR_SPEED.

Referenced by convert_mult_to_fma(), reassociate_bb(), and replacement_internal_fn().

◆ br_prob_note_reliable_p()

bool br_prob_note_reliable_p ( const_rtx note)
Same predicate as edge_probability_reliable_p, working on notes.   

References profile_probability::from_reg_br_prob_note(), gcc_assert, profile_probability::probably_reliable_p(), REG_NOTE_KIND, and XINT.

◆ build_predict_expr()

tree build_predict_expr ( enum br_predictor predictor,
enum prediction taken )

◆ can_predict_insn_p()

static bool can_predict_insn_p ( const rtx_insn * insn)
Return true when we can store prediction on insn INSN.
At the moment we represent predictions only on conditional
jumps, not at computed jump or other complicated cases.   

References any_condjump_p(), BLOCK_FOR_INSN(), EDGE_COUNT, and JUMP_P.

Referenced by bb_estimate_probability_locally(), and combine_predictions_for_insn().

◆ clear_bb_predictions()

static void clear_bb_predictions ( basic_block bb)
Clears the list of predictions stored for BB.   

References bb_predictions, edge_prediction::ep_next, free(), and NULL.

Referenced by combine_predictions_for_bb().

◆ combine_predictions_for_bb()

◆ combine_predictions_for_insn()

◆ compute_function_frequency()

◆ default_rtl_profile()

void default_rtl_profile ( void )

◆ determine_unlikely_bbs()

◆ drop_profile()

◆ dump_prediction()

◆ edge_predicted_by_p()

bool edge_predicted_by_p ( edge e,
enum br_predictor predictor,
bool taken )
Return true if the one of outgoing edges is already predicted by
PREDICTOR for edge E predicted as TAKEN.   

References bb_predictions, edge_prediction::ep_next, i, REG_BR_PROB_BASE, and TAKEN.

Referenced by maybe_predict_edge().

◆ edge_probability_reliable_p()

bool edge_probability_reliable_p ( const_edge e)
Same predicate as above, working on edges.   

◆ estimate_bb_frequencies()

◆ estimate_loops()

static void estimate_loops ( void )

◆ estimate_loops_at_level()

static void estimate_loops_at_level ( class loop * first_loop,
sreal max_cyclic_prob )

◆ expensive_function_p()

bool expensive_function_p ( int threshold)
Return true if function is likely to be expensive, so there is no point to
optimize performance of prologue, epilogue or do inlining at the expense
of code size growth.  THRESHOLD is the limit of number of instructions
function can execute at average to be still considered not expensive.   

References active_insn_p(), cfun, basic_block_def::count, count, dump_file, ENTRY_BLOCK_PTR_FOR_FN, FOR_BB_INSNS, FOR_EACH_BB_FN, basic_block_def::index, profile_count::initialized_p(), and profile_count::zero().

◆ expr_coherent_p()

static bool expr_coherent_p ( tree t1,
tree t2 )
Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent.   

References gcc_assert, is_gimple_assign(), NULL, SINGLE_SSA_TREE_OPERAND, SSA_NAME_DEF_STMT, SSA_OP_USE, and TREE_CODE.

Referenced by predict_iv_comparison().

◆ expr_expected_value()

static tree expr_expected_value ( tree expr,
bitmap visited,
enum br_predictor * predictor,
HOST_WIDE_INT * probability )
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

References expr, expr_expected_value_1(), extract_ops_from_tree(), TREE_CONSTANT, TREE_TYPE, and visited.

Referenced by expr_expected_value_1(), and tree_predict_by_opcode().

◆ expr_expected_value_1()

◆ filter_predictions()

static void filter_predictions ( edge_prediction ** preds,
bool(* filter )(edge_prediction *, void *),
void * data )
Filter edge predictions PREDS by a function FILTER: if FILTER return false
the prediction is removed.
DATA are passed to the filter function.   

References bb_predictions, edge_prediction::ep_next, and free().

Referenced by maybe_predict_edge(), prune_predictions_for_bb(), and remove_predictions_associated_with_edge().

◆ force_edge_cold()

void force_edge_cold ( edge e,
bool impossible )
Force edge E to be cold.
If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
keep low probability to represent possible error in a guess.  This is used
i.e. in case we predict loop to likely iterate given number of times but
we are not 100% sure.

This function locally updates profile without attempt to keep global
consistency which cannot be reached in full generality without full profile
rebuild from probabilities alone.  Doing so is not necessarily a good idea
because frequencies and counts may be more realistic then probabilities.

In some cases (such as for elimination of early exits during full loop
unrolling) the caller can ensure that profile will get consistent

References profile_probability::always(), cfun, current_ir_type(), profile_probability::dump(), dump_file, dump_flags, ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, force_edge_cold(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), IR_GIMPLE, maybe_hot_bb_p(), MIN, profile_probability::never(), set_edge_probability_and_rescale_others(), single_pred_edge(), single_pred_p(), stmt_can_terminate_bb_p(), TDF_DETAILS, profile_count::to_frequency(), update_br_prob_note(), profile_probability::very_unlikely(), and profile_count::zero().

Referenced by duplicate_loop_body_to_header_edge(), force_edge_cold(), isolate_path(), and try_unroll_loop_completely().

◆ function_optimization_type()

optimization_type function_optimization_type ( struct function * fun)
Return the optimization type that should be used for function FUN.   

References OPTIMIZE_FOR_SIZE, OPTIMIZE_FOR_SPEED, and optimize_function_for_speed_p().

◆ get_base_value()

static tree get_base_value ( tree t)
Return the SSA_NAME in T or T's operands.
Return NULL if SSA_NAME cannot be found.   

References BINARY_CLASS_P, NULL, strips_small_constant(), TREE_CODE, TREE_OPERAND, and TREE_OPERAND_LENGTH.

Referenced by is_comparison_with_loop_invariant_p().

◆ get_hot_bb_threshold()

◆ get_predictor_value()

static HOST_WIDE_INT get_predictor_value ( br_predictor predictor,
HOST_WIDE_INT probability )
Return probability of a PREDICTOR.  If the predictor has variable
probability return passed PROBABILITY.   

References gcc_assert.

Referenced by expr_expected_value_1(), and tree_predict_by_opcode().

◆ gimple_predict_edge()

void gimple_predict_edge ( edge e,
enum br_predictor predictor,
int probability )
Predict edge E with the given PROBABILITY.   

References bb_predictions, cfun, EDGE_COUNT, ENTRY_BLOCK_PTR_FOR_FN, edge_prediction::ep_next, edge_prediction::ep_probability, and i.

◆ gimple_predicted_by_p()

bool gimple_predicted_by_p ( const_basic_block bb,
enum br_predictor predictor )
Return true if the one of outgoing edges is already predicted by

References bb_predictions, edge_prediction::ep_next, and i.

◆ guess_outgoing_edge_probabilities()

void guess_outgoing_edge_probabilities ( basic_block bb)
Set edge->probability for each successor edge of BB.   

References BB_END, bb_estimate_probability_locally(), and combine_predictions_for_insn().

Referenced by compute_outgoing_frequencies().

◆ handle_missing_profiles()

void handle_missing_profiles ( void )
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.   

References cgraph_edge::callee, cgraph_node::callees, cgraph_edge::caller, cgraph_node::callers, function::cfg, cgraph_edge::count, cgraph_node::count, symtab_node::decl, DECL_COMDAT, DECL_EXTERNAL, DECL_STRUCT_FUNCTION, drop_profile(), FOR_EACH_DEFINED_FUNCTION, profile_count::initialized_p(), profile_count::ipa(), cgraph_edge::next_caller, profile_count::nonzero_p(), profile_info, PROFILE_READ, profile_status_for_fn, gcov_summary::runs, cgraph_node::tp_first_run, worklist, and profile_count::zero().

Referenced by tree_profiling().

◆ insn_optimization_type()

optimization_type insn_optimization_type ( )
Return the optimization type that should be used for the current

References OPTIMIZE_FOR_SIZE, OPTIMIZE_FOR_SPEED, and optimize_insn_for_speed_p().

Referenced by expand_sfix_optab().

◆ invert_br_probabilities()

void invert_br_probabilities ( rtx insn)
Invert all branch predictions or probability notes in the INSN.  This needs
to be done each time we invert the condition used by the jump.   

References profile_probability::from_reg_br_prob_note(), GEN_INT, INTVAL, profile_probability::invert(), REG_BR_PROB_BASE, REG_NOTE_KIND, REG_NOTES, profile_probability::to_reg_br_prob_note(), XEXP, and XINT.

Referenced by redirect_jump_2().

◆ is_comparison_with_loop_invariant_p()

static bool is_comparison_with_loop_invariant_p ( gcond * stmt,
class loop * loop,
tree * loop_invariant,
enum tree_code * compare_code,
tree * loop_step,
tree * loop_iv_base )
Check the compare STMT in LOOP. If it compares an induction
variable to a loop invariant, return true, and save
Otherwise return false and set LOOP_INVAIANT to NULL.   

References affine_iv::base, get_base_value(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), integer_zerop(), invert_tree_comparison(), loop_containing_stmt(), NULL, simple_iv(), affine_iv::step, TREE_CODE, and tree_fits_shwi_p().

Referenced by predict_iv_comparison(), and predict_loops().

◆ is_exit_with_zero_arg()

static bool is_exit_with_zero_arg ( const gimple * stmt)
Returns TRUE if the STMT is exit(0) like statement.  

References gimple_call_arg(), gimple_call_builtin_p(), integer_zerop(), and nb_iter_bound::stmt.

Referenced by tree_bb_level_predictions().

◆ make_pass_profile()

gimple_opt_pass * make_pass_profile ( gcc::context * ctxt)

◆ make_pass_rebuild_frequencies()

gimple_opt_pass * make_pass_rebuild_frequencies ( gcc::context * ctxt)

◆ make_pass_strip_predict_hints()

gimple_opt_pass * make_pass_strip_predict_hints ( gcc::context * ctxt)

◆ maybe_hot_bb_p()

bool maybe_hot_bb_p ( struct function * fun,
const_basic_block bb )
Return true if basic block BB of function FUN can be CPU intensive
and should thus be optimized for maximum performance.   

References basic_block_def::count, gcc_checking_assert, and maybe_hot_count_p().

Referenced by compute_function_frequency(), dump_bb_info(), force_edge_cold(), optimize_bb_for_size_p(), and rtl_profile_for_bb().

◆ maybe_hot_count_p()

◆ maybe_hot_edge_p()

bool maybe_hot_edge_p ( edge e)
Return true if edge E can be CPU intensive and should thus be optimized
for maximum performance.   

References cfun, and maybe_hot_count_p().

Referenced by optimize_edge_for_size_p(), and rtl_profile_for_edge().

◆ maybe_predict_edge()

static void maybe_predict_edge ( edge e,
enum br_predictor pred,
enum prediction taken )
Predict edge E with PRED unless it is already predicted by some predictor
considered equivalent.   

References bb_predictions, edge_predicted_by_p(), filter_predictions(), not_loop_guard_equal_edge_p(), and predict_edge_def().

Referenced by predict_paths_for_bb(), and predict_paths_leading_to_edge().

◆ not_equal_edge_p()

static bool not_equal_edge_p ( edge_prediction * p,
void * data )
Filter function predicate that returns true for a edge predicate P
if its edge is equal to DATA.   

References edge_prediction::ep_edge.

Referenced by remove_predictions_associated_with_edge().

◆ not_loop_guard_equal_edge_p()

static bool not_loop_guard_equal_edge_p ( edge_prediction * p,
void * data )
Filter function predicate that returns true for a edge predicate P
if its edge is equal to DATA.   

References edge_prediction::ep_edge, and edge_prediction::ep_predictor.

Referenced by maybe_predict_edge().

◆ not_removed_prediction_p()

static bool not_removed_prediction_p ( edge_prediction * p,
void * data )
Return true if edge prediction P is not in DATA hash set.   

References hash_set< KeyId, Lazy, Traits >::contains().

Referenced by prune_predictions_for_bb().

◆ optimize_bb_for_size_p()

◆ optimize_bb_for_speed_p()

◆ optimize_edge_for_size_p()

optimize_size_level optimize_edge_for_size_p ( edge e)

◆ optimize_edge_for_speed_p()

bool optimize_edge_for_speed_p ( edge e)

◆ optimize_function_for_size_p()

◆ optimize_function_for_speed_p()

◆ optimize_insn_for_size_p()

◆ optimize_insn_for_speed_p()

◆ optimize_loop_for_size_p()

optimize_size_level optimize_loop_for_size_p ( class loop * loop)
Return TRUE if LOOP should be optimized for size.   

References loop::header, and optimize_bb_for_size_p().

Referenced by decide_unrolling(), optimize_loop_nest_for_size_p(), tree_ssa_split_loops(), and tree_ssa_unswitch_loops().

◆ optimize_loop_for_speed_p()

◆ optimize_loop_nest_for_size_p()

optimize_size_level optimize_loop_nest_for_size_p ( class loop * loop)
Return TRUE if nest rooted at LOOP should be optimized for size.   

References loop::inner, loop_outer(), MIN, loop::next, optimize_loop_for_size_p(), and OPTIMIZE_SIZE_NO.

Referenced by loop_prefetch_arrays(), parallelize_loops(), and tree_loop_unroll_and_jam().

◆ optimize_loop_nest_for_speed_p()

bool optimize_loop_nest_for_speed_p ( class loop * loop)

◆ predict_edge_def()

void predict_edge_def ( edge e,
enum br_predictor predictor,
enum prediction taken )
Predict edge E by given predictor if possible.   

References predict_edge(), REG_BR_PROB_BASE, and TAKEN.

Referenced by maybe_predict_edge(), predict_iv_comparison(), tree_estimate_probability_bb(), and tree_predict_by_opcode().

◆ predict_extra_loop_exits()

static void predict_extra_loop_exits ( class loop * loop,
edge exit_edge )
Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
exits are resulted from short-circuit conditions that will generate an
if_tmp. E.g.:

if (foo() || global > 10)

This will be translated into:

  loop header...
  if foo() goto BB6 else goto BB5
  if global > 10 goto BB6 else goto BB7
  goto BB7
  iftmp = (PHI 0(BB5), 1(BB6))
  if iftmp == 1 goto BB8 else goto BB3
  outside of the loop...

The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
exits. This function takes BB7->BB8 as input, and finds out the extra loop
exits to predict them using PRED_LOOP_EXTRA_EXIT.   

References dyn_cast(), EDGE_COUNT, FOR_EACH_EDGE, gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gsi_last_bb(), i, integer_onep(), integer_zerop(), NOT_TAKEN, predict_paths_leading_to_edge(), safe_dyn_cast(), SSA_NAME_DEF_STMT, TREE_CODE, and TREE_CONSTANT.

Referenced by predict_loops().

◆ predict_insn()

static void predict_insn ( rtx_insn * insn,
enum br_predictor predictor,
int probability )

◆ predict_insn_def()

void predict_insn_def ( rtx_insn * insn,
enum br_predictor predictor,
enum prediction taken )

◆ predict_iv_comparison()

static void predict_iv_comparison ( class loop * loop,
basic_block bb,
tree loop_bound_var,
tree loop_iv_base_var,
enum tree_code loop_bound_code,
int loop_bound_step )
Predict branch probability of BB when BB contains a branch that compares
 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.

   for (int i = 0; i < bound; i++) {
     if (i < bound - 2)

In this loop, we will predict the branch inside the loop to be taken.   

References wi::cmps(), wi::div_trunc(), expr_coherent_p(), FOR_EACH_EDGE, gcc_assert, gsi_last_bb(), is_comparison_with_loop_invariant_p(), wi::neg_p(), NOT_TAKEN, predict_edge(), predict_edge_def(), predicted_by_loop_heuristics_p(), REG_BR_PROB_BASE, safe_dyn_cast(), SIGNED, wi::sub(), basic_block_def::succs, TAKEN, generic_wide_int< storage >::to_uhwi(), wi::to_widest(), tree_fits_shwi_p(), and wi::udiv_trunc().

Referenced by predict_loops().

◆ predict_loops()

static void predict_loops ( void )
Predict edge probabilities by exploiting loop structure.   

References hash_set< KeyId, Lazy, Traits >::add(), as_a(), loop::bounds, CDI_DOMINATORS, cfun, compare_tree_int(), hash_set< KeyId, Lazy, Traits >::contains(), CONVERT_EXPR_CODE_P, current_function_decl, dominated_by_p(), dump_file, dump_flags, estimated_stmt_executions(), flow_bb_inside_loop_p(), FOR_EACH_BB_FN, FOR_EACH_EDGE, FOR_EACH_VEC_ELT, free(), get_loop_body(), get_loop_exit_edges(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_call_arg(), gimple_call_fndecl(), gimple_call_internal_p(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_start_bb(), gsi_stmt(), wi::gtu_p(), loop::header, HITRATE, predictor_info::hitrate, basic_block_def::index, integer_zerop(), is_comparison_with_loop_invariant_p(), is_gimple_call(), LI_FROM_INNERMOST, likely_max_loop_iterations_int(), likely_max_stmt_executions(), basic_block_def::loop_father, loop_niter_by_eval(), loop_outer(), loop_preheader_edge(), wi::ltu_p(), max_loop_iterations_int(), predictor_info::name, nb_iter_bound::next, niter_desc::niter, NOT_TAKEN, NULL, loop::num, NUM_FIXED_BLOCKS, loop::num_nodes, number_of_iterations_exit(), predict_edge(), predict_extra_loop_exits(), predict_iv_comparison(), predict_paths_leading_to(), predict_paths_leading_to_edge(), predicted_by_loop_heuristics_p(), predicted_by_p(), print_generic_expr(), RDIV, recursive_call_p(), REG_BR_PROB_BASE, safe_dyn_cast(), single_pred_edge(), single_pred_p(), single_succ_p(), SSA_NAME_DEF_STMT, nb_iter_bound::stmt, basic_block_def::succs, TDF_DETAILS, TDF_SLIM, generic_wide_int< storage >::to_shwi(), TREE_CODE, tree_fits_uhwi_p(), tree_to_shwi(), tree_to_uhwi(), and unlikely_executed_edge_p().

Referenced by tree_estimate_probability().

◆ predict_paths_for_bb()

static void predict_paths_for_bb ( basic_block cur,
basic_block bb,
enum br_predictor pred,
enum prediction taken,
bitmap visited,
class loop * in_loop = NULL )

◆ predict_paths_leading_to()

static void predict_paths_leading_to ( basic_block bb,
enum br_predictor pred,
enum prediction taken,
class loop * in_loop )
Sets branch probabilities according to PREDiction and

References predict_paths_for_bb().

Referenced by predict_loops(), and tree_bb_level_predictions().

◆ predict_paths_leading_to_edge()

static void predict_paths_leading_to_edge ( edge e,
enum br_predictor pred,
enum prediction taken,
class loop * in_loop )

◆ predictable_edge_p()

bool predictable_edge_p ( edge e)
Return true if edge E is likely to be well predictable by branch

References REG_BR_PROB_BASE.

Referenced by default_max_noce_ifcvt_seq_cost(), find_if_case_1(), and find_if_case_2().

◆ predicted_by_loop_heuristics_p()

static bool predicted_by_loop_heuristics_p ( basic_block bb)
Return true if E is predicted by one of loop heuristics.   

References bb_predictions, edge_prediction::ep_next, and i.

Referenced by predict_iv_comparison(), and predict_loops().

◆ predictor_name()

const char * predictor_name ( enum br_predictor predictor)

◆ probably_never_executed()

static bool probably_never_executed ( struct function * fun,
profile_count count )
Return true if COUNT is considered to be never executed in function FUN
or if function FUN is considered so in the static profile.   

References count, function::decl, cgraph_node::frequency, gcc_checking_assert, cgraph_node::get(), NODE_FREQUENCY_UNLIKELY_EXECUTED, profile_info, PROFILE_READ, profile_status_for_fn, gcov_summary::runs, and profile_count::zero().

Referenced by probably_never_executed_bb_p(), and probably_never_executed_edge_p().

◆ probably_never_executed_bb_p()

bool probably_never_executed_bb_p ( struct function * fun,
const_basic_block bb )

◆ probably_never_executed_edge_p()

◆ propagate_freq()

static void propagate_freq ( basic_block head,
bitmap tovisit,
sreal max_cyclic_prob )

◆ propagate_unlikely_bbs_forward()

void propagate_unlikely_bbs_forward ( void )

◆ prune_predictions_for_bb()

static void prune_predictions_for_bb ( basic_block bb)
Prune predictions for a basic block BB.  Currently we do following
clean-up steps:

1) remove duplicate prediction that is guessed with the same probability
   (different than 1/2) to both edge
2) remove duplicates for a prediction that belongs with the same probability
   to a single edge

References hash_set< KeyId, Lazy, Traits >::add(), bb_predictions, dump_file, dump_prediction(), edge_prediction::ep_edge, edge_prediction::ep_next, edge_prediction::ep_predictor, edge_prediction::ep_probability, filter_predictions(), hash_table< Descriptor, Lazy, Allocator >::find(), hash_table< Descriptor, Lazy, Allocator >::find_slot(), not_removed_prediction_p(), REASON_EDGE_PAIR_DUPLICATE, REASON_SINGLE_EDGE_DUPLICATE, and REG_BR_PROB_BASE.

Referenced by combine_predictions_for_bb().

◆ rebuild_frequencies()

void rebuild_frequencies ( void )
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
out of scale and thus needs to be recomputed.   

References cfun, connect_infinite_loops_to_exit(), basic_block_def::count, count, profile_count::differs_from_p(), dump_file, ENTRY_BLOCK_PTR_FOR_FN, estimate_bb_frequencies(), FOR_BB_BETWEEN, FOR_EACH_EDGE, basic_block_def::index, profile_count::initialized_p(), loop_optimizer_finalize(), loop_optimizer_init(), LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS, NULL, basic_block_def::preds, PROFILE_ABSENT, profile_status_for_fn, remove_fake_exit_edges(), profile_count::uninitialized(), and profile_count::zero().

Referenced by tree_function_versioning().

◆ remove_predictions_associated_with_edge()

void remove_predictions_associated_with_edge ( edge e)
Remove all predictions on given basic block that are attached
to edge E.   

References bb_predictions, filter_predictions(), and not_equal_edge_p().

Referenced by remove_edge_raw().

◆ report_predictor_hitrates()

void report_predictor_hitrates ( void )
Perform a dry run of the branch prediction pass and report comparsion of
the predicted and real profile into the dump file.   

References cfun, dump_file, dump_flags, flow_loops_dump(), loop_optimizer_finalize(), loop_optimizer_init(), LOOPS_NORMAL, NULL, number_of_loops(), scev_finalize(), scev_initialize(), TDF_DETAILS, and tree_estimate_probability().

Referenced by branch_prob().

◆ return_prediction()

static enum br_predictor return_prediction ( tree val,
enum prediction * prediction )
Try to guess whether the value of return means error code.   

References integer_onep(), integer_zerop(), INTEGRAL_TYPE_P, NOT_TAKEN, POINTER_TYPE_P, TREE_CODE, TREE_CONSTANT, tree_int_cst_sgn(), and TREE_TYPE.

Referenced by apply_return_prediction().

◆ rtl_predict_edge()

void rtl_predict_edge ( edge e,
enum br_predictor predictor,
int probability )
Predict edge E with given probability if possible.   

References any_condjump_p(), BB_END, predict_insn(), and REG_BR_PROB_BASE.

◆ rtl_predicted_by_p()

bool rtl_predicted_by_p ( const_basic_block bb,
enum br_predictor predictor )
Return true if the one of outgoing edges is already predicted by


◆ rtl_profile_for_bb()

◆ rtl_profile_for_edge()

void rtl_profile_for_edge ( edge e)
Set RTL expansion for edge profile.   

References crtl, and maybe_hot_edge_p().

◆ set_even_probabilities()

static void set_even_probabilities ( basic_block bb,
hash_set< edge > * unlikely_edges = NULL,
hash_set< edge_prediction * > * likely_edges = NULL )
We cannot predict the probabilities of outgoing edges of bb.  Set them
evenly and hope for the best.  If UNLIKELY_EDGES is not null, distribute
even probability for all edges not mentioned in the set.  These edges
are given PROB_VERY_UNLIKELY probability.  Similarly for LIKELY_EDGES,
if we have exactly one likely edge, make the other edges predicted
as not probable.   

References profile_probability::always(), count, edge_prediction::ep_probability, FOR_EACH_EDGE, profile_probability::from_reg_br_prob_base(), gcc_assert, profile_probability::invert(), profile_probability::never(), NULL, basic_block_def::succs, unlikely_executed_edge_p(), and profile_probability::very_unlikely().

Referenced by combine_predictions_for_bb(), and combine_predictions_for_insn().

◆ set_hot_bb_threshold()

void set_hot_bb_threshold ( gcov_type min)
Set the threshold for hot BB counts.   

References min_count.

Referenced by get_hot_bb_threshold(), input_profile_summary(), and ipa_profile().

◆ strip_predict_hints()

unsigned int strip_predict_hints ( function * fun,
bool early )

◆ strip_predictor_early()

static bool strip_predictor_early ( enum br_predictor pred)
Return true when PRED predictor should be removed after early
tree passes.  Most of the predictors are beneficial to survive
as early inlining can also distribute then into caller's bodies.   

Referenced by strip_predict_hints().

◆ strips_small_constant()

static tree strips_small_constant ( tree t1,
tree t2 )
Check if T1 and T2 satisfy the IV_COMPARE condition.
Return the SSA_NAME if the condition satisfies, NULL otherwise.

T1 and T2 should be one of the following cases:
  1. T1 is SSA_NAME, T2 is NULL
  2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
  3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4]   

References NULL, TREE_CODE, tree_fits_shwi_p(), and tree_to_shwi().

Referenced by get_base_value().

◆ tree_bb_level_predictions()

static void tree_bb_level_predictions ( void )

◆ tree_estimate_probability()

void tree_estimate_probability ( bool dry_run)

◆ tree_estimate_probability_bb()

◆ tree_guess_outgoing_edge_probabilities()

void tree_guess_outgoing_edge_probabilities ( basic_block bb)
Set edge->probability for each successor edge of BB.   

References assert_is_empty(), bb_predictions, combine_predictions_for_bb(), NULL, and tree_estimate_probability_bb().

Referenced by gimple_find_sub_bbs().

◆ tree_predict_by_opcode()

◆ unlikely_executed_bb_p()

◆ unlikely_executed_edge_p()

◆ unlikely_executed_stmt_p()

◆ update_max_bb_count()

◆ zero_one_minusone()

static int zero_one_minusone ( gphi * phi,
int limit )
Return zero if phi result could have values other than -1, 0 or 1,
otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
values are used or likely.   

References as_a(), g, gimple_assign_cast_p(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_phi_num_args(), i, INTEGRAL_TYPE_P, is_gimple_assign(), PHI_ARG_DEF, r, SSA_NAME_DEF_STMT, tcc_comparison, wi::to_wide(), TREE_CODE, TREE_CODE_CLASS, TREE_TYPE, TYPE_PRECISION, TYPE_UNSIGNED, and zero_one_minusone().

Referenced by apply_return_prediction(), and zero_one_minusone().

Variable Documentation

◆ bb_predictions

◆ min_count

gcov_type min_count = -1

◆ predictor_info

const struct predictor_info predictor_info[]
Initial value:
= {
{NULL, 0, 0}
#define NULL
Definition system.h:50

◆ reason_messages

const char* reason_messages[]
Initial value:
= {"", " (ignored)",
" (single edge duplicate)", " (edge pair duplicate)"}
String messages for the aforementioned enum.   

Referenced by dump_prediction().