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/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, true, false);
  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 }