diff --git a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
index fa105e6..6731b5e 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
@@ -211,6 +211,10 @@
     return TraversalContinuation.CONTINUE;
   }
 
+  public Set<DexType> getInstantiatedLambdaInterfaces() {
+    return instantiatedLambdas.keySet();
+  }
+
   public static class Builder extends ObjectAllocationInfoCollectionImpl {
 
     private static class Data {
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
index f290cf1..a8482bb 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
@@ -59,7 +59,7 @@
       // Update the block exit state, and re-enqueue all successor blocks if the abstract state
       // changed.
       if (setBlockExitState(block, state)) {
-        worklist.addAll(block.getSuccessors());
+        worklist.addAllIgnoringSeenSet(block.getSuccessors());
       }
     }
     return new SuccessfulDataflowAnalysisResult();
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 8db8c01..100131c 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
@@ -1132,13 +1132,9 @@
       return false;
     }
     boolean didDesugar = false;
-    Supplier<AppInfoWithClassHierarchy> lazyAppInfo =
-        Suppliers.memoize(() -> appView.appInfoForDesugaring());
     if (lambdaRewriter != null) {
-      didDesugar |= lambdaRewriter.desugarLambdas(method, lazyAppInfo.get()) > 0;
-    }
-    if (backportedMethodRewriter != null) {
-      didDesugar |= backportedMethodRewriter.desugar(method, lazyAppInfo.get());
+      AppInfoWithClassHierarchy appInfo = appView.appInfoForDesugaring();
+      didDesugar |= lambdaRewriter.desugarLambdas(method, appInfo) > 0;
     }
     return didDesugar;
   }
@@ -1424,6 +1420,12 @@
       timing.end();
     }
 
+    if (backportedMethodRewriter != null) {
+      timing.begin("Rewrite backport methods");
+      backportedMethodRewriter.desugar(code);
+      timing.end();
+    }
+
     timing.begin("Desugar string concat");
     stringConcatRewriter.desugarStringConcats(method.method, code);
     timing.end();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
index 1f41aa4..da1a799 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
@@ -4,25 +4,27 @@
 
 package com.android.tools.r8.ir.desugar;
 
-import com.android.tools.r8.cf.code.CfInstruction;
-import com.android.tools.r8.cf.code.CfInvoke;
+
 import com.android.tools.r8.dex.ApplicationReader;
 import com.android.tools.r8.dex.Constants;
-import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
-import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.CfCode;
 import com.android.tools.r8.graph.Code;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
+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.InvokeStatic;
+import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.desugar.backports.BackportedMethods;
 import com.android.tools.r8.ir.desugar.backports.BooleanMethodRewrites;
@@ -38,19 +40,19 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.InternalOptions.DesugarState;
 import com.android.tools.r8.utils.Timing;
+import com.google.common.collect.Sets;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.IdentityHashMap;
 import java.util.List;
-import java.util.ListIterator;
 import java.util.Map;
 import java.util.Queue;
+import java.util.Set;
 import java.util.concurrent.ConcurrentLinkedQueue;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.function.Consumer;
-import org.objectweb.asm.Opcodes;
 
 public final class BackportedMethodRewriter {
 
@@ -109,34 +111,29 @@
     BackportedMethods.registerSynthesizedCodeReferences(options.itemFactory);
   }
 
-  public boolean desugar(ProgramMethod method, AppInfoWithClassHierarchy appInfo) {
+  public void desugar(IRCode code) {
     if (!enabled) {
-      return false;
+      return; // Nothing to do!
     }
-    CfCode code = method.getDefinition().getCode().asCfCode();
-    ListIterator<CfInstruction> iterator = code.getInstructions().listIterator();
-    boolean replaced = false;
+    Set<Value> affectedValues = Sets.newIdentityHashSet();
+    InstructionListIterator iterator = code.instructionListIterator();
     while (iterator.hasNext()) {
-      CfInvoke invoke = iterator.next().asInvoke();
-      if (invoke == null) {
+      Instruction instruction = iterator.next();
+      if (!instruction.isInvokeMethod()) {
         continue;
       }
-      DexMethod invokedMethod = invoke.getMethod();
+
+      InvokeMethod invoke = instruction.asInvokeMethod();
+      DexMethod invokedMethod = invoke.getInvokedMethod();
       MethodProvider provider = getMethodProviderOrNull(invokedMethod);
       if (provider != null) {
-        if (!replaced) {
-          // Create mutable instructions on first write.
-          ArrayList<CfInstruction> mutableInstructions = new ArrayList<>(code.getInstructions());
-          code.setInstructions(mutableInstructions);
-          iterator = mutableInstructions.listIterator(iterator.previousIndex());
-          iterator.next();
-        }
         provider.rewriteInvoke(
-            invoke, iterator, method.getHolder(), appInfo, synthesizedMethods::add);
-        replaced = true;
+            invoke, iterator, code, appView, affectedValues, synthesizedMethods::add);
       }
     }
-    return replaced;
+    if (!affectedValues.isEmpty()) {
+      new TypeAnalysis(appView).narrowing(affectedValues);
+    }
   }
 
   public void processSynthesizedClasses(IRConverter converter, ExecutorService executor)
@@ -251,7 +248,7 @@
       name = factory.createString("compare");
       proto = factory.createProto(factory.intType, factory.longType, factory.longType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, LongMethodRewrites.rewriteCompare()));
+      addProvider(new InvokeRewriter(method, LongMethodRewrites::rewriteCompare));
 
       // Boolean
       type = factory.boxedBooleanType;
@@ -296,7 +293,7 @@
       name = factory.createString("hash");
       proto = factory.createProto(factory.intType, factory.objectArrayType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, ObjectsMethodRewrites.rewriteToArraysHashCode()));
+      addProvider(new InvokeRewriter(method, ObjectsMethodRewrites::rewriteToArraysHashCode));
 
       // int Objects.hashCode(Object o)
       name = factory.createString("hashCode");
@@ -306,7 +303,7 @@
 
       // T Objects.requireNonNull(T obj)
       method = factory.objectsMethods.requireNonNull;
-      addProvider(new InvokeRewriter(method, ObjectsMethodRewrites.rewriteRequireNonNull()));
+      addProvider(new InvokeRewriter(method, ObjectsMethodRewrites::rewriteRequireNonNull));
 
       // T Objects.requireNonNull(T obj, String message)
       name = factory.createString("requireNonNull");
@@ -363,7 +360,7 @@
       DexString name = factory.createString("hashCode");
       DexProto proto = factory.createProto(factory.intType, factory.byteType);
       DexMethod method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteAsIdentity()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteAsIdentity));
 
       // Short
       type = factory.boxedShortType;
@@ -371,7 +368,7 @@
       name = factory.createString("hashCode");
       proto = factory.createProto(factory.intType, factory.shortType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteAsIdentity()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteAsIdentity));
 
       // Integer
       type = factory.boxedIntType;
@@ -380,25 +377,25 @@
       name = factory.createString("hashCode");
       proto = factory.createProto(factory.intType, factory.intType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteAsIdentity()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteAsIdentity));
 
       // int Integer.max(int a, int b)
       name = factory.createString("max");
       proto = factory.createProto(factory.intType, factory.intType, factory.intType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // int Integer.min(int a, int b)
       name = factory.createString("min");
       proto = factory.createProto(factory.intType, factory.intType, factory.intType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // int Integer.sum(int a, int b)
       name = factory.createString("sum");
       proto = factory.createProto(factory.intType, factory.intType, factory.intType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToAddInstruction()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToAddInstruction));
 
       // Double
       type = factory.boxedDoubleType;
@@ -413,19 +410,19 @@
       name = factory.createString("max");
       proto = factory.createProto(factory.doubleType, factory.doubleType, factory.doubleType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // double Double.min(double a, double b)
       name = factory.createString("min");
       proto = factory.createProto(factory.doubleType, factory.doubleType, factory.doubleType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // double Double.sum(double a, double b)
       name = factory.createString("sum");
       proto = factory.createProto(factory.doubleType, factory.doubleType, factory.doubleType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToAddInstruction()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToAddInstruction));
 
       // boolean Double.isFinite(double a)
       name = factory.createString("isFinite");
@@ -440,25 +437,25 @@
       name = factory.createString("hashCode");
       proto = factory.createProto(factory.intType, factory.floatType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, FloatMethodRewrites.rewriteHashCode()));
+      addProvider(new InvokeRewriter(method, FloatMethodRewrites::rewriteHashCode));
 
       // float Float.max(float a, float b)
       name = factory.createString("max");
       proto = factory.createProto(factory.floatType, factory.floatType, factory.floatType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // float Float.min(float a, float b)
       name = factory.createString("min");
       proto = factory.createProto(factory.floatType, factory.floatType, factory.floatType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // float Float.sum(float a, float b)
       name = factory.createString("sum");
       proto = factory.createProto(factory.floatType, factory.floatType, factory.floatType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToAddInstruction()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToAddInstruction));
 
       // boolean Float.isFinite(float a)
       name = factory.createString("isFinite");
@@ -479,19 +476,19 @@
       name = factory.createString("logicalAnd");
       proto = factory.createProto(factory.booleanType, factory.booleanType, factory.booleanType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, BooleanMethodRewrites.rewriteLogicalAnd()));
+      addProvider(new InvokeRewriter(method, BooleanMethodRewrites::rewriteLogicalAnd));
 
       // boolean Boolean.logicalOr(boolean a, boolean b)
       name = factory.createString("logicalOr");
       proto = factory.createProto(factory.booleanType, factory.booleanType, factory.booleanType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, BooleanMethodRewrites.rewriteLogicalOr()));
