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