diff --git a/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
index b8210c8..03c329c 100644
--- a/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
@@ -243,7 +243,7 @@
       return self();
     }
 
-    public Builder addClasspathClasses(List<DexClasspathClass> classes) {
+    public Builder addClasspathClasses(Collection<DexClasspathClass> classes) {
       classpathClasses =
           ImmutableList.<DexClasspathClass>builder()
               .addAll(classpathClasses)
diff --git a/src/main/java/com/android/tools/r8/graph/analysis/DesugaredLibraryConversionWrapperAnalysis.java b/src/main/java/com/android/tools/r8/graph/analysis/DesugaredLibraryConversionWrapperAnalysis.java
index d8d48a2..8d61294 100644
--- a/src/main/java/com/android/tools/r8/graph/analysis/DesugaredLibraryConversionWrapperAnalysis.java
+++ b/src/main/java/com/android/tools/r8/graph/analysis/DesugaredLibraryConversionWrapperAnalysis.java
@@ -15,18 +15,16 @@
 import com.android.tools.r8.ir.desugar.DesugaredLibraryAPIConverter.Mode;
 import com.android.tools.r8.utils.OptionalBool;
 import java.util.ArrayList;
+import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
-import java.util.Set;
-import java.util.function.Consumer;
 
 public class DesugaredLibraryConversionWrapperAnalysis extends EnqueuerAnalysis
     implements EnqueuerInvokeAnalysis {
 
   private final AppView<?> appView;
   private final DesugaredLibraryAPIConverter converter;
-  private boolean callbackGenerated = false;
-  private Map<DexProgramClass, DexProgramClass> wrappersToReverseMap = null;
+  private Map<DexType, DexProgramClass> synthesizedWrappers = new IdentityHashMap<>();
 
   public DesugaredLibraryConversionWrapperAnalysis(AppView<?> appView) {
     this.appView = appView;
@@ -69,22 +67,18 @@
   }
 
   public List<DexEncodedMethod> generateCallbackMethods() {
-    assert !callbackGenerated;
-    callbackGenerated = true;
     return converter.generateCallbackMethods();
   }
 
-  public Set<DexProgramClass> generateWrappers() {
-    assert wrappersToReverseMap == null;
-    wrappersToReverseMap = converter.synthesizeWrappersAndMapToReverse();
-    return wrappersToReverseMap.keySet();
+  public List<DexProgramClass> generateWrappers() {
+    return converter.synthesizeWrappers(synthesizedWrappers);
   }
 
   // Generate a mock classpath class for all vivified types.
   // Types will be available at runtime in the desugared library dex file.
-  public List<DexClasspathClass> generateWrappersSuperTypeMock() {
+  public List<DexClasspathClass> generateWrappersSuperTypeMock(List<DexProgramClass> wrappers) {
     List<DexClasspathClass> classpathClasses = new ArrayList<>();
-    for (DexProgramClass wrapper : wrappersToReverseMap.keySet()) {
+    for (DexProgramClass wrapper : wrappers) {
       boolean mockIsInterface = wrapper.interfaces.size() == 1;
       DexType mockType = mockIsInterface ? wrapper.interfaces.values[0] : wrapper.superType;
       if (appView.definitionFor(mockType) == null) {
@@ -106,37 +100,4 @@
     }
     return classpathClasses;
   }
-
-  public DesugaredLibraryConversionWrapperAnalysis registerWrite(
-      DexProgramClass wrapper, Consumer<DexEncodedMethod> registration) {
-    registration.accept(getInitializer(wrapper));
-    return this;
-  }
-
-  public DesugaredLibraryConversionWrapperAnalysis registerReads(
-      DexProgramClass wrapper, Consumer<DexEncodedMethod> registration) {
-    // The field of each wrapper is read exclusively in all virtual methods and the reverse wrapper
-    // convert method.
-    for (DexEncodedMethod virtualMethod : wrapper.virtualMethods()) {
-      registration.accept(virtualMethod);
-    }
-    DexProgramClass reverseWrapper = wrappersToReverseMap.get(wrapper);
-    assert reverseWrapper != null;
-    registration.accept(getConvertMethod(reverseWrapper));
-    return this;
-  }
-
-  private DexEncodedMethod getInitializer(DexProgramClass wrapper) {
-    DexEncodedMethod initializer =
-        wrapper.lookupDirectMethod(DexEncodedMethod::isInstanceInitializer);
-    assert initializer != null;
-    return initializer;
-  }
-
-  private DexEncodedMethod getConvertMethod(DexProgramClass wrapper) {
-    DexEncodedMethod convertMethod = wrapper.lookupDirectMethod(DexEncodedMethod::isStatic);
-    assert convertMethod != null;
-    assert convertMethod.method.name == appView.dexItemFactory().convertMethodName;
-    return convertMethod;
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
index fb97d0c..45c5bd2 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryAPIConverter.java
@@ -29,14 +29,15 @@
 import com.android.tools.r8.ir.synthetic.DesugaredLibraryAPIConversionCfCodeProvider.APIConverterWrapperCfCodeProvider;
 import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.StringDiagnostic;
+import com.android.tools.r8.utils.WorkList;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.HashSet;
-import java.util.LinkedList;
+import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Map;
@@ -70,7 +71,9 @@
   // Enqueuer and not during IR processing.
   private final Mode mode;
   private final DesugaredLibraryWrapperSynthesizer wrapperSynthesizor;
-  private final Map<DexClass, Set<DexEncodedMethod>> callBackMethods = new HashMap<>();
+  private final Map<DexClass, Set<DexEncodedMethod>> callBackMethods = new IdentityHashMap<>();
+  private final Map<DexClass, List<DexEncodedMethod>> pendingCallBackMethods =
+      new IdentityHashMap<>();
   private final Set<DexMethod> trackedCallBackAPIs;
   private final Set<DexMethod> trackedAPIs;
 
@@ -172,7 +175,9 @@
     // library type), but the enqueuer cannot see that.
     // To avoid too much computation we first look if the method would need to be rewritten if
     // it would override a library method, then check if it overrides a library method.
-    if (encodedMethod.isPrivateMethod() || encodedMethod.isStatic()) {
+    if (encodedMethod.isPrivateMethod()
+        || encodedMethod.isStatic()
+        || encodedMethod.isLibraryMethodOverride().isFalse()) {
       return false;
     }
     DexMethod method = encodedMethod.method;
@@ -195,22 +200,22 @@
 
   private boolean overridesLibraryMethod(DexClass theClass, DexMethod method) {
     // We look up everywhere to see if there is a supertype/interface implementing the method...
-    LinkedList<DexType> workList = new LinkedList<>();
-    Collections.addAll(workList, theClass.interfaces.values);
+    WorkList<DexType> workList = WorkList.newIdentityWorkList();
+    workList.addIfNotSeen(theClass.interfaces.values);
     boolean foundOverrideToRewrite = false;
     // There is no methods with desugared types on Object.
     if (theClass.superType != factory.objectType) {
-      workList.add(theClass.superType);
+      workList.addIfNotSeen(theClass.superType);
     }
-    while (!workList.isEmpty()) {
-      DexType current = workList.removeFirst();
+    while (workList.hasNext()) {
+      DexType current = workList.next();
       DexClass dexClass = appView.definitionFor(current);
       if (dexClass == null) {
         continue;
       }
-      workList.addAll(Arrays.asList(dexClass.interfaces.values));
+      workList.addIfNotSeen(dexClass.interfaces.values);
       if (dexClass.superType != factory.objectType) {
-        workList.add(dexClass.superType);
+        workList.addIfNotSeen(dexClass.superType);
       }
       if (!dexClass.isLibraryClass() && !appView.options().isDesugaredLibraryCompilation()) {
         continue;
@@ -249,8 +254,9 @@
 
   private synchronized void addCallBackSignature(DexClass dexClass, DexEncodedMethod method) {
     assert dexClass.type == method.method.holder;
-    callBackMethods.putIfAbsent(dexClass, new HashSet<>());
-    callBackMethods.get(dexClass).add(method);
+    if (callBackMethods.computeIfAbsent(dexClass, key -> new HashSet<>()).add(method)) {
+      pendingCallBackMethods.computeIfAbsent(dexClass, key -> new ArrayList<>()).add(method);
+    }
   }
 
   public static DexMethod methodWithVivifiedTypeInSignature(
@@ -289,19 +295,24 @@
     if (appView.options().testing.trackDesugaredAPIConversions) {
       generateTrackDesugaredAPIWarnings(trackedAPIs, "");
       generateTrackDesugaredAPIWarnings(trackedCallBackAPIs, "callback ");
+      trackedAPIs.clear();
+      trackedCallBackAPIs.clear();
     }
     List<DexEncodedMethod> result = new ArrayList<>();
-    for (DexClass dexClass : callBackMethods.keySet()) {
-      List<DexEncodedMethod> dexEncodedMethods =
-          generateCallbackMethods(callBackMethods.get(dexClass), dexClass);
-      dexClass.addVirtualMethods(dexEncodedMethods);
-      result.addAll(dexEncodedMethods);
-    }
+    pendingCallBackMethods.forEach(
+        (clazz, callbacks) -> {
+          List<DexEncodedMethod> generated =
+              ListUtils.map(callbacks, callback -> generateCallbackMethod(callback, clazz));
+          clazz.addVirtualMethods(generated);
+          result.addAll(generated);
+        });
+    pendingCallBackMethods.clear();
     return result;
   }
 
-  public Map<DexProgramClass, DexProgramClass> synthesizeWrappersAndMapToReverse() {
-    return wrapperSynthesizor.synthesizeWrappersAndMapToReverse();
+  public List<DexProgramClass> synthesizeWrappers(
+      Map<DexType, DexProgramClass> synthesizedWrappers) {
+    return wrapperSynthesizor.synthesizeWrappers(synthesizedWrappers);
   }
 
   public DexClasspathClass synthesizeClasspathMock(
@@ -309,23 +320,21 @@
     return wrapperSynthesizor.synthesizeClasspathMock(classToMock, mockType, mockIsInterface);
   }
 
-  private List<DexEncodedMethod> generateCallbackMethods(
-      Set<DexEncodedMethod> originalMethods, DexClass dexClass) {
-    List<DexEncodedMethod> newDexEncodedMethods = new ArrayList<>();
-    for (DexEncodedMethod originalMethod : originalMethods) {
-      DexMethod methodToInstall =
-          methodWithVivifiedTypeInSignature(originalMethod.method, dexClass.type, appView);
-      CfCode cfCode =
-          new APIConverterWrapperCfCodeProvider(
-                  appView, originalMethod.method, null, this, dexClass.isInterface())
-              .generateCfCode();
-      DexEncodedMethod newDexEncodedMethod =
-          wrapperSynthesizor.newSynthesizedMethod(methodToInstall, originalMethod, cfCode);
-      newDexEncodedMethod.setCode(cfCode, appView);
-      newDexEncodedMethods.add(newDexEncodedMethod);
+  private DexEncodedMethod generateCallbackMethod(
+      DexEncodedMethod originalMethod, DexClass dexClass) {
+    DexMethod methodToInstall =
+        methodWithVivifiedTypeInSignature(originalMethod.method, dexClass.type, appView);
+    CfCode cfCode =
+        new APIConverterWrapperCfCodeProvider(
+                appView, originalMethod.method, null, this, dexClass.isInterface())
+            .generateCfCode();
+    DexEncodedMethod newDexEncodedMethod =
+        wrapperSynthesizor.newSynthesizedMethod(methodToInstall, originalMethod, cfCode);
+    newDexEncodedMethod.setCode(cfCode, appView);
+    if (originalMethod.isLibraryMethodOverride().isTrue()) {
+      newDexEncodedMethod.setLibraryMethodOverride(OptionalBool.TRUE);
     }
-    assert Sets.newHashSet(newDexEncodedMethods).size() == newDexEncodedMethods.size();
-    return newDexEncodedMethods;
+    return newDexEncodedMethod;
   }
 
   private void generateTrackDesugaredAPIWarnings(Set<DexMethod> tracked, String inner) {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryWrapperSynthesizer.java b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryWrapperSynthesizer.java
index 946077d..30bc78e 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryWrapperSynthesizer.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/DesugaredLibraryWrapperSynthesizer.java
@@ -506,52 +506,33 @@
   void finalizeWrappersForD8(
       DexApplication.Builder<?> builder, IRConverter irConverter, ExecutorService executorService)
       throws ExecutionException {
-    Map<DexType, DexProgramClass> synthesizedWrappers = synthesizeWrappers();
-    registerAndProcessWrappers(builder, irConverter, executorService, synthesizedWrappers.values());
+    List<DexProgramClass> synthesizedWrappers = synthesizeWrappers(new IdentityHashMap<>());
+    registerAndProcessWrappers(builder, irConverter, executorService, synthesizedWrappers);
   }
 
-  private Map<DexType, DexProgramClass> synthesizeWrappers() {
-    Map<DexType, DexProgramClass> synthesizedWrappers = new IdentityHashMap<>();
+  List<DexProgramClass> synthesizeWrappers(Map<DexType, DexProgramClass> synthesizedWrappers) {
+    List<DexProgramClass> additions = new ArrayList<>();
     // Generating a wrapper may require other wrappers to be generated, iterate until fix point.
     while (synthesizedWrappers.size() != typeWrappers.size() + vivifiedTypeWrappers.size()) {
       for (DexType type : typeWrappers.keySet()) {
         DexType typeWrapperType = typeWrappers.get(type);
         if (!synthesizedWrappers.containsKey(typeWrapperType)) {
-          synthesizedWrappers.put(
-              typeWrapperType, generateTypeWrapper(getValidClassToWrap(type), typeWrapperType));
+          DexProgramClass wrapper = generateTypeWrapper(getValidClassToWrap(type), typeWrapperType);
+          synthesizedWrappers.put(typeWrapperType, wrapper);
+          additions.add(wrapper);
         }
       }
       for (DexType type : vivifiedTypeWrappers.keySet()) {
         DexType vivifiedTypeWrapperType = vivifiedTypeWrappers.get(type);
         if (!synthesizedWrappers.containsKey(vivifiedTypeWrapperType)) {
-          synthesizedWrappers.put(
-              vivifiedTypeWrapperType,
-              generateVivifiedTypeWrapper(getValidClassToWrap(type), vivifiedTypeWrapperType));
+          DexProgramClass wrapper =
+              generateVivifiedTypeWrapper(getValidClassToWrap(type), vivifiedTypeWrapperType);
+          synthesizedWrappers.put(vivifiedTypeWrapperType, wrapper);
+          additions.add(wrapper);
         }
       }
     }
-    return synthesizedWrappers;
-  }
-
-  private Map<DexType, DexType> reverseWrapperMap() {
-    Map<DexType, DexType> reverseWrapperMap = new IdentityHashMap<>();
-    for (DexType type : typeWrappers.keySet()) {
-      reverseWrapperMap.put(typeWrappers.get(type), vivifiedTypeWrappers.get(type));
-    }
-    for (DexType type : vivifiedTypeWrappers.keySet()) {
-      reverseWrapperMap.put(vivifiedTypeWrappers.get(type), typeWrappers.get(type));
-    }
-    return reverseWrapperMap;
-  }
-
-  Map<DexProgramClass, DexProgramClass> synthesizeWrappersAndMapToReverse() {
-    Map<DexType, DexProgramClass> synthesizedWrappers = synthesizeWrappers();
-    Map<DexType, DexType> reverseMap = reverseWrapperMap();
-    Map<DexProgramClass, DexProgramClass> wrappersAndReverse = new IdentityHashMap<>();
-    for (DexProgramClass wrapper : synthesizedWrappers.values()) {
-      wrappersAndReverse.put(wrapper, synthesizedWrappers.get(reverseMap.get(wrapper.type)));
-    }
-    return wrappersAndReverse;
+    return additions;
   }
 
   private void registerAndProcessWrappers(
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 6c7a4fe..20dde1b 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -2514,6 +2514,8 @@
 
     Map<DexMethod, ProgramMethod> liveMethods = new IdentityHashMap<>();
 
+    Map<DexType, DexClasspathClass> syntheticClasspathClasses = new IdentityHashMap<>();
+
     // Subset of live methods that need to be pinned.
     Set<DexMethod> pinnedMethods = Sets.newIdentityHashSet();
 
@@ -2535,6 +2537,11 @@
       }
     }
 
+    void addClasspathClass(DexClasspathClass clazz) {
+      DexClasspathClass old = syntheticClasspathClasses.put(clazz.type, clazz);
+      assert old == null;
+    }
+
     void addLiveMethod(ProgramMethod method) {
       DexMethod signature = method.getMethod().method;
       assert !liveMethods.containsKey(signature);
@@ -2552,6 +2559,7 @@
           syntheticInstantiations.values()) {
         appBuilder.addProgramClass(clazzAndContext.getFirst());
       }
+      appBuilder.addClasspathClasses(syntheticClasspathClasses.values());
       appBuilder.addToMainDexList(mainDexTypes);
     }
 
@@ -2590,6 +2598,7 @@
     SyntheticAdditions additions = new SyntheticAdditions();
     synthesizeInterfaceMethodBridges(additions);
     synthesizeLambdas(additions);
+    synthesizeLibraryConversionWrappers(additions);
     if (additions.isEmpty()) {
       return;
     }
@@ -2714,7 +2723,6 @@
     appBuilder.replaceClasspathClasses(classpathClasses);
     // Can't replace the program classes at this point as they are needed in tree pruning.
     // Post process the app to add synthetic content.
-    postProcessLibraryConversionWrappers(appBuilder);
     DirectMappedDexApplication app = appBuilder.build();
 
     AppInfoWithLiveness appInfoWithLiveness =
@@ -2810,7 +2818,7 @@
     }
   }
 
-  private void postProcessLibraryConversionWrappers(DirectMappedDexApplication.Builder appBuilder) {
+  private void synthesizeLibraryConversionWrappers(SyntheticAdditions additions) {
     if (desugaredLibraryWrapperAnalysis == null) {
       return;
     }
@@ -2819,41 +2827,24 @@
     List<DexEncodedMethod> callbacks = desugaredLibraryWrapperAnalysis.generateCallbackMethods();
     for (DexEncodedMethod callback : callbacks) {
       DexProgramClass clazz = getProgramClassOrNull(callback.method.holder);
-      targetedMethods.add(callback, graphReporter.fakeReportShouldNotBeUsed());
-      liveMethods.add(clazz, callback, graphReporter.fakeReportShouldNotBeUsed());
+      additions.addLiveMethod(new ProgramMethod(clazz, callback));
     }
 
     // Generate the wrappers.
-    Set<DexProgramClass> wrappers = desugaredLibraryWrapperAnalysis.generateWrappers();
+    List<DexProgramClass> wrappers = desugaredLibraryWrapperAnalysis.generateWrappers();
     for (DexProgramClass wrapper : wrappers) {
-      appBuilder.addProgramClass(wrapper);
-      liveTypes.add(wrapper, graphReporter.fakeReportShouldNotBeUsed());
-      objectAllocationInfoCollection.recordDirectAllocationSite(
-          wrapper,
-          null,
-          InstantiationReason.SYNTHESIZED_CLASS,
-          graphReporter.fakeReportShouldNotBeUsed(),
-          appInfo);
+      additions.addInstantiatedClass(wrapper, null, false);
       // Mark all methods on the wrapper as live and targeted.
       for (DexEncodedMethod method : wrapper.methods()) {
-        targetedMethods.add(method, graphReporter.fakeReportShouldNotBeUsed());
-        liveMethods.add(wrapper, method, graphReporter.fakeReportShouldNotBeUsed());
+        additions.addLiveMethod(new ProgramMethod(wrapper, method));
       }
-      // Register wrapper unique field reads and unique write.
-      assert wrapper.instanceFields().size() == 1;
-      DexField field = wrapper.instanceFields().get(0).field;
-      FieldAccessInfoImpl info = new FieldAccessInfoImpl(field);
-      fieldAccessInfoCollection.extend(field, info);
-      desugaredLibraryWrapperAnalysis
-          .registerWrite(wrapper, writeContext -> info.recordWrite(field, writeContext))
-          .registerReads(wrapper, readContext -> info.recordRead(field, readContext));
     }
 
     // Add all vivified types as classpath classes.
     // They will be available at runtime in the desugared library dex file.
-    List<DexClasspathClass> mockVivifiedClasses =
-        desugaredLibraryWrapperAnalysis.generateWrappersSuperTypeMock();
-    appBuilder.addClasspathClasses(mockVivifiedClasses);
+    desugaredLibraryWrapperAnalysis
+        .generateWrappersSuperTypeMock(wrappers)
+        .forEach(additions::addClasspathClass);
   }
 
   private void rewriteLambdaCallSites(