This is the mail archive of the
`gcc@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Jan Hubicka <jh at suse dot cz>*To*: Pat Haugen <pthaugen at us dot ibm dot com>, gcc-patches at gcc dot gnu dot org*Cc*: gcc at gcc dot gnu dot org, Jan Hubicka <hubicka at ucw dot cz>*Date*: Thu, 24 Aug 2006 00:32:11 +0200*Subject*: Re: Incorrect application of loop exit heuristic?*References*: <OF0FC22222.30F5407A-ON862571D1.00643F1A-862571D1.0064EE66@us.ibm.com> <OFD5781BD1.2A7FE0A4-ON862571D3.0055ECEB-862571D3.00564D7A@us.ibm.com>

> > > Pat Haugen <pthaugen@us.ibm.com> wrote on 08/21/2006 01:22:25 PM: > > > Jan Hubicka <hubicka@ucw.cz> wrote on 08/19/2006 07:51:42 PM: > > > > > Hi, > > > this patch at least hides the ugly details within some abstraction so > we > > > can eventally go for propagating reliability information across CFG if > > > we conclude it is important. How does it work for you? > > > > > > > I like your approach, thanks. I've confirmed that the generated code no > > longer contains the mis-predicted branch hints. Will follow up with > > results from SPEC run once I get them (hosed things up for myself, so > > restarting from scratch) :-( > > > > -Pat > > > > The results with your patch mimicked the results of my initial attempt: > perlbmk improved 7% and a couple others improved a couple percent. Happy to hear that! I've comitted the attached patch. Thank you for tracking this, very interesting, dead end of predictor machinery. Honza Index: ChangeLog =================================================================== *** ChangeLog (revision 116357) --- ChangeLog (working copy) *************** *** 1,3 **** --- 1,15 ---- + 2006-08-24 Jan Hubicka <jh@suse.cz> + + * predict.c (probability_reliable_p): New predicate. + (edge_probability_reliable_p, br_prob_note_reliable_p): Likewise. + (predict_loops): Do not predict loop exit with less than 2% + probability. + * basic-block.h (edge_probability_reliable_p, + br_prob_note_reliable_p): Declare. + * ia64.h (ia64_print_operand): Do not disable on-chip branch + prediction when static predictor is not reliable. + * rs6000.c (output_cbranch): Likewise. + 2006-08-23 Stuart Hastings <stuart@apple.com> PR 28825 Index: predict.c =================================================================== *** predict.c (revision 116355) --- predict.c (working copy) *************** tree_predicted_by_p (basic_block bb, enu *** 178,183 **** --- 178,222 ---- return false; } + /* Return true when the probability of edge is reliable. + + The profile guessing code is good at predicting branch outcome (ie. + taken/not taken), that is predicted right slightly over 75% of time. + It is however notorously poor on predicting the probability itself. + In general the profile appear a lot flatter (with probabilities closer + to 50%) than the reality so it is bad idea to use it to drive optimization + such as those disabling dynamic branch prediction for well predictable + branches. + + There are two exceptions - edges leading to noreturn edges and edges + predicted by number of iterations heuristics are predicted well. This macro + should be able to distinguish those, but at the moment it simply check for + noreturn heuristic that is only one giving probability over 99% or bellow + 1%. In future we might want to propagate reliablity information across the + CFG if we find this information useful on multiple places. */ + static bool + probability_reliable_p (int prob) + { + return (profile_status == PROFILE_READ + || (profile_status == PROFILE_GUESSED + && (prob <= HITRATE (1) || prob >= HITRATE (99)))); + } + + /* Same predicate as above, working on edges. */ + bool + edge_probability_reliable_p (edge e) + { + return probability_reliable_p (e->probability); + } + + /* Same predicate as edge_probability_reliable_p, working on notes. */ + bool + br_prob_note_reliable_p (rtx note) + { + gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB); + return probability_reliable_p (INTVAL (XEXP (note, 0))); + } + static void predict_insn (rtx insn, enum br_predictor predictor, int probability) { *************** predict_loops (struct loops *loops_info, *** 706,719 **** /* Loop exit heuristics - predict an edge exiting the loop if the conditional has no loop header successors as not taken. */ if (!header_found) ! FOR_EACH_EDGE (e, ei, bb->succs) ! if (e->dest->index < NUM_FIXED_BLOCKS ! || !flow_bb_inside_loop_p (loop, e->dest)) ! predict_edge ! (e, PRED_LOOP_EXIT, ! (REG_BR_PROB_BASE ! - predictor_info [(int) PRED_LOOP_EXIT].hitrate) ! / n_exits); } /* Free basic blocks from get_loop_body. */ --- 745,775 ---- /* Loop exit heuristics - predict an edge exiting the loop if the conditional has no loop header successors as not taken. */ if (!header_found) ! { ! /* For loop with many exits we don't want to predict all exits ! with the pretty large probability, because if all exits are ! considered in row, the loop would be predicted to iterate ! almost never. The code to divide probability by number of ! exits is very rough. It should compute the number of exits ! taken in each patch through function (not the overall number ! of exits that might be a lot higher for loops with wide switch ! statements in them) and compute n-th square root. ! ! We limit the minimal probability by 2% to avoid ! EDGE_PROBABILITY_RELIABLE from trusting the branch prediction ! as this was causing regression in perl benchmark containing such ! a wide loop. */ ! ! int probability = ((REG_BR_PROB_BASE ! - predictor_info [(int) PRED_LOOP_EXIT].hitrate) ! / n_exits); ! if (probability < HITRATE (2)) ! probability = HITRATE (2); ! FOR_EACH_EDGE (e, ei, bb->succs) ! if (e->dest->index < NUM_FIXED_BLOCKS ! || !flow_bb_inside_loop_p (loop, e->dest)) ! predict_edge (e, PRED_LOOP_EXIT, probability); ! } } /* Free basic blocks from get_loop_body. */ Index: basic-block.h =================================================================== *** basic-block.h (revision 116355) --- basic-block.h (working copy) *************** extern void rtl_predict_edge (edge, enum *** 880,885 **** --- 880,887 ---- extern void predict_edge_def (edge, enum br_predictor, enum prediction); extern void guess_outgoing_edge_probabilities (basic_block); extern void remove_predictions_associated_with_edge (edge); + extern bool edge_probability_reliable_p (edge); + extern bool br_prob_note_reliable_p (rtx); /* In flow.c */ extern void init_flow (void); Index: config/ia64/ia64.c =================================================================== *** config/ia64/ia64.c (revision 116355) --- config/ia64/ia64.c (working copy) *************** ia64_print_operand (FILE * file, rtx x, *** 4656,4666 **** int pred_val = INTVAL (XEXP (x, 0)); /* Guess top and bottom 10% statically predicted. */ ! if (pred_val < REG_BR_PROB_BASE / 50) which = ".spnt"; else if (pred_val < REG_BR_PROB_BASE / 2) which = ".dpnt"; ! else if (pred_val < REG_BR_PROB_BASE / 100 * 98) which = ".dptk"; else which = ".sptk"; --- 4656,4668 ---- int pred_val = INTVAL (XEXP (x, 0)); /* Guess top and bottom 10% statically predicted. */ ! if (pred_val < REG_BR_PROB_BASE / 50 ! && br_prob_note_reliable_p (x)) which = ".spnt"; else if (pred_val < REG_BR_PROB_BASE / 2) which = ".dpnt"; ! else if (pred_val < REG_BR_PROB_BASE / 100 * 98 ! || !br_prob_note_reliable_p (x)) which = ".dptk"; else which = ".sptk"; Index: config/rs6000/rs6000.c =================================================================== *** config/rs6000/rs6000.c (revision 116355) --- config/rs6000/rs6000.c (working copy) *************** output_cbranch (rtx op, const char *labe *** 11498,11504 **** mispredicted taken branch is more expensive than a mispredicted not-taken branch. */ if (rs6000_always_hint ! || abs (prob) > REG_BR_PROB_BASE / 100 * 48) { if (abs (prob) > REG_BR_PROB_BASE / 20 && ((prob > 0) ^ need_longbranch)) --- 11498,11505 ---- mispredicted taken branch is more expensive than a mispredicted not-taken branch. */ if (rs6000_always_hint ! || (abs (prob) > REG_BR_PROB_BASE / 100 * 48 ! && br_prob_note_reliable_p (note))) { if (abs (prob) > REG_BR_PROB_BASE / 20 && ((prob > 0) ^ need_longbranch))

**References**:**Re: Incorrect application of loop exit heuristic?***From:*Pat Haugen

**Re: Incorrect application of loop exit heuristic?***From:*Pat Haugen

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |