Generalize table switch pass

[meheff]

The table switch pass transforms a chain of select operations into a table lookup (array_index operation of a literal array). It does this by pattern matching the sequence of selects. This pattern matching is fragile and easily confused. It requires every selector to be of the form x==C for some constant C. A selector which is, say, x==C || x==D would not be matched even if the end result is still a table look up.

Here's one way to generalize the transformation:

Extract the analysis logic of comparison simplification pass which identifies nodes X which are equivalent to some other node Y being in some range R (call this a range equivalence). For example:

 x = eq(y, 42) <=> y \in [42, 42]
 x = ult(y, 123) <=> y \in [0, 122]

After running this analysis, the next step is identifying sets of sequential select instructions whose selectors share related range equivalences (same underlying node y). For example the two select instructions have selectors based on y:

  a = sel(y==3, [C, D])
  b = sel(y==2, [a, E])

These select instructions can be equivalently expressed as a partitioning of the domain of y where each partition has an associated value. For example:

 a = { D   if y \in {[3, 3]}
     { C   if y \in {[0, 2], [4, MAX]}

     { E   if y \in {[2, 2]}
 b = { D   if y \in {[3, 3]}
     { C   if y \in {[0, 1], [4, MAX]}

This can be performed via a dataflow analysis. A natural data structure for this partition map is a ordered map where the map key is a Bits value in the domain of y and the map value is one of the selected constants (e.g., C, D, E). The map key represents the start of a interval in the domain of y where the map value is the result of the select for a value of y in that range. For example, the partition map for b above might be:

  M = {0: C,  # range [0, 1]
       2: E,  # range [2, 2]
       3, D,  # range [3, 3]
       4, C}  # range [4, MAX]

Once this analysis is performed, selects which have an associated partition map can be trivial transformed into a lookup table. This transformation should be robust to selectors which are logical operations on comparisons (e.g., y == 2 || y == 3) as well as supporting comparison operations other than eq/ne (e.g., ult).

I little bit of care needs to be take to ensure that duplicate tables aren't produced (e.g., a table for a and a table for b above). I think the analysis/transformation would be quadratic in the depth of the select chain but I don't think that should be a big problem.

[meheff]

This analysis could also be used to simplify select chains into simpler select chains rather than table lookups. For example, if a large select chain is equivalent to a lookup table that has only two different values and the interval of these values are contiguous (e.g,[A, ..., A, B, ..., B]) then it would be more efficient to express the operation as a select rather than a lookup table. That is: sel(y < r, [B, A]) for some value r.