Re: [RFC] A new data structure for SWITCH_EXPR

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi Zack,

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

Sorry, the problems are described in

http://gcc.gnu.org/ml/gcc/2004-10/msg00911.html

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

Well, "case A...B:" are actually common because group_case_labels
groups case labels like

  case 1:
  case 2:
  case 3: goto <L1>;

into

  case 1..3: goto <L1>;

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

Redirecting an edge is not necessarily done by changing e->dest.  If
the edge after redirection already exists, the existing edge is
returned, and the edge you pass to redirect_edge_succ is deleted.
When this happens, we don't want to update multiple case labels
holding the edge before redirection.

That said, I don't expcet this "collision" to occur too often
(although it's easy to construct a pathological testcase).  Maybe we
can live without CASE_LEADER.

> You have to update every case label node when you merge two case
> blocks, but you had to do that anyway.

I am thinking about dropping labels entirely during the lifetime of
CFG.  As a first step, I am planning to submit a patch to drop labels
in COND_EXPR.  Once SWITCH_EXPR is edge-aware, we can drop labels from
SWITCH_EXPR, too.

Kazu Hirata