diff --git a/src/main/java/com/android/tools/r8/graph/AccessFlags.java b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
index 68921ca..cdf0ad1 100644
--- a/src/main/java/com/android/tools/r8/graph/AccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
@@ -230,8 +230,9 @@
     promote(Constants.ACC_FINAL);
   }
 
-  public void demoteFromFinal() {
+  public T demoteFromFinal() {
     demote(Constants.ACC_FINAL);
+    return self();
   }
 
   public boolean isPromotedToPublic() {
diff --git a/src/main/java/com/android/tools/r8/graph/DexTypeList.java b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
index f399895..f07c38e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexTypeList.java
+++ b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
@@ -64,7 +64,7 @@
   }
 
   public DexTypeList keepIf(Predicate<DexType> predicate) {
-    DexType[] filtered = ArrayUtils.filter(DexType[].class, values, predicate);
+    DexType[] filtered = ArrayUtils.filter(values, predicate, DexType.EMPTY_ARRAY);
     if (filtered != values) {
       return DexTypeList.create(filtered);
     }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java b/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
index 6930912..545645e 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
@@ -13,6 +13,7 @@
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.List;
+import java.util.Objects;
 import java.util.Set;
 import java.util.function.Consumer;
 import java.util.function.Function;
@@ -337,33 +338,75 @@
 
   @Override
   public void replaceMethods(Function<DexEncodedMethod, DexEncodedMethod> replacement) {
-    replaceDirectMethods(replacement);
-    replaceVirtualMethods(replacement);
+    List<DexEncodedMethod> newVirtualMethods = internalReplaceDirectMethods(replacement);
+    List<DexEncodedMethod> newDirectMethods = internalReplaceVirtualMethods(replacement);
+    addDirectMethods(newDirectMethods);
+    addVirtualMethods(newVirtualMethods);
   }
 
   @Override
   public void replaceDirectMethods(Function<DexEncodedMethod, DexEncodedMethod> replacement) {
+    List<DexEncodedMethod> newVirtualMethods = internalReplaceDirectMethods(replacement);
+    addVirtualMethods(newVirtualMethods);
+  }
+
+  private List<DexEncodedMethod> internalReplaceDirectMethods(
+      Function<DexEncodedMethod, DexEncodedMethod> replacement) {
+    List<DexEncodedMethod> newVirtualMethods = new ArrayList<>();
     for (int i = 0; i < directMethods.length; i++) {
       DexEncodedMethod method = directMethods[i];
       DexEncodedMethod newMethod = replacement.apply(method);
       assert newMethod != null;
       if (method != newMethod) {
-        assert belongsToDirectPool(newMethod);
-        directMethods[i] = newMethod;
+        if (belongsToDirectPool(newMethod)) {
+          directMethods[i] = newMethod;
+        } else {
+          directMethods[i] = null;
+          newVirtualMethods.add(newMethod);
+        }
       }
     }
+    if (!newVirtualMethods.isEmpty()) {
+      directMethods =
+          ArrayUtils.filter(
+              directMethods,
+              Objects::nonNull,
+              DexEncodedMethod.EMPTY_ARRAY,
+              directMethods.length - newVirtualMethods.size());
+    }
+    return newVirtualMethods;
   }
 
   @Override
   public void replaceVirtualMethods(Function<DexEncodedMethod, DexEncodedMethod> replacement) {
+    List<DexEncodedMethod> newDirectMethods = internalReplaceVirtualMethods(replacement);
+    addDirectMethods(newDirectMethods);
+  }
+
+  private List<DexEncodedMethod> internalReplaceVirtualMethods(
+      Function<DexEncodedMethod, DexEncodedMethod> replacement) {
+    List<DexEncodedMethod> newDirectMethods = new ArrayList<>();
     for (int i = 0; i < virtualMethods.length; i++) {
       DexEncodedMethod method = virtualMethods[i];
       DexEncodedMethod newMethod = replacement.apply(method);
       if (method != newMethod) {
-        assert belongsToVirtualPool(newMethod);
-        virtualMethods[i] = newMethod;
+        if (belongsToVirtualPool(newMethod)) {
+          virtualMethods[i] = newMethod;
+        } else {
+          virtualMethods[i] = null;
+          newDirectMethods.add(newMethod);
+        }
       }
     }
+    if (!newDirectMethods.isEmpty()) {
+      virtualMethods =
+          ArrayUtils.filter(
+              virtualMethods,
+              Objects::nonNull,
+              DexEncodedMethod.EMPTY_ARRAY,
+              virtualMethods.length - newDirectMethods.size());
+    }
+    return newDirectMethods;
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/graph/RewrittenPrototypeDescription.java b/src/main/java/com/android/tools/r8/graph/RewrittenPrototypeDescription.java
index dda7746..bf3849c 100644
--- a/src/main/java/com/android/tools/r8/graph/RewrittenPrototypeDescription.java
+++ b/src/main/java/com/android/tools/r8/graph/RewrittenPrototypeDescription.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.ir.conversion.ExtraUnusedNullParameter;
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfoFixer;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.ConsumerUtils;
 import com.android.tools.r8.utils.IntObjConsumer;
 import com.android.tools.r8.utils.IteratorUtils;
@@ -450,6 +451,11 @@
       return removed;
     }
 
+    public int numberOfRemovedNonReceiverArguments(DexEncodedMethod method) {
+      return numberOfRemovedArguments()
+          - BooleanUtils.intValue(method.isInstance() && isArgumentRemoved(0));
+    }
+
     public boolean hasArgumentInfo(int argumentIndex) {
       return argumentInfos.containsKey(argumentIndex);
     }
@@ -542,14 +548,12 @@
     }
 
     public DexType[] rewriteParameters(DexEncodedMethod encodedMethod) {
-      // Currently not allowed to remove the receiver of an instance method. This would involve
-      // changing invoke-direct/invoke-virtual into invoke-static.
-      assert encodedMethod.isStatic() || !getArgumentInfo(0).isRemovedArgumentInfo();
-      DexType[] params = encodedMethod.getReference().proto.parameters.values;
+      DexType[] params = encodedMethod.getParameters().values;
       if (isEmpty()) {
         return params;
       }
-      DexType[] newParams = new DexType[params.length - numberOfRemovedArguments()];
+      DexType[] newParams =
+          new DexType[params.length - numberOfRemovedNonReceiverArguments(encodedMethod)];
       int offset = encodedMethod.getFirstNonReceiverArgumentIndex();
       int newParamIndex = 0;
       for (int oldParamIndex = 0; oldParamIndex < params.length; oldParamIndex++) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
index 62cbb04..2ad1f65 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
@@ -275,6 +275,40 @@
   }
 
   @Override
+  public InvokeMethod insertNullCheckInstruction(
+      AppView<?> appView,
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Value value,
+      Position position) {
+    InternalOptions options = appView.options();
+
+    InvokeMethod invoke;
+    if (appView.options().canUseJavaUtilObjectsRequireNonNull()) {
+      DexMethod requireNonNullMethod = appView.dexItemFactory().objectsMethods.requireNonNull;
+      invoke =
+          InvokeStatic.builder()
+              .setMethod(requireNonNullMethod)
+              .setSingleArgument(value)
+              .setPosition(position)
+              .build();
+    } else {
+      DexMethod getClassMethod = appView.dexItemFactory().objectMembers.getClass;
+      invoke =
+          InvokeVirtual.builder()
+              .setMethod(getClassMethod)
+              .setSingleArgument(value)
+              .setPosition(position)
+              .build();
+    }
+    add(invoke);
+    if (block.hasCatchHandlers()) {
+      splitCopyCatchHandlers(code, blockIterator, options);
+    }
+    return invoke;
+  }
+
+  @Override
   public boolean replaceCurrentInstructionByNullCheckIfPossible(
       AppView<?> appView, ProgramMethod context) {
     Instruction toBeReplaced = current;
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
index f9bbcc8..a68da1a 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCodeInstructionListIterator.java
@@ -45,6 +45,17 @@
   }
 
   @Override
+  public InvokeMethod insertNullCheckInstruction(
+      AppView<?> appView,
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Value value,
+      Position position) {
+    return instructionIterator.insertNullCheckInstruction(
+        appView, code, blockIterator, value, position);
+  }
+
+  @Override
   public boolean replaceCurrentInstructionByNullCheckIfPossible(
       AppView<?> appView, ProgramMethod context) {
     return instructionIterator.replaceCurrentInstructionByNullCheckIfPossible(appView, context);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
index d08413d..bc6bec6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
@@ -100,6 +100,13 @@
 
   Value insertConstStringInstruction(AppView<?> appView, IRCode code, DexString value);
 
+  InvokeMethod insertNullCheckInstruction(
+      AppView<?> appView,
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Value value,
+      Position position);
+
   boolean replaceCurrentInstructionByNullCheckIfPossible(AppView<?> appView, ProgramMethod context);
 
   boolean replaceCurrentInstructionByInitClassIfPossible(
diff --git a/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
index cb20fd4..37d45df 100644
--- a/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/LinearFlowInstructionListIterator.java
@@ -69,6 +69,17 @@
   }
 
   @Override
+  public InvokeMethod insertNullCheckInstruction(
+      AppView<?> appView,
+      IRCode code,
+      BasicBlockIterator blockIterator,
+      Value value,
+      Position position) {
+    return currentBlockIterator.insertNullCheckInstruction(
+        appView, code, blockIterator, value, position);
+  }
+
+  @Override
   public boolean replaceCurrentInstructionByNullCheckIfPossible(
       AppView<?> appView, ProgramMethod context) {
     return currentBlockIterator.replaceCurrentInstructionByNullCheckIfPossible(appView, context);
diff --git a/src/main/java/com/android/tools/r8/utils/ArrayUtils.java b/src/main/java/com/android/tools/r8/utils/ArrayUtils.java
index 06fdc4c..13f630e 100644
--- a/src/main/java/com/android/tools/r8/utils/ArrayUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ArrayUtils.java
@@ -47,39 +47,6 @@
     return results;
   }
 
-  /**
-   * Filters the input array based on the given predicate.
-   *
-   * @param clazz target type's Class to cast
-   * @param original an array of original elements
-   * @param filter a predicate that tells us what to keep
-   * @param <T> target type
-   * @return a partial copy of the original array
-   */
-  public static <T> T[] filter(Class<T[]> clazz, T[] original, Predicate<T> filter) {
-    ArrayList<T> filtered = null;
-    for (int i = 0; i < original.length; i++) {
-      T elt = original[i];
-      if (filter.test(elt)) {
-        if (filtered != null) {
-          filtered.add(elt);
-        }
-      } else {
-        if (filtered == null) {
-          filtered = new ArrayList<>(original.length);
-          for (int j = 0; j < i; j++) {
-            filtered.add(original[j]);
-          }
-        }
-      }
-    }
-    if (filtered == null) {
-      return original;
-    }
-    return filtered.toArray(
-        clazz.cast(Array.newInstance(clazz.getComponentType(), filtered.size())));
-  }
-
   public static <T> boolean isEmpty(T[] array) {
     return array.length == 0;
   }
@@ -131,8 +98,23 @@
     return results != null ? results.toArray(emptyArray) : original;
   }
 
-  public static <T> T[] filter(T[] original, Predicate<T> test, T[] emptyArray) {
-    return map(original, e -> test.test(e) ? e : null, emptyArray);
+  public static <T> T[] filter(T[] original, Predicate<T> predicate, T[] emptyArray) {
+    return map(original, e -> predicate.test(e) ? e : null, emptyArray);
+  }
+
+  @SuppressWarnings("unchecked")
+  public static <T> T[] filter(T[] original, Predicate<T> predicate, T[] emptyArray, int newSize) {
+    T[] result = (T[]) Array.newInstance(emptyArray.getClass().getComponentType(), newSize);
+    int newIndex = 0;
+    for (int originalIndex = 0; originalIndex < original.length; originalIndex++) {
+      T element = original[originalIndex];
+      if (predicate.test(element)) {
+        result[newIndex] = element;
+        newIndex++;
+      }
+    }
+    assert newIndex == newSize;
+    return result;
   }
 
   public static int[] createIdentityArray(int size) {
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
index f3db67c..b05928d 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
@@ -19,10 +19,13 @@
 import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.BasicBlockIterator;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.Move;
+import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -65,6 +68,16 @@
     }
 
     @Override
+    public InvokeMethod insertNullCheckInstruction(
+        AppView<?> appView,
+        IRCode code,
+        BasicBlockIterator blockIterator,
+        Value value,
+        Position position) {
+      throw new Unimplemented();
+    }
+
+    @Override
     public boolean replaceCurrentInstructionByNullCheckIfPossible(
         AppView<?> appView, ProgramMethod context) {
       throw new Unimplemented();
diff --git a/src/test/java/com/android/tools/r8/utils/ArrayUtilsTest.java b/src/test/java/com/android/tools/r8/utils/ArrayUtilsTest.java
index b97fd41..93cc98f 100644
--- a/src/test/java/com/android/tools/r8/utils/ArrayUtilsTest.java
+++ b/src/test/java/com/android/tools/r8/utils/ArrayUtilsTest.java
@@ -113,7 +113,7 @@
   public void testFilter_identity() {
     int size = 3;
     Integer[] input = createInputData(size);
-    Integer[] output = ArrayUtils.filter(Integer[].class, input, x -> true);
+    Integer[] output = ArrayUtils.filter(input, x -> true, new Integer[0]);
     assertEquals(input, output);
   }
 
@@ -121,7 +121,7 @@
   public void testFilter_dropOdd() {
     int size = 3;
     Integer[] input = createInputData(size);
-    Integer[] output = ArrayUtils.filter(Integer[].class, input, x -> x % 2 == 0);
+    Integer[] output = ArrayUtils.filter(input, x -> x % 2 == 0, new Integer[0]);
     assertNotEquals(input, output);
     assertEquals(2, output.length);
     assertEquals(0, (int) output[0]);
@@ -132,7 +132,7 @@
   public void testFilter_dropAll() {
     int size = 3;
     Integer[] input = createInputData(size);
-    Integer[] output = ArrayUtils.filter(Integer[].class, input, x -> false);
+    Integer[] output = ArrayUtils.filter(input, x -> false, new Integer[0]);
     assertNotEquals(input, output);
     assertEquals(0, output.length);
   }