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 0f3b752..54a0a37 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
@@ -358,7 +358,6 @@
                     aspect.getDescriptor().getDescription(),
                     associatedConfiguredTargetAndTarget.getTarget().toString()),
                 requiredToolchains,
-                aspectConfiguration,
                 key.getAspectConfigurationKey());
       } catch (ToolchainContextException e) {
         // TODO(katre): better error handling
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 963a8be..962f136 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
@@ -249,7 +249,6 @@
                   env,
                   rule.toString(),
                   requiredToolchains,
-                  configuration,
                   configuredTargetKey.getConfigurationKey());
           if (env.valuesMissing()) {
             return null;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunction.java
index d7e6e21..9837589 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunction.java
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.ConfiguredValueCreationException;
+import com.google.devtools.build.lib.skyframe.ToolchainUtil.InvalidPlatformException;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
@@ -127,11 +128,11 @@
 
         if (platformInfo == null) {
           throw new RegisteredExecutionPlatformsFunctionException(
-              new InvalidExecutionPlatformLabelException(platformLabel), Transience.PERSISTENT);
+              new InvalidPlatformException(platformLabel), Transience.PERSISTENT);
         }
       } catch (ConfiguredValueCreationException e) {
         throw new RegisteredExecutionPlatformsFunctionException(
-            new InvalidExecutionPlatformLabelException(platformLabel, e), Transience.PERSISTENT);
+            new InvalidPlatformException(platformLabel, e), Transience.PERSISTENT);
       }
     }
 
