diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 851df61..ce2e296 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -105,6 +105,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;
@@ -706,6 +707,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 {
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/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..d14a8bd 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.isDirect()
+                  && (newType.isInterface() || newType.isStatic() || newType.isVirtual()))
+              || (type.isInterface() && (newType.isStatic() || newType.isVirtual()))
               || (type.isSuper() && newType.isVirtual())
-              || (type.isVirtual() && newType.isInterface())
+              || (type.isVirtual() && (newType.isInterface() || newType.isStatic()))
           : type + " -> " + newType;
       numberOfInvokeOpcodeChanges++;
     } else {
@@ -281,6 +294,17 @@
     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.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..ec788d1 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,8 @@
         return false;
     }
   }
+
+  public static boolean isInvokeVirtual(int opcode) {
+    return opcode == INVOKEVIRTUAL;
+  }
 }
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/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/startup/NonStartupInStartupOutliner.java b/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutliner.java
new file mode 100644
index 0000000..627c46b
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutliner.java
@@ -0,0 +1,382 @@
+// 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;
+
+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()
+              && !hasPrivateOrSuperAccess(method)) {
+            fn.accept(method);
+          }
+        });
+  }
+
+  // TODO(b/275292237): Extend to cover all possible accesses to private items (e.g., consider
+  //  method handles).
+  private boolean hasPrivateOrSuperAccess(ProgramMethod method) {
+    return method.registerCodeReferencesWithResult(
+        new DefaultUseRegistryWithResult<>(appView, method, false) {
+
+          private AppInfoWithClassHierarchy appInfo() {
+            return NonStartupInStartupOutliner.this.appView.appInfo();
+          }
+
+          private void setHasPrivateAccess() {
+            setResult(true);
+          }
+
+          private void setHasSuperAccess() {
+            setResult(true);
+          }
+
+          // 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 && resolvedField.getAccessFlags().isPrivate()) {
+              setHasPrivateAccess();
+            }
+          }
+
+          // 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) {
+            setHasSuperAccess();
+          }
+
+          @Override
+          public void registerInvokeVirtual(DexMethod method) {
+            registerInvokeMethod(appInfo().resolveMethod(method, false));
+          }
+
+          private void registerInvokeMethod(MethodResolutionResult resolutionResult) {
+            DexClassAndMethod resolvedMethod = resolutionResult.getResolutionPair();
+            if (resolvedMethod != null && resolvedMethod.getAccessFlags().isPrivate()) {
+              setHasPrivateAccess();
+            }
+          }
+        });
+  }
+
+  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 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 =
+                              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..086eab6
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/startup/NonStartupInStartupOutlinerLens.java
@@ -0,0 +1,59 @@
+// 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 previousMethod, InvokeType type) {
+    if (newMethod.isIdenticalTo(previousMethod)) {
+      return type;
+    }
+    return 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/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/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/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 =