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