tools/lto/lto.cpp

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