Merge commit '9881674a871f9b2b9650c1af6119386d72b9a5c0' into dev-release Change-Id: I2443c14cb168e2979ca36e696ce7463171be2643

diff --git a/d8_r8/commonBuildSrc/src/main/kotlin/DependenciesPlugin.kt b/d8_r8/commonBuildSrc/src/main/kotlin/DependenciesPlugin.kt
index 1f748ae..b54edc3 100644
--- a/d8_r8/commonBuildSrc/src/main/kotlin/DependenciesPlugin.kt
+++ b/d8_r8/commonBuildSrc/src/main/kotlin/DependenciesPlugin.kt

@@ -403,6 +403,7 @@
   const val kotlinMetadataVersion = "2.0.0"
   const val mockito = "2.10.0"
   const val smaliVersion = "3.0.3"
+  const val protobufVersion = "3.19.3"
 }
 
 object Deps {
@@ -422,6 +423,7 @@
   val mockito by lazy { "org.mockito:mockito-core:${Versions.mockito}" }
   val smali by lazy { "com.android.tools.smali:smali:${Versions.smaliVersion}" }
   val smaliUtil by lazy { "com.android.tools.smali:smali-util:${Versions.smaliVersion}" }
+  val protobuf by lazy { "com.google.protobuf:protobuf-java:${Versions.protobufVersion}" }
 }
 
 object ThirdPartyDeps {

diff --git a/d8_r8/keepanno/build.gradle.kts b/d8_r8/keepanno/build.gradle.kts
index a747444..f7c128b 100644
--- a/d8_r8/keepanno/build.gradle.kts
+++ b/d8_r8/keepanno/build.gradle.kts

@@ -51,7 +51,7 @@
 dependencies {
   compileOnly(Deps.asm)
   compileOnly(Deps.guava)
-  implementation("com.google.protobuf:protobuf-java:3.19.3")
+  compileOnly(Deps.protobuf)
 }
 
 tasks {

diff --git a/d8_r8/main/build.gradle.kts b/d8_r8/main/build.gradle.kts
index fd3282d..c6e6cd7 100644
--- a/d8_r8/main/build.gradle.kts
+++ b/d8_r8/main/build.gradle.kts

@@ -47,6 +47,7 @@
   compileOnly(Deps.gson)
   compileOnly(Deps.guava)
   compileOnly(Deps.kotlinMetadata)
+  compileOnly(Deps.protobuf)
   errorprone(Deps.errorprone)
 }
 
@@ -223,7 +224,7 @@
     }
     exclude("META-INF/*.kotlin_module")
     exclude("**/*.kotlin_metadata")
-    exclude("keepanno.proto")
+    exclude("keepspec.proto")
     destinationDirectory.set(getRoot().resolveAll("build", "libs"))
     archiveFileName.set("r8-full-exclude-deps.jar")
   }
@@ -268,6 +269,7 @@
     exclude("README.md")
     exclude("javax/annotation/**")
     exclude("wireless/**")
+    exclude("google/protobuf/**")
     duplicatesStrategy = DuplicatesStrategy.EXCLUDE
     archiveFileName.set("deps.jar")
   }

diff --git a/d8_r8/resourceshrinker/build.gradle.kts b/d8_r8/resourceshrinker/build.gradle.kts
index db14c2f..3016524 100644
--- a/d8_r8/resourceshrinker/build.gradle.kts
+++ b/d8_r8/resourceshrinker/build.gradle.kts

@@ -36,9 +36,9 @@
 dependencies {
   compileOnly(Deps.asm)
   compileOnly(Deps.guava)
+  compileOnly(Deps.protobuf)
   compileOnly(files(resolve(ThirdPartyDeps.r8, "r8lib_8.2.20-dev.jar")))
   implementation("com.android.tools.build:aapt2-proto:8.2.0-alpha10-10154469")
-  implementation("com.google.protobuf:protobuf-java:3.19.3")
   implementation("com.android.tools.layoutlib:layoutlib-api:31.5.0-alpha04")
   implementation("com.android.tools:common:31.5.0-alpha04")
   implementation("com.android.tools:sdk-common:31.5.0-alpha04")

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepArrayTypePattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepArrayTypePattern.java
index 5981336..0c86c6c 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepArrayTypePattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepArrayTypePattern.java

@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.TypePatternArray;
 import com.google.common.base.Strings;
 import java.util.Objects;
 
@@ -78,4 +79,19 @@
   public String toString() {
     return baseType + Strings.repeat("[]", dimensions);
   }
+
+  public static KeepArrayTypePattern fromProto(TypePatternArray array) {
+    KeepTypePattern baseType =
+        array.hasBaseType()
+            ? KeepTypePattern.fromProto(array.getBaseType())
+            : KeepTypePattern.any();
+    int dimensions = Math.max(1, array.getDimensions());
+    return new KeepArrayTypePattern(baseType, dimensions);
+  }
+
+  public TypePatternArray.Builder buildProto() {
+    return TypePatternArray.newBuilder()
+        .setDimensions(dimensions)
+        .setBaseType(baseType.buildProto());
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindingReference.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindingReference.java
index 481a6f2..a8df7aa 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindingReference.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindingReference.java

@@ -5,6 +5,7 @@
 package com.android.tools.r8.keepanno.ast;
 
 import com.android.tools.r8.keepanno.ast.KeepBindings.KeepBindingSymbol;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.BindingReference;
 import java.util.Objects;
 import java.util.function.Consumer;
 import java.util.function.Function;
@@ -85,4 +86,8 @@
   public final int hashCode() {
     return Objects.hash(isClassType(), name);
   }
+
+  public BindingReference.Builder buildProto() {
+    return BindingReference.newBuilder().setName(name.toString());
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java
index 4df258d..28ff0b1 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java

@@ -3,9 +3,12 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.Bindings;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.IdentityHashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.function.BiConsumer;
 import java.util.stream.Collectors;
@@ -85,6 +88,17 @@
             .collect(Collectors.joining(", "));
   }
 
+  public KeepSpecProtos.Bindings.Builder buildProto() {
+    KeepSpecProtos.Bindings.Builder builder = KeepSpecProtos.Bindings.newBuilder();
+    bindings.forEach(
+        ((symbol, binding) ->
+            builder.addBindings(
+                KeepSpecProtos.Binding.newBuilder()
+                    .setName(symbol.toString())
+                    .setItem(binding.getItem().buildItemProto()))));
+    return builder;
+  }
+
   /**
    * A unique binding.
    *
@@ -190,11 +204,53 @@
     private final Map<String, KeepBindingSymbol> reserved = new HashMap<>();
     private final Map<KeepBindingSymbol, KeepItemPattern> bindings = new IdentityHashMap<>();
 
+    public Builder applyProto(Bindings proto) {
+      List<KeepSpecProtos.Binding> protoList = proto.getBindingsList();
+      // The structure of keep edges and checks requires at least one consequent/check item.
+      // Thus, we should never be building empty binding lists, but the code is not incorrect.
+      assert !protoList.isEmpty();
+
+      // Two pass build.
+      // First pass validates and allocates symbols for each binding.
+      for (KeepSpecProtos.Binding binding : protoList) {
+        String protoName = binding.getName();
+        if (protoName.isEmpty()) {
+          throw new KeepEdgeException("Invalid binding to empty name");
+        }
+        create(protoName);
+      }
+      // Second pass constructs the items which may themselves have references to symbols.
+      for (KeepSpecProtos.Binding binding : protoList) {
+        KeepBindingSymbol symbol = reserved.get(binding.getName());
+        // We can only create a binding for an item that is present.
+        if (binding.hasItem()) {
+          KeepItemPattern itemPattern =
+              KeepItemPattern.fromItemProto(binding.getItem(), null, reserved::get);
+          // It also must be a class/member kind.
+          if (itemPattern != null) {
+            addBinding(symbol, itemPattern);
+          }
+        }
+      }
+      // We expect the bindings to have been read (a format change could invalidate this).
+      assert bindings.size() == protoList.size();
+      return this;
+    }
+
     public KeepBindingSymbol generateFreshSymbol(String hint) {
       // Allocate a fresh non-forgeable symbol. The actual name is chosen at build time.
       return new KeepBindingSymbol(hint);
     }
 
+    public KeepBindingReference getBindingReferenceForUserBinding(String name) {
+      KeepBindingSymbol symbol = reserved.get(name);
+      if (symbol == null) {
+        throw new KeepEdgeException("Undefined binding for name '" + name + "'");
+      }
+      KeepItemPattern item = getItemForBinding(symbol);
+      return KeepBindingReference.forItem(symbol, item);
+    }
+
     public KeepBindingSymbol create(String name) {
       KeepBindingSymbol symbol = new KeepBindingSymbol(name);
       KeepBindingSymbol old = reserved.put(name, symbol);

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCheck.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCheck.java
index d29459f..c59fe13 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCheck.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCheck.java

@@ -3,6 +3,10 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.Check;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.CheckKind;
+
 public class KeepCheck extends KeepDeclaration {
 
   public enum KeepCheckKind {
@@ -17,6 +21,37 @@
     private KeepBindings bindings = KeepBindings.none();
     private KeepBindingReference itemReference;
 
+    public Builder applyProto(KeepSpecProtos.Check proto, KeepSpecVersion version) {
+      // MetaInfo is optional, but that is handled in its applyProto.
+      setMetaInfo(KeepEdgeMetaInfo.fromProto(proto.getMetaInfo(), version));
+
+      switch (proto.getKindValue()) {
+        case CheckKind.CHECK_OPTIMIZED_OUT_VALUE:
+          setKind(KeepCheckKind.OPTIMIZED_OUT);
+          break;
+        case CheckKind.CHECK_REMOVED_VALUE:
+        default:
+          // The kind is not optional, but in the even of a format change we assume removed.
+          assert proto.getKind() == CheckKind.CHECK_REMOVED;
+          setKind(KeepCheckKind.REMOVED);
+      }
+
+      // Bindings are not optional.
+      if (!proto.hasBindings()) {
+        throw new KeepEdgeException("Invalid Check, must have valid bindings.");
+      }
+      KeepBindings.Builder bindingsBuilder = KeepBindings.builder().applyProto(proto.getBindings());
+      setBindings(bindingsBuilder.build());
+
+      // The check item reference is not optional.
+      if (!proto.hasItem() || proto.getItem().getName().isEmpty()) {
+        throw new KeepEdgeException("Invalid check, must have a valid item reference.");
+      }
+      setItemReference(
+          bindingsBuilder.getBindingReferenceForUserBinding(proto.getItem().getName()));
+      return this;
+    }
+
     public Builder setMetaInfo(KeepEdgeMetaInfo metaInfo) {
       this.metaInfo = metaInfo;
       return this;
@@ -98,4 +133,19 @@
   public String toString() {
     return "KeepCheck{kind=" + kind + ", item=" + itemReference + "}";
   }
+
+  public static KeepCheck fromCheckProto(Check proto, KeepSpecVersion version) {
+    return builder().applyProto(proto, version).build();
+  }
+
+  public Check.Builder buildCheckProto() {
+    return Check.newBuilder()
+        .setMetaInfo(getMetaInfo().buildProto())
+        .setBindings(getBindings().buildProto())
+        .setItem(itemReference.buildProto())
+        .setKind(
+            kind == KeepCheckKind.REMOVED
+                ? KeepSpecProtos.CheckKind.CHECK_REMOVED
+                : KeepSpecProtos.CheckKind.CHECK_OPTIMIZED_OUT);
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java
index a051b62..8d27307 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassItemPattern.java

@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.ClassItemPattern;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Objects;
@@ -18,6 +19,16 @@
     return new Builder();
   }
 
+  public static KeepClassItemPattern fromClassProto(ClassItemPattern proto) {
+    return builder().applyProto(proto).build();
+  }
+
+  public ClassItemPattern.Builder buildClassProto() {
+    // TODO(b/343389186): Add instance-of.
+    // TODO(b/343389186): Add annotated-by.
+    return ClassItemPattern.newBuilder().setClassName(classNamePattern.buildProto());
+  }
+
   public static class Builder {
 
     private KeepQualifiedClassNamePattern classNamePattern = KeepQualifiedClassNamePattern.any();
@@ -27,6 +38,17 @@
 
     private Builder() {}
 
+    public Builder applyProto(ClassItemPattern protoItem) {
+      assert classNamePattern.isAny();
+      if (protoItem.hasClassName()) {
+        setClassNamePattern(KeepQualifiedClassNamePattern.fromProto(protoItem.getClassName()));
+      }
+
+      // TODO(b/343389186): Add instance-of.
+      // TODO(b/343389186): Add annotated-by.
+      return this;
+    }
+
     public Builder copyFrom(KeepClassItemPattern pattern) {
       return setClassNamePattern(pattern.getClassNamePattern())
           .setInstanceOfPattern(pattern.getInstanceOfPattern())

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepDeclaration.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepDeclaration.java
index e80bfbd..12d1d31 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepDeclaration.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepDeclaration.java

@@ -3,10 +3,12 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.Declaration;
 import java.util.function.Consumer;
 import java.util.function.Function;
 
-/** Base class for the declarations represented in the keep annoations library. */
+/** Base class for the declarations represented in the keep annotations library. */
 public abstract class KeepDeclaration {
 
   public abstract KeepEdgeMetaInfo getMetaInfo();
@@ -47,4 +49,22 @@
   public final int hashCode() {
     throw new RuntimeException();
   }
+
+  public final Declaration.Builder buildDeclarationProto() {
+    Declaration.Builder builder = Declaration.newBuilder();
+    return apply(
+        edge -> builder.setEdge(edge.buildEdgeProto()),
+        check -> builder.setCheck(check.buildCheckProto()));
+  }
+
+  public static KeepDeclaration fromProto(
+      KeepSpecProtos.Declaration declaration, KeepSpecVersion version) {
+    if (declaration.hasEdge()) {
+      return KeepEdge.builder().applyProto(declaration.getEdge(), version).build();
+    }
+    if (declaration.hasCheck()) {
+      return KeepCheck.builder().applyProto(declaration.getCheck(), version).build();
+    }
+    return null;
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
index 6a741ce..3060010 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java

@@ -3,7 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
-import com.android.tools.r8.keepanno.proto.KeepAnnoProtos;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.Edge;
+import com.android.tools.r8.keepanno.utils.Unimplemented;
 
 /**
  * An edge in the keep graph.
@@ -146,8 +147,9 @@
 
     private Builder() {}
 
-    public Builder applyProto(KeepAnnoProtos.Edge edge) {
+    public Builder applyProto(Edge edge, KeepSpecVersion version) {
       // TODO(b/343389186): implement this.
+      KeepEdgeMetaInfo.builder().applyProto(edge.getMetaInfo(), version).build();
       return this;
     }
 
@@ -264,7 +266,8 @@
         + '}';
   }
 
-  public void buildProto(KeepAnnoProtos.Edge.Builder builder) {
-    // TODO(b/343389186): implement this.
+  public Edge.Builder buildEdgeProto() {
+    Edge.newBuilder().setMetaInfo(getMetaInfo().buildProto());
+    throw new Unimplemented();
   }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdgeMetaInfo.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdgeMetaInfo.java
index 9cf3305..1377a05 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdgeMetaInfo.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdgeMetaInfo.java

@@ -3,24 +3,24 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import static com.android.tools.r8.keepanno.ast.KeepSpecUtils.desc;
+
 import com.android.tools.r8.keepanno.keeprules.RulePrintingUtils;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.Context;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.FieldDesc;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MetaInfo;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MethodDesc;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.TypeDesc;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Objects;
+import org.objectweb.asm.Type;
 
 public class KeepEdgeMetaInfo {
 
-  public enum KeepEdgeVersion {
-    UNKNOWN;
-
-    public String toVersionString() {
-      return name();
-    }
-  }
-
   private static final KeepEdgeMetaInfo NONE =
       new KeepEdgeMetaInfo(
-          KeepEdgeVersion.UNKNOWN, KeepEdgeContext.none(), KeepEdgeDescription.empty());
+          KeepSpecVersion.UNKNOWN, KeepEdgeContext.none(), KeepEdgeDescription.empty());
 
   public static KeepEdgeMetaInfo none() {
     return NONE;
@@ -30,12 +30,12 @@
     return new Builder();
   }
 
-  private final KeepEdgeVersion version;
+  private final KeepSpecVersion version;
   private final KeepEdgeContext context;
   private final KeepEdgeDescription description;
 
   private KeepEdgeMetaInfo(
-      KeepEdgeVersion version, KeepEdgeContext context, KeepEdgeDescription description) {
+      KeepSpecVersion version, KeepEdgeContext context, KeepEdgeDescription description) {
     this.version = version;
     this.context = context;
     this.description = description;
@@ -58,10 +58,10 @@
   }
 
   public boolean hasVersion() {
-    return version != KeepEdgeVersion.UNKNOWN;
+    return version != KeepSpecVersion.UNKNOWN;
   }
 
-  public KeepEdgeVersion getVersion() {
+  public KeepSpecVersion getVersion() {
     return version;
   }
 
@@ -80,30 +80,73 @@
     return "MetaInfo{" + String.join(", ", props) + "}";
   }
 
+  public static KeepEdgeMetaInfo fromProto(MetaInfo proto, KeepSpecVersion version) {
+    return builder().applyProto(proto, version).build();
+  }
+
+  public MetaInfo.Builder buildProto() {
+    MetaInfo.Builder builder = MetaInfo.newBuilder();
+    builder.setContext(context.buildProto());
+    if (!description.isEmpty()) {
+      builder.setDescription(description.description);
+    }
+    return builder;
+  }
+
   public static class Builder {
+    private KeepSpecVersion version = KeepSpecVersion.UNKNOWN;
     private KeepEdgeContext context = KeepEdgeContext.none();
     private KeepEdgeDescription description = KeepEdgeDescription.empty();
 
+    public Builder applyProto(MetaInfo proto, KeepSpecVersion version) {
+      // Version is a non-optional value (not part of the proto MetaInfo).
+      setVersion(version);
+      // The proto MetaInfo is optional so guard for the null case here.
+      if (proto != null) {
+        if (proto.hasContext()) {
+          setContext(KeepEdgeContext.fromProto(proto.getContext()));
+        }
+        setDescription(proto.getDescription());
+      }
+      return this;
+    }
+
+    public Builder setVersion(KeepSpecVersion version) {
+      this.version = version;
+      return this;
+    }
+
     public Builder setDescription(String description) {
-      this.description = new KeepEdgeDescription(description);
+      this.description =
+          description.isEmpty() ? KeepEdgeDescription.EMPTY : new KeepEdgeDescription(description);
+      return this;
+    }
+
+    public Builder setContext(KeepEdgeContext context) {
+      this.context = context;
       return this;
     }
 
     public Builder setContextFromClassDescriptor(String classDescriptor) {
-      context = new KeepEdgeClassContext(classDescriptor);
-      return this;
+      return setContext(new KeepEdgeClassContext(classDescriptor));
     }
 
     public Builder setContextFromMethodDescriptor(
         String classDescriptor, String methodName, String methodDescriptor) {
-      context = new KeepEdgeMethodContext(classDescriptor, methodName, methodDescriptor);
-      return this;
+      Type methodType = Type.getMethodType(methodDescriptor);
+      Type[] argumentTypes = methodType.getArgumentTypes();
+      List<String> parameters = new ArrayList<>(argumentTypes.length);
+      for (Type argumentType : argumentTypes) {
+        parameters.add(argumentType.getDescriptor());
+      }
+      return setContext(
+          new KeepEdgeMethodContext(
+              classDescriptor, methodName, methodType.getReturnType().getDescriptor(), parameters));
     }
 
     public Builder setContextFromFieldDescriptor(
         String classDescriptor, String fieldName, String fieldType) {
-      context = new KeepEdgeFieldContext(classDescriptor, fieldName, fieldType);
-      return this;
+      return setContext(new KeepEdgeFieldContext(classDescriptor, fieldName, fieldType));
     }
 
     public KeepEdgeMetaInfo build() {
@@ -111,7 +154,7 @@
           && description.equals(KeepEdgeDescription.empty())) {
         return none();
       }
-      return new KeepEdgeMetaInfo(KeepEdgeVersion.UNKNOWN, context, description);
+      return new KeepEdgeMetaInfo(version, context, description);
     }
   }
 
@@ -124,6 +167,32 @@
 
     private KeepEdgeContext() {}
 
+    public static KeepEdgeContext fromProto(Context context) {
+      if (context.hasClassDesc()) {
+        return new KeepEdgeClassContext(context.getClassDesc().getDesc());
+      }
+      if (context.hasMethodDesc()) {
+        MethodDesc methodDesc = context.getMethodDesc();
+        List<String> parameters = new ArrayList<>(methodDesc.getParameterTypesCount());
+        for (TypeDesc typeDesc : methodDesc.getParameterTypesList()) {
+          parameters.add(typeDesc.getDesc());
+        }
+        return new KeepEdgeMethodContext(
+            methodDesc.getHolder().getDesc(),
+            methodDesc.getName(),
+            methodDesc.getReturnType().getDesc(),
+            parameters);
+      }
+      if (context.hasFieldDesc()) {
+        FieldDesc fieldDesc = context.getFieldDesc();
+        return new KeepEdgeFieldContext(
+            fieldDesc.getHolder().getDesc(),
+            fieldDesc.getName(),
+            fieldDesc.getFieldType().getDesc());
+      }
+      return none();
+    }
+
     public String getDescriptorString() {
       throw new KeepEdgeException("Invalid attempt to get descriptor string from none context");
     }
@@ -137,6 +206,15 @@
     public int hashCode() {
       return System.identityHashCode(this);
     }
+
+    public final Context.Builder buildProto() {
+      return buildProto(Context.newBuilder());
+    }
+
+    public Context.Builder buildProto(Context.Builder builder) {
+      assert this == none();
+      return builder;
+    }
   }
 
   private static class KeepEdgeClassContext extends KeepEdgeContext {
@@ -168,26 +246,41 @@
     public int hashCode() {
       return classDescriptor.hashCode();
     }
+
+    @Override
+    public Context.Builder buildProto(Context.Builder builder) {
+      return builder.setClassDesc(desc(classDescriptor));
+    }
   }
 
   private static class KeepEdgeMethodContext extends KeepEdgeContext {
     private final String classDescriptor;
     private final String methodName;
-    private final String methodDescriptor;
+    private final String methodReturnType;
+    private final List<String> methodParameters;
 
     public KeepEdgeMethodContext(
-        String classDescriptor, String methodName, String methodDescriptor) {
+        String classDescriptor,
+        String methodName,
+        String methodReturnType,
+        List<String> methodParameters) {
       assert classDescriptor != null;
       assert methodName != null;
-      assert methodDescriptor != null;
+      assert methodParameters != null;
       this.classDescriptor = classDescriptor;
       this.methodName = methodName;
-      this.methodDescriptor = methodDescriptor;
+      this.methodReturnType = methodReturnType;
+      this.methodParameters = methodParameters;
     }
 
     @Override
     public String getDescriptorString() {
-      return classDescriptor + methodName + methodDescriptor;
+      StringBuilder builder = new StringBuilder();
+      builder.append(classDescriptor).append(methodName).append('(');
+      for (String parameter : methodParameters) {
+        builder.append(parameter);
+      }
+      return builder.append(')').append(methodReturnType).toString();
     }
 
     @Override
@@ -201,12 +294,26 @@
       KeepEdgeMethodContext that = (KeepEdgeMethodContext) o;
       return classDescriptor.equals(that.classDescriptor)
           && methodName.equals(that.methodName)
-          && methodDescriptor.equals(that.methodDescriptor);
+          && methodReturnType.equals(that.methodReturnType)
+          && methodParameters.equals(that.methodParameters);
     }
 
     @Override
     public int hashCode() {
-      return Objects.hash(classDescriptor, methodName, methodDescriptor);
+      return Objects.hash(classDescriptor, methodName, methodReturnType, methodParameters);
+    }
+
+    @Override
+    public Context.Builder buildProto(Context.Builder builder) {
+      MethodDesc.Builder methodBuilder =
+          MethodDesc.newBuilder()
+              .setHolder(desc(classDescriptor))
+              .setName(methodName)
+              .setReturnType(desc(methodReturnType));
+      for (String methodParameter : methodParameters) {
+        methodBuilder.addParameterTypes(desc(methodParameter));
+      }
+      return builder.setMethodDesc(methodBuilder.build());
     }
   }
 
@@ -244,6 +351,16 @@
     public int hashCode() {
       return Objects.hash(classDescriptor, fieldName, fieldType);
     }
+
+    @Override
+    public Context.Builder buildProto(Context.Builder builder) {
+      return builder.setFieldDesc(
+          FieldDesc.newBuilder()
+              .setHolder(desc(classDescriptor))
+              .setName(fieldName)
+              .setFieldType(desc(fieldType))
+              .build());
+    }
   }
 
   private static class KeepEdgeDescription {
@@ -261,12 +378,11 @@
     }
 
     @Override
-    @SuppressWarnings("EqualsGetClass")
     public boolean equals(Object o) {
       if (this == o) {
         return true;
       }
-      if (o == null || getClass() != o.getClass()) {
+      if (!(o instanceof KeepEdgeDescription)) {
         return false;
       }
       KeepEdgeDescription that = (KeepEdgeDescription) o;
@@ -282,5 +398,9 @@
     public String toString() {
       return description;
     }
+
+    public boolean isEmpty() {
+      return description.isEmpty();
+    }
   }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepFieldPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepFieldPattern.java
index f6aab3e..f863c2e 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepFieldPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepFieldPattern.java

@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MemberPatternField;
+import com.android.tools.r8.keepanno.utils.Unimplemented;
 import java.util.Objects;
 
 public final class KeepFieldPattern extends KeepMemberPattern {
@@ -145,4 +147,8 @@
         + typePattern
         + '}';
   }
+
+  public MemberPatternField.Builder buildFieldProto() {
+    throw new Unimplemented();
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java
index f11578e..d08573c 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java

@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.ast.KeepBindings.KeepBindingSymbol;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.ItemPattern;
 import java.util.Collection;
 import java.util.function.Consumer;
 import java.util.function.Function;
@@ -10,12 +12,10 @@
 /**
  * A pattern for matching items in the program.
  *
- * <p>An item pattern can be any item, or it can describe a family of classes or a family of members
- * on a classes.
+ * <p>An item pattern can describe a family of classes or a family of members.
  *
  * <p>A pattern cannot describe both a class *and* a member of a class. Either it is a pattern on
- * classes or it is a pattern on members. The distinction is defined by having a "none" member
- * pattern.
+ * classes or it is a pattern on members.
  */
 public abstract class KeepItemPattern {
 
@@ -54,5 +54,26 @@
       Consumer<KeepClassItemPattern> onClass, Consumer<KeepMemberItemPattern> onMember) {
     apply(AstUtils.toVoidFunction(onClass), AstUtils.toVoidFunction(onMember));
   }
+
+  public static KeepItemPattern fromItemProto(
+      ItemPattern proto,
+      KeepItemPattern defaultValue,
+      Function<String, KeepBindingSymbol> getSymbol) {
+    if (proto.hasClassItem()) {
+      return KeepClassItemPattern.fromClassProto(proto.getClassItem());
+    }
+    if (proto.hasMemberItem()) {
+      return KeepMemberItemPattern.fromMemberProto(proto.getMemberItem(), getSymbol);
+    }
+    return defaultValue;
+  }
+
+  public ItemPattern.Builder buildItemProto() {
+    ItemPattern.Builder builder = ItemPattern.newBuilder();
+    match(
+        clazz -> builder.setClassItem(clazz.buildClassProto()),
+        member -> builder.setMemberItem(member.buildMemberProto()));
+    return builder;
+  }
 }
 

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberItemPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberItemPattern.java
index 0c22c66..6b3dcc2 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberItemPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberItemPattern.java

@@ -4,9 +4,13 @@
 
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.ast.KeepBindings.KeepBindingSymbol;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.BindingReference;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MemberItemPattern;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Objects;
+import java.util.function.Function;
 
 public class KeepMemberItemPattern extends KeepItemPattern {
 
@@ -14,6 +18,17 @@
     return new Builder();
   }
 
+  public static KeepItemPattern fromMemberProto(
+      MemberItemPattern protoMember, Function<String, KeepBindingSymbol> getSymbol) {
+    return builder().applyProto(protoMember, getSymbol).build();
+  }
+
+  public MemberItemPattern.Builder buildMemberProto() {
+    return MemberItemPattern.newBuilder()
+        .setClassReference(classReference.buildProto())
+        .setMemberPattern(memberPattern.buildProto());
+  }
+
   public static class Builder {
 
     private KeepClassBindingReference classReference = null;
@@ -21,6 +36,30 @@
 
     private Builder() {}
 
+    public Builder applyProto(
+        MemberItemPattern protoMember, Function<String, KeepBindingSymbol> getSymbol) {
+      // The class-reference is special as we can't artificially insert an "any class" without
+      // patching up the bindings. Thus, the following hard fails if the format is missing any
+      // part of the class-reference structure, both here and in the bindings themselves.
+      if (!protoMember.hasClassReference()) {
+        throw new KeepEdgeException("Invalid MemberItemPattern, must have a valid class reference");
+      }
+      BindingReference protoClassRef = protoMember.getClassReference();
+      String protoName = protoClassRef.getName();
+      KeepBindingSymbol symbol = getSymbol.apply(protoName);
+      if (symbol == null) {
+        throw new KeepEdgeException(
+            "Invalid MemberItemPattern, reference to unbound binding: '" + protoName + "'");
+      }
+      setClassReference(KeepBindingReference.forClass(symbol));
+
+      assert memberPattern.isAllMembers();
+      if (protoMember.hasMemberPattern()) {
+        setMemberPattern(KeepMemberPattern.fromMemberProto(protoMember.getMemberPattern()));
+      }
+      return this;
+    }
+
     public Builder copyFrom(KeepMemberItemPattern pattern) {
       return setClassReference(pattern.getClassReference())
           .setMemberPattern(pattern.getMemberPattern());

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberPattern.java
index dfce0f6..5c784bc 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMemberPattern.java

@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MemberPattern;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MemberPatternGeneral;
+import com.android.tools.r8.keepanno.utils.Unimplemented;
 import java.util.Objects;
 import java.util.function.Consumer;
 import java.util.function.Function;
@@ -90,6 +93,10 @@
           + accessPattern
           + '}';
     }
+
+    public MemberPatternGeneral.Builder buildGeneralProto() {
+      throw new Unimplemented();
+    }
   }
 
   KeepMemberPattern() {}
@@ -145,4 +152,28 @@
         AstUtils.toVoidFunction(onFieldMember),
         AstUtils.toVoidFunction(onMethodMember));
   }
+
+  public MemberPattern.Builder buildProto() {
+    MemberPattern.Builder builder = MemberPattern.newBuilder();
+    match(
+        general -> builder.setGeneralMember(((Some) general).buildGeneralProto()),
+        field -> builder.setFieldMember(field.buildFieldProto()),
+        method -> builder.setMethodMember(method.buildMethodProto()));
+    return builder;
+  }
+
+  public static KeepMemberPattern fromMemberProto(MemberPattern memberPattern) {
+    if (memberPattern.hasGeneralMember()) {
+      // return KeepMemberPattern.memberBuilder().applyProto(memberPattern.getGeneralMember());
+      throw new Unimplemented();
+    }
+    if (memberPattern.hasFieldMember()) {
+      // return KeepFieldPattern.builder().applyProto(memberPattern.getFieldMember());
+      throw new Unimplemented();
+    }
+    if (memberPattern.hasMethodMember()) {
+      return KeepMethodPattern.fromMethodProto(memberPattern.getMethodMember());
+    }
+    return KeepMemberPattern.allMembers();
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodParametersPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodParametersPattern.java
index 2a7061d..e9100ee 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodParametersPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodParametersPattern.java

@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MethodParameterTypesPattern;
 import com.google.common.collect.ImmutableList;
 import java.util.Collections;
 import java.util.List;
@@ -36,6 +37,8 @@
     return null;
   }
 
+  public abstract MethodParameterTypesPattern.Builder buildProto();
+
   public static class Builder {
     ImmutableList.Builder<KeepTypePattern> parameterPatterns = ImmutableList.builder();
 
@@ -95,6 +98,15 @@
           + parameterPatterns.stream().map(Object::toString).collect(Collectors.joining(", "))
           + ")";
     }
+
+    @Override
+    public MethodParameterTypesPattern.Builder buildProto() {
+      MethodParameterTypesPattern.Builder builder = MethodParameterTypesPattern.newBuilder();
+      for (KeepTypePattern parameterPattern : parameterPatterns) {
+        builder.addTypes(parameterPattern.buildProto());
+      }
+      return builder;
+    }
   }
 
   private static class Any extends KeepMethodParametersPattern {
@@ -123,5 +135,10 @@
     public String toString() {
       return "(...)";
     }
+
+    @Override
+    public MethodParameterTypesPattern.Builder buildProto() {
+      throw new KeepEdgeException("Attempt to build message of any type encoded as absent.");
+    }
   }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodPattern.java
