OSDN Git Service

[ThinLTO] Add an auto-hide feature
[android-x86/external-llvm.git] / 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 convertSymbolNamesToGUID(const StringSet<> &NamedSymbols,
238                          const Triple &TheTriple) {
239   DenseSet<GlobalValue::GUID> GUIDSymbols(NamedSymbols.size());
240   for (auto &Entry : NamedSymbols) {
241     StringRef Name = Entry.first();
242     if (TheTriple.isOSBinFormatMachO() && Name.size() > 0 && Name[0] == '_')
243       Name = Name.drop_front();
244     GUIDSymbols.insert(GlobalValue::getGUID(Name));
245   }
246   return GUIDSymbols;
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   CrossReferencedSymbols.insert(Name);
558 }
559
560 // TargetMachine factory
561 std::unique_ptr<TargetMachine> TargetMachineBuilder::create() const {
562   std::string ErrMsg;
563   const Target *TheTarget =
564       TargetRegistry::lookupTarget(TheTriple.str(), ErrMsg);
565   if (!TheTarget) {
566     report_fatal_error("Can't load target for this Triple: " + ErrMsg);
567   }
568
569   // Use MAttr as the default set of features.
570   SubtargetFeatures Features(MAttr);
571   Features.getDefaultSubtargetFeatures(TheTriple);
572   std::string FeatureStr = Features.getString();
573
574   return std::unique_ptr<TargetMachine>(TheTarget->createTargetMachine(
575       TheTriple.str(), MCpu, FeatureStr, Options, RelocModel,
576       CodeModel::Default, CGOptLevel));
577 }
578
579 /**
580  * Produce the combined summary index from all the bitcode files:
581  * "thin-link".
582  */
583 std::unique_ptr<ModuleSummaryIndex> ThinLTOCodeGenerator::linkCombinedIndex() {
584   std::unique_ptr<ModuleSummaryIndex> CombinedIndex;
585   uint64_t NextModuleId = 0;
586   for (auto &ModuleBuffer : Modules) {
587     Expected<std::unique_ptr<object::ModuleSummaryIndexObjectFile>> ObjOrErr =
588         object::ModuleSummaryIndexObjectFile::create(ModuleBuffer);
589     if (!ObjOrErr) {
590       // FIXME diagnose
591       logAllUnhandledErrors(
592           ObjOrErr.takeError(), errs(),
593           "error: can't create ModuleSummaryIndexObjectFile for buffer: ");
594       return nullptr;
595     }
596     auto Index = (*ObjOrErr)->takeIndex();
597     if (CombinedIndex) {
598       CombinedIndex->mergeFrom(std::move(Index), ++NextModuleId);
599     } else {
600       CombinedIndex = std::move(Index);
601     }
602   }
603   return CombinedIndex;
604 }
605
606 /**
607  * Perform promotion and renaming of exported internal functions.
608  * Index is updated to reflect linkage changes from weak resolution.
609  */
610 void ThinLTOCodeGenerator::promote(Module &TheModule,
611                                    ModuleSummaryIndex &Index) {
612   auto ModuleCount = Index.modulePaths().size();
613   auto ModuleIdentifier = TheModule.getModuleIdentifier();
614
615   // Collect for each module the list of function it defines (GUID -> Summary).
616   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries;
617   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
618
619   // Convert the preserved symbols set from string to GUID
620   auto GUIDPreservedSymbols = convertSymbolNamesToGUID(
621       PreservedSymbols, Triple(TheModule.getTargetTriple()));
622
623   // Compute "dead" symbols, we don't want to import/export these!
624   auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols);
625
626   // Generate import/export list
627   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
628   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
629   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
630                            ExportLists, &DeadSymbols);
631
632   // Resolve LinkOnce/Weak symbols.
633   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
634   resolveWeakForLinkerInIndex(Index, ResolvedODR);
635
636   thinLTOResolveWeakForLinkerModule(
637       TheModule, ModuleToDefinedGVSummaries[ModuleIdentifier]);
638
639   // Promote the exported values in the index, so that they are promoted
640   // in the module.
641   auto isExported = [&](StringRef ModuleIdentifier,
642                         GlobalValue::GUID GUID) -> SummaryResolution {
643     const auto &ExportList = ExportLists.find(ModuleIdentifier);
644     if ((ExportList != ExportLists.end() && ExportList->second.count(GUID)) ||
645         GUIDPreservedSymbols.count(GUID))
646       return Exported;
647     return Internal;
648   };
649   thinLTOInternalizeAndPromoteInIndex(Index, isExported);
650
651   promoteModule(TheModule, Index);
652 }
653
654 /**
655  * Perform cross-module importing for the module identified by ModuleIdentifier.
656  */
657 void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
658                                              ModuleSummaryIndex &Index) {
659   auto ModuleMap = generateModuleMap(Modules);
660   auto ModuleCount = Index.modulePaths().size();
661
662   // Collect for each module the list of function it defines (GUID -> Summary).
663   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
664   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
665
666   // Convert the preserved symbols set from string to GUID
667   auto GUIDPreservedSymbols = convertSymbolNamesToGUID(
668       PreservedSymbols, Triple(TheModule.getTargetTriple()));
669
670   // Compute "dead" symbols, we don't want to import/export these!
671   auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols);
672
673   // Generate import/export list
674   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
675   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
676   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
677                            ExportLists, &DeadSymbols);
678   auto &ImportList = ImportLists[TheModule.getModuleIdentifier()];
679
680   crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
681 }
682
683 /**
684  * Compute the list of summaries needed for importing into module.
685  */
686 void ThinLTOCodeGenerator::gatherImportedSummariesForModule(
687     StringRef ModulePath, ModuleSummaryIndex &Index,
688     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
689   auto ModuleCount = Index.modulePaths().size();
690
691   // Collect for each module the list of function it defines (GUID -> Summary).
692   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
693   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
694
695   // Generate import/export list
696   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
697   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
698   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
699                            ExportLists);
700
701   llvm::gatherImportedSummariesForModule(ModulePath, ModuleToDefinedGVSummaries,
702                                          ImportLists[ModulePath],
703                                          ModuleToSummariesForIndex);
704 }
705
706 /**
707  * Emit the list of files needed for importing into module.
708  */
709 void ThinLTOCodeGenerator::emitImports(StringRef ModulePath,
710                                        StringRef OutputName,
711                                        ModuleSummaryIndex &Index) {
712   auto ModuleCount = Index.modulePaths().size();
713
714   // Collect for each module the list of function it defines (GUID -> Summary).
715   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
716   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
717
718   // Generate import/export list
719   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
720   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
721   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
722                            ExportLists);
723
724   std::error_code EC;
725   if ((EC = EmitImportsFiles(ModulePath, OutputName, ImportLists[ModulePath])))
726     report_fatal_error(Twine("Failed to open ") + OutputName +
727                        " to save imports lists\n");
728 }
729
730 /**
731  * Perform internalization. Index is updated to reflect linkage changes.
732  */
733 void ThinLTOCodeGenerator::internalize(Module &TheModule,
734                                        ModuleSummaryIndex &Index) {
735   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
736   auto ModuleCount = Index.modulePaths().size();
737   auto ModuleIdentifier = TheModule.getModuleIdentifier();
738
739   // Convert the preserved symbols set from string to GUID
740   auto GUIDPreservedSymbols =
741       convertSymbolNamesToGUID(PreservedSymbols, TMBuilder.TheTriple);
742
743   // Collect for each module the list of function it defines (GUID -> Summary).
744   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
745   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
746
747   // Compute "dead" symbols, we don't want to import/export these!
748   auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols);
749
750   // Generate import/export list
751   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
752   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
753   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
754                            ExportLists, &DeadSymbols);
755   auto &ExportList = ExportLists[ModuleIdentifier];
756
757   // Be friendly and don't nuke totally the module when the client didn't
758   // supply anything to preserve.
759   if (ExportList.empty() && GUIDPreservedSymbols.empty())
760     return;
761
762   // Internalization
763   auto isExported = [&](StringRef ModuleIdentifier,
764                         GlobalValue::GUID GUID) -> SummaryResolution {
765     const auto &ExportList = ExportLists.find(ModuleIdentifier);
766     if ((ExportList != ExportLists.end() && ExportList->second.count(GUID)) ||
767         GUIDPreservedSymbols.count(GUID))
768       return Exported;
769     return Internal;
770   };
771   thinLTOInternalizeAndPromoteInIndex(Index, isExported);
772   thinLTOInternalizeModule(TheModule,
773                            ModuleToDefinedGVSummaries[ModuleIdentifier]);
774 }
775
776 /**
777  * Perform post-importing ThinLTO optimizations.
778  */
779 void ThinLTOCodeGenerator::optimize(Module &TheModule) {
780   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
781
782   // Optimize now
783   optimizeModule(TheModule, *TMBuilder.create(), OptLevel);
784 }
785
786 /**
787  * Perform ThinLTO CodeGen.
788  */
789 std::unique_ptr<MemoryBuffer> ThinLTOCodeGenerator::codegen(Module &TheModule) {
790   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
791   return codegenModule(TheModule, *TMBuilder.create());
792 }
793
794 /// Write out the generated object file, either from CacheEntryPath or from
795 /// OutputBuffer, preferring hard-link when possible.
796 /// Returns the path to the generated file in SavedObjectsDirectoryPath.
797 static std::string writeGeneratedObject(int count, StringRef CacheEntryPath,
798                                         StringRef SavedObjectsDirectoryPath,
799                                         const MemoryBuffer &OutputBuffer) {
800   SmallString<128> OutputPath(SavedObjectsDirectoryPath);
801   llvm::sys::path::append(OutputPath, Twine(count) + ".thinlto.o");
802   OutputPath.c_str(); // Ensure the string is null terminated.
803   if (sys::fs::exists(OutputPath))
804     sys::fs::remove(OutputPath);
805
806   // We don't return a memory buffer to the linker, just a list of files.
807   if (!CacheEntryPath.empty()) {
808     // Cache is enabled, hard-link the entry (or copy if hard-link fails).
809     auto Err = sys::fs::create_hard_link(CacheEntryPath, OutputPath);
810     if (!Err)
811       return OutputPath.str();
812     // Hard linking failed, try to copy.
813     Err = sys::fs::copy_file(CacheEntryPath, OutputPath);
814     if (!Err)
815       return OutputPath.str();
816     // Copy failed (could be because the CacheEntry was removed from the cache
817     // in the meantime by another process), fall back and try to write down the
818     // buffer to the output.
819     errs() << "error: can't link or copy from cached entry '" << CacheEntryPath
820            << "' to '" << OutputPath << "'\n";
821   }
822   // No cache entry, just write out the buffer.
823   std::error_code Err;
824   raw_fd_ostream OS(OutputPath, Err, sys::fs::F_None);
825   if (Err)
826     report_fatal_error("Can't open output '" + OutputPath + "'\n");
827   OS << OutputBuffer.getBuffer();
828   return OutputPath.str();
829 }
830
831 // Main entry point for the ThinLTO processing
832 void ThinLTOCodeGenerator::run() {
833   // Prepare the resulting object vector
834   assert(ProducedBinaries.empty() && "The generator should not be reused");
835   if (SavedObjectsDirectoryPath.empty())
836     ProducedBinaries.resize(Modules.size());
837   else {
838     sys::fs::create_directories(SavedObjectsDirectoryPath);
839     bool IsDir;
840     sys::fs::is_directory(SavedObjectsDirectoryPath, IsDir);
841     if (!IsDir)
842       report_fatal_error("Unexistent dir: '" + SavedObjectsDirectoryPath + "'");
843     ProducedBinaryFiles.resize(Modules.size());
844   }
845
846   if (CodeGenOnly) {
847     // Perform only parallel codegen and return.
848     ThreadPool Pool;
849     int count = 0;
850     for (auto &ModuleBuffer : Modules) {
851       Pool.async([&](int count) {
852         LLVMContext Context;
853         Context.setDiscardValueNames(LTODiscardValueNames);
854
855         // Parse module now
856         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false,
857                                               /*IsImporting*/ false);
858
859         // CodeGen
860         auto OutputBuffer = codegen(*TheModule);
861         if (SavedObjectsDirectoryPath.empty())
862           ProducedBinaries[count] = std::move(OutputBuffer);
863         else
864           ProducedBinaryFiles[count] = writeGeneratedObject(
865               count, "", SavedObjectsDirectoryPath, *OutputBuffer);
866       }, count++);
867     }
868
869     return;
870   }
871
872   // Sequential linking phase
873   auto Index = linkCombinedIndex();
874
875   // Save temps: index.
876   if (!SaveTempsDir.empty()) {
877     auto SaveTempPath = SaveTempsDir + "index.bc";
878     std::error_code EC;
879     raw_fd_ostream OS(SaveTempPath, EC, sys::fs::F_None);
880     if (EC)
881       report_fatal_error(Twine("Failed to open ") + SaveTempPath +
882                          " to save optimized bitcode\n");
883     WriteIndexToFile(*Index, OS);
884   }
885
886
887   // Prepare the module map.
888   auto ModuleMap = generateModuleMap(Modules);
889   auto ModuleCount = Modules.size();
890
891   // Collect for each module the list of function it defines (GUID -> Summary).
892   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
893   Index->collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
894
895   // Convert the preserved symbols set from string to GUID, this is needed for
896   // computing the caching hash and the internalization.
897   auto GUIDPreservedSymbols =
898       convertSymbolNamesToGUID(PreservedSymbols, TMBuilder.TheTriple);
899   auto GUIDCrossRefSymbols =
900       convertSymbolNamesToGUID(CrossReferencedSymbols, TMBuilder.TheTriple);
901
902   // Compute "dead" symbols, we don't want to import/export these!
903   auto DeadSymbols = computeDeadSymbols(*Index, GUIDPreservedSymbols);
904
905   // Collect the import/export lists for all modules from the call-graph in the
906   // combined index.
907   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
908   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
909   ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists,
910                            ExportLists, &DeadSymbols);
911
912   // We use a std::map here to be able to have a defined ordering when
913   // producing a hash for the cache entry.
914   // FIXME: we should be able to compute the caching hash for the entry based
915   // on the index, and nuke this map.
916   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
917
918   // Resolve LinkOnce/Weak symbols, this has to be computed early because it
919   // impacts the caching.
920   resolveWeakForLinkerInIndex(*Index, ResolvedODR);
921
922   auto isExported = [&](StringRef ModuleIdentifier,
923                         GlobalValue::GUID GUID) -> SummaryResolution {
924     if (GUIDPreservedSymbols.count(GUID))
925       return Exported;
926     if (GUIDCrossRefSymbols.count(GUID))
927       return Hidden;
928     const auto &ExportList = ExportLists.find(ModuleIdentifier);
929     if (ExportList != ExportLists.end() && ExportList->second.count(GUID))
930       return Hidden;
931     return Internal;
932   };
933
934   // Use global summary-based analysis to identify symbols that can be
935   // internalized (because they aren't exported or preserved as per callback).
936   // Changes are made in the index, consumed in the ThinLTO backends.
937   thinLTOInternalizeAndPromoteInIndex(*Index, isExported);
938
939   // Make sure that every module has an entry in the ExportLists and
940   // ResolvedODR maps to enable threaded access to these maps below.
941   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
942     ExportLists[DefinedGVSummaries.first()];
943     ResolvedODR[DefinedGVSummaries.first()];
944   }
945
946   // Compute the ordering we will process the inputs: the rough heuristic here
947   // is to sort them per size so that the largest module get schedule as soon as
948   // possible. This is purely a compile-time optimization.
949   std::vector<int> ModulesOrdering;
950   ModulesOrdering.resize(Modules.size());
951   std::iota(ModulesOrdering.begin(), ModulesOrdering.end(), 0);
952   std::sort(ModulesOrdering.begin(), ModulesOrdering.end(),
953             [&](int LeftIndex, int RightIndex) {
954               auto LSize = Modules[LeftIndex].getBufferSize();
955               auto RSize = Modules[RightIndex].getBufferSize();
956               return LSize > RSize;
957             });
958
959   // Parallel optimizer + codegen
960   {
961     ThreadPool Pool(ThreadCount);
962     for (auto IndexCount : ModulesOrdering) {
963       auto &ModuleBuffer = Modules[IndexCount];
964       Pool.async([&](int count) {
965         auto ModuleIdentifier = ModuleBuffer.getBufferIdentifier();
966         auto &ExportList = ExportLists[ModuleIdentifier];
967
968         auto &DefinedFunctions = ModuleToDefinedGVSummaries[ModuleIdentifier];
969
970         // The module may be cached, this helps handling it.
971         ModuleCacheEntry CacheEntry(CacheOptions.Path, *Index, ModuleIdentifier,
972                                     ImportLists[ModuleIdentifier], ExportList,
973                                     ResolvedODR[ModuleIdentifier],
974                                     DefinedFunctions, GUIDPreservedSymbols,
975                                     OptLevel, TMBuilder);
976         auto CacheEntryPath = CacheEntry.getEntryPath();
977
978         {
979           auto ErrOrBuffer = CacheEntry.tryLoadingBuffer();
980           DEBUG(dbgs() << "Cache " << (ErrOrBuffer ? "hit" : "miss") << " '"
981                        << CacheEntryPath << "' for buffer " << count << " "
982                        << ModuleIdentifier << "\n");
983
984           if (ErrOrBuffer) {
985             // Cache Hit!
986             if (SavedObjectsDirectoryPath.empty())
987               ProducedBinaries[count] = std::move(ErrOrBuffer.get());
988             else
989               ProducedBinaryFiles[count] = writeGeneratedObject(
990                   count, CacheEntryPath, SavedObjectsDirectoryPath,
991                   *ErrOrBuffer.get());
992             return;
993           }
994         }
995
996         LLVMContext Context;
997         Context.setDiscardValueNames(LTODiscardValueNames);
998         Context.enableDebugTypeODRUniquing();
999         auto DiagFileOrErr = setupOptimizationRemarks(Context, count);
1000         if (!DiagFileOrErr) {
1001           errs() << "Error: " << toString(DiagFileOrErr.takeError()) << "\n";
1002           report_fatal_error("ThinLTO: Can't get an output file for the "
1003                              "remarks");
1004         }
1005
1006         // Parse module now
1007         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false,
1008                                               /*IsImporting*/ false);
1009
1010         // Save temps: original file.
1011         saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc");
1012
1013         auto &ImportList = ImportLists[ModuleIdentifier];
1014         // Run the main process now, and generates a binary
1015         auto OutputBuffer = ProcessThinLTOModule(
1016             *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
1017             ExportList, GUIDPreservedSymbols,
1018             ModuleToDefinedGVSummaries[ModuleIdentifier], CacheOptions,
1019             DisableCodeGen, SaveTempsDir, OptLevel, count);
1020
1021         // Commit to the cache (if enabled)
1022         CacheEntry.write(*OutputBuffer);
1023
1024         if (SavedObjectsDirectoryPath.empty()) {
1025           // We need to generated a memory buffer for the linker.
1026           if (!CacheEntryPath.empty()) {
1027             // Cache is enabled, reload from the cache
1028             // We do this to lower memory pressuree: the buffer is on the heap
1029             // and releasing it frees memory that can be used for the next input
1030             // file. The final binary link will read from the VFS cache
1031             // (hopefully!) or from disk if the memory pressure wasn't too high.
1032             auto ReloadedBufferOrErr = CacheEntry.tryLoadingBuffer();
1033             if (auto EC = ReloadedBufferOrErr.getError()) {
1034               // On error, keeping the preexisting buffer and printing a
1035               // diagnostic is more friendly than just crashing.
1036               errs() << "error: can't reload cached file '" << CacheEntryPath
1037                      << "': " << EC.message() << "\n";
1038             } else {
1039               OutputBuffer = std::move(*ReloadedBufferOrErr);
1040             }
1041           }
1042           ProducedBinaries[count] = std::move(OutputBuffer);
1043           return;
1044         }
1045         ProducedBinaryFiles[count] = writeGeneratedObject(
1046             count, CacheEntryPath, SavedObjectsDirectoryPath, *OutputBuffer);
1047       }, IndexCount);
1048     }
1049   }
1050
1051   CachePruning(CacheOptions.Path)
1052       .setPruningInterval(std::chrono::seconds(CacheOptions.PruningInterval))
1053       .setEntryExpiration(std::chrono::seconds(CacheOptions.Expiration))
1054       .setMaxSize(CacheOptions.MaxPercentageOfAvailableSpace)
1055       .prune();
1056
1057   // If statistics were requested, print them out now.
1058   if (llvm::AreStatisticsEnabled())
1059     llvm::PrintStatistics();
1060 }