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