diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index 11daaa7..d4dbb0e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -205,20 +205,34 @@
 
   /**
    * Invokes the appropriate constructor to create a {@link ConfiguredTarget} instance.
+   *
    * <p>For use in {@code ConfiguredTargetFunction}.
    *
    * <p>Returns null if Skyframe deps are missing or upon certain errors.
    */
   @Nullable
-  public final ConfiguredTarget createConfiguredTarget(AnalysisEnvironment analysisEnvironment,
-      ArtifactFactory artifactFactory, Target target, BuildConfiguration config,
+  public final ConfiguredTarget createConfiguredTarget(
+      AnalysisEnvironment analysisEnvironment,
+      ArtifactFactory artifactFactory,
+      Target target,
+      BuildConfiguration config,
       BuildConfiguration hostConfig,
       OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      ImmutableMap<Label, ConfigMatchingProvider> configConditions)
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      @Nullable ToolchainContext toolchainContext)
       throws InterruptedException {
     if (target instanceof Rule) {
-      return createRule(analysisEnvironment, (Rule) target, config, hostConfig,
-          prerequisiteMap, configConditions);
+      Preconditions.checkArgument(
+          toolchainContext != null,
+          "ToolchainContext should never be null when creating a ConfiguredTarget for a Rule");
+      return createRule(
+          analysisEnvironment,
+          (Rule) target,
+          config,
+          hostConfig,
+          prerequisiteMap,
+          configConditions,
+          toolchainContext);
     }
 
     // Visibility, like all package groups, doesn't have a configuration
@@ -271,10 +285,18 @@
    */
   @Nullable
   private ConfiguredTarget createRule(
-      AnalysisEnvironment env, Rule rule, BuildConfiguration configuration,
+      AnalysisEnvironment env,
+      Rule rule,
+      BuildConfiguration configuration,
       BuildConfiguration hostConfiguration,
       OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      ToolchainContext toolchainContext)
+      throws InterruptedException {
+
+    // Load the requested toolchains into the ToolchainContext.
+    toolchainContext.resolveToolchains(prerequisiteMap);
+
     // Visibility computation and checking is done for every rule.
     RuleContext ruleContext =
         new RuleContext.Builder(
@@ -289,9 +311,7 @@
             .setPrerequisites(prerequisiteMap)
             .setConfigConditions(configConditions)
             .setUniversalFragment(ruleClassProvider.getUniversalFragment())
-            // TODO(katre): Populate the actual selected toolchains.
-            .setToolchainContext(
-                new ToolchainContext(rule.getRuleClassObject().getRequiredToolchains(), null))
+            .setToolchainContext(toolchainContext)
             .build();
     if (ruleContext.hasErrors()) {
       return null;
@@ -365,9 +385,10 @@
           return aspect.getDescriptor();
         }
       };
+
   /**
-   * Constructs an {@link ConfiguredAspect}. Returns null if an error occurs; in that case,
-   * {@code aspectFactory} should call one of the error reporting methods of {@link RuleContext}.
+   * Constructs an {@link ConfiguredAspect}. Returns null if an error occurs; in that case, {@code
+   * aspectFactory} should call one of the error reporting methods of {@link RuleContext}.
    */
   public ConfiguredAspect createAspect(
       AnalysisEnvironment env,
@@ -377,9 +398,14 @@
       Aspect aspect,
       OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      ToolchainContext toolchainContext,
       BuildConfiguration aspectConfiguration,
       BuildConfiguration hostConfiguration)
       throws InterruptedException {
+
+    // Load the requested toolchains into the ToolchainContext.
+    toolchainContext.resolveToolchains(prerequisiteMap);
+
     RuleContext.Builder builder = new RuleContext.Builder(
         env,
         associatedTarget.getTarget().getAssociatedRule(),
@@ -397,9 +423,7 @@
             .setAspectAttributes(aspect.getDefinition().getAttributes())
             .setConfigConditions(configConditions)
             .setUniversalFragment(ruleClassProvider.getUniversalFragment())
-            // TODO(katre): Populate the actual selected toolchains.
-            .setToolchainContext(
-                new ToolchainContext(aspect.getDefinition().getRequiredToolchains(), null))
+            .setToolchainContext(toolchainContext)
             .build();
     if (ruleContext.hasErrors()) {
       return null;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
index 6eea61a..69fe02a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
@@ -22,6 +22,7 @@
 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;
+import com.google.devtools.build.lib.analysis.config.HostTransition;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
 import com.google.devtools.build.lib.analysis.config.PatchTransition;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -93,12 +94,16 @@
       @Nullable Aspect aspect,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws EvalException, InvalidConfigurationException, InterruptedException,
-             InconsistentAspectOrderException {
+          InconsistentAspectOrderException {
     NestedSetBuilder<Label> rootCauses = NestedSetBuilder.<Label>stableOrder();
-    OrderedSetMultimap<Attribute, Dependency> outgoingEdges = dependentNodeMap(
-        node, hostConfig,
-        aspect != null ? ImmutableList.of(aspect) : ImmutableList.<Aspect>of(),
-        configConditions, rootCauses);
+    OrderedSetMultimap<Attribute, Dependency> outgoingEdges =
+        dependentNodeMap(
+            node,
+            hostConfig,
+            aspect != null ? ImmutableList.of(aspect) : ImmutableList.<Aspect>of(),
+            configConditions,
+            /*toolchainContext=*/ null,
+            rootCauses);
     if (!rootCauses.isEmpty()) {
       throw new IllegalStateException(rootCauses.build().iterator().next().toString());
     }
@@ -113,14 +118,13 @@
    * <p>If {@code aspects} is empty, returns the dependent nodes of the configured target node
    * representing the given target and configuration.
    *
-   * Otherwise {@code aspects} represents an aspect path. The function returns dependent nodes
-   * of the entire path applied to given target and configuration. These are the depenent nodes
-   * of the last aspect in the path.
+   * <p>Otherwise {@code aspects} represents an aspect path. The function returns dependent nodes of
+   * the entire path applied to given target and configuration. These are the depenent nodes of the
+   * last aspect in the path.
    *
-   * <p>This also implements the first step of applying
-   * configuration transitions, namely, split transitions. This needs to be done before the labels
-   * are resolved because late bound attributes depend on the configuration. A good example for this
-   * is @{code :cc_toolchain}.
+   * <p>This also implements the first step of applying configuration transitions, namely, split
+   * transitions. This needs to be done before the labels are resolved because late bound attributes
+   * depend on the configuration. A good example for this is @{code :cc_toolchain}.
    *
    * <p>The long-term goal is that most configuration transitions be applied here. However, in order
    * to do that, we first have to eliminate transitions that depend on the rule class of the
@@ -131,17 +135,19 @@
    *     This is needed to support {@link LateBoundDefault#useHostConfiguration()}.
    * @param aspects the aspects applied to this target (if any)
    * @param configConditions resolver for config_setting labels
-   * @param rootCauses collector for dep labels that can't be (loading phase) loaded
-   * @return a mapping of each attribute in this rule or aspects to its dependent nodes
+   * @param toolchainContext context information for required toolchains
+   * @param rootCauses collector for dep labels that can't be (loading phase) loaded @return a
+   *     mapping of each attribute in this rule or aspects to its dependent nodes
    */
   public final OrderedSetMultimap<Attribute, Dependency> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      @Nullable ToolchainContext toolchainContext,
       NestedSetBuilder<Label> rootCauses)
       throws EvalException, InvalidConfigurationException, InterruptedException,
-      InconsistentAspectOrderException {
+          InconsistentAspectOrderException {
     Target target = node.getTarget();
     BuildConfiguration config = node.getConfiguration();
     OrderedSetMultimap<Attribute, Dependency> outgoingEdges = OrderedSetMultimap.create();
@@ -155,7 +161,8 @@
     } else if (target instanceof EnvironmentGroup) {
       visitTargetVisibility(node, rootCauses, outgoingEdges.get(null));
     } else if (target instanceof Rule) {
-      visitRule(node, hostConfig, aspects, configConditions, rootCauses, outgoingEdges);
+      visitRule(
+          node, hostConfig, aspects, configConditions, toolchainContext, rootCauses, outgoingEdges);
     } else if (target instanceof PackageGroup) {
       visitPackageGroup(node, (PackageGroup) target, rootCauses, outgoingEdges.get(null));
     } else {
@@ -170,10 +177,11 @@
       BuildConfiguration hostConfig,
       Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      @Nullable ToolchainContext toolchainContext,
       NestedSetBuilder<Label> rootCauses,
       OrderedSetMultimap<Attribute, Dependency> outgoingEdges)
       throws EvalException, InvalidConfigurationException, InconsistentAspectOrderException,
-             InterruptedException{
+          InterruptedException {
     Preconditions.checkArgument(node.getTarget() instanceof Rule);
     BuildConfiguration ruleConfig = Preconditions.checkNotNull(node.getConfiguration());
     Rule rule = (Rule) node.getTarget();
@@ -186,6 +194,12 @@
     visitTargetVisibility(node, rootCauses, outgoingEdges.get(null));
     resolveEarlyBoundAttributes(depResolver);
     resolveLateBoundAttributes(depResolver, ruleConfig, hostConfig);
+
+    if (toolchainContext != null) {
+      Attribute toolchainsAttribute =
+          attributeMap.getAttributeDefinition(PlatformSemantics.TOOLCHAINS_ATTR);
+      resolveToolchainDependencies(outgoingEdges.get(toolchainsAttribute), toolchainContext);
+    }
   }
 
   /**
@@ -396,6 +410,16 @@
     }
   }
 
+  private void resolveToolchainDependencies(
+      Set<Dependency> dependencies, ToolchainContext toolchainContext) {
+    for (Label label : toolchainContext.getResolvedToolchainLabels()) {
+      Dependency dependency =
+          Dependency.withTransitionAndAspects(
+              label, HostTransition.INSTANCE, AspectCollection.EMPTY);
+      dependencies.add(dependency);
+    }
+  }
+
   /**
    * Returns the BuildOptions if the rule's attribute triggers a split in this configuration, or
    * the empty collection if the attribute does not trigger a split transition or if the split
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/PlatformSemantics.java b/src/main/java/com/google/devtools/build/lib/analysis/PlatformSemantics.java
index 7da9d4c..d93c5a6 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/PlatformSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/PlatformSemantics.java
@@ -18,9 +18,8 @@
 import static com.google.devtools.build.lib.packages.BuildType.LABEL;
 import static com.google.devtools.build.lib.packages.BuildType.LABEL_LIST;
 
+import com.google.common.collect.ImmutableList;
 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.packages.Attribute;
 import com.google.devtools.build.lib.packages.AttributeMap;
@@ -33,22 +32,7 @@
 
   public static final String TARGET_PLATFORMS_ATTR = ":target_platforms";
   public static final String EXECUTION_PLATFORM_ATTR = ":execution_platform";
-
-  public Iterable<PlatformInfo> getTargetPlatforms(RuleContext ruleContext) {
-    Iterable<PlatformInfo> platform =
-        PlatformProviderUtils.platforms(
-            ruleContext.getPrerequisites(
-                TARGET_PLATFORMS_ATTR, RuleConfiguredTarget.Mode.DONT_CHECK));
-    return platform;
-  }
-
-  public PlatformInfo getExecutionPlatform(RuleContext ruleContext) {
-    PlatformInfo platform =
-        PlatformProviderUtils.platform(
-            ruleContext.getPrerequisite(
-                EXECUTION_PLATFORM_ATTR, RuleConfiguredTarget.Mode.DONT_CHECK));
-    return platform;
-  }
+  public static final String TOOLCHAINS_ATTR = "$toolchains";
 
   /** Implementation for the :target_platform attribute. */
   public static final Attribute.LateBoundLabelList<BuildConfiguration> TARGET_PLATFORM =
@@ -62,6 +46,7 @@
           return configuration.getFragment(PlatformConfiguration.class).getTargetPlatforms();
         }
       };
+
   /** Implementation for the :execution_platform attribute. */
   public static final Attribute.LateBoundLabel<BuildConfiguration> EXECUTION_PLATFORM =
       new Attribute.LateBoundLabel<BuildConfiguration>(PlatformConfiguration.class) {
@@ -83,6 +68,10 @@
         .add(
             attr(EXECUTION_PLATFORM_ATTR, LABEL)
                 .value(EXECUTION_PLATFORM)
-                .nonconfigurable("Used in toolchain resolution"));
+                .nonconfigurable("Used in toolchain resolution"))
+        .add(
+            attr(TOOLCHAINS_ATTR, LABEL_LIST)
+                .nonconfigurable("Used in toolchain resolution")
+                .value(ImmutableList.of()));
   }
 }
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 8e3a1d0..fc52bd6 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
@@ -14,33 +14,186 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import static java.util.stream.Collectors.joining;
+
+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.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.syntax.SkylarkDict;
-import java.util.Map;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+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.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.SkylarkIndexable;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
+import com.google.devtools.build.lib.util.Preconditions;
+import java.util.List;
+import java.util.Optional;
 import javax.annotation.Nullable;
 
 /** Contains toolchain-related information needed for a {@link RuleContext}. */
+@Immutable
+@ThreadSafe
+@SkylarkModule(
+  name = "ToolchainContext",
+  category = SkylarkModuleCategory.BUILTIN,
+  doc = "Stores toolchains available to a given rule."
+)
 public class ToolchainContext {
+  public static ToolchainContext create(
+      List<Label> requiredToolchains, ImmutableBiMap<Label, Label> resolvedLabels) {
+    ToolchainContext toolchainContext =
+        new ToolchainContext(requiredToolchains, new ResolvedToolchainLabels(resolvedLabels));
+    return toolchainContext;
+  }
+
   private final ImmutableList<Label> requiredToolchains;
-  private final ImmutableMap<Label, ToolchainInfo> toolchains;
 
-  public ToolchainContext(
-      ImmutableList<Label> requiredToolchains, @Nullable Map<Label, ToolchainInfo> toolchains) {
-    this.requiredToolchains = requiredToolchains;
-    this.toolchains =
-        toolchains == null
-            ? ImmutableMap.<Label, ToolchainInfo>of()
-            : ImmutableMap.copyOf(toolchains);
+  // Map from toolchain type labels to actual resolved toolchain labels.
+  private final ResolvedToolchainLabels resolvedToolchainLabels;
+
+  // Stores the actual ToolchainInfo provider for each toolchain type.
+  private ResolvedToolchainProviders resolvedToolchainProviders =
+      ResolvedToolchainProviders.empty();
+
+  private ToolchainContext(
+      List<Label> requiredToolchains, ResolvedToolchainLabels resolvedToolchainLabels) {
+    this.requiredToolchains = ImmutableList.copyOf(requiredToolchains);
+    this.resolvedToolchainLabels = resolvedToolchainLabels;
   }
 
-  public ImmutableList<Label> getRequiredToolchains() {
-    return requiredToolchains;
+  public void resolveToolchains(OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap) {
+    if (!this.requiredToolchains.isEmpty()) {
+      this.resolvedToolchainProviders =
+          ResolvedToolchainProviders.create(resolvedToolchainLabels, prerequisiteMap);
+    }
   }
 
-  public SkylarkDict<Label, ToolchainInfo> collectToolchains() {
-    return SkylarkDict.<Label, ToolchainInfo>copyOf(null, toolchains);
+  @Nullable
+  public SkylarkIndexable getResolvedToolchainProviders() {
+    return resolvedToolchainProviders;
+  }
+
+  public ImmutableSet<Label> getResolvedToolchainLabels() {
+    return resolvedToolchainLabels.getToolchainLabels();
+  }
+
+  /** 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();
+    }
+  }
+
+  /** Tracks the mapping from toolchain type label to {@link ToolchainInfo} provider. */
+  private static class ResolvedToolchainProviders implements SkylarkValue, SkylarkIndexable {
+    private static ResolvedToolchainProviders empty() {
+      return new ResolvedToolchainProviders(ImmutableMap.<Label, ToolchainInfo>of());
+    }
+
+    private static ResolvedToolchainProviders create(
+        ResolvedToolchainLabels resolvedToolchainLabels,
+        OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap) {
+      // Find the prerequisites associated with the $toolchains attribute.
+      Optional<Attribute> toolchainAttribute =
+          prerequisiteMap
+              .keys()
+              .stream()
+              .filter(attribute -> attribute.getName().equals(PlatformSemantics.TOOLCHAINS_ATTR))
+              .findFirst();
+      Preconditions.checkState(
+          toolchainAttribute.isPresent(),
+          "No toolchains attribute found while loading resolved toolchains");
+
+      ImmutableMap.Builder<Label, ToolchainInfo> toolchains = new ImmutableMap.Builder<>();
+      for (ConfiguredTarget target : prerequisiteMap.get(toolchainAttribute.get())) {
+        Label discoveredLabel = target.getLabel();
+        Label toolchainType = resolvedToolchainLabels.getType(discoveredLabel);
+        if (toolchainType != null) {
+          ToolchainInfo toolchainInfo = PlatformProviderUtils.toolchain(target);
+          toolchains.put(toolchainType, toolchainInfo);
+        }
+      }
+      return new ResolvedToolchainProviders(toolchains.build());
+    }
+
+    private final ImmutableMap<Label, ToolchainInfo> toolchains;
+
+    private ResolvedToolchainProviders(ImmutableMap<Label, ToolchainInfo> toolchains) {
+      this.toolchains = toolchains;
+    }
+
+    @Override
+    public boolean isImmutable() {
+      return true;
+    }
+
+    @Override
+    public void repr(SkylarkPrinter printer) {
+      printer.append("<toolchain_context.resolved_labels: ");
+      printer.append(toolchains.keySet().stream()
+          .map(key -> key.toString())
+          .collect(joining(", ")));
+      printer.append(">");
+    }
+
+    private Label transformKey(Object key, Location loc) throws EvalException {
+      if (key instanceof Label) {
+        Label toolchainType = (Label) key;
+        return toolchainType;
+      } else if (key instanceof String) {
+        Label toolchainType = null;
+        String rawLabel = (String) key;
+        try {
+          toolchainType = Label.parseAbsolute(rawLabel);
+        } catch (LabelSyntaxException e) {
+          throw new EvalException(
+              loc, String.format("Unable to parse toolchain %s: %s", rawLabel, e.getMessage()), e);
+        }
+        return toolchainType;
+      } else {
+        throw new EvalException(
+            loc,
+            String.format(
+                "Toolchains only supports indexing by toolchain type, got %s instead",
+                EvalUtils.getDataTypeName(key)));
+      }
+    }
+
+    @Override
+    public ToolchainInfo getIndex(Object key, Location loc) throws EvalException {
+      Label toolchainType = transformKey(key, loc);
+      return toolchains.get(toolchainType);
+    }
+
+    @Override
+    public boolean containsKey(Object key, Location loc) throws EvalException {
+      Label toolchainType = transformKey(key, loc);
+      return toolchains.containsKey(toolchainType);
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
index 88eb059..7590bc3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
@@ -36,7 +36,6 @@
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.FragmentCollection;
-import com.google.devtools.build.lib.analysis.platform.ToolchainInfo;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Location;
@@ -66,6 +65,7 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression.FuncallException;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
+import com.google.devtools.build.lib.syntax.SkylarkIndexable;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkSemanticsOptions;
 import com.google.devtools.build.lib.syntax.SkylarkType;
@@ -186,7 +186,6 @@
   private SkylarkRuleAttributesCollection attributesCollection;
   private SkylarkRuleAttributesCollection ruleAttributesCollection;
   private SkylarkClassObject splitAttributes;
-  private SkylarkDict<Label, ToolchainInfo> toolchains;
 
   // TODO(bazel-team): we only need this because of the css_binary rule.
   private ImmutableMap<Artifact, Label> artifactsLabelMap;
@@ -292,10 +291,6 @@
     }
 
     makeVariables = ruleContext.getConfigurationMakeVariableContext().collectMakeVariables();
-    toolchains =
-        ruleContext.getToolchainContext() == null
-            ? SkylarkDict.<Label, ToolchainInfo>of(null)
-            : ruleContext.getToolchainContext().collectToolchains();
   }
 
   /**
@@ -315,7 +310,6 @@
     splitAttributes = null;
     artifactsLabelMap = null;
     outputsObject = null;
-    toolchains = null;
   }
 
   public void checkMutable(String attrName) throws EvalException {
@@ -852,14 +846,9 @@
   }
 
   @SkylarkCallable(structField = true, doc = "Toolchains required for this rule.")
-  public SkylarkDict<Label, ToolchainInfo> toolchains() throws EvalException {
+  public SkylarkIndexable toolchains() throws EvalException {
     checkMutable("toolchains");
-    if (isForAspect) {
-      // TODO(katre): Support toolchains on aspects.
-      throw new EvalException(
-          Location.BUILTIN, "'toolchains' is not available in aspect implementations");
-    }
-    return toolchains;
+    return ruleContext.getToolchainContext().getResolvedToolchainProviders();
   }
 
   @Override
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 5569a64..b01faa9 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
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.analysis.MergedConfiguredTarget;
 import com.google.devtools.build.lib.analysis.MergedConfiguredTarget.DuplicateException;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
@@ -54,6 +55,7 @@
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.DependencyEvaluationException;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction.SkylarkImportFailedException;
+import com.google.devtools.build.lib.skyframe.ToolchainUtil.ToolchainContextException;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -264,18 +266,35 @@
         return null;
       }
 
+      // Determine what toolchains are needed by this target.
+      ToolchainContext toolchainContext;
+      try {
+        ImmutableList<Label> requiredToolchains = aspect.getDefinition().getRequiredToolchains();
+        toolchainContext =
+            ToolchainUtil.createToolchainContext(
+                env, requiredToolchains, key.getAspectConfiguration());
+      } catch (ToolchainContextException e) {
+        // TODO(katre): better error handling
+        throw new AspectCreationException(e.getMessage());
+      }
+      if (env.valuesMissing()) {
+        return null;
+      }
+
       OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap;
       try {
-        depValueMap = ConfiguredTargetFunction.computeDependencies(
-            env,
-            resolver,
-            originalTargetAndAspectConfiguration,
-            aspectPath,
-            configConditions,
-            ruleClassProvider,
-            view.getHostConfiguration(originalTargetAndAspectConfiguration.getConfiguration()),
-            transitivePackages,
-            transitiveRootCauses);
+        depValueMap =
+            ConfiguredTargetFunction.computeDependencies(
+                env,
+                resolver,
+                originalTargetAndAspectConfiguration,
+                aspectPath,
+                configConditions,
+                toolchainContext,
+                ruleClassProvider,
+                view.getHostConfiguration(originalTargetAndAspectConfiguration.getConfiguration()),
+                transitivePackages,
+                transitiveRootCauses);
       } catch (ConfiguredTargetFunctionException e) {
         throw new AspectCreationException(e.getMessage());
       }
@@ -296,6 +315,7 @@
           associatedTarget,
           key.getAspectConfiguration(),
           configConditions,
+          toolchainContext,
           depValueMap,
           transitivePackages);
     } catch (DependencyEvaluationException e) {
@@ -419,6 +439,7 @@
       ConfiguredTarget associatedTarget,
       BuildConfiguration aspectConfiguration,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      ToolchainContext toolchainContext,
       OrderedSetMultimap<Attribute, ConfiguredTarget> directDeps,
       NestedSetBuilder<Package> transitivePackages)
       throws AspectFunctionException, InterruptedException {
@@ -434,16 +455,19 @@
 
     ConfiguredAspect configuredAspect;
     if (ConfiguredTargetFunction.aspectMatchesConfiguredTarget(associatedTarget, aspect)) {
-      configuredAspect = view.getConfiguredTargetFactory().createAspect(
-          analysisEnvironment,
-          associatedTarget,
-          aspectPath,
-          aspectFactory,
-          aspect,
-          directDeps,
-          configConditions,
-          aspectConfiguration,
-          view.getHostConfiguration(aspectConfiguration));
+      configuredAspect =
+          view.getConfiguredTargetFactory()
+              .createAspect(
+                  analysisEnvironment,
+                  associatedTarget,
+                  aspectPath,
+                  aspectFactory,
+                  aspect,
+                  directDeps,
+                  configConditions,
+                  toolchainContext,
+                  aspectConfiguration,
+                  view.getHostConfiguration(aspectConfiguration));
     } else {
       configuredAspect = ConfiguredAspect.forNonapplicableTarget(aspect.getDescriptor());
     }
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 27cc526..0d11365 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
@@ -42,6 +42,7 @@
 import com.google.devtools.build.lib.analysis.MergedConfiguredTarget;
 import com.google.devtools.build.lib.analysis.MergedConfiguredTarget.DuplicateException;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
@@ -72,6 +73,8 @@
 import com.google.devtools.build.lib.skyframe.AspectFunction.AspectCreationException;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
+import com.google.devtools.build.lib.skyframe.ToolchainUtil.ToolchainContextException;
+import com.google.devtools.build.lib.skyframe.ToolchainUtil.UnresolvedToolchainsException;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -99,12 +102,12 @@
 /**
  * SkyFunction for {@link ConfiguredTargetValue}s.
  *
- * This class, together with {@link AspectFunction} drives the analysis phase. For more information,
- * see {@link com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory}.
+ * <p>This class, together with {@link AspectFunction} drives the analysis phase. For more
+ * information, see {@link com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory}.
  *
  * @see com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory
  */
-final class ConfiguredTargetFunction implements SkyFunction {
+public final class ConfiguredTargetFunction implements SkyFunction {
   // This construction is a bit funky, but guarantees that the Object reference here is globally
   // unique.
   static final ImmutableMap<Label, ConfigMatchingProvider> NO_CONFIG_CONDITIONS =
@@ -231,6 +234,19 @@
             new ConfiguredValueCreationException(transitiveLoadingRootCauses.build()));
       }
 
+      // Determine what toolchains are needed by this target.
+      ToolchainContext toolchainContext = null;
+      if (target instanceof Rule) {
+        ImmutableList<Label> requiredToolchains =
+            ((Rule) target).getRuleClassObject().getRequiredToolchains();
+        toolchainContext =
+            ToolchainUtil.createToolchainContext(env, requiredToolchains, configuration);
+        if (env.valuesMissing()) {
+          return null;
+        }
+      }
+
+      // Calculate the dependencies of this target.
       OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap =
           computeDependencies(
               env,
@@ -238,6 +254,7 @@
               ctgValue,
               ImmutableList.<Aspect>of(),
               configConditions,
+              toolchainContext,
               ruleClassProvider,
               view.getHostConfiguration(configuration),
               transitivePackages,
@@ -250,8 +267,16 @@
             new ConfiguredValueCreationException(transitiveLoadingRootCauses.build()));
       }
       Preconditions.checkNotNull(depValueMap);
-      ConfiguredTargetValue ans = createConfiguredTarget(
-          view, env, target, configuration, depValueMap, configConditions, transitivePackages);
+      ConfiguredTargetValue ans =
+          createConfiguredTarget(
+              view,
+              env,
+              target,
+              configuration,
+              depValueMap,
+              configConditions,
+              toolchainContext,
+              transitivePackages);
       return ans;
     } catch (DependencyEvaluationException e) {
       if (e.getCause() instanceof ConfiguredValueCreationException) {
@@ -276,28 +301,45 @@
       }
       throw new ConfiguredTargetFunctionException(
           new ConfiguredValueCreationException(e.getMessage(), analysisRootCause));
+    } catch (ToolchainContextException e) {
+      if (e.getCause() instanceof UnresolvedToolchainsException) {
+        UnresolvedToolchainsException ute = (UnresolvedToolchainsException) e.getCause();
+        env.getListener()
+            .handle(Event.error(ute.getMessage() + " for target " + target.getLabel()));
+        throw new ConfiguredTargetFunctionException(
+            new ConfiguredValueCreationException(ute.getMessage(), target.getLabel()));
+      } else if (e.getCause() instanceof ConfiguredValueCreationException) {
+        ConfiguredValueCreationException cvce = (ConfiguredValueCreationException) e.getCause();
+        throw new ConfiguredTargetFunctionException(cvce);
+      } else {
+        // TODO(katre): better error handling
+        throw new ConfiguredTargetFunctionException(
+            new ConfiguredValueCreationException(e.getMessage()));
+      }
     } finally {
       cpuBoundSemaphore.release();
     }
   }
 
   /**
-   * Computes the direct dependencies of a node in the configured target graph (a configured
-   * target or an aspects).
+   * Computes the direct dependencies of a node in the configured target graph (a configured target
+   * or an aspects).
    *
    * <p>Returns null if Skyframe hasn't evaluated the required dependencies yet. In this case, the
    * caller should also return null to Skyframe.
-   *  @param env the Skyframe environment
+   *
+   * @param env the Skyframe environment
    * @param resolver the dependency resolver
    * @param ctgValue the label and the configuration of the node
    * @param aspects
    * @param configConditions the configuration conditions for evaluating the attributes of the node
+   * @param toolchainContext context information for required toolchains
    * @param ruleClassProvider rule class provider for determining the right configuration fragments
-   *   to apply to deps
+   *     to apply to deps
    * @param hostConfiguration the host configuration. There's a noticeable performance hit from
    *     instantiating this on demand for every dependency that wants it, so it's best to compute
    *     the host configuration as early as possible and pass this reference to all consumers
-   * */
+   */
   @Nullable
   static OrderedSetMultimap<Attribute, ConfiguredTarget> computeDependencies(
       Environment env,
@@ -305,17 +347,24 @@
       TargetAndConfiguration ctgValue,
       Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      @Nullable ToolchainContext toolchainContext,
       RuleClassProvider ruleClassProvider,
       BuildConfiguration hostConfiguration,
       NestedSetBuilder<Package> transitivePackages,
       NestedSetBuilder<Label> transitiveLoadingRootCauses)
       throws DependencyEvaluationException, ConfiguredTargetFunctionException,
-      AspectCreationException, InterruptedException {
+          AspectCreationException, InterruptedException {
     // Create the map from attributes to set of (target, configuration) pairs.
     OrderedSetMultimap<Attribute, Dependency> depValueNames;
     try {
-      depValueNames = resolver.dependentNodeMap(
-          ctgValue, hostConfiguration, aspects, configConditions, transitiveLoadingRootCauses);
+      depValueNames =
+          resolver.dependentNodeMap(
+              ctgValue,
+              hostConfiguration,
+              aspects,
+              configConditions,
+              toolchainContext,
+              transitiveLoadingRootCauses);
     } catch (EvalException e) {
       // EvalException can only be thrown by computed Skylark attributes in the current rule.
       env.getListener().handle(Event.error(e.getLocation(), e.getMessage()));
@@ -1102,10 +1151,14 @@
   }
 
   @Nullable
-  private ConfiguredTargetValue createConfiguredTarget(SkyframeBuildView view,
-      Environment env, Target target, BuildConfiguration configuration,
+  private ConfiguredTargetValue createConfiguredTarget(
+      SkyframeBuildView view,
+      Environment env,
+      Target target,
+      BuildConfiguration configuration,
       OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      @Nullable ToolchainContext toolchainContext,
       NestedSetBuilder<Package> transitivePackages)
       throws ConfiguredTargetFunctionException, InterruptedException {
     StoredEventHandler events = new StoredEventHandler();
@@ -1122,8 +1175,14 @@
     }
 
     Preconditions.checkNotNull(depValueMap);
-    ConfiguredTarget configuredTarget = view.createConfiguredTarget(target, configuration,
-        analysisEnvironment, depValueMap, configConditions);
+    ConfiguredTarget configuredTarget =
+        view.createConfiguredTarget(
+            target,
+            configuration,
+            analysisEnvironment,
+            depValueMap,
+            configConditions,
+            toolchainContext);
 
     events.replayOn(env.getListener());
     if (events.hasErrors()) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index 14a96e5..4f1d96e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -38,6 +38,7 @@
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.ConfiguredTargetFactory;
 import com.google.devtools.build.lib.analysis.LabelAndConfiguration;
+import com.google.devtools.build.lib.analysis.ToolchainContext;
 import com.google.devtools.build.lib.analysis.ViewCreationFailedException;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory.BuildInfoKey;
@@ -477,18 +478,28 @@
    * <p>Returns null if Skyframe deps are missing or upon certain errors.
    */
   @Nullable
-  ConfiguredTarget createConfiguredTarget(Target target, BuildConfiguration configuration,
+  ConfiguredTarget createConfiguredTarget(
+      Target target,
+      BuildConfiguration configuration,
       CachingAnalysisEnvironment analysisEnvironment,
       OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
+      @Nullable ToolchainContext toolchainContext)
+      throws InterruptedException {
     Preconditions.checkState(enableAnalysis,
         "Already in execution phase %s %s", target, configuration);
     Preconditions.checkNotNull(analysisEnvironment);
     Preconditions.checkNotNull(target);
     Preconditions.checkNotNull(prerequisiteMap);
-    return factory.createConfiguredTarget(analysisEnvironment, artifactFactory, target,
-        configuration, getHostConfiguration(configuration), prerequisiteMap,
-        configConditions);
+    return factory.createConfiguredTarget(
+        analysisEnvironment,
+        artifactFactory,
+        target,
+        configuration,
+        getHostConfiguration(configuration),
+        prerequisiteMap,
+        configConditions,
+        toolchainContext);
   }
 
   /**
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
new file mode 100644
index 0000000..3afe90a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
@@ -0,0 +1,220 @@
+// 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 com.google.auto.value.AutoValue;
+import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableBiMap;
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.analysis.ConfiguredTarget;
+import com.google.devtools.build.lib.analysis.PlatformConfiguration;
+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.skyframe.ConfiguredTargetFunction.ConfiguredValueCreationException;
+import com.google.devtools.build.lib.skyframe.RegisteredToolchainsFunction.InvalidTargetException;
+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.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunction.Environment;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.ValueOrException;
+import com.google.devtools.build.skyframe.ValueOrException4;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Common code to create a {@link ToolchainContext} given a set of required toolchain type labels.
+ */
+public class ToolchainUtil {
+
+  /**
+   * Returns a new {@link ToolchainContext}, with the correct toolchain labels based on the results
+   * of the {@link ToolchainResolutionFunction}.
+   */
+  public static ToolchainContext createToolchainContext(
+      Environment env, List<Label> requiredToolchains, BuildConfiguration configuration)
+      throws ToolchainContextException, InterruptedException {
+    ImmutableBiMap<Label, Label> resolvedLabels =
+        resolveToolchainLabels(env, requiredToolchains, configuration);
+    ToolchainContext toolchainContext = ToolchainContext.create(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 execPlatform();
+
+    abstract PlatformInfo targetPlatform();
+
+    protected static PlatformDescriptors create(
+        PlatformInfo execPlatform, PlatformInfo targetPlatform) {
+      return new AutoValue_ToolchainUtil_PlatformDescriptors(execPlatform, targetPlatform);
+    }
+  }
+
+  private static PlatformDescriptors loadPlatformDescriptors(
+      Environment env, BuildConfiguration configuration)
+      throws InterruptedException, ToolchainContextException {
+    PlatformConfiguration platformConfiguration =
+        configuration.getFragment(PlatformConfiguration.class);
+    Label executionPlatformLabel = platformConfiguration.getExecutionPlatform();
+    Label targetPlatformLabel = platformConfiguration.getTargetPlatforms().get(0);
+
+    SkyKey executionPlatformKey =
+        LegacySkyKey.create(
+            SkyFunctions.CONFIGURED_TARGET,
+            new ConfiguredTargetKey(executionPlatformLabel, configuration));
+    SkyKey targetPlatformKey =
+        LegacySkyKey.create(
+            SkyFunctions.CONFIGURED_TARGET,
+            new ConfiguredTargetKey(targetPlatformLabel, configuration));
+
+    Map<SkyKey, ValueOrException<ConfiguredValueCreationException>> values =
+        env.getValuesOrThrow(
+            ImmutableList.of(executionPlatformKey, targetPlatformKey),
+            ConfiguredValueCreationException.class);
+    if (env.valuesMissing()) {
+      return null;
+    }
+    try {
+      ConfiguredTarget executionPlatformTarget =
+          ((ConfiguredTargetValue) values.get(executionPlatformKey).get()).getConfiguredTarget();
+      ConfiguredTarget targetPlatformTarget =
+          ((ConfiguredTargetValue) values.get(targetPlatformKey).get()).getConfiguredTarget();
+      PlatformInfo execPlatform = PlatformProviderUtils.platform(executionPlatformTarget);
+      PlatformInfo targetPlatform = PlatformProviderUtils.platform(targetPlatformTarget);
+
+      return PlatformDescriptors.create(execPlatform, targetPlatform);
+    } catch (ConfiguredValueCreationException e) {
+      throw new ToolchainContextException(e);
+    }
+  }
+
+  private static ImmutableBiMap<Label, Label> resolveToolchainLabels(
+      Environment env, List<Label> requiredToolchains, BuildConfiguration configuration)
+      throws InterruptedException, ToolchainContextException {
+
+    // If there are no required toolchains, bail out early.
+    if (requiredToolchains.isEmpty()) {
+      return ImmutableBiMap.of();
+    }
+
+    // Load the execution and target platforms for the current configuration.
+    PlatformDescriptors platforms = loadPlatformDescriptors(env, configuration);
+    if (platforms == null) {
+      return null;
+    }
+
+    // Find the toolchains for the required toolchain types.
+    List<SkyKey> registeredToolchainKeys = new ArrayList<>();
+    for (Label toolchainType : requiredToolchains) {
+      registeredToolchainKeys.add(
+          ToolchainResolutionValue.key(
+              configuration, toolchainType, platforms.targetPlatform(), platforms.execPlatform()));
+    }
+
+    Map<
+            SkyKey,
+            ValueOrException4<
+                NoToolchainFoundException, ConfiguredValueCreationException, InvalidTargetException,
+                EvalException>>
+        results =
+            env.getValuesOrThrow(
+                registeredToolchainKeys,
+                NoToolchainFoundException.class,
+                ConfiguredValueCreationException.class,
+                InvalidTargetException.class,
+                EvalException.class);
+    if (env.valuesMissing()) {
+      return null;
+    }
+
+    // Load the toolchains.
+    ImmutableBiMap.Builder<Label, Label> builder = new ImmutableBiMap.Builder<>();
+    List<Label> missingToolchains = new ArrayList<>();
+    for (Map.Entry<
+            SkyKey,
+            ValueOrException4<
+                NoToolchainFoundException, ConfiguredValueCreationException, InvalidTargetException,
+                EvalException>>
+        entry : results.entrySet()) {
+      try {
+        Label requiredToolchainType =
+            ((ToolchainResolutionKey) entry.getKey().argument()).toolchainType();
+        Label toolchainLabel = ((ToolchainResolutionValue) entry.getValue().get()).toolchainLabel();
+        builder.put(requiredToolchainType, toolchainLabel);
+      } catch (NoToolchainFoundException e) {
+        // Save the missing type and continue looping to check for more.
+        missingToolchains.add(e.missingToolchainType());
+      } catch (ConfiguredValueCreationException e) {
+        throw new ToolchainContextException(e);
+      } catch (InvalidTargetException e) {
+        throw new ToolchainContextException(e);
+      } catch (EvalException e) {
+        throw new ToolchainContextException(e);
+      }
+    }
+
+    if (!missingToolchains.isEmpty()) {
+      throw new ToolchainContextException(new UnresolvedToolchainsException(missingToolchains));
+    }
+
+    return builder.build();
+  }
+
+  /** Exception used when a toolchain type is required but no matching toolchain is found. */
+  public static final class UnresolvedToolchainsException extends Exception {
+    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;
+    }
+  }
+
+  /** Exception used to wrap exceptions during toolchain resolution. */
+  public static class ToolchainContextException extends Exception {
+    public ToolchainContextException(UnresolvedToolchainsException e) {
+      super(e);
+    }
+
+    public ToolchainContextException(ConfiguredValueCreationException e) {
+      super(e);
+    }
+
+    public ToolchainContextException(InvalidTargetException e) {
+      super(e);
+    }
+
+    public ToolchainContextException(EvalException e) {
+      super(e);
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
index e8649a7..46c1cf9 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
@@ -124,6 +124,7 @@
                 (TargetAndConfiguration) skyKey.argument(),
                 ImmutableList.<Aspect>of(),
                 ImmutableMap.<Label, ConfigMatchingProvider>of(),
+                /*toolchainContext=*/ null,
                 stateProvider.lateBoundRuleClassProvider(),
                 stateProvider.lateBoundHostConfig(),
                 NestedSetBuilder.<Package>stableOrder(),
diff --git a/src/test/shell/bazel/toolchain_test.sh b/src/test/shell/bazel/toolchain_test.sh
index fcfa66e..62510c6 100755
--- a/src/test/shell/bazel/toolchain_test.sh
+++ b/src/test/shell/bazel/toolchain_test.sh
@@ -25,18 +25,7 @@
 function set_up() {
   create_new_workspace
 
-  # Create shared constraints.
-  mkdir -p constraints
-  cat >>constraints/BUILD <<EOF
-package(default_visibility = ['//visibility:public'])
-constraint_setting(name = 'os')
-constraint_value(name = 'linux',
-    constraint_setting = ':os')
-constraint_value(name = 'mac',
-    constraint_setting = ':os')
-EOF
-
-  # Create shared report rule for printing info.
+  # Create shared report rule for printing toolchain info.
   mkdir report
   touch report/BUILD
   cat >>report/report.bzl <<EOF
@@ -49,28 +38,27 @@
     print('%s = "%s"' % (field, value))
 
 report_toolchain = rule(
-  _report_impl,
-  attrs = {
-    'fields': attr.string_list(),
-    'toolchain': attr.label(providers = [platform_common.ToolchainInfo]),
-  }
+    implementation = _report_impl,
+    attrs = {
+        'fields': attr.string_list(),
+        'toolchain': attr.label(providers = [platform_common.ToolchainInfo]),
+    }
 )
 EOF
 }
 
-function test_toolchain_rule() {
-
+function write_test_toolchain() {
   mkdir -p toolchain
   cat >> toolchain/toolchain.bzl <<EOF
 def _test_toolchain_impl(ctx):
   toolchain = platform_common.ToolchainInfo(
-      type = Label('//toolchain:test_toolchain_type'),
+      type = Label('//toolchain:test_toolchain'),
       extra_label = ctx.attr.extra_label,
       extra_str = ctx.attr.extra_str)
   return [toolchain]
 
 test_toolchain = rule(
-    _test_toolchain_impl,
+    implementation = _test_toolchain_impl,
     attrs = {
         'extra_label': attr.label(),
         'extra_str': attr.string(),
@@ -79,10 +67,85 @@
 EOF
 
   cat >> toolchain/BUILD <<EOF
-load('//report:report.bzl', 'report_toolchain')
-load(':toolchain.bzl', 'test_toolchain')
+toolchain_type(name = 'test_toolchain')
+EOF
+}
+
+function write_test_rule() {
+  mkdir -p toolchain
+  cat >> toolchain/rule.bzl <<EOF
+def _impl(ctx):
+  toolchain = ctx.toolchains['//toolchain:test_toolchain']
+  message = ctx.attr.message
+  print(
+      'Using toolchain: rule message: "%s", toolchain extra_str: "%s"' %
+         (message, toolchain.extra_str))
+  return []
+
+use_toolchain = rule(
+    implementation = _impl,
+    attrs = {
+        'message': attr.string(),
+    },
+    toolchains = ['//toolchain:test_toolchain'],
+)
+EOF
+}
+
+function write_test_aspect() {
+  mkdir -p toolchain
+  cat >> toolchain/aspect.bzl <<EOF
+def _impl(target, ctx):
+  toolchain = ctx.toolchains['//toolchain:test_toolchain']
+  message = ctx.rule.attr.message
+  print(
+      'Using toolchain in aspect: rule message: "%s", toolchain extra_str: "%s"' %
+          (message, toolchain.extra_str))
+  return []
+
+use_toolchain = aspect(
+    implementation = _impl,
+    attrs = {},
+    toolchains = ['//toolchain:test_toolchain'],
+)
+EOF
+}
+
+function write_toolchains() {
+  cat >> WORKSPACE <<EOF
+register_toolchains('//:toolchain_1')
+EOF
+
+  cat >> BUILD <<EOF
+load('//toolchain:toolchain.bzl', 'test_toolchain')
+
+# Define the toolchain.
 filegroup(name = 'dep_rule')
-toolchain_type(name = 'test_toolchain_type')
+test_toolchain(
+    name = 'toolchain_impl_1',
+    extra_label = ':dep_rule',
+    extra_str = 'foo from 1',
+    visibility = ['//visibility:public'])
+
+# Declare the toolchain.
+toolchain(
+    name = 'toolchain_1',
+    toolchain_type = '//toolchain:test_toolchain',
+    exec_compatible_with = [],
+    target_compatible_with = [],
+    toolchain = ':toolchain_impl_1',
+    visibility = ['//visibility:public'])
+EOF
+}
+
+function test_toolchain_provider() {
+  write_test_toolchain
+
+  cat >> BUILD <<EOF
+load('//toolchain:toolchain.bzl', 'test_toolchain')
+load('//report:report.bzl', 'report_toolchain')
+
+filegroup(name = 'dep_rule')
 test_toolchain(
     name = 'linux_toolchain',
     extra_label = ':dep_rule',
@@ -95,10 +158,144 @@
 )
 EOF
 
-  bazel build //toolchain:report &> $TEST_log || fail "Build failed"
-  expect_log 'type = "//toolchain:test_toolchain_type"'
-  expect_log 'extra_label = "//toolchain:dep_rule"'
+  bazel build //:report &> $TEST_log || fail "Build failed"
+  expect_log 'type = "//toolchain:test_toolchain"'
+  expect_log 'extra_label = "//:dep_rule"'
   expect_log 'extra_str = "bar"'
 }
 
+function test_toolchain_use_in_rule {
+  write_test_toolchain
+  write_test_rule
+  write_toolchains
+
+  mkdir -p demo
+  cat >> demo/BUILD <<EOF
+load('//toolchain:rule.bzl', 'use_toolchain')
+# Use the toolchain.
+use_toolchain(
+    name = 'use',
+    message = 'this is the rule')
+EOF
+
+  bazel build //demo:use &> $TEST_log || fail "Build failed"
+  expect_log 'Using toolchain: rule message: "this is the rule", toolchain extra_str: "foo from 1"'
+}
+
+function test_toolchain_use_in_aspect {
+  write_test_toolchain
+  write_test_aspect
+  write_toolchains
+
+  mkdir -p demo
+  cat >> demo/demo.bzl <<EOF
+def _impl(ctx):
+  return []
+
+demo = rule(
+    implementation = _impl,
+    attrs = {
+        'message': attr.string(),
+    }
+)
+EOF
+  cat >> demo/BUILD <<EOF
+load(':demo.bzl', 'demo')
+demo(
+    name = 'demo',
+    message = 'bar from demo')
+EOF
+
+  bazel build \
+    --aspects //toolchain:aspect.bzl%use_toolchain \
+    //demo:demo &> $TEST_log || fail "Build failed"
+  expect_log 'Using toolchain in aspect: rule message: "bar from demo", toolchain extra_str: "foo from 1"'
+}
+
+function test_toolchain_constraints() {
+  write_test_toolchain
+  write_test_rule
+
+  cat >> WORKSPACE <<EOF
+register_toolchains('//:toolchain_1')
+register_toolchains('//:toolchain_2')
+EOF
+
+  cat >> BUILD <<EOF
+load('//toolchain:toolchain.bzl', 'test_toolchain')
+
+# Define constraints.
+constraint_setting(name = 'setting')
+constraint_value(name = 'value1', constraint_setting = ':setting')
+constraint_value(name = 'value2', constraint_setting = ':setting')
+
+platform(
+    name = 'platform1',
+    constraint_values = [':value1'],
+    visibility = ['//visibility:public'])
+platform(
+    name = 'platform2',
+    constraint_values = [':value2'],
+    visibility = ['//visibility:public'])
+
+# Define the toolchain.
+filegroup(name = 'dep_rule')
+test_toolchain(
+    name = 'toolchain_impl_1',
+    extra_label = ':dep_rule',
+    extra_str = 'foo from 1',
+    visibility = ['//visibility:public'])
+test_toolchain(
+    name = 'toolchain_impl_2',
+    extra_label = ':dep_rule',
+    extra_str = 'foo from 2',
+    visibility = ['//visibility:public'])
+
+# Declare the toolchain.
+toolchain(
+    name = 'toolchain_1',
+    toolchain_type = '//toolchain:test_toolchain',
+    exec_compatible_with = [':value1'],
+    target_compatible_with = [':value2'],
+    toolchain = ':toolchain_impl_1')
+toolchain(
+    name = 'toolchain_2',
+    toolchain_type = '//toolchain:test_toolchain',
+    exec_compatible_with = [':value2'],
+    target_compatible_with = [':value1'],
+    toolchain = ':toolchain_impl_2')
+EOF
+
+  mkdir -p demo
+  cat >> demo/BUILD <<EOF
+load('//toolchain:rule.bzl', 'use_toolchain')
+# Use the toolchain.
+use_toolchain(
+    name = 'use',
+    message = 'this is the rule')
+EOF
+
+  # This should use toolchain_1.
+  bazel build \
+    --experimental_host_platform=//:platform1 \
+    --experimental_platforms=//:platform2 \
+    //demo:use &> $TEST_log || fail "Build failed"
+  expect_log 'Using toolchain: rule message: "this is the rule", toolchain extra_str: "foo from 1"'
+
+  # This should use toolchain_2.
+  bazel build \
+    --experimental_host_platform=//:platform2 \
+    --experimental_platforms=//:platform1 \
+    //demo:use &> $TEST_log || fail "Build failed"
+  expect_log 'Using toolchain: rule message: "this is the rule", toolchain extra_str: "foo from 2"'
+
+  # This should not match any toolchains.
+  bazel build \
+    --experimental_host_platform=//:platform1 \
+    --experimental_platforms=//:platform1 \
+    //demo:use &> $TEST_log && fail "Build failure expected"
+  expect_log 'no matching toolchains found for types //toolchain:test_toolchain for target //demo:use'
+  expect_not_log 'Using toolchain: rule message:'
+}
+
 run_suite "toolchain tests"