[clang][modules] Deserialize included files lazily

[jansvoboda11]

Summary

In D114095, HeaderFileInfo::NumIncludes was moved into Preprocessor. This still makes sense, because we want to track this on the granularity of submodules (D112915, D114173), but the way this information is serialized is not ideal. In ASTWriter, the set of included files gets deserialized eagerly, issuing lots of calls to FileManager::getFile() for input files the PCM consumer might not be interested in.

This patch makes the information part of the header file info table, taking advantage of its lazy deserialization which typically happens when a file is about to be included.

[benlangmuir]

Now that it's not eagerly deserialized, should Preprocessor::alreadyIncluded call HeaderInfo.getFileInfo(File) to ensure the information is up to date? Similarly, we expose the list of files in Preprocessor::getIncludedFiles -- is it okay if this list is incomplete?

clang/lib/Serialization/ASTReader.cpp

1947

Reader.getPreprocessor().markIncluded?

clang/lib/Serialization/ASTWriter.cpp

2545

Can we remove ASTWriter::writeIncludedFiles now?

[jansvoboda11]

In D155131#4495489, @benlangmuir wrote:

Now that it's not eagerly deserialized, should Preprocessor::alreadyIncluded call HeaderInfo.getFileInfo(File) to ensure the information is up to date?

It should, but Preprocessor::alreadyIncluded() is only called from HeaderSearch::ShouldEnterIncludeFile() and Preprocessor::HandleHeaderIncludeOrImport(), where HeaderSearch::getFileInfo(File) has already been called. But I agree it would be better to ensure that within Preprocessor::alreadyIncluded() itself. I'll try to include that in the next revision.

Similarly, we expose the list of files in Preprocessor::getIncludedFiles -- is it okay if this list is incomplete?

That should be okay. This function only needs to return files included in the current module compilation, not all transitive includes.

clang/lib/Serialization/ASTReader.cpp

1947

That would trigger infinite recursion, since that calls getFileInfo() which attempts to deserialize.

clang/lib/Serialization/ASTWriter.cpp

2545

Yes, forgot about that, thanks.

[jansvoboda11]

Remove dead code, make sure getFileInfo() is called in alreadyIncluded().

clang/include/clang/Lex/Preprocessor.h

public:
   /// Returns true if this is the first time the file was included.
   bool markIncluded(const FileEntry *File) {
     HeaderInfo.getFileInfo(File);
     return IncludedFiles.insert(File).second;
   }
 
   /// Return true if this header has already been included.
   bool alreadyIncluded(const FileEntry *File) const {
+    HeaderInfo.getFileInfo(File);
     return IncludedFiles.count(File);
   }
 
   /// Get the set of included files.
   IncludedFilesSet &getIncludedFiles() { return IncludedFiles; }
   const IncludedFilesSet &getIncludedFiles() const { return IncludedFiles; }
 
   /// Return the name of the macro defined before \p Loc that has

clang/include/clang/Serialization/ASTBitCodes.h

 /// Whenever the AST file format changes in a way that makes it
 /// incompatible with previous versions (such that a reader
 /// designed for the previous version could not support reading
 /// the new version), this number should be increased.
 ///
 /// Version 4 of AST files also requires that the version control branch and
 /// revision match exactly, since there is no backward compatibility of
 /// AST files at this time.
-const unsigned VERSION_MAJOR = 25;
+const unsigned VERSION_MAJOR = 26;
 
 /// AST file minor version number supported by this version of
 /// Clang.
 ///
 /// Whenever the AST format changes in a way that is still
 /// compatible with previous versions (such that a reader designed
 /// for the previous version could still support reading the new
 /// version by ignoring new kinds of subblocks), this number
enum ASTRecordTypes {
   PPD_SKIPPED_RANGES = 63,
 
   /// Record code for the Decls to be checked for deferred diags.
   DECLS_TO_CHECK_FOR_DEFERRED_DIAGS = 64,
 
   /// Record code for \#pragma float_control options.
   FLOAT_CONTROL_PRAGMA_OPTIONS = 65,
 
-  /// Record code for included files.
-  PP_INCLUDED_FILES = 66,
+  /// ID 66 used to be the list of included files.
 
