Implement equals and hashCode on CfFrame

This is needed for the cf type analysis to determine if the state for a given program point has changed (meaning that its successors would need to be reprocessed by the fixpoint analysis).

Change-Id: I0af40d93baa414214d9e2fbac7f43123797e112d
diff --git a/src/main/java/com/android/tools/r8/cf/CfCodePrinter.java b/src/main/java/com/android/tools/r8/cf/CfCodePrinter.java
index 2f90085..f1cad28 100644
--- a/src/main/java/com/android/tools/r8/cf/CfCodePrinter.java
+++ b/src/main/java/com/android/tools/r8/cf/CfCodePrinter.java
@@ -197,9 +197,8 @@
     return type("ImmutableList", ImmutableList.of("com", "google", "common", "collect"));
   }
 
-  private String int2ReferenceAVLTreeMapType() {
-    return type(
-        "Int2ReferenceAVLTreeMap", ImmutableList.of("it", "unimi", "dsi", "fastutil", "ints"));
+  private String int2ObjectAVLTreeMapType() {
+    return type("Int2ObjectAVLTreeMap", ImmutableList.of("it", "unimi", "dsi", "fastutil", "ints"));
   }
 
   private String frameTypeType() {
@@ -244,6 +243,10 @@
     return r8Type(name, ImmutableList.of("cf", "code"));
   }
 
+  private String cfFrameType() {
+    return cfType("CfFrame");
+  }
+
   private String labelName(CfLabel label) {
     return "label" + labelToIndex.getInt(label);
   }
@@ -488,23 +491,40 @@
 
   @Override
   public void print(CfFrame frame) {
-    String keys = join(",", frame.getLocals().keySet());
-    String values = join(",", frame.getLocals().values(), this::frameTypeType);
-    String stack = join(",", frame.getStack(), this::frameTypeType);
-    printNewInstruction(
-        "CfFrame",
-        "new "
-            + int2ReferenceAVLTreeMapType()
-            + "<>("
-            + "new int[] {"
-            + keys
-            + "},"
-            + "new "
-            + frameTypeType()
-            + "[] { "
-            + values
-            + " })",
-        "new " + arrayDequeType() + "<>(" + arraysType() + ".asList(" + stack + "))");
+    if (frame.getLocals().isEmpty()) {
+      if (frame.getStack().isEmpty()) {
+        printNewInstruction(cfFrameType());
+      } else {
+        printNewInstruction(cfFrameType(), getCfFrameStack(frame));
+      }
+    } else {
+      if (frame.getStack().isEmpty()) {
+        printNewInstruction(cfFrameType(), getCfFrameLocals(frame));
+      } else {
+        printNewInstruction(cfFrameType(), getCfFrameLocals(frame), getCfFrameStack(frame));
+      }
+    }
+  }
+
+  private String getCfFrameLocals(CfFrame frame) {
+    String localsKeys = join(",", frame.getLocals().keySet());
+    String localsElements = join(",", frame.getLocals().values(), this::frameTypeType);
+    return "new "
+        + int2ObjectAVLTreeMapType()
+        + "<>("
+        + "new int[] {"
+        + localsKeys
+        + "},"
+        + "new "
+        + frameTypeType()
+        + "[] { "
+        + localsElements
+        + " })";
+  }
+
+  private String getCfFrameStack(CfFrame frame) {
+    String stackElements = join(",", frame.getStack(), this::frameTypeType);
+    return "new " + arrayDequeType() + "<>(" + arraysType() + ".asList(" + stackElements + "))";
   }
 
   private String frameTypeType(FrameType frameType) {
diff --git a/src/main/java/com/android/tools/r8/cf/CfPrinter.java b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
index d0a3c23..6d0c2d1 100644
--- a/src/main/java/com/android/tools/r8/cf/CfPrinter.java
+++ b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
@@ -76,7 +76,6 @@
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.utils.DescriptorUtils;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
 import it.unimi.dsi.fastutil.ints.IntList;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
@@ -434,13 +433,14 @@
   public void print(CfFrame frame) {
     indent();
     builder.append("; frame: [");
-    {
-      String separator = "";
-      for (Entry<FrameType> entry : frame.getLocals().int2ReferenceEntrySet()) {
-        builder.append(separator).append(entry.getIntKey()).append(':');
-        print(entry.getValue());
-        separator = ", ";
-      }
+    if (!frame.getLocals().isEmpty()) {
+      int firstLocalIndex = frame.getLocals().firstIntKey();
+      frame.forEachLocal(
+          (localIndex, frameType) -> {
+            String separator = localIndex == firstLocalIndex ? "" : ", ";
+            builder.append(separator).append(localIndex).append(':');
+            print(frameType);
+          });
     }
     builder.append("] [");
     {
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfFrame.java b/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
index bb74537..8df3eb6 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
@@ -28,17 +28,25 @@
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.optimize.interfaces.analysis.CfFrameState;
+import com.android.tools.r8.utils.IntObjConsumer;
+import com.android.tools.r8.utils.collections.ImmutableDeque;
 import com.android.tools.r8.utils.structural.CompareToVisitor;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
+import com.google.common.collect.Iterables;
+import it.unimi.dsi.fastutil.ints.Int2ObjectAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMaps;
 import java.util.ArrayDeque;
 import java.util.Deque;
 import java.util.Objects;
-import java.util.SortedMap;
+import java.util.function.Consumer;
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Opcodes;
 
-public class CfFrame extends CfInstruction {
+public class CfFrame extends CfInstruction implements Cloneable {
+
+  public static final Int2ObjectSortedMap<FrameType> EMPTY_LOCALS = Int2ObjectSortedMaps.emptyMap();
+  public static final Deque<FrameType> EMPTY_STACK = ImmutableDeque.of();
 
   public abstract static class FrameType {
 
@@ -51,7 +59,7 @@
     }
 
     public static FrameType uninitializedThis() {
-      return new UninitializedThis();
+      return UninitializedThis.SINGLETON;
     }
 
     public static FrameType top() {
@@ -145,6 +153,12 @@
 
     private FrameType() {}
 
+    @Override
+    public abstract boolean equals(Object obj);
+
+    @Override
+    public abstract int hashCode();
+
     public static FrameType fromMemberType(MemberType memberType, DexItemFactory factory) {
       switch (memberType) {
         case OBJECT:
@@ -177,6 +191,19 @@
     }
   }
 
+  private abstract static class SingletonFrameType extends FrameType {
+
+    @Override
+    public final boolean equals(Object obj) {
+      return this == obj;
+    }
+
+    @Override
+    public final int hashCode() {
+      return System.identityHashCode(this);
+    }
+  }
+
   @Override
   public boolean isFrame() {
     return true;
@@ -210,6 +237,23 @@
     }
 
     @Override
+    public boolean equals(Object obj) {
+      if (this == obj) {
+        return true;
+      }
+      if (obj == null || getClass() != obj.getClass()) {
+        return false;
+      }
+      InitializedType initializedType = (InitializedType) obj;
+      return type == initializedType.type;
+    }
+
+    @Override
+    public int hashCode() {
+      return type.hashCode();
+    }
+
+    @Override
     public String toString() {
       return "Initialized(" + type.toString() + ")";
     }
@@ -263,10 +307,12 @@
     }
   }
 
-  private static class Top extends FrameType {
+  private static class Top extends SingletonFrameType {
 
     private static final Top SINGLETON = new Top();
 
+    private Top() {}
+
     @Override
     public String toString() {
       return "top";
@@ -284,6 +330,7 @@
   }
 
   private static class UninitializedNew extends FrameType {
+
     private final CfLabel label;
     private final DexType type;
 
@@ -293,6 +340,23 @@
     }
 
     @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      UninitializedNew uninitializedNew = (UninitializedNew) o;
+      return label == uninitializedNew.label && type == uninitializedNew.type;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(label, type);
+    }
+
+    @Override
     public String toString() {
       return "uninitialized new";
     }
@@ -333,7 +397,9 @@
     }
   }
 
-  private static class UninitializedThis extends FrameType {
+  private static class UninitializedThis extends SingletonFrameType {
+
+    private static final UninitializedThis SINGLETON = new UninitializedThis();
 
     private UninitializedThis() {}
 
@@ -368,10 +434,12 @@
     }
   }
 
-  private static class OneWord extends FrameType {
+  private static class OneWord extends SingletonFrameType {
 
     private static final OneWord SINGLETON = new OneWord();
 
+    private OneWord() {}
+
     @Override
     Object getTypeOpcode(GraphLens graphLens, NamingLens namingLens) {
       throw new Unreachable("Should only be used for verification");
@@ -388,10 +456,12 @@
     }
   }
 
-  private static class TwoWord extends FrameType {
+  private static class TwoWord extends SingletonFrameType {
 
     private static final TwoWord SINGLETON = new TwoWord();
 
+    private TwoWord() {}
+
     @Override
     Object getTypeOpcode(GraphLens graphLens, NamingLens namingLens) {
       throw new Unreachable("Should only be used for verification");
@@ -413,27 +483,63 @@
     }
   }
 
-  private final Int2ReferenceSortedMap<FrameType> locals;
+  private final Int2ObjectSortedMap<FrameType> locals;
   private final Deque<FrameType> stack;
 
-  public CfFrame(Int2ReferenceSortedMap<FrameType> locals, Deque<FrameType> stack) {
+  // Constructor used by CfCodePrinter.
+  public CfFrame() {
+    this(EMPTY_LOCALS, EMPTY_STACK);
+  }
+
+  // Constructor used by CfCodePrinter.
+  public CfFrame(Int2ObjectAVLTreeMap<FrameType> locals) {
+    this((Int2ObjectSortedMap<FrameType>) locals, EMPTY_STACK);
+    assert !locals.isEmpty() || locals == EMPTY_LOCALS : "Should use EMPTY_LOCALS instead";
+  }
+
+  // Constructor used by CfCodePrinter.
+  public CfFrame(Deque<FrameType> stack) {
+    this(EMPTY_LOCALS, stack);
+    assert !stack.isEmpty() || stack == EMPTY_STACK : "Should use EMPTY_STACK instead";
+  }
+
+  // Constructor used by CfCodePrinter.
+  public CfFrame(Int2ObjectAVLTreeMap<FrameType> locals, Deque<FrameType> stack) {
+    this((Int2ObjectSortedMap<FrameType>) locals, stack);
+    assert !locals.isEmpty() || locals == EMPTY_LOCALS : "Should use EMPTY_LOCALS instead";
+    assert !stack.isEmpty() || stack == EMPTY_STACK : "Should use EMPTY_STACK instead";
+  }
+
+  // Internal constructor that does not require locals to be of the type Int2ObjectAVLTreeMap.
+  private CfFrame(Int2ObjectSortedMap<FrameType> locals, Deque<FrameType> stack) {
     assert locals.values().stream().allMatch(Objects::nonNull);
     assert stack.stream().allMatch(Objects::nonNull);
     this.locals = locals;
     this.stack = stack;
   }
 
-  // This is used from tests. As fastutils are repackaged and minified the method above is
-  // not available from tests which use fastutils in their original namespace.
-  public CfFrame(SortedMap<Integer, FrameType> locals, Deque<FrameType> stack) {
-    this(
-        locals instanceof Int2ReferenceAVLTreeMap
-            ? (Int2ReferenceAVLTreeMap<FrameType>) locals
-            : new Int2ReferenceAVLTreeMap<>(locals),
-        stack);
+  public static Builder builder() {
+    return new Builder();
   }
 
-  public Int2ReferenceSortedMap<FrameType> getLocals() {
+  @Override
+  public CfFrame clone() {
+    return new CfFrame(locals, stack);
+  }
+
+  public CfFrame mutableCopy() {
+    return new CfFrame(
+        (Int2ObjectSortedMap<FrameType>) new Int2ObjectAVLTreeMap<>(locals),
+        new ArrayDeque<>(stack));
+  }
+
+  public void forEachLocal(IntObjConsumer<FrameType> consumer) {
+    for (Int2ObjectMap.Entry<FrameType> entry : locals.int2ObjectEntrySet()) {
+      consumer.accept(entry.getIntKey(), entry.getValue());
+    }
+  }
+
+  public Int2ObjectSortedMap<FrameType> getLocals() {
     return locals;
   }
 
@@ -442,6 +548,28 @@
   }
 
   @Override
+  public boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (obj == null || getClass() != obj.getClass()) {
+      return false;
+    }
+    CfFrame frame = (CfFrame) obj;
+    return locals.equals(frame.locals) && Iterables.elementsEqual(stack, frame.stack);
+  }
+
+  @Override
+  public int hashCode() {
+    // Generates a hash that is identical to Objects.hash(locals, stack[0], ..., stack[n]).
+    int result = 31 + locals.hashCode();
+    for (FrameType frameType : stack) {
+      result = 31 * result + frameType.hashCode();
+    }
+    return result;
+  }
+
+  @Override
   public void write(
       AppView<?> appView,
       ProgramMethod context,
@@ -573,15 +701,15 @@
       throw CfCodeStackMapValidatingException.error(
           "Cannot instantiate already instantiated type " + uninitializedType);
     }
-    Int2ReferenceSortedMap<FrameType> newLocals = new Int2ReferenceAVLTreeMap<>();
-    for (int var : locals.keySet()) {
-      newLocals.put(var, getInitializedFrameType(uninitializedType, locals.get(var), initType));
-    }
-    Deque<FrameType> newStack = new ArrayDeque<>();
+    CfFrame.Builder builder = CfFrame.builder().allocateStack(stack.size());
+    forEachLocal(
+        (localIndex, frameType) ->
+            builder.store(
+                localIndex, getInitializedFrameType(uninitializedType, frameType, initType)));
     for (FrameType frameType : stack) {
-      newStack.addLast(getInitializedFrameType(uninitializedType, frameType, initType));
+      builder.push(getInitializedFrameType(uninitializedType, frameType, initType));
     }
-    return new CfFrame(newLocals, newStack);
+    return builder.build();
   }
 
   public static FrameType getInitializedFrameType(
@@ -623,14 +751,69 @@
     if (!mapped) {
       return this;
     }
-    Int2ReferenceSortedMap<FrameType> newLocals = new Int2ReferenceAVLTreeMap<>();
-    for (int var : locals.keySet()) {
-      newLocals.put(var, locals.get(var).map(func));
+    Builder builder = builder();
+    for (Int2ObjectMap.Entry<FrameType> entry : locals.int2ObjectEntrySet()) {
+      builder.store(entry.getIntKey(), entry.getValue().map(func));
     }
-    Deque<FrameType> newStack = new ArrayDeque<>();
     for (FrameType frameType : stack) {
-      newStack.addLast(frameType.map(func));
+      builder.push(frameType.map(func));
     }
-    return new CfFrame(newLocals, newStack);
+    return builder.build();
+  }
+
+  public static class Builder {
+
+    private Int2ObjectSortedMap<FrameType> locals = EMPTY_LOCALS;
+    private Deque<FrameType> stack = EMPTY_STACK;
+
+    private boolean seenStore = false;
+
+    public Builder allocateStack(int size) {
+      assert stack == EMPTY_STACK;
+      if (size > 0) {
+        stack = new ArrayDeque<>(size);
+      }
+      return this;
+    }
+
+    public Builder appendLocal(FrameType frameType) {
+      // Mixing appendLocal() and store() is somewhat error prone. Catch it if we ever do it.
+      assert !seenStore;
+      int localIndex = locals.size();
+      return internalStore(localIndex, frameType);
+    }
+
+    public Builder apply(Consumer<Builder> consumer) {
+      consumer.accept(this);
+      return this;
+    }
+
+    public Builder push(FrameType frameType) {
+      if (stack == EMPTY_STACK) {
+        stack = new ArrayDeque<>();
+      }
+      stack.addLast(frameType);
+      return this;
+    }
+
+    public Builder store(int localIndex, FrameType frameType) {
+      seenStore = true;
+      return internalStore(localIndex, frameType);
+    }
+
+    private Builder internalStore(int localIndex, FrameType frameType) {
+      if (locals == EMPTY_LOCALS) {
+        locals = new Int2ObjectAVLTreeMap<>();
+      }
+      locals.put(localIndex, frameType);
+      if (frameType.isWide()) {
+        locals.put(localIndex + 1, frameType);
+      }
+      return this;
+    }
+
+    public CfFrame build() {
+      return new CfFrame(locals, stack);
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfFrameVerificationHelper.java b/src/main/java/com/android/tools/r8/cf/code/CfFrameVerificationHelper.java
index aad0ba6..234c3a0 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfFrameVerificationHelper.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfFrameVerificationHelper.java
@@ -13,10 +13,8 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.utils.MapUtils;
 import com.android.tools.r8.utils.collections.ImmutableDeque;
-import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
 import com.google.common.collect.Sets;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMap;
 import java.util.ArrayDeque;
 import java.util.Arrays;
 import java.util.Deque;
@@ -28,9 +26,7 @@
 
 public class CfFrameVerificationHelper {
 
-  private static final CfFrame NO_FRAME =
-      new CfFrame(
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder().build(), ImmutableDeque.of());
+  private static final CfFrame NO_FRAME = new CfFrame();
 
   private final AppView<?> appView;
   private final DexItemFactory factory;
@@ -216,9 +212,7 @@
 
   private void setFrame(CfFrame frame) {
     assert frame != NO_FRAME;
-    currentFrame =
-        new CfFrame(
-            new Int2ReferenceAVLTreeMap<>(frame.getLocals()), new ArrayDeque<>(frame.getStack()));
+    currentFrame = frame.mutableCopy();
   }
 
   public void checkExceptionEdges() {
@@ -248,7 +242,7 @@
     checkFrame(destinationFrame.getLocals(), destinationFrame.getStack());
   }
 
-  public void checkFrame(Int2ReferenceSortedMap<FrameType> locals, Deque<FrameType> stack) {
+  public void checkFrame(Int2ObjectSortedMap<FrameType> locals, Deque<FrameType> stack) {
     checkIsAssignable(currentFrame.getLocals(), currentFrame.getStack(), locals, stack);
   }
 
@@ -295,17 +289,16 @@
 
   // Based on https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1.4.
   private void checkIsAssignable(
-      Int2ReferenceSortedMap<FrameType> sourceLocals,
+      Int2ObjectSortedMap<FrameType> sourceLocals,
       Deque<FrameType> sourceStack,
-      Int2ReferenceSortedMap<FrameType> destLocals,
+      Int2ObjectSortedMap<FrameType> destLocals,
       Deque<FrameType> destStack) {
     checkLocalsIsAssignable(sourceLocals, destLocals);
     checkStackIsAssignable(sourceStack, destStack);
   }
 
   private void checkLocalsIsAssignable(
-      Int2ReferenceSortedMap<FrameType> sourceLocals,
-      Int2ReferenceSortedMap<FrameType> destLocals) {
+      Int2ObjectSortedMap<FrameType> sourceLocals, Int2ObjectSortedMap<FrameType> destLocals) {
     // TODO(b/229826687): The tail of locals could have top(s) at destination but still be valid.
     int localsLastKey = sourceLocals.isEmpty() ? -1 : sourceLocals.lastIntKey();
     int otherLocalsLastKey = destLocals.isEmpty() ? -1 : destLocals.lastIntKey();
diff --git a/src/main/java/com/android/tools/r8/graph/CfCode.java b/src/main/java/com/android/tools/r8/graph/CfCode.java
index 8797a80..51c9868 100644
--- a/src/main/java/com/android/tools/r8/graph/CfCode.java
+++ b/src/main/java/com/android/tools/r8/graph/CfCode.java
@@ -49,11 +49,8 @@
 import com.android.tools.r8.utils.structural.StructuralMapping;
 import com.google.common.base.Strings;
 import it.unimi.dsi.fastutil.ints.Int2IntArrayMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.BitSet;
 import java.util.Collections;
@@ -971,13 +968,8 @@
       builder.checkFrameAndSet(stateMap.get(null));
     } else if (shouldComputeInitialFrame()) {
       builder.checkFrameAndSet(
-          new CfFrame(
-              computeInitialLocals(
-                  appView,
-                  previousMethodSignature,
-                  previousMethodSignatureIsInstance,
-                  protoChanges),
-              new ArrayDeque<>()));
+          computeInitialFrame(
+              appView, previousMethodSignature, previousMethodSignatureIsInstance, protoChanges));
     }
     for (int i = 0; i < instructions.size(); i++) {
       CfInstruction instruction = instructions.get(i);
@@ -1040,17 +1032,15 @@
     return true;
   }
 
-  private Int2ReferenceSortedMap<FrameType> computeInitialLocals(
+  private CfFrame computeInitialFrame(
       AppView<?> appView,
       DexMethod method,
       boolean isInstance,
       RewrittenPrototypeDescription prototypeChanges) {
     DexItemFactory dexItemFactory = appView.dexItemFactory();
-    Int2ReferenceSortedMap<FrameType> initialLocals = new Int2ReferenceAVLTreeMap<>();
-    int index = 0;
+    CfFrame.Builder builder = CfFrame.builder();
     if (isInstance) {
-      initialLocals.put(
-          index++,
+      builder.appendLocal(
           method.isInstanceInitializer(dexItemFactory)
                   || method.mustBeInlinedIntoInstanceInitializer(appView)
                   || method.isHorizontallyMergedInstanceInitializer(dexItemFactory)
@@ -1058,19 +1048,11 @@
               : FrameType.initialized(method.getHolderType()));
     }
     for (DexType parameter : method.getParameters()) {
-      FrameType frameType = FrameType.initialized(parameter);
-      initialLocals.put(index++, frameType);
-      if (frameType.isWide()) {
-        initialLocals.put(index++, frameType);
-      }
+      builder.appendLocal(FrameType.initialized(parameter));
     }
     for (ExtraParameter extraParameter : prototypeChanges.getExtraParameters()) {
-      FrameType frameType = FrameType.initialized(extraParameter.getType(dexItemFactory));
-      initialLocals.put(index++, frameType);
-      if (frameType.isWide()) {
-        initialLocals.put(index++, frameType);
-      }
+      builder.appendLocal(FrameType.initialized(extraParameter.getType(dexItemFactory)));
     }
-    return initialLocals;
+    return builder.build();
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/LazyCfCode.java b/src/main/java/com/android/tools/r8/graph/LazyCfCode.java
index c32d6cb..66a16d8 100644
--- a/src/main/java/com/android/tools/r8/graph/LazyCfCode.java
+++ b/src/main/java/com/android/tools/r8/graph/LazyCfCode.java
@@ -71,13 +71,9 @@
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.ExceptionUtils;
 import com.android.tools.r8.utils.InternalOptions;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Deque;
 import java.util.HashMap;
 import java.util.IdentityHashMap;
 import java.util.List;
@@ -446,31 +442,25 @@
     public void visitFrame(
         int frameType, int nLocals, Object[] localTypes, int nStack, Object[] stackTypes) {
       assert frameType == Opcodes.F_NEW;
-      Int2ReferenceSortedMap<FrameType> parsedLocals = parseLocals(nLocals, localTypes);
-      Deque<FrameType> parsedStack = parseStack(nStack, stackTypes);
-      instructions.add(new CfFrame(parsedLocals, parsedStack));
+      CfFrame.Builder builder = CfFrame.builder();
+      parseLocals(nLocals, localTypes, builder);
+      parseStack(nStack, stackTypes, builder);
+      instructions.add(builder.build());
     }
 
-    private Int2ReferenceSortedMap<FrameType> parseLocals(int typeCount, Object[] asmTypes) {
-      Int2ReferenceSortedMap<FrameType> types = new Int2ReferenceAVLTreeMap<>();
-      int i = 0;
+    private void parseLocals(int typeCount, Object[] asmTypes, CfFrame.Builder builder) {
       for (int j = 0; j < typeCount; j++) {
         Object localType = asmTypes[j];
         FrameType value = getFrameType(localType);
-        types.put(i++, value);
-        if (value.isWide()) {
-          i++;
-        }
+        builder.appendLocal(value);
       }
-      return types;
     }
 
-    private Deque<FrameType> parseStack(int nStack, Object[] stackTypes) {
-      Deque<FrameType> dexStack = new ArrayDeque<>(nStack);
+    private void parseStack(int nStack, Object[] stackTypes, CfFrame.Builder builder) {
+      builder.allocateStack(nStack);
       for (int i = 0; i < nStack; i++) {
-        dexStack.add(getFrameType(stackTypes[i]));
+        builder.push(getFrameType(stackTypes[i]));
       }
-      return dexStack;
     }
 
     private FrameType getFrameType(Object localType) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java
index 835daa4..02b1abe 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/IncompleteVirtuallyMergedMethodCode.java
@@ -26,12 +26,9 @@
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.IterableUtils;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
 import it.unimi.dsi.fastutil.ints.IntBidirectionalIterator;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
-import java.util.Deque;
 import java.util.List;
 import org.objectweb.asm.Opcodes;
 
@@ -156,30 +153,22 @@
   }
 
   private static CfFrame createCfFrameForSwitchCase(ProgramMethod representative, int localsSize) {
-    Deque<FrameType> stack =
-        new ArrayDeque<>(representative.getDefinition().getNumberOfArguments());
+    CfFrame.Builder builder =
+        CfFrame.builder().allocateStack(representative.getDefinition().getNumberOfArguments());
     for (int argumentIndex = 0;
         argumentIndex < representative.getDefinition().getNumberOfArguments();
         argumentIndex++) {
-      stack.add(FrameType.initialized(representative.getArgumentType(argumentIndex)));
+      builder.push(FrameType.initialized(representative.getArgumentType(argumentIndex)));
     }
-    return new CfFrame(createLocalFrames(representative, localsSize), stack);
-  }
-
-  private static Int2ReferenceAVLTreeMap<FrameType> createLocalFrames(
-      ProgramMethod representative, int localsSize) {
-    Int2ReferenceAVLTreeMap<FrameType> locals = new Int2ReferenceAVLTreeMap<>();
-    for (int argumentIndex = 0, localIndex = 0;
+    for (int argumentIndex = 0;
         argumentIndex < representative.getDefinition().getNumberOfArguments();
         argumentIndex++) {
       FrameType frameType = FrameType.initialized(representative.getArgumentType(argumentIndex));
-      locals.put(localIndex++, frameType);
-      if (frameType.isWide()) {
-        locals.put(localIndex++, frameType);
-      }
+      builder.appendLocal(frameType);
     }
-    assert locals.size() == localsSize;
-    return locals;
+    CfFrame frame = builder.build();
+    assert frame.getLocals().size() == localsSize;
+    return frame;
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
index 4039c58..13c1982 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
@@ -57,15 +57,12 @@
 import com.android.tools.r8.ir.optimize.peepholes.BasicBlockMuncher;
 import com.android.tools.r8.utils.WorkList;
 import com.google.common.collect.Sets;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
@@ -591,25 +588,23 @@
 
   private void addFrame(BasicBlock block) {
     List<TypeInfo> stack = registerAllocator.getTypesAtBlockEntry(block).stack;
-    Deque<FrameType> stackTypes;
+    CfFrame.Builder builder = CfFrame.builder();
     if (block.entry().isMoveException()) {
       assert stack.isEmpty();
       StackValue exception = (StackValue) block.entry().outValue();
-      stackTypes = new ArrayDeque<>();
-      stackTypes.add(getFrameType(block, exception.getTypeInfo()));
+      builder.push(getFrameType(block, exception.getTypeInfo()));
     } else {
-      stackTypes = new ArrayDeque<>(stack.size());
+      builder.allocateStack(stack.size());
       for (TypeInfo typeInfo : stack) {
-        stackTypes.add(getFrameType(block, typeInfo));
+        builder.push(getFrameType(block, typeInfo));
       }
     }
 
     Int2ReferenceMap<TypeInfo> locals = registerAllocator.getTypesAtBlockEntry(block).registers;
-    Int2ReferenceSortedMap<FrameType> mapping = new Int2ReferenceAVLTreeMap<>();
     for (Entry<TypeInfo> local : locals.int2ReferenceEntrySet()) {
-      mapping.put(local.getIntKey(), getFrameType(block, local.getValue()));
+      builder.store(local.getIntKey(), getFrameType(block, local.getValue()));
     }
-    CfFrame frame = new CfFrame(mapping, stackTypes);
+    CfFrame frame = builder.build();
 
     // Make sure to end locals on this transition before the synthetic CfFrame instruction.
     // Otherwise we might extend the live range of a local across a CfFrame instruction that
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
index 5270193..af394c0 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
@@ -41,10 +41,10 @@
 import com.android.tools.r8.ir.conversion.IRBuilder.BlockInfo;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.InternalOutputMode;
+import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
 import it.unimi.dsi.fastutil.ints.IntArrayList;
 import it.unimi.dsi.fastutil.ints.IntList;
 import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
@@ -604,12 +604,11 @@
   }
 
   public void setStateFromFrame(CfFrame frame) {
-    Int2ReferenceSortedMap<FrameType> frameLocals = frame.getLocals();
+    Int2ObjectSortedMap<FrameType> frameLocals = frame.getLocals();
     DexType[] locals = new DexType[frameLocals.isEmpty() ? 0 : frameLocals.lastIntKey() + 1];
     DexType[] stack = new DexType[frame.getStack().size()];
-    for (Int2ReferenceMap.Entry<FrameType> entry : frameLocals.int2ReferenceEntrySet()) {
-      locals[entry.getIntKey()] = convertUninitialized(entry.getValue());
-    }
+    frame.forEachLocal(
+        (localIndex, frameType) -> locals[localIndex] = convertUninitialized(frameType));
     int index = 0;
     for (FrameType frameType : frame.getStack()) {
       stack[index++] = convertUninitialized(frameType);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java b/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java
index 8f0ddf7..57de6e1 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java
@@ -30,8 +30,6 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.MemberType;
 import com.android.tools.r8.ir.code.ValueType;
-import com.android.tools.r8.utils.collections.ImmutableDeque;
-import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
 
@@ -89,9 +87,7 @@
     CfLabel tryCatchHandler = new CfLabel();
     builder.add(
         tryCatchHandler,
-        new CfFrame(
-            ImmutableInt2ReferenceSortedMap.empty(),
-            ImmutableDeque.of(FrameType.initialized(factory.throwableType))),
+        CfFrame.builder().push(FrameType.initialized(factory.throwableType)).build(),
         new CfStore(ValueType.OBJECT, 0),
         new CfNew(factory.serviceLoaderConfigurationErrorType),
         new CfStackInstruction(CfStackInstruction.Opcode.Dup),
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java
index 1791282..1e6c36e 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java
@@ -49,7 +49,7 @@
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableList;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectAVLTreeMap;
 import java.util.ArrayDeque;
 import java.util.Arrays;
 
@@ -132,7 +132,7 @@
         ImmutableList.of(
             label0,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(
@@ -141,8 +141,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.OBJECT, 2),
@@ -165,7 +164,7 @@
             new CfReturn(ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(
@@ -174,8 +173,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfInvoke(
@@ -211,7 +209,7 @@
         ImmutableList.of(
             label0,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(
@@ -220,8 +218,7 @@
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.OBJECT, 1),
             new CfLoad(ValueType.OBJECT, 2),
@@ -244,7 +241,7 @@
             new CfReturn(ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(
@@ -253,8 +250,7 @@
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
@@ -290,7 +286,7 @@
         ImmutableList.of(
             label0,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -298,8 +294,7 @@
                               "Ljava/util/concurrent/atomic/AtomicReference;")),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.OBJECT, 1),
             new CfLoad(ValueType.OBJECT, 2),
@@ -319,7 +314,7 @@
             new CfReturn(ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -327,8 +322,7 @@
                               "Ljava/util/concurrent/atomic/AtomicReference;")),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInvoke(
                 182,
@@ -366,30 +360,28 @@
             new CfGoto(label3),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 0),
             new CfIf(If.Type.EQ, ValueType.INT, label2),
             new CfConstNumber(1, ValueType.INT),
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(-1, ValueType.INT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
@@ -420,14 +412,13 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)})),
             new CfConstNumber(1237, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.intType)}),
                 new ArrayDeque<>(
@@ -564,15 +555,14 @@
             new CfReturn(ValueType.INT),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             new CfStore(ValueType.INT, 4),
             label5,
@@ -591,7 +581,7 @@
             new CfStore(ValueType.INT, 5),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -600,8 +590,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 4),
             new CfLoad(ValueType.INT, 5),
             new CfIfCmp(If.Type.GE, ValueType.INT, label12),
@@ -640,7 +629,7 @@
             new CfReturn(ValueType.INT),
             label11,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -649,21 +638,19 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfIinc(4, 1),
             new CfGoto(label6),
             label12,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfLoad(ValueType.INT, 3),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Sub, NumericType.INT),
@@ -772,13 +759,12 @@
             new CfGoto(label11),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 182,
@@ -821,7 +807,7 @@
             new CfGoto(label11),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
@@ -890,7 +876,7 @@
             new CfThrow(),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
@@ -957,7 +943,7 @@
             new CfThrow(),
             label9,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
@@ -981,17 +967,16 @@
             new CfThrow(),
             label11,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfGoto(label20),
             label12,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
@@ -1047,7 +1032,7 @@
             new CfGoto(label18),
             label17,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
@@ -1061,37 +1046,34 @@
             new CfStore(ValueType.OBJECT, 3),
             label18,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.throwableType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfThrow(),
             label19,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.throwableType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfThrow(),
             label20,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfReturnVoid(),
             label21),
         ImmutableList.of(
@@ -1181,7 +1163,7 @@
             new CfStore(ValueType.INT, 4),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
@@ -1190,8 +1172,7 @@
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 4),
             new CfLoad(ValueType.INT, 3),
             new CfIfCmp(If.Type.GE, ValueType.INT, label5),
@@ -1224,13 +1205,12 @@
             new CfGoto(label2),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/ArrayList;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 184,
@@ -1339,7 +1319,7 @@
             new CfStore(ValueType.INT, 4),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(
@@ -1349,8 +1329,7 @@
                           options.itemFactory.createType("[Ljava/util/Map$Entry;")),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 4),
             new CfLoad(ValueType.INT, 3),
             new CfIfCmp(If.Type.GE, ValueType.INT, label8),
@@ -1457,7 +1436,7 @@
             new CfThrow(),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(
@@ -1467,20 +1446,18 @@
                           options.itemFactory.createType("[Ljava/util/Map$Entry;")),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfIinc(4, 1),
             new CfGoto(label2),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("[Ljava/util/Map$Entry;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/HashMap;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 184,
@@ -1535,7 +1512,7 @@
             new CfStore(ValueType.INT, 4),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
@@ -1543,8 +1520,7 @@
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 4),
             new CfLoad(ValueType.INT, 3),
             new CfIfCmp(If.Type.GE, ValueType.INT, label6),
@@ -1620,7 +1596,7 @@
             new CfThrow(),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
@@ -1628,19 +1604,17 @@
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfIinc(4, 1),
             new CfGoto(label2),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/HashSet;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 184,
@@ -1703,7 +1677,7 @@
             new CfStore(ValueType.OBJECT, 2),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -1711,8 +1685,7 @@
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/ArrayList;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Iterator;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 185,
@@ -1755,14 +1728,13 @@
             new CfGoto(label2),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/Collection;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/ArrayList;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 184,
@@ -1836,14 +1808,13 @@
             new CfStore(ValueType.OBJECT, 2),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Map;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/HashMap;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Iterator;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 185,
@@ -1915,13 +1886,12 @@
             new CfGoto(label2),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Map;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/HashMap;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 184,
@@ -1984,15 +1954,14 @@
             new CfStore(ValueType.OBJECT, 2),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/Collection;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/HashSet;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Iterator;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 185,
@@ -2035,14 +2004,13 @@
             new CfGoto(label2),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/Collection;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/HashSet;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 184,
@@ -2217,14 +2185,13 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.doubleType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.doubleType)})),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.doubleType)}),
                 new ArrayDeque<>(
@@ -2270,14 +2237,13 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.floatType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.floatType)})),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.floatType)}),
                 new ArrayDeque<>(
@@ -2307,13 +2273,12 @@
             new CfGoto(label3),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfIfCmp(If.Type.GE, ValueType.INT, label2),
@@ -2321,17 +2286,16 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(1, ValueType.INT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
@@ -2525,15 +2489,14 @@
             new CfIinc(1, 1),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
@@ -2696,13 +2659,12 @@
             new CfStore(ValueType.OBJECT, 0),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfInvoke(
@@ -2799,14 +2761,13 @@
             new CfThrow(),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 2),
             new CfNumberConversion(NumericType.LONG, NumericType.INT),
             new CfReturn(ValueType.INT),
@@ -3015,26 +2976,24 @@
             new CfReturn(ValueType.LONG),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(1, ValueType.LONG),
             new CfReturn(ValueType.LONG),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(0, ValueType.LONG),
             new CfCmp(Cmp.Bias.NONE, NumericType.LONG),
@@ -3046,13 +3005,12 @@
             new CfReturn(ValueType.LONG),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(1, ValueType.INT),
             new CfLogicalBinop(CfLogicalBinop.Opcode.Ushr, NumericType.LONG),
@@ -3088,7 +3046,7 @@
             new CfGoto(label14),
             label13,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6, 8, 10},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -3103,7 +3061,7 @@
             new CfConstNumber(0, ValueType.INT),
             label14,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6, 8, 10},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -3254,15 +3212,14 @@
             new CfIinc(1, 1),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
@@ -3379,7 +3336,7 @@
             new CfThrow(),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3387,8 +3344,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 3),
             new CfConstNumber(2, ValueType.INT),
             new CfIfCmp(If.Type.LT, ValueType.INT, label4),
@@ -3397,7 +3353,7 @@
             new CfIfCmp(If.Type.LE, ValueType.INT, label5),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3405,8 +3361,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/NumberFormatException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfConstString(options.itemFactory.createString("illegal radix: ")),
@@ -3438,7 +3393,7 @@
             new CfThrow(),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3446,8 +3401,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(-1, ValueType.LONG),
             new CfLoad(ValueType.INT, 3),
             new CfNumberConversion(NumericType.INT, NumericType.LONG),
@@ -3484,7 +3438,7 @@
             new CfGoto(label8),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3493,12 +3447,11 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3519,7 +3472,7 @@
             new CfStore(ValueType.INT, 10),
             label11,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5, 7, 8, 10},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3531,8 +3484,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 10),
             new CfLoad(ValueType.INT, 2),
             new CfIfCmp(If.Type.GE, ValueType.INT, label20),
