diff options
Diffstat (limited to 'lib/Module/ModuleUtil.cpp')
| -rw-r--r-- | lib/Module/ModuleUtil.cpp | 360 |
1 files changed, 351 insertions, 9 deletions
diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 9ae72936..58096de4 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -11,6 +11,7 @@ #include "klee/Config/Version.h" // FIXME: This does not belong here. #include "../Core/Common.h" +#include "../Core/SpecialFunctionHandler.h" #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3) #include "llvm/Bitcode/ReaderWriter.h" @@ -19,6 +20,12 @@ #include "llvm/IR/IntrinsicInst.h" #include "llvm/IRReader/IRReader.h" #include "llvm/IR/Module.h" +#include "llvm/Object/Archive.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Object/Error.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/raw_os_ostream.h" +#include "llvm/IR/ValueSymbolTable.h" #include "llvm/Support/SourceMgr.h" #include "llvm/Support/DataStream.h" #else @@ -32,12 +39,14 @@ #include "llvm/Assembly/AssemblyAnnotationWriter.h" #include "llvm/Support/CFG.h" #include "llvm/Support/CallSite.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/InstIterator.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Support/Path.h" #include <map> +#include <set> #include <iostream> #include <fstream> #include <sstream> @@ -46,18 +55,349 @@ using namespace llvm; using namespace klee; +#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3) +/// Based on GetAllUndefinedSymbols() from LLVM3.2 +/// +/// GetAllUndefinedSymbols - calculates the set of undefined symbols that still +/// exist in an LLVM module. This is a bit tricky because there may be two +/// symbols with the same name but different LLVM types that will be resolved to +/// each other but aren't currently (thus we need to treat it as resolved). +/// +/// Inputs: +/// M - The module in which to find undefined symbols. +/// +/// Outputs: +/// UndefinedSymbols - A set of C++ strings containing the name of all +/// undefined symbols. +/// +static void +GetAllUndefinedSymbols(Module *M, std::set<std::string> &UndefinedSymbols) { + static const std::string llvmIntrinsicPrefix="llvm."; + std::set<std::string> DefinedSymbols; + UndefinedSymbols.clear(); + DEBUG_WITH_TYPE("klee_linker", dbgs() << "*** Computing undefined symbols ***\n"); + + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + if (I->hasName()) { + if (I->isDeclaration()) + UndefinedSymbols.insert(I->getName()); + else if (!I->hasLocalLinkage()) { + assert(!I->hasDLLImportLinkage() + && "Found dllimported non-external symbol!"); + DefinedSymbols.insert(I->getName()); + } + } + + for (Module::global_iterator I = M->global_begin(), E = M->global_end(); + I != E; ++I) + if (I->hasName()) { + if (I->isDeclaration()) + UndefinedSymbols.insert(I->getName()); + else if (!I->hasLocalLinkage()) { + assert(!I->hasDLLImportLinkage() + && "Found dllimported non-external symbol!"); + DefinedSymbols.insert(I->getName()); + } + } + + for (Module::alias_iterator I = M->alias_begin(), E = M->alias_end(); + I != E; ++I) + if (I->hasName()) + DefinedSymbols.insert(I->getName()); + + + // Prune out any defined symbols from the undefined symbols set + // and other symbols we don't want to treat as an undefined symbol + std::vector<std::string> SymbolsToRemove; + for (std::set<std::string>::iterator I = UndefinedSymbols.begin(); + I != UndefinedSymbols.end(); ++I ) + { + if (DefinedSymbols.count(*I)) + { + SymbolsToRemove.push_back(*I); + continue; + } + + // Strip out llvm intrinsics + if ( (I->size() >= llvmIntrinsicPrefix.size() ) && + (I->compare(0, llvmIntrinsicPrefix.size(), llvmIntrinsicPrefix) == 0) ) + { + DEBUG_WITH_TYPE("klee_linker", dbgs() << "LLVM intrinsic " << *I << + " has will be removed from undefined symbols"<< "\n"); + SymbolsToRemove.push_back(*I); + continue; + } + + // Symbol really is undefined + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Symbol " << *I << " is undefined.\n"); + } + + // Remove KLEE intrinsics from set of undefined symbols + for (SpecialFunctionHandler::const_iterator sf = SpecialFunctionHandler::begin(), + se = SpecialFunctionHandler::end(); sf != se; ++sf) + { + if (UndefinedSymbols.find(sf->name) == UndefinedSymbols.end()) + continue; + + SymbolsToRemove.push_back(sf->name); + DEBUG_WITH_TYPE("klee_linker", dbgs() << "KLEE intrinsic " << sf->name << + " has will be removed from undefined symbols"<< "\n"); + } + + // Now remove the symbols from undefined set. + for (size_t i = 0, j = SymbolsToRemove.size(); i < j; ++i ) + UndefinedSymbols.erase(SymbolsToRemove[i]); + + DEBUG_WITH_TYPE("klee_linker", dbgs() << "*** Finished computing undefined symbols ***\n"); +} + + +/*! A helper function for linkBCA() which cleans up + * memory allocated by that function. + */ +static void CleanUpLinkBCA(std::vector<Module*> &archiveModules) +{ + for (std::vector<Module*>::iterator I = archiveModules.begin(), E = archiveModules.end(); + I != E; ++I) + { + delete (*I); + } +} + +/*! A helper function for klee::linkWithLibrary() that links in an archive of bitcode + * modules into a composite bitcode module + * + * \param[in] archive Archive of bitcode modules + * \param[in,out] composite The bitcode module to link against the archive + * \param[out] errorMessage Set to an error message if linking fails + * + * \return True if linking succeeds otherwise false + */ +static bool linkBCA(object::Archive* archive, Module* composite, std::string& errorMessage) +{ + llvm::raw_string_ostream SS(errorMessage); + std::vector<Module*> archiveModules; + + // Is this efficient? Could we use StringRef instead? + std::set<std::string> undefinedSymbols; + GetAllUndefinedSymbols(composite, undefinedSymbols); + + if (undefinedSymbols.size() == 0) + { + // Nothing to do + DEBUG_WITH_TYPE("klee_linker", dbgs() << "No undefined symbols. Not linking anything in!\n"); + return true; + } + + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Loading modules\n"); + // Load all bitcode files in to memory so we can examine their symbols + for (object::Archive::child_iterator AI = archive->begin_children(), + AE = archive->end_children(); AI != AE; ++AI) + { + + StringRef memberName; + error_code ec = AI->getName(memberName); + + if ( ec == errc::success ) + { + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Loading archive member " << memberName << "\n"); + } + else + { + errorMessage="Archive member does not have a name!\n"; + return false; + } + + OwningPtr<object::Binary> child; + ec = AI->getAsBinary(child); + if (ec != object::object_error::success) + { + // If we can't open as a binary object file its hopefully a bitcode file + + OwningPtr<MemoryBuffer> buff; // Once this is destroyed will Module still be valid?? + Module *Result = 0; + + if (error_code ec = AI->getMemoryBuffer(buff)) + { + SS << "Failed to get MemoryBuffer: " <<ec.message(); + SS.flush(); + return false; + } + + if (buff) + { + // FIXME: Maybe load bitcode file lazily? Then if we need to link, materialise the module + Result = ParseBitcodeFile(buff.get(), getGlobalContext(), &errorMessage); + + if(!Result) + { + SS << "Loading module failed : " << errorMessage << "\n"; + SS.flush(); + return false; + } + archiveModules.push_back(Result); + } + else + { + errorMessage="Buffer was NULL!"; + return false; + } + + } + else if (object::ObjectFile *o = dyn_cast<object::ObjectFile>(child.get())) + { + SS << "Object file " << o->getFileName().data() << + " in archive is not supported"; + SS.flush(); + return false; + } + else + { + SS << "Loading archive child with error "<< ec.message(); + SS.flush(); + return false; + } + + } + + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Loaded " << archiveModules.size() << " modules\n"); + + + std::set<std::string> previouslyUndefinedSymbols; + + // Walk through the modules looking for definitions of undefined symbols + // if we find a match we should link that module in. + unsigned int passCounter=0; + do + { + unsigned int modulesLoadedOnPass=0; + previouslyUndefinedSymbols = undefinedSymbols; + + for (size_t i = 0, j = archiveModules.size(); i < j; ++i) + { + // skip empty archives + if (archiveModules[i] == 0) + continue; + Module * M = archiveModules[i]; + // Look for the undefined symbols in the composite module + for (std::set<std::string>::iterator S = undefinedSymbols.begin(), SE = undefinedSymbols.end(); + S != SE; ++S) + { + + // FIXME: We aren't handling weak symbols here! + // However the algorithm used in LLVM3.2 didn't seem to either + // so maybe it doesn't matter? + + if ( GlobalValue* GV = dyn_cast_or_null<GlobalValue>(M->getValueSymbolTable().lookup(*S))) + { + if (GV->isDeclaration()) continue; // Not a definition + + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Found " << GV->getName() << + " in " << M->getModuleIdentifier() << "\n"); + + + if (Linker::LinkModules(composite, M, Linker::DestroySource, &errorMessage)) + { + // Linking failed + SS << "Linking archive module with composite failed:" << errorMessage; + SS.flush(); + CleanUpLinkBCA(archiveModules); + return false; + } + else + { + // Link succeed, now clean up + modulesLoadedOnPass++; + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Linking succeeded.\n"); + + delete M; + archiveModules[i] = 0; + + // We need to recompute the undefined symbols in the composite module + // after linking + GetAllUndefinedSymbols(composite, undefinedSymbols); + + break; // Look for symbols in next module + } + + } + } + } + + passCounter++; + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Completed " << passCounter << + " linker passes.\n" << modulesLoadedOnPass << + " modules loaded on the last pass\n"); + } while (undefinedSymbols != previouslyUndefinedSymbols); // Iterate until we reach a fixed point + + + // What's left in archiveModules we don't want to link in so free it + CleanUpLinkBCA(archiveModules); + + return true; + +} +#endif + + Module *klee::linkWithLibrary(Module *module, const std::string &libraryName) { +DEBUG_WITH_TYPE("klee_linker", dbgs() << "Linking file " << libraryName << "\n"); #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3) - SMDiagnostic err; - std::string err_str; - sys::Path libraryPath(libraryName); - Module *new_mod = ParseIRFile(libraryPath.str(), err, -module->getContext()); - - if (Linker::LinkModules(module, new_mod, Linker::DestroySource, -&err_str)) { - klee_error("Linking library %s failed", libraryName.c_str()); + if (!sys::fs::exists(libraryName)) { + klee_error("Link with library %s failed. No such file.", + libraryName.c_str()); + } + + OwningPtr<MemoryBuffer> Buffer; + if (error_code ec = MemoryBuffer::getFile(libraryName,Buffer)) { + klee_error("Link with library %s failed: %s", libraryName.c_str(), + ec.message().c_str()); + } + + sys::fs::file_magic magic = sys::fs::identify_magic(Buffer->getBuffer()); + + LLVMContext &Context = getGlobalContext(); + std::string ErrorMessage; + + if (magic == sys::fs::file_magic::bitcode) { + Module *Result = 0; + Result = ParseBitcodeFile(Buffer.get(), Context, &ErrorMessage); + + + if (!Result || Linker::LinkModules(module, Result, Linker::DestroySource, + &ErrorMessage)) + klee_error("Link with library %s failed: %s", libraryName.c_str(), + ErrorMessage.c_str()); + + delete Result; + + } else if (magic == sys::fs::file_magic::archive) { + OwningPtr<object::Binary> arch; + if (error_code ec = object::createBinary(Buffer.take(), arch)) + klee_error("Link with library %s failed: %s", libraryName.c_str(), + ec.message().c_str()); + + if (object::Archive *a = dyn_cast<object::Archive>(arch.get())) { + // Handle in helper + if (!linkBCA(a, module, ErrorMessage)) + klee_error("Link with library %s failed: %s", libraryName.c_str(), + ErrorMessage.c_str()); + } + else { + klee_error("Link with library %s failed: Cast to archive failed", libraryName.c_str()); + } + + } else if (magic.is_object()) { + OwningPtr<object::Binary> obj; + if (object::ObjectFile *o = dyn_cast<object::ObjectFile>(obj.get())) { + klee_warning("Link with library: Object file %s in archive %s found. " + "Currently not supported.", + o->getFileName().data(), libraryName.c_str()); + } + } else { + klee_error("Link with library %s failed: Unrecognized file type.", + libraryName.c_str()); } return module; @@ -75,6 +415,8 @@ module->getContext()); #endif } + + Function *klee::getDirectCallTarget(CallSite cs) { Value *v = cs.getCalledValue(); if (Function *f = dyn_cast<Function>(v)) { |