   /// Record code for an unterminated \#pragma clang assume_nonnull begin
   /// recorded in a preamble.
   PP_ASSUME_NONNULL_LOC = 67,
 };
 
 /// Record types used within a source manager block.
 enum SourceManagerRecordTypes {

clang/include/clang/Serialization/ASTReader.h

readUnhashedControlBlockImpl(ModuleFile *F, llvm::StringRef StreamData,
                                bool ValidateDiagnosticOptions);
 
   llvm::Error ReadASTBlock(ModuleFile &F, unsigned ClientLoadCapabilities);
   llvm::Error ReadExtensionBlock(ModuleFile &F);
   void ReadModuleOffsetMap(ModuleFile &F) const;
   void ParseLineTable(ModuleFile &F, const RecordData &Record);
   llvm::Error ReadSourceManagerBlock(ModuleFile &F);
   SourceLocation getImportLocation(ModuleFile *F);
-  void readIncludedFiles(ModuleFile &F, StringRef Blob, Preprocessor &PP);
   ASTReadResult ReadModuleMapFileBlock(RecordData &Record, ModuleFile &F,
                                        const ModuleFile *ImportedBy,
                                        unsigned ClientLoadCapabilities);
   llvm::Error ReadSubmoduleBlock(ModuleFile &F,
                                  unsigned ClientLoadCapabilities);
   static bool ParseLanguageOptions(const RecordData &Record, bool Complain,
                                    ASTReaderListener &Listener,
                                    bool AllowCompatibleDifferences);

clang/include/clang/Serialization/ASTWriter.h

private:
 
   /// Calculate hash of the pcm content.
   static std::pair<ASTFileSignature, ASTFileSignature>
   createSignature(StringRef AllBytes, StringRef ASTBlockBytes);
 
   void WriteInputFiles(SourceManager &SourceMgr, HeaderSearchOptions &HSOpts);
   void WriteSourceManagerBlock(SourceManager &SourceMgr,
                                const Preprocessor &PP);
-  void writeIncludedFiles(raw_ostream &Out, const Preprocessor &PP);
   void WritePreprocessor(const Preprocessor &PP, bool IsModule);
   void WriteHeaderSearch(const HeaderSearch &HS);
   void WritePreprocessorDetail(PreprocessingRecord &PPRec,
                                uint64_t MacroOffsetsBase);
   void WriteSubmodules(Module *WritingModule);
 
   void WritePragmaDiagnosticMappings(const DiagnosticsEngine &Diag,
                                      bool isModule);

clang/lib/Serialization/ASTReader.cpp

ASTReader::getGlobalPreprocessedEntityID(ModuleFile &M,
   ContinuousRangeMap<uint32_t, int, 2>::const_iterator
     I = M.PreprocessedEntityRemap.find(LocalID - NUM_PREDEF_PP_ENTITY_IDS);
   assert(I != M.PreprocessedEntityRemap.end()
          && "Invalid index into preprocessed entity index remap");
 
   return LocalID + I->second;
 }
 
+const FileEntry *HeaderFileInfoTrait::getFile(const internal_key_type &Key) {
+  FileManager &FileMgr = Reader.getFileManager();
+  if (!Key.Imported) {
+    if (auto File = FileMgr.getFile(Key.Filename))
+      return *File;
+    return nullptr;
+  }
+
+  std::string Resolved = std::string(Key.Filename);
+  Reader.ResolveImportedPath(M, Resolved);
+  if (auto File = FileMgr.getFile(Resolved))
+    return *File;
+  return nullptr;
+}
+
 unsigned HeaderFileInfoTrait::ComputeHash(internal_key_ref ikey) {
   return llvm::hash_combine(ikey.Size, ikey.ModTime);
 }
 
 HeaderFileInfoTrait::internal_key_type
 HeaderFileInfoTrait::GetInternalKey(const FileEntry *FE) {
   internal_key_type ikey = {FE->getSize(),
                             M.HasTimestamps ? FE->getModificationTime() : 0,
                             FE->getName(), /*Imported*/ false};
   return ikey;
 }
 
 bool HeaderFileInfoTrait::EqualKey(internal_key_ref a, internal_key_ref b) {
   if (a.Size != b.Size || (a.ModTime && b.ModTime && a.ModTime != b.ModTime))
     return false;
 
   if (llvm::sys::path::is_absolute(a.Filename) && a.Filename == b.Filename)
     return true;
 
   // Determine whether the actual files are equivalent.
-  FileManager &FileMgr = Reader.getFileManager();
-  auto GetFile = [&](const internal_key_type &Key) -> const FileEntry* {
-    if (!Key.Imported) {
-      if (auto File = FileMgr.getFile(Key.Filename))
-        return *File;
-      return nullptr;
-    }
-
-    std::string Resolved = std::string(Key.Filename);
-    Reader.ResolveImportedPath(M, Resolved);
-    if (auto File = FileMgr.getFile(Resolved))
-      return *File;
-    return nullptr;
-  };
-
-  const FileEntry *FEA = GetFile(a);
-  const FileEntry *FEB = GetFile(b);
+  const FileEntry *FEA = getFile(a);
+  const FileEntry *FEB = getFile(b);
   return FEA && FEA == FEB;
 }
 
 std::pair<unsigned, unsigned>
 HeaderFileInfoTrait::ReadKeyDataLength(const unsigned char*& d) {
   return readULEBKeyDataLength(d);
 }
 

 HeaderFileInfoTrait::data_type
 HeaderFileInfoTrait::ReadData(internal_key_ref key, const unsigned char *d,
                               unsigned DataLen) {
   using namespace llvm::support;
 
   const unsigned char *End = d + DataLen;
   HeaderFileInfo HFI;
   unsigned Flags = *d++;
+
+  bool Included = (Flags >> 6) & 0x01;
+  if (Included)
+    if (const FileEntry *FE = getFile(key))
+      // Not using \c Preprocessor::markIncluded(), since that would attempt to
+      // deserialize this header file info again.
+      Reader.getPreprocessor().getIncludedFiles().insert(FE);
+
   // FIXME: Refactor with mergeHeaderFileInfo in HeaderSearch.cpp.
   HFI.isImport |= (Flags >> 5) & 0x01;
   HFI.isPragmaOnce |= (Flags >> 4) & 0x01;
   HFI.DirInfo = (Flags >> 1) & 0x07;
   HFI.IndexHeaderMapHeader = Flags & 0x01;
   HFI.ControllingMacroID = Reader.getGlobalIdentifierID(
       M, endian::readNext<uint32_t, little, unaligned>(d));
   if (unsigned FrameworkOffset =
case INPUT_FILE_OFFSETS:
       F.InputFilesLoaded.resize(NumInputs);
       F.InputFileInfosLoaded.resize(NumInputs);
       F.NumUserInputFiles = NumUserInputs;
       break;
     }
   }
 }
 
