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