Switch translation

[Remi Forax]

> De: "Brian Goetz" <brian.goetz at oracle.com>
> À: "amber-spec-experts" <amber-spec-experts at openjdk.java.net>
> Envoyé: Vendredi 6 Avril 2018 17:51:49
> Objet: Switch translation

> The following outlines our story for translating improved switches, including
> both the switch improvements coming as part of JEP 325, and follow-on work to
> add pattern matching to switches. Much of this has been discussed already over
> the last year, but here it is in one place.

> # Switch Translation
> #### Maurizio Cimadamore and Brian Goetz
> #### April 2018

> ## Part 1 -- constant switches

> This part examines the current translation of `switch` constructs by `javac`,
> and proposes a more general translation for switching on primitives, boxes,
> strings, and enums, with the goals of:

> - Unify the treatment of `switch` variants, simplifying the compiler
> implementation and reducing the static footprint of generated code;
> - Move responsibility for target classification from compile time to run time,
> allowing us to more freely update the logic without updating the compiler.

> ## Current translation

> Switches on `int` (and the smaller integer primitives) are translated in one of
> two ways. If the labels are relatively dense, we translate an `int` switch to a
> `tableswitch`; if they are sparse, we translate to a `lookupswitch`. The
> current heuristic appears to be that we use a `tableswitch` if it results in a
> smaller bytecode than a `lookupswitch` (which uses twice as many bytes per
> entry), which is a reasonable heuristic.

> #### Switches on boxes

> Switches on primitive boxes are currently implemented as if they were primitive
> switches, unconditionally unboxing the target before entry (possibly throwing
> NPE).

> #### Switches on strings

> Switches on strings are implemented as a two-step process, exploiting the fact
> that strings cache their `hashCode()` and that hash codes are reasonably spread
> out. Given a switch on strings like the one below:

> switch (s) {
> case "Hello": ...
> case "World": ...
> default: ...
> }

> The compiler desugar this into two separate switches, where the first switch
> maps the input strings into a range of numbers [0..1], as shown below, which
> can then be used in a subsequent plain switch on ints. The generated code
> unconditionally calls `hashCode()`, again possibly throwing NPE.

> int index=-1;
> switch (s.hashCode()) {
> case 12345: if (!s.equals("Hello")) break; index = 1; break;
> case 6789: if (!s.equals("World")) break; index = 0; break;
> default: index = -1;
> }
> switch (index) {
> case 0: ...
> case 1: ...
> default: ...
> }

> If there are hash collisions between the strings, the first switch must try all
> possible matching strings.

> #### Switches on enums

> Switches on `enum` constants exploit the fact that enums have (usually dense)
> integral ordinal values. Unfortunately, because an ordinal value can change
> between compilation time and runtime, we cannot rely on this mapping directly,
> but instead need to do an extra layer of mapping. Given a switch like:

> switch(color) {
> case RED: ...
> case GREEN: ...
> }

> The compiler numbers the cases starting a 1 (as with string switch), and creates
> a synthetic class that maps the runtime values of the enum ordinals to the
> statically numbered cases:

> class Outer$0 {
> synthetic final int[] $EnumMap$Color = new int[Color.values().length];
> static {
> try { $EnumMap$Color[RED.ordinal()] = 1; } catch (NoSuchFieldError ex) {}
> try { $EnumMap$Color[GREEN.ordinal()] = 2; } catch (NoSuchFieldError ex) {}
> }
> }

> Then, the switch is translated as follows:

> switch(Outer$0.$EnumMap$Color[color.ordinal()]) {
> case 1: stmt1;
> case 2: stmt2
> }

> In other words, we construct an array whose size is the cardinality of the enum,
> and then the element at position * i * of such array will contain the case
> index corresponding to the enum constant with whose ordinal is * i * .

> ## A more general scheme

> The handling of strings and enums give us a hint of how to create a more regular
> scheme; for `switch` targets more complex than `int`, we lower the `switch` to
> an `int` switch with consecutive `case` labels, and use a separate process to
> map the target into the range of synthetic case labels.

> Now that we have `invokedynamic` in our toolbox, we can reduce all of the
> non-`int` cases to a single form, where we number the cases with consecutive
> integers, and perform case selection via an `invokedynamic`-based classifier
> function, whose static argument list receives a description of the actual
> targets, and which returns an `int` identifying what `case` to select.

