1 //===-LTOBackend.cpp - LLVM Link Time Optimizer Backend -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the "backend" phase of LTO, i.e. it performs
10 // optimization and code generation on a loaded module. It is generally used
11 // internally by the LTO class but can also be used independently, for example
12 // to implement a standalone ThinLTO backend.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/LTO/LTOBackend.h"
17 #include "llvm/Analysis/AliasAnalysis.h"
18 #include "llvm/Analysis/CGSCCPassManager.h"
19 #include "llvm/Analysis/TargetLibraryInfo.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/Bitcode/BitcodeReader.h"
22 #include "llvm/Bitcode/BitcodeWriter.h"
23 #include "llvm/IR/LegacyPassManager.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/IR/RemarkStreamer.h"
26 #include "llvm/IR/Verifier.h"
27 #include "llvm/LTO/LTO.h"
28 #include "llvm/MC/SubtargetFeature.h"
29 #include "llvm/Object/ModuleSymbolTable.h"
30 #include "llvm/Passes/PassBuilder.h"
31 #include "llvm/Support/Error.h"
32 #include "llvm/Support/FileSystem.h"
33 #include "llvm/Support/MemoryBuffer.h"
34 #include "llvm/Support/Path.h"
35 #include "llvm/Support/Program.h"
36 #include "llvm/Support/TargetRegistry.h"
37 #include "llvm/Support/ThreadPool.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include "llvm/Target/TargetMachine.h"
40 #include "llvm/Transforms/IPO.h"
41 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
42 #include "llvm/Transforms/Scalar/LoopPassManager.h"
43 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
44 #include "llvm/Transforms/Utils/SplitModule.h"
45 
46 using namespace llvm;
47 using namespace lto;
48 
49 LLVM_ATTRIBUTE_NORETURN static void reportOpenError(StringRef Path, Twine Msg) {
50   errs() << "failed to open " << Path << ": " << Msg << '\n';
51   errs().flush();
52   exit(1);
53 }
54 
55 Error Config::addSaveTemps(std::string OutputFileName,
56                            bool UseInputModulePath) {
57   ShouldDiscardValueNames = false;
58 
59   std::error_code EC;
60   ResolutionFile = llvm::make_unique<raw_fd_ostream>(
61       OutputFileName + "resolution.txt", EC, sys::fs::OpenFlags::F_Text);
62   if (EC)
63     return errorCodeToError(EC);
64 
65   auto setHook = [&](std::string PathSuffix, ModuleHookFn &Hook) {
66     // Keep track of the hook provided by the linker, which also needs to run.
67     ModuleHookFn LinkerHook = Hook;
68     Hook = [=](unsigned Task, const Module &M) {
69       // If the linker's hook returned false, we need to pass that result
70       // through.
71       if (LinkerHook && !LinkerHook(Task, M))
72         return false;
73 
74       std::string PathPrefix;
75       // If this is the combined module (not a ThinLTO backend compile) or the
76       // user hasn't requested using the input module's path, emit to a file
77       // named from the provided OutputFileName with the Task ID appended.
78       if (M.getModuleIdentifier() == "ld-temp.o" || !UseInputModulePath) {
79         PathPrefix = OutputFileName;
80         if (Task != (unsigned)-1)
81           PathPrefix += utostr(Task) + ".";
82       } else
83         PathPrefix = M.getModuleIdentifier() + ".";
84       std::string Path = PathPrefix + PathSuffix + ".bc";
85       std::error_code EC;
86       raw_fd_ostream OS(Path, EC, sys::fs::OpenFlags::F_None);
87       // Because -save-temps is a debugging feature, we report the error
88       // directly and exit.
89       if (EC)
90         reportOpenError(Path, EC.message());
91       WriteBitcodeToFile(M, OS, /*ShouldPreserveUseListOrder=*/false);
92       return true;
93     };
94   };
95 
96   setHook("0.preopt", PreOptModuleHook);
97   setHook("1.promote", PostPromoteModuleHook);
98   setHook("2.internalize", PostInternalizeModuleHook);
99   setHook("3.import", PostImportModuleHook);
100   setHook("4.opt", PostOptModuleHook);
101   setHook("5.precodegen", PreCodeGenModuleHook);
102 
103   CombinedIndexHook = [=](const ModuleSummaryIndex &Index) {
104     std::string Path = OutputFileName + "index.bc";
105     std::error_code EC;
106     raw_fd_ostream OS(Path, EC, sys::fs::OpenFlags::F_None);
107     // Because -save-temps is a debugging feature, we report the error
108     // directly and exit.
109     if (EC)
110       reportOpenError(Path, EC.message());
111     WriteIndexToFile(Index, OS);
112 
113     Path = OutputFileName + "index.dot";
114     raw_fd_ostream OSDot(Path, EC, sys::fs::OpenFlags::F_None);
115     if (EC)
116       reportOpenError(Path, EC.message());
117     Index.exportToDot(OSDot);
118     return true;
119   };
120 
121   return Error::success();
122 }
123 
124 namespace {
125 
126 std::unique_ptr<TargetMachine>
127 createTargetMachine(Config &Conf, const Target *TheTarget, Module &M) {
128   StringRef TheTriple = M.getTargetTriple();
129   SubtargetFeatures Features;
130   Features.getDefaultSubtargetFeatures(Triple(TheTriple));
131   for (const std::string &A : Conf.MAttrs)
132     Features.AddFeature(A);
133 
134   Reloc::Model RelocModel;
135   if (Conf.RelocModel)
136     RelocModel = *Conf.RelocModel;
137   else
138     RelocModel =
139         M.getPICLevel() == PICLevel::NotPIC ? Reloc::Static : Reloc::PIC_;
140 
141   Optional<CodeModel::Model> CodeModel;
142   if (Conf.CodeModel)
143     CodeModel = *Conf.CodeModel;
144   else
145     CodeModel = M.getCodeModel();
146 
147   return std::unique_ptr<TargetMachine>(TheTarget->createTargetMachine(
148       TheTriple, Conf.CPU, Features.getString(), Conf.Options, RelocModel,
149       CodeModel, Conf.CGOptLevel));
150 }
151 
152 static void runNewPMPasses(Config &Conf, Module &Mod, TargetMachine *TM,
153                            unsigned OptLevel, bool IsThinLTO,
154                            ModuleSummaryIndex *ExportSummary,
155                            const ModuleSummaryIndex *ImportSummary) {
156   Optional<PGOOptions> PGOOpt;
157   if (!Conf.SampleProfile.empty())
158     PGOOpt = PGOOptions(Conf.SampleProfile, "", Conf.ProfileRemapping,
159                         PGOOptions::SampleUse, PGOOptions::NoCSAction, true);
160   else if (Conf.RunCSIRInstr) {
161     PGOOpt = PGOOptions("", Conf.CSIRProfile, Conf.ProfileRemapping,
162                         PGOOptions::IRUse, PGOOptions::CSIRInstr);
163   } else if (!Conf.CSIRProfile.empty()) {
164     PGOOpt = PGOOptions(Conf.CSIRProfile, "", Conf.ProfileRemapping,
165                         PGOOptions::IRUse, PGOOptions::CSIRUse);
166   }
167 
168   PassBuilder PB(TM, PipelineTuningOptions(), PGOOpt);
169   AAManager AA;
170 
171   // Parse a custom AA pipeline if asked to.
172   if (auto Err = PB.parseAAPipeline(AA, "default"))
173     report_fatal_error("Error parsing default AA pipeline");
174 
175   LoopAnalysisManager LAM(Conf.DebugPassManager);
176   FunctionAnalysisManager FAM(Conf.DebugPassManager);
177   CGSCCAnalysisManager CGAM(Conf.DebugPassManager);
178   ModuleAnalysisManager MAM(Conf.DebugPassManager);
179 
180   // Register the AA manager first so that our version is the one used.
181   FAM.registerPass([&] { return std::move(AA); });
182 
183   // Register all the basic analyses with the managers.
184   PB.registerModuleAnalyses(MAM);
185   PB.registerCGSCCAnalyses(CGAM);
186   PB.registerFunctionAnalyses(FAM);
187   PB.registerLoopAnalyses(LAM);
188   PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
189 
190   ModulePassManager MPM(Conf.DebugPassManager);
191   // FIXME (davide): verify the input.
192 
193   PassBuilder::OptimizationLevel OL;
194 
195   switch (OptLevel) {
196   default:
197     llvm_unreachable("Invalid optimization level");
198   case 0:
199     OL = PassBuilder::O0;
200     break;
201   case 1:
202     OL = PassBuilder::O1;
203     break;
204   case 2:
205     OL = PassBuilder::O2;
206     break;
207   case 3:
208     OL = PassBuilder::O3;
209     break;
210   }
211 
212   if (IsThinLTO)
213     MPM = PB.buildThinLTODefaultPipeline(OL, Conf.DebugPassManager,
214                                          ImportSummary);
215   else
216     MPM = PB.buildLTODefaultPipeline(OL, Conf.DebugPassManager, ExportSummary);
217   MPM.run(Mod, MAM);
218 
219   // FIXME (davide): verify the output.
220 }
221 
222 static void runNewPMCustomPasses(Module &Mod, TargetMachine *TM,
223                                  std::string PipelineDesc,
224                                  std::string AAPipelineDesc,
225                                  bool DisableVerify) {
226   PassBuilder PB(TM);
227   AAManager AA;
228 
229   // Parse a custom AA pipeline if asked to.
230   if (!AAPipelineDesc.empty())
231     if (auto Err = PB.parseAAPipeline(AA, AAPipelineDesc))
232       report_fatal_error("unable to parse AA pipeline description '" +
233                          AAPipelineDesc + "': " + toString(std::move(Err)));
234 
235   LoopAnalysisManager LAM;
236   FunctionAnalysisManager FAM;
237   CGSCCAnalysisManager CGAM;
238   ModuleAnalysisManager MAM;
239 
240   // Register the AA manager first so that our version is the one used.
241   FAM.registerPass([&] { return std::move(AA); });
242 
243   // Register all the basic analyses with the managers.
244   PB.registerModuleAnalyses(MAM);
245   PB.registerCGSCCAnalyses(CGAM);
246   PB.registerFunctionAnalyses(FAM);
247   PB.registerLoopAnalyses(LAM);
248   PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
249 
250   ModulePassManager MPM;
251 
252   // Always verify the input.
253   MPM.addPass(VerifierPass());
254 
255   // Now, add all the passes we've been requested to.
256   if (auto Err = PB.parsePassPipeline(MPM, PipelineDesc))
257     report_fatal_error("unable to parse pass pipeline description '" +
258                        PipelineDesc + "': " + toString(std::move(Err)));
259 
260   if (!DisableVerify)
261     MPM.addPass(VerifierPass());
262   MPM.run(Mod, MAM);
263 }
264 
265 static void runOldPMPasses(Config &Conf, Module &Mod, TargetMachine *TM,
266                            bool IsThinLTO, ModuleSummaryIndex *ExportSummary,
267                            const ModuleSummaryIndex *ImportSummary) {
268   legacy::PassManager passes;
269   passes.add(createTargetTransformInfoWrapperPass(TM->getTargetIRAnalysis()));
270 
271   PassManagerBuilder PMB;
272   PMB.LibraryInfo = new TargetLibraryInfoImpl(Triple(TM->getTargetTriple()));
273   PMB.Inliner = createFunctionInliningPass();
274   PMB.ExportSummary = ExportSummary;
275   PMB.ImportSummary = ImportSummary;
276   // Unconditionally verify input since it is not verified before this
277   // point and has unknown origin.
278   PMB.VerifyInput = true;
279   PMB.VerifyOutput = !Conf.DisableVerify;
280   PMB.LoopVectorize = true;
281   PMB.SLPVectorize = true;
282   PMB.OptLevel = Conf.OptLevel;
283   PMB.PGOSampleUse = Conf.SampleProfile;
284   PMB.EnablePGOCSInstrGen = Conf.RunCSIRInstr;
285   if (!Conf.RunCSIRInstr && !Conf.CSIRProfile.empty()) {
286     PMB.EnablePGOCSInstrUse = true;
287     PMB.PGOInstrUse = Conf.CSIRProfile;
288   }
289   if (IsThinLTO)
290     PMB.populateThinLTOPassManager(passes);
291   else
292     PMB.populateLTOPassManager(passes);
293   passes.run(Mod);
294 }
295 
296 bool opt(Config &Conf, TargetMachine *TM, unsigned Task, Module &Mod,
297          bool IsThinLTO, ModuleSummaryIndex *ExportSummary,
298          const ModuleSummaryIndex *ImportSummary) {
299   // FIXME: Plumb the combined index into the new pass manager.
300   if (!Conf.OptPipeline.empty())
301     runNewPMCustomPasses(Mod, TM, Conf.OptPipeline, Conf.AAPipeline,
302                          Conf.DisableVerify);
303   else if (Conf.UseNewPM)
304     runNewPMPasses(Conf, Mod, TM, Conf.OptLevel, IsThinLTO, ExportSummary,
305                    ImportSummary);
306   else
307     runOldPMPasses(Conf, Mod, TM, IsThinLTO, ExportSummary, ImportSummary);
308   return !Conf.PostOptModuleHook || Conf.PostOptModuleHook(Task, Mod);
309 }
310 
311 void codegen(Config &Conf, TargetMachine *TM, AddStreamFn AddStream,
312              unsigned Task, Module &Mod) {
313   if (Conf.PreCodeGenModuleHook && !Conf.PreCodeGenModuleHook(Task, Mod))
314     return;
315 
316   std::unique_ptr<ToolOutputFile> DwoOut;
317   SmallString<1024> DwoFile(Conf.DwoPath);
318   if (!Conf.DwoDir.empty()) {
319     std::error_code EC;
320     if (auto EC = llvm::sys::fs::create_directories(Conf.DwoDir))
321       report_fatal_error("Failed to create directory " + Conf.DwoDir + ": " +
322                          EC.message());
323 
324     DwoFile = Conf.DwoDir;
325     sys::path::append(DwoFile, std::to_string(Task) + ".dwo");
326   }
327 
328   if (!DwoFile.empty()) {
329     std::error_code EC;
330     TM->Options.MCOptions.SplitDwarfFile = DwoFile.str().str();
331     DwoOut = llvm::make_unique<ToolOutputFile>(DwoFile, EC, sys::fs::F_None);
332     if (EC)
333       report_fatal_error("Failed to open " + DwoFile + ": " + EC.message());
334   }
335 
336   auto Stream = AddStream(Task);
337   legacy::PassManager CodeGenPasses;
338   if (TM->addPassesToEmitFile(CodeGenPasses, *Stream->OS,
339                               DwoOut ? &DwoOut->os() : nullptr,
340                               Conf.CGFileType))
341     report_fatal_error("Failed to setup codegen");
342   CodeGenPasses.run(Mod);
343 
344   if (DwoOut)
345     DwoOut->keep();
346 }
347 
348 void splitCodeGen(Config &C, TargetMachine *TM, AddStreamFn AddStream,
349                   unsigned ParallelCodeGenParallelismLevel,
350                   std::unique_ptr<Module> Mod) {
351   ThreadPool CodegenThreadPool(ParallelCodeGenParallelismLevel);
352   unsigned ThreadCount = 0;
353   const Target *T = &TM->getTarget();
354 
355   SplitModule(
356       std::move(Mod), ParallelCodeGenParallelismLevel,
357       [&](std::unique_ptr<Module> MPart) {
358         // We want to clone the module in a new context to multi-thread the
359         // codegen. We do it by serializing partition modules to bitcode
360         // (while still on the main thread, in order to avoid data races) and
361         // spinning up new threads which deserialize the partitions into
362         // separate contexts.
363         // FIXME: Provide a more direct way to do this in LLVM.
364         SmallString<0> BC;
365         raw_svector_ostream BCOS(BC);
366         WriteBitcodeToFile(*MPart, BCOS);
367 
368         // Enqueue the task
369         CodegenThreadPool.async(
370             [&](const SmallString<0> &BC, unsigned ThreadId) {
371               LTOLLVMContext Ctx(C);
372               Expected<std::unique_ptr<Module>> MOrErr = parseBitcodeFile(
373                   MemoryBufferRef(StringRef(BC.data(), BC.size()), "ld-temp.o"),
374                   Ctx);
375               if (!MOrErr)
376                 report_fatal_error("Failed to read bitcode");
377               std::unique_ptr<Module> MPartInCtx = std::move(MOrErr.get());
378 
379               std::unique_ptr<TargetMachine> TM =
380                   createTargetMachine(C, T, *MPartInCtx);
381 
382               codegen(C, TM.get(), AddStream, ThreadId, *MPartInCtx);
383             },
384             // Pass BC using std::move to ensure that it get moved rather than
385             // copied into the thread's context.
386             std::move(BC), ThreadCount++);
387       },
388       false);
389 
390   // Because the inner lambda (which runs in a worker thread) captures our local
391   // variables, we need to wait for the worker threads to terminate before we
392   // can leave the function scope.
393   CodegenThreadPool.wait();
394 }
395 
396 Expected<const Target *> initAndLookupTarget(Config &C, Module &Mod) {
397   if (!C.OverrideTriple.empty())
398     Mod.setTargetTriple(C.OverrideTriple);
399   else if (Mod.getTargetTriple().empty())
400     Mod.setTargetTriple(C.DefaultTriple);
401 
402   std::string Msg;
403   const Target *T = TargetRegistry::lookupTarget(Mod.getTargetTriple(), Msg);
404   if (!T)
405     return make_error<StringError>(Msg, inconvertibleErrorCode());
406   return T;
407 }
408 
409 }
410 
411 static Error
412 finalizeOptimizationRemarks(std::unique_ptr<ToolOutputFile> DiagOutputFile) {
413   // Make sure we flush the diagnostic remarks file in case the linker doesn't
414   // call the global destructors before exiting.
415   if (!DiagOutputFile)
416     return Error::success();
417   DiagOutputFile->keep();
418   DiagOutputFile->os().flush();
419   return Error::success();
420 }
421 
422 Error lto::backend(Config &C, AddStreamFn AddStream,
423                    unsigned ParallelCodeGenParallelismLevel,
424                    std::unique_ptr<Module> Mod,
425                    ModuleSummaryIndex &CombinedIndex) {
426   Expected<const Target *> TOrErr = initAndLookupTarget(C, *Mod);
427   if (!TOrErr)
428     return TOrErr.takeError();
429 
430   std::unique_ptr<TargetMachine> TM = createTargetMachine(C, *TOrErr, *Mod);
431 
432   // Setup optimization remarks.
433   auto DiagFileOrErr =
434       lto::setupOptimizationRemarks(Mod->getContext(), C.RemarksFilename,
435                                     C.RemarksPasses, C.RemarksWithHotness);
436   if (!DiagFileOrErr)
437     return DiagFileOrErr.takeError();
438   auto DiagnosticOutputFile = std::move(*DiagFileOrErr);
439 
440   if (!C.CodeGenOnly) {
441     if (!opt(C, TM.get(), 0, *Mod, /*IsThinLTO=*/false,
442              /*ExportSummary=*/&CombinedIndex, /*ImportSummary=*/nullptr))
443       return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
444   }
445 
446   if (ParallelCodeGenParallelismLevel == 1) {
447     codegen(C, TM.get(), AddStream, 0, *Mod);
448   } else {
449     splitCodeGen(C, TM.get(), AddStream, ParallelCodeGenParallelismLevel,
450                  std::move(Mod));
451   }
452   return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
453 }
454 
455 static void dropDeadSymbols(Module &Mod, const GVSummaryMapTy &DefinedGlobals,
456                             const ModuleSummaryIndex &Index) {
457   std::vector<GlobalValue*> DeadGVs;
458   for (auto &GV : Mod.global_values())
459     if (GlobalValueSummary *GVS = DefinedGlobals.lookup(GV.getGUID()))
460       if (!Index.isGlobalValueLive(GVS)) {
461         DeadGVs.push_back(&GV);
462         convertToDeclaration(GV);
463       }
464 
465   // Now that all dead bodies have been dropped, delete the actual objects
466   // themselves when possible.
467   for (GlobalValue *GV : DeadGVs) {
468     GV->removeDeadConstantUsers();
469     // Might reference something defined in native object (i.e. dropped a
470     // non-prevailing IR def, but we need to keep the declaration).
471     if (GV->use_empty())
472       GV->eraseFromParent();
473   }
474 }
475 
476 Error lto::thinBackend(Config &Conf, unsigned Task, AddStreamFn AddStream,
477                        Module &Mod, const ModuleSummaryIndex &CombinedIndex,
478                        const FunctionImporter::ImportMapTy &ImportList,
479                        const GVSummaryMapTy &DefinedGlobals,
480                        MapVector<StringRef, BitcodeModule> &ModuleMap) {
481   Expected<const Target *> TOrErr = initAndLookupTarget(Conf, Mod);
482   if (!TOrErr)
483     return TOrErr.takeError();
484 
485   std::unique_ptr<TargetMachine> TM = createTargetMachine(Conf, *TOrErr, Mod);
486 
487   // Setup optimization remarks.
488   auto DiagFileOrErr = lto::setupOptimizationRemarks(
489       Mod.getContext(), Conf.RemarksFilename, Conf.RemarksPasses,
490       Conf.RemarksWithHotness, Task);
491   if (!DiagFileOrErr)
492     return DiagFileOrErr.takeError();
493   auto DiagnosticOutputFile = std::move(*DiagFileOrErr);
494 
495   if (Conf.CodeGenOnly) {
496     codegen(Conf, TM.get(), AddStream, Task, Mod);
497     return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
498   }
499 
500   if (Conf.PreOptModuleHook && !Conf.PreOptModuleHook(Task, Mod))
501     return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
502 
503   renameModuleForThinLTO(Mod, CombinedIndex);
504 
505   dropDeadSymbols(Mod, DefinedGlobals, CombinedIndex);
506 
507   thinLTOResolvePrevailingInModule(Mod, DefinedGlobals);
508 
509   if (Conf.PostPromoteModuleHook && !Conf.PostPromoteModuleHook(Task, Mod))
510     return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
511 
512   if (!DefinedGlobals.empty())
513     thinLTOInternalizeModule(Mod, DefinedGlobals);
514 
515   if (Conf.PostInternalizeModuleHook &&
516       !Conf.PostInternalizeModuleHook(Task, Mod))
517     return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
518 
519   auto ModuleLoader = [&](StringRef Identifier) {
520     assert(Mod.getContext().isODRUniquingDebugTypes() &&
521            "ODR Type uniquing should be enabled on the context");
522     auto I = ModuleMap.find(Identifier);
523     assert(I != ModuleMap.end());
524     return I->second.getLazyModule(Mod.getContext(),
525                                    /*ShouldLazyLoadMetadata=*/true,
526                                    /*IsImporting*/ true);
527   };
528 
529   FunctionImporter Importer(CombinedIndex, ModuleLoader);
530   if (Error Err = Importer.importFunctions(Mod, ImportList).takeError())
531     return Err;
532 
533   if (Conf.PostImportModuleHook && !Conf.PostImportModuleHook(Task, Mod))
534     return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
535 
536   if (!opt(Conf, TM.get(), Task, Mod, /*IsThinLTO=*/true,
537            /*ExportSummary=*/nullptr, /*ImportSummary=*/&CombinedIndex))
538     return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
539 
540   codegen(Conf, TM.get(), AddStream, Task, Mod);
541   return finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
542 }
543