@@ -148,44 +149,13 @@
   }
 
   /**
-   * Used to indicate that the given {@link Label} represents a {@link ConfiguredTarget} which is
-   * not a valid {@link PlatformInfo} provider.
-   */
-  static final class InvalidExecutionPlatformLabelException extends Exception {
-
-    private final Label invalidLabel;
-
-    private InvalidExecutionPlatformLabelException(Label invalidLabel) {
-      super(
-          String.format(
-              "invalid registered execution platform '%s': "
-                  + "target does not provide the PlatformInfo provider",
-              invalidLabel));
-      this.invalidLabel = invalidLabel;
-    }
-
-    private InvalidExecutionPlatformLabelException(
-        Label invalidLabel, ConfiguredValueCreationException e) {
-      super(
-          String.format(
-              "invalid registered execution platform '%s': %s", invalidLabel, e.getMessage()),
-          e);
-      this.invalidLabel = invalidLabel;
-    }
-
-    public Label getInvalidLabel() {
-      return invalidLabel;
-    }
-  }
-
-  /**
    * Used to declare all the exception types that can be wrapped in the exception thrown by {@link
    * #compute}.
    */
   private static class RegisteredExecutionPlatformsFunctionException extends SkyFunctionException {
 
     private RegisteredExecutionPlatformsFunctionException(
-        InvalidExecutionPlatformLabelException cause, Transience transience) {
+        InvalidPlatformException cause, Transience transience) {
       super(cause, transience);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsValue.java
index 03d4e92..b552777 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsValue.java
@@ -35,9 +35,12 @@
     return Key.of(configurationKey);
   }
 
+  /** {@link SkyKey} implementation used for {@link RegisteredExecutionPlatformsFunction}. */
   @AutoCodec
+  @AutoCodec.VisibleForSerialization
   static class Key implements SkyKey {
     private static final Interner<Key> interners = BlazeInterners.newWeakInterner();
+
     private final BuildConfigurationValue.Key configurationKey;
 
     private Key(BuildConfigurationValue.Key configurationKey) {
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 38ad081..68f74aa 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
@@ -901,7 +901,6 @@
         env,
         "",
         requiredToolchains,
-        config,
         config == null
             ? null
             : BuildConfigurationValue.key(config.fragmentClasses(), config.getOptions()));
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java
index 0211c46..630542b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunction.java
@@ -28,7 +28,6 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
 import com.google.devtools.build.lib.skyframe.RegisteredToolchainsFunction.InvalidToolchainLabelException;
-import com.google.devtools.build.lib.skyframe.ToolchainResolutionValue.ToolchainResolutionKey;
 import com.google.devtools.build.lib.skyframe.ToolchainUtil.ToolchainContextException;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.skyframe.SkyFunction;
@@ -39,7 +38,6 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import java.util.stream.Collectors;
 import javax.annotation.Nullable;
 
 /** {@link SkyFunction} which performs toolchain resolution for a class of rules. */
@@ -49,7 +47,7 @@
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env)
       throws ToolchainResolutionFunctionException, InterruptedException {
-    ToolchainResolutionKey key = (ToolchainResolutionKey) skyKey.argument();
+    ToolchainResolutionValue.Key key = (ToolchainResolutionValue.Key) skyKey.argument();
 
     // This call could be combined with the call below, but this SkyFunction is evaluated so rarely
     // it's not worth optimizing.
@@ -77,26 +75,19 @@
       throw new ToolchainResolutionFunctionException(e);
     }
 
-    Map<ConfiguredTargetKey, PlatformInfo> platforms;
-    try {
-      platforms =
-          ToolchainUtil.getPlatformInfo(
-              key.targetPlatformKey(), key.availableExecutionPlatformKeys(), env);
-    } catch (ToolchainContextException e) {
-      throw new ToolchainResolutionFunctionException(e);
-    }
     // Find the right one.
     boolean debug = configuration.getOptions().get(PlatformOptions.class).toolchainResolutionDebug;
-    ImmutableMap<PlatformInfo, Label> resolvedToolchainLabels =
+    ImmutableMap<ConfiguredTargetKey, Label> resolvedToolchainLabels =
         resolveConstraints(
             key.toolchainType(),
-            key.availableExecutionPlatformKeys()
-                .stream()
-                .map(platforms::get)
-                .collect(Collectors.toList()),
-            platforms.get(key.targetPlatformKey()),
+            key.availableExecutionPlatformKeys(),
+            key.targetPlatformKey(),
             toolchains.registeredToolchains(),
+            env,
             debug ? env.getListener() : null);
+    if (resolvedToolchainLabels == null) {
+      return null;
+    }
 
     if (resolvedToolchainLabels.isEmpty()) {
       throw new ToolchainResolutionFunctionException(
@@ -111,17 +102,39 @@
    * pairs that are compatible a) with each other, and b) with the toolchain type and target
    * platform.
    */
-  private static ImmutableMap<PlatformInfo, Label> resolveConstraints(
+  @Nullable
+  private static ImmutableMap<ConfiguredTargetKey, Label> resolveConstraints(
       Label toolchainType,
-      List<PlatformInfo> availableExecutionPlatforms,
-      PlatformInfo targetPlatform,
+      List<ConfiguredTargetKey> availableExecutionPlatformKeys,
+      ConfiguredTargetKey targetPlatformKey,
       ImmutableList<DeclaredToolchainInfo> toolchains,
-      @Nullable EventHandler eventHandler) {
+      Environment env,
+      @Nullable EventHandler eventHandler)
+      throws ToolchainResolutionFunctionException, InterruptedException {
 
-    // Platforms may exist multiple times in availableExecutionPlatforms. The Set lets this code
+    // Load the PlatformInfo needed to check constraints.
+    Map<ConfiguredTargetKey, PlatformInfo> platforms;
+    try {
+      platforms =
+          ToolchainUtil.getPlatformInfo(
+              new ImmutableList.Builder<ConfiguredTargetKey>()
+                  .add(targetPlatformKey)
+                  .addAll(availableExecutionPlatformKeys)
+                  .build(),
+              env);
+      if (platforms == null) {
+        return null;
+      }
+    } catch (ToolchainContextException e) {
+      throw new ToolchainResolutionFunctionException(e);
+    }
+
+    PlatformInfo targetPlatform = platforms.get(targetPlatformKey);
+
+    // Platforms may exist multiple times in availableExecutionPlatformKeys. The Set lets this code
     // check whether a platform has already been seen during processing.
-    Set<PlatformInfo> platformsSeen = new HashSet<>();
-    ImmutableMap.Builder<PlatformInfo, Label> builder = ImmutableMap.builder();
+    Set<ConfiguredTargetKey> platformKeysSeen = new HashSet<>();
+    ImmutableMap.Builder<ConfiguredTargetKey, Label> builder = ImmutableMap.builder();
 
     debugMessage(eventHandler, "Looking for toolchain of type %s...", toolchainType);
     for (DeclaredToolchainInfo toolchain : toolchains) {
@@ -142,31 +155,33 @@
       }
 
       // Find the matching execution platforms.
-      for (PlatformInfo executionPlatform : availableExecutionPlatforms) {
+      for (ConfiguredTargetKey executionPlatformKey : availableExecutionPlatformKeys) {
+        PlatformInfo executionPlatform = platforms.get(executionPlatformKey);
         if (!checkConstraints(
             eventHandler, toolchain.execConstraints(), "execution", executionPlatform)) {
           continue;
         }
 
         // Only add the toolchains if this is a new platform.
-        if (!platformsSeen.contains(executionPlatform)) {
-          builder.put(executionPlatform, toolchain.toolchainLabel());
-          platformsSeen.add(executionPlatform);
+        if (!platformKeysSeen.contains(executionPlatformKey)) {
+          builder.put(executionPlatformKey, toolchain.toolchainLabel());
+          platformKeysSeen.add(executionPlatformKey);
         }
       }
     }
 
-    ImmutableMap<PlatformInfo, Label> resolvedToolchainLabels = builder.build();
+    ImmutableMap<ConfiguredTargetKey, Label> resolvedToolchainLabels = builder.build();
     if (resolvedToolchainLabels.isEmpty()) {
       debugMessage(eventHandler, "  No toolchains found");
     } else {
       debugMessage(
           eventHandler,
-          "  Selected execution platforms and toolchains: {%s}",
+          "  For toolchain type %s, possible execution platforms and toolchains: {%s}",
+          toolchainType,
           resolvedToolchainLabels
               .entrySet()
               .stream()
-              .map(e -> String.format("%s -> %s", e.getKey().label(), e.getValue()))
+              .map(e -> String.format("%s -> %s", e.getKey().getLabel(), e.getValue()))
               .collect(joining(", ")));
     }
 
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 2ee27e9..de8d329 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
@@ -17,9 +17,7 @@
 import com.google.auto.value.AutoValue;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -36,21 +34,20 @@
 public abstract class ToolchainResolutionValue implements SkyValue {
 
   // A key representing the input data.
-  public static SkyKey key(
+  public static Key key(
       BuildConfigurationValue.Key configurationKey,
       Label toolchainType,
       ConfiguredTargetKey targetPlatformKey,
       List<ConfiguredTargetKey> availableExecutionPlatformKeys) {
-    return ToolchainResolutionKey.create(
+    return Key.create(
         configurationKey, toolchainType, targetPlatformKey, availableExecutionPlatformKeys);
   }
 
   /** {@link SkyKey} implementation used for {@link ToolchainResolutionFunction}. */
   @AutoCodec
+  @AutoCodec.VisibleForSerialization
   @AutoValue
-  public abstract static class ToolchainResolutionKey implements SkyKey {
-    public static final ObjectCodec<ToolchainResolutionKey> CODEC =
-        new ToolchainResolutionValue_ToolchainResolutionKey_AutoCodec();
+  abstract static class Key implements SkyKey {
 
     @Override
     public SkyFunctionName functionName() {
@@ -66,12 +63,12 @@
     abstract ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys();
 
     @AutoCodec.Instantiator
-    static ToolchainResolutionKey create(
+    static Key create(
         BuildConfigurationValue.Key configurationKey,
         Label toolchainType,
         ConfiguredTargetKey targetPlatformKey,
         List<ConfiguredTargetKey> availableExecutionPlatformKeys) {
-      return new AutoValue_ToolchainResolutionValue_ToolchainResolutionKey(
+      return new AutoValue_ToolchainResolutionValue_Key(
           configurationKey,
           toolchainType,
           targetPlatformKey,
@@ -80,14 +77,14 @@
   }
 
   public static ToolchainResolutionValue create(
-      ImmutableMap<PlatformInfo, Label> availableToolchainLabels) {
+      ImmutableMap<ConfiguredTargetKey, Label> availableToolchainLabels) {
     return new AutoValue_ToolchainResolutionValue(availableToolchainLabels);
   }
 
   /**
    * Returns the resolved set of toolchain labels (as {@link Label}) for the requested toolchain
-   * type, keyed by the execution platforms (as {@link PlatformInfo}). Ordering is not preserved, if
-   * the caller cares about the order of platforms it must take care of that directly.
+   * type, keyed by the execution platforms (as {@link ConfiguredTargetKey}). Ordering is not
+   * preserved, if the caller cares about the order of platforms it must take care of that directly.
    */
-  public abstract ImmutableMap<PlatformInfo, Label> availableToolchainLabels();
+  public abstract ImmutableMap<ConfiguredTargetKey, Label> availableToolchainLabels();
 }
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
index cf340d4..3b84c81 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
@@ -14,22 +14,27 @@
 
 package com.google.devtools.build.lib.skyframe;
 
+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.Iterables;
+import com.google.common.collect.Table;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 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.PlatformInfo;
 import com.google.devtools.build.lib.analysis.platform.PlatformProviderUtils;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.ConfiguredValueCreationException;
 import com.google.devtools.build.lib.skyframe.RegisteredToolchainsFunction.InvalidToolchainLabelException;
 import com.google.devtools.build.lib.skyframe.ToolchainResolutionFunction.NoToolchainFoundException;
-import com.google.devtools.build.lib.skyframe.ToolchainResolutionValue.ToolchainResolutionKey;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -56,8 +61,7 @@
       Environment env,
       String targetDescription,
       Set<Label> requiredToolchains,
-      @Nullable BuildConfiguration configuration,
-      BuildConfigurationValue.Key configurationKey)
+      @Nullable BuildConfigurationValue.Key configurationKey)
       throws ToolchainContextException, InterruptedException {
 
     // In some cases this is called with a missing configuration, so we skip toolchain context.
@@ -65,107 +69,105 @@
       return null;
     }
 
-    // TODO(katre): Load several possible execution platforms, and select one based on available
-    // toolchains.
+    // 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 host and target platforms for the current configuration.
-    PlatformDescriptors platforms = loadPlatformDescriptors(env, configuration);
-    if (platforms == null) {
+    // 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.getTargetPlatforms().get(0);
+
+    ConfiguredTargetKey hostPlatformKey = ConfiguredTargetKey.of(hostPlatformLabel, configuration);
+    ConfiguredTargetKey targetPlatformKey =
+        ConfiguredTargetKey.of(targetPlatformLabel, configuration);
+
+    // Load the host and target platforms early, to check for errors.
+    getPlatformInfo(ImmutableList.of(hostPlatformKey, targetPlatformKey), env);
+
+    // 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;
     }
 
-    // TODO(katre): This will change with remote execution.
-    PlatformInfo executionPlatform = platforms.hostPlatform();
-    PlatformInfo targetPlatform = platforms.targetPlatform();
-
-    ImmutableBiMap<Label, Label> resolvedLabels =
+    ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys =
+        new ImmutableList.Builder<ConfiguredTargetKey>()
+            .addAll(registeredExecutionPlatforms.registeredExecutionPlatformKeys())
+            .add(hostPlatformKey)
+            .build();
+    Optional<ResolvedToolchains> resolvedToolchains =
         resolveToolchainLabels(
             env,
             requiredToolchains,
+            configuration,
             configurationKey,
-            platforms.hostPlatformKey(),
-            platforms.targetPlatformKey());
-    if (resolvedLabels == null) {
+            availableExecutionPlatformKeys,
+            targetPlatformKey);
+    if (resolvedToolchains == null) {
       return null;
     }
 
-    ToolchainContext toolchainContext =
-        ToolchainContext.create(
-            targetDescription,
-            executionPlatform,
-            targetPlatform,
-            requiredToolchains,
-            resolvedLabels);
-    return toolchainContext;
-  }
-
-  /**
-   * Data class to hold platform descriptors loaded based on the current {@link BuildConfiguration}.
-   */
-  @AutoValue
-  protected abstract static class PlatformDescriptors {
-    abstract PlatformInfo hostPlatform();
-
-    abstract PlatformInfo targetPlatform();
-
-    abstract ConfiguredTargetKey hostPlatformKey();
-
-    abstract ConfiguredTargetKey targetPlatformKey();
-
-    protected static PlatformDescriptors create(
-        PlatformInfo hostPlatform,
-        PlatformInfo targetPlatform,
-        ConfiguredTargetKey hostPlatformKey,
-        ConfiguredTargetKey targetPlatformKey) {
-      return new AutoValue_ToolchainUtil_PlatformDescriptors(
-          hostPlatform, targetPlatform, hostPlatformKey, targetPlatformKey);
+    if (resolvedToolchains.isPresent()) {
+      return createContext(
+          env,
+          targetDescription,
+          resolvedToolchains.get().executionPlatformKey(),
+          resolvedToolchains.get().targetPlatformKey(),
+          requiredToolchains,
+          resolvedToolchains.get().toolchains());
+    } else {
+      // No toolchain could be resolved, but no error happened, so fall back to host platform.
+      return createContext(
+          env,
+          targetDescription,
+          hostPlatformKey,
+          targetPlatformKey,
+          requiredToolchains,
+          ImmutableBiMap.of());
     }
   }
 
-  /**
-   * Returns the {@link PlatformInfo} provider from the {@link ConfiguredTarget} in the {@link
-   * ValueOrException}, or {@code null} if the {@link ConfiguredTarget} is not present. If the
-   * {@link ConfiguredTarget} does not have a {@link PlatformInfo} provider, a {@link
-   * InvalidPlatformException} is thrown, wrapped in a {@link ToolchainContextException}.
-   */
-  @Nullable
-  private static PlatformInfo findPlatformInfo(
-      ValueOrException<ConfiguredValueCreationException> valueOrException, String platformType)
-      throws ConfiguredValueCreationException, ToolchainContextException {
-
-    ConfiguredTargetValue ctv = (ConfiguredTargetValue) valueOrException.get();
-    if (ctv == null) {
-      return null;
+  private static RegisteredExecutionPlatformsValue loadRegisteredExecutionPlatforms(
+      Environment env, BuildConfigurationValue.Key configurationKey)
+      throws InterruptedException, ToolchainContextException {
+    try {
+      RegisteredExecutionPlatformsValue registeredExecutionPlatforms =
+          (RegisteredExecutionPlatformsValue)
+              env.getValueOrThrow(
+                  RegisteredExecutionPlatformsValue.key(configurationKey),
+                  InvalidPlatformException.class);
+      if (registeredExecutionPlatforms == null) {
+        return null;
+      }
+      return registeredExecutionPlatforms;
+    } catch (InvalidPlatformException e) {
+      throw new ToolchainContextException(e);
     }
-
-    ConfiguredTarget configuredTarget = ctv.getConfiguredTarget();
-    PlatformInfo platformInfo = PlatformProviderUtils.platform(configuredTarget);
-    if (platformInfo == null) {
-      throw new ToolchainContextException(
-          new InvalidPlatformException(platformType, configuredTarget.getLabel()));
-    }
-
-    return platformInfo;
   }
 
   @Nullable
   static Map<ConfiguredTargetKey, PlatformInfo> getPlatformInfo(
-      ConfiguredTargetKey targetPlatformKey,
-      Iterable<ConfiguredTargetKey> hostPlatformKeys,
-      Environment env)
+      Iterable<ConfiguredTargetKey> platformKeys, Environment env)
       throws InterruptedException, ToolchainContextException {
-    Iterable<ConfiguredTargetKey> allKeys =
-        Iterables.concat(ImmutableList.of(targetPlatformKey), hostPlatformKeys);
+
     Map<SkyKey, ValueOrException<ConfiguredValueCreationException>> values =
-        env.getValuesOrThrow(allKeys, ConfiguredValueCreationException.class);
+        env.getValuesOrThrow(platformKeys, ConfiguredValueCreationException.class);
     boolean valuesMissing = env.valuesMissing();
     Map<ConfiguredTargetKey, PlatformInfo> platforms = valuesMissing ? null : new HashMap<>();
     try {
-      for (ConfiguredTargetKey key : allKeys) {
-        PlatformInfo platformInfo =
-            findPlatformInfo(
-                values.get(key),
-                key.equals(targetPlatformKey) ? "target platform" : "host platform");
+      for (ConfiguredTargetKey key : platformKeys) {
+        PlatformInfo platformInfo = findPlatformInfo(values.get(key));
         if (!valuesMissing && platformInfo != null) {
           platforms.put(key, platformInfo);
         }
@@ -179,57 +181,72 @@
     return platforms;
   }
 
+  /**
+   * Returns the {@link PlatformInfo} provider from the {@link ConfiguredTarget} in the {@link
+   * ValueOrException}, or {@code null} if the {@link ConfiguredTarget} is not present. If the
+   * {@link ConfiguredTarget} does not have a {@link PlatformInfo} provider, a {@link
+   * InvalidPlatformException} is thrown, wrapped in a {@link ToolchainContextException}.
+   */
   @Nullable
-  private static PlatformDescriptors loadPlatformDescriptors(
-      Environment env, BuildConfiguration configuration)
-      throws InterruptedException, ToolchainContextException {
-    PlatformConfiguration platformConfiguration =
-        configuration.getFragment(PlatformConfiguration.class);
-    if (platformConfiguration == null) {
-      return null;
-    }
-    Label hostPlatformLabel = platformConfiguration.getHostPlatform();
-    Label targetPlatformLabel = platformConfiguration.getTargetPlatforms().get(0);
+  private static PlatformInfo findPlatformInfo(
+      ValueOrException<ConfiguredValueCreationException> valueOrException)
+      throws ConfiguredValueCreationException, ToolchainContextException {
 
-    ConfiguredTargetKey hostPlatformKey = ConfiguredTargetKey.of(hostPlatformLabel, configuration);
-    ConfiguredTargetKey targetPlatformKey =
-        ConfiguredTargetKey.of(targetPlatformLabel, configuration);
-    Map<ConfiguredTargetKey, PlatformInfo> platformResult =
-        getPlatformInfo(targetPlatformKey, ImmutableList.of(hostPlatformKey), env);
-    if (env.valuesMissing()) {
+    ConfiguredTargetValue ctv = (ConfiguredTargetValue) valueOrException.get();
+    if (ctv == null) {
       return null;
     }
 
-    return PlatformDescriptors.create(
-        platformResult.get(hostPlatformKey),
-        platformResult.get(targetPlatformKey),
-        hostPlatformKey,
-        targetPlatformKey);
+    ConfiguredTarget configuredTarget = ctv.getConfiguredTarget();
+    PlatformInfo platformInfo = PlatformProviderUtils.platform(configuredTarget);
+    if (platformInfo == null) {
+      throw new ToolchainContextException(
+          new InvalidPlatformException(configuredTarget.getLabel()));
+    }
+
+    return platformInfo;
+  }
+
+  /** 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 ImmutableBiMap<Label, Label> resolveToolchainLabels(
+  private static Optional<ResolvedToolchains> resolveToolchainLabels(
       Environment env,
       Set<Label> requiredToolchains,
+      BuildConfiguration configuration,
       BuildConfigurationValue.Key configurationKey,
-      ConfiguredTargetKey executionPlatformKey,
+      ImmutableList<ConfiguredTargetKey> availableExecutionPlatformKeys,
       ConfiguredTargetKey targetPlatformKey)
       throws InterruptedException, ToolchainContextException {
 
     // If there are no required toolchains, bail out early.
     if (requiredToolchains.isEmpty()) {
-      return ImmutableBiMap.of();
+      return Optional.absent();
     }
 
     // Find the toolchains for the required toolchain types.
-    List<SkyKey> registeredToolchainKeys = new ArrayList<>();
+    List<ToolchainResolutionValue.Key> registeredToolchainKeys = new ArrayList<>();
     for (Label toolchainType : requiredToolchains) {
       registeredToolchainKeys.add(
           ToolchainResolutionValue.key(
-              configurationKey,
-              toolchainType,
-              targetPlatformKey,
-              ImmutableList.of(executionPlatformKey)));
+              configurationKey, toolchainType, targetPlatformKey, availableExecutionPlatformKeys));
     }
 
     Map<
@@ -246,8 +263,8 @@
                 EvalException.class);
     boolean valuesMissing = false;
 
-    // Load the toolchains.
-    ImmutableBiMap.Builder<Label, Label> builder = new ImmutableBiMap.Builder<>();
+    // Determine the potential set of toolchains.
+    Table<ConfiguredTargetKey, Label, Label> resolvedToolchains = HashBasedTable.create();
     List<Label> missingToolchains = new ArrayList<>();
     for (Map.Entry<
             SkyKey,
@@ -257,26 +274,19 @@
         entry : results.entrySet()) {
       try {
         Label requiredToolchainType =
-            ((ToolchainResolutionKey) entry.getKey().argument()).toolchainType();
+            ((ToolchainResolutionValue.Key) entry.getKey().argument()).toolchainType();
         ValueOrException4<
                 NoToolchainFoundException, ConfiguredValueCreationException,
                 InvalidToolchainLabelException, EvalException>
             valueOrException = entry.getValue();
         if (valueOrException.get() == null) {
           valuesMissing = true;
-        } else {
-          ToolchainResolutionValue toolchainResolutionValue =
-              (ToolchainResolutionValue) valueOrException.get();
-
-          // TODO(https://github.com/bazelbuild/bazel/issues/4442): Handle finding the best
-          // execution platform when multiple are available.
-          Label toolchainLabel =
-              Iterables.getFirst(
-                  toolchainResolutionValue.availableToolchainLabels().values(), null);
-          if (toolchainLabel != null) {
-            builder.put(requiredToolchainType, toolchainLabel);
-          }
+          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());
@@ -297,16 +307,89 @@
       return null;
     }
 
-    return builder.build();
+    boolean debug = configuration.getOptions().get(PlatformOptions.class).toolchainResolutionDebug;
+
+    // Find and return the first execution platform which has all required toolchains.
+    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(
+          ResolvedToolchains.create(executionPlatformKey, targetPlatformKey, toolchains));
+    }
+
+    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 ToolchainContextException, InterruptedException {
+
+    Map<ConfiguredTargetKey, PlatformInfo> platforms =
+        getPlatformInfo(ImmutableList.of(executionPlatformKey, targetPlatformKey), env);
+
+    if (platforms == null) {
+      return null;
+    }
+
+    return ToolchainContext.create(
+        targetDescription,
+        platforms.get(executionPlatformKey),
+        platforms.get(targetPlatformKey),
+        requiredToolchains,
+        toolchains);
   }
 
   /** Exception used when a platform label is not a valid platform. */
   static final class InvalidPlatformException extends Exception {
-    InvalidPlatformException(String platformType, Label label) {
-      super(
-          String.format(
-              "Target %s was found as the %s, but does not provide PlatformInfo",
-              label, platformType));
+    InvalidPlatformException(Label label) {
+      super(formatError(label));
+    }
+
+    InvalidPlatformException(Label label, ConfiguredValueCreationException e) {
+      super(formatError(label), e);
+    }
+
+    private static String formatError(Label label) {
+      return String.format(
+          "Target %s was referenced as a platform, but does not provide PlatformInfo", label);
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java
index 7ebc55b..c002619 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.analysis.platform.PlatformInfo.DuplicateConstraintException;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.rules.platform.ToolchainTestCase;
+import com.google.devtools.build.lib.skyframe.ToolchainUtil.InvalidPlatformException;
 import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -115,13 +116,16 @@
     SkyKey executionPlatformsKey = RegisteredExecutionPlatformsValue.key(targetConfigKey);
     EvaluationResult<RegisteredExecutionPlatformsValue> result =
         requestExecutionPlatformsFromSkyframe(executionPlatformsKey);
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(executionPlatformsKey)
+        .hasExceptionThat()
+        .isInstanceOf(InvalidPlatformException.class);
     assertThatEvaluationResult(result)
         .hasErrorEntryForKeyThat(executionPlatformsKey)
         .hasExceptionThat()
         .hasMessageThat()
-        .contains(
-            "invalid registered execution platform '//error:not_an_execution_platform': "
-                + "target does not provide the PlatformInfo provider");
+        .contains("//error:not_an_execution_platform");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java
index 0194819..702929b 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java
@@ -88,7 +88,7 @@
 
     ToolchainResolutionValue toolchainResolutionValue = result.get(key);
     assertThat(toolchainResolutionValue.availableToolchainLabels())
-        .containsExactly(macPlatform, makeLabel("//toolchain:toolchain_2_impl"));
+        .containsExactly(MAC_CTKEY, makeLabel("//toolchain:toolchain_2_impl"));
   }
 
   @Test
@@ -118,9 +118,9 @@
     ToolchainResolutionValue toolchainResolutionValue = result.get(key);
     assertThat(toolchainResolutionValue.availableToolchainLabels())
         .containsExactly(
-            linuxPlatform,
+            LINUX_CTKEY,
             makeLabel("//extra:extra_toolchain_impl"),
-            macPlatform,
+            MAC_CTKEY,
             makeLabel("//toolchain:toolchain_2_impl"));
   }
 
@@ -146,37 +146,27 @@
     new EqualsTester()
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .build()),
+                ImmutableMap.of(LINUX_CTKEY, makeLabel("//test:toolchain_impl_1"))),
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .build()))
+                ImmutableMap.of(LINUX_CTKEY, makeLabel("//test:toolchain_impl_1"))))
         // Different execution platform, same label.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(macPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .build()))
+                ImmutableMap.of(MAC_CTKEY, makeLabel("//test:toolchain_impl_1"))))
         // Same execution platform, different label.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_2"))
-                    .build()))
+                ImmutableMap.of(LINUX_CTKEY, makeLabel("//test:toolchain_impl_2"))))
         // Different execution platform, different label.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(macPlatform, makeLabel("//test:toolchain_impl_2"))
-                    .build()))
+                ImmutableMap.of(MAC_CTKEY, makeLabel("//test:toolchain_impl_2"))))
         // Multiple execution platforms.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .put(macPlatform, makeLabel("//test:toolchain_impl_1"))
+                ImmutableMap.<ConfiguredTargetKey, Label>builder()
+                    .put(LINUX_CTKEY, makeLabel("//test:toolchain_impl_1"))
+                    .put(MAC_CTKEY, makeLabel("//test:toolchain_impl_1"))
                     .build()));
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
index 442f5de..166bc22 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
@@ -18,14 +18,15 @@
 import static com.google.devtools.build.skyframe.EvaluationResultSubjectFactory.assertThatEvaluationResult;
 
 import com.google.auto.value.AutoValue;
