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