google / google/xls

Generalize table switch pass

Open
#535 1 comment 0 reactions 0 assignees View on GitHub
optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.