diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java
index 26803f8..1bed59f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java
@@ -89,4 +89,13 @@
     help = "No-op."
   )
   public boolean interleaveLoadingAndAnalysis;
+
+  @Option(
+    name = "experimental_skyframe_prepare_analysis",
+    defaultValue = "false",
+    documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
+    effectTags = {OptionEffectTag.BAZEL_INTERNAL_CONFIGURATION},
+    help = "Switches analysis preparation to a new code path based on Skyframe."
+  )
+  public boolean skyframePrepareAnalysis;
 }
\ No newline at end of file
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisResult.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisResult.java
index 1fc7048..fa7984d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisResult.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisResult.java
@@ -21,7 +21,6 @@
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import java.util.Collection;
-import java.util.List;
 import javax.annotation.Nullable;
 
 /**
@@ -41,7 +40,7 @@
   private final ImmutableSet<AspectValue> aspects;
   private final PackageRoots packageRoots;
   private final String workspaceName;
-  private final List<TargetAndConfiguration> topLevelTargetsWithConfigs;
+  private final Collection<TargetAndConfiguration> topLevelTargetsWithConfigs;
 
   AnalysisResult(
       BuildConfigurationCollection configurations,
@@ -57,7 +56,7 @@
       TopLevelArtifactContext topLevelContext,
       PackageRoots packageRoots,
       String workspaceName,
-      List<TargetAndConfiguration> topLevelTargetsWithConfigs) {
+      Collection<TargetAndConfiguration> topLevelTargetsWithConfigs) {
     this.configurations = configurations;
     this.targetsToBuild = ImmutableSet.copyOf(targetsToBuild);
     this.aspects = aspects;
@@ -157,7 +156,7 @@
     return workspaceName;
   }
 
-  public List<TargetAndConfiguration> getTopLevelTargetsWithConfigs() {
+  public Collection<TargetAndConfiguration> getTopLevelTargetsWithConfigs() {
     return topLevelTargetsWithConfigs;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
index 32fa07f..b7d8e14 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
@@ -196,13 +196,13 @@
    *
    * <p>Preserves the original input ordering.
    */