index 38cb49a..504bba8 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodPattern.java

@@ -3,6 +3,10 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MemberPatternMethod;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MethodParameterTypesPattern;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MethodReturnTypePattern;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.TypePattern;
 import java.util.Objects;
 
 public final class KeepMethodPattern extends KeepMemberPattern {
@@ -30,6 +34,42 @@
       return this;
     }
 
+    public Builder applyProto(MemberPatternMethod methodMember) {
+      assert namePattern.isAny();
+      if (methodMember.hasName()) {
+        setNamePattern(
+            KeepMethodNamePattern.fromStringPattern(
+                KeepStringPattern.fromProto(methodMember.getName())));
+      }
+
+      assert returnTypePattern.isAny();
+      if (methodMember.hasReturnType()) {
+        MethodReturnTypePattern returnType = methodMember.getReturnType();
+        if (returnType.hasVoidType()) {
+          setReturnTypeVoid();
+        } else if (returnType.hasSomeType()) {
+          setReturnTypePattern(
+              KeepMethodReturnTypePattern.fromType(
+                  KeepTypePattern.fromProto(returnType.getSomeType())));
+        }
+      }
+
+      assert parametersPattern.isAny();
+      if (methodMember.hasParameterTypes()) {
+        MethodParameterTypesPattern parameterTypes = methodMember.getParameterTypes();
+        KeepMethodParametersPattern.Builder parametersBuilder =
+            KeepMethodParametersPattern.builder();
+        for (TypePattern typePattern : parameterTypes.getTypesList()) {
+          parametersBuilder.addParameterTypePattern(KeepTypePattern.fromProto(typePattern));
+        }
+        setParametersPattern(parametersBuilder.build());
+      }
+
+      // TODO(b/343389186): Add annotated-by.
+      // TODO(b/343389186): Add access.
+      return this;
+    }
+
     public Builder copyFromMemberPattern(KeepMemberPattern memberPattern) {
       assert memberPattern.isGeneralMember();
       return setAccessPattern(
@@ -176,4 +216,21 @@
         + parametersPattern
         + '}';
   }
+
+  public static KeepMemberPattern fromMethodProto(MemberPatternMethod methodMember) {
+    return builder().applyProto(methodMember).build();
+  }
+
+  public MemberPatternMethod.Builder buildMethodProto() {
+    MemberPatternMethod.Builder builder =
+        MemberPatternMethod.newBuilder()
+            .setName(namePattern.asStringPattern().buildProto())
+            .setReturnType(returnTypePattern.buildProto());
+    if (!parametersPattern.isAny()) {
+      builder.setParameterTypes(parametersPattern.buildProto());
+    }
+    // TODO(b/343389186): Add annotated-by.
+    // TODO(b/343389186): Add access.
+    return builder;
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodReturnTypePattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodReturnTypePattern.java
index bd8d66f..d289c58 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodReturnTypePattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepMethodReturnTypePattern.java

@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.MethodReturnTypePattern;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.TypeVoid;
 
 public abstract class KeepMethodReturnTypePattern {
 
@@ -101,4 +103,16 @@
       return typePattern.toString();
     }
   }
+
+  public MethodReturnTypePattern.Builder buildProto() {
+    MethodReturnTypePattern.Builder builder = MethodReturnTypePattern.newBuilder();
+    if (isAny()) {
+      // The unset oneof denotes any return type.
+      return builder;
+    }
+    if (isVoid()) {
+      return builder.setVoidType(TypeVoid.getDefaultInstance());
+    }
+    return builder.setSomeType(asType().buildProto());
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPackagePattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPackagePattern.java
index 69fc5b4..16d9ef2 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPackagePattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPackagePattern.java

@@ -3,6 +3,10 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.PackagePattern;
+import com.android.tools.r8.keepanno.utils.Unimplemented;
+
 public abstract class KeepPackagePattern {
 
   public static Builder builder() {
@@ -21,10 +25,48 @@
     return KeepPackagePattern.builder().exact(fullPackage).build();
   }
 
+  public static KeepPackagePattern fromProto(PackagePattern proto) {
+    return builder().applyProto(proto).build();
+  }
+
+  public PackagePattern.Builder buildProto() {
+    PackagePattern.Builder builder = PackagePattern.newBuilder();
+    if (isAny()) {
+      // An unset oneof implies "any package" (including multiple package parts).
+      return builder;
+    }
+    if (isTop()) {
+      // The top/unspecified package is encoded as the empty package name.
+      return builder.setName(KeepSpecProtos.StringPattern.newBuilder().setExact(""));
+    }
+    // TODO(b/343389186): Rewrite the package patterns to use the tree structure.
+    return builder.setExactPackageHack(getExactPackageAsString());
+  }
+
   public static class Builder {
 
     private KeepPackagePattern pattern;
 
+    public Builder applyProto(PackagePattern pkg) {
+      if (pkg.hasExactPackageHack()) {
+        exact(pkg.getExactPackageHack());
+        return this;
+      }
+      if (pkg.hasName()) {
+        KeepStringPattern stringPattern = KeepStringPattern.fromProto(pkg.getName());
+        if (stringPattern.isExact() && stringPattern.asExactString().isEmpty()) {
+          return top();
+        }
+        throw new Unimplemented();
+      }
+      if (pkg.hasNode()) {
+        throw new Unimplemented();
+      }
+      // The unset oneof implies any package.
+      assert pattern.isAny();
+      return this;
+    }
+
     public Builder any() {
       pattern = Any.getInstance();
       return this;

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPrimitiveTypePattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPrimitiveTypePattern.java
index f79093d..ca5d756 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPrimitiveTypePattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepPrimitiveTypePattern.java

@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.TypePatternPrimitive;
 import com.google.common.collect.ImmutableMap;
 import java.util.Map;
 import java.util.function.Consumer;
@@ -92,4 +93,56 @@
   public static void forEachPrimitive(Consumer<KeepPrimitiveTypePattern> fn) {
     PRIMITIVES.values().forEach(fn);
   }
+
+  public static KeepPrimitiveTypePattern fromProto(TypePatternPrimitive primitive) {
+    switch (primitive.getNumber()) {
+      case TypePatternPrimitive.PRIMITIVE_BOOLEAN_VALUE:
+        return getBoolean();
+      case TypePatternPrimitive.PRIMITIVE_BYTE_VALUE:
+        return getByte();
+      case TypePatternPrimitive.PRIMITIVE_CHAR_VALUE:
+        return getChar();
+      case TypePatternPrimitive.PRIMITIVE_SHORT_VALUE:
+        return getShort();
+      case TypePatternPrimitive.PRIMITIVE_INT_VALUE:
+        return getInt();
+      case TypePatternPrimitive.PRIMITIVE_LONG_VALUE:
+        return getLong();
+      case TypePatternPrimitive.PRIMITIVE_FLOAT_VALUE:
+        return getFloat();
+      case TypePatternPrimitive.PRIMITIVE_DOUBLE_VALUE:
+        return getDouble();
+      default:
+        return getAny();
+    }
+  }
+
+  public TypePatternPrimitive buildProto() {
+    if (this == BOOLEAN) {
+      return TypePatternPrimitive.PRIMITIVE_BOOLEAN;
+    }
+    if (this == BYTE) {
+      return TypePatternPrimitive.PRIMITIVE_BYTE;
+    }
+    if (this == CHAR) {
+      return TypePatternPrimitive.PRIMITIVE_CHAR;
+    }
+    if (this == SHORT) {
+      return TypePatternPrimitive.PRIMITIVE_SHORT;
+    }
+    if (this == INT) {
+      return TypePatternPrimitive.PRIMITIVE_INT;
+    }
+    if (this == LONG) {
+      return TypePatternPrimitive.PRIMITIVE_LONG;
+    }
+    if (this == FLOAT) {
+      return TypePatternPrimitive.PRIMITIVE_FLOAT;
+    }
+    if (this == DOUBLE) {
+      return TypePatternPrimitive.PRIMITIVE_DOUBLE;
+    }
+    assert isAny();
+    return TypePatternPrimitive.PRIMITIVE_UNSPECIFIED;
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepQualifiedClassNamePattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepQualifiedClassNamePattern.java
index 25b98af..4b1fcf7 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepQualifiedClassNamePattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepQualifiedClassNamePattern.java

@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.ClassNamePattern;
 import java.util.Objects;
 
 public final class KeepQualifiedClassNamePattern {
@@ -44,13 +45,36 @@
         .build();
   }
 
+  public static KeepQualifiedClassNamePattern fromProto(ClassNamePattern clazz) {
+    return KeepQualifiedClassNamePattern.builder().applyProto(clazz).build();
+  }
+
+  public ClassNamePattern.Builder buildProto() {
+    return ClassNamePattern.newBuilder()
+        .setPackage(packagePattern.buildProto())
+        .setUnqualifiedName(namePattern.buildProto());
+  }
+
   public static class Builder {
 
-    private KeepPackagePattern packagePattern;
-    private KeepUnqualfiedClassNamePattern namePattern;
+    private KeepPackagePattern packagePattern = KeepPackagePattern.any();
+    private KeepUnqualfiedClassNamePattern namePattern = KeepUnqualfiedClassNamePattern.any();
 
     private Builder() {}
 
+    public Builder applyProto(ClassNamePattern proto) {
+      assert packagePattern.isAny();
+      if (proto.hasPackage()) {
+        setPackagePattern(KeepPackagePattern.fromProto(proto.getPackage()));
+      }
+
+      assert namePattern.isAny();
+      if (proto.hasUnqualifiedName()) {
+        setNamePattern(KeepUnqualfiedClassNamePattern.fromProto(proto.getUnqualifiedName()));
+      }
+      return this;
+    }
+
     public Builder setPackagePattern(KeepPackagePattern packagePattern) {
       this.packagePattern = packagePattern;
       return this;

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepSpecUtils.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepSpecUtils.java
new file mode 100644
index 0000000..b5f934b
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepSpecUtils.java

@@ -0,0 +1,18 @@
+// Copyright (c) 2024, 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.keepanno.ast;
+
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.TypeDesc;
+import com.google.protobuf.MessageOrBuilder;
+import java.util.function.Consumer;
+
+public final class KeepSpecUtils {
+
+  private KeepSpecUtils() {}
+
+  public static TypeDesc desc(String descriptor) {
+    return TypeDesc.newBuilder().setDesc(descriptor).build();
+  }
+}

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepSpecVersion.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepSpecVersion.java
new file mode 100644
index 0000000..4a06ff5
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepSpecVersion.java

@@ -0,0 +1,45 @@
+// Copyright (c) 2024, 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.keepanno.ast;
+
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.Version;
+
+public enum KeepSpecVersion {
+  UNKNOWN(0, 0, 0),
+  ALPHA(0, 1, 0);
+
+  private final int major;
+  private final int minor;
+  private final int patch;
+
+  KeepSpecVersion(int major, int minor, int patch) {
+    this.major = major;
+    this.minor = minor;
+    this.patch = patch;
+  }
+
+  public static KeepSpecVersion getCurrent() {
+    return ALPHA;
+  }
+
+  public static KeepSpecVersion fromProto(Version version) {
+    for (KeepSpecVersion value : values()) {
+      if (value.major == version.getMajor()
+          && value.minor == version.getMinor()
+          && value.patch == version.getPatch()) {
+        return value;
+      }
+    }
+    return UNKNOWN;
+  }
+
+  public String toVersionString() {
+    return "" + major + "." + minor + "." + patch;
+  }
+
+  public Version.Builder buildProto() {
+    return Version.newBuilder().setMajor(major).setMinor(minor).setPatch(patch);
+  }
+}

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepStringPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepStringPattern.java
index a9b1772..549e12f 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepStringPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepStringPattern.java

@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.StringPattern;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.StringPatternInexact;
 import java.util.Objects;
 
 public class KeepStringPattern {
@@ -22,6 +24,25 @@
     return new Builder();
   }
 
+  public static KeepStringPattern fromProto(StringPattern proto) {
+    return builder().applyProto(proto).build();
+  }
+
+  public StringPattern.Builder buildProto() {
+    StringPattern.Builder builder = StringPattern.newBuilder();
+    if (isAny()) {
+      // An unset oneof signifies the "any" string pattern.
+      return builder;
+    }
+    if (isExact()) {
+      return builder.setExact(exact);
+    }
+    return builder.setInexact(
+        StringPatternInexact.newBuilder()
+            .setPrefix(prefix == null ? "" : prefix)
+            .setSuffix(suffix == null ? "" : suffix));
+  }
+
   public static class Builder {
     private String exact = null;
     private String prefix = null;
@@ -29,6 +50,21 @@
 
     private Builder() {}
 
+    public Builder applyProto(StringPattern name) {
+      if (name.hasExact()) {
+        return setExact(name.getExact());
+      }
+      if (name.hasInexact()) {
+        StringPatternInexact inexact = name.getInexact();
+        setPrefix(inexact.getPrefix());
+        setSuffix(inexact.getSuffix());
+        return this;
+      }
+      // The unset oneof implies any. Don't assign any fields.
+      assert build().isAny();
+      return this;
+    }
+
     public Builder setExact(String exact) {
       this.exact = exact;
       return this;

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTypePattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTypePattern.java
index 7e3c088..a123e61 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTypePattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTypePattern.java

@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.TypePattern;
+import com.android.tools.r8.keepanno.utils.Unimplemented;
 import com.google.common.collect.ImmutableMap;
 import java.util.Map;
 import java.util.Objects;
@@ -56,6 +58,21 @@
     throw new KeepEdgeException("Invalid type descriptor: " + typeDescriptor);
   }
 
+  public static KeepTypePattern fromProto(TypePattern typeProto) {
+    if (typeProto.hasPrimitive()) {
+      return KeepTypePattern.fromPrimitive(
+          KeepPrimitiveTypePattern.fromProto(typeProto.getPrimitive()));
+    }
+    if (typeProto.hasArray()) {
+      return KeepTypePattern.fromArray(KeepArrayTypePattern.fromProto(typeProto.getArray()));
+    }
+    if (typeProto.hasClazz()) {
+      return KeepTypePattern.fromClass(
+          KeepQualifiedClassNamePattern.fromProto(typeProto.getClazz()));
+    }
+    return KeepTypePattern.any();
+  }
+
   public abstract <T> T apply(
       Supplier<T> onAny,
       Function<KeepPrimitiveTypePattern, T> onPrimitive,
@@ -263,4 +280,19 @@
       return onInstanceOf.apply(instanceOf);
     }
   }
+
+  public TypePattern.Builder buildProto() {
+    TypePattern.Builder builder = TypePattern.newBuilder();
+    match(
+        () -> {
+          // The unset oneof is "any type".
+        },
+        primitive -> builder.setPrimitive(primitive.buildProto()),
+        array -> builder.setArray(array.buildProto()),
+        clazz -> builder.setClazz(clazz.buildProto()),
+        instanceOf -> {
+          throw new Unimplemented();
+        });
+    return builder;
+  }
 }

diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepUnqualfiedClassNamePattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepUnqualfiedClassNamePattern.java
index a974f67..e00ed78 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepUnqualfiedClassNamePattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepUnqualfiedClassNamePattern.java

@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.UnqualifiedNamePattern;
+
 public class KeepUnqualfiedClassNamePattern {
 
   private static final KeepUnqualfiedClassNamePattern ANY =
@@ -68,10 +70,26 @@
     return unqualifiedNamePattern.toString();
   }
 
+  public static KeepUnqualfiedClassNamePattern fromProto(UnqualifiedNamePattern proto) {
+    return builder().applyProto(proto).build();
+  }
+
+  public UnqualifiedNamePattern.Builder buildProto() {
+    return UnqualifiedNamePattern.newBuilder().setName(unqualifiedNamePattern.buildProto());
+  }
+
   public static class Builder {
 
     private KeepStringPattern pattern = KeepStringPattern.any();
 
+    public Builder applyProto(UnqualifiedNamePattern proto) {
+      assert pattern.isAny();
+      if (proto.hasName()) {
+        setPattern(KeepStringPattern.fromProto(proto.getName()));
+      }
+      return this;
+    }
+
     public Builder any() {
       pattern = KeepStringPattern.any();
       return this;

diff --git a/src/keepanno/proto/keepanno.proto b/src/keepanno/proto/keepanno.proto
deleted file mode 100644
index a4f96d7..0000000
--- a/src/keepanno/proto/keepanno.proto
+++ /dev/null

@@ -1,56 +0,0 @@
-// Copyright (c) 2024, 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.
-syntax = "proto3";
-
-package com.android.tools.r8.keepanno.proto;
-
-// All messages are placed under the outer class. This makes it a bit nicer to
-// implement the AST <-> Proto conversions without type conflicts.
-option java_multiple_files = false;
-
-// Descriptive name of the outer class (default would have been `Keepanno`).
-option java_outer_classname = "KeepAnnoProtos";
-
-// Java package consistent with R8 convention.
-option java_package = "com.android.tools.r8.keepanno.proto";
-
-message Version {
-  uint32 major = 1;
-  uint32 minor = 2;
-  uint32 patch = 3;
-}
-
-message Context {
-  oneof context_oneof {
-    string class_descriptor = 1;
-    string method_descriptor = 2;
-    string field_descriptor = 3;
-  }
-}
-
-message MetaInfo {
-  Version version = 1;
-  Context context = 2;
-}
-
-message Declaration {
-  MetaInfo meta_info = 1;
-  oneof decl_oneof {
-    Edge edge = 2;
-    CheckRemoved check_removed = 3;
-    CheckDiscarded check_discarded = 4;
-  }
-}
-
-message CheckRemoved {
-  // TODO(b/343389186): Add content.
-}
-
-message CheckDiscarded {
-  // TODO(b/343389186): Add content.
-}
-
-message Edge {
-  // TODO(b/343389186): Add content.
-}

diff --git a/src/keepanno/proto/keepspec.proto b/src/keepanno/proto/keepspec.proto
new file mode 100644
index 0000000..451b137
--- /dev/null
+++ b/src/keepanno/proto/keepspec.proto

@@ -0,0 +1,226 @@
+// Copyright (c) 2024, 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.
+syntax = "proto3";
+
+package com.android.tools.r8.keepanno.proto;
+
+// All messages are placed under the outer class. This makes it a bit nicer to
+// implement the AST <-> Proto conversions without type conflicts.
+option java_multiple_files = false;
+
+// Camel-case the outer class name (default is `Keepspec`).
+option java_outer_classname = "KeepSpecProtos";
+
+// Java package consistent with R8 convention.
+option java_package = "com.android.tools.r8.keepanno.proto";
+
+// Top-level container for the keep specification
+message KeepSpec {
+  Version version = 1;
+  repeated Declaration declarations = 2;
+}
+
+message Version {
+  uint32 major = 1;
+  uint32 minor = 2;
+  uint32 patch = 3;
+}
+
+message Declaration {
+  oneof decl_oneof {
+    Edge edge = 2;
+    Check check = 3;
+  }
+}
+
+// Note: the messages and fields avoid the use of `descriptor` in any place as
+// that name is used internally in the protobuf encodings. We consistently use
+// the short-form `desc` throughout.
+
+message Context {
+  oneof context_oneof {
+    TypeDesc class_desc = 1;
+    MethodDesc method_desc = 2;
+    FieldDesc field_desc = 3;
+  }
+}
+
+message TypeDesc {
+  string desc = 1;
+}
+
+message MethodDesc {
+  string name = 1;
+  TypeDesc holder = 2;
+  TypeDesc return_type = 3;
+  repeated TypeDesc parameter_types = 4;
+}
+
+message FieldDesc {
+  string name = 1;
+  TypeDesc holder = 2;
+  TypeDesc field_type = 3;
+}
+
+message MetaInfo {
+  optional Context context = 1;
+  optional string description = 2;
+}
+
+enum CheckKind {
+  CHECK_UNSPECIFIED = 0;
+  CHECK_REMOVED = 1;
+  CHECK_OPTIMIZED_OUT = 2;
+}
+
+message Check {
+  optional MetaInfo meta_info = 1;
+  CheckKind kind = 2;
+  Bindings bindings = 3;
+  BindingReference item = 4;
+}
+
+message Edge {
+  MetaInfo meta_info = 1;
+  // TODO(b/343389186): Add content.
+}
+
+message Bindings {
+  repeated Binding bindings = 1;
+}
+
+message Binding {
+  string name = 1;
+  ItemPattern item = 2;
+}
+
+message BindingReference {
+  string name = 1;
+}
+
+message ItemPattern {
+  oneof item_oneof {
+    ClassItemPattern class_item = 1;
+    MemberItemPattern member_item = 2;
+  }
+}
+
+message ClassItemPattern {
+  optional ClassNamePattern class_name = 1;
+  // TODO(b/343389186): Add instance-of.
+  // TODO(b/343389186): Add annotated-by.
+}
+
+message ClassNamePattern {
+  optional PackagePattern package = 1;
+  optional UnqualifiedNamePattern unqualified_name = 2;
+}
+
+message PackagePattern {
+  oneof package_oneof {
+    // An unset oneof implies any package (including multiple package parts).
+    StringPattern name = 1;
+    PackageNode node = 2;
+    // TODO(b/343389186): Rewrite package pattern AST to the tree structure.
+    string exact_package_hack = 3;
+  }
+}
+
+message PackageNode {
+  PackagePattern lhs = 1;
+  PackagePattern rhs = 2;
+}
+
+message StringPattern {
+  // The string pattern is split in two so that we can distinguish the exact
+  // empty string, from the inexact patterns.
+  oneof pattern_oneof {
+    // Unset oneof denotes any type.
+    string exact = 1;
+    StringPatternInexact inexact = 2;
+  }
+}
+
+message StringPatternInexact {
+  optional string prefix = 2;
+  optional string suffix = 3;
+}
+
+message UnqualifiedNamePattern {
+  optional StringPattern name = 1;
+}
+
+message MemberItemPattern {
+  BindingReference class_reference = 1;
+  optional MemberPattern member_pattern = 2;
+}
+
+message MemberPattern {
+  oneof member_oneof {
+    MemberPatternGeneral general_member = 1;
+    MemberPatternField field_member = 2;
+    MemberPatternMethod method_member = 3;
+  }
+}
+
+message MemberPatternGeneral {
+  // TODO(b/343389186): Add content.
+}
+
+message MemberPatternField {
+  // TODO(b/343389186): Add content.
+}
+
+message MemberPatternMethod {
+  optional StringPattern name = 1;
+  optional MethodReturnTypePattern return_type = 2;
+  optional MethodParameterTypesPattern parameter_types = 3;
+  // TODO(b/343389186): Add annotated-by.
+  // TODO(b/343389186): Add access.
+}
+
+message MethodReturnTypePattern {
+  oneof return_type_oneof {
+    // Unset type denotes any type.
+    TypeVoid void_type = 1;
+    TypePattern some_type = 2;
+  }
+}
+
+message MethodParameterTypesPattern {
+  repeated TypePattern types = 1;
+}
+
+message TypeVoid {
+  // Placeholder to denote a 'void' method return type.
+}
+
+message TypePattern {
+  oneof type_oneof {
+    // Unset type denotes any type.
+    TypePatternPrimitive primitive = 1;
+    TypePatternArray array = 2;
+    ClassNamePattern clazz = 3;
+    // TODO(b/343389186): Add instance-of.
+  }
+}
+
+enum TypePatternPrimitive {
+  PRIMITIVE_UNSPECIFIED = 0; // Denotes any primitive.
+  PRIMITIVE_BOOLEAN = 1;
+  PRIMITIVE_BYTE = 2;
+  PRIMITIVE_CHAR = 3;
+  PRIMITIVE_SHORT = 4;
+  PRIMITIVE_INT = 5;
+  PRIMITIVE_LONG = 6;
+  PRIMITIVE_FLOAT = 7;
+  PRIMITIVE_DOUBLE = 8;
+}
+
+message TypePatternArray {
+  // An unset or zero-valued dimensions will be interpreted as 1.
+  optional uint32 dimensions = 1;
+  optional TypePattern base_type = 2;
+}
+

diff --git a/src/main/java/com/android/tools/r8/D8CommandParser.java b/src/main/java/com/android/tools/r8/D8CommandParser.java
index a6e5d5f..a16189b 100644
--- a/src/main/java/com/android/tools/r8/D8CommandParser.java
+++ b/src/main/java/com/android/tools/r8/D8CommandParser.java

@@ -396,8 +396,6 @@
     if (globalsOutputPath != null) {
       builder.setGlobalSyntheticsOutput(globalsOutputPath);
     }
-    builder.setOutput(outputPath, outputMode);
-    builder.setEnableExperimentalMissingLibraryApiModeling(true);
-    return builder;
+    return builder.setOutput(outputPath, outputMode);
   }
 }

diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 851df61..74f9c92 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java

@@ -94,6 +94,7 @@
 import com.android.tools.r8.shaking.Enqueuer.Mode;
 import com.android.tools.r8.shaking.EnqueuerFactory;
 import com.android.tools.r8.shaking.EnqueuerResult;
+import com.android.tools.r8.shaking.KeepSpecificationSource;
 import com.android.tools.r8.shaking.MainDexInfo;
 import com.android.tools.r8.shaking.MainDexListBuilder;
 import com.android.tools.r8.shaking.ProguardConfigurationRule;
@@ -105,6 +106,7 @@
 import com.android.tools.r8.shaking.TreePruner;
 import com.android.tools.r8.shaking.TreePrunerConfiguration;
 import com.android.tools.r8.shaking.WhyAreYouKeepingConsumer;
+import com.android.tools.r8.startup.NonStartupInStartupOutliner;
 import com.android.tools.r8.synthesis.SyntheticFinalization;
 import com.android.tools.r8.synthesis.SyntheticItems;
 import com.android.tools.r8.utils.AndroidApp;
@@ -309,6 +311,8 @@
       timing.begin("Register references and more setup");
       assert ArtProfileCompletenessChecker.verify(appView);
 
+      readKeepSpecifications(appView, keepDeclarations);
+
       // Check for potentially having pass-through of Cf-code for kotlin libraries.
       options.enableCfByteCodePassThrough =
           options.isGeneratingClassFiles() && KotlinMetadataUtils.mayProcessKotlinMetadata(appView);
@@ -706,6 +710,8 @@
           appView.getArtProfileCollection().withoutMissingItems(appView));
       appView.setStartupProfile(appView.getStartupProfile().withoutMissingItems(appView));
 
+      new NonStartupInStartupOutliner(appView).runIfNecessary(executorService, timing);
+
       if (appView.appInfo().hasLiveness()) {
         SyntheticFinalization.finalizeWithLiveness(appView.withLiveness(), executorService, timing);
       } else {
@@ -891,6 +897,19 @@
     }
   }
 
+  private void readKeepSpecifications(
+      AppView<AppInfoWithClassHierarchy> appView, List<KeepDeclaration> keepDeclarations) {
+    timing.begin("Read keep specifications");
+    try {
+      for (KeepSpecificationSource source : appView.options().getKeepSpecifications()) {
+        source.parse(keepDeclarations::add);
+      }
+    } catch (ResourceException e) {
+      options.reporter.error(new ExceptionDiagnostic(e, e.getOrigin()));
+    }
+    timing.end();
+  }
+
   private void writeKeepDeclarationsToConfigurationConsumer(
       List<KeepDeclaration> keepDeclarations) {
     if (options.configurationConsumer == null) {

diff --git a/src/main/java/com/android/tools/r8/R8Command.java b/src/main/java/com/android/tools/r8/R8Command.java
index adfaf29..36f1ff3 100644
--- a/src/main/java/com/android/tools/r8/R8Command.java
+++ b/src/main/java/com/android/tools/r8/R8Command.java

@@ -27,6 +27,7 @@
 import com.android.tools.r8.origin.PathOrigin;
 import com.android.tools.r8.profile.art.ArtProfileForRewriting;
 import com.android.tools.r8.shaking.FilteredClassPath;
+import com.android.tools.r8.shaking.KeepSpecificationSource;
 import com.android.tools.r8.shaking.ProguardConfiguration;
 import com.android.tools.r8.shaking.ProguardConfigurationParser;
 import com.android.tools.r8.shaking.ProguardConfigurationParserOptions;
@@ -120,6 +121,7 @@
     private Consumer<ProguardConfiguration.Builder> proguardConfigurationConsumerForTesting = null;
     private Consumer<List<ProguardConfigurationRule>> syntheticProguardRulesConsumer = null;
     private StringConsumer desugaredLibraryKeepRuleConsumer = null;
+    private final List<KeepSpecificationSource> keepSpecifications = new ArrayList<>();
     private final List<ProguardConfigurationSource> proguardConfigs = new ArrayList<>();
     private boolean disableTreeShaking = false;
     private boolean disableMinification = false;
@@ -235,6 +237,20 @@
       return self();
     }
 
+    public Builder addKeepSpecificationFiles(Path... paths) {
+      return addKeepSpecificationFiles(Arrays.asList(paths));
+    }
+
+    public Builder addKeepSpecificationFiles(Collection<Path> paths) {
+      paths.forEach(p -> keepSpecifications.add(KeepSpecificationSource.fromFile(p)));
+      return self();
+    }
+
+    public Builder addKeepSpecificationData(byte[] data, Origin origin) {
+      keepSpecifications.add(KeepSpecificationSource.fromBytes(origin, data));
+      return self();
+    }
+
     /**
      * Set Proguard compatibility mode.
      *
@@ -755,7 +771,8 @@
               getCancelCompilationChecker(),
               androidResourceProvider,
               androidResourceConsumer,
-              resourceShrinkerConfiguration);
+              resourceShrinkerConfiguration,
+              keepSpecifications);
 
       if (inputDependencyGraphConsumer != null) {
         inputDependencyGraphConsumer.finished();
@@ -933,6 +950,7 @@
 
   private final List<ProguardConfigurationRule> mainDexKeepRules;
   private final ProguardConfiguration proguardConfiguration;
+  private final List<KeepSpecificationSource> keepSpecifications;
   private final boolean enableTreeShaking;
   private final boolean enableMinification;
   private final boolean forceProguardCompatibility;
@@ -1051,7 +1069,8 @@
       CancelCompilationChecker cancelCompilationChecker,
       AndroidResourceProvider androidResourceProvider,
       AndroidResourceConsumer androidResourceConsumer,
-      ResourceShrinkerConfiguration resourceShrinkerConfiguration) {
+      ResourceShrinkerConfiguration resourceShrinkerConfiguration,
+      List<KeepSpecificationSource> keepSpecifications) {
     super(
         inputApp,
         mode,
@@ -1078,6 +1097,7 @@
     assert mainDexKeepRules != null;
     this.mainDexKeepRules = mainDexKeepRules;
     this.proguardConfiguration = proguardConfiguration;
+    this.keepSpecifications = keepSpecifications;
     this.enableTreeShaking = enableTreeShaking;
     this.enableMinification = enableMinification;
     this.forceProguardCompatibility = forceProguardCompatibility;
@@ -1105,6 +1125,7 @@
     super(printHelp, printVersion);
     mainDexKeepRules = ImmutableList.of();
     proguardConfiguration = null;
+    keepSpecifications = null;
     enableTreeShaking = false;
     enableMinification = false;
     forceProguardCompatibility = false;
@@ -1164,6 +1185,8 @@
                 && !internal.isShrinking()
                 && !internal.isMinifying());
 
+    internal.setKeepSpecificationSources(keepSpecifications);
+
     assert !internal.verbose;
     internal.mainDexKeepRules = mainDexKeepRules;
     internal.minimalMainDex = internal.debug;

diff --git a/src/main/java/com/android/tools/r8/graph/AccessFlags.java b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
index 825655a..175abb4 100644
--- a/src/main/java/com/android/tools/r8/graph/AccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/AccessFlags.java

@@ -269,8 +269,9 @@
     return newAccessFlags;
   }
 
-  public void promoteToStatic() {
+  public T promoteToStatic() {
     promote(Constants.ACC_STATIC);
+    return self();
   }
 
   private boolean wasSet(int flag) {

diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index d6216c3..30f63fd 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java

@@ -1003,10 +1003,12 @@
       DexDebugInfo newDebugInfo = dexCode.debugInfoWithFakeThisParameter(appView.dexItemFactory());
       assert (newDebugInfo == null) || (arity == newDebugInfo.getParameterCount());
       dexCode.setDebugInfo(newDebugInfo);
-    } else {
-      assert code.isCfCode();
+    } else if (code.isCfCode()) {
       CfCode cfCode = code.asCfCode();
       cfCode.addFakeThisParameter(appView.dexItemFactory());
+    } else if (code.isLirCode()) {
+      assert appView.options().isRelease();
+      assert code.asLirCode().getDebugLocalInfoTable() == null;
     }
   }
 

diff --git a/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java b/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java
index 2aad1c9..e198ebf 100644
--- a/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/lens/GraphLens.java

@@ -460,6 +460,10 @@
     return null;
   }
 
+  public boolean isNonStartupInStartupOutlinerLens() {
+    return false;
+  }
+
   public boolean isProtoNormalizerLens() {
     return false;
   }

diff --git a/src/main/java/com/android/tools/r8/graph/lens/NestedGraphLens.java b/src/main/java/com/android/tools/r8/graph/lens/NestedGraphLens.java
index fd7a46d..4363bdf 100644
--- a/src/main/java/com/android/tools/r8/graph/lens/NestedGraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/lens/NestedGraphLens.java

@@ -27,8 +27,8 @@
  * <p>Subclasses can override the lookup methods.
  *
  * <p>For method mapping where invocation type can change just override {@link
- * #mapInvocationType(DexMethod, DexMethod, InvokeType)} if the default name mapping applies, and
- * only invocation type might need to change.
+ * #mapInvocationType(DexMethod, DexMethod, DexMethod, InvokeType)} if the default name mapping
+ * applies, and only invocation type might need to change.
  */
 public class NestedGraphLens extends DefaultNonIdentityGraphLens {
 
@@ -199,7 +199,10 @@
                   rewrittenReboundReference))
           .setType(
               mapInvocationType(
-                  rewrittenReboundReference, previous.getReference(), previous.getType()))
+                  rewrittenReference,
+                  rewrittenReboundReference,
+                  previous.getReference(),
+                  previous.getType()))
           .build();
     } else {
       // TODO(b/168282032): We should always have the rebound reference, so this should become
@@ -220,7 +223,8 @@
       return MethodLookupResult.builder(this, codeLens)
           .setReference(newMethod)
           .setPrototypeChanges(newPrototypeChanges)
-          .setType(mapInvocationType(newMethod, previous.getReference(), previous.getType()))
+          .setType(
+              mapInvocationType(newMethod, newMethod, previous.getReference(), previous.getType()))
           .build();
     }
   }
@@ -271,7 +275,7 @@
    * method or {@link #lookupMethod(DexMethod, DexMethod, InvokeType)}
    */
   protected InvokeType mapInvocationType(
-      DexMethod newMethod, DexMethod originalMethod, InvokeType type) {
+      DexMethod newMethod, DexMethod newReboundMethod, DexMethod originalMethod, InvokeType type) {
     return type;
   }
 

diff --git a/src/main/java/com/android/tools/r8/ir/code/FieldGet.java b/src/main/java/com/android/tools/r8/ir/code/FieldGet.java
index c1dee99..5a42ddc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/FieldGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/FieldGet.java

@@ -17,6 +17,8 @@
 
   TypeElement getOutType();
 
+  FieldInstruction asFieldInstruction();
+
   boolean isInstanceGet();
 
   InstanceGet asInstanceGet();

diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index 13ce76b..ca0f4269 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java

@@ -76,6 +76,7 @@
 import com.android.tools.r8.ir.code.ConstMethodHandle;
 import com.android.tools.r8.ir.code.ConstMethodType;
 import com.android.tools.r8.ir.code.DexItemBasedConstString;
+import com.android.tools.r8.ir.code.FieldGet;
 import com.android.tools.r8.ir.code.FieldInstruction;
 import com.android.tools.r8.ir.code.FieldPut;
 import com.android.tools.r8.ir.code.IRCode;
@@ -626,21 +627,8 @@
               }
               if (newOutValue != null) {
                 if (lookup.hasReadCastType() && newOutValue.hasNonDebugUsers()) {
-                  TypeElement castType =
-                      TypeElement.fromDexType(
-                          lookup.getReadCastType(), newOutValue.getType().nullability(), appView);
-                  Value castOutValue = code.createValue(castType);
-                  newOutValue.replaceUsers(castOutValue);
-                  CheckCast checkCast =
-                      SafeCheckCast.builder()
-                          .setCastType(lookup.getReadCastType())
-                          .setObject(newOutValue)
-                          .setOutValue(castOutValue)
-                          .setPosition(instanceGet)
-                          .build();
-                  iterator.addThrowingInstructionToPossiblyThrowingBlock(
-                      code, blocks, checkCast, options);
-                  affectedPhis.addAll(checkCast.outValue().uniquePhiUsers());
+                  insertReadCast(
+                      code, blocks, iterator, instanceGet, lookup, newOutValue, affectedPhis);
                 } else if (newOutValue.getType() != instanceGet.getOutType()) {
                   affectedPhis.addAll(newOutValue.uniquePhiUsers());
                 }
@@ -684,21 +672,8 @@
               }
               if (newOutValue != null) {
                 if (lookup.hasReadCastType() && newOutValue.hasNonDebugUsers()) {
-                  TypeElement castType =
-                      TypeElement.fromDexType(
-                          lookup.getReadCastType(), newOutValue.getType().nullability(), appView);
-                  Value castOutValue = code.createValue(castType);
-                  newOutValue.replaceUsers(castOutValue);
-                  CheckCast checkCast =
-                      SafeCheckCast.builder()
-                          .setCastType(lookup.getReadCastType())
-                          .setObject(newOutValue)
-                          .setOutValue(castOutValue)
-                          .setPosition(staticGet)
-                          .build();
-                  iterator.addThrowingInstructionToPossiblyThrowingBlock(
-                      code, blocks, checkCast, options);
-                  affectedPhis.addAll(checkCast.outValue().uniquePhiUsers());
+                  insertReadCast(
+                      code, blocks, iterator, staticGet, lookup, newOutValue, affectedPhis);
                 } else if (newOutValue.getType() != staticGet.getOutType()) {
                   affectedPhis.addAll(newOutValue.uniquePhiUsers());
                 }
@@ -1067,6 +1042,30 @@
     instructionIterator.removeOrReplaceByDebugLocalRead();
   }
 
+  private void insertReadCast(
+      IRCode code,
+      BasicBlockIterator blocks,
+      InstructionListIterator iterator,
+      FieldGet fieldGet,
+      FieldLookupResult lookup,
+      Value newOutValue,
+      Set<Phi> affectedPhis) {
+    TypeElement castTypeElement =
+        TypeElement.fromDexType(
+            lookup.getReadCastType(), newOutValue.getType().nullability(), appView);
+    Value castOutValue = code.createValue(castTypeElement);
+    newOutValue.replaceUsers(castOutValue);
+    CheckCast checkCast =
+        SafeCheckCast.builder()
+            .setCastType(lookup.getReadCastType())
+            .setObject(newOutValue)
+            .setOutValue(castOutValue)
+            .setPosition(fieldGet.asFieldInstruction())
+            .build();
+    iterator.addThrowingInstructionToPossiblyThrowingBlock(code, blocks, checkCast, options);
+    affectedPhis.addAll(checkCast.outValue().uniquePhiUsers());
+  }
+
   private Argument rewriteArgumentType(
       IRCode code,
       Argument argument,

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java
index 5d60881..ca1d499 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java

@@ -196,7 +196,7 @@
         .setPrototypeChanges(
             internalDescribePrototypeChanges(
                 previous.getPrototypeChanges(), previous.getReference(), result))
-        .setType(mapInvocationType(result, previous.getReference(), previous.getType()))
+        .setType(mapInvocationType(result, result, previous.getReference(), previous.getType()))
         .build();
   }
 
@@ -244,7 +244,7 @@
   @Override
   @SuppressWarnings("ReferenceEquality")
   protected InvokeType mapInvocationType(
-      DexMethod newMethod, DexMethod originalMethod, InvokeType type) {
+      DexMethod newMethod, DexMethod newReboundMethod, DexMethod originalMethod, InvokeType type) {
     if (typeMap.containsKey(originalMethod.getHolderType())) {
       // Methods moved from unboxed enums to the utility class are either static or statified.
       assert newMethod != originalMethod;

diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/MethodResolutionOptimizationInfoAnalysis.java b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodResolutionOptimizationInfoAnalysis.java
index 0dd4db5..7cd5d83 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/MethodResolutionOptimizationInfoAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodResolutionOptimizationInfoAnalysis.java

@@ -69,6 +69,7 @@
 
   private static class Traversal extends DepthFirstTopDownClassHierarchyTraversal {
 
+    private final AppView<AppInfoWithLiveness> appViewWithLiveness;
     private final MethodResolutionOptimizationInfoCollection.Builder builder;
     private final Map<DexProgramClass, TraversalState> states = new IdentityHashMap<>();
 
@@ -77,6 +78,7 @@
         MethodResolutionOptimizationInfoCollection.Builder builder,
         ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
       super(appView, immediateSubtypingInfo);
+      this.appViewWithLiveness = appView;
       this.builder = builder;
     }
 
@@ -145,7 +147,7 @@
                 states
                     .getOrDefault(subClass, UpwardsTraversalState.empty())
                     .asUpwardsTraversalState();
-            newState.join(appView, subClassState);
+            newState.join(appViewWithLiveness, subClassState);
 
             // If the current class is an interface and the current subclass is not, then we need
             // special handling to account for the fact that invoke-interface instructions may
@@ -156,26 +158,30 @@
             }
           });
       ObjectAllocationInfoCollection objectAllocationInfoCollection =
