diff --git a/src/gn/label.cc b/src/gn/label.cc
index 93f3505..887f135 100644
--- a/src/gn/label.cc
+++ b/src/gn/label.cc
@@ -302,6 +302,29 @@
   return Label(dir_, name_);
 }
 
+bool Label::Matches(const Label& other, const Label& default_toolchain) const {
+  // First, the dir and name must match.
+  if (dir_ != other.dir_ || name_ != other.name_)
+    return false;
+
+  // If this instance has no toolchain
+  if (toolchain_dir_.is_null()) {
+    return other.toolchain_dir_.is_null() ||
+           (other.toolchain_dir_ == default_toolchain.dir_ &&
+            other.toolchain_name_ == default_toolchain.name_);
+  }
+
+  // If other has no toolchain
+  if (other.toolchain_dir_.is_null()) {
+    return toolchain_dir_ == default_toolchain.dir_ &&
+           toolchain_name_ == default_toolchain.name_;
+  }
+
+  // Otherwise, both explicit toolchains must match
+  return toolchain_dir_ == other.toolchain_dir_ &&
+         toolchain_name_ == other.toolchain_name_;
+}
+
 std::string Label::GetUserVisibleName(bool include_toolchain) const {
   std::string ret;
   ret.reserve(dir_.value().size() + name_.str().size() + 1);
diff --git a/src/gn/label.h b/src/gn/label.h
index de0b32c..7adca69 100644
--- a/src/gn/label.h
+++ b/src/gn/label.h
@@ -69,6 +69,11 @@
   // non-default ones, so this can make certain output more clear.
   std::string GetUserVisibleName(const Label& default_toolchain) const;
 
+  // Return true if this instance matches |other|. |default_toolchain| is
+  // used when either label doesn't have a toolchain suffix to ensure
+  // canonical and non-canonical labels are compared correctly.
+  bool Matches(const Label& other, const Label& default_toolchain) const;
+
   bool operator==(const Label& other) const {
     return hash_ == other.hash_ && name_.SameAs(other.name_) &&
            dir_ == other.dir_ && toolchain_dir_ == other.toolchain_dir_ &&
diff --git a/src/gn/label_unittest.cc b/src/gn/label_unittest.cc
index 1b545ae..3cfb85c 100644
--- a/src/gn/label_unittest.cc
+++ b/src/gn/label_unittest.cc
@@ -216,3 +216,74 @@
   // Also test empty label case.
   EXPECT_EQ("", Label().GetUserVisibleName(Label(SourceDir("//t/"), "tn")));
 }
+
+TEST(Label, Matches) {
+  // Convenience wrapper around Label for smaller test cases.
+  struct TestLabel : public Label {
+    TestLabel(const char* label) : Label(GetDir(label), GetName(label)) {}
+    TestLabel(const char* label, const char* toolchain)
+        : Label(GetDir(label),
+                GetName(label),
+                GetDir(toolchain),
+                GetName(toolchain)) {}
+
+   private:
+    SourceDir GetDir(const char* label) {
+      const char* colon = strchr(label, ':');
+      CHECK(colon) << "Missing colon in " << label;
+      return SourceDir(std::string(label, colon - label) + "/");
+    }
+
+    std::string_view GetName(const char* label) {
+      const char* colon = strchr(label, ':');
+      CHECK(colon) << "Missing colon in " << label;
+      return std::string_view(colon + 1);
+    }
+  };
+  const struct TestCase {
+    const TestLabel label_a;
+    const TestLabel label_b;
+    const TestLabel default_toolchain;
+    bool expected;
+  } test_cases[] = {
+      // clang-format off
+
+      // Same label, with or without toolchain suffixes
+      { {"//aa:a"}, {"//aa:a"}, {"//tc:one"}, true },
+      { {"//aa:a", "//tc:one"}, {"//aa:a"}, {"//tc:one"}, true },
+      { {"//aa:a"}, {"//aa:a", "//tc:one"}, {"//tc:one"}, true },
+      { {"//aa:a", "//tc:two"}, {"//aa:a", "//tc:two"}, {"//tc:one"}, true },
+
+      // Mistmatched labels, same toolchains
+      { {"//aa:a"}, {"//aa:b"}, {"//tc:one"}, false },
+      { {"//aa:a", "//tc:one"}, {"//aa:b"}, {"//tc:one"}, false },
+      { {"//aa:a"}, {"//aa:b", "//tc:one"}, {"//tc:one"}, false },
+      { {"//aa:a", "//tc:one"}, {"//aa:b", "//tc:one"}, {"//tc:one"}, false },
+
+      { {"//bb:a"}, {"//aa:a"}, {"//tc:one"}, false },
+      { {"//bb:a", "//tc:one"}, {"//aa:a"}, {"//tc:one"}, false },
+      { {"//bb:a"}, {"//aa:a", "//tc:one"}, {"//tc:one"}, false },
+      { {"//bb:a", "//tc:one"}, {"//aa:a", "//tc:one"}, {"//tc:one"}, false },
+
+      // Same labels, mistmatches tooclhains
+      { {"//aa:a"}, {"//aa:a", "//tc:two"}, {"//tc:one"}, false },
+      { {"//aa:a", "//tc:two"}, {"//aa:a"}, {"//tc:one"}, false },
+      { {"//aa:a", "//tc:two"}, {"//aa:a", "//tc:three"}, {"//tc:one"}, false },
+
+      { {"//aa:a"}, {"//aa:a", "//tc2:one"}, {"//tc:one"}, false },
+      { {"//aa:a", "//tc2:one"}, {"//aa:a"}, {"//tc:one"}, false },
+      { {"//aa:a", "//tc2:one"}, {"//aa:a", "//tc3:one"}, {"//tc:one"}, false },
+
+      // clang-format on
+  };
+  for (const auto& test_case : test_cases) {
+    EXPECT_EQ(test_case.label_a.Matches(test_case.label_b,
+                                        test_case.default_toolchain),
+              test_case.expected)
+        << "label_a: " << test_case.label_a.GetUserVisibleName(true) << " "
+        << "label_b: " << test_case.label_b.GetUserVisibleName(true) << " "
+        << "default toolchain: "
+        << test_case.default_toolchain.GetUserVisibleName(true) << " "
+        << "expected match: " << (test_case.expected ? "true" : "false");
+  }
+}
diff --git a/src/gn/target.cc b/src/gn/target.cc
index 20e8a60..dc0d539 100644
--- a/src/gn/target.cc
+++ b/src/gn/target.cc
@@ -1354,20 +1354,21 @@
 
       // Otherwise, look through the target's deps for the specified one.
       // Canonicalize the label if possible.
+      const Settings* settings = target.settings();
+      const Label& toolchain_label = settings->toolchain_label();
       Label next_label = Label::Resolve(
-          current_dir, target.settings()->build_settings()->root_path_utf8(),
-          target.settings()->toolchain_label(), next, &err_);
+          current_dir, settings->build_settings()->root_path_utf8(),
+          toolchain_label, next, &err_);
       if (next_label.is_null()) {
         err_ = Err(next.origin(), std::string("Failed to canonicalize ") +
                                       next.string_value() + std::string("."));
         return false;
       }