+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.config.BuildConfiguration;
 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.ToolchainUtil.InvalidPlatformException;
 import com.google.devtools.build.lib.skyframe.ToolchainUtil.ToolchainContextException;
 import com.google.devtools.build.lib.skyframe.ToolchainUtil.UnresolvedToolchainsException;
 import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
@@ -72,11 +73,28 @@
 
   @Test
   public void createToolchainContext() throws Exception {
-    useConfiguration(
-        "--host_platform=//platforms:linux",
-        "--platforms=//platforms:mac");
+    // This should select platform mac, toolchain extra_toolchain_mac, because platform
+    // mac is listed first.
+    addToolchain(
+        "extra",
+        "extra_toolchain_linux",
+        ImmutableList.of("//constraints:linux"),
+        ImmutableList.of("//constraints:linux"),
+        "baz");
+    addToolchain(
+        "extra",
+        "extra_toolchain_mac",
+        ImmutableList.of("//constraints:mac"),
+        ImmutableList.of("//constraints:linux"),
+        "baz");
+    rewriteWorkspace(
+        "register_toolchains('//extra:extra_toolchain_linux', '//extra:extra_toolchain_mac')",
+        "register_execution_platforms('//platforms:mac', '//platforms:linux')");
+
+    useConfiguration("--platforms=//platforms:linux");
     CreateToolchainContextKey key =
-        CreateToolchainContextKey.create("test", ImmutableSet.of(testToolchainType), targetConfig);
+        CreateToolchainContextKey.create(
+            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
 
     EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
 
@@ -86,15 +104,15 @@
 
     assertThat(toolchainContext.getRequiredToolchains()).containsExactly(testToolchainType);
     assertThat(toolchainContext.getResolvedToolchainLabels())
-        .containsExactly(Label.parseAbsoluteUnchecked("//toolchain:toolchain_1_impl"));
+        .containsExactly(Label.parseAbsoluteUnchecked("//extra:extra_toolchain_mac_impl"));
 
     assertThat(toolchainContext.getExecutionPlatform()).isNotNull();
     assertThat(toolchainContext.getExecutionPlatform().label())
-        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
+        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:mac"));
 
     assertThat(toolchainContext.getTargetPlatform()).isNotNull();
     assertThat(toolchainContext.getTargetPlatform().label())
-        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:mac"));
+        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
   }
 
   @Test
@@ -107,7 +125,7 @@
             "test",
             ImmutableSet.of(
                 testToolchainType, Label.parseAbsoluteUnchecked("//fake/toolchain:type_1")),
-            targetConfig);
+            targetConfigKey);
 
     EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
 
