antlr/antlr4 — pull request #89 by sharwell (2012-11-27 15:15:00+00:00)
Title: Optimized set comparisons

I implemented this optimization in several phases. Initially, all set comparisons were naively switched over to bitwise tests. Over the next 3 commits I optimized these tests and restricted their use to larger comparisons like the example below.

Previously, the generated code could include Boolean expressions like the following.

```
_la==ACTION_DOT || _la==ACTION_LT || _la==ACTION_GT
|| _la==ACTION_LPAREN || _la==ACTION_RPAREN || _la==ACTION_LBRACK
|| _la==ACTION_RBRACK || _la==ACTION_EQUALS || _la==ACTION_COMMA
|| _la==ACTION_COLON2 || _la==ACTION_COLON || _la==ACTION_MINUS
|| _la==ACTION_ESCAPE || _la==ACTION_WORD || _la==ACTION_REFERENCE
|| _la==ACTION_COMMENT || _la==ACTION_LITERAL || _la==ACTION_TEXT
|| _la==ACTION_WS || _la==ACTION_NEWLINE
```

After this change, the generated code for this expression is the following:

```
(((_la - 66)) & ~0x3f) == 0
&& ((1L << (_la - 66))
& ((1L << (ACTION_DOT - 66)) | (1L << (ACTION_LT - 66))
| (1L << (ACTION_GT - 66)) | (1L << (ACTION_LPAREN - 66))
| (1L << (ACTION_RPAREN - 66)) | (1L << (ACTION_LBRACK - 66))
| (1L << (ACTION_RBRACK - 66)) | (1L << (ACTION_EQUALS - 66))
| (1L << (ACTION_COMMA - 66)) | (1L << (ACTION_COLON2 - 66))
| (1L << (ACTION_COLON - 66)) | (1L << (ACTION_MINUS - 66))
| (1L << (ACTION_ESCAPE - 66)) | (1L << (ACTION_WORD - 66))
| (1L << (ACTION_REFERENCE - 66)) | (1L << (ACTION_COMMENT - 66))
| (1L << (ACTION_LITERAL - 66)) | (1L << (ACTION_TEXT - 66))
| (1L << (ACTION_WS - 66)) | (1L << (ACTION_NEWLINE - 66))))
!= 0)
```

The Java compiler folds the long expression into a single constant in the compiled code, so I left it in expanded form here so it's easy to read (and see which specific tokens it's testing for). The comparison simplifies to the following pseudo-expression:

```
(input & ~0x3f) == 0 && ((1L << input) & mask) != 0
```

The expression `(input & ~0x3f) == 0` is required due to section [15.19 of the Java language specification](http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19), which says the right hand side of the `<<` operator is masked rather than allow the operation to overflow to 0.

The compiled bytecode for this example expression is ___ bytes (___ opcodes) shorter than the original.