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