tools/lto/lto.cpp

   1 //===-lto.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 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/Module.h"
  16 #include "llvm/PassManager.h"
  17 #include "llvm/Linker.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/ModuleProvider.h"
  21 #include "llvm/Bitcode/ReaderWriter.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/FileUtilities.h"
  24 #include "llvm/Support/SystemUtils.h"
  25 #include "llvm/Support/Mangler.h"
  26 #include "llvm/Support/MemoryBuffer.h"
  27 #include "llvm/System/Program.h"
  28 #include "llvm/System/Signals.h"
  29 #include "llvm/Analysis/Passes.h"
  30 #include "llvm/Analysis/LoopPass.h"
  31 #include "llvm/Analysis/Verifier.h"
  32 #include "llvm/CodeGen/FileWriters.h"
  33 #include "llvm/Target/SubtargetFeature.h"
  34 #include "llvm/Target/TargetOptions.h"
  35 #include "llvm/Target/TargetData.h"
  36 #include "llvm/Target/TargetMachine.h"
  37 #include "llvm/Target/TargetMachineRegistry.h"
  38 #include "llvm/Target/TargetAsmInfo.h"
  39 #include "llvm/Transforms/IPO.h"
  40 #include "llvm/Transforms/Scalar.h"
  41 #include "llvm/Analysis/LoadValueNumbering.h"
  42 #include "llvm/Support/MathExtras.h"
  43 #include "llvm/LinkTimeOptimizer.h"
  44 #include <fstream>
  45 #include <ostream>
  46 using namespace llvm;
  47
  48 extern "C"
  49 llvm::LinkTimeOptimizer *createLLVMOptimizer(unsigned VERSION)
  50 {
  51   // Linker records LLVM_LTO_VERSION based on llvm optimizer available
  52   // during linker build. Match linker's recorded LTO VERSION number
  53   // with installed llvm optimizer version. If these numbers do not match
  54   // then linker may not be able to use llvm optimizer dynamically.
  55   if (VERSION != LLVM_LTO_VERSION)
  56     return NULL;
  57
  58   llvm::LTO *l = new llvm::LTO();
  59   return l;
  60 }
  61
  62 /// If symbol is not used then make it internal and let optimizer takes
  63 /// care of it.
  64 void LLVMSymbol::mayBeNotUsed() {
  65   gv->setLinkage(GlobalValue::InternalLinkage);
  66 }
  67
  68 // Map LLVM LinkageType to LTO LinakgeType
  69 static LTOLinkageTypes
  70 getLTOLinkageType(GlobalValue *v)
  71 {
  72   LTOLinkageTypes lt;
  73   if (v->hasExternalLinkage())
  74     lt = LTOExternalLinkage;
  75   else if (v->hasLinkOnceLinkage())
  76     lt = LTOLinkOnceLinkage;
  77   else if (v->hasWeakLinkage())
  78     lt = LTOWeakLinkage;
  79   else
  80     // Otherwise it is internal linkage for link time optimizer
  81     lt = LTOInternalLinkage;
  82   return lt;
  83 }
  84
  85 // MAP LLVM VisibilityType to LTO VisibilityType
  86 static LTOVisibilityTypes
  87 getLTOVisibilityType(GlobalValue *v)
  88 {
  89   LTOVisibilityTypes vis;
  90   if (v->hasHiddenVisibility())
  91     vis = LTOHiddenVisibility;
  92   else if (v->hasProtectedVisibility())
  93     vis = LTOProtectedVisibility;
  94   else
  95     vis = LTODefaultVisibility;
  96   return vis;
  97 }
  98
  99 // Find exeternal symbols referenced by VALUE. This is a recursive function.
 100 static void
 101 findExternalRefs(Value *value, std::set<std::string> &references,
 102                  Mangler &mangler) {
 103
 104   if (GlobalValue *gv = dyn_cast<GlobalValue>(value)) {
 105     LTOLinkageTypes lt = getLTOLinkageType(gv);
 106     if (lt != LTOInternalLinkage && strncmp (gv->getName().c_str(), "llvm.", 5))
 107       references.insert(mangler.getValueName(gv));
 108   }
 109
 110   // GlobalValue, even with InternalLinkage type, may have operands with
 111   // ExternalLinkage type. Do not ignore these operands.
 112   if (Constant *c = dyn_cast<Constant>(value))
 113     // Handle ConstantExpr, ConstantStruct, ConstantArry etc..
 114     for (unsigned i = 0, e = c->getNumOperands(); i != e; ++i)
 115       findExternalRefs(c->getOperand(i), references, mangler);
 116 }
 117
 118 /// If Module with InputFilename is available then remove it from allModules
 119 /// and call delete on it.
 120 void
 121 LTO::removeModule (const std::string &InputFilename)
 122 {
 123   NameToModuleMap::iterator pos = allModules.find(InputFilename.c_str());
 124   if (pos == allModules.end())
 125     return;
 126
 127   Module *m = pos->second;
 128   allModules.erase(pos);
 129   delete m;
 130 }
 131
 132 /// InputFilename is a LLVM bitcode file. If Module with InputFilename is
 133 /// available then return it. Otherwise parseInputFilename.
 134 Module *
 135 LTO::getModule(const std::string &InputFilename)
 136 {
 137   Module *m = NULL;
 138
 139   NameToModuleMap::iterator pos = allModules.find(InputFilename.c_str());
 140   if (pos != allModules.end())
 141     m = allModules[InputFilename.c_str()];
 142   else {
 143     if (MemoryBuffer *Buffer
 144         = MemoryBuffer::getFile(&InputFilename[0], InputFilename.size())) {
 145       m = ParseBitcodeFile(Buffer);
 146       delete Buffer;
 147     }
 148     allModules[InputFilename.c_str()] = m;
 149   }
 150   return m;
 151 }
 152
 153 /// InputFilename is a LLVM bitcode file. Reade this bitcode file and
 154 /// set corresponding target triplet string.
 155 void
 156 LTO::getTargetTriple(const std::string &InputFilename,
 157                      std::string &targetTriple)
 158 {
 159   Module *m = getModule(InputFilename);
 160   if (m)
 161     targetTriple = m->getTargetTriple();
 162 }
 163
 164 /// InputFilename is a LLVM bitcode file. Read it using bitcode reader.
 165 /// Collect global functions and symbol names in symbols vector.
 166 /// Collect external references in references vector.
 167 /// Return LTO_READ_SUCCESS if there is no error.
 168 enum LTOStatus
 169 LTO::readLLVMObjectFile(const std::string &InputFilename,
 170                         NameToSymbolMap &symbols,
 171                         std::set<std::string> &references)
 172 {
 173   Module *m = getModule(InputFilename);
 174   if (!m)
 175     return LTO_READ_FAILURE;
 176
 177   // Collect Target info
 178   getTarget(m);
 179
 180   if (!Target)
 181     return LTO_READ_FAILURE;
 182
 183   // Use mangler to add GlobalPrefix to names to match linker names.
 184   // FIXME : Instead of hard coding "-" use GlobalPrefix.
 185   Mangler mangler(*m, Target->getTargetAsmInfo()->getGlobalPrefix());
 186   modules.push_back(m);
 187
 188   for (Module::iterator f = m->begin(), e = m->end(); f != e; ++f) {
 189     LTOLinkageTypes lt = getLTOLinkageType(f);
 190     LTOVisibilityTypes vis = getLTOVisibilityType(f);
 191     if (!f->isDeclaration() && lt != LTOInternalLinkage
 192         && strncmp (f->getName().c_str(), "llvm.", 5)) {
 193       int alignment = ( 16 > f->getAlignment() ? 16 : f->getAlignment());
 194       LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, f, f->getName(),
 195                                              mangler.getValueName(f),
 196                                              Log2_32(alignment));
 197       symbols[newSymbol->getMangledName()] = newSymbol;
 198       allSymbols[newSymbol->getMangledName()] = newSymbol;
 199     }
 200
 201     // Collect external symbols referenced by this function.
 202     for (Function::iterator b = f->begin(), fe = f->end(); b != fe; ++b)
 203       for (BasicBlock::iterator i = b->begin(), be = b->end();
 204            i != be; ++i) {
 205         for (unsigned count = 0, total = i->getNumOperands();
 206              count != total; ++count)
 207           findExternalRefs(i->getOperand(count), references, mangler);
 208       }
 209   }
 210
 211   for (Module::global_iterator v = m->global_begin(), e = m->global_end();
 212        v !=  e; ++v) {
 213     LTOLinkageTypes lt = getLTOLinkageType(v);
 214     LTOVisibilityTypes vis = getLTOVisibilityType(v);
 215     if (!v->isDeclaration() && lt != LTOInternalLinkage
 216         && strncmp (v->getName().c_str(), "llvm.", 5)) {
 217       const TargetData *TD = Target->getTargetData();
 218       LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, v, v->getName(),
 219                                              mangler.getValueName(v),
 220                                              TD->getPreferredAlignmentLog(v));
 221       symbols[newSymbol->getMangledName()] = newSymbol;
 222       allSymbols[newSymbol->getMangledName()] = newSymbol;
 223
 224       for (unsigned count = 0, total = v->getNumOperands();
 225            count != total; ++count)
 226         findExternalRefs(v->getOperand(count), references, mangler);
 227
 228     }
 229   }
 230
 231   return LTO_READ_SUCCESS;
 232 }
 233
 234 /// Get TargetMachine.
 235 /// Use module M to find appropriate Target.
 236 void
 237 LTO::getTarget (Module *M) {
 238
 239   if (Target)
 240     return;
 241
 242   std::string Err;
 243   const TargetMachineRegistry::entry* March =
 244     TargetMachineRegistry::getClosestStaticTargetForModule(*M, Err);
 245
 246   if (March == 0)
 247     return;
 248
 249   // Create target
 250   std::string Features;
 251   Target = March->CtorFn(*M, Features);
 252 }
 253
 254 /// Optimize module M using various IPO passes. Use exportList to
 255 /// internalize selected symbols. Target platform is selected
 256 /// based on information available to module M. No new target
 257 /// features are selected.
 258 enum LTOStatus
 259 LTO::optimize(Module *M, std::ostream &Out,
 260               std::vector<const char *> &exportList)
 261 {
 262   // Instantiate the pass manager to organize the passes.
 263   PassManager Passes;
 264
 265   // Collect Target info
 266   getTarget(M);
 267
 268   if (!Target)
 269     return LTO_NO_TARGET;
 270
 271   // If target supports exception handling then enable it now.
 272   if (Target->getTargetAsmInfo()->doesSupportExceptionHandling())
 273     ExceptionHandling = true;
 274
 275   // Start off with a verification pass.
 276   Passes.add(createVerifierPass());
 277
 278   // Add an appropriate TargetData instance for this module...
 279   Passes.add(new TargetData(*Target->getTargetData()));
 280
 281   // Internalize symbols if export list is nonemty
 282   if (!exportList.empty())
 283     Passes.add(createInternalizePass(exportList));
 284
 285   // Now that we internalized some globals, see if we can hack on them!
 286   Passes.add(createGlobalOptimizerPass());
 287
 288   // Linking modules together can lead to duplicated global constants, only
 289   // keep one copy of each constant...
 290   Passes.add(createConstantMergePass());
 291
 292   // If the -s command line option was specified, strip the symbols out of the
 293   // resulting program to make it smaller.  -s is a GLD option that we are
 294   // supporting.
 295   Passes.add(createStripSymbolsPass());
 296
 297   // Propagate constants at call sites into the functions they call.
 298   Passes.add(createIPConstantPropagationPass());
 299
 300   // Remove unused arguments from functions...
 301   Passes.add(createDeadArgEliminationPass());
 302
 303   Passes.add(createFunctionInliningPass()); // Inline small functions
 304
 305   Passes.add(createPruneEHPass());            // Remove dead EH info
 306
 307   Passes.add(createGlobalDCEPass());          // Remove dead functions
 308
 309   // If we didn't decide to inline a function, check to see if we can
 310   // transform it to pass arguments by value instead of by reference.
 311   Passes.add(createArgumentPromotionPass());
 312
 313   // The IPO passes may leave cruft around.  Clean up after them.
 314   Passes.add(createInstructionCombiningPass());
 315
 316   Passes.add(createScalarReplAggregatesPass()); // Break up allocas
 317
 318   // Run a few AA driven optimizations here and now, to cleanup the code.
 319   Passes.add(createGlobalsModRefPass());      // IP alias analysis
 320
 321   Passes.add(createLICMPass());               // Hoist loop invariants
 322   Passes.add(createLoadValueNumberingPass()); // GVN for load instrs
 323   Passes.add(createGCSEPass());               // Remove common subexprs
 324   Passes.add(createDeadStoreEliminationPass()); // Nuke dead stores
 325
 326   // Cleanup and simplify the code after the scalar optimizations.
 327   Passes.add(createInstructionCombiningPass());
 328
 329   // Delete basic blocks, which optimization passes may have killed...
 330   Passes.add(createCFGSimplificationPass());
 331
 332   // Now that we have optimized the program, discard unreachable functions...
 333   Passes.add(createGlobalDCEPass());
 334
 335   // Make sure everything is still good.
 336   Passes.add(createVerifierPass());
 337
 338   FunctionPassManager *CodeGenPasses =
 339     new FunctionPassManager(new ExistingModuleProvider(M));
 340
 341   CodeGenPasses->add(new TargetData(*Target->getTargetData()));
 342
 343   MachineCodeEmitter *MCE = 0;
 344
 345   switch (Target->addPassesToEmitFile(*CodeGenPasses, Out,
 346                                       TargetMachine::AssemblyFile, true)) {
 347   default:
 348   case FileModel::Error:
 349     return LTO_WRITE_FAILURE;
 350   case FileModel::AsmFile:
 351     break;
 352   case FileModel::MachOFile:
 353     MCE = AddMachOWriter(*CodeGenPasses, Out, *Target);
 354     break;
 355   case FileModel::ElfFile:
 356     MCE = AddELFWriter(*CodeGenPasses, Out, *Target);
 357     break;
 358   }
 359
 360   if (Target->addPassesToEmitFileFinish(*CodeGenPasses, MCE, true))
 361     return LTO_WRITE_FAILURE;
 362
 363   // Run our queue of passes all at once now, efficiently.
 364   Passes.run(*M);
 365
 366   // Run the code generator, if present.
 367   CodeGenPasses->doInitialization();
 368   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
 369     if (!I->isDeclaration())
 370       CodeGenPasses->run(*I);
 371   }
 372   CodeGenPasses->doFinalization();
 373
 374   return LTO_OPT_SUCCESS;
 375 }
 376
 377 ///Link all modules together and optimize them using IPO. Generate
 378 /// native object file using OutputFilename
 379 /// Return appropriate LTOStatus.
 380 enum LTOStatus
 381 LTO::optimizeModules(const std::string &OutputFilename,
 382                      std::vector<const char *> &exportList,
 383                      std::string &targetTriple,
 384                      bool saveTemps, const char *FinalOutputFilename)
 385 {
 386   if (modules.empty())
 387     return LTO_NO_WORK;
 388
 389   std::ios::openmode io_mode =
 390     std::ios::out | std::ios::trunc | std::ios::binary;
 391   std::string *errMsg = NULL;
 392   Module *bigOne = modules[0];
 393   Linker theLinker("LinkTimeOptimizer", bigOne, false);
 394   for (unsigned i = 1, e = modules.size(); i != e; ++i)
 395     if (theLinker.LinkModules(bigOne, modules[i], errMsg))
 396       return LTO_MODULE_MERGE_FAILURE;
 397   //  all modules have been handed off to the linker.
 398   modules.clear();
 399
 400   sys::Path FinalOutputPath(FinalOutputFilename);
 401   FinalOutputPath.eraseSuffix();
 402
 403   switch(CGModel) {
 404   case LTO_CGM_Dynamic:
 405     Target->setRelocationModel(Reloc::PIC_);
 406     break;
 407   case LTO_CGM_DynamicNoPIC:
 408     Target->setRelocationModel(Reloc::DynamicNoPIC);
 409     break;
 410   case LTO_CGM_Static:
 411     Target->setRelocationModel(Reloc::Static);
 412     break;
 413   }
 414
 415   if (saveTemps) {
 416     std::string tempFileName(FinalOutputPath.c_str());
 417     tempFileName += "0.bc";
 418     std::ofstream Out(tempFileName.c_str(), io_mode);
 419     WriteBitcodeToFile(bigOne, Out);
 420   }
 421
 422   // Strip leading underscore because it was added to match names
 423   // seen by linker.
 424   for (unsigned i = 0, e = exportList.size(); i != e; ++i) {
 425     const char *name = exportList[i];
 426     NameToSymbolMap::iterator itr = allSymbols.find(name);
 427     if (itr != allSymbols.end())
 428       exportList[i] = allSymbols[name]->getName();
 429   }
 430
 431
 432   std::string ErrMsg;
 433   sys::Path TempDir = sys::Path::GetTemporaryDirectory(&ErrMsg);
 434   if (TempDir.isEmpty()) {
 435     cerr << "lto: " << ErrMsg << "\n";
 436     return LTO_WRITE_FAILURE;
 437   }
 438   sys::Path tmpAsmFilePath(TempDir);
 439   if (!tmpAsmFilePath.appendComponent("lto")) {
 440     cerr << "lto: " << ErrMsg << "\n";
 441     TempDir.eraseFromDisk(true);
 442     return LTO_WRITE_FAILURE;
 443   }
 444   if (tmpAsmFilePath.createTemporaryFileOnDisk(true, &ErrMsg)) {
 445     cerr << "lto: " << ErrMsg << "\n";
 446     TempDir.eraseFromDisk(true);
 447     return LTO_WRITE_FAILURE;
 448   }
 449   sys::RemoveFileOnSignal(tmpAsmFilePath);
 450
 451   std::ofstream asmFile(tmpAsmFilePath.c_str(), io_mode);
 452   if (!asmFile.is_open() || asmFile.bad()) {
 453     if (tmpAsmFilePath.exists()) {
 454       tmpAsmFilePath.eraseFromDisk();
 455       TempDir.eraseFromDisk(true);
 456     }
 457     return LTO_WRITE_FAILURE;
 458   }
 459
 460   enum LTOStatus status = optimize(bigOne, asmFile, exportList);
 461   asmFile.close();
 462   if (status != LTO_OPT_SUCCESS) {
 463     tmpAsmFilePath.eraseFromDisk();
 464     TempDir.eraseFromDisk(true);
 465     return status;
 466   }
 467
 468   if (saveTemps) {
 469     std::string tempFileName(FinalOutputPath.c_str());
 470     tempFileName += "1.bc";
 471     std::ofstream Out(tempFileName.c_str(), io_mode);
 472     WriteBitcodeToFile(bigOne, Out);
 473   }
 474
 475   targetTriple = bigOne->getTargetTriple();
 476
 477   // Run GCC to assemble and link the program into native code.
 478   //
 479   // Note:
 480   //  We can't just assemble and link the file with the system assembler
 481   //  and linker because we don't know where to put the _start symbol.
 482   //  GCC mysteriously knows how to do it.
 483   const sys::Path gcc = sys::Program::FindProgramByName("gcc");
 484   if (gcc.isEmpty()) {
 485     tmpAsmFilePath.eraseFromDisk();
 486     TempDir.eraseFromDisk(true);
 487     return LTO_ASM_FAILURE;
 488   }
 489
 490   std::vector<const char*> args;
 491   args.push_back(gcc.c_str());
 492   args.push_back("-c");
 493   args.push_back("-x");
 494   args.push_back("assembler");
 495   args.push_back("-o");
 496   args.push_back(OutputFilename.c_str());
 497   args.push_back(tmpAsmFilePath.c_str());
 498   args.push_back(0);
 499
 500   if (sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 1, 0, &ErrMsg)) {
 501     cerr << "lto: " << ErrMsg << "\n";
 502     return LTO_ASM_FAILURE;
 503   }
 504
 505   tmpAsmFilePath.eraseFromDisk();
 506   TempDir.eraseFromDisk(true);
 507
 508   return LTO_OPT_SUCCESS;
 509 }
 510
 511 void LTO::printVersion() {
 512     cl::PrintVersionMessage();
 513 }
 514
 515 /// Unused pure-virtual destructor. Must remain empty.
 516 LinkTimeOptimizer::~LinkTimeOptimizer() {}
 517
 518 /// Destruct LTO. Delete all modules, symbols and target.
 519 LTO::~LTO() {
 520
 521   for (std::vector<Module *>::iterator itr = modules.begin(), e = modules.end();
 522        itr != e; ++itr)
 523     delete *itr;
 524
 525   modules.clear();
 526
 527   for (NameToSymbolMap::iterator itr = allSymbols.begin(), e = allSymbols.end();
 528        itr != e; ++itr)
 529     delete itr->second;
 530
 531   allSymbols.clear();
 532
 533   delete Target;
 534 }