From 9e16c443aea9104609c5d5f4016ff41190c7dd24 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Wed, 4 Dec 2013 23:35:10 +0100 Subject: Add support for archive and single bc file linking With LLVM 3.3 the linker does not support reading of archive files directly. This brings the support back (based on llvm-mn). Furthermore, linking single bc files or archives with bc and object files mixed is supported as well. --- lib/Module/ModuleUtil.cpp | 85 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 76 insertions(+), 9 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 9ae72936..c1ea274f 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -19,6 +19,9 @@ #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/Support/FileSystem.h" #include "llvm/Support/SourceMgr.h" #include "llvm/Support/DataStream.h" #else @@ -49,15 +52,79 @@ using namespace klee; Module *klee::linkWithLibrary(Module *module, const std::string &libraryName) { #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 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 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(arch.get())) { + for (object::Archive::child_iterator i = a->begin_children(), + e = a->end_children(); i != e; ++i) { + OwningPtr child; + if (i->getAsBinary(child)) { + // Try opening it as a bitcode file. + OwningPtr buff; + if (error_code ec = i->getMemoryBuffer(buff)) + klee_error("Link with library %s failed: %s", libraryName.c_str(), + ec.message().c_str()); + Module *Result = 0; + if (buff) + Result = ParseBitcodeFile(buff.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; + + continue; + } + if (object::ObjectFile *o = dyn_cast(child.get())) { + klee_warning("Link with library: Object file %s in archive %s found. " + "Currently not supported.", + o->getFileName().data(), libraryName.c_str()); + } + } + } + } else if (magic.is_object()) { + OwningPtr obj; + if (object::ObjectFile *o = dyn_cast(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; -- cgit 1.4.1 From 2bddb27b38b4aebee7977afb8de4f5c849384750 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Thu, 23 Jan 2014 19:39:12 +0000 Subject: Improved archive (of bitcode modules) linking performance for LLVM >= 3.3 by effectively reimplementing the linking algorithm used in LLVM <= 3.2. The LLVM specific bitcode archive format has been removed from LLVM >= 3.3 . Now archives are normal system archives that can contain LLVM bitcode modules as well as regular binary object files. The previous commit implemented an approach where ALL the bitcode modules get linked in which can be terribly slow when klee-uclibc gets linked (~600 LLVM modules). Here are the options that I considered to address this: * Use LD with LLVM gold plug-in and call as an external program. I Don't really want to add another dependency to KLEE. It already has enough! * Use the upcomming LLVM linker (lld). Not really an option because at the time of writing there is no support for linking archives of bitcode modules. * Don't use archives at all and just work with modules (i.e. replace uses of llvm-ar with llvm-link and tinker with the flags a little). This isn't so great because the resulting LLVM bitcode module we execute is bigger than it should be. * Reimpelent bitcode archive linking ourselves in a slightly better way. I've gone for the last option This implementation unfortunately loads all bitcode modules into memory first so we can query the module symbols tables. I would prefer to read the archive's index and link in modules on demand but unfortunately although the new Object::Archive interface in LLVM allows iteration over symbols it doesn't provide a way of knowing if that symbol is defined/undefined. This implementation is far from perfect! --- lib/Module/ModuleUtil.cpp | 294 +++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 267 insertions(+), 27 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index c1ea274f..ef2752ed 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -21,7 +21,10 @@ #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 @@ -35,6 +38,7 @@ #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" @@ -49,8 +53,261 @@ 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 &UndefinedSymbols) { + std::set 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... + for (std::set::iterator I = UndefinedSymbols.begin(); + I != UndefinedSymbols.end(); ) + if (DefinedSymbols.count(*I)) + UndefinedSymbols.erase(I++); // This symbol really is defined! + else + { + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Symbol " << *I << " is undefined.\n"); + ++I; // Keep this symbol in the undefined symbols list + } + + // FIXME: Remove KLEE special functions and LLVM intrinsics + // from the list of undefined symbols. HandlerInfo in SpecialFunctionHandler + // needs to be moved so we can use it here. + + DEBUG_WITH_TYPE("klee_linker", dbgs() << "*** Finished computing undefined symbols ***\n"); +} + + + +/*! 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 archive to link the archive with + * \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 archiveModules; + + // Is this efficient? Could we use StringRef instead? + std::set 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 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 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: " <(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 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 (std::vector::iterator M = archiveModules.begin(), ME = archiveModules.end(); + M != ME ;) + { + // Look for the undefined symbols in the composite module + for (std::set::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((**M).getValueSymbolTable().lookup(*S))) + { + if (GV->isDeclaration()) continue; // Not a definition + + Module* moduleToLinkIn = *M; + + + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Found " << GV->getName() << + " in " << (**M).getModuleIdentifier() << "\n"); + + + if (Linker::LinkModules(composite, moduleToLinkIn, Linker::DestroySource, &errorMessage)) + { + // Linking failed + SS << "Linking archive module with composite failed:" << errorMessage; + SS.flush(); + return false; + } + else + { + // Link succeed, now clean up + modulesLoadedOnPass++; + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Linking succeeded.\n"); + + // Note use of postfix operator here so that the iterator gets incremented + // BEFORE we remove it from the vector so the iterator is not invalidated + archiveModules.erase(M++); + delete moduleToLinkIn; + + // We need to recompute the undefined symbols in the composite module + // after linking + GetAllUndefinedSymbols(composite, undefinedSymbols); + + break; // Look for symbols in next module + } + + } + } + + ++M; // Try next module + } + + passCounter++; + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Completed " << passCounter << + " linker passes.\n" << modulesLoadedOnPass << + " modules loaded on the last pass\n" << + archiveModules.size() << " modules left.\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 + for (std::vector::iterator I = archiveModules.begin(), E = archiveModules.end(); + I != E; ++I) + { + delete (*I); + } + + + 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) if (!sys::fs::exists(libraryName)) { klee_error("Link with library %s failed. No such file.", @@ -87,34 +344,15 @@ Module *klee::linkWithLibrary(Module *module, ec.message().c_str()); if (object::Archive *a = dyn_cast(arch.get())) { - for (object::Archive::child_iterator i = a->begin_children(), - e = a->end_children(); i != e; ++i) { - OwningPtr child; - if (i->getAsBinary(child)) { - // Try opening it as a bitcode file. - OwningPtr buff; - if (error_code ec = i->getMemoryBuffer(buff)) - klee_error("Link with library %s failed: %s", libraryName.c_str(), - ec.message().c_str()); - Module *Result = 0; - if (buff) - Result = ParseBitcodeFile(buff.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; - - continue; - } - if (object::ObjectFile *o = dyn_cast(child.get())) { - klee_warning("Link with library: Object file %s in archive %s found. " - "Currently not supported.", - o->getFileName().data(), libraryName.c_str()); - } - } + // 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 obj; if (object::ObjectFile *o = dyn_cast(obj.get())) { @@ -142,6 +380,8 @@ Module *klee::linkWithLibrary(Module *module, #endif } + + Function *klee::getDirectCallTarget(CallSite cs) { Value *v = cs.getCalledValue(); if (Function *f = dyn_cast(v)) { -- cgit 1.4.1 From d3202c9705ebd840051574956c04d12322c8afe6 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 29 Jan 2014 15:24:46 +0000 Subject: Do not consider llvm intrinsics as undefined symbols in KLEE's bitcode archive linker. --- lib/Module/ModuleUtil.cpp | 26 +++++++++++++++++++++----- 1 file changed, 21 insertions(+), 5 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index ef2752ed..1881c817 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -70,6 +70,7 @@ using namespace klee; /// static void GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { + static const std::string llvmIntrinsicPrefix="llvm."; std::set DefinedSymbols; UndefinedSymbols.clear(); DEBUG_WITH_TYPE("klee_linker", dbgs() << "*** Computing undefined symbols ***\n"); @@ -102,18 +103,33 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { if (I->hasName()) DefinedSymbols.insert(I->getName()); - // Prune out any defined symbols from the undefined symbols set... + // Prune out any defined symbols from the undefined symbols set + // and other symbols we don't want to treat as an undefined symbol for (std::set::iterator I = UndefinedSymbols.begin(); I != UndefinedSymbols.end(); ) + { if (DefinedSymbols.count(*I)) + { UndefinedSymbols.erase(I++); // This symbol really is defined! - else + continue; + } + + // Strip out llvm intrinsics + if ( (I->size() >= llvmIntrinsicPrefix.size() ) && + (I->compare(0, llvmIntrinsicPrefix.size(), llvmIntrinsicPrefix) == 0) ) { - DEBUG_WITH_TYPE("klee_linker", dbgs() << "Symbol " << *I << " is undefined.\n"); - ++I; // Keep this symbol in the undefined symbols list + DEBUG_WITH_TYPE("klee_linker", dbgs() << "LLVM intrinsic " << *I << + " has been removed from undefined symbols"<< "\n"); + UndefinedSymbols.erase(I++); + continue; } - // FIXME: Remove KLEE special functions and LLVM intrinsics + // Symbol really is undefined + DEBUG_WITH_TYPE("klee_linker", dbgs() << "Symbol " << *I << " is undefined.\n"); + ++I; // Keep this symbol in the undefined symbols list + } + + // FIXME: Remove KLEE special functions // from the list of undefined symbols. HandlerInfo in SpecialFunctionHandler // needs to be moved so we can use it here. -- cgit 1.4.1 From baa7bff33bc9e69bdd4f0d6621b9c06ff82e11b4 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 29 Jan 2014 17:18:22 +0000 Subject: When using KLEE's built-in Bitcode archive linker do not consider KLEE intrinsics as undefined symbols --- lib/Module/ModuleUtil.cpp | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 1881c817..54cc0429 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" @@ -103,6 +104,7 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { 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 for (std::set::iterator I = UndefinedSymbols.begin(); @@ -124,15 +126,28 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { continue; } + // Remove KLEE intrinsics from set of undefined symbols + bool kleeIntrinsicStripped=false; + for (SpecialFunctionHandler::const_iterator sf = SpecialFunctionHandler::begin(), + se = SpecialFunctionHandler::end(); sf != se; ++sf) + { + if (*I == sf->name) + { + DEBUG_WITH_TYPE("klee_linker", dbgs() << "KLEE intrinsic " << sf->name << + " has been removed from undefined symbols"<< "\n"); + UndefinedSymbols.erase(I++); + kleeIntrinsicStripped=true; + break; + } + } + + if (kleeIntrinsicStripped) continue; + // Symbol really is undefined DEBUG_WITH_TYPE("klee_linker", dbgs() << "Symbol " << *I << " is undefined.\n"); ++I; // Keep this symbol in the undefined symbols list } - // FIXME: Remove KLEE special functions - // from the list of undefined symbols. HandlerInfo in SpecialFunctionHandler - // needs to be moved so we can use it here. - DEBUG_WITH_TYPE("klee_linker", dbgs() << "*** Finished computing undefined symbols ***\n"); } -- cgit 1.4.1 From 129a80e282a4740f479e68c84f8982a42f26ce83 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Thu, 6 Feb 2014 23:49:19 +0100 Subject: Fix access of iterators after they have been invalidated Iterators get invalidated after elements of std::vector/set are deleted. Avoid this by remembering which elements need to be deleted and do it after iterating over the data structure. --- lib/Module/ModuleUtil.cpp | 68 +++++++++++++++++++++++------------------------ 1 file changed, 33 insertions(+), 35 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 54cc0429..51375719 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -46,6 +46,7 @@ #include "llvm/Support/Path.h" #include +#include #include #include #include @@ -107,12 +108,13 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { // 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 RemovedSymbols; for (std::set::iterator I = UndefinedSymbols.begin(); - I != UndefinedSymbols.end(); ) + I != UndefinedSymbols.end(); ++I ) { if (DefinedSymbols.count(*I)) { - UndefinedSymbols.erase(I++); // This symbol really is defined! + RemovedSymbols.push_back(*I); continue; } @@ -122,32 +124,29 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { { DEBUG_WITH_TYPE("klee_linker", dbgs() << "LLVM intrinsic " << *I << " has been removed from undefined symbols"<< "\n"); - UndefinedSymbols.erase(I++); + RemovedSymbols.push_back(*I); continue; } - // Remove KLEE intrinsics from set of undefined symbols - bool kleeIntrinsicStripped=false; - for (SpecialFunctionHandler::const_iterator sf = SpecialFunctionHandler::begin(), - se = SpecialFunctionHandler::end(); sf != se; ++sf) - { - if (*I == sf->name) - { - DEBUG_WITH_TYPE("klee_linker", dbgs() << "KLEE intrinsic " << sf->name << - " has been removed from undefined symbols"<< "\n"); - UndefinedSymbols.erase(I++); - kleeIntrinsicStripped=true; - break; - } - } - - if (kleeIntrinsicStripped) continue; - // Symbol really is undefined DEBUG_WITH_TYPE("klee_linker", dbgs() << "Symbol " << *I << " is undefined.\n"); - ++I; // Keep this symbol in the undefined symbols list } + // 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; + + RemovedSymbols.push_back(sf->name); + DEBUG_WITH_TYPE("klee_linker", dbgs() << "KLEE intrinsic " << sf->name << + " has been removed from undefined symbols"<< "\n"); + } + + for (size_t i = 0, j = RemovedSymbols.size(); i < j; ++i ) + UndefinedSymbols.erase(RemovedSymbols[i]); + DEBUG_WITH_TYPE("klee_linker", dbgs() << "*** Finished computing undefined symbols ***\n"); } @@ -262,33 +261,36 @@ static bool linkBCA(object::Archive* archive, Module* composite, std::string& er unsigned int modulesLoadedOnPass=0; previouslyUndefinedSymbols = undefinedSymbols; - for (std::vector::iterator M = archiveModules.begin(), ME = archiveModules.end(); - M != ME ;) + 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::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? + // klee_warning("S: %s",(*S).c_str()); - if ( GlobalValue* GV = dyn_cast_or_null((**M).getValueSymbolTable().lookup(*S))) + if ( GlobalValue* GV = dyn_cast_or_null(M->getValueSymbolTable().lookup(*S))) { if (GV->isDeclaration()) continue; // Not a definition - Module* moduleToLinkIn = *M; - - DEBUG_WITH_TYPE("klee_linker", dbgs() << "Found " << GV->getName() << - " in " << (**M).getModuleIdentifier() << "\n"); + " in " << M->getModuleIdentifier() << "\n"); - if (Linker::LinkModules(composite, moduleToLinkIn, Linker::DestroySource, &errorMessage)) + if (Linker::LinkModules(composite, M, Linker::DestroySource, &errorMessage)) { // Linking failed SS << "Linking archive module with composite failed:" << errorMessage; SS.flush(); + delete M; return false; } else @@ -297,10 +299,8 @@ static bool linkBCA(object::Archive* archive, Module* composite, std::string& er modulesLoadedOnPass++; DEBUG_WITH_TYPE("klee_linker", dbgs() << "Linking succeeded.\n"); - // Note use of postfix operator here so that the iterator gets incremented - // BEFORE we remove it from the vector so the iterator is not invalidated - archiveModules.erase(M++); - delete moduleToLinkIn; + delete M; + archiveModules[i] = 0; // We need to recompute the undefined symbols in the composite module // after linking @@ -311,8 +311,6 @@ static bool linkBCA(object::Archive* archive, Module* composite, std::string& er } } - - ++M; // Try next module } passCounter++; -- cgit 1.4.1 From 01fd5aa74c7bbfeeaa10d24e7578a59fa1dab3de Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Fri, 14 Feb 2014 12:32:10 +0000 Subject: Correct and tidy up comments. --- lib/Module/ModuleUtil.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 51375719..7b19639e 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -156,7 +156,7 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { * modules into a composite bitcode module * * \param[in] archive Archive of bitcode modules - * \param[in,out] composite The archive to link the archive with + * \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 @@ -275,7 +275,6 @@ static bool linkBCA(object::Archive* archive, Module* composite, std::string& er // 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? - // klee_warning("S: %s",(*S).c_str()); if ( GlobalValue* GV = dyn_cast_or_null(M->getValueSymbolTable().lookup(*S))) { -- cgit 1.4.1 From 360f372b46478d4f94f8696f4931cd85c20beb88 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Fri, 14 Feb 2014 12:36:05 +0000 Subject: Refactor variable name s/RemovedSymbols/SymbolsToRemove/ because "RemovedSymbols" implies that the symbols have already been removed which is misleading because we don't remove until the end. --- lib/Module/ModuleUtil.cpp | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 7b19639e..7a0e18d2 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -108,13 +108,13 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { // 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 RemovedSymbols; + std::vector SymbolsToRemove; for (std::set::iterator I = UndefinedSymbols.begin(); I != UndefinedSymbols.end(); ++I ) { if (DefinedSymbols.count(*I)) { - RemovedSymbols.push_back(*I); + SymbolsToRemove.push_back(*I); continue; } @@ -123,8 +123,8 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { (I->compare(0, llvmIntrinsicPrefix.size(), llvmIntrinsicPrefix) == 0) ) { DEBUG_WITH_TYPE("klee_linker", dbgs() << "LLVM intrinsic " << *I << - " has been removed from undefined symbols"<< "\n"); - RemovedSymbols.push_back(*I); + " has will be removed from undefined symbols"<< "\n"); + SymbolsToRemove.push_back(*I); continue; } @@ -139,13 +139,14 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { if (UndefinedSymbols.find(sf->name) == UndefinedSymbols.end()) continue; - RemovedSymbols.push_back(sf->name); + SymbolsToRemove.push_back(sf->name); DEBUG_WITH_TYPE("klee_linker", dbgs() << "KLEE intrinsic " << sf->name << - " has been removed from undefined symbols"<< "\n"); + " has will be removed from undefined symbols"<< "\n"); } - for (size_t i = 0, j = RemovedSymbols.size(); i < j; ++i ) - UndefinedSymbols.erase(RemovedSymbols[i]); + // 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"); } -- cgit 1.4.1 From 3c49bee67765e3b58ff5cfd2dcc26568509e275b Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Fri, 14 Feb 2014 14:00:11 +0000 Subject: Refactor cleaning up memory in linkBCA() so that if linking fails then clean up is performed. --- lib/Module/ModuleUtil.cpp | 21 ++++++++++++++------- 1 file changed, 14 insertions(+), 7 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 7a0e18d2..349defb3 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -152,6 +152,17 @@ GetAllUndefinedSymbols(Module *M, std::set &UndefinedSymbols) { } +/*! A helper function for linkBCA() which cleans up + * memory allocated by that function. + */ +static void CleanUpLinkBCA(std::vector &archiveModules) +{ + for (std::vector::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 @@ -290,7 +301,7 @@ static bool linkBCA(object::Archive* archive, Module* composite, std::string& er // Linking failed SS << "Linking archive module with composite failed:" << errorMessage; SS.flush(); - delete M; + CleanUpLinkBCA(archiveModules); return false; } else @@ -320,13 +331,9 @@ static bool linkBCA(object::Archive* archive, Module* composite, std::string& er archiveModules.size() << " modules left.\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 - for (std::vector::iterator I = archiveModules.begin(), E = archiveModules.end(); - I != E; ++I) - { - delete (*I); - } + // What's left in archiveModules we don't want to link in so free it + CleanUpLinkBCA(archiveModules); return true; -- cgit 1.4.1 From fd0c6614ec5eb93fb00de029a79de4247511d0ef Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Fri, 14 Feb 2014 14:10:29 +0000 Subject: When running with -debug-only=klee_linker do not report the number of modules left because this information is no longer correct (we no longer shrink the vector). --- lib/Module/ModuleUtil.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib/Module') diff --git a/lib/Module/ModuleUtil.cpp b/lib/Module/ModuleUtil.cpp index 349defb3..58096de4 100644 --- a/lib/Module/ModuleUtil.cpp +++ b/lib/Module/ModuleUtil.cpp @@ -327,8 +327,7 @@ static bool linkBCA(object::Archive* archive, Module* composite, std::string& er passCounter++; DEBUG_WITH_TYPE("klee_linker", dbgs() << "Completed " << passCounter << " linker passes.\n" << modulesLoadedOnPass << - " modules loaded on the last pass\n" << - archiveModules.size() << " modules left.\n"); + " modules loaded on the last pass\n"); } while (undefinedSymbols != previouslyUndefinedSymbols); // Iterate until we reach a fixed point -- cgit 1.4.1