- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | predictor_info |
| struct | edge_prediction |
| struct | block_info_def |
| struct | edge_info_def |
Typedefs | |
| typedef struct block_info_def * | block_info |
| typedef struct edge_info_def * | edge_info |
Variables | |
| static sreal | real_zero |
| static sreal | real_one |
| static sreal | real_almost_one |
| static sreal | real_br_prob_base |
| static sreal | real_inv_br_prob_base |
| static sreal | real_one_half |
| static sreal | real_bb_freq_max |
| static struct predictor_info | predictor_info [] |
| static gcov_type | min_count = -1 |
| static struct pointer_map_t * | bb_predictions |
| typedef struct block_info_def * block_info |
This is used to carry information about basic blocks. It is attached to the AUX field of the standard CFG block.
| typedef struct edge_info_def * edge_info |
Similar information for edges.
|
static |
Find the basic block with return expression and look up for possible return value trying to apply RETURN_PREDICTION heuristics.
Avoid the degenerate case where all return values form the function
belongs to same category (ie they are all positive constants)
so we can hardly say something about them.
References gimple_label_label(), gsi_stmt(), lookup_attribute(), predict_edge_def(), and TAKEN.
|
static |
Callback for pointer_map_traverse, asserts that the pointer map is empty.
|
static |
Attempt to predict probabilities of BB outgoing edges using local properties.
Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
Similarly, a comparison ptr1 == ptr2 is predicted as false. Try "opcode heuristic."
EQ tests are usually false and NE tests are usually true. Also,
most quantities are positive, so we can make the appropriate guesses
about signed comparisons against zero. Unconditional branch.
Floating point comparisons appears to behave in a very
unpredictable way because of special role of = tests in
FP code. Comparisons with 0 are often used for booleans and there is
nothing useful to predict about them. Floating point comparisons appears to behave in a very
unpredictable way because of special role of = tests in
FP code. Comparisons with 0 are often used for booleans and there is
nothing useful to predict about them.
| bool br_prob_note_reliable_p | ( | ) |
Same predicate as edge_probability_reliable_p, working on notes.
| tree build_predict_expr | ( | ) |
Build PREDICT_EXPR.
|
static |
Referenced by dump_prediction().
|
static |
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 basic_block_def::count, and HOST_WIDEST_INT_PRINT_DEC.
| bool cgraph_maybe_hot_edge_p | ( | ) |
Return true if the call can be hot.
References cgraph_edge::frequency.
| bool cgraph_optimize_for_size_p | ( | ) |
Return true if NODE should be optimized for size.
References optimize_function_for_size_p().
|
static |
Clears the list of predictions stored for BB.
|
static |
Combine predictions into single probability and store them into CFG. Remove now useless prediction entries.
When there is no successor or only one choice, prediction is easy.
We are lazy for now and predict only basic blocks with two outgoing
edges. It is possible to predict generic case too, but we have to
ignore first match heuristics and do more involved combining. Implement
this later. We implement "first match" heuristics and use probability guessed
by predictor with smallest index. First match heuristics would be widly confused if we predicted
both directions. If the same predictor later gave better result, go for it!
Use FP math to avoid overflows of 32bit integers.
If one probability is 0% and one 100%, avoid division by zero.
Decide which heuristic to use. In case we didn't match anything,
use no_prediction heuristic, in case we did match, use either
first match or Dempster-Shaffer theory depending on the flags.
References edge_prediction::ep_edge, and edge_prediction::ep_probability.
|
static |
|
static |
Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB note if not already present. Remove now useless REG_BR_PRED notes.
We implement "first match" heuristics and use probability guessed
by predictor with smallest index. Use FP math to avoid overflows of 32bit integers.
If one probability is 0% and one 100%, avoid division by zero.
Decide which heuristic to use. In case we didn't match anything,
use no_prediction heuristic, in case we did match, use either
first match or Dempster-Shaffer theory depending on the flags. Save the prediction into CFG in case we are seeing non-degenerated
conditional jump.
| void compute_function_frequency | ( | void | ) |
Decide whether function is hot, cold or unlikely executed.
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.
| int counts_to_freqs | ( | void | ) |
Convert counts measured by profile driven feedback to frequencies. Return nonzero iff there was any nonzero execution count.
| void default_rtl_profile | ( | void | ) |
Set RTL expansion to default mode (i.e. when profile info is not known).
References pointer_map_contains().
Referenced by blocks_nreverse().
|
static |
Dump information about the branch prediction to the output file.
References can_predict_insn_p(), dump_file, END_PREDICTORS, find_reg_note(), and set_even_probabilities().
| bool edge_probability_reliable_p | ( | ) |
Same predicate as above, working on edges.
References any_condjump_p(), and edge_def::src.
| void estimate_bb_frequencies | ( | ) |
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.
Set up block info for each basic block.
First compute frequencies locally for each loop from innermost
to outermost to examine frequencies for back edges.
References GIMPLE_PASS.
|
static |
Propagates frequencies through structure of loops.
Start by estimating the frequencies in the loops.
Now propagate the frequencies through all the blocks.
|
static |
Estimate frequencies in loops at same nest level.
Find current loop back edge and mark it.
| bool expensive_function_p | ( | ) |
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.
We can not compute accurately for large thresholds due to scaled
frequencies. 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. Maximally BB_FREQ_MAX^2 so overflow won't happen.
References predictor_info::name.
|
static |
Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent.
Check to see if t1 is expressed/defined with t2.
Check to see if t2 is expressed/defined with t1.
Compare if t1 and t2's def_stmts are identical.
|
static |
Return constant EXPR will likely have at execution time, NULL if unknown. The function is used by builtin_expect branch predictor so the evidence must come from this construct and additional possible constant folding. We may want to implement more involved value guess (such as value range propagation based prediction), but such tricks shall go to new implementation.
|
static |
Helper function for expr_expected_value.
If we were already here, break the infinite cycle.
All the arguments of the PHI node must have the same constant
length. If this PHI has itself as an argument, we cannot
determine the string length of this argument. However,
if we can find an expected constant value for the other
PHI args then we can still be sure that this is
likely a constant. So be optimistic and just
continue with the next argument. Assume that any given atomic operation has low contention,
and thus the compare-and-swap operation succeeds.
|
static |
|
static |
Return the SSA_NAME in T or T's operands. Return NULL if SSA_NAME cannot be found.
References affine_iv_d::base, host_integerp(), invert_tree_comparison(), and affine_iv_d::step.
| gcov_type get_hot_bb_threshold | ( | void | ) |
Determine the threshold for hot BB counts.
| void gimple_predict_edge | ( | ) |
Predict edge E with the given PROBABILITY.
References edge_prediction::ep_next, free(), and pointer_map_contains().
| bool gimple_predicted_by_p | ( | ) |
Return true if the one of outgoing edges is already predicted by PREDICTOR.
References edge_def::probability, and probability_reliable_p().
| void guess_outgoing_edge_probabilities | ( | ) |
Set edge->probability for each successor edge of BB.
| void invert_br_probabilities | ( | ) |
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.
|
static |
Check the compare STMT in LOOP. If it compares an induction variable to a loop invariant, return true, and save LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP. Otherwise return false and set LOOP_INVAIANT to NULL.
| gimple_opt_pass* make_pass_profile | ( | ) |
| gimple_opt_pass* make_pass_strip_predict_hints | ( | ) |
| bool maybe_hot_bb_p | ( | ) |
Return true in case BB can be CPU intensive and should be optimized for maximal performance.
|
inlinestatic |
Return TRUE if frequency FREQ is considered to be hot.
Code executed at most once is not hot.
References basic_block_def::count, basic_block_def::frequency, maybe_hot_frequency_p(), and PROFILE_READ.
| bool maybe_hot_edge_p | ( | ) |
Return true in case BB can be CPU intensive and should be optimized for maximal performance.
|
inlinestatic |
Return TRUE if frequency FREQ is considered to be hot.
Referenced by maybe_hot_count_p().
| bool optimize_bb_for_size_p | ( | ) |
Return TRUE when BB should be optimized for size.
References optimize_edge_for_size_p().
| bool optimize_bb_for_speed_p | ( | ) |
Return TRUE when BB should be optimized for speed.
References cfun, and optimize_function_for_size_p().
| bool optimize_edge_for_size_p | ( | ) |
Return TRUE when BB should be optimized for size.
| bool optimize_edge_for_speed_p | ( | ) |
Return TRUE when BB should be optimized for speed.
| bool optimize_function_for_size_p | ( | ) |
Return true when current function should always be optimized for size.
| bool optimize_function_for_speed_p | ( | ) |
Return true when current function should always be optimized for speed.
References cfun, maybe_hot_edge_p(), and optimize_function_for_size_p().
| bool optimize_insn_for_size_p | ( | void | ) |
Return TRUE when BB should be optimized for size.
References optimize_loop_for_speed_p().
| bool optimize_insn_for_speed_p | ( | void | ) |
Return TRUE when BB should be optimized for speed.
References loop::inner, loop::next, and optimize_loop_for_speed_p().
Referenced by emit_cstore(), expand_mult(), expand_mult_highpart_adjust(), expand_widening_mult(), and no_conflict_move_test().
| bool optimize_loop_for_size_p | ( | ) |
Return TRUE when LOOP should be optimized for size.
References loop_outer(), and loop::next.
| bool optimize_loop_for_speed_p | ( | ) |
Return TRUE when LOOP should be optimized for speed.
| bool optimize_loop_nest_for_size_p | ( | ) |
Return TRUE when LOOP nest should be optimized for size.
References maybe_hot_edge_p().
| bool optimize_loop_nest_for_speed_p | ( | ) |
Return TRUE when LOOP nest should be optimized for speed.
References edge_def::probability, and PROFILE_ABSENT.
| void predict_edge_def | ( | edge | e, |
| enum br_predictor | predictor, | ||
| enum prediction | taken | ||
| ) |
Predict edge E by given predictor if possible.
Referenced by apply_return_prediction(), and tree_bb_level_predictions().
|
static |
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)
break;
This will be translated into:
BB3:
loop header...
BB4:
if foo() goto BB6 else goto BB5
BB5:
if global > 10 goto BB6 else goto BB7
BB6:
goto BB7
BB7:
iftmp = (PHI 0(BB5), 1(BB6))
if iftmp == 1 goto BB8 else goto BB3
BB8:
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_EXIT. If check_value_one is true, only the phi_args with value '1' will lead
to loop exit. Otherwise, only the phi_args with value '0' will lead to
loop exit.
|
static |
| void predict_insn_def | ( | rtx | insn, |
| enum br_predictor | predictor, | ||
| enum prediction | taken | ||
| ) |
Predict insn by given predictor.
|
static |
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.
E.g.
for (int i = 0; i < bound; i++) {
if (i < bound - 2)
computation_1();
else
computation_2();
}
In this loop, we will predict the branch inside the loop to be taken. Find the taken edge.
When comparing an IV to a loop invariant, NE is more likely to be
taken while EQ is more likely to be not-taken. If loop bound, base and compare bound are all constants, we can
calculate the probability directly. (loop_bound - base) / compare_step
(loop_bound - compare_bound) / compare_step
(compare_bound - base) / compare_step
If loop_count is too big, such that REG_BR_PROB_BASE * loop_count
could overflow, shift both loop_count and compare_count right
a bit so that it doesn't overflow. Note both counts are known not
to be negative at this point. If the loop backedge condition is "(i != bound)", we do
the comparison based on the step of IV:
* step < 0 : backedge condition is like (i > bound)
* step > 0 : backedge condition is like (i < bound) The branch is predicted not-taken if loop_bound_code is
opposite with compare_code. For cases like:
for (i = s; i < h; i++)
if (i > s + 2) ....
The branch should be predicted taken.
|
static |
Predict edge probabilities by exploiting loop structure.
Try to predict out blocks in a loop that are not part of a
natural loop. If we have just one exit and we can derive some information about
the number of iterations of the loop from the statements inside
the loop, use it to predict this exit. If the prediction for number of iterations is zero, do not
predict the exit edges. Find information about loop bound variables.
Bypass loop heuristics on continue statement. These
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. Loop branch heuristics - predict an edge back to a
loop's head as taken. Loop exit heuristics - predict an edge exiting the loop if the
conditional has no loop header successors as not taken. If we already used more reliable loop exit predictors, do not
bother with PRED_LOOP_EXIT. For loop with many exits we don't want to predict all exits
with the pretty large probability, because if all exits are
considered in row, the loop would be predicted to iterate
almost never. The code to divide probability by number of
exits is very rough. It should compute the number of exits
taken in each patch through function (not the overall number
of exits that might be a lot higher for loops with wide switch
statements in them) and compute n-th square root.
We limit the minimal probability by 2% to avoid
EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
as this was causing regression in perl benchmark containing such
a wide loop. Free basic blocks from get_loop_body.
|
static |
Predict edges to successors of CUR whose sources are not postdominated by BB by PRED and recurse to all postdominators.
We are looking for all edges forming edge cut induced by
set of all blocks postdominated by BB. Ignore fake edges and eh, we predict them as not taken anyway.
See if there is an edge from e->src that is not abnormal
and does not lead to BB. If there is non-abnormal path leaving e->src, predict edge
using predictor. Otherwise we need to look for paths
leading to e->src.
The second may lead to infinite loop in the case we are predicitng
regions that are only reachable by abnormal edges. We simply
prevent visiting given BB twice.
References bitmap_bit_p(), dump_file, edge_def::flags, basic_block_def::index, and edge_def::src.
|
static |
Sets branch probabilities according to PREDiction and FLAGS.
|
static |
Like predict_paths_leading_to but take edge instead of basic block.
| bool predictable_edge_p | ( | ) |
Return true when edge E is likely to be well predictable by branch predictor.
| const char* predictor_name | ( | ) |
|
static |
Return true when the probability of edge is reliable. The profile guessing code is good at predicting branch outcome (ie. taken/not taken), that is predicted right slightly over 75% of time. It is however notoriously poor on predicting the probability itself. In general the profile appear a lot flatter (with probabilities closer to 50%) than the reality so it is bad idea to use it to drive optimization such as those disabling dynamic branch prediction for well predictable branches. There are two exceptions - edges leading to noreturn edges and edges predicted by number of iterations heuristics are predicted well. This macro should be able to distinguish those, but at the moment it simply check for noreturn heuristic that is only one giving probability over 99% or bellow 1%. In future we might want to propagate reliability information across the CFG if we find this information useful on multiple places.
Referenced by gimple_predicted_by_p().
|
static |
Return true if profile COUNT and FREQUENCY, or function FUN static node frequency reflects never being executed.
Check for possibility of overflow, in which case entry bb count
is large enough to do the division first without losing much
precision.
| bool probably_never_executed_bb_p | ( | ) |
Return true in case BB is probably never executed.
| bool probably_never_executed_edge_p | ( | ) |
Return true in case edge E is probably never executed.
References cgraph_get_node(), and cgraph_optimize_for_size_p().
|
static |
Helper function for estimate_bb_frequencies. Propagate the frequencies in blocks marked in TOVISIT, starting in HEAD.
For each basic block we need to visit count number of his predecessors
we need to visit first. When function never returns, we will never process exit block.
Compute frequency of basic block.
frequency += (e->probability
* BLOCK_INFO (e->src)->frequency /
REG_BR_PROB_BASE); BLOCK_INFO (bb)->frequency = frequency
/ (1 - cyclic_probability) EDGE_INFO (e)->back_edge_prob
= ((e->probability * BLOCK_INFO (bb)->frequency)
/ REG_BR_PROB_BASE); Propagate to successor blocks.
| 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.
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.
Referenced by copy_static_chain().
| void remove_predictions_associated_with_edge | ( | ) |
Remove all predictions on given basic block that are attached to edge E.
References any_condjump_p().
|
static |
Try to guess whether the value of return means error code.
VOID.
Different heuristics for pointers and scalars.
NULL is usually not returned.
Negative return values are often used to indicate
errors. Constant return values seems to be commonly taken.
Zero/one often represent booleans so exclude them from the
heuristics.
| void rtl_predict_edge | ( | ) |
Predict edge E with given probability if possible.
We can store the branch prediction information only about
conditional jumps. We always store probability of branching.
| bool rtl_predicted_by_p | ( | ) |
Return true if the one of outgoing edges is already predicted by PREDICTOR.
| void rtl_profile_for_bb | ( | ) |
Set RTL expansion for BB profile.
| void rtl_profile_for_edge | ( | ) |
Set RTL expansion for edge profile.
|
static |
We can not predict the probabilities of outgoing edges of bb. Set them evenly and hope for the best.
Referenced by dump_prediction().
| void set_hot_bb_threshold | ( | ) |
Set the threshold for hot BB counts.
|
static |
Get rid of all builtin_expect calls and GIMPLE_PREDICT statements we no longer need.
|
static |
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]
|
static |
Look for basic block that contains unlikely to happen events (such as noreturn calls) and mark all paths leading to execution of this basic blocks as unlikely.
Keep GIMPLE_PREDICT around so early inlining will propagate
hints to callers.
References gimple_has_side_effects(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), is_gimple_call(), and predict_edge_def().
| void tree_estimate_probability | ( | void | ) |
Predict branch probabilities and estimate profile of the tree CFG. This function can be called from the loop optimizers to recompute the profile information.
We use loop_niter_by_eval, which requires that the loops have
preheaders.
|
static |
Predict branch probabilities and estimate profile for basic block BB.
Predict edges to user labels with attributes.
Finally, we have a user-defined label.
Predict early returns to be probable, as we've already taken
care for error returns and other cases are often used for
fast paths through function.
Since we've already removed the return statements, we are
looking for CFG like:
if (conditional)
{
..
goto return_block
}
some other blocks
return_block:
return_stmt. Look for block we are guarding (ie we dominate it,
but it doesn't postdominate us). The call heuristic claims that a guarded function call
is improbable. This is because such calls are often used
to signal exceptional situations such as printing error
messages. Constant and pure calls are hardly used to signalize
something exceptional.
|
static |
Predict branch probabilities and estimate profile of the tree CFG. This is the driver function for PASS_PROFILE.
|
static |
Predict using opcode of the last statement in basic block.
Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
Similarly, a comparison ptr1 == ptr2 is predicted as false. Try "opcode heuristic."
EQ tests are usually false and NE tests are usually true. Also,
most quantities are positive, so we can make the appropriate guesses
about signed comparisons against zero. Floating point comparisons appears to behave in a very
unpredictable way because of special role of = tests in
FP code. Comparisons with 0 are often used for booleans and there is
nothing useful to predict about them. Floating point comparisons appears to behave in a very
unpredictable way because of special role of = tests in
FP code. Comparisons with 0 are often used for booleans and there is
nothing useful to predict about them.
References integer_onep(), integer_zerop(), NOT_TAKEN, TAKEN, and tree_int_cst_sgn().
|
static |
This map contains for a basic block the list of predictions for the outgoing edges.
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
@verbatim
Branch prediction routines for the GNU compiler. Copyright (C) 2000-2013 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 version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 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 http://www.gnu.org/licenses/.
References:
[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. real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX.
1.8.1.1