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