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/ThinLTOCodeGenerator.h"
16 
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/StringExtras.h"
19 #include "llvm/Analysis/TargetLibraryInfo.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/Bitcode/BitcodeWriterPass.h"
22 #include "llvm/Bitcode/ReaderWriter.h"
23 #include "llvm/ExecutionEngine/ObjectMemoryBuffer.h"
24 #include "llvm/IR/DiagnosticPrinter.h"
25 #include "llvm/IR/LLVMContext.h"
26 #include "llvm/IR/LegacyPassManager.h"
27 #include "llvm/IR/Mangler.h"
28 #include "llvm/IRReader/IRReader.h"
29 #include "llvm/Linker/Linker.h"
30 #include "llvm/MC/SubtargetFeature.h"
31 #include "llvm/Object/ModuleSummaryIndexObjectFile.h"
32 #include "llvm/Support/SourceMgr.h"
33 #include "llvm/Support/TargetRegistry.h"
34 #include "llvm/Support/ThreadPool.h"
35 #include "llvm/Target/TargetMachine.h"
36 #include "llvm/Transforms/IPO.h"
37 #include "llvm/Transforms/IPO/FunctionImport.h"
38 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
39 #include "llvm/Transforms/ObjCARC.h"
40 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
41 
42 using namespace llvm;
43 
44 namespace llvm {
45 // Flags -discard-value-names, defined in LTOCodeGenerator.cpp
46 extern cl::opt<bool> LTODiscardValueNames;
47 }
48 
49 namespace {
50 
51 static cl::opt<int> ThreadCount("threads",
52                                 cl::init(std::thread::hardware_concurrency()));
53 
54 static void diagnosticHandler(const DiagnosticInfo &DI) {
55   DiagnosticPrinterRawOStream DP(errs());
56   DI.print(DP);
57   errs() << '\n';
58 }
59 
60 // Simple helper to load a module from bitcode
61 static std::unique_ptr<Module>
62 loadModuleFromBuffer(const MemoryBufferRef &Buffer, LLVMContext &Context,
63                      bool Lazy) {
64   SMDiagnostic Err;
65   ErrorOr<std::unique_ptr<Module>> ModuleOrErr(nullptr);
66   if (Lazy) {
67     ModuleOrErr =
68         getLazyBitcodeModule(MemoryBuffer::getMemBuffer(Buffer, false), Context,
69                              /* ShouldLazyLoadMetadata */ Lazy);
70   } else {
71     ModuleOrErr = parseBitcodeFile(Buffer, Context);
72   }
73   if (std::error_code EC = ModuleOrErr.getError()) {
74     Err = SMDiagnostic(Buffer.getBufferIdentifier(), SourceMgr::DK_Error,
75                        EC.message());
76     Err.print("ThinLTO", errs());
77     report_fatal_error("Can't load module, abort.");
78   }
79   return std::move(ModuleOrErr.get());
80 }
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   auto SaveTempPath = TempDir + llvm::utostr(count) + Suffix;
89   std::error_code EC;
90   raw_fd_ostream OS(SaveTempPath.str(), 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 bool IsFirstDefinitionForLinker(const GlobalValueInfoList &GVInfo,
98                                 const ModuleSummaryIndex &Index,
99                                 StringRef ModulePath) {
100   // Get the first *linker visible* definition for this global in the summary
101   // list.
102   auto FirstDefForLinker = llvm::find_if(
103       GVInfo, [](const std::unique_ptr<GlobalValueInfo> &FuncInfo) {
104         auto Linkage = FuncInfo->summary()->linkage();
105         return !GlobalValue::isAvailableExternallyLinkage(Linkage);
106       });
107   // If \p GV is not the first definition, give up...
108   if ((*FirstDefForLinker)->summary()->modulePath() != ModulePath)
109     return false;
110   // If there is any strong definition anywhere, do not bother emitting this.
111   if (llvm::any_of(
112           GVInfo, [](const std::unique_ptr<GlobalValueInfo> &FuncInfo) {
113             auto Linkage = FuncInfo->summary()->linkage();
114             return !GlobalValue::isAvailableExternallyLinkage(Linkage) &&
115                    !GlobalValue::isWeakForLinker(Linkage);
116           }))
117     return false;
118   return true;
119 }
120 
121 static void ResolveODR(GlobalValue &GV, const ModuleSummaryIndex &Index,
122                              StringRef ModulePath) {
123   if (GV.isDeclaration())
124     return;
125 
126   auto HasMultipleCopies =
127       [&](const GlobalValueInfoList &GVInfo) { return GVInfo.size() > 1; };
128 
129   auto getGVInfo = [&](GlobalValue &GV) -> const GlobalValueInfoList *{
130     auto GUID = Function::getGlobalIdentifier(GV.getName(), GV.getLinkage(),
131                                               ModulePath);
132     auto It = Index.findGlobalValueInfoList(GV.getName());
133     if (It == Index.end())
134       return nullptr;
135     return &It->second;
136   };
137 
138   switch (GV.getLinkage()) {
139   case GlobalValue::ExternalLinkage:
140   case GlobalValue::AvailableExternallyLinkage:
141   case GlobalValue::AppendingLinkage:
142   case GlobalValue::InternalLinkage:
143   case GlobalValue::PrivateLinkage:
144   case GlobalValue::ExternalWeakLinkage:
145   case GlobalValue::CommonLinkage:
146   case GlobalValue::LinkOnceAnyLinkage:
147   case GlobalValue::WeakAnyLinkage:
148     break;
149   case GlobalValue::LinkOnceODRLinkage:
150   case GlobalValue::WeakODRLinkage: {
151     auto *GVInfo = getGVInfo(GV);
152     if (!GVInfo)
153       break;
154     // We need to emit only one of these, the first module will keep
155     // it, but turned into a weak while the others will drop it.
156     if (!HasMultipleCopies(*GVInfo))
157       break;
158     if (IsFirstDefinitionForLinker(*GVInfo, Index, ModulePath))
159       GV.setLinkage(GlobalValue::WeakODRLinkage);
160     else
161       GV.setLinkage(GlobalValue::AvailableExternallyLinkage);
162     break;
163   }
164   }
165 }
166 
167 /// Resolve LinkOnceODR and WeakODR.
168 ///
169 /// We'd like to drop these function if they are no longer referenced in the
170 /// current module. However there is a chance that another module is still
171 /// referencing them because of the import. We make sure we always emit at least
172 /// one copy.
173 static void ResolveODR(Module &TheModule,
174                              const ModuleSummaryIndex &Index) {
175   // We won't optimize the globals that are referenced by an alias for now
176   // Ideally we should turn the alias into a global and duplicate the definition
177   // when needed.
178   DenseSet<GlobalValue *> GlobalInvolvedWithAlias;
179   for (auto &GA : TheModule.aliases()) {
180     auto *GO = GA.getBaseObject();
181     if (auto *GV = dyn_cast<GlobalValue>(GO))
182       GlobalInvolvedWithAlias.insert(GV);
183   }
184   // Process functions and global now
185   for (auto &GV : TheModule) {
186     if (!GlobalInvolvedWithAlias.count(&GV))
187       ResolveODR(GV, Index, TheModule.getModuleIdentifier());
188   }
189   for (auto &GV : TheModule.globals()) {
190     if (!GlobalInvolvedWithAlias.count(&GV))
191       ResolveODR(GV, Index, TheModule.getModuleIdentifier());
192   }
193 }
194 
195 static StringMap<MemoryBufferRef>
196 generateModuleMap(const std::vector<MemoryBufferRef> &Modules) {
197   StringMap<MemoryBufferRef> ModuleMap;
198   for (auto &ModuleBuffer : Modules) {
199     assert(ModuleMap.find(ModuleBuffer.getBufferIdentifier()) ==
200                ModuleMap.end() &&
201            "Expect unique Buffer Identifier");
202     ModuleMap[ModuleBuffer.getBufferIdentifier()] = ModuleBuffer;
203   }
204   return ModuleMap;
205 }
206 
207 /// Provide a "loader" for the FunctionImporter to access function from other
208 /// modules.
209 class ModuleLoader {
210   /// The context that will be used for importing.
211   LLVMContext &Context;
212 
213   /// Map from Module identifier to MemoryBuffer. Used by clients like the
214   /// FunctionImported to request loading a Module.
215   StringMap<MemoryBufferRef> &ModuleMap;
216 
217 public:
218   ModuleLoader(LLVMContext &Context, StringMap<MemoryBufferRef> &ModuleMap)
219       : Context(Context), ModuleMap(ModuleMap) {}
220 
221   /// Load a module on demand.
222   std::unique_ptr<Module> operator()(StringRef Identifier) {
223     return loadModuleFromBuffer(ModuleMap[Identifier], Context, /*Lazy*/ true);
224   }
225 };
226 
227 static void promoteModule(Module &TheModule, const ModuleSummaryIndex &Index) {
228   if (renameModuleForThinLTO(TheModule, Index))
229     report_fatal_error("renameModuleForThinLTO failed");
230 }
231 
232 static void
233 crossImportIntoModule(Module &TheModule, const ModuleSummaryIndex &Index,
234                       StringMap<MemoryBufferRef> &ModuleMap,
235                       const FunctionImporter::ImportMapTy &ImportList) {
236   ModuleLoader Loader(TheModule.getContext(), ModuleMap);
237   FunctionImporter Importer(Index, Loader);
238   Importer.importFunctions(TheModule, ImportList);
239 }
240 
241 static void optimizeModule(Module &TheModule, TargetMachine &TM) {
242   // Populate the PassManager
243   PassManagerBuilder PMB;
244   PMB.LibraryInfo = new TargetLibraryInfoImpl(TM.getTargetTriple());
245   PMB.Inliner = createFunctionInliningPass();
246   // FIXME: should get it from the bitcode?
247   PMB.OptLevel = 3;
248   PMB.LoopVectorize = true;
249   PMB.SLPVectorize = true;
250   PMB.VerifyInput = true;
251   PMB.VerifyOutput = false;
252 
253   legacy::PassManager PM;
254 
255   // Add the TTI (required to inform the vectorizer about register size for
256   // instance)
257   PM.add(createTargetTransformInfoWrapperPass(TM.getTargetIRAnalysis()));
258 
259   // Add optimizations
260   PMB.populateThinLTOPassManager(PM);
261 
262   PM.run(TheModule);
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, 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<ObjectMemoryBuffer>(std::move(OutputBuffer));
287 }
288 
289 static std::unique_ptr<MemoryBuffer>
290 ProcessThinLTOModule(Module &TheModule, const ModuleSummaryIndex &Index,
291                      StringMap<MemoryBufferRef> &ModuleMap, TargetMachine &TM,
292                      const FunctionImporter::ImportMapTy &ImportList,
293                      ThinLTOCodeGenerator::CachingOptions CacheOptions,
294                      bool DisableCodeGen, StringRef SaveTempsDir,
295                      unsigned count) {
296 
297   // Save temps: after IPO.
298   saveTempBitcode(TheModule, SaveTempsDir, count, ".1.IPO.bc");
299 
300   // "Benchmark"-like optimization: single-source case
301   bool SingleModule = (ModuleMap.size() == 1);
302 
303   if (!SingleModule) {
304     promoteModule(TheModule, Index);
305 
306     // Resolve the LinkOnce/Weak ODR, trying to turn them into
307     // "available_externally" when possible.
308     // This is a compile-time optimization.
309     ResolveODR(TheModule, Index);
310 
311     // Save temps: after promotion.
312     saveTempBitcode(TheModule, SaveTempsDir, count, ".2.promoted.bc");
313 
314     crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
315 
316     // Save temps: after cross-module import.
317     saveTempBitcode(TheModule, SaveTempsDir, count, ".3.imported.bc");
318   }
319 
320   optimizeModule(TheModule, TM);
321 
322   saveTempBitcode(TheModule, SaveTempsDir, count, ".3.opt.bc");
323 
324   if (DisableCodeGen) {
325     // Configured to stop before CodeGen, serialize the bitcode and return.
326     SmallVector<char, 128> OutputBuffer;
327     {
328       raw_svector_ostream OS(OutputBuffer);
329       WriteBitcodeToFile(&TheModule, OS, true, true);
330     }
331     return make_unique<ObjectMemoryBuffer>(std::move(OutputBuffer));
332   }
333 
334   return codegenModule(TheModule, TM);
335 }
336 
337 // Initialize the TargetMachine builder for a given Triple
338 static void initTMBuilder(TargetMachineBuilder &TMBuilder,
339                           const Triple &TheTriple) {
340   // Set a default CPU for Darwin triples (copied from LTOCodeGenerator).
341   // FIXME this looks pretty terrible...
342   if (TMBuilder.MCpu.empty() && TheTriple.isOSDarwin()) {
343     if (TheTriple.getArch() == llvm::Triple::x86_64)
344       TMBuilder.MCpu = "core2";
345     else if (TheTriple.getArch() == llvm::Triple::x86)
346       TMBuilder.MCpu = "yonah";
347     else if (TheTriple.getArch() == llvm::Triple::aarch64)
348       TMBuilder.MCpu = "cyclone";
349   }
350   TMBuilder.TheTriple = std::move(TheTriple);
351 }
352 
353 } // end anonymous namespace
354 
355 void ThinLTOCodeGenerator::addModule(StringRef Identifier, StringRef Data) {
356   MemoryBufferRef Buffer(Data, Identifier);
357   if (Modules.empty()) {
358     // First module added, so initialize the triple and some options
359     LLVMContext Context;
360     Triple TheTriple(getBitcodeTargetTriple(Buffer, Context));
361     initTMBuilder(TMBuilder, Triple(TheTriple));
362   }
363 #ifndef NDEBUG
364   else {
365     LLVMContext Context;
366     assert(TMBuilder.TheTriple.str() ==
367                getBitcodeTargetTriple(Buffer, Context) &&
368            "ThinLTO modules with different triple not supported");
369   }
370 #endif
371   Modules.push_back(Buffer);
372 }
373 
374 void ThinLTOCodeGenerator::preserveSymbol(StringRef Name) {
375   PreservedSymbols.insert(Name);
376 }
377 
378 void ThinLTOCodeGenerator::crossReferenceSymbol(StringRef Name) {
379   CrossReferencedSymbols.insert(Name);
380 }
381 
382 // TargetMachine factory
383 std::unique_ptr<TargetMachine> TargetMachineBuilder::create() const {
384   std::string ErrMsg;
385   const Target *TheTarget =
386       TargetRegistry::lookupTarget(TheTriple.str(), ErrMsg);
387   if (!TheTarget) {
388     report_fatal_error("Can't load target for this Triple: " + ErrMsg);
389   }
390 
391   // Use MAttr as the default set of features.
392   SubtargetFeatures Features(MAttr);
393   Features.getDefaultSubtargetFeatures(TheTriple);
394   std::string FeatureStr = Features.getString();
395   return std::unique_ptr<TargetMachine>(TheTarget->createTargetMachine(
396       TheTriple.str(), MCpu, FeatureStr, Options, RelocModel,
397       CodeModel::Default, CGOptLevel));
398 }
399 
400 /**
401  * Produce the combined summary index from all the bitcode files:
402  * "thin-link".
403  */
404 std::unique_ptr<ModuleSummaryIndex> ThinLTOCodeGenerator::linkCombinedIndex() {
405   std::unique_ptr<ModuleSummaryIndex> CombinedIndex;
406   uint64_t NextModuleId = 0;
407   for (auto &ModuleBuffer : Modules) {
408     ErrorOr<std::unique_ptr<object::ModuleSummaryIndexObjectFile>> ObjOrErr =
409         object::ModuleSummaryIndexObjectFile::create(ModuleBuffer,
410                                                      diagnosticHandler, false);
411     if (std::error_code EC = ObjOrErr.getError()) {
412       // FIXME diagnose
413       errs() << "error: can't create ModuleSummaryIndexObjectFile for buffer: "
414              << EC.message() << "\n";
415       return nullptr;
416     }
417     auto Index = (*ObjOrErr)->takeIndex();
418     if (CombinedIndex) {
419       CombinedIndex->mergeFrom(std::move(Index), ++NextModuleId);
420     } else {
421       CombinedIndex = std::move(Index);
422     }
423   }
424   return CombinedIndex;
425 }
426 
427 /**
428  * Perform promotion and renaming of exported internal functions.
429  */
430 void ThinLTOCodeGenerator::promote(Module &TheModule,
431                                    ModuleSummaryIndex &Index) {
432 
433   // Resolve the LinkOnceODR, trying to turn them into "available_externally"
434   // where possible.
435   ResolveODR(TheModule, Index);
436 
437   promoteModule(TheModule, Index);
438 }
439 
440 /**
441  * Perform cross-module importing for the module identified by ModuleIdentifier.
442  */
443 void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
444                                              ModuleSummaryIndex &Index) {
445   auto ModuleMap = generateModuleMap(Modules);
446 
447   // Generate import/export list
448   auto ModuleCount = Index.modulePaths().size();
449   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
450   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
451   ComputeCrossModuleImport(Index, ImportLists, ExportLists);
452   auto &ImportList = ImportLists[TheModule.getModuleIdentifier()];
453 
454   crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
455 }
456 
457 /**
458  * Perform post-importing ThinLTO optimizations.
459  */
460 void ThinLTOCodeGenerator::optimize(Module &TheModule) {
461   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
462   optimizeModule(TheModule, *TMBuilder.create());
463 }
464 
465 /**
466  * Perform ThinLTO CodeGen.
467  */
468 std::unique_ptr<MemoryBuffer> ThinLTOCodeGenerator::codegen(Module &TheModule) {
469   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
470   return codegenModule(TheModule, *TMBuilder.create());
471 }
472 
473 // Main entry point for the ThinLTO processing
474 void ThinLTOCodeGenerator::run() {
475   if (CodeGenOnly) {
476     // Perform only parallel codegen and return.
477     ThreadPool Pool;
478     assert(ProducedBinaries.empty() && "The generator should not be reused");
479     ProducedBinaries.resize(Modules.size());
480     int count = 0;
481     for (auto &ModuleBuffer : Modules) {
482       Pool.async([&](int count) {
483         LLVMContext Context;
484         Context.setDiscardValueNames(LTODiscardValueNames);
485 
486         // Parse module now
487         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false);
488 
489         // CodeGen
490         ProducedBinaries[count] = codegen(*TheModule);
491       }, count++);
492     }
493 
494     return;
495   }
496 
497   // Sequential linking phase
498   auto Index = linkCombinedIndex();
499 
500   // Save temps: index.
501   if (!SaveTempsDir.empty()) {
502     auto SaveTempPath = SaveTempsDir + "index.bc";
503     std::error_code EC;
504     raw_fd_ostream OS(SaveTempPath, EC, sys::fs::F_None);
505     if (EC)
506       report_fatal_error(Twine("Failed to open ") + SaveTempPath +
507                          " to save optimized bitcode\n");
508     WriteIndexToFile(*Index, OS);
509   }
510 
511   // Prepare the resulting object vector
512   assert(ProducedBinaries.empty() && "The generator should not be reused");
513   ProducedBinaries.resize(Modules.size());
514 
515   // Prepare the module map.
516   auto ModuleMap = generateModuleMap(Modules);
517   auto ModuleCount = Modules.size();
518 
519   // Collect the import/export lists for all modules from the call-graph in the
520   // combined index.
521   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
522   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
523   ComputeCrossModuleImport(*Index, ImportLists, ExportLists);
524 
525   // Parallel optimizer + codegen
526   {
527     ThreadPool Pool(ThreadCount);
528     int count = 0;
529     for (auto &ModuleBuffer : Modules) {
530       Pool.async([&](int count) {
531         LLVMContext Context;
532         Context.setDiscardValueNames(LTODiscardValueNames);
533 
534         // Parse module now
535         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false);
536 
537         // Save temps: original file.
538         if (!SaveTempsDir.empty()) {
539           saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc");
540         }
541 
542         auto &ImportList = ImportLists[TheModule->getModuleIdentifier()];
543         ProducedBinaries[count] = ProcessThinLTOModule(
544             *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
545             CacheOptions, DisableCodeGen, SaveTempsDir, count);
546       }, count);
547       count++;
548     }
549   }
550 
551   // If statistics were requested, print them out now.
552   if (llvm::AreStatisticsEnabled())
553     llvm::PrintStatistics();
554 }
555