[RFC] A new data structure for SWITCH_EXPR

[Zack Weinberg]

Kazu Hirata <kazu@cs.umass.edu> writes:
> I've been thinking what to do with SWITCH_EXPR.  I came up with one
> possible solution.

Keep in mind that I'm not sure what the problems are - I gather that
there are time and possibly space complexity concerns with the way it
works now, but that's all I know.

That said:

> 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.
>
> CASE_LOW
>   as usual
>
> CASE_HIGH
>   as usual
>
> CASE_LABEL
>   as usual, but we will drop these labels during the lifetime of CFG.
>
> CASE_LEADER
>   an integer.  The index of the leader for this case label.  If this
>   case label is a leader, CASE_LABEL is the index of this case label.
>
> CASE_EDGE
>   an edge.  Replacement for CASE_LABEL.  Valid only when this case
>   label is a leader.

First, I'd like to point out that use of the "case A ... B:" feature
is extremely rare, at least when it's via the GNU extension to C.
Perhaps other languages use it more frequently.  As such, it might
make sense to drop CASE_HIGH entirely, having front ends break up A
... B into individual CASE_LABEL_NODEs for all the values in the
range.  Ranges would get more expensive, but each individual case
would get cheaper.

Second, I do not see the need for both CASE_LEADER and CASE_EDGE.  Why
not put the edge directly into all the cases sharing it?  The *same*
edge, not a copy of it in each CASE_LABEL.  Then redirecting that edge
is a matter simply of changing the successor pointer.  You have to
update every case label node when you merge two case blocks, but you
had to do that anyway.

zw