Prune .pcm files based on the results of include scanning.

Basically, take the set of headers found by #include scanning and check what modules they are coming from. If a module provides at least one of the required headers, it is required as are all of its dependent modules (because of the way modules are implemented). Only use the actually required modules as compilation inputs and as flags handed in on the command line. Also move the logic to calculate top-level modules from the analysis phase into the execution phase. In the long run, we might be able to completely remove this logic now, but for now, we want to be able to quickly switch between the old and the new behavior. Thus, pruning of modules is now guarded on a feature prune_module_headers.

--
MOS_MIGRATED_REVID=131058820

9 files changed, 332 insertions, 211 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
index 0a641af0c4..541cd6c7a5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
@@ -142,9 +142,7 @@ public abstract class CcBinary implements RuleConfiguredTargetFactory {
       builder.addSymlinksToArtifacts(cppCompilationContext.getDeclaredIncludeSrcs());
       // Add additional files that are referenced from the compile command, like module maps
       // or header modules.
-      builder.addSymlinksToArtifacts(
-          cppCompilationContext.getAdditionalInputs(
-              CppHelper.usePic(context, !isLinkShared(context))));
+      builder.addSymlinksToArtifacts(cppCompilationContext.getAdditionalInputs());
     }
     return builder.build();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
index 1c751e9697..50903b55c4 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
@@ -87,6 +87,7 @@ public final class CcCommon {
       CppRuleClasses.MODULE_MAPS,
       CppRuleClasses.MODULE_MAP_HOME_CWD,
       CppRuleClasses.HEADER_MODULE_INCLUDES_DEPENDENCIES,
+      CppRuleClasses.PRUNE_HEADER_MODULES,
       CppRuleClasses.INCLUDE_PATHS,
       CppRuleClasses.PIC,
       CppRuleClasses.PER_OBJECT_DEBUG_INFO,
@@ -455,7 +456,9 @@ public final class CcCommon {
       }
     }
     prerequisites.addTransitive(context.getDeclaredIncludeSrcs());
-    prerequisites.addTransitive(context.getAdditionalInputs(CppHelper.usePic(ruleContext, false)));
+    prerequisites.addTransitive(context.getAdditionalInputs());
+    prerequisites.addTransitive(context.getTransitiveModules(true));
+    prerequisites.addTransitive(context.getTransitiveModules(false));
     return prerequisites.build();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