@@ -140,7 +158,7 @@
                 testToolchainType,
                 Label.parseAbsoluteUnchecked("//fake/toolchain:type_1"),
                 Label.parseAbsoluteUnchecked("//fake/toolchain:type_2")),
-            targetConfig);
+            targetConfigKey);
 
     EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
 
@@ -156,6 +174,90 @@
     // Only one of the missing types will be reported, so do not check the specific error message.
   }
 
+  @Test
+  public void createToolchainContext_invalidTargetPlatform() 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);
+
+    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .isInstanceOf(ToolchainContextException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .isInstanceOf(InvalidPlatformException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .hasMessageThat()
+        .contains("//invalid:not_a_platform");
+  }
+
+  @Test
+  public void createToolchainContext_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);
+
+    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .isInstanceOf(ToolchainContextException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .isInstanceOf(InvalidPlatformException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .hasMessageThat()
+        .contains("//invalid:not_a_platform");
+  }
+
+  @Test
+  public void createToolchainContext_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);
+
+    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .isInstanceOf(ToolchainContextException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .isInstanceOf(InvalidPlatformException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .hasMessageThat()
+        .contains("//invalid:not_a_platform");
+  }
+
   // Calls ToolchainUtil.createToolchainContext.
   private static final SkyFunctionName CREATE_TOOLCHAIN_CONTEXT_FUNCTION =
       SkyFunctionName.create("CREATE_TOOLCHAIN_CONTEXT_FUNCTION");
@@ -171,12 +273,14 @@
 
     abstract Set<Label> requiredToolchains();
 
-    abstract BuildConfiguration configuration();
+    abstract BuildConfigurationValue.Key configurationKey();
 
     public static CreateToolchainContextKey create(
-        String targetDescription, Set<Label> requiredToolchains, BuildConfiguration configuration) {
+        String targetDescription,
+        Set<Label> requiredToolchains,
+        BuildConfigurationValue.Key configurationKey) {
       return new AutoValue_ToolchainUtilTest_CreateToolchainContextKey(
-          targetDescription, requiredToolchains, configuration);
+          targetDescription, requiredToolchains, configurationKey);
     }
   }
 
