Merge commit '1553132b6bf4b1b5c267ea6dde019d9b2b7be23c' into dev-release
diff --git a/build.gradle b/build.gradle
index 280db74..e614057 100644
--- a/build.gradle
+++ b/build.gradle
@@ -30,6 +30,7 @@
 ext {
     androidSupportVersion = '25.4.0'
     asmVersion = '9.4'  // When updating update tools/asmifier.py, build.src and Toolhelper as well.
+    javassistVersion = '3.29.2-GA'
     espressoVersion = '3.0.0'
     fastutilVersion = '7.2.0'
     guavaVersion = '30.1.1-jre'
@@ -269,6 +270,7 @@
     testCompile group: 'org.ow2.asm', name: 'asm-analysis', version: asmVersion
     testCompile group: 'org.ow2.asm', name: 'asm-util', version: asmVersion
     testCompile group: 'it.unimi.dsi', name: 'fastutil', version: fastutilVersion
+    testCompile group: 'org.javassist', name: 'javassist', version: javassistVersion
 
     examplesAndroidOCompile group: 'org.ow2.asm', name: 'asm', version: asmVersion
     examplesAndroidPCompile group: 'org.ow2.asm', name: 'asm', version: asmVersion
@@ -2301,9 +2303,6 @@
         println "Running with deprecated tool d8, not running any tests"
         include ""
     }
-    if (!project.hasProperty('all_tests')) {
-        exclude "com/android/tools/r8/art/dx/**"
-    }
     if (project.hasProperty('no_arttests')) {
         exclude "com/android/tools/r8/art/**"
     }
diff --git a/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelDatabaseHelper.java b/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelDatabaseHelper.java
index 03727d7..546b40b 100644
--- a/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelDatabaseHelper.java
+++ b/src/main/java/com/android/tools/r8/androidapi/AndroidApiLevelDatabaseHelper.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.androidapi;
 
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.utils.AndroidApiLevel;
@@ -14,6 +15,15 @@
 
   static void visitAdditionalKnownApiReferences(
       DexItemFactory factory, BiConsumer<DexReference, AndroidApiLevel> apiLevelConsumer) {
+    addStringBuilderAndBufferMethods(factory, apiLevelConsumer);
+    addConcurrentKeySetViewMethods(factory, apiLevelConsumer);
+    addNfcMethods(factory, apiLevelConsumer);
+    addWebkitCookieSyncManagerMethods(factory, apiLevelConsumer);
+    addChronoTimeMethods(factory, apiLevelConsumer);
+  }
+
+  private static void addStringBuilderAndBufferMethods(
+      DexItemFactory factory, BiConsumer<DexReference, AndroidApiLevel> apiLevelConsumer) {
     // StringBuilder and StringBuffer lack api definitions for the exact same methods in
     // api-versions.xml. See b/216587554 for related error.
     for (DexType type : new DexType[] {factory.stringBuilderType, factory.stringBufferType}) {
@@ -100,4 +110,199 @@
           AndroidApiLevel.B);
     }
   }
+
+  private static void addConcurrentKeySetViewMethods(
+      DexItemFactory factory, BiConsumer<DexReference, AndroidApiLevel> apiLevelConsumer) {
+    // KeysetView.getMap was also added in N (24).
+    apiLevelConsumer.accept(
+        factory.createMethod(
+            factory.concurrentHashMapKeySetViewType,
+            factory.createProto(factory.concurrentHashMapType),
+            "getMap"),
+        AndroidApiLevel.N);
+  }
+
+  private static void addNfcMethods(
+      DexItemFactory factory, BiConsumer<DexReference, AndroidApiLevel> apiLevelConsumer) {
+    String[] nfcClasses =
+        new String[] {
+          "Landroid/nfc/tech/Ndef;",
+          "Landroid/nfc/tech/NfcA;",
+          "Landroid/nfc/tech/NfcB;",
+          "Landroid/nfc/tech/NfcBarcode;",
+          "Landroid/nfc/tech/NfcF;",
+          "Landroid/nfc/tech/NdefFormatable;",
+          "Landroid/nfc/tech/IsoDep;",
+          "Landroid/nfc/tech/MifareClassic;",
+          "Landroid/nfc/tech/MifareUltralight;",
+          "Landroid/nfc/tech/NfcV;"
+        };
+    DexType tagType = factory.createType("Landroid/nfc/Tag;");
+    // Seems like all methods are available from api level G_MR1 but we choose K since some of these
+    // classes are introduced at 17.
+    for (String nfcClass : nfcClasses) {
+      DexType nfcClassType = factory.createType(nfcClass);
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              nfcClassType, factory.createProto(factory.booleanType), "isConnected"),
+          AndroidApiLevel.K);
+      apiLevelConsumer.accept(
+          factory.createMethod(nfcClassType, factory.createProto(tagType), "getTag"),
+          AndroidApiLevel.K);
+      apiLevelConsumer.accept(
+          factory.createMethod(nfcClassType, factory.createProto(factory.voidType), "close"),
+          AndroidApiLevel.K);
+      apiLevelConsumer.accept(
+          factory.createMethod(nfcClassType, factory.createProto(factory.voidType), "connect"),
+          AndroidApiLevel.K);
+    }
+  }
+
+  private static void addWebkitCookieSyncManagerMethods(
+      DexItemFactory factory, BiConsumer<DexReference, AndroidApiLevel> apiLevelConsumer) {
+    // All of these are added in android.jar from at least 14.
+    DexType cookieSyncManager = factory.createType("Landroid/webkit/CookieSyncManager;");
+    DexProto voidProto = factory.createProto(factory.voidType);
+    for (String methodName : new String[] {"sync", "resetSync", "startSync", "stopSync", "run"}) {
+      apiLevelConsumer.accept(
+          factory.createMethod(cookieSyncManager, voidProto, methodName), AndroidApiLevel.I);
+    }
+  }
+
+  private static void addChronoTimeMethods(
+      DexItemFactory factory, BiConsumer<DexReference, AndroidApiLevel> apiLevelConsumer) {
+    DexType valueRangeType = factory.createType("Ljava/time/temporal/ValueRange;");
+    DexType chronoLocalDateType = factory.createType("Ljava/time/chrono/ChronoLocalDate;");
+    DexType temporalType = factory.createType("Ljava/time/temporal/Temporal;");
+    DexType temporalFieldType = factory.createType("Ljava/time/temporal/TemporalField;");
+    DexType temporalUnitType = factory.createType("Ljava/time/temporal/TemporalUnit;");
+    DexType temporalAmountType = factory.createType("Ljava/time/temporal/TemporalAmount;");
+    DexType temporalAdjusterType = factory.createType("Ljava/time/temporal/TemporalAdjuster;");
+
+    // All of these classes was added in 26.
+    String[] timeClasses =
+        new String[] {
+          "Ljava/time/chrono/JapaneseDate;",
+          "Ljava/time/chrono/MinguoDate;",
+          "Ljava/time/chrono/HijrahDate;",
+          "Ljava/time/chrono/ThaiBuddhistDate;"
+        };
+    for (String timeClass : timeClasses) {
+      DexType timeType = factory.createType(timeClass);
+      // int lengthOfMonth()
+      apiLevelConsumer.accept(
+          factory.createMethod(timeType, factory.createProto(factory.intType), "lengthOfMonth"),
+          AndroidApiLevel.O);
+      // int lengthOfYear()
+      apiLevelConsumer.accept(
+          factory.createMethod(timeType, factory.createProto(factory.intType), "lengthOfYear"),
+          AndroidApiLevel.O);
+      // boolean isSupported(java.time.temporal.TemporalField)
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType, factory.createProto(factory.booleanType, temporalFieldType), "isSupported"),
+          AndroidApiLevel.O);
+      // java.time.temporal.ValueRange range(java.time.temporal.TemporalField)
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType, factory.createProto(valueRangeType, temporalFieldType), "range"),
+          AndroidApiLevel.O);
+      // long getLong(java.time.temporal.TemporalField)
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType, factory.createProto(factory.longType, temporalFieldType), "getLong"),
+          AndroidApiLevel.O);
+      // java.time.chrono.ChronoLocalDateTime atTime(java.time.LocalTime)
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType,
+              factory.createProto(
+                  factory.createType("Ljava/time/chrono/ChronoLocalDateTime;"),
+                  factory.createType("Ljava/time/LocalTime;")),
+              "atTime"),
+          AndroidApiLevel.O);
+      // java.time.chrono.ChronoPeriod
+      // java.time.chrono.JapaneseDate.until(java.time.chrono.ChronoLocalDate)
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType,
+              factory.createProto(
+                  factory.createType("Ljava/time/chrono/ChronoPeriod;"), chronoLocalDateType),
+              "until"),
+          AndroidApiLevel.O);
+      // long toEpochDay()
+      apiLevelConsumer.accept(
+          factory.createMethod(timeType, factory.createProto(factory.longType), "toEpochDay"),
+          AndroidApiLevel.O);
+      // long until(java.time.temporal.Temporal, java.time.temporal.TemporalUnit)
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType,
+              factory.createProto(factory.longType, temporalType, temporalUnitType),
+              "until"),
+          AndroidApiLevel.O);
+
+      // java.time.chrono.Era getEra()
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType,
+              factory.createProto(factory.createType("Ljava/time/chrono/Era;")),
+              "getEra"),
+          AndroidApiLevel.O);
+      // java.time.chrono.Chronology getChronology()
+      apiLevelConsumer.accept(
+          factory.createMethod(
+              timeType,
+              factory.createProto(factory.createType("Ljava/time/chrono/Chronology;")),
+              "getChronology"),
+          AndroidApiLevel.O);
+      DexType[] returnTypesForModificationMethods =
+          new DexType[] {chronoLocalDateType, temporalType};
+      for (DexType returnType : returnTypesForModificationMethods) {
+        // [returnType] minus(long, java.time.temporal.TemporalUnit)
+        apiLevelConsumer.accept(
+            factory.createMethod(
+                timeType,
+                factory.createProto(returnType, factory.longType, temporalUnitType),
+                "minus"),
+            AndroidApiLevel.O);
+        // [returnType] minus(java.time.temporal.TemporalAmount)
+        apiLevelConsumer.accept(
+            factory.createMethod(
+                timeType, factory.createProto(returnType, temporalAmountType), "minus"),
+            AndroidApiLevel.O);
+        // [returnType] plus(long, java.time.temporal.TemporalUnit)
+        apiLevelConsumer.accept(
+            factory.createMethod(
+                timeType,
+                factory.createProto(returnType, factory.longType, temporalUnitType),
+                "plus"),
+            AndroidApiLevel.O);
+        // [returnType] plus(java.time.temporal.TemporalAmount)
+        apiLevelConsumer.accept(
+            factory.createMethod(
+                timeType, factory.createProto(returnType, temporalAmountType), "plus"),
+            AndroidApiLevel.O);
+        // [returnType] with(java.time.temporal.TemporalField, long)
+        apiLevelConsumer.accept(
+            factory.createMethod(
+                timeType,
+                factory.createProto(returnType, temporalFieldType, factory.longType),
+                "with"),
+            AndroidApiLevel.O);
+        // [returnType] with(java.time.temporal.TemporalAdjuster)
+        apiLevelConsumer.accept(
+            factory.createMethod(
+                timeType, factory.createProto(returnType, temporalAdjusterType), "with"),
+            AndroidApiLevel.O);
+      }
+    }
+    // boolean java.time.chrono.HijrahDate.isLeapYear()
+    apiLevelConsumer.accept(
+        factory.createMethod(
+            factory.createType("Ljava/time/chrono/HijrahDate;"),
+            factory.createProto(factory.booleanType),
+            "isLeapYear"),
+        AndroidApiLevel.O);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/androidapi/ApiReferenceStubber.java b/src/main/java/com/android/tools/r8/androidapi/ApiReferenceStubber.java
index 8bbfcfd..c42f8c6 100644
--- a/src/main/java/com/android/tools/r8/androidapi/ApiReferenceStubber.java
+++ b/src/main/java/com/android/tools/r8/androidapi/ApiReferenceStubber.java
@@ -139,24 +139,25 @@
     if (!type.isClassType() || isJavaType(type)) {
       return;
     }
