This is the mail archive of the
mailing list for the GCC project.
Re: Incorrect application of loop exit heuristic?
- From: Pat Haugen <pthaugen at us dot ibm dot com>
- To: Jan Hubicka <hubicka at ucw dot cz>
- Cc: gcc at gcc dot gnu dot org
- Date: Tue, 8 Aug 2006 11:07:58 -0500
- Subject: Re: Incorrect application of loop exit heuristic?
Jan Hubicka <firstname.lastname@example.org> wrote on 08/08/2006 01:04:33 AM:
> > are predicted. Should the 10% probability be applied without dividing
> > the number of exits (i.e. each exit has a 10% probability of being
> > independent of other loop exits)? The way things are now, once we get
> > than 5 exits in a loop those exits may be statically predicted as not
> > since their probabilities will be less than the 2% threshold.
> > The benchmark code in question was a fairly large switch statement
> > 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.