diff --git a/clang/include/clang/Basic/FileManager.h b/clang/include/clang/Basic/FileManager.h
--- a/clang/include/clang/Basic/FileManager.h
+++ b/clang/include/clang/Basic/FileManager.h
@@ -310,10 +310,10 @@
   /// \returns true if \c Path changed to absolute.
   bool makeAbsolutePath(SmallVectorImpl<char> &Path) const;
 
-  /// Produce an array mapping from the unique IDs assigned to each
-  /// file to the corresponding FileEntry pointer.
-  void GetUniqueIDMapping(
-                    SmallVectorImpl<const FileEntry *> &UIDToFiles) const;
+  /// Produce an array of seen FileEntryRef. The entries will be sorted
+  /// by UID and Name. Virtual file entries will not be returned.
+  void
+  getSeenNonVirtualFileEntries(SmallVectorImpl<FileEntryRef> &Entries) const;
 
   /// Retrieve the canonical name for a given directory.
   ///
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
@@ -793,8 +793,6 @@
   /// Retrieve the module map.
   const ModuleMap &getModuleMap() const { return ModMap; }
 
-  unsigned header_file_size() const { return FileInfo.size(); }
-
   /// Return the HeaderFileInfo structure for the specified FileEntry,
   /// in preparation for updating it in some way.
   HeaderFileInfo &getFileInfo(const FileEntry *FE);
diff --git a/clang/lib/Basic/FileManager.cpp b/clang/lib/Basic/FileManager.cpp
--- a/clang/lib/Basic/FileManager.cpp
+++ b/clang/lib/Basic/FileManager.cpp
@@ -611,25 +611,26 @@
   return std::error_code();
 }
 
-void FileManager::GetUniqueIDMapping(
-    SmallVectorImpl<const FileEntry *> &UIDToFiles) const {
-  UIDToFiles.clear();
-  UIDToFiles.resize(NextFileUID);
-
-  // Map file entries
-  for (llvm::StringMap<llvm::ErrorOr<FileEntryRef::MapValue>,
-                       llvm::BumpPtrAllocator>::const_iterator
-           FE = SeenFileEntries.begin(),
-           FEEnd = SeenFileEntries.end();
-       FE != FEEnd; ++FE)
-    if (llvm::ErrorOr<FileEntryRef::MapValue> Entry = FE->getValue()) {
-      if (const auto *FE = Entry->V.dyn_cast<FileEntry *>())
-        UIDToFiles[FE->getUID()] = FE;
-    }
+void FileManager::getSeenNonVirtualFileEntries(
+    SmallVectorImpl<FileEntryRef> &Entries) const {
+  Entries.reserve(SeenFileEntries.size());
+
+  for (const auto &Entry : SeenFileEntries) {
+    if (auto Value = Entry.getValue())
+      // Ignore VFS-mapped entries, they will have a separate on-disk
+      // file entry.
+      if (Value->V.is<FileEntry *>())
+        Entries.push_back(FileEntryRef(Entry));
+  }
+
+  // We want the file entries in deterministic order for
+  // module serialization.
+  llvm::sort(Entries, [](FileEntryRef &A, FileEntryRef &B) {
+    if (A.getUID() != B.getUID())
+      return A.getUID() < B.getUID();
 
-  // Map virtual file entries
-  for (const auto &VFE : VirtualFileEntries)
-    UIDToFiles[VFE->getUID()] = VFE;
+    return A.getName() < B.getName();
+  });
 }
 
 StringRef FileManager::getCanonicalName(const DirectoryEntry *Dir) {
diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp
--- a/clang/lib/Serialization/ASTWriter.cpp
+++ b/clang/lib/Serialization/ASTWriter.cpp
@@ -169,17 +169,10 @@
 
   const HeaderSearch &HS = PP.getHeaderSearchInfo();
 
-  SmallVector<const FileEntry *, 16> FilesByUID;
-  HS.getFileMgr().GetUniqueIDMapping(FilesByUID);
-
-  if (FilesByUID.size() > HS.header_file_size())
-    FilesByUID.resize(HS.header_file_size());
-
-  for (unsigned UID = 0, LastUID = FilesByUID.size(); UID != LastUID; ++UID) {
-    const FileEntry *File = FilesByUID[UID];
-    if (!File)
-      continue;
+  SmallVector<FileEntryRef, 16> FileEntries;
+  HS.getFileMgr().getSeenNonVirtualFileEntries(FileEntries);
 
+  for (auto File : FileEntries) {
     const HeaderFileInfo *HFI =
         HS.getExistingFileInfo(File, /*WantExternal*/ false);
     if (!HFI || (HFI->isModuleHeader && !HFI->isCompilingModuleHeader))
@@ -1918,16 +1911,10 @@
     }
   }
 
-  SmallVector<const FileEntry *, 16> FilesByUID;
-  HS.getFileMgr().GetUniqueIDMapping(FilesByUID);
+  SmallVector<FileEntryRef, 16> FileEntries;
+  HS.getFileMgr().getSeenNonVirtualFileEntries(FileEntries);
 
-  if (FilesByUID.size() > HS.header_file_size())
-    FilesByUID.resize(HS.header_file_size());
-
-  for (unsigned UID = 0, LastUID = FilesByUID.size(); UID != LastUID; ++UID) {
-    const FileEntry *File = FilesByUID[UID];
-    if (!File)
-      continue;
+  for (auto File : FileEntries) {
 
     // Get the file info. This will load info from the external source if
     // necessary. Skip emitting this file if we have no information on it
@@ -1941,7 +1928,7 @@
       continue;
 
     // Massage the file path into an appropriate form.
-    StringRef Filename = File->getName();
+    StringRef Filename = File.getName();
     SmallString<128> FilenameTmp(Filename);
     if (PreparePathForOutput(FilenameTmp)) {
       // If we performed any translation on the file name at all, we need to
@@ -1950,9 +1937,8 @@
       SavedStrings.push_back(Filename.data());
     }
 
-    HeaderFileInfoTrait::key_type Key = {
-      Filename, File->getSize(), getTimestampForOutput(File)
-    };
+    HeaderFileInfoTrait::key_type Key = {Filename, File.getSize(),
+                                         getTimestampForOutput(File)};
     HeaderFileInfoTrait::data_type Data = {
       *HFI, HS.getModuleMap().findResolvedModulesForHeader(File), {}
     };