-void ASTReader::readIncludedFiles(ModuleFile &F, StringRef Blob,
-                                  Preprocessor &PP) {
-  using namespace llvm::support;
-
-  const unsigned char *D = (const unsigned char *)Blob.data();
-  unsigned FileCount = endian::readNext<uint32_t, little, unaligned>(D);
-
-  for (unsigned I = 0; I < FileCount; ++I) {
-    size_t ID = endian::readNext<uint32_t, little, unaligned>(D);
-    InputFileInfo IFI = getInputFileInfo(F, ID);
-    if (llvm::ErrorOr<const FileEntry *> File =
-            PP.getFileManager().getFile(IFI.Filename))
-      PP.getIncludedFiles().insert(*File);
-  }
-}
-
 llvm::Error ASTReader::ReadASTBlock(ModuleFile &F,
                                     unsigned ClientLoadCapabilities) {
   BitstreamCursor &Stream = F.Stream;
 
   if (llvm::Error Err = Stream.EnterSubBlock(AST_BLOCK_ID))
     return Err;
   F.ASTBlockStartOffset = Stream.GetCurrentBitNo();
 
case MACRO_OFFSET: {
           std::make_pair(LocalBaseMacroID,
                          F.BaseMacroID - LocalBaseMacroID));
 
         MacrosLoaded.resize(MacrosLoaded.size() + F.LocalNumMacros);
       }
       break;
     }
 
-    case PP_INCLUDED_FILES:
-      readIncludedFiles(F, Blob, PP);
-      break;
-
     case LATE_PARSED_TEMPLATE:
       LateParsedTemplates.emplace_back(
           std::piecewise_construct, std::forward_as_tuple(&F),
           std::forward_as_tuple(Record.begin(), Record.end()));
       break;
 
     case OPTIMIZE_PRAGMA_OPTIONS:
       if (Record.size() != 1)

clang/lib/Serialization/ASTReaderInternals.h

