lto.cpp revision d2368dc344bf46e2f5df3de1bff74ab0228d99a9 
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  Passes.add(createStripSymbolsPass());
307
308  // Propagate constants at call sites into the functions they call.
309  Passes.add(createIPConstantPropagationPass());
310
311  // Remove unused arguments from functions...
312  Passes.add(createDeadArgEliminationPass());
313
314  Passes.add(createFunctionInliningPass()); // Inline small functions
315
316  Passes.add(createPruneEHPass());            // Remove dead EH info
317
318  Passes.add(createGlobalDCEPass());          // Remove dead functions
319
320  // If we didn't decide to inline a function, check to see if we can
321  // transform it to pass arguments by value instead of by reference.
322  Passes.add(createArgumentPromotionPass());
323
324  // The IPO passes may leave cruft around.  Clean up after them.
325  Passes.add(createInstructionCombiningPass());
326
327  Passes.add(createScalarReplAggregatesPass()); // Break up allocas
328
329  // Run a few AA driven optimizations here and now, to cleanup the code.
330  Passes.add(createGlobalsModRefPass());      // IP alias analysis
331
332  Passes.add(createLICMPass());               // Hoist loop invariants
333  Passes.add(createGVNPass());               // Remove common subexprs
334  Passed.add(createMemCpyOptPass());  // Remove dead memcpy's
335  Passes.add(createDeadStoreEliminationPass()); // Nuke dead stores
336
337  // Cleanup and simplify the code after the scalar optimizations.
338  Passes.add(createInstructionCombiningPass());
339
340  // Delete basic blocks, which optimization passes may have killed...
341  Passes.add(createCFGSimplificationPass());
342
343  // Now that we have optimized the program, discard unreachable functions...
344  Passes.add(createGlobalDCEPass());
345
346  // Make sure everything is still good.
347  Passes.add(createVerifierPass());
348
349  FunctionPassManager *CodeGenPasses =
350    new FunctionPassManager(new ExistingModuleProvider(M));
351
352  CodeGenPasses->add(new TargetData(*Target->getTargetData()));
353
354  MachineCodeEmitter *MCE = 0;
355
356  switch (Target->addPassesToEmitFile(*CodeGenPasses, Out,
357                                      TargetMachine::AssemblyFile, true)) {
358  default:
359  case FileModel::Error:
360    return LTO_WRITE_FAILURE;
361  case FileModel::AsmFile:
362    break;
363  case FileModel::MachOFile:
364    MCE = AddMachOWriter(*CodeGenPasses, Out, *Target);
365    break;
366  case FileModel::ElfFile:
367    MCE = AddELFWriter(*CodeGenPasses, Out, *Target);
368    break;
369  }
370
371  if (Target->addPassesToEmitFileFinish(*CodeGenPasses, MCE, true))
372    return LTO_WRITE_FAILURE;
373
374  // Run our queue of passes all at once now, efficiently.
375  Passes.run(*M);
376
377  // Run the code generator, if present.
378  CodeGenPasses->doInitialization();
379  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
380    if (!I->isDeclaration())
381      CodeGenPasses->run(*I);
382  }
383  CodeGenPasses->doFinalization();
384
385  return LTO_OPT_SUCCESS;
386}
387
388///Link all modules together and optimize them using IPO. Generate
389/// native object file using OutputFilename
390/// Return appropriate LTOStatus.
391enum LTOStatus
392LTO::optimizeModules(const std::string &OutputFilename,
393                     std::vector<const char *> &exportList,
394                     std::string &targetTriple,
395                     bool saveTemps, const char *FinalOutputFilename)
396{
397  if (modules.empty())
398    return LTO_NO_WORK;
399
400  std::ios::openmode io_mode =
401    std::ios::out | std::ios::trunc | std::ios::binary;
402  std::string *errMsg = NULL;
403  Module *bigOne = modules[0];
404  Linker theLinker("LinkTimeOptimizer", bigOne, false);
405  for (unsigned i = 1, e = modules.size(); i != e; ++i)
406    if (theLinker.LinkModules(bigOne, modules[i], errMsg))
407      return LTO_MODULE_MERGE_FAILURE;
408  //  all modules have been handed off to the linker.
409  modules.clear();
410
411  sys::Path FinalOutputPath(FinalOutputFilename);
412  FinalOutputPath.eraseSuffix();
413
414  switch(CGModel) {
415  case LTO_CGM_Dynamic:
416    Target->setRelocationModel(Reloc::PIC_);
417    break;
418  case LTO_CGM_DynamicNoPIC:
419    Target->setRelocationModel(Reloc::DynamicNoPIC);
420    break;
421  case LTO_CGM_Static:
422    Target->setRelocationModel(Reloc::Static);
423    break;
424  }
425
426  if (saveTemps) {
427    std::string tempFileName(FinalOutputPath.c_str());
428    tempFileName += "0.bc";
429    std::ofstream Out(tempFileName.c_str(), io_mode);
430    WriteBitcodeToFile(bigOne, Out);
431  }
432
433  // Strip leading underscore because it was added to match names
434  // seen by linker.
435  for (unsigned i = 0, e = exportList.size(); i != e; ++i) {
436    const char *name = exportList[i];
437    NameToSymbolMap::iterator itr = allSymbols.find(name);
438    if (itr != allSymbols.end())
439      exportList[i] = allSymbols[name]->getName();
440  }
441
442
443  std::string ErrMsg;
444  sys::Path TempDir = sys::Path::GetTemporaryDirectory(&ErrMsg);
445  if (TempDir.isEmpty()) {
446    cerr << "lto: " << ErrMsg << "\n";
447    return LTO_WRITE_FAILURE;
448  }
449  sys::Path tmpAsmFilePath(TempDir);
450  if (!tmpAsmFilePath.appendComponent("lto")) {
451    cerr << "lto: " << ErrMsg << "\n";
452    TempDir.eraseFromDisk(true);
453    return LTO_WRITE_FAILURE;
454  }
455  if (tmpAsmFilePath.createTemporaryFileOnDisk(true, &ErrMsg)) {
456    cerr << "lto: " << ErrMsg << "\n";
457    TempDir.eraseFromDisk(true);
458    return LTO_WRITE_FAILURE;
459  }
460  sys::RemoveFileOnSignal(tmpAsmFilePath);
461
462  std::ofstream asmFile(tmpAsmFilePath.c_str(), io_mode);
463  if (!asmFile.is_open() || asmFile.bad()) {
464    if (tmpAsmFilePath.exists()) {
465      tmpAsmFilePath.eraseFromDisk();
466      TempDir.eraseFromDisk(true);
467    }
468    return LTO_WRITE_FAILURE;
469  }
470
471  enum LTOStatus status = optimize(bigOne, asmFile, exportList);
472  asmFile.close();
473  if (status != LTO_OPT_SUCCESS) {
474    tmpAsmFilePath.eraseFromDisk();
475    TempDir.eraseFromDisk(true);
476    return status;
477  }
478
479  if (saveTemps) {
480    std::string tempFileName(FinalOutputPath.c_str());
481    tempFileName += "1.bc";
482    std::ofstream Out(tempFileName.c_str(), io_mode);
483    WriteBitcodeToFile(bigOne, Out);
484  }
485
486  targetTriple = bigOne->getTargetTriple();
487
488  // Run GCC to assemble and link the program into native code.
489  //
490  // Note:
491  //  We can't just assemble and link the file with the system assembler
492  //  and linker because we don't know where to put the _start symbol.
493  //  GCC mysteriously knows how to do it.
494  const sys::Path gcc = sys::Program::FindProgramByName("gcc");
495  if (gcc.isEmpty()) {
496    tmpAsmFilePath.eraseFromDisk();
497    TempDir.eraseFromDisk(true);
498    return LTO_ASM_FAILURE;
499  }
500
501  std::vector<const char*> args;
502  args.push_back(gcc.c_str());
503  if (strncmp(targetTriple.c_str(), "i686-apple-", 11) == 0) {
504    args.push_back("-arch");
505    args.push_back("i386");
506  }
507  if (strncmp(targetTriple.c_str(), "x86_64-apple-", 13) == 0) {
508    args.push_back("-arch");
509    args.push_back("x86_64");
510  }
511  if (strncmp(targetTriple.c_str(), "powerpc-apple-", 14) == 0) {
512    args.push_back("-arch");
513    args.push_back("ppc");
514  }
515  if (strncmp(targetTriple.c_str(), "powerpc64-apple-", 16) == 0) {
516    args.push_back("-arch");
517    args.push_back("ppc64");
518  }
519  args.push_back("-c");
520  args.push_back("-x");
521  args.push_back("assembler");
522  args.push_back("-o");
523  args.push_back(OutputFilename.c_str());
524  args.push_back(tmpAsmFilePath.c_str());
525  args.push_back(0);
526
527  if (sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 0, 0, &ErrMsg)) {
528    cerr << "lto: " << ErrMsg << "\n";
529    return LTO_ASM_FAILURE;
530  }
531
532  tmpAsmFilePath.eraseFromDisk();
533  TempDir.eraseFromDisk(true);
534
535  return LTO_OPT_SUCCESS;
536}
537
538void LTO::printVersion() {
539    cl::PrintVersionMessage();
540}
541
542/// Unused pure-virtual destructor. Must remain empty.
543LinkTimeOptimizer::~LinkTimeOptimizer() {}
544
545/// Destruct LTO. Delete all modules, symbols and target.
546LTO::~LTO() {
547
548  for (std::vector<Module *>::iterator itr = modules.begin(), e = modules.end();
549       itr != e; ++itr)
550    delete *itr;
551
552  modules.clear();
553
554  for (NameToSymbolMap::iterator itr = allSymbols.begin(), e = allSymbols.end();
555       itr != e; ++itr)
556    delete itr->second;
557
558  allSymbols.clear();
559
560  delete Target;
561}
562