-          appView.appInfo().getObjectAllocationInfoCollection();
+          appViewWithLiveness.appInfo().getObjectAllocationInfoCollection();
       if (objectAllocationInfoCollection.isImmediateInterfaceOfInstantiatedLambda(clazz)) {
         for (DexEncodedMethod method : clazz.virtualMethods()) {
           newState.joinMethodOptimizationInfo(
-              appView, method.getSignature(), DefaultMethodOptimizationInfo.getInstance());
+              appViewWithLiveness,
+              method.getSignature(),
+              DefaultMethodOptimizationInfo.getInstance());
         }
       } else {
         for (DexEncodedMethod method : clazz.virtualMethods()) {
-          KeepMethodInfo keepInfo = appView.getKeepInfo().getMethodInfo(method, clazz);
-          if (!keepInfo.isShrinkingAllowed(appView.options())) {
+          KeepMethodInfo keepInfo = appViewWithLiveness.getKeepInfo().getMethodInfo(method, clazz);
+          if (!keepInfo.isShrinkingAllowed(appViewWithLiveness.options())) {
             // Method is kept and could be overridden outside app (e.g., in tests). Verify we don't
             // have any optimization info recorded for non-abstract methods.
             assert method.isAbstract()
                 || method.getOptimizationInfo().isDefault()
                 || method.getOptimizationInfo().returnValueHasBeenPropagated();
             newState.joinMethodOptimizationInfo(
-                appView, method.getSignature(), DefaultMethodOptimizationInfo.getInstance());
+                appViewWithLiveness,
+                method.getSignature(),
+                DefaultMethodOptimizationInfo.getInstance());
           } else if (!method.isAbstract()) {
             newState.joinMethodOptimizationInfo(
-                appView, method.getSignature(), method.getOptimizationInfo());
+                appViewWithLiveness, method.getSignature(), method.getOptimizationInfo());
           }
         }
       }
@@ -214,7 +220,7 @@
 
       for (DexMethodSignature method : interfaceMethodsInClassOrAbove) {
         MethodResolutionResult resolutionResult =
-            appView.appInfo().resolveMethodOnClass(subClass, method);
+            appViewWithLiveness.appInfo().resolveMethodOnClass(subClass, method);
         if (resolutionResult.isFailedResolution()) {
           assert resolutionResult.asFailedResolution().hasMethodsCausingError();
           continue;
@@ -223,7 +229,7 @@
         if (resolutionResult.isMultiMethodResolutionResult()) {
           // Conservatively drop the current optimization info.
           newState.joinMethodOptimizationInfo(
-              appView, method, DefaultMethodOptimizationInfo.getInstance());
+              appViewWithLiveness, method, DefaultMethodOptimizationInfo.getInstance());
           continue;
         }
 
@@ -231,7 +237,7 @@
         DexClassAndMethod resolvedMethod = resolutionResult.getResolutionPair();
         if (!resolvedMethod.getHolder().isInterface() && resolvedMethod.getHolder() != subClass) {
           newState.joinMethodOptimizationInfo(
-              appView, method, resolvedMethod.getOptimizationInfo());
+              appViewWithLiveness, method, resolvedMethod.getOptimizationInfo());
         }
       }
     }

diff --git a/src/main/java/com/android/tools/r8/lightir/LirLensCodeRewriter.java b/src/main/java/com/android/tools/r8/lightir/LirLensCodeRewriter.java
index b5ab4d1..0b52815 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirLensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirLensCodeRewriter.java

@@ -21,6 +21,7 @@
 import com.android.tools.r8.graph.lens.FieldLookupResult;
 import com.android.tools.r8.graph.lens.GraphLens;
 import com.android.tools.r8.graph.lens.MethodLookupResult;
+import com.android.tools.r8.graph.lens.NonIdentityGraphLens;
 import com.android.tools.r8.graph.proto.RewrittenPrototypeDescription;
 import com.android.tools.r8.horizontalclassmerging.HorizontalClassMergerGraphLens;
 import com.android.tools.r8.ir.code.IRCode;
@@ -54,6 +55,8 @@
   private final GraphLens codeLens;
   private final LensCodeRewriterUtils helper;
 
+  private final boolean isNonStartupInStartupOutlinerLens;
+
   private int numberOfInvokeOpcodeChanges = 0;
   private Map<LirConstant, LirConstant> constantPoolMapping = null;
 
@@ -71,6 +74,15 @@
     this.graphLens = appView.graphLens();
     this.codeLens = context.getDefinition().getCode().getCodeLens(appView);
     this.helper = helper;
+    NonIdentityGraphLens nonStartupInStartupOutlinerLens =
+        graphLens.isNonIdentityLens()
+            ? graphLens
+                .asNonIdentityLens()
+                .find(l -> l.isNonStartupInStartupOutlinerLens() || l == codeLens)
+            : null;
+    this.isNonStartupInStartupOutlinerLens =
+        nonStartupInStartupOutlinerLens != null
+            && nonStartupInStartupOutlinerLens.isNonStartupInStartupOutlinerLens();
   }
 
   @Override
@@ -120,13 +132,14 @@
     InvokeType newType = result.getType();
     boolean newIsInterface = lookupIsInterface(method, opcode, result);
     int newOpcode = newType.getLirOpcode(newIsInterface);
-    assert newMethod.getArity() == method.getArity();
+    assert newMethod.getArity() == method.getArity() || newType.isStatic();
     if (newOpcode != opcode) {
       assert type == newType
-              || (type.isDirect() && (newType.isInterface() || newType.isVirtual()))
-              || (type.isInterface() && newType.isVirtual())
-              || (type.isSuper() && newType.isVirtual())
-              || (type.isVirtual() && newType.isInterface())
+              || (type.isDirect()
+                  && (newType.isInterface() || newType.isStatic() || newType.isVirtual()))
+              || (type.isInterface() && (newType.isStatic() || newType.isVirtual()))
+              || (type.isSuper() && (newType.isStatic() || newType.isVirtual()))
+              || (type.isVirtual() && (newType.isInterface() || newType.isStatic()))
           : type + " -> " + newType;
       numberOfInvokeOpcodeChanges++;
     } else {
@@ -281,6 +294,20 @@
     if (opcode == LirOpcodes.INVOKEINTERFACE) {
       return InvokeType.INTERFACE;
     }
+    if (isNonStartupInStartupOutlinerLens) {
+      if (LirOpcodeUtils.isInvokeDirect(opcode)) {
+        return InvokeType.DIRECT;
+      }
+      if (LirOpcodeUtils.isInvokeInterface(opcode)) {
+        return InvokeType.INTERFACE;
+      }
+      if (LirOpcodeUtils.isInvokeSuper(opcode)) {
+        return InvokeType.SUPER;
+      }
+      if (LirOpcodeUtils.isInvokeVirtual(opcode)) {
+        return InvokeType.VIRTUAL;
+      }
+    }
     if (graphLens.isVerticalClassMergerLens()) {
       if (opcode == LirOpcodes.INVOKESTATIC_ITF) {
         return InvokeType.STATIC;

diff --git a/src/main/java/com/android/tools/r8/lightir/LirOpcodeUtils.java b/src/main/java/com/android/tools/r8/lightir/LirOpcodeUtils.java
index 7b110eb..d9efe9b 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirOpcodeUtils.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirOpcodeUtils.java

@@ -54,6 +54,14 @@
     }
   }
 
+  public static boolean isInvokeDirect(int opcode) {
+    return opcode == INVOKEDIRECT || opcode == INVOKEDIRECT_ITF;
+  }
+
+  public static boolean isInvokeInterface(int opcode) {
+    return opcode == INVOKEINTERFACE;
+  }
+
   public static boolean isInvokeMethod(int opcode) {
     switch (opcode) {
       case INVOKEDIRECT:
@@ -69,4 +77,12 @@
         return false;
     }
   }
+
+  public static boolean isInvokeSuper(int opcode) {
+    return opcode == INVOKESUPER || opcode == INVOKESUPER_ITF;
+  }
+
+  public static boolean isInvokeVirtual(int opcode) {
+    return opcode == INVOKEVIRTUAL;
+  }
 }

diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorGraphLens.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorGraphLens.java
index a5a4a61..87a811b 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorGraphLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/ArgumentPropagatorGraphLens.java

@@ -89,13 +89,13 @@
 
   @Override
   protected InvokeType mapInvocationType(
-      DexMethod newMethod, DexMethod originalMethod, InvokeType type) {
-    return hasPrototypeChanges(newMethod)
-            && getPrototypeChanges(newMethod)
+      DexMethod newMethod, DexMethod newReboundMethod, DexMethod originalMethod, InvokeType type) {
+    return hasPrototypeChanges(newReboundMethod)
+            && getPrototypeChanges(newReboundMethod)
                 .getArgumentInfoCollection()
                 .isConvertedToStaticMethod()
         ? InvokeType.STATIC
-        : super.mapInvocationType(newMethod, originalMethod, type);
+        : super.mapInvocationType(newMethod, newReboundMethod, originalMethod, type);
   }
 
   public static class Builder {

diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java
index c380eab..28d6b5c 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/codescanner/VirtualRootMethodsAnalysisBase.java

@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize.argumentpropagation.codescanner;
 
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexMethod;
@@ -10,7 +11,6 @@
 import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.optimize.argumentpropagation.utils.DepthFirstTopDownClassHierarchyTraversal;
-import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.collections.DexMethodSignatureMap;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.Sets;
@@ -140,7 +140,8 @@
   protected final Map<DexMethod, DexMethod> virtualRootMethods = new IdentityHashMap<>();
 
   protected VirtualRootMethodsAnalysisBase(
-      AppView<AppInfoWithLiveness> appView, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
     super(appView, immediateSubtypingInfo);
   }
 

diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
index 22b1a0e..c882a7c 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/InterfaceMethodArgumentPropagator.java

@@ -43,6 +43,7 @@
 
   // Contains the argument information for each interface method (including inherited interface
   // methods) on the seen but not finished interfaces.
+  final AppView<AppInfoWithLiveness> appViewWithLiveness;
   final Map<DexProgramClass, MethodStateCollectionBySignature> methodStatesToPropagate =
       new IdentityHashMap<>();
   final Consumer<DexMethodSignature> interfaceDispatchOutsideProgram;
@@ -53,6 +54,7 @@
       MethodStateCollectionByReference methodStates,
       Consumer<DexMethodSignature> interfaceDispatchOutsideProgram) {
     super(appView, immediateSubtypingInfo, methodStates);
+    this.appViewWithLiveness = appView;
     this.interfaceDispatchOutsideProgram = interfaceDispatchOutsideProgram;
   }
 
@@ -98,7 +100,7 @@
           MethodStateCollectionBySignature implementedInterfaceState =
               methodStatesToPropagate.get(superclass);
           assert implementedInterfaceState != null;
-          interfaceState.addMethodStates(appView, implementedInterfaceState);
+          interfaceState.addMethodStates(appViewWithLiveness, implementedInterfaceState);
         });
 
     // Add any argument information for virtual methods on the current interface to the state.
@@ -116,7 +118,7 @@
           }
 
           assert methodState.isUnknown() || methodState.asConcrete().isPolymorphic();
-          interfaceState.addMethodState(appView, method, methodState);
+          interfaceState.addMethodState(appViewWithLiveness, method, methodState);
         });
 
     methodStatesToPropagate.put(interfaceDefinition, interfaceState);
@@ -134,7 +136,9 @@
             interfaceState.forEach(
                 (interfaceMethod, interfaceMethodState) -> {
                   MethodResolutionResult resolutionResult =
-                      appView.appInfo().resolveMethodOnClassLegacy(subclass, interfaceMethod);
+                      appViewWithLiveness
+                          .appInfo()
+                          .resolveMethodOnClassLegacy(subclass, interfaceMethod);
                   if (resolutionResult.isFailedResolution()) {
                     // TODO(b/190154391): Do we need to propagate argument information to the first
                     //  virtual method above the inaccessible method in the class hierarchy?
@@ -155,10 +159,14 @@
 
                   MethodState transformedInterfaceMethodState =
                       transformInterfaceMethodStateForClassMethod(
-                          appView, subclass, resolvedMethod, interfaceMethodState, methodStates);
+                          appViewWithLiveness,
+                          subclass,
+                          resolvedMethod,
+                          interfaceMethodState,
+                          methodStates);
                   if (!transformedInterfaceMethodState.isBottom()) {
                     methodStates.addMethodState(
-                        appView, resolvedMethod, transformedInterfaceMethodState);
+                        appViewWithLiveness, resolvedMethod, transformedInterfaceMethodState);
                   }
                 }));
   }

diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
index e14addb..14eb036 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/propagation/VirtualDispatchMethodArgumentPropagator.java

@@ -70,14 +70,14 @@
       assert parentState != null;
 
       // Add the argument information that must be propagated to all method overrides.
-      active.addMethodStates(appView, parentState.active);
+      active.addMethodStates(appViewWithLiveness, parentState.active);
 
       // Add the argument information that is active until a given lower bound.
       parentState.activeUntilLowerBound.forEach(
           (lowerBound, activeMethodState) -> {
-            TypeElement lowerBoundType = lowerBound.toTypeElement(appView);
-            TypeElement currentType = clazz.getType().toTypeElement(appView);
-            if (lowerBoundType.lessThanOrEqual(currentType, appView)) {
+            TypeElement lowerBoundType = lowerBound.toTypeElement(appViewWithLiveness);
+            TypeElement currentType = clazz.getType().toTypeElement(appViewWithLiveness);
+            if (lowerBoundType.lessThanOrEqual(currentType, appViewWithLiveness)) {
               addActiveUntilLowerBound(lowerBound, activeMethodState);
             } else {
               // No longer active.
@@ -109,21 +109,22 @@
               // interface method is not applied. The information is propagated to the class
               // method that implements the interface method below.
               ClassTypeElement lowerBound = bounds.getDynamicLowerBoundType();
-              TypeElement currentType = clazz.getType().toTypeElement(appView);
-              if (lowerBound.lessThanOrEqual(currentType, appView)) {
-                DexType activeUntilLowerBoundType = lowerBound.toDexType(appView.dexItemFactory());
+              TypeElement currentType = clazz.getType().toTypeElement(appViewWithLiveness);
+              if (lowerBound.lessThanOrEqual(currentType, appViewWithLiveness)) {
+                DexType activeUntilLowerBoundType =
+                    lowerBound.toDexType(appViewWithLiveness.dexItemFactory());
                 addActiveUntilLowerBound(activeUntilLowerBoundType, inactiveMethodStates);
               } else {
                 return;
               }
             } else {
-              active.addMethodStates(appView, inactiveMethodStates);
+              active.addMethodStates(appViewWithLiveness, inactiveMethodStates);
             }
 
             inactiveMethodStates.forEach(
                 (signature, methodState) -> {
                   SingleResolutionResult<?> resolutionResult =
-                      appView
+                      appViewWithLiveness
                           .appInfo()
                           .resolveMethodOnLegacy(clazz, signature)
                           .asSingleResolution();
@@ -132,7 +133,7 @@
                   while (resolutionResult != null
                       && resolutionResult.getResolvedMethod().belongsToDirectPool()) {
                     resolutionResult =
-                        appView
+                        appViewWithLiveness
                             .appInfo()
                             .resolveMethodOnClassLegacy(
                                 resolutionResult.getResolvedHolder().getSuperType(), signature)
@@ -160,28 +161,28 @@
         DexType lowerBound, ProgramMethod method, MethodState methodState) {
       activeUntilLowerBound
           .computeIfAbsent(lowerBound, ignoreKey(MethodStateCollectionBySignature::create))
-          .addMethodState(appView, method, methodState);
+          .addMethodState(appViewWithLiveness, method, methodState);
     }
 
     private void addActiveUntilLowerBound(
         DexType lowerBound, MethodStateCollectionBySignature methodStates) {
       activeUntilLowerBound
           .computeIfAbsent(lowerBound, ignoreKey(MethodStateCollectionBySignature::create))
-          .addMethodStates(appView, methodStates);
+          .addMethodStates(appViewWithLiveness, methodStates);
     }
 
     private void addInactiveUntilUpperBound(
         DynamicTypeWithUpperBound upperBound, ProgramMethod method, MethodState methodState) {
       inactiveUntilUpperBound
           .computeIfAbsent(upperBound, ignoreKey(MethodStateCollectionBySignature::create))
-          .addMethodState(appView, method, methodState);
+          .addMethodState(appViewWithLiveness, method, methodState);
     }
 
     private void addInactiveUntilUpperBound(
         DynamicTypeWithUpperBound upperBound, MethodStateCollectionBySignature methodStates) {
       inactiveUntilUpperBound
           .computeIfAbsent(upperBound, ignoreKey(MethodStateCollectionBySignature::create))
-          .addMethodStates(appView, methodStates);
+          .addMethodStates(appViewWithLiveness, methodStates);
     }
 
     private MethodState computeMethodStateForPolymorphicMethod(ProgramMethod method) {
@@ -192,7 +193,10 @@
         for (MethodStateCollectionBySignature methodStates : activeUntilLowerBound.values()) {
           methodState =
               methodState.mutableJoin(
-                  appView, methodSignature, methodStates.get(method), StateCloner.getCloner());
+                  appViewWithLiveness,
+                  methodSignature,
+                  methodStates.get(method),
+                  StateCloner.getCloner());
         }
       }
       if (methodState.isMonomorphic()) {
@@ -226,8 +230,9 @@
           dynamicType.asDynamicTypeWithUpperBound();
       TypeElement dynamicUpperBoundType = dynamicTypeWithUpperBound.getDynamicUpperBoundType();
       TypeElement staticUpperBoundType =
-          method.getHolderType().toTypeElement(appView, definitelyNotNull());
-      if (dynamicUpperBoundType.lessThanOrEqualUpToNullability(staticUpperBoundType, appView)) {
+          method.getHolderType().toTypeElement(appViewWithLiveness, definitelyNotNull());
+      if (dynamicUpperBoundType.lessThanOrEqualUpToNullability(
+          staticUpperBoundType, appViewWithLiveness)) {
         DynamicType newDynamicType = dynamicType.withNullability(definitelyNotNull());
         assert newDynamicType.equals(dynamicType)
             || !dynamicType.getNullability().isDefinitelyNotNull();
@@ -237,25 +242,27 @@
       if (dynamicLowerBoundType == null) {
         return DynamicType.definitelyNotNull();
       }
-      assert dynamicLowerBoundType.lessThanOrEqualUpToNullability(staticUpperBoundType, appView);
+      assert dynamicLowerBoundType.lessThanOrEqualUpToNullability(
+          staticUpperBoundType, appViewWithLiveness);
       if (dynamicLowerBoundType.equalUpToNullability(staticUpperBoundType)) {
         return DynamicType.createExact(dynamicLowerBoundType.asDefinitelyNotNull());
       }
       return DynamicType.create(
-          appView, staticUpperBoundType, dynamicLowerBoundType.asDefinitelyNotNull());
+          appViewWithLiveness, staticUpperBoundType, dynamicLowerBoundType.asDefinitelyNotNull());
     }
 
     @SuppressWarnings("ReferenceEquality")
     private boolean shouldActivateMethodStateGuardedByBounds(
         ClassTypeElement upperBound, DexProgramClass currentClass, DexProgramClass superClass) {
       ClassTypeElement classType =
-          TypeElement.fromDexType(currentClass.getType(), maybeNull(), appView).asClassType();
+          TypeElement.fromDexType(currentClass.getType(), maybeNull(), appViewWithLiveness)
+              .asClassType();
       // When propagating argument information for interface methods downwards from an interface to
       // a non-interface we need to account for the parent classes of the current class.
       if (superClass.isInterface()
           && !currentClass.isInterface()
-          && currentClass.getSuperType() != appView.dexItemFactory().objectType) {
-        return classType.lessThanOrEqualUpToNullability(upperBound, appView);
+          && currentClass.getSuperType() != appViewWithLiveness.dexItemFactory().objectType) {
+        return classType.lessThanOrEqualUpToNullability(upperBound, appViewWithLiveness);
       }
       // If the upper bound does not have any interfaces we simply activate the method state when
       // meeting the upper bound class type in the downwards traversal over the class hierarchy.
@@ -264,19 +271,21 @@
       }
       // If the upper bound has interfaces, we check if the current class is a subtype of *both* the
       // upper bound class type and the upper bound interface types.
-      return classType.lessThanOrEqualUpToNullability(upperBound, appView);
+      return classType.lessThanOrEqualUpToNullability(upperBound, appViewWithLiveness);
     }
 
     boolean verifyActiveUntilLowerBoundRelevance(DexProgramClass clazz) {
-      TypeElement currentType = clazz.getType().toTypeElement(appView);
+      TypeElement currentType = clazz.getType().toTypeElement(appViewWithLiveness);
       for (DexType lowerBound : activeUntilLowerBound.keySet()) {
-        TypeElement lowerBoundType = lowerBound.toTypeElement(appView);
-        assert lowerBoundType.lessThanOrEqual(currentType, appView);
+        TypeElement lowerBoundType = lowerBound.toTypeElement(appViewWithLiveness);
+        assert lowerBoundType.lessThanOrEqual(currentType, appViewWithLiveness);
       }
       return true;
     }
   }
 
+  final AppView<AppInfoWithLiveness> appViewWithLiveness;
+
   // For each class, stores the argument information for each virtual method on this class and all
   // direct and indirect super classes.
   //
@@ -290,6 +299,7 @@
       ImmediateProgramSubtypingInfo immediateSubtypingInfo,
       MethodStateCollectionByReference methodStates) {
     super(appView, immediateSubtypingInfo, methodStates);
+    this.appViewWithLiveness = appView;
   }
 
   @Override
@@ -336,7 +346,8 @@
           polymorphicMethodState.forEach(
               (bounds, methodStateForBounds) -> {
                 if (bounds.isUnknown()) {
-                  propagationState.active.addMethodState(appView, method, methodStateForBounds);
+                  propagationState.active.addMethodState(
+                      appViewWithLiveness, method, methodStateForBounds);
                 } else {
                   // TODO(b/190154391): Verify that the bounds are not trivial according to the
                   //  static receiver type.
@@ -347,19 +358,20 @@
                       //  class.
                       ClassTypeElement lowerBound = bounds.getDynamicLowerBoundType();
                       DexType activeUntilLowerBoundType =
-                          lowerBound.toDexType(appView.dexItemFactory());
+                          lowerBound.toDexType(appViewWithLiveness.dexItemFactory());
                       assert !bounds.isExactClassType()
                           || activeUntilLowerBoundType.isIdenticalTo(clazz.getType());
                       propagationState.addActiveUntilLowerBound(
                           activeUntilLowerBoundType, method, methodStateForBounds);
                     } else {
-                      propagationState.active.addMethodState(appView, method, methodStateForBounds);
+                      propagationState.active.addMethodState(
+                          appViewWithLiveness, method, methodStateForBounds);
                     }
                   } else {
                     assert !clazz
                         .getType()
-                        .toTypeElement(appView)
-                        .lessThanOrEqualUpToNullability(upperBound, appView);
+                        .toTypeElement(appViewWithLiveness)
+                        .lessThanOrEqualUpToNullability(upperBound, appViewWithLiveness);
                     propagationState.addInactiveUntilUpperBound(
                         bounds, method, methodStateForBounds);
                   }
@@ -372,8 +384,9 @@
   }
 
   private boolean isUpperBoundSatisfied(ClassTypeElement upperBound, DexProgramClass currentClass) {
-    DexType upperBoundType = upperBound.toDexType(appView.dexItemFactory());
-    DexProgramClass upperBoundClass = asProgramClassOrNull(appView.definitionFor(upperBoundType));
+    DexType upperBoundType = upperBound.toDexType(appViewWithLiveness.dexItemFactory());
+    DexProgramClass upperBoundClass =
+        asProgramClassOrNull(appViewWithLiveness.definitionFor(upperBoundType));
     if (upperBoundClass == null) {
       // We should generally never have a dynamic receiver upper bound for a program method which is
       // not a program class. However, since the program may not type change or there could be

diff --git a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/DepthFirstTopDownClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/DepthFirstTopDownClassHierarchyTraversal.java
index a843a58..3585041 100644
--- a/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/DepthFirstTopDownClassHierarchyTraversal.java
+++ b/src/main/java/com/android/tools/r8/optimize/argumentpropagation/utils/DepthFirstTopDownClassHierarchyTraversal.java

@@ -6,11 +6,11 @@
 
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
-import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -34,7 +34,7 @@
     FINISHED
   }
 
-  protected final AppView<AppInfoWithLiveness> appView;
+  protected final AppView<? extends AppInfoWithClassHierarchy> appView;
   protected final ImmediateProgramSubtypingInfo immediateSubtypingInfo;
 
   // Contains the traversal state for each class. If a given class is not in the map the class is
@@ -53,7 +53,8 @@
   private final List<DexProgramClass> newlySeenButNotFinishedRoots = new ArrayList<>();
 
   public DepthFirstTopDownClassHierarchyTraversal(
-      AppView<AppInfoWithLiveness> appView, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
     this.appView = appView;
     this.immediateSubtypingInfo = immediateSubtypingInfo;
   }

diff --git a/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java b/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java
index 00588b5..fbbf49f 100644
--- a/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java
+++ b/src/main/java/com/android/tools/r8/optimize/redundantbridgeremoval/RedundantBridgeRemover.java

@@ -5,6 +5,7 @@
 
 import static com.android.tools.r8.graph.DexClassAndMethod.asProgramMethodOrNull;
 
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DefaultUseRegistry;
 import com.android.tools.r8.graph.DexClass;
@@ -387,7 +388,7 @@
       if (superTargets != null) {
         return superTargets;
       }
-      AppView<AppInfoWithLiveness> appViewWithLiveness = appView;
+      AppView<? extends AppInfoWithClassHierarchy> appViewWithClassHierarchy = appView;
       superTargets = ProgramMethodSet.create();
       WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList(root);
       while (worklist.hasNext()) {
@@ -402,9 +403,10 @@
                       public void registerInvokeSuper(DexMethod method) {
                         ProgramMethod superTarget =
                             asProgramMethodOrNull(
-                                appViewWithLiveness
+                                appViewWithClassHierarchy
                                     .appInfo()
-                                    .lookupSuperTarget(method, getContext(), appViewWithLiveness));
+                                    .lookupSuperTarget(
+                                        method, getContext(), appViewWithClassHierarchy));
                         if (superTarget != null) {
                           superTargets.add(superTarget);
                         }

diff --git a/src/main/java/com/android/tools/r8/optimize/singlecaller/MonomorphicVirtualMethodsAnalysis.java b/src/main/java/com/android/tools/r8/optimize/singlecaller/MonomorphicVirtualMethodsAnalysis.java
index 8d589a8..77d3764 100644
--- a/src/main/java/com/android/tools/r8/optimize/singlecaller/MonomorphicVirtualMethodsAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/singlecaller/MonomorphicVirtualMethodsAnalysis.java

@@ -3,11 +3,11 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize.singlecaller;
 
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.ImmediateProgramSubtypingInfo;
 import com.android.tools.r8.optimize.argumentpropagation.codescanner.VirtualRootMethodsAnalysisBase;
-import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import java.util.List;
@@ -18,12 +18,13 @@
 public class MonomorphicVirtualMethodsAnalysis extends VirtualRootMethodsAnalysisBase {
 
   public MonomorphicVirtualMethodsAnalysis(
-      AppView<AppInfoWithLiveness> appView, ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
+      AppView<? extends AppInfoWithClassHierarchy> appView,
+      ImmediateProgramSubtypingInfo immediateSubtypingInfo) {
     super(appView, immediateSubtypingInfo);
   }
 
   public static ProgramMethodSet computeMonomorphicVirtualRootMethods(
-      AppView<AppInfoWithLiveness> appView,
+      AppView<? extends AppInfoWithClassHierarchy> appView,
       ImmediateProgramSubtypingInfo immediateSubtypingInfo,
       List<Set<DexProgramClass>> stronglyConnectedComponents,
       ExecutorService executorService)
@@ -43,7 +44,7 @@
   }
 
   private static ProgramMethodSet computeMonomorphicVirtualRootMethodsInComponent(
-      AppView<AppInfoWithLiveness> appView,
+      AppView<? extends AppInfoWithClassHierarchy> appView,
       ImmediateProgramSubtypingInfo immediateSubtypingInfo,
       Set<DexProgramClass> stronglyConnectedComponent) {
     MonomorphicVirtualMethodsAnalysis analysis =

diff --git a/src/main/java/com/android/tools/r8/optimize/singlecaller/SingleCallerInliner.java b/src/main/java/com/android/tools/r8/optimize/singlecaller/SingleCallerInliner.java
index 5645247..e16c128 100644
--- a/src/main/java/com/android/tools/r8/optimize/singlecaller/SingleCallerInliner.java
+++ b/src/main/java/com/android/tools/r8/optimize/singlecaller/SingleCallerInliner.java

@@ -6,6 +6,7 @@
 import static com.android.tools.r8.ir.optimize.info.OptimizationFeedback.getSimpleFeedback;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexMethod;
@@ -69,7 +70,7 @@
 
   public void run(ExecutorService executorService) throws ExecutionException {
     ProgramMethodSet monomorphicVirtualMethods =
-        computeMonomorphicVirtualRootMethods(executorService);
+        computeMonomorphicVirtualRootMethods(appView, executorService);
     ProgramMethodMap<ProgramMethod> singleCallerMethods =
         new SingleCallerScanner(appView, monomorphicVirtualMethods)
             .getSingleCallerMethods(executorService);
@@ -87,8 +88,8 @@
   // deal with (rooted) virtual methods that do not override abstract/interface methods. In order to
   // also deal with virtual methods that override abstract/interface methods we would need to record
   // calls to the abstract/interface methods as calls to the non-abstract virtual method.
-  @SuppressWarnings("UnusedMethod")
-  private ProgramMethodSet computeMonomorphicVirtualRootMethods(ExecutorService executorService)
+  public static ProgramMethodSet computeMonomorphicVirtualRootMethods(
+      AppView<? extends AppInfoWithClassHierarchy> appView, ExecutorService executorService)
       throws ExecutionException {
     ImmediateProgramSubtypingInfo immediateSubtypingInfo =
         ImmediateProgramSubtypingInfo.create(appView);

diff --git a/src/main/java/com/android/tools/r8/profile/AbstractProfile.java b/src/main/java/com/android/tools/r8/profile/AbstractProfile.java
index ff8c494..dd76864 100644
--- a/src/main/java/com/android/tools/r8/profile/AbstractProfile.java
+++ b/src/main/java/com/android/tools/r8/profile/AbstractProfile.java

@@ -4,12 +4,19 @@
 
 package com.android.tools.r8.profile;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.profile.AbstractProfile.Builder;
 import com.android.tools.r8.utils.ThrowingConsumer;
+import java.util.function.BiConsumer;
 
 public interface AbstractProfile<
-    ClassRule extends AbstractProfileClassRule, MethodRule extends AbstractProfileMethodRule> {
+    ClassRule extends AbstractProfileClassRule,
+    MethodRule extends AbstractProfileMethodRule,
+    Profile extends AbstractProfile<ClassRule, MethodRule, Profile, ProfileBuilder>,
+    ProfileBuilder extends Builder<ClassRule, MethodRule, Profile, ProfileBuilder>> {
 
   boolean containsClassRule(DexType type);
 
@@ -24,18 +31,60 @@
 
   MethodRule getMethodRule(DexMethod method);
 
+  ProfileBuilder toEmptyBuilderWithCapacity();
+
+  default Profile toProfileWithSuperclasses(AppView<?> appView) {
+    return transform(
+        (classRule, builder) -> builder.addClassAndParentClasses(classRule.getReference(), appView),
+        (methodRule, builder) -> {
+          builder.addClassAndParentClasses(methodRule.getReference().getHolderType(), appView);
+          builder.addMethodRule(methodRule);
+        });
+  }
+
+  default Profile transform(
+      BiConsumer<ClassRule, ProfileBuilder> classRuleTransformer,
+      BiConsumer<MethodRule, ProfileBuilder> methodRuleTransformer) {
+    ProfileBuilder builder = toEmptyBuilderWithCapacity();
+    forEachRule(
+        classRule -> classRuleTransformer.accept(classRule, builder),
+        methodRule -> methodRuleTransformer.accept(methodRule, builder));
+    return builder.build();
+  }
+
   interface Builder<
       ClassRule extends AbstractProfileClassRule,
       MethodRule extends AbstractProfileMethodRule,
-      Profile extends AbstractProfile<ClassRule, MethodRule>,
+      Profile extends AbstractProfile<ClassRule, MethodRule, Profile, ProfileBuilder>,
       ProfileBuilder extends Builder<ClassRule, MethodRule, Profile, ProfileBuilder>> {
 
     ProfileBuilder addRule(AbstractProfileRule rule);
 
     ProfileBuilder addClassRule(ClassRule classRule);
 
+    boolean addClassRule(DexType type);
+
+    default void addClassAndParentClasses(DexType type, AppView<?> appView) {
+      DexProgramClass definition = appView.app().programDefinitionFor(type);
+      if (definition != null) {
+        addClassAndParentClasses(definition, appView);
+      }
+    }
+
+    private void addClassAndParentClasses(DexProgramClass clazz, AppView<?> appView) {
+      if (addClassRule(clazz.getType())) {
+        addParentClasses(clazz, appView);
+      }
+    }
+
+    private void addParentClasses(DexProgramClass clazz, AppView<?> appView) {
+      clazz.forEachImmediateSupertype(supertype -> addClassAndParentClasses(supertype, appView));
+    }
+
     ProfileBuilder addMethodRule(MethodRule methodRule);
 
     Profile build();
+
+    int size();
   }
 }

diff --git a/src/main/java/com/android/tools/r8/profile/art/ArtProfile.java b/src/main/java/com/android/tools/r8/profile/art/ArtProfile.java
index f33323f..16058e4 100644
--- a/src/main/java/com/android/tools/r8/profile/art/ArtProfile.java
+++ b/src/main/java/com/android/tools/r8/profile/art/ArtProfile.java

@@ -4,8 +4,6 @@
 
 package com.android.tools.r8.profile.art;
 
-import static com.android.tools.r8.utils.MapUtils.ignoreKey;
-
 import com.android.tools.r8.TextInputStream;
 import com.android.tools.r8.TextOutputStream;
 import com.android.tools.r8.graph.AppInfo;
@@ -24,18 +22,17 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Reporter;
 import com.android.tools.r8.utils.ThrowingConsumer;
-import com.android.tools.r8.utils.TriConsumer;
 import java.io.IOException;
 import java.io.OutputStreamWriter;
 import java.io.UncheckedIOException;
 import java.util.Collection;
 import java.util.LinkedHashMap;
 import java.util.Map;
-import java.util.function.BiConsumer;
 import java.util.function.Consumer;
-import java.util.function.Function;
 
-public class ArtProfile implements AbstractProfile<ArtProfileClassRule, ArtProfileMethodRule> {
+public class ArtProfile
+    implements AbstractProfile<
+        ArtProfileClassRule, ArtProfileMethodRule, ArtProfile, ArtProfile.Builder> {
 
   private final Map<DexReference, ArtProfileRule> rules;
 
@@ -52,6 +49,15 @@
     return new Builder(artProfileProvider, options);
   }
 
+  public static Builder builderWithCapacity(int capacity) {
+    return new Builder(capacity);
+  }
+
+  @Override
+  public Builder toEmptyBuilderWithCapacity() {
+    return builderWithCapacity(rules.size());
+  }
+
   @Override
   public boolean containsClassRule(DexType type) {
     return rules.containsKey(type);
@@ -99,31 +105,33 @@
       return rewrittenWithLens(appView, lens.asEnumUnboxerLens());
     }
     return transform(
-        (classRule, classRuleBuilderFactory) -> {
+        (classRule, builder) -> {
           DexType newClassRule = lens.lookupType(classRule.getType());
           assert newClassRule.isClassType();
-          classRuleBuilderFactory.accept(newClassRule);
+          builder.addClassRule(ArtProfileClassRule.builder().setType(newClassRule).build());
         },
-        (methodRule, classRuleBuilderFactory, methodRuleBuilderFactory) ->
-            methodRuleBuilderFactory
-                .apply(lens.getRenamedMethodSignature(methodRule.getMethod()))
-                .acceptMethodRuleInfoBuilder(
-                    methodRuleInfoBuilder ->
-                        methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo())));
+        (methodRule, builder) ->
+            builder.addMethodRule(
+                ArtProfileMethodRule.builder()
+                    .setMethod(lens.getRenamedMethodSignature(methodRule.getMethod()))
+                    .acceptMethodRuleInfoBuilder(
+                        methodRuleInfoBuilder ->
+                            methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo()))
+                    .build()));
   }
 
   @SuppressWarnings("ReferenceEquality")
   public ArtProfile rewrittenWithLens(AppView<?> appView, EnumUnboxingLens lens) {
     return transform(
-        (classRule, classRuleBuilderFactory) -> {
+        (classRule, builder) -> {
           DexType newClassRule = lens.lookupType(classRule.getType());
           if (newClassRule.isClassType()) {
-            classRuleBuilderFactory.accept(newClassRule);
+            builder.addClassRule(ArtProfileClassRule.builder().setType(newClassRule).build());
           } else {
             assert newClassRule.isIntType();
           }
         },
-        (methodRule, classRuleBuilderFactory, methodRuleBuilderFactory) -> {
+        (methodRule, builder) -> {
           DexMethod newMethod = lens.getRenamedMethodSignature(methodRule.getMethod());
           // When moving non-synthetic methods from an enum class to its enum utility class we also
           // add a rule for the utility class.
@@ -132,47 +140,61 @@
                 .getSyntheticItems()
                 .isSyntheticOfKind(
                     newMethod.getHolderType(), naming -> naming.ENUM_UNBOXING_LOCAL_UTILITY_CLASS);
-            classRuleBuilderFactory.accept(newMethod.getHolderType());
+            builder.addClassRule(
+                ArtProfileClassRule.builder().setType(newMethod.getHolderType()).build());
           }
-          methodRuleBuilderFactory
-              .apply(newMethod)
-              .acceptMethodRuleInfoBuilder(
-                  methodRuleInfoBuilder ->
-                      methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo()));
+          builder.addMethodRule(
+              ArtProfileMethodRule.builder()
+                  .setMethod(newMethod)
+                  .acceptMethodRuleInfoBuilder(
+                      methodRuleInfoBuilder ->
+                          methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo()))
+                  .build());
         });
   }
 
   public ArtProfile rewrittenWithLens(AppView<?> appView, NamingLens lens) {
+    if (lens.isIdentityLens()) {
+      return this;
+    }
     DexItemFactory dexItemFactory = appView.dexItemFactory();
     assert !lens.isIdentityLens();
     return transform(
-        (classRule, classRuleBuilderFactory) ->
-            classRuleBuilderFactory.accept(lens.lookupType(classRule.getType(), dexItemFactory)),
-        (methodRule, classRuleBuilderFactory, methodRuleBuilderFactory) ->
-            methodRuleBuilderFactory
-                .apply(lens.lookupMethod(methodRule.getMethod(), dexItemFactory))
-                .acceptMethodRuleInfoBuilder(
-                    methodRuleInfoBuilder ->
-                        methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo())));
+        (classRule, builder) ->
+            builder.addClassRule(
+                ArtProfileClassRule.builder()
+                    .setType(lens.lookupType(classRule.getType(), dexItemFactory))
+                    .build()),
+        (methodRule, builder) ->
+            builder.addMethodRule(
+                ArtProfileMethodRule.builder()
+                    .setMethod(lens.lookupMethod(methodRule.getMethod(), dexItemFactory))
+                    .acceptMethodRuleInfoBuilder(
+                        methodRuleInfoBuilder ->
+                            methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo()))
+                    .build()));
   }
 
   public ArtProfile withoutMissingItems(AppView<?> appView) {
     AppInfo appInfo = appView.appInfo();
     return transform(
-        (classRule, classRuleBuilderFactory) -> {
+        (classRule, builder) -> {
           if (appInfo.hasDefinitionForWithoutExistenceAssert(classRule.getType())) {
-            classRuleBuilderFactory.accept(classRule.getType());
+            builder.addClassRule(
+                ArtProfileClassRule.builder().setType(classRule.getType()).build());
           }
         },
-        (methodRule, classRuleBuilderFactory, methodRuleBuilderFactory) -> {
+        (methodRule, builder) -> {
           DexClass clazz =
               appInfo.definitionForWithoutExistenceAssert(methodRule.getMethod().getHolderType());
           if (methodRule.getMethod().isDefinedOnClass(clazz)) {
-            methodRuleBuilderFactory
-                .apply(methodRule.getMethod())
-                .acceptMethodRuleInfoBuilder(
-                    methodRuleInfoBuilder ->
-                        methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo()));
+            builder.addMethodRule(
+                ArtProfileMethodRule.builder()
+                    .setMethod(methodRule.getMethod())
+                    .acceptMethodRuleInfoBuilder(
+                        methodRuleInfoBuilder ->
+                            methodRuleInfoBuilder.merge(methodRule.getMethodRuleInfo()))
+                    .build());
           }
         });
   }
@@ -182,40 +204,6 @@
     return this;
   }
 
-  private ArtProfile transform(
-      BiConsumer<ArtProfileClassRule, Consumer<DexType>> classTransformation,
-      TriConsumer<
-              ArtProfileMethodRule,
-              Consumer<DexType>,
-              Function<DexMethod, ArtProfileMethodRule.Builder>>
-          methodTransformation) {
-    Map<DexReference, ArtProfileRule.Builder> ruleBuilders = new LinkedHashMap<>();
-    Consumer<DexType> classRuleBuilderFactory =
-        newType ->
-            ruleBuilders
-                .computeIfAbsent(
-                    newType, ignoreKey(() -> ArtProfileClassRule.builder().setType(newType)))
-                .asClassRuleBuilder();
-    Function<DexMethod, ArtProfileMethodRule.Builder> methodRuleBuilderFactory =
-        newMethod ->
-            ruleBuilders
-                .computeIfAbsent(
-                    newMethod, ignoreKey(() -> ArtProfileMethodRule.builder().setMethod(newMethod)))
-                .asMethodRuleBuilder();
-    forEachRule(
-        // Supply a factory method for creating a builder. If the current rule should be included in
-        // the rewritten profile, the caller should call the provided builder factory method to
-        // create a class rule builder. If two rules are mapped to the same reference, the same rule
-        // builder is reused so that the two rules are merged into a single rule (with their flags
-        // merged).
-        classRule -> classTransformation.accept(classRule, classRuleBuilderFactory),
-        // As above.
-        methodRule ->
-            methodTransformation.accept(
-                methodRule, classRuleBuilderFactory, methodRuleBuilderFactory));
-    return builder().addRuleBuilders(ruleBuilders.values()).build();
-  }
-
   public void supplyConsumer(ArtProfileConsumer consumer, Reporter reporter) {
     if (consumer != null) {
       TextOutputStream textOutputStream = consumer.getHumanReadableArtProfileConsumer();
@@ -263,12 +251,21 @@
     private final ArtProfileProvider artProfileProvider;
     private final DexItemFactory dexItemFactory;
     private Reporter reporter;
-    private final Map<DexReference, ArtProfileRule> rules = new LinkedHashMap<>();
+    private final Map<DexReference, ArtProfileRule> rules;
 
     Builder() {
+      this(new LinkedHashMap<>());
+    }
+
+    Builder(Map<DexReference, ArtProfileRule> rules) {
       this.artProfileProvider = null;
       this.dexItemFactory = null;
       this.reporter = null;
+      this.rules = rules;
+    }
+
+    Builder(int capacity) {
+      this(new LinkedHashMap<>(capacity));
     }
 
     // Constructor for building the initial ART profile. The input is based on the Reference API, so
@@ -278,6 +275,7 @@
       this.artProfileProvider = artProfileProvider;
       this.dexItemFactory = options.dexItemFactory();
       this.reporter = options.reporter;
+      this.rules = new LinkedHashMap<>();
     }
 
     @Override
@@ -292,6 +290,13 @@
     }
 
     @Override
+    public boolean addClassRule(DexType type) {
+      int oldSize = size();
+      addClassRule(ArtProfileClassRule.builder().setType(type).build());
+      return size() > oldSize;
+    }
+
+    @Override
     public Builder addMethodRule(ArtProfileMethodRule methodRule) {
       rules.compute(
           methodRule.getReference(),
@@ -351,5 +356,10 @@
     public ArtProfile build() {
       return new ArtProfile(rules);
     }
+
+    @Override
+    public int size() {
+      return rules.size();
+    }
   }
 }

diff --git a/src/main/java/com/android/tools/r8/profile/art/ArtProfileMethodRule.java b/src/main/java/com/android/tools/r8/profile/art/ArtProfileMethodRule.java
index c0b377f..527734f 100644
--- a/src/main/java/com/android/tools/r8/profile/art/ArtProfileMethodRule.java
+++ b/src/main/java/com/android/tools/r8/profile/art/ArtProfileMethodRule.java

@@ -105,7 +105,7 @@
     private final DexItemFactory dexItemFactory;
 
     private DexMethod method;
-    private ArtProfileMethodRuleInfoImpl.Builder methodRuleInfoBuilder =
+    private final ArtProfileMethodRuleInfoImpl.Builder methodRuleInfoBuilder =
         ArtProfileMethodRuleInfoImpl.builder();
 
     Builder() {

diff --git a/src/main/java/com/android/tools/r8/profile/art/NonEmptyArtProfileCollection.java b/src/main/java/com/android/tools/r8/profile/art/NonEmptyArtProfileCollection.java
index c98371b..926bab4 100644
--- a/src/main/java/com/android/tools/r8/profile/art/NonEmptyArtProfileCollection.java
+++ b/src/main/java/com/android/tools/r8/profile/art/NonEmptyArtProfileCollection.java

@@ -81,19 +81,18 @@
         return;
       }
     }
-    NonEmptyArtProfileCollection collection =
-        appView.getNamingLens().isIdentityLens()
-            ? this
-            : rewrittenWithLens(appView, appView.getNamingLens());
     InternalOptions options = appView.options();
     Collection<ArtProfileForRewriting> inputs =
         options.getArtProfileOptions().getArtProfilesForRewriting();
     assert !inputs.isEmpty();
-    assert collection.artProfiles.size() == inputs.size();
+    assert artProfiles.size() == inputs.size();
     Iterator<ArtProfileForRewriting> inputIterator = inputs.iterator();
-    for (ArtProfile artProfile : collection.artProfiles) {
+    for (ArtProfile artProfile : artProfiles) {
       ArtProfileForRewriting input = inputIterator.next();
-      artProfile.supplyConsumer(input.getResidualArtProfileConsumer(), options.reporter);
+      artProfile
+          .toProfileWithSuperclasses(appView)
+          .rewrittenWithLens(appView, appView.getNamingLens())
+          .supplyConsumer(input.getResidualArtProfileConsumer(), options.reporter);
     }
   }
 

diff --git a/src/main/java/com/android/tools/r8/profile/rewriting/ProfileAdditions.java b/src/main/java/com/android/tools/r8/profile/rewriting/ProfileAdditions.java
index 877df9a..0269114 100644
--- a/src/main/java/com/android/tools/r8/profile/rewriting/ProfileAdditions.java
+++ b/src/main/java/com/android/tools/r8/profile/rewriting/ProfileAdditions.java

@@ -47,7 +47,7 @@
     MethodRule extends AbstractProfileMethodRule,
     MethodRuleBuilder extends AbstractProfileMethodRule.Builder<MethodRule, MethodRuleBuilder>,
     ProfileRule extends AbstractProfileRule,
-    Profile extends AbstractProfile<ClassRule, MethodRule>,
+    Profile extends AbstractProfile<ClassRule, MethodRule, Profile, ProfileBuilder>,
     ProfileBuilder extends
         AbstractProfile.Builder<ClassRule, MethodRule, Profile, ProfileBuilder>> {
 

diff --git a/src/main/java/com/android/tools/r8/profile/startup/StartupOptions.java b/src/main/java/com/android/tools/r8/profile/startup/StartupOptions.java
index e6406bc..62ee585 100644
--- a/src/main/java/com/android/tools/r8/profile/startup/StartupOptions.java
+++ b/src/main/java/com/android/tools/r8/profile/startup/StartupOptions.java

@@ -17,6 +17,14 @@
 public class StartupOptions {
 
   /**
+   * When enabled, attempts to move or outline all non-startup methods on startup classes.
+   *
+   * <p>Currently only supported in R8.
+   */
+  private boolean enableOutlining =
+      parseSystemPropertyOrDefault("com.android.tools.r8.startup.outline", false);
+
+  /**
    * When enabled, all startup classes will be placed in the primary classes.dex file. All other
    * (non-startup) classes will be placed in classes2.dex, ..., classesN.dex.
    */
@@ -68,6 +76,10 @@
             Collections::emptyList);
   }
 
+  public boolean isOutliningEnabled() {
+    return enableOutlining;
+  }
+
   public boolean isMinimalStartupDexEnabled() {
     return enableMinimalStartupDex;
   }
@@ -99,6 +111,11 @@
     return enableStartupLayoutOptimization;
   }
 
+  public StartupOptions setEnableOutlining(boolean enableOutlining) {
+    this.enableOutlining = enableOutlining;
+    return this;
+  }
+
   public StartupOptions setEnableStartupCompletenessCheckForTesting() {
     return setEnableStartupCompletenessCheckForTesting(true);
   }

diff --git a/src/main/java/com/android/tools/r8/profile/startup/profile/EmptyStartupProfile.java b/src/main/java/com/android/tools/r8/profile/startup/profile/EmptyStartupProfile.java
index a051dc9..666338a 100644
--- a/src/main/java/com/android/tools/r8/profile/startup/profile/EmptyStartupProfile.java
+++ b/src/main/java/com/android/tools/r8/profile/startup/profile/EmptyStartupProfile.java

@@ -66,6 +66,11 @@
   }
 
   @Override