> This approach has several advantages:
> - Reduced compiler complexity -- all switches follow a common pattern;
> - Reduced static code size;
> - The classification function can select from a wide range of strategies (linear
> search, binary search, building a `HashMap`, constructing a perfect hash
> function, etc), which can vary over time or from situation to situation;
> - We are free to improve the strategy or select an alternate strategy (say, to
> optimize for startup time) without having to recompile the code;
> - Hopefully at least, if not more, JIT-friendly than the existing translation.

> We can also use this approach in preference to `lookupswitch` for non-dense
> `int` switches, as well as use it to extend `switch` to handle `long`, `float`,
> and `double` targets (which were surely excluded in part because the JVM didn't
> provide a convenient translation target for these types.)

It seems to be a good general approach but it has several drawbacks: 
- do not work well with the type switch because the instanceof part (at least the part that recognizes the type) will be inside invokedynamic while the cast part will be in the tableswitch, 
so there is little chance that the VM can optimize such construction to avoid to do the instanceof/checkcast twice. 
- is not optimal in term of bytecode size with an expression switch that doesn't do any side effect on the local variable because there is a better representation where each case is desugared as a static method like for a lambda. In that case, you do not need a tableswitch, an invokedynamic is enough. In term of performance, because the VM used to did not gather profile when executing tableswitch/lookupswitch, performance were not good compared to only use an invokedynamic but JDK-8200303 may change things. 

So trying to detect if an invokedynamic alone is not enough can be interesting. In term of bootstrap method, most of the code can be shared apart returning an int or calling a static method on the leaf. 

> #### Bootstrap design

> When designing the `invokedynamic` bootstraps to support this translation, we
> face the classic lumping-vs-splitting decision. For now, we'll bias towards
> splitting. In the following example, `BOOTSTRAP_PREAMBLE` indicates the usual
> leading arguments for an indy bootstrap. We assume the compiler has numbered
> the case values densely from 0..N, and the bootstrap will return [0,n) for
> success, or N for "no match".

> A strawman design might be:

> // Numeric switches for P, accepts invocation as P -> I or Box(P) -> I
> CallSite intSwitch(BOOTSTRAP_PREAMBLE, int... caseValues)

> // Switch for String, invocation descriptor is String -> I
> CallSite stringSwitch(BOOTSTRAP_PREAMBLE, String... caseValues)

> // Switch for Enum, invocation descriptor is E -> I
> CallSite enumSwitch(BOOTSTRAP_PREAMBLE, Class<Enum<E extends Enum<E>>> clazz,
> String... caseNames)

> It might be possible to encode all of these into a single bootstrap, but given
> that the compiler already treats each type slightly differently, it seems there
> is little value in this sort of lumping for non-pattern switches.

> The `enumSwitch` bootstrap as proposed uses `String` values to describe the enum
> constants, rather than encoding the enum constants directly via condy. This
> allows us to be more robust to enums disappearing after compilation.

> This strategy is also dependent on having broken the limitation on 253 bootstrap
> arguments in indy/condy.

> #### Extending to other primitive types

> This approach extends naturally to other primitive types (long, double, float),
> by the addition of some more bootstraps (which need to deal with the additional
> complexities of infinity, NaN, etc):

> CallSite longSwitch(BOOTSTRAP_PREAMBLE, long... caseValues)
> CallSite floatSwitch(BOOTSTRAP_PREAMBLE, float... caseValues)
> CallSite doubleSwitch(BOOTSTRAP_PREAMBLE, double... caseValues)

> #### Extending to null

> The scheme as proposed above does not explicitly handle nulls, which is a
> feature we'd like to have in `switch`. There are a few ways we could add null
> handling into the API:

> - Split entry points into null-friendly or null-hostile switches;
> - Find a way to encode nulls in the array of case values (which can be done with
> condy);
> - Always treat null as a possible input and a distinguished output, and have the
> compiler ensure the switch can handle this distinguished output.

> The last strategy is appealing and straightforward; assign a sentinel value (-1)
> to `null`, and always return this sentinel when the input is null. The compiler
> ensures that some case handles `null`, and if no case handles `null` then it
> inserts an implicit

