This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] PR/7344, O(n^2) branch prediction
- From: Brad Lucier <lucier at math dot purdue dot edu>
- To: rakdver at atrey dot karlin dot mff dot cuni dot cz (Zdenek Dvorak)
- Cc: dberlin at dberlin dot org (Daniel Berlin), tm at mail dot kloo dot net (tm), lucier at math dot purdue dot edu (Brad Lucier), jh at suse dot cz, gcc-patches at gcc dot gnu dot org
- Date: Thu, 5 Sep 2002 19:34:19 -0500 (EST)
- Subject: Re: [PATCH] PR/7344, O(n^2) branch prediction
>
> > > > > > I tried to make bootstrap, but it didn't finish due to unrelated issues.
> > > > > > Would appreciate if you could run it.
> > > > >
> > > > > OK, it's in progress. Results in a few hours.
> > > > >
> > > > > Brad
> > > > >
> > > >
> > > > Also, it would be good if someone more familiar with branch prediction
> > > > checked the patch, and make sure I'm testing for the right condition...
> > >
> > > ! for (e = BASIC_BLOCK (y)->succ, count = 0; e; e = e->succ_next)
> > > ! {
> > > ! if (++count >= 2)
> > > ! break;
> > > ! if (e->dest->index >= 0
> > > ! && dominated_by_p (post_dominators, e->dest, bb))
> > > ! predict_edge_def (e, pred, taken);
> > > ! }
> > >
> > > I believe there should be "if (count++ >= 2)"; the way it is here it
> > > will break too soon.
> >
> > No it won't, it'll break if the branch is multiway. Multiway is > 1, not
> > > 2.
> >
> > In fact, the whole loop is pointless, since it will only execute once. You
> > might as well just say
> > if (BASIC_BLOCK (y)->succ)
> > {
> > ...
> > }
>
> But this is wrong -- we want it to work for ordinary conditional jumps,
> i.e. we really want to break only if >2; alternatively
> we could test for anycondjump_p.
Well, the patch as it was originally written was tested at
http://gcc.gnu.org/ml/gcc-testresults/2002-09/msg00163.html
which has many fewer g++ and g77 failures than without the patch:
http://gcc.gnu.org/ml/gcc-testresults/2002-09/msg00149.html
Perhaps if you guys can figure out what the right condition should be,
it can be tested again.
Brad