-    WorkList<DexType> workList = WorkList.newIdentityWorkList(type, seenTypes);
-    while (workList.hasNext()) {
-      DexClass clazz = appView.definitionFor(workList.next());
-      if (clazz == null || !clazz.isLibraryClass()) {
-        continue;
-      }
-      ComputedApiLevel androidApiLevel =
-          apiLevelCompute.computeApiLevelForLibraryReference(
-              clazz.type, ComputedApiLevel.unknown());
-      if (androidApiLevel.isGreaterThan(appView.computedMinApiLevel())
-          && androidApiLevel.isKnownApiLevel()) {
-        workList.addIfNotSeen(clazz.allImmediateSupertypes());
-        libraryClassesToMock.add(clazz.asLibraryClass());
-        referencingContexts
-            .computeIfAbsent(clazz.asLibraryClass(), ignoreKey(Sets::newConcurrentHashSet))
-            .add(context);
-      }
-    }
+    WorkList.newIdentityWorkList(type, seenTypes)
+        .process(
+            (classType, workList) -> {
+              DexClass clazz = appView.definitionFor(classType);
+              if (clazz == null || !clazz.isLibraryClass()) {
+                return;
+              }
+              ComputedApiLevel androidApiLevel =
+                  apiLevelCompute.computeApiLevelForLibraryReference(
+                      clazz.type, ComputedApiLevel.unknown());
+              if (androidApiLevel.isGreaterThan(appView.computedMinApiLevel())
+                  && androidApiLevel.isKnownApiLevel()) {
+                workList.addIfNotSeen(clazz.allImmediateSupertypes());
+                libraryClassesToMock.add(clazz.asLibraryClass());
+                referencingContexts
+                    .computeIfAbsent(clazz.asLibraryClass(), ignoreKey(Sets::newConcurrentHashSet))
+                    .add(context);
+              }
+            });
   }
 
   private boolean isJavaType(DexType type) {
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 7562429..51394a9 100644
--- a/src/main/java/com/android/tools/r8/androidapi/ComputedApiLevel.java
+++ b/src/main/java/com/android/tools/r8/androidapi/ComputedApiLevel.java
@@ -79,6 +79,8 @@
 
   OptionalBool isLessThanOrEqualTo(ComputedApiLevel other);
 
+  OptionalBool isGreaterThan(AndroidApiLevel other);
+
   class NotSetApiLevel implements ComputedApiLevel {
 
     private static final NotSetApiLevel INSTANCE = new NotSetApiLevel();
@@ -98,6 +100,12 @@
     }
 
     @Override
+    public OptionalBool isGreaterThan(AndroidApiLevel other) {
+      assert false : "Cannot compute relationship for not set";
+      return OptionalBool.unknown();
+    }
+
+    @Override
     public boolean isNotSetApiLevel() {
       return true;
     }
@@ -130,6 +138,11 @@
     }
 
     @Override
+    public OptionalBool isGreaterThan(AndroidApiLevel other) {
+      return OptionalBool.unknown();
+    }
+
+    @Override
     public boolean isUnknownApiLevel() {
       return true;
     }
@@ -192,6 +205,11 @@
     }
 
     @Override
+    public OptionalBool isGreaterThan(AndroidApiLevel other) {
+      return OptionalBool.of(apiLevel.isGreaterThan(other));
+    }
+
+    @Override
     public String toString() {
       return apiLevel.toString();
     }
diff --git a/src/main/java/com/android/tools/r8/cf/code/frame/UninitializedNew.java b/src/main/java/com/android/tools/r8/cf/code/frame/UninitializedNew.java
index a57c5e6..0d45c04 100644
--- a/src/main/java/com/android/tools/r8/cf/code/frame/UninitializedNew.java
+++ b/src/main/java/com/android/tools/r8/cf/code/frame/UninitializedNew.java
@@ -19,7 +19,7 @@
   private final DexType type;
 
   public UninitializedNew(CfLabel label, DexType type) {
-    assert type.isClassType();
+    assert type == null || type.isClassType();
     this.label = label;
     this.type = type;
   }
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 270fcf2..d163330 100644
--- a/src/main/java/com/android/tools/r8/dex/VirtualFile.java
+++ b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
@@ -1335,7 +1335,7 @@
 
       private static Predicate<DexProgramClass> getStartupClassPredicate(
           StartupProfile startupProfile) {
-        return clazz -> startupProfile.containsClassRule(clazz.getType());
+        return clazz -> startupProfile.isStartupClass(clazz.getType());
       }
 
       public List<DexProgramClass> getStartupClasses() {
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupProfile.java b/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupProfile.java
index 7f2a248..a91c273 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupProfile.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupProfile.java
@@ -59,6 +59,11 @@
   }
 
   @Override
+  public boolean isStartupClass(DexType type) {
+    return false;
+  }
+
+  @Override
   public EmptyStartupProfile rewrittenWithLens(GraphLens graphLens) {
     return this;
   }
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/StartupProfile.java b/src/main/java/com/android/tools/r8/experimental/startup/StartupProfile.java
index b85dbaa..0689d7c 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/StartupProfile.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/StartupProfile.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexReference;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.origin.Origin;
@@ -130,6 +131,8 @@
     return StartupProfile.merge(startupProfiles);
   }
 
+  public abstract boolean isStartupClass(DexType type);
+
   public abstract Collection<StartupProfileRule> getRules();
 
   public abstract boolean isEmpty();
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/profile/NonEmptyStartupProfile.java b/src/main/java/com/android/tools/r8/experimental/startup/profile/NonEmptyStartupProfile.java
index ab251a8..4b35a4b 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/profile/NonEmptyStartupProfile.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/profile/NonEmptyStartupProfile.java
@@ -15,28 +15,33 @@
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.synthesis.SyntheticItems;
+import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.ThrowingConsumer;
 import java.util.Collection;
 import java.util.LinkedHashMap;