+  public Builder toEmptyBuilderWithCapacity() {
+    return builder();
+  }
+
+  @Override
   public EmptyStartupProfile toStartupProfileForWriting(AppView<?> appView) {
     return this;
   }

diff --git a/src/main/java/com/android/tools/r8/profile/startup/profile/NonEmptyStartupProfile.java b/src/main/java/com/android/tools/r8/profile/startup/profile/NonEmptyStartupProfile.java
index 5ccba97..f675a24 100644
--- a/src/main/java/com/android/tools/r8/profile/startup/profile/NonEmptyStartupProfile.java
+++ b/src/main/java/com/android/tools/r8/profile/startup/profile/NonEmptyStartupProfile.java

@@ -8,7 +8,6 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.PrunedItems;
@@ -21,7 +20,6 @@
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.Set;
-import java.util.function.BiConsumer;
 
 public class NonEmptyStartupProfile extends StartupProfile {
 
@@ -105,6 +103,11 @@
     return startupRules.size();
   }
 
+  @Override
+  public Builder toEmptyBuilderWithCapacity() {
+    return builderWithCapacity(size());
+  }
+
   /**
    * This is called to process the startup profile before computing the startup layouts.
    *
@@ -118,42 +121,7 @@
    */
   @Override
   public StartupProfile toStartupProfileForWriting(AppView<?> appView) {
-    return transform(
-        (classRule, builder) -> addStartupItem(classRule, builder, appView),
-        (methodRule, builder) -> addStartupItem(methodRule, builder, appView));
-  }
-
-  private static void addStartupItem(
-      StartupProfileRule startupItem, Builder builder, AppView<?> appView) {
-    startupItem.accept(
-        classRule -> addClassAndParentClasses(classRule.getReference(), builder, appView),
-        builder::addMethodRule);
-  }
-
-  private static boolean addClass(DexProgramClass clazz, Builder builder) {
-    int oldSize = builder.size();
-    builder.addClassRule(
-        StartupProfileClassRule.builder().setClassReference(clazz.getType()).build());
-    return builder.size() > oldSize;
-  }
-
-  private static void addClassAndParentClasses(DexType type, Builder builder, AppView<?> appView) {
-    DexProgramClass definition = appView.app().programDefinitionFor(type);
-    if (definition != null) {
-      addClassAndParentClasses(definition, builder, appView);
-    }
-  }
-
-  private static void addClassAndParentClasses(
-      DexProgramClass clazz, Builder builder, AppView<?> appView) {
-    if (addClass(clazz, builder)) {
-      addParentClasses(clazz, builder, appView);
-    }
-  }
-
-  private static void addParentClasses(DexProgramClass clazz, Builder builder, AppView<?> appView) {
-    clazz.forEachImmediateSupertype(
-        supertype -> addClassAndParentClasses(supertype, builder, appView));
+    return toProfileWithSuperclasses(appView);
   }
 
   @Override
@@ -194,14 +162,4 @@
     timing.end();
     return result;
   }
-
-  private StartupProfile transform(
-      BiConsumer<StartupProfileClassRule, Builder> classRuleTransformer,
-      BiConsumer<StartupProfileMethodRule, Builder> methodRuleTransformer) {
-    Builder builder = builderWithCapacity(startupRules.size());
-    forEachRule(
-        classRule -> classRuleTransformer.accept(classRule, builder),
-        methodRule -> methodRuleTransformer.accept(methodRule, builder));
-    return builder.build();
-  }
 }

diff --git a/src/main/java/com/android/tools/r8/profile/startup/profile/StartupProfile.java b/src/main/java/com/android/tools/r8/profile/startup/profile/StartupProfile.java
index 8ee1fd5..e6a4cb5 100644
--- a/src/main/java/com/android/tools/r8/profile/startup/profile/StartupProfile.java
+++ b/src/main/java/com/android/tools/r8/profile/startup/profile/StartupProfile.java

@@ -36,7 +36,8 @@
 import java.util.function.Function;
 
 public abstract class StartupProfile
-    implements AbstractProfile<StartupProfileClassRule, StartupProfileMethodRule> {
+    implements AbstractProfile<
+        StartupProfileClassRule, StartupProfileMethodRule, StartupProfile, StartupProfile.Builder> {
 
   protected StartupProfile() {}
 
@@ -195,6 +196,13 @@
     }
 
     @Override
+    public boolean addClassRule(DexType type) {
+      int oldSize = size();
+      addClassRule(StartupProfileClassRule.builder().setClassReference(type).build());
+      return size() > oldSize;
+    }
+
+    @Override
     public Builder addMethodRule(StartupProfileMethodRule methodRule) {
       return addStartupItem(methodRule);
     }
@@ -258,6 +266,7 @@
       return this;
     }
 
+    @Override
     public int size() {
       return startupItems.size();
     }

diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 530ec46..abee4a2 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java

@@ -3372,6 +3372,8 @@
       markFieldAsLive(field, context, reason);
     }
 
+    handleFieldAccessWithInaccessibleFieldType(field, context);
+
     if (liveFields.contains(field)
         || !reachableInstanceFields
             .computeIfAbsent(field.getHolder(), ignore -> ProgramFieldSet.create())
@@ -3386,6 +3388,21 @@
     analyses.forEach(analysis -> analysis.notifyMarkFieldAsReachable(field, worklist));
   }
 
+  private void handleFieldAccessWithInaccessibleFieldType(
+      ProgramField field, ProgramDefinition context) {
+    if (mode.isFinalTreeShaking() && options.isOptimizing() && !field.getAccessFlags().isStatic()) {
+      DexType fieldBaseType = field.getType().toBaseType(appView.dexItemFactory());
+      if (fieldBaseType.isClassType()) {
+        DexClass clazz = definitionFor(fieldBaseType, context);
+        if (clazz != null
+            && AccessControl.isClassAccessible(clazz, context, appView).isPossiblyFalse()) {
+          applyMinimumKeepInfoWhenLive(
+              field.getHolder(), KeepClassInfo.newEmptyJoiner().disallowHorizontalClassMerging());
+        }
+      }
+    }
+  }
+
   private void traceFieldDefinition(ProgramField field) {
     markTypeAsLive(field.getHolder(), field);
     markTypeAsLive(field.getType(), field);

diff --git a/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java b/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java
index e524b2a..990c260 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepInfoCollection.java

@@ -440,13 +440,16 @@
             assert !info.isPinned(options)
                 || info.isMinificationAllowed(options)
                 || newMethod.name.isIdenticalTo(method.name);
-            assert !info.isPinned(options) || newMethod.getArity() == method.getArity();
+            assert !info.isPinned(options)
+                || newMethod.getArity() == method.getArity()
+                || (info.isShrinkingAllowed(options) && lens.isNonStartupInStartupOutlinerLens());
             assert !info.isPinned(options)
                 || Streams.zip(
                         newMethod.getParameters().stream(),
                         method.getParameters().stream().map(lens::lookupType),
                         Object::equals)
-                    .allMatch(x -> x);
+                    .allMatch(x -> x)
+                || (info.isShrinkingAllowed(options) && lens.isNonStartupInStartupOutlinerLens());
             assert !info.isPinned(options)
                 || newMethod.getReturnType().isIdenticalTo(lens.lookupType(method.getReturnType()));
             KeepMethodInfo previous = newMethodInfo.put(newMethod, info);

diff --git a/src/main/java/com/android/tools/r8/shaking/KeepSpecificationSource.java b/src/main/java/com/android/tools/r8/shaking/KeepSpecificationSource.java
new file mode 100644
index 0000000..1dfda01
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/KeepSpecificationSource.java

@@ -0,0 +1,96 @@
+// Copyright (c) 2024, 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.shaking;
+
+import com.android.tools.r8.ResourceException;
+import com.android.tools.r8.keepanno.ast.KeepDeclaration;
+import com.android.tools.r8.keepanno.ast.KeepSpecVersion;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.Declaration;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.KeepSpec;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.origin.PathOrigin;
+import com.google.protobuf.InvalidProtocolBufferException;
+import java.io.IOException;
+import java.io.InputStream;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.function.Consumer;
+
+public abstract class KeepSpecificationSource {
+
+  public static KeepSpecificationSource fromFile(Path path) {
+    return new KeepSpecificationFile(path);
+  }
+
+  public static KeepSpecificationSource fromBytes(Origin origin, byte[] bytes) {
+    return new KeepSpecificationBytes(origin, bytes);
+  }
+
+  private final Origin origin;
+
+  private KeepSpecificationSource(Origin origin) {
+    this.origin = origin;
+  }
+
+  public Origin getOrigin() {
+    return origin;
+  }
+
+  public void parse(Consumer<KeepDeclaration> consumer) throws ResourceException {
+    KeepSpec spec = read();
+    KeepSpecVersion version = KeepSpecVersion.fromProto(spec.getVersion());
+    if (version == KeepSpecVersion.UNKNOWN) {
+      throw new ResourceException(getOrigin(), "Unknown keepspec version " + spec.getVersion());
+    }
+    for (Declaration declaration : spec.getDeclarationsList()) {
+      KeepDeclaration parsedDeclaration = KeepDeclaration.fromProto(declaration, version);
+      if (parsedDeclaration == null) {
+        throw new ResourceException(getOrigin(), "Unable to parse declaration " + declaration);
+      } else {
+        consumer.accept(parsedDeclaration);
+      }
+    }
+  }
+
+  abstract KeepSpec read() throws ResourceException;
+
+  private static class KeepSpecificationFile extends KeepSpecificationSource {
+
+    private final Path path;
+
+    private KeepSpecificationFile(Path path) {
+      super(new PathOrigin(path));
+      this.path = path;
+    }
+
+    @Override
+    KeepSpec read() throws ResourceException {
+      try (InputStream stream = Files.newInputStream(path)) {
+        return KeepSpec.parseFrom(stream);
+      } catch (IOException e) {
+        throw new ResourceException(getOrigin(), e);
+      }
+    }
+  }
+
+  private static class KeepSpecificationBytes extends KeepSpecificationSource {
+
+    private final byte[] content;
+
+    public KeepSpecificationBytes(Origin origin, byte[] bytes) {
+      super(origin);
+      this.content = bytes;
+    }
+
+    @Override
+    KeepSpec read() throws ResourceException {
+      try {
+        return KeepSpec.parseFrom(content);
+      } catch (InvalidProtocolBufferException e) {
+        throw new ResourceException(getOrigin(), e);
+      }
+    }
+  }
+}

diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParserOptions.java b/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParserOptions.java
index acdd37c..a584eb4 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParserOptions.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardConfigurationParserOptions.java

@@ -72,9 +72,10 @@
               "com.android.tools.r8.experimental.enablewhyareyounotinlining", false);
       enableTestingOptions =
           parseSystemPropertyOrDefault("com.android.tools.r8.allowTestProguardOptions", false);
+      // TODO(b/323136645): This should default to false.
       forceEnableEmptyMemberRulesToDefaultInitRuleConversion =
           parseSystemPropertyOrDefault(
-              "com.android.tools.r8.enableEmptyMemberRulesToDefaultInitRuleConversion", false);
+              "com.android.tools.r8.enableEmptyMemberRulesToDefaultInitRuleConversion", true);
       return this;
     }
 

