diff --git a/src/gn/command_suggest.cc b/src/gn/command_suggest.cc
index 9a0ca03..5009b9a 100644
--- a/src/gn/command_suggest.cc
+++ b/src/gn/command_suggest.cc
@@ -5,8 +5,8 @@
 #include <stddef.h>
 
 #include <algorithm>
-#include <deque>
 #include <functional>
+#include <memory>
 #include <mutex>
 #include <tuple>
 #include <unordered_map>
@@ -187,51 +187,6 @@
   return SourceFile();
 }
 
-// Finds the shortest dependency path from `from` to `to`.
-// Returns a vector where the first element is `from` and the last is `to`.
-// Returns the empty vector if no path was found.
-std::vector<const Target*> FindDependencyPath(const Target* from,
-                                              const Target* to) {
-  std::deque<const Target*> queue;
-  std::unordered_map<const Target*, const Target*> parents;
-  parents[from] = nullptr;
-  queue.push_back(from);
-
-  const Target* cur = nullptr;
-  while (!queue.empty()) {
-    cur = queue.front();
-    queue.pop_front();
-    if (cur == to) {
-      break;
-    }
-
-    auto add_deps = [&](const LabelTargetVector& deps) {
-      for (const auto& dep : deps) {
-        if (dep.ptr) {
-          if (parents.emplace(dep.ptr, cur).second) {
-            queue.push_back(dep.ptr);
-          }
-        }
-      }
-    };
-
-    add_deps(cur->public_deps());
-    add_deps(cur->private_deps());
-  }
-
-  if (cur != to) {
-    return {};
-  }
-
-  std::vector<const Target*> path;
-  while (cur != nullptr) {
-    path.push_back(cur);
-    cur = parents[cur];
-  }
-  std::reverse(path.begin(), path.end());
-  return path;
-}
-
 }  // namespace
 
 TargetResolutionCache::TargetResolutionCache() = default;
@@ -334,6 +289,20 @@
   return results;
 }
 
+HeaderChecker::ReachabilityCache& TargetResolutionCache::GetReachabilityCache(
+    const Target* target) {
+  std::lock_guard<std::mutex> lock(reachability_cache_lock_);
+  auto it = reachability_cache_.find(target);
+  if (it == reachability_cache_.end()) {
+    it =
+        reachability_cache_
+            .emplace(target,
+                     std::make_unique<HeaderChecker::ReachabilityCache>(target))
+            .first;
+  }
+  return *it->second;
+}
+
 // Resolves an input to a list of targets, and whether each are private.
 // The input can be:
 // * A module name for a target
