[clang][lex] Include tracking: simplify and move to preprocessor

[jansvoboda11]

Summary

This patch replaces the exact include count of each file in HeaderFileInfo with a set of included files in Preprocessor.

The number of includes isn't a property of a header file but rather a preprocessor state. The exact number of includes is not used anywhere except statistic tracking.

[dexonsmith]

I'm not sure this commit stands on its own, since it introduces a (temporary) regression in .pcm size; I suggest squashing with the follow-up, https://reviews.llvm.org/D114096.

clang/include/clang/Lex/HeaderSearch.h

55

Note that clang-format is complaining about a trailing space / here.

[jansvoboda11]

Squash with D114096.

[vsapsai]

Haven't checked the details of serialization/deserialization. High-level question about different serialization approaches (bitvector vs list of file ids) is in D112915.

clang/lib/Lex/Preprocessor.cpp

561

Why do you need to getFileInfo but don't use it? I have no objections but it looks like it deserves a comment because it's not obvious.

[vsapsai]

clang/include/clang/Serialization/ASTBitCodes.h

700

Small detail. Do you need to add the new record to ASTWriter::WriteBlockInfoBlock? It's not critical but you are one of those who might be grateful later seeing PP_INCLUDED_FILES instead of UnknownCode66 in .pcm dump.

[jansvoboda11]

Add new record into block info.

[jansvoboda11]

clang/lib/Lex/Preprocessor.cpp

561

Without the call, I'm hitting some assertions when running C++20 modules tests:

Assertion failed: (CurDiagID == std::numeric_limits<unsigned>::max() && "Multiple diagnostics in flight at once!"), function Report, file Diagnostic.h, line 1526.

fatal error: error in backend: -verify directives found after rather than during normal parsing of <llvm>/clang/test/CXX/modules-ts/basic/basic.def.odr/p6/global-vs-module.cpp

Might need to investigate more to be able to write up a reasonable comment here.

[vsapsai]

clang/lib/Serialization/ASTWriter.cpp

820

I believe PP_INCLUDED_FILES is located in AST_BLOCK. Yes, you write it in ASTWriter::WritePreprocessor but after Stream.ExitBlock() together with MACRO_OFFSET. And then you read it in ASTReader::ReadASTBlock at the top level and not inside case PREPROCESSOR_BLOCK_ID or from ModuleFile::MacroCursor.

[jansvoboda11]

clang/lib/Serialization/ASTWriter.cpp

820

That's right. This is modeled after PP_CONDITIONAL_STACK and PP_COUNTER_VALUE.

The problem is that the whole PREPROCESSOR_BLOCK_ID is treated as "macros only" block that's not being split into individual records right away and is instead deserialized lazily in ReadMacroRecord, ReadDefinedMacros, resolvePendingMacro. I think this should be fixed eventually, but I didn't want to expand the scope of my changes, since it's already somewhat complex already.

[jansvoboda11]

Move record ID from PREPROCESSOR_BLOCK to AST_BLOCK.

[dexonsmith]

