diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 1fa0b29..16f5f2e 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.4.4-dev";
+  public static final String LABEL = "1.4.5-dev";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 357de74..9500f9a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -822,7 +822,12 @@
     private TrivialInitializer trivialInitializerInfo = null;
     private boolean initializerEnablingJavaAssertions = false;
     private ParameterUsagesInfo parametersUsages = null;
-    private BitSet kotlinNotNullParamHints = null;
+    // Stores information about nullability hint per parameter. If set, that means, the method
+    // somehow (e.g., null check, such as arg != null, or using checkParameterIsNotNull) ensures
+    // the corresponding parameter is not null, or throws NPE before any other side effects.
+    // TODO(b/71500340): We call this *hint* because it does not 100% guarantee that a parameter is
+    // not null when the method returns normally. Maybe nonNullParamOnNormalExit in the future.
+    private BitSet nonNullParamHints = null;
 
     private OptimizationInfo() {
       // Intentionally left empty.
@@ -848,12 +853,12 @@
       return parametersUsages == null ? null : parametersUsages.getParameterUsage(parameter);
     }
 
-    public BitSet getKotlinNotNullParamHints() {
-      return kotlinNotNullParamHints;
+    public BitSet getNonNullParamHints() {
+      return nonNullParamHints;
     }
 
-    public void setKotlinNotNullParamHints(BitSet hints) {
-      this.kotlinNotNullParamHints = hints;
+    public void setNonNullParamHints(BitSet hints) {
+      this.nonNullParamHints = hints;
     }
 
     public boolean returnsArgument() {
@@ -1037,8 +1042,8 @@
     ensureMutableOI().setParameterUsages(parametersUsages);
   }
 
-  synchronized public void setKotlinNotNullParamHints(BitSet hints) {
-    ensureMutableOI().setKotlinNotNullParamHints(hints);
+  synchronized public void setNonNullParamHints(BitSet hints) {
+    ensureMutableOI().setNonNullParamHints(hints);
   }
 
   synchronized public void setTrivialInitializer(TrivialInitializer info) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 1ee16fb..3d5c58d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -160,6 +160,8 @@
   public final DexString methodHandleDescriptor = createString("Ljava/lang/invoke/MethodHandle;");
   public final DexString methodTypeDescriptor = createString("Ljava/lang/invoke/MethodType;");
 
+  public final DexString npeDescriptor = createString("Ljava/lang/NullPointerException;");
+
   public final DexString intFieldUpdaterDescriptor =
       createString("Ljava/util/concurrent/atomic/AtomicIntegerFieldUpdater;");
   public final DexString longFieldUpdaterDescriptor =
@@ -215,6 +217,8 @@
   public final DexType methodHandleType = createType(methodHandleDescriptor);
   public final DexType methodTypeType = createType(methodTypeDescriptor);
 
+  public final DexType npeType = createType(npeDescriptor);
+
   public final StringBuildingMethods stringBuilderMethods =
       new StringBuildingMethods(stringBuilderType);
   public final StringBuildingMethods stringBufferMethods =
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index f49115a..c628893 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -553,6 +553,9 @@
   }
 
   public DexType computeLeastUpperBoundOfClasses(AppInfo appInfo, DexType other) {
+    if (this == other) {
+      return this;
+    }
     DexType objectType = appInfo.dexItemFactory.objectType;
     // If we have no definition for either class, stop proceeding.
     if (hierarchyLevel == UNKNOWN_LEVEL || other.hierarchyLevel == UNKNOWN_LEVEL) {
@@ -561,10 +564,6 @@
     if (this == objectType || other == objectType) {
       return objectType;
     }
-    if (this == other) {
-      return this;
-    }
-
     DexType t1;
     DexType t2;
     if (other.hierarchyLevel < this.hierarchyLevel) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/Add.java b/src/main/java/com/android/tools/r8/ir/code/Add.java
index d5896da..2a8da38 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Add.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Add.java
@@ -83,11 +83,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asAdd().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left + right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java
index bff16af..9c3e58d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java
+++ b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java
@@ -42,11 +42,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java
index aa14475..49f144e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java
@@ -40,11 +40,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java
index 91be1a4..c7d617b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java
+++ b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java
@@ -40,11 +40,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     assert inValues.get(0).definition instanceof AlwaysMaterializingDefinition;
     return inValues.get(0).definition.maxOutValueRegister();
diff --git a/src/main/java/com/android/tools/r8/ir/code/And.java b/src/main/java/com/android/tools/r8/ir/code/And.java
index 283f369..73d3158 100644
--- a/src/main/java/com/android/tools/r8/ir/code/And.java
+++ b/src/main/java/com/android/tools/r8/ir/code/And.java
@@ -69,11 +69,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asAnd().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left & right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Argument.java b/src/main/java/com/android/tools/r8/ir/code/Argument.java
index cf52e26..92e16f4 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Argument.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Argument.java
@@ -56,12 +56,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isArgument();
-    return 0;
-  }
-
-  @Override
   public boolean isArgument() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
index 4254eef..b7286f8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
@@ -101,11 +101,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asArrayGet().type.ordinal();
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
index e222eaa..709ac0e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
@@ -82,12 +82,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isArrayLength();
-    return 0;
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forArrayLength();
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
index f27d55f..31ec3df 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
@@ -139,11 +139,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asArrayPut().type.ordinal();
-  }
-
-  @Override
   public boolean isArrayPut() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
index 03d718f..bb61b03 100644
--- a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
+++ b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
@@ -77,11 +77,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.slowCompareTo(other.asCheckCast().type);
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Cmp.java b/src/main/java/com/android/tools/r8/ir/code/Cmp.java
index 4c2529d..2f346a5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Cmp.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Cmp.java
@@ -127,11 +127,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return bias.ordinal() - other.asCmp().bias.ordinal();
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
index e612448..6f1b171 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
@@ -86,11 +86,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return clazz.slowCompareTo(other.asConstClass().clazz);
-  }
-
-  @Override
   public boolean canBeDeadCode(IRCode code, InternalOptions options) {
     // A const-class instruction can be dead code only if the resulting program is known to contain
     // the class mentioned.
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java b/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java
index 4f6b20e..e0b57f1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java
@@ -62,11 +62,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return methodHandle.slowCompareTo(other.asConstMethodHandle().methodHandle);
-  }
-
-  @Override
   public int maxInValueRegister() {
     assert false : "ConstMethodHandle has no register arguments.";
     return 0;
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java b/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java
index 584b109..fb23503 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java
@@ -62,11 +62,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return methodType.slowCompareTo(other.asConstMethodType().methodType);
-  }
-
-  @Override
   public int maxInValueRegister() {
     assert false : "ConstMethodType has no register arguments.";
     return 0;
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
index 1f31c3a..c09b6aa 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
@@ -215,17 +215,6 @@
     return o.outType() == outType() && o.value == value;
   }
 
-  @Override
-  public int compareNonValueParts(Instruction other) {
-    ConstNumber o = other.asConstNumber();
-    int result;
-    result = outType().ordinal() - o.outType().ordinal();
-    if (result != 0) {
-      return result;
-    }
-    return Long.signum(value - o.value);
-  }
-
   public boolean is8Bit() {
     return NumberUtils.is8Bit(value);
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstString.java b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
index 596bd81..f55d35f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
@@ -58,11 +58,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return value.slowCompareTo(other.asConstString().value);
-  }
-
-  @Override
   public int maxInValueRegister() {
     assert false : "ConstString has no register arguments.";
     return 0;
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java b/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java
index c7a45f2..ca9063d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java
@@ -45,11 +45,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java b/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java
index c956593..34ca368 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java
@@ -74,12 +74,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isDebugLocalsChange();
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java b/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
index 0fcc466..c373853 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
@@ -41,12 +41,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isDebugPosition();
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Div.java b/src/main/java/com/android/tools/r8/ir/code/Div.java
index 6c9537a..60daec0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Div.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Div.java
@@ -95,11 +95,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asDiv().type.ordinal();
-  }
-
-  @Override
   public boolean canBeFolded() {
     return super.canBeFolded() && !rightValue().isZero();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Dup.java b/src/main/java/com/android/tools/r8/ir/code/Dup.java
index 640d24c..090099e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Dup.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Dup.java
@@ -16,11 +16,41 @@
 
 public class Dup extends Instruction {
 
-  public Dup(StackValues dest, StackValue src) {
+  public Dup(StackValue destBottom, StackValue destTop, StackValue src) {
+    this(new StackValues(destBottom, destTop), src);
+  }
+
+  private Dup(StackValues dest, StackValue src) {
     super(dest, src);
   }
 
   @Override
+  public void setOutValue(Value value) {
+    assert outValue == null || !outValue.hasUsersInfo() || !outValue.isUsed() ||
+        value instanceof StackValues;
+    this.outValue = value;
+    for (StackValue val : ((StackValues)value).getStackValues()) {
+      val.definition = this;
+    }
+  }
+
+  private StackValue[] getStackValues() {
+    return ((StackValues) outValue()).getStackValues();
+  }
+
+  public StackValue outBottom() {
+    return getStackValues()[0];
+  }
+
+  public StackValue outTop() {
+    return getStackValues()[1];
+  }
+
+  public StackValue src() {
+    return (StackValue) inValues.get(0);
+  }
+
+  @Override
   public void buildDex(DexBuilder builder) {
     throw new Unreachable("This classfile-specific IR should not be inserted in the Dex backend.");
   }
@@ -40,11 +70,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    throw new Unreachable();
-  }
-
-  @Override
   public int maxInValueRegister() {
     return 0;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Dup2.java b/src/main/java/com/android/tools/r8/ir/code/Dup2.java
index decbaec..a682dc6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Dup2.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Dup2.java
@@ -17,11 +17,54 @@
 
 public class Dup2 extends Instruction {
 
-  public Dup2(StackValues dest, StackValue src1, StackValue src2) {
-    super(dest, ImmutableList.of(src1, src2));
-    assert !src1.getTypeLattice().isWide();
-    assert !src2.getTypeLattice().isWide();
-    assert dest.getStackValues().size() == 4;
+  public Dup2(
+      StackValue destTowMinusThree,
+      StackValue destTopMinusTwo,
+      StackValue destTopMinusOne,
+      StackValue destTop,
+      StackValue srcBottom,
+      StackValue srcTop) {
+    this(
+        new StackValues(destTowMinusThree, destTopMinusTwo, destTopMinusOne, destTop),
+        srcBottom,
+        srcTop);
+  }
+
+  private Dup2(StackValues dest, StackValue srcBottom, StackValue srcTop) {
+    super(dest, ImmutableList.of(srcBottom, srcTop));
+    assert !srcBottom.getTypeLattice().isWide();
+    assert !srcTop.getTypeLattice().isWide();
+    assert dest.getStackValues().length == 4;
+  }
+
+  @Override
+  public void setOutValue(Value value) {
+    assert outValue == null || !outValue.hasUsersInfo() || !outValue.isUsed() ||
+        value instanceof StackValues;
+    this.outValue = value;
+    for (StackValue val : ((StackValues)value).getStackValues()) {
+      val.definition = this;
+    }
+  }
+
+  private StackValue[] getStackValues() {
+    return ((StackValues) outValue()).getStackValues();
+  }
+
+  public StackValue outTopMinusThree() {
+    return getStackValues()[0];
+  }
+
+  public StackValue outTopMinusTwo() {
+    return getStackValues()[1];
+  }
+
+  public StackValue outTopMinusOne() {
+    return getStackValues()[2];
+  }
+
+  public StackValue outTop() {
+    return getStackValues()[3];
   }
 
   @Override
@@ -40,11 +83,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    throw new Unreachable();
-  }
-
-  @Override
   public int maxInValueRegister() {
     return 0;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Goto.java b/src/main/java/com/android/tools/r8/ir/code/Goto.java
index 972d2d2..dfe5b28 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Goto.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Goto.java
@@ -76,13 +76,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isGoto();
-    assert false : "Not supported";
-    return 0;
-  }
-
-  @Override
   public boolean isGoto() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/If.java b/src/main/java/com/android/tools/r8/ir/code/If.java
index 4fdb047..025dce9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/If.java
+++ b/src/main/java/com/android/tools/r8/ir/code/If.java
@@ -164,13 +164,6 @@
         && o.type == type;
   }
 
-  @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isIf();
-    assert false : "Not supported";
-    return 0;
-  }
-
   public BasicBlock targetFromCondition(ConstNumber value) {
     assert isZeroTest();
     assert value.outType() == ValueType.INT
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
index 3d30b82..a8bbcb3 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
@@ -103,16 +103,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    InstanceGet o = other.asInstanceGet();
-    int result = field.slowCompareTo(o.field);
-    if (result != 0) {
-      return result;
-    }
-    return type.ordinal() - o.type.ordinal();
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forInstanceGet(field, invocationContext);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
index 8e2446b..917c7fc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
@@ -64,11 +64,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.slowCompareTo(other.asInstanceOf().type);
-  }
-
-  @Override
   public boolean isInstanceOf() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstancePut.java b/src/main/java/com/android/tools/r8/ir/code/InstancePut.java
index e8d917d..0ad8544 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstancePut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstancePut.java
@@ -92,16 +92,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    InstancePut o = other.asInstancePut();
-    int result = field.slowCompareTo(o.field);
-    if (result != 0) {
-      return result;
-    }
-    return type.ordinal() - o.type.ordinal();
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U4BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index d4229bd..cda1c48 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -345,8 +345,6 @@
     return position.equals(other.position) && identicalNonValueNonPositionParts(other);
   }
 
-  public abstract int compareNonValueParts(Instruction other);
-
   private boolean identicalInputAfterRegisterAllocation(
       Value a, int aInstrNumber, Instruction bInstr, Value b, int bInstrNumber,
       RegisterAllocator allocator) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeCustom.java b/src/main/java/com/android/tools/r8/ir/code/InvokeCustom.java
index 1b03815..bb42328 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeCustom.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeCustom.java
@@ -84,13 +84,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isInvokeCustom();
-    assert false : "Not supported";
-    return 0;
-  }
-
-  @Override
   public boolean isInvokeCustom() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index 9689d22..060f1d8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -39,11 +39,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return getInvokedMethod().slowCompareTo(other.asInvokeMethod().getInvokedMethod());
-  }
-
-  @Override
   public String toString() {
     return super.toString() + "; method: " + method.toSourceString();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
index 002fa9d..cfd3b1d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
@@ -60,14 +60,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    if (!other.isInvokeMultiNewArray()) {
-      return -1;
-    }
-    return type.slowCompareTo(other.asInvokeMultiNewArray().type);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forInvokeMultiNewArray(type, invocationContext);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
index b071703..df74e17 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
@@ -80,14 +80,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    if (!other.isInvokeNewArray()) {
-      return -1;
-    }
-    return type.slowCompareTo(other.asInvokeNewArray().type);
-  }
-
-  @Override
   public boolean isInvokeNewArray() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Load.java b/src/main/java/com/android/tools/r8/ir/code/Load.java
