diff --git a/tools/gn/header_checker.cc b/tools/gn/header_checker.cc
index 6f0b9d0..8407bd0 100644
--- a/tools/gn/header_checker.cc
+++ b/tools/gn/header_checker.cc
@@ -308,12 +308,15 @@
   CIncludeIterator iter(&input_file);
   base::StringPiece current_include;
   LocationRange range;
+
+  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
   while (iter.GetNextIncludeString(&current_include, &range)) {
     Err err;
     SourceFile include = SourceFileForInclude(current_include, include_dirs,
                                               input_file, range, &err);
     if (!include.is_null())
-      CheckInclude(from_target, input_file, include, range, errors);
+      CheckInclude(from_target, input_file, include, range,
+                   &no_dependency_cache, errors);
   }
 
   return errors->size() == error_count_before;
@@ -325,11 +328,13 @@
 //  - The dependency path to the included target must follow only public_deps.
 //  - If there are multiple targets with the header in it, only one need be
 //    valid for the check to pass.
-void HeaderChecker::CheckInclude(const Target* from_target,
-                                 const InputFile& source_file,
-                                 const SourceFile& include_file,
-                                 const LocationRange& range,
-                                 std::vector<Err>* errors) const {
+void HeaderChecker::CheckInclude(
+    const Target* from_target,
+    const InputFile& source_file,
+    const SourceFile& include_file,
+    const LocationRange& range,
+    std::set<std::pair<const Target*, const Target*>>* no_dependency_cache,
+    std::vector<Err>* errors) const {
   // Assume if the file isn't declared in our sources that we don't need to
   // check it. It would be nice if we could give an error if this happens, but
   // our include finder is too primitive and returns all includes, even if
@@ -388,7 +393,17 @@
       return;
 
     bool is_permitted_chain = false;
-    if (IsDependencyOf(to_target, from_target, &chain, &is_permitted_chain)) {
+
+    bool cached_no_dependency =
+        no_dependency_cache->find(std::make_pair(to_target, from_target)) !=
+        no_dependency_cache->end();
+
+    bool add_to_cache = !cached_no_dependency;
+
+    if (!cached_no_dependency &&
+        IsDependencyOf(to_target, from_target, &chain, &is_permitted_chain)) {
+      add_to_cache = false;
+
       DCHECK(chain.size() >= 2);
       DCHECK(chain[0].target == to_target);
       DCHECK(chain[chain.size() - 1].target == from_target);
@@ -426,6 +441,10 @@
       last_error = Err();
       break;
     }
+
+    if (add_to_cache) {
+      no_dependency_cache->emplace(to_target, from_target);
+    }
   }
 
   if (!found_dependency || last_error.has_error()) {
diff --git a/tools/gn/header_checker.h b/tools/gn/header_checker.h
index 46a47b9..3932001 100644
--- a/tools/gn/header_checker.h
+++ b/tools/gn/header_checker.h
@@ -8,6 +8,7 @@
 #include <condition_variable>
 #include <map>
 #include <mutex>
+#include <set>
 #include <vector>
 
 #include "base/atomic_ref_count.h"
@@ -127,11 +128,15 @@
   // given include file. If disallowed, adds the error or errors to
   // the errors array.  The range indicates the location of the
   // include in the file for error reporting.
-  void CheckInclude(const Target* from_target,
-                    const InputFile& source_file,
-                    const SourceFile& include_file,
-                    const LocationRange& range,
-                    std::vector<Err>* errors) const;
+  // |no_depeency_cache| is used to cache or check whether there is no
+  // dependency from |from_target| to target having |include_file|.
+  void CheckInclude(
+      const Target* from_target,
+      const InputFile& source_file,
+      const SourceFile& include_file,
+      const LocationRange& range,
+      std::set<std::pair<const Target*, const Target*>>* no_dependency_cache,
+      std::vector<Err>* errors) const;
 
   // Returns true if the given search_for target is a dependency of
   // search_from.
diff --git a/tools/gn/header_checker_unittest.cc b/tools/gn/header_checker_unittest.cc
index ab0a6c8..c6529d5 100644
--- a/tools/gn/header_checker_unittest.cc
+++ b/tools/gn/header_checker_unittest.cc
@@ -193,35 +193,46 @@
   scoped_refptr<HeaderChecker> checker(
       new HeaderChecker(setup_.build_settings(), targets_));
 
+  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
   // A file in target A can't include a header from D because A has no
   // dependency on D.
   std::vector<Err> errors;
-  checker->CheckInclude(&a_, input_file, d_header, range, &errors);
+  checker->CheckInclude(&a_, input_file, d_header, range, &no_dependency_cache,
+                        &errors);
   EXPECT_GT(errors.size(), 0);
 
   // A can include the public header in B.
   errors.clear();
-  checker->CheckInclude(&a_, input_file, b_public, range, &errors);
+  no_dependency_cache.clear();
+  checker->CheckInclude(&a_, input_file, b_public, range, &no_dependency_cache,
+                        &errors);
   EXPECT_EQ(errors.size(), 0);
 
   // Check A depending on the public and private headers in C.
   errors.clear();
-  checker->CheckInclude(&a_, input_file, c_public, range, &errors);
+  no_dependency_cache.clear();
+  checker->CheckInclude(&a_, input_file, c_public, range, &no_dependency_cache,
+                        &errors);
   EXPECT_EQ(errors.size(), 0);
   errors.clear();
-  checker->CheckInclude(&a_, input_file, c_private, range, &errors);
+  no_dependency_cache.clear();
+  checker->CheckInclude(&a_, input_file, c_private, range, &no_dependency_cache,
+                        &errors);
   EXPECT_GT(errors.size(), 0);
 
   // A can depend on a random file unknown to the build.
   errors.clear();
-  checker->CheckInclude(&a_, input_file, SourceFile("//random.h"),
-                                    range, &errors);
+  no_dependency_cache.clear();
+  checker->CheckInclude(&a_, input_file, SourceFile("//random.h"), range,
+                        &no_dependency_cache, &errors);
   EXPECT_EQ(errors.size(), 0);
 
   // A can depend on a file present only in another toolchain even with no
   // dependency path.
   errors.clear();
-  checker->CheckInclude(&a_, input_file, otc_header, range, &errors);
+  no_dependency_cache.clear();
+  checker->CheckInclude(&a_, input_file, otc_header, range,
+                        &no_dependency_cache, &errors);
   EXPECT_EQ(errors.size(), 0);
 }
 
@@ -285,7 +296,9 @@
 
   // A depends on B. So B normally can't include headers from A.
   std::vector<Err> errors;
-  checker->CheckInclude(&b_, input_file, a_public, range, &errors);
+  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
+  checker->CheckInclude(&b_, input_file, a_public, range, &no_dependency_cache,
+                        &errors);
   EXPECT_GT(errors.size(), 0);
 
   // Add an allow_circular_includes_from on A that lists B.
@@ -293,7 +306,9 @@
 
   // Now the include from B to A should be allowed.
   errors.clear();
-  checker->CheckInclude(&b_, input_file, a_public, range, &errors);
+  no_dependency_cache.clear();
+  checker->CheckInclude(&b_, input_file, a_public, range, &no_dependency_cache,
+                        &errors);
   EXPECT_EQ(errors.size(), 0);
 }
 
@@ -374,11 +389,15 @@
 
   // B should not be allowed to include C's private header.
   std::vector<Err> errors;
-  checker->CheckInclude(&b_, input_file, c_private, range, &errors);
+  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
+  checker->CheckInclude(&b_, input_file, c_private, range, &no_dependency_cache,
+                        &errors);
   EXPECT_GT(errors.size(), 0);
 
   // A should be able to because of the friend declaration.
   errors.clear();
-  checker->CheckInclude(&a_, input_file, c_private, range, &errors);
+  no_dependency_cache.clear();
+  checker->CheckInclude(&a_, input_file, c_private, range, &no_dependency_cache,
+                        &errors);
   EXPECT_EQ(errors.size(), 0);
 }
diff --git a/tools/gn/substitution_writer.h b/tools/gn/substitution_writer.h
index d5cb1c3..530f064 100644
--- a/tools/gn/substitution_writer.h
+++ b/tools/gn/substitution_writer.h
@@ -6,6 +6,7 @@
 #define TOOLS_GN_SUBSTITUTION_WRITER_H_
 
 #include <iosfwd>
+#include <string>
 #include <vector>
 
 #include "tools/gn/substitution_type.h"