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
@@ -10,6 +10,8 @@
 #include "Compiler.h"
 #include "SourceCode.h"
 #include "support/Logger.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
@@ -21,6 +23,11 @@
 namespace clangd {
 namespace {
 
+bool isMainFile(llvm::StringRef FileName, const SourceManager &SM) {
+  auto FE = SM.getFileManager().getFile(FileName);
+  return FE && *FE == SM.getFileEntryForID(SM.getMainFileID());
+}
+
 class RecordHeaders : public PPCallbacks {
 public:
   RecordHeaders(const SourceManager &SM, IncludeStructure *Out)
@@ -30,11 +37,27 @@
   // in the main file are collected.
   void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
                           llvm::StringRef FileName, bool IsAngled,
-                          CharSourceRange FilenameRange, const FileEntry *File,
-                          llvm::StringRef /*SearchPath*/,
+                          CharSourceRange /*FilenameRange*/,
+                          const FileEntry *File, llvm::StringRef /*SearchPath*/,
                           llvm::StringRef /*RelativePath*/,
                           const Module * /*Imported*/,
                           SrcMgr::CharacteristicKind FileKind) override {
+    auto MainFID = SM.getMainFileID();
+    // If an include is part of the preamble patch, translate #line directives.
+    if (InBuiltinFile) {
+      auto Presumed = SM.getPresumedLoc(HashLoc);
+      // Presumed locations will have an invalid file id when #line directive
+      // changes the filename.
+      if (Presumed.getFileID().isInvalid() &&
+          isMainFile(Presumed.getFilename(), SM)) {
+        // Now we'll hit the case below.
+        HashLoc = SM.translateLineCol(MainFID, Presumed.getLine(),
+                                      Presumed.getColumn());
+      }
+    }
+
+    // Record main-file inclusions (including those mapped from the preamble
+    // patch).
     if (isInsideMainFile(HashLoc, SM)) {
       Out->MainFileIncludes.emplace_back();
       auto &Inc = Out->MainFileIncludes.back();
@@ -47,21 +70,48 @@
       Inc.FileKind = FileKind;
       Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
     }
+
+    // Record include graph (not just for main-file includes)
     if (File) {
       auto *IncludingFileEntry = SM.getFileEntryForID(SM.getFileID(HashLoc));
       if (!IncludingFileEntry) {
         assert(SM.getBufferName(HashLoc).startswith("<") &&
                "Expected #include location to be a file or <built-in>");
         // Treat as if included from the main file.
-        IncludingFileEntry = SM.getFileEntryForID(SM.getMainFileID());
+        IncludingFileEntry = SM.getFileEntryForID(MainFID);
       }
       Out->recordInclude(IncludingFileEntry->getName(), File->getName(),
                          File->tryGetRealPathName());
     }
   }
 
+  void FileChanged(SourceLocation Loc, FileChangeReason Reason,
+                   SrcMgr::CharacteristicKind FileType,
+                   FileID PrevFID) override {
+    switch (Reason) {
+    case PPCallbacks::EnterFile:
+      if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
+        BuiltinFile = SM.getFileID(Loc);
+        InBuiltinFile = true;
+      }
+      break;
+    case PPCallbacks::ExitFile:
+      if (PrevFID == BuiltinFile)
+        InBuiltinFile = false;
+      break;
+    case PPCallbacks::RenameFile:
+    case PPCallbacks::SystemHeaderPragma:
+      break;
+    }
+  }
+
 private:
   const SourceManager &SM;
+  // Set after entering the <built-in> file.
+  FileID BuiltinFile;
+  // Indicates whether <built-in> file is part of include stack.
+  bool InBuiltinFile = false;
+
   IncludeStructure *Out;
 };
 
diff --git a/clang-tools-extra/clangd/unittests/HeadersTests.cpp b/clang-tools-extra/clangd/unittests/HeadersTests.cpp
--- a/clang-tools-extra/clangd/unittests/HeadersTests.cpp
+++ b/clang-tools-extra/clangd/unittests/HeadersTests.cpp
@@ -16,6 +16,7 @@
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Lex/PreprocessorOptions.h"
+#include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
@@ -25,7 +26,9 @@
 namespace {
 
 using ::testing::AllOf;
+using ::testing::Contains;
 using ::testing::ElementsAre;
+using ::testing::Not;
 using ::testing::UnorderedElementsAre;
 
 class HeadersTest : public ::testing::Test {
@@ -302,6 +305,27 @@
             llvm::None);
 }
 
+TEST_F(HeadersTest, PresumedLocations) {
+  std::string HeaderFile = "implicit_include.h";
+
+  // Line map inclusion back to main file.
+  std::string HeaderContents =
+      llvm::formatv("#line 0 \"{0}\"", llvm::sys::path::filename(MainFile));
+  HeaderContents += R"cpp(
+#line 3
+#include <a.h>)cpp";
+  FS.Files[HeaderFile] = HeaderContents;
+
+  // Including through non-builtin file has no effects.
+  FS.Files[MainFile] = "#include \"implicit_include.h\"\n\n";
+  EXPECT_THAT(collectIncludes().MainFileIncludes,
+              Not(Contains(Written("<a.h>"))));
+
+  // Now include through built-in file.
+  CDB.ExtraClangFlags = {"-include", testPath(HeaderFile)};
+  EXPECT_THAT(collectIncludes().MainFileIncludes,
+              Contains(AllOf(IncludeLine(2), Written("<a.h>"))));
+}
 } // namespace
 } // namespace clangd
 } // namespace clang