diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java
index 3f22aa6..1dc9c73 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java
@@ -16,169 +16,84 @@
 
 import static java.util.stream.Collectors.joining;
 
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableBiMap;
-import com.google.common.collect.ImmutableList;
+import com.google.auto.value.AutoValue;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
-import com.google.devtools.build.lib.analysis.platform.PlatformProviderUtils;
 import com.google.devtools.build.lib.analysis.platform.ToolchainInfo;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 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.Location;
-import com.google.devtools.build.lib.packages.Attribute;
-import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
 import com.google.devtools.build.lib.skylarkbuildapi.ToolchainContextApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
-import com.google.devtools.build.lib.util.OrderedSetMultimap;
-import java.util.Optional;
 import java.util.Set;
-import java.util.stream.StreamSupport;
+import javax.annotation.Nullable;
 
-/** Contains toolchain-related information needed for a {@link RuleContext}. */
+/** Represents the data needed for a specific target's use of toolchains and platforms. */
+@AutoValue
 @Immutable
 @ThreadSafe
-public class ToolchainContext implements ToolchainContextApi {
+public abstract class ToolchainContext implements ToolchainContextApi {
 
-  public static ToolchainContext create(
-      String targetDescription,
-      PlatformInfo executionPlatform,
-      PlatformInfo targetPlatform,
-      Set<Label> requiredToolchains,
-      ImmutableBiMap<Label, Label> resolvedLabels) {
-    return new ToolchainContext(
-        targetDescription,
-        executionPlatform,
-        targetPlatform,
-        requiredToolchains,
-        new ResolvedToolchainLabels(resolvedLabels));
+  static Builder builder() {
+    return new AutoValue_ToolchainContext.Builder();
   }
 
-  /** The {@link PlatformInfo} describing where these toolchains can be executed. */
-  private final PlatformInfo executionPlatform;
+  /** Builder interface to help create new instances of {@link ToolchainContext}. */
+  @AutoValue.Builder
+  interface Builder {
+    /** Sets a description of the target being used, for error messaging. */
+    Builder setTargetDescription(String targetDescription);
 
-  /** The {@link PlatformInfo} describing the outputs of these toolchains. */
-  private final PlatformInfo targetPlatform;
+    /** Sets the selected execution platform that these toolchains use. */
+    Builder setExecutionPlatform(PlatformInfo executionPlatform);
 
-  /** Description of the target the toolchain context applies to, for use in error messages. */
-  private final String targetDescription;
+    /** Sets the target platform that these toolchains generate output for. */
+    Builder setTargetPlatform(PlatformInfo targetPlatform);
 
-  /** The toolchain types that are required by the target. */
-  private final ImmutableList<Label> requiredToolchains;
+    /** Sets the toolchain types that were requested. */
+    Builder setRequiredToolchainTypes(Set<Label> requiredToolchainTypes);
 
-  /** Map from toolchain type labels to actual resolved toolchain labels. */
-  private final ResolvedToolchainLabels resolvedToolchainLabels;
+    /** Sets the map from toolchain type to toolchain provider. */
+    Builder setToolchains(ImmutableMap<Label, ToolchainInfo> toolchains);
 
-  /** Stores the actual ToolchainInfo provider for each toolchain type. */
-  private ImmutableMap<Label, ToolchainInfo> toolchainProviders;
+    /** Sets the labels of the specific toolchains being used. */
+    Builder setResolvedToolchainLabels(ImmutableSet<Label> resolvedToolchainLabels);
 
-  private ToolchainContext(
-      String targetDescription,
-      PlatformInfo executionPlatform,
-      PlatformInfo targetPlatform,
-      Set<Label> requiredToolchains,
-      ResolvedToolchainLabels resolvedToolchainLabels) {
-    this.targetDescription = targetDescription;
-    this.executionPlatform = executionPlatform;
-    this.targetPlatform = targetPlatform;
-    this.requiredToolchains = ImmutableList.copyOf(requiredToolchains);
-    this.resolvedToolchainLabels = resolvedToolchainLabels;
-    this.toolchainProviders = ImmutableMap.of();
+    /** Returns a new {@link ToolchainContext}. */
+    ToolchainContext build();
   }
 
-  public PlatformInfo executionPlatform() {
-    return executionPlatform;
+  /** Returns a description of the target being used, for error messaging. */
+  abstract String targetDescription();
+
+  /** Returns the selected execution platform that these toolchains use. */
+  public abstract PlatformInfo executionPlatform();
+
+  /** Returns the target platform that these toolchains generate output for. */
+  public abstract PlatformInfo targetPlatform();
+
+  /** Returns the toolchain types that were requested. */
+  public abstract ImmutableSet<Label> requiredToolchainTypes();
+
+  abstract ImmutableMap<Label, ToolchainInfo> toolchains();
+
+  /** Returns the labels of the specific toolchains being used. */
+  public abstract ImmutableSet<Label> resolvedToolchainLabels();
+
+  /**
+   * Returns the toolchain for the given type, or {@code null} if the toolchain type was not
+   * required in this context.
+   */
+  @Nullable
+  public ToolchainInfo forToolchainType(Label toolchainType) {
+    return toolchains().get(toolchainType);
   }
 
-  public PlatformInfo targetPlatform() {
-    return targetPlatform;
-  }
-
-  public ImmutableList<Label> requiredToolchainTypes() {
-    return requiredToolchains;
-  }
-
-  public void resolveToolchains(
-      OrderedSetMultimap<Attribute, ConfiguredTargetAndData> prerequisiteMap) {
-    if (!this.requiredToolchains.isEmpty()) {
-      this.toolchainProviders = findToolchains(resolvedToolchainLabels, prerequisiteMap);
-    }
-  }
-
-  public ImmutableSet<Label> resolvedToolchainLabels() {
-    return resolvedToolchainLabels.getToolchainLabels();
-  }
-
-  /** Returns the {@link Label}s from the {@link NestedSet} that refer to toolchain dependencies. */
-  public Set<Label> filterToolchainLabels(Iterable<Label> labels) {
-    return StreamSupport.stream(labels.spliterator(), false)
-        .filter(label -> resolvedToolchainLabels.isToolchainDependency(label))
-        .collect(ImmutableSet.toImmutableSet());
-  }
-
-  /** Tracks the mapping from toolchain type label to the label of the actual resolved toolchain. */
-  private static class ResolvedToolchainLabels {
-
-    private final ImmutableBiMap<Label, Label> toolchainLabels;
-
-    private ResolvedToolchainLabels(ImmutableBiMap<Label, Label> toolchainLabels) {
-      this.toolchainLabels = toolchainLabels;
-    }
-
-    public Label getType(Label toolchainLabel) {
-      return toolchainLabels.inverse().get(toolchainLabel);
-    }
-
-    public Label getResolvedToolchainLabel(Label toolchainType) {
-      return toolchainLabels.get(toolchainType);
-    }
-
-    public ImmutableSet<Label> getToolchainLabels() {
-      return toolchainLabels.values();
-    }
-
-    public boolean isToolchainDependency(Label label) {
-      return toolchainLabels.containsValue(label);
-    }
-  }
-
-  private static ImmutableMap<Label, ToolchainInfo> findToolchains(
-      ResolvedToolchainLabels resolvedToolchainLabels,
-      OrderedSetMultimap<Attribute, ConfiguredTargetAndData> prerequisiteMap) {
-    // Find the prerequisites associated with PlatformSemantics.RESOLVED_TOOLCHAINS_ATTR.
-    Optional<Attribute> toolchainAttribute =
-        prerequisiteMap
-            .keys()
-            .stream()
-            .filter(attribute -> attribute != null)
-            .filter(
-                attribute -> attribute.getName().equals(PlatformSemantics.RESOLVED_TOOLCHAINS_ATTR))
-            .findFirst();
-    Preconditions.checkState(
-        toolchainAttribute.isPresent(),
-        "No toolchains attribute found while loading resolved toolchains");
-
-    ImmutableMap.Builder<Label, ToolchainInfo> toolchains = new ImmutableMap.Builder<>();
-    for (ConfiguredTargetAndData target : prerequisiteMap.get(toolchainAttribute.get())) {
-      Label discoveredLabel = target.getTarget().getLabel();
-      Label toolchainType = resolvedToolchainLabels.getType(discoveredLabel);
-      if (toolchainType != null) {
-        ToolchainInfo toolchainInfo = PlatformProviderUtils.toolchain(target.getConfiguredTarget());
-        toolchains.put(toolchainType, toolchainInfo);
-      }
-    }
-
-    return toolchains.build();
-  }
-
-  // Implement SkylarkValue and SkylarkIndexable.
-
   @Override
   public boolean isImmutable() {
     return true;
@@ -187,17 +102,15 @@
   @Override
   public void repr(SkylarkPrinter printer) {
     printer.append("<toolchain_context.resolved_labels: ");
-    printer.append(
-        toolchainProviders.keySet().stream().map(key -> key.toString()).collect(joining(", ")));
+    printer.append(toolchains().keySet().stream().map(Label::toString).collect(joining(", ")));
     printer.append(">");
   }
 
   private Label transformKey(Object key, Location loc) throws EvalException {
     if (key instanceof Label) {
-      Label toolchainType = (Label) key;
-      return toolchainType;
+      return (Label) key;
     } else if (key instanceof String) {
-      Label toolchainType = null;
+      Label toolchainType;
       String rawLabel = (String) key;
       try {
         toolchainType = Label.parseAbsolute(rawLabel, ImmutableMap.of());
@@ -219,29 +132,21 @@
   public ToolchainInfo getIndex(Object key, Location loc) throws EvalException {
     Label toolchainType = transformKey(key, loc);
 
-    if (!requiredToolchains.contains(toolchainType)) {
+    if (!requiredToolchainTypes().contains(toolchainType)) {
       throw new EvalException(
           loc,
           String.format(
               "In %s, toolchain type %s was requested but only types [%s] are configured",
-              targetDescription,
+              targetDescription(),
               toolchainType,
-              requiredToolchains
-                  .stream()
-                  .map(toolchain -> toolchain.toString())
-                  .collect(joining())));
+              requiredToolchainTypes().stream().map(Label::toString).collect(joining())));
     }
-    return toolchainProviders.get(toolchainType);
-  }
-
-  /** Returns the toolchain for the given type */
-  public ToolchainInfo forToolchainType(Label toolchainType) {
-    return toolchainProviders.get(toolchainType);
+    return forToolchainType(toolchainType);
   }
 
   @Override
   public boolean containsKey(Object key, Location loc) throws EvalException {
     Label toolchainType = transformKey(key, loc);
-    return toolchainProviders.containsKey(toolchainType);
+    return toolchains().containsKey(toolchainType);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java
new file mode 100644
index 0000000..e03fa6f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java
@@ -0,0 +1,591 @@
+// 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.analysis;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.collect.ImmutableList.toImmutableList;
+import static java.util.stream.Collectors.joining;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.base.Joiner;
+import com.google.common.collect.HashBasedTable;
+import com.google.common.collect.ImmutableBiMap;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Table;
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
+import com.google.devtools.build.lib.analysis.platform.ConstraintValueInfo;
+import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
+import com.google.devtools.build.lib.analysis.platform.PlatformProviderUtils;
+import com.google.devtools.build.lib.analysis.platform.ToolchainInfo;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.skyframe.BuildConfigurationValue;
+import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
+import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
+import com.google.devtools.build.lib.skyframe.ConstraintValueLookupUtil;
+import com.google.devtools.build.lib.skyframe.ConstraintValueLookupUtil.InvalidConstraintValueException;
+import com.google.devtools.build.lib.skyframe.PlatformLookupUtil;
+import com.google.devtools.build.lib.skyframe.PlatformLookupUtil.InvalidPlatformException;
+import com.google.devtools.build.lib.skyframe.RegisteredExecutionPlatformsValue;
+import com.google.devtools.build.lib.skyframe.RegisteredToolchainsFunction.InvalidToolchainLabelException;
+import com.google.devtools.build.lib.skyframe.ToolchainException;
+import com.google.devtools.build.lib.skyframe.ToolchainResolutionFunction.NoToolchainFoundException;
+import com.google.devtools.build.lib.skyframe.ToolchainResolutionValue;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
+import com.google.devtools.build.skyframe.SkyFunction.Environment;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.ValueOrException2;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Optional;
+import java.util.Set;
+import java.util.stream.Collectors;
+import javax.annotation.Nullable;
+
+/**
+ * Performs the toolchain resolution process to determine the correct toolchain target dependencies
+ * for a target being configured, based on the required toolchain types, target platform, and
+ * available execution platforms.
+ */
+public class ToolchainResolver {
+  // Required data.
+  private final Environment environment;
+  private final BuildConfigurationValue.Key configurationKey;
+
+  // Optional data.
+  private String targetDescription = "";
+  private ImmutableSet<Label> requiredToolchainTypes = ImmutableSet.of();
+  private ImmutableSet<Label> execConstraintLabels = ImmutableSet.of();
+
+  // Determined during execution.
+  private boolean debug = false;
+
+  /**
+   * Creates a new {@link ToolchainResolver} to help find the required toolchains for a configured
+   * target.
+   *
+   * @param env the environment to use to request dependent Skyframe nodes
+   * @param configurationKey The build configuration to use for dependent targets
+   */
+  public ToolchainResolver(Environment env, BuildConfigurationValue.Key configurationKey) {
+    this.environment = checkNotNull(env);
+    this.configurationKey = checkNotNull(configurationKey);
+  }
+
+  /**
+   * Sets a description of the target that toolchains will be resolved for. This is primarily useful
+   * for printing informative error messages, so that users can tell which targets had difficulty.
+   */
+  public ToolchainResolver setTargetDescription(String targetDescription) {
+    this.targetDescription = targetDescription;
+    return this;
+  }
+
+  /** Sets the required toolchain types that this resolver needs to find toolchains for. */
+  public ToolchainResolver setRequiredToolchainTypes(Set<Label> requiredToolchainTypes) {
+    this.requiredToolchainTypes = ImmutableSet.copyOf(requiredToolchainTypes);
+    return this;
+  }
+
+  /**
+   * Sets extra constraints on the execution platform. Targets can use this to ensure that the
+   * execution platform has some desired characteristics, such as having enough memory to run tests.
+   */
+  public ToolchainResolver setExecConstraintLabels(Set<Label> execConstraintLabels) {
+    this.execConstraintLabels = ImmutableSet.copyOf(execConstraintLabels);
+    return this;
+  }
+
+  /**
+   * Determines the specific toolchains that are required, given the requested toolchain types,
+   * target platform, and configuration.
+   *
+   * <p>In order to resolve toolchains, first the {@link ToolchainResolver} must be created, and
+   * then an {@link UnloadedToolchainContext} generated. The {@link UnloadedToolchainContext} will
+   * report the specific toolchain targets to depend on, and those can be found using the typical
+   * dependency machinery. Once dependencies, including toolchains, have been loaded, the {@link
+   * UnloadedToolchainContext#load} method can be called to generate the final {@link
+   * ToolchainContext} to be used by the target.
+   *
+   * <p>This makes several SkyFrame calls, particularly to {@link
+   * com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction} (to load platforms and
+   * toolchains), to {@link
+   * com.google.devtools.build.lib.skyframe.RegisteredExecutionPlatformsFunction}, and to {@link
+   * com.google.devtools.build.lib.skyframe.ToolchainResolutionFunction}. This method return {@code
+   * null} to signal a SkyFrame restart is needed to resolve dependencies.
+   */
+  @Nullable
+  public UnloadedToolchainContext resolve() throws InterruptedException, ToolchainException {
+
+    try {
+      UnloadedToolchainContext.Builder unloadedToolchainContext =
+          UnloadedToolchainContext.builder();
+      unloadedToolchainContext
+          .setTargetDescription(targetDescription)
+          .setRequiredToolchainTypes(requiredToolchainTypes);
+
+      // Determine the configuration being used.
+      BuildConfigurationValue value =
+          (BuildConfigurationValue) environment.getValue(configurationKey);
+      if (value == null) {
+        throw new ValueMissingException();
+      }
+      BuildConfiguration configuration = value.getConfiguration();
+      PlatformConfiguration platformConfiguration =
+          configuration.getFragment(PlatformConfiguration.class);
+      if (platformConfiguration == null) {
+        throw new ValueMissingException();
+      }
+
+      // Check if debug output should be generated.
+      this.debug = configuration.getOptions().get(PlatformOptions.class).toolchainResolutionDebug;
+
+      // Create keys for all platforms that will be used, and validate them early.
+      PlatformKeys platformKeys = loadPlatformKeys(configuration, platformConfiguration);
+      if (environment.valuesMissing()) {
+        return null;
+      }
+
+      // Determine the actual toolchain implementations to use.
+      determineToolchainImplementations(unloadedToolchainContext, platformKeys);
+
+      return unloadedToolchainContext.build();
+    } catch (ValueMissingException e) {
+      return null;
+    }
+  }
+
+  @AutoValue
+  abstract static class PlatformKeys {
+    abstract ConfiguredTargetKey hostPlatformKey();
+
+    abstract ConfiguredTargetKey targetPlatformKey();
+
+    abstract ImmutableList<ConfiguredTargetKey> executionPlatformKeys();
+
+    static PlatformKeys create(
+        ConfiguredTargetKey hostPlatformKey,
+        ConfiguredTargetKey targetPlatformKey,
+        List<ConfiguredTargetKey> executionPlatformKeys) {
+      return new AutoValue_ToolchainResolver_PlatformKeys(
+          hostPlatformKey, targetPlatformKey, ImmutableList.copyOf(executionPlatformKeys));
+    }
+  }
+
+  private PlatformKeys loadPlatformKeys(
+      BuildConfiguration configuration, PlatformConfiguration platformConfiguration)
+      throws InterruptedException, InvalidPlatformException, ValueMissingException,
+          InvalidConstraintValueException {
+    // Determine the target and host platform keys.
+    Label hostPlatformLabel = platformConfiguration.getHostPlatform();
+    Label targetPlatformLabel = platformConfiguration.getTargetPlatform();
+
+    ConfiguredTargetKey hostPlatformKey = ConfiguredTargetKey.of(hostPlatformLabel, configuration);
+    ConfiguredTargetKey targetPlatformKey =
+        ConfiguredTargetKey.of(targetPlatformLabel, configuration);
+
+    // Load the host and target platforms early, to check for errors.
+    PlatformLookupUtil.getPlatformInfo(
+        ImmutableList.of(hostPlatformKey, targetPlatformKey), environment);
+    if (environment.valuesMissing()) {
+      throw new ValueMissingException();
+    }
+
+    ImmutableList<ConfiguredTargetKey> executionPlatformKeys =
+        loadExecutionPlatformKeys(configuration, hostPlatformKey);
+
+    return PlatformKeys.create(hostPlatformKey, targetPlatformKey, executionPlatformKeys);
+  }
+
+  private ImmutableList<ConfiguredTargetKey> loadExecutionPlatformKeys(
+      BuildConfiguration configuration, ConfiguredTargetKey defaultPlatformKey)
+      throws InvalidPlatformException, InterruptedException, InvalidConstraintValueException,
+          ValueMissingException {
+    RegisteredExecutionPlatformsValue registeredExecutionPlatforms =
+        (RegisteredExecutionPlatformsValue)
+            environment.getValueOrThrow(
+                RegisteredExecutionPlatformsValue.key(configurationKey),
+                InvalidPlatformException.class);
+    if (registeredExecutionPlatforms == null) {
+      throw new ValueMissingException();
+    }
+
+    ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys =
+        new ImmutableList.Builder<ConfiguredTargetKey>()
+            .addAll(registeredExecutionPlatforms.registeredExecutionPlatformKeys())
+            .add(defaultPlatformKey)
+            .build();
+
+    // Filter out execution platforms that don't satisfy the extra constraints.
+    ImmutableList<ConfiguredTargetKey> execConstraintKeys =
+        execConstraintLabels.stream()
+            .map(label -> ConfiguredTargetKey.of(label, configuration))
+            .collect(toImmutableList());
+
+    return filterAvailablePlatforms(availableExecutionPlatformKeys, execConstraintKeys);
+  }
+
+  /** Returns only the platform keys that match the given constraints. */
+  private ImmutableList<ConfiguredTargetKey> filterAvailablePlatforms(
+      ImmutableList<ConfiguredTargetKey> platformKeys,
+      ImmutableList<ConfiguredTargetKey> constraintKeys)
+      throws InterruptedException, InvalidPlatformException, InvalidConstraintValueException,
+          ValueMissingException {
+
+    // Short circuit if not needed.
+    if (constraintKeys.isEmpty()) {
+      return platformKeys;
+    }
+
+    // At this point the host and target platforms have been loaded, but not necessarily the chosen
+    // execution platform (it might be the same as the host platform, and might not).
+    //
+    // It's not worth trying to optimize away this call, since in the optimizable case (the exec
+    // platform is the host platform), Skyframe will return the correct results immediately without
+    // need of a restart.
+    Map<ConfiguredTargetKey, PlatformInfo> platformInfoMap =
+        PlatformLookupUtil.getPlatformInfo(platformKeys, environment);
+    if (platformInfoMap == null) {
+      throw new ValueMissingException();
+    }
+    List<ConstraintValueInfo> constraints =
+        ConstraintValueLookupUtil.getConstraintValueInfo(constraintKeys, environment);
+    if (constraints == null) {
+      throw new ValueMissingException();
+    }
+
+    return platformKeys.stream()
+        .filter(key -> filterPlatform(platformInfoMap.get(key), constraints))
+        .collect(toImmutableList());
+  }
+
+  /** Returns {@code true} if the given platform has all of the constraints. */
+  private boolean filterPlatform(PlatformInfo platformInfo, List<ConstraintValueInfo> constraints) {
+    for (ConstraintValueInfo filterConstraint : constraints) {
+      ConstraintValueInfo platformInfoConstraint =
+          platformInfo.getConstraint(filterConstraint.constraint());
+      if (platformInfoConstraint == null || !platformInfoConstraint.equals(filterConstraint)) {
+        // The value for this setting is not present in the platform, or doesn't match the expected
+        // value.
+        if (debug) {
+          environment
+              .getListener()
+              .handle(
+                  Event.info(
+                      String.format(
+                          "ToolchainUtil: Removed execution platform %s from"
+                              + " available execution platforms, it is missing constraint %s",
+                          platformInfo.label(), filterConstraint.label())));
+        }
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  private void determineToolchainImplementations(
+      UnloadedToolchainContext.Builder unloadedToolchainContext, PlatformKeys platformKeys)
+      throws InterruptedException, ToolchainException, ValueMissingException {
+
+    // Find the toolchains for the required toolchain types.
+    List<ToolchainResolutionValue.Key> registeredToolchainKeys = new ArrayList<>();
+    for (Label toolchainType : requiredToolchainTypes) {
+      registeredToolchainKeys.add(
+          ToolchainResolutionValue.key(
+              configurationKey,
+              toolchainType,
+              platformKeys.targetPlatformKey(),
+              platformKeys.executionPlatformKeys()));
+    }
+
+    Map<SkyKey, ValueOrException2<NoToolchainFoundException, InvalidToolchainLabelException>>
+        results =
+            environment.getValuesOrThrow(
+                registeredToolchainKeys,
+                NoToolchainFoundException.class,
+                InvalidToolchainLabelException.class);
+    boolean valuesMissing = false;
+
+    // Determine the potential set of toolchains.
+    Table<ConfiguredTargetKey, Label, Label> resolvedToolchains = HashBasedTable.create();
+    List<Label> missingToolchains = new ArrayList<>();
+    for (Map.Entry<
+            SkyKey, ValueOrException2<NoToolchainFoundException, InvalidToolchainLabelException>>
+        entry : results.entrySet()) {
+      try {
+        Label requiredToolchainType =
+            ((ToolchainResolutionValue.Key) entry.getKey().argument()).toolchainType();
+        ValueOrException2<NoToolchainFoundException, InvalidToolchainLabelException>
+            valueOrException = entry.getValue();
+        ToolchainResolutionValue toolchainResolutionValue =
+            (ToolchainResolutionValue) valueOrException.get();
+        if (toolchainResolutionValue == null) {
+          valuesMissing = true;
+          continue;
+        }
+
+        resolvedToolchains.putAll(
+            findPlatformsAndLabels(requiredToolchainType, toolchainResolutionValue));
+      } catch (NoToolchainFoundException e) {
+        // Save the missing type and continue looping to check for more.
+        missingToolchains.add(e.missingToolchainType());
+      }
+    }
+
+    if (!missingToolchains.isEmpty()) {
+      throw new UnresolvedToolchainsException(missingToolchains);
+    }
+
+    if (valuesMissing) {
+      throw new ValueMissingException();
+    }
+
+    // Find and return the first execution platform which has all required toolchains.
+    Optional<ConfiguredTargetKey> selectedExecutionPlatformKey;
+    if (requiredToolchainTypes.isEmpty()
+        && platformKeys.executionPlatformKeys().contains(platformKeys.hostPlatformKey())) {
+      // Fall back to the legacy behavior: use the host platform if it's available, otherwise the
+      // first execution platform.
+      selectedExecutionPlatformKey = Optional.of(platformKeys.hostPlatformKey());
+    } else {
+      // If there are no toolchains, this will return the first execution platform.
+      selectedExecutionPlatformKey =
+          findExecutionPlatformForToolchains(
+              platformKeys.executionPlatformKeys(), resolvedToolchains);
+    }
+
+    if (!selectedExecutionPlatformKey.isPresent()) {
+      throw new NoMatchingPlatformException(
+          requiredToolchainTypes,
+          platformKeys.executionPlatformKeys(),
+          platformKeys.targetPlatformKey());
+    }
+
+    Map<ConfiguredTargetKey, PlatformInfo> platforms =
+        PlatformLookupUtil.getPlatformInfo(
+            ImmutableList.of(selectedExecutionPlatformKey.get(), platformKeys.targetPlatformKey()),
+            environment);
+    if (platforms == null) {
+      throw new ValueMissingException();
+    }
+
+    unloadedToolchainContext.setExecutionPlatform(
+        platforms.get(selectedExecutionPlatformKey.get()));
+    unloadedToolchainContext.setTargetPlatform(platforms.get(platformKeys.targetPlatformKey()));
+
+    Map<Label, Label> toolchains = resolvedToolchains.row(selectedExecutionPlatformKey.get());
+    unloadedToolchainContext.setToolchainTypeToResolved(ImmutableBiMap.copyOf(toolchains));
+  }
+
+  /**
+   * Adds all of toolchain labels from{@code toolchainResolutionValue} to {@code
+   * resolvedToolchains}.
+   */
+  private static Table<ConfiguredTargetKey, Label, Label> findPlatformsAndLabels(
+      Label requiredToolchainType, ToolchainResolutionValue toolchainResolutionValue) {
+
+    Table<ConfiguredTargetKey, Label, Label> resolvedToolchains = HashBasedTable.create();
+    for (Map.Entry<ConfiguredTargetKey, Label> entry :
+        toolchainResolutionValue.availableToolchainLabels().entrySet()) {
+      resolvedToolchains.put(entry.getKey(), requiredToolchainType, entry.getValue());
+    }
+    return resolvedToolchains;
+  }
+
+  /**
+   * Finds the first platform from {@code availableExecutionPlatformKeys} that is present in {@code
+   * resolvedToolchains} and has all required toolchain types.
+   */
+  private Optional<ConfiguredTargetKey> findExecutionPlatformForToolchains(
+      ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
+      Table<ConfiguredTargetKey, Label, Label> resolvedToolchains) {
+    for (ConfiguredTargetKey executionPlatformKey : availableExecutionPlatformKeys) {
+      Map<Label, Label> toolchains = resolvedToolchains.row(executionPlatformKey);
+      if (!toolchains.keySet().containsAll(requiredToolchainTypes)) {
+        // Not all toolchains are present, keep going
+        continue;
+      }
+
+      if (debug) {
+        String selectedToolchains =
+            toolchains.entrySet().stream()
+                .map(e -> String.format("type %s -> toolchain %s", e.getKey(), e.getValue()))
+                .collect(joining(", "));
+        environment
+            .getListener()
+            .handle(
+                Event.info(
+                    String.format(
+                        "ToolchainUtil: Selected execution platform %s, %s",
+                        executionPlatformKey.getLabel(), selectedToolchains)));
+      }
+      return Optional.of(executionPlatformKey);
+    }
+
+    return Optional.empty();
+  }
+
+  /**
+   * Represents the state of toolchain resolution once the specific required toolchains have been
+   * determined, but before the toolchain dependencies have been resolved.
+   */
+  @AutoValue
+  public abstract static class UnloadedToolchainContext {
+
+    static Builder builder() {
+      return new AutoValue_ToolchainResolver_UnloadedToolchainContext.Builder();
+    }
+
+    /** Builder class to help create the {@link UnloadedToolchainContext}. */
+    @AutoValue.Builder
+    public interface Builder {
+      /** Sets a description of the target being used, for error messaging. */
+      Builder setTargetDescription(String targetDescription);
+
+      /** Sets the selected execution platform that these toolchains use. */
+      Builder setExecutionPlatform(PlatformInfo executionPlatform);
+
+      /** Sets the target platform that these toolchains generate output for. */
+      Builder setTargetPlatform(PlatformInfo targetPlatform);
+
+      /** Sets the toolchain types that were requested. */
+      Builder setRequiredToolchainTypes(Set<Label> requiredToolchainTypes);
+
+      Builder setToolchainTypeToResolved(ImmutableBiMap<Label, Label> toolchainTypeToResolved);
+
+      UnloadedToolchainContext build();
+    }
+
+    /** Returns a description of the target being used, for error messaging. */
+    abstract String targetDescription();
+
+    /** Returns the selected execution platform that these toolchains use. */
+    abstract PlatformInfo executionPlatform();
+
+    /** Returns the target platform that these toolchains generate output for. */
+    abstract PlatformInfo targetPlatform();
+
+    /** Returns the toolchain types that were requested. */
+    abstract ImmutableSet<Label> requiredToolchainTypes();
+
+    /** The map of toolchain type to resolved toolchain to be used. */
+    abstract ImmutableBiMap<Label, Label> toolchainTypeToResolved();
+
+    /** Returns the labels of the specific toolchains being used. */
+    public ImmutableSet<Label> resolvedToolchainLabels() {
+      return toolchainTypeToResolved().values();
+    }
+
+    /**
+     * Finishes preparing the {@link ToolchainContext} by finding the specific toolchain providers
+     * to be used for each toolchain type.
+     */
+    public ToolchainContext load(
+        OrderedSetMultimap<Attribute, ConfiguredTargetAndData> prerequisiteMap) {
+
+      ToolchainContext.Builder toolchainContext =
+          ToolchainContext.builder()
+              .setTargetDescription(targetDescription())
+              .setExecutionPlatform(executionPlatform())
+              .setTargetPlatform(targetPlatform())
+              .setRequiredToolchainTypes(requiredToolchainTypes())
+              .setResolvedToolchainLabels(resolvedToolchainLabels());
+
+      // Find the prerequisites associated with PlatformSemantics.RESOLVED_TOOLCHAINS_ATTR.
+      Optional<Attribute> toolchainAttribute =
+          prerequisiteMap.keys().stream()
+              .filter(Objects::nonNull)
+              .filter(
+                  attribute ->
+                      attribute.getName().equals(PlatformSemantics.RESOLVED_TOOLCHAINS_ATTR))
+              .findFirst();
+      ImmutableMap.Builder<Label, ToolchainInfo> toolchains = new ImmutableMap.Builder<>();
+      if (toolchainAttribute.isPresent()) {
+        for (ConfiguredTargetAndData target : prerequisiteMap.get(toolchainAttribute.get())) {
+          Label discoveredLabel = target.getTarget().getLabel();
+          Label toolchainType = toolchainTypeToResolved().inverse().get(discoveredLabel);
+
+          // If the toolchainType hadn't been resolved to an actual toolchain, resolution would have
+          // failed with an error much earlier. This null check is just for safety.
+          if (toolchainType != null) {
+            ToolchainInfo toolchainInfo =
+                PlatformProviderUtils.toolchain(target.getConfiguredTarget());
+            toolchains.put(toolchainType, toolchainInfo);
+          }
+
+          // Find any template variables present for this toolchain.
+          // TODO(jcater): save this somewhere.
+        }
+      }
+
+      return toolchainContext.setToolchains(toolchains.build()).build();
+    }
+  }
+
+  private static final class ValueMissingException extends Exception {
+    private ValueMissingException() {
+      super();
+    }
+  }
+
+  /** Exception used when no execution platform can be found. */
+  static final class NoMatchingPlatformException extends ToolchainException {
+    NoMatchingPlatformException(
+        Set<Label> requiredToolchains,
+        ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
+        ConfiguredTargetKey targetPlatformKey) {
+      super(formatError(requiredToolchains, availableExecutionPlatformKeys, targetPlatformKey));
+    }
+
+    private static String formatError(
+        Set<Label> requiredToolchains,
+        ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
+        ConfiguredTargetKey targetPlatformKey) {
+      if (requiredToolchains.isEmpty()) {
+        return String.format(
+            "Unable to find an execution platform for target platform %s"
+                + " from available execution platforms [%s]",
+            targetPlatformKey.getLabel(),
+            availableExecutionPlatformKeys.stream()
+                .map(key -> key.getLabel().toString())
+                .collect(Collectors.joining(", ")));
+      }
+      return String.format(
+          "Unable to find an execution platform for toolchains [%s] and target platform %s"
+              + " from available execution platforms [%s]",
+          Joiner.on(", ").join(requiredToolchains),
+          targetPlatformKey.getLabel(),
+          availableExecutionPlatformKeys.stream()
+              .map(key -> key.getLabel().toString())
+              .collect(Collectors.joining(", ")));
+    }
+  }
+
+  /** Exception used when a toolchain type is required but no matching toolchain is found. */
+  static final class UnresolvedToolchainsException extends ToolchainException {
+    UnresolvedToolchainsException(List<Label> missingToolchainTypes) {
+      super(
+          String.format(
+              "no matching toolchains found for types %s",
+              Joiner.on(", ").join(missingToolchainTypes)));
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index 4088d3f..2ab09fc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -30,6 +30,8 @@
 import com.google.devtools.build.lib.analysis.DependencyResolver.InconsistentAspectOrderException;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
+import com.google.devtools.build.lib.analysis.ToolchainResolver;
+import com.google.devtools.build.lib.analysis.ToolchainResolver.UnloadedToolchainContext;
 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.ConfigMatchingProvider;
@@ -402,26 +404,29 @@
       }
 
       // Determine what toolchains are needed by this target.
-      ToolchainContext toolchainContext;
-      try {
-        ImmutableSet<Label> requiredToolchains = aspect.getDefinition().getRequiredToolchains();
-        toolchainContext =
-            ToolchainUtil.createToolchainContext(
-                env,
-                String.format(
-                    "aspect %s applied to %s",
-                    aspect.getDescriptor().getDescription(),
-                    associatedConfiguredTargetAndData.getTarget().toString()),
-                requiredToolchains,
-                /* execConstraintLabels= */ ImmutableSet.of(),
-                key.getAspectConfigurationKey());
-      } catch (ToolchainException e) {
-        // TODO(katre): better error handling
-        throw new AspectCreationException(
-            e.getMessage(), new LabelCause(key.getLabel(), e.getMessage()));
-      }
-      if (env.valuesMissing()) {
-        return null;
+      UnloadedToolchainContext unloadedToolchainContext = null;
+      if (configuration != null) {
+        // Configuration can be null in the case of aspects applied to input files. In this case,
+        // there are no chances of toolchains being used, so skip it.
+        try {
+          ImmutableSet<Label> requiredToolchains = aspect.getDefinition().getRequiredToolchains();
+          unloadedToolchainContext =
+              new ToolchainResolver(env, BuildConfigurationValue.key(configuration))
+                  .setTargetDescription(
+                      String.format(
+                          "aspect %s applied to %s",
+                          aspect.getDescriptor().getDescription(),
+                          associatedConfiguredTargetAndData.getTarget()))
+                  .setRequiredToolchainTypes(requiredToolchains)
+                  .resolve();
+        } catch (ToolchainException e) {
+          // TODO(katre): better error handling
+          throw new AspectCreationException(
+              e.getMessage(), new LabelCause(key.getLabel(), e.getMessage()));
+        }
+        if (env.valuesMissing()) {
+          return null;
+        }
       }
 
       OrderedSetMultimap<Attribute, ConfiguredTargetAndData> depValueMap;
@@ -433,9 +438,9 @@
                 originalTargetAndAspectConfiguration,
                 aspectPath,
                 configConditions,
-                toolchainContext == null
+                unloadedToolchainContext == null
                     ? ImmutableSet.of()
-                    : toolchainContext.resolvedToolchainLabels(),
+                    : unloadedToolchainContext.resolvedToolchainLabels(),
                 ruleClassProvider,
                 view.getHostConfiguration(originalTargetAndAspectConfiguration.getConfiguration()),
                 transitivePackagesForPackageRootResolution,
@@ -453,8 +458,9 @@
       }
 
       // Load the requested toolchains into the ToolchainContext, now that we have dependencies.
-      if (toolchainContext != null) {
-        toolchainContext.resolveToolchains(depValueMap);
+      ToolchainContext toolchainContext = null;
+      if (unloadedToolchainContext != null) {
+        toolchainContext = unloadedToolchainContext.load(depValueMap);
       }
 
       return createAspect(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index bad9ec0..f88f7b6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
+import com.google.common.collect.Streams;
 import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
@@ -32,6 +33,8 @@
 import com.google.devtools.build.lib.analysis.PlatformSemantics;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
+import com.google.devtools.build.lib.analysis.ToolchainResolver;
+import com.google.devtools.build.lib.analysis.ToolchainResolver.UnloadedToolchainContext;
 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.ConfigMatchingProvider;
@@ -229,7 +232,7 @@
 
     SkyframeDependencyResolver resolver = view.createDependencyResolver(env);
 
-    ToolchainContext toolchainContext = null;
+    UnloadedToolchainContext unloadedToolchainContext = null;
 
     // TODO(janakr): this acquire() call may tie up this thread indefinitely, reducing the
     // parallelism of Skyframe. This is a strict improvement over the prior state of the code, in
@@ -272,13 +275,12 @@
 
           // Collect local (target, rule) constraints for filtering out execution platforms.
           ImmutableSet<Label> execConstraintLabels = getExecutionPlatformConstraints(rule);
-          toolchainContext =
-              ToolchainUtil.createToolchainContext(
-                  env,
-                  rule.toString(),
-                  requiredToolchains,
-                  execConstraintLabels,
-                  configuredTargetKey.getConfigurationKey());
+          unloadedToolchainContext =
+              new ToolchainResolver(env, configuredTargetKey.getConfigurationKey())
+                  .setTargetDescription(rule.toString())
+                  .setRequiredToolchainTypes(requiredToolchains)
+                  .setExecConstraintLabels(execConstraintLabels)
+                  .resolve();
           if (env.valuesMissing()) {
             return null;
           }
@@ -293,9 +295,9 @@
               ctgValue,
               ImmutableList.<Aspect>of(),
               configConditions,
-              toolchainContext == null
+              unloadedToolchainContext == null
                   ? ImmutableSet.of()
-                  : toolchainContext.resolvedToolchainLabels(),
+                  : unloadedToolchainContext.resolvedToolchainLabels(),
               ruleClassProvider,
               view.getHostConfiguration(configuration),
               transitivePackagesForPackageRootResolution,
@@ -312,8 +314,9 @@
       Preconditions.checkNotNull(depValueMap);
 
       // Load the requested toolchains into the ToolchainContext, now that we have dependencies.
-      if (toolchainContext != null) {
-        toolchainContext.resolveToolchains(depValueMap);
+      ToolchainContext toolchainContext = null;
+      if (unloadedToolchainContext != null) {
+        toolchainContext = unloadedToolchainContext.load(depValueMap);
       }
 
       ConfiguredTargetValue ans =
@@ -332,10 +335,14 @@
         ConfiguredValueCreationException cvce = (ConfiguredValueCreationException) e.getCause();
 
         // Check if this is caused by an unresolved toolchain, and report it as such.
-        if (toolchainContext != null) {
+        if (unloadedToolchainContext != null) {
+          UnloadedToolchainContext finalUnloadedToolchainContext = unloadedToolchainContext;
           Set<Label> toolchainDependencyErrors =
-              toolchainContext.filterToolchainLabels(
-                  Iterables.transform(cvce.getRootCauses(), Cause::getLabel));
+              Streams.stream(cvce.getRootCauses())
+                  .map(Cause::getLabel)
+                  .filter(l -> finalUnloadedToolchainContext.resolvedToolchainLabels().contains(l))
+                  .collect(ImmutableSet.toImmutableSet());
+
           if (!toolchainDependencyErrors.isEmpty()) {
             env.getListener()
                 .handle(
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 22f3d66..8d9309f 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
@@ -64,7 +64,6 @@
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.Dependency;
-import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
@@ -1014,17 +1013,9 @@
   }
 
   @VisibleForTesting
-  public ToolchainContext getToolchainContextForTesting(
-      Set<Label> requiredToolchains, BuildConfiguration config, ExtendedEventHandler eventHandler)
-      throws ToolchainException, InterruptedException {
-    SkyFunctionEnvironmentForTesting env =
-        new SkyFunctionEnvironmentForTesting(buildDriver, eventHandler, this);
-    return ToolchainUtil.createToolchainContext(
-        env,
-        "",
-        requiredToolchains,
-        /* execConstraintLabels= */ ImmutableSet.of(),
-        config == null ? null : BuildConfigurationValue.key(config));
+  public SkyFunctionEnvironmentForTesting getSkyFunctionEnvironmentForTesting(
+      ExtendedEventHandler eventHandler) {
+    return new SkyFunctionEnvironmentForTesting(buildDriver, eventHandler, this);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionValue.java
index abaa41f..341be5a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionValue.java
@@ -48,7 +48,7 @@
   @AutoCodec
   @AutoCodec.VisibleForSerialization
   @AutoValue
-  abstract static class Key implements SkyKey {
+  public abstract static class Key implements SkyKey {
 
     @Override
     public SkyFunctionName functionName() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
deleted file mode 100644
index 8399fb7..0000000
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
+++ /dev/null
@@ -1,469 +0,0 @@
-// Copyright 2017 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 static com.google.common.collect.ImmutableList.toImmutableList;
-import static java.util.stream.Collectors.joining;
-
-import com.google.auto.value.AutoValue;
-import com.google.common.base.Joiner;
-import com.google.common.base.Optional;
-import com.google.common.collect.HashBasedTable;
-import com.google.common.collect.ImmutableBiMap;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Table;
-import com.google.devtools.build.lib.analysis.PlatformConfiguration;
-import com.google.devtools.build.lib.analysis.PlatformOptions;
-import com.google.devtools.build.lib.analysis.ToolchainContext;
-import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
-import com.google.devtools.build.lib.analysis.platform.ConstraintValueInfo;
-import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
-import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.skyframe.ConstraintValueLookupUtil.InvalidConstraintValueException;
-import com.google.devtools.build.lib.skyframe.PlatformLookupUtil.InvalidPlatformException;
-import com.google.devtools.build.lib.skyframe.RegisteredToolchainsFunction.InvalidToolchainLabelException;
-import com.google.devtools.build.lib.skyframe.ToolchainResolutionFunction.NoToolchainFoundException;
-import com.google.devtools.build.skyframe.SkyFunction.Environment;
-import com.google.devtools.build.skyframe.SkyKey;
-import com.google.devtools.build.skyframe.ValueOrException2;
-import java.util.ArrayList;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-import java.util.stream.Collectors;
-import javax.annotation.Nullable;
-
-/**
- * Common code to create a {@link ToolchainContext} given a set of required toolchain type labels.
- */
-// TODO(katre): Refactor this and ToolchainContext into something nicer to work with and with
-// fewer static methods everywhere.
-public class ToolchainUtil {
-
-  /**
-   * Returns a new {@link ToolchainContext}, containing:
-   *
-   * <ul>
-   *   <li>If {@code requiredToolchains} was non-empty, the resolved toolchains and execution
-   *       platform (as labels), based on the results of the {@link ToolchainResolutionFunction}
-   *   <li>If {@code requiredToolchains} was empty:
-   *       <ul>
-   *         <li>The resolved toolchains will be empty.
-   *         <li>The execution platform will be the host platform, if the host platform was in the
-   *             set of available execution platforms.
-   *         <li>Otherwise, the execution platform will be the first available execution platform.
-   *       </ul>
-   * </ul>
-   *
-   * @param env the Skyframe environment to use to acquire dependencies
-   * @param targetDescription a description of the target use, for error and debug message context
-   * @param requiredToolchains the required toolchain types that must be resolved
-   * @param execConstraintLabels extra constraints on the execution platform to select
-   * @param configurationKey the build configuration to use for resolving other targets
-   */
-  @Nullable
-  static ToolchainContext createToolchainContext(
-      Environment env,
-      String targetDescription,
-      Set<Label> requiredToolchains,
-      Set<Label> execConstraintLabels,
-      @Nullable BuildConfigurationValue.Key configurationKey)
-      throws InterruptedException, ToolchainException {
-
-    // In some cases this is called with a missing configuration, so we skip toolchain context.
-    if (configurationKey == null) {
-      return null;
-    }
-
-    // This call could be combined with the call below, but this SkyFunction is evaluated so rarely
-    // it's not worth optimizing.
-    BuildConfigurationValue value = (BuildConfigurationValue) env.getValue(configurationKey);
-    if (env.valuesMissing()) {
-      return null;
-    }
-    BuildConfiguration configuration = value.getConfiguration();
-
-    // Load the target and host platform keys.
-    PlatformConfiguration platformConfiguration =
-        configuration.getFragment(PlatformConfiguration.class);
-    if (platformConfiguration == null) {
-      return null;
-    }
-    Label hostPlatformLabel = platformConfiguration.getHostPlatform();
-    Label targetPlatformLabel = platformConfiguration.getTargetPlatform();
-
-    ConfiguredTargetKey hostPlatformKey = ConfiguredTargetKey.of(hostPlatformLabel, configuration);
-    ConfiguredTargetKey targetPlatformKey =
-        ConfiguredTargetKey.of(targetPlatformLabel, configuration);
-    ImmutableList<ConfiguredTargetKey> execConstraintKeys =
-        execConstraintLabels
-            .stream()
-            .map(label -> ConfiguredTargetKey.of(label, configuration))
-            .collect(toImmutableList());
-
-    // Load the host and target platforms early, to check for errors.
-    PlatformLookupUtil.getPlatformInfo(ImmutableList.of(hostPlatformKey, targetPlatformKey), env);
-    if (env.valuesMissing()) {
-      return null;
-    }
-
-    // Load all available execution platform keys. This will find any errors in the execution
-    // platform definitions.
-    RegisteredExecutionPlatformsValue registeredExecutionPlatforms =
-        loadRegisteredExecutionPlatforms(env, configurationKey);
-    if (registeredExecutionPlatforms == null) {
-      return null;
-    }
-
-    ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys =
-        new ImmutableList.Builder<ConfiguredTargetKey>()
-            .addAll(registeredExecutionPlatforms.registeredExecutionPlatformKeys())
-            .add(hostPlatformKey)
-            .build();
-
-    // Filter out execution platforms that don't satisfy the extra constraints.
-    boolean debug = configuration.getOptions().get(PlatformOptions.class).toolchainResolutionDebug;
-    availableExecutionPlatformKeys =
-        filterPlatforms(availableExecutionPlatformKeys, execConstraintKeys, env, debug);
-    if (availableExecutionPlatformKeys == null) {
-      return null;
-    }
-
-    ResolvedToolchains resolvedToolchains =
-        resolveToolchainLabels(
-            env,
-            requiredToolchains,
-            configurationKey,
-            hostPlatformKey,
-            availableExecutionPlatformKeys,
-            targetPlatformKey,
-            debug);
-    if (resolvedToolchains == null) {
-      return null;
-    }
-
-    return createContext(
-        env,
-        targetDescription,
-        resolvedToolchains.executionPlatformKey(),
-        resolvedToolchains.targetPlatformKey(),
-        requiredToolchains,
-        resolvedToolchains.toolchains());
-  }
-
-  private static RegisteredExecutionPlatformsValue loadRegisteredExecutionPlatforms(
-      Environment env, BuildConfigurationValue.Key configurationKey)
-      throws InterruptedException, InvalidPlatformException {
-      RegisteredExecutionPlatformsValue registeredExecutionPlatforms =
-          (RegisteredExecutionPlatformsValue)
-              env.getValueOrThrow(
-                  RegisteredExecutionPlatformsValue.key(configurationKey),
-                  InvalidPlatformException.class);
-      if (registeredExecutionPlatforms == null) {
-        return null;
-      }
-      return registeredExecutionPlatforms;
-  }
-
-  /** Data class to hold the result of resolving toolchain labels. */
-  @AutoValue
-  protected abstract static class ResolvedToolchains {
-
-    abstract ConfiguredTargetKey executionPlatformKey();
-
-    abstract ConfiguredTargetKey targetPlatformKey();
-
-    abstract ImmutableBiMap<Label, Label> toolchains();
-
-    protected static ResolvedToolchains create(
-        ConfiguredTargetKey executionPlatformKey,
-        ConfiguredTargetKey targetPlatformKey,
-        Map<Label, Label> toolchains) {
-      return new AutoValue_ToolchainUtil_ResolvedToolchains(
-          executionPlatformKey, targetPlatformKey, ImmutableBiMap.copyOf(toolchains));
-    }
-  }
-
-  @Nullable
-  private static ResolvedToolchains resolveToolchainLabels(
-      Environment env,
-      Set<Label> requiredToolchains,
-      BuildConfigurationValue.Key configurationKey,
-      ConfiguredTargetKey hostPlatformKey,
-      ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
-      ConfiguredTargetKey targetPlatformKey,
-      boolean debug)
-      throws InterruptedException, ToolchainException {
-
-    // Find the toolchains for the required toolchain types.
-    List<ToolchainResolutionValue.Key> registeredToolchainKeys = new ArrayList<>();
-    for (Label toolchainType : requiredToolchains) {
-      registeredToolchainKeys.add(
-          ToolchainResolutionValue.key(
-              configurationKey, toolchainType, targetPlatformKey, availableExecutionPlatformKeys));
-    }
-
-    Map<SkyKey, ValueOrException2<NoToolchainFoundException, InvalidToolchainLabelException>>
-        results =
-            env.getValuesOrThrow(
-                registeredToolchainKeys,
-                NoToolchainFoundException.class,
-                InvalidToolchainLabelException.class);
-    boolean valuesMissing = false;
-
-    // Determine the potential set of toolchains.
-    Table<ConfiguredTargetKey, Label, Label> resolvedToolchains = HashBasedTable.create();
-    List<Label> missingToolchains = new ArrayList<>();
-    for (Map.Entry<
-            SkyKey, ValueOrException2<NoToolchainFoundException, InvalidToolchainLabelException>>
-        entry : results.entrySet()) {
-      try {
-        Label requiredToolchainType =
-            ((ToolchainResolutionValue.Key) entry.getKey().argument()).toolchainType();
-        ValueOrException2<NoToolchainFoundException, InvalidToolchainLabelException>
-            valueOrException = entry.getValue();
-        if (valueOrException.get() == null) {
-          valuesMissing = true;
-          continue;
-        }
-
-        ToolchainResolutionValue toolchainResolutionValue =
-            (ToolchainResolutionValue) valueOrException.get();
-        addPlatformsAndLabels(resolvedToolchains, requiredToolchainType, toolchainResolutionValue);
-      } catch (NoToolchainFoundException e) {
-        // Save the missing type and continue looping to check for more.
-        missingToolchains.add(e.missingToolchainType());
-      }
-    }
-
-    if (!missingToolchains.isEmpty()) {
-      throw new UnresolvedToolchainsException(missingToolchains);
-    }
-
-    if (valuesMissing) {
-      return null;
-    }
-
-    // Find and return the first execution platform which has all required toolchains.
-    Optional<ConfiguredTargetKey> selectedExecutionPlatformKey;
-    if (requiredToolchains.isEmpty() && availableExecutionPlatformKeys.contains(hostPlatformKey)) {
-      // Fall back to the legacy behavior: use the host platform if it's available, otherwise the
-      // first execution platform.
-      selectedExecutionPlatformKey = Optional.of(hostPlatformKey);
-    } else {
-      // If there are no toolchains, this will return the first execution platform.
-      selectedExecutionPlatformKey =
-          findExecutionPlatformForToolchains(
-              env, requiredToolchains, availableExecutionPlatformKeys, resolvedToolchains, debug);
-    }
-
-    if (!selectedExecutionPlatformKey.isPresent()) {
-      throw new NoMatchingPlatformException(
-          requiredToolchains, availableExecutionPlatformKeys, targetPlatformKey);
-    }
-
-    return ResolvedToolchains.create(
-        selectedExecutionPlatformKey.get(),
-        targetPlatformKey,
-        resolvedToolchains.row(selectedExecutionPlatformKey.get()));
-  }
-
-  private static Optional<ConfiguredTargetKey> findExecutionPlatformForToolchains(
-      Environment env,
-      Set<Label> requiredToolchains,
-      ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
-      Table<ConfiguredTargetKey, Label, Label> resolvedToolchains,
-      boolean debug) {
-    for (ConfiguredTargetKey executionPlatformKey : availableExecutionPlatformKeys) {
-      // PlatformInfo executionPlatform = platforms.get(executionPlatformKey);
-      Map<Label, Label> toolchains = resolvedToolchains.row(executionPlatformKey);
-      if (!toolchains.keySet().containsAll(requiredToolchains)) {
-        // Not all toolchains are present, keep going
-        continue;
-      }
-
-      if (debug) {
-        env.getListener()
-            .handle(
-                Event.info(
-                    String.format(
-                        "ToolchainUtil: Selected execution platform %s, %s",
-                        executionPlatformKey.getLabel(),
-                        toolchains
-                            .entrySet()
-                            .stream()
-                            .map(
-                                e ->
-                                    String.format(
-                                        "type %s -> toolchain %s", e.getKey(), e.getValue()))
-                            .collect(joining(", ")))));
-      }
-      return Optional.of(executionPlatformKey);
-    }
-
-    return Optional.absent();
-  }
-
-  private static void addPlatformsAndLabels(
-      Table<ConfiguredTargetKey, Label, Label> resolvedToolchains,
-      Label requiredToolchainType,
-      ToolchainResolutionValue toolchainResolutionValue) {
-
-    for (Map.Entry<ConfiguredTargetKey, Label> entry :
-        toolchainResolutionValue.availableToolchainLabels().entrySet()) {
-      resolvedToolchains.put(entry.getKey(), requiredToolchainType, entry.getValue());
-    }
-  }
-
-  @Nullable
-  private static ToolchainContext createContext(
-      Environment env,
-      String targetDescription,
-      ConfiguredTargetKey executionPlatformKey,
-      ConfiguredTargetKey targetPlatformKey,
-      Set<Label> requiredToolchains,
-      ImmutableBiMap<Label, Label> toolchains)
-      throws InterruptedException, InvalidPlatformException {
-
-    Map<ConfiguredTargetKey, PlatformInfo> platforms =
-        PlatformLookupUtil.getPlatformInfo(
-            ImmutableList.of(executionPlatformKey, targetPlatformKey), env);
-
-    if (platforms == null) {
-      return null;
-    }
-
-    return ToolchainContext.create(
-        targetDescription,
-        platforms.get(executionPlatformKey),
-        platforms.get(targetPlatformKey),
-        requiredToolchains,
-        toolchains);
-  }
-
-  @Nullable
-  private static ImmutableList<ConfiguredTargetKey> filterPlatforms(
-      ImmutableList<ConfiguredTargetKey> platformKeys,
-      ImmutableList<ConfiguredTargetKey> constraintKeys,
-      Environment env,
-      boolean debug)
-      throws InterruptedException, InvalidConstraintValueException, InvalidPlatformException {
-
-    // Short circuit if not needed.
-    if (constraintKeys.isEmpty()) {
-      return platformKeys;
-    }
-
-    Map<ConfiguredTargetKey, PlatformInfo> platformInfoMap =
-        PlatformLookupUtil.getPlatformInfo(platformKeys, env);
-    if (platformInfoMap == null) {
-      return null;
-    }
-    List<ConstraintValueInfo> constraints =
-        ConstraintValueLookupUtil.getConstraintValueInfo(constraintKeys, env);
-    if (constraints == null) {
-      return null;
-    }
-
-    return platformKeys
-        .stream()
-        .filter(key -> filterPlatform(platformInfoMap.get(key), constraints, env, debug))
-        .collect(toImmutableList());
-  }
-
-  private static boolean filterPlatform(
-      PlatformInfo platformInfo,
-      List<ConstraintValueInfo> constraints,
-      Environment env,
-      boolean debug) {
-    for (ConstraintValueInfo filterConstraint : constraints) {
-      ConstraintValueInfo platformInfoConstraint =
-          platformInfo.getConstraint(filterConstraint.constraint());
-      if (platformInfoConstraint == null || !platformInfoConstraint.equals(filterConstraint)) {
-        // The value for this setting is not present in the platform, or doesn't match the expected
-        // value.
-        if (debug) {
-          env.getListener()
-              .handle(
-                  Event.info(
-                      String.format(
-                          "ToolchainUtil: Removed execution platform %s from"
-                              + " available execution platforms, it is missing constraint %s",
-                          platformInfo.label(), filterConstraint.label())));
-        }
-        return false;
-      }
-    }
-
-    return true;
-  }
-
-  /** Exception used when no execution platform can be found. */
-  static final class NoMatchingPlatformException extends ToolchainException {
-    NoMatchingPlatformException() {
-      super("No available execution platform satisfies all requested toolchain types");
-    }
-
-    public NoMatchingPlatformException(
-        Set<Label> requiredToolchains,
-        ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
-        ConfiguredTargetKey targetPlatformKey) {
-      super(formatError(requiredToolchains, availableExecutionPlatformKeys, targetPlatformKey));
-    }
-
-    private static String formatError(
-        Set<Label> requiredToolchains,
-        ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
-        ConfiguredTargetKey targetPlatformKey) {
-      if (requiredToolchains.isEmpty()) {
-        return String.format(
-            "Unable to find an execution platform for target platform %s"
-                + " from available execution platforms [%s]",
-            targetPlatformKey.getLabel(),
-            availableExecutionPlatformKeys
-                .stream()
-                .map(key -> key.getLabel().toString())
-                .collect(Collectors.joining(", ")));
-      }
-      return String.format(
-          "Unable to find an execution platform for toolchains [%s] and target platform %s"
-              + " from available execution platforms [%s]",
-          Joiner.on(", ").join(requiredToolchains),
-          targetPlatformKey.getLabel(),
-          availableExecutionPlatformKeys
-              .stream()
-              .map(key -> key.getLabel().toString())
-              .collect(Collectors.joining(", ")));
-    }
-  }
-
-  /** Exception used when a toolchain type is required but no matching toolchain is found. */
-  public static final class UnresolvedToolchainsException extends ToolchainException {
-    private final ImmutableList<Label> missingToolchainTypes;
-
-    public UnresolvedToolchainsException(List<Label> missingToolchainTypes) {
-      super(
-          String.format(
-              "no matching toolchains found for types %s",
-              Joiner.on(", ").join(missingToolchainTypes)));
-      this.missingToolchainTypes = ImmutableList.copyOf(missingToolchainTypes);
-    }
-
-    public ImmutableList<Label> missingToolchainTypes() {
-      return missingToolchainTypes;
-    }
-  }
-}
diff --git a/src/test/java/com/google/devtools/build/lib/BUILD b/src/test/java/com/google/devtools/build/lib/BUILD
index 4f04b02..25ce176 100644
--- a/src/test/java/com/google/devtools/build/lib/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/BUILD
@@ -818,6 +818,7 @@
         "//src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs",
         "//src/main/java/com/google/devtools/build/skyframe",
         "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
+        "//src/test/java/com/google/devtools/build/lib/rules/platform:testutil",
         "//src/test/java/com/google/devtools/build/lib/skyframe:testutil",
         "//third_party:auto_value",
         "//third_party:jsr305",
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java b/src/test/java/com/google/devtools/build/lib/analysis/ToolchainResolverTest.java
similarity index 61%
rename from src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
rename to src/test/java/com/google/devtools/build/lib/analysis/ToolchainResolverTest.java
index 8d77206..37efeb2 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/ToolchainResolverTest.java
@@ -1,4 +1,4 @@
-// Copyright 2017 The Bazel Authors. All rights reserved.
+// 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.
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package com.google.devtools.build.lib.skyframe;
+package com.google.devtools.build.lib.analysis;
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.skyframe.EvaluationResultSubjectFactory.assertThatEvaluationResult;
@@ -21,15 +21,16 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.analysis.BlazeDirectories;
-import com.google.devtools.build.lib.analysis.ToolchainContext;
+import com.google.devtools.build.lib.analysis.ToolchainResolver.NoMatchingPlatformException;
+import com.google.devtools.build.lib.analysis.ToolchainResolver.UnloadedToolchainContext;
+import com.google.devtools.build.lib.analysis.ToolchainResolver.UnresolvedToolchainsException;
 import com.google.devtools.build.lib.analysis.util.AnalysisMock;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.rules.platform.ToolchainTestCase;
+import com.google.devtools.build.lib.skyframe.BuildConfigurationValue;
 import com.google.devtools.build.lib.skyframe.ConstraintValueLookupUtil.InvalidConstraintValueException;
 import com.google.devtools.build.lib.skyframe.PlatformLookupUtil.InvalidPlatformException;
-import com.google.devtools.build.lib.skyframe.ToolchainUtil.NoMatchingPlatformException;
-import com.google.devtools.build.lib.skyframe.ToolchainUtil.UnresolvedToolchainsException;
+import com.google.devtools.build.lib.skyframe.ToolchainException;
 import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyFunction;
@@ -43,17 +44,15 @@
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-/** Tests for {@link ToolchainUtil}. */
+/** Tests for {@link ToolchainResolver}. */
 @RunWith(JUnit4.class)
-public class ToolchainUtilTest extends ToolchainTestCase {
-
+public class ToolchainResolverTest extends ToolchainTestCase {
   /**
-   * An {@link AnalysisMock} that injects {@link CreateToolchainContextFunction} into the Skyframe
+   * An {@link AnalysisMock} that injects {@link ResolveToolchainsFunction} into the Skyframe
    * executor.
    */
-  private static final class AnalysisMockWithCreateToolchainContextFunction
-      extends AnalysisMock.Delegate {
-    AnalysisMockWithCreateToolchainContextFunction() {
+  private static final class LocalAnalysisMock extends AnalysisMock.Delegate {
+    LocalAnalysisMock() {
       super(AnalysisMock.get());
     }
 
@@ -62,18 +61,18 @@
         BlazeDirectories directories) {
       return ImmutableMap.<SkyFunctionName, SkyFunction>builder()
           .putAll(super.getSkyFunctions(directories))
-          .put(CREATE_TOOLCHAIN_CONTEXT_FUNCTION, new CreateToolchainContextFunction())
+          .put(RESOLVE_TOOLCHAINS_FUNCTION, new ResolveToolchainsFunction())
           .build();
     }
   }
 
   @Override
   protected AnalysisMock getAnalysisMock() {
-    return new AnalysisMockWithCreateToolchainContextFunction();
+    return new LocalAnalysisMock();
   }
 
   @Test
-  public void createToolchainContext() throws Exception {
+  public void resolve() throws Exception {
     // This should select platform mac, toolchain extra_toolchain_mac, because platform
     // mac is listed first.
     addToolchain(
@@ -93,58 +92,58 @@
         "register_execution_platforms('//platforms:mac', '//platforms:linux')");
 
     useConfiguration("--platforms=//platforms:linux");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
-            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create("test", ImmutableSet.of(testToolchainType), targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasNoError();
-    ToolchainContext toolchainContext = result.get(key).toolchainContext();
-    assertThat(toolchainContext).isNotNull();
+    UnloadedToolchainContext unloadedToolchainContext = result.get(key).unloadedToolchainContext();
+    assertThat(unloadedToolchainContext).isNotNull();
 
-    assertThat(toolchainContext.requiredToolchainTypes()).containsExactly(testToolchainType);
-    assertThat(toolchainContext.resolvedToolchainLabels())
+    assertThat(unloadedToolchainContext.requiredToolchainTypes())
+        .containsExactly(testToolchainType);
+    assertThat(unloadedToolchainContext.resolvedToolchainLabels())
         .containsExactly(Label.parseAbsoluteUnchecked("//extra:extra_toolchain_mac_impl"));
 
-    assertThat(toolchainContext.executionPlatform()).isNotNull();
-    assertThat(toolchainContext.executionPlatform().label())
+    assertThat(unloadedToolchainContext.executionPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.executionPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:mac"));
 
-    assertThat(toolchainContext.targetPlatform()).isNotNull();
-    assertThat(toolchainContext.targetPlatform().label())
+    assertThat(unloadedToolchainContext.targetPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.targetPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
   }
 
   @Test
-  public void createToolchainContext_noToolchainType() throws Exception {
+  public void resolve_noToolchainType() throws Exception {
     scratch.file("host/BUILD", "platform(name = 'host')");
     rewriteWorkspace("register_execution_platforms('//platforms:mac', '//platforms:linux')");
 
     useConfiguration("--host_platform=//host:host", "--platforms=//platforms:linux");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create("test", ImmutableSet.of(), targetConfigKey);
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create("test", ImmutableSet.of(), targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasNoError();
-    ToolchainContext toolchainContext = result.get(key).toolchainContext();
-    assertThat(toolchainContext).isNotNull();
+    UnloadedToolchainContext unloadedToolchainContext = result.get(key).unloadedToolchainContext();
+    assertThat(unloadedToolchainContext).isNotNull();
 
-    assertThat(toolchainContext.requiredToolchainTypes()).isEmpty();
+    assertThat(unloadedToolchainContext.requiredToolchainTypes()).isEmpty();
 
     // With no toolchains requested, should fall back to the host platform.
-    assertThat(toolchainContext.executionPlatform()).isNotNull();
-    assertThat(toolchainContext.executionPlatform().label())
+    assertThat(unloadedToolchainContext.executionPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.executionPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//host:host"));
 
-    assertThat(toolchainContext.targetPlatform()).isNotNull();
-    assertThat(toolchainContext.targetPlatform().label())
+    assertThat(unloadedToolchainContext.targetPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.targetPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
   }
 
   @Test
-  public void createToolchainContext_noToolchainType_hostNotAvailable() throws Exception {
+  public void resolve_noToolchainType_hostNotAvailable() throws Exception {
     scratch.file("host/BUILD", "platform(name = 'host')");
     scratch.file(
         "sample/BUILD",
@@ -162,44 +161,41 @@
         "    '//sample:sample_a', '//sample:sample_b')");
 
     useConfiguration("--host_platform=//host:host", "--platforms=//platforms:linux");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create(
             "test",
             ImmutableSet.of(),
             ImmutableSet.of(Label.parseAbsoluteUnchecked("//sample:demo_b")),
             targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasNoError();
-    ToolchainContext toolchainContext = result.get(key).toolchainContext();
-    assertThat(toolchainContext).isNotNull();
+    UnloadedToolchainContext unloadedToolchainContext = result.get(key).unloadedToolchainContext();
+    assertThat(unloadedToolchainContext).isNotNull();
 
-    assertThat(toolchainContext.requiredToolchainTypes()).isEmpty();
+    assertThat(unloadedToolchainContext.requiredToolchainTypes()).isEmpty();
 
-    // With no toolchains requested, should fall back to the host platform.
-    assertThat(toolchainContext.executionPlatform()).isNotNull();
-    assertThat(toolchainContext.executionPlatform().label())
+    assertThat(unloadedToolchainContext.executionPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.executionPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//sample:sample_b"));
 
-    assertThat(toolchainContext.targetPlatform()).isNotNull();
-    assertThat(toolchainContext.targetPlatform().label())
+    assertThat(unloadedToolchainContext.targetPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.targetPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
   }
 
   @Test
-  public void createToolchainContext_unavailableToolchainType_single() throws Exception {
-    useConfiguration(
-        "--host_platform=//platforms:linux",
-        "--platforms=//platforms:mac");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
+  public void resolve_unavailableToolchainType_single() throws Exception {
+    useConfiguration("--host_platform=//platforms:linux", "--platforms=//platforms:mac");
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create(
             "test",
             ImmutableSet.of(
                 testToolchainType, Label.parseAbsoluteUnchecked("//fake/toolchain:type_1")),
             targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result)
         .hasErrorEntryForKeyThat(key)
@@ -213,12 +209,10 @@
   }
 
   @Test
-  public void createToolchainContext_unavailableToolchainType_multiple() throws Exception {
-    useConfiguration(
-        "--host_platform=//platforms:linux",
-        "--platforms=//platforms:mac");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
+  public void resolve_unavailableToolchainType_multiple() throws Exception {
+    useConfiguration("--host_platform=//platforms:linux", "--platforms=//platforms:mac");
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create(
             "test",
             ImmutableSet.of(
                 testToolchainType,
@@ -226,7 +220,7 @@
                 Label.parseAbsoluteUnchecked("//fake/toolchain:type_2")),
             targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result)
         .hasErrorEntryForKeyThat(key)
@@ -236,14 +230,13 @@
   }
 
   @Test
-  public void createToolchainContext_invalidTargetPlatform_badTarget() throws Exception {
+  public void resolve_invalidTargetPlatform_badTarget() throws Exception {
     scratch.file("invalid/BUILD", "filegroup(name = 'not_a_platform')");
     useConfiguration("--platforms=//invalid:not_a_platform");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
-            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create("test", ImmutableSet.of(testToolchainType), targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasError();
     assertThatEvaluationResult(result)
@@ -260,14 +253,13 @@
   }
 
   @Test
-  public void createToolchainContext_invalidTargetPlatform_badPackage() throws Exception {
+  public void resolve_invalidTargetPlatform_badPackage() throws Exception {
     scratch.resolve("invalid").delete();
     useConfiguration("--platforms=//invalid:not_a_platform");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
-            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create("test", ImmutableSet.of(testToolchainType), targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasError();
     assertThatEvaluationResult(result)
@@ -282,14 +274,13 @@
   }
 
   @Test
-  public void createToolchainContext_invalidHostPlatform() throws Exception {
+  public void resolve_invalidHostPlatform() throws Exception {
     scratch.file("invalid/BUILD", "filegroup(name = 'not_a_platform')");
     useConfiguration("--host_platform=//invalid:not_a_platform");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
-            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create("test", ImmutableSet.of(testToolchainType), targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasError();
     assertThatEvaluationResult(result)
@@ -304,14 +295,13 @@
   }
 
   @Test
-  public void createToolchainContext_invalidExecutionPlatform() throws Exception {
+  public void resolve_invalidExecutionPlatform() throws Exception {
     scratch.file("invalid/BUILD", "filegroup(name = 'not_a_platform')");
     useConfiguration("--extra_execution_platforms=//invalid:not_a_platform");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
-            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create("test", ImmutableSet.of(testToolchainType), targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasError();
     assertThatEvaluationResult(result)
@@ -326,7 +316,7 @@
   }
 
   @Test
-  public void createToolchainContext_execConstraints() throws Exception {
+  public void resolve_execConstraints() throws Exception {
     // This should select platform linux, toolchain extra_toolchain_linux, due to extra constraints,
     // even though platform mac is registered first.
     addToolchain(
@@ -346,42 +336,43 @@
         "register_execution_platforms('//platforms:mac', '//platforms:linux')");
 
     useConfiguration("--platforms=//platforms:linux");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create(
             "test",
             ImmutableSet.of(testToolchainType),
             ImmutableSet.of(Label.parseAbsoluteUnchecked("//constraints:linux")),
             targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasNoError();
-    ToolchainContext toolchainContext = result.get(key).toolchainContext();
-    assertThat(toolchainContext).isNotNull();
+    UnloadedToolchainContext unloadedToolchainContext = result.get(key).unloadedToolchainContext();
+    assertThat(unloadedToolchainContext).isNotNull();
 
-    assertThat(toolchainContext.requiredToolchainTypes()).containsExactly(testToolchainType);
-    assertThat(toolchainContext.resolvedToolchainLabels())
+    assertThat(unloadedToolchainContext.requiredToolchainTypes())
+        .containsExactly(testToolchainType);
+    assertThat(unloadedToolchainContext.resolvedToolchainLabels())
         .containsExactly(Label.parseAbsoluteUnchecked("//extra:extra_toolchain_linux_impl"));
 
-    assertThat(toolchainContext.executionPlatform()).isNotNull();
-    assertThat(toolchainContext.executionPlatform().label())
+    assertThat(unloadedToolchainContext.executionPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.executionPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
 
-    assertThat(toolchainContext.targetPlatform()).isNotNull();
-    assertThat(toolchainContext.targetPlatform().label())
+    assertThat(unloadedToolchainContext.targetPlatform()).isNotNull();
+    assertThat(unloadedToolchainContext.targetPlatform().label())
         .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
   }
 
   @Test
-  public void createToolchainContext_execConstraints_invalid() throws Exception {
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
+  public void resolve_execConstraints_invalid() throws Exception {
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create(
             "test",
             ImmutableSet.of(testToolchainType),
             ImmutableSet.of(Label.parseAbsoluteUnchecked("//platforms:linux")),
             targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
 
     assertThatEvaluationResult(result).hasError();
     assertThatEvaluationResult(result)
@@ -396,7 +387,7 @@
   }
 
   @Test
-  public void createToolchainContext_noMatchingPlatform() throws Exception {
+  public void resolve_noMatchingPlatform() throws Exception {
     // Write toolchain A, and a toolchain implementing it.
     scratch.appendFile(
         "a/BUILD",
@@ -426,15 +417,15 @@
         "register_execution_platforms('//platforms:mac', '//platforms:linux')");
 
     useConfiguration("--platforms=//platforms:linux");
-    CreateToolchainContextKey key =
-        CreateToolchainContextKey.create(
+    ResolveToolchainsKey key =
+        ResolveToolchainsKey.create(
             "test",
             ImmutableSet.of(
                 Label.parseAbsoluteUnchecked("//a:toolchain_type_A"),
                 Label.parseAbsoluteUnchecked("//b:toolchain_type_B")),
             targetConfigKey);
 
-    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+    EvaluationResult<ResolveToolchainsValue> result = createToolchainContextBuilder(key);
     assertThatEvaluationResult(result).hasError();
     assertThatEvaluationResult(result)
         .hasErrorEntryForKeyThat(key)
@@ -442,26 +433,25 @@
         .isInstanceOf(NoMatchingPlatformException.class);
   }
 
-  // Calls ToolchainUtil.createToolchainContext.
-  private static final SkyFunctionName CREATE_TOOLCHAIN_CONTEXT_FUNCTION =
-      SkyFunctionName.createHermetic("CREATE_TOOLCHAIN_CONTEXT_FUNCTION");
+  private static final SkyFunctionName RESOLVE_TOOLCHAINS_FUNCTION =
+      SkyFunctionName.createHermetic("RESOLVE_TOOLCHAINS_FUNCTION");
 
   @AutoValue
-  abstract static class CreateToolchainContextKey implements SkyKey {
+  abstract static class ResolveToolchainsKey implements SkyKey {
     @Override
     public SkyFunctionName functionName() {
-      return CREATE_TOOLCHAIN_CONTEXT_FUNCTION;
+      return RESOLVE_TOOLCHAINS_FUNCTION;
     }
 
     abstract String targetDescription();
 
-    abstract ImmutableSet<Label> requiredToolchains();
+    abstract ImmutableSet<Label> requiredToolchainTypes();
 
     abstract ImmutableSet<Label> execConstraintLabels();
 
     abstract BuildConfigurationValue.Key configurationKey();
 
-    public static CreateToolchainContextKey create(
+    public static ResolveToolchainsKey create(
         String targetDescription,
         Set<Label> requiredToolchains,
         BuildConfigurationValue.Key configurationKey) {
@@ -472,12 +462,12 @@
           configurationKey);
     }
 
-    public static CreateToolchainContextKey create(
+    public static ResolveToolchainsKey create(
         String targetDescription,
         Set<Label> requiredToolchains,
         Set<Label> execConstraintLabels,
         BuildConfigurationValue.Key configurationKey) {
-      return new AutoValue_ToolchainUtilTest_CreateToolchainContextKey(
+      return new AutoValue_ToolchainResolverTest_ResolveToolchainsKey(
           targetDescription,
           ImmutableSet.copyOf(requiredToolchains),
           ImmutableSet.copyOf(execConstraintLabels),
@@ -485,8 +475,8 @@
     }
   }
 
-  EvaluationResult<CreateToolchainContextValue> createToolchainContext(
-      CreateToolchainContextKey key) throws InterruptedException {
+  private EvaluationResult<ResolveToolchainsValue> createToolchainContextBuilder(
+      ResolveToolchainsKey key) throws InterruptedException {
     try {
       // Must re-enable analysis for Skyframe functions that create configured targets.
       skyframeExecutor.getSkyframeBuildView().enableAnalysis(true);
@@ -497,46 +487,36 @@
     }
   }
 
-  // TODO(blaze-team): implement equals and hashcode for ToolchainContext and convert this to
-  // autovalue.
-  static class CreateToolchainContextValue implements SkyValue {
-    private final ToolchainContext toolchainContext;
+  @AutoValue
+  abstract static class ResolveToolchainsValue implements SkyValue {
+    abstract UnloadedToolchainContext unloadedToolchainContext();
 
-    private CreateToolchainContextValue(ToolchainContext toolchainContext) {
-      this.toolchainContext = toolchainContext;
-    }
-
-    static CreateToolchainContextValue create(ToolchainContext toolchainContext) {
-      return new CreateToolchainContextValue(toolchainContext);
-    }
-
-    ToolchainContext toolchainContext() {
-      return toolchainContext;
+    static ResolveToolchainsValue create(UnloadedToolchainContext unloadedToolchainContext) {
+      return new AutoValue_ToolchainResolverTest_ResolveToolchainsValue(unloadedToolchainContext);
     }
   }
 
-  private static final class CreateToolchainContextFunction implements SkyFunction {
+  private static final class ResolveToolchainsFunction implements SkyFunction {
 
     @Nullable
     @Override
     public SkyValue compute(SkyKey skyKey, Environment env)
         throws SkyFunctionException, InterruptedException {
-      CreateToolchainContextKey key = (CreateToolchainContextKey) skyKey;
-      ToolchainContext toolchainContext = null;
+      ResolveToolchainsKey key = (ResolveToolchainsKey) skyKey;
+      ToolchainResolver toolchainResolver =
+          new ToolchainResolver(env, key.configurationKey())
+              .setTargetDescription(key.targetDescription())
+              .setRequiredToolchainTypes(key.requiredToolchainTypes())
+              .setExecConstraintLabels(key.execConstraintLabels());
+
       try {
-        toolchainContext =
-            ToolchainUtil.createToolchainContext(
-                env,
-                key.targetDescription(),
-                key.requiredToolchains(),
-                key.execConstraintLabels(),
-                key.configurationKey());
-        if (toolchainContext == null) {
+        UnloadedToolchainContext unloadedToolchainContext = toolchainResolver.resolve();
+        if (unloadedToolchainContext == null) {
           return null;
         }
-        return CreateToolchainContextValue.create(toolchainContext);
+        return ResolveToolchainsValue.create(unloadedToolchainContext);
       } catch (ToolchainException e) {
-        throw new CreateToolchainContextFunctionException(e);
+        throw new ResolveToolchainsFunctionException(e);
       }
     }
 
@@ -547,8 +527,8 @@
     }
   }
 
-  private static class CreateToolchainContextFunctionException extends SkyFunctionException {
-    public CreateToolchainContextFunctionException(ToolchainException e) {
+  private static class ResolveToolchainsFunctionException extends SkyFunctionException {
+    ResolveToolchainsFunctionException(ToolchainException e) {
       super(e, Transience.PERSISTENT);
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
index 1f92bea..fbb2944 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
@@ -42,6 +42,8 @@
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
+import com.google.devtools.build.lib.analysis.ToolchainResolver;
+import com.google.devtools.build.lib.analysis.ToolchainResolver.UnloadedToolchainContext;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
 import com.google.devtools.build.lib.analysis.ViewCreationFailedException;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
@@ -78,6 +80,7 @@
 import com.google.devtools.build.lib.skyframe.BuildConfigurationValue;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
+import com.google.devtools.build.lib.skyframe.SkyFunctionEnvironmentForTesting;
 import com.google.devtools.build.lib.skyframe.SkyframeBuildView;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
 import com.google.devtools.build.lib.skyframe.TargetPatternPhaseValue;
@@ -504,18 +507,22 @@
           Event.error("Failed to get target when trying to get rule context for testing"));
       throw new IllegalStateException(e);
     }
-    Set<Label> requiredToolchains =
+    ImmutableSet<Label> requiredToolchains =
         target.getAssociatedRule().getRuleClassObject().getRequiredToolchains();
-    ToolchainContext toolchainContext =
-        skyframeExecutor.getToolchainContextForTesting(
-            requiredToolchains, targetConfig, eventHandler);
+    SkyFunctionEnvironmentForTesting skyfunctionEnvironment =
+        skyframeExecutor.getSkyFunctionEnvironmentForTesting(eventHandler);
+    UnloadedToolchainContext unloadedToolchainContext =
+        new ToolchainResolver(skyfunctionEnvironment, BuildConfigurationValue.key(targetConfig))
+            .setRequiredToolchainTypes(requiredToolchains)
+            .resolve();
+
     OrderedSetMultimap<Attribute, ConfiguredTargetAndData> prerequisiteMap =
         getPrerequisiteMapForTesting(
             eventHandler,
             configuredTarget,
             configurations,
-            toolchainContext.resolvedToolchainLabels());
-    toolchainContext.resolveToolchains(prerequisiteMap);
+            unloadedToolchainContext.resolvedToolchainLabels());
+    ToolchainContext toolchainContext = unloadedToolchainContext.load(prerequisiteMap);
 
     return new RuleContext.Builder(
             env,
@@ -534,7 +541,7 @@
                 eventHandler,
                 configuredTarget,
                 configurations,
-                toolchainContext.resolvedToolchainLabels()))
+                unloadedToolchainContext.resolvedToolchainLabels()))
         .setConfigConditions(ImmutableMap.<Label, ConfigMatchingProvider>of())
         .setUniversalFragments(ruleClassProvider.getUniversalFragments())
         .setToolchainContext(toolchainContext)