diff --git a/clang/include/clang/Lex/HeaderSearch.h b/clang/include/clang/Lex/HeaderSearch.h
--- a/clang/include/clang/Lex/HeaderSearch.h
+++ b/clang/include/clang/Lex/HeaderSearch.h
@@ -175,48 +175,52 @@
 
   bool operator==(const DirectoryLookupIterator &RHS) const {
     assert(*this && RHS && "Invalid iterators.");
-    return DL == RHS.DL;
+    assert(HS == RHS.HS && "Different HeaderSearch objects.");
+    return Idx == RHS.Idx;
   }
 
   bool operator<(const DirectoryLookupIterator &RHS) const {
     assert(*this && RHS && "Invalid iterators.");
-    return DL < RHS.DL;
+    assert(HS == RHS.HS && "Different HeaderSearch objects.");
+    return Idx < RHS.Idx;
   }
 
   std::ptrdiff_t operator-(const DirectoryLookupIterator &RHS) const {
     assert(*this && RHS && "Invalid iterators.");
-    return DL - RHS.DL;
+    assert(HS == RHS.HS && "Different HeaderSearch objects.");
+    return Idx - RHS.Idx;
   }
 
   DirectoryLookupIterator &operator+=(std::ptrdiff_t N) {
     assert(*this && "Invalid iterator.");
-    DL += N;
+    Idx += N;
     return *this;
   }
 
   DirectoryLookupIterator &operator-=(ptrdiff_t N) {
     assert(*this && "Invalid iterator.");
-    DL -= N;
+    Idx -= N;
     return *this;
   }
 
-  const DirectoryLookup &operator*() const {
-    assert(*this && "Invalid iterator.");
-    return *DL;
-  }
+  const DirectoryLookup &operator*() const;
 
   /// Creates an invalid iterator.
-  DirectoryLookupIterator(std::nullptr_t) : DL(nullptr) {}
+  DirectoryLookupIterator(std::nullptr_t) : HS(nullptr) {}
 
   /// Checks whether the iterator is valid.
-  operator bool() const { return DL != nullptr; }
+  operator bool() const { return HS != nullptr; }
 
 private:
-  /// The current element.
-  const DirectoryLookup *DL;
+  /// The object storing DirectoryLookup elements.
+  const HeaderSearch *HS;
+
+  /// Index of the current element.
+  unsigned Idx;
 
   /// The constructor that creates a valid iterator.
-  explicit DirectoryLookupIterator(const DirectoryLookup *DL) : DL(DL) {}
+  explicit DirectoryLookupIterator(const HeaderSearch *HS, unsigned Idx)
+      : HS(HS), Idx(Idx) {}
 
   /// Only HeaderSearch is allowed to instantiate valid references.
   friend HeaderSearch;
