From 87022a6b0e909befbd0cf98339cd65eede6060f3 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Thu, 9 Sep 2004 14:20:40 +0200 Subject: [PATCH] basic-block.h (guess_outgoing_edge_probabilities): Declare. * basic-block.h (guess_outgoing_edge_probabilities): Declare. * cfgbuild.c (compute_outgoing_frequencies): When probability is missing, guess it. (find_many_sub_basic_blocks): Do update profile only when it is present. * predict.c (set_even_probabilities): Break out from ... (combine_predictions_for_insn): ... here; deal with !can_predict_insn_p insns. (combine_predictions_for_bb): Use set_even_probabilities. (bb_estimate_probability_locally): Break out from .... (estimate_probability): ... here. (guess_outgoing_edge_probabilities): New entry point. From-SVN: r87234 --- gcc/ChangeLog | 13 +++ gcc/basic-block.h | 1 + gcc/cfgbuild.c | 66 +++++++------ gcc/predict.c | 241 +++++++++++++++++++++++++++------------------- 4 files changed, 194 insertions(+), 127 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 4dff1b82143..e7ad26d087d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +2004-09-09 Jan Hubicka + + * basic-block.h (guess_outgoing_edge_probabilities): Declare. + * cfgbuild.c (compute_outgoing_frequencies): When probability is missing, + guess it. + (find_many_sub_basic_blocks): Do update profile only when it is present. + * predict.c (set_even_probabilities): Break out from ... + (combine_predictions_for_insn): ... here; deal with !can_predict_insn_p insns. + (combine_predictions_for_bb): Use set_even_probabilities. + (bb_estimate_probability_locally): Break out from .... + (estimate_probability): ... here. + (guess_outgoing_edge_probabilities): New entry point. + 2004-09-09 Nathan Sidwell * gcc.c (add_sysrooted_prefix, execute, do_self_spec, do_spec_1, diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 19ed577fe55..34c58d91d85 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -622,6 +622,7 @@ extern bool rtl_predicted_by_p (basic_block, enum br_predictor); 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); diff --git a/gcc/cfgbuild.c b/gcc/cfgbuild.c index 2f59d7e982c..453e65cf495 100644 --- a/gcc/cfgbuild.c +++ b/gcc/cfgbuild.c @@ -646,17 +646,18 @@ compute_outgoing_frequencies (basic_block b) 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 (note) + { + 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) @@ -664,7 +665,13 @@ compute_outgoing_frequencies (basic_block b) e = b->succ; e->probability = REG_BR_PROB_BASE; e->count = b->count; + return; } + 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); } /* Assume that someone emitted code with control flow instructions to the @@ -698,25 +705,26 @@ find_many_sub_basic_blocks (sbitmap blocks) /* Update branch probabilities. Expect only (un)conditional jumps to be created with only the forward edges. */ - FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) - { - edge e; - - if (STATE (bb) == BLOCK_ORIGINAL) - continue; - if (STATE (bb) == BLOCK_NEW) - { - bb->count = 0; - bb->frequency = 0; - for (e = bb->pred; e; e = e->pred_next) - { - bb->count += e->count; - bb->frequency += EDGE_FREQUENCY (e); - } - } + if (profile_status != PROFILE_ABSENT) + FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) + { + edge e; + + if (STATE (bb) == BLOCK_ORIGINAL) + continue; + if (STATE (bb) == BLOCK_NEW) + { + bb->count = 0; + bb->frequency = 0; + for (e = bb->pred; e; e = e->pred_next) + { + bb->count += e->count; + bb->frequency += EDGE_FREQUENCY (e); + } + } - compute_outgoing_frequencies (bb); - } + compute_outgoing_frequencies (bb); + } FOR_EACH_BB (bb) SET_STATE (bb, 0); diff --git a/gcc/predict.c b/gcc/predict.c index e4e077658c9..99dac1c1386 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -313,14 +313,32 @@ dump_prediction (FILE *file, enum br_predictor predictor, int probability, 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 = find_reg_note (insn, REG_BR_PROB, 0); - rtx *pnote = ®_NOTES (insn); + rtx prob_note; + rtx *pnote; rtx note; int best_probability = PROB_EVEN; int best_predictor = END_PREDICTORS; @@ -329,6 +347,14 @@ combine_predictions_for_insn (rtx insn, basic_block bb) 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); @@ -446,11 +472,8 @@ combine_predictions_for_bb (FILE *file, basic_block bb) 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; + 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", @@ -521,8 +544,11 @@ combine_predictions_for_bb (FILE *file, basic_block bb) } bb_ann (bb)->predictions = NULL; - first->probability = combined_probability; - second->probability = REG_BR_PROB_BASE - combined_probability; + if (!bb->count) + { + first->probability = combined_probability; + second->probability = REG_BR_PROB_BASE - combined_probability; + } } /* Predict edge probabilities by exploiting loop structure. @@ -615,6 +641,105 @@ predict_loops (struct loops *loops_info, bool simpleloops) } } +/* 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; + + if (! can_predict_insn_p (last_insn)) + return; + cond = get_condition (last_insn, NULL, false, 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. */ @@ -636,7 +761,6 @@ estimate_probability (struct loops *loops_info) FOR_EACH_BB (bb) { rtx last_insn = BB_END (bb); - rtx cond; edge e; if (! can_predict_insn_p (last_insn)) @@ -680,94 +804,7 @@ estimate_probability (struct loops *loops_info) } } } - - 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 (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; - } + bb_estimate_probability_locally (bb); } /* Attach the combined probability to each conditional jump. */ @@ -808,6 +845,14 @@ estimate_probability (struct loops *loops_info) if (profile_status == PROFILE_ABSENT) profile_status = PROFILE_GUESSED; } + +/* 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); +} /* Predict using opcode of the last statement in basic block. */ -- 2.30.2