Don't build jobs for the same Action + ToolChain twice.

[jlebar]

Summary

Right now if the Action graph is a DAG and we encounter an action twice,
we will run it twice.

This patch is difficult to test as-is, but I have testcases for this as
used within CUDA compilation.

[jlebar]

This actually has a subtle issue not found with existing unit tests: BuildJobsForAction has an outparam and we don't set it on cache hit.

Please hold off reviewing this until I fix the problem.

[jlebar]

Fixing bug caused by missing an outparam.

Covered by tests in WIP CUDA+ptxas+fatbin patch.

Depends on D16013.

[jlebar]

OK, this is now working, please have a look. I'm not sure if it's possible to write a test as-is, but I have a test for my mistake in my WIP CUDA patch. (Also this mistake is much harder to make after D16013.)

[echristo]

So, how are you getting to the point where you're trying to create the same action twice?

-eric

[jlebar]

In D15960#324162, @echristo wrote:

So, how are you getting to the point where you're trying to create the same action twice?

-eric

In the new CUDA world, we have the following graph, which I hope will render properly:

foo.cu --> foo.s (PTX) --> foo.cubin --> foo.fatbin
               └-----------------------┙

That is, foo.s is an input to foo.cubin *and* an input to foo.fatbin.

The Driver stores each Action's inputs. So starting from the fatbin, we look at its two inputs, and try to create jobs for them. Fine. Then we look at the input to the cubin. That's foo.s, which we already visited.

[jlebar]

This comment was removed by jlebar.

[jlebar]

Pushed in r257808 with echristo's lg (sorry, didn't have the right metadata in the commit).

include/clang/Driver/Driver.h

 #include "clang/Driver/Types.h"
 #include "clang/Driver/Util.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Support/Path.h" // FIXME: Kill when CompilationInfo lands.
 
 #include <list>
