diff --git a/src/main/java/com/android/tools/r8/DexSegments.java b/src/main/java/com/android/tools/r8/DexSegments.java
index 591b1f3..c9073be 100644
--- a/src/main/java/com/android/tools/r8/DexSegments.java
+++ b/src/main/java/com/android/tools/r8/DexSegments.java
@@ -13,13 +13,14 @@
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.google.common.collect.ImmutableList;
 import com.google.common.io.Closer;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceLinkedOpenHashMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import java.io.IOException;
 import java.nio.file.Paths;
-import java.util.LinkedHashMap;
 import java.util.Map;
 
 public class DexSegments {
-  private static class Command extends BaseCommand {
+  public static class Command extends BaseCommand {
 
     public static class Builder
         extends BaseCommand.Builder<Command, Builder> {
@@ -89,14 +90,27 @@
   public static void main(String[] args)
       throws IOException, CompilationFailedException, ResourceException {
     Command.Builder builder = Command.parse(args);
-    Command command = builder.build();
+    Map<Integer, SegmentInfo> result = run(builder.build());
+    if (result == null) {
+      return;
+    }
+    System.out.println("Segments in dex application (name: size / items):");
+    // This output is parsed by tools/test_framework.py. Check the parsing there when updating.
+    result.forEach(
+        (key, value) ->
+            System.out.println(
+                " - " + DexSection.typeName(key) + ": " + value.size + " / " + value.items));
+  }
+
+  public static Map<Integer, SegmentInfo> run(Command command)
+      throws CompilationFailedException, IOException, ResourceException {
     if (command.isPrintHelp()) {
       System.out.println(Command.USAGE_MESSAGE);
-      return;
+      return null;
     }
     AndroidApp app = command.getInputApp();
 
-    Map<String, SegmentInfo> result = new LinkedHashMap<>();
+    Int2ReferenceMap<SegmentInfo> result = new Int2ReferenceLinkedOpenHashMap<>();
     // Fill the results with all benchmark items otherwise golem may report missing benchmarks.
     int[] benchmarks =
         new int[] {
@@ -119,7 +133,7 @@
           Constants.TYPE_CLASS_DEF_ITEM
         };
     for (int benchmark : benchmarks) {
-      result.computeIfAbsent(DexSection.typeName(benchmark), (key) -> new SegmentInfo());
+      result.computeIfAbsent(benchmark, (key) -> new SegmentInfo());
     }
     try (Closer closer = Closer.create()) {
       for (ProgramResource resource : app.computeAllProgramResources()) {
@@ -127,20 +141,16 @@
           for (DexSection dexSection :
               DexParser.parseMapFrom(
                   closer.register(resource.getByteStream()), resource.getOrigin())) {
-            SegmentInfo info =
-                result.computeIfAbsent(dexSection.typeName(), (key) -> new SegmentInfo());
+            SegmentInfo info = result.computeIfAbsent(dexSection.type, (key) -> new SegmentInfo());
             info.increment(dexSection.length, dexSection.size());
           }
         }
       }
     }
-    System.out.println("Segments in dex application (name: size / items):");
-    // This output is parsed by tools/test_framework.py. Check the parsing there when updating.
-    result.forEach(
-        (key, value) -> System.out.println(" - " + key + ": " + value.size + " / " + value.items));
+    return result;
   }
 
-  private static class SegmentInfo {
+  public static class SegmentInfo {
     private int items;
     private int size;
 
@@ -153,5 +163,13 @@
       this.items += items;
       this.size += size;
     }
+
+    public int getItemCount() {
+      return items;
+    }
+
+    public int getSegmentSize() {
+      return size;
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelCompute.java b/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelCompute.java
index 48d4d4f..4afafc1 100644
--- a/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelCompute.java
+++ b/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelCompute.java
@@ -47,7 +47,11 @@
   public static AndroidApiLevelCompute create(AppView<?> appView) {
     return appView.options().apiModelingOptions().enableApiCallerIdentification
         ? new DefaultAndroidApiLevelCompute(appView)
-        : new NoAndroidApiLevelCompute();
+        : noAndroidApiLevelCompute();
+  }
+
+  public static AndroidApiLevelCompute noAndroidApiLevelCompute() {
+    return new NoAndroidApiLevelCompute();
   }
 
   public static ComputedApiLevel computeInitialMinApiLevel(InternalOptions options) {
diff --git a/src/main/java/com/android/tools/r8/androidapi/AndroidApiReferenceLevelCache.java b/src/main/java/com/android/tools/r8/androidapi/AndroidApiReferenceLevelCache.java
index 4e17f60..27fbc38 100644
--- a/src/main/java/com/android/tools/r8/androidapi/AndroidApiReferenceLevelCache.java
+++ b/src/main/java/com/android/tools/r8/androidapi/AndroidApiReferenceLevelCache.java
@@ -63,10 +63,7 @@
       return appView.computedMinApiLevel();
     }
     DexClass clazz = appView.definitionFor(contextType);
-    if (clazz == null) {
-      return unknownValue;
-    }
-    if (!clazz.isLibraryClass()) {
+    if (clazz != null && clazz.isProgramClass()) {
       return appView.computedMinApiLevel();
     }
     if (reference.getContextType() == factory.objectType) {
diff --git a/src/main/java/com/android/tools/r8/androidapi/ComputedApiLevel.java b/src/main/java/com/android/tools/r8/androidapi/ComputedApiLevel.java
index 2f5ab5e..a2e9e87 100644
--- a/src/main/java/com/android/tools/r8/androidapi/ComputedApiLevel.java
+++ b/src/main/java/com/android/tools/r8/androidapi/ComputedApiLevel.java
@@ -38,19 +38,23 @@
     return isGreaterThanOrEqualTo(other) ? this : other;
   }
 
-  default boolean isGreaterThanOrEqualTo(ComputedApiLevel other) {
+  default boolean isGreaterThan(ComputedApiLevel other) {
     assert !isNotSetApiLevel() && !other.isNotSetApiLevel()
         : "Cannot compute relationship for not set";
-    if (isUnknownApiLevel()) {
-      return true;
-    }
     if (other.isUnknownApiLevel()) {
       return false;
     }
+    if (isUnknownApiLevel()) {
+      return true;
+    }
     assert isKnownApiLevel() && other.isKnownApiLevel();
-    return asKnownApiLevel()
-        .getApiLevel()
-        .isGreaterThanOrEqualTo(other.asKnownApiLevel().getApiLevel());
+    return asKnownApiLevel().getApiLevel().isGreaterThan(other.asKnownApiLevel().getApiLevel());
+  }
+
+  default boolean isGreaterThanOrEqualTo(ComputedApiLevel other) {
+    assert !isNotSetApiLevel() && !other.isNotSetApiLevel()
+        : "Cannot compute relationship for not set";
+    return other.equals(this) || isGreaterThan(other);
   }
 
   default boolean isKnownApiLevel() {
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
index 8209749..3acd908 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
@@ -46,6 +46,7 @@
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.shaking.MainDexInfo;
 import com.android.tools.r8.utils.ArrayUtils;
+import com.android.tools.r8.utils.Box;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.ExceptionUtils;
 import com.android.tools.r8.utils.InternalOptions;
@@ -63,13 +64,10 @@
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashSet;
-import java.util.IdentityHashMap;
 import java.util.List;
-import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Future;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
 
@@ -229,31 +227,18 @@
     }
   }
 
+  private boolean willComputeProguardMap() {
+    return proguardMapSupplier != null && options.proguardMapConsumer != null;
+  }
+
   public void write(ExecutorService executorService) throws IOException, ExecutionException {
     Timing timing = appView.appInfo().app().timing;
     timing.begin("DexApplication.write");
-    ProguardMapId proguardMapId =
-        (proguardMapSupplier != null && options.proguardMapConsumer != null)
-            ? proguardMapSupplier.writeProguardMap()
-            : null;
 
-    // If we do have a map then we're called from R8. In that case we have at least one marker.
-    assert proguardMapId == null || (markers != null && markers.size() >= 1);
-
-    if (markers != null && !markers.isEmpty()) {
-      if (proguardMapId != null) {
-        markers.get(0).setPgMapId(proguardMapId.getId());
-      }
-      markerStrings = new ArrayList<>(markers.size());
-      for (Marker marker : markers) {
-        markerStrings.add(appView.dexItemFactory().createString(marker.toString()));
-      }
-    }
-
-    if (options.sourceFileProvider != null) {
-      SourceFileEnvironment environment = createSourceFileEnvironment(proguardMapId);
-      appView.appInfo().classes().forEach(clazz -> rewriteSourceFile(clazz, environment));
-    }
+    Box<ProguardMapId> delayedProguardMapId = new Box<>();
+    List<LazyDexString> lazyDexStrings = new ArrayList<>();
+    computeMarkerStrings(delayedProguardMapId, lazyDexStrings);
+    computeSourceFileString(delayedProguardMapId, lazyDexStrings);
 
     try {
       timing.begin("Insert Attribute Annotations");
@@ -269,7 +254,6 @@
       }
 
       // Generate the dex file contents.
-      List<Future<Boolean>> dexDataFutures = new ArrayList<>();
       timing.begin("Distribute");
       List<VirtualFile> virtualFiles = distribute(executorService);
       timing.end();
@@ -291,20 +275,59 @@
       appView.appInfo().classes().forEach((clazz) -> clazz.addDependencies(sortAnnotations));
       timing.end();
 
-      TimingMerger merger =
-          timing.beginMerger("Write files", ThreadUtils.getNumberOfThreads(executorService));
-      Collection<Timing> timings =
-          ThreadUtils.processItemsWithResults(
-              virtualFiles,
-              virtualFile -> {
-                Timing fileTiming = Timing.create("VirtualFile " + virtualFile.getId(), options);
-                writeVirtualFile(virtualFile, fileTiming);
-                fileTiming.end();
-                return fileTiming;
-              },
-              executorService);
-      merger.add(timings);
-      merger.end();
+      {
+        // Compute offsets and rewrite jumbo strings so that code offsets are fixed.
+        TimingMerger merger =
+            timing.beginMerger("Pre-write phase", ThreadUtils.getNumberOfThreads(executorService));
+        Collection<Timing> timings =
+            ThreadUtils.processItemsWithResults(
+                virtualFiles,
+                virtualFile -> {
+                  Timing fileTiming = Timing.create("VirtualFile " + virtualFile.getId(), options);
+                  computeOffsetMappingAndRewriteJumboStrings(
+                      virtualFile, lazyDexStrings, fileTiming);
+                  fileTiming.end();
+                  return fileTiming;
+                },
+                executorService);
+        merger.add(timings);
+        merger.end();
+      }
+
+      // Now code offsets are fixed, compute the mapping file content.
+      // TODO(b/207765416): Move the line number optimizer to this point so PC info can be used.
+      if (willComputeProguardMap()) {
+        timing.begin("Write proguard map");
+        delayedProguardMapId.set(proguardMapSupplier.writeProguardMap());
+        timing.end();
+      }
+
+      // With the mapping id/hash known, it is safe to compute the remaining dex strings.
+      timing.begin("Compute lazy strings");
+      List<DexString> forcedStrings = new ArrayList<>();
+      for (LazyDexString lazyDexString : lazyDexStrings) {
+        forcedStrings.add(lazyDexString.compute());
+      }
+      timing.end();
+
+      {
+        // Write the actual dex code.
+        TimingMerger merger =
+            timing.beginMerger("Write files", ThreadUtils.getNumberOfThreads(executorService));
+        Collection<Timing> timings =
+            ThreadUtils.processItemsWithResults(
+                virtualFiles,
+                virtualFile -> {
+                  Timing fileTiming = Timing.create("VirtualFile " + virtualFile.getId(), options);
+                  writeVirtualFile(virtualFile, fileTiming, forcedStrings);
+                  fileTiming.end();
+                  return fileTiming;
+                },
+                executorService);
+        merger.add(timings);
+        merger.end();
+      }
+
       // A consumer can manage the generated keep rules.
       if (options.desugaredLibraryKeepRuleConsumer != null && !desugaredLibraryCodeToKeep.isNop()) {
         assert !options.isDesugaredLibraryCompilation();
@@ -319,6 +342,51 @@
     }
   }
 
+  private void computeMarkerStrings(
+      Box<ProguardMapId> delayedProguardMapId, List<LazyDexString> lazyDexStrings) {
+    if (markers != null && !markers.isEmpty()) {
+      int firstNonLazyMarker = 0;
+      if (willComputeProguardMap()) {
+        firstNonLazyMarker++;
+        lazyDexStrings.add(
+            new LazyDexString() {
+
+              @Override
+              public DexString internalCompute() {
+                Marker marker = markers.get(0);
+                marker.setPgMapId(delayedProguardMapId.get().getId());
+                return marker.toDexString(appView.dexItemFactory());
+              }
+            });
+      }
+      markerStrings = new ArrayList<>(markers.size() - firstNonLazyMarker);
+      for (int i = firstNonLazyMarker; i < markers.size(); i++) {
+        markerStrings.add(markers.get(i).toDexString(appView.dexItemFactory()));
+      }
+    }
+  }
+
+  private void computeSourceFileString(
+      Box<ProguardMapId> delayedProguardMapId, List<LazyDexString> lazyDexStrings) {
+    if (options.sourceFileProvider == null) {
+      return;
+    }
+    if (!willComputeProguardMap()) {
+      rewriteSourceFile(null);
+      return;
+    }
+    // Clear all source files so as not to collect the original files.
+    appView.appInfo().classes().forEach(clazz -> clazz.setSourceFile(null));
+    // Add a lazy dex string computation to defer construction of the actual string.
+    lazyDexStrings.add(
+        new LazyDexString() {
+          @Override
+          public DexString internalCompute() {
+            return rewriteSourceFile(delayedProguardMapId.get());
+          }
+        });
+  }
+
   public static SourceFileEnvironment createSourceFileEnvironment(ProguardMapId proguardMapId) {
     if (proguardMapId == null) {
       return new SourceFileEnvironment() {
@@ -346,16 +414,37 @@
     };
   }
 
-  private void rewriteSourceFile(DexProgramClass clazz, SourceFileEnvironment environment) {
+  private DexString rewriteSourceFile(ProguardMapId proguardMapId) {
     assert options.sourceFileProvider != null;
+    SourceFileEnvironment environment = createSourceFileEnvironment(proguardMapId);
     String sourceFile = options.sourceFileProvider.get(environment);
-    clazz.setSourceFile(sourceFile == null ? null : options.itemFactory.createString(sourceFile));
+    DexString dexSourceFile =
+        sourceFile == null ? null : options.itemFactory.createString(sourceFile);
+    appView.appInfo().classes().forEach(clazz -> clazz.setSourceFile(dexSourceFile));
+    return dexSourceFile;
   }
 
-  private void writeVirtualFile(VirtualFile virtualFile, Timing timing) {
+  private void computeOffsetMappingAndRewriteJumboStrings(
+      VirtualFile virtualFile, List<LazyDexString> lazyDexStrings, Timing timing) {
     if (virtualFile.isEmpty()) {
       return;
     }
+    timing.begin("Compute object offset mapping");
+    virtualFile.computeMapping(
+        appView, graphLens, namingLens, initClassLens, lazyDexStrings.size(), timing);
+    timing.end();
+    timing.begin("Rewrite jumbo strings");
+    rewriteCodeWithJumboStrings(
+        virtualFile.getObjectMapping(), virtualFile.classes(), appView.appInfo().app());
+    timing.end();
+  }
+
+  private void writeVirtualFile(
+      VirtualFile virtualFile, Timing timing, List<DexString> forcedStrings) {
+    if (virtualFile.isEmpty()) {
+      return;
+    }
+
     ProgramConsumer consumer;
     ByteBufferProvider byteBufferProvider;
     if (programConsumer != null) {
@@ -375,16 +464,14 @@
         byteBufferProvider = options.getDexIndexedConsumer();
       }
     }
-    timing.begin("Compute object offset mapping");
-    ObjectToOffsetMapping objectMapping =
-        virtualFile.computeMapping(appView, graphLens, namingLens, initClassLens, timing);
+
+    timing.begin("Reindex for lazy strings");
+    ObjectToOffsetMapping objectMapping = virtualFile.getObjectMapping();
+    objectMapping.computeAndReindexForLazyDexStrings(forcedStrings);
     timing.end();
-    timing.begin("Rewrite jumbo strings");
-    MethodToCodeObjectMapping codeMapping =
-        rewriteCodeWithJumboStrings(objectMapping, virtualFile.classes(), appView.appInfo().app());
-    timing.end();
+
     timing.begin("Write bytes");
-    ByteBufferResult result = writeDexFile(objectMapping, codeMapping, byteBufferProvider);
+    ByteBufferResult result = writeDexFile(objectMapping, byteBufferProvider);
     ByteDataView data =
         new ByteDataView(result.buffer.array(), result.buffer.arrayOffset(), result.length);
     timing.end();
@@ -652,7 +739,7 @@
    * <p>If run multiple times on a class, the lowest index that is required to be a JumboString will
    * be used.
    */
-  private MethodToCodeObjectMapping rewriteCodeWithJumboStrings(
+  private void rewriteCodeWithJumboStrings(
       ObjectToOffsetMapping mapping,
       Collection<DexProgramClass> classes,
       DexApplication application) {
@@ -660,19 +747,14 @@
     if (!options.testing.forceJumboStringProcessing) {
       // If there are no strings with jumbo indices at all this is a no-op.
       if (!mapping.hasJumboStrings()) {
-        return MethodToCodeObjectMapping.fromMethodBacking();
+        return;
       }
       // If the globally highest sorting string is not a jumbo string this is also a no-op.
       if (application.highestSortingString != null
           && application.highestSortingString.compareTo(mapping.getFirstJumboString()) < 0) {
-        return MethodToCodeObjectMapping.fromMethodBacking();
+        return;
       }
     }
-    // At least one method needs a jumbo string in which case we construct a thread local mapping
-    // for all code objects and write the processed results into that map.
-    // TODO(b/181636450): Reconsider the code mapping setup now that synthetics are never duplicated
-    //  in outputs.
-    Map<DexEncodedMethod, DexWritableCode> codeMapping = new IdentityHashMap<>();
     for (DexProgramClass clazz : classes) {
       clazz.forEachProgramMethodMatching(
           DexEncodedMethod::hasCode,
@@ -684,25 +766,18 @@
                     mapping,
                     application.dexItemFactory,
                     options.testing.forceJumboStringProcessing);
-            codeMapping.put(method.getDefinition(), rewrittenCode);
-            // The mapping now has ownership of the methods code object. This ensures freeing of
-            // code resources once the map entry is cleared and also ensures that we don't end up
-            // using the incorrect code pointer again later!
-            method.getDefinition().unsetCode();
+            method.getDefinition().setCode(rewrittenCode.asCode(), appView);
           });
     }
-    return MethodToCodeObjectMapping.fromMapBacking(codeMapping);
   }
 
   private ByteBufferResult writeDexFile(
       ObjectToOffsetMapping objectMapping,
-      MethodToCodeObjectMapping codeMapping,
       ByteBufferProvider provider) {
     FileWriter fileWriter =
         new FileWriter(
             provider,
             objectMapping,
-            codeMapping,
             appView.appInfo(),
             options,
             namingLens,
@@ -729,4 +804,17 @@
         type -> builder.append(mapMainDexListName(type, namingLens)).append('\n'));
     return builder.toString();
   }
+
+  public abstract static class LazyDexString {
+    private boolean computed = false;
+
+    public abstract DexString internalCompute();
+
+    public final DexString compute() {
+      assert !computed;
+      DexString value = internalCompute();
+      computed = true;
+      return value;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/dex/FileWriter.java b/src/main/java/com/android/tools/r8/dex/FileWriter.java
index c937839..84b245c 100644
--- a/src/main/java/com/android/tools/r8/dex/FileWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/FileWriter.java
@@ -98,8 +98,6 @@
   }
 
   private final ObjectToOffsetMapping mapping;
-  private final MethodToCodeObjectMapping codeMapping;
-  private final AppInfo appInfo;
   private final DexApplication application;
   private final InternalOptions options;
   private final GraphLens graphLens;
@@ -112,20 +110,17 @@
   public FileWriter(
       ByteBufferProvider provider,
       ObjectToOffsetMapping mapping,
-      MethodToCodeObjectMapping codeMapping,
       AppInfo appInfo,
       InternalOptions options,
       NamingLens namingLens,
       CodeToKeep desugaredLibraryCodeToKeep) {
     this.mapping = mapping;
-    this.codeMapping = codeMapping;
-    this.appInfo = appInfo;
     this.application = appInfo.app();
     this.options = options;
     this.graphLens = mapping.getGraphLens();
     this.namingLens = namingLens;
     this.dest = new DexOutputBuffer(provider);
-    this.mixedSectionOffsets = new MixedSectionOffsets(options, codeMapping);
+    this.mixedSectionOffsets = new MixedSectionOffsets(options);
     this.desugaredLibraryCodeToKeep = desugaredLibraryCodeToKeep;
   }
 
@@ -179,9 +174,6 @@
     Layout layout = Layout.from(mapping);
     layout.setCodesOffset(layout.dataSectionOffset);
 
-    // Check code objects in the code-mapping are consistent with the collected code objects.
-    assert codeMapping.verifyCodeObjects(mixedSectionOffsets.getCodes());
-
     // Sort the codes first, as their order might impact size due to alignment constraints.
     List<ProgramDexCode> codes = sortDexCodesByClassName();
 
@@ -340,7 +332,7 @@
     for (DexProgramClass clazz : mapping.getClasses()) {
       clazz.forEachProgramMethod(
           method -> {
-            DexWritableCode code = codeMapping.getCode(method.getDefinition());
+            DexWritableCode code = method.getDefinition().getDexWritableCodeOrNull();
             assert code != null || method.getDefinition().shouldNotHaveCode();
             if (code != null) {
               ProgramDexCode programCode = new ProgramDexCode(code, method);
@@ -661,7 +653,7 @@
       dest.putUleb128(nextOffset - currentOffset);
       currentOffset = nextOffset;
       dest.putUleb128(method.accessFlags.getAsDexAccessFlags());
-      DexWritableCode code = codeMapping.getCode(method);
+      DexWritableCode code = method.getDexWritableCodeOrNull();
       desugaredLibraryCodeToKeep.recordMethod(method.getReference());
       if (code == null) {
         assert method.shouldNotHaveCode();
@@ -670,7 +662,7 @@
         dest.putUleb128(mixedSectionOffsets.getOffsetFor(method, code));
         // Writing the methods starts to take up memory so we are going to flush the
         // code objects since they are no longer necessary after this.
-        codeMapping.clearCode(method);
+        method.unsetCode();
       }
     }
   }
@@ -1077,8 +1069,6 @@
     private static final int NOT_SET = -1;
     private static final int NOT_KNOWN = -2;
 
-    private final MethodToCodeObjectMapping codeMapping;
-
     private final Reference2IntMap<DexEncodedMethod> codes = createReference2IntMap();
     private final Object2IntMap<DexDebugInfo> debugInfos = createObject2IntMap();
     private final Object2IntMap<DexTypeList> typeLists = createObject2IntMap();
@@ -1108,9 +1098,8 @@
       return result;
     }
 
-    private MixedSectionOffsets(InternalOptions options, MethodToCodeObjectMapping codeMapping) {
+    private MixedSectionOffsets(InternalOptions options) {
       this.minApiLevel = options.getMinApiLevel();
-      this.codeMapping = codeMapping;
     }
 
     private <T> boolean add(Object2IntMap<T> map, T item) {
@@ -1151,7 +1140,7 @@
 
     @Override
     public void visit(DexEncodedMethod method) {
-      method.collectMixedSectionItemsWithCodeMapping(this, codeMapping);
+      method.collectMixedSectionItemsWithCodeMapping(this);
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/dex/Marker.java b/src/main/java/com/android/tools/r8/dex/Marker.java
index 4770922..8d57a1c 100644
--- a/src/main/java/com/android/tools/r8/dex/Marker.java
+++ b/src/main/java/com/android/tools/r8/dex/Marker.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.errors.DesugaredLibraryMismatchDiagnostic;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.utils.Reporter;
 import com.android.tools.r8.utils.StringDiagnostic;
@@ -291,6 +292,10 @@
     return tool.hashCode() + 3 * jsonObject.hashCode();
   }
 
+  public DexString toDexString(DexItemFactory factory) {
+    return factory.createString(toString());
+  }
+
   // Try to parse str as a marker.
   // Returns null if parsing fails.
   public static Marker parse(DexString dexString) {
diff --git a/src/main/java/com/android/tools/r8/dex/MethodToCodeObjectMapping.java b/src/main/java/com/android/tools/r8/dex/MethodToCodeObjectMapping.java
deleted file mode 100644
index dfdb07a..0000000
--- a/src/main/java/com/android/tools/r8/dex/MethodToCodeObjectMapping.java
+++ /dev/null
@@ -1,81 +0,0 @@
-// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-package com.android.tools.r8.dex;
-
-import com.android.tools.r8.graph.Code;
-import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexWritableCode;
-import java.util.Collection;
-import java.util.List;
-import java.util.Map;
-import java.util.stream.Collectors;
-
-public abstract class MethodToCodeObjectMapping {
-
-  public abstract DexWritableCode getCode(DexEncodedMethod method);
-
-  public abstract void clearCode(DexEncodedMethod method);
-
-  public abstract boolean verifyCodeObjects(Collection<DexEncodedMethod> codes);
-
-  public static MethodToCodeObjectMapping fromMethodBacking() {
-    return MethodBacking.INSTANCE;
-  }
-
-  public static MethodToCodeObjectMapping fromMapBacking(
-      Map<DexEncodedMethod, DexWritableCode> map) {
-    return new MapBacking(map);
-  }
-
-  private static class MethodBacking extends MethodToCodeObjectMapping {
-
-    private static final MethodBacking INSTANCE = new MethodBacking();
-
-    @Override
-    public DexWritableCode getCode(DexEncodedMethod method) {
-      Code code = method.getCode();
-      assert code == null || code.isDexWritableCode();
-      return code == null ? null : code.asDexWritableCode();
-    }
-
-    @Override
-    public void clearCode(DexEncodedMethod method) {
-      method.unsetCode();
-    }
-
-    @Override
-    public boolean verifyCodeObjects(Collection<DexEncodedMethod> codes) {
-      return true;
-    }
-  }
-
-  private static class MapBacking extends MethodToCodeObjectMapping {
-
-    private final Map<DexEncodedMethod, DexWritableCode> codes;
-
-    public MapBacking(Map<DexEncodedMethod, DexWritableCode> codes) {
-      this.codes = codes;
-    }
-
-    @Override
-    public DexWritableCode getCode(DexEncodedMethod method) {
-      return codes.get(method);
-    }
-
-    @Override
-    public void clearCode(DexEncodedMethod method) {
-      // We can safely clear the thread local pointer to even shared methods.
-      codes.put(method, null);
-    }
-
-    @Override
-    public boolean verifyCodeObjects(Collection<DexEncodedMethod> methods) {
-      // TODO(b/204056443): Convert to a Set<DexWritableCode> when DexCode#hashCode() works.
-      List<DexWritableCode> codes =
-          methods.stream().map(this::getCode).collect(Collectors.toList());
-      assert this.codes.values().containsAll(codes);
-      return true;
-    }
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/dex/MixedSectionCollection.java b/src/main/java/com/android/tools/r8/dex/MixedSectionCollection.java
index 0ca695e..e082a31 100644
--- a/src/main/java/com/android/tools/r8/dex/MixedSectionCollection.java
+++ b/src/main/java/com/android/tools/r8/dex/MixedSectionCollection.java
@@ -59,8 +59,7 @@
    * <p>Allows overriding the behavior when dex-file writing.
    */
   public void visit(DexEncodedMethod dexEncodedMethod) {
-    dexEncodedMethod.collectMixedSectionItemsWithCodeMapping(
-        this, MethodToCodeObjectMapping.fromMethodBacking());
+    dexEncodedMethod.collectMixedSectionItemsWithCodeMapping(this);
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/dex/VirtualFile.java b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
index 072fab7..e7c7a1d 100644
--- a/src/main/java/com/android/tools/r8/dex/VirtualFile.java
+++ b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
@@ -209,28 +209,39 @@
     return prefix;
   }
 
-  public ObjectToOffsetMapping computeMapping(
+  private ObjectToOffsetMapping objectMapping = null;
+
+  public ObjectToOffsetMapping getObjectMapping() {
+    assert objectMapping != null;
+    return objectMapping;
+  }
+
+  public void computeMapping(
       AppView<?> appView,
       GraphLens graphLens,
       NamingLens namingLens,
       InitClassLens initClassLens,
+      int lazyDexStringsCount,
       Timing timing) {
     assert transaction.isEmpty();
-    return new ObjectToOffsetMapping(
-        appView,
-        graphLens,
-        namingLens,
-        initClassLens,
-        transaction.rewriter,
-        indexedItems.classes,
-        indexedItems.protos,
-        indexedItems.types,
-        indexedItems.methods,
-        indexedItems.fields,
-        indexedItems.strings,
-        indexedItems.callSites,
-        indexedItems.methodHandles,
-        timing);
+    assert objectMapping == null;
+    objectMapping =
+        new ObjectToOffsetMapping(
+            appView,
+            graphLens,
+            namingLens,
+            initClassLens,
+            transaction.rewriter,
+            indexedItems.classes,
+            indexedItems.protos,
+            indexedItems.types,
+            indexedItems.methods,
+            indexedItems.fields,
+            indexedItems.strings,
+            indexedItems.callSites,
+            indexedItems.methodHandles,
+            lazyDexStringsCount,
+            timing);
   }
 
   void addClass(DexProgramClass clazz) {
diff --git a/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java b/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java
index f336d89..e25cb47 100644
--- a/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java
+++ b/src/main/java/com/android/tools/r8/graph/DefaultInstanceInitializerCode.java
@@ -123,6 +123,11 @@
   }
 
   @Override
+  public Code asCode() {
+    return this;
+  }
+
+  @Override
   public void acceptHashing(HashingVisitor visitor) {
     visitor.visitInt(getCfWritableCodeKind().hashCode());
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexCode.java b/src/main/java/com/android/tools/r8/graph/DexCode.java
index d49c43f..703977e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexCode.java
+++ b/src/main/java/com/android/tools/r8/graph/DexCode.java
@@ -351,6 +351,11 @@
   }
 
   @Override
+  public Code asCode() {
+    return this;
+  }
+
+  @Override
   public IRCode buildIR(ProgramMethod method, AppView<?> appView, Origin origin) {
     DexSourceCode source =
         new DexSourceCode(
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 a68f038..2a9e275 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -38,7 +38,6 @@
 import com.android.tools.r8.code.Return;
 import com.android.tools.r8.code.Throw;
 import com.android.tools.r8.code.XorIntLit8;
-import com.android.tools.r8.dex.MethodToCodeObjectMapping;
 import com.android.tools.r8.dex.MixedSectionCollection;
 import com.android.tools.r8.errors.InternalCompilerError;
 import com.android.tools.r8.errors.Unreachable;
@@ -286,7 +285,6 @@
         .withBool(DexEncodedMember::isD8R8Synthesized)
         // TODO(b/171867022): Make signatures structural and include it in the definition.
         .withAssert(m -> m.genericSignature.hasNoSignature())
-        .withAssert(DexEncodedMethod::hasCode)
         .withCustomItem(
             DexEncodedMethod::getCode,
             DexEncodedMethod::compareCodeObject,
@@ -294,6 +292,13 @@
   }
 
   private static int compareCodeObject(Code code1, Code code2, CompareToVisitor visitor) {
+    if (code1 == code2) {
+      return 0;
+    }
+    if (code1 == null || code2 == null) {
+      // This call is to remain order consistent with the 'withNullableItem' code.
+      return visitor.visitBool(code1 != null, code2 != null);
+    }
     if (code1.isCfWritableCode() && code2.isCfWritableCode()) {
       return code1.asCfWritableCode().acceptCompareTo(code2.asCfWritableCode(), visitor);
     }
@@ -305,7 +310,10 @@
   }
 
   private static void hashCodeObject(Code code, HashingVisitor visitor) {
-    if (code.isCfWritableCode()) {
+    if (code == null) {
+      // The null code does not contribute to the hash. This should be distinct from non-null as
+      // code otherwise has a non-empty instruction payload.
+    } else if (code.isCfWritableCode()) {
       code.asCfWritableCode().acceptHashing(visitor);
     } else {
       assert code.isDexWritableCode();
@@ -768,9 +776,8 @@
     mixedItems.visit(this);
   }
 
-  public void collectMixedSectionItemsWithCodeMapping(
-      MixedSectionCollection mixedItems, MethodToCodeObjectMapping mapping) {
-    DexWritableCode code = mapping.getCode(this);
+  public void collectMixedSectionItemsWithCodeMapping(MixedSectionCollection mixedItems) {
+    DexWritableCode code = getDexWritableCodeOrNull();
     if (code != null && mixedItems.add(this, code)) {
       code.collectMixedSectionItems(mixedItems);
     }
@@ -1315,6 +1322,12 @@
     this.genericSignature = MethodTypeSignature.noSignature();
   }
 
+  public DexWritableCode getDexWritableCodeOrNull() {
+    Code code = getCode();
+    assert code == null || code.isDexWritableCode();
+    return code == null ? null : code.asDexWritableCode();
+  }
+
   public static Builder syntheticBuilder() {
     return new Builder(true);
   }
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 4879d46..c108238 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -2582,6 +2582,10 @@
     return prependTypeToProto(method.holder, method.proto);
   }
 
+  public DexProto prependHolderToProtoIf(DexMethod method, boolean condition) {
+    return condition ? prependHolderToProto(method) : method.getProto();
+  }
+
   public DexProto prependTypeToProto(DexType extraFirstType, DexProto initialProto) {
     DexType[] parameterTypes = new DexType[initialProto.parameters.size() + 1];
     parameterTypes[0] = extraFirstType;
diff --git a/src/main/java/com/android/tools/r8/graph/DexWritableCode.java b/src/main/java/com/android/tools/r8/graph/DexWritableCode.java
index 664b4e8..fffff66 100644
--- a/src/main/java/com/android/tools/r8/graph/DexWritableCode.java
+++ b/src/main/java/com/android/tools/r8/graph/DexWritableCode.java
@@ -71,6 +71,8 @@
 
   int getOutgoingRegisterSize();
 
+  Code asCode();
+
   default boolean isDexCode() {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java b/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java
index 04b3eb0..fcdafdd 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.ir.conversion.LensCodeRewriterUtils;
 import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.Box;
 import com.android.tools.r8.utils.Timing;
 import com.android.tools.r8.utils.structural.CompareToVisitor;
 import com.android.tools.r8.utils.structural.CompareToVisitorWithStringTable;
@@ -29,6 +30,7 @@
   private final static int NOT_FOUND = -1;
   private final static int NOT_SET = -2;
 
+  private final int lazyDexStringsCount;
   private final AppView<?> appView;
   private final GraphLens graphLens;
   private final NamingLens namingLens;
@@ -41,7 +43,8 @@
   private final Reference2IntLinkedOpenHashMap<DexType> types;
   private final Reference2IntLinkedOpenHashMap<DexMethod> methods;
   private final Reference2IntLinkedOpenHashMap<DexField> fields;
-  private final Reference2IntLinkedOpenHashMap<DexString> strings;
+  // Non-final to support (order consistent) reindexing in case of lazy computed strings.
+  private Reference2IntLinkedOpenHashMap<DexString> strings;
   private final Reference2IntLinkedOpenHashMap<DexCallSite> callSites;
   private final Reference2IntLinkedOpenHashMap<DexMethodHandle> methodHandles;
 
@@ -63,6 +66,7 @@
       Collection<DexString> strings,
       Collection<DexCallSite> callSites,
       Collection<DexMethodHandle> methodHandles,
+      int lazyDexStringsCount,
       Timing timing) {
     assert appView != null;
     assert graphLens != null;
@@ -75,13 +79,16 @@
     assert callSites != null;
     assert methodHandles != null;
     assert initClassLens != null;
+    this.lazyDexStringsCount = lazyDexStringsCount;
     this.appView = appView;
     this.graphLens = graphLens;
     this.namingLens = namingLens;
     this.initClassLens = initClassLens;
     this.lensCodeRewriter = lensCodeRewriter;
     timing.begin("Sort strings");
-    this.strings = createSortedMap(strings, DexString::compareTo, this::setFirstJumboString);
+    this.strings =
+        createSortedMap(
+            strings, DexString::compareTo, this::setFirstJumboString, lazyDexStringsCount);
     CompareToVisitor visitor =
         new CompareToVisitorWithStringTable(namingLens, this.strings::getInt);
     timing.end();
@@ -126,6 +133,27 @@
         };
   }
 
+  public void computeAndReindexForLazyDexStrings(List<DexString> forcedStrings) {
+    assert lazyDexStringsCount == forcedStrings.size();
+    if (forcedStrings.isEmpty()) {
+      return;
+    }
+    // If there are any lazy strings we need to recompute the offsets, even if the strings
+    // are already in the set as we have shifted the initial offset by the size of lazy strings.
+    for (DexString forcedString : forcedStrings) {
+      // Amend the string table to ensure all strings are now present.
+      if (forcedString != null) {
+        strings.put(forcedString, -1);
+      }
+    }
+    Box<DexString> newJumboString = new Box<>();
+    strings = createSortedMap(strings.keySet(), DexString::compareTo, newJumboString::set);
+    // After reindexing it must hold that the new jumbo start is on the same or a larger string.
+    // The new jumbo string is not set as the first determined string is still the cut-off point
+    // where JumboString instructions are used.
+    assert !hasJumboStrings() || newJumboString.get().isGreaterThanOrEqualTo(getFirstJumboString());
+  }
+
   public CompareToVisitor getCompareToVisitor() {
     return compareToVisitor;
   }
@@ -145,6 +173,14 @@
 
   private <T> Reference2IntLinkedOpenHashMap<T> createSortedMap(
       Collection<T> items, Comparator<T> comparator, Consumer<T> onUInt16Overflow) {
+    return createSortedMap(items, comparator, onUInt16Overflow, 0);
+  }
+
+  private <T> Reference2IntLinkedOpenHashMap<T> createSortedMap(
+      Collection<T> items,
+      Comparator<T> comparator,
+      Consumer<T> onUInt16Overflow,
+      int reservedIndicesBeforeOverflow) {
     if (items.isEmpty()) {
       return new Reference2IntLinkedOpenHashMap<>();
     }
@@ -155,7 +191,7 @@
     map.defaultReturnValue(NOT_FOUND);
     int index = 0;
     for (T item : sorted) {
-      if (index == Constants.U16BIT_MAX + 1) {
+      if (index + reservedIndicesBeforeOverflow == Constants.U16BIT_MAX + 1) {
         onUInt16Overflow.accept(item);
       }
       map.put(item, index++);
diff --git a/src/main/java/com/android/tools/r8/graph/ThrowNullCode.java b/src/main/java/com/android/tools/r8/graph/ThrowNullCode.java
index eb7728c..c573130 100644
--- a/src/main/java/com/android/tools/r8/graph/ThrowNullCode.java
+++ b/src/main/java/com/android/tools/r8/graph/ThrowNullCode.java
@@ -41,6 +41,11 @@
   }
 
   @Override
+  public Code asCode() {
+    return this;
+  }
+
+  @Override
   public void acceptHashing(HashingVisitor visitor) {
     visitor.visitInt(getCfWritableCodeKind().hashCode());
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicTypeWithUpperBound.java b/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicTypeWithUpperBound.java
index fa985fa..0ce069a 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicTypeWithUpperBound.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/DynamicTypeWithUpperBound.java
@@ -235,11 +235,21 @@
         return hasDynamicLowerBoundType();
       }
       return hasDynamicLowerBoundType()
-          && getDynamicLowerBoundType()
-              .strictlyLessThan(dynamicType.getDynamicLowerBoundType(), appView);
+          && dynamicType
+              .getDynamicLowerBoundType()
+              .strictlyLessThan(getDynamicLowerBoundType(), appView);
     }
-    return getDynamicUpperBoundType()
-        .strictlyLessThan(dynamicType.getDynamicUpperBoundType(), appView);
+    if (!getDynamicUpperBoundType()
+        .strictlyLessThan(dynamicType.getDynamicUpperBoundType(), appView)) {
+      return false;
+    }
+    if (!dynamicType.hasDynamicLowerBoundType()) {
+      return true;
+    }
+    return hasDynamicLowerBoundType()
+        && dynamicType
+            .getDynamicLowerBoundType()
+            .lessThanOrEqualUpToNullability(getDynamicUpperBoundType(), appView);
   }
 
   @Override
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 047894d..1250ada 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
@@ -204,6 +204,7 @@
             .map(prefix -> "L" + DescriptorUtils.getPackageBinaryNameFromJavaType(prefix))
             .map(options.itemFactory::createString)
             .collect(Collectors.toList());
+    AndroidApiLevelCompute apiLevelCompute = AndroidApiLevelCompute.create(appView);
     if (options.isDesugaredLibraryCompilation()) {
       // Specific L8 Settings, performs all desugaring including L8 specific desugaring.
       //
@@ -221,7 +222,8 @@
       // - nest based access desugaring,
       // - invoke-special desugaring.
       assert options.desugarState.isOn();
-      this.instructionDesugaring = CfInstructionDesugaringCollection.create(appView);
+      this.instructionDesugaring =
+          CfInstructionDesugaringCollection.create(appView, apiLevelCompute);
       this.covariantReturnTypeAnnotationTransformer = null;
       this.dynamicTypeOptimization = null;
       this.classInliner = null;
@@ -246,7 +248,7 @@
     this.instructionDesugaring =
         appView.enableWholeProgramOptimizations()
             ? CfInstructionDesugaringCollection.empty()
-            : CfInstructionDesugaringCollection.create(appView);
+            : CfInstructionDesugaringCollection.create(appView, apiLevelCompute);
     this.covariantReturnTypeAnnotationTransformer =
         options.processCovariantReturnTypeAnnotations
             ? new CovariantReturnTypeAnnotationTransformer(this, appView.dexItemFactory())
@@ -285,8 +287,7 @@
       this.typeChecker = new TypeChecker(appViewWithLiveness, VerifyTypesHelper.create(appView));
       this.serviceLoaderRewriter =
           options.enableServiceLoaderRewriting
-              ? new ServiceLoaderRewriter(
-                  appViewWithLiveness, AndroidApiLevelCompute.create(appView))
+              ? new ServiceLoaderRewriter(appViewWithLiveness, apiLevelCompute)
               : null;
       this.enumValueOptimizer =
           options.enableEnumValueOptimization ? new EnumValueOptimizer(appViewWithLiveness) : null;
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java
index b34a515..2257925 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.ir.desugar;
 
+import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
 import com.android.tools.r8.graph.AppView;
@@ -27,9 +28,10 @@
  */
 public abstract class CfInstructionDesugaringCollection {
 
-  public static CfInstructionDesugaringCollection create(AppView<?> appView) {
+  public static CfInstructionDesugaringCollection create(
+      AppView<?> appView, AndroidApiLevelCompute apiLevelCompute) {
     if (appView.options().desugarState.isOn()) {
-      return new NonEmptyCfInstructionDesugaringCollection(appView);
+      return new NonEmptyCfInstructionDesugaringCollection(appView, apiLevelCompute);
     }
     // TODO(b/145775365): invoke-special desugaring is mandatory, since we currently can't map
     //  invoke-special instructions that require desugaring into IR.
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java b/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java
index bc5c0fa..f722159 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java
@@ -4,6 +4,9 @@
 
 package com.android.tools.r8.ir.desugar;
 
+import static com.android.tools.r8.androidapi.AndroidApiLevelCompute.noAndroidApiLevelCompute;
+
+import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
 import com.android.tools.r8.errors.Unreachable;
@@ -11,6 +14,7 @@
 import com.android.tools.r8.graph.CfCode;
 import com.android.tools.r8.graph.Code;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.desugar.apimodel.ApiInvokeOutlinerDesugaring;
 import com.android.tools.r8.ir.desugar.constantdynamic.ConstantDynamicInstructionDesugaring;
 import com.android.tools.r8.ir.desugar.desugaredlibrary.DesugaredLibraryAPIConverter;
 import com.android.tools.r8.ir.desugar.desugaredlibrary.DesugaredLibraryRetargeter;
@@ -51,9 +55,12 @@
   private final DesugaredLibraryRetargeter desugaredLibraryRetargeter;
   private final InterfaceMethodRewriter interfaceMethodRewriter;
   private final DesugaredLibraryAPIConverter desugaredLibraryAPIConverter;
+  private final AndroidApiLevelCompute apiLevelCompute;
 
-  NonEmptyCfInstructionDesugaringCollection(AppView<?> appView) {
+  NonEmptyCfInstructionDesugaringCollection(
+      AppView<?> appView, AndroidApiLevelCompute apiLevelCompute) {
     this.appView = appView;
+    this.apiLevelCompute = apiLevelCompute;
     AlwaysThrowingInstructionDesugaring alwaysThrowingInstructionDesugaring =
         appView.enableWholeProgramOptimizations()
             ? new AlwaysThrowingInstructionDesugaring(appView.withClassHierarchy())
@@ -81,6 +88,9 @@
     if (appView.options().enableBackportedMethodRewriting()) {
       backportedMethodRewriter = new BackportedMethodRewriter(appView);
     }
+    if (appView.options().apiModelingOptions().enableOutliningOfMethods) {
+      desugarings.add(new ApiInvokeOutlinerDesugaring(appView, apiLevelCompute));
+    }
     if (appView.options().enableTryWithResourcesDesugaring()) {
       desugarings.add(new TwrInstructionDesugaring(appView));
     }
@@ -131,7 +141,7 @@
     assert appView.options().desugarState.isOff();
     assert appView.options().isGeneratingClassFiles();
     NonEmptyCfInstructionDesugaringCollection desugaringCollection =
-        new NonEmptyCfInstructionDesugaringCollection(appView);
+        new NonEmptyCfInstructionDesugaringCollection(appView, noAndroidApiLevelCompute());
     // TODO(b/145775365): special constructor for cf-to-cf compilations with desugaring disabled.
     //  This should be removed once we can represent invoke-special instructions in the IR.
     desugaringCollection.desugarings.add(new InvokeSpecialToSelfDesugaring(appView));
@@ -142,7 +152,7 @@
     assert appView.options().desugarState.isOff();
     assert appView.options().isGeneratingDex();
     NonEmptyCfInstructionDesugaringCollection desugaringCollection =
-        new NonEmptyCfInstructionDesugaringCollection(appView);
+        new NonEmptyCfInstructionDesugaringCollection(appView, noAndroidApiLevelCompute());
     desugaringCollection.desugarings.add(new InvokeSpecialToSelfDesugaring(appView));
     desugaringCollection.desugarings.add(new InvokeToPrivateRewriter());
     return desugaringCollection;
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java b/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
new file mode 100644
index 0000000..62c0445
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/desugar/apimodel/ApiInvokeOutlinerDesugaring.java
@@ -0,0 +1,162 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.desugar.apimodel;
+
+import static org.objectweb.asm.Opcodes.INVOKESTATIC;
+
+import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
+import com.android.tools.r8.androidapi.ComputedApiLevel;
+import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.cf.code.CfInvoke;
+import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
+import com.android.tools.r8.contexts.CompilationContext.UniqueContext;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProto;
+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.desugar.CfInstructionDesugaring;
+import com.android.tools.r8.ir.desugar.CfInstructionDesugaringCollection;
+import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer;
+import com.android.tools.r8.ir.desugar.FreshLocalProvider;
+import com.android.tools.r8.ir.desugar.LocalStackAllocator;
+import com.android.tools.r8.ir.synthetic.ForwardMethodBuilder;
+import com.android.tools.r8.synthesis.SyntheticNaming.SyntheticKind;
+import com.google.common.collect.ImmutableList;
+import java.util.Collection;
+
+public class ApiInvokeOutlinerDesugaring implements CfInstructionDesugaring {
+
+  private final AppView<?> appView;
+  private final AndroidApiLevelCompute apiLevelCompute;
+
+  public ApiInvokeOutlinerDesugaring(AppView<?> appView, AndroidApiLevelCompute apiLevelCompute) {
+    this.appView = appView;
+    this.apiLevelCompute = apiLevelCompute;
+  }
+
+  @Override
+  public Collection<CfInstruction> desugarInstruction(
+      CfInstruction instruction,
+      FreshLocalProvider freshLocalProvider,
+      LocalStackAllocator localStackAllocator,
+      CfInstructionDesugaringEventConsumer eventConsumer,
+      ProgramMethod context,
+      MethodProcessingContext methodProcessingContext,
+      CfInstructionDesugaringCollection desugaringCollection,
+      DexItemFactory dexItemFactory) {
+    ComputedApiLevel computedApiLevel = getComputedApiLevelForMethodOnHolderWithMinApi(instruction);
+    if (computedApiLevel.isGreaterThan(appView.computedMinApiLevel())) {
+      return desugarLibraryCall(
+          methodProcessingContext.createUniqueContext(),
+          instruction,
+          computedApiLevel,
+          dexItemFactory);
+    }
+    return null;
+  }
+
+  @Override
+  public boolean needsDesugaring(CfInstruction instruction, ProgramMethod context) {
+    if (context.getDefinition().isD8R8Synthesized()) {
+      return false;
+    }
+    return getComputedApiLevelForMethodOnHolderWithMinApi(instruction)
+        .isGreaterThan(appView.computedMinApiLevel());
+  }
+
+  private ComputedApiLevel getComputedApiLevelForMethodOnHolderWithMinApi(
+      CfInstruction instruction) {
+    if (!instruction.isInvoke()) {
+      return appView.computedMinApiLevel();
+    }
+    CfInvoke cfInvoke = instruction.asInvoke();
+    if (cfInvoke.isInvokeSpecial()) {
+      return appView.computedMinApiLevel();
+    }
+    DexType holderType = cfInvoke.getMethod().getHolderType();
+    if (!holderType.isClassType()) {
+      return appView.computedMinApiLevel();
+    }
+    DexClass clazz = appView.definitionFor(holderType);
+    if (clazz == null || !clazz.isLibraryClass()) {
+      return appView.computedMinApiLevel();
+    }
+    ComputedApiLevel apiLevel =
+        apiLevelCompute.computeApiLevelForLibraryReference(
+            cfInvoke.getMethod(), ComputedApiLevel.unknown());
+    if (apiLevel.isGreaterThan(appView.computedMinApiLevel())) {
+      ComputedApiLevel holderApiLevel =
+          apiLevelCompute.computeApiLevelForLibraryReference(
+              holderType, ComputedApiLevel.unknown());
+      if (holderApiLevel.isGreaterThan(appView.computedMinApiLevel())) {
+        // Do not outline where the holder is unknown or introduced later then min api.
+        // TODO(b/208978971): Describe where mocking is done when landing.
+        return appView.computedMinApiLevel();
+      }
+      return apiLevel;
+    }
+    return appView.computedMinApiLevel();
+  }
+
+  private Collection<CfInstruction> desugarLibraryCall(
+      UniqueContext context,
+      CfInstruction instruction,
+      ComputedApiLevel computedApiLevel,
+      DexItemFactory factory) {
+    DexMethod method = instruction.asInvoke().getMethod();
+    ProgramMethod programMethod = ensureOutlineMethod(context, method, computedApiLevel, factory);
+    return ImmutableList.of(new CfInvoke(INVOKESTATIC, programMethod.getReference(), false));
+  }
+
+  private ProgramMethod ensureOutlineMethod(
+      UniqueContext context,
+      DexMethod apiMethod,
+      ComputedApiLevel apiLevel,
+      DexItemFactory factory) {
+    DexClass libraryHolder = appView.definitionFor(apiMethod.getHolderType());
+    assert libraryHolder != null;
+    DexEncodedMethod libraryApiMethodDefinition = libraryHolder.lookupMethod(apiMethod);
+    DexProto proto =
+        factory.prependHolderToProtoIf(apiMethod, libraryApiMethodDefinition.isVirtualMethod());
+    return appView
+        .getSyntheticItems()
+        .createMethod(
+            SyntheticKind.API_MODEL_OUTLINE,
+            context,
+            appView,
+            syntheticMethodBuilder -> {
+              syntheticMethodBuilder
+                  .setProto(proto)
+                  .setAccessFlags(
+                      MethodAccessFlags.builder()
+                          .setPublic()
+                          .setSynthetic()
+                          .setStatic()
+                          .setBridge()
+                          .build())
+                  .setApiLevelForDefinition(apiLevel)
+                  .setApiLevelForCode(apiLevel)
+                  .setCode(
+                      m -> {
+                        if (libraryApiMethodDefinition.isStatic()) {
+                          return ForwardMethodBuilder.builder(factory)
+                              .setStaticTarget(apiMethod, libraryHolder.isInterface())
+                              .setStaticSource(apiMethod)
+                              .build();
+                        } else {
+                          return ForwardMethodBuilder.builder(factory)
+                              .setVirtualTarget(apiMethod, libraryHolder.isInterface())
+                              .setNonStaticSource(apiMethod)
+                              .build();
+                        }
+                      });
+            });
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/DesugaredLibraryRetargeter.java b/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/DesugaredLibraryRetargeter.java
index 5c6d6c1..01c504c 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/DesugaredLibraryRetargeter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/DesugaredLibraryRetargeter.java
@@ -128,6 +128,13 @@
     if (retargetLibraryMember.isEmpty() || !instruction.isInvoke()) {
       return NO_REWRITING;
     }
+    if (appView
+        .options()
+        .desugaredLibraryConfiguration
+        .getDontRetargetLibMember()
+        .contains(context.getContextType())) {
+      return NO_REWRITING;
+    }
     CfInvoke cfInvoke = instruction.asInvoke();
     DexMethod invokedMethod = cfInvoke.getMethod();
     InvokeRetargetingResult retarget =
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/itf/EmulatedInterfaceApplicationRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/itf/EmulatedInterfaceApplicationRewriter.java
index b2308ae..af7fb9f 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/itf/EmulatedInterfaceApplicationRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/itf/EmulatedInterfaceApplicationRewriter.java
@@ -5,7 +5,6 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
-import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -15,9 +14,7 @@
 import com.android.tools.r8.graph.GenericSignature.ClassSignature;
 import com.android.tools.r8.utils.IterableUtils;
 import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.Collections;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 
@@ -38,11 +35,6 @@
     for (DexProgramClass clazz : builder.getProgramClasses()) {
       if (emulatedInterfaces.containsKey(clazz.type)) {
         newProgramClasses.add(rewriteEmulatedInterface(clazz));
-      } else if (clazz.isInterface()
-          && !appView.rewritePrefix.hasRewrittenType(clazz.type, appView)
-          && isEmulatedInterfaceSubInterface(clazz)) {
-        // Intentionally filter such classes out.
-        handleEmulatedInterfaceSubInterface(clazz);
       } else {
         newProgramClasses.add(clazz);
       }
@@ -50,38 +42,6 @@
     builder.replaceProgramClasses(newProgramClasses);
   }
 
-  private void handleEmulatedInterfaceSubInterface(DexProgramClass clazz) {
-    // TODO(b/183918843): Investigate how to specify these in the json file.
-    // These are interfaces which needs a companion class for desugared library to work, but
-    // the interface is not supported outside of desugared library. The interface has to be
-    // present during the compilation for the companion class to be generated, but filtered out
-    // afterwards. The companion class needs to be rewritten to have the desugared library
-    // prefix since all classes in desugared library should have the prefix, we used the
-    // questionable method convertJavaNameToDesugaredLibrary to generate a correct type.
-    String newName =
-        appView
-            .options()
-            .desugaredLibraryConfiguration
-            .convertJavaNameToDesugaredLibrary(clazz.type);
-    InterfaceMethodRewriter.addCompanionClassRewriteRule(clazz.type, newName, appView);
-  }
-
-  private boolean isEmulatedInterfaceSubInterface(DexClass subInterface) {
-    assert !emulatedInterfaces.containsKey(subInterface.type);
-    LinkedList<DexType> workList = new LinkedList<>(Arrays.asList(subInterface.interfaces.values));
-    while (!workList.isEmpty()) {
-      DexType next = workList.removeFirst();
-      if (emulatedInterfaces.containsKey(next)) {
-        return true;
-      }
-      DexClass nextClass = appView.definitionFor(next);
-      if (nextClass != null) {
-        workList.addAll(Arrays.asList(nextClass.interfaces.values));
-      }
-    }
-    return false;
-  }
-
   // The method transforms emulated interface such as they now have the rewritten type and
   // implement the rewritten version of each emulated interface they implement.
   private DexProgramClass rewriteEmulatedInterface(DexProgramClass emulatedInterface) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
index ca6c387..27a4893 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
@@ -126,8 +126,8 @@
         if (current.isInvokeSuper()) {
           InvokeSuper invoke = current.asInvokeSuper();
 
-          // Check if the instruction can be rewritten to invoke-super. This allows inlining of the
-          // enclosing method into contexts outside the current class.
+          // Check if the instruction can be rewritten to invoke-virtual. This allows inlining of
+          // the enclosing method into contexts outside the current class.
           if (options.testing.enableInvokeSuperToInvokeVirtualRewriting) {
             DexClassAndMethod singleTarget = invoke.lookupSingleTarget(appView, context);
             if (singleTarget != null) {
@@ -150,16 +150,19 @@
 
           // Rebind the invoke to the most specific target.
           DexMethod invokedMethod = invoke.getInvokedMethod();
-          DexClassAndMethod reboundTarget = rebindSuperInvokeToMostSpecific(invokedMethod, context);
-          if (reboundTarget != null
-              && reboundTarget.getReference() != invokedMethod
-              && !isRebindingNewClassIntoMainDex(context, reboundTarget.getReference())) {
-            it.replaceCurrentInstruction(
-                new InvokeSuper(
-                    reboundTarget.getReference(),
-                    invoke.outValue(),
-                    invoke.arguments(),
-                    reboundTarget.getHolder().isInterface()));
+          DexClass reboundTargetClass = rebindSuperInvokeToMostSpecific(invokedMethod, context);
+          if (reboundTargetClass != null) {
+            DexMethod reboundMethod =
+                invokedMethod.withHolder(reboundTargetClass, appView.dexItemFactory());
+            if (reboundMethod != invokedMethod
+                && !isRebindingNewClassIntoMainDex(context, reboundMethod)) {
+              it.replaceCurrentInstruction(
+                  new InvokeSuper(
+                      reboundMethod,
+                      invoke.outValue(),
+                      invoke.arguments(),
+                      reboundTargetClass.isInterface()));
+            }
           }
           continue;
         }
@@ -318,8 +321,7 @@
   }
 
   /** This rebinds invoke-super instructions to their most specific target. */
-  private DexClassAndMethod rebindSuperInvokeToMostSpecific(
-      DexMethod target, ProgramMethod context) {
+  private DexClass rebindSuperInvokeToMostSpecific(DexMethod target, ProgramMethod context) {
     DexClassAndMethod method = appView.appInfo().lookupSuperTarget(target, context);
     if (method == null) {
       return null;
@@ -336,7 +338,20 @@
       return null;
     }
 
-    return method;
+    if (method.getHolder().isLibraryClass()) {
+      // We've found a library class as the new holder of the method. Since the library can only
+      // rebind to the library class boundary. Search from the target upwards until we find a
+      // library class.
+      DexClass lowerBound = appView.definitionFor(target.getHolderType(), context);
+      while (lowerBound != null
+          && lowerBound.isProgramClass()
+          && lowerBound != method.getHolder()) {
+        lowerBound = appView.definitionFor(lowerBound.superType, lowerBound.asProgramClass());
+      }
+      return lowerBound;
+    }
+
+    return method.getHolder();
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/ForwardMethodBuilder.java b/src/main/java/com/android/tools/r8/ir/synthetic/ForwardMethodBuilder.java
index 4a24a4b..90065e6 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/ForwardMethodBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/ForwardMethodBuilder.java
@@ -37,7 +37,8 @@
   private enum InvokeType {
     STATIC,
     VIRTUAL,
-    SPECIAL
+    INTERFACE,
+    SPECIAL,
   }
 
   private final DexItemFactory factory;
@@ -115,7 +116,7 @@
 
   public ForwardMethodBuilder setVirtualTarget(DexMethod method, boolean isInterface) {
     targetMethod = method;
-    invokeType = InvokeType.VIRTUAL;
+    invokeType = isInterface ? InvokeType.INTERFACE : InvokeType.VIRTUAL;
     this.isInterface = isInterface;
     return this;
   }
@@ -243,6 +244,8 @@
         return Opcodes.INVOKEVIRTUAL;
       case SPECIAL:
         return Opcodes.INVOKESPECIAL;
+      case INTERFACE:
+        return Opcodes.INVOKEINTERFACE;
     }
     throw new Unreachable("Unexpected invoke type: " + invokeType);
   }
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 2121adc..351815d 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -502,7 +502,7 @@
     liveFields = new LiveFieldsSet(graphReporter::registerField);
     apiLevelCompute = AndroidApiLevelCompute.create(appView);
     if (mode.isInitialTreeShaking()) {
-      desugaring = CfInstructionDesugaringCollection.create(appView);
+      desugaring = CfInstructionDesugaringCollection.create(appView, apiLevelCompute);
       interfaceProcessor = new InterfaceProcessor(appView);
     } else {
       desugaring = CfInstructionDesugaringCollection.empty();
diff --git a/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java b/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java
index 57f27cf..c42b3e0 100644
--- a/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/L8TreePruner.java
@@ -5,16 +5,13 @@
 package com.android.tools.r8.shaking;
 
 import com.android.tools.r8.graph.DexApplication;
-import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.desugar.PrefixRewritingMapper;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.IdentityHashMap;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -38,15 +35,12 @@
 
   public DexApplication prune(DexApplication app, PrefixRewritingMapper rewritePrefix) {
     Map<DexType, DexProgramClass> typeMap = new IdentityHashMap<>();
-    for (DexProgramClass aClass : app.classes()) {
-      typeMap.put(aClass.type, aClass);
-    }
     List<DexProgramClass> toKeep = new ArrayList<>();
     boolean pruneNestMember = false;
     for (DexProgramClass aClass : app.classes()) {
+      typeMap.put(aClass.type, aClass);
       if (rewritePrefix.hasRewrittenType(aClass.type, null)
-          || emulatedInterfaces.contains(aClass.type)
-          || interfaceImplementsEmulatedInterface(aClass, typeMap)) {
+          || emulatedInterfaces.contains(aClass.type)) {
         toKeep.add(aClass);
       } else {
         pruneNestMember |= aClass.isInANest();
@@ -63,24 +57,4 @@
     // of just doing nothing with it.
     return app.builder().replaceProgramClasses(toKeep).build();
   }
-
-  private boolean interfaceImplementsEmulatedInterface(
-      DexClass itf, Map<DexType, DexProgramClass> typeMap) {
-    if (!itf.isInterface()) {
-      return false;
-    }
-    LinkedList<DexType> workList = new LinkedList<>();
-    Collections.addAll(workList, itf.interfaces.values);
-    while (!workList.isEmpty()) {
-      DexType dexType = workList.removeFirst();
-      if (emulatedInterfaces.contains(dexType)) {
-        return true;
-      }
-      if (typeMap.containsKey(dexType)) {
-        DexProgramClass dexProgramClass = typeMap.get(dexType);
-        Collections.addAll(workList, dexProgramClass.interfaces.values);
-      }
-    }
-    return false;
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
index f8e241b..2d16065 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
@@ -713,7 +713,7 @@
         new SyntheticProgramClassBuilder(type, kind, outerContext, appView.dexItemFactory());
     DexProgramClass clazz =
         classBuilder
-            .addMethod(fn.andThen(m -> m.setName(SyntheticNaming.INTERNAL_SYNTHETIC_METHOD_PREFIX)))
+            .addMethod(fn.andThen(m -> m.setName(SyntheticNaming.INTERNAL_SYNTHETIC_METHOD_NAME)))
             .build();
     ProgramMethod method = new ProgramMethod(clazz, clazz.methods().iterator().next());
     addPendingDefinition(new SyntheticMethodDefinition(kind, outerContext, method));
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java
index 0af4bf0..b7861e3 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java
@@ -55,6 +55,10 @@
     this.syntheticKind = syntheticKind;
   }
 
+  public boolean hasName() {
+    return name != null;
+  }
+
   public SyntheticMethodBuilder setName(String name) {
     return setName(factory.createString(name));
   }
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
index 41020e2..1bc77c4 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
@@ -34,13 +34,11 @@
     RETARGET_INTERFACE("RetargetInterface", 21, false, true),
     WRAPPER("$Wrapper", 22, false, true),
     VIVIFIED_WRAPPER("$VivifiedWrapper", 23, false, true),
-    ENUM_CONVERSION("$EnumConversion", 31, false, true),
     LAMBDA("Lambda", 4, false),
     INIT_TYPE_ARGUMENT("-IA", 5, false, true),
     HORIZONTAL_INIT_TYPE_ARGUMENT_1(SYNTHETIC_CLASS_SEPARATOR + "IA$1", 6, false, true),
     HORIZONTAL_INIT_TYPE_ARGUMENT_2(SYNTHETIC_CLASS_SEPARATOR + "IA$2", 7, false, true),
     HORIZONTAL_INIT_TYPE_ARGUMENT_3(SYNTHETIC_CLASS_SEPARATOR + "IA$3", 8, false, true),
-    CONST_DYNAMIC("$Condy", 30, false),
     // Method synthetics.
     ENUM_UNBOXING_CHECK_NOT_ZERO_METHOD("CheckNotZero", 27, true),
     RECORD_HELPER("Record", 9, true),
@@ -56,7 +54,10 @@
     OUTLINE("Outline", 19, true),
     API_CONVERSION("APIConversion", 26, true),
     API_CONVERSION_PARAMETERS("APIConversionParameters", 28, true),
-    EMULATED_INTERFACE_MARKER_CLASS("", 29, false, true, true);
+    EMULATED_INTERFACE_MARKER_CLASS("", 29, false, true, true),
+    CONST_DYNAMIC("$Condy", 30, false),
+    ENUM_CONVERSION("$EnumConversion", 31, false, true),
+    API_MODEL_OUTLINE("ApiModelOutline", 32, true, false, false);
 
     static {
       assert verifyNoOverlappingIds();
@@ -140,8 +141,8 @@
    */
   private static final String EXTERNAL_SYNTHETIC_CLASS_SEPARATOR =
       SYNTHETIC_CLASS_SEPARATOR + "ExternalSynthetic";
-  /** Method prefix when generating synthetic methods in a class. */
-  static final String INTERNAL_SYNTHETIC_METHOD_PREFIX = "m";
+  /** Method name when generating synthetic methods in a class. */
+  static final String INTERNAL_SYNTHETIC_METHOD_NAME = "m";
 
   static String getPrefixForExternalSyntheticType(SyntheticKind kind, DexType type) {
     String binaryName = type.toBinaryName();
diff --git a/src/main/java/com/android/tools/r8/utils/AccessUtils.java b/src/main/java/com/android/tools/r8/utils/AccessUtils.java
index 0498949..6e54e2a 100644
--- a/src/main/java/com/android/tools/r8/utils/AccessUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/AccessUtils.java
@@ -4,33 +4,56 @@
 
 package com.android.tools.r8.utils;
 
+import com.android.tools.r8.FeatureSplit;
+import com.android.tools.r8.features.ClassToFeatureSplitMap;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
-import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.synthesis.SyntheticItems;
 
 public class AccessUtils {
 
   public static boolean isAccessibleInSameContextsAs(
-      DexType newType, DexType oldType, DexDefinitionSupplier definitions) {
-    DexItemFactory dexItemFactory = definitions.dexItemFactory();
+      DexType newType, DexType oldType, AppView<AppInfoWithLiveness> appView) {
+    DexItemFactory dexItemFactory = appView.dexItemFactory();
     DexType newBaseType = newType.toBaseType(dexItemFactory);
     if (!newBaseType.isClassType()) {
       return true;
     }
-    DexClass newBaseClass = definitions.definitionFor(newBaseType);
+    DexClass newBaseClass = appView.definitionFor(newBaseType);
     if (newBaseClass == null) {
       return false;
     }
-    if (newBaseClass.isPublic()) {
-      return true;
-    }
+
+    // If the new class is not public, then the old class must be non-public as well and reside in
+    // the same package as the new class.
     DexType oldBaseType = oldType.toBaseType(dexItemFactory);
-    assert oldBaseType.isClassType();
-    DexClass oldBaseClass = definitions.definitionFor(oldBaseType);
-    if (oldBaseClass == null || oldBaseClass.isPublic()) {
-      return false;
+    if (!newBaseClass.isPublic()) {
+      assert oldBaseType.isClassType();
+      DexClass oldBaseClass = appView.definitionFor(oldBaseType);
+      if (oldBaseClass == null
+          || oldBaseClass.isPublic()
+          || !newBaseType.isSamePackage(oldBaseType)) {
+        return false;
+      }
     }
-    return newBaseType.isSamePackage(oldBaseType);
+
+    // If the new class is a program class, we need to check if it is in a feature.
+    if (newBaseClass.isProgramClass()) {
+      ClassToFeatureSplitMap classToFeatureSplitMap = appView.appInfo().getClassToFeatureSplitMap();
+      SyntheticItems syntheticItems = appView.getSyntheticItems();
+      if (classToFeatureSplitMap != null) {
+        FeatureSplit newFeatureSplit =
+            classToFeatureSplitMap.getFeatureSplit(newBaseClass.asProgramClass(), syntheticItems);
+        if (!newFeatureSplit.isBase()
+            && newFeatureSplit
+                != classToFeatureSplitMap.getFeatureSplit(oldBaseType, syntheticItems)) {
+          return false;
+        }
+      }
+    }
+    return true;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index fadaaa0..c1fbc42 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -1382,7 +1382,7 @@
     // TODO(b/205611444): Enable by default.
     private boolean enableClassInitializerDeadlockDetection = true;
     private boolean enableInterfaceMerging =
-        System.getProperty("com.android.tools.r8.disableHorizontalInterfaceMerging") == null;
+        System.getProperty("com.android.tools.r8.enableHorizontalInterfaceMerging") != null;
     private boolean enableInterfaceMergingInInitial = false;
     private boolean enableSyntheticMerging = true;
     private boolean ignoreRuntimeTypeChecksForTesting = false;
@@ -1458,6 +1458,10 @@
       enableClassInitializerDeadlockDetection = true;
     }
 
+    public void setEnableInterfaceMerging() {
+      enableInterfaceMerging = true;
+    }
+
     public void setEnableInterfaceMergingInInitial() {
       enableInterfaceMergingInInitial = true;
     }
@@ -1481,6 +1485,8 @@
 
     public boolean enableApiCallerIdentification = true;
     public boolean checkAllApiReferencesAreSet = true;
+    public boolean enableStubbingOfClasses = false;
+    public boolean enableOutliningOfMethods = false;
 
     public void visitMockedApiLevelsForReferences(
         DexItemFactory factory, Consumer<AndroidApiForHashingClass> consumer) {
diff --git a/src/test/java/com/android/tools/r8/SingleTestRunResult.java b/src/test/java/com/android/tools/r8/SingleTestRunResult.java
index 726acbd..68e132a 100644
--- a/src/test/java/com/android/tools/r8/SingleTestRunResult.java
+++ b/src/test/java/com/android/tools/r8/SingleTestRunResult.java
@@ -119,6 +119,7 @@
     return self();
   }
 
+  @Override
   public <E extends Throwable> RR inspectFailure(ThrowingConsumer<CodeInspector, E> consumer)
       throws IOException, E {
     assertFailure();
diff --git a/src/test/java/com/android/tools/r8/TestCompileResult.java b/src/test/java/com/android/tools/r8/TestCompileResult.java
index af079d9..ebf30b6 100644
--- a/src/test/java/com/android/tools/r8/TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/TestCompileResult.java
@@ -22,6 +22,7 @@
 import com.android.tools.r8.debug.DebugTestConfig;
 import com.android.tools.r8.debug.DexDebugTestConfig;
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.DescriptorUtils;
@@ -39,6 +40,7 @@
 import java.nio.file.Path;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 import java.util.Set;
@@ -255,6 +257,35 @@
     }
   }
 
+  public CR addRunClasspathClassFileData(byte[]... classes) throws Exception {
+    return addRunClasspathClassFileData(Arrays.asList(classes));
+  }
+
+  public CR addRunClasspathClassFileData(Collection<byte[]> classes) throws Exception {
+    if (getBackend() == Backend.DEX) {
+      additionalRunClassPath.add(
+          testForD8(state.getTempFolder())
+              .addProgramClassFileData(classes)
+              .setMinApi(minApiLevel)
+              .compile()
+              .writeToZip());
+      return self();
+    }
+    assert getBackend() == Backend.CF;
+    try {
+      AndroidApp.Builder appBuilder = AndroidApp.builder();
+      for (byte[] clazz : classes) {
+        appBuilder.addClassProgramData(clazz, Origin.unknown());
+      }
+      Path path = state.getNewTempFolder().resolve("runtime-classes.jar");
+      appBuilder.build().writeToZip(path, OutputMode.ClassFile);
+      additionalRunClassPath.add(path);
+      return self();
+    } catch (IOException e) {
+      throw new RuntimeException(e);
+    }
+  }
+
   public CR addBootClasspathClasses(Class<?>... classes) throws Exception {
     return addBootClasspathClasses(Arrays.asList(classes));
   }
diff --git a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
index c4e86e3..4a6db32 100644
--- a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
@@ -56,6 +56,7 @@
         options.testing.allowUnnecessaryDontWarnWildcards = false;
         options.testing.reportUnusedProguardConfigurationRules = true;
         options.horizontalClassMergerOptions().enable();
+        options.horizontalClassMergerOptions().setEnableInterfaceMerging();
       };
 
   final Backend backend;
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelMockMethodMissingClassTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelMockMethodMissingClassTest.java
deleted file mode 100644
index 6b91898..0000000
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelMockMethodMissingClassTest.java
+++ /dev/null
@@ -1,128 +0,0 @@
-// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-package com.android.tools.r8.apimodel;
-
-import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
-import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForDefaultInstanceInitializer;
-import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForMethod;
-import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assume.assumeFalse;
-
-import com.android.tools.r8.TestBase;
-import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.ToolHelper.DexVm.Version;
-import com.android.tools.r8.testing.AndroidBuildVersion;
-import com.android.tools.r8.utils.AndroidApiLevel;
-import com.android.tools.r8.utils.codeinspector.Matchers;
-import java.lang.reflect.Method;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.Parameterized;
-import org.junit.runners.Parameterized.Parameter;
-import org.junit.runners.Parameterized.Parameters;
-
-@RunWith(Parameterized.class)
-public class ApiModelMockMethodMissingClassTest extends TestBase {
-
-  private final AndroidApiLevel initialLibraryMockLevel = AndroidApiLevel.M;
-  private final AndroidApiLevel finalLibraryMethodLevel = AndroidApiLevel.O_MR1;
-
-  @Parameter public TestParameters parameters;
-
-  @Parameters(name = "{0}")
-  public static TestParametersCollection data() {
-    return getTestParameters().withAllRuntimesAndApiLevels().build();
-  }
-
-  @Test
-  public void testR8() throws Exception {
-    // TODO(b/197078995): Make this work on 12.
-    assumeFalse(
-        parameters.isDexRuntime() && parameters.getDexRuntimeVersion().isEqualTo(Version.V12_0_0));
-    boolean preMockApis =
-        parameters.isCfRuntime() || parameters.getApiLevel().isLessThan(initialLibraryMockLevel);
-    boolean postMockApis =
-        !preMockApis && parameters.getApiLevel().isGreaterThanOrEqualTo(finalLibraryMethodLevel);
-    boolean betweenMockApis = !preMockApis && !postMockApis;
-    Method addedOn23 = LibraryClass.class.getMethod("addedOn23");
-    Method adeddOn27 = LibraryClass.class.getMethod("addedOn27");
-    testForR8(parameters.getBackend())
-        .addProgramClasses(Main.class)
-        .addLibraryClasses(LibraryClass.class)
-        .addDefaultRuntimeLibrary(parameters)
-        .setMinApi(parameters.getApiLevel())
-        .addKeepMainRule(Main.class)
-        .addAndroidBuildVersion()
-        .apply(setMockApiLevelForClass(LibraryClass.class, initialLibraryMockLevel))
-        .apply(
-            setMockApiLevelForDefaultInstanceInitializer(
-                LibraryClass.class, initialLibraryMockLevel))
-        .apply(setMockApiLevelForMethod(addedOn23, initialLibraryMockLevel))
-        .apply(setMockApiLevelForMethod(adeddOn27, finalLibraryMethodLevel))
-        .compile()
-        .applyIf(
-            parameters.isDexRuntime()
-                && parameters
-                    .getRuntime()
-                    .maxSupportedApiLevel()
-                    .isGreaterThanOrEqualTo(initialLibraryMockLevel),
-            b -> b.addBootClasspathClasses(LibraryClass.class))
-        .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLinesIf(preMockApis, "Hello World")
-        .assertSuccessWithOutputLinesIf(
-            betweenMockApis,
-            "LibraryClass::addedOn23",
-            "LibraryClass::missingAndReferenced",
-            "Hello World")
-        .assertSuccessWithOutputLinesIf(
-            postMockApis,
-            "LibraryClass::addedOn23",
-            "LibraryClass::missingAndReferenced",
-            "LibraryCLass::addedOn27",
-            "Hello World")
-        .inspect(
-            inspector -> {
-              // TODO(b/204982782): Should be stubbed for api-level 1-23 with methods.
-              assertThat(
-                  inspector.clazz(ApiModelMockClassTest.LibraryClass.class), Matchers.isAbsent());
-            });
-  }
-
-  // Only present from api level 23.
-  public static class LibraryClass {
-
-    public void addedOn23() {
-      System.out.println("LibraryClass::addedOn23");
-    }
-
-    public void addedOn27() {
-      System.out.println("LibraryCLass::addedOn27");
-    }
-
-    public void missingAndReferenced() {
-      System.out.println("LibraryClass::missingAndReferenced");
-    }
-
-    public void missingNotReferenced() {
-      System.out.println("LibraryClass::missingNotReferenced");
-    }
-  }
-
-  public static class Main {
-
-    public static void main(String[] args) {
-      if (AndroidBuildVersion.VERSION >= 23) {
-        LibraryClass libraryClass = new LibraryClass();
-        libraryClass.addedOn23();
-        libraryClass.missingAndReferenced();
-        if (AndroidBuildVersion.VERSION >= 27) {
-          libraryClass.addedOn27();
-        }
-      }
-      System.out.println("Hello World");
-    }
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelNoLibraryReferenceTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelNoLibraryReferenceTest.java
new file mode 100644
index 0000000..f80e5d2
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelNoLibraryReferenceTest.java
@@ -0,0 +1,80 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.apimodel;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.references.MethodReference;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.testing.AndroidBuildVersion;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.DescriptorUtils;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ApiModelNoLibraryReferenceTest extends TestBase {
+
+  private static final String API_TYPE_NAME = "android.view.accessibility.AccessibilityEvent";
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    MethodReference main =
+        Reference.methodFromMethod(Main.class.getDeclaredMethod("main", String[].class));
+    testForR8(parameters.getBackend())
+        .addProgramClassFileData(
+            transformer(Main.class)
+                .replaceClassDescriptorInMethodInstructions(
+                    descriptor(AccessibilityEvent.class),
+                    DescriptorUtils.javaTypeToDescriptor(API_TYPE_NAME))
+                .transform())
+        .addLibraryFiles(ToolHelper.getJava8RuntimeJar())
+        .setMinApi(parameters.getApiLevel())
+        .addDontWarn(API_TYPE_NAME)
+        .addKeepMainRule(Main.class)
+        .addAndroidBuildVersion()
+        .apply(ApiModelingTestHelper::enableApiCallerIdentification)
+        .apply(
+            ApiModelingTestHelper.addTracedApiReferenceLevelCallBack(
+                (methodReference, apiLevel) -> {
+                  if (methodReference.equals(main)) {
+                    Assert.assertEquals(
+                        parameters.isCfRuntime()
+                            ? AndroidApiLevel.R
+                            : AndroidApiLevel.R.max(parameters.getApiLevel()),
+                        apiLevel);
+                  }
+                }))
+        .compile();
+  }
+
+  /* Only here to get the test to compile */
+  public static class AccessibilityEvent {
+    public AccessibilityEvent() {}
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      if (AndroidBuildVersion.VERSION >= 4) {
+        // Will be rewritten to android.view.accessibility.AccessibilityEvent.
+        new AccessibilityEvent();
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineDuplicateMethodTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineDuplicateMethodTest.java
new file mode 100644
index 0000000..71bb770
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineDuplicateMethodTest.java
@@ -0,0 +1,154 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.apimodel;
+
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForDefaultInstanceInitializer;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForMethod;
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithName;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeFalse;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.testing.AndroidBuildVersion;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.lang.reflect.Method;
+import java.util.Optional;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ApiModelOutlineDuplicateMethodTest extends TestBase {
+
+  private final AndroidApiLevel classApiLevel = AndroidApiLevel.K;
+  private final AndroidApiLevel methodApiLevel = AndroidApiLevel.M;
+
+  @Parameter public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    assumeFalse(
+        parameters.isDexRuntime() && parameters.getDexRuntimeVersion().isEqualTo(Version.V12_0_0));
+    boolean isMethodApiLevel =
+        parameters.isDexRuntime()
+            && parameters.getApiLevel().isGreaterThanOrEqualTo(methodApiLevel);
+    Method adeddOn23 = LibraryClass.class.getMethod("addedOn23");
+    testForR8(parameters.getBackend())
+        .addProgramClasses(Main.class, TestClass.class)
+        .addLibraryClasses(LibraryClass.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .addAndroidBuildVersion()
+        .apply(setMockApiLevelForClass(LibraryClass.class, classApiLevel))
+        .apply(setMockApiLevelForDefaultInstanceInitializer(LibraryClass.class, classApiLevel))
+        .apply(setMockApiLevelForMethod(adeddOn23, methodApiLevel))
+        .apply(ApiModelingTestHelper::enableOutliningOfMethods)
+        .enableInliningAnnotations()
+        .compile()
+        .applyIf(
+            parameters.isDexRuntime()
+                && parameters
+                    .getRuntime()
+                    .maxSupportedApiLevel()
+                    .isGreaterThanOrEqualTo(classApiLevel),
+            b -> b.addBootClasspathClasses(LibraryClass.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLinesIf(!isMethodApiLevel, "Hello World")
+        .assertSuccessWithOutputLinesIf(
+            isMethodApiLevel, "LibraryClass::addedOn23", "LibraryClass::addedOn23", "Hello World")
+        .inspect(
+            inspector -> {
+              // No need to check further on CF.
+              Optional<FoundMethodSubject> synthesizedAddedOn23 =
+                  inspector.allClasses().stream()
+                      .flatMap(clazz -> clazz.allMethods().stream())
+                      .filter(
+                          methodSubject ->
+                              methodSubject.isSynthetic()
+                                  && invokesMethodWithName("addedOn23").matches(methodSubject))
+                      .findFirst();
+              if (parameters.isCfRuntime() || parameters.getApiLevel().isLessThan(classApiLevel)) {
+                assertFalse(synthesizedAddedOn23.isPresent());
+                assertEquals(3, inspector.allClasses().size());
+              } else if (parameters.getApiLevel().isLessThan(methodApiLevel)) {
+                assertTrue(synthesizedAddedOn23.isPresent());
+                assertEquals(4, inspector.allClasses().size());
+                ClassSubject testClass = inspector.clazz(TestClass.class);
+                assertThat(testClass, isPresent());
+                MethodSubject testMethod = testClass.uniqueMethodWithName("test");
+                assertThat(testMethod, isPresent());
+                assertEquals(
+                    2,
+                    testMethod
+                        .streamInstructions()
+                        .filter(
+                            instructionSubject -> {
+                              if (!instructionSubject.isInvoke()) {
+                                return false;
+                              }
+                              return instructionSubject
+                                  .getMethod()
+                                  .asMethodReference()
+                                  .equals(synthesizedAddedOn23.get().asMethodReference());
+                            })
+                        .count());
+              } else {
+                // No outlining on this api level.
+                assertFalse(synthesizedAddedOn23.isPresent());
+                assertEquals(3, inspector.allClasses().size());
+              }
+            });
+  }
+
+  // Only present from api level 19.
+  public static class LibraryClass {
+
+    public void addedOn23() {
+      System.out.println("LibraryClass::addedOn23");
+    }
+  }
+
+  public static class TestClass {
+
+    @NeverInline
+    public static void test() {
+      if (AndroidBuildVersion.VERSION >= 19) {
+        LibraryClass libraryClass = new LibraryClass();
+        if (AndroidBuildVersion.VERSION >= 23) {
+          libraryClass.addedOn23();
+          libraryClass.addedOn23();
+        }
+      }
+      System.out.println("Hello World");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      TestClass.test();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineHorizontalMergingTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineHorizontalMergingTest.java
new file mode 100644
index 0000000..436d2fc
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineHorizontalMergingTest.java
@@ -0,0 +1,223 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.apimodel;
+
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForDefaultInstanceInitializer;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForMethod;
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithName;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeFalse;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.testing.AndroidBuildVersion;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
+import java.util.List;
+import java.util.stream.Collectors;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ApiModelOutlineHorizontalMergingTest extends TestBase {
+
+  private final AndroidApiLevel libraryClassApiLevel = AndroidApiLevel.K;
+  private final AndroidApiLevel otherLibraryClassApiLevel = AndroidApiLevel.K;
+  private final AndroidApiLevel firstMethodApiLevel = AndroidApiLevel.M;
+  private final AndroidApiLevel secondMethodApiLevel = AndroidApiLevel.O_MR1;
+
+  @Parameter public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    assumeFalse(
+        parameters.isDexRuntime() && parameters.getDexRuntimeVersion().isEqualTo(Version.V12_0_0));
+    boolean beforeFirstApiMethodLevel =
+        parameters.isCfRuntime() || parameters.getApiLevel().isLessThan(firstMethodApiLevel);
+    boolean afterSecondApiMethodLevel =
+        parameters.isDexRuntime()
+            && parameters.getApiLevel().isGreaterThanOrEqualTo(secondMethodApiLevel);
+    boolean betweenMethodApiLevels = !beforeFirstApiMethodLevel && !afterSecondApiMethodLevel;
+    testForR8(parameters.getBackend())
+        .addProgramClasses(Main.class, TestClass.class)
+        .addLibraryClasses(LibraryClass.class, OtherLibraryClass.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .addAndroidBuildVersion()
+        .apply(setMockApiLevelForClass(LibraryClass.class, libraryClassApiLevel))
+        .apply(
+            setMockApiLevelForDefaultInstanceInitializer(LibraryClass.class, libraryClassApiLevel))
+        .apply(
+            setMockApiLevelForMethod(
+                LibraryClass.class.getMethod("addedOn23"), firstMethodApiLevel))
+        .apply(
+            setMockApiLevelForMethod(
+                LibraryClass.class.getMethod("addedOn27"), secondMethodApiLevel))
+        .apply(setMockApiLevelForClass(OtherLibraryClass.class, otherLibraryClassApiLevel))
+        .apply(
+            setMockApiLevelForDefaultInstanceInitializer(
+                OtherLibraryClass.class, otherLibraryClassApiLevel))
+        .apply(
+            setMockApiLevelForMethod(
+                OtherLibraryClass.class.getMethod("addedOn23"), firstMethodApiLevel))
+        .apply(
+            setMockApiLevelForMethod(
+                OtherLibraryClass.class.getMethod("addedOn27"), secondMethodApiLevel))
+        .apply(ApiModelingTestHelper::enableOutliningOfMethods)
+        .enableInliningAnnotations()
+        .compile()
+        .applyIf(
+            parameters.isDexRuntime()
+                && parameters
+                    .getRuntime()
+                    .maxSupportedApiLevel()
+                    .isGreaterThanOrEqualTo(libraryClassApiLevel),
+            b -> b.addBootClasspathClasses(LibraryClass.class, OtherLibraryClass.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLinesIf(beforeFirstApiMethodLevel, "Hello World")
+        .assertSuccessWithOutputLinesIf(
+            betweenMethodApiLevels,
+            "LibraryClass::addedOn23",
+            "OtherLibraryClass::addedOn23",
+            "Hello World")
+        .assertSuccessWithOutputLinesIf(
+            afterSecondApiMethodLevel,
+            "LibraryClass::addedOn23",
+            "LibraryClass::addedOn27",
+            "OtherLibraryClass::addedOn23",
+            "OtherLibraryClass::addedOn27",
+            "Hello World")
+        .inspect(
+            inspector -> {
+              // No need to check further on CF.
+              List<FoundMethodSubject> outlinedAddedOn23 =
+                  inspector.allClasses().stream()
+                      .flatMap(clazz -> clazz.allMethods().stream())
+                      .filter(
+                          methodSubject ->
+                              methodSubject.isSynthetic()
+                                  && invokesMethodWithName("addedOn23").matches(methodSubject))
+                      .collect(Collectors.toList());
+              List<FoundMethodSubject> outlinedAddedOn27 =
+                  inspector.allClasses().stream()
+                      .flatMap(clazz -> clazz.allMethods().stream())
+                      .filter(
+                          methodSubject ->
+                              methodSubject.isSynthetic()
+                                  && invokesMethodWithName("addedOn27").matches(methodSubject))
+                      .collect(Collectors.toList());
+              if (parameters.isCfRuntime()
+                  || parameters.getApiLevel().isLessThan(libraryClassApiLevel)) {
+                assertTrue(outlinedAddedOn23.isEmpty());
+                assertTrue(outlinedAddedOn27.isEmpty());
+                assertEquals(3, inspector.allClasses().size());
+              } else if (parameters.getApiLevel().isLessThan(firstMethodApiLevel)) {
+                // We have generated 4 outlines two having api level 23 and two having api level 27.
+                // Check that the levels are horizontally merged.
+                assertEquals(5, inspector.allClasses().size());
+                assertEquals(2, outlinedAddedOn23.size());
+                assertTrue(
+                    outlinedAddedOn23.stream()
+                        .allMatch(
+                            outline ->
+                                outline.getMethod().getHolderType()
+                                    == outlinedAddedOn23.get(0).getMethod().getHolderType()));
+                assertEquals(2, outlinedAddedOn27.size());
+                assertTrue(
+                    outlinedAddedOn27.stream()
+                        .allMatch(
+                            outline ->
+                                outline.getMethod().getHolderType()
+                                    == outlinedAddedOn27.get(0).getMethod().getHolderType()));
+              } else if (parameters.getApiLevel().isLessThan(secondMethodApiLevel)) {
+                assertTrue(outlinedAddedOn23.isEmpty());
+                assertEquals(4, inspector.allClasses().size());
+                assertEquals(2, outlinedAddedOn27.size());
+                assertTrue(
+                    outlinedAddedOn27.stream()
+                        .allMatch(
+                            outline ->
+                                outline.getMethod().getHolderType()
+                                    == outlinedAddedOn27.get(0).getMethod().getHolderType()));
+              } else {
+                // No outlining on this api level.
+                assertTrue(outlinedAddedOn23.isEmpty());
+                assertTrue(outlinedAddedOn27.isEmpty());
+                assertEquals(3, inspector.allClasses().size());
+              }
+            });
+  }
+
+  // Only present from api level 19.
+  public static class LibraryClass {
+
+    public void addedOn23() {
+      System.out.println("LibraryClass::addedOn23");
+    }
+
+    public void addedOn27() {
+      System.out.println("LibraryClass::addedOn27");
+    }
+  }
+
+  // Only present from api level 19.
+  public static class OtherLibraryClass {
+
+    public void addedOn23() {
+      System.out.println("OtherLibraryClass::addedOn23");
+    }
+
+    public static void addedOn27() {
+      System.out.println("OtherLibraryClass::addedOn27");
+    }
+  }
+
+  public static class TestClass {
+
+    @NeverInline
+    public static void test() {
+      if (AndroidBuildVersion.VERSION >= 19) {
+        LibraryClass libraryClass = new LibraryClass();
+        if (AndroidBuildVersion.VERSION >= 23) {
+          libraryClass.addedOn23();
+        }
+        if (AndroidBuildVersion.VERSION >= 27) {
+          libraryClass.addedOn27();
+        }
+      }
+      if (AndroidBuildVersion.VERSION >= 19) {
+        OtherLibraryClass otherLibraryClass = new OtherLibraryClass();
+        if (AndroidBuildVersion.VERSION >= 23) {
+          otherLibraryClass.addedOn23();
+        }
+        if (AndroidBuildVersion.VERSION >= 27) {
+          OtherLibraryClass.addedOn27();
+        }
+      }
+      System.out.println("Hello World");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      TestClass.test();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineMethodMissingClassTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineMethodMissingClassTest.java
new file mode 100644
index 0000000..4d6a526
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineMethodMissingClassTest.java
@@ -0,0 +1,237 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.apimodel;
+
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForDefaultInstanceInitializer;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForMethod;
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithName;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeFalse;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.references.MethodReference;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.testing.AndroidBuildVersion;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.lang.reflect.Method;
+import java.util.Optional;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ApiModelOutlineMethodMissingClassTest extends TestBase {
+
+  private final AndroidApiLevel initialLibraryMockLevel = AndroidApiLevel.M;
+  private final AndroidApiLevel finalLibraryMethodLevel = AndroidApiLevel.O_MR1;
+
+  @Parameter public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    // TODO(b/197078995): Make this work on 12.
+    assumeFalse(
+        parameters.isDexRuntime() && parameters.getDexRuntimeVersion().isEqualTo(Version.V12_0_0));
+    boolean preMockApis =
+        parameters.isCfRuntime() || parameters.getApiLevel().isLessThan(initialLibraryMockLevel);
+    boolean postMockApis =
+        !preMockApis && parameters.getApiLevel().isGreaterThanOrEqualTo(finalLibraryMethodLevel);
+    boolean betweenMockApis = !preMockApis && !postMockApis;
+    Method addedOn23 = LibraryClass.class.getMethod("addedOn23");
+    Method adeddOn27 = LibraryClass.class.getMethod("addedOn27");
+    testForR8(parameters.getBackend())
+        .addProgramClasses(Main.class, TestClass.class)
+        .addLibraryClasses(LibraryClass.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .addAndroidBuildVersion()
+        .apply(setMockApiLevelForClass(LibraryClass.class, initialLibraryMockLevel))
+        .apply(
+            setMockApiLevelForDefaultInstanceInitializer(
+                LibraryClass.class, initialLibraryMockLevel))
+        .apply(setMockApiLevelForMethod(addedOn23, initialLibraryMockLevel))
+        .apply(setMockApiLevelForMethod(adeddOn27, finalLibraryMethodLevel))
+        .apply(ApiModelingTestHelper::enableOutliningOfMethods)
+        .enableInliningAnnotations()
+        .compile()
+        .applyIf(
+            parameters.isDexRuntime()
+                && parameters
+                    .getRuntime()
+                    .maxSupportedApiLevel()
+                    .isGreaterThanOrEqualTo(initialLibraryMockLevel),
+            b -> b.addBootClasspathClasses(LibraryClass.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLinesIf(preMockApis, "Hello World")
+        .assertSuccessWithOutputLinesIf(
+            betweenMockApis,
+            "LibraryClass::addedOn23",
+            "LibraryClass::missingAndReferenced",
+            "Hello World")
+        .assertSuccessWithOutputLinesIf(
+            postMockApis,
+            "LibraryClass::addedOn23",
+            "LibraryClass::missingAndReferenced",
+            "LibraryCLass::addedOn27",
+            "Hello World")
+        .inspect(
+            inspector -> {
+              // No need to check further on CF.
+              if (parameters.isCfRuntime()) {
+                assertEquals(3, inspector.allClasses().size());
+                return;
+              }
+              ClassSubject testClass = inspector.clazz(TestClass.class);
+              assertThat(testClass, isPresent());
+              MethodSubject testMethod = testClass.uniqueMethodWithName("test");
+              assertThat(testMethod, isPresent());
+              Optional<FoundMethodSubject> synthesizedAddedOn27 =
+                  inspector.allClasses().stream()
+                      .flatMap(clazz -> clazz.allMethods().stream())
+                      .filter(
+                          methodSubject ->
+                              methodSubject.isSynthetic()
+                                  && invokesMethodWithName("addedOn27").matches(methodSubject))
+                      .findFirst();
+              Optional<FoundMethodSubject> synthesizedMissingAndReferenced =
+                  inspector.allClasses().stream()
+                      .flatMap(clazz -> clazz.allMethods().stream())
+                      .filter(
+                          methodSubject ->
+                              methodSubject.isSynthetic()
+                                  && invokesMethodWithName("missingAndReferenced")
+                                      .matches(methodSubject))
+                      .findFirst();
+              Optional<FoundMethodSubject> synthesizedMissingNotReferenced =
+                  inspector.allClasses().stream()
+                      .flatMap(clazz -> clazz.allMethods().stream())
+                      .filter(
+                          methodSubject ->
+                              methodSubject.isSynthetic()
+                                  && invokesMethodWithName("missingNotReferenced")
+                                      .matches(methodSubject))
+                      .findFirst();
+              assertFalse(synthesizedMissingNotReferenced.isPresent());
+              if (parameters.getApiLevel().isLessThan(AndroidApiLevel.M)) {
+                assertEquals(3, inspector.allClasses().size());
+                assertFalse(synthesizedAddedOn27.isPresent());
+                assertFalse(synthesizedMissingAndReferenced.isPresent());
+              } else if (parameters.getApiLevel().isLessThan(AndroidApiLevel.O_MR1)) {
+                assertEquals(5, inspector.allClasses().size());
+                assertTrue(synthesizedAddedOn27.isPresent());
+                inspectRewrittenToOutline(testMethod, synthesizedAddedOn27.get(), "addedOn27");
+                assertTrue(synthesizedMissingAndReferenced.isPresent());
+                inspectRewrittenToOutline(
+                    testMethod, synthesizedMissingAndReferenced.get(), "missingAndReferenced");
+              } else {
+                assertEquals(4, inspector.allClasses().size());
+                assertFalse(synthesizedAddedOn27.isPresent());
+                assertTrue(synthesizedMissingAndReferenced.isPresent());
+                inspectRewrittenToOutline(
+                    testMethod, synthesizedMissingAndReferenced.get(), "missingAndReferenced");
+              }
+            });
+  }
+
+  private void inspectRewrittenToOutline(
+      MethodSubject callerSubject, FoundMethodSubject outline, String apiMethodName)
+      throws Exception {
+    // Check that the library reference is no longer present.
+    MethodReference libraryMethodReference =
+        Reference.methodFromMethod(LibraryClass.class.getDeclaredMethod(apiMethodName));
+    assertFalse(
+        callerSubject
+            .streamInstructions()
+            .anyMatch(
+                instructionSubject -> {
+                  if (!instructionSubject.isInvoke()) {
+                    return false;
+                  }
+                  return instructionSubject
+                      .getMethod()
+                      .asMethodReference()
+                      .equals(libraryMethodReference);
+                }));
+    MethodReference outlineReference = outline.getMethod().getReference().asMethodReference();
+    assertEquals(
+        1,
+        callerSubject
+            .streamInstructions()
+            .filter(
+                instructionSubject -> {
+                  if (!instructionSubject.isInvoke()) {
+                    return false;
+                  }
+                  return instructionSubject
+                      .getMethod()
+                      .asMethodReference()
+                      .equals(outlineReference);
+                })
+            .count());
+  }
+
+  // Only present from api level 23.
+  public static class LibraryClass {
+
+    public void addedOn23() {
+      System.out.println("LibraryClass::addedOn23");
+    }
+
+    public void addedOn27() {
+      System.out.println("LibraryCLass::addedOn27");
+    }
+
+    public void missingAndReferenced() {
+      System.out.println("LibraryClass::missingAndReferenced");
+    }
+
+    public void missingNotReferenced() {
+      System.out.println("LibraryClass::missingNotReferenced");
+    }
+  }
+
+  public static class TestClass {
+
+    @NeverInline
+    public static void test() {
+      if (AndroidBuildVersion.VERSION >= 23) {
+        LibraryClass libraryClass = new LibraryClass();
+        libraryClass.addedOn23();
+        libraryClass.missingAndReferenced();
+        if (AndroidBuildVersion.VERSION >= 27) {
+          libraryClass.addedOn27();
+        }
+      }
+      System.out.println("Hello World");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      TestClass.test();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java
index c8ee027..a5c2487 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java
@@ -105,6 +105,20 @@
         });
   }
 
+  static void enableStubbingOfClasses(TestCompilerBuilder<?, ?, ?, ?, ?> compilerBuilder) {
+    compilerBuilder.addOptionsModification(
+        options -> {
+          options.apiModelingOptions().enableStubbingOfClasses = true;
+        });
+  }
+
+  static void enableOutliningOfMethods(TestCompilerBuilder<?, ?, ?, ?, ?> compilerBuilder) {
+    compilerBuilder.addOptionsModification(
+        options -> {
+          options.apiModelingOptions().enableOutliningOfMethods = true;
+        });
+  }
+
   static void disableCheckAllApiReferencesAreNotUnknown(
       TestCompilerBuilder<?, ?, ?, ?, ?> compilerBuilder) {
     compilerBuilder.addOptionsModification(
diff --git a/src/test/java/com/android/tools/r8/apimodel/DuplicateClassTest.java b/src/test/java/com/android/tools/r8/apimodel/DuplicateClassTest.java
new file mode 100644
index 0000000..458bb9d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/DuplicateClassTest.java
@@ -0,0 +1,69 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.apimodel;
+
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+/**
+ * A simple test showing that adding a program class as a duplicate for a bootclasspath class for
+ * dalvik causes an error where the referencing class cannot be optimized (b/208978971).
+ */
+public class DuplicateClassTest extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  @Test
+  public void testRuntime() throws Exception {
+    testForD8(parameters.getBackend())
+        .addProgramClassFileData(
+            transformer(Main.class).removeInnerClasses().transform(),
+            transformer(Foo.class)
+                .setClassDescriptor("Ljava/lang/Exception;")
+                .removeInnerClasses()
+                .transform())
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello World")
+        .applyIf(
+            parameters.getDexRuntimeVersion().isDalvik(),
+            result ->
+                assertThat(
+                    result.getStdErr(),
+                    containsString(
+                        "DexOpt: not resolving ambiguous class 'Ljava/lang/Exception;'")),
+            result ->
+                assertThat(
+                    result.getStdErr(),
+                    not(containsString("not resolving ambiguous class 'Ljava/lang/Exception;'"))));
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      Exception exception = new Exception("Hello World");
+      System.out.println(exception.getMessage());
+    }
+  }
+
+  public static class /* java.lang.Exception */ Foo {}
+}
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/MergingWithDesugaredLibraryTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/MergingWithDesugaredLibraryTest.java
index ac25355..6eeabe2 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/MergingWithDesugaredLibraryTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/MergingWithDesugaredLibraryTest.java
@@ -210,7 +210,7 @@
   }
 
   private boolean someLibraryDesugaringRequired() {
-    return parameters.getApiLevel().getLevel() <= AndroidApiLevel.N.getLevel();
+    return requiresAnyCoreLibDesugaring(parameters);
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/dex/DebugByteCodeWriterTest.java b/src/test/java/com/android/tools/r8/dex/DebugByteCodeWriterTest.java
index 9954a41..5aeaddc 100644
--- a/src/test/java/com/android/tools/r8/dex/DebugByteCodeWriterTest.java
+++ b/src/test/java/com/android/tools/r8/dex/DebugByteCodeWriterTest.java
@@ -62,6 +62,7 @@
         Collections.emptyList(),
         Collections.emptyList(),
         Collections.emptyList(),
+        0,
         Timing.empty());
   }
 
diff --git a/src/test/java/com/android/tools/r8/dexsplitter/DexSplitterFieldTypeStrengtheningTest.java b/src/test/java/com/android/tools/r8/dexsplitter/DexSplitterFieldTypeStrengtheningTest.java
new file mode 100644
index 0000000..45a3be4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/dexsplitter/DexSplitterFieldTypeStrengtheningTest.java
@@ -0,0 +1,122 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.dexsplitter;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.R8TestCompileResult;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestShrinkerBuilder;
+import com.android.tools.r8.ThrowableConsumer;
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.ThrowingConsumer;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.FieldSubject;
+import com.google.common.collect.ImmutableSet;
+import java.io.IOException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class DexSplitterFieldTypeStrengtheningTest extends SplitterTestBase {
+
+  public static final String EXPECTED = StringUtils.lines("FeatureClass");
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection params() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  private final TestParameters parameters;
+
+  public DexSplitterFieldTypeStrengtheningTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testPropagationFromFeature() throws Exception {
+    ThrowingConsumer<R8TestCompileResult, Exception> ensureGetFromFeatureGone =
+        r8TestCompileResult -> {
+          // Ensure that getFromFeature from FeatureClass is inlined into the run method.
+          ClassSubject clazz = r8TestCompileResult.inspector().clazz(FeatureClass.class);
+          assertThat(clazz.uniqueMethodWithName("getFromFeature"), not(isPresent()));
+        };
+    ProcessResult processResult =
+        testDexSplitter(
+            parameters,
+            ImmutableSet.of(BaseSuperClass.class),
+            ImmutableSet.of(FeatureClass.class),
+            FeatureClass.class,
+            EXPECTED,
+            ensureGetFromFeatureGone,
+            TestShrinkerBuilder::noMinification);
+    // We expect art to fail on this with the dex splitter, see b/122902374
+    assertNotEquals(processResult.exitCode, 0);
+    assertTrue(processResult.stderr.contains("NoClassDefFoundError"));
+  }
+
+  @Test
+  public void testOnR8Splitter() throws IOException, CompilationFailedException {
+    assumeTrue(parameters.isDexRuntime());
+    ProcessResult processResult =
+        testR8Splitter(
+            parameters,
+            ImmutableSet.of(BaseSuperClass.class),
+            ImmutableSet.of(FeatureClass.class),
+            FeatureClass.class,
+            compileResult ->
+                compileResult.inspect(
+                    inspector -> {
+                      ClassSubject baseSuperClassSubject = inspector.clazz(BaseSuperClass.class);
+                      assertThat(baseSuperClassSubject, isPresent());
+
+                      FieldSubject fieldSubject = baseSuperClassSubject.uniqueFieldWithName("f");
+                      assertThat(fieldSubject, isPresent());
+                      assertEquals(
+                          Object.class.getTypeName(),
+                          fieldSubject.getField().getType().getTypeName());
+                    }),
+            ThrowableConsumer.empty());
+    assertEquals(processResult.exitCode, 0);
+    assertEquals(processResult.stdout, EXPECTED);
+  }
+
+  public abstract static class BaseSuperClass implements RunInterface {
+
+    public static Object f;
+
+    @Override
+    public void run() {
+      setFieldFromFeature();
+      System.out.println(f);
+    }
+
+    public abstract void setFieldFromFeature();
+  }
+
+  public static class FeatureClass extends BaseSuperClass {
+
+    @Override
+    public void setFieldFromFeature() {
+      BaseSuperClass.f = this;
+    }
+
+    @Override
+    public String toString() {
+      return "FeatureClass";
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/DevirtualizeLibrarySuperTest.java b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/DevirtualizeLibrarySuperTest.java
new file mode 100644
index 0000000..e82bd6e
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/DevirtualizeLibrarySuperTest.java
@@ -0,0 +1,103 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.devirtualize;
+
+import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithHolderAndName;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class DevirtualizeLibrarySuperTest extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    boolean hasNewLibraryHierarchyOnClassPath =
+        parameters.isCfRuntime()
+            || parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.M);
+    testForR8(parameters.getBackend())
+        .addLibraryClasses(Library.class, LibraryOverride.class, LibraryBoundary.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .addProgramClasses(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .enableInliningAnnotations()
+        .compile()
+        .inspect(
+            inspector -> {
+              MethodSubject fooMethod = inspector.clazz(Main.class).uniqueMethodWithName("foo");
+              assertThat(fooMethod, isPresent());
+              assertThat(
+                  fooMethod,
+                  not(invokesMethodWithHolderAndName(LibraryOverride.class.getTypeName(), "foo")));
+            })
+        .applyIf(
+            hasNewLibraryHierarchyOnClassPath,
+            b ->
+                b.addRunClasspathClasses(
+                    Library.class, LibraryOverride.class, LibraryBoundary.class),
+            b ->
+                b.addRunClasspathClassFileData(
+                    transformer(Library.class).transform(),
+                    transformer(LibraryBoundary.class)
+                        .replaceClassDescriptorInMethodInstructions(
+                            descriptor(LibraryOverride.class), descriptor(Library.class))
+                        .setSuper(descriptor(Library.class))
+                        .transform()))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLinesIf(hasNewLibraryHierarchyOnClassPath, "LibraryOverride::foo")
+        .assertSuccessWithOutputLinesIf(!hasNewLibraryHierarchyOnClassPath, "Library::foo");
+  }
+
+  public static class Library {
+
+    public void foo() {
+      System.out.println("Library::foo");
+    }
+  }
+
+  // This class will is inserted in the hierarchy from api 23.
+  public static class LibraryOverride extends Library {
+
+    @Override
+    public void foo() {
+      System.out.println("LibraryOverride::foo");
+    }
+  }
+
+  public static class LibraryBoundary extends LibraryOverride {}
+
+  public static class Main extends LibraryBoundary {
+
+    @NeverInline
+    @Override
+    public void foo() {
+      super.foo();
+    }
+
+    public static void main(String[] args) {
+      new Main().foo();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/TargetedButNotLiveLambdaAfterDevirtualizationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/TargetedButNotLiveLambdaAfterDevirtualizationTest.java
new file mode 100644
index 0000000..999e2f4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/fields/TargetedButNotLiveLambdaAfterDevirtualizationTest.java
@@ -0,0 +1,80 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.membervaluepropagation.fields;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+/** Reproduction of b/209475782. */
+@RunWith(Parameterized.class)
+public class TargetedButNotLiveLambdaAfterDevirtualizationTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .enableInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithEmptyOutput();
+  }
+
+  static class Main {
+
+    static I f;
+    static I f2;
+
+    public static void main(String[] args) {
+      if (alwaysFalse()) {
+        setFields();
+      }
+      if (unknownButFalse()) {
+        callLambdaMethods();
+      }
+    }
+
+    static boolean alwaysFalse() {
+      return false;
+    }
+
+    static boolean unknownButFalse() {
+      return System.currentTimeMillis() < 0;
+    }
+
+    @NeverInline
+    static void setFields() {
+      f = () -> System.out.println("Foo!");
+      f2 = () -> System.out.println("Bar!");
+    }
+
+    @NeverInline
+    static void callLambdaMethods() {
+      f.m();
+      f2.m();
+    }
+  }
+
+  interface I {
+
+    void m();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionFunctionTest.java b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionFunctionTest.java
index a03354e..19550d1 100644
--- a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionFunctionTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionFunctionTest.java
@@ -8,7 +8,6 @@
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndNotRenamed;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndRenamed;
-import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
@@ -25,10 +24,10 @@
 import com.android.tools.r8.utils.codeinspector.KmTypeProjectionSubject;
 import com.android.tools.r8.utils.codeinspector.KmTypeSubject;
 import com.android.tools.r8.utils.codeinspector.KmValueParameterSubject;
+import com.android.tools.r8.utils.codeinspector.Matchers;
 import java.nio.file.Path;
 import java.util.Collection;
 import java.util.List;
-import org.junit.Ignore;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -77,13 +76,20 @@
   }
 
   @Test
-  @Ignore("b/154300326")
-  public void testMetadataInExtensionFunction_merged() throws Exception {
+  public void testMetadataInExtensionFunction_merged_compat() throws Exception {
+    testMetadataInExtensionFunction_merged(false);
+  }
+
+  @Test
+  public void testMetadataInExtensionFunction_merged_full() throws Exception {
+    testMetadataInExtensionFunction_merged(true);
+  }
+
+  public void testMetadataInExtensionFunction_merged(boolean full) throws Exception {
     Path libJar =
-        testForR8(parameters.getBackend())
-            .addProgramFiles(
-                extLibJarMap.getForConfiguration(kotlinc, targetVersion),
-                kotlinc.getKotlinAnnotationJar())
+        (full ? testForR8(parameters.getBackend()) : testForR8Compat(parameters.getBackend()))
+            .addClasspathFiles(kotlinc.getKotlinStdlibJar(), kotlinc.getKotlinAnnotationJar())
+            .addProgramFiles(extLibJarMap.getForConfiguration(kotlinc, targetVersion))
             // Keep the B class and its interface (which has the doStuff method).
             .addKeepRules("-keep class **.B")
             .addKeepRules("-keep class **.I { <methods>; }")
@@ -95,7 +101,7 @@
             .addKeepAttributes(ProguardKeepAttributes.INNER_CLASSES)
             .addKeepAttributes(ProguardKeepAttributes.ENCLOSING_METHOD)
             .compile()
-            .inspect(this::inspectMerged)
+            .inspect(inspector -> inspectMerged(inspector, full))
             .writeToZip();
 
     Path output =
@@ -103,7 +109,10 @@
             .addClasspathFiles(libJar)
             .addSourceFiles(getKotlinFileInTest(PKG_PREFIX + "/extension_function_app", "main"))
             .setOutputPath(temp.newFolder().toPath())
-            .compile();
+            .compile(full || kotlinParameters.isOlderThanMinSupported());
+    if (full || kotlinParameters.isOlderThanMinSupported()) {
+      return;
+    }
 
     testForJvm()
         .addRunClasspathFiles(kotlinc.getKotlinStdlibJar(), libJar)
@@ -112,11 +121,11 @@
         .assertSuccessWithOutput(EXPECTED);
   }
 
-  private void inspectMerged(CodeInspector inspector) {
+  private void inspectMerged(CodeInspector inspector, boolean full) {
     String superClassName = PKG + ".extension_function_lib.Super";
     String bClassName = PKG + ".extension_function_lib.B";
 
-    assertThat(inspector.clazz(superClassName), not(isPresent()));
+    assertThat(inspector.clazz(superClassName), Matchers.notIf(isPresent(), full));
 
     ClassSubject impl = inspector.clazz(bClassName);
     assertThat(impl, isPresentAndNotRenamed());
diff --git a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionPropertyTest.java b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionPropertyTest.java
index 67401c2..3a8760a 100644
--- a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionPropertyTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInExtensionPropertyTest.java
@@ -24,10 +24,10 @@
 import com.android.tools.r8.utils.codeinspector.KmFunctionSubject;
 import com.android.tools.r8.utils.codeinspector.KmPackageSubject;
 import com.android.tools.r8.utils.codeinspector.KmPropertySubject;
+import com.android.tools.r8.utils.codeinspector.Matchers;
 import java.nio.file.Path;
 import java.util.Collection;
 import java.util.List;
-import org.junit.Ignore;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -76,13 +76,20 @@
   }
 
   @Test
-  @Ignore("b/154300326")
-  public void testMetadataInExtensionProperty_merged() throws Exception {
+  public void testMetadataInExtensionProperty_merged_compat() throws Exception {
+    testMetadataInExtensionProperty_merged(false);
+  }
+
+  @Test
+  public void testMetadataInExtensionProperty_merged_full() throws Exception {
+    testMetadataInExtensionProperty_merged(true);
+  }
+
+  public void testMetadataInExtensionProperty_merged(boolean full) throws Exception {
     Path libJar =
-        testForR8(parameters.getBackend())
-            .addProgramFiles(
-                extLibJarMap.getForConfiguration(kotlinc, targetVersion),
-                kotlinc.getKotlinAnnotationJar())
+        (full ? testForR8(parameters.getBackend()) : testForR8Compat(parameters.getBackend()))
+            .addClasspathFiles(kotlinc.getKotlinStdlibJar(), kotlinc.getKotlinAnnotationJar())
+            .addProgramFiles(extLibJarMap.getForConfiguration(kotlinc, targetVersion))
             // Keep the B class and its interface (which has the doStuff method).
             .addKeepRules("-keep class **.B")
             .addKeepRules("-keep class **.I { <methods>; }")
@@ -91,7 +98,7 @@
             .addKeepRules("-keep class **.BKt { <methods>; }")
             .addKeepAttributes(ProguardKeepAttributes.RUNTIME_VISIBLE_ANNOTATIONS)
             .compile()
-            .inspect(this::inspectMerged)
+            .inspect(inspector -> inspectMerged(inspector, full))
             .writeToZip();
 
     Path output =
@@ -99,7 +106,10 @@
             .addClasspathFiles(libJar)
             .addSourceFiles(getKotlinFileInTest(PKG_PREFIX + "/extension_property_app", "main"))
             .setOutputPath(temp.newFolder().toPath())
-            .compile();
+            .compile(full || kotlinParameters.isOlderThanMinSupported());
+    if (full || kotlinParameters.isOlderThanMinSupported()) {
+      return;
+    }
 
     testForJvm()
         .addRunClasspathFiles(kotlinc.getKotlinStdlibJar(), libJar)
@@ -108,12 +118,12 @@
         .assertSuccessWithOutput(EXPECTED);
   }
 
-  private void inspectMerged(CodeInspector inspector) {
+  private void inspectMerged(CodeInspector inspector, boolean full) {
     String superClassName = PKG + ".extension_property_lib.Super";
     String bClassName = PKG + ".extension_property_lib.B";
     String bKtClassName = PKG + ".extension_property_lib.BKt";
 
-    assertThat(inspector.clazz(superClassName), not(isPresent()));
+    assertThat(inspector.clazz(superClassName), Matchers.notIf(isPresent(), full));
 
     ClassSubject impl = inspector.clazz(bClassName);
     assertThat(impl, isPresentAndNotRenamed());
@@ -124,7 +134,7 @@
     assertTrue(superTypes.stream().noneMatch(
         supertype -> supertype.getFinalDescriptor().contains("Super")));
     KmFunctionSubject kmFunction = kmClass.kmFunctionWithUniqueName("doStuff");
-    assertThat(kmFunction, isPresent());
+    assertThat(kmFunction, not(isPresent()));
     assertThat(kmFunction, not(isExtensionFunction()));
 
     ClassSubject bKt = inspector.clazz(bKtClassName);
diff --git a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInFunctionTest.java b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInFunctionTest.java
index 10afff3..875b475 100644
--- a/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInFunctionTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/metadata/MetadataRewriteInFunctionTest.java
@@ -22,11 +22,11 @@
 import com.android.tools.r8.utils.codeinspector.KmClassSubject;
 import com.android.tools.r8.utils.codeinspector.KmFunctionSubject;
 import com.android.tools.r8.utils.codeinspector.KmPackageSubject;
+import com.android.tools.r8.utils.codeinspector.Matchers;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import java.nio.file.Path;
 import java.util.Collection;
 import java.util.List;
-import org.junit.Ignore;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -75,13 +75,20 @@
   }
 
   @Test
-  @Ignore("b/154300326")
-  public void testMetadataInFunction_merged() throws Exception {
+  public void testMetadataInFunction_merged_compat() throws Exception {
+    testMetadataInFunction_merged(false);
+  }
+
+  @Test
+  public void testMetadataInFunction_merged_full() throws Exception {
+    testMetadataInFunction_merged(true);
+  }
+
+  public void testMetadataInFunction_merged(boolean full) throws Exception {
     Path libJar =
-        testForR8(parameters.getBackend())
-            .addProgramFiles(
-                funLibJarMap.getForConfiguration(kotlinc, targetVersion),
-                kotlinc.getKotlinAnnotationJar())
+        (full ? testForR8(parameters.getBackend()) : testForR8Compat(parameters.getBackend()))
+            .addClasspathFiles(kotlinc.getKotlinStdlibJar(), kotlinc.getKotlinAnnotationJar())
+            .addProgramFiles(funLibJarMap.getForConfiguration(kotlinc, targetVersion))
             // Keep the B class and its interface (which has the doStuff method).
             .addKeepRules("-keep class **.B")
             .addKeepRules("-keep class **.I { <methods>; }")
@@ -89,7 +96,7 @@
             .addKeepRules("-keep class **.BKt { <methods>; }")
             .addKeepAttributes(ProguardKeepAttributes.RUNTIME_VISIBLE_ANNOTATIONS)
             .compile()
-            .inspect(this::inspectMerged)
+            .inspect(inspector -> inspectMerged(inspector, full))
             .writeToZip();
 
     Path output =
@@ -97,7 +104,10 @@
             .addClasspathFiles(libJar)
             .addSourceFiles(getKotlinFileInTest(PKG_PREFIX + "/function_app", "main"))
             .setOutputPath(temp.newFolder().toPath())
-            .compile();
+            .compile(full || kotlinParameters.isOlderThanMinSupported());
+    if (full || kotlinParameters.isOlderThanMinSupported()) {
+      return;
+    }
 
     testForJvm()
         .addRunClasspathFiles(kotlinc.getKotlinStdlibJar(), libJar)
@@ -106,12 +116,12 @@
         .assertSuccessWithOutput(EXPECTED);
   }
 
-  private void inspectMerged(CodeInspector inspector) {
+  private void inspectMerged(CodeInspector inspector, boolean full) {
     String superClassName = PKG + ".function_lib.Super";
     String bClassName = PKG + ".function_lib.B";
     String bKtClassName = PKG + ".function_lib.BKt";
 
-    assertThat(inspector.clazz(superClassName), not(isPresent()));
+    assertThat(inspector.clazz(superClassName), Matchers.notIf(isPresent(), full));
 
     ClassSubject impl = inspector.clazz(bClassName);
     assertThat(impl, isPresentAndNotRenamed());
diff --git a/src/test/java/com/android/tools/r8/naming/sourcefile/StringPoolSizeWithLazyDexStringsTest.java b/src/test/java/com/android/tools/r8/naming/sourcefile/StringPoolSizeWithLazyDexStringsTest.java
new file mode 100644
index 0000000..8981bd9
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/sourcefile/StringPoolSizeWithLazyDexStringsTest.java
@@ -0,0 +1,80 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.naming.sourcefile;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+
+import com.android.tools.r8.DexSegments;
+import com.android.tools.r8.DexSegments.Command;
+import com.android.tools.r8.DexSegments.SegmentInfo;
+import com.android.tools.r8.R8TestCompileResult;
+import com.android.tools.r8.SourceFileEnvironment;
+import com.android.tools.r8.SourceFileProvider;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import java.util.Map;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class StringPoolSizeWithLazyDexStringsTest extends TestBase {
+
+  static final String EXPECTED = StringUtils.lines("Hello, world");
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDefaultDexRuntime().withApiLevel(AndroidApiLevel.B).build();
+  }
+
+  public StringPoolSizeWithLazyDexStringsTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(StringPoolSizeWithLazyDexStringsTest.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        // Ensure we have a source file that depends on the hash.
+        .apply(
+            b ->
+                b.getBuilder()
+                    .setSourceFileProvider(
+                        new SourceFileProvider() {
+                          @Override
+                          public String get(SourceFileEnvironment environment) {
+                            return environment.getMapHash();
+                          }
+                        }))
+        .compile()
+        // Ensure we are computing a mapping file.
+        .apply(r -> assertFalse(r.getProguardMap().isEmpty()))
+        .apply(this::checkStringSegmentSize)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput("");
+  }
+
+  private void checkStringSegmentSize(R8TestCompileResult result) throws Exception {
+    Map<Integer, SegmentInfo> segments =
+        DexSegments.run(Command.builder().addProgramFiles(result.writeToZip()).build());
+    SegmentInfo stringInfo = segments.get(Constants.TYPE_STRING_ID_ITEM);
+    assertEquals(8, stringInfo.getItemCount());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      // Empty program to reduce string count.
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java b/src/test/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java
index 92774e1..6264a4b 100644
--- a/src/test/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java
+++ b/src/test/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java
@@ -17,7 +17,7 @@
 public class SyntheticItemsTestUtils {
 
   public static String syntheticMethodName() {
-    return SyntheticNaming.INTERNAL_SYNTHETIC_METHOD_PREFIX;
+    return SyntheticNaming.INTERNAL_SYNTHETIC_METHOD_NAME;
   }
 
   public static ClassReference syntheticCompanionClass(Class<?> clazz) {
diff --git a/tools/r8_release.py b/tools/r8_release.py
index f9d14f9..d60baa0 100755
--- a/tools/r8_release.py
+++ b/tools/r8_release.py
@@ -15,7 +15,7 @@
 
 import utils
 
-R8_DEV_BRANCH = '3.2'
+R8_DEV_BRANCH = '3.3'
 R8_VERSION_FILE = os.path.join(
     'src', 'main', 'java', 'com', 'android', 'tools', 'r8', 'Version.java')
 THIS_FILE_RELATIVE = os.path.join('tools', 'r8_release.py')