1 //===-ThinLTOCodeGenerator.cpp - LLVM Link Time Optimizer -----------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the Thin Link Time Optimization library. This library is
11 // intended to be used by linker to optimize code at link time.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/LTO/legacy/ThinLTOCodeGenerator.h"
16 
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/StringExtras.h"
19 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
20 #include "llvm/Analysis/ProfileSummaryInfo.h"
21 #include "llvm/Analysis/TargetLibraryInfo.h"
22 #include "llvm/Analysis/TargetTransformInfo.h"
23 #include "llvm/Bitcode/BitcodeReader.h"
24 #include "llvm/Bitcode/BitcodeWriter.h"
25 #include "llvm/Bitcode/BitcodeWriterPass.h"
26 #include "llvm/Config/llvm-config.h"
27 #include "llvm/IR/DebugInfo.h"
28 #include "llvm/IR/DiagnosticPrinter.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/LegacyPassManager.h"
31 #include "llvm/IR/Mangler.h"
32 #include "llvm/IR/PassTimingInfo.h"
33 #include "llvm/IR/Verifier.h"
34 #include "llvm/IRReader/IRReader.h"
35 #include "llvm/LTO/LTO.h"
36 #include "llvm/MC/SubtargetFeature.h"
37 #include "llvm/Object/IRObjectFile.h"
38 #include "llvm/Support/CachePruning.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/Error.h"
41 #include "llvm/Support/Path.h"
42 #include "llvm/Support/SHA1.h"
43 #include "llvm/Support/SmallVectorMemoryBuffer.h"
44 #include "llvm/Support/TargetRegistry.h"
45 #include "llvm/Support/ThreadPool.h"
46 #include "llvm/Support/Threading.h"
47 #include "llvm/Support/ToolOutputFile.h"
48 #include "llvm/Support/VCSRevision.h"
49 #include "llvm/Target/TargetMachine.h"
50 #include "llvm/Transforms/IPO.h"
51 #include "llvm/Transforms/IPO/FunctionImport.h"
52 #include "llvm/Transforms/IPO/Internalize.h"
53 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
54 #include "llvm/Transforms/ObjCARC.h"
55 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
56 
57 #include <numeric>
58 
59 #if !defined(_MSC_VER) && !defined(__MINGW32__)
60 #include <unistd.h>
61 #else
62 #include <io.h>
63 #endif
64 
65 using namespace llvm;
66 
67 #define DEBUG_TYPE "thinlto"
68 
69 namespace llvm {
70 // Flags -discard-value-names, defined in LTOCodeGenerator.cpp
71 extern cl::opt<bool> LTODiscardValueNames;
72 extern cl::opt<std::string> LTORemarksFilename;
73 extern cl::opt<bool> LTOPassRemarksWithHotness;
74 }
75 
76 namespace {
77 
78 static cl::opt<int>
79     ThreadCount("threads", cl::init(llvm::heavyweight_hardware_concurrency()));
80 
81 // Simple helper to save temporary files for debug.
82 static void saveTempBitcode(const Module &TheModule, StringRef TempDir,
83                             unsigned count, StringRef Suffix) {
84   if (TempDir.empty())
85     return;
86   // User asked to save temps, let dump the bitcode file after import.
87   std::string SaveTempPath = (TempDir + llvm::Twine(count) + Suffix).str();
88   std::error_code EC;
89   raw_fd_ostream OS(SaveTempPath, EC, sys::fs::F_None);
90   if (EC)
91     report_fatal_error(Twine("Failed to open ") + SaveTempPath +
92                        " to save optimized bitcode\n");
93   WriteBitcodeToFile(TheModule, OS, /* ShouldPreserveUseListOrder */ true);
94 }
95 
96 static const GlobalValueSummary *
97 getFirstDefinitionForLinker(const GlobalValueSummaryList &GVSummaryList) {
98   // If there is any strong definition anywhere, get it.
99   auto StrongDefForLinker = llvm::find_if(
100       GVSummaryList, [](const std::unique_ptr<GlobalValueSummary> &Summary) {
101         auto Linkage = Summary->linkage();
102         return !GlobalValue::isAvailableExternallyLinkage(Linkage) &&
103                !GlobalValue::isWeakForLinker(Linkage);
104       });
105   if (StrongDefForLinker != GVSummaryList.end())
106     return StrongDefForLinker->get();
107   // Get the first *linker visible* definition for this global in the summary
108   // list.
109   auto FirstDefForLinker = llvm::find_if(
110       GVSummaryList, [](const std::unique_ptr<GlobalValueSummary> &Summary) {
111         auto Linkage = Summary->linkage();
112         return !GlobalValue::isAvailableExternallyLinkage(Linkage);
113       });
114   // Extern templates can be emitted as available_externally.
115   if (FirstDefForLinker == GVSummaryList.end())
116     return nullptr;
117   return FirstDefForLinker->get();
118 }
119 
120 // Populate map of GUID to the prevailing copy for any multiply defined
121 // symbols. Currently assume first copy is prevailing, or any strong
122 // definition. Can be refined with Linker information in the future.
123 static void computePrevailingCopies(
124     const ModuleSummaryIndex &Index,
125     DenseMap<GlobalValue::GUID, const GlobalValueSummary *> &PrevailingCopy) {
126   auto HasMultipleCopies = [&](const GlobalValueSummaryList &GVSummaryList) {
127     return GVSummaryList.size() > 1;
128   };
129 
130   for (auto &I : Index) {
131     if (HasMultipleCopies(I.second.SummaryList))
132       PrevailingCopy[I.first] =
133           getFirstDefinitionForLinker(I.second.SummaryList);
134   }
135 }
136 
137 static StringMap<MemoryBufferRef>
138 generateModuleMap(const std::vector<ThinLTOBuffer> &Modules) {
139   StringMap<MemoryBufferRef> ModuleMap;
140   for (auto &ModuleBuffer : Modules) {
141     assert(ModuleMap.find(ModuleBuffer.getBufferIdentifier()) ==
142                ModuleMap.end() &&
143            "Expect unique Buffer Identifier");
144     ModuleMap[ModuleBuffer.getBufferIdentifier()] = ModuleBuffer.getMemBuffer();
145   }
146   return ModuleMap;
147 }
148 
149 static void promoteModule(Module &TheModule, const ModuleSummaryIndex &Index) {
150   if (renameModuleForThinLTO(TheModule, Index))
151     report_fatal_error("renameModuleForThinLTO failed");
152 }
153 
154 namespace {
155 class ThinLTODiagnosticInfo : public DiagnosticInfo {
156   const Twine &Msg;
157 public:
158   ThinLTODiagnosticInfo(const Twine &DiagMsg,
159                         DiagnosticSeverity Severity = DS_Error)
160       : DiagnosticInfo(DK_Linker, Severity), Msg(DiagMsg) {}
161   void print(DiagnosticPrinter &DP) const override { DP << Msg; }
162 };
163 }
164 
165 /// Verify the module and strip broken debug info.
166 static void verifyLoadedModule(Module &TheModule) {
167   bool BrokenDebugInfo = false;
168   if (verifyModule(TheModule, &dbgs(), &BrokenDebugInfo))
169     report_fatal_error("Broken module found, compilation aborted!");
170   if (BrokenDebugInfo) {
171     TheModule.getContext().diagnose(ThinLTODiagnosticInfo(
172         "Invalid debug info found, debug info will be stripped", DS_Warning));
173     StripDebugInfo(TheModule);
174   }
175 }
176 
177 static std::unique_ptr<Module>
178 loadModuleFromBuffer(const MemoryBufferRef &Buffer, LLVMContext &Context,
179                      bool Lazy, bool IsImporting) {
180   SMDiagnostic Err;
181   Expected<std::unique_ptr<Module>> ModuleOrErr =
182       Lazy
183           ? getLazyBitcodeModule(Buffer, Context,
184                                  /* ShouldLazyLoadMetadata */ true, IsImporting)
185           : parseBitcodeFile(Buffer, Context);
186   if (!ModuleOrErr) {
187     handleAllErrors(ModuleOrErr.takeError(), [&](ErrorInfoBase &EIB) {
188       SMDiagnostic Err = SMDiagnostic(Buffer.getBufferIdentifier(),
189                                       SourceMgr::DK_Error, EIB.message());
190       Err.print("ThinLTO", errs());
191     });
192     report_fatal_error("Can't load module, abort.");
193   }
194   if (!Lazy)
195     verifyLoadedModule(*ModuleOrErr.get());
196   return std::move(ModuleOrErr.get());
197 }
198 
199 static void
200 crossImportIntoModule(Module &TheModule, const ModuleSummaryIndex &Index,
201                       StringMap<MemoryBufferRef> &ModuleMap,
202                       const FunctionImporter::ImportMapTy &ImportList) {
203   auto Loader = [&](StringRef Identifier) {
204     return loadModuleFromBuffer(ModuleMap[Identifier], TheModule.getContext(),
205                                 /*Lazy=*/true, /*IsImporting*/ true);
206   };
207 
208   FunctionImporter Importer(Index, Loader);
209   Expected<bool> Result = Importer.importFunctions(TheModule, ImportList);
210   if (!Result) {
211     handleAllErrors(Result.takeError(), [&](ErrorInfoBase &EIB) {
212       SMDiagnostic Err = SMDiagnostic(TheModule.getModuleIdentifier(),
213                                       SourceMgr::DK_Error, EIB.message());
214       Err.print("ThinLTO", errs());
215     });
216     report_fatal_error("importFunctions failed");
217   }
218   // Verify again after cross-importing.
219   verifyLoadedModule(TheModule);
220 }
221 
222 static void optimizeModule(Module &TheModule, TargetMachine &TM,
223                            unsigned OptLevel, bool Freestanding) {
224   // Populate the PassManager
225   PassManagerBuilder PMB;
226   PMB.LibraryInfo = new TargetLibraryInfoImpl(TM.getTargetTriple());
227   if (Freestanding)
228     PMB.LibraryInfo->disableAllFunctions();
229   PMB.Inliner = createFunctionInliningPass();
230   // FIXME: should get it from the bitcode?
231   PMB.OptLevel = OptLevel;
232   PMB.LoopVectorize = true;
233   PMB.SLPVectorize = true;
234   // Already did this in verifyLoadedModule().
235   PMB.VerifyInput = false;
236   PMB.VerifyOutput = false;
237 
238   legacy::PassManager PM;
239 
240   // Add the TTI (required to inform the vectorizer about register size for
241   // instance)
242   PM.add(createTargetTransformInfoWrapperPass(TM.getTargetIRAnalysis()));
243 
244   // Add optimizations
245   PMB.populateThinLTOPassManager(PM);
246 
247   PM.run(TheModule);
248 }
249 
250 // Convert the PreservedSymbols map from "Name" based to "GUID" based.
251 static DenseSet<GlobalValue::GUID>
252 computeGUIDPreservedSymbols(const StringSet<> &PreservedSymbols,
253                             const Triple &TheTriple) {
254   DenseSet<GlobalValue::GUID> GUIDPreservedSymbols(PreservedSymbols.size());
255   for (auto &Entry : PreservedSymbols) {
256     StringRef Name = Entry.first();
257     if (TheTriple.isOSBinFormatMachO() && Name.size() > 0 && Name[0] == '_')
258       Name = Name.drop_front();
259     GUIDPreservedSymbols.insert(GlobalValue::getGUID(Name));
260   }
261   return GUIDPreservedSymbols;
262 }
263 
264 std::unique_ptr<MemoryBuffer> codegenModule(Module &TheModule,
265                                             TargetMachine &TM) {
266   SmallVector<char, 128> OutputBuffer;
267 
268   // CodeGen
269   {
270     raw_svector_ostream OS(OutputBuffer);
271     legacy::PassManager PM;
272 
273     // If the bitcode files contain ARC code and were compiled with optimization,
274     // the ObjCARCContractPass must be run, so do it unconditionally here.
275     PM.add(createObjCARCContractPass());
276 
277     // Setup the codegen now.
278     if (TM.addPassesToEmitFile(PM, OS, nullptr, TargetMachine::CGFT_ObjectFile,
279                                /* DisableVerify */ true))
280       report_fatal_error("Failed to setup codegen");
281 
282     // Run codegen now. resulting binary is in OutputBuffer.
283     PM.run(TheModule);
284   }
285   return make_unique<SmallVectorMemoryBuffer>(std::move(OutputBuffer));
286 }
287 
288 /// Manage caching for a single Module.
289 class ModuleCacheEntry {
290   SmallString<128> EntryPath;
291 
292 public:
293   // Create a cache entry. This compute a unique hash for the Module considering
294   // the current list of export/import, and offer an interface to query to
295   // access the content in the cache.
296   ModuleCacheEntry(
297       StringRef CachePath, const ModuleSummaryIndex &Index, StringRef ModuleID,
298       const FunctionImporter::ImportMapTy &ImportList,
299       const FunctionImporter::ExportSetTy &ExportList,
300       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
301       const GVSummaryMapTy &DefinedGVSummaries, unsigned OptLevel,
302       bool Freestanding, const TargetMachineBuilder &TMBuilder) {
303     if (CachePath.empty())
304       return;
305 
306     if (!Index.modulePaths().count(ModuleID))
307       // The module does not have an entry, it can't have a hash at all
308       return;
309 
310     if (all_of(Index.getModuleHash(ModuleID),
311                [](uint32_t V) { return V == 0; }))
312       // No hash entry, no caching!
313       return;
314 
315     llvm::lto::Config Conf;
316     Conf.OptLevel = OptLevel;
317     Conf.Options = TMBuilder.Options;
318     Conf.CPU = TMBuilder.MCpu;
319     Conf.MAttrs.push_back(TMBuilder.MAttr);
320     Conf.RelocModel = TMBuilder.RelocModel;
321     Conf.CGOptLevel = TMBuilder.CGOptLevel;
322     Conf.Freestanding = Freestanding;
323     SmallString<40> Key;
324     computeLTOCacheKey(Key, Conf, Index, ModuleID, ImportList, ExportList,
325                        ResolvedODR, DefinedGVSummaries);
326 
327     // This choice of file name allows the cache to be pruned (see pruneCache()
328     // in include/llvm/Support/CachePruning.h).
329     sys::path::append(EntryPath, CachePath, "llvmcache-" + Key);
330   }
331 
332   // Access the path to this entry in the cache.
333   StringRef getEntryPath() { return EntryPath; }
334 
335   // Try loading the buffer for this cache entry.
336   ErrorOr<std::unique_ptr<MemoryBuffer>> tryLoadingBuffer() {
337     if (EntryPath.empty())
338       return std::error_code();
339     int FD;
340     SmallString<64> ResultPath;
341     std::error_code EC = sys::fs::openFileForRead(
342         Twine(EntryPath), FD, sys::fs::OF_UpdateAtime, &ResultPath);
343     if (EC)
344       return EC;
345     ErrorOr<std::unique_ptr<MemoryBuffer>> MBOrErr =
346         MemoryBuffer::getOpenFile(FD, EntryPath,
347                                   /*FileSize*/ -1,
348                                   /*RequiresNullTerminator*/ false);
349     close(FD);
350     return MBOrErr;
351   }
352 
353   // Cache the Produced object file
354   void write(const MemoryBuffer &OutputBuffer) {
355     if (EntryPath.empty())
356       return;
357 
358     // Write to a temporary to avoid race condition
359     SmallString<128> TempFilename;
360     SmallString<128> CachePath(EntryPath);
361     int TempFD;
362     llvm::sys::path::remove_filename(CachePath);
363     sys::path::append(TempFilename, CachePath, "Thin-%%%%%%.tmp.o");
364     std::error_code EC =
365       sys::fs::createUniqueFile(TempFilename, TempFD, TempFilename);
366     if (EC) {
367       errs() << "Error: " << EC.message() << "\n";
368       report_fatal_error("ThinLTO: Can't get a temporary file");
369     }
370     {
371       raw_fd_ostream OS(TempFD, /* ShouldClose */ true);
372       OS << OutputBuffer.getBuffer();
373     }
374     // Rename temp file to final destination; rename is atomic
375     EC = sys::fs::rename(TempFilename, EntryPath);
376     if (EC)
377       sys::fs::remove(TempFilename);
378   }
379 };
380 
381 static std::unique_ptr<MemoryBuffer>
382 ProcessThinLTOModule(Module &TheModule, ModuleSummaryIndex &Index,
383                      StringMap<MemoryBufferRef> &ModuleMap, TargetMachine &TM,
384                      const FunctionImporter::ImportMapTy &ImportList,
385                      const FunctionImporter::ExportSetTy &ExportList,
386                      const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
387                      const GVSummaryMapTy &DefinedGlobals,
388                      const ThinLTOCodeGenerator::CachingOptions &CacheOptions,
389                      bool DisableCodeGen, StringRef SaveTempsDir,
390                      bool Freestanding, unsigned OptLevel, unsigned count) {
391 
392   // "Benchmark"-like optimization: single-source case
393   bool SingleModule = (ModuleMap.size() == 1);
394 
395   if (!SingleModule) {
396     promoteModule(TheModule, Index);
397 
398     // Apply summary-based prevailing-symbol resolution decisions.
399     thinLTOResolvePrevailingInModule(TheModule, DefinedGlobals);
400 
401     // Save temps: after promotion.
402     saveTempBitcode(TheModule, SaveTempsDir, count, ".1.promoted.bc");
403   }
404 
405   // Be friendly and don't nuke totally the module when the client didn't
406   // supply anything to preserve.
407   if (!ExportList.empty() || !GUIDPreservedSymbols.empty()) {
408     // Apply summary-based internalization decisions.
409     thinLTOInternalizeModule(TheModule, DefinedGlobals);
410   }
411 
412   // Save internalized bitcode
413   saveTempBitcode(TheModule, SaveTempsDir, count, ".2.internalized.bc");
414 
415   if (!SingleModule) {
416     crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
417 
418     // Save temps: after cross-module import.
419     saveTempBitcode(TheModule, SaveTempsDir, count, ".3.imported.bc");
420   }
421 
422   optimizeModule(TheModule, TM, OptLevel, Freestanding);
423 
424   saveTempBitcode(TheModule, SaveTempsDir, count, ".4.opt.bc");
425 
426   if (DisableCodeGen) {
427     // Configured to stop before CodeGen, serialize the bitcode and return.
428     SmallVector<char, 128> OutputBuffer;
429     {
430       raw_svector_ostream OS(OutputBuffer);
431       ProfileSummaryInfo PSI(TheModule);
432       auto Index = buildModuleSummaryIndex(TheModule, nullptr, &PSI);
433       WriteBitcodeToFile(TheModule, OS, true, &Index);
434     }
435     return make_unique<SmallVectorMemoryBuffer>(std::move(OutputBuffer));
436   }
437 
438   return codegenModule(TheModule, TM);
439 }
440 
441 /// Resolve prevailing symbols. Record resolutions in the \p ResolvedODR map
442 /// for caching, and in the \p Index for application during the ThinLTO
443 /// backends. This is needed for correctness for exported symbols (ensure
444 /// at least one copy kept) and a compile-time optimization (to drop duplicate
445 /// copies when possible).
446 static void resolvePrevailingInIndex(
447     ModuleSummaryIndex &Index,
448     StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>>
449         &ResolvedODR) {
450 
451   DenseMap<GlobalValue::GUID, const GlobalValueSummary *> PrevailingCopy;
452   computePrevailingCopies(Index, PrevailingCopy);
453 
454   auto isPrevailing = [&](GlobalValue::GUID GUID, const GlobalValueSummary *S) {
455     const auto &Prevailing = PrevailingCopy.find(GUID);
456     // Not in map means that there was only one copy, which must be prevailing.
457     if (Prevailing == PrevailingCopy.end())
458       return true;
459     return Prevailing->second == S;
460   };
461 
462   auto recordNewLinkage = [&](StringRef ModuleIdentifier,
463                               GlobalValue::GUID GUID,
464                               GlobalValue::LinkageTypes NewLinkage) {
465     ResolvedODR[ModuleIdentifier][GUID] = NewLinkage;
466   };
467 
468   thinLTOResolvePrevailingInIndex(Index, isPrevailing, recordNewLinkage);
469 }
470 
471 // Initialize the TargetMachine builder for a given Triple
472 static void initTMBuilder(TargetMachineBuilder &TMBuilder,
473                           const Triple &TheTriple) {
474   // Set a default CPU for Darwin triples (copied from LTOCodeGenerator).
475   // FIXME this looks pretty terrible...
476   if (TMBuilder.MCpu.empty() && TheTriple.isOSDarwin()) {
477     if (TheTriple.getArch() == llvm::Triple::x86_64)
478       TMBuilder.MCpu = "core2";
479     else if (TheTriple.getArch() == llvm::Triple::x86)
480       TMBuilder.MCpu = "yonah";
481     else if (TheTriple.getArch() == llvm::Triple::aarch64)
482       TMBuilder.MCpu = "cyclone";
483   }
484   TMBuilder.TheTriple = std::move(TheTriple);
485 }
486 
487 } // end anonymous namespace
488 
489 void ThinLTOCodeGenerator::addModule(StringRef Identifier, StringRef Data) {
490   ThinLTOBuffer Buffer(Data, Identifier);
491   LLVMContext Context;
492   StringRef TripleStr;
493   ErrorOr<std::string> TripleOrErr = expectedToErrorOrAndEmitErrors(
494       Context, getBitcodeTargetTriple(Buffer.getMemBuffer()));
495 
496   if (TripleOrErr)
497     TripleStr = *TripleOrErr;
498 
499   Triple TheTriple(TripleStr);
500 
501   if (Modules.empty())
502     initTMBuilder(TMBuilder, Triple(TheTriple));
503   else if (TMBuilder.TheTriple != TheTriple) {
504     if (!TMBuilder.TheTriple.isCompatibleWith(TheTriple))
505       report_fatal_error("ThinLTO modules with incompatible triples not "
506                          "supported");
507     initTMBuilder(TMBuilder, Triple(TMBuilder.TheTriple.merge(TheTriple)));
508   }
509 
510   Modules.push_back(Buffer);
511 }
512 
513 void ThinLTOCodeGenerator::preserveSymbol(StringRef Name) {
514   PreservedSymbols.insert(Name);
515 }
516 
517 void ThinLTOCodeGenerator::crossReferenceSymbol(StringRef Name) {
518   // FIXME: At the moment, we don't take advantage of this extra information,
519   // we're conservatively considering cross-references as preserved.
520   //  CrossReferencedSymbols.insert(Name);
521   PreservedSymbols.insert(Name);
522 }
523 
524 // TargetMachine factory
525 std::unique_ptr<TargetMachine> TargetMachineBuilder::create() const {
526   std::string ErrMsg;
527   const Target *TheTarget =
528       TargetRegistry::lookupTarget(TheTriple.str(), ErrMsg);
529   if (!TheTarget) {
530     report_fatal_error("Can't load target for this Triple: " + ErrMsg);
531   }
532 
533   // Use MAttr as the default set of features.
534   SubtargetFeatures Features(MAttr);
535   Features.getDefaultSubtargetFeatures(TheTriple);
536   std::string FeatureStr = Features.getString();
537 
538   return std::unique_ptr<TargetMachine>(
539       TheTarget->createTargetMachine(TheTriple.str(), MCpu, FeatureStr, Options,
540                                      RelocModel, None, CGOptLevel));
541 }
542 
543 /**
544  * Produce the combined summary index from all the bitcode files:
545  * "thin-link".
546  */
547 std::unique_ptr<ModuleSummaryIndex> ThinLTOCodeGenerator::linkCombinedIndex() {
548   std::unique_ptr<ModuleSummaryIndex> CombinedIndex =
549       llvm::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/false);
550   uint64_t NextModuleId = 0;
551   for (auto &ModuleBuffer : Modules) {
552     if (Error Err = readModuleSummaryIndex(ModuleBuffer.getMemBuffer(),
553                                            *CombinedIndex, NextModuleId++)) {
554       // FIXME diagnose
555       logAllUnhandledErrors(
556           std::move(Err), errs(),
557           "error: can't create module summary index for buffer: ");
558       return nullptr;
559     }
560   }
561   return CombinedIndex;
562 }
563 
564 static void internalizeAndPromoteInIndex(
565     const StringMap<FunctionImporter::ExportSetTy> &ExportLists,
566     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
567     ModuleSummaryIndex &Index) {
568   auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
569     const auto &ExportList = ExportLists.find(ModuleIdentifier);
570     return (ExportList != ExportLists.end() &&
571             ExportList->second.count(GUID)) ||
572            GUIDPreservedSymbols.count(GUID);
573   };
574 
575   thinLTOInternalizeAndPromoteInIndex(Index, isExported);
576 }
577 
578 static void computeDeadSymbolsInIndex(
579     ModuleSummaryIndex &Index,
580     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
581   // We have no symbols resolution available. And can't do any better now in the
582   // case where the prevailing symbol is in a native object. It can be refined
583   // with linker information in the future.
584   auto isPrevailing = [&](GlobalValue::GUID G) {
585     return PrevailingType::Unknown;
586   };
587   computeDeadSymbolsWithConstProp(Index, GUIDPreservedSymbols, isPrevailing,
588                                   /* ImportEnabled = */ true);
589 }
590 
591 /**
592  * Perform promotion and renaming of exported internal functions.
593  * Index is updated to reflect linkage changes from weak resolution.
594  */
595 void ThinLTOCodeGenerator::promote(Module &TheModule,
596                                    ModuleSummaryIndex &Index) {
597   auto ModuleCount = Index.modulePaths().size();
598   auto ModuleIdentifier = TheModule.getModuleIdentifier();
599 
600   // Collect for each module the list of function it defines (GUID -> Summary).
601   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries;
602   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
603 
604   // Convert the preserved symbols set from string to GUID
605   auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
606       PreservedSymbols, Triple(TheModule.getTargetTriple()));
607 
608   // Compute "dead" symbols, we don't want to import/export these!
609   computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
610 
611   // Generate import/export list
612   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
613   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
614   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
615                            ExportLists);
616 
617   // Resolve prevailing symbols
618   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
619   resolvePrevailingInIndex(Index, ResolvedODR);
620 
621   thinLTOResolvePrevailingInModule(
622       TheModule, ModuleToDefinedGVSummaries[ModuleIdentifier]);
623 
624   // Promote the exported values in the index, so that they are promoted
625   // in the module.
626   internalizeAndPromoteInIndex(ExportLists, GUIDPreservedSymbols, Index);
627 
628   promoteModule(TheModule, Index);
629 }
630 
631 /**
632  * Perform cross-module importing for the module identified by ModuleIdentifier.
633  */
634 void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
635                                              ModuleSummaryIndex &Index) {
636   auto ModuleMap = generateModuleMap(Modules);
637   auto ModuleCount = Index.modulePaths().size();
638 
639   // Collect for each module the list of function it defines (GUID -> Summary).
640   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
641   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
642 
643   // Convert the preserved symbols set from string to GUID
644   auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
645       PreservedSymbols, Triple(TheModule.getTargetTriple()));
646 
647   // Compute "dead" symbols, we don't want to import/export these!
648   computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
649 
650   // Generate import/export list
651   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
652   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
653   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
654                            ExportLists);
655   auto &ImportList = ImportLists[TheModule.getModuleIdentifier()];
656 
657   crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
658 }
659 
660 /**
661  * Compute the list of summaries needed for importing into module.
662  */
663 void ThinLTOCodeGenerator::gatherImportedSummariesForModule(
664     Module &TheModule, ModuleSummaryIndex &Index,
665     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
666   auto ModuleCount = Index.modulePaths().size();
667   auto ModuleIdentifier = TheModule.getModuleIdentifier();
668 
669   // Collect for each module the list of function it defines (GUID -> Summary).
670   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
671   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
672 
673   // Convert the preserved symbols set from string to GUID
674   auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
675       PreservedSymbols, Triple(TheModule.getTargetTriple()));
676 
677   // Compute "dead" symbols, we don't want to import/export these!
678   computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
679 
680   // Generate import/export list
681   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
682   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
683   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
684                            ExportLists);
685 
686   llvm::gatherImportedSummariesForModule(
687       ModuleIdentifier, ModuleToDefinedGVSummaries,
688       ImportLists[ModuleIdentifier], ModuleToSummariesForIndex);
689 }
690 
691 /**
692  * Emit the list of files needed for importing into module.
693  */
694 void ThinLTOCodeGenerator::emitImports(Module &TheModule, StringRef OutputName,
695                                        ModuleSummaryIndex &Index) {
696   auto ModuleCount = Index.modulePaths().size();
697   auto ModuleIdentifier = TheModule.getModuleIdentifier();
698 
699   // Collect for each module the list of function it defines (GUID -> Summary).
700   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
701   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
702 
703   // Convert the preserved symbols set from string to GUID
704   auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
705       PreservedSymbols, Triple(TheModule.getTargetTriple()));
706 
707   // Compute "dead" symbols, we don't want to import/export these!
708   computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
709 
710   // Generate import/export list
711   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
712   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
713   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
714                            ExportLists);
715 
716   std::map<std::string, GVSummaryMapTy> ModuleToSummariesForIndex;
717   llvm::gatherImportedSummariesForModule(
718       ModuleIdentifier, ModuleToDefinedGVSummaries,
719       ImportLists[ModuleIdentifier], ModuleToSummariesForIndex);
720 
721   std::error_code EC;
722   if ((EC = EmitImportsFiles(ModuleIdentifier, OutputName,
723                              ModuleToSummariesForIndex)))
724     report_fatal_error(Twine("Failed to open ") + OutputName +
725                        " to save imports lists\n");
726 }
727 
728 /**
729  * Perform internalization. Index is updated to reflect linkage changes.
730  */
731 void ThinLTOCodeGenerator::internalize(Module &TheModule,
732                                        ModuleSummaryIndex &Index) {
733   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
734   auto ModuleCount = Index.modulePaths().size();
735   auto ModuleIdentifier = TheModule.getModuleIdentifier();
736 
737   // Convert the preserved symbols set from string to GUID
738   auto GUIDPreservedSymbols =
739       computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
740 
741   // Collect for each module the list of function it defines (GUID -> Summary).
742   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
743   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
744 
745   // Compute "dead" symbols, we don't want to import/export these!
746   computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
747 
748   // Generate import/export list
749   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
750   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
751   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
752                            ExportLists);
753   auto &ExportList = ExportLists[ModuleIdentifier];
754 
755   // Be friendly and don't nuke totally the module when the client didn't
756   // supply anything to preserve.
757   if (ExportList.empty() && GUIDPreservedSymbols.empty())
758     return;
759 
760   // Internalization
761   internalizeAndPromoteInIndex(ExportLists, GUIDPreservedSymbols, Index);
762   thinLTOInternalizeModule(TheModule,
763                            ModuleToDefinedGVSummaries[ModuleIdentifier]);
764 }
765 
766 /**
767  * Perform post-importing ThinLTO optimizations.
768  */
769 void ThinLTOCodeGenerator::optimize(Module &TheModule) {
770   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
771 
772   // Optimize now
773   optimizeModule(TheModule, *TMBuilder.create(), OptLevel, Freestanding);
774 }
775 
776 /// Write out the generated object file, either from CacheEntryPath or from
777 /// OutputBuffer, preferring hard-link when possible.
778 /// Returns the path to the generated file in SavedObjectsDirectoryPath.
779 static std::string writeGeneratedObject(int count, StringRef CacheEntryPath,
780                                         StringRef SavedObjectsDirectoryPath,
781                                         const MemoryBuffer &OutputBuffer) {
782   SmallString<128> OutputPath(SavedObjectsDirectoryPath);
783   llvm::sys::path::append(OutputPath, Twine(count) + ".thinlto.o");
784   OutputPath.c_str(); // Ensure the string is null terminated.
785   if (sys::fs::exists(OutputPath))
786     sys::fs::remove(OutputPath);
787 
788   // We don't return a memory buffer to the linker, just a list of files.
789   if (!CacheEntryPath.empty()) {
790     // Cache is enabled, hard-link the entry (or copy if hard-link fails).
791     auto Err = sys::fs::create_hard_link(CacheEntryPath, OutputPath);
792     if (!Err)
793       return OutputPath.str();
794     // Hard linking failed, try to copy.
795     Err = sys::fs::copy_file(CacheEntryPath, OutputPath);
796     if (!Err)
797       return OutputPath.str();
798     // Copy failed (could be because the CacheEntry was removed from the cache
799     // in the meantime by another process), fall back and try to write down the
800     // buffer to the output.
801     errs() << "error: can't link or copy from cached entry '" << CacheEntryPath
802            << "' to '" << OutputPath << "'\n";
803   }
804   // No cache entry, just write out the buffer.
805   std::error_code Err;
806   raw_fd_ostream OS(OutputPath, Err, sys::fs::F_None);
807   if (Err)
808     report_fatal_error("Can't open output '" + OutputPath + "'\n");
809   OS << OutputBuffer.getBuffer();
810   return OutputPath.str();
811 }
812 
813 // Main entry point for the ThinLTO processing
814 void ThinLTOCodeGenerator::run() {
815   // Prepare the resulting object vector
816   assert(ProducedBinaries.empty() && "The generator should not be reused");
817   if (SavedObjectsDirectoryPath.empty())
818     ProducedBinaries.resize(Modules.size());
819   else {
820     sys::fs::create_directories(SavedObjectsDirectoryPath);
821     bool IsDir;
822     sys::fs::is_directory(SavedObjectsDirectoryPath, IsDir);
823     if (!IsDir)
824       report_fatal_error("Unexistent dir: '" + SavedObjectsDirectoryPath + "'");
825     ProducedBinaryFiles.resize(Modules.size());
826   }
827 
828   if (CodeGenOnly) {
829     // Perform only parallel codegen and return.
830     ThreadPool Pool;
831     int count = 0;
832     for (auto &ModuleBuffer : Modules) {
833       Pool.async([&](int count) {
834         LLVMContext Context;
835         Context.setDiscardValueNames(LTODiscardValueNames);
836 
837         // Parse module now
838         auto TheModule =
839             loadModuleFromBuffer(ModuleBuffer.getMemBuffer(), Context, false,
840                                  /*IsImporting*/ false);
841 
842         // CodeGen
843         auto OutputBuffer = codegenModule(*TheModule, *TMBuilder.create());
844         if (SavedObjectsDirectoryPath.empty())
845           ProducedBinaries[count] = std::move(OutputBuffer);
846         else
847           ProducedBinaryFiles[count] = writeGeneratedObject(
848               count, "", SavedObjectsDirectoryPath, *OutputBuffer);
849       }, count++);
850     }
851 
852     return;
853   }
854 
855   // Sequential linking phase
856   auto Index = linkCombinedIndex();
857 
858   // Save temps: index.
859   if (!SaveTempsDir.empty()) {
860     auto SaveTempPath = SaveTempsDir + "index.bc";
861     std::error_code EC;
862     raw_fd_ostream OS(SaveTempPath, EC, sys::fs::F_None);
863     if (EC)
864       report_fatal_error(Twine("Failed to open ") + SaveTempPath +
865                          " to save optimized bitcode\n");
866     WriteIndexToFile(*Index, OS);
867   }
868 
869 
870   // Prepare the module map.
871   auto ModuleMap = generateModuleMap(Modules);
872   auto ModuleCount = Modules.size();
873 
874   // Collect for each module the list of function it defines (GUID -> Summary).
875   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
876   Index->collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
877 
878   // Convert the preserved symbols set from string to GUID, this is needed for
879   // computing the caching hash and the internalization.
880   auto GUIDPreservedSymbols =
881       computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
882 
883   // Compute "dead" symbols, we don't want to import/export these!
884   computeDeadSymbolsInIndex(*Index, GUIDPreservedSymbols);
885 
886   // Collect the import/export lists for all modules from the call-graph in the
887   // combined index.
888   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
889   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
890   ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists,
891                            ExportLists);
892 
893   // We use a std::map here to be able to have a defined ordering when
894   // producing a hash for the cache entry.
895   // FIXME: we should be able to compute the caching hash for the entry based
896   // on the index, and nuke this map.
897   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
898 
899   // Resolve prevailing symbols, this has to be computed early because it
900   // impacts the caching.
901   resolvePrevailingInIndex(*Index, ResolvedODR);
902 
903   // Use global summary-based analysis to identify symbols that can be
904   // internalized (because they aren't exported or preserved as per callback).
905   // Changes are made in the index, consumed in the ThinLTO backends.
906   internalizeAndPromoteInIndex(ExportLists, GUIDPreservedSymbols, *Index);
907 
908   // Make sure that every module has an entry in the ExportLists, ImportList,
909   // GVSummary and ResolvedODR maps to enable threaded access to these maps
910   // below.
911   for (auto &Module : Modules) {
912     auto ModuleIdentifier = Module.getBufferIdentifier();
913     ExportLists[ModuleIdentifier];
914     ImportLists[ModuleIdentifier];
915     ResolvedODR[ModuleIdentifier];
916     ModuleToDefinedGVSummaries[ModuleIdentifier];
917   }
918 
919   // Compute the ordering we will process the inputs: the rough heuristic here
920   // is to sort them per size so that the largest module get schedule as soon as
921   // possible. This is purely a compile-time optimization.
922   std::vector<int> ModulesOrdering;
923   ModulesOrdering.resize(Modules.size());
924   std::iota(ModulesOrdering.begin(), ModulesOrdering.end(), 0);
925   llvm::sort(ModulesOrdering, [&](int LeftIndex, int RightIndex) {
926     auto LSize = Modules[LeftIndex].getBuffer().size();
927     auto RSize = Modules[RightIndex].getBuffer().size();
928     return LSize > RSize;
929   });
930 
931   // Parallel optimizer + codegen
932   {
933     ThreadPool Pool(ThreadCount);
934     for (auto IndexCount : ModulesOrdering) {
935       auto &ModuleBuffer = Modules[IndexCount];
936       Pool.async([&](int count) {
937         auto ModuleIdentifier = ModuleBuffer.getBufferIdentifier();
938         auto &ExportList = ExportLists[ModuleIdentifier];
939 
940         auto &DefinedGVSummaries = ModuleToDefinedGVSummaries[ModuleIdentifier];
941 
942         // The module may be cached, this helps handling it.
943         ModuleCacheEntry CacheEntry(CacheOptions.Path, *Index, ModuleIdentifier,
944                                     ImportLists[ModuleIdentifier], ExportList,
945                                     ResolvedODR[ModuleIdentifier],
946                                     DefinedGVSummaries, OptLevel, Freestanding,
947                                     TMBuilder);
948         auto CacheEntryPath = CacheEntry.getEntryPath();
949 
950         {
951           auto ErrOrBuffer = CacheEntry.tryLoadingBuffer();
952           LLVM_DEBUG(dbgs() << "Cache " << (ErrOrBuffer ? "hit" : "miss")
953                             << " '" << CacheEntryPath << "' for buffer "
954                             << count << " " << ModuleIdentifier << "\n");
955 
956           if (ErrOrBuffer) {
957             // Cache Hit!
958             if (SavedObjectsDirectoryPath.empty())
959               ProducedBinaries[count] = std::move(ErrOrBuffer.get());
960             else
961               ProducedBinaryFiles[count] = writeGeneratedObject(
962                   count, CacheEntryPath, SavedObjectsDirectoryPath,
963                   *ErrOrBuffer.get());
964             return;
965           }
966         }
967 
968         LLVMContext Context;
969         Context.setDiscardValueNames(LTODiscardValueNames);
970         Context.enableDebugTypeODRUniquing();
971         auto DiagFileOrErr = lto::setupOptimizationRemarks(
972             Context, LTORemarksFilename, LTOPassRemarksWithHotness, count);
973         if (!DiagFileOrErr) {
974           errs() << "Error: " << toString(DiagFileOrErr.takeError()) << "\n";
975           report_fatal_error("ThinLTO: Can't get an output file for the "
976                              "remarks");
977         }
978 
979         // Parse module now
980         auto TheModule =
981             loadModuleFromBuffer(ModuleBuffer.getMemBuffer(), Context, false,
982                                  /*IsImporting*/ false);
983 
984         // Save temps: original file.
985         saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc");
986 
987         auto &ImportList = ImportLists[ModuleIdentifier];
988         // Run the main process now, and generates a binary
989         auto OutputBuffer = ProcessThinLTOModule(
990             *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
991             ExportList, GUIDPreservedSymbols,
992             ModuleToDefinedGVSummaries[ModuleIdentifier], CacheOptions,
993             DisableCodeGen, SaveTempsDir, Freestanding, OptLevel, count);
994 
995         // Commit to the cache (if enabled)
996         CacheEntry.write(*OutputBuffer);
997 
998         if (SavedObjectsDirectoryPath.empty()) {
999           // We need to generated a memory buffer for the linker.
1000           if (!CacheEntryPath.empty()) {
1001             // When cache is enabled, reload from the cache if possible.
1002             // Releasing the buffer from the heap and reloading it from the
1003             // cache file with mmap helps us to lower memory pressure.
1004             // The freed memory can be used for the next input file.
1005             // The final binary link will read from the VFS cache (hopefully!)
1006             // or from disk (if the memory pressure was too high).
1007             auto ReloadedBufferOrErr = CacheEntry.tryLoadingBuffer();
1008             if (auto EC = ReloadedBufferOrErr.getError()) {
1009               // On error, keep the preexisting buffer and print a diagnostic.
1010               errs() << "error: can't reload cached file '" << CacheEntryPath
1011                      << "': " << EC.message() << "\n";
1012             } else {
1013               OutputBuffer = std::move(*ReloadedBufferOrErr);
1014             }
1015           }
1016           ProducedBinaries[count] = std::move(OutputBuffer);
1017           return;
1018         }
1019         ProducedBinaryFiles[count] = writeGeneratedObject(
1020             count, CacheEntryPath, SavedObjectsDirectoryPath, *OutputBuffer);
1021       }, IndexCount);
1022     }
1023   }
1024 
1025   pruneCache(CacheOptions.Path, CacheOptions.Policy);
1026 
1027   // If statistics were requested, print them out now.
1028   if (llvm::AreStatisticsEnabled())
1029     llvm::PrintStatistics();
1030   reportAndResetTimings();
1031 }
1032