@@ -212,14 +316,7 @@
       try {
         toolchainContext =
             ToolchainUtil.createToolchainContext(
-                env,
-                key.targetDescription(),
-                key.requiredToolchains(),
-                key.configuration(),
-                key.configuration() == null
-                    ? null
-                    : BuildConfigurationValue.key(
-                        key.configuration().fragmentClasses(), key.configuration().getOptions()));
+                env, key.targetDescription(), key.requiredToolchains(), key.configurationKey());
         if (toolchainContext == null) {
           return null;
         }
diff --git a/src/test/shell/bazel/toolchain_test.sh b/src/test/shell/bazel/toolchain_test.sh
index 002a779..24abfcc 100755
--- a/src/test/shell/bazel/toolchain_test.sh
+++ b/src/test/shell/bazel/toolchain_test.sh
@@ -350,7 +350,8 @@
     --toolchain_resolution_debug \
     //demo:use &> $TEST_log || fail "Build failed"
   expect_log 'ToolchainResolution: Looking for toolchain of type //toolchain:test_toolchain'
-  expect_log 'ToolchainResolution:   Selected execution platforms and toolchains: {@bazel_tools//platforms:host_platform -> //:test_toolchain_impl_1}'
+  expect_log 'ToolchainResolution:   For toolchain type //toolchain:test_toolchain, possible execution platforms and toolchains: {@bazel_tools//platforms:host_platform -> //:test_toolchain_impl_1}'
+  expect_log 'ToolchainUtil: Selected execution platform @bazel_tools//platforms:host_platform, type //toolchain:test_toolchain -> toolchain //:test_toolchain_impl_1'
   expect_log 'Using toolchain: rule message: "this is the rule", toolchain extra_str: "foo from test_toolchain"'
 }
 
@@ -648,10 +649,10 @@
 EOF
 
   bazel build --platforms=//platform:not_a_platform //demo:use &> $TEST_log && fail "Build failure expected"
-  expect_log "While resolving toolchains for target //demo:use: Target //platform:not_a_platform was found as the target platform, but does not provide PlatformInfo"
+  expect_log "While resolving toolchains for target //demo:use: Target //platform:not_a_platform was referenced as a platform, but does not provide PlatformInfo"
 
   bazel build --host_platform=//platform:not_a_platform //demo:use &> $TEST_log && fail "Build failure expected"
-  expect_log "While resolving toolchains for target //demo:use: Target //platform:not_a_platform was found as the host platform, but does not provide PlatformInfo"
+  expect_log "While resolving toolchains for target //demo:use: Target //platform:not_a_platform was referenced as a platform, but does not provide PlatformInfo"
 }
 
 run_suite "toolchain tests"