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