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