+      addProvider(new InvokeRewriter(method, BooleanMethodRewrites::rewriteLogicalOr));
 
       // boolean Boolean.logicalXor(boolean a, boolean b)
       name = factory.createString("logicalXor");
       proto = factory.createProto(factory.booleanType, factory.booleanType, factory.booleanType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, BooleanMethodRewrites.rewriteLogicalXor()));
+      addProvider(new InvokeRewriter(method, BooleanMethodRewrites::rewriteLogicalXor));
 
       // Long
       type = factory.boxedLongType;
@@ -506,19 +503,19 @@
       name = factory.createString("max");
       proto = factory.createProto(factory.longType, factory.longType, factory.longType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // long Long.min(long a, long b)
       name = factory.createString("min");
       proto = factory.createProto(factory.longType, factory.longType, factory.longType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToInvokeMath()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToInvokeMath));
 
       // long Long.sum(long a, long b)
       name = factory.createString("sum");
       proto = factory.createProto(factory.longType, factory.longType, factory.longType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteToAddInstruction()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteToAddInstruction));
 
       // Character
       type = factory.boxedCharType;
@@ -527,7 +524,7 @@
       name = factory.createString("hashCode");
       proto = factory.createProto(factory.intType, factory.charType);
       method = factory.createMethod(type, proto, name);
-      addProvider(new InvokeRewriter(method, NumericMethodRewrites.rewriteAsIdentity()));
+      addProvider(new InvokeRewriter(method, NumericMethodRewrites::rewriteAsIdentity));
 
       // Objects
       type = factory.objectsType;
