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