+  // Keep this in sync with PrepareAnalysisPhaseFunction.
   public static List<TargetAndConfiguration> getTargetsWithConfigs(
       BuildConfigurationCollection configurations,
       Collection<Target> targets,
       ExtendedEventHandler eventHandler,
       ConfiguredRuleClassProvider ruleClassProvider,
-      SkyframeExecutor skyframeExecutor)
-      throws InterruptedException {
+      SkyframeExecutor skyframeExecutor) {
     // We use a hash set here to remove duplicate nodes; this can happen for input files and package
     // groups.
     LinkedHashSet<TargetAndConfiguration> nodes = new LinkedHashSet<>(targets.size());
@@ -225,7 +225,7 @@
 
   @VisibleForTesting
   public static Multimap<BuildConfiguration, Dependency> targetsToDeps(
-      LinkedHashSet<TargetAndConfiguration> nodes, ConfiguredRuleClassProvider ruleClassProvider) {
+      Collection<TargetAndConfiguration> nodes, ConfiguredRuleClassProvider ruleClassProvider) {
     Multimap<BuildConfiguration, Dependency> asDeps =
         ArrayListMultimap.<BuildConfiguration, Dependency>create();
     for (TargetAndConfiguration targetAndConfig : nodes) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 9995de0..e93d119 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -15,13 +15,11 @@
 package com.google.devtools.build.lib.analysis;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Lists;
 import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
@@ -34,6 +32,8 @@
 import com.google.devtools.build.lib.actions.PackageRoots;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection;
+import com.google.devtools.build.lib.analysis.config.BuildOptions;
+import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
 import com.google.devtools.build.lib.analysis.constraints.TopLevelConstraintSemantics;
 import com.google.devtools.build.lib.analysis.test.CoverageReportActionFactory;
 import com.google.devtools.build.lib.analysis.test.CoverageReportActionFactory.CoverageReportActionsWrapper;
@@ -55,11 +55,14 @@
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.pkgcache.PackageManager.PackageManagerStatistics;
+import com.google.devtools.build.lib.profiler.Profiler;
+import com.google.devtools.build.lib.profiler.SilentCloseable;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectValueKey;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
 import com.google.devtools.build.lib.skyframe.CoverageReportValue;
+import com.google.devtools.build.lib.skyframe.PrepareAnalysisPhaseValue;
 import com.google.devtools.build.lib.skyframe.SkyframeAnalysisResult;
 import com.google.devtools.build.lib.skyframe.SkyframeBuildView;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
@@ -182,7 +185,8 @@
   @ThreadCompatible
   public AnalysisResult update(
       TargetPatternPhaseValue loadingResult,
-      BuildConfigurationCollection configurations,
+      BuildOptions targetOptions,
+      Set<String> multiCpu,
       List<String> aspects,
       AnalysisOptions viewOptions,
       boolean keepGoing,
@@ -190,7 +194,7 @@
       TopLevelArtifactContext topLevelOptions,
       ExtendedEventHandler eventHandler,
       EventBus eventBus)
-      throws ViewCreationFailedException, InterruptedException {
+      throws ViewCreationFailedException, InvalidConfigurationException, InterruptedException {
     logger.info("Starting analysis");
     pollInterruptedStatus();
 
@@ -202,12 +206,49 @@
         loadingResult.getTargets(eventHandler, skyframeExecutor.getPackageManager());
     eventBus.post(new AnalysisPhaseStartedEvent(targets));
 
+    // Prepare the analysis phase
+    BuildConfigurationCollection configurations;
+    Collection<TargetAndConfiguration> topLevelTargetsWithConfigs;
+    if (viewOptions.skyframePrepareAnalysis) {
+      PrepareAnalysisPhaseValue prepareAnalysisPhaseValue;
+      try (SilentCloseable c = Profiler.instance().profile("Prepare analysis phase")) {
+        prepareAnalysisPhaseValue = skyframeExecutor.prepareAnalysisPhase(
+            eventHandler, targetOptions, multiCpu, loadingResult.getTargetLabels());
+  
+        // Determine the configurations
+        configurations =
+            prepareAnalysisPhaseValue.getConfigurations(eventHandler, skyframeExecutor);
+        topLevelTargetsWithConfigs =
+            prepareAnalysisPhaseValue.getTopLevelCts(eventHandler, skyframeExecutor);
+      }
+    } else {
+      // Configuration creation.
+      // TODO(gregce): Consider dropping this phase and passing on-the-fly target / host configs as
+      // needed. This requires cleaning up the invalidation in SkyframeBuildView.setConfigurations.
+      try (SilentCloseable c = Profiler.instance().profile("createConfigurations")) {
+        configurations =
+            skyframeExecutor
+                .createConfigurations(
+                    eventHandler,
+                    targetOptions,
+                    multiCpu,
+                    keepGoing);
+      }
+      try (SilentCloseable c = Profiler.instance().profile("AnalysisUtils.getTargetsWithConfigs")) {
+        topLevelTargetsWithConfigs =
+            AnalysisUtils.getTargetsWithConfigs(
+                configurations, targets, eventHandler, ruleClassProvider, skyframeExecutor);
+      }
+    }
+
     skyframeBuildView.setConfigurations(eventHandler, configurations);
 
-    // Determine the configurations.
-    List<TargetAndConfiguration> topLevelTargetsWithConfigs =
-        AnalysisUtils.getTargetsWithConfigs(
-            configurations, targets, eventHandler, ruleClassProvider, skyframeExecutor);
+    if (configurations.getTargetConfigurations().size() == 1) {
+      eventBus
+          .post(
+              new MakeEnvironmentEvent(
+                  configurations.getTargetConfigurations().get(0).getMakeEnvironment()));
+    }
 
     // Report the generated association of targets to configurations
     Multimap<Label, BuildConfiguration> byLabel =
@@ -220,14 +261,10 @@
     }
 
     List<ConfiguredTargetKey> topLevelCtKeys =
-        Lists.transform(
-            topLevelTargetsWithConfigs,
-            new Function<TargetAndConfiguration, ConfiguredTargetKey>() {
-              @Override
-              public ConfiguredTargetKey apply(TargetAndConfiguration node) {
-                return ConfiguredTargetKey.of(node.getLabel(), node.getConfiguration());
-              }
-            });
+        topLevelTargetsWithConfigs
+            .stream()
+            .map(node -> ConfiguredTargetKey.of(node.getLabel(), node.getConfiguration()))
+            .collect(Collectors.toList());
 
     Multimap<Pair<Label, String>, BuildConfiguration> aspectConfigurations =
         ArrayListMultimap.create();
@@ -362,7 +399,7 @@
       AnalysisOptions viewOptions,
       SkyframeAnalysisResult skyframeAnalysisResult,
       Set<ConfiguredTarget> targetsToSkip,
-      List<TargetAndConfiguration> topLevelTargetsWithConfigs)
+      Collection<TargetAndConfiguration> topLevelTargetsWithConfigs)
       throws InterruptedException {
     Set<Label> testsToRun = loadingResult.getTestsToRunLabels();
     Set<ConfiguredTarget> configuredTargets =
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java
index fb9a66a..2045933 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java
@@ -17,8 +17,8 @@
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.buildtool.BuildRequestOptions;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import java.util.Collection;
 import java.util.HashMap;
-import java.util.List;
 
 /**
  * Convenience container for top-level target and host configurations.
@@ -34,9 +34,10 @@
   private final ImmutableList<BuildConfiguration> targetConfigurations;
   private final BuildConfiguration hostConfiguration;
 
-  public BuildConfigurationCollection(List<BuildConfiguration> targetConfigurations,
+  public BuildConfigurationCollection(
+      Collection<BuildConfiguration> targetConfigurations,
       BuildConfiguration hostConfiguration)
-      throws InvalidConfigurationException {
+          throws InvalidConfigurationException {
     this.targetConfigurations = ImmutableList.copyOf(targetConfigurations);
     this.hostConfiguration = hostConfiguration;
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java
index 405d272..6dde833 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java
@@ -558,6 +558,7 @@
   //   should never make it through analysis (and especially not seed ConfiguredTargetValues)
   // TODO(gregce): merge this more with resolveConfigurations? One crucial difference is
   //   resolveConfigurations can null-return on missing deps since it executes inside Skyfunctions.
+  // Keep this in sync with {@link PrepareAnalysisPhaseFunction#resolveConfigurations}.
   public static LinkedHashSet<TargetAndConfiguration> getConfigurationsFromExecutor(
       Iterable<TargetAndConfiguration> defaultContext,
       Multimap<BuildConfiguration, Dependency> targetsToEvaluate,
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/AnalysisPhaseRunner.java b/src/main/java/com/google/devtools/build/lib/buildtool/AnalysisPhaseRunner.java
index be441c1..97e2a67 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/AnalysisPhaseRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/AnalysisPhaseRunner.java
@@ -22,11 +22,9 @@
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.LicensesProvider;
 import com.google.devtools.build.lib.analysis.LicensesProvider.TargetLicense;
-import com.google.devtools.build.lib.analysis.MakeEnvironmentEvent;
 import com.google.devtools.build.lib.analysis.StaticallyLinkedMarkerProvider;
 import com.google.devtools.build.lib.analysis.ViewCreationFailedException;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
-import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
 import com.google.devtools.build.lib.buildeventstream.AbortedEvent;
@@ -112,45 +110,22 @@
     // Exit if there are any pending exceptions from modules.
     env.throwPendingException();
 
-    // Configuration creation.
-    // TODO(gregce): Consider dropping this phase and passing on-the-fly target / host configs as
-    // needed. This requires cleaning up the invalidation in SkyframeBuildView.setConfigurations.
-    BuildConfigurationCollection configurations;
-    try (SilentCloseable c = Profiler.instance().profile("createConfigurations")) {
-      configurations =
-          env.getSkyframeExecutor()
-              .createConfigurations(
-                  env.getReporter(),
-                  env.getRuntime().getConfigurationFragmentFactories(),
-                  buildOptions,
-                  request.getMultiCpus(),
-                  request.getKeepGoing());
-    }
-
-    env.throwPendingException();
-    if (configurations.getTargetConfigurations().size() == 1) {
-      // TODO(bazel-team): This is not optimal - we retain backwards compatibility in the case
-      // where there's only a single configuration, but we don't send an event in the multi-config
-      // case. Can we do better? [multi-config]
-      env.getEventBus()
-          .post(
-              new MakeEnvironmentEvent(
-                  configurations.getTargetConfigurations().get(0).getMakeEnvironment()));
-    }
-    logger.info("Configurations created");
+    env.getSkyframeExecutor().setConfigurationFragmentFactories(
+        env.getRuntime().getConfigurationFragmentFactories());
 
     AnalysisResult analysisResult = null;
     if (request.getBuildOptions().performAnalysisPhase) {
       Profiler.instance().markPhase(ProfilePhase.ANALYZE);
       try (SilentCloseable c = Profiler.instance().profile("runAnalysisPhase")) {
-        analysisResult = runAnalysisPhase(request, loadingResult, configurations);
+        analysisResult =
+            runAnalysisPhase(request, loadingResult, buildOptions, request.getMultiCpus());
       }
 
       // Check licenses.
       // We check licenses if the first target configuration has license checking enabled. Right
       // now, it is not possible to have multiple target configurations with different settings
       // for this flag, which allows us to take this short cut.
-      boolean checkLicenses = configurations.getTargetConfigurations().get(0).checkLicenses();
+      boolean checkLicenses = buildOptions.get(BuildConfiguration.Options.class).checkLicenses;
       if (checkLicenses) {
         Profiler.instance().markPhase(ProfilePhase.LICENSE);
         try (SilentCloseable c = Profiler.instance().profile("validateLicensingForTargets")) {
@@ -221,8 +196,9 @@
   private AnalysisResult runAnalysisPhase(
       BuildRequest request,
       TargetPatternPhaseValue loadingResult,
-      BuildConfigurationCollection configurations)
-      throws InterruptedException, ViewCreationFailedException {
+      BuildOptions targetOptions,
+      Set<String> multiCpu)
+      throws InterruptedException, InvalidConfigurationException, ViewCreationFailedException {
     Stopwatch timer = Stopwatch.createStarted();
     env.getReporter().handle(Event.progress("Loading complete.  Analyzing..."));
 
@@ -235,7 +211,8 @@
     AnalysisResult analysisResult =
         view.update(
             loadingResult,
-            configurations,
+            targetOptions,
+            multiCpu,
             request.getAspects(),
             request.getViewOptions(),
             request.getKeepGoing(),
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryBuildTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryBuildTool.java
index b2018a2..101529d 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryBuildTool.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryBuildTool.java
@@ -28,6 +28,7 @@
 import com.google.devtools.build.lib.skyframe.SkyframeExecutorWrappingWalkableGraph;
 import com.google.devtools.build.skyframe.WalkableGraph;
 import java.io.IOException;
+import java.util.Collection;
 import java.util.List;
 import java.util.stream.Collectors;
 
@@ -83,8 +84,9 @@
       WalkableGraph walkableGraph);
 
   private BuildConfiguration getBuildConfiguration(
-      List<TargetAndConfiguration> topLevelTargetsWithConfigs, QueryExpression queryExpression)
-      throws QueryException {
+      Collection<TargetAndConfiguration> topLevelTargetsWithConfigs,
+      QueryExpression queryExpression)
+          throws QueryException {
     // Currently, CTQE assumes that all top level targets take on the same default config and we
     // don't have the ability to map multiple configs to multiple top level targets.
     // So for now, we only allow multiple targets when they all carry the same config.
@@ -115,7 +117,7 @@
   private void doPostAnalysisQuery(
       BuildRequest request,
       BuildConfiguration hostConfiguration,
-      List<TargetAndConfiguration> topLevelTargetsWithConfigs,
+      Collection<TargetAndConfiguration> topLevelTargetsWithConfigs,
       QueryExpression queryExpression)
       throws InterruptedException, QueryException, IOException {
     BuildConfiguration targetConfig =
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AbstractLabelCycleReporter.java b/src/main/java/com/google/devtools/build/lib/skyframe/AbstractLabelCycleReporter.java
index ec4d791..cb410f2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AbstractLabelCycleReporter.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AbstractLabelCycleReporter.java
@@ -48,6 +48,22 @@
 
   protected abstract boolean canReportCycle(SkyKey topLevelKey, CycleInfo cycleInfo);
 
+  /**
+   * Can be used to skip individual keys on the path to cycle.
+   *
+   * @param key
+   */
+  protected boolean shouldSkip(SkyKey key) {
+    return false;
+  }
+
+  /**
+   * Can be used to report an additional message about the cycle.
+   *
+   * @param eventHandler
+   * @param topLevelKey
+   * @param cycleInfo
+   */
   protected String getAdditionalMessageAboutCycle(
       ExtendedEventHandler eventHandler, SkyKey topLevelKey, CycleInfo cycleInfo) {
     return "";
@@ -75,6 +91,9 @@
       ImmutableList<SkyKey> pathToCycle = cycleInfo.getPathToCycle();
       ImmutableList<SkyKey> cycle = cycleInfo.getCycle();
       for (SkyKey value : pathToCycle) {
+        if (shouldSkip(value)) {
+          continue;
+        }
         cycleMessage.append("\n    ");
         cycleMessage.append(prettyPrint(value));
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseFunction.java
new file mode 100644
index 0000000..3fada69
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseFunction.java
@@ -0,0 +1,353 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import com.google.common.base.Predicates;
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedSet;
+import com.google.common.collect.Multimap;
+import com.google.devtools.build.lib.analysis.AnalysisUtils;
+import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
+import com.google.devtools.build.lib.analysis.Dependency;
+import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
+import com.google.devtools.build.lib.analysis.config.BuildOptions;
+import com.google.devtools.build.lib.analysis.config.ConfigurationResolver;
+import com.google.devtools.build.lib.analysis.config.HostTransition;
+import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.events.ErrorSensingEventHandler;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.skyframe.PrepareAnalysisPhaseValue.PrepareAnalysisPhaseKey;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionException;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.ValueOrException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import javax.annotation.Nullable;
+
+/**
+ * Prepares for analysis - creates the top-level configurations and evaluates the transitions needed
+ * for the top-level targets (including trimming).
+ */
+final class PrepareAnalysisPhaseFunction implements SkyFunction {
+  private final ConfiguredRuleClassProvider ruleClassProvider;
+  private final BuildOptions defaultBuildOptions;
+
+  PrepareAnalysisPhaseFunction(
+      ConfiguredRuleClassProvider ruleClassProvider, BuildOptions defaultBuildOptions) {
+    this.ruleClassProvider = ruleClassProvider;
+    this.defaultBuildOptions = defaultBuildOptions;
+  }
+
+  @Override
+  public PrepareAnalysisPhaseValue compute(SkyKey key, Environment env)
+      throws InterruptedException, PrepareAnalysisPhaseFunctionException {
+    PrepareAnalysisPhaseKey options = (PrepareAnalysisPhaseKey) key.argument();
+
+    BuildOptions targetOptions = defaultBuildOptions.applyDiff(options.getOptionsDiff());
+    BuildOptions hostOptions =
+        targetOptions.get(BuildConfiguration.Options.class).useDistinctHostConfiguration
+            ? HostTransition.INSTANCE.patch(targetOptions)
+            : targetOptions;
+
+    ImmutableSortedSet<Class<? extends BuildConfiguration.Fragment>> allFragments =
+        options.getFragments().fragmentClasses();
+    BuildConfigurationValue.Key hostConfigurationKey =
+        BuildConfigurationValue.key(
+            allFragments,
+            BuildOptions.diffForReconstruction(defaultBuildOptions, hostOptions));
+    ImmutableList<BuildConfigurationValue.Key> targetConfigurationKeys =
+        getTopLevelBuildOptions(targetOptions, options.getMultiCpu())
+            .stream()
+            .map(
+                elem ->
+                    BuildConfigurationValue.key(
+                        allFragments,
+                        BuildOptions.diffForReconstruction(defaultBuildOptions, elem)))
+            .collect(ImmutableList.toImmutableList());
+
+    // We don't need the host configuration below, but we call this to get the error, if any.
+    try {
+      env.getValueOrThrow(hostConfigurationKey, InvalidConfigurationException.class);
+    } catch (InvalidConfigurationException e) {
+      throw new PrepareAnalysisPhaseFunctionException(e);
+    }
+
+    Map<SkyKey, SkyValue> configs = env.getValues(targetConfigurationKeys);
+
+    // We only report invalid options for the target configurations, and abort if there's an error.
+    ErrorSensingEventHandler nosyEventHandler = new ErrorSensingEventHandler(env.getListener());
+    targetConfigurationKeys
+        .stream()
+        .map(k -> configs.get(k))
+        .filter(Predicates.notNull())
+        .map(v -> ((BuildConfigurationValue) v).getConfiguration())
+        .forEach(config -> config.reportInvalidOptions(nosyEventHandler));
+    if (nosyEventHandler.hasErrors()) {
+      throw new PrepareAnalysisPhaseFunctionException(
+          new InvalidConfigurationException("Build options are invalid"));
+    }
+
+    // We get the list of labels from the TargetPatternPhaseValue, so we are reasonably certain that
+    // there will not be an error loading these again.
+    ResolvedTargets<Target> resolvedTargets =
+        TestSuiteExpansionFunction.labelsToTargets(env, options.getLabels(), false);
+    if (resolvedTargets == null) {
+      return null;
+    }
+    ImmutableSet<Target> targets = resolvedTargets.getTargets();
+
+    // We use a hash set here to remove duplicate nodes; this can happen for input files and package
+    // groups.
+    LinkedHashSet<TargetAndConfiguration> nodes = new LinkedHashSet<>(targets.size());
+    for (Target target : targets) {
+      if (target.isConfigurable()) {
+        for (BuildConfigurationValue.Key configKey : targetConfigurationKeys) {
+          BuildConfiguration config =
+              ((BuildConfigurationValue) configs.get(configKey)).getConfiguration();
+          nodes.add(new TargetAndConfiguration(target, config));
+        }
+      } else {
+        nodes.add(new TargetAndConfiguration(target, null));
+      }
+    }
+
+    // We'll get the configs from #resolveConfigurations below, which started out as a copy of the
+    // same code in SkyframeExecutor, which gets configurations for deps including transitions. So,
+    // for now, to satisfy its API we resolve transitions and repackage each target as a Dependency
+    // (with a NONE transition if necessary).
+    // Keep this in sync with AnalysisUtils#getTargetsWithConfigs.
+    Multimap<BuildConfiguration, Dependency> asDeps =
+        AnalysisUtils.targetsToDeps(nodes, ruleClassProvider);
+    LinkedHashSet<TargetAndConfiguration> topLevelTargetsWithConfigs =
+        resolveConfigurations(env, nodes, asDeps);
+    if (env.valuesMissing()) {
+      return null;
+    }
+    ImmutableList<ConfiguredTargetKey> topLevelCtKeys =
+        topLevelTargetsWithConfigs
+            .stream()
+            .map(node -> ConfiguredTargetKey.of(node.getLabel(), node.getConfiguration()))
+            .collect(ImmutableList.toImmutableList());
+    return new PrepareAnalysisPhaseValue(
+        hostConfigurationKey, targetConfigurationKeys, topLevelCtKeys);
+  }
+
+  /**
+   * Returns the {@link BuildOptions} to apply to the top-level build configurations. This can be
+   * plural because of {@code multiCpu}.
+   */
+  // Visible for SkyframeExecutor, which uses it for tests.
+  static List<BuildOptions> getTopLevelBuildOptions(
+      BuildOptions buildOptions, Set<String> multiCpu) {
+    if (multiCpu.isEmpty()) {
+      return ImmutableList.of(buildOptions);
+    }
+    ImmutableList.Builder<BuildOptions> multiCpuOptions = ImmutableList.builder();
+    for (String cpu : multiCpu) {
+      BuildOptions clonedOptions = buildOptions.clone();
+      clonedOptions.get(BuildConfiguration.Options.class).cpu = cpu;
+      multiCpuOptions.add(clonedOptions);
+    }
+    return multiCpuOptions.build();
+  }
+
+  // TODO(bazel-team): error out early for targets that fail - untrimmed configurations should
+  // never make it through analysis (and especially not seed ConfiguredTargetValues)
+  // Keep this in sync with {@link ConfigurationResolver#getConfigurationsFromExecutor}.
+  private LinkedHashSet<TargetAndConfiguration> resolveConfigurations(
+      SkyFunction.Environment env,
+      Iterable<TargetAndConfiguration> nodes,
+      Multimap<BuildConfiguration, Dependency> asDeps)
+          throws InterruptedException {
+    Map<Label, Target> labelsToTargets = new LinkedHashMap<>();
+    for (TargetAndConfiguration node : nodes) {
+      labelsToTargets.put(node.getTarget().getLabel(), node.getTarget());
+    }
+
+    // Maps <target, originalConfig> pairs to <target, finalConfig> pairs for targets that
+    // could be successfully Skyframe-evaluated.
+    Map<TargetAndConfiguration, TargetAndConfiguration> successfullyEvaluatedTargets =
+        new LinkedHashMap<>();
+    for (BuildConfiguration fromConfig : asDeps.keySet()) {
+      Multimap<Dependency, BuildConfiguration> trimmedTargets =
+          getConfigurations(
+              env, fromConfig.getOptions(), asDeps.get(fromConfig));
+      if (trimmedTargets == null) {
+        continue;
+      }
+      for (Map.Entry<Dependency, BuildConfiguration> trimmedTarget : trimmedTargets.entries()) {
+        Target target = labelsToTargets.get(trimmedTarget.getKey().getLabel());
+        successfullyEvaluatedTargets.put(
+            new TargetAndConfiguration(target, fromConfig),
+            new TargetAndConfiguration(target, trimmedTarget.getValue()));
+      }
+    }
+
+    if (env.valuesMissing()) {
+      return null;
+    }
+
+    LinkedHashSet<TargetAndConfiguration> result = new LinkedHashSet<>();
+    for (TargetAndConfiguration originalNode : nodes) {
+      if (successfullyEvaluatedTargets.containsKey(originalNode)) {
+        // The configuration was successfully trimmed.
+        result.add(successfullyEvaluatedTargets.get(originalNode));
+      } else {
+        // Either the configuration couldn't be determined (e.g. loading phase error) or it's null.
+        result.add(originalNode);
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Returns whether configurations should trim their fragments to only those needed by
+   * targets and their transitive dependencies.
+   */
+  private static boolean useUntrimmedConfigs(BuildOptions options) {
+    return options.get(BuildConfiguration.Options.class).configsMode
+        == BuildConfiguration.Options.ConfigsMode.NOTRIM;
+  }
+
+  // Keep in sync with {@link SkyframeExecutor#getConfigurations}.
+  // Note: this implementation runs inside Skyframe, so it has access to SkyFunction.Environment.
+  private Multimap<Dependency, BuildConfiguration> getConfigurations(
+      SkyFunction.Environment env, BuildOptions fromOptions, Iterable<Dependency> keys)
+          throws InterruptedException {
+    Multimap<Dependency, BuildConfiguration> builder =
+        ArrayListMultimap.<Dependency, BuildConfiguration>create();
+    Set<Dependency> depsToEvaluate = new HashSet<>();
+
+    ImmutableSortedSet<Class<? extends BuildConfiguration.Fragment>> allFragments = null;
+    if (useUntrimmedConfigs(fromOptions)) {
+      allFragments = ruleClassProvider.getAllFragments();
+    }
+
+    // Get the fragments needed for dynamic configuration nodes.
+    final List<SkyKey> transitiveFragmentSkyKeys = new ArrayList<>();
+    Map<Label, ImmutableSortedSet<Class<? extends BuildConfiguration.Fragment>>> fragmentsMap =
+        new HashMap<>();
+    Set<Label> labelsWithErrors = new HashSet<>();
+    for (Dependency key : keys) {
+      if (key.hasExplicitConfiguration()) {
+        builder.put(key, key.getConfiguration());
+      } else if (useUntrimmedConfigs(fromOptions)) {
+        fragmentsMap.put(key.getLabel(), allFragments);
+      } else {
+        depsToEvaluate.add(key);
+        transitiveFragmentSkyKeys.add(TransitiveTargetKey.of(key.getLabel()));
+      }
+    }
+    Map<SkyKey, ValueOrException<NoSuchThingException>> fragmentsResult =
+        env.getValuesOrThrow(transitiveFragmentSkyKeys, NoSuchThingException.class);
+    if (env.valuesMissing()) {
+      return null;
+    }
+    for (Dependency key : keys) {
+      if (!depsToEvaluate.contains(key)) {
+        // No fragments to compute here.
+      } else {
+        TransitiveTargetKey targetKey = TransitiveTargetKey.of(key.getLabel());
+        try {
+          TransitiveTargetValue ttv =
+              (TransitiveTargetValue) fragmentsResult.get(targetKey).get();
+          fragmentsMap.put(
+              key.getLabel(),
+              ImmutableSortedSet.copyOf(
+                  BuildConfiguration.lexicalFragmentSorter,
+                  ttv.getTransitiveConfigFragments().toSet()));
+        } catch (NoSuchThingException e) {
+          // We silently skip any labels with errors - they'll be reported in the analysis phase.
+          labelsWithErrors.add(key.getLabel());
+        }
+      }
+    }
+
+    // Now get the configurations.
+    final List<SkyKey> configSkyKeys = new ArrayList<>();
+    for (Dependency key : keys) {
+      if (labelsWithErrors.contains(key.getLabel()) || key.hasExplicitConfiguration()) {
+        continue;
+      }
+      ImmutableSortedSet<Class<? extends BuildConfiguration.Fragment>> depFragments =
+          fragmentsMap.get(key.getLabel());
+      if (depFragments != null) {
+        for (BuildOptions toOptions : ConfigurationResolver.applyTransition(
+            fromOptions, key.getTransition(), depFragments, ruleClassProvider, true)) {
+          configSkyKeys.add(
+              BuildConfigurationValue.key(
+                  depFragments,
+                  BuildOptions.diffForReconstruction(defaultBuildOptions, toOptions)));
+        }
+      }
+    }
+    Map<SkyKey, SkyValue> configsResult = env.getValues(configSkyKeys);
+    if (env.valuesMissing()) {
+      return null;
+    }
+    for (Dependency key : keys) {
+      if (labelsWithErrors.contains(key.getLabel()) || key.hasExplicitConfiguration()) {
+        continue;
+      }
+      ImmutableSortedSet<Class<? extends BuildConfiguration.Fragment>> depFragments =
+          fragmentsMap.get(key.getLabel());
+      if (depFragments != null) {
+        for (BuildOptions toOptions : ConfigurationResolver.applyTransition(
+            fromOptions, key.getTransition(), depFragments, ruleClassProvider, true)) {
+          SkyKey configKey =
+              BuildConfigurationValue.key(
+                  depFragments, BuildOptions.diffForReconstruction(defaultBuildOptions, toOptions));
+          BuildConfigurationValue configValue =
+              ((BuildConfigurationValue) configsResult.get(configKey));
+          // configValue will be null here if there was an exception thrown during configuration
+          // creation. This will be reported elsewhere.
+          if (configValue != null) {
+            builder.put(key, configValue.getConfiguration());
+          }
+        }
+      }
+    }
+    return builder;
+  }
+
+  @Nullable
+  @Override
+  public String extractTag(SkyKey skyKey) {
+    return null;
+  }
+
+  /**
+   * Used to declare all the exception types that can be wrapped in the exception thrown by
+   * {@link PrepareAnalysisPhaseFunction#compute}.
+   */
+  private static final class PrepareAnalysisPhaseFunctionException extends SkyFunctionException {
+    public PrepareAnalysisPhaseFunctionException(InvalidConfigurationException e) {
+      super(e, Transience.PERSISTENT);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseValue.java
new file mode 100644
index 0000000..9743624
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseValue.java
@@ -0,0 +1,233 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedSet;
+import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
+import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection;
+import com.google.devtools.build.lib.analysis.config.BuildOptions;
+import com.google.devtools.build.lib.analysis.config.FragmentClassSet;
+import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.events.ExtendedEventHandler;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+/**
+ * A value referring to a set of build configuration keys in order to reconstruct the
+ * legacy {@link BuildConfigurationCollection} as well as a set of top level configured target keys
+ * that are subsequently requested to trigger the analysis phase.
+ *
+ * <p>The public interface returns {@link BuildConfigurationCollection} and {@link
+ * TargetAndConfiguration} even though these are not internally stored - the construction of these
+ * objects requires additional Skyframe calls. The intention is that these are temporary until a
+ * larger fraction of the code has been ported to Skyframe, at which point we'll use the internal
+ * representation.
+ */
+@Immutable
+@ThreadSafe
+@AutoCodec
+public final class PrepareAnalysisPhaseValue implements SkyValue {
+  private final BuildConfigurationValue.Key hostConfigurationKey;
+  private final ImmutableList<BuildConfigurationValue.Key> targetConfigurationKeys;
+  private final ImmutableList<ConfiguredTargetKey> topLevelCtKeys;
+
+  PrepareAnalysisPhaseValue(
+      BuildConfigurationValue.Key hostConfigurationKey,
+      ImmutableList<BuildConfigurationValue.Key> targetConfigurationKeys,
+      ImmutableList<ConfiguredTargetKey> topLevelCtKeys) {
+    this.hostConfigurationKey = Preconditions.checkNotNull(hostConfigurationKey);
+    this.targetConfigurationKeys = Preconditions.checkNotNull(targetConfigurationKeys);
+    this.topLevelCtKeys = Preconditions.checkNotNull(topLevelCtKeys);
+  }
+
+  /**
+   * Returns the legacy {@link BuildConfigurationCollection}. Note that this performs additional
+   * Skyframe calls, which may be expensive.
+   */
+  public BuildConfigurationCollection getConfigurations(
+      ExtendedEventHandler eventHandler, SkyframeExecutor skyframeExecutor)
+          throws InvalidConfigurationException {
+    BuildConfiguration hostConfiguration =
+        skyframeExecutor.getConfiguration(eventHandler, hostConfigurationKey);
+    Collection<BuildConfiguration> targetConfigurations =
+        skyframeExecutor.getConfigurations(eventHandler, targetConfigurationKeys).values();
+    return new BuildConfigurationCollection(targetConfigurations, hostConfiguration);
+  }
+
+  /**
+   * Returns the intended top-level targets and configurations for the build. Note that this
+   * performs additional Skyframe calls for the involved configurations and targets, which may be
+   * expensive.
+   */
+  public Collection<TargetAndConfiguration> getTopLevelCts(
+      ExtendedEventHandler eventHandler, SkyframeExecutor skyframeExecutor) {
+    List<TargetAndConfiguration> result = new ArrayList<>();
+    Map<BuildConfigurationValue.Key, BuildConfiguration> configs =
+        skyframeExecutor.getConfigurations(
+            eventHandler,
+            topLevelCtKeys
+                .stream()
+                .map(ctk -> ctk.getConfigurationKey())
+                .filter(Predicates.notNull())
+                .collect(Collectors.toSet()));
+
+    // TODO(ulfjack): This performs one Skyframe call per top-level target. This is not a
+    // regression, but we should fix it nevertheless, either by doing a bulk lookup call or by
+    // migrating the consumers of these to Skyframe so they can directly request the values.
+    for (ConfiguredTargetKey key : topLevelCtKeys) {
+      Target target;
+      try {
+        target = skyframeExecutor.getPackageManager().getTarget(eventHandler, key.getLabel());
+      } catch (NoSuchPackageException | NoSuchTargetException | InterruptedException e) {
+        throw new RuntimeException("Failed to get package from TargetPatternPhaseValue", e);
+      }
+      BuildConfiguration config =
+          key.getConfigurationKey() == null ? null : configs.get(key.getConfigurationKey());
+      result.add(new TargetAndConfiguration(target, config));
+    }
+    return result;
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (!(obj instanceof PrepareAnalysisPhaseValue)) {
+      return false;
+    }
+    PrepareAnalysisPhaseValue that = (PrepareAnalysisPhaseValue) obj;
+    return this.hostConfigurationKey.equals(that.hostConfigurationKey)
+        && this.targetConfigurationKeys.equals(that.targetConfigurationKeys)
+        && this.topLevelCtKeys.equals(that.topLevelCtKeys);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(
+        this.hostConfigurationKey,
+        this.targetConfigurationKeys,
+        this.topLevelCtKeys);
+  }
+
+  /** Create a prepare analysis phase key. */
+  @ThreadSafe
+  public static SkyKey key(
+      FragmentClassSet fragments,
+      BuildOptions.OptionsDiffForReconstruction optionsDiff,
+      Set<String> multiCpu,
+      Collection<Label> labels) {
+    return new PrepareAnalysisPhaseKey(fragments, optionsDiff, multiCpu, labels);
+  }
+
+  /** The configuration needed to prepare the analysis phase. */
+  @ThreadSafe
+  @VisibleForSerialization
+  @AutoCodec
+  public static final class PrepareAnalysisPhaseKey implements SkyKey, Serializable {
+    private final FragmentClassSet fragments;
+    private final BuildOptions.OptionsDiffForReconstruction optionsDiff;
+    private final ImmutableSortedSet<String> multiCpu;
+    private final ImmutableSet<Label> labels;
+
+    PrepareAnalysisPhaseKey(
+        FragmentClassSet fragments,
+        BuildOptions.OptionsDiffForReconstruction optionsDiff,
+        Set<String> multiCpu,
+        Collection<Label> labels) {
+      this.fragments = Preconditions.checkNotNull(fragments);
+      this.optionsDiff = Preconditions.checkNotNull(optionsDiff);
+      this.multiCpu = ImmutableSortedSet.copyOf(multiCpu);
+      this.labels = ImmutableSet.copyOf(labels);
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.PREPARE_ANALYSIS_PHASE;
+    }
+
+    public FragmentClassSet getFragments() {
+      return fragments;
+    }
+
+    public BuildOptions.OptionsDiffForReconstruction getOptionsDiff() {
+      return optionsDiff;
+    }
+
+    public ImmutableSortedSet<String> getMultiCpu() {
+      return multiCpu;
+    }
+
+    public ImmutableSet<Label> getLabels() {
+      return labels;
+    }
+
+    @Override
+    public String toString() {
+      return MoreObjects.toStringHelper(PrepareAnalysisPhaseKey.class)
+          .add("fragments", fragments)
+          .add("optionsDiff", optionsDiff)
+          .add("multiCpu", multiCpu)
+          .add("labels", labels)
+          .toString();
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(
+          fragments,
+          optionsDiff,
+          multiCpu,
+          labels);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (this == obj) {
+        return true;
+      }
+      if (!(obj instanceof PrepareAnalysisPhaseKey)) {
+        return false;
+      }
+      PrepareAnalysisPhaseKey other = (PrepareAnalysisPhaseKey) obj;
+      return other.fragments.equals(this.fragments)
+          && other.optionsDiff.equals(this.optionsDiff)
+          && other.multiCpu.equals(multiCpu)
+          && other.labels.equals(labels);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
index 09bdcd3..ac9228c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
@@ -79,6 +79,8 @@
   // Non-hermetic because accesses package locator
   static final SkyFunctionName TARGET_PATTERN_PHASE =
       SkyFunctionName.createNonHermetic("TARGET_PATTERN_PHASE");
+  static final SkyFunctionName PREPARE_ANALYSIS_PHASE =
+      SkyFunctionName.createNonHermetic("PREPARE_ANALYSIS_PHASE");
   static final SkyFunctionName RECURSIVE_PKG = SkyFunctionName.createHermetic("RECURSIVE_PKG");
   static final SkyFunctionName TRANSITIVE_TARGET =
       SkyFunctionName.createHermetic("TRANSITIVE_TARGET");
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index a95bcd0..4a9c7bf 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -432,6 +432,9 @@
     map.put(SkyFunctions.TESTS_IN_SUITE, new TestsInSuiteFunction());
     map.put(SkyFunctions.TEST_SUITE_EXPANSION, new TestSuiteExpansionFunction());
     map.put(SkyFunctions.TARGET_PATTERN_PHASE, new TargetPatternPhaseFunction());
+    map.put(
+        SkyFunctions.PREPARE_ANALYSIS_PHASE,
+        new PrepareAnalysisPhaseFunction(ruleClassProvider, defaultBuildOptions));
     map.put(SkyFunctions.RECURSIVE_PKG, new RecursivePkgFunction(directories));
     map.put(
         SkyFunctions.PACKAGE,
@@ -1195,16 +1198,18 @@
    * Asks the Skyframe evaluator to build the value for BuildConfigurationCollection and returns the
    * result.
    */
+  // TODO(ulfjack): Remove this legacy method after switching to the Skyframe-based implementation.
   public BuildConfigurationCollection createConfigurations(
       ExtendedEventHandler eventHandler,
-      List<ConfigurationFragmentFactory> configurationFragmentFactories,
       BuildOptions buildOptions,
       Set<String> multiCpu,
       boolean keepGoing)
-      throws InvalidConfigurationException, InterruptedException {
-    setConfigurationFragmentFactories(configurationFragmentFactories);
+      throws InvalidConfigurationException {
     List<BuildConfiguration> topLevelTargetConfigs =
-        getConfigurations(eventHandler, getTopLevelBuildOptions(buildOptions, multiCpu), keepGoing);
+        getConfigurations(
+            eventHandler,
+            PrepareAnalysisPhaseFunction.getTopLevelBuildOptions(buildOptions, multiCpu),
+            keepGoing);
 
     BuildConfiguration firstTargetConfig = topLevelTargetConfigs.get(0);
 
@@ -1225,24 +1230,6 @@
     return new BuildConfigurationCollection(topLevelTargetConfigs, hostConfig);
   }
 
-  /**
-   * Returns the {@link BuildOptions} to apply to the top-level build configurations. This can be
-   * plural because of {@code multiCpu}.
-   */
-  private static List<BuildOptions> getTopLevelBuildOptions(BuildOptions buildOptions,
-      Set<String> multiCpu) {
-    if (multiCpu.isEmpty()) {
-      return ImmutableList.of(buildOptions);
-    }
-    ImmutableList.Builder<BuildOptions> multiCpuOptions = ImmutableList.builder();
-    for (String cpu : multiCpu) {
-      BuildOptions clonedOptions = buildOptions.clone();
-      clonedOptions.get(BuildConfiguration.Options.class).cpu = cpu;
-      multiCpuOptions.add(clonedOptions);
-    }
-    return multiCpuOptions.build();
-  }
-
   @SuppressWarnings({"unchecked", "rawtypes"})
   Map<SkyKey, ActionLookupValue> getActionLookupValueMap() {
     return (Map) Maps.filterValues(memoizingEvaluator.getDoneValues(),
@@ -1552,7 +1539,7 @@
   }
 
   public Map<BuildConfigurationValue.Key, BuildConfiguration> getConfigurations(
-      ExtendedEventHandler eventHandler, ImmutableSet<BuildConfigurationValue.Key> keys) {
+      ExtendedEventHandler eventHandler, Collection<BuildConfigurationValue.Key> keys) {
     EvaluationResult<SkyValue> evaluationResult = evaluateSkyKeys(eventHandler, keys);
     return keys.stream()
         .collect(
@@ -1566,8 +1553,10 @@
    *
    * @throws InvalidConfigurationException if any build options produces an invalid configuration
    */
-  public List<BuildConfiguration> getConfigurations(ExtendedEventHandler eventHandler,
-      List<BuildOptions> optionsList, boolean keepGoing) throws InvalidConfigurationException {
+  // TODO(ulfjack): Remove this legacy method after switching to the Skyframe-based implementation.
+  public List<BuildConfiguration> getConfigurations(
+      ExtendedEventHandler eventHandler, List<BuildOptions> optionsList, boolean keepGoing)
+          throws InvalidConfigurationException {
     Preconditions.checkArgument(!Iterables.isEmpty(optionsList));
 
     // Prepare the Skyframe inputs.
@@ -1625,6 +1614,8 @@
    *
    * <p>Skips targets with loading phase errors.
    */
+  // Keep this in sync with {@link PrepareAnalysisPhaseFunction#getConfigurations}.
+  // TODO(ulfjack): Remove this legacy method after switching to the Skyframe-based implementation.
   public Multimap<Dependency, BuildConfiguration> getConfigurations(
       ExtendedEventHandler eventHandler, BuildOptions fromOptions, Iterable<Dependency> keys) {
     Multimap<Dependency, BuildConfiguration> builder =
@@ -2286,6 +2277,55 @@
     return patternParsingValue;
   }
 
+  public PrepareAnalysisPhaseValue prepareAnalysisPhase(
+      ExtendedEventHandler eventHandler,
+      BuildOptions buildOptions,
+      Set<String> multiCpu,
+      Collection<Label> labels)
+      throws InvalidConfigurationException, InterruptedException {
+    FragmentClassSet allFragments =
+        FragmentClassSet.of(
+            configurationFragments
+                .get()
+                .stream()
+                .map(factory -> factory.creates())
+                .collect(
+                    ImmutableSortedSet.toImmutableSortedSet(
+                        BuildConfiguration.lexicalFragmentSorter)));
+    SkyKey key =
+        PrepareAnalysisPhaseValue.key(
+            allFragments,
+            BuildOptions.diffForReconstruction(defaultBuildOptions, buildOptions),
+            multiCpu,
+            labels);
+    EvaluationResult<PrepareAnalysisPhaseValue> evalResult;
+    evalResult =
+        buildDriver.evaluate(
+            ImmutableList.of(key),
+            /* keepGoing= */ true,
+            /*numThreads=*/ DEFAULT_THREAD_COUNT,
+            eventHandler);
+    if (evalResult.hasError()) {
+      ErrorInfo errorInfo = evalResult.getError(key);
+      Exception e = errorInfo.getException();
+      if (e == null && !Iterables.isEmpty(errorInfo.getCycleInfo())) {
+        getCyclesReporter().reportCycles(errorInfo.getCycleInfo(), key, eventHandler);
+        e = new InvalidConfigurationException(
+            "cannot load build configuration because of this cycle");
+      } else if (e instanceof NoSuchThingException) {
+        e = new InvalidConfigurationException(e);
+      }
+      if (e != null) {
+        Throwables.throwIfInstanceOf(e, InvalidConfigurationException.class);
+      }
+      throw new IllegalStateException(
+          "Unknown error during configuration creation evaluation", e);
+    }
+
+    PrepareAnalysisPhaseValue prepareAnalysisPhaseValue = evalResult.get(key);
+    return prepareAnalysisPhaseValue;
+  }
+
   public Consumer<Artifact.SourceArtifact> getSourceDependencyListener(SkyKey key) {
     return unusedSource -> {}; // Default, no-op implementation.
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java
index a7c9b31..617e320 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetCycleReporter.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
@@ -31,9 +32,10 @@
  * (e.g. '//a:foo' depends on '//b:bar' and '//b:bar' depends on '//a:foo').
  */
 class TransitiveTargetCycleReporter extends AbstractLabelCycleReporter {
-
-  private static final Predicate<SkyKey> IS_TRANSITIVE_TARGET_SKY_KEY =
-      SkyFunctions.isSkyFunction(SkyFunctions.TRANSITIVE_TARGET);
+  private static final Predicate<SkyKey> IS_SUPPORTED_SKY_KEY =
+      Predicates.or(
+          SkyFunctions.isSkyFunction(SkyFunctions.TRANSITIVE_TARGET),
+          SkyFunctions.isSkyFunction(SkyFunctions.PREPARE_ANALYSIS_PHASE));
 
   TransitiveTargetCycleReporter(PackageProvider packageProvider) {
     super(packageProvider);
@@ -43,7 +45,7 @@
   protected boolean canReportCycle(SkyKey topLevelKey, CycleInfo cycleInfo) {
     return Iterables.all(Iterables.concat(ImmutableList.of(topLevelKey),
         cycleInfo.getPathToCycle(), cycleInfo.getCycle()),
-        IS_TRANSITIVE_TARGET_SKY_KEY);
+        IS_SUPPORTED_SKY_KEY);
   }
 
   @Override
@@ -57,18 +59,29 @@
   }
 
   @Override
+  protected boolean shouldSkip(SkyKey key) {
+    return SkyFunctions.PREPARE_ANALYSIS_PHASE.equals(key.functionName());
+  }
+
+  @Override
   protected String getAdditionalMessageAboutCycle(
       ExtendedEventHandler eventHandler, SkyKey topLevelKey, CycleInfo cycleInfo) {
-    Target currentTarget = getTargetForLabel(eventHandler, getLabel(topLevelKey));
     List<SkyKey> keys = Lists.newArrayList();
     if (!cycleInfo.getPathToCycle().isEmpty()) {
-      keys.add(topLevelKey);
-      keys.addAll(cycleInfo.getPathToCycle());
+      if (!shouldSkip(topLevelKey)) {
+        keys.add(topLevelKey);
+      }
+      cycleInfo.getPathToCycle()
+          .stream()
+          .filter(key -> !shouldSkip(key))
+          .forEach(keys::add);
     }
     keys.addAll(cycleInfo.getCycle());
     // Make sure we check the edge from the last element of the cycle to the first element of the
     // cycle.
     keys.add(cycleInfo.getCycle().get(0));
+
+    Target currentTarget = getTargetForLabel(eventHandler, getLabel(keys.get(0)));
     for (SkyKey nextKey : keys) {
       Label nextLabel = getLabel(nextKey);
       Target nextTarget = getTargetForLabel(eventHandler, nextLabel);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetKey.java
index 0e48d42..410b48b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetKey.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetKey.java
@@ -27,7 +27,7 @@
 @Immutable
 @ThreadSafe
 public final class TransitiveTargetKey implements SkyKey {
-  public static SkyKey of(Label label) {
+  public static TransitiveTargetKey of(Label label) {
     Preconditions.checkArgument(!label.getPackageIdentifier().getRepository().isDefault());
     return new TransitiveTargetKey(label);
   }