<html>
  <head>

    <meta http-equiv="content-type" content="text/html; charset=utf-8">
  </head>
  <body text="#000000" bgcolor="#FFFFFF">
    <div class="moz-text-flowed" style="font-family: -moz-fixed;
      font-size: 14px;" lang="x-unicode">This doc covers some groundwork
      on rationalizing existing translation of switch as we move towards
      pattern-enabled switches.  <br>
      <br>
      <br>
      # Switch Translation, Part 1
      <br>
      #### Maurizio Cimadamore and Brian Goetz
      <br>
      #### December 2017
      <br>
      <br>
      This document 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:
      <br>
      <br>
       - Unify the treatment of `switch` variants, simplifying the
      compiler implementation and reducing the static footprint of
      generated code;
      <br>
       - Move responsibility for target classification from compile time
      to run time, allowing us to more freely update the logic without
      updating the compiler;
      <br>
       - Lay the groundwork for patterns in `switch`.
      <br>
      <br>
      Part 2 of this document will focus on the challenges of
      translating pattern `switch`.
      <br>
      <br>
      ## Current translation
      <br>
      <br>
      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.
      <br>
      <br>
      #### Switches on boxes
      <br>
      <br>
      Switches on primitive boxes are currently implemented as if they
      were primitive switches, unconditionally unboxing the target
      before entry (possibly throwing NPE).
      <br>
      <br>
      #### Switches on strings
      <br>
      <br>
      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:
      <br>
      <br>
          switch (s) {
      <br>
              case "Hello": ...
      <br>
              case "World": ...
      <br>
              default: ...
      <br>
          }
      <br>
      <br>
      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.
      <br>
      <br>
          int index=-1;
      <br>
          switch (s.hashCode()) {
      <br>
              case 12345: if (!s.equals("Hello")) break; index = 1;
      break;
      <br>
              case 6789: if (!s.equals("World")) break; index = 0;
      break;
      <br>
              default: index = -1;
      <br>
          }
      <br>
          switch (index) {
      <br>
              case 0: ...
      <br>
              case 1: ...
      <br>
              default: ...
      <br>
          }
      <br>
      <br>
      If there are hash collisions between the strings, the first switch
      must try all possible matching strings.
      <br>
      <br>
      #### Switches on enums
      <br>
      <br>
      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:
      <br>
      <br>
          switch(color) {
      <br>
              case RED: ...
      <br>
              case GREEN: ...
      <br>
          }
      <br>
      <br>
      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:
      <br>
      <br>
          class Outer$0 {
      <br>
              synthetic final int[] $EnumMap$Color = new
      int[Color.values().length];
      <br>
              static {
      <br>
                  try { $EnumMap$Color[RED.ordinal()] = 1; } catch
      (NoSuchFieldError ex) {}
      <br>
                  try { $EnumMap$Color[GREEN.ordinal()] = 2; } catch
      (NoSuchFieldError ex) {}
      <br>
              }
      <br>
          }
      <br>
      <br>
      Then, the switch is translated as follows:
      <br>
      <br>
          switch(Outer$0.$EnumMap$Color[color.ordinal()]) {
      <br>
              case 1: stmt1;
      <br>
              case 2: stmt2
      <br>
          }
      <br>
      <br>
      In other words, we construct an array whose size is the
      cardinality of the enum, and then the element at position <b
        class="moz-txt-star"><span class="moz-txt-tag">*</span>i<span
          class="moz-txt-tag">*</span></b> of such array will contain
      the case index corresponding to the enum constant with whose
      ordinal is <b class="moz-txt-star"><span class="moz-txt-tag">*</span>i<span
          class="moz-txt-tag">*</span></b>.
      <br>
      <br>
      ## A more general scheme
      <br>
      <br>
      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.
      <br>
      <br>
      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.
      <br>
      <br>
      This approach has several advantages:
      <br>
       - Reduced compiler complexity -- all switches follow a common
      pattern;
      <br>
       - Reduced static code size;
      <br>
       - 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;
      <br>
       - We are free to improve the strategy or select an alternate
      strategy (say, to optimize for startup time) without having to
      recompile the code;
      <br>
       - Hopefully at least, if not more, JIT-friendly than the existing
      translation.
      <br>
      <br>
      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.)
      <br>
      <br>
      #### Bootstrap design
      <br>
      <br>
      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".
      <br>
      <br>
      A strawman design might be:
      <br>
      <br>
          // Numeric switches for P, accepts invocation as P -> I or
      Box(P) -> I
      <br>
          CallSite intSwitch(BOOTSTRAP_PREAMBLE, int... caseValues)
      <br>
      <br>
          // Switch for String, invocation descriptor is String -> I
      <br>
          CallSite stringSwitch(BOOTSTRAP_PREAMBLE, String...
      caseValues)
      <br>
      <br>
          // Switch for Enum, invocation descriptor is E -> I
      <br>
          CallSite enumSwitch(BOOTSTRAP_PREAMBLE, Class<Enum<E
      extends Enum<E>>> clazz,
      <br>
                              String... caseNames)
      <br>
      <br>
      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.
      <br>
      <br>
      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.
      <br>
      <br>
      This strategy is also dependent on having broken the limitation on
      253 bootstrap arguments in indy/condy.
      <br>
      <br>
      #### Extending to other primitive types
      <br>
      <br>
      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):
      <br>
      <br>
          CallSite longSwitch(BOOTSTRAP_PREAMBLE, long... caseValues)
      <br>
          CallSite floatSwitch(BOOTSTRAP_PREAMBLE, float... caseValues)
      <br>
          CallSite doubleSwitch(BOOTSTRAP_PREAMBLE, double...
      caseValues)
      <br>
      <br>
      #### Extending to null
      <br>
      <br>
      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:
      <br>
      <br>
       - Split entry points into null-friendly or null-hostile switches;
      <br>
       - Find a way to encode nulls in the array of case values (which
      can be done with condy);
      <br>
       - Always treat null as a possible input and a distinguished
      output, and have the compiler ensure the switch can handle this
      distinguished output.
      <br>
      <br>
      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
      <br>
      <br>
          case -1: throw new NullPointerException();
      <br>
      <br>
      into the generated code.
      <br>
      <br>
      #### General example
      <br>
      <br>
      If we have a string switch:
      <br>
      <br>
          switch (x) {
      <br>
              case "Foo": m(); break;
      <br>
              case "Bar": n(); // fall through
      <br>
              case "Baz": r(); break;
      <br>
              default: p();
      <br>
          }
      <br>
      <br>
      we translate into:
      <br>
      <br>
          int t = indy[bsm=stringSwitch["Foo", "Bar", "Baz"]](x)
      <br>
          switch (t) {
      <br>
              case -1: throw new NullPointerException();  // implicit
      null case
      <br>
              case 0: m(); break;
      <br>
              case 1: n(); // fall through
      <br>
              case 2: r(); break;
      <br>
              case 3: p();                                // default
      case
      <br>
          }
      <br>
      <br>
      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.
      <br>
      <br>
      ## Patterns in narrow-target switches
      <br>
      <br>
      When we add patterns to the language, 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`:
      <br>
      <br>
          case var x:
      <br>
          case _:
      <br>
          case Integer x:
      <br>
          case Integer(var x):
      <br>
      <br>
      The first three (if supported at all) 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 will need to translate as a pattern
      switch scheme -- details coming in 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.)
      <br>
      <br>
      ## Looking ahead -- patterns
      <br>
      <br>
      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.
      <br>
      <br>
      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).  These will be explored in Part 2.
      <br>
      <br>
      <br>
      <br>
      <br>
      <br>
      <br>
    </div>
  </body>
</html>