/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
#include "recog.h"
#include "expr.h"
#include "predict.h"
-#include "profile.h"
+#include "coverage.h"
#include "sreal.h"
#include "params.h"
#include "target.h"
#define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
#define PROB_ALWAYS (REG_BR_PROB_BASE)
-static bool predicted_by_p PARAMS ((basic_block,
- enum br_predictor));
-static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
-static void dump_prediction PARAMS ((enum br_predictor, int,
- basic_block, int));
-static void estimate_loops_at_level PARAMS ((struct loop *loop));
-static void propagate_freq PARAMS ((struct loop *));
-static void estimate_bb_frequencies PARAMS ((struct loops *));
-static void counts_to_freqs PARAMS ((void));
-static void process_note_predictions PARAMS ((basic_block, int *,
- dominance_info,
- dominance_info));
-static void process_note_prediction PARAMS ((basic_block, int *,
- dominance_info,
- dominance_info, int, int));
-static bool last_basic_block_p PARAMS ((basic_block));
-static void compute_function_frequency PARAMS ((void));
-static void choose_function_section PARAMS ((void));
-static bool can_predict_insn_p PARAMS ((rtx));
+static bool predicted_by_p (basic_block, enum br_predictor);
+static void combine_predictions_for_insn (rtx, basic_block);
+static void dump_prediction (enum br_predictor, int, basic_block, int);
+static void estimate_loops_at_level (struct loop *loop);
+static void propagate_freq (struct loop *);
+static void estimate_bb_frequencies (struct loops *);
+static void counts_to_freqs (void);
+static void process_note_predictions (basic_block, int *);
+static void process_note_prediction (basic_block, int *, int, int);
+static bool last_basic_block_p (basic_block);
+static void compute_function_frequency (void);
+static void choose_function_section (void);
+static bool can_predict_insn_p (rtx);
/* Information we hold about each branch predictor.
Filled using information from predict.def. */
for maximal performance. */
bool
-maybe_hot_bb_p (bb)
- basic_block bb;
+maybe_hot_bb_p (basic_block bb)
{
- if (profile_info.count_profiles_merged
- && flag_branch_probabilities
+ if (profile_info && flag_branch_probabilities
&& (bb->count
- < profile_info.max_counter_in_program
- / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
+ < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
return false;
if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
return false;
/* Return true in case BB is cold and should be optimized for size. */
bool
-probably_cold_bb_p (bb)
- basic_block bb;
+probably_cold_bb_p (basic_block bb)
{
- if (profile_info.count_profiles_merged
- && flag_branch_probabilities
+ if (profile_info && flag_branch_probabilities
&& (bb->count
- < profile_info.max_counter_in_program
- / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
+ < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
return true;
if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
return true;
/* Return true in case BB is probably never executed. */
bool
-probably_never_executed_bb_p (bb)
- basic_block bb;
+probably_never_executed_bb_p (basic_block bb)
{
- if (profile_info.count_profiles_merged
- && flag_branch_probabilities)
- return ((bb->count + profile_info.count_profiles_merged / 2)
- / profile_info.count_profiles_merged) == 0;
+ if (profile_info && flag_branch_probabilities)
+ return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
return false;
}
PREDICTOR. */
static bool
-predicted_by_p (bb, predictor)
- basic_block bb;
- enum br_predictor predictor;
+predicted_by_p (basic_block bb, enum br_predictor predictor)
{
rtx note;
- if (!INSN_P (bb->end))
+ if (!INSN_P (BB_END (bb)))
return false;
- for (note = REG_NOTES (bb->end); note; note = XEXP (note, 1))
+ for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_BR_PRED
&& INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
return true;
}
void
-predict_insn (insn, predictor, probability)
- rtx insn;
- int probability;
- enum br_predictor predictor;
+predict_insn (rtx insn, enum br_predictor predictor, int probability)
{
if (!any_condjump_p (insn))
abort ();
/* Predict insn by given predictor. */
void
-predict_insn_def (insn, predictor, taken)
- rtx insn;
- enum br_predictor predictor;
- enum prediction taken;
+predict_insn_def (rtx insn, enum br_predictor predictor,
+ enum prediction taken)
{
int probability = predictor_info[(int) predictor].hitrate;
/* Predict edge E with given probability if possible. */
void
-predict_edge (e, predictor, probability)
- edge e;
- int probability;
- enum br_predictor predictor;
+predict_edge (edge e, enum br_predictor predictor, int probability)
{
rtx last_insn;
- last_insn = e->src->end;
+ last_insn = BB_END (e->src);
/* We can store the branch prediction information only about
conditional jumps. */
At the moment we represent predictions only on conditional
jumps, not at computed jump or other complicated cases. */
static bool
-can_predict_insn_p (insn)
- rtx insn;
+can_predict_insn_p (rtx insn)
{
return (GET_CODE (insn) == JUMP_INSN
&& any_condjump_p (insn)
/* Predict edge E by given predictor if possible. */
void
-predict_edge_def (e, predictor, taken)
- edge e;
- enum br_predictor predictor;
- enum prediction taken;
+predict_edge_def (edge e, enum br_predictor predictor,
+ enum prediction taken)
{
int probability = predictor_info[(int) predictor].hitrate;
to be done each time we invert the condition used by the jump. */
void
-invert_br_probabilities (insn)
- rtx insn;
+invert_br_probabilities (rtx insn)
{
rtx note;
/* Dump information about the branch prediction to the output file. */
static void
-dump_prediction (predictor, probability, bb, used)
- enum br_predictor predictor;
- int probability;
- basic_block bb;
- int used;
+dump_prediction (enum br_predictor predictor, int probability,
+ basic_block bb, int used)
{
edge e = bb->succ;
note if not already present. Remove now useless REG_BR_PRED notes. */
static void
-combine_predictions_for_insn (insn, bb)
- rtx insn;
- basic_block bb;
+combine_predictions_for_insn (rtx insn, basic_block bb)
{
rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
rtx *pnote = ®_NOTES (insn);
predictions). */
void
-estimate_probability (loops_info)
- struct loops *loops_info;
+estimate_probability (struct loops *loops_info)
{
- dominance_info dominators, post_dominators;
basic_block bb;
unsigned i;
connect_infinite_loops_to_exit ();
- dominators = calculate_dominance_info (CDI_DOMINATORS);
- post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
+ calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
struct loop_desc desc;
unsigned HOST_WIDE_INT niter;
- flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
+ flow_loop_scan (loop, LOOP_EXIT_EDGES);
exits = loop->num_exits;
- if (simple_loop_p (loops_info, loop, &desc)
- && desc.const_iter)
+ if (simple_loop_p (loop, &desc) && desc.const_iter)
{
int prob;
niter = desc.niter + 1;
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. */
- if (!can_predict_insn_p (bb->end)
+ if (!can_predict_insn_p (BB_END (bb))
|| predicted_by_p (bb, PRED_CONTINUE))
continue;
- predictor_info [(int) PRED_LOOP_EXIT].hitrate)
/ exits);
}
+
+ /* Free basic blocks from get_loop_body. */
+ free (bbs);
}
/* Attempt to predict conditional jumps using a number of heuristics. */
FOR_EACH_BB (bb)
{
- rtx last_insn = bb->end;
+ rtx last_insn = BB_END (bb);
rtx cond, earliest;
edge e;
/* Look for block we are guarding (ie we dominate it,
but it doesn't postdominate us). */
if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
- && dominated_by_p (dominators, e->dest, e->src)
- && !dominated_by_p (post_dominators, e->src, e->dest))
+ && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
+ && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
{
rtx insn;
is improbable. This is because such calls are often used
to signal exceptional situations such as printing error
messages. */
- for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
+ for (insn = BB_HEAD (e->dest); insn != NEXT_INSN (BB_END (e->dest));
insn = NEXT_INSN (insn))
if (GET_CODE (insn) == CALL_INSN
/* Constant and pure calls are hardly used to signalize
}
}
- cond = get_condition (last_insn, &earliest);
+ cond = get_condition (last_insn, &earliest, false);
if (! cond)
continue;
/* Attach the combined probability to each conditional jump. */
FOR_EACH_BB (bb)
- if (GET_CODE (bb->end) == JUMP_INSN
- && any_condjump_p (bb->end)
+ if (GET_CODE (BB_END (bb)) == JUMP_INSN
+ && any_condjump_p (BB_END (bb))
&& bb->succ->succ_next != NULL)
- combine_predictions_for_insn (bb->end, bb);
+ combine_predictions_for_insn (BB_END (bb), bb);
- free_dominance_info (post_dominators);
- free_dominance_info (dominators);
+ free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_edges ();
estimate_bb_frequencies (loops_info);
values. */
void
-expected_value_to_br_prob ()
+expected_value_to_br_prob (void)
{
rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
(lt r70, r71)
Could use cselib to try and reduce this further. */
cond = XEXP (SET_SRC (pc_set (insn)), 0);
- cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
+ cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg, false);
if (! cond || XEXP (cond, 0) != ev_reg
|| GET_CODE (XEXP (cond, 1)) != CONST_INT)
continue;
}
}
\f
-/* Check whether this is the last basic block of function. Commonly tehre
- is one extra common cleanup block. */
+/* Check whether this is the last basic block of function. Commonly
+ there is one extra common cleanup block. */
static bool
-last_basic_block_p (bb)
- basic_block bb;
+last_basic_block_p (basic_block bb)
{
if (bb == EXIT_BLOCK_PTR)
return false;
&& bb->succ->dest->next_bb == EXIT_BLOCK_PTR));
}
-/* Sets branch probabilities according to PREDiction and FLAGS. HEADS[bb->index]
- should be index of basic block in that we need to alter branch predictions
- (i.e. the first of our dominators such that we do not post-dominate it)
- (but we fill this information on demand, so -1 may be there in case this
- was not needed yet). */
+/* Sets branch probabilities according to PREDiction and
+ FLAGS. HEADS[bb->index] should be index of basic block in that we
+ need to alter branch predictions (i.e. the first of our dominators
+ such that we do not post-dominate it) (but we fill this information
+ on demand, so -1 may be there in case this was not needed yet). */
static void
-process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
- basic_block bb;
- int *heads;
- dominance_info dominators;
- dominance_info post_dominators;
- int pred;
- int flags;
+process_note_prediction (basic_block bb, int *heads, int pred, int flags)
{
edge e;
int y;
find first dominator that we do not post-dominate (we are
using already known members of heads array). */
basic_block ai = bb;
- basic_block next_ai = get_immediate_dominator (dominators, bb);
+ basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
int head;
while (heads[next_ai->index] < 0)
{
- if (!dominated_by_p (post_dominators, next_ai, bb))
+ if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
break;
heads[next_ai->index] = ai->index;
ai = next_ai;
- next_ai = get_immediate_dominator (dominators, next_ai);
+ next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
}
- if (!dominated_by_p (post_dominators, next_ai, bb))
+ if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
head = next_ai->index;
else
head = heads[next_ai->index];
/* Now find the edge that leads to our branch and aply the prediction. */
- if (y == last_basic_block || !can_predict_insn_p (BASIC_BLOCK (y)->end))
+ if (y == last_basic_block || !can_predict_insn_p (BB_END (BASIC_BLOCK (y))))
return;
for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
if (e->dest->index >= 0
- && dominated_by_p (post_dominators, e->dest, bb))
+ && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
predict_edge_def (e, pred, taken);
}
process_note_prediction. */
static void
-process_note_predictions (bb, heads, dominators, post_dominators)
- basic_block bb;
- int *heads;
- dominance_info dominators;
- dominance_info post_dominators;
+process_note_predictions (basic_block bb, int *heads)
{
rtx insn;
edge e;
int was_bb_head = 0;
int noreturn_block = 1;
- for (insn = bb->end; insn;
- was_bb_head |= (insn == bb->head), insn = PREV_INSN (insn))
+ for (insn = BB_END (bb); insn;
+ was_bb_head |= (insn == BB_HEAD (bb)), insn = PREV_INSN (insn))
{
if (GET_CODE (insn) != NOTE)
{
/* Process single prediction note. */
process_note_prediction (bb,
heads,
- dominators,
- post_dominators,
alg, (int) NOTE_PREDICTION_FLAGS (insn));
delete_insn (insn);
}
/* This block ended from other reasons than because of return.
If it is because of noreturn call, this should certainly not
be taken. Otherwise it is probably some error recovery. */
- process_note_prediction (bb,
- heads,
- dominators,
- post_dominators, PRED_NORETURN, NOT_TAKEN);
+ process_note_prediction (bb, heads, PRED_NORETURN, NOT_TAKEN);
}
}
branch probabilities. */
void
-note_prediction_to_br_prob ()
+note_prediction_to_br_prob (void)
{
basic_block bb;
- dominance_info post_dominators, dominators;
int *heads;
/* To enable handling of noreturn blocks. */
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
- post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
- dominators = calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+ calculate_dominance_info (CDI_DOMINATORS);
heads = xmalloc (sizeof (int) * last_basic_block);
memset (heads, -1, sizeof (int) * last_basic_block);
/* Process all prediction notes. */
FOR_EACH_BB (bb)
- process_note_predictions (bb, heads, dominators, post_dominators);
+ process_note_predictions (bb, heads);
- free_dominance_info (post_dominators);
- free_dominance_info (dominators);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ free_dominance_info (CDI_DOMINATORS);
free (heads);
remove_fake_edges ();
/* To keep queue of basic blocks to process. */
basic_block next;
- /* True if block needs to be visited in prop_freqency. */
- int tovisit:1;
+ /* True if block needs to be visited in propagate_freq. */
+ unsigned int tovisit:1;
/* Number of predecessors we need to visit first. */
int npredecessors;
then computed as 1 / (1 - back_edge_prob). */
sreal back_edge_prob;
/* True if the edge is an loopback edge in the natural loop. */
- int back_edge:1;
+ unsigned int back_edge:1;
} *edge_info;
#define BLOCK_INFO(B) ((block_info) (B)->aux)
Propagate the frequencies for LOOP. */
static void
-propagate_freq (loop)
- struct loop *loop;
+propagate_freq (struct loop *loop)
{
basic_block head = loop->header;
basic_block bb;
sizeof (real_almost_one));
}
- /* BLOCK_INFO (bb)->frequency = frequency
+ /* BLOCK_INFO (bb)->frequency = frequency
/ (1 - cyclic_probability) */
sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
/* Estimate probabilities of loopback edges in loops at same nest level. */
static void
-estimate_loops_at_level (first_loop)
- struct loop *first_loop;
+estimate_loops_at_level (struct loop *first_loop)
{
struct loop *loop;
unsigned i;
estimate_loops_at_level (loop->inner);
-
+
if (loop->latch->succ) /* Do not do this for dummy function loop. */
{
/* Find current loop back edge and mark it. */
/* Convert counts measured by profile driven feedback to frequencies. */
static void
-counts_to_freqs ()
+counts_to_freqs (void)
{
gcov_type count_max = 1;
basic_block bb;
function can execute at average to be still considered not expensive. */
bool
-expensive_function_p (threshold)
- int threshold;
+expensive_function_p (int threshold)
{
unsigned int sum = 0;
basic_block bb;
{
rtx insn;
- for (insn = bb->head; insn != NEXT_INSN (bb->end);
+ for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
if (active_insn_p (insn))
{
/* Estimate basic blocks frequency by given branch probabilities. */
static void
-estimate_bb_frequencies (loops)
- struct loops *loops;
+estimate_bb_frequencies (struct loops *loops)
{
basic_block bb;
sreal freq_max;
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);
notes. */
FOR_EACH_BB (bb)
{
- rtx last_insn = bb->end;
+ rtx last_insn = BB_END (bb);
if (!can_predict_insn_p (last_insn))
{
/* Decide whether function is hot, cold or unlikely executed. */
static void
-compute_function_frequency ()
+compute_function_frequency (void)
{
basic_block bb;
- if (!profile_info.count_profiles_merged
- || !flag_branch_probabilities)
+ if (!profile_info || !flag_branch_probabilities)
return;
cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
FOR_EACH_BB (bb)
/* Choose appropriate section for the function. */
static void
-choose_function_section ()
+choose_function_section (void)
{
if (DECL_SECTION_NAME (current_function_decl)
|| !targetm.have_named_sections
/* Theoretically we can split the gnu.linkonce text section too,
- but this requires more work as the frequency needs to match
+ but this requires more work as the frequency needs to match
for all generated objects so we need to merge the frequency
of all instances. For now just never set frequency for these. */
|| DECL_ONE_ONLY (current_function_decl))
OSDN Git Service