@@ -226,26 +230,28 @@
 /// by a \#include or \#include_next, (sub-)framework lookup, etc.
 class HeaderSearch {
   friend class DirectoryLookup;
+  friend DirectoryLookupIterator;
 
   /// Header-search options used to initialize this header search.
   std::shared_ptr<HeaderSearchOptions> HSOpts;
 
-  /// Mapping from SearchDir to HeaderSearchOptions::UserEntries indices.
-  llvm::DenseMap<unsigned, unsigned> SearchDirToHSEntry;
-
   DiagnosticsEngine &Diags;
   FileManager &FileMgr;
 
+  /// The allocator owning search directories.
+  llvm::SpecificBumpPtrAllocator<DirectoryLookup> SearchDirsAlloc;
   /// \#include search path information.  Requests for \#include "x" search the
   /// directory of the \#including file first, then each directory in SearchDirs
   /// consecutively. Requests for <x> search the current dir first, then each
   /// directory in SearchDirs, starting at AngledDirIdx, consecutively.  If
   /// NoCurDirSearch is true, then the check for the file in the current
   /// directory is suppressed.
-  std::vector<DirectoryLookup> SearchDirs;
-  /// Whether the DirectoryLookup at the corresponding index in SearchDirs has
-  /// been successfully used to lookup a file.
-  std::vector<bool> SearchDirsUsage;
+  std::vector<DirectoryLookup *> SearchDirs;
+  /// Set of SearchDirs that have been successfully used to lookup a file.
+  llvm::DenseSet<const DirectoryLookup *> UsedSearchDirs;
+  /// Mapping from SearchDir to HeaderSearchOptions::UserEntries indices.
+  llvm::DenseMap<const DirectoryLookup *, unsigned> SearchDirToHSEntry;
+
   unsigned AngledDirIdx = 0;
   unsigned SystemDirIdx = 0;
   bool NoCurDirSearch = false;
@@ -353,8 +359,7 @@
 
   /// Add an additional system search path.
   void AddSystemSearchPath(const DirectoryLookup &dir) {
-    SearchDirs.push_back(dir);
-    SearchDirsUsage.push_back(false);
+    SearchDirs.push_back(storeSearchDir(dir));
   }
 
   /// Set the list of system header prefixes.
@@ -558,7 +563,11 @@
 
   /// Determine which HeaderSearchOptions::UserEntries have been successfully
   /// used so far and mark their index with 'true' in the resulting bit vector.
+  // TODO: Use llvm::BitVector instead.
   std::vector<bool> computeUserEntryUsage() const;
+  /// Return a bit vector of length \c SearchDirs.size() that indicates for each
+  /// search directory whether it was used.
+  std::vector<bool> getSearchDirUsage() const;
 
   /// This method returns a HeaderMap for the specified
   /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
@@ -688,6 +697,11 @@
   void loadTopLevelSystemModules();
 
 private:
+  /// Stores the given search directory and returns a stable pointer.
+  DirectoryLookup *storeSearchDir(const DirectoryLookup &Dir) {
+    return new (SearchDirsAlloc.Allocate()) DirectoryLookup(Dir);
+  }
+
   /// Lookup a module with the given module name and search-name.
   ///
   /// \param ModuleName The name of the module we're looking for.
@@ -774,8 +788,9 @@
   void cacheLookupSuccess(LookupFileCacheInfo &CacheLookup, unsigned HitIdx,
                           SourceLocation IncludeLoc);
   /// Note that a lookup at the given include location was successful using the
-  /// search path at index `HitIdx`.
-  void noteLookupUsage(unsigned HitIdx, SourceLocation IncludeLoc);
+  /// given search path.
+  void noteLookupUsage(const DirectoryLookup *SearchDir,
+                       SourceLocation IncludeLoc);
 
 public:
   /// Retrieve the module map.
@@ -798,7 +813,8 @@
                                             bool WantExternal = true) const;
 
   // Used by external tools
-  using search_dir_iterator = std::vector<DirectoryLookup>::const_iterator;
+  using search_dir_iterator =
+      llvm::pointee_iterator<decltype(SearchDirs)::const_iterator>;
 
   search_dir_iterator search_dir_begin() const { return SearchDirs.begin(); }
   search_dir_iterator search_dir_end() const { return SearchDirs.end(); }
@@ -826,9 +842,6 @@
 
   search_dir_iterator system_dir_end() const { return SearchDirs.end(); }
 
-  /// Get the index of the given search directory.
-  Optional<unsigned> searchDirIdx(const DirectoryLookup &DL) const;
-
   /// Retrieve a uniqued framework name.
   StringRef getUniqueFrameworkName(StringRef Framework);
 
diff --git a/clang/lib/Lex/HeaderSearch.cpp b/clang/lib/Lex/HeaderSearch.cpp
--- a/clang/lib/Lex/HeaderSearch.cpp
+++ b/clang/lib/Lex/HeaderSearch.cpp
@@ -79,6 +79,10 @@
 
 ExternalHeaderFileInfoSource::~ExternalHeaderFileInfoSource() = default;
 
