Re: Attacking quadratic behaviors associated with SWITCH_EXPR

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

On Fri, 2004-10-22 at 20:43 -0400, Kazu Hirata wrote:

> INTEGER_CST -> CASE_LABEL_EXPR
>   O(log n).  Implemented in find_case_label_for_value.
Typically only performed when we know the incoming value for the 
SWITCH_COND.  Given that it's a binary search, I'm terribly worried
about this one right now.


> CASE_LABEL_EXPR -> LABEL_DECL
>   O(1).  This is a primitive operation.
Yup.  Note this is primarily done during coalescing adjacent cases,
expansion and when redirecting edges out of the SWITCH_EXPR via
the need to map from CASE_LABEL_EXPR to a basic block.


> 
> CASE_LABEL_EXPR -> basic_block (via LABEL_DECL)
>   O(1).  Implemented in label_to_block.
I believe this happens primarily when redirecting edges out of 
the SWITCH_EXPR.


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

> 
> edge -> CASE_LABEL_EXPR
>   O(n).  Performed in tree_redirect_edge_and_branch.
Yup.  And this is actually the real killer these days.


> 
> 1. add "edge e;" to stmt_ann_d
> 
> 2. allocate stmt_ann for each CASE_LABEL_EXPR
Ouch. 


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


> to get an edge equivalent to find_edge (label_to_block (CASE_LABEL ()))
> in constant time.  Now the obvious concern is memory consumption
> arising from having edge for every statement with stmt_ann.  I need
> come clever ideas here.  Maybe a hash table mapping CASE_LABEL_EXPR to
> edge
Well, I wouldn't tackle CASE_LABEL_EXPR to edge right now -- it's not
as important as edge to CASE_LABEL_EXPRs with my recent change to
find_edge.


> ======================================================================
> 
> Second, I am thinking about improving "edge -> CASE_LABEL_EXPR" as
> follows.
> 
> 1. Have exactly one CASE_LABEL_EXPR per edge by doing something like
>    this
> 
>    case 6 ... 8, 16 ... 20: goto <L5>;
> 
>    This means that we goto <L5> if a value given to the SWITCH_EXPR is
>    between 6 and 8 or 16 and 20.
Or chain together CASE_LABEL_EXPRs which hit the same destination
via their TREE_CHAIN field.  Your scheme might be cheaper for the
edge->case_label_expr case, but it may also introduce inefficiencies
elsewhere (INTEGER_CST->CASE_LABEL_EXPR and dealing with edge
redirections where two previously disjoint cases now reach the
same destination).


> 2. Create a sorted array of single ranges like 6...8, so that
>    "INTEGER_CST -> CASE_LABEL_EXPR" can continue to use a binary
>    search.
> 
> 3. Put the sorted array in the SWITCH_EXPR.  As a result, the
>    SWITCH_EXPR would have a sorted array of ranges *and* an array of
>    CASE_LABEL_EXPRs.
> 
> 4. Put a pointer in edge to point back to CASE_LABEL_EXPR.
> 
> Then we should be able to do "edge -> CASE_LABEL_EXPR" in constant
> time.
Yea, but I think you end up paying a pretty high cost when you need
to merge.  Of course the other schemes I've pondered have a high cost
then as well.



> I think it's easier to address "CASE_LABEL_EXPR -> edge", and that
> should probably be done first.
Possibly, but it's not going to give you the big win that dealing
with edge->CASE_LABEL_EXPR(s) would give you.

jeff