Rename new lto2 tool as lto.

lto2->lto


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52912 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 1268 insertions, 0 deletions

diff --git a/tools/lto/LTOCodeGenerator.cpp b/tools/lto/LTOCodeGenerator.cpp
new file mode 100644
index 0000000000..d82279d494
--- /dev/null
+++ b/tools/lto/LTOCodeGenerator.cpp
@@ -0,0 +1,445 @@
+//===-LTOCodeGenerator.cpp - LLVM Link Time Optimizer ---------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file implements the Link Time Optimization library. This library is 
+// intended to be used by linker to optimize code at link time.
+//
+//===----------------------------------------------------------------------===//
+
+#include "LTOModule.h"
+#include "LTOCodeGenerator.h"
+
+
+#include "llvm/Module.h"
+#include "llvm/PassManager.h"
+#include "llvm/Linker.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/ModuleProvider.h"
+#include "llvm/Bitcode/ReaderWriter.h"
+#include "llvm/Support/SystemUtils.h"
+#include "llvm/Support/Mangler.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/System/Signals.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/Verifier.h"
+#include "llvm/Analysis/LoadValueNumbering.h"
+#include "llvm/CodeGen/FileWriters.h"
+#include "llvm/Target/SubtargetFeature.h"
+#include "llvm/Target/TargetOptions.h"
+#include "llvm/Target/TargetData.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetMachineRegistry.h"
+#include "llvm/Target/TargetAsmInfo.h"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Config/config.h"
+
+
+#include <fstream>
+#include <unistd.h>
+#include <stdlib.h>
+#include <fcntl.h>
+
+
+using namespace llvm;
+
+
+
+const char* LTOCodeGenerator::getVersionString()
+{
+#ifdef LLVM_VERSION_INFO
+    return PACKAGE_NAME " version " PACKAGE_VERSION ", " LLVM_VERSION_INFO;
+#else
+    return PACKAGE_NAME " version " PACKAGE_VERSION;
+#endif
+}
+
+
+LTOCodeGenerator::LTOCodeGenerator() 
+    : _linker("LinkTimeOptimizer", "ld-temp.o"), _target(NULL),
+      _emitDwarfDebugInfo(false), _scopeRestrictionsDone(false),
+      _codeModel(LTO_CODEGEN_PIC_MODEL_DYNAMIC),
+      _nativeObjectFile(NULL)
+{
+
+}
+
+LTOCodeGenerator::~LTOCodeGenerator()
+{
+    delete _target;
+    delete _nativeObjectFile;
+}
+
+
+
+bool LTOCodeGenerator::addModule(LTOModule* mod, std::string& errMsg)
+{
+    return _linker.LinkInModule(mod->getLLVVMModule(), &errMsg);
+}
+    
+
+bool LTOCodeGenerator::setDebugInfo(lto_debug_model debug, std::string& errMsg)
+{
+    switch (debug) {
+        case LTO_DEBUG_MODEL_NONE:
+            _emitDwarfDebugInfo = false;
+            return false;
+            
+        case LTO_DEBUG_MODEL_DWARF:
+            _emitDwarfDebugInfo = true;
+            return false;
+    }
+    errMsg = "unknown debug format";
+    return true;
+}
+
+
+bool LTOCodeGenerator::setCodePICModel(lto_codegen_model model, 
+                                                        std::string& errMsg)
+{
+    switch (model) {
+        case LTO_CODEGEN_PIC_MODEL_STATIC:
+        case LTO_CODEGEN_PIC_MODEL_DYNAMIC:
+        case LTO_CODEGEN_PIC_MODEL_DYNAMIC_NO_PIC:
+            _codeModel = model;
+            return false;
+    }
+    errMsg = "unknown pic model";
+    return true;
+}
+
+
+void LTOCodeGenerator::addMustPreserveSymbol(const char* sym)
+{
+    _mustPreserveSymbols[sym] = 1;
+}
+
+
+bool LTOCodeGenerator::writeMergedModules(const char* path, std::string& errMsg)
+{
+    if ( this->determineTarget(errMsg) ) 
+        return true;
+
+    // mark which symbols can not be internalized 
+    this->applyScopeRestrictions();
+
+    // create output file
+    std::ofstream out(path, std::ios_base::out|std::ios::trunc|std::ios::binary);
+    if ( out.fail() ) {
+        errMsg = "could not open bitcode file for writing: ";
+        errMsg += path;
+        return true;
+    }
+    
+    // write bitcode to it
+    WriteBitcodeToFile(_linker.getModule(), out);
+    if ( out.fail() ) {
+        errMsg = "could not write bitcode file: ";
+        errMsg += path;
+        return true;
+    }
+    
+    return false;
+}
+
+
+const void* LTOCodeGenerator::compile(size_t* length, std::string& errMsg)
+{
+    // make unique temp .s file to put generated assembly code
+    sys::Path uniqueAsmPath("lto-llvm.s");
+    if ( uniqueAsmPath.createTemporaryFileOnDisk(true, &errMsg) )
+        return NULL;
+    sys::RemoveFileOnSignal(uniqueAsmPath);
+       
+    // generate assembly code
+    std::ofstream asmFile(uniqueAsmPath.c_str());
+    bool genResult = this->generateAssemblyCode(asmFile, errMsg);
+    asmFile.close();
+    if ( genResult ) {
+        if ( uniqueAsmPath.exists() )
+            uniqueAsmPath.eraseFromDisk();
+        return NULL;
+    }
+    
+    // make unique temp .o file to put generated object file
+    sys::PathWithStatus uniqueObjPath("lto-llvm.o");
+    if ( uniqueObjPath.createTemporaryFileOnDisk(true, &errMsg) ) {
+        if ( uniqueAsmPath.exists() )
+            uniqueAsmPath.eraseFromDisk();
+        return NULL;
+    }
+    sys::RemoveFileOnSignal(uniqueObjPath);
+
+    // assemble the assembly code
+    const std::string& uniqueObjStr = uniqueObjPath.toString();
+    bool asmResult = this->assemble(uniqueAsmPath.toString(), 
+                                                        uniqueObjStr, errMsg);
+    if ( !asmResult ) {
+        // remove old buffer if compile() called twice
+        delete _nativeObjectFile;
+        
+        // read .o file into memory buffer
+        _nativeObjectFile = MemoryBuffer::getFile(uniqueObjStr.c_str(),&errMsg);
+    }
+
+    // remove temp files
+    uniqueAsmPath.eraseFromDisk();
+    uniqueObjPath.eraseFromDisk();
+
+    // return buffer, unless error
+    if ( _nativeObjectFile == NULL )
+        return NULL;
+    *length = _nativeObjectFile->getBufferSize();
+    return _nativeObjectFile->getBufferStart();
+}
+
+
+bool LTOCodeGenerator::assemble(const std::string& asmPath, 
+                                const std::string& objPath, std::string& errMsg)
+{
+    // find compiler driver
+    const sys::Path gcc = sys::Program::FindProgramByName("gcc");
+    if ( gcc.isEmpty() ) {
+        errMsg = "can't locate gcc";
+        return true;
+    }
+
+    // build argument list
+    std::vector<const char*> args;
+    std::string targetTriple = _linker.getModule()->getTargetTriple();
+    args.push_back(gcc.c_str());
+    if ( targetTriple.find("darwin") != targetTriple.size() ) {
+        if (strncmp(targetTriple.c_str(), "i686-apple-", 11) == 0) {
+            args.push_back("-arch");
+            args.push_back("i386");
+        }
+        else if (strncmp(targetTriple.c_str(), "x86_64-apple-", 13) == 0) {
+            args.push_back("-arch");
+            args.push_back("x86_64");
+        }
+        else if (strncmp(targetTriple.c_str(), "powerpc-apple-", 14) == 0) {
+            args.push_back("-arch");
+            args.push_back("ppc");
+        }
+        else if (strncmp(targetTriple.c_str(), "powerpc64-apple-", 16) == 0) {
+            args.push_back("-arch");
+            args.push_back("ppc64");
+        }
+    }
+    args.push_back("-c");
+    args.push_back("-x");
+    args.push_back("assembler");
+    args.push_back("-o");
+    args.push_back(objPath.c_str());
+    args.push_back(asmPath.c_str());
+    args.push_back(0);
+
+    // invoke assembler
+    if ( sys::Program::ExecuteAndWait(gcc, &args[0], 0, 0, 0, 0, &errMsg) ) {
+        errMsg = "error in assembly";    
+        return true;
+    }
+    return false; // success
+}
+
+
+
+bool LTOCodeGenerator::determineTarget(std::string& errMsg)
+{
+    if ( _target == NULL ) {
+        // create target machine from info for merged modules
+        Module* mergedModule = _linker.getModule();
+        const TargetMachineRegistry::entry* march = 
+          TargetMachineRegistry::getClosestStaticTargetForModule(
+                                                       *mergedModule, errMsg);
+        if ( march == NULL )
+            return true;
+
+        // construct LTModule, hand over ownership of module and target
+        std::string FeatureStr =
+          getFeatureString(_linker.getModule()->getTargetTriple().c_str());
+        _target = march->CtorFn(*mergedModule, FeatureStr.c_str());
+    }
+    return false;
+}
+
+void LTOCodeGenerator::applyScopeRestrictions()
+{
+    if ( !_scopeRestrictionsDone ) {
+        Module* mergedModule = _linker.getModule();
+
+        // Start off with a verification pass.
+        PassManager passes;
+        passes.add(createVerifierPass());
+
+        // mark which symbols can not be internalized 
+        if ( !_mustPreserveSymbols.empty() ) {
+            Mangler mangler(*mergedModule, 
+                                _target->getTargetAsmInfo()->getGlobalPrefix());
+            std::vector<const char*> mustPreserveList;
+            for (Module::iterator f = mergedModule->begin(), 
+                                        e = mergedModule->end(); f != e; ++f) {
+                if ( !f->isDeclaration() 
+                  && _mustPreserveSymbols.count(mangler.getValueName(f)) )
+                    mustPreserveList.push_back(::strdup(f->getName().c_str()));
+            }
+            for (Module::global_iterator v = mergedModule->global_begin(), 
+                                 e = mergedModule->global_end(); v !=  e; ++v) {
+                if ( !v->isDeclaration()
+                  && _mustPreserveSymbols.count(mangler.getValueName(v)) )
+                    mustPreserveList.push_back(::strdup(v->getName().c_str()));
+            }
+            passes.add(createInternalizePass(mustPreserveList));
+        }
+        // apply scope restrictions
+        passes.run(*mergedModule);
+        
+        _scopeRestrictionsDone = true;
+    }
+}
+
+/// Optimize merged modules using various IPO passes
+bool LTOCodeGenerator::generateAssemblyCode(std::ostream& out, std::string& errMsg)
+{
+    if (  this->determineTarget(errMsg) ) 
+        return true;
+
+    // mark which symbols can not be internalized 
+    this->applyScopeRestrictions();
+
+    Module* mergedModule = _linker.getModule();
+
+     // If target supports exception handling then enable it now.
+    if ( _target->getTargetAsmInfo()->doesSupportExceptionHandling() )
+        llvm::ExceptionHandling = true;
+
+    // set codegen model
+    switch( _codeModel ) {
+        case LTO_CODEGEN_PIC_MODEL_STATIC:
+            _target->setRelocationModel(Reloc::Static);
+            break;
+        case LTO_CODEGEN_PIC_MODEL_DYNAMIC:
+            _target->setRelocationModel(Reloc::PIC_);
+            break;
+        case LTO_CODEGEN_PIC_MODEL_DYNAMIC_NO_PIC:
+            _target->setRelocationModel(Reloc::DynamicNoPIC);
+            break;
+    }
+
+    // Instantiate the pass manager to organize the passes.
+    PassManager passes;
+
+    // Start off with a verification pass.
+    passes.add(createVerifierPass());
+
+    // Add an appropriate TargetData instance for this module...
+    passes.add(new TargetData(*_target->getTargetData()));
+    
+    // Propagate constants at call sites into the functions they call.  This
+    // opens opportunities for globalopt (and inlining) by substituting function
+    // pointers passed as arguments to direct uses of functions.  
+    passes.add(createIPSCCPPass());
+
+    // Now that we internalized some globals, see if we can hack on them!
+    passes.add(createGlobalOptimizerPass());
+
+    // Linking modules together can lead to duplicated global constants, only
+    // keep one copy of each constant...
+    passes.add(createConstantMergePass());
+
+    // Remove unused arguments from functions...
+    passes.add(createDeadArgEliminationPass());
+
+    // Reduce the code after globalopt and ipsccp.  Both can open up significant
+    // simplification opportunities, and both can propagate functions through
+    // function pointers.  When this happens, we often have to resolve varargs
+    // calls, etc, so let instcombine do this.
+    passes.add(createInstructionCombiningPass());
+    passes.add(createFunctionInliningPass());     // Inline small functions
+    passes.add(createPruneEHPass());              // Remove dead EH info
+    passes.add(createGlobalDCEPass());            // Remove dead functions
+
+    // If we didn't decide to inline a function, check to see if we can
+    // transform it to pass arguments by value instead of by reference.
+    passes.add(createArgumentPromotionPass());
+
+    // The IPO passes may leave cruft around.  Clean up after them.
+    passes.add(createInstructionCombiningPass());
+    passes.add(createJumpThreadingPass());        // Thread jumps.
+    passes.add(createScalarReplAggregatesPass()); // Break up allocas
+
+    // Run a few AA driven optimizations here and now, to cleanup the code.
+    passes.add(createGlobalsModRefPass());        // IP alias analysis
+    passes.add(createLICMPass());                 // Hoist loop invariants
+    passes.add(createGVNPass());                  // Remove common subexprs
+    passes.add(createMemCpyOptPass());            // Remove dead memcpy's
+    passes.add(createDeadStoreEliminationPass()); // Nuke dead stores
+
+    // Cleanup and simplify the code after the scalar optimizations.
+    passes.add(createInstructionCombiningPass());
+    passes.add(createJumpThreadingPass());        // Thread jumps.
+    passes.add(createPromoteMemoryToRegisterPass()); // Cleanup after threading.
+
+
+    // Delete basic blocks, which optimization passes may have killed...
+    passes.add(createCFGSimplificationPass());
+
+    // Now that we have optimized the program, discard unreachable functions...
+    passes.add(createGlobalDCEPass());
+
+    // Make sure everything is still good.
+    passes.add(createVerifierPass());
+
+    FunctionPassManager* codeGenPasses =
+            new FunctionPassManager(new ExistingModuleProvider(mergedModule));
+
+    codeGenPasses->add(new TargetData(*_target->getTargetData()));
+
+    MachineCodeEmitter* mce = NULL;
+
+    switch (_target->addPassesToEmitFile(*codeGenPasses, out,
+                                      TargetMachine::AssemblyFile, true)) {
+        case FileModel::MachOFile:
+            mce = AddMachOWriter(*codeGenPasses, out, *_target);
+            break;
+        case FileModel::ElfFile:
+            mce = AddELFWriter(*codeGenPasses, out, *_target);
+            break;
+        case FileModel::AsmFile:
+            break;
+        case FileModel::Error:
+        case FileModel::None:
+            errMsg = "target file type not supported";
+            return true;
+    }
+
+    if (_target->addPassesToEmitFileFinish(*codeGenPasses, mce, true)) {
+        errMsg = "target does not support generation of this file type";
+        return true;
+    }
+
+    // Run our queue of passes all at once now, efficiently.
+    passes.run(*mergedModule);
+
+    // Run the code generator, and write assembly file
+    codeGenPasses->doInitialization();
+
+    for (Module::iterator
+           it = mergedModule->begin(), e = mergedModule->end(); it != e; ++it)
+      if (!it->isDeclaration())
+        codeGenPasses->run(*it);
+
+    codeGenPasses->doFinalization();
+    return false; // success
+}
+
+
+
diff --git a/tools/lto/LTOCodeGenerator.h b/tools/lto/LTOCodeGenerator.h
new file mode 100644
index 0000000000..eab076ebc8
--- /dev/null
+++ b/tools/lto/LTOCodeGenerator.h
@@ -0,0 +1,62 @@
+//===-LTOCodeGenerator.h - LLVM Link Time Optimizer -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file declares the LTOCodeGenerator class. 
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LTO_CODE_GENERATOR_H
+#define LTO_CODE_GENERATOR_H
+
+#include "llvm/Linker.h"
+#include "llvm/ADT/StringMap.h"
+
+#include <string>
+
+
+//
+// C++ class which implements the opaque lto_code_gen_t
+//
+class LTOCodeGenerator {
+public:
+    static const char*        getVersionString();
+    
+                            LTOCodeGenerator();
+                            ~LTOCodeGenerator();
+                            
+    bool                addModule(class LTOModule*, std::string& errMsg);
+    bool                setDebugInfo(lto_debug_model, std::string& errMsg);
+    bool                setCodePICModel(lto_codegen_model, std::string& errMsg);
+    void                addMustPreserveSymbol(const char* sym);
+    bool                writeMergedModules(const char* path, 
+                                                           std::string& errMsg);
+    const void*         compile(size_t* length, std::string& errMsg);
+    
+private:
+    bool                generateAssemblyCode(std::ostream& out, 
+                                                        std::string& errMsg);
+    bool                assemble(const std::string& asmPath, 
+                            const std::string& objPath, std::string& errMsg);
+    void                applyScopeRestrictions();
+    bool                determineTarget(std::string& errMsg);
+    
+    typedef llvm::StringMap<uint8_t> StringSet;
+
+    llvm::Linker                _linker;
+    llvm::TargetMachine*        _target;
+    bool                        _emitDwarfDebugInfo;
+    bool                        _scopeRestrictionsDone;
+    lto_codegen_model           _codeModel;
+    StringSet                   _mustPreserveSymbols;
+    llvm::MemoryBuffer*         _nativeObjectFile;
+};
+
+#endif // LTO_CODE_GENERATOR_H
+
diff --git a/tools/lto/LTOModule.cpp b/tools/lto/LTOModule.cpp
new file mode 100644
index 0000000000..333e9ba103
--- /dev/null
+++ b/tools/lto/LTOModule.cpp
@@ -0,0 +1,340 @@
+//===-LTOModule.cpp - LLVM Link Time Optimizer ----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file implements the Link Time Optimization library. This library is 
+// intended to be used by linker to optimize code at link time.
+//
+//===----------------------------------------------------------------------===//
+
+#include "LTOModule.h"
+
+#include "llvm/Module.h"
+#include "llvm/ModuleProvider.h"
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/Bitcode/ReaderWriter.h"
+#include "llvm/Support/SystemUtils.h"
+#include "llvm/Support/Mangler.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/System/Path.h"
+#include "llvm/System/Process.h"
+#include "llvm/Target/SubtargetFeature.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetMachineRegistry.h"
+#include "llvm/Target/TargetAsmInfo.h"
+
+#include <fstream>
+
+using namespace llvm;
+
+bool LTOModule::isBitcodeFile(const void* mem, size_t length)
+{
+    return ( llvm::sys::IdentifyFileType((char*)mem, length) 
+                                            == llvm::sys::Bitcode_FileType );
+}
+
+bool LTOModule::isBitcodeFile(const char* path)
+{
+    return llvm::sys::Path(path).isBitcodeFile();
+}
+
+bool LTOModule::isBitcodeFileForTarget(const void* mem, size_t length,
+                                       const char* triplePrefix) 
+{
+    MemoryBuffer* buffer = makeBuffer(mem, length);
+    if ( buffer == NULL )
+        return false;
+    return isTargetMatch(buffer, triplePrefix);
+}
+
+
+bool LTOModule::isBitcodeFileForTarget(const char* path,
+                                       const char* triplePrefix) 
+{
+    MemoryBuffer *buffer = MemoryBuffer::getFile(path);
+    if (buffer == NULL)
+        return false;
+    return isTargetMatch(buffer, triplePrefix);
+}
+
+// takes ownership of buffer
+bool LTOModule::isTargetMatch(MemoryBuffer* buffer, const char* triplePrefix)
+{
+    OwningPtr<ModuleProvider> mp(getBitcodeModuleProvider(buffer));
+    // on success, mp owns buffer and both are deleted at end of this method
+    if ( !mp ) {
+        delete buffer;
+        return false;
+    }
+    std::string actualTarget = mp->getModule()->getTargetTriple();
+    return ( strncmp(actualTarget.c_str(), triplePrefix, 
+                    strlen(triplePrefix)) == 0);
+}
+
+
+LTOModule::LTOModule(Module* m, TargetMachine* t) 
+ : _module(m), _target(t), _symbolsParsed(false)
+{
+}
+
+LTOModule* LTOModule::makeLTOModule(const char* path, std::string& errMsg)
+{
+    OwningPtr<MemoryBuffer> buffer(MemoryBuffer::getFile(path, &errMsg));
+    if ( !buffer )
+        return NULL;
+    return makeLTOModule(buffer.get(), errMsg);
+}
+
+/// makeBuffer - create a MemoryBuffer from a memory range.
+/// MemoryBuffer requires the byte past end of the buffer to be a zero.
+/// We might get lucky and already be that way, otherwise make a copy.
+/// Also if next byte is on a different page, don't assume it is readable.
+MemoryBuffer* LTOModule::makeBuffer(const void* mem, size_t length)
+{
+    const char* startPtr = (char*)mem;
+    const char* endPtr = startPtr+length;
+    if ( (((uintptr_t)endPtr & (sys::Process::GetPageSize()-1)) == 0) 
+        || (*endPtr != 0) ) 
+        return MemoryBuffer::getMemBufferCopy(startPtr, endPtr);
+    else
+        return MemoryBuffer::getMemBuffer(startPtr, endPtr);
+}
+
+
+LTOModule* LTOModule::makeLTOModule(const void* mem, size_t length, 
+                                                        std::string& errMsg)
+{
+    OwningPtr<MemoryBuffer> buffer(makeBuffer(mem, length));
+    if ( !buffer )
+        return NULL;
+    return makeLTOModule(buffer.get(), errMsg);
+}
+
+/// getFeatureString - Return a string listing the features associated with the
+/// target triple.
+///
+/// FIXME: This is an inelegant way of specifying the features of a
+/// subtarget. It would be better if we could encode this information into the
+/// IR. See <rdar://5972456>.
+std::string getFeatureString(const char *TargetTriple) {
+  SubtargetFeatures Features;
+
+  if (strncmp(TargetTriple, "powerpc-apple-", 14) == 0) {
+    Features.AddFeature("altivec", true);
+  } else if (strncmp(TargetTriple, "powerpc64-apple-", 16) == 0) {
+    Features.AddFeature("64bit", true);
+    Features.AddFeature("altivec", true);
+  }
+
+  return Features.getString();
+}
+
+LTOModule* LTOModule::makeLTOModule(MemoryBuffer* buffer, std::string& errMsg)
+{
+    // parse bitcode buffer
+    OwningPtr<Module> m(ParseBitcodeFile(buffer, &errMsg));
+    if ( !m )
+        return NULL;
+    // find machine architecture for this module
+    const TargetMachineRegistry::entry* march = 
+            TargetMachineRegistry::getClosestStaticTargetForModule(*m, errMsg);
+
+    if ( march == NULL ) 
+        return NULL;
+
+    // construct LTModule, hand over ownership of module and target
+    std::string FeatureStr = getFeatureString(m->getTargetTriple().c_str());
+    TargetMachine* target = march->CtorFn(*m, FeatureStr);
+    return new LTOModule(m.take(), target);
+}
+
+
+const char* LTOModule::getTargetTriple()
+{
+    return _module->getTargetTriple().c_str();
+}
+
+void LTOModule::addDefinedFunctionSymbol(Function* f, Mangler &mangler)
+{
+    // add to list of defined symbols
+    addDefinedSymbol(f, mangler, true); 
+
+    // add external symbols referenced by this function.
+    for (Function::iterator b = f->begin(); b != f->end(); ++b) {
+        for (BasicBlock::iterator i = b->begin(); i != b->end(); ++i) {
+            for (unsigned count = 0, total = i->getNumOperands(); 
+                                        count != total; ++count) {
+                findExternalRefs(i->getOperand(count), mangler);
+            }
+        }
+    }
+}
+
+void LTOModule::addDefinedDataSymbol(GlobalValue* v, Mangler &mangler)
+{    
+    // add to list of defined symbols
+    addDefinedSymbol(v, mangler, false); 
+
+    // add external symbols referenced by this data.
+    for (unsigned count = 0, total = v->getNumOperands();
+                                                count != total; ++count) {
+        findExternalRefs(v->getOperand(count), mangler);
+    }
+}
+
+
+void LTOModule::addDefinedSymbol(GlobalValue* def, Mangler &mangler, 
+                                bool isFunction)
+{    
+    // string is owned by _defines
+    const char* symbolName = ::strdup(mangler.getValueName(def).c_str());
+    
+    // set alignment part log2() can have rounding errors
+    uint32_t align = def->getAlignment();
+    uint32_t attr = align ? CountTrailingZeros_32(def->getAlignment()) : 0;
+    
+    // set permissions part
+    if ( isFunction )
+        attr |= LTO_SYMBOL_PERMISSIONS_CODE;
+    else {
+        GlobalVariable* gv = dyn_cast<GlobalVariable>(def);
+        if ( (gv != NULL) && gv->isConstant() )
+            attr |= LTO_SYMBOL_PERMISSIONS_RODATA;
+        else
+            attr |= LTO_SYMBOL_PERMISSIONS_DATA;
+    }
+    
+    // set definition part 
+    if ( def->hasWeakLinkage() || def->hasLinkOnceLinkage() ) {
+        attr |= LTO_SYMBOL_DEFINITION_WEAK;
+    }
+    else if ( def->hasCommonLinkage()) {
+        attr |= LTO_SYMBOL_DEFINITION_TENTATIVE;
+    }
+    else { 
+        attr |= LTO_SYMBOL_DEFINITION_REGULAR;
+    }
+    
+    // set scope part
+    if ( def->hasHiddenVisibility() )
+        attr |= LTO_SYMBOL_SCOPE_HIDDEN;
+    else if ( def->hasExternalLinkage() || def->hasWeakLinkage() )
+        attr |= LTO_SYMBOL_SCOPE_DEFAULT;
+    else
+        attr |= LTO_SYMBOL_SCOPE_INTERNAL;
+
+    // add to table of symbols
+    NameAndAttributes info;
+    info.name = symbolName;
+    info.attributes = (lto_symbol_attributes)attr;
+    _symbols.push_back(info);
+    _defines[info.name] = 1;
+}
+
+
+void LTOModule::addPotentialUndefinedSymbol(GlobalValue* decl, Mangler &mangler)
+{   
+   const char* name = mangler.getValueName(decl).c_str();
+    // ignore all llvm.* symbols
+    if ( strncmp(name, "llvm.", 5) != 0 ) {
+        _undefines[name] = 1;
+    }
+}
+
+
+
+// Find exeternal symbols referenced by VALUE. This is a recursive function.
+void LTOModule::findExternalRefs(Value* value, Mangler &mangler) {
+
+    if (GlobalValue* gv = dyn_cast<GlobalValue>(value)) {
+        if ( !gv->hasExternalLinkage() )
+            addPotentialUndefinedSymbol(gv, mangler);
+        // If this is a variable definition, do not recursively process
+        // initializer.  It might contain a reference to this variable
+        // and cause an infinite loop.  The initializer will be
+        // processed in addDefinedDataSymbol(). 
+        return;
+    }
+    
+    // GlobalValue, even with InternalLinkage type, may have operands with 
+    // ExternalLinkage type. Do not ignore these operands.
+    if (Constant* c = dyn_cast<Constant>(value)) {
+        // Handle ConstantExpr, ConstantStruct, ConstantArry etc..
+        for (unsigned i = 0, e = c->getNumOperands(); i != e; ++i)
+            findExternalRefs(c->getOperand(i), mangler);
+    }
+}
+
+void LTOModule::lazyParseSymbols()
+{
+    if ( !_symbolsParsed ) {
+        _symbolsParsed = true;
+        
+        // Use mangler to add GlobalPrefix to names to match linker names.
+        Mangler mangler(*_module, _target->getTargetAsmInfo()->getGlobalPrefix());
+
+        // add functions
+        for (Module::iterator f = _module->begin(); f != _module->end(); ++f) {
+            if ( f->isDeclaration() ) 
+                addPotentialUndefinedSymbol(f, mangler);
+            else 
+                addDefinedFunctionSymbol(f, mangler);
+        }
+        
+        // add data 
+        for (Module::global_iterator v = _module->global_begin(), 
+                                    e = _module->global_end(); v !=  e; ++v) {
+            if ( v->isDeclaration() ) 
+                addPotentialUndefinedSymbol(v, mangler);
+            else 
+                addDefinedDataSymbol(v, mangler);
+        }
+
+        // make symbols for all undefines
+        for (StringSet::iterator it=_undefines.begin(); 
+                                                it != _undefines.end(); ++it) {
+            // if this symbol also has a definition, then don't make an undefine
+            // because it is a tentative definition
+            if ( _defines.count(it->getKeyData(), it->getKeyData()+
+                                                  it->getKeyLength()) == 0 ) {
+                NameAndAttributes info;
+                info.name = it->getKeyData();
+                info.attributes = LTO_SYMBOL_DEFINITION_UNDEFINED;
+                _symbols.push_back(info);
+            }
+        }
+    }    
+}
+
+
+uint32_t LTOModule::getSymbolCount()
+{
+    lazyParseSymbols();
+    return _symbols.size();
+}
+
+
+lto_symbol_attributes LTOModule::getSymbolAttributes(uint32_t index)
+{
+    lazyParseSymbols();
+    if ( index < _symbols.size() )
+        return _symbols[index].attributes;
+    else
+        return lto_symbol_attributes(0);
+}
+
+const char* LTOModule::getSymbolName(uint32_t index)
+{
+    lazyParseSymbols();
+    if ( index < _symbols.size() )
+        return _symbols[index].name;
+    else
+        return NULL;
+}
+
diff --git a/tools/lto/LTOModule.h b/tools/lto/LTOModule.h
new file mode 100644
index 0000000000..40f92f9816
--- /dev/null
+++ b/tools/lto/LTOModule.h
@@ -0,0 +1,105 @@
+//===-LTOModule.h - LLVM Link Time Optimizer ------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file declares the LTOModule class. 
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LTO_MODULE_H
+#define LTO_MODULE_H
+
+#include "llvm/Module.h"
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/ADT/StringMap.h"
+
+#include "llvm-c/lto.h"
+
+#include <vector>
+#include <string>
+
+
+// forward references to llvm classes
+namespace llvm {
+    class Mangler;
+    class MemoryBuffer;
+    class GlobalValue;
+    class Value;
+    class Function;
+}
+
+
+//
+// C++ class which implements the opaque lto_module_t
+//
+class LTOModule {
+public:
+
+    static bool              isBitcodeFile(const void* mem, size_t length);
+    static bool              isBitcodeFile(const char* path);
+
+    static bool              isBitcodeFileForTarget(const void* mem, 
+                                    size_t length, const char* triplePrefix);
+
+    static bool              isBitcodeFileForTarget(const char* path, 
+                                                    const char* triplePrefix);
+
+    static LTOModule*        makeLTOModule(const char* path, std::string& errMsg);
+    static LTOModule*        makeLTOModule(const void* mem, size_t length,
+                                                            std::string& errMsg);
+
+    const char*              getTargetTriple();
+    uint32_t                 getSymbolCount();
+    lto_symbol_attributes    getSymbolAttributes(uint32_t index);
+    const char*              getSymbolName(uint32_t index);
+    
+    llvm::Module *           getLLVVMModule() { return _module.get(); }
+
+private:
+                            LTOModule(llvm::Module* m, llvm::TargetMachine* t);
+
+    void                    lazyParseSymbols();
+    void                    addDefinedSymbol(llvm::GlobalValue* def, 
+                                                    llvm::Mangler& mangler, 
+                                                    bool isFunction);
+    void                    addPotentialUndefinedSymbol(llvm::GlobalValue* decl, 
+                                                        llvm::Mangler &mangler);
+    void                    findExternalRefs(llvm::Value* value, 
+                                                llvm::Mangler& mangler);
+    void                    addDefinedFunctionSymbol(llvm::Function* f, 
+                                                        llvm::Mangler &mangler);
+    void                    addDefinedDataSymbol(llvm::GlobalValue* v, 
+                                                        llvm::Mangler &mangler);
+    static bool             isTargetMatch(llvm::MemoryBuffer* memBuffer, 
+                                                    const char* triplePrefix);
+    
+    static LTOModule*       makeLTOModule(llvm::MemoryBuffer* buffer, 
+                                                        std::string& errMsg);
+	static llvm::MemoryBuffer* makeBuffer(const void* mem, size_t length);
+                                                        
+    typedef llvm::StringMap<uint8_t> StringSet;
+    
+    struct NameAndAttributes { 
+        const char*            name; 
+        lto_symbol_attributes  attributes; 
+    };
+
+    llvm::OwningPtr<llvm::Module>           _module;
+    llvm::OwningPtr<llvm::TargetMachine>    _target;
+    bool                                    _symbolsParsed;
+    std::vector<NameAndAttributes>          _symbols;
+    // _defines and _undefines only needed to disambiguate tentative definitions
+    StringSet                               _defines;    
+    StringSet                               _undefines; 
+};
+
+extern std::string getFeatureString(const char *TargetTriple);
+
+#endif // LTO_MODULE_H
+
diff --git a/tools/lto/Makefile b/tools/lto/Makefile
new file mode 100644
index 0000000000..45fa69cd87
--- /dev/null
+++ b/tools/lto/Makefile
@@ -0,0 +1,53 @@
+##===- tools/lto2/Makefile ---------------------------------*- Makefile -*-===##
+# 
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+# 
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../..
+LIBRARYNAME = LTO
+
+# Include this here so we can get the configuration of the targets
+# that have been configured for construction. We have to do this 
+# early so we can set up LINK_COMPONENTS before includeing Makefile.rules
+include $(LEVEL)/Makefile.config
+
+LINK_LIBS_IN_SHARED = 1
+ifeq ($(OS),Darwin)
+  SHARED_LIBRARY = 1
+  BUILD_ARCHIVE = 0
+  DONT_BUILD_RELINKED = 1
+else
+  BUILD_ARCHIVE = 1
+endif
+
+LINK_COMPONENTS := $(TARGETS_TO_BUILD) ipo scalaropts linker bitreader bitwriter
+
+include $(LEVEL)/Makefile.common
+
+ifeq ($(OS),Darwin)
+    # set dylib internal version number to llvmCore submission number
+    ifdef LLVM_SUBMIT_VERSION
+        LLVMLibsOptions := $(LLVMLibsOptions) -Wl,-current_version \
+                        -Wl,$(LLVM_SUBMIT_VERSION).$(LLVM_SUBMIT_SUBVERSION) \
+                        -Wl,-compatibility_version -Wl,1
+    endif
+    # extra options to override libtool defaults 
+    LLVMLibsOptions    := $(LLVMLibsOptions)  \
+                         -no-undefined  -avoid-version \
+                         -Wl,-exported_symbols_list -Wl,$(PROJ_SRC_DIR)/lto.exports \
+                         -Wl,-dead_strip \
+                         -Wl,-seg1addr -Wl,0xE0000000 
+
+    # Mac OS X 10.4 and earlier tools do not allow a second -install_name on command line
+    DARWIN_VERS := $(shell echo $(TARGET_TRIPLE) | sed 's/.*darwin\([0-9]*\).*/\1/')
+    ifneq ($(DARWIN_VERS),8)
+       LLVMLibsOptions    := $(LLVMLibsOptions)  \
+                            -Wl,-install_name \
+                            -Wl,"@executable_path/../lib/lib$(LIBRARYNAME)$(SHLIBEXT)"
+    endif
+      
+endif
diff --git a/tools/lto/lto.cpp b/tools/lto/lto.cpp
new file mode 100644
index 0000000000..f60f7b5ac0
--- /dev/null
+++ b/tools/lto/lto.cpp
@@ -0,0 +1,241 @@
+//===-lto.cpp - LLVM Link Time Optimizer ----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file implements the Link Time Optimization library. This library is 
+// intended to be used by linker to optimize code at link time.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm-c/lto.h"
+
+#include "LTOModule.h"
+#include "LTOCodeGenerator.h"
+
+
+// holds most recent error string
+// *** not thread safe ***
+static std::string sLastErrorString;
+
+
+
+//
+// returns a printable string
+//
+extern const char* lto_get_version()
+{
+    return LTOCodeGenerator::getVersionString();
+}
+
+//
+// returns the last error string or NULL if last operation was successful
+//
+const char* lto_get_error_message()
+{
+    return sLastErrorString.c_str();
+}
+
+
+
+//
+// validates if a file is a loadable object file
+//
+bool lto_module_is_object_file(const char* path)
+{
+    return LTOModule::isBitcodeFile(path);
+}
+
+
+//
+// validates if a file is a loadable object file compilable for requested target
+//
+bool lto_module_is_object_file_for_target(const char* path, 
+                                            const char* target_triplet_prefix)
+{
+    return LTOModule::isBitcodeFileForTarget(path, target_triplet_prefix);
+}
+
+
+//
+// validates if a buffer is a loadable object file
+//
+bool lto_module_is_object_file_in_memory(const void* mem, size_t length)
+{
+    return LTOModule::isBitcodeFile(mem, length);
+}
+
+
+//
+// validates if a buffer is a loadable object file compilable for the target
+//
+bool lto_module_is_object_file_in_memory_for_target(const void* mem, 
+                            size_t length, const char* target_triplet_prefix)
+{
+    return LTOModule::isBitcodeFileForTarget(mem, length, target_triplet_prefix);
+}
+
+
+
+//
+// loads an object file from disk  
+// returns NULL on error (check lto_get_error_message() for details)
+//
+lto_module_t lto_module_create(const char* path)
+{
+     return LTOModule::makeLTOModule(path, sLastErrorString);
+}
+
+
+//
+// loads an object file from memory 
+// returns NULL on error (check lto_get_error_message() for details)
+//
+lto_module_t lto_module_create_from_memory(const void* mem, size_t length)
+{
+     return LTOModule::makeLTOModule(mem, length, sLastErrorString);
+}
+
+
+//
+// frees all memory for a module
+// upon return the lto_module_t is no longer valid
+//
+void lto_module_dispose(lto_module_t mod)
+{
+    delete mod;
+}
+
+
+//
+// returns triplet string which the object module was compiled under
+//
+const char* lto_module_get_target_triple(lto_module_t mod)
+{
+    return mod->getTargetTriple();
+}
+
+
+//
+// returns the number of symbols in the object module
+//
+uint32_t lto_module_get_num_symbols(lto_module_t mod)
+{
+    return mod->getSymbolCount();
+}
+
+//
+// returns the name of the ith symbol in the object module
+//
+const char* lto_module_get_symbol_name(lto_module_t mod, uint32_t index)
+{
+    return mod->getSymbolName(index);
+}
+
+
+//
+// returns the attributes of the ith symbol in the object module
+//
+lto_symbol_attributes lto_module_get_symbol_attribute(lto_module_t mod, 
+                                                            uint32_t index)
+{
+    return mod->getSymbolAttributes(index);
+}
+
+
+
+
+
+//
+// instantiates a code generator
+// returns NULL if there is an error
+//
+lto_code_gen_t lto_codegen_create()
+{
+     return new LTOCodeGenerator();
+}
+
+
+
+//
+// frees all memory for a code generator
+// upon return the lto_code_gen_t is no longer valid
+//
+void lto_codegen_dispose(lto_code_gen_t cg)
+{
+    delete cg;
+}
+
+
+
+//
+// add an object module to the set of modules for which code will be generated
+// returns true on error (check lto_get_error_message() for details)
+//
+bool lto_codegen_add_module(lto_code_gen_t cg, lto_module_t mod)
+{
+    return cg->addModule(mod, sLastErrorString);
+}
+
+
+//
+// sets what if any format of debug info should be generated
+// returns true on error (check lto_get_error_message() for details)
+//
+bool lto_codegen_set_debug_model(lto_code_gen_t cg, lto_debug_model debug)
+{
+    return cg->setDebugInfo(debug, sLastErrorString);
+}
+
+
+//
+// sets what code model to generated
+// returns true on error (check lto_get_error_message() for details)
+//
+bool lto_codegen_set_pic_model(lto_code_gen_t cg, lto_codegen_model model)
+{
+    return cg->setCodePICModel(model, sLastErrorString);
+}
+
+//
+// adds to a list of all global symbols that must exist in the final
+// generated code.  If a function is not listed there, it might be
+// inlined into every usage and optimized away.
+//
+void lto_codegen_add_must_preserve_symbol(lto_code_gen_t cg, const char* symbol)
+{
+    cg->addMustPreserveSymbol(symbol);
+}
+
+
+//
+// writes a new file at the specified path that contains the
+// merged contents of all modules added so far.
+// returns true on error (check lto_get_error_message() for details)
+//
+bool lto_codegen_write_merged_modules(lto_code_gen_t cg, const char* path)
+{
+   return cg->writeMergedModules(path, sLastErrorString);
+}
+
+
+//
+// Generates code for all added modules into one native object file.
+// On sucess returns a pointer to a generated mach-o/ELF buffer and
+// length set to the buffer size.  The buffer is owned by the 
+// lto_code_gen_t and will be freed when lto_codegen_dispose()
+// is called, or lto_codegen_compile() is called again.
+// On failure, returns NULL (check lto_get_error_message() for details).
+//
+extern const void*
+lto_codegen_compile(lto_code_gen_t cg, size_t* length)
+{
+    return cg->compile(length, sLastErrorString);
+}
+
+
+
diff --git a/tools/lto/lto.exports b/tools/lto/lto.exports
new file mode 100644
index 0000000000..415cbbe25b
--- /dev/null
+++ b/tools/lto/lto.exports
@@ -0,0 +1,22 @@
+_lto_get_error_message
+_lto_get_version
+_lto_module_create
+_lto_module_create_from_memory
+_lto_module_get_num_symbols
+_lto_module_get_symbol_attribute
+_lto_module_get_symbol_name
+_lto_module_get_target_triple
+_lto_module_is_object_file
+_lto_module_is_object_file_for_target
+_lto_module_is_object_file_in_memory
+_lto_module_is_object_file_in_memory_for_target
+_lto_module_dispose
+_lto_codegen_add_module
+_lto_codegen_add_must_preserve_symbol
+_lto_codegen_compile
+_lto_codegen_create
+_lto_codegen_dispose
+_lto_codegen_set_debug_model
+_lto_codegen_set_pic_model
+_lto_codegen_write_merged_modules
+