[clang][modules] Track included files per submodule

[jansvoboda11]

Summary

When building a module consisting of submodules, the preprocessor keeps a "global" state that for each header file tracks (amongst other things) the number of times it was included/imported. This information is serialized into the PCM file.

When importing anything from such module (either the top-level module or any of its submodules), this number is merged into the state of the importing preprocessor.

This can incorrectly prevent imports of textual headers (see attached tests). This patch fixes this bug by making the number of times a header was included more fine-grained and tracks it on per-submodule basis. This information is lazily deserialized when first importing each (sub)module.

(This patch is an alternative approach to the same issue addressed in D104344.)

Depends on D114095.

[jansvoboda11]

I'm interested in hearing some feedback whether the direction I'm taking here makes sense.

There are a couple of TODOs (mostly on optimizing away unnecessary maps) and a few modules-ts tests are failing.

@rsmith left a suggestion on D104344 to track this information in Preprocessor::SubmoduleState, which has similar semantics to what I'm doing with Preprocessor::IncludeMap (dividing the state during submodule compilation). The issue is that it (Preprocessor::Submodules) is really only enabled when Clang gets invoked with -fmodules-local-submodule-visibility. To keep its current semantics and make it usable for our use-case (which needs to work even without the flag), I think we'd need to always track the submodule state and conditionally merge the outer and local macro states as we now do for IncludeMap in PPLexerChange.cpp. I'm not really sure this is correct/feasible.

Any opinions on this?

[vsapsai]

I'm not going to cover the entire change, some parts I need to consider more carefully.

There can be other reasons to keep IncludeMap out of SubmoduleState but I'm not sure the local submodule visibility is the right reason. I might be reading the code incorrectly but looks like CurSubmoduleState is used when local submodule visibility is disabled. The difference is it's tracking the aggregate state instead of per-submodule state. Need to experiment more but so far tracking includes in SubmoduleState follows the spirit of local submodule visibility. Though it's not guaranteed it'll work perfectly from the technical perspective.

Also I think we'll need to increase granularity to track other HeaderFileInfo attributes, not just NumIncludes. Don't have a test case to illustrate that right now and no need to change that now but something to keep in mind.

clang/lib/Lex/PPLexerChange.cpp

699

How many includes are expected to be here? Are this only immediate includes or also transitive?

Asking to evaluate how expensive iterating through the includes can get.

[jansvoboda11]

Avoid copying data between submodules

[jansvoboda11]

In D112915#3104873, @vsapsai wrote:

There can be other reasons to keep IncludeMap out of SubmoduleState but I'm not sure the local submodule visibility is the right reason. I might be reading the code incorrectly but looks like CurSubmoduleState is used when local submodule visibility is disabled. The difference is it's tracking the aggregate state instead of per-submodule state. Need to experiment more but so far tracking includes in SubmoduleState follows the spirit of local submodule visibility. Though it's not guaranteed it'll work perfectly from the technical perspective.

Yes, CurSubmoduleState is being used unconditionally. However, without local submodule visibility enabled, it always points to NullSubmoduleState. Only with the feature enabled does it point to the current submodule state (stored in Submodules). The change happens in Preprocessor::{Enter,Leave}Submodule.

Also I think we'll need to increase granularity to track other HeaderFileInfo attributes, not just NumIncludes. Don't have a test case to illustrate that right now and no need to change that now but something to keep in mind.

That's interesting. I think HeaderFileInfo::isImport should definitely be tracked in the preprocessor, not in HeaderFileInfo. The fact that the header was #imported is not an intrinsic property of the file itself, but rather a preprocessor state. Can you think of other fields that don't really belong to HeaderFileInfo?

Based on your feedback, I simplified the patch quite a bit. We're no longer copying the include state between submodules. In its current form, this patch essentially moves HeaderFileInfo::NumIncludes into Preprocessor::NumIncludes and still uses it as the source of truth.
However, we're also tracking NumIncludes separately in each submodule and serializing this into the PCM. Instead of merging NumIncludes of the whole module when loading it (which we did before), we can merge NumIncludes only of the modules we actually import.

clang/lib/Lex/Preprocessor.cpp

1322

Iterating over all FileEntries is probably not very efficient, as Volodymyr mentioned. Thinking about how to make this more efficient...

[dexonsmith]

Just a few comments on implementation details. The only high-level piece to call out is that I wonder if NumIncludes could/should be simplified (semantically) to a Boolean in a prep commit.

clang/include/clang/Lex/Preprocessor.h

720–723

I'm not sure about this choice. UIDs are unlikely to be adjacent and in SubmoduleIncludeState, since a given submodule is unlikely to have "most" files. Also, memory usage characteristics could be "weird" if the FileManager is being reused between different compilations.

DenseMap<unsigned, unsigned> will have the same number of allocations (i.e., just 1). If UIDs really are dense and near each other in one of the submodules then that map will be a little bigger than necessary (~2x), but it should be better for the rest of them.

clang/lib/Lex/Preprocessor.cpp

1322

My suggestion above to drop FileEntryMap in favour of a simple DenseMap would help a bit, just iterating through the files actually included by the submodules.

Further, I wonder if "num-includes"/file/submodule (unsigned) is actually useful, vs. "was-included"/file/submodule (bool). The only observer I see is HeaderSearch::PrintStats() but maybe I missed something?

If I'm right and we can switch to bool, then NumIncludes becomes a DenseSet<FileEntry *> IncludedFiles (or DenseSet<unsigned> for UIDs). (BTW, I also wondered if you could rotate the map, using File as the outer key, and then use bitsets for the sbumodules, but I doubt this is better, since most files are only included by a few submodules, right?)

Then you can just do a set union here. Also simplifies bitcode serialization.

