From 134d3a2eaa33145cc91a8f9a8b9ad01c399923bb Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Sat, 28 Jul 2001 23:37:35 +0200 Subject: [PATCH] basic-block.h (EDGE_FREQUENCY): New macro. * basic-block.h (EDGE_FREQUENCY): New macro. * bb-reorder (fixup_reorder_chain): Set counts and frequencies for new BB/edges. * flow.c (find_sub_basic_blocks): Likewise. (try_crossjump_to_edge): Likewise; use EDGE_FREQUENCY (redirect_edge_and_branch): Use EDGE_FREQUENCY. * predict.c (DEF_PREDICTOR): New argument FLAGS. (HITRATE): New macro. (PRED_FLAG_FIRST_MATCH): New constant. (predictor_info): New field flgags. (combine_predictions_for_insn): Use DS theory to combine probabilities; set the edge probabilities when finished. (estimate_probability): Avoid duplicated matches of LOOP_BRANCH heuristics for nested loops; update comment. * predict.def: Add flags for each prediction, set probabilities according to B&L paper. * predict.h (DEF_PREDICTOR): New argument FLAGS. * profile.c (compute_branch_probabilities): Cleanup way the edge probabilities are computed and REG_BR_PROB notes are dropped; if values does not match, emit error. (init_branch_prob): Do error instead of warning when profile driven feedback is missing or corrupt. From-SVN: r44439 --- gcc/ChangeLog | 27 +++++++++++ gcc/basic-block.h | 6 +++ gcc/bb-reorder.c | 4 ++ gcc/flow.c | 60 ++++++++++++++++++++----- gcc/predict.c | 44 ++++++++++++++---- gcc/predict.def | 37 ++++++++------- gcc/predict.h | 2 +- gcc/profile.c | 112 +++++++++++++++++++--------------------------- 8 files changed, 190 insertions(+), 102 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 6b0f4f7118a..6ed56dfa20d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,30 @@ +Sat Jul 28 23:35:22 CEST 2001 Jan Hubicka + + * basic-block.h (EDGE_FREQUENCY): New macro. + * bb-reorder (fixup_reorder_chain): Set counts and frequencies + for new BB/edges. + * flow.c (find_sub_basic_blocks): Likewise. + (try_crossjump_to_edge): Likewise; use EDGE_FREQUENCY + (redirect_edge_and_branch): Use EDGE_FREQUENCY. + + * predict.c (DEF_PREDICTOR): New argument FLAGS. + (HITRATE): New macro. + (PRED_FLAG_FIRST_MATCH): New constant. + (predictor_info): New field flgags. + (combine_predictions_for_insn): Use DS theory to combine + probabilities; set the edge probabilities when finished. + (estimate_probability): Avoid duplicated matches + of LOOP_BRANCH heuristics for nested loops; update comment. + * predict.def: Add flags for each prediction, set probabilities + according to B&L paper. + * predict.h (DEF_PREDICTOR): New argument FLAGS. + + * profile.c (compute_branch_probabilities): Cleanup way the edge + probabilities are computed and REG_BR_PROB notes are dropped; if + values does not match, emit error. + (init_branch_prob): Do error instead of warning when profile driven + feedback is missing or corrupt. + 2001-07-27 DJ Delorie * ifcvt.c (noce_get_alt_condition): If the condition is a compare diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 654e63a9478..bddba84b7e1 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -511,6 +511,12 @@ struct edge_list #define BRANCH_EDGE(bb) ((bb)->succ->flags & EDGE_FALLTHRU \ ? (bb)->succ->succ_next : (bb)->succ) +/* Return expected execution frequency of the edge E. */ +#define EDGE_FREQUENCY(e) (((e)->src->frequency \ + * (e)->probability \ + + REG_BR_PROB_BASE / 2) \ + / REG_BR_PROB_BASE) + struct edge_list * create_edge_list PARAMS ((void)); void free_edge_list PARAMS ((struct edge_list *)); void print_edge_list PARAMS ((FILE *, struct edge_list *)); diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c index e1b341755b1..ffbc4506764 100644 --- a/gcc/bb-reorder.c +++ b/gcc/bb-reorder.c @@ -719,6 +719,8 @@ fixup_reorder_chain () nb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); nb->local_set = 0; + nb->count = e_fall->count; + nb->frequency = EDGE_FREQUENCY (e_fall); COPY_REG_SET (nb->global_live_at_start, bb->global_live_at_start); COPY_REG_SET (nb->global_live_at_end, bb->global_live_at_start); @@ -735,6 +737,8 @@ fixup_reorder_chain () /* Link to new block. */ make_edge (NULL, nb, e_fall->dest, 0); redirect_edge_succ (e_fall, nb); + nb->succ->count = e_fall->count; + nb->succ->probability = REG_BR_PROB_BASE; /* Don't process this new block. */ bb = nb; diff --git a/gcc/flow.c b/gcc/flow.c index 4f339cd7076..04b1b2d0342 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -713,6 +713,7 @@ find_sub_basic_blocks (bb) rtx jump_insn = NULL_RTX; edge falltru = 0; basic_block first_bb = bb; + int i; if (insn == bb->end) return; @@ -784,6 +785,48 @@ find_sub_basic_blocks (bb) /* Now re-scan and wire in all edges. This expect simple (conditional) jumps at the end of each new basic blocks. */ make_edges (NULL, first_bb->index, bb->index, 1); + + /* Update branch probabilities. Expect only (un)conditional jumps + to be created with only the forward edges. */ + for (i = first_bb->index; i <= bb->index; i++) + { + edge e,f; + basic_block b = BASIC_BLOCK (i); + if (b != first_bb) + { + b->count = 0; + b->frequency = 0; + for (e = b->pred; e; e=e->pred_next) + { + b->count += e->count; + b->frequency += EDGE_FREQUENCY (e); + } + } + if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next) + { + rtx note = find_reg_note (b->end, REG_BR_PROB, NULL); + int probability; + + if (!note) + continue; + probability = INTVAL (XEXP (find_reg_note (b->end, + REG_BR_PROB, + NULL), 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) + { + e = b->succ; + e->probability = REG_BR_PROB_BASE; + e->count = b->count; + } + } } /* Find all basic blocks of the function whose first insn is F. @@ -1935,7 +1978,7 @@ redirect_edge_and_branch_force (e, target) new_bb->succ = NULL; new_bb->pred = new_edge; new_bb->count = e->count; - new_bb->frequency = e->probability * e->src->frequency / REG_BR_PROB_BASE; + new_bb->frequency = EDGE_FREQUENCY (e); new_bb->loop_depth = e->dest->loop_depth; new_edge->flags = EDGE_FALLTHRU; @@ -2060,8 +2103,7 @@ split_edge (edge_in) /* Wire them up. */ bb->succ = edge_out; bb->count = edge_in->count; - bb->frequency = (edge_in->probability * edge_in->src->frequency - / REG_BR_PROB_BASE); + bb->frequency = EDGE_FREQUENCY (edge_in); edge_in->flags &= ~EDGE_CRITICAL; @@ -3542,6 +3584,7 @@ try_crossjump_to_edge (mode, e1, e2) edge s; rtx last; rtx label; + rtx note; /* Search backward through forwarder blocks. We don't need to worry about multiple entry or chained forwarders, as they will be optimized @@ -3640,15 +3683,13 @@ try_crossjump_to_edge (mode, e1, e2) { s->dest->succ->count += s2->count; s->dest->count += s2->count; - s->dest->frequency += ((s->probability * s->src->frequency) - / REG_BR_PROB_BASE); + s->dest->frequency += EDGE_FREQUENCY (s); } if (forwarder_block_p (s2->dest)) { s2->dest->succ->count -= s2->count; s2->dest->count -= s2->count; - s2->dest->frequency -= ((s->probability * s->src->frequency) - / REG_BR_PROB_BASE); + s2->dest->frequency -= EDGE_FREQUENCY (s); } if (!redirect_to->frequency && !src1->frequency) s->probability = (s->probability + s2->probability) / 2; @@ -3659,12 +3700,9 @@ try_crossjump_to_edge (mode, e1, e2) / (redirect_to->frequency + src1->frequency)); } - /* FIXME: enable once probabilities are fetched properly at CFG build. */ -#if 0 note = find_reg_note (redirect_to->end, REG_BR_PROB, 0); if (note) XEXP (note, 0) = GEN_INT (BRANCH_EDGE (redirect_to)->probability); -#endif /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */ @@ -3695,6 +3733,8 @@ try_crossjump_to_edge (mode, e1, e2) while (src1->succ) remove_edge (src1->succ); make_edge (NULL, src1, redirect_to, 0); + src1->succ->probability = REG_BR_PROB_BASE; + src1->succ->count = src1->count; return true; } diff --git a/gcc/predict.c b/gcc/predict.c index de1a1417503..38b9a5b6928 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -72,14 +72,23 @@ struct predictor_info const char *name; /* Name used in the debugging dumps. */ int hitrate; /* Expected hitrate used by predict_insn_def call. */ + int flags; }; -#define DEF_PREDICTOR(ENUM, NAME, HITRATE) {NAME, HITRATE}, +/* Use given predictor without Dempster-Shaffer theory if it matches + using first_match heuristics. */ +#define PRED_FLAG_FIRST_MATCH 1 + +/* Recompute hitrate in percent to our representation. */ + +#define HITRATE(VAL) ((int)((VAL) * REG_BR_PROB_BASE + 50) / 100) + +#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS}, struct predictor_info predictor_info[] = { #include "predict.def" - /* Upper bound on non-language-specific builtins. */ - {NULL, 0} + /* Upper bound on predictors. */ + {NULL, 0, 0} }; #undef DEF_PREDICTOR @@ -211,6 +220,8 @@ combine_predictions_for_insn (insn, bb) rtx *pnote = ®_NOTES (insn); int best_probability = PROB_EVEN; int best_predictor = END_PREDICTORS; + int combined_probability = REG_BR_PROB_BASE / 2; + int d; if (rtl_dump_file) fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), @@ -230,16 +241,33 @@ combine_predictions_for_insn (insn, bb) if (best_predictor > predictor) best_probability = probability, best_predictor = predictor; *pnote = XEXP (*pnote, 1); + + d = (combined_probability * probability + + (REG_BR_PROB_BASE - combined_probability) + * (REG_BR_PROB_BASE - probability)); + /* An FP math to avoid overflows of 32bit integers. */ + combined_probability = (((double)combined_probability) * probability + * REG_BR_PROB_BASE / d + 0.5); } else pnote = &XEXP (*pnote, 1); } + if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) + combined_probability = best_probability; dump_prediction (PRED_FIRST_MATCH, best_probability, bb); + dump_prediction (PRED_COMBINED, combined_probability, bb); if (!prob_note) { REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_BR_PROB, - GEN_INT (best_probability), REG_NOTES (insn)); + GEN_INT (combined_probability), REG_NOTES (insn)); + /* Save the prediction into CFG in case we are seeing non-degenerated + conditional jump. */ + if (bb->succ->succ_next) + { + BRANCH_EDGE (bb)->probability = combined_probability; + FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - combined_probability; + } } } @@ -280,7 +308,8 @@ estimate_probability (loops_info) /* Loop branch heruistics - predict as taken an edge back to a loop's head. */ for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next) - if (e->dest == loops_info->array[i].header) + if (e->dest == loops_info->array[i].header + && e->src == loops_info->array[i].latch) { header_found = 1; predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); @@ -296,10 +325,7 @@ estimate_probability (loops_info) } } - /* Attempt to predict conditional jumps using a number of heuristics. - For each conditional jump, we try each heuristic in a fixed order. - If more than one heuristic applies to a particular branch, the first - is used as the prediction for the branch. */ + /* Attempt to predict conditional jumps using a number of heuristics. */ for (i = 0; i < n_basic_blocks; i++) { basic_block bb = BASIC_BLOCK (i); diff --git a/gcc/predict.def b/gcc/predict.def index ff8171bcc68..577f035e97e 100644 --- a/gcc/predict.def +++ b/gcc/predict.def @@ -36,47 +36,54 @@ Boston, MA 02111-1307, USA. */ REG_BR_PROB_BASE / 2). */ +/* An combined heuristics using Dempster-Shaffer theory. */ +DEF_PREDICTOR (PRED_COMBINED, "combined", PROB_ALWAYS, 0) + /* An combined heuristics using probability determined by first matching heuristics from this list. */ -DEF_PREDICTOR (PRED_FIRST_MATCH, "first match", PROB_ALWAYS) +DEF_PREDICTOR (PRED_FIRST_MATCH, "first match", PROB_ALWAYS, 0) /* Mark unconditional jump as taken. */ -DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS) +DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS, + PRED_FLAG_FIRST_MATCH) /* Use number of loop iterations determined by loop unroller to set - probability. */ -DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS) + probability. We don't want to use Dempster-Shaffer theory here, + as the predictions is exact. */ +DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS, + PRED_FLAG_FIRST_MATCH) /* Hints dropped by user via __builtin_expect feature. */ -DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY) +DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY, + PRED_FLAG_FIRST_MATCH) /* Branch to basic block containing call marked by noreturn attribute. */ -DEF_PREDICTOR (PRED_NORETURN, "noreturn call", PROB_ALWAYS) +DEF_PREDICTOR (PRED_NORETURN, "noreturn call", PROB_ALWAYS, 0) /* Loopback edge is taken. */ -DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", PROB_VERY_LIKELY) +DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", HITRATE (88), 0) /* Edge causing loop to terminate is probably not taken. */ -DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", PROB_LIKELY) +DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE (80), 0) /* Condition emitted by preconditiong code to ensure that variable setting number of iterations is greater than initial value of iterator. */ -DEF_PREDICTOR (PRED_LOOP_CONDITION, "loop condition", PROB_VERY_LIKELY) +DEF_PREDICTOR (PRED_LOOP_CONDITION, "loop condition", PROB_VERY_LIKELY, 0) /* Preconditioning makes linear list of branches. */ -DEF_PREDICTOR (PRED_LOOP_PRECONDITIONING, "loop preconditioning", PROB_VERY_LIKELY) +DEF_PREDICTOR (PRED_LOOP_PRECONDITIONING, "loop preconditioning", PROB_VERY_LIKELY, 0) /* Copied condition for the first iteration of loop is probably true. */ -DEF_PREDICTOR (PRED_LOOP_HEADER, "loop header", PROB_LIKELY) +DEF_PREDICTOR (PRED_LOOP_HEADER, "loop header", HITRATE (75), 0) /* Pointers are usually not NULL. */ -DEF_PREDICTOR (PRED_POINTER, "pointer", PROB_LIKELY) +DEF_PREDICTOR (PRED_POINTER, "pointer", HITRATE (60), 0) /* NE is probable, EQ not etc... */ -DEF_PREDICTOR (PRED_OPCODE, "opcode", PROB_LIKELY) +DEF_PREDICTOR (PRED_OPCODE, "opcode", HITRATE (84), 0) /* Branch guarding call is probably taken. */ -DEF_PREDICTOR (PRED_CALL, "call", PROB_LIKELY) +DEF_PREDICTOR (PRED_CALL, "call", HITRATE (78), 0) /* Branch causing function to terminate is probably not taken. */ -DEF_PREDICTOR (PRED_ERROR_RETURN, "error return", PROB_LIKELY) +DEF_PREDICTOR (PRED_ERROR_RETURN, "error return", PROB_LIKELY, 0) diff --git a/gcc/predict.h b/gcc/predict.h index 3cc52deb0a5..21702183884 100644 --- a/gcc/predict.h +++ b/gcc/predict.h @@ -19,7 +19,7 @@ along with GNU CC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ -#define DEF_PREDICTOR(ENUM, NAME, HITRATE) ENUM, +#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) ENUM, enum br_predictor { #include "predict.def" diff --git a/gcc/profile.c b/gcc/profile.c index fd03d4be074..ddb621a6d19 100644 --- a/gcc/profile.c +++ b/gcc/profile.c @@ -216,7 +216,6 @@ compute_branch_probabilities () int hist_br_prob[20]; int num_never_executed; int num_branches; - int bad_counts = 0; struct bb_info *bb_infos; /* Attach extra info block to each bb. */ @@ -418,84 +417,63 @@ compute_branch_probabilities () { basic_block bb = BASIC_BLOCK (i); edge e; - rtx insn; gcov_type total; rtx note; total = bb->count; - if (!total) - continue; - for (e = bb->succ; e; e = e->succ_next) - { - if (any_condjump_p (e->src->end) - && !EDGE_INFO (e)->ignore - && !(e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))) - { - int prob; - /* This calculates the branch probability as an integer between - 0 and REG_BR_PROB_BASE, properly rounded to the nearest - integer. Perform the arithmetic in double to avoid - overflowing the range of ints. */ - if (total == 0) - prob = -1; - else - { - prob = (((double)e->count * REG_BR_PROB_BASE) - + (total >> 1)) / total; - if (prob < 0 || prob > REG_BR_PROB_BASE) - { - if (rtl_dump_file) - fprintf (rtl_dump_file, "bad count: prob for %d-%d thought to be %d (forcibly normalized)\n", - e->src->index, e->dest->index, prob); - - bad_counts = 1; - prob = REG_BR_PROB_BASE / 2; - } - - /* Match up probability with JUMP pattern. */ - if (e->flags & EDGE_FALLTHRU) - prob = REG_BR_PROB_BASE - prob; - } - - if (prob == -1) - num_never_executed++; - else + if (total) + for (e = bb->succ; e; e = e->succ_next) + { + e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total; + if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) { - int index = prob * 20 / REG_BR_PROB_BASE; - if (index == 20) - index = 19; - hist_br_prob[index]++; + error ("Corrupted profile info: prob for %d-%d thought to be %d\n", + e->src->index, e->dest->index, e->probability); + e->probability = REG_BR_PROB_BASE / 2; } - num_branches++; - - note = find_reg_note (e->src->end, REG_BR_PROB, 0); + } + if (any_condjump_p (bb->end) + && bb->succ->succ_next) + { + int prob; + edge e; + + if (total == 0) + prob = -1; + else + if (total == -1) + num_never_executed++; + else + { + int index; + + /* Find the branch edge. It is possible that we do have fake + edges here. */ + for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU); + e = e->succ_next) + continue; /* Loop body has been intentionally left blank. */ + + prob = e->probability; + index = prob * 20 / REG_BR_PROB_BASE; + + if (index == 20) + index = 19; + hist_br_prob[index]++; + + note = find_reg_note (bb->end, REG_BR_PROB, 0); /* There may be already note put by some other pass, such - as builtin_expect expander. */ + as builtin_expect expander. */ if (note) XEXP (note, 0) = GEN_INT (prob); else - REG_NOTES (e->src->end) + REG_NOTES (bb->end) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob), - REG_NOTES (e->src->end)); + REG_NOTES (bb->end)); } + num_branches++; + } - - /* Add a REG_EXEC_COUNT note to the first instruction of this block. */ - insn = next_nonnote_insn (bb->head); - - if (GET_CODE (bb->head) == CODE_LABEL) - insn = next_nonnote_insn (insn); - - /* Avoid crash on empty basic blocks. */ - if (insn && INSN_P (insn)) - REG_NOTES (insn) - = gen_rtx_EXPR_LIST (REG_EXEC_COUNT, GEN_INT (total), - REG_NOTES (insn)); } - - /* This should never happen. */ - if (bad_counts) - warning ("Arc profiling: some edge counts were bad."); if (rtl_dump_file) { @@ -1004,10 +982,10 @@ end_branch_prob () flag will not be set until an attempt is made to read past the end of the file. */ if (feof (da_file)) - warning (".da file contents exhausted too early\n"); + error (".da file contents exhausted too early"); /* Should be at end of file now. */ if (__read_long (&temp, da_file, 8) == 0) - warning (".da file contents not exhausted\n"); + error (".da file contents not exhausted"); fclose (da_file); } } -- 2.30.2