This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Incorrect application of loop exit heuristic?
- 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))