This is the mail archive of the
mailing list for the GCC project.
Incorrect application of loop exit heuristic?
- From: Pat Haugen <pthaugen at us dot ibm dot com>
- To: gcc at gcc dot gnu dot org
- Date: Mon, 7 Aug 2006 14:39:32 -0500
- Subject: Incorrect application of loop exit heuristic?
I was looking in to a degradation for perlbmk on PowerPC and tracked it
down to a mispredicted branch within a loop ( if (...) return 0; within
the loop). GCC is statically predicting the loop exit as not taken "bne-",
but it is obviously being taken the greatest share of the time because when
I remove the prediction "-", the degradation disappears.
I'm wondering if the heuristic for a loop exit is being applied
correctly. predict.def defines PRED_LOOP_EXIT with a hitrate of 90,
meaning we'll only exit the loop 10% of the time. But when this heuristic
is applied to the CFG in predict.c:predict_loops(), it is dividing that 10%
by the number of exits in the loop and then assigning that probability. In
the case I was looking at, a probability of 0.2% ended up being assigned
(quite a few exits in the loop), which then resulted in the branch being
statically predicted because it crossed the 98%/2% threshold where branches
are predicted. Should the 10% probability be applied without dividing by
the number of exits (i.e. each exit has a 10% probability of being taken,
independent of other loop exits)? The way things are now, once we get more
than 5 exits in a loop those exits may be statically predicted as not taken
since their probabilities will be less than the 2% threshold.
The benchmark code in question was a fairly large switch statement within a
loop, having several 'return' statements in the various 'case' legs.