diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
index e2d9423..2f68a94 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
@@ -25,7 +25,7 @@
 import com.android.tools.r8.dex.VirtualFile.ItemUseInfo;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.experimental.startup.StartupCompleteness;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.features.FeatureSplitConfiguration.DataResourceProvidersAndConsumer;
 import com.android.tools.r8.graph.AppServices;
 import com.android.tools.r8.graph.AppView;
@@ -241,13 +241,13 @@
       // Retrieve the startup order for writing the app. In R8, the startup order is created
       // up-front to guide optimizations through-out the compilation. In D8, the startup
       // order is only used for writing the app, so we create it here for the first time.
-      StartupOrder startupOrder =
+      StartupProfile startupProfile =
           appView.appInfo().hasClassHierarchy()
               ? appView.getStartupOrder()
-              : StartupOrder.createInitialStartupOrderForD8(appView);
+              : StartupProfile.createInitialStartupOrderForD8(appView);
       distributor =
           new VirtualFile.FillFilesDistributor(
-              this, classes, options, executorService, startupOrder);
+              this, classes, options, executorService, startupProfile);
     }
 
     List<VirtualFile> virtualFiles = distributor.run();
diff --git a/src/main/java/com/android/tools/r8/dex/MixedSectionLayoutStrategy.java b/src/main/java/com/android/tools/r8/dex/MixedSectionLayoutStrategy.java
index 13a4a2c..da63c75 100644
--- a/src/main/java/com/android/tools/r8/dex/MixedSectionLayoutStrategy.java
+++ b/src/main/java/com/android/tools/r8/dex/MixedSectionLayoutStrategy.java
@@ -5,7 +5,7 @@
 package com.android.tools.r8.dex;
 
 import com.android.tools.r8.dex.FileWriter.MixedSectionOffsets;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexAnnotationDirectory;
@@ -22,21 +22,21 @@
 
   public static MixedSectionLayoutStrategy create(
       AppView<?> appView, MixedSectionOffsets mixedSectionOffsets, VirtualFile virtualFile) {
-    StartupOrder startupOrderForWriting;
+    StartupProfile startupProfileForWriting;
     if (virtualFile.getStartupOrder().isEmpty()) {
-      startupOrderForWriting = StartupOrder.empty();
+      startupProfileForWriting = StartupProfile.empty();
     } else {
       assert virtualFile.getId() == 0;
-      startupOrderForWriting =
+      startupProfileForWriting =
           appView.options().getStartupOptions().isStartupLayoutOptimizationsEnabled()
               ? virtualFile.getStartupOrder().toStartupOrderForWriting(appView)
-              : StartupOrder.empty();
+              : StartupProfile.empty();
     }
     MixedSectionLayoutStrategy mixedSectionLayoutStrategy =
-        startupOrderForWriting.isEmpty()
+        startupProfileForWriting.isEmpty()
             ? new DefaultMixedSectionLayoutStrategy(appView, mixedSectionOffsets)
             : new StartupMixedSectionLayoutStrategy(
-                appView, mixedSectionOffsets, startupOrderForWriting, virtualFile);
+                appView, mixedSectionOffsets, startupProfileForWriting, virtualFile);
     return wrapForTesting(appView, mixedSectionLayoutStrategy, virtualFile);
   }
 
diff --git a/src/main/java/com/android/tools/r8/dex/StartupMixedSectionLayoutStrategy.java b/src/main/java/com/android/tools/r8/dex/StartupMixedSectionLayoutStrategy.java
index ffbbc4f..afab1b3 100644
--- a/src/main/java/com/android/tools/r8/dex/StartupMixedSectionLayoutStrategy.java
+++ b/src/main/java/com/android/tools/r8/dex/StartupMixedSectionLayoutStrategy.java
@@ -5,7 +5,7 @@
 package com.android.tools.r8.dex;
 
 import com.android.tools.r8.dex.FileWriter.MixedSectionOffsets;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.experimental.startup.profile.StartupClass;
 import com.android.tools.r8.experimental.startup.profile.StartupItem;
 import com.android.tools.r8.experimental.startup.profile.StartupMethod;