> case -1: throw new NullPointerException();

> into the generated code.

or 
- use a boolean as first bootstrap constant arguments to indicate if you want null to be -1 or a NPE. It will make the generated bytecode smaller and be sure that most of the time if there is no case null, the handling of null can be done implicitly by the VM. 

> #### General example

> If we have a string switch:

> switch (x) {
> case "Foo": m(); break;
> case "Bar": n(); // fall through
> case "Baz": r(); break;
> default: p();
> }

> we translate into:

> int t = indy[bsm=stringSwitch["Foo", "Bar", "Baz"]](x)
> switch (t) {
> case -1: throw new NullPointerException(); // implicit null case
> case 0: m(); break;
> case 1: n(); // fall through
> case 2: r(); break;
> case 3: p(); // default case
> }

with my proposed bootstrap recipe (use a boolen to indicate a nullcheck is needed of not), 

int t = indy[bsm=stringSwitch[false, "Foo", "Bar", "Baz"]](x) 
switch (t) { 
case 0: m(); break; 
case 1: n(); // fall through 
case 2: r(); break; 
case 3: p(); // default case 
} 

> All switches, with the exception of `int` switches (and maybe not even non-dense
> `int` switches), follow this exact pattern. If the target type is not a
> reference type, the `null` case is not needed.

> This strategy is implemented in the `switch` branch of the amber repository; see
> `java.lang.runtime.SwitchBootstraps` in that branch for (rough!)
> implementations of the bootstraps.

> ## Patterns in narrow-target switches

> When we add patterns, we may encounter switches whose targets are tightly typed
> (e.g., `String` or `int`) but still use some patterns in their expression. For
> switches whose target type is a primitive, primitive box, `String`, or `enum`,
> we'd like to use the optimized translation strategy outlined here, but the
> following kinds of patterns might still show up in a switch on, say, `Integer`:

> case var x:
> case _:
> case Integer x:
> case Integer(var x):

> The first three can be translated away by the source compiler, as they are
> semantically equivalent to `default`. If any nontrivial patterns are present
> (including deconstruction patterns), we may need to translate as a pattern
> switch scheme -- see Part 2. (While the language may not distinguish between
> "legacy" and "pattern" switches -- in that all switches are pattern switches --
> we'd like to avoid giving up obvious optimizations if we can.)

> # Part 2 -- type test patterns and guards

> A key motivation for reexamining switch translation is the impending arrival of
> patterns in switch. We expect switch translation for the pattern case to follow
> a similar structure -- lower to an `int` switch and use an indy-based
> classifier to select an index. However, there are a few additional
> complexities. One is that pattern cases may have guards, which means we need to
> be able to re-enter the bootstrap with an indication to "continue matching from
> case N", in the event of a failed guard. (Even if the language doesn't support
> guards directly, the obvious implementation strategy for nested patterns is to
> desugar them into guards.)

> Translating pattern switches is more complicated because there are more options
> for how to divide the work between the statically generated code and the switch
> classifier, and different choices have different performance side-effects (are
> binding variables "boxed" into a tuple to be returned, or do they need to be
> redundantly calculated).

I'm still not sure that having guards make sense from the language perspective, i find a switch with guard to be less readable that a switch with an if (at least in Scala). 

> ## Type-test patterns

> Type-test patterns are notable because their applicability predicate is purely
> based on the type system, meaning that the compiler can directly reason about
> it both statically (using flow analysis, optimizing away dynamic type tests)
> and dynamically (with `instanceof`.) A switch involving type-tests:

> switch (x) {
> case String s: ...
> case Integer i: ...
> case Long l: ...
> }

> can (among other strategies) be translated into a chain of `if-else` using
> `instanceof` and casts:

> if (x instanceof String) { String s = (String) x; ... }
> else if (x instanceof Integer) { Integer i = (Integer) x; ... }
> else if (x instanceof Long) { Long l = (Long) x; ... }

> #### Guards

> The `if-else` desugaring can also naturally handle guards:

> switch (x) {
> case String s
> where (s.length() > 0): ...
> case Integer i
> where (i > 0): ...
> case Long l
> where (l > 0L): ...
> }