@@ -3585,7 +3537,7 @@
             new CfThrow(),
             label15,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5, 7, 8, 10, 11},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3598,8 +3550,7 @@
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 8),
             new CfConstNumber(0, ValueType.LONG),
             new CfCmp(Cmp.Bias.NONE, NumericType.LONG),
@@ -3631,7 +3582,7 @@
             new CfIfCmp(If.Type.LE, ValueType.INT, label18),
             label17,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5, 7, 8, 10, 11},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3644,8 +3595,7 @@
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/NumberFormatException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfConstString(options.itemFactory.createString("Too large for unsigned long: ")),
@@ -3676,7 +3626,7 @@
             new CfThrow(),
             label18,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5, 7, 8, 10, 11},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3689,8 +3639,7 @@
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 8),
             new CfLoad(ValueType.INT, 3),
             new CfNumberConversion(NumericType.INT, NumericType.LONG),
@@ -3704,7 +3653,7 @@
             new CfGoto(label11),
             label20,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5, 7, 8},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -3715,8 +3664,7 @@
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 8),
             new CfReturn(ValueType.LONG),
             label21),
@@ -3810,28 +3758,26 @@
             new CfReturn(ValueType.LONG),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfLoad(ValueType.LONG, 2),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Sub, NumericType.LONG),
             new CfReturn(ValueType.LONG),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(0, ValueType.LONG),
             new CfCmp(Cmp.Bias.NONE, NumericType.LONG),