@@ -36,7 +36,7 @@
 
 public class StartupMixedSectionLayoutStrategy extends DefaultMixedSectionLayoutStrategy {
 
-  private final StartupOrder startupOrderForWriting;
+  private final StartupProfile startupProfileForWriting;
 
   private final LinkedHashSet<DexAnnotation> annotationLayout;
   private final LinkedHashSet<DexAnnotationDirectory> annotationDirectoryLayout;
@@ -51,10 +51,10 @@
   public StartupMixedSectionLayoutStrategy(
       AppView<?> appView,
       MixedSectionOffsets mixedSectionOffsets,
-      StartupOrder startupOrderForWriting,
+      StartupProfile startupProfileForWriting,
       VirtualFile virtualFile) {
     super(appView, mixedSectionOffsets);
-    this.startupOrderForWriting = startupOrderForWriting;
+    this.startupProfileForWriting = startupProfileForWriting;
 
     // Initialize startup layouts.
     this.annotationLayout = new LinkedHashSet<>(mixedSectionOffsets.getAnnotations().size());
@@ -82,7 +82,7 @@
             virtualFile.classes().size());
     LensCodeRewriterUtils rewriter = new LensCodeRewriterUtils(appView, true);
     StartupIndexedItemCollection indexedItemCollection = new StartupIndexedItemCollection();
-    for (StartupItem startupItem : startupOrderForWriting.getItems()) {
+    for (StartupItem startupItem : startupProfileForWriting.getItems()) {
       startupItem.accept(
           startupClass ->
               collectStartupItems(startupClass, indexedItemCollection, virtualFileDefinitions),
diff --git a/src/main/java/com/android/tools/r8/dex/VirtualFile.java b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
index ef76e8a..aea0add 100644
--- a/src/main/java/com/android/tools/r8/dex/VirtualFile.java
+++ b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
@@ -9,7 +9,7 @@
 import com.android.tools.r8.debuginfo.DebugRepresentation;
 import com.android.tools.r8.errors.DexFileOverflowDiagnostic;
 import com.android.tools.r8.errors.InternalCompilerError;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.features.ClassToFeatureSplitMap;
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
@@ -68,28 +68,28 @@
   public final VirtualFileIndexedItemCollection indexedItems;
   private final IndexedItemTransaction transaction;
   private final FeatureSplit featureSplit;
-  private final StartupOrder startupOrder;
+  private final StartupProfile startupProfile;
 
   private final DexString primaryClassDescriptor;
   private final DexString primaryClassSynthesizingContextDescriptor;
   private DebugRepresentation debugRepresentation;
 
   VirtualFile(int id, AppView<?> appView) {
-    this(id, appView, null, null, StartupOrder.empty());
+    this(id, appView, null, null, StartupProfile.empty());
   }
 
   VirtualFile(
       int id,
       AppView<?> appView,
       FeatureSplit featureSplit) {
-    this(id, appView, null, featureSplit, StartupOrder.empty());
+    this(id, appView, null, featureSplit, StartupProfile.empty());
   }
 
   private VirtualFile(
       int id,
       AppView<?> appView,
       DexProgramClass primaryClass) {
-    this(id, appView, primaryClass, null, StartupOrder.empty());
+    this(id, appView, primaryClass, null, StartupProfile.empty());
   }
 
   private VirtualFile(
@@ -97,12 +97,12 @@
       AppView<?> appView,
       DexProgramClass primaryClass,
       FeatureSplit featureSplit,
-      StartupOrder startupOrder) {
+      StartupProfile startupProfile) {
     this.id = id;
     this.indexedItems = new VirtualFileIndexedItemCollection(appView);
     this.transaction = new IndexedItemTransaction(indexedItems, appView);
     this.featureSplit = featureSplit;
-    this.startupOrder = startupOrder;
+    this.startupProfile = startupProfile;
     if (primaryClass == null) {
       primaryClassDescriptor = null;
       primaryClassSynthesizingContextDescriptor = null;
@@ -137,8 +137,8 @@
     return featureSplit;
   }
 
-  public StartupOrder getStartupOrder() {
-    return startupOrder;
+  public StartupProfile getStartupOrder() {
+    return startupProfile;
   }
 
   public String getPrimaryClassDescriptor() {
@@ -379,14 +379,14 @@
         ApplicationWriter writer,
         Collection<DexProgramClass> classes,
         InternalOptions options,
-        StartupOrder startupOrder) {
+        StartupProfile startupProfile) {
       super(writer);
       this.options = options;
       this.classes = SetUtils.newIdentityHashSet(classes);
 
       // Create the primary dex file. The distribution will add more if needed. We use the startup
       // order (if any) to guide the layout of the primary dex file.
-      mainDexFile = new VirtualFile(0, appView, null, null, startupOrder);
+      mainDexFile = new VirtualFile(0, appView, null, null, startupProfile);
       assert virtualFiles.isEmpty();
       virtualFiles.add(mainDexFile);
       addMarkers(mainDexFile);
@@ -449,7 +449,8 @@
     }
 
     protected void addFeatureSplitFiles(
-        Map<FeatureSplit, Set<DexProgramClass>> featureSplitClasses, StartupOrder startupOrder) {
+        Map<FeatureSplit, Set<DexProgramClass>> featureSplitClasses,
+        StartupProfile startupProfile) {
       if (featureSplitClasses.isEmpty()) {
         return;
       }
@@ -472,7 +473,7 @@
                 appView,
                 featureSplitSetEntry.getValue(),
                 originalNames,
-                startupOrder,
+                startupProfile,
                 nextFileId)
             .run();
       }
@@ -482,17 +483,17 @@
   public static class FillFilesDistributor extends DistributorBase {
 
     private final ExecutorService executorService;
-    private final StartupOrder startupOrder;
+    private final StartupProfile startupProfile;
 
     FillFilesDistributor(
         ApplicationWriter writer,
         Collection<DexProgramClass> classes,
         InternalOptions options,
         ExecutorService executorService,
-        StartupOrder startupOrder) {
-      super(writer, classes, options, startupOrder);
+        StartupProfile startupProfile) {
+      super(writer, classes, options, startupProfile);
       this.executorService = executorService;
-      this.startupOrder = startupOrder;
+      this.startupProfile = startupProfile;
     }
 
     @Override
@@ -538,11 +539,11 @@
                 appView,
                 classes,
                 originalNames,
-                startupOrder,
+                startupProfile,
                 nextFileId)
             .run();
       }
-      addFeatureSplitFiles(featureSplitClasses, startupOrder);
+      addFeatureSplitFiles(featureSplitClasses, startupProfile);
 
       assert totalClassNumber == virtualFiles.stream().mapToInt(dex -> dex.classes().size()).sum();
       return virtualFiles;
@@ -552,7 +553,7 @@
   public static class MonoDexDistributor extends DistributorBase {
     MonoDexDistributor(
         ApplicationWriter writer, Collection<DexProgramClass> classes, InternalOptions options) {
-      super(writer, classes, options, StartupOrder.empty());
+      super(writer, classes, options, StartupProfile.empty());
     }
 
     @Override
@@ -568,7 +569,7 @@
       if (options.featureSplitConfiguration != null) {
         if (!featureSplitClasses.isEmpty()) {
           // TODO(141334414): Figure out if we allow multidex in features even when mono-dexing
-          addFeatureSplitFiles(featureSplitClasses, StartupOrder.empty());
+          addFeatureSplitFiles(featureSplitClasses, StartupProfile.empty());
         }
       }
       return virtualFiles;
@@ -1278,11 +1279,11 @@
       public static PackageSplitClassPartioning create(
           Collection<DexProgramClass> classes,
           Map<DexProgramClass, String> originalNames,
-          StartupOrder startupOrder) {
+          StartupProfile startupProfile) {
         return create(
             classes,
             getClassesByPackageComparator(originalNames),
-            getStartupClassPredicate(startupOrder));
+            getStartupClassPredicate(startupProfile));
       }
 
       private static PackageSplitClassPartioning create(
@@ -1333,8 +1334,8 @@
       }
 
       private static Predicate<DexProgramClass> getStartupClassPredicate(
-          StartupOrder startupOrder) {
-        return clazz -> startupOrder.contains(clazz.getType());
+          StartupProfile startupProfile) {
+        return clazz -> startupProfile.contains(clazz.getType());
       }
 
       public List<DexProgramClass> getStartupClasses() {
@@ -1370,10 +1371,10 @@
         AppView<?> appView,
         Collection<DexProgramClass> classes,
         Map<DexProgramClass, String> originalNames,
-        StartupOrder startupOrder,
+        StartupProfile startupProfile,
         IntBox nextFileId) {
       this.classPartioning =
-          PackageSplitClassPartioning.create(classes, originalNames, startupOrder);
+          PackageSplitClassPartioning.create(classes, originalNames, startupProfile);
       this.originalNames = originalNames;
       this.dexItemFactory = appView.dexItemFactory();
       this.options = appView.options();
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupOrder.java b/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupProfile.java
similarity index 80%
rename from src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupOrder.java
rename to src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupProfile.java
index ad4d364..36e470b 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupOrder.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/EmptyStartupProfile.java
@@ -14,9 +14,9 @@
 import java.util.Collection;
 import java.util.Collections;
 
-public class EmptyStartupOrder extends StartupOrder {
+public class EmptyStartupProfile extends StartupProfile {
 
-  EmptyStartupOrder() {}
+  EmptyStartupProfile() {}
 
   @Override
   public boolean contains(DexMethod method) {
@@ -39,17 +39,17 @@
   }
 
   @Override
-  public EmptyStartupOrder rewrittenWithLens(GraphLens graphLens) {
+  public EmptyStartupProfile rewrittenWithLens(GraphLens graphLens) {
     return this;
   }
 
   @Override
-  public StartupOrder toStartupOrderForWriting(AppView<?> appView) {
+  public EmptyStartupProfile toStartupOrderForWriting(AppView<?> appView) {
     return this;
   }
 
   @Override
-  public EmptyStartupOrder withoutPrunedItems(
+  public EmptyStartupProfile withoutPrunedItems(
       PrunedItems prunedItems, SyntheticItems syntheticItems) {
     return this;
   }
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/StartupCompleteness.java b/src/main/java/com/android/tools/r8/experimental/startup/StartupCompleteness.java
index 456b3a2..68764cd 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/StartupCompleteness.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/StartupCompleteness.java
@@ -20,14 +20,14 @@
 public class StartupCompleteness {
 
   private final AppView<?> appView;
-  private final StartupOrder startupOrder;
+  private final StartupProfile startupProfile;
 
   private StartupCompleteness(AppView<?> appView) {
     this.appView = appView;
-    this.startupOrder =
+    this.startupProfile =
         appView.hasClassHierarchy()
             ? appView.getStartupOrder()
-            : StartupOrder.createInitialStartupOrder(appView.options(), null);
+            : StartupProfile.createInitialStartupOrder(appView.options(), null);
   }
 
   /**
@@ -72,7 +72,7 @@
 
   private Set<DexReference> computeStartupItems() {
     Set<DexReference> startupItems = Sets.newIdentityHashSet();
-    for (StartupItem startupItem : startupOrder.getItems()) {
+    for (StartupItem startupItem : startupProfile.getItems()) {
       startupItem.accept(
           startupClass -> startupItems.add(startupClass.getReference()),
           startupMethod -> startupItems.add(startupMethod.getReference()));
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/StartupOrder.java b/src/main/java/com/android/tools/r8/experimental/startup/StartupOrder.java
deleted file mode 100644
index e1e8408..0000000
--- a/src/main/java/com/android/tools/r8/experimental/startup/StartupOrder.java
+++ /dev/null
@@ -1,66 +0,0 @@
-// Copyright (c) 2022, 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.experimental.startup;
-
-import com.android.tools.r8.experimental.startup.profile.StartupItem;
-import com.android.tools.r8.experimental.startup.profile.StartupProfile;
-import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexApplication;
-import com.android.tools.r8.graph.DexDefinitionSupplier;
-import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexReference;
-import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.graph.GraphLens;
-import com.android.tools.r8.graph.PrunedItems;
-import com.android.tools.r8.synthesis.SyntheticItems;
-import com.android.tools.r8.utils.InternalOptions;
-import java.util.Collection;
-import java.util.LinkedHashMap;
-
-public abstract class StartupOrder {
-
-  StartupOrder() {}
-
-  public static StartupOrder createInitialStartupOrder(
-      InternalOptions options, DexDefinitionSupplier definitions) {
-    StartupProfile startupProfile = StartupProfile.parseStartupProfile(options, definitions);
-    if (startupProfile == null || startupProfile.getStartupItems().isEmpty()) {
-      return empty();
-    }
-    LinkedHashMap<DexReference, StartupItem> startupItems =
-        new LinkedHashMap<>(startupProfile.size());
-    for (StartupItem startupItem : startupProfile.getStartupItems()) {
-      startupItems.put(startupItem.getReference(), startupItem);
-    }
-    return new NonEmptyStartupOrder(new LinkedHashMap<>(startupItems));
-  }
-
-  public static StartupOrder createInitialStartupOrderForD8(AppView<?> appView) {
-    return createInitialStartupOrder(appView.options(), appView);
-  }
-
-  public static StartupOrder createInitialStartupOrderForR8(DexApplication application) {
-    return createInitialStartupOrder(application.options, application);
-  }
-
-  public static StartupOrder empty() {
-    return new EmptyStartupOrder();
-  }
-
-  public abstract boolean contains(DexMethod method);
-
-  public abstract boolean contains(DexType type);
-
-  public abstract Collection<StartupItem> getItems();
-
-  public abstract boolean isEmpty();
-
-  public abstract StartupOrder rewrittenWithLens(GraphLens graphLens);
-
-  public abstract StartupOrder toStartupOrderForWriting(AppView<?> appView);
-
-  public abstract StartupOrder withoutPrunedItems(
-      PrunedItems prunedItems, SyntheticItems syntheticItems);
-}
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/profile/StartupProfile.java b/src/main/java/com/android/tools/r8/experimental/startup/StartupProfile.java
similarity index 66%
rename from src/main/java/com/android/tools/r8/experimental/startup/profile/StartupProfile.java
rename to src/main/java/com/android/tools/r8/experimental/startup/StartupProfile.java
index f2f66a2..67a2116 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/profile/StartupProfile.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/StartupProfile.java
@@ -2,11 +2,22 @@
 // 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.experimental.startup.profile;
+package com.android.tools.r8.experimental.startup;
 
 import com.android.tools.r8.TextInputStream;
+import com.android.tools.r8.experimental.startup.profile.NonEmptyStartupProfile;
+import com.android.tools.r8.experimental.startup.profile.StartupClass;
+import com.android.tools.r8.experimental.startup.profile.StartupItem;
+import com.android.tools.r8.experimental.startup.profile.StartupMethod;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexReference;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.GraphLens;
+import com.android.tools.r8.graph.PrunedItems;
 import com.android.tools.r8.profile.art.ArtProfileBuilderUtils;
 import com.android.tools.r8.profile.art.HumanReadableArtProfileParser;
 import com.android.tools.r8.profile.art.HumanReadableArtProfileParserBuilder;
@@ -15,20 +26,21 @@
 import com.android.tools.r8.startup.StartupProfileBuilder;
 import com.android.tools.r8.startup.StartupProfileProvider;
 import com.android.tools.r8.startup.diagnostic.MissingStartupProfileItemsDiagnostic;
+import com.android.tools.r8.synthesis.SyntheticItems;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Reporter;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.LinkedHashSet;
+import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.function.Consumer;
 
-public class StartupProfile {
+public abstract class StartupProfile {
 
-  private final LinkedHashSet<StartupItem> startupItems;
+  protected StartupProfile() {}
 
-  StartupProfile(LinkedHashSet<StartupItem> startupItems) {
-    this.startupItems = startupItems;
+  public static Builder builder() {
+    return new Builder();
   }
 
   public static Builder builder(
@@ -38,12 +50,37 @@
     return new Builder(options, missingItemsDiagnosticBuilder, startupProfileProvider);
   }
 
-  public static StartupProfile merge(Collection<StartupProfile> startupProfiles) {
-    LinkedHashSet<StartupItem> mergedStartupItems = new LinkedHashSet<>();
-    for (StartupProfile startupProfile : startupProfiles) {
-      mergedStartupItems.addAll(startupProfile.getStartupItems());
+  public static StartupProfile createInitialStartupOrder(
+      InternalOptions options, DexDefinitionSupplier definitions) {
+    StartupProfile startupProfile = StartupProfile.parseStartupProfile(options, definitions);
+    if (startupProfile == null || startupProfile.isEmpty()) {
+      return empty();
     }
-    return new StartupProfile(mergedStartupItems);
+    StartupProfile.Builder builder = StartupProfile.builder();
+    for (StartupItem startupItem : startupProfile.getItems()) {
+      builder.addStartupItem(startupItem);
+    }
+    return builder.build();
+  }
+
+  public static StartupProfile createInitialStartupOrderForD8(AppView<?> appView) {
+    return createInitialStartupOrder(appView.options(), appView);
+  }
+
+  public static StartupProfile createInitialStartupOrderForR8(DexApplication application) {
+    return createInitialStartupOrder(application.options, application);
+  }
+
+  public static StartupProfile empty() {
+    return new EmptyStartupProfile();
+  }
+
+  public static StartupProfile merge(Collection<StartupProfile> startupProfiles) {
+    Builder builder = builder();
+    for (StartupProfile startupProfile : startupProfiles) {
+      startupProfile.getItems().forEach(builder::addStartupItem);
+    }
+    return builder.build();
   }
 
   /**
@@ -73,8 +110,9 @@
       MissingStartupProfileItemsDiagnostic.Builder missingItemsDiagnosticBuilder =
           new MissingStartupProfileItemsDiagnostic.Builder(definitions)
               .setOrigin(startupProfileProvider.getOrigin());
-      StartupProfile.Builder startupProfileBuilder =
-          StartupProfile.builder(options, missingItemsDiagnosticBuilder, startupProfileProvider);
+      NonEmptyStartupProfile.Builder startupProfileBuilder =
+          NonEmptyStartupProfile.builder(
+              options, missingItemsDiagnosticBuilder, startupProfileProvider);
       startupProfileProvider.getStartupProfile(startupProfileBuilder);
       startupProfiles.add(startupProfileBuilder.build());
       if (missingItemsDiagnosticBuilder.hasMissingStartupItems()) {
@@ -84,13 +122,20 @@
     return StartupProfile.merge(startupProfiles);
   }
 
-  public Collection<StartupItem> getStartupItems() {
-    return startupItems;
-  }
+  public abstract boolean contains(DexMethod method);
 
-  public int size() {
-    return startupItems.size();
-  }
+  public abstract boolean contains(DexType type);
+
+  public abstract Collection<StartupItem> getItems();
+
+  public abstract boolean isEmpty();
+
+  public abstract StartupProfile rewrittenWithLens(GraphLens graphLens);
+
+  public abstract StartupProfile toStartupOrderForWriting(AppView<?> appView);
+
+  public abstract StartupProfile withoutPrunedItems(
+      PrunedItems prunedItems, SyntheticItems syntheticItems);
 
   public static class Builder implements StartupProfileBuilder {
 
@@ -99,7 +144,14 @@
     private Reporter reporter;
     private final StartupProfileProvider startupProfileProvider;
 
-    private final LinkedHashSet<StartupItem> startupItems = new LinkedHashSet<>();
+    private final LinkedHashMap<DexReference, StartupItem> startupItems = new LinkedHashMap<>();
+
+    Builder() {
+      this.dexItemFactory = null;
+      this.missingItemsDiagnosticBuilder = null;
+      this.reporter = null;
+      this.startupProfileProvider = null;
+    }
 
     Builder(
         InternalOptions options,
@@ -149,8 +201,8 @@
       return this;
     }
 
-    private Builder addStartupItem(StartupItem startupItem) {
-      this.startupItems.add(startupItem);
+    public Builder addStartupItem(StartupItem startupItem) {
+      startupItems.put(startupItem.getReference(), startupItem);
       return this;
     }
 
@@ -169,7 +221,10 @@
     }
 
     public StartupProfile build() {
-      return new StartupProfile(startupItems);
+      if (startupItems.isEmpty()) {
+        return empty();
+      }
+      return new NonEmptyStartupProfile(startupItems);
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/StartupProfileProviderUtils.java b/src/main/java/com/android/tools/r8/experimental/startup/StartupProfileProviderUtils.java
index 6e288b5..a815ecb 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/StartupProfileProviderUtils.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/StartupProfileProviderUtils.java
@@ -6,8 +6,8 @@
 
 import static com.android.tools.r8.utils.ConsumerUtils.emptyConsumer;
 
+import com.android.tools.r8.experimental.startup.profile.NonEmptyStartupProfile;
 import com.android.tools.r8.experimental.startup.profile.StartupItem;
-import com.android.tools.r8.experimental.startup.profile.StartupProfile;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.origin.PathOrigin;
 import com.android.tools.r8.profile.art.HumanReadableArtProfileParserBuilder;
@@ -54,15 +54,16 @@
     // Do not report missing items.
     MissingStartupProfileItemsDiagnostic.Builder missingItemsDiagnosticBuilder =
         MissingStartupProfileItemsDiagnostic.Builder.nop();
-    StartupProfile.Builder startupProfileBuilder =
-        StartupProfile.builder(options, missingItemsDiagnosticBuilder, startupProfileProvider);
+    NonEmptyStartupProfile.Builder startupProfileBuilder =
+        NonEmptyStartupProfile.builder(
+            options, missingItemsDiagnosticBuilder, startupProfileProvider);
     // Do not report warnings for lines that cannot be parsed.
     startupProfileBuilder.setIgnoreWarnings();
     // Populate the startup profile builder.
     startupProfileProvider.getStartupProfile(startupProfileBuilder);
     // Serialize the startup items.
     StringBuilder resultBuilder = new StringBuilder();
-    for (StartupItem startupItem : startupProfileBuilder.build().getStartupItems()) {
+    for (StartupItem startupItem : startupProfileBuilder.build().getItems()) {
       startupItem.write(resultBuilder);
       resultBuilder.append('\n');
     }
diff --git a/src/main/java/com/android/tools/r8/experimental/startup/NonEmptyStartupOrder.java b/src/main/java/com/android/tools/r8/experimental/startup/profile/NonEmptyStartupProfile.java
similarity index 88%
rename from src/main/java/com/android/tools/r8/experimental/startup/NonEmptyStartupOrder.java
rename to src/main/java/com/android/tools/r8/experimental/startup/profile/NonEmptyStartupProfile.java
index e67e98a..8ebd821 100644
--- a/src/main/java/com/android/tools/r8/experimental/startup/NonEmptyStartupOrder.java
+++ b/src/main/java/com/android/tools/r8/experimental/startup/profile/NonEmptyStartupProfile.java
@@ -2,11 +2,9 @@
 // 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.experimental.startup;
+package com.android.tools.r8.experimental.startup.profile;
 
-import com.android.tools.r8.experimental.startup.profile.StartupClass;
-import com.android.tools.r8.experimental.startup.profile.StartupItem;
-import com.android.tools.r8.experimental.startup.profile.StartupMethod;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -18,11 +16,11 @@
 import java.util.Collection;
 import java.util.LinkedHashMap;
 
-public class NonEmptyStartupOrder extends StartupOrder {
+public class NonEmptyStartupProfile extends StartupProfile {
 
   private final LinkedHashMap<DexReference, StartupItem> startupItems;
 
-  NonEmptyStartupOrder(LinkedHashMap<DexReference, StartupItem> startupItems) {
+  public NonEmptyStartupProfile(LinkedHashMap<DexReference, StartupItem> startupItems) {
     assert !startupItems.isEmpty();
     this.startupItems = startupItems;
   }
@@ -48,7 +46,7 @@
   }
 
   @Override
-  public StartupOrder rewrittenWithLens(GraphLens graphLens) {
+  public StartupProfile rewrittenWithLens(GraphLens graphLens) {
     LinkedHashMap<DexReference, StartupItem> rewrittenStartupItems =
         new LinkedHashMap<>(startupItems.size());
     for (StartupItem startupItem : startupItems.values()) {
@@ -72,6 +70,10 @@
     return createNonEmpty(rewrittenStartupItems);
   }
 
+  public int size() {
+    return startupItems.size();
+  }
+
   /**
    * This is called to process the startup order before computing the startup layouts.
    *
@@ -92,7 +94,7 @@
    * </ul>
    */
   @Override
-  public StartupOrder toStartupOrderForWriting(AppView<?> appView) {
+  public StartupProfile toStartupOrderForWriting(AppView<?> appView) {
     LinkedHashMap<DexReference, StartupItem> rewrittenStartupItems =
         new LinkedHashMap<>(startupItems.size());
     for (StartupItem startupItem : startupItems.values()) {
@@ -147,7 +149,7 @@
   }
 
   @Override
-  public StartupOrder withoutPrunedItems(PrunedItems prunedItems, SyntheticItems syntheticItems) {
+  public StartupProfile withoutPrunedItems(PrunedItems prunedItems, SyntheticItems syntheticItems) {
     LinkedHashMap<DexReference, StartupItem> rewrittenStartupItems =
         new LinkedHashMap<>(startupItems.size());
     for (StartupItem startupItem : startupItems.values()) {
@@ -168,11 +170,11 @@
     return createNonEmpty(rewrittenStartupItems);
   }
 
-  private StartupOrder createNonEmpty(LinkedHashMap<DexReference, StartupItem> startupItems) {
+  private StartupProfile createNonEmpty(LinkedHashMap<DexReference, StartupItem> startupItems) {
     if (startupItems.isEmpty()) {
       assert false;
       return empty();
     }
-    return new NonEmptyStartupOrder(startupItems);
+    return new NonEmptyStartupProfile(startupItems);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java b/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java
index cb6c4ac..88d2a35 100644
--- a/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java
+++ b/src/main/java/com/android/tools/r8/features/ClassToFeatureSplitMap.java
@@ -8,7 +8,7 @@
 import com.android.tools.r8.ProgramResource;
 import com.android.tools.r8.ProgramResourceProvider;
 import com.android.tools.r8.ResourceException;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexItemFactory;
@@ -112,11 +112,11 @@
   public Map<FeatureSplit, Set<DexProgramClass>> getFeatureSplitClasses(
       Set<DexProgramClass> classes,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
     Map<FeatureSplit, Set<DexProgramClass>> result = new IdentityHashMap<>();
     for (DexProgramClass clazz : classes) {
-      FeatureSplit featureSplit = getFeatureSplit(clazz, options, startupOrder, syntheticItems);
+      FeatureSplit featureSplit = getFeatureSplit(clazz, options, startupProfile, syntheticItems);
       if (featureSplit != null && !featureSplit.isBase()) {
         result.computeIfAbsent(featureSplit, ignore -> Sets.newIdentityHashSet()).add(clazz);
       }
@@ -133,9 +133,9 @@
   public FeatureSplit getFeatureSplit(
       ProgramDefinition definition,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
-    return getFeatureSplit(definition.getContextType(), options, startupOrder, syntheticItems);
+    return getFeatureSplit(definition.getContextType(), options, startupProfile, syntheticItems);
   }
 
   public FeatureSplit getFeatureSplit(
@@ -147,11 +147,11 @@
   public FeatureSplit getFeatureSplit(
       DexType type,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
     if (syntheticItems == null) {
       // Called from AndroidApp.dumpProgramResources().
-      assert startupOrder.isEmpty();
+      assert startupProfile.isEmpty();
       return classToFeatureSplitMap.getOrDefault(type, FeatureSplit.BASE);
     }
     FeatureSplit feature;
@@ -162,7 +162,7 @@
         // the shared utility class in case it is used during startup. The use of base startup
         // allows for merging startup classes with the shared utility class, however, which could be
         // bad for startup if the shared utility class is not used during startup.
-        return startupOrder.isEmpty()
+        return startupProfile.isEmpty()
                 || options.getStartupOptions().isStartupBoundaryOptimizationsEnabled()
             ? FeatureSplit.BASE
             : FeatureSplit.BASE_STARTUP;
@@ -175,7 +175,7 @@
       feature = classToFeatureSplitMap.getOrDefault(type, FeatureSplit.BASE);
     }
     if (feature.isBase()) {
-      return !startupOrder.contains(type)
+      return !startupProfile.contains(type)
               || options.getStartupOptions().isStartupBoundaryOptimizationsEnabled()
           ? FeatureSplit.BASE
           : FeatureSplit.BASE_STARTUP;
@@ -199,9 +199,9 @@
   public boolean isInBase(
       DexProgramClass clazz,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
-    return getFeatureSplit(clazz, options, startupOrder, syntheticItems).isBase();
+    return getFeatureSplit(clazz, options, startupProfile, syntheticItems).isBase();
   }
 
   public boolean isInBaseOrSameFeatureAs(
@@ -216,10 +216,10 @@
       DexProgramClass clazz,
       ProgramDefinition context,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
     return isInBaseOrSameFeatureAs(
-        clazz.getContextType(), context, options, startupOrder, syntheticItems);
+        clazz.getContextType(), context, options, startupProfile, syntheticItems);
   }
 
   public boolean isInBaseOrSameFeatureAs(
@@ -234,19 +234,19 @@
       DexType clazz,
       ProgramDefinition context,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
-    FeatureSplit split = getFeatureSplit(clazz, options, startupOrder, syntheticItems);
+    FeatureSplit split = getFeatureSplit(clazz, options, startupProfile, syntheticItems);
     return split.isBase()
-        || split == getFeatureSplit(context, options, startupOrder, syntheticItems);
+        || split == getFeatureSplit(context, options, startupProfile, syntheticItems);
   }
 
   public boolean isInFeature(
       DexProgramClass clazz,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
-    return !isInBase(clazz, options, startupOrder, syntheticItems);
+    return !isInBase(clazz, options, startupProfile, syntheticItems);
   }
 
   public boolean isInSameFeatureOrBothInSameBase(
@@ -259,10 +259,10 @@
       ProgramMethod a,
       ProgramMethod b,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
     return isInSameFeatureOrBothInSameBase(
-        a.getHolder(), b.getHolder(), options, startupOrder, syntheticItems);
+        a.getHolder(), b.getHolder(), options, startupProfile, syntheticItems);
   }
 
   public boolean isInSameFeatureOrBothInSameBase(
@@ -275,10 +275,10 @@
       DexProgramClass a,
       DexProgramClass b,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
-    return getFeatureSplit(a, options, startupOrder, syntheticItems)
-        == getFeatureSplit(b, options, startupOrder, syntheticItems);
+    return getFeatureSplit(a, options, startupProfile, syntheticItems)
+        == getFeatureSplit(b, options, startupProfile, syntheticItems);
   }
 
   public ClassToFeatureSplitMap rewrittenWithLens(GraphLens lens) {
diff --git a/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java b/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java
index d88be72..bf3fc09 100644
--- a/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java
+++ b/src/main/java/com/android/tools/r8/features/FeatureSplitBoundaryOptimizationUtils.java
@@ -5,7 +5,7 @@
 package com.android.tools.r8.features;
 
 import com.android.tools.r8.FeatureSplit;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexEncodedMember;
@@ -44,10 +44,10 @@
       ProgramDefinition accessor,
       ClassToFeatureSplitMap classToFeatureSplitMap,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
     return classToFeatureSplitMap.isInBaseOrSameFeatureAs(
-        accessedClass, accessor, options, startupOrder, syntheticItems);
+        accessedClass, accessor, options, startupProfile, syntheticItems);
   }
 
   public static boolean isSafeForInlining(
@@ -66,32 +66,32 @@
     }
 
     // Next perform startup checks.
-    StartupOrder startupOrder = appView.getStartupOrder();
-    OptionalBool callerIsStartupMethod = isStartupMethod(caller, startupOrder);
+    StartupProfile startupProfile = appView.getStartupOrder();
+    OptionalBool callerIsStartupMethod = isStartupMethod(caller, startupProfile);
     if (callerIsStartupMethod.isTrue()) {
       // If the caller is a startup method, then only allow inlining if the callee is also a startup
       // method.
-      if (isStartupMethod(callee, startupOrder).isFalse()) {
+      if (isStartupMethod(callee, startupProfile).isFalse()) {
         return false;
       }
     } else if (callerIsStartupMethod.isFalse()) {
       // If the caller is not a startup method, then only allow inlining if the caller is not a
       // startup class or the callee is a startup class.
-      if (startupOrder.contains(caller.getHolderType())
-          && !startupOrder.contains(callee.getHolderType())) {
+      if (startupProfile.contains(caller.getHolderType())
+          && !startupProfile.contains(callee.getHolderType())) {
         return false;
       }
     }
     return true;
   }
 
-  private static OptionalBool isStartupMethod(ProgramMethod method, StartupOrder startupOrder) {
+  private static OptionalBool isStartupMethod(ProgramMethod method, StartupProfile startupProfile) {
     if (method.getDefinition().isD8R8Synthesized()) {
       // Due to inadequate rewriting of the startup list during desugaring, we do not give an
       // accurate result in this case.
       return OptionalBool.unknown();
     }
-    return OptionalBool.of(startupOrder.contains(method.getReference()));
+    return OptionalBool.of(startupProfile.contains(method.getReference()));
   }
 
   public static boolean isSafeForVerticalClassMerging(
@@ -113,9 +113,9 @@
 
     // If the source class is a startup class then require that the target class is also a startup
     // class.
-    StartupOrder startupOrder = appView.getStartupOrder();
-    if (startupOrder.contains(sourceClass.getType())
-        && !startupOrder.contains(targetClass.getType())) {
+    StartupProfile startupProfile = appView.getStartupOrder();
+    if (startupProfile.contains(sourceClass.getType())
+        && !startupProfile.contains(targetClass.getType())) {
       return false;
     }
     return true;
diff --git a/src/main/java/com/android/tools/r8/graph/AccessControl.java b/src/main/java/com/android/tools/r8/graph/AccessControl.java
index 40bbf74..eac86b3 100644
--- a/src/main/java/com/android/tools/r8/graph/AccessControl.java
+++ b/src/main/java/com/android/tools/r8/graph/AccessControl.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.features.ClassToFeatureSplitMap;
 import com.android.tools.r8.features.FeatureSplitBoundaryOptimizationUtils;
 import com.android.tools.r8.synthesis.SyntheticItems;
@@ -36,7 +36,7 @@
       Definition context,
       ClassToFeatureSplitMap classToFeatureSplitMap,
       InternalOptions options,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       SyntheticItems syntheticItems) {
     if (!clazz.isPublic() && !clazz.getType().isSamePackage(context.getContextType())) {
       return OptionalBool.FALSE;
@@ -48,7 +48,7 @@
             context.asProgramDefinition(),
             classToFeatureSplitMap,
             options,
-            startupOrder,
+            startupProfile,
             syntheticItems)) {
       return OptionalBool.UNKNOWN;
     }
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 42a4744..5bf8bd1 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -9,7 +9,7 @@
 import com.android.tools.r8.contexts.CompilationContext;
 import com.android.tools.r8.contexts.CompilationContext.ProcessorContext;
 import com.android.tools.r8.errors.dontwarn.DontWarnConfiguration;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.features.ClassToFeatureSplitMap;
 import com.android.tools.r8.graph.DexValue.DexValueString;
 import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
@@ -87,7 +87,7 @@
   private ProguardCompatibilityActions proguardCompatibilityActions;
   private RootSet rootSet;
   private MainDexRootSet mainDexRootSet = null;
-  private StartupOrder startupOrder;
+  private StartupProfile startupProfile;
 
   // This should preferably always be obtained via AppInfoWithLiveness.
   // Currently however the liveness may be downgraded thus loosing the computed keep info.
@@ -140,13 +140,13 @@
   private AppView(
       T appInfo,
       ArtProfileCollection artProfileCollection,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       WholeProgramOptimizations wholeProgramOptimizations,
       TypeRewriter mapper) {
     this(
         appInfo,
         artProfileCollection,
-        startupOrder,
+        startupProfile,
         wholeProgramOptimizations,
         mapper,
         Timing.empty());
@@ -155,7 +155,7 @@
   private AppView(
       T appInfo,
       ArtProfileCollection artProfileCollection,
-      StartupOrder startupOrder,
+      StartupProfile startupProfile,
       WholeProgramOptimizations wholeProgramOptimizations,
       TypeRewriter mapper,
       Timing timing) {
@@ -165,7 +165,7 @@
         timing.time(
             "Compilation context", () -> CompilationContext.createInitialContext(options()));
     this.artProfileCollection = artProfileCollection;
-    this.startupOrder = startupOrder;
+    this.startupProfile = startupProfile;
     this.dontWarnConfiguration =
         timing.time(
             "Dont warn config",
@@ -211,7 +211,7 @@
     return new AppView<>(
         appInfo,
         ArtProfileCollection.createInitialArtProfileCollection(appInfo, appInfo.options()),
-        StartupOrder.empty(),
+        StartupProfile.empty(),
         WholeProgramOptimizations.OFF,
         defaultTypeRewriter(appInfo));
   }
@@ -220,7 +220,7 @@
     return new AppView<>(
         appInfo,
         ArtProfileCollection.empty(),
-        StartupOrder.empty(),
+        StartupProfile.empty(),
         WholeProgramOptimizations.OFF,
         defaultTypeRewriter(appInfo));
   }
@@ -230,7 +230,7 @@
     return new AppView<>(
         appInfo,
         ArtProfileCollection.createInitialArtProfileCollection(appInfo, appInfo.options()),
-        StartupOrder.empty(),
+        StartupProfile.empty(),
         WholeProgramOptimizations.OFF,
         mapper,
         timing);
@@ -253,7 +253,7 @@
     return new AppView<>(
         appInfo,
         ArtProfileCollection.createInitialArtProfileCollection(appInfo, appInfo.options()),
-        StartupOrder.createInitialStartupOrderForR8(application),
+        StartupProfile.createInitialStartupOrderForR8(application),
         WholeProgramOptimizations.ON,
         defaultTypeRewriter(appInfo));
   }
@@ -262,7 +262,7 @@
     return new AppView<>(
         appInfo,
         ArtProfileCollection.createInitialArtProfileCollection(appInfo, appInfo.options()),
-        StartupOrder.empty(),
+        StartupProfile.empty(),
         WholeProgramOptimizations.OFF,
         mapper);
   }
@@ -271,7 +271,7 @@
     return new AppView<>(
         appInfo,
         ArtProfileCollection.empty(),
-        StartupOrder.empty(),
+        StartupProfile.empty(),
         WholeProgramOptimizations.OFF,
         defaultTypeRewriter(appInfo));
   }
@@ -281,7 +281,7 @@
     return new AppView<>(
         appInfo,
         ArtProfileCollection.empty(),
-        StartupOrder.empty(),
+        StartupProfile.empty(),
         WholeProgramOptimizations.ON,
         defaultTypeRewriter(appInfo));
   }
@@ -377,12 +377,12 @@
     this.artProfileCollection = artProfileCollection;
   }
 
-  public StartupOrder getStartupOrder() {
-    return startupOrder;
+  public StartupProfile getStartupOrder() {
+    return startupProfile;
   }
 
-  public void setStartupOrder(StartupOrder startupOrder) {
-    this.startupOrder = startupOrder;
+  public void setStartupOrder(StartupProfile startupProfile) {
+    this.startupProfile = startupProfile;
   }
 
   public AssumeInfoCollection getAssumeInfoCollection() {
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
index 4ec6686..fab68db 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
@@ -11,7 +11,7 @@
 import com.android.tools.r8.contexts.CompilationContext.UniqueContext;
 import com.android.tools.r8.errors.MissingGlobalSyntheticsConsumerDiagnostic;
 import com.android.tools.r8.errors.Unreachable;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.features.ClassToFeatureSplitMap;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
@@ -616,7 +616,7 @@
         context,
         ClassToFeatureSplitMap.createEmptyClassToFeatureSplitMap(),
         options,
-        StartupOrder.empty());
+        StartupProfile.empty());
   }
 
   /** Used to find the synthesizing context for a new synthetic that is about to be created. */
@@ -624,7 +624,7 @@
       ProgramDefinition context,
       ClassToFeatureSplitMap featureSplits,
       InternalOptions options,
-      StartupOrder startupOrder) {
+      StartupProfile startupProfile) {
     DexType contextType = context.getContextType();
     SyntheticDefinition<?, ?, ?> existingDefinition = pending.definitions.get(contextType);
     if (existingDefinition != null) {
@@ -640,7 +640,8 @@
           .getContext();
     }
     // This context is not nested in an existing synthetic context so create a new "leaf" context.
-    FeatureSplit featureSplit = featureSplits.getFeatureSplit(context, options, startupOrder, this);
+    FeatureSplit featureSplit =
+        featureSplits.getFeatureSplit(context, options, startupProfile, this);
     return SynthesizingContext.fromNonSyntheticInputContext(context, featureSplit);
   }
 
diff --git a/src/main/java/com/android/tools/r8/utils/AndroidApp.java b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
index cf3047d..ee770f8 100644
--- a/src/main/java/com/android/tools/r8/utils/AndroidApp.java
+++ b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
@@ -34,7 +34,7 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.InternalCompilerError;
 import com.android.tools.r8.errors.Unreachable;
-import com.android.tools.r8.experimental.startup.StartupOrder;
+import com.android.tools.r8.experimental.startup.StartupProfile;
 import com.android.tools.r8.experimental.startup.StartupProfileProviderUtils;
 import com.android.tools.r8.features.ClassToFeatureSplitMap;
 import com.android.tools.r8.features.FeatureSplitConfiguration;
@@ -679,7 +679,7 @@
                           SyntheticItems syntheticItems = null;
                           FeatureSplit featureSplit =
                               classToFeatureSplitMap.getFeatureSplit(
-                                  type, options, StartupOrder.empty(), syntheticItems);
+                                  type, options, StartupProfile.empty(), syntheticItems);
                           if (featureSplit != null && !featureSplit.isBase()) {
                             return featureSplitArchiveOutputStreams.get(featureSplit);
                           }
diff --git a/src/test/java/com/android/tools/r8/D8CommandTest.java b/src/test/java/com/android/tools/r8/D8CommandTest.java
index 9066212..b4c8475 100644
--- a/src/test/java/com/android/tools/r8/D8CommandTest.java
+++ b/src/test/java/com/android/tools/r8/D8CommandTest.java
@@ -21,8 +21,9 @@
 import com.android.tools.r8.ToolHelper.ProcessResult;
 import com.android.tools.r8.dex.Marker;
 import com.android.tools.r8.dex.Marker.Tool;
+import com.android.tools.r8.experimental.startup.StartupProfile;
+import com.android.tools.r8.experimental.startup.profile.NonEmptyStartupProfile;
 import com.android.tools.r8.experimental.startup.profile.StartupItem;
-import com.android.tools.r8.experimental.startup.profile.StartupProfile;
 import com.android.tools.r8.origin.EmbeddedOrigin;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.references.Reference;
@@ -805,14 +806,14 @@
     MissingStartupProfileItemsDiagnostic.Builder missingStartupProfileItemsDiagnosticBuilder =
         MissingStartupProfileItemsDiagnostic.Builder.nop();
     StartupProfileProvider startupProfileProvider = startupProfileProviders.get(0);
-    StartupProfile.Builder startupProfileBuilder =
-        StartupProfile.builder(
+    NonEmptyStartupProfile.Builder startupProfileBuilder =
+        NonEmptyStartupProfile.builder(
             options, missingStartupProfileItemsDiagnosticBuilder, startupProfileProvider);
     startupProfileProvider.getStartupProfile(startupProfileBuilder);
 
     // Verify we found the same rule.
     StartupProfile startupProfile = startupProfileBuilder.build();
-    Collection<StartupItem> startupItems = startupProfile.getStartupItems();
+    Collection<StartupItem> startupItems = startupProfile.getItems();
     assertEquals(1, startupItems.size());
     StartupItem startupItem = startupItems.iterator().next();
     startupItem.accept(