diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
index ea8e23b..14a2fb5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
@@ -41,7 +41,6 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
-import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.packages.RuleErrorConsumer;
@@ -87,10 +86,8 @@
    * Configures a compile action builder by setting up command line options and auxiliary inputs
    * according to the FDO configuration. This method does nothing If FDO is disabled.
    */
-  @ThreadSafe
-  public static void configureFdoBuildVariables(
-      ImmutableMap.Builder<String, String> variablesBuilder,
-      CppCompileActionBuilder builder,
+  private static void configureFdoBuildVariables(
+      Map<String, String> variablesBuilder,
       FeatureConfiguration featureConfiguration,
       FdoContext fdoContext,
       String fdoInstrument,
@@ -117,13 +114,10 @@
           fdoContext.getPrefetchHintsArtifact().getExecPathString());
     }
 
-    Iterable<Artifact> auxiliaryInputs = getAuxiliaryFdoInputs(fdoContext);
-    builder.addMandatoryInputs(auxiliaryInputs);
-
     FdoContext.BranchFdoProfile branchFdoProfile = fdoContext.getBranchFdoProfile();
     // Optimization phase
     if (branchFdoProfile != null) {
-      if (!Iterables.isEmpty(auxiliaryInputs)) {
+      if (!Iterables.isEmpty(getAuxiliaryFdoInputs(fdoContext))) {
         if (featureConfiguration.isEnabled(CppRuleClasses.AUTOFDO)
             || featureConfiguration.isEnabled(CppRuleClasses.XBINARYFDO)) {
           variablesBuilder.put(
@@ -255,6 +249,8 @@
 
   private final SourceCategory sourceCategory;
   private final List<VariablesExtension> variablesExtensions = new ArrayList<>();
+  private CcToolchainVariables prebuiltParent;
+  private CcToolchainVariables prebuiltParentWithFdo;
   @Nullable private CppModuleMap cppModuleMap;
   private boolean propagateModuleMapToCompileAction = true;
 
@@ -1361,7 +1357,7 @@
             builder,
             /* sourceLabel= */ null,
             usePic,
-            /* ccRelativeName= */ null,
+            /* needsFdoBuildVariables= */ false,
             ccCompilationContext.getCppModuleMap(),
             /* gcnoFile= */ null,
             /* isUsingFission= */ false,
@@ -1423,7 +1419,7 @@
       CppCompileActionBuilder builder,
       Label sourceLabel,
       boolean usePic,
-      PathFragment ccRelativeName,
+      boolean needsFdoBuildVariables,
       CppModuleMap cppModuleMap,
       Artifact gcnoFile,
       boolean isUsingFission,
@@ -1435,51 +1431,94 @@
     if (builder.getDotdFile() != null) {
       dotdFileExecPath = builder.getDotdFile().getExecPathString();
     }
-    ImmutableMap.Builder<String, String> allAdditionalBuildVariables = ImmutableMap.builder();
-    allAdditionalBuildVariables.putAll(additionalBuildVariables);
-    if (ccRelativeName != null) {
-      configureFdoBuildVariables(
-          allAdditionalBuildVariables,
-          builder,
-          featureConfiguration,
-          fdoContext,
-          cppConfiguration.getFdoInstrument(),
-          cppConfiguration.getCSFdoInstrument(),
-          cppConfiguration);
+    if (needsFdoBuildVariables && fdoContext.hasArtifacts(cppConfiguration)) {
+      // This modifies the passed-in builder, which is a surprising side-effect, and makes it unsafe
+      // to call this method multiple times for the same builder.
+      builder.addMandatoryInputs(getAuxiliaryFdoInputs(fdoContext));
     }
-    return CompileBuildVariables.setupVariablesOrReportRuleError(
-        ruleErrorConsumer,
-        featureConfiguration,
-        ccToolchain,
-        configuration.getOptions(),
-        cppConfiguration,
+    CcToolchainVariables parent = needsFdoBuildVariables ? prebuiltParentWithFdo : prebuiltParent;
+    // We use the prebuilt parent variables if and only if the passed in cppModuleMap is the
+    // identical to the one returned from ccCompilationContext.getCppModuleMap(): there is exactly
+    // one caller which passes in any other value (the verification module map), so this should be
+    // fine for now.
+    boolean usePrebuiltParent =
+        cppModuleMap == ccCompilationContext.getCppModuleMap()
+            // Only use the prebuilt parent if there are enough sources to make it worthwhile. The
+            // threshold was chosen by looking at a heap dump.
+            && (compilationUnitSources.size() > 1);
+    CcToolchainVariables.Builder buildVariables;
+    if (parent != null && usePrebuiltParent) {
+      // If we have a pre-built parent and we are allowed to use it, then do so.
+      buildVariables = CcToolchainVariables.builder(parent);
+    } else {
+      Map<String, String> genericAdditionalBuildVariables = new LinkedHashMap<>();
+      if (needsFdoBuildVariables) {
+        configureFdoBuildVariables(
+            genericAdditionalBuildVariables,
+            featureConfiguration,
+            fdoContext,
+            cppConfiguration.getFdoInstrument(),
+            cppConfiguration.getCSFdoInstrument(),
+            cppConfiguration);
+      }
+      buildVariables =
+          CcToolchainVariables.builder(
+              ccToolchain.getBuildVariables(configuration.getOptions(), cppConfiguration));
+      CompileBuildVariables.setupCommonVariables(
+          buildVariables,
+          featureConfiguration,
+          ImmutableList.of(),
+          cppModuleMap,
+          CppHelper.getFdoBuildStamp(cppConfiguration, fdoContext, featureConfiguration),
+          variablesExtensions,
+          genericAdditionalBuildVariables,
+          ccCompilationContext.getDirectModuleMaps(),
+          ccCompilationContext.getIncludeDirs(),
+          ccCompilationContext.getQuoteIncludeDirs(),
+          ccCompilationContext.getSystemIncludeDirs(),
+          ccCompilationContext.getFrameworkIncludeDirs(),
+          ccCompilationContext.getDefines());
+
+      if (usePrebuiltParent) {
+        parent = buildVariables.build();
+        if (needsFdoBuildVariables) {
+          prebuiltParentWithFdo = parent;
+        } else {
+          prebuiltParent = parent;
+        }
+        buildVariables = CcToolchainVariables.builder(parent);
+      }
+    }
+    if (usePic
+        && !featureConfiguration.isEnabled(CppRuleClasses.PIC)
+        && !featureConfiguration.isEnabled(CppRuleClasses.SUPPORTS_PIC)) {
+      ruleErrorConsumer.ruleError(CcCommon.PIC_CONFIGURATION_ERROR);
+    }
+
+    CompileBuildVariables.setupSpecificVariables(
+        buildVariables,
         toPathString(sourceFile),
         toPathString(builder.getOutputFile()),
         toPathString(gcnoFile),
-        isUsingFission,
         toPathString(dwoFile),
+        isUsingFission,
         toPathString(ltoIndexingFile),
-        ImmutableList.of(),
         getCopts(builder.getSourceFile(), sourceLabel),
-        cppModuleMap,
-        usePic,
-        builder.getTempOutputFile(),
-        CppHelper.getFdoBuildStamp(cppConfiguration, fdoContext, featureConfiguration),
+        toPathString(builder.getTempOutputFile()),
         dotdFileExecPath,
-        ImmutableList.copyOf(variablesExtensions),
-        allAdditionalBuildVariables.build(),
-        ccCompilationContext.getDirectModuleMaps(),
-        ccCompilationContext.getIncludeDirs(),
-        ccCompilationContext.getQuoteIncludeDirs(),
-        ccCompilationContext.getSystemIncludeDirs(),
-        ccCompilationContext.getFrameworkIncludeDirs(),
-        ccCompilationContext.getDefines());
+        usePic,
+        additionalBuildVariables);
+    return buildVariables.build();
   }
 
   private static String toPathString(Artifact a) {
     return a == null ? null : a.getExecPathString();
   }
 
+  private static String toPathString(PathFragment a) {
+    return a == null ? null : a.getSafePathString();
+  }
+
   /**
    * Returns a {@code CppCompileActionBuilder} with the common fields for a C++ compile action being
    * initialized.
@@ -1544,7 +1583,7 @@
             builder,
             sourceLabel,
             /* usePic= */ pic,
-            ccRelativeName,
+            /* needsFdoBuildVariables= */ ccRelativeName != null,
             ccCompilationContext.getCppModuleMap(),
             gcnoFile,
             generateDwo,
@@ -1598,7 +1637,7 @@
             builder,
             sourceLabel,
             generatePicAction,
-            /* ccRelativeName= */ null,
+            /* needsFdoBuildVariables= */ false,
             ccCompilationContext.getCppModuleMap(),
             /* gcnoFile= */ null,
             /* isUsingFission= */ false,
@@ -1692,7 +1731,7 @@
                 picBuilder,
                 sourceLabel,
                 /* usePic= */ true,
-                ccRelativeName,
+                /* needsFdoBuildVariables= */ ccRelativeName != null,
                 ccCompilationContext.getCppModuleMap(),
                 gcnoFile,
                 generateDwo,
@@ -1767,7 +1806,7 @@
                 builder,
                 sourceLabel,
                 /* usePic= */ false,
-                ccRelativeName,
+                /* needsFdoBuildVariables= */ ccRelativeName != null,
                 cppModuleMap,
                 gcnoFile,
                 generateDwo,
@@ -1880,7 +1919,7 @@
             builder,
             sourceLabel,
             usePic,
-            ccRelativeName,
+            /* needsFdoBuildVariables= */ ccRelativeName != null,
             ccCompilationContext.getCppModuleMap(),
             /* gcnoFile= */ null,
             /* isUsingFission= */ false,
@@ -1996,7 +2035,7 @@
             dBuilder,
             sourceLabel,
             usePic,
-            ccRelativeName,
+            /* needsFdoBuildVariables= */ ccRelativeName != null,
             ccCompilationContext.getCppModuleMap(),
             /* gcnoFile= */ null,
             /* isUsingFission= */ false,
@@ -2022,7 +2061,7 @@
             sdBuilder,
             sourceLabel,
             usePic,
-            ccRelativeName,
+            /* needsFdoBuildVariables= */ ccRelativeName != null,
             ccCompilationContext.getCppModuleMap(),
             /* gcnoFile= */ null,
             /* isUsingFission= */ false,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java
index ad1ee48..bd4b054 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java
@@ -26,6 +26,8 @@
 import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariablesExtension;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.List;
+import java.util.Map;
 
 /** Enum covering all build variables we create for all various {@link CppCompileAction}. */
 public enum CompileBuildVariables {
@@ -135,11 +137,14 @@
       Iterable<PathFragment> frameworkIncludeDirs,
       Iterable<String> defines) {
     try {
-      return setupVariablesOrThrowEvalException(
+      if (usePic
+          && !featureConfiguration.isEnabled(CppRuleClasses.PIC)
+          && !featureConfiguration.isEnabled(CppRuleClasses.SUPPORTS_PIC)) {
+        throw new EvalException(Location.BUILTIN, CcCommon.PIC_CONFIGURATION_ERROR);
+      }
+      return setupVariables(
           featureConfiguration,
-          ccToolchainProvider,
-          buildOptions,
-          cppConfiguration,
+          ccToolchainProvider.getBuildVariables(buildOptions, cppConfiguration),
           sourceFile,
           outputFile,
           gcnoFile,
@@ -194,16 +199,105 @@
       Iterable<String> frameworkIncludeDirs,
       Iterable<String> defines)
       throws EvalException {
-    Preconditions.checkNotNull(directModuleMaps);
-    Preconditions.checkNotNull(includeDirs);
-    Preconditions.checkNotNull(quoteIncludeDirs);
-    Preconditions.checkNotNull(systemIncludeDirs);
-    Preconditions.checkNotNull(frameworkIncludeDirs);
-    Preconditions.checkNotNull(defines);
-    CcToolchainVariables.Builder buildVariables =
-        CcToolchainVariables.builder(
-            ccToolchainProvider.getBuildVariables(buildOptions, cppConfiguration));
+    if (usePic
+        && !featureConfiguration.isEnabled(CppRuleClasses.PIC)
+        && !featureConfiguration.isEnabled(CppRuleClasses.SUPPORTS_PIC)) {
+      throw new EvalException(Location.BUILTIN, CcCommon.PIC_CONFIGURATION_ERROR);
+    }
+    return setupVariables(
+        featureConfiguration,
+        ccToolchainProvider.getBuildVariables(buildOptions, cppConfiguration),
+        sourceFile,
+        outputFile,
+        gcnoFile,
+        isUsingFission,
+        dwoFile,
+        ltoIndexingFile,
+        includes,
+        userCompileFlags,
+        cppModuleMap,
+        usePic,
+        fakeOutputFile,
+        fdoStamp,
+        dotdFileExecPath,
+        variablesExtensions,
+        additionalBuildVariables,
+        directModuleMaps,
+        includeDirs,
+        quoteIncludeDirs,
+        systemIncludeDirs,
+        frameworkIncludeDirs,
+        defines);
+  }
 
+  private static CcToolchainVariables setupVariables(
+      FeatureConfiguration featureConfiguration,
+      CcToolchainVariables parent,
+      String sourceFile,
+      String outputFile,
+      String gcnoFile,
+      boolean isUsingFission,
+      String dwoFile,
+      String ltoIndexingFile,
+      ImmutableList<String> includes,
+      Iterable<String> userCompileFlags,
+      CppModuleMap cppModuleMap,
+      boolean usePic,
+      String fakeOutputFile,
+      String fdoStamp,
+      String dotdFileExecPath,
+      ImmutableList<VariablesExtension> variablesExtensions,
+      ImmutableMap<String, String> additionalBuildVariables,
+      Iterable<Artifact> directModuleMaps,
+      Iterable<String> includeDirs,
+      Iterable<String> quoteIncludeDirs,
+      Iterable<String> systemIncludeDirs,
+      Iterable<String> frameworkIncludeDirs,
+      Iterable<String> defines) {
+    CcToolchainVariables.Builder buildVariables = CcToolchainVariables.builder(parent);
+    setupCommonVariablesInternal(
+        buildVariables,
+        featureConfiguration,
+        includes,
+        cppModuleMap,
+        fdoStamp,
+        variablesExtensions,
+        additionalBuildVariables,
+        directModuleMaps,
+        includeDirs,
+        quoteIncludeDirs,
+        systemIncludeDirs,
+        frameworkIncludeDirs,
+        defines);
+    setupSpecificVariables(
+        buildVariables,
+        sourceFile,
+        outputFile,
+        gcnoFile,
+        dwoFile,
+        isUsingFission,
+        ltoIndexingFile,
+        userCompileFlags,
+        fakeOutputFile,
+        dotdFileExecPath,
+        usePic,
+        ImmutableMap.of());
+    return buildVariables.build();
+  }
+
+  public static void setupSpecificVariables(
+      CcToolchainVariables.Builder buildVariables,
+      String sourceFile,
+      String outputFile,
+      String gcnoFile,
+      String dwoFile,
+      boolean isUsingFission,
+      String ltoIndexingFile,
+      Iterable<String> userCompileFlags,
+      String fakeOutputFile,
+      String dotdFileExecPath,
+      boolean usePic,
+      Map<String, String> additionalBuildVariables) {
     buildVariables.addStringSequenceVariable(
         USER_COMPILE_FLAGS.getVariableName(), userCompileFlags);
 
@@ -223,6 +317,81 @@
       buildVariables.addStringVariable(DEPENDENCY_FILE.getVariableName(), dotdFileExecPath);
     }
 
+    if (gcnoFile != null) {
+      buildVariables.addStringVariable(GCOV_GCNO_FILE.getVariableName(), gcnoFile);
+    }
+
+    if (dwoFile != null) {
+      buildVariables.addStringVariable(PER_OBJECT_DEBUG_INFO_FILE.getVariableName(), dwoFile);
+    }
+
+    if (isUsingFission) {
+      buildVariables.addStringVariable(IS_USING_FISSION.getVariableName(), "");
+    }
+
+    if (ltoIndexingFile != null) {
+      buildVariables.addStringVariable(
+          LTO_INDEXING_BITCODE_FILE.getVariableName(), ltoIndexingFile);
+    }
+
+    if (usePic) {
+      buildVariables.addStringVariable(PIC.getVariableName(), "");
+    }
+
+    buildVariables.addAllStringVariables(additionalBuildVariables);
+  }
+
+  public static void setupCommonVariables(
+      CcToolchainVariables.Builder buildVariables,
+      FeatureConfiguration featureConfiguration,
+      List<String> includes,
+      CppModuleMap cppModuleMap,
+      String fdoStamp,
+      List<VariablesExtension> variablesExtensions,
+      Map<String, String> additionalBuildVariables,
+      Iterable<Artifact> directModuleMaps,
+      Iterable<PathFragment> includeDirs,
+      Iterable<PathFragment> quoteIncludeDirs,
+      Iterable<PathFragment> systemIncludeDirs,
+      Iterable<PathFragment> frameworkIncludeDirs,
+      Iterable<String> defines) {
+    setupCommonVariablesInternal(
+        buildVariables,
+        featureConfiguration,
+        includes,
+        cppModuleMap,
+        fdoStamp,
+        variablesExtensions,
+        additionalBuildVariables,
+        directModuleMaps,
+        getSafePathStrings(includeDirs),
+        getSafePathStrings(quoteIncludeDirs),
+        getSafePathStrings(systemIncludeDirs),
+        getSafePathStrings(frameworkIncludeDirs),
+        defines);
+  }
+
+  private static void setupCommonVariablesInternal(
+      CcToolchainVariables.Builder buildVariables,
+      FeatureConfiguration featureConfiguration,
+      List<String> includes,
+      CppModuleMap cppModuleMap,
+      String fdoStamp,
+      List<VariablesExtension> variablesExtensions,
+      Map<String, String> additionalBuildVariables,
+      Iterable<Artifact> directModuleMaps,
+      Iterable<String> includeDirs,
+      Iterable<String> quoteIncludeDirs,
+      Iterable<String> systemIncludeDirs,
+      Iterable<String> frameworkIncludeDirs,
+      Iterable<String> defines) {
+    Preconditions.checkNotNull(directModuleMaps);
+    Preconditions.checkNotNull(includeDirs);
+    Preconditions.checkNotNull(quoteIncludeDirs);
+    Preconditions.checkNotNull(systemIncludeDirs);
+    Preconditions.checkNotNull(frameworkIncludeDirs);
+    Preconditions.checkNotNull(defines);
+
     if (featureConfiguration.isEnabled(CppRuleClasses.MODULE_MAPS) && cppModuleMap != null) {
       // If the feature is enabled and cppModuleMap is null, we are about to fail during analysis
       // in any case, but don't crash.
@@ -266,36 +435,10 @@
 
     buildVariables.addStringSequenceVariable(PREPROCESSOR_DEFINES.getVariableName(), allDefines);
 
-    if (usePic) {
-      if (!featureConfiguration.isEnabled(CppRuleClasses.PIC)
-          && !featureConfiguration.isEnabled(CppRuleClasses.SUPPORTS_PIC)) {
-        throw new EvalException(Location.BUILTIN, CcCommon.PIC_CONFIGURATION_ERROR);
-      }
-      buildVariables.addStringVariable(PIC.getVariableName(), "");
-    }
-
-    if (gcnoFile != null) {
-      buildVariables.addStringVariable(GCOV_GCNO_FILE.getVariableName(), gcnoFile);
-    }
-
-    if (isUsingFission) {
-      buildVariables.addStringVariable(IS_USING_FISSION.getVariableName(), "");
-    }
-    if (dwoFile != null) {
-      buildVariables.addStringVariable(PER_OBJECT_DEBUG_INFO_FILE.getVariableName(), dwoFile);
-    }
-
-    if (ltoIndexingFile != null) {
-      buildVariables.addStringVariable(
-          LTO_INDEXING_BITCODE_FILE.getVariableName(), ltoIndexingFile);
-    }
-
     buildVariables.addAllStringVariables(additionalBuildVariables);
     for (VariablesExtension extension : variablesExtensions) {
       extension.addVariables(buildVariables);
     }
-
-    return buildVariables.build();
   }
 
   /** Get the safe path strings for a list of paths to use in the build variables. */
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 da44be5..8a71ad6 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
@@ -58,7 +58,7 @@
   private Artifact outputFile;
   private Artifact dwoFile;
   private Artifact ltoIndexingFile;
-  private PathFragment tempOutputFile;
+  @Nullable private PathFragment tempOutputFile;
   private Artifact dotdFile;
   private Artifact gcnoFile;
   private CcCompilationContext ccCompilationContext = CcCompilationContext.EMPTY;
@@ -140,6 +140,7 @@
     this.builtinIncludeDirectories = other.builtinIncludeDirectories;
   }
 
+  @Nullable
   public PathFragment getTempOutputFile() {
     return tempOutputFile;
   }