1 //===-lto.cpp - LLVM Link Time Optimizer ----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
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"
49 llvm::LinkTimeOptimizer *createLLVMOptimizer(unsigned VERSION)
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)
58 llvm::LTO *l = new llvm::LTO();
62 /// If symbol is not used then make it internal and let optimizer takes
64 void LLVMSymbol::mayBeNotUsed() {
65 gv->setLinkage(GlobalValue::InternalLinkage);
68 // Map LLVM LinkageType to LTO LinkageType
69 static LTOLinkageTypes
70 getLTOLinkageType(GlobalValue *v)
73 if (v->hasExternalLinkage())
74 lt = LTOExternalLinkage;
75 else if (v->hasLinkOnceLinkage())
76 lt = LTOLinkOnceLinkage;
77 else if (v->hasWeakLinkage())
79 else if (v->hasCommonLinkage())
80 lt = LTOCommonLinkage;
82 // Otherwise it is internal linkage for link time optimizer
83 lt = LTOInternalLinkage;
87 // MAP LLVM VisibilityType to LTO VisibilityType
88 static LTOVisibilityTypes
89 getLTOVisibilityType(GlobalValue *v)
91 LTOVisibilityTypes vis;
92 if (v->hasHiddenVisibility())
93 vis = LTOHiddenVisibility;
94 else if (v->hasProtectedVisibility())
95 vis = LTOProtectedVisibility;
97 vis = LTODefaultVisibility;
101 // Find exeternal symbols referenced by VALUE. This is a recursive function.
103 findExternalRefs(Value *value, std::set<std::string> &references,
106 if (GlobalValue *gv = dyn_cast<GlobalValue>(value)) {
107 LTOLinkageTypes lt = getLTOLinkageType(gv);
108 if (lt != LTOInternalLinkage && strncmp (gv->getName().c_str(), "llvm.", 5))
109 references.insert(mangler.getValueName(gv));
112 // GlobalValue, even with InternalLinkage type, may have operands with
113 // ExternalLinkage type. Do not ignore these operands.
114 if (Constant *c = dyn_cast<Constant>(value))
115 // Handle ConstantExpr, ConstantStruct, ConstantArry etc..
116 for (unsigned i = 0, e = c->getNumOperands(); i != e; ++i)
117 findExternalRefs(c->getOperand(i), references, mangler);
120 /// If Module with InputFilename is available then remove it from allModules
121 /// and call delete on it.
123 LTO::removeModule (const std::string &InputFilename)
125 NameToModuleMap::iterator pos = allModules.find(InputFilename.c_str());
126 if (pos == allModules.end())
129 Module *m = pos->second;
130 allModules.erase(pos);
134 /// InputFilename is a LLVM bitcode file. If Module with InputFilename is
135 /// available then return it. Otherwise parseInputFilename.
137 LTO::getModule(const std::string &InputFilename)
141 NameToModuleMap::iterator pos = allModules.find(InputFilename.c_str());
142 if (pos != allModules.end())
143 m = allModules[InputFilename.c_str()];
145 if (MemoryBuffer *Buffer
146 = MemoryBuffer::getFile(&InputFilename[0], InputFilename.size())) {
147 m = ParseBitcodeFile(Buffer);
150 allModules[InputFilename.c_str()] = m;
155 /// InputFilename is a LLVM bitcode file. Reade this bitcode file and
156 /// set corresponding target triplet string.
158 LTO::getTargetTriple(const std::string &InputFilename,
159 std::string &targetTriple)
161 Module *m = getModule(InputFilename);
163 targetTriple = m->getTargetTriple();
166 /// InputFilename is a LLVM bitcode file. Read it using bitcode reader.
167 /// Collect global functions and symbol names in symbols vector.
168 /// Collect external references in references vector.
169 /// Return LTO_READ_SUCCESS if there is no error.
171 LTO::readLLVMObjectFile(const std::string &InputFilename,
172 NameToSymbolMap &symbols,
173 std::set<std::string> &references)
175 Module *m = getModule(InputFilename);
177 return LTO_READ_FAILURE;
179 // Collect Target info
183 return LTO_READ_FAILURE;
185 // Use mangler to add GlobalPrefix to names to match linker names.
186 // FIXME : Instead of hard coding "-" use GlobalPrefix.
187 Mangler mangler(*m, Target->getTargetAsmInfo()->getGlobalPrefix());
188 modules.push_back(m);
190 for (Module::iterator f = m->begin(), e = m->end(); f != e; ++f) {
191 LTOLinkageTypes lt = getLTOLinkageType(f);
192 LTOVisibilityTypes vis = getLTOVisibilityType(f);
193 if (!f->isDeclaration() && lt != LTOInternalLinkage
194 && strncmp (f->getName().c_str(), "llvm.", 5)) {
195 int alignment = ( 16 > f->getAlignment() ? 16 : f->getAlignment());
196 LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, f, f->getName(),
197 mangler.getValueName(f),
199 symbols[newSymbol->getMangledName()] = newSymbol;
200 allSymbols[newSymbol->getMangledName()] = newSymbol;
203 // Collect external symbols referenced by this function.
204 for (Function::iterator b = f->begin(), fe = f->end(); b != fe; ++b)
205 for (BasicBlock::iterator i = b->begin(), be = b->end();
207 for (unsigned count = 0, total = i->getNumOperands();
208 count != total; ++count)
209 findExternalRefs(i->getOperand(count), references, mangler);
213 for (Module::global_iterator v = m->global_begin(), e = m->global_end();
215 LTOLinkageTypes lt = getLTOLinkageType(v);
216 LTOVisibilityTypes vis = getLTOVisibilityType(v);
217 if (!v->isDeclaration() && lt != LTOInternalLinkage
218 && strncmp (v->getName().c_str(), "llvm.", 5)) {
219 const TargetData *TD = Target->getTargetData();
220 LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, v, v->getName(),
221 mangler.getValueName(v),
222 TD->getPreferredAlignmentLog(v));
223 symbols[newSymbol->getMangledName()] = newSymbol;
224 allSymbols[newSymbol->getMangledName()] = newSymbol;
226 for (unsigned count = 0, total = v->getNumOperands();
227 count != total; ++count)
228 findExternalRefs(v->getOperand(count), references, mangler);
233 return LTO_READ_SUCCESS;
236 /// Get TargetMachine.
237 /// Use module M to find appropriate Target.
239 LTO::getTarget (Module *M) {
245 const TargetMachineRegistry::entry* March =
246 TargetMachineRegistry::getClosestStaticTargetForModule(*M, Err);
252 SubtargetFeatures Features;
253 std::string FeatureStr;
254 std::string TargetTriple = M->getTargetTriple();
256 if (strncmp(TargetTriple.c_str(), "powerpc-apple-", 14) == 0)
257 Features.AddFeature("altivec", true);
258 else if (strncmp(TargetTriple.c_str(), "powerpc64-apple-", 16) == 0) {
259 Features.AddFeature("64bit", true);
260 Features.AddFeature("altivec", true);
263 FeatureStr = Features.getString();
264 Target = March->CtorFn(*M, FeatureStr);
267 /// Optimize module M using various IPO passes. Use exportList to
268 /// internalize selected symbols. Target platform is selected
269 /// based on information available to module M. No new target
270 /// features are selected.
272 LTO::optimize(Module *M, std::ostream &Out,
273 std::vector<const char *> &exportList)
275 // Instantiate the pass manager to organize the passes.
278 // Collect Target info
282 return LTO_NO_TARGET;
284 // If target supports exception handling then enable it now.
285 if (Target->getTargetAsmInfo()->doesSupportExceptionHandling())
286 ExceptionHandling = true;
288 // Start off with a verification pass.
289 Passes.add(createVerifierPass());
291 // Add an appropriate TargetData instance for this module...
292 Passes.add(new TargetData(*Target->getTargetData()));
294 // Internalize symbols if export list is nonemty
295 if (!exportList.empty())
296 Passes.add(createInternalizePass(exportList));
298 // Now that we internalized some globals, see if we can hack on them!
299 Passes.add(createGlobalOptimizerPass());
301 // Linking modules together can lead to duplicated global constants, only
302 // keep one copy of each constant...
303 Passes.add(createConstantMergePass());
305 // If the -s command line option was specified, strip the symbols out of the
306 // resulting program to make it smaller. -s is a GLD option that we are
308 Passes.add(createStripSymbolsPass());
310 // Propagate constants at call sites into the functions they call.
311 Passes.add(createIPConstantPropagationPass());
313 // Remove unused arguments from functions...
314 Passes.add(createDeadArgEliminationPass());
316 Passes.add(createFunctionInliningPass()); // Inline small functions
318 Passes.add(createPruneEHPass()); // Remove dead EH info
320 Passes.add(createGlobalDCEPass()); // Remove dead functions
322 // If we didn't decide to inline a function, check to see if we can
323 // transform it to pass arguments by value instead of by reference.
324 Passes.add(createArgumentPromotionPass());
326 // The IPO passes may leave cruft around. Clean up after them.
327 Passes.add(createInstructionCombiningPass());
329 Passes.add(createScalarReplAggregatesPass()); // Break up allocas
331 // Run a few AA driven optimizations here and now, to cleanup the code.
332 Passes.add(createGlobalsModRefPass()); // IP alias analysis
334 Passes.add(createLICMPass()); // Hoist loop invariants
335 Passes.add(createGVNPass()); // Remove common subexprs
336 Passed.add(createMemCpyOptPass()); // Remove dead memcpy's
337 Passes.add(createDeadStoreEliminationPass()); // Nuke dead stores
339 // Cleanup and simplify the code after the scalar optimizations.
340 Passes.add(createInstructionCombiningPass());
342 // Delete basic blocks, which optimization passes may have killed...
343 Passes.add(createCFGSimplificationPass());
345 // Now that we have optimized the program, discard unreachable functions...
346 Passes.add(createGlobalDCEPass());
348 // Make sure everything is still good.
349 Passes.add(createVerifierPass());
351 FunctionPassManager *CodeGenPasses =
352 new FunctionPassManager(new ExistingModuleProvider(M));
354 CodeGenPasses->add(new TargetData(*Target->getTargetData()));
356 MachineCodeEmitter *MCE = 0;
358 switch (Target->addPassesToEmitFile(*CodeGenPasses, Out,
359 TargetMachine::AssemblyFile, true)) {
361 case FileModel::Error:
362 return LTO_WRITE_FAILURE;
363 case FileModel::AsmFile:
365 case FileModel::MachOFile:
366 MCE = AddMachOWriter(*CodeGenPasses, Out, *Target);
368 case FileModel::ElfFile:
369 MCE = AddELFWriter(*CodeGenPasses, Out, *Target);
373 if (Target->addPassesToEmitFileFinish(*CodeGenPasses, MCE, true))
374 return LTO_WRITE_FAILURE;
376 // Run our queue of passes all at once now, efficiently.
379 // Run the code generator, if present.
380 CodeGenPasses->doInitialization();
381 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
382 if (!I->isDeclaration())
383 CodeGenPasses->run(*I);
385 CodeGenPasses->doFinalization();
387 return LTO_OPT_SUCCESS;
390 ///Link all modules together and optimize them using IPO. Generate
391 /// native object file using OutputFilename
392 /// Return appropriate LTOStatus.
394 LTO::optimizeModules(const std::string &OutputFilename,
395 std::vector<const char *> &exportList,
396 std::string &targetTriple,
397 bool saveTemps, const char *FinalOutputFilename)
402 std::ios::openmode io_mode =
403 std::ios::out | std::ios::trunc | std::ios::binary;
404 std::string *errMsg = NULL;
405 Module *bigOne = modules[0];
406 Linker theLinker("LinkTimeOptimizer", bigOne, false);
407 for (unsigned i = 1, e = modules.size(); i != e; ++i)
408 if (theLinker.LinkModules(bigOne, modules[i], errMsg))
409 return LTO_MODULE_MERGE_FAILURE;
410 // all modules have been handed off to the linker.
413 sys::Path FinalOutputPath(FinalOutputFilename);
414 FinalOutputPath.eraseSuffix();
417 case LTO_CGM_Dynamic:
418 Target->setRelocationModel(Reloc::PIC_);
420 case LTO_CGM_DynamicNoPIC:
421 Target->setRelocationModel(Reloc::DynamicNoPIC);
424 Target->setRelocationModel(Reloc::Static);
429 std::string tempFileName(FinalOutputPath.c_str());
430 tempFileName += "0.bc";
431 std::ofstream Out(tempFileName.c_str(), io_mode);
432 WriteBitcodeToFile(bigOne, Out);
435 // Strip leading underscore because it was added to match names
437 for (unsigned i = 0, e = exportList.size(); i != e; ++i) {
438 const char *name = exportList[i];
439 NameToSymbolMap::iterator itr = allSymbols.find(name);
440 if (itr != allSymbols.end())
441 exportList[i] = allSymbols[name]->getName();
446 sys::Path TempDir = sys::Path::GetTemporaryDirectory(&ErrMsg);
447 if (TempDir.isEmpty()) {
448 cerr << "lto: " << ErrMsg << "\n";
449 return LTO_WRITE_FAILURE;
451 sys::Path tmpAsmFilePath(TempDir);
452 if (!tmpAsmFilePath.appendComponent("lto")) {
453 cerr << "lto: " << ErrMsg << "\n";
454 TempDir.eraseFromDisk(true);
455 return LTO_WRITE_FAILURE;
457 if (tmpAsmFilePath.createTemporaryFileOnDisk(true, &ErrMsg)) {
458 cerr << "lto: " << ErrMsg << "\n";
459 TempDir.eraseFromDisk(true);
460 return LTO_WRITE_FAILURE;
462 sys::RemoveFileOnSignal(tmpAsmFilePath);
464 std::ofstream asmFile(tmpAsmFilePath.c_str(), io_mode);
465 if (!asmFile.is_open() || asmFile.bad()) {
466 if (tmpAsmFilePath.exists()) {
467 tmpAsmFilePath.eraseFromDisk();
468 TempDir.eraseFromDisk(true);
470 return LTO_WRITE_FAILURE;
473 enum LTOStatus status = optimize(bigOne, asmFile, exportList);
475 if (status != LTO_OPT_SUCCESS) {
476 tmpAsmFilePath.eraseFromDisk();
477 TempDir.eraseFromDisk(true);
482 std::string tempFileName(FinalOutputPath.c_str());
483 tempFileName += "1.bc";
484 std::ofstream Out(tempFileName.c_str(), io_mode);
485 WriteBitcodeToFile(bigOne, Out);
488 targetTriple = bigOne->getTargetTriple();
490 // Run GCC to assemble and link the program into native code.
493 // We can't just assemble and link the file with the system assembler
494 // and linker because we don't know where to put the _start symbol.
495 // GCC mysteriously knows how to do it.
496 const sys::Path gcc = sys::Program::FindProgramByName("gcc");
498 tmpAsmFilePath.eraseFromDisk();
499 TempDir.eraseFromDisk(true);
500 return LTO_ASM_FAILURE;
503 std::vector<const char*> args;
504 args.push_back(gcc.c_str());
505 if (strncmp(targetTriple.c_str(), "i686-apple-", 11) == 0) {
506 args.push_back("-arch");
507 args.push_back("i386");
509 if (strncmp(targetTriple.c_str(), "x86_64-apple-", 13) == 0) {
510 args.push_back("-arch");
511 args.push_back("x86_64");
513 if (strncmp(targetTriple.c_str(), "powerpc-apple-", 14) == 0) {
514 args.push_back("-arch");
515 args.push_back("ppc");
517 if (strncmp(targetTriple.c_str(), "powerpc64-apple-", 16) == 0) {
518 args.push_back("-arch");
519 args.push_back("ppc64");
521 args.push_back("-c");
522 args.push_back("-x");
523 args.push_back("assembler");
524 args.push_back("-o");
525 args.push_back(OutputFilename.c_str());
526 args.push_back(tmpAsmFilePath.c_str());
529 if (sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 0, 0, &ErrMsg)) {
530 cerr << "lto: " << ErrMsg << "\n";
531 return LTO_ASM_FAILURE;
534 tmpAsmFilePath.eraseFromDisk();
535 TempDir.eraseFromDisk(true);
537 return LTO_OPT_SUCCESS;
540 void LTO::printVersion() {
541 cl::PrintVersionMessage();
544 /// Unused pure-virtual destructor. Must remain empty.
545 LinkTimeOptimizer::~LinkTimeOptimizer() {}
547 /// Destruct LTO. Delete all modules, symbols and target.
550 for (std::vector<Module *>::iterator itr = modules.begin(), e = modules.end();
556 for (NameToSymbolMap::iterator itr = allSymbols.begin(), e = allSymbols.end();