@@ -3843,13 +3789,12 @@
             new CfReturn(ValueType.LONG),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(1, ValueType.INT),
             new CfLogicalBinop(CfLogicalBinop.Opcode.Ushr, NumericType.LONG),
@@ -3885,7 +3830,7 @@
             new CfGoto(label14),
             label13,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6, 8, 10},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -3900,7 +3845,7 @@
             new CfConstNumber(0, ValueType.LONG),
             label14,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6, 8, 10},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -3992,13 +3937,12 @@
             new CfReturn(ValueType.OBJECT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(0, ValueType.LONG),
             new CfCmp(Cmp.Bias.NONE, NumericType.LONG),
@@ -4019,13 +3963,12 @@
             new CfReturn(ValueType.OBJECT),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfConstNumber(2, ValueType.INT),
             new CfIfCmp(If.Type.LT, ValueType.INT, label5),
@@ -4034,24 +3977,22 @@
             new CfIfCmp(If.Type.LE, ValueType.INT, label6),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(10, ValueType.INT),
             new CfStore(ValueType.INT, 2),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(64, ValueType.INT),
             new CfNewArray(options.itemFactory.charArrayType),
             new CfStore(ValueType.OBJECT, 3),
@@ -4084,7 +4025,7 @@
             new CfStore(ValueType.INT, 6),
             label11,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 3, 4, 5, 6},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4093,8 +4034,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 3),
             new CfIinc(4, -1),
             new CfLoad(ValueType.INT, 4),