> can be translated to:

> if (x instanceof String
> && ((String) x).length() > 0) { String s = (String) x; ... }
> else if (x instanceof Integer
> && ((Integer) x) > 0) { Integer i = (Integer) x; ... }
> else if (x instanceof Long
> && ((Long) x) > 0L) { Long l = (Long) x; ... }

> #### Performance concerns

> The translation to `if-else` chains is simple (for switches without
> fallthrough), but is harder for the VM to optimize, because we've used a more
> general control flow mechanism. If the target is an empty `String`, which means
> we'd pass the first `instanceof` but fail the guard, class-hierarchy analysis
> could tell us that it can't possibly be an `Integer` or a `Long`, and so
> there's no need to perform those tests. But generating code that takes
> advantage of this information is more complex.

it's worst than that, it's not a if-else chain it's a if-instanceof-else chain, instanceof by itself is decomposed into several ifs, so when you have enough (the number depend on your CPU) if-instanceof-else because the assembly code if full of conditional branches, it will be really slow but branch predictor will be lost. 

> In the extreme case, where a switch consists entirely of type test patterns for
> final classes, this could be performed as an O(1) operation by hashing. And
> this is a common case involving switches over alternatives in a sum (sealed)
> type. (We shouldn't rely on finality at compile time, as this can change
> between compile and run time, but we should take advantage of this at run time
> if we can.)

Hashing is complex without VM support because you have to be able to update dynamically the cache and to not have strong pointers to the classes otherwise you wil not be able to unload the classes. 
So while the complexity is O(1) it may requires several loads making hashing only useful when there is quite a few cases. 

> Finally, the straightforward static translation may miss opportunities for
> optimization. For example:

> switch (x) {
> case Point p
> where p.x > 0 && p.y > 0: A
> case Point p
> where p.x > 0 && p.y == 0: B
> }

> Here, not only would we potentially test the target twice to see if it is a
> `Point`, but we then further extract the `x` component twice and perform the
> `p.x > 0` test twice.

> #### Optimization opportunities

> The compiler can eliminate some redundant calculations through straightforward
> techniques. The previous switch can be transformed to:

