mozilla/rust — Issue #1897: Alt optimizations
Author: jruderman
Created: 2012-02-24 18:38:30+00:00
State: open

Let's take advantage of enum types and alt-expressions to optimize code that uses `alt`. Some of these optimizations might require teaching LLVM about the restrictions on enums, or doing the work ourselves in trans_alt.

### Algorithm selection

Based on the cases, pick a map structure:
* For dense enums, use `i = (x - smallest)`
* For sparse enums, use `i = perfecthash(x)`
* For strings, look up `i` in a hash table
* For int ranges, consider a binary search
* Otherwise (e.g. pattern matching) fall back on testing each case (if/elif/else)

Based on the branches, pick an output type:
* For constant values, use `i` as an index into an array of values
* For similar-length blocks, pad the shorter blocks with nops, and jump to `i * block_length`
* For differing-length blocks, use `i` as an index into an array of jump offsets

In this example, the cases are a dense enum and the branches are values:

y = alt x { red { 9 } green { 1 } blue { 4 } }

So it can use an array of values, with no branching (even for a bounds check):

const_table = [9, 1, 4]
y = const_table[x as uint]

This is something Mozilla programmers do in C++ all the time, manually, often [messing it up](http://glandium.org/blog/?p=2361).

### Optimizations for if/elif/else compilation

Omit the last "else if" check when the alt is exhaustive, turning these into a simple "if":

alt x { one {} _ {} }
alt x { one {} two {} }

Reorder cases in order to put a difficult case at the end (where it can be omitted):

alt { one, three { 5 } two { 7 } }

Collapse adjacent cases into a single less-than check:

alt x { one, two, three { 7 } four, five, six { 9 } }

### "Pass through" optimization

Compile as "pass through" if the arms all match the values. Useful when translating between two enum types.

alt x { one { 1 } two { 2 } }
alt x { one { one_ } two { two_ } }