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
@@ -163,6 +163,48 @@
   bool IsUserSpecifiedSystemFramework;
 };
 
+/// Index of a search directory.
+class SearchDirIdx {
+  /// The underlying index.
+  size_t Idx;
+
+  friend HeaderSearch;
+
+public:
+  explicit SearchDirIdx(size_t Idx) : Idx(Idx) {}
+
+  bool operator==(const SearchDirIdx &Other) const { return Idx == Other.Idx; }
+
+  llvm::hash_code hash_value() const { return Idx; }
+
+  void increment() { ++Idx; }
+
+  /// Get search directory stored at the index.
+  const DirectoryLookup &get(const HeaderSearch &HS) const;
+  /// Get search directory stored at the index.
+  DirectoryLookup &get(HeaderSearch &HS) const;
+};
+} // namespace clang
+
+namespace llvm {
+template <> struct DenseMapInfo<clang::SearchDirIdx> {
+  static inline clang::SearchDirIdx getEmptyKey() {
+    return clang::SearchDirIdx(-1);
+  }
+  static inline clang::SearchDirIdx getTombstoneKey() {
+    return clang::SearchDirIdx(-2);
+  }
+  static unsigned getHashValue(const clang::SearchDirIdx &Val) {
+    return Val.hash_value();
+  }
+  static bool isEqual(const clang::SearchDirIdx &LHS,
+                      const clang::SearchDirIdx &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
+namespace clang {
 namespace detail {
 template <bool Const, typename T>
 using Qualified = std::conditional_t<Const, const T, T>;
@@ -189,13 +231,13 @@
 
   SearchDirIteratorImpl &operator++() {
     assert(*this && "Invalid iterator.");
-    ++Idx;
+    Idx.increment();
     return *this;
   }
 
   Qualified<IsConst, DirectoryLookup> &operator*() const {
     assert(*this && "Invalid iterator.");
-    return HS->SearchDirs[Idx];
+    return Idx.get(*HS);
   }
 
   /// Creates an invalid iterator.
@@ -209,7 +251,7 @@
   Qualified<IsConst, HeaderSearch> *HS;
 
   /// The index of the current element.
-  size_t Idx;
+  SearchDirIdx Idx;
 
   /// The constructor that creates a valid iterator.
   SearchDirIteratorImpl(Qualified<IsConst, HeaderSearch> &HS, size_t Idx)
@@ -234,14 +276,13 @@
 class HeaderSearch {
   friend class DirectoryLookup;
 
-  friend ConstSearchDirIterator;
-  friend SearchDirIterator;
+  friend SearchDirIdx;
 
   /// 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;
+  llvm::DenseMap<SearchDirIdx, unsigned> SearchDirToHSEntry;
 
   DiagnosticsEngine &Diags;
   FileManager &FileMgr;
@@ -255,7 +296,7 @@
   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;
+  llvm::DenseSet<SearchDirIdx> UsedSearchDirs;
   unsigned AngledDirIdx = 0;
   unsigned SystemDirIdx = 0;
   bool NoCurDirSearch = false;
@@ -364,7 +405,6 @@
   /// Add an additional system search path.
   void AddSystemSearchPath(const DirectoryLookup &dir) {
     SearchDirs.push_back(dir);
-    SearchDirsUsage.push_back(false);
   }
 
   /// Set the list of system header prefixes.
@@ -780,8 +820,8 @@
                           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);
+  /// search path at index \c HitIdx.
+  void noteLookupUsage(SearchDirIdx HitIdx, SourceLocation IncludeLoc);
 
 public:
   /// Retrieve the module map.
@@ -833,7 +873,7 @@
   }
 
   /// Get the index of the given search directory.
-  unsigned searchDirIdx(const DirectoryLookup &DL) const;
+  SearchDirIdx 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,14 @@
 
 ExternalHeaderFileInfoSource::~ExternalHeaderFileInfoSource() = default;
 
+const DirectoryLookup &SearchDirIdx::get(const HeaderSearch &HS) const {
+  return HS.SearchDirs[Idx];
+}
+
+DirectoryLookup &SearchDirIdx::get(HeaderSearch &HS) const {
+  return HS.SearchDirs[Idx];
+}
+
 HeaderSearch::HeaderSearch(std::shared_ptr<HeaderSearchOptions> HSOpts,
                            SourceManager &SourceMgr, DiagnosticsEngine &Diags,
                            const LangOptions &LangOpts,
@@ -110,18 +118,22 @@
   assert(angledDirIdx <= systemDirIdx && systemDirIdx <= dirs.size() &&
          "Directory indices are unordered");
   SearchDirs = std::move(dirs);
-  SearchDirsUsage.assign(SearchDirs.size(), false);
   AngledDirIdx = angledDirIdx;
   SystemDirIdx = systemDirIdx;
   NoCurDirSearch = noCurDirSearch;
-  SearchDirToHSEntry = std::move(searchDirToHSEntry);
+
+  UsedSearchDirs.clear();
+
+  SearchDirToHSEntry.clear();
+  for (const auto &Entry : searchDirToHSEntry)
+    SearchDirToHSEntry.insert({SearchDirIdx(Entry.first), Entry.second});
+
   //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);
   if (!isAngled)
     AngledDirIdx++;
   SystemDirIdx++;
@@ -129,14 +141,11 @@
 
 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);
-      // Check whether this DirectoryLookup maps to a HeaderSearch::UserEntry.
-      if (UserEntryIdxIt != SearchDirToHSEntry.end())
-        UserEntryUsage[UserEntryIdxIt->second] = true;
-    }
+  for (SearchDirIdx Idx : UsedSearchDirs) {
+    auto UserEntryIdxIt = SearchDirToHSEntry.find(Idx);
+    // Check whether this DirectoryLookup maps to a HeaderSearch::UserEntry.
+    if (UserEntryIdxIt != SearchDirToHSEntry.end())
+      UserEntryUsage[UserEntryIdxIt->second] = true;
   }
   return UserEntryUsage;
 }
@@ -704,8 +713,8 @@
   noteLookupUsage(HitIt.Idx, Loc);
 }
 
-void HeaderSearch::noteLookupUsage(unsigned HitIdx, SourceLocation Loc) {
-  SearchDirsUsage[HitIdx] = true;
+void HeaderSearch::noteLookupUsage(SearchDirIdx HitIdx, SourceLocation Loc) {
+  UsedSearchDirs.insert(HitIdx);
 
   auto UserEntryIdxIt = SearchDirToHSEntry.find(HitIdx);
   if (UserEntryIdxIt != SearchDirToHSEntry.end())
@@ -1446,8 +1455,8 @@
     + FrameworkMap.getAllocator().getTotalMemory();
 }
 
-unsigned HeaderSearch::searchDirIdx(const DirectoryLookup &DL) const {
-  return &DL - &*SearchDirs.begin();
+SearchDirIdx HeaderSearch::searchDirIdx(const DirectoryLookup &DL) const {
+  return SearchDirIdx(&DL - &*SearchDirs.begin());
 }
 
 StringRef HeaderSearch::getUniqueFrameworkName(StringRef Framework) {