[RFC] A new data structure for SWITCH_EXPR

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

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.

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.

For example,

  switch (a)
    {
    case 1   : goto <L5>;
    case 2..3: goto <L7>;
    case 5   : goto <L5>;
    case 9   : goto <L8>;
    default  : goto <L9>;
    }

would generate the following case label vector.

index  LOW HIGH LABEL LEADER  EDGE
    0    1 null    L5      0 valid  <- leader of cases going to L5
    1    2    3    L7      1 valid  <- leader of cases going to L7
    2    5 null    L5      0  null  <- not leader
    3    9 null    L8      3 valid  <- leader of cases going to L8
    4 null null    L9      4 valid  <- leader

The O(n) operations that we are concerned about are

a) given CASE_LABEL_NODE, find edge - involves find_edge

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

First, about a).  Given a CASE_LABEL_NODE node, we find its associated
edge as follows.  This part corresponds to the Find operation of
Union-Find algorithm.

edge
find_edge_for_case_label (tree node)
{
  int index = CASE_LEADER (node);

  while (CASE_LEADER (node) != index)
    {
      index = CASE_LEADER (node);
      node = TREE_VEC_ELT (case_vector, index);
    }

  return CASE_EDGE (TREE_VEC_ELT (case_vector, index));
}

In English, we keep following CASE_LABEL_LEADER until we get to a
leader.

An edge redirection proceeds as follows.  Suppose we are in
tree_redirect_edge_and_branch and are asked to redirect edge e, an
outgoing edge from a basic block ending with SWITCH_EXPR.

1) Call ssa_redirect_edge on e.  Store the result to f.

2) If e == f, return without doing any further work.

3) Otherwise, we need to update CASE_LEADER.  This part more or less
   corresponds to the Union operation of Union-Find algorithm.
   Specifically, we find a CASE_LABEL_NODE with its edge being e using
   a linear search.  (Note that there is only one such node, namely a
   leader.)  Similarly find a CASE_LABEL_NODE with its edge being f.
   If e's index is smaller than f's index, change f's CASE_LEADER to
   e's index.  Otherwise, do the opposite.  In either case, we clear
   the edge field of the non-leader.

Unfortunately, step 3) above still involves a linear search, but I
would expect it to have a minor impact because if we have e != f, that
means two case labels become "equivalent".  That should be far less
frequent than the e == f case because one label must have dead code.

Of course, we can do path compression, but I avoided it to simplify
the description.

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.

p.s.
Actually, we could speed up the linear search above by stealing 8 bits
or so from edge flags to store "index % 256" into flags, where index
is the index of the leader case label.  Although this trick does not
cure the asymptotic behavior of the linear search, it would help a lot
in real-world programs.

Kazu Hirata