-      std::string canonicalize_next_label = next_label.GetUserVisibleName(true);
 
       bool found_next = false;
       for (const auto& dep : all_deps) {
         // Match against the label with the toolchain.
-        if (dep.label.GetUserVisibleName(true) == canonicalize_next_label) {
+        if (dep.label.Matches(next_label, toolchain_label)) {
           // If we haven't walked this dep yet, go down into it.
           if (targets_walked_.add(dep.ptr)) {
             if (!Walk(*dep.ptr, false))
@@ -1381,7 +1382,7 @@
       if (!found_next) {
         for (const auto& dep : target.validations()) {
           // Match against the label with the toolchain.
-          if (dep.label.GetUserVisibleName(true) == canonicalize_next_label) {
+          if (dep.label.Matches(next_label, toolchain_label)) {
             // If we haven't walked this dep yet, go down into it.
             if (targets_walked_.add(dep.ptr)) {
               if (!Walk(*dep.ptr, false))
@@ -1398,7 +1399,8 @@
       if (!found_next) {
         err_ =
             Err(next.origin(),
-                std::string("I was expecting ") + canonicalize_next_label +
+                std::string("I was expecting ") +
+                    next_label.GetUserVisibleName(true) +
                     std::string(" to be a dependency of ") +
                     target.label().GetUserVisibleName(true) +
                     ". Make sure it's included in the deps or data_deps, and "