This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Incorrect application of loop exit heuristic?
> >
> >
> > Pat Haugen <pthaugen@us.ibm.com> wrote on 08/08/2006 11:07:58 AM:
> >
> > > Jan Hubicka <hubicka@ucw.cz> wrote on 08/08/2006 01:04:33 AM:
> > >
> > > > The code there is basically avoiding loops with many exists to be
> > > > predicted to not loop at all (ie if you have 10 exits, having every
> > exit
> > > > with 10% probability is going to make 0.9^10 (roughly 30%) probability
> > > > that the loop will trip.
> > > >
> > > > The code is not quite correct - first it should be computing -10th
> > power
> > > > of the probability (that is close enough to division) and also it
> > should
> > > > track down number of exist conditionals executed each iteration...
> > > > Would be possible to benchmark the SPEC without this division for
> > start?
> > > > How many exit conditionals are executed per iteration in your loop?
> > > >
> > >
> > > I did a quick scan of the loop in question. There are 62 exits in the
> > > loop, but best I could tell, the most that would ever be seen on a single
> > > iteration of the loop is 9 since most the case legs end with a 'break'.
> > >
> > > Another alternative a colleague and I kicked around was something like
> > > applying "max(10%/num_exits, 2%)" as the probability of the exit edges.
> > >
> >
> > I tried the "max(10%/num_exits, 2%)" approach and reran SPEC. Got back the
> > degradation on perlbmk and then some (7% improvement), also saw a couple
> > others improve by a couple percent. If this sounds like an acceptable
> > approach, I can submit a patch.
>
> Hi,
> thepatch limiting minimal probability to 2% seems to make sense to me,
> so please submit it for review. It would be nice to have the code to
> compute maximal number of exits from loop too, but if it is really 9, we
> would end up with 1% (it might however make difference elsewhere).
> If you would feed motivated to do so, please just do ;) Otheriwse I will
> add it to my ever growing TODO list.
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?
index: predict.c
===================================================================
*** predict.c (revision 116257)
--- 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: rtl.h
===================================================================
*** rtl.h (revision 116257)
--- rtl.h (working copy)
*************** enum label_kind
*** 1029,1035 ****
/* Maximum cost of an rtl expression. This value has the special meaning
not to use an rtx with this cost under any circumstances. */
#define MAX_COST INT_MAX
-
extern void init_rtlanal (void);
extern int rtx_cost (rtx, enum rtx_code);
extern int address_cost (rtx, enum machine_mode);
--- 1029,1034 ----
Index: basic-block.h
===================================================================
*** basic-block.h (revision 116257)
--- 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 116257)
--- 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 116257)
--- 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))