+import java.util.Set;
 import java.util.function.BiConsumer;
 
 public class NonEmptyStartupProfile extends StartupProfile {
 
-  private final LinkedHashMap<DexReference, StartupProfileRule> startupItems;
+  private final Set<DexType> startupClasses;
+  private final LinkedHashMap<DexReference, StartupProfileRule> startupRules;
 
-  public NonEmptyStartupProfile(LinkedHashMap<DexReference, StartupProfileRule> startupItems) {
-    assert !startupItems.isEmpty();
-    this.startupItems = startupItems;
-  }
-
-  @Override
-  public boolean containsMethodRule(DexMethod method) {
-    return startupItems.containsKey(method);
+  public NonEmptyStartupProfile(LinkedHashMap<DexReference, StartupProfileRule> startupRules) {
+    assert !startupRules.isEmpty();
+    this.startupClasses =
+        SetUtils.mapIdentityHashSet(startupRules.keySet(), DexReference::getContextType);
+    this.startupRules = startupRules;
   }
 
   @Override
   public boolean containsClassRule(DexType type) {
-    return startupItems.containsKey(type);
+    return startupRules.containsKey(type);
+  }
+
+  @Override
+  public boolean containsMethodRule(DexMethod method) {
+    return startupRules.containsKey(method);
   }
 
   @Override
@@ -51,17 +56,17 @@
 
   @Override
   public StartupProfileClassRule getClassRule(DexType type) {
-    return (StartupProfileClassRule) startupItems.get(type);
+    return (StartupProfileClassRule) startupRules.get(type);
   }
 
   @Override
   public StartupProfileMethodRule getMethodRule(DexMethod method) {
-    return (StartupProfileMethodRule) startupItems.get(method);
+    return (StartupProfileMethodRule) startupRules.get(method);
   }
 
   @Override
   public Collection<StartupProfileRule> getRules() {
-    return startupItems.values();
+    return startupRules.values();
   }
 
   @Override
@@ -70,6 +75,11 @@
   }
 
   @Override
+  public boolean isStartupClass(DexType type) {
+    return startupClasses.contains(type);
+  }
+
+  @Override
   public StartupProfile rewrittenWithLens(GraphLens graphLens) {
     return transform(
         (classRule, builder) ->
@@ -85,7 +95,7 @@
   }
 
   public int size() {
-    return startupItems.size();
+    return startupRules.size();
   }
 
   /**
@@ -176,7 +186,7 @@
   private StartupProfile transform(
       BiConsumer<StartupProfileClassRule, Builder> classRuleTransformer,
       BiConsumer<StartupProfileMethodRule, Builder> methodRuleTransformer) {
-    Builder builder = builderWithCapacity(startupItems.size());
+    Builder builder = builderWithCapacity(startupRules.size());
     forEachRule(
         classRule -> classRuleTransformer.accept(classRule, builder),
         methodRule -> methodRuleTransformer.accept(methodRule, builder));
diff --git a/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java b/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java
index dc33db7..88bfb4f 100644
--- a/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java
+++ b/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java
@@ -175,7 +175,7 @@
       feature = classToFeatureSplitMap.getOrDefault(type, FeatureSplit.BASE);
     }
     if (feature.isBase()) {
-      return !startupProfile.containsClassRule(type)
+      return !startupProfile.isStartupClass(type)
               || options.getStartupOptions().isStartupBoundaryOptimizationsEnabled()
           ? FeatureSplit.BASE
           : FeatureSplit.BASE_STARTUP;
diff --git a/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java b/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java
index 37f1494..4c3c809 100644
--- a/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java
+++ b/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java
@@ -77,8 +77,8 @@
     } else if (callerIsStartupMethod.isFalse()) {
       // If the caller is not a startup method, then only allow inlining if the caller is not a
       // startup class or the callee is a startup class.
-      if (startupProfile.containsClassRule(caller.getHolderType())
-          && !startupProfile.containsClassRule(callee.getHolderType())) {
+      if (startupProfile.isStartupClass(caller.getHolderType())
+          && !startupProfile.isStartupClass(callee.getHolderType())) {
         return false;
       }
     }
@@ -114,8 +114,8 @@
     // If the source class is a startup class then require that the target class is also a startup
     // class.
     StartupProfile startupProfile = appView.getStartupProfile();
-    if (startupProfile.containsClassRule(sourceClass.getType())
-        && !startupProfile.containsClassRule(targetClass.getType())) {
+    if (startupProfile.isStartupClass(sourceClass.getType())
+        && !startupProfile.isStartupClass(targetClass.getType())) {
       return false;
     }
     return 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 e0e16a6..9cdb7f2 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -305,6 +305,10 @@
   public final DexString streamDescriptor = createString("Ljava/util/stream/Stream;");
   public final DexString arraysDescriptor = createString("Ljava/util/Arrays;");
   public final DexString threadLocalDescriptor = createString("Ljava/lang/ThreadLocal;");
+  public final DexString concurrentHashMapDescriptor =
+      createString("Ljava/util/concurrent/ConcurrentHashMap;");
+  public final DexString concurrentHaspMapKeySetViewDescriptor =
+      createString("Ljava/util/concurrent/ConcurrentHashMap$KeySetView;");
 
   public final DexString throwableDescriptor = createString(throwableDescriptorString);
   public final DexString illegalAccessErrorDescriptor =
@@ -478,6 +482,10 @@
   public final DexType optionalLongType = createStaticallyKnownType(optionalLongDescriptor);
   public final DexType streamType = createStaticallyKnownType(streamDescriptor);
   public final DexType threadLocalType = createStaticallyKnownType(threadLocalDescriptor);
+  public final DexType concurrentHashMapType =
+      createStaticallyKnownType(concurrentHashMapDescriptor);
+  public final DexType concurrentHashMapKeySetViewType =
+      createStaticallyKnownType(concurrentHaspMapKeySetViewDescriptor);
 
   public final DexType bufferType = createStaticallyKnownType(bufferDescriptor);
   public final DexType byteBufferType = createStaticallyKnownType(byteBufferDescriptor);
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java
index 3492c06..b761eb99b 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java
@@ -182,20 +182,26 @@
 
   public static GenericSignatureContextBuilder createForSingleClass(
       AppView<?> appView, DexProgramClass clazz) {
-    WorkList<DexProgramClass> workList = WorkList.newIdentityWorkList(clazz);
-    while (workList.hasNext()) {
-      DexProgramClass current = workList.next();
-      DexClass outer = null;
-      if (current.getEnclosingMethodAttribute() != null) {
-        outer = appView.definitionFor(current.getEnclosingMethodAttribute().getEnclosingType());
-      } else if (current.getInnerClassAttributeForThisClass() != null) {
-        outer = appView.definitionFor(current.getInnerClassAttributeForThisClass().getOuter());
-      }
-      if (outer != null && outer.isProgramClass()) {
-        workList.addIfNotSeen(outer.asProgramClass());
-      }
-    }
-    return create(appView, workList.getSeenSet());
+    return create(
+        appView,
+        WorkList.newIdentityWorkList(clazz)
+            .process(
+                (current, workList) -> {
+                  DexClass outer = null;
+                  if (current.getEnclosingMethodAttribute() != null) {
+                    outer =
+                        appView.definitionFor(
+                            current.getEnclosingMethodAttribute().getEnclosingType());
+                  } else if (current.getInnerClassAttributeForThisClass() != null) {
+                    outer =
+                        appView.definitionFor(
+                            current.getInnerClassAttributeForThisClass().getOuter());
+                  }
+                  if (outer != null && outer.isProgramClass()) {
+                    workList.addIfNotSeen(outer.asProgramClass());
+                  }
+                })
+            .getSeenSet());
   }
 
   public TypeParameterContext computeTypeParameterContext(
diff --git a/src/main/java/com/android/tools/r8/graph/LazyCfCode.java b/src/main/java/com/android/tools/r8/graph/LazyCfCode.java
index 153f85f..d393d72 100644
--- a/src/main/java/com/android/tools/r8/graph/LazyCfCode.java
+++ b/src/main/java/com/android/tools/r8/graph/LazyCfCode.java
@@ -493,7 +493,7 @@
             builder.push(frameType);
           }
         }
-        instructions.add(builder.build());
+        instructions.set(instructionIndex, builder.build());
       }
     }
 
diff --git a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
index 1aa8117..98eab7f 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectAllocationInfoCollectionImpl.java
@@ -217,26 +217,27 @@
       }
     }
 
-    while (worklist.hasNext()) {
-      DexClass clazz = worklist.next();
-      if (clazz.isProgramClass()) {
-        DexProgramClass programClass = clazz.asProgramClass();
-        if (isInstantiatedDirectly(programClass)
-            || isInterfaceWithUnknownSubtypeHierarchy(programClass)) {
-          if (onClass.apply(programClass).shouldBreak()) {
-            return TraversalContinuation.doBreak();
+    return worklist.run(
+        clazz -> {
+          if (clazz.isProgramClass()) {
+            DexProgramClass programClass = clazz.asProgramClass();
+            if (isInstantiatedDirectly(programClass)
+                || isInterfaceWithUnknownSubtypeHierarchy(programClass)) {
+              if (onClass.apply(programClass).shouldBreak()) {
+                return TraversalContinuation.doBreak();
+              }
+            }
           }
-        }
-      }
-      worklist.addIfNotSeen(instantiatedHierarchy.getOrDefault(clazz.type, Collections.emptySet()));
-      for (LambdaDescriptor lambda :
-          instantiatedLambdas.getOrDefault(clazz.type, Collections.emptyList())) {
-        if (onLambda.apply(lambda).shouldBreak()) {
-          return TraversalContinuation.doBreak();
-        }
-      }
-    }
-    return TraversalContinuation.doContinue();
+          worklist.addIfNotSeen(
+              instantiatedHierarchy.getOrDefault(clazz.type, Collections.emptySet()));
+          for (LambdaDescriptor lambda :
+              instantiatedLambdas.getOrDefault(clazz.type, Collections.emptyList())) {
+            if (onLambda.apply(lambda).shouldBreak()) {
+              return TraversalContinuation.doBreak();
+            }
+          }
+          return TraversalContinuation.doContinue();
+        });
   }
 
   public Set<DexType> getInstantiatedLambdaInterfaces() {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java
index e77b31a..6e94908 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java
@@ -79,33 +79,33 @@
     // Find the set of types that must not be merged, because they could lead to a constructor
     // collision.
     Set<DexType> collisionResolution = Sets.newIdentityHashSet();
-    WorkList<DexProgramClass> workList = WorkList.newIdentityWorkList(appView.appInfo().classes());
-    while (workList.hasNext()) {
-      // Iterate over all the instance initializers of the current class. If the current class is in
-      // a merge group, we must include all constructors of the entire merge group.
-      DexProgramClass current = workList.next();
-      Iterable<DexProgramClass> group =
-          groupsByType.containsKey(current.getType())
-              ? groupsByType.get(current.getType())
-              : IterableUtils.singleton(current);
-      Set<DexMethod> seen = Sets.newIdentityHashSet();
-      for (DexProgramClass clazz : group) {
-        for (DexEncodedMethod method :
-            clazz.directMethods(DexEncodedMethod::isInstanceInitializer)) {
-          // Rewrite the constructor reference using the current merge groups.
-          DexMethod newReference = rewriteReference(method.getReference(), groupsByType);
-          if (!seen.add(newReference)) {
-            // Found a collision. Block all referenced types from being merged.
-            for (DexType type : method.getProto().getBaseTypes(dexItemFactory)) {
-              if (type.isClassType() && groupsByType.containsKey(type)) {
-                collisionResolution.add(type);
+    // Iterate over all the instance initializers of the current class. If the current class is in
+    // a merge group, we must include all constructors of the entire merge group.
+    WorkList.newIdentityWorkList(appView.appInfo().classes())
+        .process(
+            (current, workList) -> {
+              Iterable<DexProgramClass> group =
+                  groupsByType.containsKey(current.getType())
+                      ? groupsByType.get(current.getType())
+                      : IterableUtils.singleton(current);
+              Set<DexMethod> seen = Sets.newIdentityHashSet();
+              for (DexProgramClass clazz : group) {
+                for (DexEncodedMethod method :
+                    clazz.directMethods(DexEncodedMethod::isInstanceInitializer)) {
+                  // Rewrite the constructor reference using the current merge groups.
+                  DexMethod newReference = rewriteReference(method.getReference(), groupsByType);
+                  if (!seen.add(newReference)) {
+                    // Found a collision. Block all referenced types from being merged.
+                    for (DexType type : method.getProto().getBaseTypes(dexItemFactory)) {
+                      if (type.isClassType() && groupsByType.containsKey(type)) {
+                        collisionResolution.add(type);
+                      }
+                    }
+                  }
+                }
               }
-            }
-          }
-        }
-      }
-      workList.markAsSeen(group);
-    }
+              workList.markAsSeen(group);
+            });
     return collisionResolution;
   }
 
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java
index fd24d1f..a64402a 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java
@@ -133,21 +133,21 @@
     WorkList<DexProgramClass> workList = WorkList.newWorkList(new LinkedHashSet<>());
     // Intentionally not marking `clazz` as seen, since we only want the strict sub/super types.
     workList.addIgnoringSeenSet(clazz);
-    while (workList.hasNext()) {
-      DexProgramClass interfaceDefinition = workList.next();
-      MergeGroup group = committed.get(interfaceDefinition);
-      if (group != null) {
-        workList.addIfNotSeen(group);
-      }
-      for (DexType immediateSubOrSuperInterfaceType :
-          immediateSubOrSuperInterfacesProvider.apply(interfaceDefinition)) {
-        DexProgramClass immediateSubOrSuperInterface =
-            asProgramClassOrNull(appView.definitionFor(immediateSubOrSuperInterfaceType));
-        if (immediateSubOrSuperInterface != null) {
-          workList.addIfNotSeen(immediateSubOrSuperInterface);
-        }
-      }
-    }
+    workList.process(
+        interfaceDefinition -> {
+          MergeGroup group = committed.get(interfaceDefinition);
+          if (group != null) {
+            workList.addIfNotSeen(group);
+          }
+          for (DexType immediateSubOrSuperInterfaceType :
+              immediateSubOrSuperInterfacesProvider.apply(interfaceDefinition)) {
+            DexProgramClass immediateSubOrSuperInterface =
+                asProgramClassOrNull(appView.definitionFor(immediateSubOrSuperInterfaceType));
+            if (immediateSubOrSuperInterface != null) {
+              workList.addIfNotSeen(immediateSubOrSuperInterface);
+            }
+          }
+        });
     assert !workList.isSeen(clazz);
     return workList.getMutableSeenSet();
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
index 3891d20..5bf3bd6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
@@ -35,6 +35,7 @@
 
 public class InvokeDirect extends InvokeMethodWithReceiver {
 
+  // TODO(b/145775365): The interface bit should never be needed once invoke special is in the IR.
   private final boolean isInterface;
 
   public InvokeDirect(DexMethod target, Value result, List<Value> arguments) {
@@ -220,7 +221,7 @@
 
   @Override
   public void buildLir(LirBuilder<Value, ?> builder) {
-    builder.addInvokeDirect(getInvokedMethod(), arguments());
+    builder.addInvokeDirect(getInvokedMethod(), arguments(), isInterface);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
index 3acd5fc..afeda79 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
@@ -247,7 +247,7 @@
 
   @Override
   public void buildLir(LirBuilder<Value, ?> builder) {
-    builder.addInvokeStatic(getInvokedMethod(), arguments());
+    builder.addInvokeStatic(getInvokedMethod(), arguments(), isInterface);
   }
 
   public static class Builder extends InvokeMethod.Builder<Builder, InvokeStatic> {
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
index 4eaae3c..b63fc98 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
@@ -22,11 +22,13 @@
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
+import com.android.tools.r8.lightir.LirBuilder;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.List;
 
 public class InvokeSuper extends InvokeMethodWithReceiver {
 
+  // TODO(b/145775365): The interface bit should never be needed once invoke special is in the IR.
   public final boolean isInterface;
 
   public InvokeSuper(DexMethod target, Value result, List<Value> arguments, boolean isInterface) {
@@ -140,4 +142,9 @@
   void internalRegisterUse(UseRegistry<?> registry, DexClassAndMethod context) {
     registry.registerInvokeSuper(getInvokedMethod());
   }
+
+  @Override
+  public void buildLir(LirBuilder<Value, ?> builder) {
+    builder.addInvokeSuper(getInvokedMethod(), arguments(), isInterface);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Return.java b/src/main/java/com/android/tools/r8/ir/code/Return.java
index 7cd7505..1efb557 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Return.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Return.java
@@ -141,9 +141,16 @@
 
   public static class Builder extends BuilderBase<Builder, Return> {
 
+    private Value returnValue = null;
+
+    public Builder setReturnValue(Value returnValue) {
+      this.returnValue = returnValue;
+      return self();
+    }
+
     @Override
     public Return build() {
-      return amend(new Return());
+      return amend(returnValue == null ? new Return() : new Return(returnValue));
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/Throw.java b/src/main/java/com/android/tools/r8/ir/code/Throw.java
index 7968409..86b9f0e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Throw.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Throw.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
+import com.android.tools.r8.lightir.LirBuilder;
 
 public class Throw extends JumpInstruction {
 
@@ -88,6 +89,11 @@
   }
 
   @Override
+  public void buildLir(LirBuilder<Value, ?> builder) {
+    builder.addThrow(exception());
+  }
+
+  @Override
   public boolean throwsNpeIfValueIsNull(Value value, AppView<?> appView, ProgramMethod context) {
     if (exception() == value) {
       return true;
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 4291c1c..fc8d1f2 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
@@ -43,6 +43,7 @@
 import com.android.tools.r8.ir.optimize.NaturalIntLoopRemover;
 import com.android.tools.r8.ir.optimize.RedundantFieldLoadAndStoreElimination;
 import com.android.tools.r8.ir.optimize.ReflectionOptimizer;
+import com.android.tools.r8.ir.optimize.RemoveVerificationErrorForUnknownReturnedValues;
 import com.android.tools.r8.ir.optimize.ServiceLoaderRewriter;
 import com.android.tools.r8.ir.optimize.api.InstanceInitializerOutliner;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInliner;
@@ -120,6 +121,8 @@
   private final EnumValueOptimizer enumValueOptimizer;
   protected final EnumUnboxer enumUnboxer;
   protected final InstanceInitializerOutliner instanceInitializerOutliner;
+  protected final RemoveVerificationErrorForUnknownReturnedValues
+      removeVerificationErrorForUnknownReturnedValues;
 
   public final AssumeInserter assumeInserter;
   private final DynamicTypeOptimization dynamicTypeOptimization;
@@ -206,6 +209,7 @@
       this.enumUnboxer = EnumUnboxer.empty();
       this.assumeInserter = null;
       this.instanceInitializerOutliner = null;
+      this.removeVerificationErrorForUnknownReturnedValues = null;
       return;
     }
     this.instructionDesugaring =
@@ -223,6 +227,11 @@
     } else {
       this.instanceInitializerOutliner = null;
     }
+    removeVerificationErrorForUnknownReturnedValues =
+        (appView.options().apiModelingOptions().enableLibraryApiModeling
+                && appView.options().canHaveVerifyErrorForUnknownUnusedReturnValue())
+            ? new RemoveVerificationErrorForUnknownReturnedValues(appView)
+            : null;
     if (appView.enableWholeProgramOptimizations()) {
       assert appView.appInfo().hasLiveness();
       assert appView.rootSet() != null;
@@ -739,7 +748,7 @@
     timing.begin("Split range invokes");
     codeRewriter.splitRangeInvokeConstants(code);
     timing.end();
-    timing.begin("Propogate sparse conditionals");
+    timing.begin("Propagate sparse conditionals");
     new SparseConditionalConstantPropagation(appView, code).run();
     timing.end();
     timing.begin("Rewrite always throwing instructions");
@@ -862,6 +871,10 @@
       previous = printMethod(code, "IR after shorten live ranges (SSA)", previous);
     }
 
+    if (removeVerificationErrorForUnknownReturnedValues != null) {
+      removeVerificationErrorForUnknownReturnedValues.run(context, code, timing);
+    }
+
     timing.begin("Canonicalize idempotent calls");
     idempotentFunctionCallCanonicalizer.canonicalize(code);
     timing.end();
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
index e2a0c14..9085bd8 100644
--- 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
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.ir.desugar.apimodel;
 
+import static com.android.tools.r8.utils.AndroidApiLevelUtils.isApiLevelLessThanOrEqualToG;
 import static com.android.tools.r8.utils.AndroidApiLevelUtils.isOutlinedAtSameOrLowerLevel;
 import static org.objectweb.asm.Opcodes.INVOKESTATIC;
 
@@ -38,7 +39,6 @@
 import com.android.tools.r8.ir.synthetic.ForwardMethodBuilder;
 import com.android.tools.r8.ir.synthetic.InstanceOfSourceCode;
 import com.android.tools.r8.synthesis.SyntheticMethodBuilder;
-import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApiLevelUtils;
 import com.android.tools.r8.utils.Pair;
 import com.android.tools.r8.utils.TraversalContinuation;
@@ -114,7 +114,7 @@
                 appView, appView.appInfoForDesugaring(), holder, reference.asDexMember());
     ComputedApiLevel referenceApiLevel = classAndApiLevel.getSecond();
     if (appView.computedMinApiLevel().isGreaterThanOrEqualTo(referenceApiLevel)
-        || isApiLevelLessThanOrEqualTo9(referenceApiLevel)
+        || isApiLevelLessThanOrEqualToG(referenceApiLevel)
         || referenceApiLevel.isUnknownApiLevel()) {
       return appView.computedMinApiLevel();
     }
@@ -184,11 +184,6 @@
     return traversalResult.isBreak() ? traversalResult.asBreak().getValue() : null;
   }
 
-  private boolean isApiLevelLessThanOrEqualTo9(ComputedApiLevel apiLevel) {
-    return apiLevel.isKnownApiLevel()
-        && apiLevel.asKnownApiLevel().getApiLevel().isLessThanOrEqualTo(AndroidApiLevel.G);
-  }
-
   private Collection<CfInstruction> desugarLibraryCall(
       UniqueContext uniqueContext,
       CfInstruction instruction,
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/RemoveVerificationErrorForUnknownReturnedValues.java b/src/main/java/com/android/tools/r8/ir/optimize/RemoveVerificationErrorForUnknownReturnedValues.java
new file mode 100644
index 0000000..1b4ad0f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/RemoveVerificationErrorForUnknownReturnedValues.java
@@ -0,0 +1,217 @@
+// Copyright (c) 2023, 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;
+
+import static com.android.tools.r8.utils.AndroidApiLevelUtils.isApiLevelLessThanOrEqualToG;
+
+import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
+import com.android.tools.r8.androidapi.ComputedApiLevel;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.code.CheckCast;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.Return;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.synthesis.SyntheticItems;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.Timing;
+import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Sets;
+import java.util.Collections;
+import java.util.Set;
+
+/***
+ * Some Dalvik and ART runtimes have problems with verification when it comes to computing subtype
+ * relationship. Take the following code:
+ * <pre>
+ *     public LibraryClass callLibraryWithDirectReturn() {
+ *       if (AndroidBuildVersion.SDK_INT < 31) {
+ *         return null;
+ *       } else {
+ *         LibrarySub sub = Outline.create();
+ *         return sub;
+ *       }
+ *     }
+ * </pre>
+ *
+ * This can cause verification failures if LibraryClass is known but LibrarySub is unknown. It seems
+ * like the problem is that the verifier assumes that it can compute the relationship. If we add
+ * an instruction that causes soft-verification we remove the hard verification error:
+ * <pre>
+ *     public LibraryClass callLibraryWithDirectReturn() {
+ *       if (AndroidBuildVersion.SDK_INT < 31) {
+ *         return null;
+ *       } else {
+ *         LibrarySub sub = Outline.create();
+ *         sub.foo();
+ *         return sub;
+ *       }
+ *     }
+ * </pre>
+ *
+ * The assumption here is that the verifier will figure out that it needs to run this by
+ * interpreting and bails out.
+ *
+ * We fix the issue here, both for our outlines and for manual outlines, by putting in a check-cast
+ * on the return value if a potential unknown library subtype flows to the return value.
+ * <pre>
+ *     public LibraryClass callLibraryWithDirectReturn() {
+ *       if (AndroidBuildVersion.SDK_INT < 31) {
+ *         return null;
+ *       } else {
+ *         LibrarySub sub = Outline.create();
+ *         return (LibraryClass)sub;
+ *       }
+ *     }
+ * </pre>
+ *
+ * See b/272725341 for more information.
+ */
+public class RemoveVerificationErrorForUnknownReturnedValues {
+
+  private final AppView<?> appView;
+  private final AndroidApiLevelCompute apiLevelCompute;
+  private final SyntheticItems syntheticItems;
+
+  public RemoveVerificationErrorForUnknownReturnedValues(AppView<?> appView) {
+    this.appView = appView;
+    this.apiLevelCompute = appView.apiLevelCompute();
+    this.syntheticItems = appView.getSyntheticItems();
+  }
+
+  private AppInfoWithClassHierarchy getAppInfoWithClassHierarchy() {
+    return appView.appInfoForDesugaring();
+  }
+
+  public void run(ProgramMethod context, IRCode code, Timing timing) {
+    timing.begin("Compute and insert checkcast on return values");
+    AppInfoWithClassHierarchy appInfoWithClassHierarchy = getAppInfoWithClassHierarchy();
+    Set<Return> returnValuesNeedingCheckCast =
+        getReturnsPotentiallyNeedingCheckCast(appInfoWithClassHierarchy, context, code);
+    insertCheckCastForReturnValues(context, code, returnValuesNeedingCheckCast);
+    timing.end();
+  }
+
+  private Set<Return> getReturnsPotentiallyNeedingCheckCast(
+      AppInfoWithClassHierarchy appInfo, ProgramMethod context, IRCode code) {
+    if (syntheticItems.isSyntheticOfKind(context.getHolderType(), kinds -> kinds.API_MODEL_OUTLINE)
+        || syntheticItems.isSyntheticOfKind(
+            context.getHolderType(), kinds -> kinds.API_MODEL_OUTLINE_WITHOUT_GLOBAL_MERGING)) {
+      return Collections.emptySet();
+    }
+    DexType returnType = context.getReturnType();
+    if (!returnType.isClassType()) {
+      return Collections.emptySet();
+    }
+    // Everything is assignable to object type and the verifier do not throw an error here.
+    if (returnType == appView.dexItemFactory().objectType) {
+      return Collections.emptySet();
+    }
+    DexClass returnTypeClass = appInfo.definitionFor(returnType);
+    if (returnTypeClass == null || !returnTypeClass.isLibraryClass()) {
+      return Collections.emptySet();
+    }
+    ComputedApiLevel computedReturnApiLevel =
+        apiLevelCompute.computeApiLevelForLibraryReference(returnType, ComputedApiLevel.unknown());
+    if (computedReturnApiLevel.isUnknownApiLevel()) {
+      return Collections.emptySet();
+    }
+    Set<Value> seenSet = Sets.newIdentityHashSet();
+    Set<Return> returnsOfInterest = Sets.newIdentityHashSet();
+    code.computeNormalExitBlocks()
+        .forEach(
+            basicBlock -> {
+              Return exit = basicBlock.exit().asReturn();
+              Value aliasedReturnValue = exit.returnValue().getAliasedValue();
+              if (shouldInsertCheckCastForValue(appInfo, returnType, aliasedReturnValue, seenSet)) {
+                returnsOfInterest.add(exit);
+              }
+            });
+    return returnsOfInterest;
+  }
+
+  private boolean shouldInsertCheckCastForValue(
+      AppInfoWithClassHierarchy appInfo, DexType returnType, Value value, Set<Value> seenSet) {
+    WorkList<Value> workList = WorkList.newIdentityWorkList(value, seenSet);
+    while (workList.hasNext()) {
+      Value next = workList.next();
+      if (next.isPhi()) {
+        workList.addIfNotSeen(next.asPhi().getOperands());
+      }
+      TypeElement type = next.getType();
+      if (!type.isClassType()) {
+        assert type.isNullType() || type.isArrayType();
+        continue;
+      }
+      DexType returnValueType = type.asClassType().getClassType();
+      DexClass returnValueClass = appInfo.definitionFor(returnValueType);
+      if (returnValueClass == null || !returnValueClass.isLibraryClass()) {
+        continue;
+      }
+      if (!appInfo.isStrictSubtypeOf(returnValueType, returnType)) {
+        continue;
+      }
+      ComputedApiLevel computedValueApiLevel =
+          apiLevelCompute.computeApiLevelForLibraryReference(
+              returnValueType, ComputedApiLevel.unknown());
+      // We could in principle also bail out if the computedValueApiLevel == computedReturnApiLevel,
+      // however, if we stub the return type class we will introduce the error again. We do not know
+      // at this point if we stub the returnTypeClass.
+      ComputedApiLevel minApiLevel = appView.computedMinApiLevel();
+      if (!computedValueApiLevel.isUnknownApiLevel()
+          && !isApiLevelLessThanOrEqualToG(computedValueApiLevel)
+          && computedValueApiLevel.isGreaterThan(minApiLevel)
+          && isDalvikOrSubTypeIntroducedLaterThanAndroidR(minApiLevel, computedValueApiLevel)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  // Dalvik and some new ART versions have a stricter verifier that do not allow type-checking
+  // unknown return value types against a known return type.
+  private boolean isDalvikOrSubTypeIntroducedLaterThanAndroidR(
+      ComputedApiLevel minApiLevel, ComputedApiLevel subTypeApiLevel) {
+    if (minApiLevel.isLessThanOrEqualTo(AndroidApiLevel.K_WATCH).isPossiblyTrue()) {
+      return true;
+    }
+    return subTypeApiLevel.isGreaterThan(AndroidApiLevel.R).isPossiblyTrue();
+  }
+
+  private void insertCheckCastForReturnValues(
+      ProgramMethod context, IRCode code, Set<Return> returnsNeedingCast) {
+    if (returnsNeedingCast.isEmpty()) {
+      return;
+    }
+    InstructionListIterator iterator = code.instructionListIterator();
+    while (iterator.hasNext()) {
+      Return returnInstruction = iterator.next().asReturn();
+      if (returnInstruction == null) {
+        continue;
+      }
+      DexType returnType = context.getReturnType();
+      Value returnValue = returnInstruction.returnValue();
+      CheckCast checkCast =
+          CheckCast.builder()
+              .setObject(returnValue)
+              .setFreshOutValue(
+                  code, returnType.toTypeElement(appView, returnValue.getType().nullability()))
+              .setCastType(returnType)
+              .setPosition(returnInstruction.getPosition())
+              .build();
+      iterator.replaceCurrentInstruction(checkCast);
+      iterator.add(
+          Return.builder()
+              .setPosition(returnInstruction.getPosition())
+              .setReturnValue(checkCast.outValue())
+              .build());
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java b/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
index 689d5ff..ebaa39c 100644
--- a/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
+++ b/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
@@ -33,6 +33,7 @@
 import com.android.tools.r8.ir.code.InvokeDirect;
 import com.android.tools.r8.ir.code.InvokeInterface;
 import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.InvokeSuper;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.MoveException;
 import com.android.tools.r8.ir.code.NewInstance;
@@ -43,6 +44,7 @@
 import com.android.tools.r8.ir.code.Position.SyntheticPosition;
 import com.android.tools.r8.ir.code.Return;
 import com.android.tools.r8.ir.code.StaticGet;
+import com.android.tools.r8.ir.code.Throw;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.MethodConversionOptions.MutableMethodConversionOptions;
 import com.android.tools.r8.lightir.LirCode.PositionEntry;
@@ -189,6 +191,15 @@
         BasicBlock block = blocks.get(blockIndices.getInt(i));
         block.setFilled();
         blockList.add(block);
+        // LIR has no value-user info so after building is done, removed unused values.
+        for (Instruction instruction : block.getInstructions()) {
+          if (instruction.hasOutValue()
+              && !instruction.isArgument()
+              && !instruction.isMoveException()
+              && instruction.hasUnusedOutValue()) {
+            instruction.clearOutValue();
+          }
+        }
       }
       for (int i = 0; i < peekNextInstructionIndex(); ++i) {
         valueNumberGenerator.next();
@@ -360,17 +371,23 @@
     }
 
     @Override
-    public void onInvokeDirect(DexMethod target, List<EV> arguments) {
-      // TODO(b/225838009): Maintain is-interface bit.
+    public void onInvokeDirect(DexMethod target, List<EV> arguments, boolean isInterface) {
       Value dest = getInvokeInstructionOutputValue(target);
       List<Value> ssaArgumentValues = getValues(arguments);
-      InvokeDirect instruction = new InvokeDirect(target, dest, ssaArgumentValues);
+      InvokeDirect instruction = new InvokeDirect(target, dest, ssaArgumentValues, isInterface);
+      addInstruction(instruction);
+    }
+
+    @Override
+    public void onInvokeSuper(DexMethod method, List<EV> arguments, boolean isInterface) {
+      Value dest = getInvokeInstructionOutputValue(method);
+      List<Value> ssaArgumentValues = getValues(arguments);
+      InvokeSuper instruction = new InvokeSuper(method, dest, ssaArgumentValues, isInterface);
       addInstruction(instruction);
     }
 
     @Override
     public void onInvokeVirtual(DexMethod target, List<EV> arguments) {
-      // TODO(b/225838009): Maintain is-interface bit.
       Value dest = getInvokeInstructionOutputValue(target);
       List<Value> ssaArgumentValues = getValues(arguments);
       InvokeVirtual instruction = new InvokeVirtual(target, dest, ssaArgumentValues);
@@ -378,11 +395,10 @@
     }
 
     @Override
-    public void onInvokeStatic(DexMethod target, List<EV> arguments) {
-      // TODO(b/225838009): Maintain is-interface bit.
+    public void onInvokeStatic(DexMethod target, List<EV> arguments, boolean isInterface) {
       Value dest = getInvokeInstructionOutputValue(target);
       List<Value> ssaArgumentValues = getValues(arguments);
-      InvokeStatic instruction = new InvokeStatic(target, dest, ssaArgumentValues);
+      InvokeStatic instruction = new InvokeStatic(target, dest, ssaArgumentValues, isInterface);
       addInstruction(instruction);
     }
 
@@ -425,6 +441,12 @@
     }
 
     @Override
+    public void onThrow(EV exception) {
+      addInstruction(new Throw(getValue(exception)));
+      closeCurrentBlock();
+    }
+
+    @Override
     public void onReturnVoid() {
       addInstruction(new Return());
       closeCurrentBlock();
diff --git a/src/main/java/com/android/tools/r8/lightir/LirBuilder.java b/src/main/java/com/android/tools/r8/lightir/LirBuilder.java
index 8209c80..37806dd 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirBuilder.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirBuilder.java
@@ -312,16 +312,26 @@
     return addInstructionTemplate(opcode, Collections.singletonList(method), arguments);
   }
 
-  public LirBuilder<V, EV> addInvokeDirect(DexMethod method, List<V> arguments) {
-    return addInvokeInstruction(LirOpcodes.INVOKEDIRECT, method, arguments);
+  public LirBuilder<V, EV> addInvokeDirect(
+      DexMethod method, List<V> arguments, boolean isInterface) {
+    int opcode = isInterface ? LirOpcodes.INVOKEDIRECT_ITF : LirOpcodes.INVOKEDIRECT;
+    return addInvokeInstruction(opcode, method, arguments);
+  }
+
+  public LirBuilder<V, EV> addInvokeSuper(
+      DexMethod method, List<V> arguments, boolean isInterface) {
+    int opcode = isInterface ? LirOpcodes.INVOKESUPER_ITF : LirOpcodes.INVOKESUPER;
+    return addInvokeInstruction(opcode, method, arguments);
   }
 
   public LirBuilder<V, EV> addInvokeVirtual(DexMethod method, List<V> arguments) {
     return addInvokeInstruction(LirOpcodes.INVOKEVIRTUAL, method, arguments);
   }
 
-  public LirBuilder<V, EV> addInvokeStatic(DexMethod method, List<V> arguments) {
-    return addInvokeInstruction(LirOpcodes.INVOKESTATIC, method, arguments);
+  public LirBuilder<V, EV> addInvokeStatic(
+      DexMethod method, List<V> arguments, boolean isInterface) {
+    int opcode = isInterface ? LirOpcodes.INVOKESTATIC_ITF : LirOpcodes.INVOKESTATIC;
+    return addInvokeInstruction(opcode, method, arguments);
   }
 
   public LirBuilder<V, EV> addInvokeInterface(DexMethod method, List<V> arguments) {
@@ -332,6 +342,10 @@
     return addOneItemInstruction(LirOpcodes.NEW, clazz);
   }
 
+  public LirBuilder<V, EV> addThrow(V exception) {
+    return addOneValueInstruction(LirOpcodes.ATHROW, exception);
+  }
+
   public LirBuilder<V, EV> addReturn(V value) {
     throw new Unimplemented();
   }
diff --git a/src/main/java/com/android/tools/r8/lightir/LirOpcodes.java b/src/main/java/com/android/tools/r8/lightir/LirOpcodes.java
index 0d30efd..a0300d2 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirOpcodes.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirOpcodes.java
@@ -181,12 +181,16 @@
   int LCONST = 201;
   int FCONST = 202;
   int DCONST = 203;
-  int INVOKEDIRECT = 204;
-  int DEBUGPOS = 205;
-  int PHI = 206;
-  int FALLTHROUGH = 207;
-  int MOVEEXCEPTION = 208;
-  int DEBUGLOCALWRITE = 209;
+  int INVOKESTATIC_ITF = 204;
+  int INVOKEDIRECT = 205;
+  int INVOKEDIRECT_ITF = 206;
+  int INVOKESUPER = 207;
+  int INVOKESUPER_ITF = 208;
+  int DEBUGPOS = 209;
+  int PHI = 210;
+  int FALLTHROUGH = 211;
+  int MOVEEXCEPTION = 212;
+  int DEBUGLOCALWRITE = 213;
 
   static String toString(int opcode) {
     switch (opcode) {
@@ -489,8 +493,16 @@
         return "FCONST";
       case DCONST:
         return "DCONST";
+      case INVOKESTATIC_ITF:
+        return "INVOKESTATIC_ITF";
       case INVOKEDIRECT:
         return "INVOKEDIRECT";
+      case INVOKEDIRECT_ITF:
+        return "INVOKEDIRECT_ITF";
+      case INVOKESUPER:
+        return "INVOKESUPER";
+      case INVOKESUPER_ITF:
+        return "INVOKESUPER_ITF";
       case DEBUGPOS:
         return "DEBUGPOS";
       case PHI:
diff --git a/src/main/java/com/android/tools/r8/lightir/LirParsedInstructionCallback.java b/src/main/java/com/android/tools/r8/lightir/LirParsedInstructionCallback.java
index a83524c..96cb7ee 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirParsedInstructionCallback.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirParsedInstructionCallback.java
@@ -98,7 +98,11 @@
     onInstruction();
   }
 
-  public void onInvokeDirect(DexMethod method, List<EV> arguments) {
+  public void onInvokeDirect(DexMethod method, List<EV> arguments, boolean isInterface) {
+    onInvokeMethodInstruction(method, arguments);
+  }
+
+  public void onInvokeSuper(DexMethod method, List<EV> arguments, boolean isInterface) {
     onInvokeMethodInstruction(method, arguments);
   }
 
@@ -106,7 +110,7 @@
     onInvokeMethodInstruction(method, arguments);
   }
 
-  public void onInvokeStatic(DexMethod method, List<EV> arguments) {
+  public void onInvokeStatic(DexMethod method, List<EV> arguments, boolean isInterface) {
     onInvokeMethodInstruction(method, arguments);
   }
 
@@ -130,6 +134,8 @@
 
   public abstract void onInstancePut(DexField field, EV object, EV value);
 
+  public abstract void onThrow(EV exception);
+
   public void onReturnVoid() {
     onInstruction();
   }
@@ -212,10 +218,19 @@
           return;
         }
       case LirOpcodes.INVOKEDIRECT:
+      case LirOpcodes.INVOKEDIRECT_ITF:
         {
           DexMethod target = getInvokeInstructionTarget(view);
           List<EV> arguments = getInvokeInstructionArguments(view);
-          onInvokeDirect(target, arguments);
+          onInvokeDirect(target, arguments, opcode == LirOpcodes.INVOKEDIRECT_ITF);
+          return;
+        }
+      case LirOpcodes.INVOKESUPER:
+      case LirOpcodes.INVOKESUPER_ITF:
+        {
+          DexMethod target = getInvokeInstructionTarget(view);
+          List<EV> arguments = getInvokeInstructionArguments(view);
+          onInvokeSuper(target, arguments, opcode == LirOpcodes.INVOKESUPER_ITF);
           return;
         }
       case LirOpcodes.INVOKEVIRTUAL:
@@ -226,10 +241,11 @@
           return;
         }
       case LirOpcodes.INVOKESTATIC:
+      case LirOpcodes.INVOKESTATIC_ITF:
         {
           DexMethod target = getInvokeInstructionTarget(view);
           List<EV> arguments = getInvokeInstructionArguments(view);
-          onInvokeStatic(target, arguments);
+          onInvokeStatic(target, arguments, opcode == LirOpcodes.INVOKESTATIC_ITF);
           return;
         }
       case LirOpcodes.INVOKEINTERFACE:
@@ -269,6 +285,12 @@
           onInstancePut(field, object, value);
           return;
         }
+      case LirOpcodes.ATHROW:
+        {
+          EV exception = getNextValueOperand(view);
+          onThrow(exception);
+          return;
+        }
       case LirOpcodes.RETURN:
         {
           onReturnVoid();
diff --git a/src/main/java/com/android/tools/r8/lightir/LirPrinter.java b/src/main/java/com/android/tools/r8/lightir/LirPrinter.java
index 33dedd6..965b6d7 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirPrinter.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirPrinter.java
@@ -202,6 +202,11 @@
   }
 
   @Override
+  public void onThrow(EV exception) {
+    appendValueArguments(exception);
+  }
+
+  @Override
   public void onReturnVoid() {
     // Nothing to append.
   }
diff --git a/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java b/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java
index fd21f2a..1975d03 100644
--- a/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java
+++ b/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java
@@ -85,6 +85,10 @@
     return this == ANDROID_PLATFORM;
   }
 
+  public AndroidApiLevel next() {
+    return getAndroidApiLevel(getLevel() + 1);
+  }
+
   public static List<AndroidApiLevel> getAndroidApiLevelsSorted() {
     return Arrays.asList(AndroidApiLevel.values());
   }
diff --git a/src/main/java/com/android/tools/r8/utils/AndroidApiLevelUtils.java b/src/main/java/com/android/tools/r8/utils/AndroidApiLevelUtils.java
index 1c323cb..1a2d82b 100644
--- a/src/main/java/com/android/tools/r8/utils/AndroidApiLevelUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/AndroidApiLevelUtils.java
@@ -258,20 +258,22 @@
     if (originalClass.isLibraryClass()) {
       return originalClass;
     }
-    WorkList<DexClass> workList = WorkList.newIdentityWorkList(originalClass);
-    while (workList.hasNext()) {
-      DexClass clazz = workList.next();
-      if (clazz.isLibraryClass()) {
-        return clazz;
-      } else if (clazz.lookupMember(reference) != null) {
-        return clazz;
-      } else if (clazz.getSuperType() != null) {
-        appInfo
-            .contextIndependentDefinitionForWithResolutionResult(clazz.getSuperType())
-            .forEachClassResolutionResult(workList::addIfNotSeen);
-      }
-    }
-    return null;
+    return WorkList.newIdentityWorkList(originalClass)
+        .run(
+            (clazz, workList) -> {
+              if (clazz.isLibraryClass()) {
+                return TraversalContinuation.doBreak(clazz);
+              } else if (clazz.lookupMember(reference) != null) {
+                return TraversalContinuation.doBreak(clazz);
+              } else if (clazz.getSuperType() != null) {
+                appInfo
+                    .contextIndependentDefinitionForWithResolutionResult(clazz.getSuperType())
+                    .forEachClassResolutionResult(workList::addIfNotSeen);
+              }
+              return TraversalContinuation.doContinue();
+            })
+        .asBreakOrDefault(null)
+        .getValue();
   }
 
   private static Set<DexClass> findAllFirstLibraryInterfacesOrProgramClassWithDefinition(
@@ -329,4 +331,9 @@
     }
     return apiLevel.asKnownApiLevel().getApiLevel().getLevel() <= apiLevelAsInt;
   }
+
+  public static boolean isApiLevelLessThanOrEqualToG(ComputedApiLevel apiLevel) {
+    return apiLevel.isKnownApiLevel()
+        && apiLevel.asKnownApiLevel().getApiLevel().isLessThanOrEqualTo(AndroidApiLevel.G);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/CompileDumpBase.java b/src/main/java/com/android/tools/r8/utils/CompileDumpBase.java
index 2a928b0..aa74f03 100644
--- a/src/main/java/com/android/tools/r8/utils/CompileDumpBase.java
+++ b/src/main/java/com/android/tools/r8/utils/CompileDumpBase.java
@@ -4,7 +4,6 @@
 
 package com.android.tools.r8.utils;
 
-import com.android.tools.r8.CompatProguardCommandBuilder;
 import java.io.IOException;
 import java.lang.reflect.Method;
 import java.nio.file.Files;
@@ -113,7 +112,7 @@
   static Consumer<Object[]> getReflectiveBuilderMethod(
       Object builder, String setter, Class<?>... parameters) {
     try {
-      Method declaredMethod = CompatProguardCommandBuilder.class.getMethod(setter, parameters);
+      Method declaredMethod = builder.getClass().getMethod(setter, parameters);
       return args -> {
         try {
           declaredMethod.invoke(builder, args);
diff --git a/src/main/java/com/android/tools/r8/utils/CompileDumpD8.java b/src/main/java/com/android/tools/r8/utils/CompileDumpD8.java
index b63f5d8..137dfe7 100644
--- a/src/main/java/com/android/tools/r8/utils/CompileDumpD8.java
+++ b/src/main/java/com/android/tools/r8/utils/CompileDumpD8.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.D8;
 import com.android.tools.r8.D8Command;
 import com.android.tools.r8.OutputMode;
+import com.android.tools.r8.StringConsumer;
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.ArrayList;
@@ -49,7 +50,9 @@
           "--main-dex-list-output",
           "--desugared-lib",
           "--threads",
-          "--startup-profile");
+          "--startup-profile",
+          "--desugared-lib",
+          "--desugared-lib-pg-conf-output");
 
   private static final List<String> VALID_OPTIONS_WITH_TWO_OPERANDS =
       Arrays.asList("--art-profile");
@@ -58,6 +61,7 @@
     OutputMode outputMode = OutputMode.DexIndexed;
     Path outputPath = null;
     Path desugaredLibJson = null;
+    Path desugaredLibConfig = null;
     CompilationMode compilationMode = CompilationMode.RELEASE;
     List<Path> program = new ArrayList<>();
     List<Path> library = new ArrayList<>();
@@ -125,6 +129,11 @@
               desugaredLibJson = Paths.get(operand);
               break;
             }
+          case "--desugared-lib-pg-conf-output":
+            {
+              desugaredLibConfig = Paths.get(operand);
+              break;
+            }
           case "--threads":
             {
               threads = Integer.parseInt(operand);
@@ -174,6 +183,10 @@
     if (desugaredLibJson != null) {
       commandBuilder.addDesugaredLibraryConfiguration(readAllBytesJava7(desugaredLibJson));
     }
+    if (desugaredLibConfig != null) {
+      StringConsumer consumer = new StringConsumer.FileConsumer(desugaredLibConfig);
+      commandBuilder.setDesugaredLibraryKeepRuleConsumer(consumer);
+    }
     commandBuilder.setMinApiLevel(minApi);
     D8Command command = commandBuilder.build();
     if (threads != -1) {
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 8275b55..f9bd041 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -2258,7 +2258,7 @@
    * Predicate to guard against the possible presence of a VM bug.
    *
    * <p>Note that if the compilation is not desugaring to a min-api or targeting DEX at a min-api,
-   * then the bug is assumed to be present as the CF output could be futher compiled to any target.
+   * then the bug is assumed to be present as the CF output could be further compiled to any target.
    */
   private boolean canHaveBugPresentUntil(AndroidApiLevel level) {
     if (desugarState.isOn() || isGeneratingDex()) {
@@ -2893,4 +2893,10 @@
   public boolean canHaveIssueWithInlinedMonitors() {
     return canHaveBugPresentUntil(AndroidApiLevel.N);
   }
+
+  // b/272725341. ART 11 and 12 re-introduced hard verification errors when unable to compute
+  // subtype relationship when no other verification issues exists in code.
+  public boolean canHaveVerifyErrorForUnknownUnusedReturnValue() {
+    return isGeneratingDex() && canHaveBugPresentUntil(AndroidApiLevel.T);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java b/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java
index c33d020..f2b96f3 100644
--- a/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java
+++ b/src/main/java/com/android/tools/r8/utils/TraversalContinuation.java
@@ -18,6 +18,11 @@
     return null;
   }
 
+  public Break<TB, TC> asBreakOrDefault(TB defaultValue) {
+    Break<TB, TC> breakValue = asBreak();
+    return breakValue == null ? doBreak(defaultValue) : breakValue;
+  }
+
   public boolean isContinue() {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/utils/WorkList.java b/src/main/java/com/android/tools/r8/utils/WorkList.java
index 79c2ed7..5aa700a 100644
--- a/src/main/java/com/android/tools/r8/utils/WorkList.java
+++ b/src/main/java/com/android/tools/r8/utils/WorkList.java
@@ -10,6 +10,10 @@
 import java.util.Deque;
 import java.util.HashSet;
 import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
+import java.util.function.Consumer;
+import java.util.function.Function;
 
 public class WorkList<T> {
 
@@ -100,6 +104,32 @@
     return false;
   }
 
+  public WorkList<T> process(Consumer<T> consumer) {
+    return process((item, ignored) -> consumer.accept(item));
+  }
+
+  public WorkList<T> process(BiConsumer<T, WorkList<T>> consumer) {
+    while (hasNext()) {
+      consumer.accept(next(), this);
+    }
+    return this;
+  }
+
+  public <TB, TC> TraversalContinuation<TB, TC> run(Function<T, TraversalContinuation<TB, TC>> fn) {
+    return run((item, ignored) -> fn.apply(item));
+  }
+
+  public <TB, TC> TraversalContinuation<TB, TC> run(
+      BiFunction<T, WorkList<T>, TraversalContinuation<TB, TC>> fn) {
+    while (hasNext()) {
+      TraversalContinuation<TB, TC> result = fn.apply(next(), this);
+      if (result.shouldBreak()) {
+        return result;
+      }
+    }
+    return TraversalContinuation.doContinue();
+  }
+
   public void addFirstIgnoringSeenSet(T item) {
     workingList.addFirst(item);
   }
diff --git a/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGenerator.java b/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGenerator.java
index b8d3f1f..4bdba09 100644
--- a/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGenerator.java
+++ b/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGenerator.java
@@ -87,10 +87,9 @@
     for (ParsedApiClass apiClass : apiClasses) {
       Map<DexMethod, AndroidApiLevel> methodsForApiClass = new HashMap<>();
       apiClass.visitMethodReferences(
-          (apiLevel, methods) -> {
-            methods.forEach(
-                method -> methodsForApiClass.put(factory.createMethod(method), apiLevel));
-          });
+          (apiLevel, methods) ->
+              methods.forEach(
+                  method -> methodsForApiClass.put(factory.createMethod(method), apiLevel)));
       covariantMethodsInJar.visitCovariantMethodsForHolder(
           apiClass.getClassReference(),
           methodReferenceWithApiLevel -> {
@@ -105,9 +104,8 @@
           });
       Map<DexField, AndroidApiLevel> fieldsForApiClass = new HashMap<>();
       apiClass.visitFieldReferences(
-          (apiLevel, fields) -> {
-            fields.forEach(field -> fieldsForApiClass.put(factory.createField(field), apiLevel));
-          });
+          (apiLevel, fields) ->
+              fields.forEach(field -> fieldsForApiClass.put(factory.createField(field), apiLevel)));
       methodMap.put(apiClass.getClassReference(), methodsForApiClass);
       fieldMap.put(apiClass.getClassReference(), fieldsForApiClass);
       lookupMap.put(apiClass.getClassReference(), apiClass);
diff --git a/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGeneratorTest.java b/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGeneratorTest.java
index 285d96a..9ce5fd6 100644
--- a/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGeneratorTest.java
+++ b/src/test/java/com/android/tools/r8/apimodel/AndroidApiHashingDatabaseBuilderGeneratorTest.java
@@ -13,21 +13,29 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.androidapi.AndroidApiLevelCompute;
+import com.android.tools.r8.androidapi.AndroidApiLevelCompute.DefaultAndroidApiLevelCompute;
 import com.android.tools.r8.androidapi.AndroidApiLevelHashingDatabaseImpl;
 import com.android.tools.r8.apimodel.AndroidApiVersionsXmlParser.ParsedApiClass;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexLibraryClass;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.references.MethodReference;
 import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.IntBox;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableList;
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.Paths;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 import org.junit.Test;
 import org.junit.rules.TemporaryFolder;
 import org.junit.runner.RunWith;
@@ -114,6 +122,53 @@
   }
 
   @Test
+  public void testAmendedClassesToApiDatabase() throws Exception {
+    Path androidJar = ToolHelper.getAndroidJar(API_LEVEL);
+    AppView<AppInfoWithClassHierarchy> appView =
+        computeAppViewWithClassHierarchy(AndroidApp.builder().addLibraryFile(androidJar).build());
+    AndroidApiLevelCompute androidApiLevelCompute = DefaultAndroidApiLevelCompute.create(appView);
+    assertTrue(androidApiLevelCompute.isEnabled());
+    ensureAllPublicMethodsAreMapped(appView, androidApiLevelCompute);
+  }
+
+  private static void ensureAllPublicMethodsAreMapped(
+      AppView<AppInfoWithClassHierarchy> appView, AndroidApiLevelCompute apiLevelCompute) {
+    Set<String> notModeledTypes = new HashSet<>();
+    notModeledTypes.add("androidx.annotation.RecentlyNullable");
+    notModeledTypes.add("androidx.annotation.RecentlyNonNull");
+    notModeledTypes.add("android.annotation.Nullable");
+    notModeledTypes.add("android.annotation.NonNull");
+    DexItemFactory factory = appView.dexItemFactory();
+    for (DexLibraryClass clazz : appView.app().asDirect().libraryClasses()) {
+      if (notModeledTypes.contains(clazz.getClassReference().getTypeName())) {
+        continue;
+      }
+      assertTrue(
+          apiLevelCompute
+              .computeApiLevelForLibraryReference(clazz.getReference())
+              .isKnownApiLevel());
+      clazz.forEachClassField(
+          field -> {
+            if (field.getAccessFlags().isPublic() && !field.toSourceString().contains("this$0")) {
+              assertTrue(
+                  apiLevelCompute
+                      .computeApiLevelForLibraryReference(field.getReference())
+                      .isKnownApiLevel());
+            }
+          });
+      clazz.forEachClassMethod(
+          method -> {
+            if (method.getAccessFlags().isPublic()) {
+              assertTrue(
+                  apiLevelCompute
+                      .computeApiLevelForLibraryReference(method.getReference())
+                      .isKnownApiLevel());
+            }
+          });
+    }
+  }
+
+  @Test
   public void testCanLookUpAllParsedApiClassesAndMembers() throws Exception {
     List<ParsedApiClass> parsedApiClasses =
         AndroidApiVersionsXmlParser.getParsedApiClasses(
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelManualOutlineWithUnknownReturnTypeTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelManualOutlineWithUnknownReturnTypeTest.java
new file mode 100644
index 0000000..6df9998
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelManualOutlineWithUnknownReturnTypeTest.java
@@ -0,0 +1,162 @@
+// Copyright (c) 2023, 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 org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestCompileResult;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.BooleanUtils;
+import java.util.List;
+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;
+
+/***
+ * This is a regression test for b/272725341 where we manually outline to show runtime behavior.
+ */
+@RunWith(Parameterized.class)
+public class ApiModelManualOutlineWithUnknownReturnTypeTest extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameter(1)
+  public boolean addedToLibraryHere;
+
+  @Parameters(name = "{0}, addedToLibraryHere: {1}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withAllRuntimesAndApiLevels().build(), BooleanUtils.values());
+  }
+
+  private AndroidApiLevel runApiLevel() {
+    return parameters.getRuntime().maxSupportedApiLevel();
+  }
+
+  private AndroidApiLevel getMockApiLevel() {
+    return addedToLibraryHere ? runApiLevel() : runApiLevel().next();
+  }
+
+  @Test
+  public void testJvm() throws Exception {
+    assumeTrue(parameters.isCfRuntime());
+    testForJvm(parameters)
+        .addProgramClasses(Main.class, ProgramClass.class, ManualOutline.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .addLibraryClasses(LibraryClass.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertFailureWithErrorThatThrows(NoClassDefFoundError.class)
+        .assertFailureWithErrorThatMatches(containsString(typeName(LibrarySub.class)));
+  }
+
+  private void setupRuntime(TestCompileResult<?, ?> compileResult) throws Exception {
+    if (runApiLevel().isGreaterThanOrEqualTo(getMockApiLevel())) {
+      compileResult.addBootClasspathFiles(
+          buildOnDexRuntime(parameters, LibraryClass.class, LibrarySub.class));
+    } else {
+      compileResult.addBootClasspathFiles(buildOnDexRuntime(parameters, LibraryClass.class));
+    }
+  }
+
+  @Test
+  public void testD8WithModeling() throws Exception {
+    assumeTrue(parameters.isDexRuntime());
+    testForD8(parameters.getBackend())
+        .addProgramClasses(Main.class, ProgramClass.class, ManualOutline.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .addLibraryClasses(LibraryClass.class, LibrarySub.class)
+        .setMinApi(parameters)
+        .addOptionsModification(
+            options -> options.apiModelingOptions().disableOutliningAndStubbing())
+        .apply(setMockApiLevelForClass(LibraryClass.class, AndroidApiLevel.B))
+        .apply(setMockApiLevelForClass(LibrarySub.class, getMockApiLevel()))
+        .compile()
+        .apply(this::setupRuntime)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("ProgramClass::print");
+  }
+
+  @Test
+  public void testD8NoModeling() throws Exception {
+    assumeTrue(parameters.isDexRuntime());
+    boolean willHaveVerifyError =
+        (parameters.getDexRuntimeVersion().isDalvik()
+                || parameters.isDexRuntimeVersion(Version.V12_0_0))
+            && !addedToLibraryHere;
+    testForD8(parameters.getBackend())
+        .addProgramClasses(Main.class, ProgramClass.class, ManualOutline.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .addLibraryClasses(LibraryClass.class, LibrarySub.class)
+        .setMinApi(parameters)
+        .addOptionsModification(options -> options.apiModelingOptions().disableApiModeling())
+        .compile()
+        .apply(this::setupRuntime)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLinesIf(!willHaveVerifyError, "ProgramClass::print")
+        .assertFailureWithErrorThatThrowsIf(willHaveVerifyError, VerifyError.class);
+  }
+
+  public static class LibraryClass {
+
+    public void foo() {
+      System.out.println("LibraryClass::foo");
+    }
+  }
+
+  public static class LibrarySub extends LibraryClass {
+
+    public static LibrarySub create() {
+      return new LibrarySub();
+    }
+  }
+
+  public static class ManualOutline {
+
+    public static LibrarySub create() {
+      return LibrarySub.create();
+    }
+  }
+
+  public static class ProgramClass {
+
+    public LibraryClass callLibraryWithDirectReturn() {
+      LibrarySub libraryClass = ManualOutline.create();
+      if (System.currentTimeMillis() > 0) {
+        return null;
+      } else {
+        return libraryClass;
+      }
+    }
+
+    public LibraryClass callLibraryWithIndirectReturn() {
+      LibrarySub libraryClass = ManualOutline.create();
+      LibraryClass libClass;
+      if (System.currentTimeMillis() > 0) {
+        libClass = null;
+      } else {
+        libClass = libraryClass;
+      }
+      return libClass;
+    }
+
+    public void print() {
+      System.out.println("ProgramClass::print");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      new ProgramClass().print();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineWithUnknownReturnTypeTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineWithUnknownReturnTypeTest.java
new file mode 100644
index 0000000..643fc38
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineWithUnknownReturnTypeTest.java
@@ -0,0 +1,165 @@
+// Copyright (c) 2023, 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.setMockApiLevelForMethod;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.verifyThat;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.SingleTestRunResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestCompileResult;
+import com.android.tools.r8.TestCompilerBuilder;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.util.List;
+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;
+
+/***
+ * This is a regression test for b/272725341.
+ */
+@RunWith(Parameterized.class)
+public class ApiModelOutlineWithUnknownReturnTypeTest extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameter(1)
+  public boolean addedToLibraryHere;
+
+  @Parameters(name = "{0}, addedToLibraryHere: {1}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withDexRuntimes().withAllApiLevels().build(), BooleanUtils.values());
+  }
+
+  private AndroidApiLevel runApiLevel() {
+    return parameters.getRuntime().maxSupportedApiLevel();
+  }
+
+  private AndroidApiLevel getMockApiLevel() {
+    return addedToLibraryHere ? runApiLevel() : runApiLevel().next();
+  }
+
+  private void setupTestBuilder(TestCompilerBuilder<?, ?, ?, ?, ?> testBuilder) throws Exception {
+    testBuilder
+        .addProgramClasses(Main.class, ProgramClass.class)
+        .addLibraryClasses(LibraryClass.class, LibrarySub.class)
+        .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.LATEST))
+        .setMinApi(parameters)
+        .apply(ApiModelingTestHelper::enableApiCallerIdentification)
+        .apply(ApiModelingTestHelper::enableOutliningOfMethods)
+        .apply(setMockApiLevelForClass(LibraryClass.class, AndroidApiLevel.B))
+        .apply(setMockApiLevelForClass(LibrarySub.class, getMockApiLevel()))
+        .apply(
+            setMockApiLevelForMethod(
+                LibrarySub.class.getDeclaredMethod("create"), getMockApiLevel()));
+  }
+
+  private void setupRuntime(TestCompileResult<?, ?> compileResult) throws Exception {
+    if (runApiLevel().isGreaterThanOrEqualTo(getMockApiLevel())) {
+      compileResult.addBootClasspathFiles(
+          buildOnDexRuntime(parameters, LibraryClass.class, LibrarySub.class));
+    } else {
+      compileResult.addBootClasspathFiles(buildOnDexRuntime(parameters, LibraryClass.class));
+    }
+  }
+
+  @Test
+  public void testD8Debug() throws Exception {
+    testForD8()
+        .setMode(CompilationMode.DEBUG)
+        .apply(this::setupTestBuilder)
+        .compile()
+        .inspect(this::inspect)
+        .apply(this::setupRuntime)
+        .run(parameters.getRuntime(), Main.class)
+        .apply(this::checkOutput);
+  }
+
+  @Test
+  public void testD8Release() throws Exception {
+    testForD8()
+        .setMode(CompilationMode.RELEASE)
+        .apply(this::setupTestBuilder)
+        .compile()
+        .inspect(this::inspect)
+        .apply(this::setupRuntime)
+        .run(parameters.getRuntime(), Main.class)
+        .apply(this::checkOutput);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .apply(this::setupTestBuilder)
+        .addKeepMainRule(Main.class)
+        .addKeepClassAndMembersRules(ProgramClass.class)
+        .compile()
+        .inspect(this::inspect)
+        .apply(this::setupRuntime)
+        .run(parameters.getRuntime(), Main.class)
+        .apply(this::checkOutput);
+  }
+
+  private void inspect(CodeInspector inspector) throws Exception {
+    assertThat(inspector.clazz(ProgramClass.class), isPresent());
+    verifyThat(inspector, parameters, LibrarySub.class.getDeclaredMethod("create"))
+        .isOutlinedFromBetween(
+            ProgramClass.class.getDeclaredMethod("callLibrary"),
+            AndroidApiLevel.B,
+            getMockApiLevel());
+  }
+
+  private void checkOutput(SingleTestRunResult<?> runResult) {
+    runResult.assertSuccessWithOutputLines("ProgramClass::print");
+  }
+
+  public static class LibraryClass {
+
+    public void foo() {
+      System.out.println("LibraryClass::foo");
+    }
+  }
+
+  public static class LibrarySub extends LibraryClass {
+
+    public static LibrarySub create() {
+      return new LibrarySub();
+    }
+  }
+
+  public static class ProgramClass {
+
+    public LibraryClass callLibrary() {
+      LibrarySub libraryClass = LibrarySub.create();
+      if (System.currentTimeMillis() > 0) {
+        return null;
+      } else {
+        return libraryClass;
+      }
+    }
+
+    public void print() {
+      System.out.println("ProgramClass::print");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      new ProgramClass().print();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/cf/frames/InitBeforeNewInInstructionStreamTest.java b/src/test/java/com/android/tools/r8/cf/frames/InitBeforeNewInInstructionStreamTest.java
new file mode 100644
index 0000000..1d93a7a
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/cf/frames/InitBeforeNewInInstructionStreamTest.java
@@ -0,0 +1,187 @@
+// Copyright (c) 2023, 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.cf.frames;
+
+import static org.junit.Assert.fail;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.StringUtils;
+import javassist.ByteArrayClassPath;
+import javassist.ClassPool;
+import javassist.CtClass;
+import javassist.bytecode.CodeAttribute;
+import javassist.bytecode.StackMapTable;
+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;
+import org.objectweb.asm.ClassWriter;
+import org.objectweb.asm.Label;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+@RunWith(Parameterized.class)
+public class InitBeforeNewInInstructionStreamTest extends TestBase implements Opcodes {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().withAllApiLevelsAlsoForCf().build();
+  }
+
+  public static final String MAIN_CLASS = "Test";
+  private static final String EXPECTED_OUTPUT = StringUtils.lines("Hello, world!");
+
+  @Test
+  public void testJvm() throws Exception {
+    parameters.assumeJvmTestParameters();
+    testForJvm(parameters)
+        .addProgramClassFileData(patchedDump())
+        .run(parameters.getRuntime(), MAIN_CLASS)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  @Test
+  public void testD8() throws Exception {
+    parameters.assumeDexRuntime();
+    testForD8(parameters.getBackend())
+        .addProgramClassFileData(patchedDump())
+        .setMinApi(parameters)
+        .run(parameters.getRuntime(), MAIN_CLASS)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    parameters.assumeR8TestParameters();
+    testForR8(parameters.getBackend())
+        .addProgramClassFileData(patchedDump())
+        .addKeepMainRule(MAIN_CLASS)
+        .setMinApi(parameters)
+        .run(parameters.getRuntime(), MAIN_CLASS)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  // This is reproducing b/b274337639, where a new instruction is before the corresponding
+  // invokespecial of <init> in the instruction stream. The code is correct as control flow ensures
+  // new is called before init, and the stack map encodes this.
+  //
+  // Writing this code with ASM did not generate the correct stack map, so using javassist to patch
+  // it up.
+
+  public static byte[] patchedDump() throws Exception {
+    ClassPool classPool = new ClassPool();
+    classPool.insertClassPath(new ByteArrayClassPath(MAIN_CLASS, dump()));
+    CtClass clazz = classPool.get(MAIN_CLASS);
+    clazz.defrost();
+    CodeAttribute code =
+        (CodeAttribute) clazz.getClassFile().getMethod("main").getAttribute("Code");
+    StackMapTable stackMapTableAttribute = (StackMapTable) code.getAttribute("StackMapTable");
+    byte[] stackMapTable = stackMapTableAttribute.get();
+    // Uninitialized has type 8 in the stack map. See
+    // https://docs.oracle.com/javase/specs/jvms/se17/html/jvms-4.html#jvms-4.7.4.
+    // The instruction index 0 generated by ASM is not correct, patch to index 12.
+    if (stackMapTable[15] == 8
+        && stackMapTable[16] == 0
+        && stackMapTable[17] == 0
+        && stackMapTable[18] == 8
+        && stackMapTable[19] == 0
+        && stackMapTable[20] == 0) {
+      stackMapTable[17] = 12;
+      stackMapTable[20] = 12;
+    } else {
+      // If an ASM update fails here maybe the stack map is generated correctly and the javassist
+      // patching can be removed.
+      fail("Unexpected class file*");
+    }
+    stackMapTableAttribute.set(stackMapTable);
+    return clazz.toBytecode();
+  }
+
+  public static byte[] dump() throws Exception {
+
+    ClassWriter classWriter = new ClassWriter(0);
+    MethodVisitor methodVisitor;
+
+    classWriter.visit(V1_8, ACC_FINAL | ACC_SUPER, MAIN_CLASS, null, "java/lang/Object", null);
+
+    {
+      methodVisitor = classWriter.visitMethod(0, "<init>", "()V", null, null);
+      methodVisitor.visitCode();
+      methodVisitor.visitVarInsn(ALOAD, 0);
+      methodVisitor.visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V", false);
+      methodVisitor.visitInsn(RETURN);
+      methodVisitor.visitMaxs(1, 1);
+      methodVisitor.visitEnd();
+    }
+    {
+      Label labelNew = new Label();
+      Label labelInit = new Label();
+      Label labelAfterInit = new Label();
+
+      methodVisitor =
+          classWriter.visitMethod(
+              ACC_PUBLIC | ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null);
+      methodVisitor.visitCode();
+      methodVisitor.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
+      methodVisitor.visitJumpInsn(GOTO, labelNew);
+
+      methodVisitor.visitLabel(labelInit);
+      methodVisitor.visitFrame(
+          Opcodes.F_FULL,
+          1,
+          new Object[] {"[Ljava/lang/String;"},
+          3,
+          new Object[] {"java/io/PrintStream", labelNew, labelNew});
+      methodVisitor.visitMethodInsn(INVOKESPECIAL, MAIN_CLASS, "<init>", "()V", false);
+      methodVisitor.visitFrame(
+          Opcodes.F_FULL,
+          1,
+          new Object[] {"[Ljava/lang/String;"},
+          2,
+          new Object[] {"java/io/PrintStream", MAIN_CLASS});
+      methodVisitor.visitJumpInsn(GOTO, labelAfterInit);
+
+      methodVisitor.visitLabel(labelNew);
+      methodVisitor.visitFrame(
+          Opcodes.F_FULL,
+          1,
+          new Object[] {"[Ljava/lang/String;"},
+          1,
+          new Object[] {"java/io/PrintStream"});
+      methodVisitor.visitTypeInsn(NEW, MAIN_CLASS);
+      methodVisitor.visitInsn(DUP);
+      methodVisitor.visitJumpInsn(GOTO, labelInit);
+
+      methodVisitor.visitLabel(labelAfterInit);
+      methodVisitor.visitFrame(
+          Opcodes.F_FULL,
+          1,
+          new Object[] {"[Ljava/lang/String;"},
+          2,
+          new Object[] {"java/io/PrintStream", MAIN_CLASS});
+      methodVisitor.visitMethodInsn(
+          INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/Object;)V", false);
+      methodVisitor.visitInsn(RETURN);
+      methodVisitor.visitMaxs(3, 1);
+      methodVisitor.visitEnd();
+    }
+    {
+      methodVisitor =
+          classWriter.visitMethod(ACC_PUBLIC, "toString", "()Ljava/lang/String;", null, null);
+      methodVisitor.visitCode();
+      methodVisitor.visitLdcInsn("Hello, world!");
+      methodVisitor.visitInsn(ARETURN);
+      methodVisitor.visitMaxs(1, 1);
+      methodVisitor.visitEnd();
+    }
+    classWriter.visitEnd();
+
+    return classWriter.toByteArray();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/startup/MinimalStartupDexFromStartupMethodRuleTest.java b/src/test/java/com/android/tools/r8/startup/MinimalStartupDexFromStartupMethodRuleTest.java
new file mode 100644
index 0000000..6034910
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/startup/MinimalStartupDexFromStartupMethodRuleTest.java
@@ -0,0 +1,87 @@
+// Copyright (c) 2023, 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.startup;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestCompilerBuilder;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.startup.profile.ExternalStartupMethod;
+import com.android.tools.r8.startup.utils.StartupTestingUtils;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.MethodReferenceUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.google.common.collect.ImmutableList;
+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 MinimalStartupDexFromStartupMethodRuleTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters()
+        .withDexRuntimes()
+        .withApiLevelsStartingAtIncluding(AndroidApiLevel.L)
+        .build();
+  }
+
+  @Test
+  public void testD8() throws Exception {
+    runTest(testForD8(parameters.getBackend()));
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    runTest(testForR8(parameters.getBackend()).addKeepAllClassesRule());
+  }
+
+  private void runTest(TestCompilerBuilder<?, ?, ?, ?, ?> testCompilerBuilder) throws Exception {
+    testCompilerBuilder
+        .addInnerClasses(getClass())
+        .apply(this::configureStartupConfiguration)
+        .setMinApi(parameters)
+        .compile()
+        .inspectMultiDex(
+            primaryDexInspector -> {
+              ClassSubject mainClassSubject = primaryDexInspector.clazz(Main.class);
+              assertThat(mainClassSubject, isPresent());
+            },
+            secondaryDexInspector -> {
+              ClassSubject postStartupClassSubject =
+                  secondaryDexInspector.clazz(PostStartupClass.class);
+              assertThat(postStartupClassSubject, isPresent());
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello, world!");
+  }
+
+  private void configureStartupConfiguration(TestCompilerBuilder<?, ?, ?, ?, ?> testBuilder) {
+    StartupTestingUtils.setStartupConfiguration(
+        testBuilder,
+        ImmutableList.of(
+            ExternalStartupMethod.builder()
+                .setMethodReference(MethodReferenceUtils.mainMethod(Main.class))
+                .build()));
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      System.out.println("Hello, world!");
+    }
+  }
+
+  static class PostStartupClass {}
+}