@@ -753,8 +722,10 @@
     std::vector<CandidateDep> candidate_deps;
     for (const auto& target : candidates) {
       Label label = target->label();
-      std::vector<const Target*> cycle = FindDependencyPath(target, includer);
-      if (!cycle.empty()) {
+      HeaderChecker::Chain cycle;
+      if (cache.GetReachabilityCache(target).SearchForDependencyTo(
+              includer, /*permitted=*/false, &cycle)) {
+        std::reverse(cycle.begin(), cycle.end());
         StartWarning();
         OutputTarget(target);
         OutputString(" depends on ");
@@ -768,7 +739,7 @@
 
         for (size_t i = 0; i < cycle.size(); i++) {
           OutputString("  ");
-          OutputTarget(cycle[i]);
+          OutputTarget(cycle[i].target);
           if (i + 1 < cycle.size()) {
             OutputString(" ->");
           }
@@ -776,7 +747,8 @@
         }
 
         bool has_allow_circular_includes_from = false;
-        for (const Target* t : cycle) {
+        for (const auto& link : cycle) {
+          const Target* t = link.target;
           if (!t->allow_circular_includes_from().empty()) {
             has_allow_circular_includes_from = true;
             SetAmbiguous();
diff --git a/src/gn/commands.h b/src/gn/commands.h
index 6325058..98009ee 100644
--- a/src/gn/commands.h
+++ b/src/gn/commands.h
@@ -7,6 +7,7 @@
 
 #include <functional>
 #include <map>
+#include <memory>
 #include <mutex>
 #include <optional>
 #include <set>
@@ -16,6 +17,7 @@
 #include <vector>
 
 #include "base/values.h"
+#include "gn/header_checker.h"
 #include "gn/standard_out.h"
 #include "gn/target.h"
 #include "gn/unique_vector.h"
@@ -149,6 +151,9 @@
       const Target& target,
       const std::vector<const Target*>& all_targets);
 
+  // Returns reference to ReachabilityCache for the given target.
+  HeaderChecker::ReachabilityCache& GetReachabilityCache(const Target* target);
+
  private:
   std::once_flag file_to_target_initialized_;
   std::unordered_map<SourceFile,
@@ -161,6 +166,12 @@
   std::once_flag forwarding_parents_initialized_;
   std::unordered_map<const Target*, std::vector<const Target*>>
       forwarding_parents_;
+
+  // Maps a Target to its ReachabilityCache for cycle detection.
+  std::mutex reachability_cache_lock_;
+  std::unordered_map<const Target*,
+                     std::unique_ptr<HeaderChecker::ReachabilityCache>>
+      reachability_cache_;
 };
 
 SuggestResult OutputSuggestions(const std::vector<const Target*>& all_targets,
diff --git a/src/gn/header_checker.h b/src/gn/header_checker.h
index 0fee4b6..17e2afc 100644
--- a/src/gn/header_checker.h
+++ b/src/gn/header_checker.h
@@ -67,6 +67,141 @@
     SourceFile included_file;
   };
 
+  // Store the shortest-dependency-path information for all BFS walks starting
+  // from a given `search_from` target.
+  //
+  // `permitted_breadcrumbs` corresponds to public dependencies only.
+  // `any_breadcrumbs` corresponds to all dependencies.
+  //
+  // Each walk type needs only to be performed once, which is recorded by the
+  // corresponding completion flag.
+  class ReachabilityCache {
+   public:
+    ReachabilityCache(const Target* source) : source_target_(source) {}
+    ReachabilityCache(const ReachabilityCache&) = delete;
+    ReachabilityCache& operator=(const ReachabilityCache&) = delete;
+
+    const Target* source_target() const { return source_target_; }
+
+    // Returns true if the given `search_for` target is reachable from
+    // `source_target_`.
+    //
+    // If found, the vector given in `chain` will be filled with the reverse
+    // dependency chain from the destination target to the source target.
+    //
+    // If `permitted` is true, only permitted (public) dependency paths are
+    // searched.
+    bool SearchForDependencyTo(const Target* search_for,
+                               bool permitted,
+                               Chain* chain);
+
+    // Conducts a breadth-first search through the dependency graph to find a
+    // shortest chain from source_target_.
+    void PerformDependencyWalk(bool permitted);
+
+   private:
+    // Header checking structures ----------------------------------------------
+
+    // Data for BreadcrumbNode.
+    //
+    // This class is a trivial type so it can be used in HashTableBase.
+    // To implement IsDependencyOf(from_target, to_target), a BFS starting from
+    // an arbitrary `from_target` is performed, and a BreadCrumbTable is used to
+    // record during the walk, that a given `|target|` is a dependency of
+    // `|src_target|`, with `|is_public|` indicating the type of dependency.
+    //
+    // This table only records the first (src_target->target) dependency during
+    // the BFS, since only the shortest dependency path is interesting. This
+    // also means that if a target is the dependency of two distinct parents at
+    // the same level, only the first parent will be recorded in the table.
+    // Consider the following graph:
+    //
+    // ```
+    //     A
+    //    / \
+    //   B   C
+    //    \ /
+    //     D
+    // ```
+    //
+    // The BFS will visit nodes in order: A, B, C and D, but will record only
+    // the (D, B) edge, not the (D, C) one, even if B->D is private and C->D is
+    // public.
+    //
+    // This information is later used to reconstruct the dependency chain when
+    // `to_target` is found by the walk.
+    struct BreadcrumbNode {
+      const Target* target;
+      const Target* src_target;
+      bool is_public;
+
+      bool is_null() const { return !target; }
+      static bool is_tombstone() { return false; }
+      bool is_valid() const { return !is_null(); }
+      size_t hash_value() const { return std::hash<const Target*>()(target); }
+    };
+
+    struct BreadcrumbTable : public HashTableBase<BreadcrumbNode> {
+      using Base = HashTableBase<BreadcrumbNode>;
+      using Node = Base::Node;
+
+      // Since we only insert, we don't need to return success/failure.
+      // We can also assume that key uniqueness is checked before insertion if
+      // necessary, or that we simply overwrite (though BFS usually checks
+      // existence first).
+      //
+      // In IsDependencyOf, we use the return value checking if it was already
+      // there. So we need an Insert that returns whether it was new.
+      bool Insert(const Target* target,
+                  const Target* src_target,
+                  bool is_public) {
+        size_t hash = std::hash<const Target*>()(target);
+        Node* node = NodeLookup(
+            hash, [target](const Node* n) { return n->target == target; });
+
+        if (node->is_valid())
+          return false;
+
+        node->target = target;
+        node->src_target = src_target;
+        node->is_public = is_public;
+        UpdateAfterInsert(false);
+        return true;
+      }
+
+      // Returns the ChainLink for the given target, or a null-target ChainLink
+      // if not found. The returned link.target, if not nullptr, is a dependent
+      // of the input target that was found during the BFS walk, with dependency
+      // type link.is_public.
+      ChainLink GetLink(const Target* target) const {
+        size_t hash = std::hash<const Target*>()(target);
+        const Node* node = NodeLookup(
+            hash, [target](const Node* n) { return n->target == target; });
+
+        if (node->is_valid())
+          return ChainLink(node->src_target, node->is_public);
+        return ChainLink();
+      }
+    };
+
+    // Reconstructs the shortest dependency chain to the given target if it was
+    // found during a previous walk of the given type. Returns true on success.
+    bool SearchBreadcrumbs(const Target* search_for,
+                           bool permitted,
+                           Chain* chain) const;
+
+    const Target* source_target_;
+
+    mutable std::shared_mutex lock_;
+    // Breadcrumbs for the shortest permitted path.
+    BreadcrumbTable permitted_breadcrumbs_;
+    // Breadcrumbs for the shortest path of any type.
+    BreadcrumbTable any_breadcrumbs_;
+
+    std::atomic<bool> permitted_complete_ = false;
+    std::atomic<bool> any_complete_ = false;
+  };
+
   // check_generated, if true, will also check generated
   // files. Something that can only be done after running a build that
   // has generated them.
@@ -106,141 +241,6 @@
 
   ~HeaderChecker();
 
-  // Header checking structures ------------------------------------------------
-
-  // Data for BreadcrumbNode.
-  //
-  // This class is a trivial type so it can be used in HashTableBase.
-  // To implement IsDependencyOf(from_target, to_target), a BFS starting from an
-  // arbitrary `from_target` is performed, and a BreadCrumbTable is used to
-  // record during the walk, that a given `|target|` is a dependency of
-  // `|src_target|`, with `|is_public|` indicating the type of dependency.
-  //
-  // This table only records the first (src_target->target) dependency during
-  // the BFS, since only the shortest dependency path is interesting. This also
-  // means that if a target is the dependency of two distinct parents at the
-  // same level, only the first parent will be recorded in the table. Consider
-  // the following graph:
-  //
-  // ```
-  //     A
-  //    / \
-  //   B   C
-  //    \ /
-  //     D
-  // ```
-  //
-  // The BFS will visit nodes in order: A, B, C and D, but will record only the
-  // (D, B) edge, not the (D, C) one, even if B->D is private and C->D is
-  // public.
-  //
-  // This information is later used to reconstruct the dependency chain when
-  // `to_target` is found by the walk.
-  struct BreadcrumbNode {
-    const Target* target;
-    const Target* src_target;
-    bool is_public;
-
-    bool is_null() const { return !target; }
-    static bool is_tombstone() { return false; }
-    bool is_valid() const { return !is_null(); }
-    size_t hash_value() const { return std::hash<const Target*>()(target); }
-  };
-
-  struct BreadcrumbTable : public HashTableBase<BreadcrumbNode> {
-    using Base = HashTableBase<BreadcrumbNode>;
-    using Node = Base::Node;
-
-    // Since we only insert, we don't need to return success/failure.
-    // We can also assume that key uniqueness is checked before insertion if
-    // necessary, or that we simply overwrite (though BFS usually checks
-    // existence first).
-    //
-    // In IsDependencyOf, we use the return value checking if it was already
-    // there. So we need an Insert that returns whether it was new.
-    bool Insert(const Target* target,
-                const Target* src_target,
-                bool is_public) {
-      size_t hash = std::hash<const Target*>()(target);
-      Node* node = NodeLookup(
-          hash, [target](const Node* n) { return n->target == target; });
-
-      if (node->is_valid())
-        return false;
-
-      node->target = target;
-      node->src_target = src_target;
-      node->is_public = is_public;
-      UpdateAfterInsert(false);
-      return true;
-    }
-
-    // Returns the ChainLink for the given target, or a null-target ChainLink if
-    // not found. The returned link.target, if not nullptr, is a dependent of
-    // the input target that was found during the BFS walk, with dependency
-    // type link.is_public.
-    ChainLink GetLink(const Target* target) const {
-      size_t hash = std::hash<const Target*>()(target);
-      const Node* node = NodeLookup(
-          hash, [target](const Node* n) { return n->target == target; });
-
-      if (node->is_valid())
-        return ChainLink(node->src_target, node->is_public);
-      return ChainLink();
-    }
-  };
-
-  // Store the shortest-dependency-path information for all BFS walks starting
-  // from a given `search_from` target.
-  //
-  // `permitted_breadcrumbs` corresponds to public dependencies only.
-  // `any_breadcrumbs` corresponds to all dependencies.
-  //
-  // Each walk type needs only to be performed once, which is recorded by the
-  // corresponding completion flag.
-  class ReachabilityCache {
-   public:
-    ReachabilityCache(const Target* source) : source_target_(source) {}
-    ReachabilityCache(const ReachabilityCache&) = delete;
-    ReachabilityCache& operator=(const ReachabilityCache&) = delete;
-
-    // Returns true if the given `search_for` target is reachable from
-    // `source_target_`.
-    //
-    // If found, the vector given in `chain` will be filled with the reverse
-    // dependency chain from the destination target to the source target.
-    //
-    // If `permitted` is true, only permitted (public) dependency paths are
-    // searched.
-    bool SearchForDependencyTo(const Target* search_for,
-                               bool permitted,
-                               Chain* chain);
-
-    // Conducts a breadth-first search through the dependency graph to find a
-    // shortest chain from source_target_.
-    void PerformDependencyWalk(bool permitted);
-
-    const Target* source_target() const { return source_target_; }
-
-   private:
-    // Reconstructs the shortest dependency chain to the given target if it was
-    // found during a previous walk of the given type. Returns true on success.
-    bool SearchBreadcrumbs(const Target* search_for,
-                           bool permitted,
-                           Chain* chain) const;
-
-    const Target* source_target_;
-
-    mutable std::shared_mutex lock_;
-    // Breadcrumbs for the shortest permitted path.
-    BreadcrumbTable permitted_breadcrumbs_;
-    // Breadcrumbs for the shortest path of any type.
-    BreadcrumbTable any_breadcrumbs_;
-
-    std::atomic<bool> permitted_complete_ = false;
-    std::atomic<bool> any_complete_ = false;
-  };
-
   struct TargetInfo {
     TargetInfo() : target(nullptr), is_public(false), is_generated(false) {}
     TargetInfo(const Target* t, bool is_pub, bool is_gen)