Re: PR/7344 - O(n^2) algorithm?

[Jan Hubicka <jh at suse dot cz>]

> Hello,
> 
> > I looked at PR/7344 which is entitled
> > 
> > "performance regression on huge case statements"
> > 
> > The problem appears to be bad O-complexity scalability in        
> > process_note_prediction. It contains this loop:
> > 
> >   /* Now find the edge that leads to our branch and aply the
> > prediction.  */
> > 
> >   if (y == last_basic_block)
> >     return;
> >   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
> >     if (e->dest->index >= 0
> >         && dominated_by_p (post_dominators, e->dest, bb))
> >       predict_edge_def (e, pred, taken);
> > 
> > This algorithm appears to be O(n^2) for our testcase.
> > There seem to be 10,000 basic blocks dominated by each other,
> > so predict_edge_def() would be called 100 million times.
> > 
> > Is there an alternate solution for this problem?
> 
> Yes, I can imagine it can happen. Considering that
> 
> - handling the situation correctly&fast in this case is not easy

Currently any predictions to multiway branches are ignored as we don't
have way to handle them in the RTL, so it is safe to just give up
on BB with more than 2 succesors.

Honza
> - resulting predictions are not very useful nor reliable
> - this case should not be too frequent
> 
> I would solve this by simply giving up provided that BASIC_BLOCK (y) has
> more than some constant number of succesors.
> 
> Zdenek