+const DirectoryLookup &DirectoryLookupIterator::operator*() const {
+  return *HS->SearchDirs[Idx];
+}
+
 HeaderSearch::HeaderSearch(std::shared_ptr<HeaderSearchOptions> HSOpts,
                            SourceManager &SourceMgr, DiagnosticsEngine &Diags,
                            const LangOptions &LangOpts,
@@ -115,19 +119,24 @@
     llvm::DenseMap<unsigned int, unsigned int> searchDirToHSEntry) {
   assert(angledDirIdx <= systemDirIdx && systemDirIdx <= dirs.size() &&
          "Directory indices are unordered");
-  SearchDirs = std::move(dirs);
-  SearchDirsUsage.assign(SearchDirs.size(), false);
+  SearchDirsAlloc.DestroyAll();
+  SearchDirs.clear();
+  for (const DirectoryLookup &Dir : dirs)
+    SearchDirs.push_back(storeSearchDir(Dir));
+  UsedSearchDirs.clear();
+  SearchDirToHSEntry.clear();
+  for (const auto &Entry : searchDirToHSEntry)
+    SearchDirToHSEntry.insert({SearchDirs[Entry.first], Entry.second});
+
   AngledDirIdx = angledDirIdx;
   SystemDirIdx = systemDirIdx;
   NoCurDirSearch = noCurDirSearch;
-  SearchDirToHSEntry = std::move(searchDirToHSEntry);
   //LookupFileCache.clear();
 }
 
 void HeaderSearch::AddSearchPath(const DirectoryLookup &dir, bool isAngled) {
   unsigned idx = isAngled ? SystemDirIdx : AngledDirIdx;
-  SearchDirs.insert(SearchDirs.begin() + idx, dir);
-  SearchDirsUsage.insert(SearchDirsUsage.begin() + idx, false);
+  SearchDirs.insert(SearchDirs.begin() + idx, storeSearchDir(dir));
   if (!isAngled)
     AngledDirIdx++;
   SystemDirIdx++;
@@ -135,10 +144,9 @@
 
 std::vector<bool> HeaderSearch::computeUserEntryUsage() const {
   std::vector<bool> UserEntryUsage(HSOpts->UserEntries.size());
-  for (unsigned I = 0, E = SearchDirsUsage.size(); I < E; ++I) {
-    // Check whether this DirectoryLookup has been successfully used.
-    if (SearchDirsUsage[I]) {
-      auto UserEntryIdxIt = SearchDirToHSEntry.find(I);
+  for (const DirectoryLookup *SearchDir : UsedSearchDirs) {
+    if (UsedSearchDirs.contains(SearchDir)) {
+      auto UserEntryIdxIt = SearchDirToHSEntry.find(SearchDir);
       // Check whether this DirectoryLookup maps to a HeaderSearch::UserEntry.
       if (UserEntryIdxIt != SearchDirToHSEntry.end())
         UserEntryUsage[UserEntryIdxIt->second] = true;
@@ -147,6 +155,14 @@
   return UserEntryUsage;
 }
 
+std::vector<bool> HeaderSearch::getSearchDirUsage() const {
+  std::vector<bool> SearchDirUsage(SearchDirs.size());
+  for (unsigned I = 0, E = SearchDirs.size(); I < E; ++I)
+    if (UsedSearchDirs.contains(SearchDirs[I]))
+      SearchDirUsage[I] = true;
+  return SearchDirUsage;
+}
+
 /// CreateHeaderMap - This method returns a HeaderMap for the specified
 /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
 const HeaderMap *HeaderSearch::CreateHeaderMap(const FileEntry *FE) {
@@ -301,21 +317,23 @@
                                    SourceLocation ImportLoc,
                                    bool AllowExtraModuleMapSearch) {
   Module *Module = nullptr;
-  unsigned Idx;
+  DirectoryLookup *SearchDir = nullptr;
 
   // Look through the various header search paths to load any available module
   // maps, searching for a module map that describes this module.
-  for (Idx = 0; Idx != SearchDirs.size(); ++Idx) {
-    if (SearchDirs[Idx].isFramework()) {
+  for (unsigned Idx = 0; Idx != SearchDirs.size(); ++Idx) {
+    SearchDir = SearchDirs[Idx];
+
+    if (SearchDirs[Idx]->isFramework()) {
       // Search for or infer a module map for a framework. Here we use
       // SearchName rather than ModuleName, to permit finding private modules
       // named FooPrivate in buggy frameworks named Foo.
       SmallString<128> FrameworkDirName;
-      FrameworkDirName += SearchDirs[Idx].getFrameworkDir()->getName();
+      FrameworkDirName += SearchDirs[Idx]->getFrameworkDir()->getName();
       llvm::sys::path::append(FrameworkDirName, SearchName + ".framework");
       if (auto FrameworkDir = FileMgr.getDirectory(FrameworkDirName)) {
         bool IsSystem
-          = SearchDirs[Idx].getDirCharacteristic() != SrcMgr::C_User;
+          = SearchDirs[Idx]->getDirCharacteristic() != SrcMgr::C_User;
         Module = loadFrameworkModule(ModuleName, *FrameworkDir, IsSystem);
         if (Module)
           break;
@@ -325,12 +343,12 @@
     // FIXME: Figure out how header maps and module maps will work together.
 
     // Only deal with normal search directories.
-    if (!SearchDirs[Idx].isNormalDir())
+    if (!SearchDirs[Idx]->isNormalDir())
       continue;
 
-    bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
+    bool IsSystem = SearchDirs[Idx]->isSystemHeaderDirectory();
     // Search for a module map file in this directory.
-    if (loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
+    if (loadModuleMapFile(SearchDirs[Idx]->getDir(), IsSystem,
                           /*IsFramework*/false) == LMM_NewlyLoaded) {
       // We just loaded a module map file; check whether the module is
       // available now.
@@ -342,7 +360,7 @@
     // Search for a module map in a subdirectory with the same name as the
     // module.
     SmallString<128> NestedModuleMapDirName;
-    NestedModuleMapDirName = SearchDirs[Idx].getDir()->getName();
+    NestedModuleMapDirName = SearchDirs[Idx]->getDir()->getName();
     llvm::sys::path::append(NestedModuleMapDirName, ModuleName);
     if (loadModuleMapFile(NestedModuleMapDirName, IsSystem,
                           /*IsFramework*/false) == LMM_NewlyLoaded){
@@ -354,13 +372,13 @@
 
     // If we've already performed the exhaustive search for module maps in this
     // search directory, don't do it again.
-    if (SearchDirs[Idx].haveSearchedAllModuleMaps())
+    if (SearchDirs[Idx]->haveSearchedAllModuleMaps())
       continue;
 
     // Load all module maps in the immediate subdirectories of this search
     // directory if ModuleName was from @import.
     if (AllowExtraModuleMapSearch)
-      loadSubdirectoryModuleMaps(SearchDirs[Idx]);
+      loadSubdirectoryModuleMaps(*SearchDirs[Idx]);
 
     // Look again for the module.
     Module = ModMap.findModule(ModuleName);
@@ -369,7 +387,7 @@
   }
 
   if (Module)
-    noteLookupUsage(Idx, ImportLoc);
+    noteLookupUsage(SearchDir, ImportLoc);
 
   return Module;
 }
@@ -495,7 +513,7 @@
   // The case where the target file **exists** is handled by callee of this
   // function as part of the regular logic that applies to include search paths.
   // The case where the target file **does not exist** is handled here:
-  HS.noteLookupUsage(*HS.searchDirIdx(*this), IncludeLoc);
+  HS.noteLookupUsage(this, IncludeLoc);
   return None;
 }
 
@@ -703,13 +721,14 @@
 void HeaderSearch::cacheLookupSuccess(LookupFileCacheInfo &CacheLookup,
                                       unsigned HitIdx, SourceLocation Loc) {
   CacheLookup.HitIdx = HitIdx;
-  noteLookupUsage(HitIdx, Loc);
+  noteLookupUsage(SearchDirs[HitIdx], Loc);
 }
 
-void HeaderSearch::noteLookupUsage(unsigned HitIdx, SourceLocation Loc) {
-  SearchDirsUsage[HitIdx] = true;
+void HeaderSearch::noteLookupUsage(const DirectoryLookup *SearchDir,
+                                   SourceLocation Loc) {
+  UsedSearchDirs.insert(SearchDir);
 
-  auto UserEntryIdxIt = SearchDirToHSEntry.find(HitIdx);
+  auto UserEntryIdxIt = SearchDirToHSEntry.find(SearchDir);
   if (UserEntryIdxIt != SearchDirToHSEntry.end())
     Diags.Report(Loc, diag::remark_pp_search_path_usage)
         << HSOpts->UserEntries[UserEntryIdxIt->second].Path;
@@ -966,7 +985,7 @@
   // If this is a #include_next request, start searching after the directory the
   // file was found in.
   if (FromDir)
-    i = FromDir - DirectoryLookupIterator(&SearchDirs[0]);
+    i = FromDir - DirectoryLookupIterator(this, 0);
 
   // Cache all of the lookups performed by this method.  Many headers are
   // multiply included, and the "pragma once" optimization prevents them from
@@ -999,7 +1018,7 @@
     bool InUserSpecifiedSystemFramework = false;
     bool IsInHeaderMap = false;
     bool IsFrameworkFoundInDir = false;
-    Optional<FileEntryRef> File = SearchDirs[i].LookupFile(
+    Optional<FileEntryRef> File = SearchDirs[i]->LookupFile(
         Filename, *this, IncludeLoc, SearchPath, RelativePath, RequestingModule,
         SuggestedModule, InUserSpecifiedSystemFramework, IsFrameworkFoundInDir,
         IsInHeaderMap, MappedName);
@@ -1021,7 +1040,7 @@
     if (!File)
       continue;
 
-    CurDir = DirectoryLookupIterator(&SearchDirs[i]);
+    CurDir = DirectoryLookupIterator(this, i);
 
     // This file is a system header or C++ unfriendly if the dir is.
     HeaderFileInfo &HFI = getFileInfo(&File->getFileEntry());
@@ -1443,13 +1462,6 @@
     + FrameworkMap.getAllocator().getTotalMemory();
 }
 
-Optional<unsigned> HeaderSearch::searchDirIdx(const DirectoryLookup &DL) const {
-  for (unsigned I = 0; I < SearchDirs.size(); ++I)
-    if (&SearchDirs[I] == &DL)
-      return I;
-  return None;
-}
-
 StringRef HeaderSearch::getUniqueFrameworkName(StringRef Framework) {
   return FrameworkNames.insert(Framework).first->first();
 }
@@ -1777,11 +1789,11 @@
   if (HSOpts->ImplicitModuleMaps) {
     // Load module maps for each of the header search directories.
     for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
-      bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
-      if (SearchDirs[Idx].isFramework()) {
+      bool IsSystem = SearchDirs[Idx]->isSystemHeaderDirectory();
+      if (SearchDirs[Idx]->isFramework()) {
         std::error_code EC;
         SmallString<128> DirNative;
-        llvm::sys::path::native(SearchDirs[Idx].getFrameworkDir()->getName(),
+        llvm::sys::path::native(SearchDirs[Idx]->getFrameworkDir()->getName(),
                                 DirNative);
 
         // Search each of the ".framework" directories to load them as modules.
@@ -1805,16 +1817,16 @@
       }
 
       // FIXME: Deal with header maps.
-      if (SearchDirs[Idx].isHeaderMap())
+      if (SearchDirs[Idx]->isHeaderMap())
         continue;
 
       // Try to load a module map file for the search directory.
-      loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
+      loadModuleMapFile(SearchDirs[Idx]->getDir(), IsSystem,
                         /*IsFramework*/ false);
 
       // Try to load module map files for immediate subdirectories of this
       // search directory.
-      loadSubdirectoryModuleMaps(SearchDirs[Idx]);
+      loadSubdirectoryModuleMaps(*SearchDirs[Idx]);
     }
   }
 
@@ -1830,14 +1842,13 @@
   // Load module maps for each of the header search directories.
   for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
     // We only care about normal header directories.
-    if (!SearchDirs[Idx].isNormalDir()) {
+    if (!SearchDirs[Idx]->isNormalDir())
       continue;
-    }
 
     // Try to load a module map file for the search directory.
-    loadModuleMapFile(SearchDirs[Idx].getDir(),
-                      SearchDirs[Idx].isSystemHeaderDirectory(),
-                      SearchDirs[Idx].isFramework());
+    loadModuleMapFile(SearchDirs[Idx]->getDir(),
+                      SearchDirs[Idx]->isSystemHeaderDirectory(),
+                      SearchDirs[Idx]->isFramework());
   }
 }
 
@@ -1935,15 +1946,15 @@
 
   bool BestPrefixIsFramework = false;
   for (unsigned I = 0; I != SearchDirs.size(); ++I) {
-    if (SearchDirs[I].isNormalDir()) {
-      StringRef Dir = SearchDirs[I].getDir()->getName();
+    if (SearchDirs[I]->isNormalDir()) {
+      StringRef Dir = SearchDirs[I]->getDir()->getName();
       if (CheckDir(Dir)) {
         if (IsSystem)
           *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
         BestPrefixIsFramework = false;
       }
-    } else if (SearchDirs[I].isFramework()) {
-      StringRef Dir = SearchDirs[I].getFrameworkDir()->getName();
+    } else if (SearchDirs[I]->isFramework()) {
+      StringRef Dir = SearchDirs[I]->getFrameworkDir()->getName();
       if (CheckDir(Dir)) {
         if (IsSystem)
           *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
@@ -1964,11 +1975,11 @@
   // key from header name is user prefered name for the include file.
   StringRef Filename = File.drop_front(BestPrefixLength);
   for (unsigned I = 0; I != SearchDirs.size(); ++I) {
-    if (!SearchDirs[I].isHeaderMap())
+    if (!SearchDirs[I]->isHeaderMap())
       continue;
 
     StringRef SpelledFilename =
-        SearchDirs[I].getHeaderMap()->reverseLookupFilename(Filename);
+        SearchDirs[I]->getHeaderMap()->reverseLookupFilename(Filename);
     if (!SpelledFilename.empty()) {
       Filename = SpelledFilename;
       BestPrefixIsFramework = false;
diff --git a/clang/unittests/Lex/HeaderSearchTest.cpp b/clang/unittests/Lex/HeaderSearchTest.cpp
--- a/clang/unittests/Lex/HeaderSearchTest.cpp
+++ b/clang/unittests/Lex/HeaderSearchTest.cpp
@@ -23,6 +23,12 @@
 namespace clang {
 namespace {
 
+static std::shared_ptr<TargetOptions> createTargetOptions() {
+  auto TargetOpts = std::make_shared<TargetOptions>();
+  TargetOpts->Triple = "x86_64-apple-darwin11.1.0";
+  return TargetOpts;
+}
+
 // The test fixture.
 class HeaderSearchTest : public ::testing::Test {
 protected:
@@ -30,12 +36,10 @@
       : VFS(new llvm::vfs::InMemoryFileSystem), FileMgr(FileMgrOpts, VFS),
         DiagID(new DiagnosticIDs()),
         Diags(DiagID, new DiagnosticOptions, new IgnoringDiagConsumer()),
-        SourceMgr(Diags, FileMgr), TargetOpts(new TargetOptions),
+        SourceMgr(Diags, FileMgr), TargetOpts(createTargetOptions()),
+        Target(TargetInfo::CreateTargetInfo(Diags, TargetOpts)),
         Search(std::make_shared<HeaderSearchOptions>(), SourceMgr, Diags,
-               LangOpts, Target.get()) {
-    TargetOpts->Triple = "x86_64-apple-darwin11.1.0";
-    Target = TargetInfo::CreateTargetInfo(Diags, TargetOpts);
-  }
+               LangOpts, Target.get()) {}
 
   void addSearchDir(llvm::StringRef Dir) {
     VFS->addFile(Dir, 0, llvm::MemoryBuffer::getMemBuffer(""), /*User=*/None,
@@ -55,6 +59,27 @@
     Search.AddSystemSearchPath(DL);
   }
 
+  void setSearchDirs(llvm::ArrayRef<llvm::StringRef> QuotedDirs,
+                     llvm::ArrayRef<llvm::StringRef> AngledDirs) {
+    auto AddPath = [&](StringRef Dir, bool IsAngled) {
+      VFS->addFile(Dir, 0, llvm::MemoryBuffer::getMemBuffer(""), /*User=*/None,
+                   /*Group=*/None, llvm::sys::fs::file_type::directory_file);
+      auto Group = IsAngled ? frontend::IncludeDirGroup::Angled
+                            : frontend::IncludeDirGroup::Quoted;
+      Search.getHeaderSearchOpts().AddPath(Dir, Group,
+                                           /*IsFramework=*/false,
+                                           /*IgnoreSysRoot=*/true);
+    };
+
+    for (llvm::StringRef Dir : QuotedDirs)
+      AddPath(Dir, /*IsAngled=*/false);
+    for (llvm::StringRef Dir : AngledDirs)
+      AddPath(Dir, /*IsAngled=*/true);
+
+    clang::ApplyHeaderSearchOptions(Search, Search.getHeaderSearchOpts(),
+                                    LangOpts, Target->getTriple());
+  }
+
   void addHeaderMap(llvm::StringRef Filename,
                     std::unique_ptr<llvm::MemoryBuffer> Buf,
                     bool isAngled = false) {
@@ -71,6 +96,17 @@
     Search.AddSearchPath(DL, isAngled);
   }
 
+  void createModule(StringRef Mod) {
+    std::string ModDir = ("/" + Mod).str();
+    std::string ModHeader = (Mod + ".h").str();
+    VFS->addFile(
+        ModDir + "/module.modulemap", 0,
+        llvm::MemoryBuffer::getMemBufferCopy(
+            ("module " + Mod + " { header \"" + ModHeader + "\" }").str()));
+    VFS->addFile(ModDir + "/" + ModHeader, 0,
+                 llvm::MemoryBuffer::getMemBuffer(""));
+  }
+
   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> VFS;
   FileSystemOptions FileMgrOpts;
   FileManager FileMgr;
@@ -254,5 +290,31 @@
   EXPECT_EQ(FI->Framework.str(), "Foo");
 }
 
+TEST_F(HeaderSearchTest, SearchPathUsage) {
+  Search.getHeaderSearchOpts().ImplicitModuleMaps = true;
+
+  setSearchDirs(/*QuotedDirs=*/{"/M0"}, /*AngledDirs=*/{"/M2", "/M3"});
+  createModule("M0");
+  createModule("M2");
+  createModule("M3");
+
+  {
+    Module *M2 = Search.lookupModule("M2");
+    EXPECT_NE(M2, nullptr);
+    EXPECT_EQ(Search.getSearchDirUsage(), (std::vector<bool>{0, 1, 0}));
+    EXPECT_EQ(Search.computeUserEntryUsage(), (std::vector<bool>{0, 1, 0}));
+  }
+
+  addSearchDir("/M1");
+  createModule("M1");
+
+  {
+    Module *M1 = Search.lookupModule("M1");
+    EXPECT_NE(M1, nullptr);
+    EXPECT_EQ(Search.getSearchDirUsage(), (std::vector<bool>{0, 1, 1, 0}));
+    EXPECT_EQ(Search.computeUserEntryUsage(), (std::vector<bool>{0, 1, 0}));
+  }
+}
+
 } // namespace
 } // namespace clang