+#include <map>
 #include <memory>
 #include <set>
 #include <string>
 
 namespace llvm {
 namespace opt {
   class Arg;
   class ArgList;
public:
   /// ConstructAction - Construct the appropriate action to do for
   /// \p Phase on the \p Input, taking in to account arguments
   /// like -fsyntax-only or --analyze.
   Action *ConstructPhaseAction(Compilation &C, const ToolChain &TC,
                                const llvm::opt::ArgList &Args, phases::ID Phase,
                                Action *Input) const;
 
   /// BuildJobsForAction - Construct the jobs to perform for the
-  /// action \p A.
+  /// action \p A.  Will only construct jobs for a given (Action,
+  /// ToolChain) pair once.
   InputInfo BuildJobsForAction(Compilation &C, const Action *A,
                                const ToolChain *TC, const char *BoundArch,
                                bool AtTopLevel, bool MultipleArchs,
-                               const char *LinkingOutput) const;
+                               const char *LinkingOutput,
+                               std::map<std::pair<const Action *, std::string>,
+                                        InputInfo> &CachedResults) const;
 
   /// Returns the default name for linked images (e.g., "a.out").
   const char *getDefaultImageName() const;
 
   /// GetNamedOutputPath - Return the name to use for the output of
   /// the action \p JA. The result is appended to the compilation's
   /// list of temporary or result files, as appropriate.
   ///
const ToolChain &getToolChain(const llvm::opt::ArgList &Args,
                                 const llvm::Triple &Target) const;
 
   /// @}
 
   /// \brief Get bitmasks for which option flags to include and exclude based on
   /// the driver mode.
   std::pair<unsigned, unsigned> getIncludeExcludeOptionFlagMasks() const;
 
+  /// Helper used in BuildJobsForAction.  Doesn't use the cache when building
+  /// jobs specifically for the given action, but will use the cache when
+  /// building jobs for the Action's inputs.
+  InputInfo BuildJobsForActionNoCache(
+      Compilation &C, const Action *A, const ToolChain *TC,
+      const char *BoundArch, bool AtTopLevel, bool MultipleArchs,
+      const char *LinkingOutput,
+      std::map<std::pair<const Action *, std::string>, InputInfo>
+          &CachedResults) const;
+
 public:
   /// GetReleaseVersion - Parse (([0-9]+)(.([0-9]+)(.([0-9]+)?))?)? and
   /// return the grouped values as integers. Numbers which are not
   /// provided are set to 0.
   ///
   /// \return True if the entire string was parsed (9.2), or all
   /// groups were parsed (10.3.5extrastuff). HadExtra is true if all
   /// groups were parsed but extra characters remain at the end.

lib/Driver/Driver.cpp

void Driver::BuildJobs(Compilation &C) const {
 
   // Collect the list of architectures.
   llvm::StringSet<> ArchNames;
   if (C.getDefaultToolChain().getTriple().isOSBinFormatMachO())
     for (const Arg *A : C.getArgs())
       if (A->getOption().matches(options::OPT_arch))
         ArchNames.insert(A->getValue());
 
+  // Set of (Action, canonical ToolChain triple) pairs we've built jobs for.
+  std::map<std::pair<const Action *, std::string>, InputInfo> CachedResults;
   for (Action *A : C.getActions()) {
     // If we are linking an image for multiple archs then the linker wants
     // -arch_multiple and -final_output <final image name>. Unfortunately, this
     // doesn't fit in cleanly because we have to pass this information down.
     //
     // FIXME: This is a hack; find a cleaner way to integrate this into the
     // process.
     const char *LinkingOutput = nullptr;
     if (isa<LipoJobAction>(A)) {
       if (FinalOutput)
         LinkingOutput = FinalOutput->getValue();
       else
         LinkingOutput = getDefaultImageName();
     }
 
     BuildJobsForAction(C, A, &C.getDefaultToolChain(),
                        /*BoundArch*/ nullptr,
                        /*AtTopLevel*/ true,
                        /*MultipleArchs*/ ArchNames.size() > 1,
-                       /*LinkingOutput*/ LinkingOutput);
+                       /*LinkingOutput*/ LinkingOutput, CachedResults);
   }
 
   // If the user passed -Qunused-arguments or there were errors, don't warn
   // about any unused arguments.
   if (Diags.hasErrorOccurred() ||
       C.getArgs().hasArg(options::OPT_Qunused_arguments))
     return;
 
if (Inputs->size() == 1 && isa<PreprocessJobAction>(*Inputs->begin()) &&
       !C.getArgs().hasArg(options::OPT_traditional_cpp) && !SaveTemps &&
       !C.getArgs().hasArg(options::OPT_rewrite_objc) &&
       ToolForJob->hasIntegratedCPP())
     Inputs = &(*Inputs)[0]->getInputs();
 
   return ToolForJob;
 }
 