diff --git a/src/main/java/com/android/tools/r8/shaking/rules/MaterializedConditionalRule.java b/src/main/java/com/android/tools/r8/shaking/rules/MaterializedConditionalRule.java
index cbae8fe..b6c85d0 100644
--- a/src/main/java/com/android/tools/r8/shaking/rules/MaterializedConditionalRule.java
+++ b/src/main/java/com/android/tools/r8/shaking/rules/MaterializedConditionalRule.java

@@ -26,23 +26,8 @@
   }
 
   public boolean pruneItems(PrunedItems prunedItems) {
-    for (DexReference precondition : preconditions) {
-      if (precondition.isDexType()) {
-        if (prunedItems.getRemovedClasses().contains(precondition.asDexType())) {
-          return true;
-        }
-      } else if (precondition.isDexField()) {
-        if (prunedItems.getRemovedFields().contains(precondition.asDexField())) {
-          return true;
-        }
-      } else {
-        assert precondition.isDexMethod();
-        if (prunedItems.getRemovedMethods().contains(precondition.asDexMethod())) {
-          return true;
-        }
-      }
-    }
-    // Preconditions are in place, so trim down consequences.
+    // Preconditions cannot be pruned as they reference "original" program references which may be
+    // in inlined positions even when the items themselves are "pruned".
     consequences.pruneItems(prunedItems);
     return consequences.isEmpty();
   }

diff --git a/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutliner.java b/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutliner.java
new file mode 100644
index 0000000..5e5f3bd
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutliner.java

@@ -0,0 +1,400 @@
+// Copyright (c) 2024, 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.MapUtils.ignoreKey;
+
+import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
+import com.android.tools.r8.contexts.CompilationContext.ProcessorContext;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.Code;
+import com.android.tools.r8.graph.DefaultUseRegistryWithResult;
+import com.android.tools.r8.graph.DexClassAndField;
+import com.android.tools.r8.graph.DexClassAndMethod;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.graph.MethodResolutionResult;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.synthetic.ForwardMethodBuilder;
+import com.android.tools.r8.optimize.singlecaller.SingleCallerInliner;
+import com.android.tools.r8.profile.rewriting.ProfileCollectionAdditions;
+import com.android.tools.r8.profile.startup.profile.StartupProfile;
+import com.android.tools.r8.shaking.KeepMethodInfo.Joiner;
+import com.android.tools.r8.synthesis.CommittedItems;
+import com.android.tools.r8.synthesis.SyntheticItems;
+import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.Timing;
+import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.function.Consumer;
+
+// TODO(b/275292237): Preserve class initialization side effects using InitClass.
+// TODO(b/275292237): Preserve receiver NPE semantics by inserting null checks.
+public class NonStartupInStartupOutliner {
+
+  private final AppView<? extends AppInfoWithClassHierarchy> appView;
+  private final DexItemFactory factory;
+  private final NonStartupInStartupOutlinerLens.Builder lensBuilder =
+      NonStartupInStartupOutlinerLens.builder();
+  private final StartupProfile startupProfile;
+  private final ProgramMethodSet syntheticMethods;
+
+  public NonStartupInStartupOutliner(AppView<? extends AppInfoWithClassHierarchy> appView) {
+    this.appView = appView;
+    this.factory = appView.dexItemFactory();
+    this.startupProfile = appView.getStartupProfile();
+    this.syntheticMethods = ProgramMethodSet.createConcurrent();
+  }
+
+  public void runIfNecessary(ExecutorService executorService, Timing timing)
+      throws ExecutionException {
+    if (!startupProfile.isEmpty() && appView.options().getStartupOptions().isOutliningEnabled()) {
+      timing.time("NonStartupInStartupOutliner", () -> run(executorService, timing));
+    }
+  }
+
+  private void run(ExecutorService executorService, Timing timing) throws ExecutionException {
+    Map<DexProgramClass, List<ProgramMethod>> methodsToOutline =
+        getMethodsToOutline(executorService);
+    if (methodsToOutline.isEmpty()) {
+      return;
+    }
+    ProfileCollectionAdditions profileCollectionAdditions =
+        ProfileCollectionAdditions.create(appView);
+    performOutlining(methodsToOutline, executorService, profileCollectionAdditions);
+    profileCollectionAdditions.commit(appView);
+    commitPendingSyntheticClasses();
+    setSyntheticKeepInfo();
+    rewriteWithLens(executorService, timing);
+  }
+
+  private Map<DexProgramClass, List<ProgramMethod>> getMethodsToOutline(
+      ExecutorService executorService) throws ExecutionException {
+    Map<DexProgramClass, List<ProgramMethod>> methodsToOutline = new ConcurrentHashMap<>();
+    ThreadUtils.processItems(
+        appView.appInfo().classes(),
+        clazz ->
+            forEachMethodToOutline(
+                clazz,
+                method ->
+                    methodsToOutline.computeIfAbsent(clazz, ignoreKey(ArrayList::new)).add(method)),
+        appView.options().getThreadingModule(),
+        executorService);
+    return methodsToOutline;
+  }
+
+  private void forEachMethodToOutline(DexProgramClass clazz, Consumer<ProgramMethod> fn) {
+    if (!startupProfile.isStartupClass(clazz.getType())) {
+      return;
+    }
+    clazz.forEachProgramMethodMatching(
+        DexEncodedMethod::hasCode,
+        method -> {
+          if (!startupProfile.containsMethodRule(method.getReference())
+              && !method.getDefinition().isInitializer()
+              && canCodeBeMoved(method)) {
+            fn.accept(method);
+          }
+        });
+  }
+
+  // TODO(b/275292237): Extend to cover all possible accesses to private items (e.g., consider
+  //  method handles).
+  private boolean canCodeBeMoved(ProgramMethod method) {
+    return method.registerCodeReferencesWithResult(
+        new DefaultUseRegistryWithResult<>(appView, method, true) {
+
+          private AppInfoWithClassHierarchy appInfo() {
+            return NonStartupInStartupOutliner.this.appView.appInfo();
+          }
+
+          private void setCodeCannotBeMoved() {
+            setResult(false);
+          }
+
+          // Field accesses.
+
+          @Override
+          public void registerInstanceFieldRead(DexField field) {
+            registerFieldAccess(field);
+          }
+
+          @Override
+          public void registerInstanceFieldWrite(DexField field) {
+            registerFieldAccess(field);
+          }
+
+          @Override
+          public void registerStaticFieldRead(DexField field) {
+            registerFieldAccess(field);
+          }
+
+          @Override
+          public void registerStaticFieldWrite(DexField field) {
+            registerFieldAccess(field);
+          }
+
+          private void registerFieldAccess(DexField field) {
+            DexClassAndField resolvedField =
+                appInfo().resolveField(field, getContext()).getResolutionPair();
+            if (resolvedField == null) {
+              return;
+            }
+            if (resolvedField.getAccessFlags().isPrivate()) {
+              setCodeCannotBeMoved();
+            } else if (resolvedField.getAccessFlags().isProtected()
+                && !resolvedField.isSamePackage(getContext())) {
+              setCodeCannotBeMoved();
+            }
+          }
+
+          // Invokes.
+
+          @Override
+          public void registerInvokeDirect(DexMethod method) {
+            registerInvokeMethod(appInfo().unsafeResolveMethodDueToDexFormat(method));
+          }
+
+          @Override
+          public void registerInvokeInterface(DexMethod method) {
+            registerInvokeMethod(appInfo().resolveMethod(method, true));
+          }
+
+          @Override
+          public void registerInvokeStatic(DexMethod method) {
+            registerInvokeMethod(appInfo().unsafeResolveMethodDueToDexFormat(method));
+          }
+
+          @Override
+          public void registerInvokeSuper(DexMethod method) {
+            setCodeCannotBeMoved();
+          }
+
+          @Override
+          public void registerInvokeVirtual(DexMethod method) {
+            registerInvokeMethod(appInfo().resolveMethod(method, false));
+          }
+
+          private void registerInvokeMethod(MethodResolutionResult resolutionResult) {
+            DexClassAndMethod resolvedMethod = resolutionResult.getResolutionPair();
+            if (resolvedMethod == null) {
+              return;
+            }
+            if (resolvedMethod.getAccessFlags().isPrivate()) {
+              setCodeCannotBeMoved();
+            } else if (resolvedMethod.getAccessFlags().isProtected()
+                && !resolvedMethod.isSamePackage(getContext())) {
+              setCodeCannotBeMoved();
+            }
+          }
+        });
+  }
+
+  private void performOutlining(
+      Map<DexProgramClass, List<ProgramMethod>> methodsToOutline,
+      ExecutorService executorService,
+      ProfileCollectionAdditions profileCollectionAdditions)
+      throws ExecutionException {
+    // TODO(b/275292237): Only compute this information for virtual methods in startup classes.
+    ProcessorContext processorContext = appView.createProcessorContext();
+    ProgramMethodSet monomorphicVirtualMethods =
+        SingleCallerInliner.computeMonomorphicVirtualRootMethods(appView, executorService);
+    ThreadUtils.processMap(
+        methodsToOutline,
+        (clazz, methods) ->
+            performOutliningForClass(
+                clazz,
+                methods,
+                monomorphicVirtualMethods,
+                processorContext,
+                profileCollectionAdditions),
+        appView.options().getThreadingModule(),
+        executorService);
+  }
+
+  private void performOutliningForClass(
+      DexProgramClass clazz,
+      List<ProgramMethod> methodsToOutline,
+      ProgramMethodSet monomorphicVirtualMethods,
+      ProcessorContext processorContext,
+      ProfileCollectionAdditions profileCollectionAdditions) {
+    Set<DexEncodedMethod> methodsToRemove = Sets.newIdentityHashSet();
+    for (ProgramMethod method : methodsToOutline) {
+      MethodProcessingContext methodProcessingContext =
+          processorContext.createMethodProcessingContext(method);
+      ProgramMethod syntheticMethod;
+      boolean isMove = isMoveable(method, monomorphicVirtualMethods);
+      if (isMove) {
+        syntheticMethod = performMove(method, methodProcessingContext);
+        methodsToRemove.add(method.getDefinition());
+      } else {
+        syntheticMethod = performOutliningForMethod(method, methodProcessingContext);
+      }
+      profileCollectionAdditions.applyIfContextIsInProfile(
+          method.getReference(),
+          additionsBuilder -> {
+            additionsBuilder
+                .addClassRule(syntheticMethod.getHolderType())
+                .addMethodRule(syntheticMethod.getReference());
+            if (isMove) {
+              additionsBuilder.removeMovedMethodRule(method, syntheticMethod);
+            }
+          });
+      syntheticMethods.add(syntheticMethod);
+    }
+    clazz.getMethodCollection().removeMethods(methodsToRemove);
+  }
+
+  private boolean isMoveable(ProgramMethod method, ProgramMethodSet monomorphicVirtualMethods) {
+    // If we extend this to D8 then we can never move any methods since this would require a mapping
+    // file for retracing.
+    assert appView.enableWholeProgramOptimizations();
+    if (!appView.getKeepInfo(method).isShrinkingAllowed(appView.options())) {
+      // Kept methods can never be moved.
+      return false;
+    }
+    if (method.getAccessFlags().isStatic()) {
+      // Static methods can always be moved. Class initialization side effects can be preserved by
+      // inserting an InitClass instruction in the beginning of the moved method.
+      return true;
+    }
+    if (method.getAccessFlags().isPrivate()) {
+      // Private methods have direct dispatch and can always be made public static.
+      return true;
+    }
+    // Virtual methods can only be staticized and moved if they are monomorphic.
+    assert method.getAccessFlags().belongsToVirtualPool();
+    return method.getDefinition().isLibraryMethodOverride().isFalse()
+        && monomorphicVirtualMethods.contains(method);
+  }
+
+  private ProgramMethod performMove(
+      ProgramMethod method, MethodProcessingContext methodProcessingContext) {
+    ProgramMethod movedMethod =
+        createSyntheticMethod(
+            method,
+            methodProcessingContext,
+            method.getAccessFlags().copy().promoteToPublic().promoteToStatic());
+
+    // Record the move in the lens for correct lens code rewriting.
+    lensBuilder.recordMove(method, movedMethod);
+
+    return movedMethod;
+  }
+
+  private ProgramMethod performOutliningForMethod(
+      ProgramMethod method, MethodProcessingContext methodProcessingContext) {
+    ProgramMethod outlinedMethod =
+        createSyntheticMethod(
+            method, methodProcessingContext, MethodAccessFlags.createPublicStaticSynthetic());
+
+    // Rewrite the non-synthetic method to call the synthetic method.
+    method.setCode(
+        ForwardMethodBuilder.builder(factory)
+            .applyIf(
+                method.getAccessFlags().isStatic(),
+                codeBuilder -> codeBuilder.setStaticSource(method.getReference()),
+                codeBuilder -> codeBuilder.setNonStaticSource(method.getReference()))
+            .setStaticTarget(outlinedMethod.getReference(), false)
+            .buildLir(appView),
+        appView);
+
+    return outlinedMethod;
+  }
+
+  private ProgramMethod createSyntheticMethod(
+      ProgramMethod method,
+      MethodProcessingContext methodProcessingContext,
+      MethodAccessFlags accessFlags) {
+    return appView
+        .getSyntheticItems()
+        .createMethod(
+            kinds -> kinds.NON_STARTUP_IN_STARTUP_OUTLINE,
+            methodProcessingContext.createUniqueContext(),
+            appView,
+            builder ->
+                builder
+                    .setAccessFlags(accessFlags)
+                    .setApiLevelForCode(method.getDefinition().getApiLevelForCode())
+                    .setApiLevelForDefinition(method.getDefinition().getApiLevelForDefinition())
+                    .setProto(
+                        factory.prependHolderToProtoIf(
+                            method.getReference(), !method.getAccessFlags().isStatic()))
+                    .setCode(
+                        syntheticMethod -> {
+                          Code code;
+                          if (method.getDefinition().getCode().supportsPendingInlineFrame()) {
+                            code = method.getDefinition().getCode();
+                            builder.setInlineFrame(
+                                method.getReference(), method.getDefinition().isD8R8Synthesized());
+                          } else {
+                            code =
+                                method
+                                    .getDefinition()
+                                    .getCode()
+                                    .getCodeAsInlining(
+                                        syntheticMethod,
+                                        true,
+                                        method.getReference(),
+                                        method.getDefinition().isD8R8Synthesized(),
+                                        factory);
+                          }
+                          if (!method.getAccessFlags().isStatic()) {
+                            DexEncodedMethod.setDebugInfoWithFakeThisParameter(
+                                code, syntheticMethod.getArity(), appView);
+                          }
+                          return code;
+                        }));
+  }
+
+  private void commitPendingSyntheticClasses() {
+    SyntheticItems syntheticItems = appView.getSyntheticItems();
+    if (!syntheticItems.hasPendingSyntheticClasses()) {
+      return;
+    }
+    CommittedItems committedItems = syntheticItems.commit(appView.app());
+    if (appView.hasLiveness()) {
+      appView
+          .withLiveness()
+          .setAppInfo(appView.appInfoWithLiveness().rebuildWithLiveness(committedItems));
+    } else {
+      appView
+          .withClassHierarchy()
+          .setAppInfo(appView.appInfo().rebuildWithClassHierarchy(committedItems));
+    }
+  }
+
+  private void setSyntheticKeepInfo() {
+    appView
+        .getKeepInfo()
+        .mutate(
+            keepInfo ->
+                syntheticMethods.forEach(
+                    syntheticMethod -> {
+                      keepInfo.registerCompilerSynthesizedMethod(syntheticMethod);
+                      keepInfo.joinMethod(syntheticMethod, Joiner::disallowInlining);
+                    }));
+  }
+
+  private void rewriteWithLens(ExecutorService executorService, Timing timing)
+      throws ExecutionException {
+    if (lensBuilder.isEmpty()) {
+      return;
+    }
+    NonStartupInStartupOutlinerLens lens = lensBuilder.build(appView);
+    appView.rewriteWithLens(lens, executorService, timing);
+  }
+}

diff --git a/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutlinerLens.java b/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutlinerLens.java
new file mode 100644
index 0000000..61ee4ec
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutlinerLens.java

@@ -0,0 +1,55 @@
+// Copyright (c) 2024, 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 com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.graph.lens.NestedGraphLens;
+import com.android.tools.r8.ir.code.InvokeType;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
+
+public class NonStartupInStartupOutlinerLens extends NestedGraphLens {
+
+  public NonStartupInStartupOutlinerLens(
+      AppView<?> appView, BidirectionalOneToOneMap<DexMethod, DexMethod> methodMap) {
+    super(appView, EMPTY_FIELD_MAP, methodMap, EMPTY_TYPE_MAP);
+  }
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  @Override
+  public boolean isNonStartupInStartupOutlinerLens() {
+    return true;
+  }
+
+  @Override
+  protected InvokeType mapInvocationType(
+      DexMethod newMethod, DexMethod newReboundMethod, DexMethod previousMethod, InvokeType type) {
+    return newMethod.isIdenticalTo(previousMethod) ? type : InvokeType.STATIC;
+  }
+
+  public static class Builder {
+
+    private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> newMethodSignatures =
+        new BidirectionalOneToOneHashMap<>();
+
+    public boolean isEmpty() {
+      return newMethodSignatures.isEmpty();
+    }
+
+    public synchronized void recordMove(ProgramMethod from, ProgramMethod to) {
+      newMethodSignatures.put(from.getReference(), to.getReference());
+    }
+    public NonStartupInStartupOutlinerLens build(
+        AppView<? extends AppInfoWithClassHierarchy> appView) {
+      return new NonStartupInStartupOutlinerLens(appView, newMethodSignatures);
+    }
+  }
+}

diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java
index b758859..27ae067 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticMethodBuilder.java

@@ -35,6 +35,7 @@
   private DexProto proto = null;
   private CfVersion classFileVersion;
   private SyntheticCodeGenerator codeGenerator = null;
+  private DexMethod pendingInlineFrame = null;
   private MethodAccessFlags accessFlags = null;
   private MethodTypeSignature genericSignature = MethodTypeSignature.noSignature();
   private DexAnnotationSet annotations = DexAnnotationSet.empty();
@@ -95,6 +96,14 @@
     return this;
   }
 
+  public SyntheticMethodBuilder setInlineFrame(DexMethod callee, boolean calleeIsD8R8Synthesized) {
+    if (!calleeIsD8R8Synthesized) {
+      // // No need to record a compiler synthesized inline frame.
+      this.pendingInlineFrame = callee;
+    }
+    return this;
+  }
+
   public SyntheticMethodBuilder setAccessFlags(MethodAccessFlags accessFlags) {
     this.accessFlags = accessFlags;
     return this;
@@ -144,6 +153,7 @@
             .setAnnotations(annotations)
             .setParameterAnnotations(parameterAnnotationsList)
             .setCode(code)
+            .applyIf(pendingInlineFrame != null, b -> b.setInlineFrame(pendingInlineFrame, false))
             .setClassFileVersion(classFileVersion)
             .setApiLevelForDefinition(apiLevelForDefinition)
             .setApiLevelForCode(apiLevelForCode)

diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
index 1ab00b6..0030cec 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java

@@ -102,6 +102,8 @@
       generator.forSingleMethod("ApiModelOutline");
   public final SyntheticKind DESUGARED_LIBRARY_BRIDGE =
       generator.forSingleMethod("DesugaredLibraryBridge");
+  public final SyntheticKind NON_STARTUP_IN_STARTUP_OUTLINE =
+      generator.forSingleMethodWithGlobalMerging("NonStartupInStartupOutline");
 
   private final List<SyntheticKind> ALL_KINDS;
   private String lazyVersionHash = null;

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 b3d395b..ef49e3a 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java

@@ -100,6 +100,7 @@
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.GlobalKeepInfoConfiguration;
+import com.android.tools.r8.shaking.KeepSpecificationSource;
 import com.android.tools.r8.shaking.ProguardConfiguration;
 import com.android.tools.r8.shaking.ProguardConfigurationRule;
 import com.android.tools.r8.threading.ThreadingModule;
@@ -118,6 +119,7 @@
 import java.io.IOException;
 import java.nio.file.Paths;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.Deque;
@@ -240,6 +242,8 @@
   private final ProguardConfiguration proguardConfiguration;
   public final Reporter reporter;
 
+  private Collection<KeepSpecificationSource> keepSpecificationSources = Collections.emptyList();
+
   // TODO(zerny): Make this private-final once we have full program-consumer support.
   public ProgramConsumer programConsumer = null;
 
@@ -314,6 +318,14 @@
     return lazyThreadingModule;
   }
 
+  public Collection<KeepSpecificationSource> getKeepSpecifications() {
+    return keepSpecificationSources;
+  }
+
+  public void setKeepSpecificationSources(Collection<KeepSpecificationSource> specifications) {
+    keepSpecificationSources = specifications;
+  }
+
   private void keepDebugRelatedInformation() {
     assert !proguardConfiguration.isObfuscating();
     getProguardConfiguration().getKeepAttributes().sourceFile = true;

diff --git a/src/main/java/com/android/tools/r8/utils/positions/MappedPositionToClassNameMapperBuilder.java b/src/main/java/com/android/tools/r8/utils/positions/MappedPositionToClassNameMapperBuilder.java
index 7f78da8..516241e 100644
--- a/src/main/java/com/android/tools/r8/utils/positions/MappedPositionToClassNameMapperBuilder.java
+++ b/src/main/java/com/android/tools/r8/utils/positions/MappedPositionToClassNameMapperBuilder.java

@@ -462,7 +462,11 @@
       assert residualIsD8R8Synthesized
           || originalMethod.isIdenticalTo(lensOriginalMethod)
           // TODO(b/326562454): In some case the lens is mapping two methods to a common original.
-          || originalMethod.getHolderType().isIdenticalTo(lensOriginalMethod.getHolderType());
+          || originalMethod.getHolderType().isIdenticalTo(lensOriginalMethod.getHolderType())
+          || appView
+              .getSyntheticItems()
+              .isSyntheticOfKind(
+                  method.getHolderType(), kinds -> kinds.NON_STARTUP_IN_STARTUP_OUTLINE);
       return true;
     }
 

diff --git a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java
index f6583d2..7860fed 100644
--- a/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/verticalclassmerging/VerticalClassMergerGraphLens.java

@@ -222,7 +222,12 @@
           MethodLookupResult.builder(this, codeLens)
               .setReboundReference(newReboundReference)
               .setReference(newReference)