@@ -4128,15 +4068,14 @@
             new CfGoto(label25),
             label15,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.charArrayType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfConstNumber(1, ValueType.INT),
             new CfLogicalBinop(CfLogicalBinop.Opcode.And, NumericType.INT),
@@ -4155,15 +4094,14 @@
             new CfGoto(label19),
             label18,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.charArrayType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfLoad(ValueType.INT, 2),
             new CfNumberConversion(NumericType.INT, NumericType.LONG),
@@ -4180,7 +4118,7 @@
             new CfStore(ValueType.LONG, 5),
             label19,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 3, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4188,8 +4126,7 @@
                       FrameType.initialized(options.itemFactory.charArrayType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfLoad(ValueType.LONG, 5),
             new CfLoad(ValueType.INT, 2),
@@ -4220,7 +4157,7 @@
             new CfStore(ValueType.LONG, 0),
             label22,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 3, 4, 5, 7},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4229,8 +4166,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(0, ValueType.LONG),
             new CfCmp(Cmp.Bias.NONE, NumericType.LONG),
@@ -4265,15 +4201,14 @@
             new CfGoto(label22),
             label25,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.charArrayType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.stringType),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfLoad(ValueType.OBJECT, 3),
@@ -4333,15 +4268,14 @@
             new CfReturn(ValueType.INT),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/ArithmeticException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -4388,18 +4322,17 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4418,7 +4351,7 @@
             new CfGoto(label5),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4430,7 +4363,7 @@
             new CfConstNumber(0, ValueType.INT),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4448,14 +4381,13 @@
             new CfReturn(ValueType.LONG),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/ArithmeticException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -4498,10 +4430,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)})),
             new CfLoad(ValueType.INT, 0),
             new CfConstNumber(1, ValueType.INT),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Sub, NumericType.INT),
