This is the 26th day of my participation in Gwen Challenge

This article is part 13 of jakewharton’s series on D8 and R8.

  • R8 Optimization: Enum Switch Maps
  • Originally written by jakewharton
  • Translator: Antway

In the previous article about enumerating ordinals, we learned that R8 optimizes switch expressions. In that article, the bytecode for the switch on the enumeration was omitted because there was actually more optimization to be done.

Let’s start with a simple enumeration and switch its contents between two separate source files (this is important later).

enum Greeting {
  FORMAL, INFORMAL
}
Copy the code
class Main {
  static String greetingType(Greeting greeting) {
    switch (greeting) {
      case FORMAL: return "formal";
      case INFORMAL: return "informal";
      default: throw newAssertionError(); }}public static void main(String... args) { System.out.println(greetingType(Greeting.INFORMAL)); }}Copy the code

If we compile and run these files, the output is as expected.

$ javac Greeting.java Main.java
$ java -cp . Main
informal
Copy the code

In the previous article, reordering the greeting constant interrupts the output of Main when the switch expression bytecode shows a call to ordinal().

 enum Greeting {
-  FORMAL, INFORMAL
+  INFORMAL, FORMAL
 }
Copy the code

After changing the constant order, we can only recompile greeting. Java, but the application still generates the correct output.

$ javac Greeting.java
$ java -cp . Main
informal
Copy the code

So if bytecode depends only on the value of ordinal(), this code will generate Formal.

1. Into The Bytecode

To better understand, let’s look at the bytecode of the greetingType method.

$ javap -c Main.class
class Main {
  static java.lang.String greetingType(Greeting);
    Code:
       0: getstatic     #2      // Field Main$1.$SwitchMap$Greeting:[I
       3: aload_0
       4: invokevirtual #3      // Method Greeting.ordinal:()I
       7: iaload
       8: lookupswitch  {
                     1: 36
                     2: 39
               default: 42
          }
      36: ldc           #4      // String formal
      38: areturn
      39: ldc           #5      // String informal
      41: areturn
      42: new           #6      // class java/lang/AssertionError
      45: dup
      46: invokespecial #7      // Method java/lang/AssertionError."<init>":()V
      49: athrow
}
Copy the code

Let’s break down the bytecode. The first bytecode of this method has a lot of information to unpack:

0: getstatic     #2      // Field Main$1.$SwitchMap$Greeting:[I
Copy the code

This line of bytecode says: Look for a static field called $SwitchMap$Greeting of type int[] in class Main$1. But we didn’t define this field in the class, so it must have been generated by JavAC.

The next two bytecodes call the ordinal() method in the method argument.

3: aload_0
4: invokevirtual #3      // Method Greeting.ordinal:()I`java
Copy the code

Java bytecode is stack-based, so both the int[] value of getstatic and the int value of ordinal() remain on the stack. (If you don’t know how stack-based machines work, you can see below.) The next instruction uses int[] and int as its operands.

7: iaload
Copy the code

The iaload directive looks for the value at the index returned by ordinal() in int[]. The rest of the bytecode of the method is a Normal Switch statement that takes the values from the array as input.

2. Switch Maps

Obviously, the $SwitchMap$Greeting array is a mechanism that allows our code to continue working even though the Ordinal Numbers change their values. So how does it work?

When compiled, each case statement of the switch has a subscript position, and the default branch defaults to 0.

switch (greeting) {
  case FORMAL: ...   // <-- index 1
  case INFORMAL: ... // <-- index 2
  default:...// <-- index 0
}
Copy the code

The $SwitchMap$Greeting array is populated at run time in the static initializer of Main$1. First create the empty int[] and assign it to the $SwitchMap$Greeting field.

0: invokestatic  #1      // Method Greeting.values:()[LGreeting;
3: arraylength
4: newarray      int
6: putstatic     #2      // Field $SwitchMap$Greeting:[I
Copy the code

The length of this array is the same as the number of constants (which may not match the number of case blocks). This is important because the ordinal is used as the index of this array.

The next bytecode instruction is to prepare the constants in the SWtiCH statement.

 9: getstatic     #2      // Field $SwitchMap$Greeting:[I
12: getstatic     #3      // Field Greeting.FORMAL:LGreeting;
15: invokevirtual #4      // Method Greeting.ordinal:()I
18: iconst_1
19: iastore
Copy the code

The FORMAL number of the first case is used as an offset in an array that stores the corresponding switch index value 1. The same is true for informal ordinals and the value 2. The int[] effectively creates a mapping from an ordinal to a fixed set of integer values that may change, but does not.

By using this mapping,switchStatements can remain stable even if we rearrange themGreetingThe constants.

3. The optimization

The switch-map indirection created by JavAC is useful when enumerations can be recompiled separately from the caller. Android applications are packaged as a unit, so indirection is just a waste of binary size and runtime overhead.

Running the example class above through D8 shows that indirection is maintained.

$ java -jar $R8_HOME/build/libs/d8.jar \
      --lib $ANDROID_HOME/platforms/android-29/android.jar \
      --release \
      --output . \
      *.class

$ $ANDROID_HOME/build-tools/29.02./dexdump -d classes.dex ⋮ [00040c] main.greetingtype :(LGreeting;) Ljava/lang/String;0000: sget-object v0, LMain$1; .$SwitchMap$Greeting:[I0002: invoke-virtual {v1}, LGreeting; .ordinal:()I0005: move-result v1
0006: aget v1, v0, v1
0008: packed-switch v1, 00000024
Copy the code

However, R8 performs overall program analysis and optimization. It does not need to preserve this indirection because enumerations cannot be independent of the switch.

[00040c] Main.greetingType:(LGreeting;) Ljava/lang/String; -0000: sget-object v0, LMain$1; .$SwitchMap$Greeting:[I0000: invoke-virtual {v1}, LGreeting; .ordinal:()I0003: move-result v1
-0006: aget v1, v0, v1
 0004: packed-switch v1, 00000024
Copy the code

The switch branch will be rewritten, explaining that the input now directly uses zero-based Ordinal Numbers instead of the one-based values in the switch mapping. Since Main$1 and its array are no longer referenced, it is eliminated just like normal dead code.

Only by removing this indirection can you optimize from the enumeration ordinal(), thus eliminating the switch. Otherwise, the ordinal value flows into int[] as an index, which is generally unsafe.

4. Kotlin

Enumerations used in Kotlin generate similar indirection for the same reason.

val Greeting.type get() = when (this) {
  Greeting.FORMAL -> "formal"
  Greeting.INFORMAL -> "informal"
}
Copy the code

When compiled, Java bytecode shows a similar mechanism, but with a different name.

$ javap -c MainKt
public final class MainKt {
  public static final java.lang.String getType(Greeting);
    Code:
      0: aload_0
      1: getstatic     #21     // Field MainKt$WhenMappings.$EnumSwitchMapping$0:[I
      4: swap
      5: invokevirtual #27     // Method Greeting.ordinal:()I
      8: iaload
      9: tableswitch   {
                    1: 36
                    2: 41
              default: 46
         }
     ⋮
Copy the code

The resulting class suffix is $WhenMappings, not int[] named $EnumSwitchMapping$0.

R8 does not initially detect Kotlin mappings because the names are slightly different. Version 1.6 of R8 (included in AGP 3.6) will detect and eliminate them correctly.

Switch map mapping elimination is a nice win for binary size and runtime performance. More importantly, by removing the indirection between the switch and its branch logic, other optimizations (such as converting calls to ordinal() to constants) can eliminate the branch.

More R8 optimization posts coming soon. Stay tuned!