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