Add a flag to evaluate the top level transitions in Skyframe

This adds a new PrepareAnalysisPhaseFunction, which started out as a copy of
some existing code from SkyframeExecutor, BuildView, AnalysisPhaseRunner,
AnalysisUtils, and ConfigurationResolver, which was then modified to work
inside Skyframe.

Most of our tests already work with the new code, except for some of the tests
related to configuration trimming in combination with dependency cycles. The
reason for this is that we can only recover from dependency cycles at the end
of a Skyframe invocation, but never inside a Skyframe invocation. The new code
therefore cannot return partial results like the old code.

This seems to make null builds a bit faster. In my testing, I saw null build
times for a single test target go from ~50ms to ~40ms. This is probably due to
slightly better caching - it seems that computing the configuration transitions
and top-level targets is non-negligible, even if there's only a single
top-level configuration for a single top-level target.

This might be an even bigger win if there are a lot of top-level targets and
configurations.

PiperOrigin-RevId: 207083192

15 files changed, 782 insertions, 96 deletions

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 26803f8294..1bed59f362 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 @@ public class AnalysisOptions extends OptionsBase {
     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 1fc7048aa5..fa7984d1d7 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.actions.PackageRoots;
 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 @@ public final class AnalysisResult {
   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 @@ public final class AnalysisResult {
       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 @@ public final class AnalysisResult {
     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 32fa07f03f..b7d8e14281 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 @@ public final class AnalysisUtils {
    *
    * <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 @@ public final class AnalysisUtils {
 
   @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 9995de0c73..e93d119eb1 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.ArtifactOwner;
 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.Rule;
 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 @@ public class BuildView {
   @ThreadCompatible
   public AnalysisResult update(
       TargetPatternPhaseValue loadingResult,
-      BuildConfigurationCollection configurations,
+      BuildOptions targetOptions,
+      Set<String> multiCpu,
       List<String> aspects,
       AnalysisOptions viewOptions,
       boolean keepGoing,
@@ -190,7 +194,7 @@ public class BuildView {
       TopLevelArtifactContext topLevelOptions,
       ExtendedEventHandler eventHandler,
       EventBus eventBus)
-      throws ViewCreationFailedException, InterruptedException {
+      throws ViewCreationFailedException, InvalidConfigurationException, InterruptedException {
     logger.info("Starting analysis");
     pollInterruptedStatus();
 
@@ -202,12 +206,49 @@ public class BuildView {
         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 @@ public class BuildView {
     }
 
     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 @@ public class BuildView {
       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 fb9a66a8c4..20459337d4 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 @@ package com.google.devtools.build.lib.analysis.config;
 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 @@ public final class BuildConfigurationCollection {
   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 405d272649..6dde833cdc 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 @@ public final class ConfigurationResolver {
   //   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 be441c15cc..97e2a67d51 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.BuildView;
 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 @@ public final class AnalysisPhaseRunner {
     // 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 @@ public final class AnalysisPhaseRunner {
   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 @@ public final class AnalysisPhaseRunner {
     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 b2018a23fa..101529d950 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.runtime.CommandEnvironment;
 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 @@ public abstract class PostAnalysisQueryBuildTool<T> extends BuildTool {
       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 @@ public abstract class PostAnalysisQueryBuildTool<T> extends BuildTool {
   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 ec4d791148..cb410f2227 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 @@ abstract class AbstractLabelCycleReporter implements CyclesReporter.SingleCycleR
 
   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 @@ abstract class AbstractLabelCycleReporter implements CyclesReporter.SingleCycleR
       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 0000000000..3fada696df
--- /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 0000000000..97436242fb
--- /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 09bdcd3ba5..ac9228cb33 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 @@ public final class SkyFunctions {
   // 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 a95bcd02f1..4a9c7bfc0b 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 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     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 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
    * 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 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     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 abstract class SkyframeExecutor implements WalkableGraphFactory {
   }
 
   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 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
    *
    * @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 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
    *
    * <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 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     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 a7c9b3126d..617e320899 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 @@ import java.util.List;
  * (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 @@ class TransitiveTargetCycleReporter extends AbstractLabelCycleReporter {
   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 @@ class TransitiveTargetCycleReporter extends AbstractLabelCycleReporter {
   }
 
   @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 0e48d42102..410b48b0b5 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 @@ import com.google.devtools.build.skyframe.SkyKey;
 @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);
   }