(If a bool/set is sufficient, then I'd suggest landing that first/separately, before adding the per-submodule granularity in this patch.)

clang/lib/Serialization/ASTWriter.cpp

2392–2393

A vector of maps would be an improvement, but that'll still be a lot of allocations.

• Since insertion/lookup/deletion aren't intermingled, the simplest way to avoid adding unnecessary overhead is a sorted vector (https://llvm.org/docs/ProgrammersManual.html#dss-sortedvectormap).
• With no lookups (at all), there's no benefit to a tiered data structure (vs flat).

Leading me toward a simple flat vector + sort.

struct IncludeToSerialize { // Probably more straightforward than a std::tuple...
  StringRef Filename;
  unsigned SMID;
  unsigned NumIncludes;

  bool operator<(const IncludeToSerialize &RHS) const {
    if (SMID != RHS.SMID)
      return SMID < RHS.SMID;
    int Diff = Filename.compare(RHS.Filename);
    assert(Diff && "Expected unique SMID / Filename pairs");
    return Diff < 0;
  }
};
SmallVector<IncludeToSerialize> IncludesToSerialize;
// ...
    IncludesToSerialize.push_back({Filename, LocalSMID, NumIncludes});
// ...
llvm::sort(IncludesToSerialize);
for (const IncludeToSerialize &SI : IncludesToSerialize) {
  // emit record
}

(Or if there are duplicates expected to be encountered and ignored, you can remove the assertion and use stable_sort + unique + erase.)

2418

I wonder, will the Filename already be serialized elsewhere? Could an ID from that be reused here, rather than writing the filename again? (Maybe that'd need a bigger refactor of some sort to create a filename table?)

Stepping back, it looks like this is always eagerly loaded.

• Could it be lazily-loaded by submodule?
• Could it be lazily-loaded by filename?

In the former case, seems like a single record per submodule makes sense, with a single blob that can be decoded on-demand.

In the latter case, maybe it should be rotated, and stored a single record per filename as a blob that can be lazily decoded:

<filename-size> <filename> <num-submodules> (<smid> <num-includes>)+

[vsapsai]

In D112915#3106472, @jansvoboda11 wrote:

That's interesting. I think HeaderFileInfo::isImport should definitely be tracked in the preprocessor, not in HeaderFileInfo. The fact that the header was #imported is not an intrinsic property of the file itself, but rather a preprocessor state. Can you think of other fields that don't really belong to HeaderFileInfo?

After checking HeaderFileInfo, looks like isImport is the only other field that should be tracked in the preprocessor. I had in mind a case where a hidden submodule imports a file with x-macros and then a visible submodule includes this header twice with different macros. First include would go through because NumIncludes == 0, and the second one shouldn't because NumIncludes == 1 && isImport == true. The import in the hidden submodule is incorrect but errors in unused headers shouldn't break actually used headers.

[jansvoboda11]

Call getFileInfo in Preprocessor::EnterMainSourceFile. This ensures deserialization of HeaderFileInfo, which seems to be necessary with modules-ts enabled.

[jansvoboda11]

Fix deserialization, improve (sub)module state tracking

[jansvoboda11]

Make loading of (sub)module includes lazy

[jansvoboda11]

Thanks for your feedback @dexonsmith. I reworked the patch to use more sensible data structures as suggested, and made the AST deserialization lazy (on (sub)module import).

I think the only thing to figure out is the exact structure of the serialized information - whether we're fine with serializing all transitively included files in each AST file, or whether we'd like to fetch that information from other AST files instead.

I removed the WIP tag and would be happy to gather more feedback.

clang/include/clang/Lex/Preprocessor.h

720–723

You're right that UIDs of files included in a single submodule are unlikely to have "most" files. Thanks for pointing that out.

In the latest revision, I switched to llvm::DenseMap<const FileEntry *, unsigned>.

clang/lib/Lex/Preprocessor.cpp

1322

For each file, we need to have three distinct states: not included at all, included exactly once (firstTimeLexingFile), included more than once. This means we can't use a single DenseSet.

But we could use a DenseMap<Key, bool>, where "not included at all" can be expressed as being absent from the map, exactly once as having true in the map and more than once as having false in the map. Alternatively, we could use two DenseSet instances to encode the same, but I don't think having two lookups per file to determine stuff is efficient.

I can look into this in a follow-up patch.

clang/lib/Serialization/ASTWriter.cpp

2392–2393

In the latest revision, I ended up sorting just based on Filename, since this is now explicitly stored per submodule.

2418

We already serialize Filename elsewhere, but only for local input files. Here we need transitive closure of all included input files.

I'm still unsure whether it's fine to store transitively included files here or if we should look that information up in the respective AST files.

The current solution looks like it will bloat sizes of the AST files, but I think the transitive closure is already being stored for HeaderFileInfo anyways, so it shouldn't be that big of a deal?

2418

Thinking about it some more, the current implementation will be duplicating a lot of filenames between submodules of the same module. We might need to extract that to some common storage that we can refer to with simple integer offsets...

[jansvoboda11]

Make clang-format happy.

[jansvoboda11]

Store only direct includes in the PCM (compared to transitive stored previously), use InputFile ID (instead of full filesystem path).

Also: add test of transitive includes, fix bug in VisibleModuleSet::setVisible.

[dexonsmith]

Implementation looks a lot cleaner!

I'd still like to drop NumIncludes first if possible because I think it'll be easier to reason about without this extra layer of complexity. Also, that'd mitigate the potential regression in .pcm size.

(Note: I'd be more comfortable with @vsapsai and/or @rsmith reviewing the overall direction; I just jumped in for the implementation details.)

clang/include/clang/Lex/HeaderSearch.h

133–139

Looks like this is already dead code? If so, please separate out and commit ahead of time (e.g., now).

clang/include/clang/Serialization/ModuleFile.h

399 ↗

(On Diff #386139)

Each StringMapEntry is going to have a pretty big allocation here, for a 512B vector. Given that it doesn't need to be after creation, it'd be more efficient to use this pattern:

llvm::StringMap<ArrayRef<uint64_t>> SubmoduleIncludedFiles;
SpecificBumpPtrAlloc<uint64_t> SubmoduleIncludedFilesAlloc;

// later
MutableArrayRef<uint64_t> Files(SubmoduleIncludedFiles.Allocate(Record.size()), Record.size());
llvm::copy(Record, Files.begin());
SubmoduleIncludedFiles[Key] = Files;

That said, I feel like this should just be:

DenseMap<StringRef, StringRef> SubmoduleIncludedFiles;

The key can point at the name of the submodule, which must already exist somewhere without needing a StringMap to create a new copy of it. The value is a lazily deserialized blob.

clang/lib/Lex/Preprocessor.cpp

1322

Seems like a DenseSet could still be used by having HeaderInfo pass back the WasInserted bit from the insertion to the preprocessor, and threading it through to Preprocessor::HandleEndOfFile (the only caller of FirstTimeLexingFile):

bool IsFirst = Set.insert(Key).second;

The threading doesn't seem too hard. Looking at main:

• Preprocessor::HandleHeaderIncludeOrImport calls HeaderInfo::ShouldEnterIncludeFile. This does the ++FI.NumIncludes (going from 0 to 1). Instead, it could be IsFirst = !FI.WasIncluded; FI.WasIncluded = true;, then return IsFirst somehow. (Then your patch can pull IsFirst from the insert().second).
• Preprocessor::HandleHeaderIncludeOrImport calls Preprocessor::EnterSourceFile. This creates a new Lexer for that file. IsFirst can be stored on that Lexer.
• Preprocessor::HandleEndOfFile calls FirstTimeLexingFile. Instead, it can check the new accessor CurLexer->isFirstTimeLexing().

I can look into this in a follow-up patch.

Follow-up might be okay, but it'd be nice to remove an axis of complexity before adding a new one if it's reasonable. E.g., it'll be easier to debug emergent issues from changing it to a simple set since there's less machinery to worry about.

clang/lib/Serialization/ASTReader.cpp

5736–5738

This looks lazy, but a bunch of work was just done to decode the Record from bitcode. To make this actually lazy, you can encode the data in a blob, which doesn't have to be decoded until it's used.

clang/lib/Serialization/ASTWriter.cpp

2175–2179

Why does the count need to be encoded?

The only observer is Preprocessor::HandleEndOfFile. If it gets called again for this file, it'll be after ++NumIncludes.

[vsapsai]

As we've discussed earlier, tracking isImport shouldn't be done per .pcm and here is the test case https://gist.github.com/vsapsai/a2d2bd19c54c24540495fd9b262106aa I'm not sure it is worth adding the second #include as the test fails just with one.

Overall, the change seems more complicated than it has to be. I need to check it carefully to see what can be simplified. And I need to check in debugger how and when AST reading is triggered. Looks like not all of that is lazy but I need to check the compiled code, not my guesses.

[vsapsai]

Didn't go in-depth for serialization/deserialization. When we add tracking isImport on per-submodule basis, do you think AST reading/writing would change significantly?

clang/include/clang/Lex/ExternalPreprocessorSource.h

45 ↗

(On Diff #386139)

I think it is better for understanding and more convenient to use some using instead of duplicating llvm::DenseMap<const FileEntry *, unsigned> in multiple places.

clang/include/clang/Lex/Preprocessor.h

782–788

I think the interplay between CurSubmoduleIncludeState, IncludedFiles, and CurSubmoduleState is pretty complicated. Recently I've realized that it can be beneficial to distinguish include tracking for the purpose of serializing per submodule and for the purpose of deciding if should enter a file. In D114051 I've tried to illustrate this approach. There are some tests failing but hope the main idea is still understandable.

One of my big concerns is tracking VisibleModules in multiple places. D114051 demonstrates one of the ways to deal with it but I think it is more important for you to know the problem I was trying to solve, not the solution I came up with.

clang/lib/Basic/Module.cpp

653 ↗

(On Diff #386139)

Was meaning to make this fix for a long time but couldn't test it. Thanks for finally fixing it!

clang/lib/Lex/Preprocessor.cpp

1321

If I drop checking getLocalSubmoduleIncludes, no tests are failing. But it seems like this call is required. How can we test it?

[jansvoboda11]

Rebase on top of extracted patches.

[jansvoboda11]

In D112915#3122340, @dexonsmith wrote:

Implementation looks a lot cleaner!

I'd still like to drop NumIncludes first if possible because I think it'll be easier to reason about without this extra layer of complexity. Also, that'd mitigate the potential regression in .pcm size.

Done in D114096. Thanks for the feedback.

clang/include/clang/Lex/HeaderSearch.h

133–139

Done in D114092.

clang/include/clang/Serialization/ModuleFile.h

399 ↗

(On Diff #386139)

I switched to StringRef value in the latest revision. Unfortunately, had to use std::string as the key instead of StringRef, since getFullModuleName constructs the string on heap. That forced me to use std::map, too. I'll explore using something else entirely as the key.

clang/lib/Lex/Preprocessor.cpp

1322

Extracted into D114093.

[jansvoboda11]

In D112915#3136492, @vsapsai wrote:

Didn't go in-depth for serialization/deserialization. When we add tracking isImport on per-submodule basis, do you think AST reading/writing would change significantly?

I think moving isImport into Preprocessor can be done in a similar way to how we handle the number of includes (or rather "has been included/imported" behavior), so we should be able to reuse some parts of this patch there.

One question that remains to be answered is whether to keep two separate DenseSet<const FileEntry *> instances, or merge them into something like:

struct IncludeInfo {
  bool IsImportedOrIncluded; // currently Preprocessor::IncludedFiles
  bool IsImported;           // currently HeaderFileInfo::isImport
}
llvm::DenseMap<const FileEntry *, IncludeInfo> IncludedFilesInfo;

Thanks a lot for the feedback, I appreciate it.

clang/include/clang/Lex/ExternalPreprocessorSource.h

45 ↗

(On Diff #386139)

Yeah, spelling the type out everywhere is a bit unwieldy. It's a bit better with llvm::DenseSet<const FileEntry *> in the latest revision, but still not pretty. I wanted to avoid pulling Preprocessor.h everywhere, but will probably reconsider doing that.

clang/include/clang/Lex/Preprocessor.h

782–788

Thanks a ton, this must've taken quite a bit of time to put together. I agree your approach is much simpler. I'll investigate how it behaves on larger projects, but probably will end up adopting it in this patch.

I have done some minor tweaks locally to fix the failing PCH tests, Modules/import-textual-noguard.mm doesn't make much sense to me, I think I'll end up updating that test.

clang/lib/Lex/Preprocessor.cpp

1321

I think this should kick in when importing a submodule from the same module. I'll try to come up with a test case.

[dexonsmith]

clang/include/clang/Serialization/ModuleFile.h

399 ↗

(On Diff #386139)

Oh, if the key isn't being kept alive elsewhere, you can/should use StringMap<StringRef>, which is strictly better than std::map<std::string, StringRef> (except for non-deterministic iteration order). I suggested otherwise because I assumed the key already existed.

Also, if the map isn't being deleted from (much), might as well bump-ptr-allocate it:

BumpPtrAllocator SubmoduleIncludedFilesAlloc;
StringMap<StringRef, BumpPtrAllocator> SubmoduleIncludedFiles; // iniitalized with teh Alloc above.

I'll explore using something else entirely as the key.

Not necessarily important; just if the key was already (e.g., stored in its Module or something) you might as well use it. Unless, maybe if the Module is known to be constructed already, you could use its address?

399 ↗

(On Diff #386139)

I switched to StringRef value in the latest revision. Unfortunately, had to use std::string as the key instead of StringRef, since getFullModuleName constructs the string on heap. That forced me to use std::map, too. I'll explore using something else entirely as the key.

[jansvoboda11]

Rebase, add type alias, improve map allocation in ASTReader.

[jansvoboda11]

Apply part of Volodymyr's cleanup.

[jansvoboda11]

Add missed newline.

[vsapsai]

I think AST format for IncludedFiles was discussed here, so I'll continue here though the bulk of implementation is in D114095 now. Have you compared the size of resulting .pcm files when you are using a bitvector compared to a list of included headers? In my quick check (which is not a perfect comparison, to be honest) bitvector approach takes more space. For example, Darwin.pcm is 7320 bytes bigger, UIKit.pcm is 2388 bytes bigger, and entire modules cache is 14KB bigger. I haven't checked the details of the discrepancies, so curious if you have some insights already. For the record, I was testing with

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

[jansvoboda11]

Rebase

[jansvoboda11]

In D112915#3141417, @vsapsai wrote:

I think AST format for IncludedFiles was discussed here, so I'll continue here though the bulk of implementation is in D114095 now. Have you compared the size of resulting .pcm files when you are using a bitvector compared to a list of included headers? In my quick check (which is not a perfect comparison, to be honest) bitvector approach takes more space. For example, Darwin.pcm is 7320 bytes bigger, UIKit.pcm is 2388 bytes bigger, and entire modules cache is 14KB bigger. I haven't checked the details of the discrepancies, so curious if you have some insights already. For the record, I was testing with

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

Replied in D114095.

[vsapsai]

Can you please rebase this change after D114095 lands? Overall looks good but I want to take one final look and triggering the pre-merge checks will be useful.

[jansvoboda11]

Rebase, update unnecessary auto, run clang-format

[vsapsai]

clang/include/clang/Lex/Preprocessor.h

1252–1261

Was curious why getNullSubmoduleIncludes isn't getLocalSubmoduleIncludes(nullptr)? If we want to have separate methods and implementations, it might be useful to assert M isn't null in getLocalSubmoduleIncludes.

clang/lib/Serialization/ASTReader.cpp

8618

Can you please check again the returned pointer doesn't end up as a dangling pointer? I don't think we store the pointer anywhere, which is good. My bigger concern is if we can invalidate SubmoduleIncludedFiles iterator while working with the returned pointer. I haven't found any indication of that but would like somebody else to check that.

clang/include/clang/Lex/HeaderSearch.h

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
HeaderFileInfo()
       : isImport(false), isPragmaOnce(false), DirInfo(SrcMgr::C_User),
         External(false), isModuleHeader(false), isCompilingModuleHeader(false),
         Resolved(false), IndexHeaderMapHeader(false), IsValid(false)  {}
 
   /// Retrieve the controlling macro for this header file, if
   /// any.
   const IdentifierInfo *
   getControllingMacro(ExternalPreprocessorSource *External);
-
-  /// Determine whether this is a non-default header file info, e.g.,
-  /// it corresponds to an actual header we've included or tried to include.
-  bool isNonDefault() const {
-    return isImport || isPragmaOnce || NumIncludes || ControllingMacro ||
-      ControllingMacroID;
-  }
 };
 
 /// An external source of header file information, which may supply
 /// information about header files already included.
 class ExternalHeaderFileInfoSource {
 public:
   virtual ~ExternalHeaderFileInfoSource();
 
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;
   }
 
-  /// Return true if this is the first time encountering this header.
-  bool FirstTimeLexingFile(const FileEntry *File) {
-    return getFileInfo(File).NumIncludes == 1;
-  }
-
   /// Determine whether this file is intended to be safe from
   /// multiple inclusions, e.g., it has \#pragma once or a controlling
   /// macro.
   ///
   /// This routine does not consider the effect of \#import
   bool isFileMultipleIncludeGuarded(const FileEntry *File);
 
   /// Determine whether the given file is known to have ever been \#imported.

clang/include/clang/Lex/Preprocessor.h

private:
 
   /// For each IdentifierInfo that was associated with a macro, we
   /// keep a mapping to the history of all macro definitions and #undefs in
   /// the reverse order (the latest one is in the head of the list).
   ///
   /// This mapping lives within the \p CurSubmoduleState.
   using MacroMap = llvm::DenseMap<const IdentifierInfo *, MacroState>;
 
+  /// For each included header file, we keep a mapping to the number of times it
+  /// was included.
+  struct IncludeMap {
+    // TODO: Store this in a vector indexed by the FileEntry UID.
+    llvm::DenseMap<const FileEntry *, unsigned> LocalIncludes;
+    llvm::DenseMap<const FileEntry *, unsigned> OuterIncludes;
+  };
+
   struct SubmoduleState;
 
   /// Information about a submodule that we're currently building.
   struct BuildingSubmoduleInfo {
     /// The module that we are building.
     Module *M;
 
     /// The location at which the module was included.
     SourceLocation ImportLoc;
 
     /// Whether we entered this submodule via a pragma.
     bool IsPragma;
 
     /// The previous SubmoduleState.
     SubmoduleState *OuterSubmoduleState;
 
     /// The number of pending module macro names when we started building this.
     unsigned OuterPendingModuleMacroNames;
 
+    /// The previous IncludeMap.
+    IncludeMap *OuterSubmoduleIncludes;
+
     BuildingSubmoduleInfo(Module *M, SourceLocation ImportLoc, bool IsPragma,
                           SubmoduleState *OuterSubmoduleState,
-                          unsigned OuterPendingModuleMacroNames)
+                          unsigned OuterPendingModuleMacroNames,
+                          IncludeMap *OuterSubmoduleIncludes)
         : M(M), ImportLoc(ImportLoc), IsPragma(IsPragma),
           OuterSubmoduleState(OuterSubmoduleState),
-          OuterPendingModuleMacroNames(OuterPendingModuleMacroNames) {}
+          OuterPendingModuleMacroNames(OuterPendingModuleMacroNames),
+          OuterSubmoduleIncludes(OuterSubmoduleIncludes) {}
   };
   SmallVector<BuildingSubmoduleInfo, 8> BuildingSubmoduleStack;
 
   /// Information about a submodule's preprocessor state.
   struct SubmoduleState {
     /// The macros for the submodule.
     MacroMap Macros;
 
     /// The set of modules that are visible within the submodule.
     VisibleModuleSet VisibleModules;
 
     // FIXME: CounterValue?
     // FIXME: PragmaPushMacroInfo?
   };
   std::map<Module *, SubmoduleState> Submodules;
 
   /// 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;
 
+  /// Include maps of each entered submodule.
+  std::map<Module *, IncludeMap> SubmoduleIncludeMaps;
+
+  /// The root include map.
+  IncludeMap RootIncludeMap;
+
+  /// The current include map. Will be \p RootIncludeMap if we're not in a
+  /// submodule.
+  IncludeMap *CurIncludeMap;
+
   /// 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);
   }
 
   /// \}
 
+  /// Return true if this is the first time encountering this header.
+  bool FirstTimeLexingFile(const FileEntry *File) const;
+
+  /// Return the number of times the given file has been entered.
+  unsigned NumIncludes(const FileEntry *File) const;
+
+  /// Increment the count for the number of times the specified
+  /// FileEntry has been entered.
+  void IncrementIncludeCount(const FileEntry *File);
+
+  /// Get the submodule include information.
+  const std::map<Module *, IncludeMap> &getSubmoduleIncludes() const {
+    return SubmoduleIncludeMaps;
+  }
+
+  /// Get the root include information.
+  const IncludeMap &getRootIncludes() const { return RootIncludeMap; }
+
+  /// Add a submodule include.
+  void addSubmoduleInclude(Module *M, StringRef Filename, unsigned NumIncludes);
+
   /// 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 submodule includes.
+  INCLUDES = 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:
   SmallVector<serialization::DeclID, 2> CUDASpecialDeclRefs;
 
   /// The floating point pragma option settings.
   SmallVector<uint64_t, 1> FPPragmaOptions;
 
   /// The pragma clang optimize location (if the pragma state is "off").
   SourceLocation OptimizeOffPragmaLocation;
 
+  /// The submodule include maps. Translates local submodule ID to the map that
+  /// contains the number of includes for a file.
+  llvm::DenseMap<unsigned, llvm::StringMap<unsigned>> SubmoduleImports;
+
   /// The PragmaMSStructKind pragma ms_struct state if set, or -1.
   int PragmaMSStructState = -1;
 
   /// The PragmaMSPointersToMembersKind pragma pointers_to_members state.
   int PragmaMSPointersToMembersState = -1;
   SourceLocation PointersToMembersPragmaLocation;
 
   /// The pragma float_control state.

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) {
-    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";
+//  unsigned NumOnceOnlyFiles = 0, MaxNumIncludes = 0, NumSingleIncludedFiles = 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() << "  " << 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(Preprocessor &PP,
 
   // 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.NumIncludes(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;
+  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

#endif
 
   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)
+      NumIncludes(*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,
#endif
 
   case Import: {
     // If this is a module import, make it visible if needed.
     Module *M = SuggestedModule.getModule();
     assert(M && "no module to import");
 
     makeModuleVisible(M, EndLoc);
 
+    // TODO: Consider storing this into "ImportedIncludes" or something.
+    for (const auto& Include : SubmoduleIncludeMaps[M].LocalIncludes)
+      CurIncludeMap->LocalIncludes[Include.getFirst()] += Include.getSecond();
+
     if (IncludeTok.getIdentifierInfo()->getPPKeywordID() ==
         tok::pp___include_macros)
       return {ImportAction::None};
 
     return {ImportAction::ModuleImport, M};
   }
 
   case Enter:

clang/lib/Lex/PPLexerChange.cpp

if (const IdentifierInfo *ControllingMacro =
       if (const FileEntry *FE = CurPPLexer->getFileEntry()) {
         HeaderInfo.SetFileControllingMacro(FE, ControllingMacro);
         if (MacroInfo *MI =
               getMacroInfo(const_cast<IdentifierInfo*>(ControllingMacro)))
           MI->setUsedForHeaderGuard(true);
         if (const IdentifierInfo *DefinedMacro =
               CurPPLexer->MIOpt.GetDefinedMacro()) {
           if (!isMacroDefined(ControllingMacro) &&
-              DefinedMacro != ControllingMacro &&
-              HeaderInfo.FirstTimeLexingFile(FE)) {
+              DefinedMacro != ControllingMacro && FirstTimeLexingFile(FE)) {
 
             // If the edit distance between the two macros is more than 50%,
             // DefinedMacro may not be header guard, or can be header guard of
             // another header file. Therefore, it maybe defining something
             // completely different. This can be observed in the wild when
             // handling feature macros or header guards in different files.
 
             const StringRef ControllingMacroName = ControllingMacro->getName();

 }
 
 void Preprocessor::EnterSubmodule(Module *M, SourceLocation ImportLoc,
                                   bool ForPragma) {
   if (!getLangOpts().ModulesLocalVisibility) {
     // Just track that we entered this submodule.
     BuildingSubmoduleStack.push_back(
         BuildingSubmoduleInfo(M, ImportLoc, ForPragma, CurSubmoduleState,
-                              PendingModuleMacroNames.size()));
+                              PendingModuleMacroNames.size(), CurIncludeMap));
+
+    auto IncludeStateIt = SubmoduleIncludeMaps.emplace(M, IncludeMap());
+    auto &IncludeState = IncludeStateIt.first->second;
+
+    // Propagate all include information from the outer include state into the
+    // current.
+    for (const auto& Includes : CurIncludeMap->OuterIncludes)
+      IncludeState.OuterIncludes[Includes.getFirst()] += Includes.getSecond();
+    for (const auto& Includes : CurIncludeMap->LocalIncludes)
+      IncludeState.OuterIncludes[Includes.getFirst()] += Includes.getSecond();
+
+    CurIncludeMap = &IncludeState;
+
     if (Callbacks)
       Callbacks->EnteredSubmodule(M, ImportLoc, ForPragma);
     return;
   }
 
   // Resolve as much of the module definition as we can now, before we enter
   // one of its headers.
   // FIXME: Can we enable Complain here?
   // FIXME: Can we do this when local visibility is disabled?
   ModuleMap &ModMap = getHeaderSearchInfo().getModuleMap();
   ModMap.resolveExports(M, /*Complain=*/false);
   ModMap.resolveUses(M, /*Complain=*/false);
   ModMap.resolveConflicts(M, /*Complain=*/false);
 
   // If this is the first time we've entered this module, set up its state.
   auto R = Submodules.insert(std::make_pair(M, SubmoduleState()));
+  auto IncludeIt = SubmoduleIncludeMaps.emplace(M, IncludeMap());
   auto &State = R.first->second;
+  auto &IncludeState = IncludeIt.first->second;
   bool FirstTime = R.second;
   if (FirstTime) {
     // Determine the set of starting macros for this submodule; take these
     // from the "null" module (the predefines buffer).
     //
     // FIXME: If we have local visibility but not modules enabled, the
     // NullSubmoduleState is polluted by #defines in the top-level source
     // file.
for (auto &Macro : StartingMacros) {
       MS.setOverriddenMacros(*this, Macro.second.getOverriddenMacros());
       State.Macros.insert(std::make_pair(Macro.first, std::move(MS)));
     }
   }
 
   // Track that we entered this module.
   BuildingSubmoduleStack.push_back(
       BuildingSubmoduleInfo(M, ImportLoc, ForPragma, CurSubmoduleState,
-                            PendingModuleMacroNames.size()));
+                            PendingModuleMacroNames.size(), CurIncludeMap));
 
   if (Callbacks)
     Callbacks->EnteredSubmodule(M, ImportLoc, ForPragma);
 
   // Switch to this submodule as the current submodule.
   CurSubmoduleState = &State;
 
+  // Propagate all include information from the outer include state into the
+  // current.
+  for (const auto& Includes : CurIncludeMap->OuterIncludes)
+    IncludeState.OuterIncludes[Includes.getFirst()] += Includes.getSecond();
+  for (const auto& Includes : CurIncludeMap->LocalIncludes)
+    IncludeState.OuterIncludes[Includes.getFirst()] += Includes.getSecond();
+
+  CurIncludeMap = &IncludeState;
+
   // This module is visible to itself.
   if (FirstTime)
     makeModuleVisible(M, ImportLoc);
 }
 
 bool Preprocessor::needModuleMacros() const {
   // If we're not within a submodule, we never need to create ModuleMacros.
   if (BuildingSubmoduleStack.empty())
if (BuildingSubmoduleStack.empty() ||
     return nullptr;
   }
 
   auto &Info = BuildingSubmoduleStack.back();
 
   Module *LeavingMod = Info.M;
   SourceLocation ImportLoc = Info.ImportLoc;
 
+  // Propagate local include information from the inner submodule include
+  // state into the outer.
+  for (const auto &Includes : CurIncludeMap->LocalIncludes)
+    Info.OuterSubmoduleIncludes->OuterIncludes[Includes.getFirst()] +=
+        Includes.getSecond();
+  CurIncludeMap = Info.OuterSubmoduleIncludes;
+
   if (!needModuleMacros() ||
       (!getLangOpts().ModulesLocalVisibility &&
        LeavingMod->getTopLevelModuleName() != getLangOpts().CurrentModule)) {
     // If we don't need module macros, or this is not a module for which we
     // are tracking macro visibility, don't build any, and preserve the list
     // of pending names for the surrounding submodule.
     BuildingSubmoduleStack.pop_back();
 

clang/lib/Lex/Preprocessor.cpp

: PPOpts(std::move(PPOpts)), Diags(&diags), LangOpts(opts),
       FileMgr(Headers.getFileMgr()), SourceMgr(SM),
       ScratchBuf(new ScratchBuffer(SourceMgr)), HeaderInfo(Headers),
       TheModuleLoader(TheModuleLoader), ExternalSource(nullptr),
       // As the language options may have not been loaded yet (when
       // deserializing an ASTUnit), adding keywords to the identifier table is
       // deferred to Preprocessor::Initialize().
       Identifiers(IILookup), PragmaHandlers(new PragmaNamespace(StringRef())),
       TUKind(TUKind), SkipMainFilePreamble(0, true),
-      CurSubmoduleState(&NullSubmoduleState) {
+      CurSubmoduleState(&NullSubmoduleState), CurIncludeMap(&RootIncludeMap) {
   OwnsHeaderSearch = OwnsHeaders;
 
   // Default to discarding comments.
   KeepComments = false;
   KeepMacroComments = false;
   SuppressIncludeNotFoundError = false;
 
   // Macro expansion is enabled.
if (!SourceMgr.isLoadedFileID(MainFileID)) {
     // 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);
+      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?");
CurSubmoduleState->VisibleModules.setVisible(
             << Path[0]->getFullModuleName()
             << Conflict->getFullModuleName()
             << Message;
       });
 
   // Add this module to the imports list of the currently-built submodule.
   if (!BuildingSubmoduleStack.empty() && M != BuildingSubmoduleStack.back().M)
     BuildingSubmoduleStack.back().M->Imports.insert(M);
 }
 
 bool Preprocessor::FinishLexStringLiteral(Token &Result, std::string &String,
                                           const char *DiagnosticTag,
                                           bool AllowMacroExpansion) {
   // We need at least one string literal.
   if (Result.isNot(tok::string_literal)) {
     Diag(Result, diag::err_expected_string_literal)
       << /*Source='in...'*/0 << DiagnosticTag;
     return false;

 
 void Preprocessor::createPreprocessingRecord() {
   if (Record)
     return;
 
   Record = new PreprocessingRecord(getSourceManager());
   addPPCallbacks(std::unique_ptr<PPCallbacks>(Record));
 }
+
+bool Preprocessor::FirstTimeLexingFile(const FileEntry *File) const {
+  return NumIncludes(File) == 1;
+}
+
+unsigned Preprocessor::NumIncludes(const FileEntry *File) const {
+  return (CurIncludeMap->LocalIncludes[File] +
+          CurIncludeMap->OuterIncludes[File]);
+}
+
+void Preprocessor::IncrementIncludeCount(const FileEntry *File) {
+  CurIncludeMap->LocalIncludes[File] += 1;
+}
+
+void Preprocessor::addSubmoduleInclude(Module *M, StringRef Filename,
+                                       unsigned NumIncludes) {
+  if (auto MaybeFE = FileMgr.getFile(Filename)) {
+    if (M == nullptr) {
+      CurIncludeMap->OuterIncludes[*MaybeFE] += NumIncludes;
+    } else {
+      SubmoduleIncludeMaps[M].LocalIncludes[*MaybeFE] += NumIncludes;
+    }
+  }
+}

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 MACRO_OFFSET: {
           std::make_pair(LocalBaseMacroID,
                          F.BaseMacroID - LocalBaseMacroID));
 
         MacrosLoaded.resize(MacrosLoaded.size() + F.LocalNumMacros);
       }
       break;
     }
 
+    case INCLUDES: {
+      unsigned LocalSMID = Record[0];
+      unsigned NumIncludes = Record[1];
+      StringRef Filename = Blob;
+      // PCHs don't have submodules. We can add the includes right away.
+      if (PP.getPreprocessorOpts().ImplicitPCHInclude == F.FileName)
+        PP.addSubmoduleInclude(nullptr, Filename, NumIncludes);
+      else
+        SubmoduleImports[LocalSMID][Filename] = NumIncludes;
+      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)
case SUBMODULE_DEFINITION: {
       // Missing headers that were present when the module was built do not
       // make it unavailable -- if we got this far, this must be an explicitly
       // imported module file.
       CurrentModule->Requirements.clear();
       CurrentModule->MissingHeaders.clear();
       CurrentModule->IsUnimportable =
           ParentModule && ParentModule->IsUnimportable;
       CurrentModule->IsAvailable = !CurrentModule->IsUnimportable;
+
+      // Now that we can map the local submodule ID to an actual Module
+      // instance, pass the include information to the preprocessor.
+      for (const auto &Submodule : SubmoduleImports) {
+        unsigned LocalID = Submodule.getFirst();
+        if (GlobalID == getGlobalSubmoduleID(F, LocalID)) {
+          for (const auto &Include : Submodule.getSecond())
+            PP.addSubmoduleInclude(CurrentModule, Include.getKey(),
+                                   Include.getValue());
+          break;
+        }
+      }
+
       break;
     }
 
     case SUBMODULE_UMBRELLA_HEADER: {
       // FIXME: This doesn't work for framework modules as `Filename` is the
       //        name as written in the module file and does not include
       //        `Headers/`, so this path will never exist.
       std::string Filename = std::string(Blob);
case SUBMODULE_INITIALIZERS: {
       break;
     }
 
     case SUBMODULE_EXPORT_AS:
       CurrentModule->ExportAsModule = Blob.str();
       ModMap.addLinkAsDependency(CurrentModule);
       break;
     }
   }
 }
 
 /// Parse the record that corresponds to a LangOptions data
 /// structure.
 ///
 /// This routine parses the language options from the AST file and then gives
 /// them to the AST listener if one is set.
 ///
 /// \returns true if the listener deems the file unacceptable, false otherwise.
 bool ASTReader::ParseLanguageOptions(const RecordData &Record,
ASTReader::getGlobalSubmoduleID(ModuleFile &M, unsigned LocalID) {
   ContinuousRangeMap<uint32_t, int, 2>::iterator I
     = M.SubmoduleRemap.find(LocalID - NUM_PREDEF_SUBMODULE_IDS);
   assert(I != M.SubmoduleRemap.end()
          && "Invalid index into submodule index remap");
 
   return LocalID + I->second;
 }
 
 Module *ASTReader::getSubmodule(SubmoduleID GlobalID) {
   if (GlobalID < NUM_PREDEF_SUBMODULE_IDS) {
     assert(GlobalID == 0 && "Unhandled global submodule ID");
     return nullptr;
   }
 
   if (GlobalID > SubmodulesLoaded.size()) {
     Error("submodule ID out of range in AST file");
     return nullptr;

clang/lib/Serialization/ASTWriter.cpp

 #include <deque>
 #include <limits>
 #include <memory>
 #include <queue>
 #include <tuple>
 #include <utility>
 #include <vector>
 
+#include <map>
+
 using namespace clang;
 using namespace clang::serialization;
 
 template <typename T, typename Allocator>
 static StringRef bytes(const std::vector<T, Allocator> &v) {
   if (v.empty()) return StringRef();
   return StringRef(reinterpret_cast<const char*>(&v[0]),
                          sizeof(T) * v.size());
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;
 }
 
 /// 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);
 
   RecordData Record;
   RecordData ModuleMacroRecord;
 
   // If the preprocessor __COUNTER__ value has been bumped, remember it.
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));
   }
+
+  Abbrev = std::make_shared<BitCodeAbbrev>();
+  Abbrev->Add(BitCodeAbbrevOp(INCLUDES));
+  Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32)); // # submodule ID
+  Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32)); // # of includes
+  Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
+
+  unsigned IncludesAbbrev = Stream.EmitAbbrev(std::move(Abbrev));
+
+  // TODO: Find a more efficient way to stabilize the order here.
+  std::map<unsigned, std::map<StringRef, unsigned>> ToBeSerialized;
+
+  auto CollectModuleIncludes = [&](Module *M, const auto &Includes){
+    unsigned LocalSMID = getLocalOrImportedSubmoduleID(M);
+
+    // TODO: If we make this more granular ("ImportedIncludes"), serialize them
+    //  too.
+    // Only serializing local includes. We don't want includes made by other
+    // submodules to propagate into consumers of this submodule.
+    for (const auto &Inc : Includes.LocalIncludes) {
+      unsigned NumIncludes = Inc.getSecond();
+      StringRef Filename = Inc.getFirst()->getName();
+      ToBeSerialized[LocalSMID].insert({Filename, NumIncludes});
+    }
+  };
+
+  CollectModuleIncludes(const_cast<Preprocessor &>(PP).getCurrentModule(),
+                        PP.getRootIncludes());
+  for (const auto &SubM : PP.getSubmoduleIncludes())
+    CollectModuleIncludes(SubM.first, SubM.second);
+
+  for (const auto& Include : ToBeSerialized) {
+    unsigned LocalSMID = Include.first;
+
+    for (const auto& X : Include.second) {
+      StringRef Filename = X.first;
+      unsigned NumIncludes = X.second;
+      RecordData::value_type Record[] = {INCLUDES, LocalSMID, NumIncludes};
+      Stream.EmitRecordWithBlob(IncludesAbbrev, Record, Filename);
+    }
+  }
 }
 
 void ASTWriter::WritePreprocessorDetail(PreprocessingRecord &PPRec,
                                         uint64_t MacroOffsetsBase) {
   if (PPRec.local_begin() == PPRec.local_end())
     return;
 
   SmallVector<PPEntityOffset, 64> PreprocessedEntityOffsets;

clang/test/Modules/Inputs/import-submodule-visibility/A.framework/Headers/A.h

+#include "Textual.h"

clang/test/Modules/Inputs/import-submodule-visibility/A.framework/Modules/module.modulemap

+framework module A {
+  header "A.h"
+}

clang/test/Modules/Inputs/import-submodule-visibility/B.framework/Headers/B1.h

+#include "Textual.h"

clang/test/Modules/Inputs/import-submodule-visibility/B.framework/Modules/module.modulemap

+framework module B {
+  module B1 { header "B1.h" }
+  module B2 { header "B2.h" }
+}

clang/test/Modules/Inputs/import-submodule-visibility/C/C.h

+#include "Textual.h"

clang/test/Modules/Inputs/import-submodule-visibility/C/module.modulemap

+module C { header "C.h" }

clang/test/Modules/Inputs/import-submodule-visibility/D/D1.h

+#include "Textual.h"

clang/test/Modules/Inputs/import-submodule-visibility/D/module.modulemap

+module D {
+  module D1 { header "D1.h" }
+  module D2 { header "D2.h" }
+}

clang/test/Modules/Inputs/import-submodule-visibility/Textual.h

+#define MACRO_TEXTUAL 1

clang/test/Modules/import-submodule-visibility.c

+// RUN: rm -rf %t && mkdir -p %t
+
+// This test checks that imports of headers that appeared in a different submodule than
+// what is imported by the current TU don't affect the compilation.
+
+// Framework "A" includes "Textual.h" in the top-level module.
+// This test checks that simply specifying the PCM file on the command line (without actually importing "A") does not
+// prevent "Textual.h" to be included in the TU.
+//
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility \
+// RUN:   -emit-module %S/Inputs/import-submodule-visibility/A.framework/Modules/module.modulemap -fmodule-name=A -o %t/A.pcm
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility -fsyntax-only %s -DA \
+// RUN:   -fmodule-file=%t/A.pcm -fmodule-map-file=%S/Inputs/import-submodule-visibility/A.framework/Modules/module.modulemap
+
+// Framework "B" includes "Textual.h" in the "B1" submodule and its "B2" submodule does not include "Textual.h" at all.
+// This test checks that specifying the PCM file on the command line and importing "B2" in the source does not
+// prevent "Textual.h" to be included in the TU.
+//
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility \
+// RUN:   -emit-module %S/Inputs/import-submodule-visibility/B.framework/Modules/module.modulemap -fmodule-name=B -o %t/B.pcm
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility -fsyntax-only %s -DB -iframework %S/Inputs/import-submodule-visibility \
+// RUN:   -fmodule-file=%t/B.pcm -fmodule-map-file=%S/Inputs/import-submodule-visibility/B.framework/Modules/module.modulemap
+
+// Module "C" includes "Textual.h" in the top level module.
+// This is a module-only version of the test with framework A.
+//
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility \
+// RUN:   -emit-module %S/Inputs/import-submodule-visibility/C/module.modulemap -fmodule-name=C -o %t/C.pcm
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility -fsyntax-only %s -DC \
+// RUN:   -fmodule-file=%t/C.pcm -fmodule-map-file=%S/Inputs/import-submodule-visibility/C/module.modulemap
+
+// Module "D" includes "Textual.h" in the "D1" submodule and its "D2" submodules does not include "Textual.h" at all.
+// This is a module-only version of the test with framework B.
+//
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility \
+// RUN:   -emit-module %S/Inputs/import-submodule-visibility/D/module.modulemap -fmodule-name=D -o %t/D.pcm
+// RUN: %clang_cc1 -fmodules -I %S/Inputs/import-submodule-visibility -fsyntax-only %s -DD \
+// RUN:   -fmodule-file=%t/D.pcm -fmodule-map-file=%S/Inputs/import-submodule-visibility/D/module.modulemap
+
+#ifdef A
+//
+#endif
+
+#ifdef B
+#import <B/B2.h>
+#endif
+
+#ifdef C
+//
+#endif
+
+#ifdef D
+#import "D/D2.h"
+#endif
+
+#import "Textual.h"
+
+static int x = MACRO_TEXTUAL;