/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
#include "target.h"
#include "loop.h"
#include "cfgloop.h"
+#include "tree-flow.h"
+#include "ggc.h"
+#include "tree-dump.h"
+#include "tree-pass.h"
+#include "timevar.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. */
#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 void combine_predictions_for_insn (rtx, basic_block);
+static void dump_prediction (FILE *, 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 int counts_to_freqs (void);
+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 && flag_branch_probabilities
&& (bb->count
/* 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 && flag_branch_probabilities
&& (bb->count
/* 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 && flag_branch_probabilities)
return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
/* Return true if the one of outgoing edges is already predicted by
PREDICTOR. */
-static bool
-predicted_by_p (bb, predictor)
- basic_block bb;
- enum br_predictor predictor;
+bool
+rtl_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;
return false;
}
+/* Return true if the one of outgoing edges is already predicted by
+ PREDICTOR. */
+
+bool
+tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
+{
+ struct edge_prediction *i = bb_ann (bb)->predictions;
+ for (i = bb_ann (bb)->predictions; i; i = i->next)
+ if (i->predictor == predictor)
+ return true;
+ return false;
+}
+
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;
+rtl_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. */
predict_insn (last_insn, predictor, probability);
}
+/* Predict edge E with the given PROBABILITY. */
+void
+tree_predict_edge (edge e, enum br_predictor predictor, int probability)
+{
+ struct edge_prediction *i = ggc_alloc (sizeof (struct edge_prediction));
+
+ i->next = bb_ann (e->src)->predictions;
+ bb_ann (e->src)->predictions = i;
+ i->probability = probability;
+ i->predictor = predictor;
+ i->edge = e;
+}
+
/* 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. */
static bool
-can_predict_insn_p (insn)
- rtx insn;
+can_predict_insn_p (rtx insn)
{
- return (GET_CODE (insn) == JUMP_INSN
+ return (JUMP_P (insn)
&& any_condjump_p (insn)
&& BLOCK_FOR_INSN (insn)->succ->succ_next);
}
/* 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 (FILE *file, enum br_predictor predictor, int probability,
+ basic_block bb, int used)
{
edge e = bb->succ;
- if (!rtl_dump_file)
+ if (!file)
return;
while (e && (e->flags & EDGE_FALLTHRU))
e = e->succ_next;
- fprintf (rtl_dump_file, " %s heuristics%s: %.1f%%",
+ fprintf (file, " %s heuristics%s: %.1f%%",
predictor_info[predictor].name,
used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
if (bb->count)
{
- fprintf (rtl_dump_file, " exec ");
- fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
+ fprintf (file, " exec ");
+ fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
if (e)
{
- fprintf (rtl_dump_file, " hit ");
- fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count);
- fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count);
+ fprintf (file, " hit ");
+ fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
+ fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
}
}
- fprintf (rtl_dump_file, "\n");
+ fprintf (file, "\n");
}
/* 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. */
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);
bool first_match = false;
bool found = false;
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
+ if (dump_file)
+ fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
bb->index);
/* We implement "first match" heuristics and use probability guessed
- by predictor with smallest index. In the future we will use better
- probability combination techniques. */
+ by predictor with smallest index. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_BR_PRED)
{
first_match = true;
if (!found)
- dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
+ dump_prediction (dump_file, PRED_NO_PREDICTION,
+ combined_probability, bb, true);
else
{
- dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match);
- dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match);
+ dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
+ bb, !first_match);
+ dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
+ bb, first_match);
}
if (first_match)
combined_probability = best_probability;
- dump_prediction (PRED_COMBINED, combined_probability, bb, true);
+ dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
while (*pnote)
{
int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
- dump_prediction (predictor, probability, bb,
+ dump_prediction (dump_file, predictor, probability, bb,
!first_match || best_predictor == predictor);
*pnote = XEXP (*pnote, 1);
}
}
}
-/* Statically estimate the probability that a branch will be taken.
- ??? In the next revision there will be a number of other predictors added
- from the above references. Further, each heuristic will be factored out
- into its own function for clarity (and to facilitate the combination of
- predictions). */
+/* Combine predictions into single probability and store them into CFG.
+ Remove now useless prediction entries. */
-void
-estimate_probability (loops_info)
- struct loops *loops_info;
+static void
+combine_predictions_for_bb (FILE *file, basic_block bb)
{
- dominance_info dominators, post_dominators;
- basic_block bb;
- unsigned i;
+ int best_probability = PROB_EVEN;
+ int best_predictor = END_PREDICTORS;
+ int combined_probability = REG_BR_PROB_BASE / 2;
+ int d;
+ bool first_match = false;
+ bool found = false;
+ struct edge_prediction *pred;
+ int nedges = 0;
+ edge e, first = NULL, second = NULL;
- connect_infinite_loops_to_exit ();
- dominators = calculate_dominance_info (CDI_DOMINATORS);
- post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
+ {
+ nedges ++;
+ if (first && !second)
+ second = e;
+ if (!first)
+ first = e;
+ }
+
+ /* 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. */
+ if (nedges != 2)
+ {
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
+ e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
+ else
+ e->probability = 0;
+ bb_ann (bb)->predictions = NULL;
+ if (file)
+ fprintf (file, "%i edges in bb %i predicted to even probabilities\n",
+ nedges, bb->index);
+ return;
+ }
+
+ if (file)
+ fprintf (file, "Predictions for bb %i\n", bb->index);
+
+ /* We implement "first match" heuristics and use probability guessed
+ by predictor with smallest index. */
+ for (pred = bb_ann (bb)->predictions; pred; pred = pred->next)
+ {
+ int predictor = pred->predictor;
+ int probability = pred->probability;
+
+ if (pred->edge != first)
+ probability = REG_BR_PROB_BASE - probability;
+
+ found = true;
+ if (best_predictor > predictor)
+ best_probability = probability, best_predictor = predictor;
+
+ d = (combined_probability * probability
+ + (REG_BR_PROB_BASE - combined_probability)
+ * (REG_BR_PROB_BASE - probability));
+
+ /* Use FP math to avoid overflows of 32bit integers. */
+ if (d == 0)
+ /* If one probability is 0% and one 100%, avoid division by zero. */
+ combined_probability = REG_BR_PROB_BASE / 2;
+ else
+ combined_probability = (((double) combined_probability) * probability
+ * REG_BR_PROB_BASE / d + 0.5);
+ }
+
+ /* 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. */
+
+ if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
+ first_match = true;
+
+ if (!found)
+ dump_prediction (file, PRED_NO_PREDICTION, combined_probability, bb, true);
+ else
+ {
+ dump_prediction (file, PRED_DS_THEORY, combined_probability, bb,
+ !first_match);
+ dump_prediction (file, PRED_FIRST_MATCH, best_probability, bb,
+ first_match);
+ }
+
+ if (first_match)
+ combined_probability = best_probability;
+ dump_prediction (file, PRED_COMBINED, combined_probability, bb, true);
+
+ for (pred = bb_ann (bb)->predictions; pred; pred = pred->next)
+ {
+ int predictor = pred->predictor;
+ int probability = pred->probability;
+
+ if (pred->edge != bb->succ)
+ probability = REG_BR_PROB_BASE - probability;
+ dump_prediction (file, predictor, probability, bb,
+ !first_match || best_predictor == predictor);
+ }
+ bb_ann (bb)->predictions = NULL;
+
+ first->probability = combined_probability;
+ second->probability = REG_BR_PROB_BASE - combined_probability;
+}
+
+/* Predict edge probabilities by exploiting loop structure.
+ When SIMPLELOOPS is set, attempt to count number of iterations by analyzing
+ RTL. */
+static void
+predict_loops (struct loops *loops_info, bool simpleloops)
+{
+ unsigned i;
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
unsigned j;
int exits;
struct loop *loop = loops_info->parray[i];
- struct loop_desc desc;
+ struct niter_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 (simpleloops)
{
- int prob;
- niter = desc.niter + 1;
- if (niter == 0) /* We might overflow here. */
- niter = desc.niter;
-
- prob = (REG_BR_PROB_BASE
- - (REG_BR_PROB_BASE + niter /2) / niter);
- /* Branch prediction algorithm gives 0 frequency for everything
- after the end of loop for loop having 0 probability to finish. */
- if (prob == REG_BR_PROB_BASE)
- prob = REG_BR_PROB_BASE - 1;
- predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS,
- prob);
+ iv_analysis_loop_init (loop);
+ find_simple_exit (loop, &desc);
+
+ if (desc.simple_p && desc.const_iter)
+ {
+ int prob;
+ niter = desc.niter + 1;
+ if (niter == 0) /* We might overflow here. */
+ niter = desc.niter;
+
+ prob = (REG_BR_PROB_BASE
+ - (REG_BR_PROB_BASE + niter /2) / niter);
+ /* Branch prediction algorithm gives 0 frequency for everything
+ after the end of loop for loop having 0 probability to finish. */
+ if (prob == REG_BR_PROB_BASE)
+ prob = REG_BR_PROB_BASE - 1;
+ predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS,
+ prob);
+ }
}
bbs = get_loop_body (loop);
+
for (j = 0; j < loop->num_nodes; j++)
{
int header_found = 0;
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 ((simpleloops && !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);
}
+}
+
+/* Statically estimate the probability that a branch will be taken and produce
+ estimated profile. When profile feedback is present never executed portions
+ of function gets estimated. */
+
+void
+estimate_probability (struct loops *loops_info)
+{
+ basic_block bb;
+
+ connect_infinite_loops_to_exit ();
+ calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+
+ predict_loops (loops_info, true);
+
+ iv_analysis_done ();
/* Attempt to predict conditional jumps using a number of heuristics. */
FOR_EACH_BB (bb)
{
- rtx last_insn = bb->end;
- rtx cond, earliest;
+ rtx last_insn = BB_END (bb);
+ rtx cond;
edge e;
if (! can_predict_insn_p (last_insn))
/* 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
+ if (CALL_P (insn)
/* Constant and pure calls are hardly used to signalize
something exceptional. */
&& ! CONST_OR_PURE_CALL_P (insn))
}
}
- cond = get_condition (last_insn, &earliest);
+ cond = get_condition (last_insn, NULL, false, false);
if (! cond)
continue;
/* Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
Similarly, a comparison ptr1 == ptr2 is predicted as false. */
- if (GET_RTX_CLASS (GET_CODE (cond)) == '<'
+ if (COMPARISON_P (cond)
&& ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
|| (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
{
/* 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 (JUMP_P (BB_END (bb))
+ && 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);
+ remove_fake_exit_edges ();
+ /* Fill in the probability values in flowgraph based on the REG_BR_PROB
+ notes. */
+ FOR_EACH_BB (bb)
+ {
+ rtx last_insn = BB_END (bb);
- remove_fake_edges ();
+ if (!can_predict_insn_p (last_insn))
+ {
+ /* We can predict only conditional jumps at the moment.
+ Expect each edge to be equally probable.
+ ?? In the future we want to make abnormal edges improbable. */
+ int nedges = 0;
+ edge e;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ nedges++;
+ if (e->probability != 0)
+ break;
+ }
+ if (!e)
+ for (e = bb->succ; e; e = e->succ_next)
+ e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
+ }
+ }
estimate_bb_frequencies (loops_info);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ if (profile_status == PROFILE_ABSENT)
+ profile_status = PROFILE_GUESSED;
+}
+\f
+
+/* Predict using opcode of the last statement in basic block. */
+static void
+tree_predict_by_opcode (basic_block bb)
+{
+ tree stmt = last_stmt (bb);
+ edge then_edge;
+ tree cond;
+ tree op0;
+ tree type;
+
+ if (!stmt || TREE_CODE (stmt) != COND_EXPR)
+ return;
+ for (then_edge = bb->succ; then_edge; then_edge = then_edge->succ_next)
+ if (then_edge->flags & EDGE_TRUE_VALUE)
+ break;
+ cond = TREE_OPERAND (stmt, 0);
+ if (TREE_CODE_CLASS (TREE_CODE (cond)) != '<')
+ return;
+ op0 = TREE_OPERAND (cond, 0);
+ type = TREE_TYPE (op0);
+ /* Try "pointer heuristic."
+ A comparison ptr == 0 is predicted as false.
+ Similarly, a comparison ptr1 == ptr2 is predicted as false. */
+ if (POINTER_TYPE_P (type))
+ {
+ if (TREE_CODE (cond) == EQ_EXPR)
+ predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
+ else if (TREE_CODE (cond) == NE_EXPR)
+ predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
+ }
+ else
+
+ /* 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. */
+ switch (TREE_CODE (cond))
+ {
+ case EQ_EXPR:
+ case UNEQ_EXPR:
+ /* Floating point comparisons appears to behave in a very
+ unpredictable way because of special role of = tests in
+ FP code. */
+ if (FLOAT_TYPE_P (type))
+ ;
+ /* Comparisons with 0 are often used for booleans and there is
+ nothing useful to predict about them. */
+ else if (integer_zerop (op0)
+ || integer_zerop (TREE_OPERAND (cond, 1)))
+ ;
+ else
+ predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
+ break;
+
+ case NE_EXPR:
+ case LTGT_EXPR:
+ /* Floating point comparisons appears to behave in a very
+ unpredictable way because of special role of = tests in
+ FP code. */
+ if (FLOAT_TYPE_P (type))
+ ;
+ /* Comparisons with 0 are often used for booleans and there is
+ nothing useful to predict about them. */
+ else if (integer_zerop (op0)
+ || integer_zerop (TREE_OPERAND (cond, 1)))
+ ;
+ else
+ predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
+ break;
+
+ case ORDERED_EXPR:
+ predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
+ break;
+
+ case UNORDERED_EXPR:
+ predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
+ break;
+
+ case LE_EXPR:
+ case LT_EXPR:
+ if (integer_zerop (TREE_OPERAND (cond, 1))
+ || integer_onep (TREE_OPERAND (cond, 1))
+ || integer_all_onesp (TREE_OPERAND (cond, 1))
+ || real_zerop (TREE_OPERAND (cond, 1))
+ || real_onep (TREE_OPERAND (cond, 1))
+ || real_minus_onep (TREE_OPERAND (cond, 1)))
+ predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
+ break;
+
+ case GE_EXPR:
+ case GT_EXPR:
+ if (integer_zerop (TREE_OPERAND (cond, 1))
+ || integer_onep (TREE_OPERAND (cond, 1))
+ || integer_all_onesp (TREE_OPERAND (cond, 1))
+ || real_zerop (TREE_OPERAND (cond, 1))
+ || real_onep (TREE_OPERAND (cond, 1))
+ || real_minus_onep (TREE_OPERAND (cond, 1)))
+ predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
+ break;
+
+ default:
+ break;
+ }
+}
+
+/* Predict branch probabilities and estimate profile of the tree CFG. */
+static void
+tree_estimate_probability (void)
+{
+ basic_block bb;
+ struct loops loops_info;
+
+ flow_loops_find (&loops_info, LOOP_TREE);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ flow_loops_dump (&loops_info, dump_file, NULL, 0);
+
+ connect_infinite_loops_to_exit ();
+ calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+
+ predict_loops (&loops_info, false);
+
+ FOR_EACH_BB (bb)
+ {
+ edge e;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ /* Predict early returns to be probable, as we've already taken
+ care for error returns and other are often used for fast paths
+ trought function. */
+ if ((e->dest == EXIT_BLOCK_PTR
+ || (e->dest->succ && !e->dest->succ->succ_next
+ && e->dest->succ->dest == EXIT_BLOCK_PTR))
+ && !predicted_by_p (bb, PRED_NULL_RETURN)
+ && !predicted_by_p (bb, PRED_CONST_RETURN)
+ && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
+ && !last_basic_block_p (e->dest))
+ predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
+
+ /* 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 (CDI_DOMINATORS, e->dest, e->src)
+ && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
+ {
+ block_stmt_iterator bi;
+
+ /* 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. */
+ for (bi = bsi_start (e->dest); !bsi_end_p (bi);
+ bsi_next (&bi))
+ {
+ tree stmt = bsi_stmt (bi);
+ if ((TREE_CODE (stmt) == CALL_EXPR
+ || (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
+ /* Constant and pure calls are hardly used to signalize
+ something exceptional. */
+ && TREE_SIDE_EFFECTS (stmt))
+ {
+ predict_edge_def (e, PRED_CALL, NOT_TAKEN);
+ break;
+ }
+ }
+ }
+ }
+ tree_predict_by_opcode (bb);
+ }
+ FOR_EACH_BB (bb)
+ combine_predictions_for_bb (dump_file, bb);
+
+ estimate_bb_frequencies (&loops_info);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ remove_fake_exit_edges ();
+ flow_loops_free (&loops_info);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ dump_tree_cfg (dump_file, dump_flags);
+ if (profile_status == PROFILE_ABSENT)
+ profile_status = PROFILE_GUESSED;
}
\f
/* __builtin_expect dropped tokens into the insn stream describing expected
values. */
void
-expected_value_to_br_prob ()
+expected_value_to_br_prob (void)
{
rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
case JUMP_INSN:
/* Look for simple conditional branches. If we haven't got an
expected value yet, no point going further. */
- if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX
+ if (!JUMP_P (insn) || ev == NULL_RTX
|| ! any_condjump_p (insn))
continue;
break;
(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, 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 && !bb->succ->succ_next
&& 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). */
-
-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;
-{
- edge e;
- int y;
- bool taken;
-
- taken = flags & IS_TAKEN;
-
- if (heads[bb->index] < 0)
- {
- /* This is first time we need this field in heads array; so
- 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);
- int head;
-
- while (heads[next_ai->index] < 0)
- {
- if (!dominated_by_p (post_dominators, next_ai, bb))
- break;
- heads[next_ai->index] = ai->index;
- ai = next_ai;
- next_ai = get_immediate_dominator (dominators, next_ai);
- }
- if (!dominated_by_p (post_dominators, next_ai, bb))
- head = next_ai->index;
- else
- head = heads[next_ai->index];
- while (next_ai != bb)
- {
- next_ai = ai;
- if (heads[ai->index] == ENTRY_BLOCK)
- ai = ENTRY_BLOCK_PTR;
- else
- ai = BASIC_BLOCK (heads[ai->index]);
- heads[next_ai->index] = head;
- }
- }
- y = heads[bb->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))
- 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))
- predict_edge_def (e, pred, taken);
-}
-
-/* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
- into branch probabilities. For description of heads array, see
- 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;
-{
- rtx insn;
- edge e;
-
- /* Additionally, we check here for blocks with no successors. */
- int contained_noreturn_call = 0;
- int was_bb_head = 0;
- int noreturn_block = 1;
-
- for (insn = bb->end; insn;
- was_bb_head |= (insn == bb->head), insn = PREV_INSN (insn))
- {
- if (GET_CODE (insn) != NOTE)
- {
- if (was_bb_head)
- break;
- else
- {
- /* Noreturn calls cause program to exit, therefore they are
- always predicted as not taken. */
- if (GET_CODE (insn) == CALL_INSN
- && find_reg_note (insn, REG_NORETURN, NULL))
- contained_noreturn_call = 1;
- continue;
- }
- }
- if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
- {
- int alg = (int) NOTE_PREDICTION_ALG (insn);
- /* Process single prediction note. */
- process_note_prediction (bb,
- heads,
- dominators,
- post_dominators,
- alg, (int) NOTE_PREDICTION_FLAGS (insn));
- delete_insn (insn);
- }
- }
- for (e = bb->succ; e; e = e->succ_next)
- if (!(e->flags & EDGE_FAKE))
- noreturn_block = 0;
- if (contained_noreturn_call)
- {
- /* 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);
- }
-}
-
-/* Gathers NOTE_INSN_PREDICTIONs and turns them into
- branch probabilities. */
-
-void
-note_prediction_to_br_prob ()
-{
- 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);
-
- heads = xmalloc (sizeof (int) * last_basic_block);
- memset (heads, -1, sizeof (int) * last_basic_block);
- heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
-
- /* Process all prediction notes. */
-
- FOR_EACH_BB (bb)
- process_note_predictions (bb, heads, dominators, post_dominators);
-
- free_dominance_info (post_dominators);
- free_dominance_info (dominators);
- free (heads);
-
- remove_fake_edges ();
-}
\f
/* This is used to carry information about basic blocks. It is
attached to the AUX field of the standard CFG block. */
/* 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;
/* For each basic block we need to visit count number of his predecessors
we need to visit first. */
- FOR_EACH_BB (bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
{
if (BLOCK_INFO (bb)->tovisit)
{
if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
count++;
else if (BLOCK_INFO (e->src)->tovisit
- && rtl_dump_file && !EDGE_INFO (e)->back_edge)
- fprintf (rtl_dump_file,
+ && dump_file && !EDGE_INFO (e)->back_edge)
+ fprintf (dump_file,
"Irreducible region hit, ignoring edge to %i->%i\n",
e->src->index, bb->index);
BLOCK_INFO (bb)->npredecessors = count;
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. */
+/* Convert counts measured by profile driven feedback to frequencies.
+ Return nonzero iff there was any nonzero execution count. */
-static void
-counts_to_freqs ()
+static int
+counts_to_freqs (void)
{
- gcov_type count_max = 1;
+ gcov_type count_max, true_count_max = 0;
basic_block bb;
FOR_EACH_BB (bb)
- count_max = MAX (bb->count, count_max);
+ true_count_max = MAX (bb->count, true_count_max);
+ count_max = MAX (true_count_max, 1);
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
+ return true_count_max;
}
/* Return true if function is likely to be expensive, so there is no point to
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 (flag_branch_probabilities)
- counts_to_freqs ();
- else
+ if (!flag_branch_probabilities || !counts_to_freqs ())
{
static int real_values_initialized = 0;
}
mark_dfs_back_edges ();
- /* Fill in the probability values in flowgraph based on the REG_BR_PROB
- notes. */
- FOR_EACH_BB (bb)
- {
- rtx last_insn = bb->end;
-
- if (!can_predict_insn_p (last_insn))
- {
- /* We can predict only conditional jumps at the moment.
- Expect each edge to be equally probable.
- ?? In the future we want to make abnormal edges improbable. */
- int nedges = 0;
- edge e;
-
- for (e = bb->succ; e; e = e->succ_next)
- {
- nedges++;
- if (e->probability != 0)
- break;
- }
- if (!e)
- for (e = bb->succ; e; e = e->succ_next)
- e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
- }
- }
ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
/* Decide whether function is hot, cold or unlikely executed. */
static void
-compute_function_frequency ()
+compute_function_frequency (void)
{
basic_block 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))
return;
+
+ /* If we are doing the partitioning optimization, let the optimization
+ choose the correct section into which to put things. */
+
+ if (flag_reorder_blocks_and_partition)
+ return;
+
if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
DECL_SECTION_NAME (current_function_decl) =
build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
}
+
+
+struct tree_opt_pass pass_profile =
+{
+ "profile", /* name */
+ NULL, /* gate */
+ tree_estimate_probability, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_BRANCH_PROB, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+};
OSDN Git Service