index 02f1f950a3..bcb97ce22d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
@@ -26,6 +26,7 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -871,8 +872,8 @@ public class CcToolchainFeatures implements Serializable {
      * Builder for {@code Variables}.
      */
     public static class Builder {
-      private final ImmutableMap.Builder<String, String> variables = ImmutableMap.builder();
-      private final ImmutableMap.Builder<String, Sequence> expandables = ImmutableMap.builder();
+      private final Map<String, String> variables = Maps.newLinkedHashMap();
+      private final Map<String, Sequence> expandables = Maps.newLinkedHashMap();
       
       /**
        * Add a variable that expands {@code name} to {@code value}.
@@ -899,6 +900,15 @@ public class CcToolchainFeatures implements Serializable {
       }
 
       /**
+       * Adds all variables to this builder.
+       */
+      public Builder addAll(Variables variables) {
+        this.variables.putAll(variables.variables);
+        this.expandables.putAll(variables.sequenceVariables);
+        return this;
+      }
+
+      /**
        * Add a variable that expands a flag group containing a reference to {@code name} for each
        * entry in {@code values}.
        */
@@ -914,7 +924,7 @@ public class CcToolchainFeatures implements Serializable {
        * @return a new {@Variables} object.
        */
       Variables build() {
-        return new Variables(variables.build(), expandables.build());
+        return new Variables(ImmutableMap.copyOf(variables), ImmutableMap.copyOf(expandables));
       }
     }
     
@@ -932,7 +942,7 @@ public class CcToolchainFeatures implements Serializable {
     interface View {
 
       /**
-       * Returns all bounds variables in the current view.
+       * Returns all bound variables in the current view.
        */
       Map<String, String> getVariables();
 
@@ -1250,7 +1260,6 @@ public class CcToolchainFeatures implements Serializable {
    *
    * @param toolchain the toolchain configuration as specified by the user.
    * @throws InvalidConfigurationException if the configuration has logical errors.
-   * @throws ArtifactNamePatternNotProvidedException
    */
   @VisibleForTesting
   public CcToolchainFeatures(CToolchain toolchain) throws InvalidConfigurationException {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java
index 0a6e8b5248..43192b932d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java
@@ -30,6 +30,7 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.Collection;
 import java.util.LinkedHashSet;
 import java.util.Map;
 import java.util.Set;
@@ -54,25 +55,10 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
    */
   private final NestedSet<Artifact> directModuleMaps;
 
-  /**
-   * All declared headers of the current module, if compiled as a header module.
-   */
-  private final NestedSet<Artifact> headerModuleSrcs;
-
-  /**
-   * All header modules in the transitive closure of {@code topLevelHeaderModules}.
-   */
-  private final NestedSet<Artifact> impliedHeaderModules;
-  private final NestedSet<Artifact> picImpliedHeaderModules;
-
   private final NestedSet<Pair<Artifact, Artifact>> pregreppedHdrs;
-
-  /**
-   * All header modules in our transitive closure that are not in the transitive closure of
-   * another header module in our transitive closure.
-   */
-  private final NestedSet<Artifact> topLevelHeaderModules;
-  private final NestedSet<Artifact> picTopLevelHeaderModules;
+  
+  private final ModuleInfo moduleInfo;
+  private final ModuleInfo picModuleInfo;
 
   /**
    * The module maps from all targets the current target depends on transitively.
@@ -80,8 +66,6 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
   private final NestedSet<Artifact> transitiveModuleMaps;
 
   private final CppModuleMap cppModuleMap;
-  private final Artifact headerModule;
-  private final Artifact picHeaderModule;
   
   // True if this context is for a compilation that needs transitive module maps.
   private final boolean provideTransitiveModuleMaps;
@@ -99,16 +83,11 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
       NestedSet<PathFragment> declaredIncludeWarnDirs,
       NestedSet<Artifact> declaredIncludeSrcs,
       NestedSet<Pair<Artifact, Artifact>> pregreppedHdrs,
-      NestedSet<Artifact> headerModuleSrcs,
-      NestedSet<Artifact> topLevelHeaderModules,
-      NestedSet<Artifact> picTopLevelHeaderModules,
-      NestedSet<Artifact> impliedHeaderModules,
-      NestedSet<Artifact> picImpliedHeaderModules,
+      ModuleInfo moduleInfo,
+      ModuleInfo picModuleInfo,
       NestedSet<Artifact> transitiveModuleMaps,
       NestedSet<Artifact> directModuleMaps,
       CppModuleMap cppModuleMap,
-      Artifact headerModule,
-      Artifact picHeaderModule,
       boolean provideTransitiveModuleMaps,
       boolean useHeaderModules) {
     Preconditions.checkNotNull(commandLineContext);
@@ -117,16 +96,11 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
     this.declaredIncludeWarnDirs = declaredIncludeWarnDirs;
     this.declaredIncludeSrcs = declaredIncludeSrcs;
     this.directModuleMaps = directModuleMaps;
-    this.headerModuleSrcs = headerModuleSrcs;
-    this.impliedHeaderModules = impliedHeaderModules;
-    this.picImpliedHeaderModules = picImpliedHeaderModules;
     this.pregreppedHdrs = pregreppedHdrs;
-    this.topLevelHeaderModules = topLevelHeaderModules;
-    this.picTopLevelHeaderModules = picTopLevelHeaderModules;
+    this.moduleInfo = moduleInfo;
+    this.picModuleInfo = picModuleInfo;
     this.transitiveModuleMaps = transitiveModuleMaps;
     this.cppModuleMap = cppModuleMap;
-    this.headerModule = headerModule;
-    this.picHeaderModule = picHeaderModule;
     this.provideTransitiveModuleMaps = provideTransitiveModuleMaps;
     this.useHeaderModules = useHeaderModules;
     this.compilationPrerequisites = compilationPrerequisites;
@@ -236,22 +210,27 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
   NestedSet<Pair<Artifact, Artifact>> getPregreppedHeaders() {
     return pregreppedHdrs;
   }
+  
+  public NestedSet<Artifact> getTransitiveModules(boolean usePic) {
+    return usePic ? picModuleInfo.transitiveModules : moduleInfo.transitiveModules;
+  }
+  
+  public Set<Artifact> getTopLevelModules(boolean usePic) {
+    return usePic ? picModuleInfo.getTopLevelModules() : moduleInfo.getTopLevelModules();
+  }
+  
+  public Collection<Artifact> getUsedModules(boolean usePic, Set<Artifact> usedHeaders) {
+    return usePic
+        ? picModuleInfo.getUsedModules(usedHeaders)
+        : moduleInfo.getUsedModules(usedHeaders);
+  }
 
   /**
    * Returns the immutable set of additional transitive inputs needed for
    * compilation, like C++ module map artifacts.
    */
-  public NestedSet<Artifact> getAdditionalInputs(boolean usePic) {
+  public NestedSet<Artifact> getAdditionalInputs() {
     NestedSetBuilder<Artifact> builder = NestedSetBuilder.stableOrder();
-    if (useHeaderModules) {
-      if (usePic) {
-        builder.addTransitive(picTopLevelHeaderModules);
-        builder.addTransitive(picImpliedHeaderModules);
-      } else {
-        builder.addTransitive(topLevelHeaderModules);
-        builder.addTransitive(impliedHeaderModules);
-      }
-    }
     builder.addTransitive(directModuleMaps);
     if (provideTransitiveModuleMaps) {
       builder.addTransitive(transitiveModuleMaps);
@@ -259,7 +238,6 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
     if (cppModuleMap != null) {
       builder.add(cppModuleMap.getArtifact());
     }
-
     return builder.build();
   }
 
@@ -281,23 +259,8 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
    * @return all declared headers of the current module if the current target
    * is compiled as a module.
    */
-  protected NestedSet<Artifact> getHeaderModuleSrcs() {
-    return headerModuleSrcs;
-  }
-
-  /**
-   * @return all header modules in our transitive closure that are not in the transitive closure
-   * of another header module in our transitive closure.
-   */
-  protected NestedSet<Artifact> getTopLevelHeaderModules(boolean usePic) {
-    return usePic ? picTopLevelHeaderModules : topLevelHeaderModules;
-  }
-
-  /**
-   * @return all header modules in the transitive closure of {@code getTopLevelHeaderModules()}.
-   */
-  protected NestedSet<Artifact> getImpliedHeaderModules(boolean usePic) {
-    return usePic ? picImpliedHeaderModules : impliedHeaderModules;
+  protected Set<Artifact> getHeaderModuleSrcs() {
+    return moduleInfo.headerModuleSrcs;
   }
 
   /**
@@ -321,16 +284,11 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
         NestedSetBuilder.<PathFragment>emptySet(Order.STABLE_ORDER),
         context.declaredIncludeSrcs,
         context.pregreppedHdrs,
-        context.headerModuleSrcs,
-        context.topLevelHeaderModules,
-        context.picTopLevelHeaderModules,
-        context.impliedHeaderModules,
-        context.picImpliedHeaderModules,
+        context.moduleInfo,
+        context.picModuleInfo,
         context.transitiveModuleMaps,
         context.directModuleMaps,
         context.cppModuleMap,
-        context.headerModule,
-        context.picHeaderModule,
         context.provideTransitiveModuleMaps,
         context.useHeaderModules);
   }
@@ -365,6 +323,12 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
     ImmutableSet.Builder<Artifact> prerequisites = ImmutableSet.builder();
     prerequisites.addAll(ownerContext.compilationPrerequisites);
     prerequisites.addAll(libContext.compilationPrerequisites);
+    ModuleInfo.Builder moduleInfo = new ModuleInfo.Builder();
+    moduleInfo.merge(ownerContext.moduleInfo);
+    moduleInfo.merge(libContext.moduleInfo);
+    ModuleInfo.Builder picModuleInfo = new ModuleInfo.Builder();
+    picModuleInfo.merge(ownerContext.picModuleInfo);
+    picModuleInfo.merge(libContext.picModuleInfo);
     return new CppCompilationContext(
         libContext.commandLineContext,
         prerequisites.build(),
@@ -372,16 +336,11 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
         mergeSets(ownerContext.declaredIncludeWarnDirs, libContext.declaredIncludeWarnDirs),
         mergeSets(ownerContext.declaredIncludeSrcs, libContext.declaredIncludeSrcs),
         mergeSets(ownerContext.pregreppedHdrs, libContext.pregreppedHdrs),
-        mergeSets(ownerContext.headerModuleSrcs, libContext.headerModuleSrcs),
-        mergeSets(ownerContext.topLevelHeaderModules, libContext.topLevelHeaderModules),
-        mergeSets(ownerContext.picTopLevelHeaderModules, libContext.picTopLevelHeaderModules),
-        mergeSets(ownerContext.impliedHeaderModules, libContext.impliedHeaderModules),
-        mergeSets(ownerContext.picImpliedHeaderModules, libContext.picImpliedHeaderModules),
+        moduleInfo.build(),
+        picModuleInfo.build(),
         mergeSets(ownerContext.transitiveModuleMaps, libContext.transitiveModuleMaps),
         mergeSets(ownerContext.directModuleMaps, libContext.directModuleMaps),
         libContext.cppModuleMap,
-        libContext.headerModule,
-        libContext.picHeaderModule,
         libContext.provideTransitiveModuleMaps,
         libContext.useHeaderModules);
   }
@@ -404,20 +363,6 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
   }
 
   /**
-   * @return the non-pic C++ header module of the owner.
-   */
-  private Artifact getHeaderModule() {
-    return headerModule;
-  }
-
-  /**
-   * @return the pic C++ header module of the owner.
-   */
-  private Artifact getPicHeaderModule() {
-    return picHeaderModule;
-  }
-
-  /**
    * The parts of the compilation context that influence the command line of
    * compilation actions.
    */
@@ -456,24 +401,12 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
         NestedSetBuilder.stableOrder();
     private final NestedSetBuilder<Pair<Artifact, Artifact>> pregreppedHdrs =
         NestedSetBuilder.stableOrder();
-    private final NestedSetBuilder<Artifact> headerModuleSrcs =
-        NestedSetBuilder.stableOrder();
-    private final NestedSetBuilder<Artifact> topLevelHeaderModules =
-        NestedSetBuilder.stableOrder();
-    private final NestedSetBuilder<Artifact> picTopLevelHeaderModules =
-        NestedSetBuilder.stableOrder();
-    private final NestedSetBuilder<Artifact> impliedHeaderModules =
-        NestedSetBuilder.stableOrder();
-    private final NestedSetBuilder<Artifact> picImpliedHeaderModules =
-        NestedSetBuilder.stableOrder();
-    private final NestedSetBuilder<Artifact> transitiveModuleMaps =
-        NestedSetBuilder.stableOrder();
-    private final NestedSetBuilder<Artifact> directModuleMaps =
-        NestedSetBuilder.stableOrder();
+    private final ModuleInfo.Builder moduleInfo = new ModuleInfo.Builder();
+    private final ModuleInfo.Builder picModuleInfo = new ModuleInfo.Builder();
+    private final NestedSetBuilder<Artifact> transitiveModuleMaps = NestedSetBuilder.stableOrder();
+    private final NestedSetBuilder<Artifact> directModuleMaps = NestedSetBuilder.stableOrder();
     private final Set<String> defines = new LinkedHashSet<>();
     private CppModuleMap cppModuleMap;
-    private Artifact headerModule;
-    private Artifact picHeaderModule;
     private boolean provideTransitiveModuleMaps = false;
     private boolean useHeaderModules = false;
 
@@ -531,42 +464,23 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
       declaredIncludeWarnDirs.addTransitive(otherContext.getDeclaredIncludeWarnDirs());
       declaredIncludeSrcs.addTransitive(otherContext.getDeclaredIncludeSrcs());
       pregreppedHdrs.addTransitive(otherContext.getPregreppedHeaders());
+      moduleInfo.addTransitive(otherContext.moduleInfo);
+      picModuleInfo.addTransitive(otherContext.picModuleInfo);
 
       NestedSet<Artifact> othersTransitiveModuleMaps = otherContext.getTransitiveModuleMaps();
       NestedSet<Artifact> othersDirectModuleMaps = otherContext.getDirectModuleMaps();
-      NestedSet<Artifact> othersTopLevelHeaderModules =
-          otherContext.getTopLevelHeaderModules(/*usePic=*/ false);
-      NestedSet<Artifact> othersPicTopLevelHeaderModules =
-          otherContext.getTopLevelHeaderModules(/*usePic=*/ true);
 
       // Forward transitive information.
       // The other target's transitive module maps do not include its direct module maps, so we
       // add both.
       transitiveModuleMaps.addTransitive(othersTransitiveModuleMaps);
       transitiveModuleMaps.addTransitive(othersDirectModuleMaps);
-      impliedHeaderModules.addTransitive(otherContext.getImpliedHeaderModules(/*usePic=*/ false));
-      picImpliedHeaderModules.addTransitive(otherContext.getImpliedHeaderModules(/*usePic=*/ true));
-      topLevelHeaderModules.addTransitive(othersTopLevelHeaderModules);
-      picTopLevelHeaderModules.addTransitive(othersPicTopLevelHeaderModules);
 
       // All module maps of direct dependencies are inputs to the current compile independently of
       // the build type.
       if (otherContext.getCppModuleMap() != null) {
         directModuleMaps.add(otherContext.getCppModuleMap().getArtifact());
       }
-      if (otherContext.getHeaderModule() != null || otherContext.getPicHeaderModule() != null) {
-        // If the other context is for a target that compiles a header module, that context's
-        // header module becomes our top-level header module, and its top-level header modules
-        // become our implied header modules.
-        impliedHeaderModules.addTransitive(othersTopLevelHeaderModules);
-        picImpliedHeaderModules.addTransitive(othersPicTopLevelHeaderModules);
-        if (otherContext.getHeaderModule() != null) {
-          topLevelHeaderModules.add(otherContext.getHeaderModule());
-        }
-        if (otherContext.getPicHeaderModule() != null) {
-          picTopLevelHeaderModules.add(otherContext.getPicHeaderModule());
-        }
-      }
 
       defines.addAll(otherContext.getDefines());
       return this;
@@ -674,7 +588,8 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
     public Builder addDeclaredIncludeSrc(Artifact header) {
       declaredIncludeSrcs.add(header);
       compilationPrerequisites.add(header);
-      headerModuleSrcs.add(header);
+      moduleInfo.addHeader(header);
+      picModuleInfo.addHeader(header);
       return this;
     }
 
@@ -682,9 +597,10 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
      * Adds multiple headers that have been declared in the {@code src} or {@code headers
      * attribute}. The headers will also be added to the compilation prerequisites.
      */
-    public Builder addDeclaredIncludeSrcs(Iterable<Artifact> declaredIncludeSrcs) {
+    public Builder addDeclaredIncludeSrcs(Collection<Artifact> declaredIncludeSrcs) {
       this.declaredIncludeSrcs.addAll(declaredIncludeSrcs);
-      this.headerModuleSrcs.addAll(declaredIncludeSrcs);
+      this.moduleInfo.addHeaders(declaredIncludeSrcs);
+      this.picModuleInfo.addHeaders(declaredIncludeSrcs);
       return addCompilationPrerequisites(declaredIncludeSrcs);
     }
 
@@ -726,17 +642,19 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
 
     /**
      * Sets the C++ header module in non-pic mode.
+     * @param headerModule The .pcm file generated for this library.
      */
     public Builder setHeaderModule(Artifact headerModule) {
-      this.headerModule = headerModule;
+      this.moduleInfo.setHeaderModule(headerModule);
       return this;
     }
 
     /**
      * Sets the C++ header module in pic mode.
+     * @param picHeaderModule The .pic.pcm file generated for this library.
      */
     public Builder setPicHeaderModule(Artifact picHeaderModule) {
-      this.picHeaderModule = picHeaderModule;
+      this.picModuleInfo.setHeaderModule(picHeaderModule);
       return this;
     }
     
@@ -768,16 +686,6 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
 
     @VisibleForTesting  // productionVisibility = Visibility.PRIVATE
     public CppCompilationContext build(ActionOwner owner, MiddlemanFactory middlemanFactory) {
-      // During merging we might have put header modules into topLevelHeaderModules that were
-      // also in the transitive closure of a different header module; we need to filter those out.
-      NestedSet<Artifact> impliedHeaderModules = this.impliedHeaderModules.build();
-      NestedSet<Artifact> topLevelHeaderModules =
-          filterTopLevelHeaderModules(this.topLevelHeaderModules.build(), impliedHeaderModules);
-      NestedSet<Artifact> picImpliedHeaderModules = this.picImpliedHeaderModules.build();
-      NestedSet<Artifact> picTopLevelHeaderModules =
-          filterTopLevelHeaderModules(
-              this.picTopLevelHeaderModules.build(), picImpliedHeaderModules);
-      
       // We don't create middlemen in LIPO collector subtree, because some target CT
       // will do that instead.
       Artifact prerequisiteStampFile = (ruleContext != null
@@ -798,37 +706,16 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
           declaredIncludeWarnDirs.build(),
           declaredIncludeSrcs.build(),
           pregreppedHdrs.build(),
-          headerModuleSrcs.build(),
-          topLevelHeaderModules,
-          picTopLevelHeaderModules,
-          impliedHeaderModules,
-          picImpliedHeaderModules,
+          moduleInfo.build(),
+          picModuleInfo.build(),
           transitiveModuleMaps.build(),
           directModuleMaps.build(),
           cppModuleMap,
-          headerModule,
-          picHeaderModule,
           provideTransitiveModuleMaps,
           useHeaderModules);
     }
     
     /**
-     * Filter out artifacts from {@code topLevelHeaderModuels} that are also in
-     * {@code impliedHeaderModules}.
-     */
-    private static NestedSet<Artifact> filterTopLevelHeaderModules(
-        NestedSet<Artifact> topLevelHeaderModules, NestedSet<Artifact> impliedHeaderModules) {
-      NestedSetBuilder<Artifact> filtered = NestedSetBuilder.stableOrder();
-      Set<Artifact> impliedHeaderModulesSet = impliedHeaderModules.toSet();
-      for (Artifact artifact : topLevelHeaderModules) {
-        if (!impliedHeaderModulesSet.contains(artifact)) {
-          filtered.add(artifact);
-        }
-      }
-      return filtered.build();
-    }
-
-    /**
      * Creates a middleman for the compilation prerequisites.
      *
      * @return the middleman or null if there are no prerequisites
@@ -879,4 +766,197 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
               ruleContext.getRule().getRepository()));
     }
   }
+  
+  /**
+   * Gathers data about the direct and transitive .pcm files belonging to this context. Can be to
+   * either gather data on PIC or on no-PIC .pcm files.
+   */
+  @Immutable
+  public static final class ModuleInfo {
+    /**
+     * The module built for this context. If null, then no module is being compiled for this
+     * context.
+     */
+    private final Artifact headerModule;
+    
+    /**
+     * All header files that are compiled into this module.
+     */
+    private final ImmutableSet<Artifact> headerModuleSrcs;
+    
+    /**
+     * All transitive modules that this context depends on, excluding headerModule.
+     */
+    private final NestedSet<Artifact> transitiveModules;
+    
+    /**
+     * All implied modules that this context depends on, i.e. all transitiveModules, that are also
+     * a dependency of other transitiveModules.
+     */
+    private final NestedSet<Artifact> impliedModules;
+    
+    /**
+     * All information about mapping transitive headers to transitive modules.
+     */
+    public final NestedSet<TransitiveModuleHeaders> transitiveModuleHeaders;
+
+    public ModuleInfo(
+        Artifact headerModule,
+        ImmutableSet<Artifact> headerModuleSrcs,
+        NestedSet<Artifact> transitiveModules,
+        NestedSet<Artifact> impliedModules,
+        NestedSet<TransitiveModuleHeaders> transitiveModuleHeaders) {
+      this.headerModule = headerModule;
+      this.headerModuleSrcs = headerModuleSrcs;
+      this.transitiveModules = transitiveModules;
+      this.impliedModules = impliedModules;
+      this.transitiveModuleHeaders = transitiveModuleHeaders;
+    }
+
+    public Set<Artifact> getTopLevelModules() {
+      Set<Artifact> impliedModules = this.impliedModules.toSet();
+      Set<Artifact> topLevelModules = new LinkedHashSet<>();
+      for (Artifact module : transitiveModules) {
+        if (!impliedModules.contains(module)) {
+          topLevelModules.add(module);
+        }
+      }
+      return topLevelModules;
+    }
+
+    public Collection<Artifact> getUsedModules(Set<Artifact> usedHeaders) {
+      Set<Artifact> result = new LinkedHashSet<>();
+      for (TransitiveModuleHeaders transitiveModule : transitiveModuleHeaders) {
+        if (result.contains(transitiveModule.module)) {
+          // If result already contains this module, we will have added it and all its
+          // transitive dependencies to result already. No need to check whether to add it again.
+          continue;
+        }
+        boolean providesUsedHeader = false;
+        for (Artifact header : transitiveModule.headers) {
+          if (usedHeaders.contains(header)) {
+            providesUsedHeader = true;
+            break;
+          }
+        }
+        if (providesUsedHeader) {
+          result.addAll(transitiveModule.transitiveModules.toCollection());
+          if (!transitiveModule.module.equals(headerModule)) {
+            // Only add the module itself if it is not the main headerModule. This is done because
+            // we don't want to pass the header module when compiling the translation unit that
+            // defines it. Due to how modules are implemented, #includes from a translation unit to
+            // the headers that it implements remain textual. Thus, adding this header module as a
+            // dependency would only prolong the build without any possible benefit.
+            result.add(transitiveModule.module);
+          }
+        }
+      }
+      return result;
+    }
+
+    /**
+     * Builder class for {@link ModuleInfo}.
+     */
+    public static class Builder {
+      private Artifact headerModule = null;
+      private Set<Artifact> headerModuleSrcs = new LinkedHashSet<>();
+      private NestedSetBuilder<Artifact> transitiveModules = NestedSetBuilder.stableOrder();
+      private NestedSetBuilder<Artifact> impliedModules = NestedSetBuilder.stableOrder();
+      private NestedSetBuilder<TransitiveModuleHeaders> transitiveModuleHeaders =
+          NestedSetBuilder.stableOrder();
+      
+      public Builder setHeaderModule(Artifact headerModule) {
+        this.headerModule = headerModule;
+        return this;
+      }
+
+      public Builder addHeaders(Collection<Artifact> headers) {
+        this.headerModuleSrcs.addAll(headers);
+        return this;
+      }
+
+      public Builder addHeader(Artifact header) {
+        this.headerModuleSrcs.add(header);
+        return this;
+      }
+
+      /**
+       * Merges a {@link ModuleInfo} into this one. In contrast to addTransitive, this doesn't add
+       * the dependent module to transitiveModules, but just merges the transitive sets. The main
+       * usage is to merge multiple {@link ModuleInfo} instances for Lipo.
+       */
+      public Builder merge(ModuleInfo other) {
+        if (headerModule == null) {
+          headerModule = other.headerModule;
+        }
+        headerModuleSrcs.addAll(other.headerModuleSrcs);
+        transitiveModules.addTransitive(other.transitiveModules);
+        impliedModules.addTransitive(other.impliedModules);
+        transitiveModuleHeaders.addTransitive(other.transitiveModuleHeaders);
+        return this;
+      }
+
+      /**
+       * Adds the {@link ModuleInfo} of a dependency and builds up the transitive data structures.
+       */
+      public Builder addTransitive(ModuleInfo moduleInfo) {
+        if (moduleInfo.headerModule != null) {
+          transitiveModules.add(moduleInfo.headerModule);
+          impliedModules.addTransitive(moduleInfo.transitiveModules);
+        } else {
+          impliedModules.addTransitive(moduleInfo.impliedModules);
+        }
+        transitiveModules.addTransitive(moduleInfo.transitiveModules);
+        impliedModules.addTransitive(moduleInfo.impliedModules);
+        transitiveModuleHeaders.addTransitive(moduleInfo.transitiveModuleHeaders);
+        return this;
+      }
+
+      public ModuleInfo build() {
+        ImmutableSet<Artifact> headerModuleSrcs = ImmutableSet.copyOf(this.headerModuleSrcs);
+        NestedSet<Artifact> transitiveModules = this.transitiveModules.build();
+        if (headerModule != null) {
+          transitiveModuleHeaders.add(
+              new TransitiveModuleHeaders(headerModule, headerModuleSrcs, transitiveModules));
+        }
+        return new ModuleInfo(
+            headerModule,
+            headerModuleSrcs,
+            transitiveModules,
+            impliedModules.build(),
+            transitiveModuleHeaders.build());
+      }
+    }
+  }
+  
+  /**
+   * Collects data for a specific module in a special format that makes pruning easy.
+   */
+  @Immutable
+  public static final class TransitiveModuleHeaders {
+    /**
+     * The module that we are calculating information for.
+     */
+    private final Artifact module;
+
+    /**
+     * The headers compiled into this module.
+     */
+    private final ImmutableSet<Artifact> headers;
+
+    /**
+     * This nested set contains 'module' as well as all targets it transitively depends on.
+     * If any of the 'headers' is used, all of these modules a required for the compilation.
+     */
+    private final NestedSet<Artifact> transitiveModules;
+
+    public TransitiveModuleHeaders(
+        Artifact module,
+        ImmutableSet<Artifact> headers,
+        NestedSet<Artifact> transitiveModules) {
+      this.module = module;
+      this.headers = headers;
+      this.transitiveModules = transitiveModules;
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 3769518150..28cfb02651 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -20,6 +20,7 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.AbstractAction;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
@@ -163,14 +164,15 @@ public class CppCompileAction extends AbstractAction
   private final Artifact optionalSourceFile;
   private final NestedSet<Artifact> mandatoryInputs;
   private final boolean shouldScanIncludes;
+  private final boolean usePic;
   private final CppCompilationContext context;
   private final Iterable<IncludeScannable> lipoScannables;
   private final ImmutableList<Artifact> builtinIncludeFiles;
   @VisibleForTesting public final CppCompileCommandLine cppCompileCommandLine;
   private final ImmutableSet<String> executionRequirements;
 
-  @VisibleForTesting
-  final CppConfiguration cppConfiguration;
+  @VisibleForTesting final CppConfiguration cppConfiguration;
+  private final FeatureConfiguration featureConfiguration;
   protected final Class<? extends CppCompileActionContext> actionContext;
   private final SpecialInputsHandler specialInputsHandler;
 
@@ -191,6 +193,8 @@ public class CppCompileAction extends AbstractAction
    * execution.
    */
   private Collection<Artifact> additionalInputs = null;
+  
+  private CcToolchainFeatures.Variables overwrittenVariables = null;
 
   private ImmutableList<Artifact> resolvedInputs = ImmutableList.<Artifact>of();
 
@@ -233,6 +237,7 @@ public class CppCompileAction extends AbstractAction
       CcToolchainFeatures.Variables variables,
       Artifact sourceFile,
       boolean shouldScanIncludes,
+      boolean usePic,
       Label sourceLabel,
       NestedSet<Artifact> mandatoryInputs,
       Artifact outputFile,
@@ -269,22 +274,17 @@ public class CppCompileAction extends AbstractAction
     this.context = context;
     this.specialInputsHandler = specialInputsHandler;
     this.cppConfiguration = cppConfiguration;
+    this.featureConfiguration = featureConfiguration;
     // inputsKnown begins as the logical negation of shouldScanIncludes.
     // When scanning includes, the inputs begin as not known, and become
     // known after inclusion scanning. When *not* scanning includes,
     // the inputs are as declared, hence known, and remain so.
     this.shouldScanIncludes = shouldScanIncludes;
+    this.usePic = usePic;
     this.inputsKnown = !shouldScanIncludes;
     this.cppCompileCommandLine =
         new CppCompileCommandLine(
-            sourceFile,
-            dotdFile,
-            copts,
-            coptsFilter,
-            features,
-            featureConfiguration,
-            variables,
-            actionName);
+            sourceFile, dotdFile, copts, coptsFilter, features, variables, actionName);
     this.actionContext = actionContext;
     this.lipoScannables = lipoScannables;
     this.actionClassId = actionClassId;
@@ -436,6 +436,21 @@ public class CppCompileAction extends AbstractAction
       this.additionalInputs = ImmutableList.of();
       return null;
     }
+
+    if (featureConfiguration.isEnabled(CppRuleClasses.PRUNE_HEADER_MODULES)) {
+      Set<Artifact> initialResultSet = Sets.newLinkedHashSet(initialResult);
+      List<String> usedModulePaths = Lists.newArrayList();
+      for (Artifact usedModule : context.getUsedModules(usePic, initialResultSet)) {
+        initialResultSet.add(usedModule);
+        usedModulePaths.add(usedModule.getExecPathString());
+      }
+      CcToolchainFeatures.Variables.Builder variableBuilder =
+          new CcToolchainFeatures.Variables.Builder();
+      variableBuilder.addSequenceVariable("module_files", usedModulePaths);
+      this.overwrittenVariables = variableBuilder.build();
+      initialResult = initialResultSet;
+    }
+    
     this.additionalInputs = initialResult;
     // In some cases, execution backends need extra files for each included file. Add them
     // to the set of inputs the caller may need to be aware of.
@@ -589,7 +604,7 @@ public class CppCompileAction extends AbstractAction
       // module map, and we need to include-scan all headers that are referenced in the module map.
       // We need to do include scanning as long as we want to support building code bases that are
       // not fully strict layering clean.
-      builder.addTransitive(context.getHeaderModuleSrcs());
+      builder.addAll(context.getHeaderModuleSrcs());
     } else {
       builder.add(getSourceFile());
     }
@@ -661,7 +676,7 @@ public class CppCompileAction extends AbstractAction
   }
 
   protected final List<String> getArgv(PathFragment outputFile) {
-    return cppCompileCommandLine.getArgv(outputFile);
+    return cppCompileCommandLine.getArgv(outputFile, overwrittenVariables);
   }
 
   @Override
@@ -696,7 +711,7 @@ public class CppCompileAction extends AbstractAction
    */
   @VisibleForTesting
   public List<String> getCompilerOptions() {
-    return cppCompileCommandLine.getCompilerOptions();
+    return cppCompileCommandLine.getCompilerOptions(/*updatedVariables=*/null);
   }
 
   @Override
@@ -951,6 +966,10 @@ public class CppCompileAction extends AbstractAction
       IncludeProblems problems = new IncludeProblems();
       Map<PathFragment, Artifact> allowedDerivedInputsMap = getAllowedDerivedInputsMap();
       for (Path execPath : depSet.getDependencies()) {
+        // Module .pcm files are generated and thus aren't declared inputs.
+        if (execPath.getBaseName().endsWith(".pcm")) {
+          continue;
+        }
         PathFragment execPathFragment = execPath.asFragment();
         if (execPathFragment.isAbsolute()) {
           // Absolute includes from system paths are ignored.
@@ -1271,7 +1290,6 @@ public class CppCompileAction extends AbstractAction
     private final List<String> copts;
     private final Predicate<String> coptsFilter;
     private final Collection<String> features;
-    private final FeatureConfiguration featureConfiguration;
     @VisibleForTesting public final CcToolchainFeatures.Variables variables;
     private final String actionName;
 
@@ -1281,7 +1299,6 @@ public class CppCompileAction extends AbstractAction
         ImmutableList<String> copts,
         Predicate<String> coptsFilter,
         Collection<String> features,
-        FeatureConfiguration featureConfiguration,
         CcToolchainFeatures.Variables variables,
         String actionName) {
       this.sourceFile = Preconditions.checkNotNull(sourceFile);
@@ -1290,7 +1307,6 @@ public class CppCompileAction extends AbstractAction
       this.copts = Preconditions.checkNotNull(copts);
       this.coptsFilter = coptsFilter;
       this.features = Preconditions.checkNotNull(features);
-      this.featureConfiguration = featureConfiguration;
       this.variables = variables;
       this.actionName = actionName;
     }
@@ -1302,7 +1318,8 @@ public class CppCompileAction extends AbstractAction
       return featureConfiguration.getEnvironmentVariables(actionName, variables);
     }
 
-    protected List<String> getArgv(PathFragment outputFile) {
+    protected List<String> getArgv(
+        PathFragment outputFile, CcToolchainFeatures.Variables overwrittenVariables) {
       List<String> commandLine = new ArrayList<>();
 
       // first: The command name.
@@ -1317,7 +1334,7 @@ public class CppCompileAction extends AbstractAction
       }
 
       // second: The compiler options.
-      commandLine.addAll(getCompilerOptions());
+      commandLine.addAll(getCompilerOptions(overwrittenVariables));
 
       if (!featureConfiguration.isEnabled("compile_action_flags_in_flag_set")) {
         // third: The file to compile!
@@ -1332,7 +1349,8 @@ public class CppCompileAction extends AbstractAction
       return commandLine;
     }
 
-    public List<String> getCompilerOptions() {
+    public List<String> getCompilerOptions(
+        @Nullable CcToolchainFeatures.Variables overwrittenVariables) {
       List<String> options = new ArrayList<>();
       CppConfiguration toolchain = cppConfiguration;
 
@@ -1353,7 +1371,16 @@ public class CppCompileAction extends AbstractAction
       // unfiltered compiler options to inject include paths, which is superseded by the feature
       // configuration; on the other hand toolchains switch off warnings for the layering check
       // that will be re-added by the feature flags.
-      addFilteredOptions(options, featureConfiguration.getCommandLine(actionName, variables));
+      CcToolchainFeatures.Variables updatedVariables = variables;
+      if (overwrittenVariables != null) {
+        CcToolchainFeatures.Variables.Builder variablesBuilder =
+            new CcToolchainFeatures.Variables.Builder();
+        variablesBuilder.addAll(variables);
+        variablesBuilder.addAll(overwrittenVariables);
+        updatedVariables = variablesBuilder.build();
+      }
+      addFilteredOptions(
+          options, featureConfiguration.getCommandLine(actionName, updatedVariables));
 
       // Users don't expect the explicit copts to be filtered by coptsFilter, add them verbatim.
       // Make sure these are added after the options from the feature configuration, so that
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
index e7dc066a74..d5bd8ed5be 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
@@ -245,7 +245,12 @@ public class CppCompileActionBuilder {
     if (tempOutputFile == null && !shouldScanIncludes) {
       realMandatoryInputsBuilder.addTransitive(context.getDeclaredIncludeSrcs());
     }
-    realMandatoryInputsBuilder.addTransitive(context.getAdditionalInputs(usePic));
+    if (featureConfiguration.isEnabled(CppRuleClasses.USE_HEADER_MODULES)
+        && (!shouldScanIncludes
+            || !featureConfiguration.isEnabled(CppRuleClasses.PRUNE_HEADER_MODULES))) {
+      realMandatoryInputsBuilder.addTransitive(context.getTransitiveModules(usePic));
+    }
+    realMandatoryInputsBuilder.addTransitive(context.getAdditionalInputs());
 
     realMandatoryInputsBuilder.add(sourceFile);
     boolean fake = tempOutputFile != null;
@@ -268,6 +273,7 @@ public class CppCompileActionBuilder {
           variables,
           sourceFile,
           shouldScanIncludes,
+          usePic,
           sourceLabel,
           realMandatoryInputsBuilder.build(),
           outputFile,
@@ -290,6 +296,7 @@ public class CppCompileActionBuilder {
           variables,
           sourceFile,
           shouldScanIncludes,
+          usePic,
           sourceLabel,
           realMandatoryInputs,
           outputFile,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java
index a1c9644ef7..f4c8e09a04 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java
@@ -25,7 +25,6 @@ import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.rules.cpp.CcCompilationOutputs.Builder;
@@ -349,24 +348,14 @@ public final class CppModel {
    * Select .pcm inputs to pass on the command line depending on whether we are in pic or non-pic
    * mode.
    */
-  private Collection<String> getHeaderModulePaths(CppCompileActionBuilder builder,
-      boolean usePic) {
+  private Collection<String> getHeaderModulePaths(CppCompileActionBuilder builder, boolean usePic) {
     Collection<String> result = new LinkedHashSet<>();
-    NestedSet<Artifact> artifacts =
+    Iterable<Artifact> artifacts =
         featureConfiguration.isEnabled(CppRuleClasses.HEADER_MODULE_INCLUDES_DEPENDENCIES)
-            ? builder.getContext().getTopLevelHeaderModules(usePic)
-            : builder.getContext().getAdditionalInputs(usePic);
+            ? builder.getContext().getTopLevelModules(usePic)
+            : builder.getContext().getTransitiveModules(usePic);
     for (Artifact artifact : artifacts) {
-      String filename = artifact.getFilename();
-      if (!filename.endsWith(".pcm")) {
-        continue;
-      }
-      // Depending on whether this specific compile action is pic or non-pic, select the
-      // corresponding header modules. Note that the compilation context might give us both
-      // from targets that are built in both modes.
-      if (usePic == filename.endsWith(".pic.pcm")) {
-        result.add(artifact.getExecPathString());
-      }
+      result.add(artifact.getExecPathString());
     }
     return result;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
index 097fd3fc6a..c53434be53 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
@@ -232,6 +232,12 @@ public class CppRuleClasses {
       "header_module_includes_dependencies";
 
   /**
+   * A string constant for switching on that header modules are pruned based on the results of
+   * include scanning.
+   */
+  public static final String PRUNE_HEADER_MODULES = "prune_header_modules";
+
+  /**
    * A string constant for the no_legacy_features feature.
    *
    * <p>If this feature is enabled, Bazel will not extend the crosstool configuration with the
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
index 874f1fd608..e31ff2ee4b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
@@ -65,6 +65,7 @@ public class FakeCppCompileAction extends CppCompileAction {
       CcToolchainFeatures.Variables variables,
       Artifact sourceFile,
       boolean shouldScanIncludes,
+      boolean usePic,
       Label sourceLabel,
       NestedSet<Artifact> mandatoryInputs,
       Artifact outputFile,
@@ -84,6 +85,7 @@ public class FakeCppCompileAction extends CppCompileAction {
         variables,
         sourceFile,
         shouldScanIncludes,
+        usePic,
         sourceLabel,
         mandatoryInputs,
         outputFile,