@@ -4539,10 +4470,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.longType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.longType)})),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(1, ValueType.LONG),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Sub, NumericType.LONG),
@@ -4587,15 +4517,14 @@
             new CfReturn(ValueType.INT),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(1, ValueType.INT),
             new CfLoad(ValueType.INT, 0),
             new CfLoad(ValueType.INT, 1),
@@ -4613,7 +4542,7 @@
             new CfGoto(label7),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
@@ -4621,12 +4550,11 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
@@ -4680,15 +4608,14 @@
             new CfReturn(ValueType.LONG),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(1, ValueType.LONG),
             new CfLoad(ValueType.LONG, 0),
             new CfLoad(ValueType.LONG, 2),
@@ -4708,7 +4635,7 @@
             new CfGoto(label7),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6, 8},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4716,12 +4643,11 @@
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 4),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6, 8},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4793,14 +4719,13 @@
             new CfReturn(ValueType.INT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(1, ValueType.INT),
             new CfLoad(ValueType.INT, 0),
             new CfLoad(ValueType.INT, 1),
@@ -4816,21 +4741,20 @@
             new CfGoto(label6),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfLoad(ValueType.INT, 1),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.INT),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
@@ -4875,14 +4799,13 @@
             new CfReturn(ValueType.LONG),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(1, ValueType.LONG),
             new CfLoad(ValueType.LONG, 0),
             new CfLoad(ValueType.LONG, 2),
@@ -4900,21 +4823,20 @@
             new CfGoto(label6),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 4),
             new CfLoad(ValueType.LONG, 2),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.LONG),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 6},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -4986,10 +4908,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)})),
             new CfLoad(ValueType.INT, 0),
             new CfConstNumber(1, ValueType.INT),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.INT),
@@ -5027,10 +4948,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.longType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.longType)})),
             new CfLoad(ValueType.LONG, 0),
             new CfConstNumber(1, ValueType.LONG),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.LONG),
@@ -5074,15 +4994,14 @@
             new CfReturn(ValueType.INT),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/ArithmeticException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -5181,14 +5100,13 @@
             new CfReturn(ValueType.LONG),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 4),
             new CfConstNumber(64, ValueType.INT),
             new CfIfCmp(If.Type.LT, ValueType.INT, label15),
@@ -5200,18 +5118,17 @@
             new CfGoto(label9),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label9,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -5228,7 +5145,7 @@
             new CfGoto(label11),
             label10,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -5240,7 +5157,7 @@
             new CfConstNumber(0, ValueType.INT),
             label11,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -5271,27 +5188,25 @@
             new CfIf(If.Type.NE, ValueType.INT, label15),
             label14,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.LONG, 5),
             new CfReturn(ValueType.LONG),
             label15,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/ArithmeticException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -5486,10 +5401,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)})),
             new CfLoad(ValueType.INT, 0),
             new CfNeg(NumericType.INT),
             new CfReturn(ValueType.INT),
@@ -5526,10 +5440,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.longType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.longType)})),
             new CfLoad(ValueType.LONG, 0),
             new CfNeg(NumericType.LONG),
             new CfReturn(ValueType.LONG),
@@ -5624,15 +5537,14 @@
             new CfReturn(ValueType.INT),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/ArithmeticException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -5679,18 +5591,17 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -5709,7 +5620,7 @@
             new CfGoto(label5),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -5721,7 +5632,7 @@
             new CfConstNumber(0, ValueType.INT),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
@@ -5739,14 +5650,13 @@
             new CfReturn(ValueType.LONG),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.longType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/ArithmeticException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -5796,13 +5706,12 @@
             new CfThrow(),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfReturn(ValueType.INT),
             label4),
@@ -5835,14 +5744,13 @@
             new CfIfCmp(If.Type.LE, ValueType.INT, label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/IndexOutOfBoundsException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfNew(options.itemFactory.stringBuilderType),
@@ -5944,14 +5852,13 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 0),
             new CfReturn(ValueType.INT),
             label3),
@@ -5980,14 +5887,13 @@
             new CfIfCmp(If.Type.LE, ValueType.INT, label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/IndexOutOfBoundsException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfNew(options.itemFactory.stringBuilderType),
@@ -6071,14 +5977,13 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 0),
             new CfReturn(ValueType.INT),
             label3),
@@ -6104,13 +6009,12 @@
             new CfIfCmp(If.Type.LT, ValueType.INT, label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/IndexOutOfBoundsException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfNew(options.itemFactory.stringBuilderType),
@@ -6176,13 +6080,12 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 0),
             new CfReturn(ValueType.INT),
             label3),
@@ -6208,15 +6111,14 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/Comparator;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.OBJECT, 1),
@@ -6232,7 +6134,7 @@
                 true),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6302,26 +6204,24 @@
             new CfReturn(ValueType.INT),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfIf(If.Type.NE, ValueType.OBJECT, label2),
             new CfConstNumber(0, ValueType.INT),
             new CfReturn(ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.booleanArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label6),
@@ -6348,17 +6248,16 @@
             new CfGoto(label5),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6369,13 +6268,12 @@
             new CfReturn(ValueType.INT),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.byteArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label10),
@@ -6402,17 +6300,16 @@
             new CfGoto(label9),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label9,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6423,13 +6320,12 @@
             new CfReturn(ValueType.INT),
             label10,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.charArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label14),
@@ -6456,17 +6352,16 @@
             new CfGoto(label13),
             label12,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label13,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6477,13 +6372,12 @@
             new CfReturn(ValueType.INT),
             label14,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.doubleArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label18),
@@ -6510,17 +6404,16 @@
             new CfGoto(label17),
             label16,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label17,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6531,13 +6424,12 @@
             new CfReturn(ValueType.INT),
             label18,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.floatArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label22),
@@ -6564,17 +6456,16 @@
             new CfGoto(label21),
             label20,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label21,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6585,13 +6476,12 @@
             new CfReturn(ValueType.INT),
             label22,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.intArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label26),
@@ -6618,17 +6508,16 @@
             new CfGoto(label25),
             label24,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label25,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6639,13 +6528,12 @@
             new CfReturn(ValueType.INT),
             label26,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.longArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label30),
@@ -6672,17 +6560,16 @@
             new CfGoto(label29),
             label28,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label29,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6693,13 +6580,12 @@
             new CfReturn(ValueType.INT),
             label30,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.shortArrayType),
             new CfIf(If.Type.EQ, ValueType.INT, label34),
@@ -6726,17 +6612,16 @@
             new CfGoto(label33),
             label32,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label33,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6747,13 +6632,12 @@
             new CfReturn(ValueType.INT),
             label34,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInstanceOf(options.itemFactory.createType("[Ljava/lang/Object;")),
             new CfIf(If.Type.EQ, ValueType.INT, label38),
@@ -6780,17 +6664,16 @@
             new CfGoto(label37),
             label36,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label37,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6801,13 +6684,12 @@
             new CfReturn(ValueType.INT),
             label38,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
@@ -6854,28 +6736,26 @@
             new CfIf(If.Type.EQ, ValueType.INT, label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(1, ValueType.INT),
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -6906,10 +6786,9 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)})),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInvoke(
                 182,
@@ -6920,7 +6799,7 @@
                 false),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
                 new ArrayDeque<>(
@@ -6948,14 +6827,13 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)})),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
                 new ArrayDeque<>(
@@ -6983,14 +6861,13 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)})),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
                 new ArrayDeque<>(
@@ -7018,13 +6895,12 @@
             new CfReturn(ValueType.OBJECT),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfConstString(options.itemFactory.createString("defaultObj")),
             new CfInvoke(
@@ -7061,14 +6937,13 @@
             new CfReturn(ValueType.OBJECT),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/Supplier;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfConstString(options.itemFactory.createString("supplier")),
             new CfInvoke(
@@ -7138,13 +7013,12 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.stringType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfReturn(ValueType.OBJECT),
             label3),
@@ -7184,18 +7058,17 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/Supplier;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNull(),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -7220,14 +7093,13 @@
             new CfThrow(),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/Supplier;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfReturn(ValueType.OBJECT),
             label6),
@@ -7279,13 +7151,12 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.stringType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInvoke(
                 182,
@@ -7296,7 +7167,7 @@
                 false),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.objectType),