> switch (x) {
> case Point p:
> if (((Point) p).x > 0 && ((Point) p).y > 0) { A }
> else if (((Point) p).x > 0 && ((Point) p).y > 0) { B }

> to eliminate the redundant `instanceof` (and admits further CSE optimizations.)

> #### Clause reordering

> The above example was easy to transform because the two `case Point` clauses
> were adjacent. But what if they are not? In some cases, it is safe to reorder
> them. For types `T` and `U`, it is safe to reorder `case T` and `case U` if the
> two types have no intersection; that there can be no types that are subtypes of
> them both. This is true when `T` and `U` are classes and neither extends the
> other, or when one is a final class and the other is an interface that the
> class does not implement.

> The compiler could then reorder case clauses so that all the ones whose first
> test is `case Point` are adjacent, and then coalesce them all into a single arm
> of the `if-else` chain.

> A possible spoiler here is fallthrough; if case A falls into case B, then cases
> A and B have to be moved as a group. (This is another reason to consider
> limiting fallthrough.)

> A bigger possible spoiler here is separate compilation. If at compile time, we
> see that `T` and `U` are disjoint types, do we want to bake that assumption
> into the compilation, or do we have to re-check that assumption at runtime?

> #### Summary of if-else translation

> While the if-else translation at first looks pretty bad, we are able to extract
> a fair amount of redundancy through well-understood compiler transformations.
> If an N-way switch has only M distinct types in it, in most cases we can reduce
> the cost from _O(N)_ to _O(M)_. Sometimes _M == N_, so this doesn't help, but
> sometimes _ M << N _ (and sometimes `N` is small, in which case _O(N)_ is
> fine.)

> Reordering clauses involves some risk; specifically, that the class hierarchy
> will change between compile and run time. It seems eminently safe to reorder
> `String` and `Integer`, but more questionable to reorder an arbitrary class
> `Foo` with `Runnable`, even if `Foo` doesn't implement `Runnable` now, because
> it might easily be changed to do so later. Ideally we'd like to perform
> class-hierarchy optimizations using the runtime hierarchy, not the compile-time
> hierarchy.

> ## Type classifiers

> The technique outlined in _Part 1_, where we lower the complex switch to a dense
> `int` switch, and use an indy-based classifier to select an index, is
> applicable here as well. First let's consider a switch consisting only of
> unguarded type-test patterns, optionally with a default clause.

> We'll start with an `indy` bootstrap whose static argument are `Class` constants
> corresponding to each arm of the switch, whose dynamic argument is the switch
> target, and whose return value is a case number (or distinguished sentinels for
> "no match" and `null`.) We can easily implement such a bootstrap with a linear
> search, but can also do better; if some subset of the classes are `final`, we
> can choose between these more quickly (such as via binary search on
> `hashCode()`, hash function, or hash table), and we need perform only a single
> operation to test all of those at once. Dynamic techniques (such as a building
> a hash map of previously seen target types), which `indy` is well-suited to,
> can asymptotically approach _O(1)_ even when the classes involved are not
> final.

> So we can lower:

> switch (x) {
> case T t: A
> case U u: B
> case V v: C
> }

> to

> int y = indy[bootstrap=typeSwitch(T.class, U.class, V.class)](x)
> switch (y) {
> case 0: A
> case 1: B
> case 2: C
> }

> This has the advantages that the generated code is very similar to the source
> code, we can (in some cases) get _O(1)_ dispatch performance, and we can handle
> fallthrough with no additional complexity.

as i said above, you need to do the checkcast twice in that case. 

> #### Guards

> There are two approaches we could take to add support for guards into the
> process; we could try to teach the bootstrap about guards (and would have to
> pass locals that appear in guard expressions as additional arguments to the
> classifier), or we could leave guards to the generated bytecode. The latter
> seems far more attractive, but requires some tweaks to the bootstrap arguments
> and to the shape of the generated code.

> If the classifier says "you have matched case #3", but then we fail the guard
> for #3, we want to go back into the classifier and start again at #4.
> (Sometimes the classifier can also use this information ("start over at #4") to
> optimize away unnecessary tests.)

> We add a second argument (where to start) to the classifier invocation
> signature, and wrap the switch in a loop, lowering:

> switch (target) {
> case T t where (e1): A
> case T t where (e2): B
> case U u where (e3): C
> }

> into

> int index = -1; // start at the top
> while (true) {
> index = indy[...](target, index)
> switch (index) {
> case 0: if (!e1) continue; A
> case 1: if (!e2) continue; B
> case 2: if (!e3) continue; C
> default: break;
> }
> break;
> }

> For cases where the same type test is repeated in consecutive positions (at N
> and N+1), we can have the static compiler coalesce them as above, or we could
> have the bootstrap maintain a table so that if you re-enter the bootstrap where
> the previous answer was N, then it can immediately return N+1. Similarly, if N
> and N+1 are known to be mutually exclusive types (like `String` and `Integer`),
> on reentering the classifier with N, we can skip right to N+2 since if we
> matched `String`, we cannot match `Integer`. Lookup tables for such
> optimizations can be built at callsite linkage time.

> #### Mixing constants and type tests

> This approach also extends to tests that are a mix of constant patterns and
> type-test patterns, such as:

> switch (x) {
> case "Foo": ...
> case 0L: ...
> case Integer i:
> }

> We can extend the bootstrap protocol to accept constants as well as types, and
> it is a straightforward optimization to combine both type matching and constant
> matching in a single pass.

> ## Nested patterns

> Nested patterns are essentially guards; even if we don't expose guards in the
> language, we can desugar

> case Point(0, var x):

> into the equivalent of

> case Point(var a, var x) && a matches 0:

> using the same translation story as above -- use the classifier to select a
> candidate case arm based on the top-type of the pattern, and then do additional
> checks in the generated bytecode, and if the checks fail, continue and re-enter
> the classifier starting at the next case.

> #### Explicit continue

> An alternative to exposing guards is to expose an explicit `continue` statement
> in switch, which would have the effect of "keep matching at the next case."
> Then guards could be expressed imperatively as:

> case P:
> if (!guard)
> continue;
> ...
> break;
> case Q: ...

Rémi 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/amber-spec-experts/attachments/20180406/80793fa3/attachment-0001.html>