index 4a6817f..fb1c0ef 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Load.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Load.java
@@ -42,11 +42,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U16BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Monitor.java b/src/main/java/com/android/tools/r8/ir/code/Monitor.java
index eb1c030..766da27 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Monitor.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Monitor.java
@@ -66,11 +66,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asMonitor().type.ordinal();
-  }
-
-  @Override
   public int maxInValueRegister() {
     return U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Move.java b/src/main/java/com/android/tools/r8/ir/code/Move.java
index 7c9dcca..0ee6178 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Move.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Move.java
@@ -67,12 +67,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isMove();
-    return 0;
-  }
-
-  @Override
   public String toString() {
     return super.toString() + " (" + outType() + ")";
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/MoveException.java b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
index 8166f6e..8bbb672 100644
--- a/src/main/java/com/android/tools/r8/ir/code/MoveException.java
+++ b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
@@ -53,12 +53,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isMoveException();
-    return 0;
-  }
-
-  @Override
   public boolean isMoveException() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Mul.java b/src/main/java/com/android/tools/r8/ir/code/Mul.java
index 7407f2e..ebe12f8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Mul.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Mul.java
@@ -95,11 +95,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asMul().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left * right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Neg.java b/src/main/java/com/android/tools/r8/ir/code/Neg.java
index 86e7440..856e2e0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Neg.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Neg.java
@@ -40,11 +40,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asNeg().type.ordinal();
-  }
-
-  @Override
   public void buildDex(DexBuilder builder) {
     com.android.tools.r8.code.Instruction instruction;
     int dest = builder.allocatedRegister(dest(), getNumber());
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
index c8f229a..95a9225 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
@@ -68,11 +68,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.slowCompareTo(other.asNewArrayEmpty().type);
-  }
-
-  @Override
   public boolean isNewArrayEmpty() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