@@ -7352,15 +7223,14 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Optional;")),
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/Consumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 185,
@@ -7371,15 +7241,14 @@
                 true),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Optional;")),
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/Consumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfReturnVoid(),
             label4),
         ImmutableList.of(),
@@ -7429,7 +7298,7 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7437,8 +7306,7 @@
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/DoubleConsumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 185,
@@ -7449,7 +7317,7 @@
                 true),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7457,8 +7325,7 @@
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/DoubleConsumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfReturnVoid(),
             label4),
         ImmutableList.of(),
@@ -7508,7 +7375,7 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7516,8 +7383,7 @@
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/IntConsumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 185,
@@ -7528,7 +7394,7 @@
                 true),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7536,8 +7402,7 @@
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/IntConsumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfReturnVoid(),
             label4),
         ImmutableList.of(),
@@ -7587,7 +7452,7 @@
             new CfGoto(label3),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7595,8 +7460,7 @@
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/LongConsumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 185,
@@ -7607,7 +7471,7 @@
                 true),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7615,8 +7479,7 @@
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/LongConsumer;")),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Runnable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfReturnVoid(),
             label4),
         ImmutableList.of(),
@@ -7647,16 +7510,15 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Optional;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Optional;"))
@@ -7693,17 +7555,16 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/OptionalDouble;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7741,17 +7602,16 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/OptionalInt;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7789,17 +7649,16 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/OptionalLong;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
@@ -7851,14 +7710,13 @@
             new CfReturn(ValueType.OBJECT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Optional;")),
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/function/Supplier;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfInvoke(
                 185,
@@ -7927,12 +7785,11 @@
             new CfReturn(ValueType.OBJECT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Optional;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfInvoke(
                 184,
                 options.itemFactory.createMethod(
@@ -7988,13 +7845,12 @@
             new CfReturn(ValueType.OBJECT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/OptionalDouble;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfInvoke(
                 184,
                 options.itemFactory.createMethod(
@@ -8050,13 +7906,12 @@
             new CfReturn(ValueType.OBJECT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/OptionalInt;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfInvoke(
                 184,
                 options.itemFactory.createMethod(
@@ -8112,13 +7967,12 @@
             new CfReturn(ValueType.OBJECT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {
                       FrameType.initialized(
                           options.itemFactory.createType("Ljava/util/OptionalLong;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfInvoke(
                 184,
                 options.itemFactory.createMethod(
@@ -8258,10 +8112,9 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)})),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInvoke(
                 184,
@@ -8274,7 +8127,7 @@
                 true),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
                 new ArrayDeque<>(
@@ -8318,14 +8171,13 @@
             new CfStore(ValueType.INT, 2),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
             new CfIfCmp(If.Type.GE, ValueType.INT, label8),
@@ -8357,15 +8209,14 @@
             new CfReturn(ValueType.INT),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 3),
             new CfInvoke(
@@ -8382,10 +8233,9 @@
             new CfGoto(label2),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.stringType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.stringType)})),
             new CfConstNumber(1, ValueType.INT),
             new CfReturn(ValueType.INT),
             label9),
@@ -8427,14 +8277,13 @@
             new CfThrow(),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(
                           options.itemFactory.createType("[Ljava/lang/CharSequence;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.stringBuilderType),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -8469,7 +8318,7 @@
             new CfStore(ValueType.INT, 3),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
@@ -8477,8 +8326,7 @@
                           options.itemFactory.createType("[Ljava/lang/CharSequence;")),
                       FrameType.initialized(options.itemFactory.stringBuilderType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 3),
             new CfLoad(ValueType.OBJECT, 1),
             new CfArrayLength(),
@@ -8516,15 +8364,14 @@
             new CfGoto(label5),
             label9,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(
                           options.itemFactory.createType("[Ljava/lang/CharSequence;")),
                       FrameType.initialized(options.itemFactory.stringBuilderType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 182,
@@ -8572,13 +8419,12 @@
             new CfThrow(),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Iterable;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.stringBuilderType),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -8633,15 +8479,14 @@
             new CfStackInstruction(CfStackInstruction.Opcode.Pop),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Iterable;")),
                       FrameType.initialized(options.itemFactory.stringBuilderType),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Iterator;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 3),
             new CfInvoke(
                 185,
@@ -8688,15 +8533,14 @@
             new CfGoto(label5),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.charSequenceType),
                       FrameType.initialized(options.itemFactory.createType("Ljava/lang/Iterable;")),
                       FrameType.initialized(options.itemFactory.stringBuilderType),
                       FrameType.initialized(options.itemFactory.createType("Ljava/util/Iterator;"))
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfInvoke(
                 182,
@@ -8785,13 +8629,12 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInvoke(
                 182,
@@ -8808,26 +8651,24 @@
             new CfIf(If.Type.NE, ValueType.INT, label5),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstString(options.itemFactory.createString("")),
             new CfReturn(ValueType.OBJECT),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfConstNumber(1, ValueType.INT),
             new CfIfCmp(If.Type.NE, ValueType.INT, label7),
@@ -8836,14 +8677,13 @@
             new CfReturn(ValueType.OBJECT),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfInvoke(
                 182,
@@ -8941,14 +8781,13 @@
             new CfThrow(),
             label10,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.stringBuilderType),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfLoad(ValueType.INT, 2),
@@ -8968,7 +8807,7 @@
             new CfStore(ValueType.INT, 4),
             label12,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
@@ -8976,8 +8815,7 @@
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.stringBuilderType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 4),
             new CfLoad(ValueType.INT, 1),
             new CfIfCmp(If.Type.GE, ValueType.INT, label15),
@@ -8998,15 +8836,14 @@
             new CfGoto(label12),
             label15,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.stringBuilderType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 3),
             new CfInvoke(
                 182,
@@ -9058,14 +8895,13 @@
             new CfStore(ValueType.INT, 2),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
             new CfIfCmp(If.Type.GE, ValueType.INT, label8),
@@ -9096,15 +8932,14 @@
             new CfGoto(label8),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 3),
             new CfInvoke(
@@ -9121,14 +8956,13 @@
             new CfGoto(label2),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfLoad(ValueType.INT, 1),
             new CfIfCmp(If.Type.LE, ValueType.INT, label14),
@@ -9161,15 +8995,14 @@
             new CfGoto(label14),
             label12,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfLoad(ValueType.INT, 3),
             new CfInvoke(
@@ -9186,14 +9019,13 @@
             new CfGoto(label8),
             label14,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
@@ -9244,14 +9076,13 @@
             new CfStore(ValueType.INT, 2),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
             new CfIfCmp(If.Type.GE, ValueType.INT, label8),
@@ -9282,15 +9113,14 @@
             new CfGoto(label8),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 3),
             new CfInvoke(
@@ -9307,14 +9137,13 @@
             new CfGoto(label2),
             label8,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
@@ -9361,13 +9190,12 @@
             new CfStore(ValueType.INT, 1),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfIf(If.Type.LE, ValueType.INT, label7),
             label2,
@@ -9399,14 +9227,13 @@
             new CfGoto(label7),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 1),
             new CfLoad(ValueType.INT, 2),
             new CfInvoke(
@@ -9423,13 +9250,12 @@
             new CfGoto(label1),
             label7,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfConstNumber(0, ValueType.INT),
             new CfLoad(ValueType.INT, 1),
@@ -9505,7 +9331,7 @@
             new CfGoto(label4),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
@@ -9518,13 +9344,12 @@
             new CfStore(ValueType.OBJECT, 2),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.throwableType),
                       FrameType.initialized(options.itemFactory.throwableType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfReturnVoid(),
             label5),
         ImmutableList.of(
@@ -9584,7 +9409,7 @@
             new CfReturn(ValueType.OBJECT),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
                     new FrameType[] {FrameType.initialized(options.itemFactory.throwableType)}),
                 new ArrayDeque<>(
@@ -9620,7 +9445,7 @@
         ImmutableList.of(
             label0,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Lsun/misc/Unsafe;")),
@@ -9628,8 +9453,7 @@
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.OBJECT, 1),
             new CfLoad(ValueType.LONG, 2),
@@ -9653,7 +9477,7 @@
             new CfReturn(ValueType.INT),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("Lsun/misc/Unsafe;")),
@@ -9661,8 +9485,7 @@
                       FrameType.initialized(options.itemFactory.longType),
                       FrameType.initialized(options.itemFactory.objectType),
                       FrameType.initialized(options.itemFactory.objectType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 0),
             new CfLoad(ValueType.OBJECT, 1),
             new CfLoad(ValueType.LONG, 2),
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/constantdynamic/ConstantDynamicClass.java b/src/main/java/com/android/tools/r8/ir/desugar/constantdynamic/ConstantDynamicClass.java
index e408232..3378f64 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/constantdynamic/ConstantDynamicClass.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/constantdynamic/ConstantDynamicClass.java
@@ -60,8 +60,6 @@
 import com.android.tools.r8.synthesis.SyntheticProgramClassBuilder;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.ListUtils;
-import com.android.tools.r8.utils.collections.ImmutableDeque;
-import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
 import com.google.common.collect.ImmutableList;
 import java.util.Collection;
 import java.util.List;
@@ -307,11 +305,9 @@
 
     instructions.add(initializedTrueSecond);
     instructions.add(
-        new CfFrame(
-            ImmutableInt2ReferenceSortedMap.of(
-                new int[] {0},
-                new FrameType[] {FrameType.initialized(builder.getFactory().objectType)}),
-            ImmutableDeque.of()));
+        CfFrame.builder()
+            .appendLocal(FrameType.initialized(builder.getFactory().objectType))
+            .build());
     instructions.add(new CfLoad(ValueType.OBJECT, 0));
     instructions.add(new CfMonitor(Monitor.Type.EXIT));
     instructions.add(tryCatchEnd);
@@ -319,11 +315,10 @@
 
     instructions.add(tryCatchTarget);
     instructions.add(
-        new CfFrame(
-            ImmutableInt2ReferenceSortedMap.of(
-                new int[] {0},
-                new FrameType[] {FrameType.initialized(builder.getFactory().objectType)}),
-            ImmutableDeque.of(FrameType.initialized(builder.getFactory().throwableType))));
+        CfFrame.builder()
+            .appendLocal(FrameType.initialized(builder.getFactory().objectType))
+            .push(FrameType.initialized(builder.getFactory().throwableType))
+            .build());
     instructions.add(new CfStore(ValueType.OBJECT, 1));
     instructions.add(new CfLoad(ValueType.OBJECT, 0));
     instructions.add(new CfMonitor(Monitor.Type.EXIT));
@@ -332,7 +327,7 @@
     instructions.add(new CfThrow());
 
     instructions.add(initializedTrue);
-    instructions.add(new CfFrame(ImmutableInt2ReferenceSortedMap.empty(), ImmutableDeque.of()));
+    instructions.add(new CfFrame());
     instructions.add(new CfStaticFieldRead(constantValueField));
     instructions.add(new CfReturn(ValueType.OBJECT));
 
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/records/RecordCfMethods.java b/src/main/java/com/android/tools/r8/ir/desugar/records/RecordCfMethods.java
index f64b05b..25be1ab 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/records/RecordCfMethods.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/records/RecordCfMethods.java
@@ -36,7 +36,7 @@
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableList;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectAVLTreeMap;
 import java.util.ArrayDeque;
 import java.util.Arrays;
 
@@ -119,14 +119,13 @@
             new CfGoto(label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
                       FrameType.initialized(options.itemFactory.classType),
                       FrameType.initialized(options.itemFactory.stringType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 2),
             new CfConstString(options.itemFactory.createString(";")),
             new CfInvoke(
@@ -140,7 +139,7 @@
                 false),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
@@ -196,7 +195,7 @@
             new CfStore(ValueType.INT, 5),
             label6,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
@@ -205,8 +204,7 @@
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/String;")),
                       FrameType.initialized(options.itemFactory.stringBuilderType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 5),
             new CfLoad(ValueType.OBJECT, 3),
             new CfArrayLength(),
@@ -266,7 +264,7 @@
             new CfStackInstruction(CfStackInstruction.Opcode.Pop),
             label10,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
@@ -275,13 +273,12 @@
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/String;")),
                       FrameType.initialized(options.itemFactory.stringBuilderType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfIinc(5, 1),
             new CfGoto(label6),
             label11,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/Object;")),
@@ -289,8 +286,7 @@
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/String;")),
                       FrameType.initialized(options.itemFactory.stringBuilderType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 4),
             new CfConstString(options.itemFactory.createString("]")),
             new CfInvoke(
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCfMethods.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCfMethods.java
index 21c8b07..72473d5 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCfMethods.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingCfMethods.java
@@ -37,7 +37,7 @@
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableList;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectAVLTreeMap;
 import java.util.ArrayDeque;
 import java.util.Arrays;
 
@@ -64,13 +64,12 @@
             new CfIf(If.Type.NE, ValueType.INT, label2),
             label1,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfNew(options.itemFactory.createType("Ljava/lang/NullPointerException;")),
             new CfStackInstruction(CfStackInstruction.Opcode.Dup),
             new CfInvoke(
@@ -83,13 +82,12 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Sub, NumericType.INT),
@@ -127,13 +125,12 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 0),
             new CfLoad(ValueType.INT, 1),
             new CfIfCmp(If.Type.NE, ValueType.INT, label3),
@@ -141,17 +138,16 @@
             new CfGoto(label4),
             label3,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfConstNumber(0, ValueType.INT),
             label4,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
@@ -191,10 +187,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)})),
             new CfLoad(ValueType.INT, 0),
             new CfConstNumber(1, ValueType.INT),
             new CfArithmeticBinop(CfArithmeticBinop.Opcode.Sub, NumericType.INT),
@@ -226,14 +221,13 @@
             new CfStore(ValueType.INT, 2),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intArrayType),
                       FrameType.initialized(options.itemFactory.intType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.INT, 2),
             new CfLoad(ValueType.OBJECT, 1),
             new CfArrayLength(),
@@ -250,13 +244,12 @@
             new CfGoto(label2),
             label5,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.intArrayType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfLoad(ValueType.OBJECT, 1),
             new CfReturn(ValueType.OBJECT),
             label6),
@@ -290,10 +283,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.intType)})),
             new CfReturnVoid(),
             label3),
         ImmutableList.of(),
