diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SingleToolchainResolutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SingleToolchainResolutionFunction.java
index 4fb0efa..912ff66 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SingleToolchainResolutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SingleToolchainResolutionFunction.java
@@ -132,55 +132,61 @@
     ImmutableMap.Builder<ConfiguredTargetKey, Label> builder = ImmutableMap.builder();
     ToolchainTypeInfo toolchainType = null;
 
-    debugMessage(eventHandler, "Looking for toolchain of type %s...", toolchainTypeLabel);
     for (DeclaredToolchainInfo toolchain : toolchains) {
       // Make sure the type matches.
       if (!toolchain.toolchainType().typeLabel().equals(toolchainTypeLabel)) {
         continue;
       }
-      debugMessage(eventHandler, "  Considering toolchain %s...", toolchain.toolchainLabel());
 
       // Make sure the target platform matches.
       if (!checkConstraints(
-          eventHandler, toolchain.targetConstraints(), "target", targetPlatform)) {
-        debugMessage(
-            eventHandler,
-            "  Rejected toolchain %s, because of target platform mismatch",
-            toolchain.toolchainLabel());
+          eventHandler,
+          toolchain.targetConstraints(),
+          "target",
+          targetPlatform,
+          toolchainTypeLabel,
+          toolchain.toolchainLabel())) {
         continue;
       }
 
       // Find the matching execution platforms.
       for (ConfiguredTargetKey executionPlatformKey : availableExecutionPlatformKeys) {
-        PlatformInfo executionPlatform = platforms.get(executionPlatformKey);
-        if (!checkConstraints(
-            eventHandler, toolchain.execConstraints(), "execution", executionPlatform)) {
+        // Only check the toolchains if this is a new platform.
+        if (platformKeysSeen.contains(executionPlatformKey)) {
           continue;
         }
 
-        // Only add the toolchains if this is a new platform.
-        if (!platformKeysSeen.contains(executionPlatformKey)) {
-          toolchainType = toolchain.toolchainType();
-          builder.put(executionPlatformKey, toolchain.toolchainLabel());
-          platformKeysSeen.add(executionPlatformKey);
+        PlatformInfo executionPlatform = platforms.get(executionPlatformKey);
+        if (!checkConstraints(
+            eventHandler,
+            toolchain.execConstraints(),
+            "execution",
+            executionPlatform,
+            toolchainTypeLabel,
+            toolchain.toolchainLabel())) {
+          continue;
         }
+
+        debugMessage(
+            eventHandler,
+            "  Type %s: target platform %s: execution %s: Selected toolchain %s",
+            toolchainTypeLabel,
+            targetPlatform.label(),
+            executionPlatformKey.getLabel(),
+            toolchain.toolchainLabel());
+        toolchainType = toolchain.toolchainType();
+        builder.put(executionPlatformKey, toolchain.toolchainLabel());
+        platformKeysSeen.add(executionPlatformKey);
       }
     }
 
     ImmutableMap<ConfiguredTargetKey, Label> resolvedToolchainLabels = builder.build();
-    if (resolvedToolchainLabels.isEmpty()) {
-      debugMessage(eventHandler, "  No toolchains found");
-    } else {
+    if (toolchainType == null || resolvedToolchainLabels.isEmpty()) {
       debugMessage(
           eventHandler,
-          "  For toolchain type %s, possible execution platforms and toolchains: {%s}",
+          "  Type %s: target platform %s: No toolchains found.",
           toolchainTypeLabel,
-          resolvedToolchainLabels.entrySet().stream()
-              .map(e -> String.format("%s -> %s", e.getKey().getLabel(), e.getValue()))
-              .collect(joining(", ")));
-    }
-
-    if (toolchainType == null || resolvedToolchainLabels.isEmpty()) {
+          targetPlatform.label());
       throw new ToolchainResolutionFunctionException(
           new NoToolchainFoundException(toolchainTypeLabel));
     }
@@ -210,41 +216,57 @@
       @Nullable EventHandler eventHandler,
       ConstraintCollection toolchainConstraints,
       String platformType,
-      PlatformInfo platform) {
+      PlatformInfo platform,
+      Label toolchainTypeLabel,
+      Label toolchainLabel) {
 
     // Check every constraint_setting in either the toolchain or the platform.
     ImmutableSet<ConstraintSettingInfo> mismatchSettings =
         toolchainConstraints.diff(platform.constraints());
-    boolean matches = true;
-    for (ConstraintSettingInfo mismatchSetting : mismatchSettings) {
-      // If a constraint_setting has a default_constraint_value, and the platform
-      // sets a non-default constraint value for the same constraint_setting, then
-      // even toolchains with no reference to that constraint_setting will detect
-      // a mismatch here. This manifests as a toolchain resolution failure (#8778).
-      //
-      // To allow combining rulesets with their own toolchains in a single top-level
-      // workspace, toolchains that do not reference a constraint_setting should not
-      // be forced to match with it.
-      if (!toolchainConstraints.hasWithoutDefault(mismatchSetting)) {
-        continue;
-      }
-      matches = false;
 
+    // If a constraint_setting has a default_constraint_value, and the platform
+    // sets a non-default constraint value for the same constraint_setting, then
+    // even toolchains with no reference to that constraint_setting will detect
+    // a mismatch here. This manifests as a toolchain resolution failure (#8778).
+    //
+    // To allow combining rulesets with their own toolchains in a single top-level
+    // workspace, toolchains that do not reference a constraint_setting should not
+    // be forced to match with it.
+    ImmutableSet<ConstraintSettingInfo> mismatchSettingsWithDefault =
+        mismatchSettings.stream()
+            .filter(toolchainConstraints::hasWithoutDefault)
+            .collect(ImmutableSet.toImmutableSet());
+
+    if (!mismatchSettingsWithDefault.isEmpty()) {
+      String mismatchValues =
+          mismatchSettingsWithDefault.stream()
+              .filter(toolchainConstraints::has)
+              .map(s -> toolchainConstraints.get(s).label().getName())
+              .collect(joining(", "));
+      if (!mismatchValues.isEmpty()) {
+        mismatchValues = "; mismatching values: " + mismatchValues;
+      }
+
+      String missingSettings =
+          mismatchSettingsWithDefault.stream()
+              .filter(s -> !toolchainConstraints.has(s))
+              .map(s -> s.label().getName())
+              .collect(joining(", "));
+      if (!missingSettings.isEmpty()) {
+        missingSettings = "; missing: " + missingSettings;
+      }
       debugMessage(
           eventHandler,
-          "    Toolchain constraint %s has value %s, "
-              + "which does not match value %s from the %s platform %s",
-          mismatchSetting.label(),
-          toolchainConstraints.has(mismatchSetting)
-              ? toolchainConstraints.get(mismatchSetting).label()
-              : "<missing>",
-          platform.constraints().has(mismatchSetting)
-              ? platform.constraints().get(mismatchSetting).label()
-              : "<missing>",
+          "    Type %s: %s %s: Rejected toolchain %s%s%s",
+          toolchainTypeLabel,
           platformType,
-          platform.label());
+          platform.label(),
+          toolchainLabel,
+          mismatchValues,
+          missingSettings);
     }
-    return matches;
+
+    return mismatchSettingsWithDefault.isEmpty();
   }
 
   @Nullable
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 5a4dd6d..f264947 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
@@ -133,8 +133,11 @@
             .handle(
                 Event.info(
                     String.format(
-                        "ToolchainResolution: Selected execution platform %s, %s",
-                        unloadedToolchainContext.executionPlatform().label(), selectedToolchains)));
+                        "ToolchainResolution: Target platform %s: Selected execution platform %s,"
+                            + " %s",
+                        unloadedToolchainContext.targetPlatform().label(),
+                        unloadedToolchainContext.executionPlatform().label(),
+                        selectedToolchains)));
       }
       return unloadedToolchainContext;
     } catch (ToolchainException e) {
diff --git a/src/test/shell/bazel/toolchain_test.sh b/src/test/shell/bazel/toolchain_test.sh
index 701198a..397d71a 100755
--- a/src/test/shell/bazel/toolchain_test.sh
+++ b/src/test/shell/bazel/toolchain_test.sh
@@ -533,9 +533,8 @@
     --toolchain_resolution_debug \
     --incompatible_auto_configure_host_platform \
     //demo:use &> $TEST_log || fail "Build failed"
-  expect_log 'ToolchainResolution: Looking for toolchain of type //toolchain:test_toolchain'
-  expect_log 'ToolchainResolution:   For toolchain type //toolchain:test_toolchain, possible execution platforms and toolchains: {@local_config_platform//:host -> //:test_toolchain_impl_1}'
-  expect_log 'ToolchainResolution: Selected execution platform @local_config_platform//:host, type //toolchain:test_toolchain -> toolchain //:test_toolchain_impl_1'
+  expect_log 'ToolchainResolution:   Type //toolchain:test_toolchain: target platform @local_config_platform//.*: execution @local_config_platform//:host: Selected toolchain //:test_toolchain_impl_1'
+  expect_log 'ToolchainResolution: Target platform @local_config_platform//.*: Selected execution platform @local_config_platform//:host, 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"'
 }
 
@@ -914,7 +913,7 @@
     --extra_execution_platforms=//platform:test_platform \
     --toolchain_resolution_debug \
     //demo:target &> $TEST_log || fail "Build failed"
-  expect_log "ToolchainResolution: Selected execution platform //platform:test_platform"
+  expect_log "Selected execution platform //platform:test_platform"
 }