index 0574e59..f0b1db9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
@@ -63,28 +63,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    NewArrayFilledData o = other.asNewArrayFilledData();
-    int result;
-    result = element_width - o.element_width;
-    if (result != 0) {
-      return result;
-    }
-    result = Long.signum(size - o.size);
-    if (result != 0) {
-      return result;
-    }
-    assert data.length == o.data.length;
-    for (int i = 0; i < data.length; i++) {
-      result = data[i] - o.data[i];
-      if (result != 0) {
-        return result;
-      }
-    }
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
index 18a60d4..747966c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
@@ -48,11 +48,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return clazz.slowCompareTo(other.asNewInstance().clazz);
-  }
-
-  @Override
   public int maxInValueRegister() {
     assert false : "NewInstance has no register arguments";
     return 0;
diff --git a/src/main/java/com/android/tools/r8/ir/code/NonNull.java b/src/main/java/com/android/tools/r8/ir/code/NonNull.java
index 17bd113..55b9b67 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NonNull.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NonNull.java
@@ -78,12 +78,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other instanceof NonNull;
-    return 0;
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forNonNull();
diff --git a/src/main/java/com/android/tools/r8/ir/code/Not.java b/src/main/java/com/android/tools/r8/ir/code/Not.java
index 1073f4e..013b219 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Not.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Not.java
@@ -74,11 +74,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asNot().type.ordinal();
-  }
-
-  @Override
   public boolean isNot() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/NumberConversion.java b/src/main/java/com/android/tools/r8/ir/code/NumberConversion.java
index d676216..fd9afa8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NumberConversion.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NumberConversion.java
@@ -128,17 +128,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    NumberConversion o = other.asNumberConversion();
-    int result;
-    result = from.ordinal() - o.from.ordinal();
-    if (result != 0) {
-      return result;
-    }
-    return to.ordinal() - o.to.ordinal();
-  }
-
-  @Override
   public boolean isNumberConversion() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Or.java b/src/main/java/com/android/tools/r8/ir/code/Or.java