public:
   bool EqualKey(internal_key_ref a, internal_key_ref b);
 
   static std::pair<unsigned, unsigned>
   ReadKeyDataLength(const unsigned char*& d);
 
   static internal_key_type ReadKey(const unsigned char *d, unsigned);
 
   data_type ReadData(internal_key_ref,const unsigned char *d, unsigned DataLen);
+
+private:
+  const FileEntry *getFile(const internal_key_type &Key);
 };
 
 /// The on-disk hash table used for known header files.
 using HeaderFileInfoLookupTable =
     llvm::OnDiskChainedHashTable<HeaderFileInfoTrait>;
 
 } // namespace reader
 
 } // namespace serialization
 
 } // namespace clang
 
 #endif // LLVM_CLANG_LIB_SERIALIZATION_ASTREADERINTERNALS_H

clang/lib/Serialization/ASTWriter.cpp

#define RECORD(X) EmitRecordID(X, #X, Stream, Record)
   RECORD(OPTIMIZE_PRAGMA_OPTIONS);
   RECORD(MSSTRUCT_PRAGMA_OPTIONS);
   RECORD(POINTERS_TO_MEMBERS_PRAGMA_OPTIONS);
   RECORD(UNUSED_LOCAL_TYPEDEF_NAME_CANDIDATES);
   RECORD(DELETE_EXPRS_TO_ANALYZE);
   RECORD(CUDA_PRAGMA_FORCE_HOST_DEVICE_DEPTH);
   RECORD(PP_CONDITIONAL_STACK);
   RECORD(DECLS_TO_CHECK_FOR_DEFERRED_DIAGS);
-  RECORD(PP_INCLUDED_FILES);
   RECORD(PP_ASSUME_NONNULL_LOC);
 
   // SourceManager Block.
   BLOCK(SOURCE_MANAGER_BLOCK);
   RECORD(SM_SLOC_FILE_ENTRY);
   RECORD(SM_SLOC_BUFFER_ENTRY);
   RECORD(SM_SLOC_BUFFER_BLOB);
   RECORD(SM_SLOC_BUFFER_BLOB_COMPRESSED);
public:
     };
     using key_type_ref = const key_type &;
 
     using UnresolvedModule =
         llvm::PointerIntPair<Module *, 2, ModuleMap::ModuleHeaderRole>;
 
     struct data_type {
       const HeaderFileInfo &HFI;
+      bool AlreadyIncluded;
       ArrayRef<ModuleMap::KnownHeader> KnownHeaders;
       UnresolvedModule Unresolved;
     };
     using data_type_ref = const data_type &;
 
     using hash_value_type = unsigned;
     using offset_type = unsigned;
 
public:
 
     void EmitData(raw_ostream &Out, key_type_ref key,
                   data_type_ref Data, unsigned DataLen) {
       using namespace llvm::support;
 
       endian::Writer LE(Out, little);
       uint64_t Start = Out.tell(); (void)Start;
 
-      unsigned char Flags = (Data.HFI.isImport << 5)
+      unsigned char Flags = (Data.AlreadyIncluded << 6)
+                          | (Data.HFI.isImport << 5)
                           | (Data.HFI.isPragmaOnce << 4)
                           | (Data.HFI.DirInfo << 1)
                           | Data.HFI.IndexHeaderMapHeader;
       LE.write<uint8_t>(Flags);
 
       if (!Data.HFI.ControllingMacro)
         LE.write<uint32_t>(Data.HFI.ControllingMacroID);
       else
while (!Worklist.empty()) {
         PreparePathForOutput(Filename);
 
         StringRef FilenameDup = strdup(Filename.c_str());
         SavedStrings.push_back(FilenameDup.data());
 
         HeaderFileInfoTrait::key_type Key = {
             FilenameDup, *U.Size, IncludeTimestamps ? *U.ModTime : 0};
         HeaderFileInfoTrait::data_type Data = {
-            Empty, {}, {M, ModuleMap::headerKindToRole(U.Kind)}};
+            Empty, false, {}, {M, ModuleMap::headerKindToRole(U.Kind)}};
         // FIXME: Deal with cases where there are multiple unresolved header
         // directives in different submodules for the same header.
         Generator.insert(Key, Data, GeneratorTrait);
         ++NumHeaderSearchEntries;
       }
       auto SubmodulesRange = M->submodules();
       Worklist.append(SubmodulesRange.begin(), SubmodulesRange.end());
     }