-InputInfo Driver::BuildJobsForAction(Compilation &C, const Action *A,
-                                     const ToolChain *TC, const char *BoundArch,
-                                     bool AtTopLevel, bool MultipleArchs,
-                                     const char *LinkingOutput) const {
+InputInfo Driver::BuildJobsForAction(
+    Compilation &C, const Action *A, const ToolChain *TC, const char *BoundArch,
+    bool AtTopLevel, bool MultipleArchs, const char *LinkingOutput,
+    std::map<std::pair<const Action *, std::string>, InputInfo> &CachedResults)
+    const {
+  std::pair<const Action *, std::string> ActionTC = {
+      A, TC->getTriple().normalize()};
+  auto CachedResult = CachedResults.find(ActionTC);
+  if (CachedResult != CachedResults.end()) {
+    return CachedResult->second;
+  }
+  InputInfo Result =
+      BuildJobsForActionNoCache(C, A, TC, BoundArch, AtTopLevel, MultipleArchs,
+                                LinkingOutput, CachedResults);
+  CachedResults[ActionTC] = Result;
+  return Result;
+}
+
+InputInfo Driver::BuildJobsForActionNoCache(
+    Compilation &C, const Action *A, const ToolChain *TC, const char *BoundArch,
+    bool AtTopLevel, bool MultipleArchs, const char *LinkingOutput,
+    std::map<std::pair<const Action *, std::string>, InputInfo> &CachedResults)
+    const {
   llvm::PrettyStackTraceString CrashInfo("Building compilation jobs");
 
   InputInfoList CudaDeviceInputInfos;
   if (const CudaHostAction *CHA = dyn_cast<CudaHostAction>(A)) {
     // Append outputs of device jobs to the input list.
     for (const Action *DA : CHA->getDeviceActions()) {
-      CudaDeviceInputInfos.push_back(
-          BuildJobsForAction(C, DA, TC, nullptr, AtTopLevel,
-                             /*MultipleArchs*/ false, LinkingOutput));
+      CudaDeviceInputInfos.push_back(BuildJobsForAction(
+          C, DA, TC, nullptr, AtTopLevel,
+          /*MultipleArchs*/ false, LinkingOutput, CachedResults));
     }
     // Override current action with a real host compile action and continue
     // processing it.
     A = *CHA->begin();
   }
 
   if (const InputAction *IA = dyn_cast<InputAction>(A)) {
     // FIXME: It would be nice to not claim this here; maybe the old scheme of
if (const BindArchAction *BAA = dyn_cast<BindArchAction>(A)) {
     if (ArchName)
       TC = &getToolChain(
           C.getArgs(),
           computeTargetTriple(DefaultTargetTriple, C.getArgs(), ArchName));
     else
       TC = &C.getDefaultToolChain();
 
     return BuildJobsForAction(C, *BAA->begin(), TC, ArchName, AtTopLevel,
-                              MultipleArchs, LinkingOutput);
+                              MultipleArchs, LinkingOutput, CachedResults);
   }
 
   if (const CudaDeviceAction *CDA = dyn_cast<CudaDeviceAction>(A)) {
     // Initial processing of CudaDeviceAction carries host params.
     // Call BuildJobsForAction() again, now with correct device parameters.
     assert(CDA->getGpuArchName() && "No GPU name in device action.");
     return BuildJobsForAction(C, *CDA->begin(), C.getCudaDeviceToolChain(),
                               CDA->getGpuArchName(), CDA->isAtTopLevel(),
-                              /*MultipleArchs*/ true, LinkingOutput);
+                              /*MultipleArchs*/ true, LinkingOutput,
+                              CachedResults);
   }
 
   const ActionList *Inputs = &A->getInputs();
 
   const JobAction *JA = cast<JobAction>(A);
   const CudaHostAction *CollapsedCHA = nullptr;
   const Tool *T =
       selectToolForJob(C, isSaveTempsEnabled(), TC, JA, Inputs, CollapsedCHA);
   if (!T)
     return InputInfo();
 
   // If we've collapsed action list that contained CudaHostAction we
   // need to build jobs for device-side inputs it may have held.
   if (CollapsedCHA) {
     for (const Action *DA : CollapsedCHA->getDeviceActions()) {
-      CudaDeviceInputInfos.push_back(
-          BuildJobsForAction(C, DA, TC, "", AtTopLevel,
-                             /*MultipleArchs*/ false, LinkingOutput));
+      CudaDeviceInputInfos.push_back(BuildJobsForAction(
+          C, DA, TC, "", AtTopLevel,
+          /*MultipleArchs*/ false, LinkingOutput, CachedResults));
     }
   }
 
   // Only use pipes when there is exactly one input.
   InputInfoList InputInfos;
   for (const Action *Input : *Inputs) {
     // Treat dsymutil and verify sub-jobs as being at the top-level too, they
     // shouldn't get temporary output names.
     // FIXME: Clean this up.
     bool SubJobAtTopLevel =
         AtTopLevel && (isa<DsymutilJobAction>(A) || isa<VerifyJobAction>(A));
     InputInfos.push_back(BuildJobsForAction(C, Input, TC, BoundArch,
                                             SubJobAtTopLevel, MultipleArchs,
-                                            LinkingOutput));
+                                            LinkingOutput, CachedResults));
   }
 
   // Always use the first input as the base input.
   const char *BaseInput = InputInfos[0].getBaseInput();
 
   // ... except dsymutil actions, which use their actual input as the base
   // input.
   if (JA->getType() == types::TY_dSYM)