This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
tree profiling merge 4 - branch predictions improvements
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at redhat dot com
- Date: Thu, 27 May 2004 14:20:53 +0200
- Subject: tree profiling merge 4 - branch predictions improvements
Hi,
this patch contains some improvements to tree based branch predictions
(BUILTIN_EXPECT is no longer ignored, return heuristics is now about the same
as it used to be before the merge) and it extends the find_sub_basic_blocks to
use simple branch predictions heuristics in the case caller didn't care to
insert branch probabilities (I hope that in future most of callers will, but at
the moment most of doesn't). Finally frequencies are computed when
-fprofile-trees is used.
These changes are splittable, but they got bit interferred in the diffs so I
kept them together. I can split them up or commit just part of the patch if
needed.
Bootstrapped/regtested i686-pc-gnu-linux, OK?
Honza
2004-05-25 Jan Hubicka <jh@suse.cz>
* cfgbuild.c (compute_outgoing_frequencies): Use branch predictors
when REG_BR_PROB note is missing.
* predict.c (counts_to_freqs): Make global.
(tree_estimate_probability): Bail out when profile has been read.
* predict.h (counts_to_freqs): Declare.
* profile.c (compute_branch_probabilities): Use it.
* predict.c (process_note_prediction): Rename to:
(predict_paths_leading_to): ... this one.
(expr_expected_value): New function.
(tree_predict_by_opcode): Analyze builtin_expect.
(return_prediction): New function.
(tree_bb_level_predictions): New function.
(strip_builtin_expect): New function.
(tree_esitmate_probability): Add noreturn edges; do
bb_level_predictions; enable return heuristics; strip
builtin_expect_calls.
* basic-block.h (guess_outgoing_edge_probabilities): Declare.
* cfgbuild.c (compute_outgoing_frequencies): Use it.
* predict.c (bb_estimate_probability_locally): Break out from ...
(estimate_probability): ... this one.
(guess_outgoing_edge_probabilities): New function.
(set_even_probabilities): Break out from ...
(combine_predictions_for_bb): ... here.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.196
diff -c -3 -p -r1.196 basic-block.h
*** basic-block.h 15 May 2004 09:39:28 -0000 1.196
--- basic-block.h 26 May 2004 22:58:45 -0000
*************** extern bool rtl_predicted_by_p (basic_bl
*** 603,608 ****
--- 603,609 ----
extern void tree_predict_edge (edge, enum br_predictor, int);
extern void rtl_predict_edge (edge, enum br_predictor, int);
extern void predict_edge_def (edge, enum br_predictor, enum prediction);
+ extern void guess_outgoing_edge_probabilities (basic_block);
/* In flow.c */
extern void init_flow (void);
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.45
diff -c -3 -p -r1.45 cfgbuild.c
*** cfgbuild.c 13 May 2004 06:39:32 -0000 1.45
--- cfgbuild.c 26 May 2004 22:58:45 -0000
*************** compute_outgoing_frequencies (basic_bloc
*** 726,744 ****
if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
{
rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
- int probability;
! if (!note)
! return;
! probability = INTVAL (XEXP (note, 0));
! e = BRANCH_EDGE (b);
! e->probability = probability;
! e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
! / REG_BR_PROB_BASE);
! f = FALLTHRU_EDGE (b);
! f->probability = REG_BR_PROB_BASE - probability;
! f->count = b->count - e->count;
}
if (b->succ && !b->succ->succ_next)
--- 726,745 ----
if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
{
rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
! if (note)
! {
! int probability = INTVAL (XEXP (note, 0));
! e = BRANCH_EDGE (b);
! e->probability = probability;
! e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
! / REG_BR_PROB_BASE);
! f = FALLTHRU_EDGE (b);
! f->probability = REG_BR_PROB_BASE - probability;
! f->count = b->count - e->count;
! return;
! }
}
if (b->succ && !b->succ->succ_next)
*************** compute_outgoing_frequencies (basic_bloc
*** 746,751 ****
--- 747,761 ----
e = b->succ;
e->probability = REG_BR_PROB_BASE;
e->count = b->count;
+ return;
+ }
+ if (flag_guess_branch_prob && b->succ)
+ {
+ guess_outgoing_edge_probabilities (b);
+ if (b->count)
+ for (e = b->succ; e; e = e->succ_next)
+ e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
+ / REG_BR_PROB_BASE);
}
}
*************** find_many_sub_basic_blocks (sbitmap bloc
*** 797,803 ****
}
}
! compute_outgoing_frequencies (bb);
}
FOR_EACH_BB (bb)
--- 807,815 ----
}
}
! /* When the profile is built, update it. */
! if (ENTRY_BLOCK_PTR->succ->probability)
! compute_outgoing_frequencies (bb);
}
FOR_EACH_BB (bb)
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.104
diff -c -3 -p -r1.104 predict.c
*** predict.c 13 May 2004 06:39:44 -0000 1.104
--- predict.c 26 May 2004 22:58:45 -0000
*************** static void dump_prediction (FILE *, enu
*** 75,83 ****
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 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);
--- 75,82 ----
static void estimate_loops_at_level (struct loop *loop);
static void propagate_freq (struct loop *);
static void estimate_bb_frequencies (struct loops *);
static void process_note_predictions (basic_block, int *);
! static void predict_paths_leading_to (basic_block, int *, enum br_predictor, enum prediction);
static bool last_basic_block_p (basic_block);
static void compute_function_frequency (void);
static void choose_function_section (void);
*************** dump_prediction (FILE *file, enum br_pre
*** 315,328 ****
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 (rtx insn, basic_block bb)
{
! rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
! rtx *pnote = ®_NOTES (insn);
rtx note;
int best_probability = PROB_EVEN;
int best_predictor = END_PREDICTORS;
--- 314,345 ----
fprintf (file, "\n");
}
+ /* We can not predict the probabilities of ougtoing edges of bb. Set them
+ evenly and hope for the best. */
+ static void
+ set_even_probabilities (basic_block bb)
+ {
+ int nedges = 0;
+ edge e;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
+ nedges ++;
+ 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;
+ }
+
/* 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 (rtx insn, basic_block bb)
{
! rtx prob_note;
! rtx *pnote;
rtx note;
int best_probability = PROB_EVEN;
int best_predictor = END_PREDICTORS;
*************** combine_predictions_for_insn (rtx insn,
*** 331,336 ****
--- 348,361 ----
bool first_match = false;
bool found = false;
+ if (!can_predict_insn_p (insn))
+ {
+ set_even_probabilities (bb);
+ return;
+ }
+
+ prob_note = find_reg_note (insn, REG_BR_PROB, 0);
+ pnote = ®_NOTES (insn);
if (dump_file)
fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
bb->index);
*************** combine_predictions_for_bb (FILE *file,
*** 448,458 ****
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",
--- 473,480 ----
this later. */
if (nedges != 2)
{
! if (!bb->count)
! set_even_probabilities (bb);
bb_ann (bb)->predictions = NULL;
if (file)
fprintf (file, "%i edges in bb %i predicted to even probabilities\n",
*************** combine_predictions_for_bb (FILE *file,
*** 523,530 ****
}
bb_ann (bb)->predictions = NULL;
! first->probability = combined_probability;
! second->probability = REG_BR_PROB_BASE - combined_probability;
}
/* Predict edge probabilities by exploiting loop structure.
--- 545,555 ----
}
bb_ann (bb)->predictions = NULL;
! if (!bb->count)
! {
! first->probability = combined_probability;
! second->probability = REG_BR_PROB_BASE - combined_probability;
! }
}
/* Predict edge probabilities by exploiting loop structure.
*************** predict_loops (struct loops *loops_info,
*** 617,622 ****
--- 642,746 ----
}
}
+ /* Attempt to predict probabilities of BB outgoing edges using local
+ properties. */
+ static void
+ bb_estimate_probability_locally (basic_block bb)
+ {
+ rtx last_insn = BB_END (bb);
+ rtx cond, earliest;
+
+ if (! can_predict_insn_p (last_insn))
+ return;
+ cond = get_condition (last_insn, &earliest, false);
+ if (! cond)
+ return;
+
+ /* Try "pointer heuristic."
+ A comparison ptr == 0 is predicted as false.
+ Similarly, a comparison ptr1 == ptr2 is predicted as false. */
+ if (COMPARISON_P (cond)
+ && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
+ || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
+ {
+ if (GET_CODE (cond) == EQ)
+ predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
+ else if (GET_CODE (cond) == NE)
+ predict_insn_def (last_insn, PRED_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 (GET_CODE (cond))
+ {
+ case CONST_INT:
+ /* Unconditional branch. */
+ predict_insn_def (last_insn, PRED_UNCONDITIONAL,
+ cond == const0_rtx ? NOT_TAKEN : TAKEN);
+ break;
+
+ case EQ:
+ case UNEQ:
+ /* Floating point comparisons appears to behave in a very
+ unpredictable way because of special role of = tests in
+ FP code. */
+ if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
+ ;
+ /* Comparisons with 0 are often used for booleans and there is
+ nothing useful to predict about them. */
+ else if (XEXP (cond, 1) == const0_rtx
+ || XEXP (cond, 0) == const0_rtx)
+ ;
+ else
+ predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
+ break;
+
+ case NE:
+ case LTGT:
+ /* Floating point comparisons appears to behave in a very
+ unpredictable way because of special role of = tests in
+ FP code. */
+ if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
+ ;
+ /* Comparisons with 0 are often used for booleans and there is
+ nothing useful to predict about them. */
+ else if (XEXP (cond, 1) == const0_rtx
+ || XEXP (cond, 0) == const0_rtx)
+ ;
+ else
+ predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
+ break;
+
+ case ORDERED:
+ predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
+ break;
+
+ case UNORDERED:
+ predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
+ break;
+
+ case LE:
+ case LT:
+ if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
+ || XEXP (cond, 1) == constm1_rtx)
+ predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
+ break;
+
+ case GE:
+ case GT:
+ if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
+ || XEXP (cond, 1) == constm1_rtx)
+ predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
+ break;
+
+ default:
+ break;
+ }
+ }
+
/* 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. */
*************** estimate_probability (struct loops *loop
*** 638,644 ****
FOR_EACH_BB (bb)
{
rtx last_insn = BB_END (bb);
- rtx cond, earliest;
edge e;
if (! can_predict_insn_p (last_insn))
--- 762,767 ----
*************** estimate_probability (struct loops *loop
*** 681,815 ****
break;
}
}
}
! cond = get_condition (last_insn, &earliest, 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 (COMPARISON_P (cond)
! && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
! || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
! {
! if (GET_CODE (cond) == EQ)
! predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
! else if (GET_CODE (cond) == NE)
! predict_insn_def (last_insn, PRED_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 (GET_CODE (cond))
! {
! case CONST_INT:
! /* Unconditional branch. */
! predict_insn_def (last_insn, PRED_UNCONDITIONAL,
! cond == const0_rtx ? NOT_TAKEN : TAKEN);
! break;
! case EQ:
! case UNEQ:
! /* Floating point comparisons appears to behave in a very
! unpredictable way because of special role of = tests in
! FP code. */
! if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
! ;
! /* Comparisons with 0 are often used for booleans and there is
! nothing useful to predict about them. */
! else if (XEXP (cond, 1) == const0_rtx
! || XEXP (cond, 0) == const0_rtx)
! ;
! else
! predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
! break;
! case NE:
! case LTGT:
! /* Floating point comparisons appears to behave in a very
! unpredictable way because of special role of = tests in
! FP code. */
! if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
! ;
! /* Comparisons with 0 are often used for booleans and there is
! nothing useful to predict about them. */
! else if (XEXP (cond, 1) == const0_rtx
! || XEXP (cond, 0) == const0_rtx)
! ;
! else
! predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
! break;
! case ORDERED:
! predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
! break;
! case UNORDERED:
! predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
! break;
! case LE:
! case LT:
! if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
! || XEXP (cond, 1) == constm1_rtx)
! predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
! break;
! case GE:
! case GT:
! if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
! || XEXP (cond, 1) == constm1_rtx)
! predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
! break;
! default:
! break;
! }
}
!
! /* Attach the combined probability to each conditional jump. */
! FOR_EACH_BB (bb)
! 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), bb);
!
! remove_fake_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);
!
! 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);
}
-
/* Predict using opcode of the last statement in basic block. */
static void
tree_predict_by_opcode (basic_block bb)
--- 804,965 ----
break;
}
}
+ bb_estimate_probability_locally (bb);
}
! }
! /* Attach the combined probability to each conditional jump. */
! FOR_EACH_BB (bb)
! combine_predictions_for_insn (BB_END (bb), bb);
! remove_fake_edges ();
! estimate_bb_frequencies (loops_info);
! free_dominance_info (CDI_POST_DOMINATORS);
! }
! /* Set edge->probability for each succestor edge of BB. */
! void
! guess_outgoing_edge_probabilities (basic_block bb)
! {
! bb_estimate_probability_locally (bb);
! combine_predictions_for_insn (BB_END (bb), bb);
! }
!
! /* 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 tree
! expr_expected_value (tree expr, bitmap visited)
! {
! if (TREE_CONSTANT (expr))
! return expr;
! else if (TREE_CODE (expr) == SSA_NAME)
! {
! tree def = SSA_NAME_DEF_STMT (expr);
!
! /* If we were already here, break the infinite cycle. */
! if (bitmap_bit_p (visited, SSA_NAME_VERSION (expr)))
! return NULL;
! bitmap_set_bit (visited, SSA_NAME_VERSION (expr));
! if (TREE_CODE (def) == PHI_NODE)
! {
! /* All the arguments of the PHI node must have the same constant
! length. */
! int i;
! tree val = NULL, new_val;
! for (i = 0; i < PHI_NUM_ARGS (def); i++)
! {
! tree arg = PHI_ARG_DEF (def, i);
! /* If this PHI has itself as an argument, we cannot
! determine the string length of this argument. However,
! if we can find a constant string length for the other
! PHI args then we can still be sure that this is a
! constant string length. So be optimistic and just
! continue with the next argument. */
! if (arg == PHI_RESULT (def))
! continue;
!
! new_val = expr_expected_value (arg, visited);
! if (!new_val)
! return NULL;
! if (!val)
! val = new_val;
! else if (!operand_equal_p (val, new_val, false))
! return NULL;
! }
! return val;
! }
! if (TREE_CODE (def) != MODIFY_EXPR || TREE_OPERAND (def, 0) != expr)
! return NULL;
! return expr_expected_value (TREE_OPERAND (def, 1), visited);
! }
! else if (TREE_CODE (expr) == CALL_EXPR)
! {
! tree decl = get_callee_fndecl (expr);
! if (!decl)
! return NULL;
! if (DECL_BUILT_IN (decl) && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
! {
! tree arglist = TREE_OPERAND (expr, 1);
! tree val;
! if (arglist == NULL_TREE
! || TREE_CHAIN (arglist) == NULL_TREE)
! return NULL;
! val = TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1)));
! if (TREE_CONSTANT (val))
! return val;
! return TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1)));
! }
! }
! if (TREE_CODE_CLASS (TREE_CODE (expr)) == '2'
! || TREE_CODE_CLASS (TREE_CODE (expr)) == '<')
! {
! tree op0, op1, res;
! op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
! if (!op0)
! return NULL;
! op1 = expr_expected_value (TREE_OPERAND (expr, 1), visited);
! if (!op1)
! return NULL;
! res = fold (build (TREE_CODE (expr), TREE_TYPE (expr), op0, op1));
! if (TREE_CONSTANT (res))
! return res;
! return NULL;
! }
! if (TREE_CODE_CLASS (TREE_CODE (expr)) == '1')
! {
! tree op0, res;
! op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
! if (!op0)
! return NULL;
! res = fold (build1 (TREE_CODE (expr), TREE_TYPE (expr), op0));
! if (TREE_CONSTANT (res))
! return res;
! return NULL;
}
! return NULL;
! }
!
! /* Get rid of all builtin_expect calls we no longer need.
! ??? This function is not called until we get profile transparency merged. */
! static void
! strip_builtin_expect (void)
! {
! basic_block bb;
FOR_EACH_BB (bb)
{
! block_stmt_iterator bi;
! for (bi = bsi_start (bb); !bsi_end_p (bi); bsi_next (&bi))
{
! tree stmt = bsi_stmt (bi);
! tree fndecl;
! tree arglist;
!
! if (TREE_CODE (stmt) == MODIFY_EXPR
! && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR
! && (fndecl = get_callee_fndecl (TREE_OPERAND (stmt, 1)))
! && DECL_BUILT_IN (fndecl)
! && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
! && (arglist = TREE_OPERAND (TREE_OPERAND (stmt, 1), 1))
! && TREE_CHAIN (arglist))
{
! TREE_OPERAND (stmt, 1) = TREE_VALUE (arglist);
! modify_stmt (stmt);
}
}
}
}
/* Predict using opcode of the last statement in basic block. */
static void
tree_predict_by_opcode (basic_block bb)
*************** tree_predict_by_opcode (basic_block bb)
*** 819,824 ****
--- 968,975 ----
tree cond;
tree op0;
tree type;
+ tree val;
+ bitmap visited;
if (!stmt || TREE_CODE (stmt) != COND_EXPR)
return;
*************** tree_predict_by_opcode (basic_block bb)
*** 830,835 ****
--- 981,997 ----
return;
op0 = TREE_OPERAND (cond, 0);
type = TREE_TYPE (op0);
+ visited = BITMAP_XMALLOC ();
+ val = expr_expected_value (cond, visited);
+ BITMAP_XFREE (visited);
+ if (val)
+ {
+ if (integer_zerop (val))
+ predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
+ else
+ predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
+ return;
+ }
/* Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
Similarly, a comparison ptr1 == ptr2 is predicted as false. */
*************** tree_predict_by_opcode (basic_block bb)
*** 914,919 ****
--- 1076,1169 ----
}
}
+ /* Try to guess whether the value of return means error code. */
+ static enum br_predictor
+ return_prediction (tree val)
+ {
+ /* VOID. */
+ if (!val)
+ return PRED_NO_PREDICTION;
+ /* Different heuristics for pointers and scalars. */
+ if (POINTER_TYPE_P (TREE_TYPE (val)))
+ {
+ /* NULL is usually not returned. */
+ if (integer_zerop (val))
+ return PRED_NULL_RETURN;
+ }
+ else
+ {
+ /* Negative return values are often used to indicate
+ errors. */
+ if (TREE_CODE (val) == INTEGER_CST
+ && tree_int_cst_sgn (val) < 0)
+ return PRED_NEGATIVE_RETURN;
+ /* Constant return values are also usually erors,
+ zero/one often mean booleans so exclude them from the
+ heuristics. */
+ if (TREE_CONSTANT (val)
+ && (!integer_zerop (val) && !integer_onep (val)))
+ return PRED_CONST_RETURN;
+ }
+ return PRED_NO_PREDICTION;
+ }
+
+ /* 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. */
+
+ static void
+ tree_bb_level_predictions (void)
+ {
+ basic_block bb;
+ int *heads;
+
+ 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)
+ {
+ block_stmt_iterator bsi = bsi_last (bb);
+ enum br_predictor pred;
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ switch (TREE_CODE (stmt))
+ {
+ case MODIFY_EXPR:
+ if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
+ {
+ stmt = TREE_OPERAND (stmt, 1);
+ goto call_expr;
+ }
+ break;
+ case CALL_EXPR:
+ if (call_expr_flags (stmt) & ECF_NORETURN)
+ predict_paths_leading_to (bb, heads, PRED_NORETURN,
+ NOT_TAKEN);
+ call_expr:;
+ break;
+ case RETURN_EXPR:
+ stmt = TREE_OPERAND (stmt, 0);
+ if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
+ stmt = TREE_OPERAND (stmt, 1);
+ pred = return_prediction (stmt);
+ if (pred != PRED_NO_PREDICTION)
+ predict_paths_leading_to (bb, heads, pred,
+ NOT_TAKEN);
+ break;
+ default:
+ break;
+ }
+ }
+ }
+
+ free (heads);
+ }
+
/* Predict branch probabilities and estimate profile of the tree CFG. */
static void
tree_estimate_probability (void)
*************** tree_estimate_probability (void)
*** 925,934 ****
--- 1175,1187 ----
if (dump_file && (dump_flags & TDF_DETAILS))
flow_loops_dump (&loops_info, dump_file, NULL, 0);
+ add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
calculate_dominance_info (CDI_DOMINATORS);
calculate_dominance_info (CDI_POST_DOMINATORS);
+ tree_bb_level_predictions ();
+
predict_loops (&loops_info, false);
FOR_EACH_BB (bb)
*************** tree_estimate_probability (void)
*** 940,953 ****
/* 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). */
--- 1193,1212 ----
/* 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
! && !last_basic_block_p (bb))
! {
! edge e1;
!
! for (e1 = bb->pred; e1; e1 = e1->pred_next)
! if (predicted_by_p (bb, PRED_NULL_RETURN)
! || predicted_by_p (bb, PRED_CONST_RETURN)
! || predicted_by_p (bb, PRED_NEGATIVE_RETURN))
! break;
! if (!e1)
! for (e1 = bb->pred; e1; e1 = e1->pred_next)
! predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
! }
/* Look for block we are guarding (ie we dominate it,
but it doesn't postdominate us). */
*************** last_basic_block_p (basic_block bb)
*** 1085,1097 ****
on demand, so -1 may be there in case this was not needed yet). */
static void
! process_note_prediction (basic_block bb, int *heads, int pred, int flags)
{
edge e;
int y;
- bool taken;
-
- taken = flags & IS_TAKEN;
if (heads[bb->index] < 0)
{
--- 1345,1355 ----
on demand, so -1 may be there in case this was not needed yet). */
static void
! predict_paths_leading_to (basic_block bb, int *heads, enum br_predictor pred,
! enum prediction taken)
{
edge e;
int y;
if (heads[bb->index] < 0)
{
*************** process_note_prediction (basic_block bb,
*** 1128,1134 ****
/* Now find the edge that leads to our branch and aply the prediction. */
! 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
--- 1386,1392 ----
/* Now find the edge that leads to our branch and aply the prediction. */
! if (y == last_basic_block)
return;
for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
if (e->dest->index >= 0
*************** process_note_predictions (basic_block bb
*** 1172,1180 ****
{
int alg = (int) NOTE_PREDICTION_ALG (insn);
/* Process single prediction note. */
! process_note_prediction (bb,
! heads,
! alg, (int) NOTE_PREDICTION_FLAGS (insn));
delete_insn (insn);
}
}
--- 1430,1440 ----
{
int alg = (int) NOTE_PREDICTION_ALG (insn);
/* Process single prediction note. */
! predict_paths_leading_to (bb,
! heads,
! alg,
! NOTE_PREDICTION_FLAGS (insn) & IS_TAKEN
! ? TAKEN : NOT_TAKEN);
delete_insn (insn);
}
}
*************** process_note_predictions (basic_block bb
*** 1186,1192 ****
/* 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, PRED_NORETURN, NOT_TAKEN);
}
}
--- 1446,1452 ----
/* 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. */
! predict_paths_leading_to (bb, heads, PRED_NORETURN, NOT_TAKEN);
}
}
*************** estimate_loops_at_level (struct loop *fi
*** 1419,1425 ****
/* Convert counts measured by profile driven feedback to frequencies.
Return nonzero iff there was any nonzero execution count. */
! static int
counts_to_freqs (void)
{
gcov_type count_max, true_count_max = 0;
--- 1679,1685 ----
/* Convert counts measured by profile driven feedback to frequencies.
Return nonzero iff there was any nonzero execution count. */
! int
counts_to_freqs (void)
{
gcov_type count_max, true_count_max = 0;
Index: predict.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.def,v
retrieving revision 1.18
diff -c -3 -p -r1.18 predict.def
*** predict.def 13 May 2004 06:39:44 -0000 1.18
--- predict.def 26 May 2004 22:58:45 -0000
*************** DEF_PREDICTOR (PRED_CALL, "call", HITRAT
*** 104,109 ****
--- 104,110 ----
/* Branch causing function to terminate is probably not taken. */
DEF_PREDICTOR (PRED_EARLY_RETURN, "early return", HITRATE (67), 0)
+ DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE (67), 0)
/* Branch containing goto is probably not taken. */
DEF_PREDICTOR (PRED_GOTO, "goto", HITRATE (70), 0)
Index: predict.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.h,v
retrieving revision 1.10
diff -c -3 -p -r1.10 predict.h
*** predict.h 13 May 2004 06:39:44 -0000 1.10
--- predict.h 26 May 2004 22:58:45 -0000
*************** enum prediction
*** 41,45 ****
--- 41,46 ----
extern void predict_insn_def (rtx, enum br_predictor, enum prediction);
extern void predict_insn (rtx, enum br_predictor, int);
+ extern int counts_to_freqs (void);
#endif /* GCC_PREDICT_H */
Index: profile.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/profile.c,v
retrieving revision 1.132
diff -c -3 -p -r1.132 profile.c
*** profile.c 13 May 2004 06:39:44 -0000 1.132
--- profile.c 26 May 2004 22:58:45 -0000
*************** compute_branch_probabilities (void)
*** 591,596 ****
--- 591,597 ----
num_branches++, num_never_executed;
}
}
+ counts_to_freqs ();
if (dump_file)
{