Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Jeffrey A Law <law at redhat dot com>]

On Wed, 2004-11-10 at 02:34 +0100, Steven Bosscher wrote:
> > Actually this was O(p) where p is the number of unique outgoing
> > edges.  Now it's O(min (p,q)) where p is the number of unique
> > outgoing edges and q is the number of unique incoming edges
> > into the destination block.  Typically q is significantly
> > smaller than p or n for switch statements.
> 
> That was a nice catch, yes :-)
I'd noticed it before and when it showed its ugly head again on
15524 we were finally in a position to actually solve it thanks
to those who worked on the edge-vector changes.

> 
> 
> > > edge -> CASE_LABEL_EXPR
> > >   O(n).  Performed in tree_redirect_edge_and_branch.
> >
> > Yup.  And this is actually the real killer these days.
> 
> Yup, this is a real problem in the critical edge splitting pass and
> thread_jumps_from_bb.  Here are some bits from a gprof profile for
> the very artificial code of PR15524:
I'm well aware of it  :( It's going to stick out even worse once I fix
flow_dfs_compute_reverse_execute which accounts for the remaining
lameness charged PRE and branch prediction.


> You think of this as a single, global hash table, or a hash table for
> each SWITCH_EXPR?  You'd guess the latter is overkill but the former
> could grow just huge for test cases of the kind of PR15524.  How would
> you add the cases to the hash element for the edge?  Some linked list
> for that?
I've prototyped it as a single global hash table.  It works damn well
for 15524, but I haven't looked at its behavior for more sane code.

There's this nagging voice telling me there's a better way, possibly
using a combination of Kazu's ideas and a hash table.  Anyway, I'm
continuing to prototype various approaches to see where their
strengths and weaknesses are.

> The *cough* good news is that despite all the new tree-ssa passes with
> their wards, CSE and reg_scan are now consistenly back on top in almost
> any profile I look at ;-)
Good.  That's the way I want the profiles to look right now :-)

Jeff