@@ -329,13 +321,12 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
                       FrameType.initialized(options.itemFactory.intType),
                       FrameType.initialized(options.itemFactory.stringType)
-                    }),
-                new ArrayDeque<>(Arrays.asList())),
+                    })),
             new CfReturnVoid(),
             label3),
         ImmutableList.of(),
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/templates/CfUtilityMethodsForCodeOptimizations.java b/src/main/java/com/android/tools/r8/ir/optimize/templates/CfUtilityMethodsForCodeOptimizations.java
index 33f1c04..2cdaa8e 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/templates/CfUtilityMethodsForCodeOptimizations.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/templates/CfUtilityMethodsForCodeOptimizations.java
@@ -25,9 +25,7 @@
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableList;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
-import java.util.ArrayDeque;
-import java.util.Arrays;
+import it.unimi.dsi.fastutil.ints.Int2ObjectAVLTreeMap;
 
 public final class CfUtilityMethodsForCodeOptimizations {
 
@@ -66,10 +64,9 @@
             new CfThrow(),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)})),
             new CfReturnVoid(),
             label3),
         ImmutableList.of(),
@@ -172,10 +169,9 @@
             new CfStackInstruction(CfStackInstruction.Opcode.Pop),
             label2,
             new CfFrame(
-                new Int2ReferenceAVLTreeMap<>(
+                new Int2ObjectAVLTreeMap<>(
                     new int[] {0},
-                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)}),
-                new ArrayDeque<>(Arrays.asList())),
+                    new FrameType[] {FrameType.initialized(options.itemFactory.objectType)})),
             new CfReturnVoid(),
             label3),
         ImmutableList.of(),
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/EmulateDispatchSyntheticCfCodeProvider.java b/src/main/java/com/android/tools/r8/ir/synthetic/EmulateDispatchSyntheticCfCodeProvider.java
index a82579e..480490c 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/EmulateDispatchSyntheticCfCodeProvider.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/EmulateDispatchSyntheticCfCodeProvider.java
@@ -21,8 +21,6 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.If;
 import com.android.tools.r8.ir.code.ValueType;
-import com.android.tools.r8.utils.collections.ImmutableDeque;
-import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
 import java.util.ArrayList;
 import java.util.LinkedHashMap;
 import java.util.List;
@@ -57,14 +55,16 @@
     }
     int nextLabel = 0;
 
-    ImmutableInt2ReferenceSortedMap.Builder<FrameType> localsBuilder =
-        ImmutableInt2ReferenceSortedMap.builder();
-    localsBuilder.put(0, FrameType.initialized(receiverType));
-    int index = 1;
-    for (DexType param : interfaceMethod.proto.parameters.values) {
-      localsBuilder.put(index++, FrameType.initialized(param));
-    }
-    ImmutableInt2ReferenceSortedMap<FrameType> locals = localsBuilder.build();
+    CfFrame frame =
+        CfFrame.builder()
+            .appendLocal(FrameType.initialized(receiverType))
+            .apply(
+                builder -> {
+                  for (DexType parameter : interfaceMethod.getParameters()) {
+                    builder.appendLocal(FrameType.initialized(parameter));
+                  }
+                })
+            .build();
 
     instructions.add(new CfLoad(ValueType.fromDexType(receiverType), 0));
     instructions.add(new CfInstanceOf(interfaceMethod.holder));
@@ -81,7 +81,7 @@
     for (Map.Entry<DexType, DexMethod> dispatch : extraDispatchCases.entrySet()) {
       // Type check basic block.
       instructions.add(labels[nextLabel++]);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame);
       instructions.add(new CfLoad(ValueType.fromDexType(receiverType), 0));
       instructions.add(new CfInstanceOf(dispatch.getKey()));
       instructions.add(new CfIf(If.Type.EQ, ValueType.INT, labels[nextLabel]));
@@ -96,7 +96,7 @@
 
     // Branch with companion call.
     instructions.add(labels[nextLabel]);
-    instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+    instructions.add(frame.clone());
     instructions.add(new CfLoad(ValueType.fromDexType(receiverType), 0));
     loadExtraParameters(instructions);
     instructions.add(new CfInvoke(Opcodes.INVOKESTATIC, forwardingMethod, false));
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java b/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java
index 6427f75..7de8d21 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java
@@ -34,8 +34,6 @@
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.optimize.enums.EnumDataMap.EnumData;
 import com.android.tools.r8.ir.optimize.enums.EnumInstanceFieldData.EnumInstanceFieldMappingData;
-import com.android.tools.r8.utils.collections.ImmutableDeque;
-import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
 import java.util.ArrayList;
 import java.util.List;
 import org.objectweb.asm.Opcodes;
@@ -102,13 +100,10 @@
       DexItemFactory factory = appView.dexItemFactory();
       List<CfInstruction> instructions = new ArrayList<>();
 
-      ImmutableInt2ReferenceSortedMap<FrameType> locals =
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-              .put(0, FrameType.initialized(factory.intType))
-              .build();
-
       // if (i == 1) { return 10;}
       // if (i == 2) { return 20;}
+      CfFrame.Builder frameBuilder =
+          CfFrame.builder().appendLocal(FrameType.initialized(factory.intType));
       fieldDataMap.forEach(
           (unboxedEnumValue, value) -> {
             CfLabel dest = new CfLabel();
@@ -118,7 +113,7 @@
             addCfInstructionsForAbstractValue(instructions, value, returnType);
             instructions.add(new CfReturn(ValueType.fromDexType(returnType)));
             instructions.add(dest);
-            instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+            instructions.add(frameBuilder.build());
           });
 
       if (nullValue != null) {
@@ -162,10 +157,8 @@
       DexItemFactory factory = appView.dexItemFactory();
       List<CfInstruction> instructions = new ArrayList<>();
 
-      ImmutableInt2ReferenceSortedMap<FrameType> locals =
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-              .put(0, FrameType.initialized(factory.stringType))
-              .build();
+      CfFrame frame =
+          CfFrame.builder().appendLocal(FrameType.initialized(factory.stringType)).build();
 
       // if (s == null) { throw npe("Name is null"); }
       CfLabel nullDest = new CfLabel();
@@ -178,7 +171,7 @@
           new CfInvoke(Opcodes.INVOKESPECIAL, factory.npeMethods.initWithMessage, false));
       instructions.add(new CfThrow());
       instructions.add(nullDest);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame);
 
       // if (s.equals("A")) { return 1;}
       // if (s.equals("B")) { return 2;}
