lto.cpp revision 0e50128099171b431b05a34f5b98ea1c2f82b867 
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  std::string Features;
251  Target = March->CtorFn(*M, Features);
252}
253
254/// Optimize module M using various IPO passes. Use exportList to
255/// internalize selected symbols. Target platform is selected
256/// based on information available to module M. No new target
257/// features are selected.
258enum LTOStatus
259LTO::optimize(Module *M, std::ostream &Out,
260              std::vector<const char *> &exportList)
261{
262  // Instantiate the pass manager to organize the passes.
263  PassManager Passes;
264
265  // Collect Target info
266  getTarget(M);
267
268  if (!Target)
269    return LTO_NO_TARGET;
270
271  // If target supports exception handling then enable it now.
272  if (Target->getTargetAsmInfo()->doesSupportExceptionHandling())
273    ExceptionHandling = true;
274
275  // Start off with a verification pass.
276  Passes.add(createVerifierPass());
277
278  // Add an appropriate TargetData instance for this module...
279  Passes.add(new TargetData(*Target->getTargetData()));
280
281  // Internalize symbols if export list is nonemty
282  if (!exportList.empty())
283    Passes.add(createInternalizePass(exportList));
284
285  // Now that we internalized some globals, see if we can hack on them!
286  Passes.add(createGlobalOptimizerPass());
287
288  // Linking modules together can lead to duplicated global constants, only
289  // keep one copy of each constant...
290  Passes.add(createConstantMergePass());
291
292  // If the -s command line option was specified, strip the symbols out of the
293  // resulting program to make it smaller.  -s is a GLD option that we are
294  // supporting.
295  if(!ExceptionHandling)
296    // FIXME : This causes multiple nameless _.eh symbols on
297    // darwin when EH is ON.
298    Passes.add(createStripSymbolsPass());
299
300  // Propagate constants at call sites into the functions they call.
301  Passes.add(createIPConstantPropagationPass());
302
303  // Remove unused arguments from functions...
304  Passes.add(createDeadArgEliminationPass());
305
306  Passes.add(createFunctionInliningPass()); // Inline small functions
307
308  Passes.add(createPruneEHPass());            // Remove dead EH info
309
310  Passes.add(createGlobalDCEPass());          // Remove dead functions
311
312  // If we didn't decide to inline a function, check to see if we can
313  // transform it to pass arguments by value instead of by reference.
314  Passes.add(createArgumentPromotionPass());
315
316  // The IPO passes may leave cruft around.  Clean up after them.
317  Passes.add(createInstructionCombiningPass());
318
319  Passes.add(createScalarReplAggregatesPass()); // Break up allocas
320
321  // Run a few AA driven optimizations here and now, to cleanup the code.
322  Passes.add(createGlobalsModRefPass());      // IP alias analysis
323
324  Passes.add(createLICMPass());               // Hoist loop invariants
325  Passes.add(createLoadValueNumberingPass()); // GVN for load instrs
326  Passes.add(createGCSEPass());               // Remove common subexprs
327  Passes.add(createDeadStoreEliminationPass()); // Nuke dead stores
328
329  // Cleanup and simplify the code after the scalar optimizations.
330  Passes.add(createInstructionCombiningPass());
331
332  // Delete basic blocks, which optimization passes may have killed...
333  Passes.add(createCFGSimplificationPass());
334
335  // Now that we have optimized the program, discard unreachable functions...
336  Passes.add(createGlobalDCEPass());
337
338  // Make sure everything is still good.
339  Passes.add(createVerifierPass());
340
341  FunctionPassManager *CodeGenPasses =
342    new FunctionPassManager(new ExistingModuleProvider(M));
343
344  CodeGenPasses->add(new TargetData(*Target->getTargetData()));
345
346  MachineCodeEmitter *MCE = 0;
347
348  switch (Target->addPassesToEmitFile(*CodeGenPasses, Out,
349                                      TargetMachine::AssemblyFile, true)) {
350  default:
351  case FileModel::Error:
352    return LTO_WRITE_FAILURE;
353  case FileModel::AsmFile:
354    break;
355  case FileModel::MachOFile:
356    MCE = AddMachOWriter(*CodeGenPasses, Out, *Target);
357    break;
358  case FileModel::ElfFile:
359    MCE = AddELFWriter(*CodeGenPasses, Out, *Target);
360    break;
361  }
362
363  if (Target->addPassesToEmitFileFinish(*CodeGenPasses, MCE, true))
364    return LTO_WRITE_FAILURE;
365
366  // Run our queue of passes all at once now, efficiently.
367  Passes.run(*M);
368
369  // Run the code generator, if present.
370  CodeGenPasses->doInitialization();
371  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
372    if (!I->isDeclaration())
373      CodeGenPasses->run(*I);
374  }
375  CodeGenPasses->doFinalization();
376
377  return LTO_OPT_SUCCESS;
378}
379
380///Link all modules together and optimize them using IPO. Generate
381/// native object file using OutputFilename
382/// Return appropriate LTOStatus.
383enum LTOStatus
384LTO::optimizeModules(const std::string &OutputFilename,
385                     std::vector<const char *> &exportList,
386                     std::string &targetTriple,
387                     bool saveTemps, const char *FinalOutputFilename)
388{
389  if (modules.empty())
390    return LTO_NO_WORK;
391
392  std::ios::openmode io_mode =
393    std::ios::out | std::ios::trunc | std::ios::binary;
394  std::string *errMsg = NULL;
395  Module *bigOne = modules[0];
396  Linker theLinker("LinkTimeOptimizer", bigOne, false);
397  for (unsigned i = 1, e = modules.size(); i != e; ++i)
398    if (theLinker.LinkModules(bigOne, modules[i], errMsg))
399      return LTO_MODULE_MERGE_FAILURE;
400  //  all modules have been handed off to the linker.
401  modules.clear();
402
403  sys::Path FinalOutputPath(FinalOutputFilename);
404  FinalOutputPath.eraseSuffix();
405
406  switch(CGModel) {
407  case LTO_CGM_Dynamic:
408    Target->setRelocationModel(Reloc::PIC_);
409    break;
410  case LTO_CGM_DynamicNoPIC:
411    Target->setRelocationModel(Reloc::DynamicNoPIC);
412    break;
413  case LTO_CGM_Static:
414    Target->setRelocationModel(Reloc::Static);
415    break;
416  }
417
418  if (saveTemps) {
419    std::string tempFileName(FinalOutputPath.c_str());
420    tempFileName += "0.bc";
421    std::ofstream Out(tempFileName.c_str(), io_mode);
422    WriteBitcodeToFile(bigOne, Out);
423  }
424
425  // Strip leading underscore because it was added to match names
426  // seen by linker.
427  for (unsigned i = 0, e = exportList.size(); i != e; ++i) {
428    const char *name = exportList[i];
429    NameToSymbolMap::iterator itr = allSymbols.find(name);
430    if (itr != allSymbols.end())
431      exportList[i] = allSymbols[name]->getName();
432  }
433
434
435  std::string ErrMsg;
436  sys::Path TempDir = sys::Path::GetTemporaryDirectory(&ErrMsg);
437  if (TempDir.isEmpty()) {
438    cerr << "lto: " << ErrMsg << "\n";
439    return LTO_WRITE_FAILURE;
440  }
441  sys::Path tmpAsmFilePath(TempDir);
442  if (!tmpAsmFilePath.appendComponent("lto")) {
443    cerr << "lto: " << ErrMsg << "\n";
444    TempDir.eraseFromDisk(true);
445    return LTO_WRITE_FAILURE;
446  }
447  if (tmpAsmFilePath.createTemporaryFileOnDisk(true, &ErrMsg)) {
448    cerr << "lto: " << ErrMsg << "\n";
449    TempDir.eraseFromDisk(true);
450    return LTO_WRITE_FAILURE;
451  }
452  sys::RemoveFileOnSignal(tmpAsmFilePath);
453
454  std::ofstream asmFile(tmpAsmFilePath.c_str(), io_mode);
455  if (!asmFile.is_open() || asmFile.bad()) {
456    if (tmpAsmFilePath.exists()) {
457      tmpAsmFilePath.eraseFromDisk();
458      TempDir.eraseFromDisk(true);
459    }
460    return LTO_WRITE_FAILURE;
461  }
462
463  enum LTOStatus status = optimize(bigOne, asmFile, exportList);
464  asmFile.close();
465  if (status != LTO_OPT_SUCCESS) {
466    tmpAsmFilePath.eraseFromDisk();
467    TempDir.eraseFromDisk(true);
468    return status;
469  }
470
471  if (saveTemps) {
472    std::string tempFileName(FinalOutputPath.c_str());
473    tempFileName += "1.bc";
474    std::ofstream Out(tempFileName.c_str(), io_mode);
475    WriteBitcodeToFile(bigOne, Out);
476  }
477
478  targetTriple = bigOne->getTargetTriple();
479
480  // Run GCC to assemble and link the program into native code.
481  //
482  // Note:
483  //  We can't just assemble and link the file with the system assembler
484  //  and linker because we don't know where to put the _start symbol.
485  //  GCC mysteriously knows how to do it.
486  const sys::Path gcc = sys::Program::FindProgramByName("gcc");
487  if (gcc.isEmpty()) {
488    tmpAsmFilePath.eraseFromDisk();
489    TempDir.eraseFromDisk(true);
490    return LTO_ASM_FAILURE;
491  }
492
493  std::vector<const char*> args;
494  args.push_back(gcc.c_str());
495  if (strncmp(targetTriple.c_str(), "i686-apple-", 11) == 0) {
496    args.push_back("-arch");
497    args.push_back("i386");
498  }
499  if (strncmp(targetTriple.c_str(), "x86_64-apple-", 13) == 0) {
500    args.push_back("-arch");
501    args.push_back("x86_64");
502  }
503  if (strncmp(targetTriple.c_str(), "powerpc-apple-", 14) == 0) {
504    args.push_back("-arch");
505    args.push_back("ppc");
506  }
507  if (strncmp(targetTriple.c_str(), "powerpc64-apple-", 16) == 0) {
508    args.push_back("-arch");
509    args.push_back("ppc64");
510  }
511  args.push_back("-c");
512  args.push_back("-x");
513  args.push_back("assembler");
514  args.push_back("-o");
515  args.push_back(OutputFilename.c_str());
516  args.push_back(tmpAsmFilePath.c_str());
517  args.push_back(0);
518
519  if (sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 0, 0, &ErrMsg)) {
520    cerr << "lto: " << ErrMsg << "\n";
521    return LTO_ASM_FAILURE;
522  }
523
524  tmpAsmFilePath.eraseFromDisk();
525  TempDir.eraseFromDisk(true);
526
527  return LTO_OPT_SUCCESS;
528}
529
530void LTO::printVersion() {
531    cl::PrintVersionMessage();
532}
533
534/// Unused pure-virtual destructor. Must remain empty.
535LinkTimeOptimizer::~LinkTimeOptimizer() {}
536
537/// Destruct LTO. Delete all modules, symbols and target.
538LTO::~LTO() {
539
540  for (std::vector<Module *>::iterator itr = modules.begin(), e = modules.end();
541       itr != e; ++itr)
542    delete *itr;
543
544  modules.clear();
545
546  for (NameToSymbolMap::iterator itr = allSymbols.begin(), e = allSymbols.end();
547       itr != e; ++itr)
548    delete itr->second;
549
550  allSymbols.clear();
551
552  delete Target;
553}
554