Re: Incorrect application of loop exit heuristic?

[Jan Hubicka <hubicka at ucw dot cz>]

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

Is it possible for you to send me the SPEC results?

Thanks,
Honza
> 
> -Pat