1//===--- ModulesDriver.cpp - Driver managed module builds -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines functionality to support driver managed builds for
11/// compilations which use Clang modules or standard C++20 named modules.
12///
13//===----------------------------------------------------------------------===//
14
15#include "clang/Driver/ModulesDriver.h"
16#include "clang/Basic/Diagnostic.h"
17#include "clang/Basic/LLVM.h"
18#include "clang/DependencyScanning/DependencyScanningUtils.h"
19#include "clang/Driver/Compilation.h"
20#include "clang/Driver/Driver.h"
21#include "clang/Driver/Job.h"
22#include "clang/Driver/Tool.h"
23#include "clang/Driver/ToolChain.h"
24#include "clang/Frontend/StandaloneDiagnostic.h"
25#include "llvm/ADT/DenseSet.h"
26#include "llvm/ADT/DepthFirstIterator.h"
27#include "llvm/ADT/DirectedGraph.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/SmallVectorExtras.h"
30#include "llvm/ADT/TypeSwitch.h"
31#include "llvm/ADT/iterator_range.h"
32#include "llvm/Support/Casting.h"
33#include "llvm/Support/GraphWriter.h"
34#include "llvm/Support/JSON.h"
35#include "llvm/Support/Path.h"
36#include "llvm/Support/PrettyStackTrace.h"
37#include "llvm/Support/ThreadPool.h"
38#include "llvm/Support/VirtualFileSystem.h"
39#include <utility>
40
41namespace deps = clang::dependencies;
42
43using namespace llvm::opt;
44using namespace clang;
45using namespace driver;
46using namespace modules;
47
48namespace clang::driver::modules {
49static bool fromJSON(const llvm::json::Value &Params,
50 StdModuleManifest::Module::LocalArguments &LocalArgs,
51 llvm::json::Path P) {
52 llvm::json::ObjectMapper O(Params, P);
53 return O.mapOptional(Prop: "system-include-directories",
54 Out&: LocalArgs.SystemIncludeDirs);
55}
56
57static bool fromJSON(const llvm::json::Value &Params,
58 StdModuleManifest::Module &ModuleEntry,
59 llvm::json::Path P) {
60 llvm::json::ObjectMapper O(Params, P);
61 return O.map(Prop: "is-std-library", Out&: ModuleEntry.IsStdlib) &&
62 O.map(Prop: "logical-name", Out&: ModuleEntry.LogicalName) &&
63 O.map(Prop: "source-path", Out&: ModuleEntry.SourcePath) &&
64 O.mapOptional(Prop: "local-arguments", Out&: ModuleEntry.LocalArgs);
65}
66
67static bool fromJSON(const llvm::json::Value &Params,
68 StdModuleManifest &Manifest, llvm::json::Path P) {
69 llvm::json::ObjectMapper O(Params, P);
70 return O.map(Prop: "modules", Out&: Manifest.Modules);
71}
72} // namespace clang::driver::modules
73
74/// Parses the Standard library module manifest from \p Buffer.
75static Expected<StdModuleManifest> parseManifest(StringRef Buffer) {
76 auto ParsedOrErr = llvm::json::parse(JSON: Buffer);
77 if (!ParsedOrErr)
78 return ParsedOrErr.takeError();
79
80 StdModuleManifest Manifest;
81 llvm::json::Path::Root Root;
82 if (!fromJSON(Params: *ParsedOrErr, Manifest, P: Root))
83 return Root.getError();
84
85 return Manifest;
86}
87
88/// Converts each file path in manifest from relative to absolute.
89///
90/// Each file path in the manifest is expected to be relative the manifest's
91/// location \p ManifestPath itself.
92static void makeManifestPathsAbsolute(
93 MutableArrayRef<StdModuleManifest::Module> ManifestEntries,
94 StringRef ManifestPath) {
95 StringRef ManifestDir = llvm::sys::path::parent_path(path: ManifestPath);
96 SmallString<256> TempPath;
97
98 auto PrependManifestDir = [&](StringRef Path) {
99 TempPath = ManifestDir;
100 llvm::sys::path::append(path&: TempPath, a: Path);
101 return std::string(TempPath);
102 };
103
104 for (auto &Entry : ManifestEntries) {
105 Entry.SourcePath = PrependManifestDir(Entry.SourcePath);
106 if (!Entry.LocalArgs)
107 continue;
108
109 for (auto &IncludeDir : Entry.LocalArgs->SystemIncludeDirs)
110 IncludeDir = PrependManifestDir(IncludeDir);
111 }
112}
113
114Expected<StdModuleManifest>
115driver::modules::readStdModuleManifest(StringRef ManifestPath,
116 llvm::vfs::FileSystem &VFS) {
117 auto MemBufOrErr = VFS.getBufferForFile(Name: ManifestPath);
118 if (!MemBufOrErr)
119 return llvm::createFileError(F: ManifestPath, EC: MemBufOrErr.getError());
120
121 auto ManifestOrErr = parseManifest(Buffer: (*MemBufOrErr)->getBuffer());
122 if (!ManifestOrErr)
123 return ManifestOrErr.takeError();
124 auto Manifest = std::move(*ManifestOrErr);
125
126 makeManifestPathsAbsolute(ManifestEntries: Manifest.Modules, ManifestPath);
127 return Manifest;
128}
129
130void driver::modules::buildStdModuleManifestInputs(
131 ArrayRef<StdModuleManifest::Module> ManifestEntries, Compilation &C,
132 InputList &Inputs) {
133 DerivedArgList &Args = C.getArgs();
134 const OptTable &Opts = C.getDriver().getOpts();
135 for (const auto &Entry : ManifestEntries) {
136 auto *InputArg =
137 makeInputArg(Args, Opts, Value: Args.MakeArgString(Str: Entry.SourcePath));
138 Inputs.emplace_back(Args: types::TY_CXXModule, Args&: InputArg);
139 }
140}
141
142using ManifestEntryLookup =
143 llvm::DenseMap<StringRef, const StdModuleManifest::Module *>;
144
145/// Builds a mapping from a module's source path to its entry in the manifest.
146static ManifestEntryLookup
147buildManifestLookupMap(ArrayRef<StdModuleManifest::Module> ManifestEntries) {
148 ManifestEntryLookup ManifestEntryBySource;
149 for (auto &Entry : ManifestEntries) {
150 [[maybe_unused]] const bool Inserted =
151 ManifestEntryBySource.try_emplace(Key: Entry.SourcePath, Args: &Entry).second;
152 assert(Inserted &&
153 "Manifest defines multiple modules with the same source path.");
154 }
155 return ManifestEntryBySource;
156}
157
158/// Returns the manifest entry corresponding to \p Job, or \c nullptr if none
159/// exists.
160static const StdModuleManifest::Module *
161getManifestEntryForCommand(const Command &Job,
162 const ManifestEntryLookup &ManifestEntryBySource) {
163 for (const auto &II : Job.getInputInfos()) {
164 if (const auto It = ManifestEntryBySource.find(Val: II.getFilename());
165 It != ManifestEntryBySource.end())
166 return It->second;
167 }
168 return nullptr;
169}
170
171/// Adds all \p SystemIncludeDirs to the \p CC1Args of \p Job.
172static void
173addSystemIncludeDirsFromManifest(Compilation &C, Command &Job,
174 ArgStringList &CC1Args,
175 ArrayRef<std::string> SystemIncludeDirs) {
176 const ToolChain &TC = Job.getCreator().getToolChain();
177 const DerivedArgList &TCArgs =
178 C.getArgsForToolChain(TC: &TC, BoundArch: Job.getSource().getOffloadingArch(),
179 DeviceOffloadKind: Job.getSource().getOffloadingDeviceKind());
180
181 for (const auto &IncludeDir : SystemIncludeDirs)
182 TC.addSystemInclude(DriverArgs: TCArgs, CC1Args, Path: IncludeDir);
183}
184
185static bool isCC1Job(const Command &Job) {
186 return StringRef(Job.getCreator().getName()) == "clang";
187}
188
189/// Apply command-line modifications specific for inputs originating from the
190/// Standard library module manifest.
191static void applyArgsForStdModuleManifestInputs(
192 Compilation &C, const ManifestEntryLookup &ManifestEntryBySource,
193 MutableArrayRef<std::unique_ptr<Command>> Jobs) {
194 for (auto &Job : Jobs) {
195 if (!isCC1Job(Job: *Job))
196 continue;
197
198 const auto *Entry = getManifestEntryForCommand(Job: *Job, ManifestEntryBySource);
199 if (!Entry)
200 continue;
201
202 auto CC1Args = Job->getArguments();
203 if (Entry->IsStdlib)
204 CC1Args.push_back(Elt: "-Wno-reserved-module-identifier");
205 if (Entry->LocalArgs)
206 addSystemIncludeDirsFromManifest(C, Job&: *Job, CC1Args,
207 SystemIncludeDirs: Entry->LocalArgs->SystemIncludeDirs);
208 Job->replaceArguments(List: CC1Args);
209 }
210}
211
212/// Computes the -fmodule-cache-path for this compilation.
213static std::optional<std::string>
214getModuleCachePath(llvm::opt::DerivedArgList &Args) {
215 if (const Arg *A = Args.getLastArg(Ids: options::OPT_fmodules_cache_path))
216 return A->getValue();
217
218 if (SmallString<128> Path; Driver::getDefaultModuleCachePath(Result&: Path))
219 return std::string(Path);
220
221 return std::nullopt;
222}
223
224/// Returns true if a dependency scan can be performed using \p Job.
225static bool isDependencyScannableJob(const Command &Job) {
226 if (!isCC1Job(Job))
227 return false;
228 const auto &InputInfos = Job.getInputInfos();
229 return !InputInfos.empty() && types::isSrcFile(Id: InputInfos.front().getType());
230}
231
232namespace {
233/// Pool of reusable dependency scanning workers and their contexts with
234/// RAII-based acquire/release.
235class ScanningWorkerPool {
236public:
237 ScanningWorkerPool(size_t NumWorkers,
238 deps::DependencyScanningService &ScanningService) {
239 for (size_t I = 0; I < NumWorkers; ++I)
240 Slots.emplace_back(Args&: ScanningService);
241
242 AvailableSlots.resize(N: NumWorkers);
243 std::iota(first: AvailableSlots.begin(), last: AvailableSlots.end(), value: 0);
244 }
245
246 /// Acquires a unique pointer to a dependency scanning worker and its
247 /// context.
248 ///
249 /// The worker bundle automatically released back to the pool when the
250 /// pointer is destroyed. The pool has to outlive the leased worker bundle.
251 [[nodiscard]] auto scopedAcquire() {
252 std::unique_lock<std::mutex> UL(Lock);
253 CV.wait(lock&: UL, p: [&] { return !AvailableSlots.empty(); });
254 const size_t Index = AvailableSlots.pop_back_val();
255 auto ReleaseHandle = [this, Index](WorkerBundle *) { release(Index); };
256 return std::unique_ptr<WorkerBundle, decltype(ReleaseHandle)>(
257 &Slots[Index], ReleaseHandle);
258 }
259
260private:
261 /// Releases the worker bundle at \c Index back into the pool.
262 void release(size_t Index) {
263 {
264 std::scoped_lock<std::mutex> SL(Lock);
265 AvailableSlots.push_back(Elt: Index);
266 }
267 CV.notify_one();
268 }
269
270 /// A scanning worker with its associated context.
271 struct WorkerBundle {
272 WorkerBundle(deps::DependencyScanningService &ScanningService)
273 : Worker(std::make_unique<deps::DependencyScanningWorker>(
274 args&: ScanningService)) {}
275
276 std::unique_ptr<deps::DependencyScanningWorker> Worker;
277 llvm::DenseSet<deps::ModuleID> SeenModules;
278 };
279
280 std::mutex Lock;
281 std::condition_variable CV;
282 SmallVector<size_t> AvailableSlots;
283 SmallVector<WorkerBundle, 0> Slots;
284};
285} // anonymous namespace
286
287// Creates a ThreadPool and a corresponding ScanningWorkerPool optimized for
288// the configuration of dependency scan inputs.
289static std::pair<std::unique_ptr<llvm::ThreadPoolInterface>,
290 std::unique_ptr<ScanningWorkerPool>>
291createOptimalThreadAndWorkerPool(
292 size_t NumScanInputs, bool HasStdlibModuleInputs,
293 deps::DependencyScanningService &ScanningService) {
294 // TODO: Benchmark: Determine the optimal number of worker threads for a
295 // given number of inputs. How many inputs are required for multi-threading
296 // to be beneficial? How many inputs should each thread scan at least?
297#if LLVM_ENABLE_THREADS
298 std::unique_ptr<llvm::ThreadPoolInterface> ThreadPool;
299 size_t WorkerCount;
300
301 if (NumScanInputs == 1 || (HasStdlibModuleInputs && NumScanInputs <= 2)) {
302 auto S = llvm::optimal_concurrency(TaskCount: 1);
303 ThreadPool = std::make_unique<llvm::SingleThreadExecutor>(args: std::move(S));
304 WorkerCount = 1;
305 } else {
306 auto ThreadPoolStrategy = llvm::optimal_concurrency(
307 TaskCount: NumScanInputs - static_cast<size_t>(HasStdlibModuleInputs));
308 ThreadPool = std::make_unique<llvm::DefaultThreadPool>(
309 args: std::move(ThreadPoolStrategy));
310 const size_t MaxConcurrency = ThreadPool->getMaxConcurrency();
311 const size_t MaxConcurrentlyScannedInputs =
312 NumScanInputs -
313 (HasStdlibModuleInputs && NumScanInputs < MaxConcurrency ? 1 : 0);
314 WorkerCount = std::min(a: MaxConcurrency, b: MaxConcurrentlyScannedInputs);
315 }
316#else
317 auto ThreadPool = std::make_unique<llvm::SingleThreadExecutor>();
318 size_t WorkerCount = 1;
319#endif
320
321 return {std::move(ThreadPool),
322 std::make_unique<ScanningWorkerPool>(args&: WorkerCount, args&: ScanningService)};
323}
324
325static StringRef getTriple(const Command &Job) {
326 return Job.getCreator().getToolChain().getTriple().getTriple();
327}
328
329using ModuleNameAndTriple = std::pair<StringRef, StringRef>;
330
331namespace {
332/// Helper to schedule on-demand dependency scans for modules originating from
333/// the Standard library module manifest.
334struct StdlibModuleScanScheduler {
335 StdlibModuleScanScheduler(const llvm::DenseMap<ModuleNameAndTriple, size_t>
336 &StdlibModuleScanIndexByID)
337 : StdlibModuleScanIndexByID(StdlibModuleScanIndexByID) {
338 ScheduledScanInputs.reserve(Size: StdlibModuleScanIndexByID.size());
339 }
340
341 /// Returns the indices of scan inputs corresponding to newly imported
342 /// Standard library modules.
343 ///
344 /// Thread-safe.
345 SmallVector<size_t, 2> getNewScanInputs(ArrayRef<std::string> NamedModuleDeps,
346 StringRef Triple) {
347 SmallVector<size_t, 2> NewScanInputs;
348 std::scoped_lock<std::mutex> Guard(Lock);
349 for (const auto &ModuleName : NamedModuleDeps) {
350 const auto It = StdlibModuleScanIndexByID.find(Val: {ModuleName, Triple});
351 if (It == StdlibModuleScanIndexByID.end())
352 continue;
353 const size_t ScanIndex = It->second;
354 const bool AlreadyScheduled =
355 !ScheduledScanInputs.insert(V: ScanIndex).second;
356 if (AlreadyScheduled)
357 continue;
358 NewScanInputs.push_back(Elt: ScanIndex);
359 }
360 return NewScanInputs;
361 }
362
363private:
364 const llvm::DenseMap<ModuleNameAndTriple, size_t> &StdlibModuleScanIndexByID;
365 llvm::SmallDenseSet<size_t> ScheduledScanInputs;
366 std::mutex Lock;
367};
368
369/// Collects diagnostics in a form that can be retained until after their
370/// associated SourceManager is destroyed.
371class StandaloneDiagCollector : public DiagnosticConsumer {
372public:
373 void BeginSourceFile(const LangOptions &LangOpts,
374 const Preprocessor *PP = nullptr) override {
375 this->LangOpts = &LangOpts;
376 }
377
378 void HandleDiagnostic(DiagnosticsEngine::Level Level,
379 const Diagnostic &Info) override {
380 StoredDiagnostic StoredDiag(Level, Info);
381 StandaloneDiags.emplace_back(Args: *LangOpts, Args&: StoredDiag);
382 DiagnosticConsumer::HandleDiagnostic(DiagLevel: Level, Info);
383 }
384
385 SmallVector<StandaloneDiagnostic, 0> takeDiagnostics() {
386 return std::move(StandaloneDiags);
387 }
388
389private:
390 const LangOptions *LangOpts = nullptr;
391 SmallVector<StandaloneDiagnostic, 0> StandaloneDiags;
392};
393
394/// RAII utility to report collected StandaloneDiagnostic through a
395/// DiagnosticsEngine.
396///
397/// The driver's DiagnosticsEngine usually does not have a SourceManager at
398/// this point of building the compilation, in which case the
399/// StandaloneDiagReporter supplies its own.
400class StandaloneDiagReporter {
401public:
402 explicit StandaloneDiagReporter(DiagnosticsEngine &Diags) : Diags(Diags) {
403 if (!Diags.hasSourceManager()) {
404 FileSystemOptions Opts;
405 Opts.WorkingDir = ".";
406 OwnedFileMgr = llvm::makeIntrusiveRefCnt<FileManager>(A: std::move(Opts));
407 OwnedSrcMgr =
408 llvm::makeIntrusiveRefCnt<SourceManager>(A&: Diags, A&: *OwnedFileMgr);
409 }
410 }
411
412 /// Emits all diagnostics in \c StandaloneDiags using the associated
413 /// DiagnosticsEngine.
414 void Report(ArrayRef<StandaloneDiagnostic> StandaloneDiags) const {
415 llvm::StringMap<SourceLocation> SrcLocCache;
416 Diags.getClient()->BeginSourceFile(LangOpts: LangOptions(), PP: nullptr);
417 for (const auto &StandaloneDiag : StandaloneDiags) {
418 const auto StoredDiag = translateStandaloneDiag(
419 FileMgr&: getFileManager(), SrcMgr&: getSourceManager(), StandaloneDiag, SrcLocCache);
420 Diags.Report(storedDiag: StoredDiag);
421 }
422 Diags.getClient()->EndSourceFile();
423 }
424
425private:
426 DiagnosticsEngine &Diags;
427 IntrusiveRefCntPtr<FileManager> OwnedFileMgr;
428 IntrusiveRefCntPtr<SourceManager> OwnedSrcMgr;
429
430 FileManager &getFileManager() const {
431 if (OwnedFileMgr)
432 return *OwnedFileMgr;
433 return Diags.getSourceManager().getFileManager();
434 }
435
436 SourceManager &getSourceManager() const {
437 if (OwnedSrcMgr)
438 return *OwnedSrcMgr;
439 return Diags.getSourceManager();
440 }
441};
442} // anonymous namespace
443
444/// Report the diagnostics collected during each dependency scan.
445static void reportAllScanDiagnostics(
446 SmallVectorImpl<SmallVector<StandaloneDiagnostic, 0>> &&AllScanDiags,
447 DiagnosticsEngine &Diags) {
448 StandaloneDiagReporter Reporter(Diags);
449 for (auto &SingleScanDiags : AllScanDiags)
450 Reporter.Report(StandaloneDiags: SingleScanDiags);
451}
452
453/// Construct a path for the explicitly built PCM.
454static std::string constructPCMPath(const deps::ModuleID &ID,
455 StringRef OutputDir) {
456 assert(!ID.ModuleName.empty() && !ID.ContextHash.empty() &&
457 "Invalid ModuleID!");
458 SmallString<256> ExplicitPCMPath(OutputDir);
459 llvm::sys::path::append(path&: ExplicitPCMPath, a: ID.ContextHash,
460 b: ID.ModuleName + "-" + ID.ContextHash + ".pcm");
461 return std::string(ExplicitPCMPath);
462}
463
464namespace {
465/// A simple dependency action controller that only provides module lookup for
466/// Clang modules.
467class ModuleLookupController : public deps::DependencyActionController {
468public:
469 ModuleLookupController(StringRef OutputDir) : OutputDir(OutputDir) {}
470
471 std::string lookupModuleOutput(const deps::ModuleDeps &MD,
472 deps::ModuleOutputKind Kind) override {
473 if (Kind == deps::ModuleOutputKind::ModuleFile)
474 return constructPCMPath(ID: MD.ID, OutputDir);
475
476 // Driver command lines that trigger lookups for unsupported
477 // ModuleOutputKinds are not supported by the modules driver. Those
478 // command lines should probably be adjusted or rejected in
479 // Driver::handleArguments or Driver::HandleImmediateArgs.
480 llvm::reportFatalInternalError(
481 reason: "call to lookupModuleOutput with unexpected ModuleOutputKind");
482 }
483
484 std::unique_ptr<DependencyActionController> clone() const override {
485 return std::make_unique<ModuleLookupController>(args: OutputDir);
486 }
487
488private:
489 StringRef OutputDir;
490};
491
492/// The full dependencies for a specific command-line input.
493struct InputDependencies {
494 /// The name of the C++20 module provided by this translation unit.
495 std::string ModuleName;
496
497 /// A list of modules this translation unit directly depends on, not including
498 /// transitive dependencies.
499 ///
500 /// This may include modules with a different context hash when it can be
501 /// determined that the differences are benign for this compilation.
502 std::vector<deps::ModuleID> ClangModuleDeps;
503
504 /// A list of the C++20 named modules this translation unit depends on.
505 ///
506 /// These correspond only to modules built with compatible compiler
507 /// invocations.
508 std::vector<std::string> NamedModuleDeps;
509
510 /// A collection of absolute paths to files that this translation unit
511 /// directly depends on, not including transitive dependencies.
512 std::vector<std::string> FileDeps;
513
514 /// The compiler invocation with modifications to properly import all Clang
515 /// module dependencies. Does not include argv[0].
516 std::vector<std::string> BuildArgs;
517};
518} // anonymous namespace
519
520static InputDependencies makeInputDeps(deps::TranslationUnitDeps &&TUDeps) {
521 InputDependencies InputDeps;
522 InputDeps.ModuleName = std::move(TUDeps.ID.ModuleName);
523 InputDeps.NamedModuleDeps = std::move(TUDeps.NamedModuleDeps);
524 InputDeps.ClangModuleDeps = std::move(TUDeps.ClangModuleDeps);
525 InputDeps.FileDeps = std::move(TUDeps.FileDeps);
526 assert(TUDeps.Commands.size() == 1 && "Expected exactly one command");
527 InputDeps.BuildArgs = std::move(TUDeps.Commands.front().Arguments);
528 return InputDeps;
529}
530
531/// Constructs the full command line, including the executable, for \p Job.
532static SmallVector<std::string, 0> buildCommandLine(const Command &Job) {
533 const auto &JobArgs = Job.getArguments();
534 SmallVector<std::string, 0> CommandLine;
535 CommandLine.reserve(N: JobArgs.size() + 1);
536 CommandLine.emplace_back(Args: Job.getExecutable());
537 for (const char *Arg : JobArgs)
538 CommandLine.emplace_back(Args&: Arg);
539 return CommandLine;
540}
541
542/// Performs a dependency scan for a single job.
543///
544/// \returns a pair containing TranslationUnitDeps on success, or std::nullopt
545/// on failure, along with any diagnostics produced.
546static std::pair<std::optional<deps::TranslationUnitDeps>,
547 SmallVector<StandaloneDiagnostic, 0>>
548scanDependenciesForJob(const Command &Job, ScanningWorkerPool &WorkerPool,
549 StringRef WorkingDirectory,
550 ModuleLookupController &LookupController) {
551 StandaloneDiagCollector DiagConsumer;
552 std::optional<deps::TranslationUnitDeps> MaybeTUDeps;
553
554 {
555 const auto CC1CommandLine = buildCommandLine(Job);
556 auto WorkerBundleHandle = WorkerPool.scopedAcquire();
557 deps::FullDependencyConsumer DepConsumer(WorkerBundleHandle->SeenModules);
558
559 if (WorkerBundleHandle->Worker->computeDependencies(
560 WorkingDirectory, CommandLine: CC1CommandLine, DepConsumer, Controller&: LookupController,
561 DiagConsumer))
562 MaybeTUDeps = DepConsumer.takeTranslationUnitDeps();
563 }
564
565 return {std::move(MaybeTUDeps), DiagConsumer.takeDiagnostics()};
566}
567
568namespace {
569struct DependencyScanResult {
570 /// Indices of jobs that were successfully scanned.
571 SmallVector<size_t> ScannedJobIndices;
572
573 /// Input dependencies for scanned jobs. Parallel to \c ScannedJobIndices.
574 SmallVector<InputDependencies, 0> InputDepsForScannedJobs;
575
576 /// Module dependency graphs for scanned jobs. Parallel to \c
577 /// ScannedJobIndices.
578 SmallVector<deps::ModuleDepsGraph, 0> ModuleDepGraphsForScannedJobs;
579
580 /// Indices of Standard library module jobs not discovered as dependencies.
581 SmallVector<size_t> UnusedStdlibModuleJobIndices;
582
583 /// Indices of jobs that could not be scanned (e.g. image jobs, ...).
584 SmallVector<size_t> NonScannableJobIndices;
585};
586} // anonymous namespace
587
588/// Scans the compilations job list \p Jobs for module dependencies.
589///
590/// Standard library module jobs are scanned on demand if imported by any
591/// user-provided input.
592///
593/// \returns DependencyScanResult on success, or std::nullopt on failure, with
594/// diagnostics reported via \p Diags in both cases.
595static std::optional<DependencyScanResult> scanDependencies(
596 ArrayRef<std::unique_ptr<Command>> Jobs,
597 llvm::DenseMap<StringRef, const StdModuleManifest::Module *> ManifestLookup,
598 StringRef ModuleCachePath, StringRef WorkingDirectory,
599 DiagnosticsEngine &Diags) {
600 llvm::PrettyStackTraceString CrashInfo("Performing module dependency scan.");
601
602 // Classify the jobs based on scan eligibility.
603 SmallVector<size_t> ScannableJobIndices;
604 SmallVector<size_t> NonScannableJobIndices;
605 for (const auto &&[Index, Job] : llvm::enumerate(First&: Jobs)) {
606 if (isDependencyScannableJob(Job: *Job))
607 ScannableJobIndices.push_back(Elt: Index);
608 else
609 NonScannableJobIndices.push_back(Elt: Index);
610 }
611
612 // Classify scannable jobs by origin. User-provided inputs will be scanned
613 // immediately, while Standard library modules are indexed for on-demand
614 // scanning when discovered as dependencies.
615 SmallVector<size_t> UserInputScanIndices;
616 llvm::DenseMap<ModuleNameAndTriple, size_t> StdlibModuleScanIndexByID;
617 for (const auto &&[ScanIndex, JobIndex] :
618 llvm::enumerate(First&: ScannableJobIndices)) {
619 const Command &ScanJob = *Jobs[JobIndex];
620 if (const auto *Entry =
621 getManifestEntryForCommand(Job: ScanJob, ManifestEntryBySource: ManifestLookup)) {
622 ModuleNameAndTriple ID{Entry->LogicalName, getTriple(Job: ScanJob)};
623 [[maybe_unused]] const bool Inserted =
624 StdlibModuleScanIndexByID.try_emplace(Key: ID, Args&: ScanIndex).second;
625 assert(Inserted &&
626 "Multiple jobs build the same module for the same triple.");
627 } else {
628 UserInputScanIndices.push_back(Elt: ScanIndex);
629 }
630 }
631
632 // Initialize the scan context.
633 const size_t NumScanInputs = ScannableJobIndices.size();
634 const bool HasStdlibModuleInputs = !StdlibModuleScanIndexByID.empty();
635
636 deps::DependencyScanningServiceOptions Opts;
637 deps::DependencyScanningService ScanningService(std::move(Opts));
638
639 std::unique_ptr<llvm::ThreadPoolInterface> ThreadPool;
640 std::unique_ptr<ScanningWorkerPool> WorkerPool;
641 std::tie(args&: ThreadPool, args&: WorkerPool) = createOptimalThreadAndWorkerPool(
642 NumScanInputs, HasStdlibModuleInputs, ScanningService);
643
644 StdlibModuleScanScheduler StdlibModuleRegistry(StdlibModuleScanIndexByID);
645 ModuleLookupController LookupController(ModuleCachePath);
646
647 // Scan results are indexed by ScanIndex into ScannableJobIndices, not by
648 // JobIndex into Jobs. This allows one result slot per scannable job.
649 SmallVector<std::optional<deps::TranslationUnitDeps>, 0> AllScanResults(
650 NumScanInputs);
651 SmallVector<SmallVector<StandaloneDiagnostic, 0>, 0> AllScanDiags(
652 NumScanInputs);
653 std::atomic<bool> HasError{false};
654
655 // Scans the job at the given scan index and schedules scans for any newly
656 // discovered Standard library module dependencies.
657 std::function<void(size_t)> ScanOneAndScheduleNew;
658 ScanOneAndScheduleNew = [&](size_t ScanIndex) {
659 const size_t JobIndex = ScannableJobIndices[ScanIndex];
660 const Command &Job = *Jobs[JobIndex];
661 auto [MaybeTUDeps, ScanDiags] = scanDependenciesForJob(
662 Job, WorkerPool&: *WorkerPool, WorkingDirectory, LookupController);
663
664 // Store diagnostics even for successful scans to also capture any warnings
665 // or notes.
666 assert(AllScanDiags[ScanIndex].empty() &&
667 "Each slot should be written to at most once.");
668 AllScanDiags[ScanIndex] = std::move(ScanDiags);
669
670 if (!MaybeTUDeps) {
671 HasError.store(i: true, m: std::memory_order_relaxed);
672 return;
673 }
674
675 // Schedule scans for newly discovered Standard library module dependencies.
676 const auto NewScanInputs = StdlibModuleRegistry.getNewScanInputs(
677 NamedModuleDeps: MaybeTUDeps->NamedModuleDeps, Triple: getTriple(Job));
678 for (const size_t NewScanIndex : NewScanInputs)
679 ThreadPool->async(
680 F: [&, NewScanIndex]() { ScanOneAndScheduleNew(NewScanIndex); });
681
682 assert(!AllScanResults[ScanIndex].has_value() &&
683 "Each slot should be written to at most once.");
684 AllScanResults[ScanIndex] = std::move(MaybeTUDeps);
685 };
686
687 // Initiate the scan with all jobs for user-provided inputs.
688 for (const size_t ScanIndex : UserInputScanIndices)
689 ThreadPool->async(F: [&ScanOneAndScheduleNew, ScanIndex]() {
690 ScanOneAndScheduleNew(ScanIndex);
691 });
692 ThreadPool->wait();
693
694 reportAllScanDiagnostics(AllScanDiags: std::move(AllScanDiags), Diags);
695 if (HasError.load(m: std::memory_order_relaxed))
696 return std::nullopt;
697
698 // Collect results, mapping scan indices back to job indices.
699 DependencyScanResult Result;
700 for (auto &&[JobIndex, MaybeTUDeps] :
701 llvm::zip_equal(t&: ScannableJobIndices, u&: AllScanResults)) {
702 if (MaybeTUDeps) {
703 Result.ScannedJobIndices.push_back(Elt: JobIndex);
704 Result.ModuleDepGraphsForScannedJobs.push_back(
705 Elt: std::move(MaybeTUDeps->ModuleGraph));
706 Result.InputDepsForScannedJobs.push_back(
707 Elt: makeInputDeps(TUDeps: std::move(*MaybeTUDeps)));
708 } else
709 Result.UnusedStdlibModuleJobIndices.push_back(Elt: JobIndex);
710 }
711 Result.NonScannableJobIndices = std::move(NonScannableJobIndices);
712
713#ifndef NDEBUG
714 llvm::SmallDenseSet<size_t> SeenJobIndices;
715 SeenJobIndices.insert_range(Result.ScannedJobIndices);
716 SeenJobIndices.insert_range(Result.UnusedStdlibModuleJobIndices);
717 SeenJobIndices.insert_range(Result.NonScannableJobIndices);
718 assert(llvm::all_of(llvm::index_range(0, Jobs.size()),
719 [&](size_t JobIndex) {
720 return SeenJobIndices.contains(JobIndex);
721 }) &&
722 "Scan result must partition all jobs");
723#endif
724
725 return Result;
726}
727
728namespace {
729class CGNode;
730class CGEdge;
731using CGNodeBase = llvm::DGNode<CGNode, CGEdge>;
732using CGEdgeBase = llvm::DGEdge<CGNode, CGEdge>;
733using CGBase = llvm::DirectedGraph<CGNode, CGEdge>;
734
735/// Compilation Graph Node
736class CGNode : public CGNodeBase {
737public:
738 enum class NodeKind {
739 ClangModuleCC1Job,
740 NamedModuleCC1Job,
741 NonModuleCC1Job,
742 MiscJob,
743 ImageJob,
744 Root,
745 };
746
747 CGNode(const NodeKind K) : Kind(K) {}
748 CGNode(const CGNode &) = delete;
749 CGNode(CGNode &&) = delete;
750 virtual ~CGNode() = 0;
751
752 NodeKind getKind() const { return Kind; }
753
754private:
755 NodeKind Kind;
756};
757CGNode::~CGNode() = default;
758
759/// Subclass of CGNode representing the root node of the graph.
760///
761/// The root node is a special node that connects to all other nodes with
762/// no incoming edges, so that there is always a path from it to any node
763/// in the graph.
764///
765/// There should only be one such node in a given graph.
766class RootNode : public CGNode {
767public:
768 RootNode() : CGNode(NodeKind::Root) {}
769 ~RootNode() override = default;
770
771 static bool classof(const CGNode *N) {
772 return N->getKind() == NodeKind::Root;
773 }
774};
775
776/// Base class for any CGNode type that represents a job.
777class JobNode : public CGNode {
778public:
779 JobNode(std::unique_ptr<Command> &&Job, NodeKind Kind)
780 : CGNode(Kind), Job(std::move(Job)) {
781 assert(this->Job && "Expected valid job!");
782 }
783 virtual ~JobNode() override = 0;
784
785 std::unique_ptr<Command> Job;
786
787 static bool classof(const CGNode *N) {
788 return N->getKind() != NodeKind::Root;
789 }
790};
791JobNode::~JobNode() = default;
792
793/// Subclass of CGNode representing a -cc1 job which produces a Clang module.
794class ClangModuleJobNode : public JobNode {
795public:
796 ClangModuleJobNode(std::unique_ptr<Command> &&Job, deps::ModuleDeps &&MD)
797 : JobNode(std::move(Job), NodeKind::ClangModuleCC1Job),
798 MD(std::move(MD)) {}
799 ~ClangModuleJobNode() override = default;
800
801 deps::ModuleDeps MD;
802
803 static bool classof(const CGNode *N) {
804 return N->getKind() == NodeKind::ClangModuleCC1Job;
805 }
806};
807
808/// Base class for any CGNode type that represents any scanned -cc1 job.
809class ScannedJobNode : public JobNode {
810public:
811 ScannedJobNode(std::unique_ptr<Command> &&Job, InputDependencies &&InputDeps,
812 NodeKind Kind)
813 : JobNode(std::move(Job), Kind), InputDeps(std::move(InputDeps)) {}
814 ~ScannedJobNode() override = default;
815
816 InputDependencies InputDeps;
817
818 static bool classof(const CGNode *N) {
819 return N->getKind() == NodeKind::NamedModuleCC1Job ||
820 N->getKind() == NodeKind::NonModuleCC1Job;
821 }
822};
823
824/// Subclass of CGNode representing a -cc1 job which produces a C++20 named
825/// module.
826class NamedModuleJobNode : public ScannedJobNode {
827public:
828 NamedModuleJobNode(std::unique_ptr<Command> &&Job,
829 InputDependencies &&InputDeps)
830 : ScannedJobNode(std::move(Job), std::move(InputDeps),
831 NodeKind::NamedModuleCC1Job) {}
832 ~NamedModuleJobNode() override = default;
833
834 static bool classof(const CGNode *N) {
835 return N->getKind() == NodeKind::NamedModuleCC1Job;
836 }
837};
838
839/// Subclass of CGNode representing a -cc1 job which does not produce any
840/// module, but might still have module imports.
841class NonModuleTUJobNode : public ScannedJobNode {
842public:
843 NonModuleTUJobNode(std::unique_ptr<Command> &&Job,
844 InputDependencies &&InputDeps)
845 : ScannedJobNode(std::move(Job), std::move(InputDeps),
846 NodeKind::NonModuleCC1Job) {}
847 ~NonModuleTUJobNode() override = default;
848
849 static bool classof(const CGNode *N) {
850 return N->getKind() == NodeKind::NonModuleCC1Job;
851 }
852};
853
854/// Subclass of CGNode representing a job which produces an image file, such as
855/// a linker or interface stub merge job.
856class ImageJobNode : public JobNode {
857public:
858 ImageJobNode(std::unique_ptr<Command> &&Job)
859 : JobNode(std::move(Job), NodeKind::ImageJob) {}
860 ~ImageJobNode() override = default;
861
862 static bool classof(const CGNode *N) {
863 return N->getKind() == NodeKind::ImageJob;
864 }
865};
866
867/// Subclass of CGNode representing any job not covered by the other node types.
868///
869/// Jobs represented by this node type are not modified by the modules driver.
870class MiscJobNode : public JobNode {
871public:
872 MiscJobNode(std::unique_ptr<Command> &&Job)
873 : JobNode(std::move(Job), NodeKind::MiscJob) {}
874 ~MiscJobNode() override = default;
875
876 static bool classof(const CGNode *N) {
877 return N->getKind() == NodeKind::MiscJob;
878 }
879};
880
881/// Compilation Graph Edge
882///
883/// Edges connect the producer of an output to its consumer, except for edges
884/// stemming from the root node.
885class CGEdge : public CGEdgeBase {
886public:
887 enum class EdgeKind {
888 Regular,
889 ModuleDependency,
890 Rooted,
891 };
892
893 CGEdge(CGNode &N, EdgeKind K) : CGEdgeBase(N), Kind(K) {}
894
895 EdgeKind getKind() const { return Kind; }
896
897private:
898 EdgeKind Kind;
899};
900
901/// Compilation Graph
902///
903/// The graph owns all of its components.
904/// All nodes and edges created by the graph have the same livetime as the
905/// graph, even if removed from the graph's node list.
906class CompilationGraph : public CGBase {
907public:
908 CompilationGraph() = default;
909 CompilationGraph(const CompilationGraph &) = delete;
910 CompilationGraph(CompilationGraph &&G) = default;
911
912 CGNode &getRoot() const {
913 assert(Root && "Root node has not yet been created!");
914 return *Root;
915 }
916
917 RootNode &createRoot() {
918 assert(!Root && "Root node has already been created!");
919 auto &RootRef = createNodeImpl<RootNode>();
920 Root = &RootRef;
921 return RootRef;
922 }
923
924 template <typename T, typename... Args> T &createJobNode(Args &&...Arg) {
925 static_assert(std::is_base_of<JobNode, T>::value,
926 "T must be derived from JobNode");
927 return createNodeImpl<T>(std::forward<Args>(Arg)...);
928 }
929
930 CGEdge &createEdge(CGEdge::EdgeKind Kind, CGNode &Src, CGNode &Dst) {
931 auto Edge = std::make_unique<CGEdge>(args&: Dst, args&: Kind);
932 CGEdge &EdgeRef = *Edge;
933 AllEdges.push_back(Elt: std::move(Edge));
934 connect(Src, Dst, E&: EdgeRef);
935 return EdgeRef;
936 }
937
938private:
939 using CGBase::addNode;
940 using CGBase::connect;
941
942 template <typename T, typename... Args> T &createNodeImpl(Args &&...Arg) {
943 auto Node = std::make_unique<T>(std::forward<Args>(Arg)...);
944 T &NodeRef = *Node;
945 AllNodes.push_back(std::move(Node));
946 addNode(N&: NodeRef);
947 return NodeRef;
948 }
949
950 CGNode *Root = nullptr;
951 SmallVector<std::unique_ptr<CGNode>> AllNodes;
952 SmallVector<std::unique_ptr<CGEdge>> AllEdges;
953};
954} // anonymous namespace
955
956static StringRef getFirstInputFilename(const Command &Job) {
957 return Job.getInputInfos().front().getFilename();
958}
959
960namespace llvm {
961/// Non-const versions of the GraphTraits specializations for CompilationGraph.
962template <> struct GraphTraits<CGNode *> {
963 using NodeRef = CGNode *;
964
965 static NodeRef CGGetTargetNode(CGEdge *E) { return &E->getTargetNode(); }
966
967 using ChildIteratorType =
968 mapped_iterator<CGNode::iterator, decltype(&CGGetTargetNode)>;
969 using ChildEdgeIteratorType = CGNode::iterator;
970
971 static NodeRef getEntryNode(NodeRef N) { return N; }
972
973 static ChildIteratorType child_begin(NodeRef N) {
974 return ChildIteratorType(N->begin(), &CGGetTargetNode);
975 }
976
977 static ChildIteratorType child_end(NodeRef N) {
978 return ChildIteratorType(N->end(), &CGGetTargetNode);
979 }
980
981 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
982 return N->begin();
983 }
984 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
985};
986
987template <> struct GraphTraits<CompilationGraph *> : GraphTraits<CGNode *> {
988 using GraphRef = CompilationGraph *;
989 using NodeRef = CGNode *;
990
991 using nodes_iterator = CompilationGraph::iterator;
992
993 static NodeRef getEntryNode(GraphRef G) { return &G->getRoot(); }
994
995 static nodes_iterator nodes_begin(GraphRef G) { return G->begin(); }
996
997 static nodes_iterator nodes_end(GraphRef G) { return G->end(); }
998};
999
1000/// Const versions of the GraphTraits specializations for CompilationGraph.
1001template <> struct GraphTraits<const CGNode *> {
1002 using NodeRef = const CGNode *;
1003
1004 static NodeRef CGGetTargetNode(const CGEdge *E) {
1005 return &E->getTargetNode();
1006 }
1007
1008 using ChildIteratorType =
1009 mapped_iterator<CGNode::const_iterator, decltype(&CGGetTargetNode)>;
1010 using ChildEdgeIteratorType = CGNode::const_iterator;
1011
1012 static NodeRef getEntryNode(NodeRef N) { return N; }
1013
1014 static ChildIteratorType child_begin(NodeRef N) {
1015 return ChildIteratorType(N->begin(), &CGGetTargetNode);
1016 }
1017
1018 static ChildIteratorType child_end(NodeRef N) {
1019 return ChildIteratorType(N->end(), &CGGetTargetNode);
1020 }
1021
1022 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
1023 return N->begin();
1024 }
1025
1026 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
1027};
1028
1029template <>
1030struct GraphTraits<const CompilationGraph *> : GraphTraits<const CGNode *> {
1031 using GraphRef = const CompilationGraph *;
1032 using NodeRef = const CGNode *;
1033
1034 using nodes_iterator = CompilationGraph::const_iterator;
1035
1036 static NodeRef getEntryNode(GraphRef G) { return &G->getRoot(); }
1037
1038 static nodes_iterator nodes_begin(GraphRef G) { return G->begin(); }
1039
1040 static nodes_iterator nodes_end(GraphRef G) { return G->end(); }
1041};
1042
1043template <>
1044struct DOTGraphTraits<const CompilationGraph *> : DefaultDOTGraphTraits {
1045 explicit DOTGraphTraits(bool IsSimple = false)
1046 : DefaultDOTGraphTraits(IsSimple) {}
1047 using GraphRef = const CompilationGraph *;
1048 using NodeRef = const CGNode *;
1049
1050 static std::string getGraphName(GraphRef) {
1051 return "Module Dependency Graph";
1052 }
1053
1054 static std::string getGraphProperties(GraphRef) {
1055 return "\tnode [shape=Mrecord, colorscheme=set23, style=filled];\n";
1056 }
1057
1058 static bool renderGraphFromBottomUp() { return true; }
1059
1060 static bool isNodeHidden(NodeRef N, GraphRef) {
1061 // Only show nodes with module dependency relations.
1062 return !isa<ClangModuleJobNode, ScannedJobNode>(Val: N);
1063 }
1064
1065 static std::string getNodeIdentifier(NodeRef N, GraphRef) {
1066 return llvm::TypeSwitch<NodeRef, std::string>(N)
1067 .Case(caseFn: [](const ClangModuleJobNode *ClangModuleNode) {
1068 const auto &ID = ClangModuleNode->MD.ID;
1069 return llvm::formatv(Fmt: "{0}-{1}", Vals: ID.ModuleName, Vals: ID.ContextHash).str();
1070 })
1071 .Case(caseFn: [](const NamedModuleJobNode *NamedModuleNode) {
1072 return llvm::formatv(Fmt: "{0}-{1}", Vals: NamedModuleNode->InputDeps.ModuleName,
1073 Vals: getTriple(Job: *NamedModuleNode->Job))
1074 .str();
1075 })
1076 .Case(caseFn: [](const NonModuleTUJobNode *NonModuleTUNode) {
1077 const auto &Job = *NonModuleTUNode->Job;
1078 return llvm::formatv(Fmt: "{0}-{1}", Vals: getFirstInputFilename(Job),
1079 Vals: getTriple(Job))
1080 .str();
1081 })
1082 .DefaultUnreachable(message: "Unexpected node kind! Is this node hidden?");
1083 }
1084
1085 static std::string getNodeLabel(NodeRef N, GraphRef) {
1086 return llvm::TypeSwitch<NodeRef, std::string>(N)
1087 .Case(caseFn: [](const ClangModuleJobNode *ClangModuleNode) {
1088 const auto &ID = ClangModuleNode->MD.ID;
1089 return llvm::formatv(Fmt: "Module type: Clang module \\| Module name: {0} "
1090 "\\| Hash: {1}",
1091 Vals: ID.ModuleName, Vals: ID.ContextHash)
1092 .str();
1093 })
1094 .Case(caseFn: [](const NamedModuleJobNode *NamedModuleNode) {
1095 const auto &Job = *NamedModuleNode->Job;
1096 return llvm::formatv(
1097 Fmt: "Filename: {0} \\| Module type: Named module \\| "
1098 "Module name: {1} \\| Triple: {2}",
1099 Vals: getFirstInputFilename(Job),
1100 Vals: NamedModuleNode->InputDeps.ModuleName, Vals: getTriple(Job))
1101 .str();
1102 })
1103 .Case(caseFn: [](const NonModuleTUJobNode *NonModuleTUNode) {
1104 const auto &Job = *NonModuleTUNode->Job;
1105 return llvm::formatv(Fmt: "Filename: {0} \\| Triple: {1}",
1106 Vals: getFirstInputFilename(Job), Vals: getTriple(Job))
1107 .str();
1108 })
1109 .DefaultUnreachable(message: "Unexpected node kind! Is this node hidden?");
1110 }
1111
1112 static std::string getNodeAttributes(NodeRef N, GraphRef) {
1113 switch (N->getKind()) {
1114 case CGNode::NodeKind::ClangModuleCC1Job:
1115 return "fillcolor=1";
1116 case CGNode::NodeKind::NamedModuleCC1Job:
1117 return "fillcolor=2";
1118 case CGNode::NodeKind::NonModuleCC1Job:
1119 return "fillcolor=3";
1120 default:
1121 llvm_unreachable("Unexpected node kind! Is this node hidden?");
1122 }
1123 }
1124};
1125
1126/// GraphWriter specialization for CompilationGraph that emits a more
1127/// human-readable DOT graph.
1128template <>
1129class GraphWriter<const CompilationGraph *>
1130 : public GraphWriterBase<const CompilationGraph *,
1131 GraphWriter<const CompilationGraph *>> {
1132public:
1133 using GraphType = const CompilationGraph *;
1134 using Base = GraphWriterBase<GraphType, GraphWriter<GraphType>>;
1135
1136 GraphWriter(llvm::raw_ostream &O, const GraphType &G, bool IsSimple)
1137 : Base(O, G, IsSimple), EscapedIDByNodeRef(G->size()) {}
1138
1139 void writeNodes() {
1140 auto IsNodeVisible = [&](NodeRef N) { return !DTraits.isNodeHidden(N, G); };
1141 auto VisibleNodes = llvm::filter_to_vector(C: nodes(G), Pred&: IsNodeVisible);
1142
1143 writeNodeDefinitions(VisibleNodes);
1144 O << "\n";
1145 writeNodeRelations(VisibleNodes);
1146 }
1147
1148private:
1149 using Base::DOTTraits;
1150 using Base::GTraits;
1151 using Base::NodeRef;
1152
1153 void writeNodeDefinitions(ArrayRef<NodeRef> VisibleNodes) {
1154 for (NodeRef Node : VisibleNodes) {
1155 std::string EscapedNodeID =
1156 DOT::EscapeString(Label: DTraits.getNodeIdentifier(N: Node, G));
1157 const std::string NodeLabel = DTraits.getNodeLabel(N: Node, G);
1158 const std::string NodeAttrs = DTraits.getNodeAttributes(N: Node, G);
1159 O << '\t' << '"' << EscapedNodeID << "\" [" << NodeAttrs << ", label=\"{ "
1160 << DOT::EscapeString(Label: NodeLabel) << " }\"];\n";
1161 EscapedIDByNodeRef.try_emplace(Key: Node, Args: std::move(EscapedNodeID));
1162 }
1163 }
1164
1165 void writeNodeRelations(ArrayRef<NodeRef> VisibleNodes) {
1166 auto IsNodeVisible = [&](NodeRef N) { return !DTraits.isNodeHidden(N, G); };
1167 for (NodeRef Node : VisibleNodes) {
1168 auto DstNodes = llvm::make_range(x: GTraits::child_begin(N: Node),
1169 y: GTraits::child_end(N: Node));
1170 auto VisibleDstNodes = llvm::make_filter_range(Range&: DstNodes, Pred: IsNodeVisible);
1171 StringRef EscapedSrcNodeID = EscapedIDByNodeRef.at(Val: Node);
1172 for (NodeRef DstNode : VisibleDstNodes) {
1173 StringRef EscapedTgtNodeID = EscapedIDByNodeRef.at(Val: DstNode);
1174 O << '\t' << '"' << EscapedSrcNodeID << "\" -> \"" << EscapedTgtNodeID
1175 << "\";\n";
1176 }
1177 }
1178 }
1179
1180 DenseMap<NodeRef, std::string> EscapedIDByNodeRef;
1181};
1182} // namespace llvm
1183
1184static SmallVector<std::unique_ptr<Command>>
1185takeJobsAtIndices(SmallVectorImpl<std::unique_ptr<Command>> &Jobs,
1186 ArrayRef<size_t> Indices) {
1187 SmallVector<std::unique_ptr<Command>> Out;
1188 for (const auto JobIndex : Indices) {
1189 assert(Jobs[JobIndex] && "Expected valid job!");
1190 Out.push_back(Elt: std::move(Jobs[JobIndex]));
1191 }
1192 return Out;
1193}
1194
1195/// Creates nodes for all jobs that could not be scanned (e.g. image jobs, ...).
1196static void createNodesForNonScannableJobs(
1197 CompilationGraph &Graph,
1198 SmallVectorImpl<std::unique_ptr<Command>> &&NonScannableJobs) {
1199 for (auto &Job : NonScannableJobs) {
1200 if (Job->getCreator().isLinkJob())
1201 Graph.createJobNode<ImageJobNode>(Arg: std::move(Job));
1202 else
1203 Graph.createJobNode<MiscJobNode>(Arg: std::move(Job));
1204 }
1205}
1206
1207/// Creates nodes for the Standard library module jobs not discovered as
1208/// dependencies.
1209///
1210/// These and any dependent (non-image) job nodes should be pruned from the
1211/// graph later.
1212static SmallVector<JobNode *> createNodesForUnusedStdlibModuleJobs(
1213 CompilationGraph &Graph,
1214 SmallVectorImpl<std::unique_ptr<Command>> &&UnusedStdlibModuleJobs) {
1215 SmallVector<JobNode *> StdlibModuleNodesToPrune;
1216 for (auto &Job : UnusedStdlibModuleJobs) {
1217 auto &NewNode = Graph.createJobNode<MiscJobNode>(Arg: std::move(Job));
1218 StdlibModuleNodesToPrune.push_back(Elt: &NewNode);
1219 }
1220 return StdlibModuleNodesToPrune;
1221}
1222
1223/// Creates a job for the Clang module described by \p MD.
1224static std::unique_ptr<CC1Command>
1225createClangModulePrecompileJob(Compilation &C, const Command &ImportingJob,
1226 const deps::ModuleDeps &MD) {
1227 DerivedArgList &Args = C.getArgs();
1228 const OptTable &Opts = C.getDriver().getOpts();
1229 Arg *InputArg = makeInputArg(Args, Opts, Value: "<discovered clang module>");
1230 Action *IA = C.MakeAction<InputAction>(Arg&: *InputArg, Arg: types::ID::TY_ModuleFile);
1231 Action *PA = C.MakeAction<PrecompileJobAction>(Arg&: IA, Arg: types::ID::TY_ModuleFile);
1232 PA->propagateOffloadInfo(A: &ImportingJob.getSource());
1233
1234 const auto &TC = ImportingJob.getCreator().getToolChain();
1235 const auto &TCArgs = C.getArgsForToolChain(TC: &TC, BoundArch: PA->getOffloadingArch(),
1236 DeviceOffloadKind: PA->getOffloadingDeviceKind());
1237
1238 const auto &BuildArgs = MD.getBuildArguments();
1239 ArgStringList JobArgs;
1240 JobArgs.reserve(N: BuildArgs.size());
1241 for (const auto &Arg : BuildArgs)
1242 JobArgs.push_back(Elt: TCArgs.MakeArgString(Str: Arg));
1243
1244 return std::make_unique<CC1Command>(
1245 args&: *PA, args: ImportingJob.getCreator(), args: ResponseFileSupport::AtFileUTF8(),
1246 args: C.getDriver().getClangProgramPath(), args&: JobArgs,
1247 /*Inputs=*/args: ArrayRef<InputInfo>{},
1248 /*Outputs=*/args: ArrayRef<InputInfo>{});
1249}
1250
1251/// Creates a ClangModuleJobNode and its job for each unique Clang module
1252/// in \p ModuleDepGraphsForScannedJobs.
1253///
1254/// Only the jobs at indices \p ScannedJobIndices in \p Jobs are expected to be
1255/// non-null.
1256static void createClangModuleJobsAndNodes(
1257 CompilationGraph &Graph, Compilation &C,
1258 ArrayRef<std::unique_ptr<Command>> Jobs, ArrayRef<size_t> ScannedJobIndices,
1259 SmallVectorImpl<deps::ModuleDepsGraph> &&ModuleDepGraphsForScannedJobs) {
1260 llvm::DenseSet<deps::ModuleID> AlreadySeen;
1261 for (auto &&[ScanIndex, ModuleDepsGraph] :
1262 llvm::enumerate(First&: ModuleDepGraphsForScannedJobs)) {
1263 const auto &ImportingJob = *Jobs[ScannedJobIndices[ScanIndex]];
1264
1265 for (auto &MD : ModuleDepsGraph) {
1266 const auto Inserted = AlreadySeen.insert(V: MD.ID).second;
1267 if (!Inserted)
1268 continue;
1269
1270 auto ClangModuleJob = createClangModulePrecompileJob(C, ImportingJob, MD);
1271 Graph.createJobNode<ClangModuleJobNode>(Arg: std::move(ClangModuleJob),
1272 Arg: std::move(MD));
1273 }
1274 }
1275}
1276
1277/// Creates nodes for all jobs which were scanned for dependencies.
1278///
1279/// The updated command lines produced by the dependency scan are installed at a
1280/// later point.
1281static void createNodesForScannedJobs(
1282 CompilationGraph &Graph,
1283 SmallVectorImpl<std::unique_ptr<Command>> &&ScannedJobs,
1284 SmallVectorImpl<InputDependencies> &&InputDepsForScannedJobs) {
1285 for (auto &&[Job, InputDeps] :
1286 llvm::zip_equal(t&: ScannedJobs, u&: InputDepsForScannedJobs)) {
1287 if (InputDeps.ModuleName.empty())
1288 Graph.createJobNode<NonModuleTUJobNode>(Arg: std::move(Job),
1289 Arg: std::move(InputDeps));
1290 else
1291 Graph.createJobNode<NamedModuleJobNode>(Arg: std::move(Job),
1292 Arg: std::move(InputDeps));
1293 }
1294}
1295
1296template <typename LookupT, typename KeyRangeT>
1297static void connectEdgesViaLookup(CompilationGraph &Graph, CGNode &TgtNode,
1298 const LookupT &SrcNodeLookup,
1299 const KeyRangeT &SrcNodeLookupKeys,
1300 CGEdge::EdgeKind Kind) {
1301 for (const auto &Key : SrcNodeLookupKeys) {
1302 const auto It = SrcNodeLookup.find(Key);
1303 if (It == SrcNodeLookup.end())
1304 continue;
1305
1306 auto &SrcNode = *It->second;
1307 Graph.createEdge(Kind, Src&: SrcNode, Dst&: TgtNode);
1308 }
1309}
1310
1311/// Create edges for regular (non-module) dependencies in \p Graph.
1312static void createRegularEdges(CompilationGraph &Graph) {
1313 llvm::DenseMap<StringRef, CGNode *> NodeByOutputFiles;
1314 for (auto *Node : Graph) {
1315 for (const auto &Output : cast<JobNode>(Val: Node)->Job->getOutputFilenames()) {
1316 [[maybe_unused]] const bool Inserted =
1317 NodeByOutputFiles.try_emplace(Key: Output, Args&: Node).second;
1318 assert(Inserted &&
1319 "Driver should not produce multiple jobs with identical outputs!");
1320 }
1321 }
1322
1323 for (auto *Node : Graph) {
1324 const auto &InputInfos = cast<JobNode>(Val: Node)->Job->getInputInfos();
1325 auto InputFilenames = llvm::map_range(
1326 C: InputInfos, F: [](const auto &II) { return II.getFilename(); });
1327
1328 connectEdgesViaLookup(Graph, TgtNode&: *Node, SrcNodeLookup: NodeByOutputFiles, SrcNodeLookupKeys: InputFilenames,
1329 Kind: CGEdge::EdgeKind::Regular);
1330 }
1331}
1332
1333/// Create edges for module dependencies in \p Graph.
1334///
1335/// \returns false if there are multiple definitions for a named module, with
1336/// diagnostics reported to \p Diags; otherwise returns true.
1337static bool createModuleDependencyEdges(CompilationGraph &Graph,
1338 DiagnosticsEngine &Diags) {
1339 llvm::DenseMap<deps::ModuleID, CGNode *> ClangModuleNodeByID;
1340 llvm::DenseMap<ModuleNameAndTriple, CGNode *> NamedModuleNodeByID;
1341
1342 // Map each module to the job that produces it.
1343 bool HasDuplicateModuleError = false;
1344 for (auto *Node : Graph) {
1345 llvm::TypeSwitch<CGNode *>(Node)
1346 .Case(caseFn: [&](ClangModuleJobNode *ClangModuleNode) {
1347 [[maybe_unused]] const bool Inserted =
1348 ClangModuleNodeByID.try_emplace(Key: ClangModuleNode->MD.ID, Args&: Node)
1349 .second;
1350 assert(Inserted &&
1351 "Multiple Clang module nodes with the same module ID!");
1352 })
1353 .Case(caseFn: [&](NamedModuleJobNode *NamedModuleNode) {
1354 StringRef ModuleName = NamedModuleNode->InputDeps.ModuleName;
1355 ModuleNameAndTriple ID{ModuleName, getTriple(Job: *NamedModuleNode->Job)};
1356 const auto [It, Inserted] = NamedModuleNodeByID.try_emplace(Key: ID, Args&: Node);
1357 if (!Inserted) {
1358 // For scan input jobs, their first input is always a filename and
1359 // the scanned source.
1360 // We don't use InputDeps.FileDeps here because diagnostics should
1361 // refer to the filename as specified on the command line, not the
1362 // canonical absolute path.
1363 StringRef PrevFile =
1364 getFirstInputFilename(Job: *cast<JobNode>(Val: It->second)->Job);
1365 StringRef CurFile = getFirstInputFilename(Job: *NamedModuleNode->Job);
1366 Diags.Report(DiagID: diag::err_modules_driver_named_module_redefinition)
1367 << ModuleName << PrevFile << CurFile;
1368 HasDuplicateModuleError = true;
1369 }
1370 });
1371 }
1372 if (HasDuplicateModuleError)
1373 return false;
1374
1375 // Create edges from the module nodes to their importers.
1376 for (auto *Node : Graph) {
1377 llvm::TypeSwitch<CGNode *>(Node)
1378 .Case(caseFn: [&](ClangModuleJobNode *ClangModuleNode) {
1379 connectEdgesViaLookup(Graph, TgtNode&: *ClangModuleNode, SrcNodeLookup: ClangModuleNodeByID,
1380 SrcNodeLookupKeys: ClangModuleNode->MD.ClangModuleDeps,
1381 Kind: CGEdge::EdgeKind::ModuleDependency);
1382 })
1383 .Case(caseFn: [&](ScannedJobNode *NodeWithInputDeps) {
1384 connectEdgesViaLookup(Graph, TgtNode&: *NodeWithInputDeps, SrcNodeLookup: ClangModuleNodeByID,
1385 SrcNodeLookupKeys: NodeWithInputDeps->InputDeps.ClangModuleDeps,
1386 Kind: CGEdge::EdgeKind::ModuleDependency);
1387
1388 StringRef Triple = getTriple(Job: *NodeWithInputDeps->Job);
1389 const auto NamedModuleDepIDs =
1390 llvm::map_range(C&: NodeWithInputDeps->InputDeps.NamedModuleDeps,
1391 F: [&](StringRef ModuleName) {
1392 return ModuleNameAndTriple{ModuleName, Triple};
1393 });
1394 connectEdgesViaLookup(Graph, TgtNode&: *NodeWithInputDeps, SrcNodeLookup: NamedModuleNodeByID,
1395 SrcNodeLookupKeys: NamedModuleDepIDs,
1396 Kind: CGEdge::EdgeKind::ModuleDependency);
1397 });
1398 }
1399
1400 return true;
1401}
1402
1403/// Prunes the compilation graph of any jobs which build Standard library
1404/// modules not required in this compilation.
1405static void
1406pruneUnusedStdlibModuleJobs(CompilationGraph &Graph,
1407 ArrayRef<JobNode *> UnusedStdlibModuleJobNodes) {
1408 // Collect all reachable non-image job nodes.
1409 llvm::SmallPtrSet<JobNode *, 16> PrunableJobNodes;
1410 for (auto *PrunableJobNodeRoot : UnusedStdlibModuleJobNodes) {
1411 auto ReachableJobNodes =
1412 llvm::map_range(C: llvm::depth_first(G: cast<CGNode>(Val: PrunableJobNodeRoot)),
1413 F: llvm::CastTo<JobNode>);
1414 auto ReachableNonImageNodes = llvm::make_filter_range(
1415 Range&: ReachableJobNodes, Pred: [](auto *N) { return !llvm::isa<ImageJobNode>(N); });
1416 PrunableJobNodes.insert_range(R&: ReachableNonImageNodes);
1417 }
1418
1419 // Map image job nodes to the prunable job nodes that feed into them.
1420 llvm::DenseMap<ImageJobNode *, llvm::SmallPtrSet<JobNode *, 4>>
1421 PrunableJobNodesByImageNode;
1422 for (auto *PrunableJobNode : PrunableJobNodes) {
1423 auto ReachableJobNodes = llvm::depth_first(G: cast<CGNode>(Val: PrunableJobNode));
1424 auto ReachableImageJobNodes = llvm::map_range(
1425 C: llvm::make_filter_range(Range&: ReachableJobNodes, Pred: llvm::IsaPred<ImageJobNode>),
1426 F: llvm::CastTo<ImageJobNode>);
1427
1428 for (auto *ImageNode : ReachableImageJobNodes)
1429 PrunableJobNodesByImageNode[ImageNode].insert(Ptr: PrunableJobNode);
1430 }
1431
1432 // Remove from each affected image job node any arguments corresponding to
1433 // outputs of the connected prunable job nodes.
1434 for (auto &[ImageNode, PrunableJobNodeInputs] : PrunableJobNodesByImageNode) {
1435 SmallVector<StringRef, 4> OutputsToRemove;
1436 for (auto *JN : PrunableJobNodeInputs)
1437 llvm::append_range(C&: OutputsToRemove, R: JN->Job->getOutputFilenames());
1438
1439 auto NewArgs = ImageNode->Job->getArguments();
1440 llvm::erase_if(C&: NewArgs, P: [&](StringRef Arg) {
1441 return llvm::is_contained(Range&: OutputsToRemove, Element: Arg);
1442 });
1443 ImageNode->Job->replaceArguments(List: NewArgs);
1444 }
1445
1446 // Erase all prunable job nodes from the graph.
1447 for (auto *JN : PrunableJobNodes) {
1448 // Nodes are owned by the graph, but we can release the associated job.
1449 JN->Job.reset();
1450 Graph.removeNode(N&: *JN);
1451 }
1452}
1453
1454/// Creates the root node and connects it to all nodes with no incoming edges
1455/// ensuring that every node in the graph is reachable from the root.
1456static void createAndConnectRoot(CompilationGraph &Graph) {
1457 llvm::SmallPtrSet<CGNode *, 16> HasIncomingEdge;
1458 for (auto *Node : Graph)
1459 for (auto *Edge : Node->getEdges())
1460 HasIncomingEdge.insert(Ptr: &Edge->getTargetNode());
1461
1462 auto AllNonRootNodes = llvm::iterator_range(Graph);
1463 auto &Root = Graph.createRoot();
1464
1465 for (auto *Node : AllNonRootNodes) {
1466 if (HasIncomingEdge.contains(Ptr: Node))
1467 continue;
1468 Graph.createEdge(Kind: CGEdge::EdgeKind::Rooted, Src&: Root, Dst&: *Node);
1469 }
1470}
1471
1472void driver::modules::runModulesDriver(
1473 Compilation &C, ArrayRef<StdModuleManifest::Module> ManifestEntries) {
1474 llvm::PrettyStackTraceString CrashInfo("Running modules driver.");
1475
1476 auto Jobs = C.getJobs().takeJobs();
1477
1478 const auto ManifestEntryBySource = buildManifestLookupMap(ManifestEntries);
1479 // Apply manifest-entry specific command-line modifications before the scan as
1480 // they might affect it.
1481 applyArgsForStdModuleManifestInputs(C, ManifestEntryBySource, Jobs);
1482
1483 DiagnosticsEngine &Diags = C.getDriver().getDiags();
1484
1485 // Run the dependency scan.
1486 const auto MaybeModuleCachePath = getModuleCachePath(Args&: C.getArgs());
1487 if (!MaybeModuleCachePath) {
1488 Diags.Report(DiagID: diag::err_default_modules_cache_not_available);
1489 return;
1490 }
1491
1492 auto MaybeCWD = C.getDriver().getVFS().getCurrentWorkingDirectory();
1493 const auto CWD = MaybeCWD ? std::move(*MaybeCWD) : ".";
1494
1495 auto MaybeScanResults = scanDependencies(Jobs, ManifestLookup: ManifestEntryBySource,
1496 ModuleCachePath: *MaybeModuleCachePath, WorkingDirectory: CWD, Diags);
1497 if (!MaybeScanResults) {
1498 Diags.Report(DiagID: diag::err_dependency_scan_failed);
1499 return;
1500 }
1501 auto &ScanResult = *MaybeScanResults;
1502
1503 // Build the compilation graph.
1504 CompilationGraph Graph;
1505 createNodesForNonScannableJobs(
1506 Graph, NonScannableJobs: takeJobsAtIndices(Jobs, Indices: ScanResult.NonScannableJobIndices));
1507 auto UnusedStdlibModuleJobNodes = createNodesForUnusedStdlibModuleJobs(
1508 Graph, UnusedStdlibModuleJobs: takeJobsAtIndices(Jobs, Indices: ScanResult.UnusedStdlibModuleJobIndices));
1509 createClangModuleJobsAndNodes(
1510 Graph, C, Jobs, ScannedJobIndices: ScanResult.ScannedJobIndices,
1511 ModuleDepGraphsForScannedJobs: std::move(ScanResult.ModuleDepGraphsForScannedJobs));
1512 createNodesForScannedJobs(
1513 Graph, ScannedJobs: takeJobsAtIndices(Jobs, Indices: ScanResult.ScannedJobIndices),
1514 InputDepsForScannedJobs: std::move(ScanResult.InputDepsForScannedJobs));
1515 createRegularEdges(Graph);
1516
1517 pruneUnusedStdlibModuleJobs(Graph, UnusedStdlibModuleJobNodes);
1518
1519 if (!createModuleDependencyEdges(Graph, Diags))
1520 return;
1521 createAndConnectRoot(Graph);
1522
1523 Diags.Report(DiagID: diag::remark_printing_module_graph);
1524 if (!Diags.isLastDiagnosticIgnored())
1525 llvm::WriteGraph<const CompilationGraph *>(O&: llvm::errs(), G: &Graph);
1526
1527 // TODO: Install all updated command-lines produced by the dependency scan.
1528 // TODO: Fix-up command-lines for named module imports.
1529
1530 // TODO: Sort the graph topologically before adding jobs back to the
1531 // Compilation being built.
1532 for (auto *N : Graph)
1533 if (auto *JN = dyn_cast<JobNode>(Val: N))
1534 C.addCommand(C: std::move(JN->Job));
1535}
1536