-              .setType(mapInvocationType(newReference, previous.getReference(), previous.getType()))
+              .setType(
+                  mapInvocationType(
+                      newReference,
+                      newReboundReference,
+                      previous.getReference(),
+                      previous.getType()))
               .setPrototypeChanges(
                   internalDescribePrototypeChanges(
                       previous.getPrototypeChanges(),
@@ -287,8 +292,8 @@
 
   @Override
   protected InvokeType mapInvocationType(
-      DexMethod newMethod, DexMethod previousMethod, InvokeType type) {
-    if (isStaticized(newMethod)) {
+      DexMethod newMethod, DexMethod newReboundMethod, DexMethod previousMethod, InvokeType type) {
+    if (isStaticized(newReboundMethod)) {
       return InvokeType.STATIC;
     }
     if (type.isInterface()

diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/InaccessibleFieldTypeMergingTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/InaccessibleFieldTypeMergingTest.java
new file mode 100644
index 0000000..185ac46
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/InaccessibleFieldTypeMergingTest.java

@@ -0,0 +1,71 @@
+// Copyright (c) 2024, 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.classmerging.horizontal;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.classmerging.horizontal.testclasses.InaccessibleFieldTypeMergingTestClasses;
+import com.android.tools.r8.classmerging.horizontal.testclasses.InaccessibleFieldTypeMergingTestClasses.BarGreeterContainer;
+import com.android.tools.r8.classmerging.horizontal.testclasses.InaccessibleFieldTypeMergingTestClasses.FooGreeterContainer;
+import com.android.tools.r8.classmerging.horizontal.testclasses.InaccessibleFieldTypeMergingTestClasses.Greeter;
+import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
+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 InaccessibleFieldTypeMergingTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass(), InaccessibleFieldTypeMergingTestClasses.class)
+        .addKeepMainRule(Main.class)
+        .addHorizontallyMergedClassesInspector(
+            HorizontallyMergedClassesInspector::assertNoClassesMerged)
+        .enableInliningAnnotations()
+        .enableNoAccessModificationAnnotationsForClasses()
+        .enableNoHorizontalClassMergingAnnotations()
+        .enableNoMethodStaticizingAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters)
+        .compile()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Foo!", "Bar!");
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      FooGreeterContainer fooGreeterContainer = createFooGreeterContainer();
+      Greeter fooGreeter = fooGreeterContainer.f;
+      fooGreeter.greet();
+      BarGreeterContainer barGreeterContainer = createBarGreeterContainer();
+      Greeter barGreeter = barGreeterContainer.f;
+      barGreeter.greet();
+    }
+
+    @NeverInline
+    static FooGreeterContainer createFooGreeterContainer() {
+      return new FooGreeterContainer();
+    }
+
+    @NeverInline
+    static BarGreeterContainer createBarGreeterContainer() {
+      return new BarGreeterContainer();
+    }
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/testclasses/InaccessibleFieldTypeMergingTestClasses.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/testclasses/InaccessibleFieldTypeMergingTestClasses.java
new file mode 100644
index 0000000..702f432
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/testclasses/InaccessibleFieldTypeMergingTestClasses.java

@@ -0,0 +1,53 @@
+// Copyright (c) 2024, 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.classmerging.horizontal.testclasses;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoAccessModification;
+import com.android.tools.r8.NoHorizontalClassMerging;
+import com.android.tools.r8.NoMethodStaticizing;
+import com.android.tools.r8.NoVerticalClassMerging;
+
+public class InaccessibleFieldTypeMergingTestClasses {
+
+  @NoVerticalClassMerging
+  public interface Greeter {
+
+    void greet();
+  }
+
+  @NoAccessModification
+  @NoHorizontalClassMerging
+  static class FooGreeter implements Greeter {
+
+    @NeverInline
+    @NoMethodStaticizing
+    @Override
+    public void greet() {
+      System.out.println("Foo!");
+    }
+  }
+
+  public static class FooGreeterContainer {
+
+    public FooGreeter f = new FooGreeter();
+  }
+
+  @NoAccessModification
+  @NoHorizontalClassMerging
+  static class BarGreeter implements Greeter {
+
+    @NeverInline
+    @NoMethodStaticizing
+    @Override
+    public void greet() {
+      System.out.println("Bar!");
+    }
+  }
+
+  public static class BarGreeterContainer {
+
+    public BarGreeter f = new BarGreeter();
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/compatproguard/CompatKeepClassMemberNamesTestRunner.java b/src/test/java/com/android/tools/r8/compatproguard/CompatKeepClassMemberNamesTestRunner.java
index bb999d8..1bd723a 100644
--- a/src/test/java/com/android/tools/r8/compatproguard/CompatKeepClassMemberNamesTestRunner.java
+++ b/src/test/java/com/android/tools/r8/compatproguard/CompatKeepClassMemberNamesTestRunner.java

@@ -333,8 +333,7 @@
 
   @Test
   public void testWithMembersStarRuleFullR8() throws Exception {
-    testWithMembersStarRule(
-        testForR8(parameters.getBackend()).allowUnusedProguardConfigurationRules());
+    testWithMembersStarRule(testForR8(parameters.getBackend()));
   }
 
   // Tests for "-keepclassmembernames" and *no* minification.

diff --git a/src/test/java/com/android/tools/r8/ir/optimize/ifs/Regress343136777Test.java b/src/test/java/com/android/tools/r8/ir/optimize/ifs/Regress343136777Test.java
new file mode 100644
index 0000000..2adf213
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/ifs/Regress343136777Test.java

@@ -0,0 +1,130 @@
+// Copyright (c) 2024, 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.ifs;
+
+import static org.junit.Assert.assertThrows;
+
+import com.android.tools.r8.CompilationFailedException;
+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 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 Regress343136777Test extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  private static final String EXPECTED_OUTPUT = StringUtils.lines("Hello, world!");
+
+  @Test
+  public void testD8Debug() throws Exception {
+    parameters.assumeDexRuntime();
+    testForD8(parameters.getBackend())
+        .addProgramClasses(TestClass.class)
+        .setMinApi(parameters)
+        .debug()
+        .compile()
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  @Test
+  public void testD8Release() throws Exception {
+    parameters.assumeDexRuntime();
+    // TODO(b/343136777: This should not fail.
+    assertThrows(
+        CompilationFailedException.class,
+        () ->
+            testForD8(parameters.getBackend())
+                .addProgramClasses(TestClass.class)
+                .setMinApi(parameters)
+                .release()
+                .compile()
+                .run(parameters.getRuntime(), TestClass.class)
+                .assertSuccessWithOutput(EXPECTED_OUTPUT));
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    // TODO(b/343136777: This should not fail.
+    assertThrows(
+        CompilationFailedException.class,
+        () ->
+            testForR8(parameters.getBackend())
+                .addProgramClasses(TestClass.class)
+                .setMinApi(parameters)
+                .addKeepMainRule(TestClass.class)
+                .compile()
+                .run(parameters.getRuntime(), TestClass.class)
+                .assertSuccessWithOutput(EXPECTED_OUTPUT));
+  }
+
+  static class TestClass {
+    /*
+      // This is the original code from b/343136777 failing the D8 release build.
+
+      class b {
+        ArrayList<String> A = new ArrayList<>();
+      }
+
+      public static StackTraceElement getCaller(b pool, StackTraceElement[] callers, int start) {
+        StackTraceElement targetStackTrace = null;
+        boolean shouldTrace = false;
+        int i = start;
+        while (i < callers.length) {
+          StackTraceElement caller = callers[i];
+          boolean isLogMethod = false;
+          for (String className : pool.A) {
+            if (caller.getClassName().equals(className)) {
+              isLogMethod = true;
+              break;
+            }
+          }
+          if (shouldTrace && !isLogMethod) {
+            targetStackTrace = caller;
+            break;
+          }
+          shouldTrace = isLogMethod;
+          i++;
+        }
+        return targetStackTrace;
+      }
+    */
+
+    public static void m() {
+      boolean a = false;
+      for (int i = 0; i < 2; i++) {
+        boolean b = false;
+        for (int j = 0; j < 2; j++) {
+          if (i == j) {
+            b = true;
+            break;
+          }
+        }
+        if (a && b) {
+          break;
+        }
+        a = b;
+      }
+    }
+
+    public static void main(String[] args) {
+      m();
+      System.out.println("Hello, world!");
+    }
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
index 27b74ee..f39df8f 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepAnnoTestBuilder.java

@@ -23,11 +23,16 @@
 import com.android.tools.r8.keepanno.asm.KeepEdgeReader;
 import com.android.tools.r8.keepanno.asm.KeepEdgeWriter;
 import com.android.tools.r8.keepanno.ast.KeepDeclaration;
+import com.android.tools.r8.keepanno.ast.KeepSpecVersion;
 import com.android.tools.r8.keepanno.keeprules.KeepRuleExtractorOptions;
+import com.android.tools.r8.keepanno.proto.KeepSpecProtos.KeepSpec;
+import com.android.tools.r8.keepanno.utils.Unimplemented;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
@@ -66,6 +71,12 @@
     return keepAnnoParams.parameters();
   }
 
+  public KeepAnnoTestBuilder addInnerClasses(Class<?> clazz) throws IOException {
+    return addProgramFiles(new ArrayList<>(ToolHelper.getClassFilesForInnerClasses(clazz)));
+  }
+
+  public abstract KeepAnnoTestBuilder addProgramFiles(List<Path> programFiles) throws IOException;
+
   public abstract KeepAnnoTestBuilder addProgramClasses(List<Class<?>> programClasses)
       throws IOException;
 
@@ -148,6 +159,12 @@
     }
 
     @Override
+    public KeepAnnoTestBuilder addProgramFiles(List<Path> programFiles) {
+      builder.addProgramFiles(programFiles);
+      return this;
+    }
+
+    @Override
     public KeepAnnoTestBuilder addProgramClasses(List<Class<?>> programClasses) {
       builder.addProgramClasses(programClasses);
       return this;
@@ -230,6 +247,14 @@
     }
 
     @Override
+    public KeepAnnoTestBuilder addProgramFiles(List<Path> programFiles) throws IOException {
+      for (Path programFile : programFiles) {
+        extractAndAdd(Files.readAllBytes(programFile));
+      }
+      return this;
+    }
+
+    @Override
     public KeepAnnoTestBuilder addProgramClasses(List<Class<?>> programClasses) throws IOException {
       for (Class<?> programClass : programClasses) {
         extractAndAdd(ToolHelper.getClassAsBytes(programClass));
@@ -258,6 +283,23 @@
       if (isNormalizeEdges()) {
         List<KeepDeclaration> declarations = KeepEdgeReader.readKeepEdges(classFileData);
         if (!declarations.isEmpty()) {
+          List<KeepDeclaration> legacyExtract = new ArrayList<>();
+          KeepSpec.Builder keepSpecBuilder = KeepSpec.newBuilder();
+          keepSpecBuilder.setVersion(KeepSpecVersion.getCurrent().buildProto());
+          for (KeepDeclaration declaration : declarations) {
+            try {
+              keepSpecBuilder.addDeclarations(declaration.buildDeclarationProto());
+            } catch (Unimplemented e) {
+              legacyExtract.add(declaration);
+            }
+          }
+          builder
+              .getBuilder()
+              .addKeepSpecificationData(keepSpecBuilder.build().toByteArray(), Origin.unknown());
+          if (legacyExtract.isEmpty()) {
+            // TODO(b/343389186): Finish the proto encoding and remove the below extraction.
+            return;
+          }
           String binaryName =
               DescriptorUtils.getBinaryNameFromDescriptor(extractClassDescriptor(classFileData));
           String synthesizingTarget = binaryName + "$$ExtractedKeepEdges";
@@ -270,7 +312,7 @@
               "java/lang/Object",
               null);
           KeepEdgeWriter.writeExtractedEdges(
-              declarations,
+              legacyExtract,
               (descriptor, visible) ->
                   KeepAnnoTestUtils.wrap(classWriter.visitAnnotation(descriptor, visible)));
           classWriter.visitEnd();
@@ -320,6 +362,14 @@
     }
 
     @Override
+    public KeepAnnoTestBuilder addProgramFiles(List<Path> programFiles) throws IOException {
+      List<String> rules = KeepAnnoTestUtils.extractRulesFromFiles(programFiles, extractorOptions);
+      builder.addProgramFiles(programFiles);
+      builder.addKeepRules(rules);
+      return this;
+    }
+
+    @Override
     public KeepAnnoTestBuilder addProgramClasses(List<Class<?>> programClasses) throws IOException {
       List<String> rules = KeepAnnoTestUtils.extractRules(programClasses, extractorOptions);
       builder.addProgramClasses(programClasses);
@@ -372,6 +422,14 @@
     }
 
     @Override
+    public KeepAnnoTestBuilder addProgramFiles(List<Path> programFiles) throws IOException {
+      List<String> rules = KeepAnnoTestUtils.extractRulesFromFiles(programFiles, extractorOptions);
+      builder.addProgramFiles(programFiles);
+      builder.addKeepRules(rules);
+      return this;
+    }
+
+    @Override
     public KeepAnnoTestBuilder addProgramClasses(List<Class<?>> programClasses) throws IOException {
       List<String> rules = KeepAnnoTestUtils.extractRules(programClasses, extractorOptions);
       builder.addProgramClasses(programClasses);

diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepTypePatternWithInstanceOfTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepTypePatternWithInstanceOfTest.java
new file mode 100644
index 0000000..ce7c1d7
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepTypePatternWithInstanceOfTest.java

@@ -0,0 +1,192 @@
+// Copyright (c) 2024, 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.keepanno;
+
+import static org.junit.Assert.assertThrows;
+
+import com.android.tools.r8.TestShrinkerBuilder;
+import com.android.tools.r8.keepanno.annotations.ClassNamePattern;
+import com.android.tools.r8.keepanno.annotations.InstanceOfPattern;
+import com.android.tools.r8.keepanno.annotations.KeepTarget;
+import com.android.tools.r8.keepanno.annotations.TypePattern;
+import com.android.tools.r8.keepanno.annotations.UsesReflection;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+
+@RunWith(Parameterized.class)
+public class KeepTypePatternWithInstanceOfTest extends KeepAnnoTestBase {
+
+  @Parameter public KeepAnnoParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static List<KeepAnnoParameters> data() {
+    return createParameters(
+        getTestParameters()
+            .withDefaultRuntimes()
+            .withApiLevel(AndroidApiLevel.B)
+            .enableApiLevelsForCf()
+            .build());
+  }
+
+  @Test
+  public void test() throws Exception {
+    if (parameters.isReference() || parameters.isNativeR8()) {
+      testForKeepAnno(parameters)
+          .addInnerClasses(getClass())
+          .addKeepMainRule(TestClass.class)
+          .run(TestClass.class)
+          .assertSuccessWithOutput(getExpectedResult(parameters.isReference() ? 9 : 4));
+    } else {
+      // It's either Unimplemented or CompilationFailedException.
+      assertThrows(
+          Exception.class,
+          () ->
+              testForKeepAnno(parameters)
+                  .addInnerClasses(getClass())
+                  .addKeepMainRule(TestClass.class)
+                  .run(TestClass.class));
+    }
+  }
+
+  private String getExpectedResult(int numMethods) {
+    return StringUtils.lines(
+        "Num methods: " + numMethods,
+        "5",
+        "8",
+        "9",
+        "6",
+        "1",
+        "2",
+        "3",
+        "4",
+        "5",
+        "6",
+        "7",
+        "8",
+        "9");
+  }
+
+  private void clearClassMerging(TestShrinkerBuilder<?, ?, ?, ?, ?> sb) {
+    sb.addOptionsModification(
+        opt -> {
+          opt.horizontalClassMergerOptions().disable();
+          opt.getVerticalClassMergerOptions().disable();
+        });
+  }
+
+  public static class Top {}
+
+  public static class Top1 extends Top {}
+
+  public static class Sub1 extends Top1 {}
+
+  public static class Subb1 extends Top1 {}
+
+  public static class Top2 extends Top {}
+
+  public static class Sub2 extends Top2 {}
+
+  public static class Subb2 extends Top2 {}
+
+  public static class A {
+
+    public void foo(Top1 a, Top2 b) {
+      System.out.println("1");
+    }
+
+    public void foo(Sub1 a, Top2 b) {
+      System.out.println("2");
+    }
+
+    public void foo(Subb1 a, Top2 b) {
+      System.out.println("3");
+    }
+
+    public void foo(Top1 a, Sub2 b) {
+      System.out.println("4");
+    }
+
+    public void foo(Sub1 a, Sub2 b) {
+      System.out.println("5");
+    }
+
+    public void foo(Subb1 a, Sub2 b) {
+      System.out.println("6");
+    }
+
+    public void foo(Top1 a, Subb2 b) {
+      System.out.println("7");
+    }
+
+    public void foo(Sub1 a, Subb2 b) {
+      System.out.println("8");
+    }
+
+    public void foo(Subb1 a, Subb2 b) {
+      System.out.println("9");
+    }
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args)
+        throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
+      System.out.println("Num methods: " + A.class.getDeclaredMethods().length);
+      for (Method method : reflectiveMethods()) {
+        method.invoke(new A(), null, null);
+      }
+      // Make sure all the methods are live, they can be inlined.
+      runAll();
+    }
+
+    private static void runAll() {
+      A a = new A();
+      a.foo(new Top1(), new Top2());
+      a.foo(new Sub1(), new Top2());
+      a.foo(new Subb1(), new Top2());
+      a.foo(new Top1(), new Sub2());
+      a.foo(new Sub1(), new Sub2());
+      a.foo(new Subb1(), new Sub2());
+      a.foo(new Top1(), new Subb2());
+      a.foo(new Sub1(), new Subb2());
+      a.foo(new Subb1(), new Subb2());
+    }
+
+    @UsesReflection(
+        @KeepTarget(
+            classConstant = A.class,
+            methodName = "foo",
+            methodParameterTypePatterns = {
+              @TypePattern(
+                  instanceOfPattern =
+                      @InstanceOfPattern(
+                          inclusive = false,
+                          classNamePattern = @ClassNamePattern(constant = Top1.class))),
+              @TypePattern(
+                  instanceOfPattern =
+                      @InstanceOfPattern(
+                          inclusive = false,
+                          classNamePattern = @ClassNamePattern(constant = Top2.class)))
+            }))
+    public static Method[] reflectiveMethods() throws NoSuchMethodException {
+      return new Method[] {
+        A.class.getDeclaredMethod(getFoo(), Sub1.class, Sub2.class),
+        A.class.getDeclaredMethod(getFoo(), Sub1.class, Subb2.class),
+        A.class.getDeclaredMethod(getFoo(), Subb1.class, Subb2.class),
+        A.class.getDeclaredMethod(getFoo(), Subb1.class, Sub2.class)
+      };
+    }
+
+    private static String getFoo() {
+      return System.currentTimeMillis() > 0 ? "foo" : "bar";
+    }
+  }
+}

diff --git a/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTrivialJavaStyleTest.java b/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTrivialJavaStyleTest.java
index ff134b5..1d1e173 100644
--- a/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTrivialJavaStyleTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTrivialJavaStyleTest.java

@@ -99,7 +99,7 @@
         && kotlinParameters.getCompilerVersion().isLessThan(KOTLINC_1_5_0)) {
       // Don't check exactly how J-style Kotlin lambdas are merged for kotlinc before 1.5.0.
       assertEquals(
-          parameters.isDexRuntime() && parameters.canUseDefaultAndStaticInterfaceMethods() ? 2 : 10,
+          parameters.isDexRuntime() && parameters.canUseDefaultAndStaticInterfaceMethods() ? 3 : 10,
           inspector.getMergeGroups().size());
       return;
     }
@@ -242,7 +242,7 @@
         kotlinParameters.getCompilerVersion().isGreaterThanOrEqualTo(KOTLINC_1_5_0)
             ? 0
             : (parameters.isDexRuntime() && parameters.canUseDefaultAndStaticInterfaceMethods()
-                ? 2
+                ? 3
                 : 8),
         lambdasInOutput.size());
   }

diff --git a/src/test/java/com/android/tools/r8/profile/art/DesugaredLibraryArtProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/DesugaredLibraryArtProfileRewritingTest.java
index 811cb53..39ef47d 100644
--- a/src/test/java/com/android/tools/r8/profile/art/DesugaredLibraryArtProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/DesugaredLibraryArtProfileRewritingTest.java

@@ -113,6 +113,9 @@
             libraryDesugaringSpecification.functionPrefix(parameters) + ".util.function.Consumer");
     assertThat(consumerClassSubject, isPresent());
 
+    ClassSubject baseStreamClassSubject = inspector.clazz("j$.util.stream.BaseStream");
+    assertThat(baseStreamClassSubject, isPresentAndRenamed(compilationSpecification.isL8Shrink()));
+
     ClassSubject streamClassSubject = inspector.clazz("j$.util.stream.Stream");
     assertThat(streamClassSubject, isPresentAndNotRenamed());
 
@@ -124,7 +127,10 @@
                 && libraryDesugaringSpecification == LibraryDesugaringSpecification.JDK8));
     assertEquals(consumerClassSubject.asTypeSubject(), forEachMethodSubject.getParameter(0));
 
-    profileInspector.assertContainsMethodRule(forEachMethodSubject).assertContainsNoOtherRules();
+    profileInspector
+        .assertContainsClassRules(streamClassSubject, baseStreamClassSubject)
+        .assertContainsMethodRule(forEachMethodSubject)
+        .assertContainsNoOtherRules();
   }
 
   static class Main {

diff --git a/src/test/java/com/android/tools/r8/profile/art/IncludeTransitiveSuperClassesInArtProfileTest.java b/src/test/java/com/android/tools/r8/profile/art/IncludeTransitiveSuperClassesInArtProfileTest.java
new file mode 100644
index 0000000..322c207
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/profile/art/IncludeTransitiveSuperClassesInArtProfileTest.java

@@ -0,0 +1,73 @@
+// Copyright (c) 2024, 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.profile.art;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndRenamed;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.profile.art.model.ExternalArtProfile;
+import com.android.tools.r8.references.ClassReference;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+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 IncludeTransitiveSuperClassesInArtProfileTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepAllClassesRuleWithAllowObfuscation()
+        .addArtProfileForRewriting(
+            ExternalArtProfile.builder().addClassRule(Reference.classFromClass(C.class)).build())
+        .setMinApi(parameters)
+        .compile()
+        .inspectResidualArtProfile(
+            (profile, inspector) ->
+                profile
+                    .assertContainsClassRules(
+                        getFinalReference(A.class, inspector),
+                        getFinalReference(B.class, inspector),
+                        getFinalReference(C.class, inspector),
+                        getFinalReference(I.class, inspector),
+                        getFinalReference(J.class, inspector),
+                        getFinalReference(K.class, inspector))
+                    .assertContainsNoOtherRules());
+  }
+
+  private static ClassReference getFinalReference(Class<?> clazz, CodeInspector inspector) {
+    ClassSubject classSubject = inspector.clazz(clazz);
+    assertThat(classSubject, isPresentAndRenamed());
+    return classSubject.getFinalReference();
+  }
+
+  interface I {}
+
+  interface J {}
+
+  interface K extends J {}
+
+  static class A implements I {}
+
+  static class B extends A {}
+
+  static class C extends B implements K {}
+}

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingShardTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingShardTest.java
index 709703c..aa6d410 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingShardTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingShardTest.java

@@ -17,6 +17,7 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.profile.art.model.ExternalArtProfile;
 import com.android.tools.r8.profile.art.utils.ArtProfileInspector;
+import com.android.tools.r8.references.Reference;
 import com.android.tools.r8.synthesis.SyntheticItemsTestUtils;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.BooleanUtils;
@@ -145,6 +146,7 @@
 
     // Verify the residual profile contains the outline method and its holder when present.
     profileInspector
