Re: Attacking quadratic behaviors associated with SWITCH_EXPR

[Steven Bosscher <stevenb at suse dot de>]

On Wednesday 10 November 2004 01:52, Jeffrey A Law wrote:
> > CASE_LABEL_EXPR -> edge (via LABEL_DECL and basic_block)
> >   O(n).  Performed in find_taken_edge_switch_expr.
> >   Implemented as label_to_block, followed by find_edge
>
> 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 :-)


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

-----------------------------------------------
                0.01   68.18   10000/100002      thread_block [37]
                0.01   68.20   10002/100002      try_forward_edges [50]
                0.02  204.55   30000/100002      tree_split_edge [23]
                0.03  340.92   50000/100002      thread_jumps_from_bb [20]
[13]    46.6    0.06  681.85  100002         redirect_edge_and_branch [13]
              264.76  412.78   90000/100000      tree_redirect_edge_and_branch [12]
                0.00    4.30   10002/10002       rtl_redirect_edge_and_branch [98]
-----------------------------------------------

It's tree_redirect_edge_and_branch that is quadratic if most outgoing
edges of a block ending in a SWITCH_EXPR are critical edges.

(Note that pass_split_crit_edges really shouldn't be a pass.  It only
provides a property, PROP_no_crit_edges, but it's run unconditionally,
so even with -fno-tree-pre (which is the only pass that requires this
property) we still run the pass_split_crit_edges pass - wasteful!)


> > 3. stop using CASE_LABEL of CASE_LABEL_EXPR after CFG is created.  In
> >    fact, we should probably put null in CASE_LABEL so that people
> >    won't mistakenly use it.
>
> Very reasonable.  This alone is reasonably easy to accomplish without
> changing how we represent the CASE_LABEL_EXPR.  We have a hash table
> which maps an edge to the cases utilizing that edge.

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?

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 ;-)

Gr.
Steven