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
@@ -488,6 +488,8 @@
   /// Determine which HeaderSearchOptions::UserEntries have been successfully
   /// used so far and mark their index with 'true' in the resulting bit vector.
   std::vector<bool> computeUserEntryUsage() const;
+  /// Return the usage of search directories.
+  std::vector<bool> getSearchDirUsage() const { return SearchDirsUsage; }
 
   /// This method returns a HeaderMap for the specified
   /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
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
@@ -124,6 +124,20 @@
   //LookupFileCache.clear();
 }
 
+/// Get a copy of the given map with keys greater or equal to the given
+/// threshold incremented.
+static llvm::DenseMap<unsigned, unsigned>
+incrementKeysGte(const llvm::DenseMap<unsigned, unsigned> &Map,
+                 unsigned Threshold) {
+  llvm::DenseMap<unsigned, unsigned> Result;
+  for (auto Entry : Map) {
+    if (Entry.first >= Threshold)
+      ++Entry.first;
+    Result.insert(Entry);
+  }
+  return Result;
+}
+
 void HeaderSearch::AddSearchPath(const DirectoryLookup &dir, bool isAngled) {
   unsigned idx = isAngled ? SystemDirIdx : AngledDirIdx;
   SearchDirs.insert(SearchDirs.begin() + idx, dir);
@@ -131,6 +145,7 @@
   if (!isAngled)
     AngledDirIdx++;
   SystemDirIdx++;
+  SearchDirToHSEntry = incrementKeysGte(SearchDirToHSEntry, idx);
 }
 
 std::vector<bool> HeaderSearch::computeUserEntryUsage() const {
diff --git a/clang/unittests/Lex/CMakeLists.txt b/clang/unittests/Lex/CMakeLists.txt
--- a/clang/unittests/Lex/CMakeLists.txt
+++ b/clang/unittests/Lex/CMakeLists.txt
@@ -15,6 +15,7 @@
   PRIVATE
   clangAST
   clangBasic
+  clangFrontend
   clangLex
   clangParse
   clangSema
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
@@ -15,6 +15,7 @@
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Basic/TargetOptions.h"
+#include "clang/Frontend/Utils.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/HeaderSearchOptions.h"
 #include "clang/Serialization/InMemoryModuleCache.h"
@@ -24,6 +25,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:
@@ -31,12 +38,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,
@@ -47,6 +52,27 @@
     Search.AddSearchPath(DL, /*isAngled=*/false);
   }
 
+  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) {
@@ -63,6 +89,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;
@@ -224,5 +261,35 @@
   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);
+    std::vector<bool> ExpectedSearchDirUsageAfterM2{false, true, false};
+    EXPECT_EQ(Search.getSearchDirUsage(), ExpectedSearchDirUsageAfterM2);
+    std::vector<bool> ExpectedUserEntryUsageAfterM2{false, true, false};
+    EXPECT_EQ(Search.computeUserEntryUsage(), ExpectedUserEntryUsageAfterM2);
+  }
+
+  addSearchDir("/M1");
+  createModule("M1");
+
+  {
+    Module *M1 = Search.lookupModule("M1");
+    EXPECT_NE(M1, nullptr);
+    std::vector<bool> ExpectedSearchDirUsageAfterM1{false, true, true, false};
+    EXPECT_EQ(Search.getSearchDirUsage(), ExpectedSearchDirUsageAfterM1);
+    std::vector<bool> ExpectedUserEntryUsageAfterM1{false, true, false};
+    EXPECT_EQ(Search.computeUserEntryUsage(), ExpectedUserEntryUsageAfterM1);
+  }
+}
+
 } // namespace
 } // namespace clang