@@ -193,7 +186,7 @@
             instructions.add(new CfConstNumber(unboxedEnumValue, ValueType.INT));
             instructions.add(new CfReturn(ValueType.INT));
             instructions.add(dest);
-            instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+            instructions.add(frame.clone());
           });
 
       // throw new IllegalArgumentException("No enum constant com.x.MyEnum." + s);
@@ -254,9 +247,7 @@
       instructions.add(new CfInvoke(Opcodes.INVOKESTATIC, initializationMethod, false));
       instructions.add(new CfStaticFieldWrite(utilityField, utilityField));
       instructions.add(nullDest);
-      instructions.add(
-          new CfFrame(
-              ImmutableInt2ReferenceSortedMap.<FrameType>builder().build(), ImmutableDeque.of()));
+      instructions.add(new CfFrame());
       instructions.add(new CfStaticFieldRead(utilityField, utilityField));
       instructions.add(new CfReturn(ValueType.OBJECT));
       return standardCfCodeFromInstructions(instructions);
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/RecordCfCodeProvider.java b/src/main/java/com/android/tools/r8/ir/synthetic/RecordCfCodeProvider.java
index be34a74..a6da57c 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/RecordCfCodeProvider.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/RecordCfCodeProvider.java
@@ -28,8 +28,6 @@
 import com.android.tools.r8.ir.code.If;
 import com.android.tools.r8.ir.code.MemberType;
 import com.android.tools.r8.ir.code.ValueType;
-import com.android.tools.r8.utils.collections.ImmutableDeque;
-import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
 import java.util.ArrayList;
 import java.util.List;
 import org.objectweb.asm.Opcodes;
@@ -161,11 +159,6 @@
       // return Arrays.equals(
       //     recordInstance.getFieldsAsObjects(),
       //     ((RecordClass) other).getFieldsAsObjects());
-      ImmutableInt2ReferenceSortedMap<FrameType> locals =
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-              .put(0, FrameType.initialized(getHolder()))
-              .put(1, FrameType.initialized(appView.dexItemFactory().objectType))
-              .build();
       DexItemFactory factory = appView.dexItemFactory();
       List<CfInstruction> instructions = new ArrayList<>();
       CfLabel fieldCmp = new CfLabel();
@@ -179,7 +172,11 @@
       instructions.add(new CfConstNumber(0, ValueType.INT));
       instructions.add(new CfReturn(ValueType.INT));
       instructions.add(fieldCmp);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(
+          CfFrame.builder()
+              .appendLocal(FrameType.initialized(getHolder()))
+              .appendLocal(FrameType.initialized(appView.dexItemFactory().objectType))
+              .build());
       instructions.add(new CfLoad(recordType, 0));
       instructions.add(new CfInvoke(Opcodes.INVOKESPECIAL, getFieldsAsObjects, false));
       instructions.add(new CfLoad(objectType, 1));
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/apiconverter/NullableConversionCfCodeProvider.java b/src/main/java/com/android/tools/r8/ir/synthetic/apiconverter/NullableConversionCfCodeProvider.java
index fc80fe8..a4f9714 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/apiconverter/NullableConversionCfCodeProvider.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/apiconverter/NullableConversionCfCodeProvider.java
@@ -41,8 +41,6 @@
 import com.android.tools.r8.ir.code.NumericType;
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.synthetic.SyntheticCfCodeProvider;
-import com.android.tools.r8.utils.collections.ImmutableDeque;
-import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
@@ -88,19 +86,14 @@
 
       // if (arg == null) { return null; }
       generateNullCheck(instructions);
-      instructions.add(
-          new CfFrame(
-              ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-                  .put(0, FrameType.initialized(typeArray))
-                  .build(),
-              ImmutableDeque.of()));
+      instructions.add(CfFrame.builder().appendLocal(FrameType.initialized(typeArray)).build());
 
-      ImmutableInt2ReferenceSortedMap<FrameType> locals =
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-              .put(0, FrameType.initialized(typeArray))
-              .put(1, FrameType.initialized(factory.intType))
-              .put(2, FrameType.initialized(convertedTypeArray))
-              .put(3, FrameType.initialized(factory.intType))
+      CfFrame frame =
+          CfFrame.builder()
+              .appendLocal(FrameType.initialized(typeArray))
+              .appendLocal(FrameType.initialized(factory.intType))
+              .appendLocal(FrameType.initialized(convertedTypeArray))
+              .appendLocal(FrameType.initialized(factory.intType))
               .build();
 
       // int t1 = arg.length;
@@ -118,7 +111,7 @@
       CfLabel returnLabel = new CfLabel();
       CfLabel loopLabel = new CfLabel();
       instructions.add(loopLabel);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame);
       instructions.add(new CfLoad(ValueType.INT, 3));
       instructions.add(new CfLoad(ValueType.INT, 1));
       instructions.add(new CfIfCmp(If.Type.GE, ValueType.INT, returnLabel));
@@ -138,7 +131,7 @@
       instructions.add(new CfGoto(loopLabel));
       // return t2;
       instructions.add(returnLabel);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame.clone());
       instructions.add(new CfLoad(ValueType.fromDexType(convertedTypeArray), 2));
       instructions.add(new CfReturn(ValueType.fromDexType(convertedTypeArray)));
       return standardCfCodeFromInstructions(instructions);
@@ -168,14 +161,11 @@
       DexItemFactory factory = appView.dexItemFactory();
       List<CfInstruction> instructions = new ArrayList<>();
 
-      ImmutableInt2ReferenceSortedMap<FrameType> locals =
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-              .put(0, FrameType.initialized(enumType))
-              .build();
+      CfFrame frame = CfFrame.builder().appendLocal(FrameType.initialized(enumType)).build();
 
       // if (arg == null) { return null; }
       generateNullCheck(instructions);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame);
 
       // if (arg == enumType.enumField1) { return convertedType.enumField1; }
       Iterator<DexEncodedField> iterator = enumFields.iterator();
@@ -194,7 +184,7 @@
         instructions.add(new CfReturn(ValueType.fromDexType(convertedType)));
         if (iterator.hasNext()) {
           instructions.add(notEqual);
-          instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+          instructions.add(frame.clone());
         }
       }
       return standardCfCodeFromInstructions(instructions);
@@ -219,14 +209,11 @@
       List<CfInstruction> instructions = new ArrayList<>();
 
       DexType argType = wrapperField.type;
-      ImmutableInt2ReferenceSortedMap<FrameType> locals =
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-              .put(0, FrameType.initialized(argType))
-              .build();
+      CfFrame frame = CfFrame.builder().appendLocal(FrameType.initialized(argType)).build();
 
       // if (arg == null) { return null };
       generateNullCheck(instructions);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame);
 
       // if (arg instanceOf ReverseWrapper) { return ((ReverseWrapper) arg).wrapperField};
       assert reverseWrapperField != null;
@@ -239,7 +226,7 @@
       instructions.add(new CfInstanceFieldRead(reverseWrapperField));
       instructions.add(new CfReturn(ValueType.fromDexType(reverseWrapperField.type)));
       instructions.add(unwrapDest);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame.clone());
 
       // return new Wrapper(wrappedValue);
       instructions.add(new CfNew(wrapperField.holder));
@@ -278,17 +265,13 @@
       // if (arg == null) { return null; }
       generateNullCheck(instructions);
       instructions.add(
-          new CfFrame(
-              ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-                  .put(0, FrameType.initialized(collectionType))
-                  .build(),
-              ImmutableDeque.of()));
+          CfFrame.builder().appendLocal(FrameType.initialized(collectionType)).build());
 
-      ImmutableInt2ReferenceSortedMap<FrameType> locals =
-          ImmutableInt2ReferenceSortedMap.<FrameType>builder()
-              .put(0, FrameType.initialized(collectionType))
-              .put(1, FrameType.initialized(collectionType))
-              .put(2, FrameType.initialized(factory.iteratorType))
+      CfFrame frame =
+          CfFrame.builder()
+              .appendLocal(FrameType.initialized(collectionType))
+              .appendLocal(FrameType.initialized(collectionType))
+              .appendLocal(FrameType.initialized(factory.iteratorType))
               .build();
 
       // Collection<E> t1 = new Collection<E>();
@@ -332,7 +315,7 @@
       CfLabel returnLabel = new CfLabel();
       CfLabel loopLabel = new CfLabel();
       instructions.add(loopLabel);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame);
       instructions.add(new CfLoad(ValueType.fromDexType(factory.iteratorType), 2));
       instructions.add(
           new CfInvoke(
@@ -367,7 +350,7 @@
 
       // return t1;
       instructions.add(returnLabel);
-      instructions.add(new CfFrame(locals, ImmutableDeque.of()));
+      instructions.add(frame.clone());
       instructions.add(new CfLoad(ValueType.fromDexType(collectionType), 1));
       instructions.add(new CfReturn(ValueType.fromDexType(collectionType)));
 
diff --git a/src/test/java/com/android/tools/r8/cf/FrameComparisonTest.java b/src/test/java/com/android/tools/r8/cf/FrameComparisonTest.java
new file mode 100644
index 0000000..5207198
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/cf/FrameComparisonTest.java
@@ -0,0 +1,51 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.cf;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.cf.code.CfFrame;
+import com.android.tools.r8.cf.code.CfFrame.FrameType;
+import com.android.tools.r8.graph.DexItemFactory;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class FrameComparisonTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    DexItemFactory dexItemFactory = new DexItemFactory();
+    CfFrame f1 =
+        CfFrame.builder()
+            .push(FrameType.initialized(dexItemFactory.objectType))
+            .store(0, FrameType.initialized(dexItemFactory.objectType))
+            .store(1, FrameType.initialized(dexItemFactory.objectType))
+            .build();
+    CfFrame f2 =
+        CfFrame.builder()
+            .push(FrameType.initialized(dexItemFactory.objectType))
+            .store(1, FrameType.initialized(dexItemFactory.objectType))
+            .store(0, FrameType.initialized(dexItemFactory.objectType))
+            .build();
+    assertEquals(f1.hashCode(), f2.hashCode());
+    assertEquals(f1, f2);
+    assertEquals(f2, f1);
+  }
+}