index 9136be3..fd4f204 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Or.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Or.java
@@ -68,11 +68,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asOr().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left | right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Pop.java b/src/main/java/com/android/tools/r8/ir/code/Pop.java
index 9d63ee1..2598d55 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Pop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Pop.java
@@ -35,11 +35,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Rem.java b/src/main/java/com/android/tools/r8/ir/code/Rem.java
index 02eb712..bd838bc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Rem.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Rem.java
@@ -95,11 +95,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asRem().type.ordinal();
-  }
-
-  @Override
   public boolean canBeFolded() {
     return super.canBeFolded() && !rightValue().isZero();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Return.java b/src/main/java/com/android/tools/r8/ir/code/Return.java
index bb750c2..2bbb8c2 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Return.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Return.java
@@ -86,15 +86,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    if (isReturnVoid()) {
-      return other.asReturn().isReturnVoid() ? 0 : -1;
-    } else {
-      return returnValue().type.ordinal() - other.asReturn().returnValue().type.ordinal();
-    }
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Shl.java b/src/main/java/com/android/tools/r8/ir/code/Shl.java
index 57b3190..d9d0be0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Shl.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Shl.java
@@ -74,11 +74,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asShl().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left << right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Shr.java b/src/main/java/com/android/tools/r8/ir/code/Shr.java
index 18c38ed..c930d1d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Shr.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Shr.java
@@ -74,11 +74,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asShr().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left >> right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/StackValues.java b/src/main/java/com/android/tools/r8/ir/code/StackValues.java
index 79ca78b..5e0a979 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StackValues.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StackValues.java
@@ -6,7 +6,6 @@
 
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
-import java.util.List;
 
 /**
  * {@link StackValues} allow us to represent stack operations that produces two or more elements on
@@ -14,15 +13,15 @@
  */
 public class StackValues extends Value {
 
-  private final List<StackValue> stackValues;
+  private final StackValue[] stackValues;
 
-  public StackValues(List<StackValue> stackValues) {
+  public StackValues(StackValue... stackValues) {
     super(Value.UNDEFINED_NUMBER, TypeLatticeElement.BOTTOM, null);
     this.stackValues = stackValues;
-    assert stackValues.size() >= 2;
+    assert stackValues.length >= 2;
   }
 
-  public List<StackValue> getStackValues() {
+  public StackValue[] getStackValues() {
     return stackValues;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
index e767246..b616d38 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
@@ -97,17 +97,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    StaticGet o = other.asStaticGet();
-    int result;
-    result = field.slowCompareTo(o.field);
-    if (result != 0) {
-      return result;
-    }
-    return type.ordinal() - o.type.ordinal();
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forStaticGet(field, invocationContext);
diff --git a/src/main/java/com/android/tools/r8/ir/code/StaticPut.java b/src/main/java/com/android/tools/r8/ir/code/StaticPut.java
index 8824d54..ef64300 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StaticPut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StaticPut.java
@@ -96,17 +96,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    StaticPut o = other.asStaticPut();
-    int result;
-    result = field.slowCompareTo(o.field);
-    if (result != 0) {
-      return result;
-    }
-    return type.ordinal() - o.type.ordinal();
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forStaticPut(field, invocationContext);
diff --git a/src/main/java/com/android/tools/r8/ir/code/Store.java b/src/main/java/com/android/tools/r8/ir/code/Store.java
index 1e71f1e..070b308 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Store.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Store.java
@@ -44,11 +44,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return 0;
-  }
-
-  @Override
   public int maxInValueRegister() {
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Sub.java b/src/main/java/com/android/tools/r8/ir/code/Sub.java
index b263e63..7e7a9f8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Sub.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Sub.java
@@ -90,11 +90,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asSub().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left - right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Swap.java b/src/main/java/com/android/tools/r8/ir/code/Swap.java
index 9e65d0f..29eb9eb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Swap.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Swap.java
@@ -17,15 +17,35 @@
 
 public class Swap extends Instruction {
 
-  public Swap(StackValues dest, StackValues src) {
-    super(dest, src.getStackValues());
-    assert src.getStackValues().size() == 2;
+  public Swap(StackValue destBottom, StackValue destTop, StackValue srcBottom, StackValue srcTop) {
+    this(new StackValues(destBottom, destTop), srcBottom, srcTop);
+  }
+
+  private Swap(StackValues dest, StackValue src1, StackValue src2) {
+    super(dest, ImmutableList.of(src1, src2));
     assert !this.inValues.get(0).type.isWide() && !this.inValues.get(1).type.isWide();
   }
 
-  public Swap(StackValues dest, StackValue src1, StackValue src2) {
-    super(dest, ImmutableList.of(src1, src2));
-    assert !this.inValues.get(0).type.isWide() && !this.inValues.get(1).type.isWide();
+  @Override
+  public void setOutValue(Value value) {
+    assert outValue == null || !outValue.hasUsersInfo() || !outValue.isUsed() ||
+        value instanceof StackValues;
+    this.outValue = value;
+    for (StackValue val : ((StackValues)value).getStackValues()) {
+      val.definition = this;
+    }
+  }
+
+  private StackValue[] getStackValues() {
+    return ((StackValues) outValue()).getStackValues();
+  }
+
+  public StackValue outBottom() {
+    return getStackValues()[0];
+  }
+
+  public StackValue outTop() {
+    return getStackValues()[1];
   }
 
   @Override
@@ -44,11 +64,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    throw new Unreachable();
-  }
-
-  @Override
   public int maxInValueRegister() {
     return 0;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Switch.java b/src/main/java/com/android/tools/r8/ir/code/Switch.java
index 871500c..fb45d97 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Switch.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Switch.java
@@ -153,12 +153,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isSwitch();
-    return 0;
-  }
-
-  @Override
   public void buildDex(DexBuilder builder) {
     int value = builder.allocatedRegister(value(), getNumber());
     if (emitPacked()) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/Throw.java b/src/main/java/com/android/tools/r8/ir/code/Throw.java
index 7bda1c8..eede2da 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Throw.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Throw.java
@@ -49,12 +49,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    assert other.isThrow();
-    return 0;
-  }
-
-  @Override
   public boolean isThrow() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Ushr.java b/src/main/java/com/android/tools/r8/ir/code/Ushr.java
index d1e5a69..65c932c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Ushr.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Ushr.java
@@ -74,11 +74,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asUshr().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left >>> right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Xor.java b/src/main/java/com/android/tools/r8/ir/code/Xor.java
index 2e9c497..f3b8858 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Xor.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Xor.java
@@ -68,11 +68,6 @@
   }
 
   @Override
-  public int compareNonValueParts(Instruction other) {
-    return type.ordinal() - other.asXor().type.ordinal();
-  }
-
-  @Override
   int foldIntegers(int left, int right) {
     return left ^ right;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index d02bdc7..540eacb 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -5,6 +5,7 @@
 
 import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.Flavor.ExcludeDexResources;
 import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.Flavor.IncludeAllResources;
+import static com.android.tools.r8.ir.optimize.CodeRewriter.checksNullReceiverBeforeSideEffect;
 
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
@@ -71,6 +72,7 @@
 import com.google.common.base.Suppliers;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ListMultimap;
+import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.BitSet;
 import java.util.Collection;
@@ -276,10 +278,11 @@
     }
   }
 
-  private void synthesizeLambdaClasses(Builder<?> builder) {
+  private void synthesizeLambdaClasses(Builder<?> builder, ExecutorService executorService)
+      throws ExecutionException {
     if (lambdaRewriter != null) {
       lambdaRewriter.adjustAccessibility();
-      lambdaRewriter.synthesizeLambdaClasses(builder);
+      lambdaRewriter.synthesizeLambdaClasses(builder, executorService);
     }
   }
 
@@ -297,9 +300,13 @@
   }
 
   private void desugarInterfaceMethods(
-      Builder<?> builder, InterfaceMethodRewriter.Flavor includeAllResources) {
+      Builder<?> builder,
+      InterfaceMethodRewriter.Flavor includeAllResources,
+      ExecutorService executorService)
+      throws ExecutionException {
     if (interfaceMethodRewriter != null) {
-      interfaceMethodRewriter.desugarInterfaceMethods(builder, includeAllResources);
+      interfaceMethodRewriter.desugarInterfaceMethods(
+          builder, includeAllResources, executorService);
     }
   }
 
@@ -326,8 +333,8 @@
     Builder<?> builder = application.builder();
     builder.setHighestSortingString(highestSortingString);
 
-    synthesizeLambdaClasses(builder);
-    desugarInterfaceMethods(builder, ExcludeDexResources);
+    synthesizeLambdaClasses(builder, executor);
+    desugarInterfaceMethods(builder, ExcludeDexResources, executor);
     synthesizeTwrCloseResourceUtilityClass(builder);
     processCovariantReturnTypeAnnotations(builder);
 
@@ -499,8 +506,8 @@
       inliner.processDoubleInlineCallers(this, directFeedback);
     }
 
-    synthesizeLambdaClasses(builder);
-    desugarInterfaceMethods(builder, IncludeAllResources);
+    synthesizeLambdaClasses(builder, executorService);
+    desugarInterfaceMethods(builder, IncludeAllResources, executorService);
     synthesizeTwrCloseResourceUtilityClass(builder);
 
     handleSynthesizedClassMapping(builder);
@@ -650,6 +657,24 @@
     }
   }
 
+  public void optimizeSynthesizedClasses(
+      Collection<DexProgramClass> classes, ExecutorService executorService)
+      throws ExecutionException {
+    Set<DexEncodedMethod> methods = Sets.newIdentityHashSet();
+    try {
+      for (DexProgramClass clazz : classes) {
+        enterCachedClass(clazz);
+        clazz.forEachMethod(methods::add);
+      }
+      // Process the generated class, but don't apply any outlining.
+      optimizeSynthesizedMethods(methods, executorService);
+    } finally {
+      for (DexProgramClass clazz : classes) {
+        leaveCachedClass(clazz);
+      }
+    }
+  }
+
   public void optimizeMethodOnSynthesizedClass(DexProgramClass clazz, DexEncodedMethod method) {
     if (!method.isProcessed()) {
       try {
@@ -670,6 +695,26 @@
     }
   }
 
+  public void optimizeSynthesizedMethods(
+      Collection<DexEncodedMethod> methods, ExecutorService executorService)
+      throws ExecutionException {
+    List<Future<?>> futures = new ArrayList<>();
+    for (DexEncodedMethod method : methods) {
+      futures.add(
+          executorService.submit(
+              () -> {
+                processMethod(
+                    method,
+                    ignoreOptimizationFeedback,
+                    methods::contains,
+                    CallSiteInformation.empty(),
+                    Outliner::noProcessing);
+                return null; // we want a Callable not a Runnable to be able to throw
+              }));
+    }
+    ThreadUtils.awaitFutures(futures);
+  }
+
   private void enterCachedClass(DexProgramClass clazz) {
     DexProgramClass previous = cachedClasses.put(clazz.type, clazz);
     assert previous == null;
@@ -740,7 +785,7 @@
     printMethod(code, "Initial IR (SSA)");
 
     if (method.getCode() != null && method.getCode().isJarCode()) {
-      computeKotlinNotNullParamHints(feedback, method, code);
+      computeKotlinNonNullParamHints(feedback, method, code);
     }
 
     if (options.canHaveArtStringNewInitBug()) {
@@ -886,6 +931,11 @@
     if (options.enableInlining && inliner != null) {
       codeRewriter.identifyInvokeSemanticsForInlining(method, code, feedback);
     }
+    // If hints from Kotlin metadata or use of Kotlin Intrinsics were not available, track usage of
+    // parameters and compute their nullability.
+    if (method.getOptimizationInfo().getNonNullParamHints() == null) {
+      computeNonNullParamHints(feedback, method, code);
+    }
 
     // Insert code to log arguments if requested.
     if (options.methodMatchesLogArgumentsFilter(method)) {
@@ -911,7 +961,7 @@
     finalizeIR(method, code, feedback);
   }
 
-  private void computeKotlinNotNullParamHints(
+  private void computeKotlinNonNullParamHints(
       OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
     DexMethod originalSignature = graphLense().getOriginalMethodSignature(method.method);
     DexClass originalHolder = definitionFor(originalSignature.holder);
@@ -927,7 +977,7 @@
               originalSignature.name.toString(), originalSignature.proto.toDescriptorString());
       if (hintFromMetadata != null) {
         if (hintFromMetadata.length() > 0) {
-          feedback.setKotlinNotNullParamHints(method, hintFromMetadata);
+          feedback.setNonNullParamHints(method, hintFromMetadata);
         }
         return;
       }
@@ -959,7 +1009,28 @@
       }
     }
     if (paramsCheckedForNull.length() > 0) {
-      feedback.setKotlinNotNullParamHints(method, paramsCheckedForNull);
+      feedback.setNonNullParamHints(method, paramsCheckedForNull);
+    }
+  }
+
+  private void computeNonNullParamHints(
+    OptimizationFeedback feedback, DexEncodedMethod method, IRCode code) {
+    List<Value> arguments = code.collectArguments(true);
+    BitSet paramsCheckedForNull = new BitSet();
+    for (int index = 0; index < arguments.size(); index++) {
+      Value argument = arguments.get(index);
+      if (argument.isUsed()
+          && checksNullReceiverBeforeSideEffect(code, appInfo.dexItemFactory, argument)) {
+        paramsCheckedForNull.set(index);
+      }
+      // TODO(b/71500340): More sophisticated analysis?
+      // The above one only catches something like:
+      //   if (param == null) return;
+      //   throw new NPE;
+      // which is good enough to handle Intrinsics.checkParameterIsNotNull(param, message)
+    }
+    if (paramsCheckedForNull.length() > 0) {
+      feedback.setNonNullParamHints(method, paramsCheckedForNull);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
index 4e6cbf4..5046513 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
@@ -531,7 +531,7 @@
       currentPosition = getCanonicalDebugPositionAtOffset(instructionIndex);
     }
 
-    String preInstructionState;
+    String preInstructionState = "";
     if (Log.ENABLED) {
       preInstructionState = state.toString();
     }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
index 0833579..102130c 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedback.java
@@ -23,5 +23,5 @@
   void setTrivialInitializer(DexEncodedMethod method, TrivialInitializer info);
   void setInitializerEnablingJavaAssertions(DexEncodedMethod method);
   void setParameterUsages(DexEncodedMethod method, ParameterUsagesInfo parameterUsagesInfo);
-  void setKotlinNotNullParamHints(DexEncodedMethod method, BitSet hints);
+  void setNonNullParamHints(DexEncodedMethod method, BitSet hints);
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDirect.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDirect.java
index 16267f6..8a37f3b 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDirect.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDirect.java
@@ -70,7 +70,7 @@
   }
 
   @Override
-  public void setKotlinNotNullParamHints(DexEncodedMethod method, BitSet hints) {
-    method.setKotlinNotNullParamHints(hints);
+  public void setNonNullParamHints(DexEncodedMethod method, BitSet hints) {
+    method.setNonNullParamHints(hints);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
index a27f200..28fb006 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackIgnore.java
@@ -52,6 +52,6 @@
   }
 
   @Override
-  public void setKotlinNotNullParamHints(DexEncodedMethod method, BitSet hints) {
+  public void setNonNullParamHints(DexEncodedMethod method, BitSet hints) {
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
index 2583f8f..449aede 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackSimple.java
@@ -71,7 +71,7 @@
   }
 
   @Override
-  public void setKotlinNotNullParamHints(DexEncodedMethod method, BitSet hints) {
+  public void setNonNullParamHints(DexEncodedMethod method, BitSet hints) {
     // Ignored.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
index 0f6dbd7..7a19fb8 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
@@ -37,6 +37,8 @@
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 
 //
 // Default and static interface method desugaring rewriter (note that lambda
@@ -374,7 +376,9 @@
    * Move static and default interface methods to companion classes,
    * add missing methods to forward to moved default methods implementation.
    */
-  public void desugarInterfaceMethods(Builder<?> builder, Flavor flavour) {
+  public void desugarInterfaceMethods(
+      Builder<?> builder, Flavor flavour, ExecutorService executorService)
+      throws ExecutionException {
     // Process all classes first. Add missing forwarding methods to
     // replace desugared default interface methods.
     synthesizedMethods.addAll(processClasses(builder, flavour));
@@ -391,9 +395,7 @@
       builder.addSynthesizedClass(entry.getValue(), isInMainDexList(entry.getKey()));
     }
 
-    for (DexEncodedMethod method : synthesizedMethods) {
-      converter.optimizeSynthesizedMethod(method);
-    }
+    converter.optimizeSynthesizedMethods(synthesizedMethods, executorService);
 
     // Cached data is not needed any more.
     clear();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
index 22113f8..b89a185 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
@@ -29,12 +29,15 @@
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
+import com.google.common.collect.ImmutableSet;
 import java.util.ArrayList;
 import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 
 /**
  * Lambda desugaring rewriter.
@@ -189,10 +192,14 @@
   }
 
   /** Generates lambda classes and adds them to the builder. */
-  public void synthesizeLambdaClasses(Builder<?> builder) {
+  public void synthesizeLambdaClasses(Builder<?> builder, ExecutorService executorService)
+      throws ExecutionException {
+    converter.optimizeSynthesizedClasses(
+        knownLambdaClasses.values().stream()
+            .map(LambdaClass::getLambdaClass).collect(ImmutableSet.toImmutableSet()),
+        executorService);
     for (LambdaClass lambdaClass : knownLambdaClasses.values()) {
       DexProgramClass synthesizedClass = lambdaClass.getLambdaClass();
-      converter.optimizeSynthesizedClass(synthesizedClass);
       builder.addSynthesizedClass(synthesizedClass, lambdaClass.addToMainDexList.get());
     }
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 4b55228..b9e8c3e 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -783,7 +783,8 @@
       // Identifies if the method preserves null check of the receiver after inlining.
       final Value receiver = code.getThis();
       feedback.markCheckNullReceiverBeforeAnySideEffect(method,
-          receiver.isUsed() && checksNullReceiverBeforeSideEffect(code, receiver));
+          receiver.isUsed()
+              && checksNullReceiverBeforeSideEffect(code, appInfo.dexItemFactory, receiver));
     }
   }
 
@@ -1096,6 +1097,7 @@
    */
   private enum InstructionEffect {
     DESIRED_EFFECT,
+    CONDITIONAL_EFFECT,
     OTHER_EFFECT,
     NO_EFFECT
   }
@@ -1106,14 +1108,48 @@
    *
    * Note: we do not track phis so we may return false negative. This is a conservative approach.
    */
-  private static boolean checksNullReceiverBeforeSideEffect(IRCode code, Value receiver) {
+  public static boolean checksNullReceiverBeforeSideEffect(
+      IRCode code, DexItemFactory factory, Value receiver) {
     return alwaysTriggerExpectedEffectBeforeAnythingElse(code, instr -> {
+      BasicBlock currentBlock = instr.getBlock();
+      // If the code explicitly checks the nullability of receiver, we should visit the next block
+      // that corresponds to the null receiver where NPE semantic could be preserved.
+      if (!currentBlock.hasCatchHandlers() && isNullabilityCheck(instr, receiver)) {
+        return InstructionEffect.CONDITIONAL_EFFECT;
+      }
+      // In general, new-instance can raise ClassNotFoundException or OutOfMemoryError, hence
+      // OTHER_EFFECT. However, if the code is creating an instance of NPE and throwing it in the
+      // same block, that's another way of preserving NPE, if the predecessor checks nullability of
+      // the receiver.
+      if (instr.isNewInstance()) {
+        if (!currentBlock.hasCatchHandlers()
+            && instr.asNewInstance().clazz.equals(factory.npeType)) {
+          boolean isThowingInTheSameBlock = false;
+          for (Instruction user : instr.outValue().uniqueUsers()) {
+            if (user.isThrow() && user.getBlock().equals(currentBlock)) {
+              isThowingInTheSameBlock = true;
+              break;
+            }
+          }
+          // We found a NPE throwing code.
+          if (isThowingInTheSameBlock) {
+            // Combined with the above CONDITIONAL_EFFECT, the code checks NPE on receiver.
+            for (BasicBlock predecessor : currentBlock.getPredecessors()) {
+              Instruction last =
+                  predecessor.listIterator(predecessor.getInstructions().size()).previous();
+              if (isNullabilityCheck(last, receiver)) {
+                return InstructionEffect.DESIRED_EFFECT;
+              }
+            }
+          }
+        }
+      }
       if (instr.throwsNpeIfValueIsNull(receiver)) {
         // In order to preserve NPE semantic, the exception must not be caught by any handler.
         // Therefore, we must ignore this instruction if it is covered by a catch handler.
         // Note: this is a conservative approach where we consider that any catch handler could
         // catch the exception, even if it cannot catch a NullPointerException.
-        if (!instr.getBlock().hasCatchHandlers()) {
+        if (!currentBlock.hasCatchHandlers()) {
           // We found a NPE check on receiver.
           return InstructionEffect.DESIRED_EFFECT;
         }
@@ -1125,6 +1161,12 @@
     });
   }
 
+  private static boolean isNullabilityCheck(Instruction instr, Value receiver) {
+    return instr.isIf() && instr.asIf().isZeroTest()
+        && instr.inValues().get(0).equals(receiver)
+        && (instr.asIf().getType() == Type.EQ || instr.asIf().getType() == Type.NE);
+  }
+
   private static boolean instructionHasSideEffects(Instruction instruction) {
     // We consider that an instruction has side effects if it can throw an exception. This is a
     // conservative approach which can be revised in the future.
@@ -1163,8 +1205,8 @@
    *
    * Note: we do not track phis so we may return false negative. This is a conservative approach.
    */
-  private static boolean alwaysTriggerExpectedEffectBeforeAnythingElse(IRCode code,
-      Function<Instruction, InstructionEffect> function) {
+  private static boolean alwaysTriggerExpectedEffectBeforeAnythingElse(
+      IRCode code, Function<Instruction, InstructionEffect> function) {
     final int color = code.reserveMarkingColor();
     try {
       ArrayDeque<BasicBlock> worklist = new ArrayDeque<>();
@@ -1188,6 +1230,17 @@
           // The current path is causing the expected effect. No need to go deeper in this path,
           // go to the next block in the work list.
           continue;
+        } else if (result == InstructionEffect.CONDITIONAL_EFFECT) {
+          assert !currentBlock.getNormalSuccessors().isEmpty();
+          Instruction lastInstruction = currentBlock.getInstructions().getLast();
+          assert lastInstruction.isIf();
+          // The current path is checking if the value of interest is null. Go deeper into the path
+          // that corresponds to the null value.
+          BasicBlock targetIfReceiverIsNull = lastInstruction.asIf().targetFromCondition(0);
+          if (!targetIfReceiverIsNull.isMarked(color)) {
+            worklist.add(targetIfReceiverIsNull);
+            targetIfReceiverIsNull.mark(color);
+          }
         } else {
           assert result == InstructionEffect.NO_EFFECT;
           // The block did not cause any particular effect.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
index ed92f64..0dacc69 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
@@ -66,7 +66,7 @@
 
   @Override
   public void finish() {
-    if (Log.ENABLED) {
+    if (Log.ENABLED && info != null) {
       Log.debug(getClass(), info.toString());
     }
   }
@@ -224,7 +224,7 @@
 
   private int computeInstructionLimit(InvokeMethod invoke, DexEncodedMethod candidate) {
     int instructionLimit = inliningInstructionLimit;
-    BitSet hints = candidate.getOptimizationInfo().getKotlinNotNullParamHints();
+    BitSet hints = candidate.getOptimizationInfo().getNonNullParamHints();
     if (hints != null) {
       List<Value> arguments = invoke.inValues();
       if (invoke.isInvokeMethodWithReceiver()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
index ba2e77f..68eb269 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
@@ -217,8 +217,8 @@
     this.strategyFactory = ApplyStrategy::new;
 
     // Add synthesized lambda group classes to the builder.
+    converter.optimizeSynthesizedClasses(lambdaGroupsClasses.values(), executorService);
     for (Entry<LambdaGroup, DexProgramClass> entry : lambdaGroupsClasses.entrySet()) {
-      converter.optimizeSynthesizedClass(entry.getValue());
       builder.addSynthesizedClass(entry.getValue(),
           entry.getKey().shouldAddToMainDex(converter.appInfo));
     }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/DupDupDupPeephole.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/DupDupDupPeephole.java
index 9b86873..af41976 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/DupDupDupPeephole.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/DupDupDupPeephole.java
@@ -8,8 +8,6 @@
 import com.android.tools.r8.ir.code.Dup2;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.StackValue;
-import com.android.tools.r8.ir.code.StackValues;
-import com.google.common.collect.ImmutableList;
 
 /**
  * Peephole that looks for the following pattern:
@@ -49,36 +47,28 @@
     Dup dupMiddle = dup2Exp.get(match).asDup();
     Dup dupBottom = dup1Exp.get(match).asDup();
 
-    StackValue src = (StackValue) dupTop.inValues().get(0);
-    StackValue srcMiddle = (StackValue) dupMiddle.inValues().get(0);
-    StackValue srcBottom = (StackValue) dupBottom.inValues().get(0);
-
-    StackValues tv = (StackValues) dupTop.outValue();
-    StackValues mv = (StackValues) dupMiddle.outValue();
-    StackValues bv = (StackValues) dupBottom.outValue();
-
     // The stack looks like:
-    // ..., tv0, mv0, bv0, bv1,.. -->
-    // because tv1 was used by dupMiddle and mv1 was used by dupBottom.
+    // ..., dupTop0, dupMiddle0, dupBottom0, dupBottom1,.. -->
+    // because dupTop1 was used by dupMiddle and dupMiddle1 was used by dupBottom.
 
-    StackValue tv0Dup2 = tv.getStackValues().get(0).duplicate(src.getHeight());
-    StackValue mv0Dup2 = mv.getStackValues().get(0).duplicate(src.getHeight() + 1);
-    StackValue bv0Dup2 = bv.getStackValues().get(0).duplicate(src.getHeight() + 2);
-    StackValue bv1Dup2 = bv.getStackValues().get(1).duplicate(src.getHeight() + 3);
+    int height = dupTop.src().getHeight();
+
+    StackValue tv0Dup2 = dupTop.outBottom().duplicate(height);
+    StackValue mv0Dup2 = dupMiddle.outBottom().duplicate(height + 1);
+    StackValue bv0Dup2 = dupBottom.outBottom().duplicate(height + 2);
+    StackValue bv1Dup2 = dupBottom.outTop().duplicate(height + 3);
 
     // Remove tv1 use.
-    srcMiddle.removeUser(dupMiddle);
+    dupMiddle.src().removeUser(dupMiddle);
     // Remove mv1 use.
-    srcBottom.removeUser(dupBottom);
+    dupBottom.src().removeUser(dupBottom);
     // Replace other uses.
-    tv.getStackValues().get(0).replaceUsers(tv0Dup2);
-    mv.getStackValues().get(0).replaceUsers(mv0Dup2);
-    bv.getStackValues().get(0).replaceUsers(bv0Dup2);
-    bv.getStackValues().get(1).replaceUsers(bv1Dup2);
+    dupTop.outBottom().replaceUsers(tv0Dup2);
+    dupMiddle.outBottom().replaceUsers(mv0Dup2);
+    dupBottom.outBottom().replaceUsers(bv0Dup2);
+    dupBottom.outTop().replaceUsers(bv1Dup2);
 
-    StackValues dest = new StackValues(ImmutableList.of(tv0Dup2, mv0Dup2, bv0Dup2, bv1Dup2));
-
-    Dup2 dup2 = new Dup2(dest, tv.getStackValues().get(0), tv.getStackValues().get(1));
+    Dup2 dup2 = new Dup2(tv0Dup2, mv0Dup2, bv0Dup2, bv1Dup2, dupTop.outBottom(), dupTop.outTop());
 
     it.removeOrReplaceByDebugLocalRead();
     it.previous();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java
index eff527c..0914ee3 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java
@@ -9,8 +9,6 @@
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.Load;
 import com.android.tools.r8.ir.code.StackValue;
-import com.android.tools.r8.ir.code.StackValues;
-import com.google.common.collect.ImmutableList;
 
 /**
  * {@link LoadLoadDupPeephole} looks for the following pattern:
@@ -59,12 +57,11 @@
     int height = src.getHeight();
     StackValue newFirstLoadOut = src.duplicate(height);
     StackValue newLastLoadOut = src.duplicate(height + 1);
-    StackValues dest = new StackValues(ImmutableList.of(newFirstLoadOut, newLastLoadOut));
 
     firstLoad.outValue().replaceUsers(newFirstLoadOut);
     lastLoad.outValue().replaceUsers(newLastLoadOut);
 
-    it.replaceCurrentInstruction(new Dup(dest, src));
+    it.replaceCurrentInstruction(new Dup(newFirstLoadOut, newLastLoadOut, src));
     return true;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
index 255e4bb..3747337 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
@@ -50,7 +50,7 @@
       return 1;
     }
     if (outValue instanceof StackValues) {
-      return ((StackValues) outValue).getStackValues().size();
+      return ((StackValues) outValue).getStackValues().length;
     }
     return 0;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/StoreSequenceLoadPeephole.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/StoreSequenceLoadPeephole.java
index c2aead8..b1514ac 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/StoreSequenceLoadPeephole.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/StoreSequenceLoadPeephole.java
@@ -11,7 +11,6 @@
 import com.android.tools.r8.ir.code.StackValues;
 import com.android.tools.r8.ir.code.Store;
 import com.android.tools.r8.ir.code.Swap;
-import com.google.common.collect.ImmutableList;
 import java.util.List;
 
 /**
@@ -99,8 +98,8 @@
     if (last.outValue() instanceof StackValue) {
       lastOut = (StackValue) last.outValue();
     } else if (last.outValue() instanceof StackValues) {
-      List<StackValue> stackValues = ((StackValues) last.outValue()).getStackValues();
-      lastOut = stackValues.get(stackValues.size() - 1);
+      StackValue[] stackValues = ((StackValues) last.outValue()).getStackValues();
+      lastOut = stackValues[stackValues.length - 1];
     }
 
     if (lastOut == null || lastOut.getTypeLattice().isWide()) {
@@ -115,19 +114,15 @@
 
     // Remove the first store.
     it.removeOrReplaceByDebugLocalRead();
-    Instruction current = it.next();
 
-    while (current != load) {
-      current = it.next();
-    }
+    it.nextUntil(i -> i == load);
 
     // Insert a swap instruction
     StackValue swapLastOut = lastOut.duplicate(source.getHeight());
     StackValue swapSource = source.duplicate(swapLastOut.getHeight() + 1);
-    StackValues dest = new StackValues(ImmutableList.of(swapLastOut, swapSource));
     source.replaceUsers(swapSource);
     lastOut.replaceUsers(swapLastOut);
-    it.replaceCurrentInstruction(new Swap(dest, source, lastOut));
+    it.replaceCurrentInstruction(new Swap(swapLastOut, swapSource, source, lastOut));
     PeepholeHelper.resetNext(it, 2);
     return true;
   }
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
index b3efe9d..aa89a3f 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.ir.analysis.type;
 
 import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.computeLeastUpperBoundOfInterfaces;
+import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.fromDexType;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
@@ -452,6 +453,18 @@
   }
 
   @Test
+  public void testSelfOrderWithoutSubtypingInfo() {
+    DexType type = appInfo.dexItemFactory.createType("Lmy/Type;");
+    TypeLatticeElement nonNullType = fromDexType(type, false, appInfo);
+    TypeLatticeElement nullableType = nonNullType.asNullable();
+    // TODO(zerny): Once the null lattice is used for null info check that the class-type null is
+    // also more specific that the nullableType.
+    assertTrue(strictlyLessThan(nonNullType, nullableType));
+    assertTrue(lessThanOrEqual(nonNullType, nullableType));
+    assertFalse(lessThanOrEqual(nullableType, nonNullType));
+  }
+
+  @Test
   public void testLeastUpperBoundOfInterfaces() {
     DexType collection = factory.createType("Ljava/util/Collection;");
     DexType set = factory.createType("Ljava/util/Set;");
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/NonNullParamTest.java b/src/test/java/com/android/tools/r8/ir/optimize/NonNullParamTest.java
index f7a4af6..d579b55 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/NonNullParamTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/NonNullParamTest.java
@@ -69,15 +69,15 @@
 
     MethodSubject selfCheck = mainSubject.method("void", "selfCheck", ImmutableList.of());
     assertThat(selfCheck, isPresent());
+    assertEquals(0, countCallToParamNullCheck(selfCheck));
     assertEquals(1, countPrintCall(selfCheck));
     assertEquals(0, countThrow(selfCheck));
 
     MethodSubject checkNull = mainSubject.method("void", "checkNull", ImmutableList.of());
     assertThat(checkNull, isPresent());
-    // TODO(b/117848700): these can be checked iff checkParameterIsNotNull is inlined even after
-    // the global inline threshold change.
-    //assertEquals(0, countPrintCall(checkNull));
-    //assertEquals(1, countThrow(checkNull));
+    assertEquals(1, countCallToParamNullCheck(checkNull));
+    assertEquals(1, countPrintCall(checkNull));
+    assertEquals(0, countThrow(checkNull));
 
     String mainName = mainClass.getCanonicalName();
     MethodSubject paramCheck =
@@ -114,6 +114,7 @@
     MethodSubject checkViaIntrinsic =
         mainSubject.method("void", "checkViaIntrinsic", ImmutableList.of(mainName));
     assertThat(checkViaIntrinsic, isPresent());
+    assertEquals(0, countCallToParamNullCheck(checkViaIntrinsic));
     // TODO(b/71500340): can be checked iff non-param info is propagated.
     //assertEquals(1, countPrintCall(checkViaIntrinsic));
 
@@ -124,12 +125,20 @@
     //assertEquals(1, countPrintCall(checkAtOneLevelHigher));
   }
 
+  private long countCallToParamNullCheck(MethodSubject method) {
+    return countCall(method, IntrinsicsDeputy.class.getSimpleName(), "checkParameterIsNotNull");
+  }
+
   private long countPrintCall(MethodSubject method) {
+    return countCall(method, "PrintStream", "print");
+  }
+
+  private long countCall(MethodSubject method, String className, String methodName) {
     return Streams.stream(method.iterateInstructions(instructionSubject -> {
       if (instructionSubject.isInvoke()) {
         DexMethod invokedMethod = instructionSubject.getMethod();
-        return invokedMethod.getHolder().toString().contains("PrintStream")
-            && invokedMethod.name.toString().contains("print");
+        return invokedMethod.getHolder().toString().contains(className)
+            && invokedMethod.name.toString().contains(methodName);
       }
       return false;
     })).count();