This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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.

-Pat


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]