Re: Incorrect application of loop exit heuristic?

[Pat Haugen <pthaugen at us dot ibm dot com>]

Jan Hubicka <hubicka@ucw.cz> wrote on 08/08/2006 01:04:33 AM:

> > 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.
>
> 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.