diff --git a/clang-tools-extra/clangd/Headers.h b/clang-tools-extra/clangd/Headers.h
--- a/clang-tools-extra/clangd/Headers.h
+++ b/clang-tools-extra/clangd/Headers.h
@@ -23,6 +23,8 @@
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
@@ -155,13 +157,16 @@
     return !NonSelfContained.contains(ID);
   }
 
-  bool hasIWYUExport(HeaderID ID) const {
-    return HasIWYUExport.contains(ID);
-  }
+  bool hasIWYUExport(HeaderID ID) const { return HasIWYUExport.contains(ID); }
 
   // Return all transitively reachable files.
   llvm::ArrayRef<std::string> allHeaders() const { return RealPathNames; }
 
+  llvm::SmallVector<HeaderID>
+  lookupHeaderIDsBySpelling(llvm::StringRef Spelling) const {
+    return MainFileIncludesBySpelling.lookup(Spelling);
+  }
+
   // Return all transitively reachable files, and their minimum include depth.
   // All transitive includes (absolute paths), with their minimum include depth.
   // Root --> 0, #included file --> 1, etc.
@@ -202,6 +207,10 @@
   // Contains a set of headers that have either "IWYU pragma: export" or "IWYU
   // pragma: begin_exports".
   llvm::DenseSet<HeaderID> HasIWYUExport;
+
+  // Maps written includes to headers IDs for easier lookup by spelling.
+  llvm::StringMap<llvm::SmallVector<IncludeStructure::HeaderID>>
+      MainFileIncludesBySpelling;
 };
 
 // Calculates insertion edit for including a new header in a file.
diff --git a/clang-tools-extra/clangd/Headers.cpp b/clang-tools-extra/clangd/Headers.cpp
--- a/clang-tools-extra/clangd/Headers.cpp
+++ b/clang-tools-extra/clangd/Headers.cpp
@@ -72,6 +72,8 @@
             if (!llvm::is_contained(IDs, HID))
               IDs.push_back(HID);
           }
+        Out->MainFileIncludesBySpelling.try_emplace(Inc.Written)
+            .first->second.push_back(static_cast<HeaderID>(*Inc.HeaderID));
       }
     }
 
diff --git a/clang-tools-extra/clangd/IncludeCleaner.cpp b/clang-tools-extra/clangd/IncludeCleaner.cpp
--- a/clang-tools-extra/clangd/IncludeCleaner.cpp
+++ b/clang-tools-extra/clangd/IncludeCleaner.cpp
@@ -85,7 +85,7 @@
     // Using templateName case is handled by the override TraverseTemplateName.
     if (TST->getTemplateName().getKind() == TemplateName::UsingTemplate)
       return true;
-    add(TST->getAsCXXRecordDecl());                  // Specialization
+    add(TST->getAsCXXRecordDecl()); // Specialization
     return true;
   }
 
@@ -474,22 +474,16 @@
       translateToHeaderIDs(ReferencedFiles, AST.getIncludeStructure(), SM);
   return getUnused(AST, ReferencedHeaders, ReferencedFiles.SpelledUmbrellas);
 }
-std::vector<const Inclusion *> computeUnusedIncludesExperimental(ParsedAST &AST) {
-   const auto &SM = AST.getSourceManager();
-   const auto &Includes = AST.getIncludeStructure();
-   // FIXME: this map should probably be in IncludeStructure.
-   llvm::StringMap<llvm::SmallVector<IncludeStructure::HeaderID>> BySpelling;
-   for (const auto &Inc : Includes.MainFileIncludes) {
-    if (Inc.HeaderID)
-      BySpelling.try_emplace(Inc.Written)
-          .first->second.push_back(
-              static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID));
-   }
-   // FIXME: !!this is a hacky way to collect macro references.
-   std::vector<include_cleaner::SymbolReference> Macros;
-    auto& PP = AST.getPreprocessor();
-   for (const syntax::Token &Tok :
-        AST.getTokens().spelledTokens(SM.getMainFileID())) {
+std::vector<const Inclusion *>
+computeUnusedIncludesExperimental(ParsedAST &AST) {
+  const auto &SM = AST.getSourceManager();
+  const auto &Includes = AST.getIncludeStructure();
+
+  // FIXME: !!this is a hacky way to collect macro references.
+  std::vector<include_cleaner::SymbolReference> Macros;
+  auto &PP = AST.getPreprocessor();
+  for (const syntax::Token &Tok :
+       AST.getTokens().spelledTokens(SM.getMainFileID())) {
     auto Macro = locateMacroAt(Tok, PP);
     if (!Macro)
       continue;
@@ -499,31 +493,32 @@
            include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok.text(SM)),
                                   DefLoc},
            include_cleaner::RefType::Explicit});
-   }
-   llvm::DenseSet<IncludeStructure::HeaderID> Used;
-   include_cleaner::walkUsed(
-       AST.getLocalTopLevelDecls(), /*MacroRefs=*/Macros,
-       AST.getPragmaIncludes(), SM,
-       [&](const include_cleaner::SymbolReference &Ref,
-           llvm::ArrayRef<include_cleaner::Header> Providers) {
-         for (const auto &H : Providers) {
-           switch (H.kind()) {
-           case include_cleaner::Header::Physical:
-             if (auto HeaderID = Includes.getID(H.physical()))
-               Used.insert(*HeaderID);
-             break;
-           case include_cleaner::Header::Standard:
-             for (auto HeaderID : Includes.StdlibHeaders.lookup(H.standard()))
-               Used.insert(HeaderID);
-             break;
-           case include_cleaner::Header::Verbatim:
-             for (auto HeaderID : BySpelling.lookup(H.verbatim()))
-               Used.insert(HeaderID);
-             break;
-           }
-         }
-       });
-   return getUnused(AST, Used, /*ReferencedPublicHeaders*/{});
+  }
+  llvm::DenseSet<IncludeStructure::HeaderID> Used;
+  include_cleaner::walkUsed(
+      AST.getLocalTopLevelDecls(), /*MacroRefs=*/Macros,
+      AST.getPragmaIncludes(), SM,
+      [&](const include_cleaner::SymbolReference &Ref,
+          llvm::ArrayRef<include_cleaner::Header> Providers) {
+        for (const auto &H : Providers) {
+          switch (H.kind()) {
+          case include_cleaner::Header::Physical:
+            if (auto HeaderID = Includes.getID(H.physical()))
+              Used.insert(*HeaderID);
+            break;
+          case include_cleaner::Header::Standard:
+            for (auto HeaderID : Includes.StdlibHeaders.lookup(H.standard()))
+              Used.insert(HeaderID);
+            break;
+          case include_cleaner::Header::Verbatim:
+            for (auto HeaderID :
+                 Includes.lookupHeaderIDsBySpelling(H.verbatim()))
+              Used.insert(HeaderID);
+            break;
+          }
+        }
+      });
+  return getUnused(AST, Used, /*ReferencedPublicHeaders*/ {});
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,