Re: [RFC] A new data structure for SWITCH_EXPR

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

On Sun, 2004-11-07 at 23:56 -0500, Kazu Hirata wrote:
> Hi,
> 
> I've been thinking what to do with SWITCH_EXPR.  I came up with one
> possible solution.
> 
> The first step is to change CASE_LABEL_EXPR to tcc_exceptional to
> remove overhead associated with being ..._EXPR.  Let's call the new
> node CASE_LABEL_NODE because it would no longer be an expression.
> 
> The next step is put more fields into CASE_LABEL_NODE.  Here is how.
> 
> Basically, we apply Union-Find-like algorithm to the case labels.  In
> Union-Find terms, we say that two CASE_LABEL_NODEs are "equivalent" if
> they have the the same LABEL_EXPR.
> 
> We define "leader" to be the first case label among those with the
> same LABEL_EXPR.  CASE_LABEL_NODE would have the following 6 fields.
[ ... ]


> 
> a) given CASE_LABEL_NODE, find edge - involves find_edge
This shouldn't be a problem in practice anymore with the changes I
checked in yesterday.  To trigger the nasty compile-time behaviors
you would need the src node in the edge to have a high out
degree _and_ the dest node in the edge to have a high in degree.
I suspect this is extremely rare in practice, though knowing how
the code works I could probably construct such cases.


> b) given edge, find CASE_LABEL_NODE - involves a linear search in the
>    case vector
Yes.

[ ... ]

What I've done is significantly less intrusive.

We have a hash table which allows us to lookup the CASE_LABEL_EXPRs
associated with a particular edge in the CFG.

Edge redirection becomes pretty simple in that case.

  1. Lookup the edge in the hash table to get a list of CASE_LABEL_EXPRs
     which reference that edge.

  2. Call ssa_redirect_edge on the edge, store the result into f.

  3. Walk the list of CASE_LABEL_EXPRs from step #1 and update
     CASE_LABEL for each of them.

     3a. If e != f, then splice the list of CASE_LABEL_EXPRs associated
         with e into the list of CASE_LABEL_EXPRs associated with f.

Note we still have a linear search, but we're only walking those
CASE_LABEL_EXPR nodes which go to the same destination.

We have to hook into the tree-cfg code in three places to accomplish
this:

  1. When we build edges for the SWITCH_EXPR, we need to also put them
     into the hash table.

  2. When an edge is removed, we may need to remove it from the hash
     table.

  3. When an edge is redirected, we may need to splice together the
     CASE_LABEL_EXPRs.


Note that we don't change the underlying representation of SWITCH_EXPR
or CASE_LABEL_EXPR.


> 
> I'll skip b) for now although I have an idea.  b) happens mainly in
> tree_redirect_edge_and_branch to update case labels upon edge
> redirection.  If we drop labels, we don't have to update labels.
But you still need to update the case leaders.  This corresponds
roughly to my splicing of the CASE_LABEL_EXPR lists together.

We might even consider the less intrusive scheme for 4.0 and your
redesign for 4.1.  I haven't formed a strong opinion about these
issues yet.

Jeff