This LGTM by the way (not sure if that was already clear, since you abandoned a different review than I anticipated when squashing, and I'd "accepted" the other one); also see my suggestion to move the call to getFileInfo inside of markIncluded (might be error prone not to make that change).

Haven't clicked "accept" here in case @vsapsai has more comments.

clang/lib/Lex/Preprocessor.cpp

561

Not sure precisely why that assertion fires, but the call to getFileInfo makes sense since it's mutating -- it adds a HeaderFileInfo entry (and IncrementIncludeCount() used to call it). There are code paths that call getExistingFileInfo that will expect it to have been created on inclusion.

I suggest moving the getFileInfo() call to inside markIncluded() and adding a comment that says "Create the HeaderFileInfo if it doesn't already exist" or something. Parting of marking it included should be to ensure that callers of HeaderSearch::getExistingFileInfo get something back.

(This'd be more obvious (and the comment unnecessary) if getFileInfo were renamed to getOrCreateFileInfo, after which getExistingFileInfo could be renamed to getFileInfo.)

[vsapsai]

I've mentioned it in D112915 as we've discussed the stored data format there. But my concern was that bitvector packing might be not the most space-efficient encoding. I haven't done proper testing, just off-the-cuff comparison and it looks like for the most of frameworks in iOS SDK storing included headers per submodule takes less space than encoding them as a bitvector. I have an idea why that might be happening but I haven't checked it in debugger, so'll keep it to myself to avoid derailing the discussion.

[jansvoboda11]

In D114095#3160103, @vsapsai wrote:

I've mentioned it in D112915 as we've discussed the stored data format there. But my concern was that bitvector packing might be not the most space-efficient encoding. I haven't done proper testing, just off-the-cuff comparison and it looks like for the most of frameworks in iOS SDK storing included headers per submodule takes less space than encoding them as a bitvector. I have an idea why that might be happening but I haven't checked it in debugger, so'll keep it to myself to avoid derailing the discussion.

Let's bring the conversation over here. I ran the same UIKit test you did and compared the following:

• current trunk
• current trunk with this patch
• current trunk with this patch, with bitvector replaced by vector of IDs (32-bit integers).

The following table shows sizes of .pcm files in bytes and their delta compared to trunk:

+----------+-----------------+-----------------+
|   trunk  |    bit vector   |    ID vector    |
+----------+-----------------+-----------------+
|   281932 |   281944    +12 |   281988    +56 |
|   989840 |   989784    -56 |   989968   +128 |
|   837116 |   837084    -32 |   837212    +96 |
|   899924 |   899912    -12 |   900004    +80 |
|   710296 |   710296     +0 |   710376    +80 |
|   273140 |   273144     +4 |   273196    +56 |
|  3649856 |  3649024   -832 |  3650804   +948 |
|   207676 |   207692    +16 |   207740    +64 |
|   342792 |   342804    +12 |   342860    +68 |
|  4137660 |  4137460   -200 |  4137940   +280 |
|   173536 |   173564    +28 |   173580    +44 |
|   787120 |   787144    +24 |   787180    +60 |
|  1260652 |  1260596    -56 |  1260804   +152 |
|   255072 |   255092    +20 |   255128    +56 |
|   973204 |   973228    +24 |   973268    +64 |
|   398952 |   398940    -12 |   399036    +84 |
|   631516 |   631516     +0 |   631588    +72 |
|  5252932 |  5252348   -584 |  5253612   +680 |
|   230160 |   230168     +8 |   230228    +68 |
|    24460 |    24500    +40 |    24500    +40 |
|    53244 |    53280    +36 |    53288    +44 |
|    75932 |    75952    +20 |    75972    +40 |
|    32840 |    32876    +36 |    32884    +44 |
+----------+-----------------+-----------------+
| 22479852 | 22478348  -1504 | 22483156  +3304 |
+----------+-----------------+-----------------+

Used command:

echo '#import <UIKit/UIKit.h>' | ./bin/clang -fsyntax-only -isysroot "$(xcrun --sdk iphoneos --show-sdk-path)" -target arm64-apple-ios -fmodules -fmodules-cache-path=modules.noindex -x objective-c -

Patch that I applied on top of the one under review to get vector of IDs:

bitvector-to-id-vector.diff2 KBDownload

I see how the bitvector could explode for large fine-grained modules. They have lots of input files (-> large bitvectors in each submodule), but each submodule only includes a handful files (-> bitvectors are sparse). It seems like this doesn't actually happen, at least in our SDK.

@vsapsai Do you think this warrants more thorough investigation?

[vsapsai]

Thanks for measuring the .pcm impact! And I appreciate including the trunk baseline.

The results aren't exactly the same I've seen before, so please forgive me my suspiciousness. When you mention

current trunk with this patch

do you mean "just this D114095 patch"? Or were you testing with D112915 applied? Because I was testing with per-submodule tracking applied. I am going to check again but it would be useful to know if you were comparing with per-submodule tracking (D112915) or not.

[jansvoboda11]

You're right, I measured only this patch, not per-submodule include tracking (D112915).

With per-submodule tracking, the results look like this:

+----------+------------------+------------------+-------------------+------------------+
| original |     ID vector    |    bit vector    | subm. w incl. [%] | 1 in bitvec. [%] |
+----------+------------------+------------------+-------------------+------------------+
|    23348 |    23380     +32 |    23380     +32 |       100.0       |       33.3       |
|    52188 |    52224     +36 |    52224     +36 |       100.0       |        6.3       |
|    74808 |    74856     +48 |    74840     +32 |       100.0       |        9.4       |
|   171772 |   171836     +64 |   171840     +68 |        40.0       |        5.7       |
|   206524 |   206584     +60 |   206540     +16 |       100.0       |       32.5       |
|   227716 |   227904    +188 |   227856    +140 |         6.3       |       33.3       |
|   253656 |   253812    +156 |   253788    +132 |        90.0       |        7.6       |
|   271332 |   271584    +252 |   271524    +192 |        85.7       |        8.5       |
|   280280 |   280460    +180 |   280428    +148 |        91.7       |        5.6       |
|   340024 |   340176    +152 |   340144    +120 |        21.4       |       10.9       |
|   394692 |   394928    +236 |   394872    +180 |        25.0       |       18.1       |
|   629740 |   630028    +288 |   629940    +200 |        83.3       |       20.0       |
|   707456 |   707732    +276 |   707676    +220 |        85.7       |       13.9       |
|   785508 |   785632    +124 |   785616    +108 |        85.7       |       18.1       |
|   835204 |   835824    +620 |   835616    +412 |        93.8       |       12.5       |
|   887764 |   888004    +240 |   887940    +176 |         8.7       |       19.1       |
|   971352 |   971504    +152 |   971500    +148 |        66.7       |        6.0       |
|   994112 |   995048    +936 |   994672    +560 |        93.5       |        9.1       |
|  1248888 |  1249408    +520 |  1249352    +464 |        29.6       |        5.0       |
|  3642908 |  3650076   +7168 |  3652668   +9760 |        74.5       |        2.8       |
|  4112848 |  4114016   +1168 |  4113780    +932 |        17.7       |        5.3       |
|  5213344 |  5216228   +2884 |  5216552   +3208 |        22.0       |        2.2       |
+----------+------------------+------------------+-------------------+------------------+
| 22325464 | 22341244  +15780 | 22342748  +17284 |                   |                  |
+----------+------------------+------------------+-------------------+------------------+

The subm. w incl. [%] column shows the percentage of submodules that include any headers and for the ones that do, 1 in bitvec. [%] shows how sparse are the bitvectors on average (what percentage of 1 bits they contain).

It seems like smaller modules are generally better off with bitvectors, but for larger modules with greater cumulative number of includes, the bitvectors get long and sparse. And it's the larger modules whose size ends up impacting the overall size of module cache. I think that matches my intuition and roughly corresponds to your own measurements.

(Note that in any case, the module cache growth is negligible: .071% for ID vector and .077% for bitvector.)

Given that, I think we should commit this patch with ID vectors, even though in isolation (without D112915) it's the worse solution. WDYT?

[vsapsai]

In D114095#3188557, @jansvoboda11 wrote:

Given that, I think we should commit this patch with ID vectors, even though in isolation (without D112915) it's the worse solution. WDYT?

I have to admit that I think ID vector code is easier to understand and the format is easier to understand. And if bitvector approach is more complicated but doesn't gain us much in efficiency, then I think it's not worth pursuing. Though I'm glad and grateful that you've tried bitvector approach, that's very helpful.

My preference is to use ID vectors but I'm open to other opinions as I might be missing other trade-offs besides complexity and .pcm file size.

And I want to thank you for checking the sparseness of submodules and how with the bigger modules the impact of the sparseness becomes more pronounced.

[jansvoboda11]

@vsapsai do you have any further concerns? My only intended change at this point is Duncan's suggestion.

[vsapsai]

In D114095#3261073, @jansvoboda11 wrote:

@vsapsai do you have any further concerns? My only intended change at this point is Duncan's suggestion.

My understanding was that we were going with ID vectors approach and not with bitvectors, and the current code still uses bitvectors. Also I have a minor readability concern about auto usage, it seems to be used more often than the coding standard asks for. But that usage is in serialization/deserialization code which I wasn't sure if it was going to stay.

[jansvoboda11]

1. Move HeaderSearch::getFileInfo() call into Preprocessor::markIncluded().
2. Switch from bitvector to vector of file IDs in AST files.
3. Remove unnecessary usages of auto.

[jansvoboda11]

In D114095#3263086, @vsapsai wrote:

My understanding was that we were going with ID vectors approach and not with bitvectors, and the current code still uses bitvectors. Also I have a minor readability concern about auto usage, it seems to be used more often than the coding standard asks for. But that usage is in serialization/deserialization code which I wasn't sure if it was going to stay.

Ah, sorry about that. Fixed in latest revision.

[vsapsai]

Looks good to me. Thanks for working on it!

Though I haven't built it locally and it can be useful for pre-merge checks to finish.

clang/include/clang/Lex/HeaderSearch.h

 class LangOptions;
 class Module;
 class Preprocessor;
 class TargetInfo;
 
 /// The preprocessor keeps track of this information for each
 /// file that is \#included.
 struct HeaderFileInfo {
+  // TODO: Whether the file was imported is not a property of the file itself.
+  // It's a preprocessor state, move it there. 
   /// True if this is a \#import'd file.
   unsigned isImport : 1;
 
   /// True if this is a \#pragma once file.
   unsigned isPragmaOnce : 1;
 
   /// Keep track of whether this is a system header, and if so,
   /// whether it is C++ clean or not.  This can be set by the include paths or
struct HeaderFileInfo {
   /// into the appropriate framework subdirectories, and therefore are
   /// provided via a header map. This bit indicates when this is one of
   /// those framework headers.
   unsigned IndexHeaderMapHeader : 1;
 
   /// Whether this file has been looked up as a header.
   unsigned IsValid : 1;
 
-  /// The number of times the file has been included already.
-  unsigned short NumIncludes = 0;
-
   /// The ID number of the controlling macro.
   ///
   /// This ID number will be non-zero when there is a controlling
   /// macro whose IdentifierInfo may not yet have been loaded from
   /// external storage.
   unsigned ControllingMacroID = 0;
 
   /// If this file has a \#ifndef XXX (or equivalent) guard that
void AddFileAlias(const FileEntry *File, StringRef Alias) {
     getFileInfo(File).Aliases.insert(Alias);
   }
 
   /// Mark the specified file as part of a module.
   void MarkFileModuleHeader(const FileEntry *FE,
                             ModuleMap::ModuleHeaderRole Role,
                             bool isCompilingModuleHeader);
 
-  /// Increment the count for the number of times the specified
-  /// FileEntry has been entered.
-  void IncrementIncludeCount(const FileEntry *File) {
-    ++getFileInfo(File).NumIncludes;
-  }
-
   /// Mark the specified file as having a controlling macro.
   ///
   /// This is used by the multiple-include optimization to eliminate
   /// no-op \#includes.
   void SetFileControllingMacro(const FileEntry *File,
                                const IdentifierInfo *ControllingMacro) {
     getFileInfo(File).ControllingMacro = ControllingMacro;
   }

clang/include/clang/Lex/Preprocessor.h

private:
 
   /// The preprocessor state for preprocessing outside of any submodule.
   SubmoduleState NullSubmoduleState;
 
   /// The current submodule state. Will be \p NullSubmoduleState if we're not
   /// in a submodule.
   SubmoduleState *CurSubmoduleState;
 
+  /// The number of times each file was included.
+  llvm::DenseMap<const FileEntry *, unsigned short> IncludedFiles;
+
   /// The set of known macros exported from modules.
   llvm::FoldingSet<ModuleMacro> ModuleMacros;
 
   /// The names of potential module macros that we've not yet processed.
   llvm::SmallVector<const IdentifierInfo *, 32> PendingModuleMacroNames;
 
   /// The list of module macros, for each identifier, that are not overridden by
   /// any other module macro.
public:
   macros(bool IncludeExternalMacros = true) const {
     macro_iterator begin = macro_begin(IncludeExternalMacros);
     macro_iterator end = macro_end(IncludeExternalMacros);
     return llvm::make_range(begin, end);
   }
 
   /// \}
 
+  /// Increment the count for the number of times the specified FileEntry has
+  /// been entered. Returns true if this is the first time it file was included.
+  bool incrementIncludeCount(const FileEntry *File) {
+    auto It = IncludedFiles.insert({File, 0});
+    ++It.first->second;
+    return It.second;
+  }
+
+  /// Return true if this header has already been included.
+  bool alreadyIncluded(const FileEntry *File) const {
+    return IncludedFiles.count(File);
+  }
+
+  /// Get the included files along with the include count.
+  llvm::DenseMap<const FileEntry *, unsigned short> &getIncludedFiles() {
+    return IncludedFiles;
+  }
+  const llvm::DenseMap<const FileEntry *, unsigned short> &
+  getIncludedFiles() const {
+    return IncludedFiles;
+  }
+
   /// Return the name of the macro defined before \p Loc that has
   /// spelling \p Tokens.  If there are multiple macros with same spelling,
   /// return the last one defined.
   StringRef getLastMacroWithSpelling(SourceLocation Loc,
                                      ArrayRef<TokenValue> Tokens) const;
 
   const std::string &getPredefines() const { return Predefines; }
 

clang/include/clang/Serialization/ASTBitCodes.h

enum ASTRecordTypes {
   /// A table of skipped ranges within the preprocessing record.
   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,
 };
 
 /// Record types used within a source manager block.
 enum SourceManagerRecordTypes {
   /// Describes a source location entry (SLocEntry) for a
   /// file.
   SM_SLOC_FILE_ENTRY = 1,
 

clang/include/clang/Serialization/ASTReader.h

private:
 
   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);
   llvm::BitstreamCursor &SLocCursorForID(int ID);
   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,
                        bool Modules);
   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/Lex/HeaderSearch.cpp

HeaderSearch::HeaderSearch(std::shared_ptr<HeaderSearchOptions> HSOpts,
                            const TargetInfo *Target)
     : HSOpts(std::move(HSOpts)), Diags(Diags),
       FileMgr(SourceMgr.getFileManager()), FrameworkMap(64),
       ModMap(SourceMgr, Diags, LangOpts, Target, *this) {}
 
 void HeaderSearch::PrintStats() {
   llvm::errs() << "\n*** HeaderSearch Stats:\n"
                << FileInfo.size() << " files tracked.\n";
-  unsigned NumOnceOnlyFiles = 0, MaxNumIncludes = 0, NumSingleIncludedFiles = 0;
-  for (unsigned i = 0, e = FileInfo.size(); i != e; ++i) {
+  unsigned NumOnceOnlyFiles = 0;
+  for (unsigned i = 0, e = FileInfo.size(); i != e; ++i)
     NumOnceOnlyFiles += (FileInfo[i].isPragmaOnce || FileInfo[i].isImport);
-    if (MaxNumIncludes < FileInfo[i].NumIncludes)
-      MaxNumIncludes = FileInfo[i].NumIncludes;
-    NumSingleIncludedFiles += FileInfo[i].NumIncludes == 1;
-  }
-  llvm::errs() << "  " << NumOnceOnlyFiles << " #import/#pragma once files.\n"
-               << "  " << NumSingleIncludedFiles << " included exactly once.\n"
-               << "  " << MaxNumIncludes << " max times a file is included.\n";
+  llvm::errs() << "  " << NumOnceOnlyFiles << " #import/#pragma once files.\n";
 
   llvm::errs() << "  " << NumIncluded << " #include/#include_next/#import.\n"
                << "    " << NumMultiIncludeFileOptzn
                << " #includes skipped due to the multi-include optimization.\n";
 
   llvm::errs() << NumFrameworkLookups << " framework lookups.\n"
                << NumSubFrameworkLookups << " subframework lookups.\n";
 }

 /// header file info (\p HFI)
 static void mergeHeaderFileInfo(HeaderFileInfo &HFI,
                                 const HeaderFileInfo &OtherHFI) {
   assert(OtherHFI.External && "expected to merge external HFI");
 
   HFI.isImport |= OtherHFI.isImport;
   HFI.isPragmaOnce |= OtherHFI.isPragmaOnce;
   HFI.isModuleHeader |= OtherHFI.isModuleHeader;
-  HFI.NumIncludes += OtherHFI.NumIncludes;
 
   if (!HFI.ControllingMacro && !HFI.ControllingMacroID) {
     HFI.ControllingMacro = OtherHFI.ControllingMacro;
     HFI.ControllingMacroID = OtherHFI.ControllingMacroID;
   }
 
   HFI.DirInfo = OtherHFI.DirInfo;
   HFI.External = (!HFI.IsValid || HFI.External);
bool HeaderSearch::ShouldEnterIncludeFile(bool &IsFirstIncludeOfFile,
 
   // If this is a #import directive, check that we have not already imported
   // this header.
   if (isImport) {
     // If this has already been imported, don't import it again.
     FileInfo.isImport = true;
 
     // Has this already been #import'ed or #include'd?
-    if (FileInfo.NumIncludes && !TryEnterImported())
+    if (PP.alreadyIncluded(File) && !TryEnterImported())
       return false;
   } else {
     // Otherwise, if this is a #include of a file that was previously #import'd
     // or if this is the second #include of a #pragma once file, ignore it.
     if ((FileInfo.isPragmaOnce || FileInfo.isImport) && !TryEnterImported())
       return false;
   }
 
   // Next, check to see if the file is wrapped with #ifndef guards.  If so, and
   // if the macro that guards it is defined, we know the #include has no effect.
   if (const IdentifierInfo *ControllingMacro
       = FileInfo.getControllingMacro(ExternalLookup)) {
     // If the header corresponds to a module, check whether the macro is already
     // defined in that module rather than checking in the current set of visible
     // modules.
     if (M ? PP.isMacroDefinedInLocalModule(ControllingMacro, M)
           : PP.isMacroDefined(ControllingMacro)) {
       ++NumMultiIncludeFileOptzn;
       return false;
     }
   }
 
-  // Increment the number of times this file has been included.
-  ++FileInfo.NumIncludes;
-
-  IsFirstIncludeOfFile = FileInfo.NumIncludes == 1;
+  IsFirstIncludeOfFile = PP.incrementIncludeCount(File);
 
   return true;
 }
 
 size_t HeaderSearch::getTotalMemory() const {
   return SearchDirs.capacity()
     + llvm::capacity_in_bytes(FileInfo)
     + llvm::capacity_in_bytes(HeaderMaps)

clang/lib/Lex/PPDirectives.cpp

Preprocessor::ImportAction Preprocessor::HandleHeaderIncludeOrImport(
 
   if (PPOpts->SingleFileParseMode)
     Action = IncludeLimitReached;
 
   // If we've reached the max allowed include depth, it is usually due to an
   // include cycle. Don't enter already processed files again as it can lead to
   // reaching the max allowed include depth again.
   if (Action == Enter && HasReachedMaxIncludeDepth && File &&
-      HeaderInfo.getFileInfo(&File->getFileEntry()).NumIncludes)
+      alreadyIncluded(*File))
     Action = IncludeLimitReached;
 
   // Determine whether we should try to import the module for this #include, if
   // there is one. Don't do so if precompiled module support is disabled or we
   // are processing this module textually (because we're building the module).
   if (Action == Enter && File && SuggestedModule && getLangOpts().Modules &&
       !isForModuleBuilding(SuggestedModule.getModule(),
                            getLangOpts().CurrentModule,

clang/lib/Lex/Preprocessor.cpp

void Preprocessor::PrintStats() {
 
   llvm::errs() << NumMacroExpanded << "/" << NumFnMacroExpanded << "/"
              << NumBuiltinMacroExpanded << " obj/fn/builtin macros expanded, "
              << NumFastMacroExpanded << " on the fast path.\n";
   llvm::errs() << (NumFastTokenPaste+NumTokenPaste)
              << " token paste (##) operations performed, "
              << NumFastTokenPaste << " on the fast path.\n";
 
+  unsigned MaxNumIncludes = 0, NumSingleIncludedFiles = 0;
+  for (const auto &IncludedFile : IncludedFiles) {
+    if (MaxNumIncludes < IncludedFile.second)
+      MaxNumIncludes = IncludedFile.second;
+    NumSingleIncludedFiles += IncludedFile.second == 1;
+  }
+  llvm::errs() << NumSingleIncludedFiles << " included exactly once.\n"
+               << MaxNumIncludes << " max times a file is included.\n";
+
   llvm::errs() << "\nPreprocessor Memory: " << getTotalMemory() << "B total";
 
   llvm::errs() << "\n  BumpPtr: " << BP.getTotalMemory();
   llvm::errs() << "\n  Macro Expanded Tokens: "
                << llvm::capacity_in_bytes(MacroExpandedTokens);
   llvm::errs() << "\n  Predefines Buffer: " << Predefines.capacity();
   // FIXME: List information for all submodules.
   llvm::errs() << "\n  Macros: "
if (!SourceMgr.isLoadedFileID(MainFileID)) {
     // If we've been asked to skip bytes in the main file (e.g., as part of a
     // precompiled preamble), do so now.
     if (SkipMainFilePreamble.first > 0)
       CurLexer->SetByteOffset(SkipMainFilePreamble.first,
                               SkipMainFilePreamble.second);
 
     // Tell the header info that the main file was entered.  If the file is later
     // #imported, it won't be re-entered.
-    if (const FileEntry *FE = SourceMgr.getFileEntryForID(MainFileID))
-      HeaderInfo.IncrementIncludeCount(FE);
+    if (const FileEntry *FE = SourceMgr.getFileEntryForID(MainFileID)) {
+      HeaderInfo.getFileInfo(FE);
+      incrementIncludeCount(FE);
+    }
   }
 
   // Preprocess Predefines to populate the initial preprocessor state.
   std::unique_ptr<llvm::MemoryBuffer> SB =
     llvm::MemoryBuffer::getMemBufferCopy(Predefines, "<built-in>");
   assert(SB && "Cannot create predefined source buffer");
   FileID FID = SourceMgr.createFileID(std::move(SB));
   assert(FID.isValid() && "Could not create FileID for predefines?");

clang/lib/Serialization/ASTReader.cpp

HeaderFileInfoTrait::ReadData(internal_key_ref key, const unsigned char *d,
   const unsigned char *End = d + DataLen;
   HeaderFileInfo HFI;
   unsigned Flags = *d++;
   // 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;
-  // FIXME: Find a better way to handle this. Maybe just store a
-  // "has been included" flag?
-  HFI.NumIncludes = std::max(endian::readNext<uint16_t, little, unaligned>(d),
-                             HFI.NumIncludes);
   HFI.ControllingMacroID = Reader.getGlobalIdentifierID(
       M, endian::readNext<uint32_t, little, unaligned>(d));
   if (unsigned FrameworkOffset =
           endian::readNext<uint32_t, little, unaligned>(d)) {
     // The framework offset is 1 greater than the actual offset,
     // since 0 is used as an indicator for "no framework name".
     StringRef FrameworkName(FrameworkStrings + FrameworkOffset - 1);
     HFI.Framework = HS->getUniqueFrameworkName(FrameworkName);
case INPUT_FILE_OFFSETS:
           (const llvm::support::unaligned_uint64_t *)Blob.data();
       F.InputFilesLoaded.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) {
+    auto InputFileID = endian::readNext<uint32_t, little, unaligned>(D);
+    auto NumIncludes = endian::readNext<uint16_t, little, unaligned>(D);
+
+    auto InputFileInfo = readInputFileInfo(F, InputFileID);
+    if (auto File = PP.getFileManager().getFile(InputFileInfo.Filename)) {
+      unsigned short &PPNumIncludes = PP.getIncludedFiles()[*File];
+      PPNumIncludes = std::max(PPNumIncludes, NumIncludes);
+    }
+  }
+}
+
 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/ASTWriter.cpp

#define RECORD(X) EmitRecordID(X, #X, Stream, Record)
 
   // Preprocessor Block.
   BLOCK(PREPROCESSOR_BLOCK);
   RECORD(PP_MACRO_DIRECTIVE_HISTORY);
   RECORD(PP_MACRO_FUNCTION_LIKE);
   RECORD(PP_MACRO_OBJECT_LIKE);
   RECORD(PP_MODULE_MACRO);
   RECORD(PP_TOKEN);
 
   // Submodule Block.
   BLOCK(SUBMODULE_BLOCK);
   RECORD(SUBMODULE_METADATA);
   RECORD(SUBMODULE_DEFINITION);
   RECORD(SUBMODULE_UMBRELLA_HEADER);
   RECORD(SUBMODULE_HEADER);
   RECORD(SUBMODULE_TOPHEADER);
   RECORD(SUBMODULE_UMBRELLA_DIR);
hash_value_type ComputeHash(key_type_ref key) {
       // match even when symlinking or excess path elements ("foo/../", "../")
       // change the form of the name. However, complete path is still the key.
       return llvm::hash_combine(key.Size, key.ModTime);
     }
 
     std::pair<unsigned, unsigned>
     EmitKeyDataLength(raw_ostream& Out, key_type_ref key, data_type_ref Data) {
       unsigned KeyLen = key.Filename.size() + 1 + 8 + 8;
-      unsigned DataLen = 1 + 2 + 4 + 4;
+      unsigned DataLen = 1 + 4 + 4;
       for (auto ModInfo : Data.KnownHeaders)
         if (Writer.getLocalOrImportedSubmoduleID(ModInfo.getModule()))
           DataLen += 4;
       if (Data.Unresolved.getPointer())
         DataLen += 4;
       return emitULEBKeyDataLength(KeyLen, DataLen, Out);
     }
 
void EmitData(raw_ostream &Out, key_type_ref key,
       endian::Writer LE(Out, little);
       uint64_t Start = Out.tell(); (void)Start;
 
       unsigned char Flags = (Data.HFI.isImport << 5)
                           | (Data.HFI.isPragmaOnce << 4)
                           | (Data.HFI.DirInfo << 1)
                           | Data.HFI.IndexHeaderMapHeader;
       LE.write<uint8_t>(Flags);
-      LE.write<uint16_t>(Data.HFI.NumIncludes);
 
       if (!Data.HFI.ControllingMacro)
         LE.write<uint32_t>(Data.HFI.ControllingMacroID);
       else
         LE.write<uint32_t>(Writer.getIdentifierRef(Data.HFI.ControllingMacro));
 
       unsigned Offset = 0;
       if (!Data.HFI.Framework.empty()) {
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;
+
+  std::vector<std::pair<uint32_t, unsigned short>> IncludedInputFiles;
+  for (const auto &File : PP.getIncludedFiles()) {
+    auto InputFileIt = InputFileIDs.find(File.first);
+    if (InputFileIt != InputFileIDs.end())
+      IncludedInputFiles.emplace_back(InputFileIt->second, File.second);
+  }
+
+  llvm::sort(IncludedInputFiles);
+
+  endian::Writer LE(Out, little);
+  LE.write<uint32_t>(IncludedInputFiles.size());
+
+  for (const auto &IncludedInputFile : IncludedInputFiles) {
+    LE.write<uint32_t>(IncludedInputFile.first);
+    LE.write<uint16_t>(IncludedInputFile.second);
+  }
+}
+
 /// 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;