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/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/Transforms/IPO.h"
  35 #include "llvm/Transforms/Scalar.h"
  36 #include "llvm/Analysis/LoadValueNumbering.h"
  37 #include "llvm/LinkTimeOptimizer.h"
  38 #include <fstream>
  39 #include <iostream>
  40
  41 using namespace llvm;
  42
  43 extern "C"
  44 llvm::LinkTimeOptimizer *createLLVMOptimizer()
  45 {
  46   llvm::LinkTimeOptimizer *l = new llvm::LinkTimeOptimizer();
  47   return l;
  48 }
  49
  50
  51
  52 /// If symbol is not used then make it internal and let optimizer takes
  53 /// care of it.
  54 void LLVMSymbol::mayBeNotUsed() {
  55   gv->setLinkage(GlobalValue::InternalLinkage);
  56 }
  57
  58 // Helper routine
  59 // FIXME : Take advantage of GlobalPrefix from AsmPrinter
  60 static const char *addUnderscore(const char *name) {
  61   size_t namelen = strlen(name);
  62   char *symName = (char*)malloc(namelen+2);
  63   symName[0] = '_';
  64   strcpy(&symName[1], name);
  65   return symName;
  66 }
  67
  68 // Map LLVM LinkageType to LTO LinakgeType
  69 static LTOLinkageTypes
  70 getLTOLinkageType(GlobalValue *v)
  71 {
  72   LTOLinkageTypes lt;
  73   if (v->hasExternalLinkage())
  74     lt = LTOExternalLinkage;
  75   else if (v->hasLinkOnceLinkage())
  76     lt = LTOLinkOnceLinkage;
  77   else if (v->hasWeakLinkage())
  78     lt = LTOWeakLinkage;
  79   else
  80     // Otherwise it is internal linkage for link time optimizer
  81     lt = LTOInternalLinkage;
  82   return lt;
  83 }
  84
  85 // Find exeternal symbols referenced by VALUE. This is a recursive function.
  86 static void
  87 findExternalRefs(Value *value, std::set<const char *> &references) {
  88
  89   if (ConstantExpr *ce = dyn_cast<ConstantExpr>(value))
  90     for (unsigned i = 0, e = ce->getNumOperands(); i != e; ++i)
  91       findExternalRefs(ce->getOperand(i), references);
  92   else if (GlobalValue *gv = dyn_cast<GlobalValue>(value)) {
  93     LTOLinkageTypes lt = getLTOLinkageType(gv);
  94     if (lt != LTOInternalLinkage && strncmp (gv->getName().c_str(), "llvm.", 5))
  95       references.insert(addUnderscore(gv->getName().c_str()));
  96   }
  97 }
  98
  99 /// InputFilename is a LLVM bytecode file. Read it using bytecode reader.
 100 /// Collect global functions and symbol names in symbols vector.
 101 /// Collect external references in references vector.
 102 /// Return LTO_READ_SUCCESS if there is no error.
 103 enum LTOStatus
 104 LinkTimeOptimizer::readLLVMObjectFile(const std::string &InputFilename,
 105                                       NameToSymbolMap &symbols,
 106                                       std::set<const char *> &references)
 107 {
 108   Module *m = ParseBytecodeFile(InputFilename);
 109   if (!m)
 110     return LTO_READ_FAILURE;
 111
 112   modules.push_back(m);
 113
 114   for (Module::iterator f = m->begin(), e = m->end(); f != e; ++f) {
 115
 116     LTOLinkageTypes lt = getLTOLinkageType(f);
 117
 118     if (!f->isExternal() && lt != LTOInternalLinkage
 119         && strncmp (f->getName().c_str(), "llvm.", 5)) {
 120       const char *name = addUnderscore(f->getName().c_str());
 121       LLVMSymbol *newSymbol = new LLVMSymbol(lt, f);
 122       symbols[name] = newSymbol;
 123       allSymbols[name] = newSymbol;
 124     }
 125
 126     // Collect external symbols referenced by this function.
 127     for (Function::iterator b = f->begin(), fe = f->end(); b != fe; ++b)
 128       for (BasicBlock::iterator i = b->begin(), be = b->end();
 129            i != be; ++i)
 130         for (unsigned count = 0, total = i->getNumOperands();
 131              count != total; ++count)
 132           findExternalRefs(i->getOperand(count), references);
 133   }
 134
 135   for (Module::global_iterator v = m->global_begin(), e = m->global_end();
 136        v !=  e; ++v) {
 137     LTOLinkageTypes lt = getLTOLinkageType(v);
 138     if (!v->isExternal() && lt != LTOInternalLinkage
 139         && strncmp (v->getName().c_str(), "llvm.", 5)) {
 140       const char *name = addUnderscore(v->getName().c_str());
 141       LLVMSymbol *newSymbol = new LLVMSymbol(lt,v);
 142       symbols[name] = newSymbol;
 143     }
 144   }
 145
 146   return LTO_READ_SUCCESS;
 147 }
 148
 149 /// Optimize module M using various IPO passes. Use exportList to
 150 /// internalize selected symbols. Target platform is selected
 151 /// based on information available to module M. No new target
 152 /// features are selected.
 153 static enum LTOStatus lto_optimize(Module *M, std::ostream &Out,
 154                                    std::vector<const char *> &exportList)
 155 {
 156   // Instantiate the pass manager to organize the passes.
 157   PassManager Passes;
 158
 159   // Collect Target info
 160   std::string Err;
 161   const TargetMachineRegistry::Entry* March =
 162     TargetMachineRegistry::getClosestStaticTargetForModule(*M, Err);
 163
 164   if (March == 0)
 165     return LTO_NO_TARGET;
 166
 167   // Create target
 168   std::string Features;
 169   std::auto_ptr<TargetMachine> target(March->CtorFn(*M, Features));
 170   if (!target.get())
 171     return LTO_NO_TARGET;
 172
 173   TargetMachine &Target = *target.get();
 174
 175   // Start off with a verification pass.
 176   Passes.add(createVerifierPass());
 177
 178   // Add an appropriate TargetData instance for this module...
 179   Passes.add(new TargetData(*Target.getTargetData()));
 180
 181   // Often if the programmer does not specify proper prototypes for the
 182   // functions they are calling, they end up calling a vararg version of the
 183   // function that does not get a body filled in (the real function has typed
 184   // arguments).  This pass merges the two functions.
 185   Passes.add(createFunctionResolvingPass());
 186
 187   // Internalize symbols if export list is nonemty
 188   if (!exportList.empty())
 189     Passes.add(createInternalizePass(exportList));
 190
 191   // Now that we internalized some globals, see if we can hack on them!
 192   Passes.add(createGlobalOptimizerPass());
 193
 194   // Linking modules together can lead to duplicated global constants, only
 195   // keep one copy of each constant...
 196   Passes.add(createConstantMergePass());
 197
 198   // If the -s command line option was specified, strip the symbols out of the
 199   // resulting program to make it smaller.  -s is a GLD option that we are
 200   // supporting.
 201   Passes.add(createStripSymbolsPass());
 202
 203   // Propagate constants at call sites into the functions they call.
 204   Passes.add(createIPConstantPropagationPass());
 205
 206   // Remove unused arguments from functions...
 207   Passes.add(createDeadArgEliminationPass());
 208
 209   Passes.add(createFunctionInliningPass()); // Inline small functions
 210
 211   Passes.add(createPruneEHPass());            // Remove dead EH info
 212
 213   Passes.add(createGlobalDCEPass());          // Remove dead functions
 214
 215   // If we didn't decide to inline a function, check to see if we can
 216   // transform it to pass arguments by value instead of by reference.
 217   Passes.add(createArgumentPromotionPass());
 218
 219   // The IPO passes may leave cruft around.  Clean up after them.
 220   Passes.add(createInstructionCombiningPass());
 221
 222   Passes.add(createScalarReplAggregatesPass()); // Break up allocas
 223
 224   // Run a few AA driven optimizations here and now, to cleanup the code.
 225   Passes.add(createGlobalsModRefPass());      // IP alias analysis
 226
 227   Passes.add(createLICMPass());               // Hoist loop invariants
 228   Passes.add(createLoadValueNumberingPass()); // GVN for load instrs
 229   Passes.add(createGCSEPass());               // Remove common subexprs
 230   Passes.add(createDeadStoreEliminationPass()); // Nuke dead stores
 231
 232   // Cleanup and simplify the code after the scalar optimizations.
 233   Passes.add(createInstructionCombiningPass());
 234
 235   // Delete basic blocks, which optimization passes may have killed...
 236   Passes.add(createCFGSimplificationPass());
 237
 238   // Now that we have optimized the program, discard unreachable functions...
 239   Passes.add(createGlobalDCEPass());
 240
 241   // Make sure everything is still good.
 242   Passes.add(createVerifierPass());
 243
 244   Target.addPassesToEmitFile(Passes, Out, TargetMachine::AssemblyFile, true);
 245
 246   // Run our queue of passes all at once now, efficiently.
 247   Passes.run(*M);
 248
 249   return LTO_OPT_SUCCESS;
 250 }
 251
 252 ///Link all modules together and optimize them using IPO. Generate
 253 /// native object file using OutputFilename
 254 /// Return appropriate LTOStatus.
 255 enum LTOStatus
 256 LinkTimeOptimizer::optimizeModules(const std::string &OutputFilename,
 257                                    std::vector<const char *> &exportList)
 258 {
 259   if (modules.empty())
 260     return LTO_NO_WORK;
 261
 262   std::ios::openmode io_mode =
 263     std::ios::out | std::ios::trunc | std::ios::binary;
 264   std::string *errMsg = NULL;
 265   Module *bigOne = modules[0];
 266   Linker theLinker("LinkTimeOptimizer", bigOne, false);
 267   for (unsigned i = 1, e = modules.size(); i != e; ++i)
 268     if (theLinker.LinkModules(bigOne, modules[i], errMsg))
 269       return LTO_MODULE_MERGE_FAILURE;
 270
 271 #if 0
 272   // Enable this when -save-temps is used
 273   std::ofstream Out("big.bc", io_mode);
 274   WriteBytecodeToFile(bigOne, Out, true);
 275 #endif
 276
 277   // Strip leading underscore because it was added to match names
 278   // seen by liner.
 279   for (unsigned i = 0, e = exportList.size(); i != e; ++i) {
 280     const char *name = exportList[i];
 281     if (strlen(name) > 2 && name[0] == '_')
 282       exportList[i] = &name[1];
 283   }
 284
 285   sys::Path tmpAsmFilePath("/tmp/");
 286   tmpAsmFilePath.createTemporaryFileOnDisk();
 287   sys::RemoveFileOnSignal(tmpAsmFilePath);
 288
 289   std::ofstream asmFile(tmpAsmFilePath.c_str(), io_mode);
 290   if (!asmFile.is_open() || asmFile.bad()) {
 291     if (tmpAsmFilePath.exists())
 292       tmpAsmFilePath.eraseFromDisk();
 293     return LTO_WRITE_FAILURE;
 294   }
 295
 296   enum LTOStatus status = lto_optimize(bigOne, asmFile, exportList);
 297   asmFile.close();
 298   if (status != LTO_OPT_SUCCESS) {
 299     tmpAsmFilePath.eraseFromDisk();
 300     return status;
 301   }
 302
 303   // Run GCC to assemble and link the program into native code.
 304   //
 305   // Note:
 306   //  We can't just assemble and link the file with the system assembler
 307   //  and linker because we don't know where to put the _start symbol.
 308   //  GCC mysteriously knows how to do it.
 309   const sys::Path gcc = FindExecutable("gcc", "/");
 310   if (gcc.isEmpty()) {
 311     tmpAsmFilePath.eraseFromDisk();
 312     return LTO_ASM_FAILURE;
 313   }
 314
 315   std::vector<const char*> args;
 316   args.push_back(gcc.c_str());
 317   args.push_back("-c");
 318   args.push_back("-x");
 319   args.push_back("assembler");
 320   args.push_back("-o");
 321   args.push_back(OutputFilename.c_str());
 322   args.push_back(tmpAsmFilePath.c_str());
 323   args.push_back(0);
 324
 325   int R1 = sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 1);
 326
 327   tmpAsmFilePath.eraseFromDisk();
 328
 329   return LTO_OPT_SUCCESS;
 330 }