+        .assertContainsClassRule(Reference.classFromClass(mainClass))
         .assertContainsMethodRule(MethodReferenceUtils.mainMethod(mainClass))
         .applyIf(
             !isLibraryClassAlwaysPresent(),
@@ -172,8 +174,11 @@
 
     // Verify the residual profile contains the outline method and its holder when present.
     profileInspector
-        .assertContainsMethodRule(MethodReferenceUtils.mainMethod(Main.class))
-        .assertContainsMethodRule(MethodReferenceUtils.mainMethod(OtherMain.class))
+        .assertContainsClassRules(
+            Reference.classFromClass(Main.class), Reference.classFromClass(OtherMain.class))
+        .assertContainsMethodRules(
+            MethodReferenceUtils.mainMethod(Main.class),
+            MethodReferenceUtils.mainMethod(OtherMain.class))
         .applyIf(
             !isLibraryClassAlwaysPresent(),
             i ->

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingTest.java
index acd0d3f..12d2ef4 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/ApiOutlineProfileRewritingTest.java

@@ -18,6 +18,7 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.profile.art.model.ExternalArtProfile;
 import com.android.tools.r8.profile.art.utils.ArtProfileInspector;
+import com.android.tools.r8.references.Reference;
 import com.android.tools.r8.synthesis.SyntheticItemsTestUtils;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.MethodReferenceUtils;
@@ -146,6 +147,7 @@
 
     // Verify the residual profile contains the outline method and its holder when present.
     profileInspector
+        .assertContainsClassRule(Reference.classFromClass(Main.class))
         .assertContainsMethodRule(MethodReferenceUtils.mainMethod(Main.class))
         .applyIf(
             !isLibraryClassAlwaysPresent,

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/BackportProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/BackportProfileRewritingTest.java
index c3d0996..3a3b463 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/BackportProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/BackportProfileRewritingTest.java

@@ -13,6 +13,7 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.profile.art.model.ExternalArtProfile;
 import com.android.tools.r8.profile.art.utils.ArtProfileInspector;
+import com.android.tools.r8.references.Reference;
 import com.android.tools.r8.synthesis.SyntheticItemsTestUtils;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.InternalOptions.InlinerOptions;
@@ -96,6 +97,7 @@
 
     // Verify residual profile contains the backported method and its holder.
     profileInspector
+        .assertContainsClassRule(Reference.classFromClass(Main.class))
         .assertContainsMethodRules(MethodReferenceUtils.mainMethod(Main.class))
         .applyIf(
             isBackportingObjectsNonNull,

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/DefaultInterfaceMethodProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/DefaultInterfaceMethodProfileRewritingTest.java
index c5adb71..c9db8f6 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/DefaultInterfaceMethodProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/DefaultInterfaceMethodProfileRewritingTest.java

@@ -95,7 +95,9 @@
       MethodSubject interfaceMethodSubject = iClassSubject.uniqueMethodWithOriginalName("m");
       assertThat(interfaceMethodSubject, isPresent());
 
-      profileInspector.assertContainsMethodRule(interfaceMethodSubject);
+      profileInspector
+          .assertContainsClassRule(iClassSubject)
+          .assertContainsMethodRule(interfaceMethodSubject);
     } else {
       ClassSubject iClassSubject = inspector.clazz(I.class);
       assertThat(iClassSubject, isPresent());
@@ -125,7 +127,8 @@
       assertThat(movedMethodSubject, isPresent());
 
       profileInspector
-          .assertContainsClassRule(companionClassSubject)
+          .assertContainsClassRules(
+              aClassSubject, bClassSubject, iClassSubject, companionClassSubject)
           .assertContainsMethodRules(
               interfaceMethodSubject,
               aForwardingMethodSubject,

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/EnumUnboxingUtilityMethodProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/EnumUnboxingUtilityMethodProfileRewritingTest.java
index 04133ca..74cd8dd 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/EnumUnboxingUtilityMethodProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/EnumUnboxingUtilityMethodProfileRewritingTest.java

@@ -99,7 +99,9 @@
 
     profileInspector
         .assertContainsClassRules(
-            enumUnboxingLocalUtilityClassSubject, enumUnboxingSharedUtilityClassSubject)
+            mainClassSubject,
+            enumUnboxingLocalUtilityClassSubject,
+            enumUnboxingSharedUtilityClassSubject)
         .assertContainsMethodRules(
             mainClassSubject.mainMethod(),
             localGreetMethodSubject,

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedConstructorMethodProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedConstructorMethodProfileRewritingTest.java
index faea413..c909872 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedConstructorMethodProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedConstructorMethodProfileRewritingTest.java

@@ -76,6 +76,7 @@
       assertThat(syntheticConstructorSubject, isPresent());
 
       profileInspector
+          .assertContainsClassRule(aClassSubject)
           .assertContainsMethodRules(syntheticConstructorSubject)
           .applyIf(
               this == A_CONSTRUCTOR,

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedVirtualMethodProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedVirtualMethodProfileRewritingTest.java
index e4196f3..0ef50da 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedVirtualMethodProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/HorizontallyMergedVirtualMethodProfileRewritingTest.java

@@ -70,6 +70,7 @@
       assertEquals(aClassSubject.asTypeSubject(), syntheticBridgeMethodSubject.getParameter(0));
 
       profileInspector
+          .assertContainsClassRule(aClassSubject)
           .assertContainsMethodRules(movedMethodSubject, syntheticBridgeMethodSubject)
           .assertContainsNoOtherRules();
     }

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/InvokeSpecialToVirtualMethodProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/InvokeSpecialToVirtualMethodProfileRewritingTest.java
index 0b423ed..08803aa 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/InvokeSpecialToVirtualMethodProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/InvokeSpecialToVirtualMethodProfileRewritingTest.java

@@ -132,6 +132,7 @@
 
     // Verify residual profile contains private synthetic method when present.
     profileInspector
+        .assertContainsClassRule(mainClassSubject)
         .assertContainsMethodRules(mMethodSubject, mMovedMethodSubject)
         .assertContainsNoOtherRules();
   }

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/LambdaStaticLibraryMethodImplementationProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/LambdaStaticLibraryMethodImplementationProfileRewritingTest.java
index 6eac7c2..56731cd 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/LambdaStaticLibraryMethodImplementationProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/LambdaStaticLibraryMethodImplementationProfileRewritingTest.java

@@ -4,8 +4,8 @@
 
 package com.android.tools.r8.profile.art.completeness;
 
+import static com.android.tools.r8.utils.codeinspector.Matchers.isAbsentIf;
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
-import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
 import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.TestBase;
@@ -75,7 +75,7 @@
   }
 
   private void inspectD8(ArtProfileInspector profileInspector, CodeInspector inspector) {
-    inspect(profileInspector, inspector, false, false);
+    inspect(profileInspector, inspector, false, false, false);
   }
 
   private void inspectR8(ArtProfileInspector profileInspector, CodeInspector inspector) {
@@ -83,37 +83,44 @@
         profileInspector,
         inspector,
         parameters.canHaveNonReboundConstructorInvoke(),
-        parameters.isCfRuntime());
+        parameters.isCfRuntime(),
+        true);
   }
 
   public void inspect(
       ArtProfileInspector profileInspector,
       CodeInspector inspector,
       boolean canHaveNonReboundConstructorInvoke,
-      boolean canUseLambdas) {
+      boolean canUseLambdas,
+      boolean isR8) {
     ClassSubject mainClassSubject = inspector.clazz(Main.class);
     assertThat(mainClassSubject, isPresent());
 
     MethodSubject mainMethodSubject = mainClassSubject.mainMethod();
     assertThat(mainMethodSubject, isPresent());
 
+    ClassSubject setSupplierClassSubject = inspector.clazz(SetSupplier.class);
+    assertThat(setSupplierClassSubject, isAbsentIf(!canUseLambdas && isR8));
+
     // Check the presence of the lambda class and its methods.
     ClassSubject lambdaClassSubject =
         inspector.clazz(SyntheticItemsTestUtils.syntheticLambdaClass(Main.class, 0));
-    assertThat(lambdaClassSubject, notIf(isPresent(), canUseLambdas));
+    assertThat(lambdaClassSubject, isAbsentIf(canUseLambdas));
 
     MethodSubject lambdaInitializerSubject = lambdaClassSubject.uniqueInstanceInitializer();
-    assertThat(lambdaInitializerSubject, notIf(isPresent(), canUseLambdas));
+    assertThat(lambdaInitializerSubject, isAbsentIf(canUseLambdas));
 
     MethodSubject lambdaMainMethodSubject =
         lambdaClassSubject.uniqueMethodThatMatches(FoundMethodSubject::isVirtual);
-    assertThat(lambdaMainMethodSubject, notIf(isPresent(), canUseLambdas));
+    assertThat(lambdaMainMethodSubject, isAbsentIf(canUseLambdas));
 
-    if (canUseLambdas) {
-      profileInspector.assertContainsMethodRule(mainMethodSubject);
-    } else {
+    profileInspector
+        .assertContainsClassRules(mainClassSubject)
+        .assertContainsMethodRule(mainMethodSubject);
+    if (!canUseLambdas) {
       profileInspector
           .assertContainsClassRules(lambdaClassSubject)
+          .applyIf(!isR8, i -> i.assertContainsClassRule(setSupplierClassSubject))
           .assertContainsMethodRules(
               mainMethodSubject, lambdaInitializerSubject, lambdaMainMethodSubject);
     }

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/MovedPrivateInterfaceMethodProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/MovedPrivateInterfaceMethodProfileRewritingTest.java
index 632fc0b..53ab39f 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/MovedPrivateInterfaceMethodProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/MovedPrivateInterfaceMethodProfileRewritingTest.java

@@ -125,6 +125,7 @@
       assertThat(privateInterfaceMethodSubject, isPresent());
 
       profileInspector
+          .assertContainsClassRule(iClassSubject)
           .assertContainsMethodRule(privateInterfaceMethodSubject)
           .assertContainsNoOtherRules();
     } else {

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/MovedStaticInterfaceMethodProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/MovedStaticInterfaceMethodProfileRewritingTest.java
index ebf293e..7d06408 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/MovedStaticInterfaceMethodProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/MovedStaticInterfaceMethodProfileRewritingTest.java

@@ -141,6 +141,7 @@
       assertThat(staticInterfaceMethodSubject, isPresent());
 
       profileInspector
+          .assertContainsClassRule(iClassSubject)
           .assertContainsMethodRule(staticInterfaceMethodSubject)
           .assertContainsNoOtherRules();
     } else {

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/NestBasedAccessBridgesProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/NestBasedAccessBridgesProfileRewritingTest.java
index f296a71..5756f2e 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/NestBasedAccessBridgesProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/NestBasedAccessBridgesProfileRewritingTest.java

@@ -104,7 +104,12 @@
 
   private void inspectD8(ArtProfileInspector profileInspector, CodeInspector inspector)
       throws Exception {
-    inspect(profileInspector, inspector, false, parameters.canUseNestBasedAccessesWhenDesugaring());
+    inspect(
+        profileInspector,
+        inspector,
+        false,
+        parameters.canUseNestBasedAccessesWhenDesugaring(),
+        false);
   }
 
   private void inspectR8(ArtProfileInspector profileInspector, CodeInspector inspector)
@@ -113,14 +118,16 @@
         profileInspector,
         inspector,
         parameters.canHaveNonReboundConstructorInvoke(),
-        parameters.canUseNestBasedAccesses());
+        parameters.canUseNestBasedAccesses(),
+        true);
   }
 
   private void inspect(
       ArtProfileInspector profileInspector,
       CodeInspector inspector,
       boolean canHaveNonReboundConstructorInvoke,
-      boolean canUseNestBasedAccesses)
+      boolean canUseNestBasedAccesses,
+      boolean isR8)
       throws Exception {
     ClassSubject nestMemberClassSubject = inspector.clazz(NestMember.class);
     assertThat(nestMemberClassSubject, isPresent());
@@ -197,8 +204,12 @@
     // Verify the residual profile contains the synthetic nest based access bridges and the
     // synthetic constructor argument class.
     profileInspector
+        .assertContainsClassRule(Reference.classFromClass(Main.class))
         .assertContainsMethodRule(MethodReferenceUtils.mainMethod(Main.class))
         .applyIf(
+            !isR8 || parameters.isDexRuntime(),
+            i -> i.assertContainsClassRule(nestMemberClassSubject))
+        .applyIf(
             !canUseNestBasedAccesses,
             i ->
                 i.assertContainsMethodRules(

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/OutlineOptimizationProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/OutlineOptimizationProfileRewritingTest.java
index 1c0ac50..0c4ceca 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/OutlineOptimizationProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/OutlineOptimizationProfileRewritingTest.java

@@ -12,6 +12,7 @@
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.profile.art.model.ExternalArtProfile;
 import com.android.tools.r8.profile.art.utils.ArtProfileInspector;
+import com.android.tools.r8.references.Reference;
 import com.android.tools.r8.synthesis.SyntheticItemsTestUtils;
 import com.android.tools.r8.utils.InternalOptions.InlinerOptions;
 import com.android.tools.r8.utils.MethodReferenceUtils;
@@ -70,6 +71,7 @@
 
     // TODO(b/265729283): Should contain the outline class and method.
     profileInspector
+        .assertContainsClassRule(Reference.classFromClass(Main.class))
         .assertContainsMethodRule(MethodReferenceUtils.mainMethod(Main.class))
         .assertContainsNoOtherRules();
   }

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/RecordProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/RecordProfileRewritingTest.java
index cbab790..f0cd1ab 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/RecordProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/RecordProfileRewritingTest.java

@@ -300,7 +300,7 @@
         toStringMethodSubject, ifThen(!canUseRecords, invokesMethod(toStringHelperMethodSubject)));
 
     profileInspector
-        .assertContainsClassRule(personRecordClassSubject)
+        .assertContainsClassRules(mainClassSubject, personRecordClassSubject)
         .assertContainsMethodRules(
             mainMethodSubject,
             personInstanceInitializerSubject,

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/SyntheticLambdaClassProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/SyntheticLambdaClassProfileRewritingTest.java
index 53fb532..a919381 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/SyntheticLambdaClassProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/SyntheticLambdaClassProfileRewritingTest.java

@@ -134,11 +134,13 @@
         switch (this) {
           case MAIN_METHOD:
             profileInspector
+                .assertContainsClassRule(mainClassSubject)
                 .assertContainsMethodRule(mainMethodSubject)
                 .assertContainsNoOtherRules();
             break;
           case IMPLEMENTATION_METHOD:
             profileInspector
+                .assertContainsClassRule(mainClassSubject)
                 .assertContainsMethodRules(
                     lambdaImplementationMethod, otherLambdaImplementationMethod)
                 .assertContainsNoOtherRules();
@@ -153,7 +155,8 @@
             // with their initializers. Since Main.lambda$main$*() is not in the art profile, the
             // interface method implementation does not need to be included in the profile.
             profileInspector
-                .assertContainsClassRules(lambdaClassSubject, otherLambdaClassSubject)
+                .assertContainsClassRules(
+                    mainClassSubject, lambdaClassSubject, otherLambdaClassSubject)
                 .assertContainsMethodRules(mainMethodSubject)
                 .applyIf(
                     !canHaveNonReboundConstructorInvoke,
@@ -166,6 +169,8 @@
             // Since Main.lambda$main$*() is in the art profile, so should the two accessibility
             // bridges be along with the main virtual methods of the lambda classes.
             profileInspector
+                .assertContainsClassRules(
+                    mainClassSubject, lambdaClassSubject, otherLambdaClassSubject)
                 .assertContainsMethodRules(
                     lambdaImplementationMethod,
                     lambdaMainMethodSubject,

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/TwrCloseResourceDuplicationProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/TwrCloseResourceDuplicationProfileRewritingTest.java
index b8db6f5..f840c33f 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/TwrCloseResourceDuplicationProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/TwrCloseResourceDuplicationProfileRewritingTest.java

@@ -159,11 +159,13 @@
         barClassSubject.uniqueMethodWithOriginalName("$closeResource");
     assertThat(barCloseResourceMethodSubject, isPresent());
 
-    profileInspector.assertContainsMethodRules(
-        fooMethodSubject,
-        fooCloseResourceMethodSubject,
-        barMethodSubject,
-        barCloseResourceMethodSubject);
+    profileInspector
+        .assertContainsClassRules(fooClassSubject, barClassSubject)
+        .assertContainsMethodRules(
+            fooMethodSubject,
+            fooCloseResourceMethodSubject,
+            barMethodSubject,
+            barCloseResourceMethodSubject);
 
     // There is 1 backport, 2 synthetic API outlines, and 3 twr classes for both Foo and Bar.
     for (JavaExampleClassProxy clazz : ImmutableList.of(FOO, BAR)) {

diff --git a/src/test/java/com/android/tools/r8/profile/art/completeness/VerticalClassMergingBridgeProfileRewritingTest.java b/src/test/java/com/android/tools/r8/profile/art/completeness/VerticalClassMergingBridgeProfileRewritingTest.java
index 4493de9..10b893b 100644
--- a/src/test/java/com/android/tools/r8/profile/art/completeness/VerticalClassMergingBridgeProfileRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/completeness/VerticalClassMergingBridgeProfileRewritingTest.java

@@ -78,6 +78,7 @@
     assertThat(syntheticBridgeMethodSubject, isPresent());
 
     profileInspector
+        .assertContainsClassRule(bClassSubject)
         .assertContainsMethodRules(movedMethodSubject, syntheticBridgeMethodSubject)
         .assertContainsNoOtherRules();
   }

diff --git a/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithCommentsAndWhitespaceTest.java b/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithCommentsAndWhitespaceTest.java
index c5fdf6c..77ffaf9 100644
--- a/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithCommentsAndWhitespaceTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithCommentsAndWhitespaceTest.java

@@ -100,7 +100,10 @@
   }
 
   private void inspectResidualArtProfile(ArtProfileInspector profileInspector) {
-    profileInspector.assertContainsMethodRule(MAIN_METHOD_REFERENCE).assertContainsNoOtherRules();
+    profileInspector
+        .assertContainsClassRule(MAIN_METHOD_REFERENCE.getHolderClass())
+        .assertContainsMethodRule(MAIN_METHOD_REFERENCE)
+        .assertContainsNoOtherRules();
   }
 
   static class Main {

diff --git a/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithFlagsInAnyOrderTest.java b/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithFlagsInAnyOrderTest.java
index 45ab398..f4a074d 100644
--- a/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithFlagsInAnyOrderTest.java
+++ b/src/test/java/com/android/tools/r8/profile/art/format/ArtProfileWithFlagsInAnyOrderTest.java

@@ -114,6 +114,7 @@
 
   private void inspectResidualArtProfile(ArtProfileInspector profileInspector) {
     profileInspector
+        .assertContainsClassRule(MAIN_METHOD_REFERENCE.getHolderClass())
         .inspectMethodRule(
             MAIN_METHOD_REFERENCE,
             ruleInspector -> ruleInspector.assertIsHot().assertIsStartup().assertIsPostStartup())

diff --git a/src/test/java/com/android/tools/r8/shaking/ifrule/ConditionalKeepIfKeptTest.java b/src/test/java/com/android/tools/r8/shaking/ifrule/ConditionalKeepIfKeptTest.java
index 96aa8fd..ab71079 100644
--- a/src/test/java/com/android/tools/r8/shaking/ifrule/ConditionalKeepIfKeptTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/ifrule/ConditionalKeepIfKeptTest.java

@@ -62,7 +62,7 @@
               ClassSubject classSubject = inspector.clazz(StaticallyReferenced.class);
               assertThat(classSubject, isPresent());
               assertEquals(0, classSubject.allFields().size());
-              assertEquals(0, classSubject.allMethods().size());
+              assertEquals(1, classSubject.allMethods().size());
             });
   }
 

diff --git a/src/test/java/com/android/tools/r8/startup/NonStartupInStartupOutlinerTest.java b/src/test/java/com/android/tools/r8/startup/NonStartupInStartupOutlinerTest.java
new file mode 100644
index 0000000..535a69c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/startup/NonStartupInStartupOutlinerTest.java

@@ -0,0 +1,206 @@
+// Copyright (c) 2024, 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.synthesis.SyntheticItemsTestUtils.syntheticNonStartupInStartupOutlineClass;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isAbsent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoAccessModification;
+import com.android.tools.r8.NoMethodStaticizing;
+import com.android.tools.r8.R8TestCompileResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.startup.profile.ExternalStartupClass;
+import com.android.tools.r8.startup.profile.ExternalStartupItem;
+import com.android.tools.r8.startup.profile.ExternalStartupMethod;
+import com.android.tools.r8.startup.utils.StartupTestingUtils;
+import com.android.tools.r8.utils.MethodReferenceUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.Lists;
+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;
+
+@RunWith(Parameterized.class)
+public class NonStartupInStartupOutlinerTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters()
+        .withDexRuntimes()
+        .withApiLevelsStartingAtIncluding(apiLevelWithNativeMultiDexSupport())
+        .build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    List<ExternalStartupItem> startupProfile =
+        Lists.newArrayList(
+            ExternalStartupClass.builder()
+                .setClassReference(Reference.classFromClass(StartupMain.class))
+                .build(),
+            ExternalStartupMethod.builder()
+                .setMethodReference(MethodReferenceUtils.mainMethod(StartupMain.class))
+                .build());
+
+    R8TestCompileResult compileResult =
+        testForR8(parameters.getBackend())
+            .addInnerClasses(getClass())
+            .addKeepMainRules(StartupMain.class, NonStartupMain.class)
+            .addKeepRules(
+                "-keepclassmembers class " + StartupMain.class.getTypeName() + " {",
+                "  void outlinePinnedInstance();",
+                "  void outlinePinnedStatic();",
+                "}")
+            .addOptionsModification(options -> options.getStartupOptions().setEnableOutlining(true))
+            .apply(StartupTestingUtils.addStartupProfile(startupProfile))
+            .allowDiagnosticInfoMessages()
+            .enableInliningAnnotations()
+            .enableNeverClassInliningAnnotations()
+            .enableNoAccessModificationAnnotationsForMembers()
+            .enableNoMethodStaticizingAnnotations()
+            // To allow inspecting the individual outline classes.
+            .noHorizontalClassMergingOfSynthetics()
+            .setMinApi(parameters)
+            .compile()
+            .inspectMultiDex(this::inspectPrimaryDex, this::inspectSecondaryDex);
+
+    compileResult
+        .run(parameters.getRuntime(), StartupMain.class)
+        .assertSuccessWithOutputLines("main");
+
+    compileResult
+        .run(parameters.getRuntime(), NonStartupMain.class)
+        .assertSuccessWithOutputLines(
+            "movePrivate", "moveStatic", "outlinePinnedInstance", "outlinePinnedStatic");
+  }
+
+  private void inspectPrimaryDex(CodeInspector inspector) {
+    assertEquals(1, inspector.allClasses().size());
+
+    ClassSubject startupMainClassSubject = inspector.clazz(StartupMain.class);
+    assertThat(startupMainClassSubject, isPresent());
+    assertEquals(
+        parameters.canInitNewInstanceUsingSuperclassConstructor() ? 4 : 3,
+        startupMainClassSubject.allMethods().size());
+
+    assertThat(startupMainClassSubject.mainMethod(), isPresent());
+    assertThat(startupMainClassSubject.init(), isAbsent());
+    assertThat(startupMainClassSubject.uniqueMethodWithOriginalName("movePrivate"), isAbsent());
+    assertThat(
+        startupMainClassSubject.uniqueMethodWithOriginalName("movePrivateAccessor"), isPresent());
+    assertThat(startupMainClassSubject.uniqueMethodWithOriginalName("moveStatic"), isAbsent());
+    assertThat(
+        startupMainClassSubject.uniqueMethodWithOriginalName("outlinePinnedInstance"), isPresent());
+    assertThat(
+        startupMainClassSubject.uniqueMethodWithOriginalName("outlinePinnedStatic"), isPresent());
+  }
+
+  private void inspectSecondaryDex(CodeInspector inspector) {
+    assertThat(inspector.clazz(NonStartupMain.class), isPresent());
+
+    ClassSubject movePrivateOutline =
+        inspector.clazz(syntheticNonStartupInStartupOutlineClass(StartupMain.class, 0));
+    assertThat(movePrivateOutline, isPresent());
+    assertTrue(
+        movePrivateOutline
+            .uniqueMethod()
+            .streamInstructions()
+            .anyMatch(i -> i.isConstString("movePrivate")));
+
+    ClassSubject outlinePinnedStaticOutline =
+        inspector.clazz(syntheticNonStartupInStartupOutlineClass(StartupMain.class, 1));
+    assertThat(
+        inspector.clazz(syntheticNonStartupInStartupOutlineClass(StartupMain.class, 1)),
+        isPresent());
+    assertTrue(
+        outlinePinnedStaticOutline
+            .uniqueMethod()
+            .streamInstructions()
+            .anyMatch(i -> i.isConstString("outlinePinnedStatic")));
+
+    ClassSubject outlinePinnedInstanceOutline =
+        inspector.clazz(syntheticNonStartupInStartupOutlineClass(StartupMain.class, 2));
+    assertThat(outlinePinnedInstanceOutline, isPresent());
+    assertTrue(
+        outlinePinnedInstanceOutline
+            .uniqueMethod()
+            .streamInstructions()
+            .anyMatch(i -> i.isConstString("outlinePinnedInstance")));
+
+    ClassSubject moveStaticOutline =
+        inspector.clazz(syntheticNonStartupInStartupOutlineClass(StartupMain.class, 3));
+    assertThat(moveStaticOutline, isPresent());
+    assertTrue(
+        moveStaticOutline
+            .uniqueMethod()
+            .streamInstructions()
+            .anyMatch(i -> i.isConstString("moveStatic")));
+
+    assertThat(
+        inspector.clazz(syntheticNonStartupInStartupOutlineClass(StartupMain.class, 4)),
+        isAbsent());
+  }
+
+  @NeverClassInline
+  static class StartupMain {
+
+    public static void main(String[] args) {
+      System.out.println("main");
+    }
+
+    // Moved to synthetic non-startup class.
+    @NeverInline
+    @NoAccessModification
+    @NoMethodStaticizing
+    private void movePrivate() {
+      System.out.println("movePrivate");
+    }
+
+    @NeverInline
+    @NoMethodStaticizing
+    void movePrivateAccessor() {
+      movePrivate();
+    }
+
+    // Moved to synthetic non-startup class.
+    @NeverInline
+    static void moveStatic() {
+      System.out.println("moveStatic");
+    }
+
+    void outlinePinnedInstance() {
+      System.out.println("outlinePinnedInstance");
+    }
+
+    static void outlinePinnedStatic() {
+      System.out.println("outlinePinnedStatic");
+    }
+  }
+
+  static class NonStartupMain {
+
+    public static void main(String[] args) {
+      new StartupMain().movePrivateAccessor();
+      StartupMain.moveStatic();
+      new StartupMain().outlinePinnedInstance();
+      StartupMain.outlinePinnedStatic();
+    }
+  }
+}

diff --git a/src/test/testbase/java/com/android/tools/r8/keepanno/KeepAnnoTestUtils.java b/src/test/testbase/java/com/android/tools/r8/keepanno/KeepAnnoTestUtils.java
index 2e21529..93384e8 100644
--- a/src/test/testbase/java/com/android/tools/r8/keepanno/KeepAnnoTestUtils.java
+++ b/src/test/testbase/java/com/android/tools/r8/keepanno/KeepAnnoTestUtils.java

@@ -61,6 +61,21 @@
     return archive;
   }
 
+  public static List<String> extractRulesFromFiles(
+      List<Path> inputFiles, KeepRuleExtractorOptions extractorOptions) {
+    return extractRulesFromBytes(
+        ListUtils.map(
+            inputFiles,
+            path -> {
+              try {
+                return Files.readAllBytes(path);
+              } catch (IOException e) {
+                throw new RuntimeException(e);
+              }
+            }),
+        extractorOptions);
+  }
+
   public static List<String> extractRules(
       List<Class<?>> inputClasses, KeepRuleExtractorOptions extractorOptions) {
     return extractRulesFromBytes(

diff --git a/src/test/testbase/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java b/src/test/testbase/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java
index b1744ee..de1aec9 100644
--- a/src/test/testbase/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java
+++ b/src/test/testbase/java/com/android/tools/r8/synthesis/SyntheticItemsTestUtils.java

@@ -227,6 +227,15 @@
         originalMethod.getMethodDescriptor());
   }
 
+  public static ClassReference syntheticNonStartupInStartupOutlineClass(Class<?> clazz, int id) {
+    return syntheticNonStartupInStartupOutlineClass(Reference.classFromClass(clazz), id);
+  }
+
+  public static ClassReference syntheticNonStartupInStartupOutlineClass(
+      ClassReference reference, int id) {
+    return syntheticClass(reference, naming.NON_STARTUP_IN_STARTUP_OUTLINE, id);
+  }
+
   public static MethodReference syntheticPrivateInterfaceMethodAsCompanionMethod(Method method) {
     MethodReference originalMethod = Reference.methodFromMethod(method);
     ClassReference companionClassReference =

diff --git a/tools/apk_masseur.py b/tools/apk_masseur.py
index 51e9366..487cb7c 100755
--- a/tools/apk_masseur.py
+++ b/tools/apk_masseur.py

@@ -23,6 +23,10 @@
                       'assets/dexopt/',
                       default=False,
                       action='store_true')
+    parser.add_option('--compress-dex',
+                      help='Whether the dex should be stored compressed',
+                      action='store_true',
+                      default=False)
     parser.add_option('--dex',
                       help='Directory or archive with dex files to use instead '
                       'of those in the apk',
@@ -67,8 +71,8 @@
     return file.endswith('.zip') or file.endswith('.jar')
 
 
-def repack(apk, clear_profile, processed_out, desugared_library_dex, resources,
-           temp, quiet, logging):
+def repack(apk, clear_profile, processed_out, desugared_library_dex,
+           compress_dex, resources, temp, quiet, logging):
     processed_apk = os.path.join(temp, 'processed.apk')
     shutil.copyfile(apk, processed_apk)
 
@@ -119,7 +123,12 @@
         dex_files = glob.glob('*.dex')
         dex_files.sort()
         resource_files = glob.glob(resources) if resources else []
-        cmd = ['zip', '-u', '-0', processed_apk] + dex_files + resource_files
+        cmd = ['zip', '-u']
+        if not compress_dex:
+            cmd.append('-0')
+        cmd.append(processed_apk)
+        cmd.extend(dex_files)
+        cmd.extend(resource_files)
         utils.RunCmd(cmd, quiet=quiet, logging=logging)
     return processed_apk
 
@@ -143,6 +152,7 @@
             clear_profile=False,
             dex=None,
             desugared_library_dex=None,
+            compress_dex=False,
             resources=None,
             out=None,
             adb_options=None,
@@ -159,8 +169,8 @@
         processed_apk = None
         if dex or clear_profile:
             processed_apk = repack(apk, clear_profile, dex,
-                                   desugared_library_dex, resources, temp,
-                                   quiet, logging)
+                                   desugared_library_dex, compress_dex,
+                                   resources, temp, quiet, logging)
         else:
             assert not desugared_library_dex
             utils.Print('Signing original APK without modifying apk',

diff --git a/tools/startup/adb_utils.py b/tools/startup/adb_utils.py
index 6ce19ab..0a4ae59 100755
--- a/tools/startup/adb_utils.py
+++ b/tools/startup/adb_utils.py

@@ -41,10 +41,14 @@
     OFF_UNLOCKED = 2
     ON_LOCKED = 3
     ON_UNLOCKED = 4
+    UNKNOWN = 5
 
     def is_off(self):
         return self == ScreenState.OFF_LOCKED or self == ScreenState.OFF_UNLOCKED
 
+    def is_off_or_unknown(self):
+        return self.is_off() or self.is_unknown()
+
     def is_on(self):
         return self == ScreenState.ON_LOCKED or self == ScreenState.ON_UNLOCKED
 
@@ -54,6 +58,15 @@
     def is_on_and_unlocked(self):
         return self == ScreenState.ON_UNLOCKED
 
+    def is_on_and_unlocked_or_unknown(self):
+        return self.is_on_and_unlocked() or self.is_unknown()
+
+    def is_on_or_unknown(self):
+        return self.is_on() or self.is_unknown()
+
+    def is_unknown(self):
+        return self == ScreenState.UNKNOWN
+
 
 def broadcast(action, component, device_id=None):
     print('Sending broadcast %s' % action)
@@ -147,13 +160,13 @@
 def ensure_screen_on(device_id=None):
     if get_screen_state(device_id).is_off():
         toggle_screen(device_id)
-    assert get_screen_state(device_id).is_on()
+    assert get_screen_state(device_id).is_on_or_unknown()
 
 
 def ensure_screen_off(device_id=None):
     if get_screen_state(device_id).is_on():
         toggle_screen(device_id)
-    assert get_screen_state(device_id).is_off()
+    assert get_screen_state(device_id).is_off_or_unknown()
 
 
 def force_compilation(app_id, device_id=None):
@@ -243,7 +256,11 @@
 
 def get_screen_state(device_id=None):
     cmd = create_adb_cmd('shell dumpsys nfc', device_id)
-    stdout = subprocess.check_output(cmd).decode('utf-8').strip()
+    process_result = subprocess.run(cmd, capture_output=True)
+    stderr = process_result.stderr.decode('utf-8')
+    if "Can't find service: nfc" in stderr:
+        return ScreenState.UNKNOWN
+    stdout = process_result.stdout.decode('utf-8').strip()
     screen_state_value = None
     for line in stdout.splitlines():
         if line.startswith('mScreenState='):
@@ -480,6 +497,8 @@
 def unlock(device_id=None, device_pin=None):
     ensure_screen_on(device_id)
     screen_state = get_screen_state(device_id)
+    if screen_state.is_unknown():
+        return
     assert screen_state.is_on(), 'was %s' % screen_state
     if screen_state.is_on_and_locked():
         if device_pin is not None:

diff --git a/tools/startup/measure_startup.py b/tools/startup/measure_startup.py
index 7e97735..322dfbe 100755
--- a/tools/startup/measure_startup.py
+++ b/tools/startup/measure_startup.py

@@ -138,7 +138,8 @@
 
 
 def teardown_for_run(out_dir, options, teardown_options):
-    assert adb_utils.get_screen_state(options.device_id).is_on_and_unlocked()
+    assert adb_utils.get_screen_state(
+        options.device_id).is_on_and_unlocked_or_unknown()
 
     if options.capture_screen:
         target = os.path.join(out_dir, 'screen.png')
@@ -153,7 +154,8 @@
 
 
 def run(out_dir, options, tmp_dir):
-    assert adb_utils.get_screen_state(options.device_id).is_on_and_unlocked()
+    assert adb_utils.get_screen_state(
+        options.device_id).is_on_and_unlocked_or_unknown()
 
     # Start logcat for time to fully drawn.
     logcat_process = None
@@ -445,7 +447,7 @@
     if options.cooldown == 0:
         teardown_options = adb_utils.prepare_for_interaction_with_device(
             options.device_id, options.device_pin)
-        assert adb_utils.get_screen_state(options.device_id).is_on()
+        assert adb_utils.get_screen_state(options.device_id).is_on_or_unknown()
     else:
         adb_utils.ensure_screen_off(options.device_id)
     return teardown_options