for (unsigned UID = 0, LastUID = FilesByUID.size(); UID != LastUID; ++UID) {
     SmallString<128> FilenameTmp(Filename);
     if (PreparePathForOutput(FilenameTmp)) {
       // If we performed any translation on the file name at all, we need to
       // save this string, since the generator will refer to it later.
       Filename = StringRef(strdup(FilenameTmp.c_str()));
       SavedStrings.push_back(Filename.data());
     }
 
+    bool Included = PP->alreadyIncluded(File);
+
     HeaderFileInfoTrait::key_type Key = {
       Filename, File->getSize(), getTimestampForOutput(File)
     };
     HeaderFileInfoTrait::data_type Data = {
-      *HFI, HS.getModuleMap().findResolvedModulesForHeader(File), {}
+      *HFI, Included, HS.getModuleMap().findResolvedModulesForHeader(File), {}
     };
     Generator.insert(Key, Data, GeneratorTrait);
     ++NumHeaderSearchEntries;
   }
 
   // Create the on-disk hash table in a buffer.
   SmallString<4096> TableData;
   uint32_t BucketOffset;
if (Loc.isInvalid())
       return true;
     if (PP.getSourceManager().getFileID(Loc) == PP.getPredefinesFileID())
       return true;
   }
 
   return false;
 }
 
-void ASTWriter::writeIncludedFiles(raw_ostream &Out, const Preprocessor &PP) {
-  using namespace llvm::support;
-
-  const Preprocessor::IncludedFilesSet &IncludedFiles = PP.getIncludedFiles();
-
-  std::vector<uint32_t> IncludedInputFileIDs;
-  IncludedInputFileIDs.reserve(IncludedFiles.size());
-
-  for (const FileEntry *File : IncludedFiles) {
-    auto InputFileIt = InputFileIDs.find(File);
-    if (InputFileIt == InputFileIDs.end())
-      continue;
-    IncludedInputFileIDs.push_back(InputFileIt->second);
-  }
-
-  llvm::sort(IncludedInputFileIDs);
-
-  endian::Writer LE(Out, little);
-  LE.write<uint32_t>(IncludedInputFileIDs.size());
-  for (uint32_t ID : IncludedInputFileIDs)
-    LE.write<uint32_t>(ID);
-}
-
 /// Writes the block containing the serialized form of the
 /// preprocessor.
 void ASTWriter::WritePreprocessor(const Preprocessor &PP, bool IsModule) {
   uint64_t MacroOffsetsBase = Stream.GetCurrentBitNo();
 
   PreprocessingRecord *PPRec = PP.getPreprocessingRecord();
   if (PPRec)
     WritePreprocessorDetail(*PPRec, MacroOffsetsBase);
void ASTWriter::WritePreprocessor(const Preprocessor &PP, bool IsModule) {
 
   unsigned MacroOffsetAbbrev = Stream.EmitAbbrev(std::move(Abbrev));
   {
     RecordData::value_type Record[] = {MACRO_OFFSET, MacroOffsets.size(),
                                        FirstMacroID - NUM_PREDEF_MACRO_IDS,
                                        MacroOffsetsBase - ASTBlockStartOffset};
     Stream.EmitRecordWithBlob(MacroOffsetAbbrev, Record, bytes(MacroOffsets));
   }
-
-  {
-    auto Abbrev = std::make_shared<BitCodeAbbrev>();
-    Abbrev->Add(BitCodeAbbrevOp(PP_INCLUDED_FILES));
-    Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
-    unsigned IncludedFilesAbbrev = Stream.EmitAbbrev(std::move(Abbrev));
-
-    SmallString<2048> Buffer;
-    raw_svector_ostream Out(Buffer);
-    writeIncludedFiles(Out, PP);
-    RecordData::value_type Record[] = {PP_INCLUDED_FILES};
-    Stream.EmitRecordWithBlob(IncludedFilesAbbrev, Record, Buffer.data(),
-                              Buffer.size());
-  }
 }
 
 void ASTWriter::WritePreprocessorDetail(PreprocessingRecord &PPRec,
                                         uint64_t MacroOffsetsBase) {
   if (PPRec.local_begin() == PPRec.local_end())
     return;
 
   SmallVector<PPEntityOffset, 64> PreprocessedEntityOffsets;