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