@@ -919,7 +916,7 @@
         method = factory.createMethod(type, proto, name);
         addProvider(
             i == 0
-                ? new InvokeRewriter(method, CollectionMethodRewrites.rewriteListOfEmpty())
+                ? new InvokeRewriter(method, CollectionMethodRewrites::rewriteListOfEmpty)
                 : new MethodGenerator(
                     method,
                     (options, methodArg) ->
@@ -940,7 +937,7 @@
         method = factory.createMethod(type, proto, name);
         addProvider(
             i == 0
-                ? new InvokeRewriter(method, CollectionMethodRewrites.rewriteSetOfEmpty())
+                ? new InvokeRewriter(method, CollectionMethodRewrites::rewriteSetOfEmpty)
                 : new MethodGenerator(
                     method,
                     (options, methodArg) ->
@@ -960,7 +957,7 @@
         method = factory.createMethod(type, proto, name);
         addProvider(
             i == 0
-                ? new InvokeRewriter(method, CollectionMethodRewrites.rewriteMapOfEmpty())
+                ? new InvokeRewriter(method, CollectionMethodRewrites::rewriteMapOfEmpty)
                 : new MethodGenerator(
                     method,
                     (options, methodArg) ->
@@ -1227,10 +1224,10 @@
           };
       MethodInvokeRewriter[] rewriters =
           new MethodInvokeRewriter[] {
-            OptionalMethodRewrites.rewriteOrElseGet(),
-            OptionalMethodRewrites.rewriteDoubleOrElseGet(),
-            OptionalMethodRewrites.rewriteLongOrElseGet(),
-            OptionalMethodRewrites.rewriteIntOrElseGet(),
+            OptionalMethodRewrites::rewriteOrElseGet,
+            OptionalMethodRewrites::rewriteDoubleOrElseGet,
+            OptionalMethodRewrites::rewriteLongOrElseGet,
+            OptionalMethodRewrites::rewriteIntOrElseGet,
           };
       DexString name = factory.createString("orElseThrow");
       for (int i = 0; i < optionalTypes.length; i++) {
@@ -1297,10 +1294,11 @@
     }
 
     public abstract void rewriteInvoke(
-        CfInvoke invoke,
-        ListIterator<CfInstruction> iterator,
-        DexProgramClass context,
-        AppInfoWithClassHierarchy appInfo,
+        InvokeMethod invoke,
+        InstructionListIterator iterator,
+        IRCode code,
+        AppView<?> appView,
+        Set<Value> affectedValues,
         Consumer<ProgramMethod> registerSynthesizedMethod);
   }
 
@@ -1315,12 +1313,14 @@
 
     @Override
     public void rewriteInvoke(
-        CfInvoke invoke,
-        ListIterator<CfInstruction> iterator,
-        DexProgramClass context,
-        AppInfoWithClassHierarchy appInfo,
+        InvokeMethod invoke,
+        InstructionListIterator iterator,
+        IRCode code,
+        AppView<?> appView,
+        Set<Value> affectedValues,
         Consumer<ProgramMethod> registerSynthesizedMethod) {
-      rewriter.rewrite(invoke, iterator, appInfo.dexItemFactory());
+      rewriter.rewrite(invoke, iterator, appView.dexItemFactory(), affectedValues);
+      assert code.isConsistentSSA();
     }
   }
 
@@ -1341,33 +1341,34 @@
 
     @Override
     public void rewriteInvoke(
-        CfInvoke invoke,
-        ListIterator<CfInstruction> iterator,
-        DexProgramClass context,
-        AppInfoWithClassHierarchy appInfo,
+        InvokeMethod invoke,
+        InstructionListIterator iterator,
+        IRCode code,
+        AppView<?> appView,
+        Set<Value> affectedValues,
         Consumer<ProgramMethod> registerSynthesizedMethod) {
-      ProgramMethod method = getSyntheticMethod(context, appInfo);
-      registerSynthesizedMethod.accept(method);
-      iterator.remove();
-      iterator.add(new CfInvoke(Opcodes.INVOKESTATIC, method.getReference(), false));
-    }
+      ProgramMethod method =
+          appView
+              .getSyntheticItems()
+              .createMethod(
+                  code.context().getHolder(),
+                  appView.dexItemFactory(),
+                  builder ->
+                      builder
+                          .setProto(getProto(appView.dexItemFactory()))
+                          .setAccessFlags(
+                              MethodAccessFlags.fromSharedAccessFlags(
+                                  Constants.ACC_PUBLIC
+                                      | Constants.ACC_STATIC
+                                      | Constants.ACC_SYNTHETIC,
+                                  false))
+                          .setCode(
+                              methodSig -> generateTemplateMethod(appView.options(), methodSig)));
 
-    private ProgramMethod getSyntheticMethod(
-        DexProgramClass context, AppInfoWithClassHierarchy appInfo) {
-      return appInfo
-          .getSyntheticItems()
-          .createMethod(
-              context,
-              appInfo.dexItemFactory(),
-              builder ->
-                  builder
-                      .setProto(getProto(appInfo.dexItemFactory()))
-                      .setAccessFlags(
-                          MethodAccessFlags.fromSharedAccessFlags(
-                              Constants.ACC_PUBLIC | Constants.ACC_STATIC | Constants.ACC_SYNTHETIC,
-                              false))
-                      .setCode(
-                          methodSig -> generateTemplateMethod(appInfo.app().options, methodSig)));
+      iterator.replaceCurrentInstruction(
+          new InvokeStatic(method.getReference(), invoke.outValue(), invoke.inValues()));
+
+      registerSynthesizedMethod.accept(method);
     }
 
     public DexProto getProto(DexItemFactory itemFactory) {
@@ -1399,30 +1400,16 @@
   }
 
   private interface TemplateMethodFactory {
+
     Code create(InternalOptions options, DexMethod method);
   }
 
-  public interface MethodInvokeRewriter {
+  private interface MethodInvokeRewriter {
 
-    CfInstruction rewriteSingle(CfInvoke invoke, DexItemFactory factory);
-
-    // Convenience wrapper since most rewrites are to a single instruction.
-    default void rewrite(
-        CfInvoke invoke, ListIterator<CfInstruction> iterator, DexItemFactory factory) {
-      iterator.remove();
-      iterator.add(rewriteSingle(invoke, factory));
-    }
-  }
-
-  public abstract static class FullMethodInvokeRewriter implements MethodInvokeRewriter {
-
-    @Override
-    public final CfInstruction rewriteSingle(CfInvoke invoke, DexItemFactory factory) {
-      throw new Unreachable();
-    }
-
-    @Override
-    public abstract void rewrite(
-        CfInvoke invoke, ListIterator<CfInstruction> iterator, DexItemFactory factory);
+    void rewrite(
+        InvokeMethod invoke,
+        InstructionListIterator iterator,
+        DexItemFactory factory,
+        Set<Value> affectedValues);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/BooleanMethodRewrites.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/BooleanMethodRewrites.java
index ec0a554..90654b2 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/BooleanMethodRewrites.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/BooleanMethodRewrites.java
@@ -4,27 +4,52 @@
 
 package com.android.tools.r8.ir.desugar.backports;
 
-import com.android.tools.r8.cf.code.CfLogicalBinop;
-import com.android.tools.r8.cf.code.CfLogicalBinop.Opcode;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.ir.code.And;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.NumericType;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.MethodInvokeRewriter;
+import com.android.tools.r8.ir.code.Or;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.code.Xor;
+import java.util.List;
+import java.util.Set;
 
 public final class BooleanMethodRewrites {
+  public static void rewriteLogicalAnd(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    List<Value> inValues = invoke.inValues();
+    assert inValues.size() == 2;
 
-  private static MethodInvokeRewriter createRewriter(CfLogicalBinop.Opcode op) {
-    return (invoke, factory) -> new CfLogicalBinop(op, NumericType.INT);
+    iterator.replaceCurrentInstruction(
+        new And(NumericType.INT, invoke.outValue(), inValues.get(0), inValues.get(1)));
   }
 
-  public static MethodInvokeRewriter rewriteLogicalAnd() {
-    return createRewriter(Opcode.And);
+  public static void rewriteLogicalOr(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    List<Value> inValues = invoke.inValues();
+    assert inValues.size() == 2;
+
+    iterator.replaceCurrentInstruction(
+        new Or(NumericType.INT, invoke.outValue(), inValues.get(0), inValues.get(1)));
   }
 
-  public static MethodInvokeRewriter rewriteLogicalOr() {
-    return createRewriter(Opcode.Or);
-  }
+  public static void rewriteLogicalXor(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    List<Value> inValues = invoke.inValues();
+    assert inValues.size() == 2;
 
-  public static MethodInvokeRewriter rewriteLogicalXor() {
-    return createRewriter(Opcode.Xor);
+    iterator.replaceCurrentInstruction(
+        new Xor(NumericType.INT, invoke.outValue(), inValues.get(0), inValues.get(1)));
   }
 
   private BooleanMethodRewrites() {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodRewrites.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodRewrites.java
index 64c94c5..354040f 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodRewrites.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodRewrites.java
@@ -4,31 +4,54 @@
 
 package com.android.tools.r8.ir.desugar.backports;
 
-import com.android.tools.r8.cf.code.CfInvoke;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.MethodInvokeRewriter;
-import org.objectweb.asm.Opcodes;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.Value;
+import java.util.Collections;
+import java.util.Set;
 
 public final class CollectionMethodRewrites {
 
   private CollectionMethodRewrites() {}
 
-  public static MethodInvokeRewriter rewriteListOfEmpty() {
-    return rewriteToCollectionMethod("emptyList");
+  public static void rewriteListOfEmpty(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    rewriteToCollectionMethod(invoke, iterator, factory, "emptyList");
   }
 
-  public static MethodInvokeRewriter rewriteSetOfEmpty() {
-    return rewriteToCollectionMethod("emptySet");
+  public static void rewriteSetOfEmpty(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    rewriteToCollectionMethod(invoke, iterator, factory, "emptySet");
   }
 
-  public static MethodInvokeRewriter rewriteMapOfEmpty() {
-    return rewriteToCollectionMethod("emptyMap");
+  public static void rewriteMapOfEmpty(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    rewriteToCollectionMethod(invoke, iterator, factory, "emptyMap");
   }
 
-  private static MethodInvokeRewriter rewriteToCollectionMethod(String methodName) {
-    return (invoke, factory) ->
-        new CfInvoke(
-            Opcodes.INVOKESTATIC,
-            factory.createMethod(factory.collectionsType, invoke.getMethod().proto, methodName),
-            false);
+  private static void rewriteToCollectionMethod(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      String methodName) {
+    assert invoke.inValues().isEmpty();
+
+    DexMethod collectionsEmptyList =
+        factory.createMethod(factory.collectionsType, invoke.getInvokedMethod().proto, methodName);
+    InvokeStatic newInvoke =
+        new InvokeStatic(collectionsEmptyList, invoke.outValue(), Collections.emptyList());
+    iterator.replaceCurrentInstruction(newInvoke);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/FloatMethodRewrites.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/FloatMethodRewrites.java
index 8670d3b..3601c51 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/FloatMethodRewrites.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/FloatMethodRewrites.java
@@ -4,20 +4,29 @@
 
 package com.android.tools.r8.ir.desugar.backports;
 
-import com.android.tools.r8.cf.code.CfInvoke;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.MethodInvokeRewriter;
-import org.objectweb.asm.Opcodes;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.Value;
+import java.util.Set;
 
 public final class FloatMethodRewrites {
 
   private FloatMethodRewrites() {}
 
-  public static MethodInvokeRewriter rewriteHashCode() {
-    return (invoke, factory) ->
-        new CfInvoke(
-            Opcodes.INVOKESTATIC,
+  public static void rewriteHashCode(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    InvokeStatic mathInvoke =
+        new InvokeStatic(
             factory.createMethod(
-                factory.boxedFloatType, invoke.getMethod().proto, "floatToIntBits"),
+                factory.boxedFloatType, invoke.getInvokedMethod().proto, "floatToIntBits"),
+            invoke.outValue(),
+            invoke.inValues(),
             false);
+    iterator.replaceCurrentInstruction(mathInvoke);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/LongMethodRewrites.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/LongMethodRewrites.java
index 5c29f81..348194b 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/LongMethodRewrites.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/LongMethodRewrites.java
@@ -4,16 +4,28 @@
 
 package com.android.tools.r8.ir.desugar.backports;
 
-import com.android.tools.r8.cf.code.CfCmp;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.ir.code.Cmp;
 import com.android.tools.r8.ir.code.Cmp.Bias;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.NumericType;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.MethodInvokeRewriter;
+import com.android.tools.r8.ir.code.Value;
+import java.util.List;
+import java.util.Set;
 
 public final class LongMethodRewrites {
 
   private LongMethodRewrites() {}
 
-  public static MethodInvokeRewriter rewriteCompare() {
-    return (invoke, factory) -> new CfCmp(Bias.NONE, NumericType.LONG);
+  public static void rewriteCompare(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    List<Value> inValues = invoke.inValues();
+    assert inValues.size() == 2;
+    iterator.replaceCurrentInstruction(
+        new Cmp(NumericType.LONG, Bias.NONE, invoke.outValue(), inValues.get(0), inValues.get(1)));
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/NumericMethodRewrites.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/NumericMethodRewrites.java
index 050aefa..4a413bc 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/NumericMethodRewrites.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/NumericMethodRewrites.java
@@ -1,44 +1,56 @@
 package com.android.tools.r8.ir.desugar.backports;
 
-import com.android.tools.r8.cf.code.CfArithmeticBinop;
-import com.android.tools.r8.cf.code.CfInstruction;
-import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.graph.DexItemFactory;
-import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.ir.code.Add;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeStatic;
 import com.android.tools.r8.ir.code.NumericType;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.FullMethodInvokeRewriter;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.MethodInvokeRewriter;
-import java.util.ListIterator;
-import org.objectweb.asm.Opcodes;
+import com.android.tools.r8.ir.code.Value;
+import java.util.List;
+import java.util.Set;
 
 public final class NumericMethodRewrites {
-
-  public static MethodInvokeRewriter rewriteToInvokeMath() {
-    return (invoke, factory) -> {
-      DexMethod method = invoke.getMethod();
-      return new CfInvoke(
-          Opcodes.INVOKESTATIC,
-          factory.createMethod(factory.mathType, method.proto, method.name),
-          false);
-    };
+  public static void rewriteToInvokeMath(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    InvokeStatic mathInvoke =
+        new InvokeStatic(
+            factory.createMethod(
+                factory.mathType, invoke.getInvokedMethod().proto, invoke.getInvokedMethod().name),
+            invoke.outValue(),
+            invoke.inValues(),
+            false);
+    iterator.replaceCurrentInstruction(mathInvoke);
   }
 
-  public static MethodInvokeRewriter rewriteToAddInstruction() {
-    return (invoke, factory) -> {
-      NumericType numericType = NumericType.fromDexType(invoke.getMethod().getReturnType());
-      return new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, numericType);
-    };
+  public static void rewriteToAddInstruction(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    List<Value> values = invoke.inValues();
+    assert values.size() == 2;
+
+    NumericType numericType = NumericType.fromDexType(invoke.getReturnType());
+    Add add = new Add(numericType, invoke.outValue(), values.get(0), values.get(1));
+    iterator.replaceCurrentInstruction(add);
   }
 
-  public static MethodInvokeRewriter rewriteAsIdentity() {
-    return new FullMethodInvokeRewriter() {
-      @Override
-      public void rewrite(
-          CfInvoke invoke, ListIterator<CfInstruction> iterator, DexItemFactory factory) {
-        // The invoke consumes the stack value and pushes another assumed to be the same.
-        iterator.remove();
-      }
-    };
+  public static void rewriteAsIdentity(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    List<Value> values = invoke.inValues();
+    assert values.size() == 1;
+    if (invoke.hasOutValue()) {
+      invoke.outValue().replaceUsers(values.get(0));
+    }
+    // TODO(b/152853271): Debugging information is lost here (DebugLocalWrite may be required).
+    iterator.removeOrReplaceByDebugLocalRead();
   }
 
   private NumericMethodRewrites() {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/ObjectsMethodRewrites.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/ObjectsMethodRewrites.java
index 69253be..de16e98 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/ObjectsMethodRewrites.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/ObjectsMethodRewrites.java
@@ -4,41 +4,43 @@
 
 package com.android.tools.r8.ir.desugar.backports;
 
-import com.android.tools.r8.cf.code.CfInstruction;
-import com.android.tools.r8.cf.code.CfInvoke;
-import com.android.tools.r8.cf.code.CfStackInstruction;
-import com.android.tools.r8.cf.code.CfStackInstruction.Opcode;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.FullMethodInvokeRewriter;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.MethodInvokeRewriter;
-import java.util.ListIterator;
-import org.objectweb.asm.Opcodes;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Value;
+import java.util.Set;
 
 public final class ObjectsMethodRewrites {
 
-  public static MethodInvokeRewriter rewriteToArraysHashCode() {
-    return (invoke, factory) -> {
-      DexType arraysType = factory.createType(factory.arraysDescriptor);
-      return new CfInvoke(
-          Opcodes.INVOKESTATIC,
-          factory.createMethod(arraysType, invoke.getMethod().proto, "hashCode"),
-          false);
-    };
+  public static void rewriteToArraysHashCode(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    DexType arraysType = factory.createType(factory.arraysDescriptor);
+    DexMethod hashCodeMethod =
+        factory.createMethod(arraysType, invoke.getInvokedMethod().proto, "hashCode");
+    InvokeStatic arraysHashCode =
+        new InvokeStatic(hashCodeMethod, invoke.outValue(), invoke.inValues(), false);
+    iterator.replaceCurrentInstruction(arraysHashCode);
   }
 
-  public static MethodInvokeRewriter rewriteRequireNonNull() {
-    return new FullMethodInvokeRewriter() {
-
-      @Override
-      public void rewrite(
-          CfInvoke invoke, ListIterator<CfInstruction> iterator, DexItemFactory factory) {
-        iterator.remove();
-        // requireNonNull returns the operand, so dup top-of-stack, do getClass and pop the class.
-        iterator.add(new CfStackInstruction(Opcode.Dup));
-        iterator.add(new CfInvoke(Opcodes.INVOKEVIRTUAL, factory.objectMembers.getClass, false));
-        iterator.add(new CfStackInstruction(Opcode.Pop));
-      }
-    };
+  public static void rewriteRequireNonNull(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    InvokeVirtual getClass =
+        new InvokeVirtual(factory.objectMembers.getClass, null, invoke.inValues());
+    if (invoke.hasOutValue()) {
+      affectedValues.addAll(invoke.outValue().affectedValues());
+      invoke.outValue().replaceUsers(invoke.inValues().get(0));
+      invoke.setOutValue(null);
+    }
+    iterator.replaceCurrentInstruction(getClass);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/OptionalMethodRewrites.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/OptionalMethodRewrites.java
index d66d7f5..1334c62 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/OptionalMethodRewrites.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/OptionalMethodRewrites.java
@@ -4,40 +4,69 @@
 
 package com.android.tools.r8.ir.desugar.backports;
 
-import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.graph.DexItemFactory;
-import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.ir.desugar.BackportedMethodRewriter.MethodInvokeRewriter;
-import java.util.function.Function;
-import org.objectweb.asm.Opcodes;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Value;
+import java.util.Set;
 
 public final class OptionalMethodRewrites {
 
   private OptionalMethodRewrites() {}
 
-  private static MethodInvokeRewriter createRewriter(
-      Function<DexItemFactory, DexType> holderTypeSupplier, String methodName) {
-    return (invoke, factory) ->
-        new CfInvoke(
-            Opcodes.INVOKEVIRTUAL,
+  public static void rewriteOrElseGet(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    InvokeVirtual getInvoke =
+        new InvokeVirtual(
+            factory.createMethod(factory.optionalType, invoke.getInvokedMethod().proto, "get"),
+            invoke.outValue(),
+            invoke.inValues());
+    iterator.replaceCurrentInstruction(getInvoke);
+  }
+
+  public static void rewriteDoubleOrElseGet(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    InvokeVirtual getInvoke =
+        new InvokeVirtual(
             factory.createMethod(
-                holderTypeSupplier.apply(factory), invoke.getMethod().proto, methodName),
-            false);
+                factory.optionalDoubleType, invoke.getInvokedMethod().proto, "getAsDouble"),
+            invoke.outValue(),
+            invoke.inValues());
+    iterator.replaceCurrentInstruction(getInvoke);
   }
 
-  public static MethodInvokeRewriter rewriteOrElseGet() {
-    return createRewriter(factory -> factory.optionalType, "get");
+  public static void rewriteIntOrElseGet(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    InvokeVirtual getInvoke =
+        new InvokeVirtual(
+            factory.createMethod(
+                factory.optionalIntType, invoke.getInvokedMethod().proto, "getAsInt"),
+            invoke.outValue(),
+            invoke.inValues());
+    iterator.replaceCurrentInstruction(getInvoke);
   }
 
-  public static MethodInvokeRewriter rewriteDoubleOrElseGet() {
-    return createRewriter(factory -> factory.optionalDoubleType, "getAsDouble");
-  }
-
-  public static MethodInvokeRewriter rewriteIntOrElseGet() {
-    return createRewriter(factory -> factory.optionalIntType, "getAsInt");
-  }
-
-  public static MethodInvokeRewriter rewriteLongOrElseGet() {
-    return createRewriter(factory -> factory.optionalLongType, "getAsLong");
+  public static void rewriteLongOrElseGet(
+      InvokeMethod invoke,
+      InstructionListIterator iterator,
+      DexItemFactory factory,
+      Set<Value> affectedValues) {
+    InvokeVirtual getInvoke =
+        new InvokeVirtual(
+            factory.createMethod(
+                factory.optionalLongType, invoke.getInvokedMethod().proto, "getAsLong"),
+            invoke.outValue(),
+            invoke.inValues());
+    iterator.replaceCurrentInstruction(getInvoke);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index 311e10d..6c28f2e 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -55,6 +55,7 @@
 import com.android.tools.r8.utils.PredicateSet;
 import com.android.tools.r8.utils.TraversalContinuation;
 import com.android.tools.r8.utils.Visibility;
+import com.android.tools.r8.utils.WorkList;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
@@ -613,21 +614,13 @@
 
   public Collection<DexClass> computeReachableInterfaces() {
     Set<DexClass> interfaces = Sets.newIdentityHashSet();
-    Set<DexType> seen = Sets.newIdentityHashSet();
-    Deque<DexType> worklist = new ArrayDeque<>();
+    WorkList<DexType> worklist = WorkList.newIdentityWorkList();
+    worklist.addIfNotSeen(objectAllocationInfoCollection.getInstantiatedLambdaInterfaces());
     for (DexProgramClass clazz : classes()) {
-      worklist.add(clazz.type);
+      worklist.addIfNotSeen(clazz.type);
     }
-    for (DexCallSite callSite : callSites.keySet()) {
-      for (DexEncodedMethod method : lookupLambdaImplementedMethods(callSite)) {
-        worklist.add(method.holder());
-      }
-    }
-    while (!worklist.isEmpty()) {
-      DexType type = worklist.pop();
-      if (!seen.add(type)) {
-        continue;
-      }
+    while (worklist.hasNext()) {
+      DexType type = worklist.next();
       DexClass definition = definitionFor(type);
       if (definition == null) {
         continue;
@@ -636,9 +629,9 @@
         interfaces.add(definition);
       }
       if (definition.superType != null) {
-        worklist.add(definition.superType);
+        worklist.addIfNotSeen(definition.superType);
       }
-      Collections.addAll(worklist, definition.interfaces.values);
+      worklist.addIfNotSeen(definition.interfaces.values);
     }
     return interfaces;
   }
@@ -1247,18 +1240,21 @@
    */
   public void forEachTypeInHierarchyOfLiveProgramClasses(Consumer<DexClass> fn) {
     forEachTypeInHierarchyOfLiveProgramClasses(
-        fn, ListUtils.map(liveTypes, t -> definitionFor(t).asProgramClass()), callSites, this);
+        fn,
+        ListUtils.map(liveTypes, t -> definitionFor(t).asProgramClass()),
+        objectAllocationInfoCollection.getInstantiatedLambdaInterfaces(),
+        this);
   }
 
   // Split in a static method so it can be used during construction.
   static void forEachTypeInHierarchyOfLiveProgramClasses(
       Consumer<DexClass> fn,
       Collection<DexProgramClass> liveProgramClasses,
-      Map<DexCallSite, ProgramMethodSet> callSites,
+      Set<DexType> lambdaInterfaces,
       AppInfoWithClassHierarchy appInfo) {
     Set<DexType> seen = Sets.newIdentityHashSet();
-    Deque<DexType> worklist = new ArrayDeque<>();
     liveProgramClasses.forEach(c -> seen.add(c.type));
+    Deque<DexType> worklist = new ArrayDeque<>(lambdaInterfaces);
     for (DexProgramClass liveProgramClass : liveProgramClasses) {
       fn.accept(liveProgramClass);
       DexType superType = liveProgramClass.superType;
@@ -1271,16 +1267,6 @@
         }
       }
     }
-    for (DexCallSite callSite : callSites.keySet()) {
-      List<DexType> interfaces = LambdaDescriptor.getInterfaces(callSite, appInfo);
-      if (interfaces != null) {
-        for (DexType iface : interfaces) {
-          if (seen.add(iface)) {
-            worklist.add(iface);
-          }
-        }
-      }
-    }
     while (!worklist.isEmpty()) {
       DexType type = worklist.pop();
       DexClass clazz = appInfo.definitionFor(type);
diff --git a/src/main/java/com/android/tools/r8/utils/WorkList.java b/src/main/java/com/android/tools/r8/utils/WorkList.java
index 2e74be4..8ee6e30 100644
--- a/src/main/java/com/android/tools/r8/utils/WorkList.java
+++ b/src/main/java/com/android/tools/r8/utils/WorkList.java
@@ -50,7 +50,7 @@
     }
   }
 
-  public void addAll(Iterable<T> items) {
+  public void addAllIgnoringSeenSet(Iterable<T> items) {
     items.forEach(workingList::addLast);
   }
 
diff --git a/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java b/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java
index 9fe1539..700b3f0 100644
--- a/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java
+++ b/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java
@@ -642,6 +642,7 @@
               "530-checker-lse2",
               TestCondition.match(
                   TestCondition.tools(DexTool.DX),
+                  TestCondition.compilers(CompilerUnderTest.R8, CompilerUnderTest.D8),
                   TestCondition.runtimesUpTo(DexVm.Version.V6_0_1)))
           .put(
               "534-checker-bce-deoptimization",