From a329a133d66a86249a3b1ce8025a88f4c0b197c4 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Wed, 13 Nov 2013 23:43:19 +0100 Subject: Simplify acquisition of debug informtion for instruction info with newer LLVM versions With newer LLVM versions (starting with LLVM 2.7) debug information are directly associated as meta data with each instruction. Therefore, debug information can be acquired directly from each instruction. --- lib/Module/InstructionInfoTable.cpp | 23 ++++++++++++++++++++++- 1 file changed, 22 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Module/InstructionInfoTable.cpp b/lib/Module/InstructionInfoTable.cpp index 301db1ff..4285c6b0 100644 --- a/lib/Module/InstructionInfoTable.cpp +++ b/lib/Module/InstructionInfoTable.cpp @@ -111,6 +111,26 @@ InstructionInfoTable::InstructionInfoTable(Module *m) const std::string *initialFile = &dummyString; unsigned initialLine = 0; +#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3) + for (inst_iterator it = inst_begin(fnIt), ie = inst_end(fnIt); it != ie; + ++it) { + const std::string *initialFile = &dummyString; + unsigned initialLine = 0; + Instruction *instr = &*it; + unsigned assemblyLine = 0; + + std::map::const_iterator ltit = + lineTable.find(instr); + if (ltit!=lineTable.end()) + assemblyLine = ltit->second; + getInstructionDebugInfo(instr, initialFile, initialLine); + infos.insert(std::make_pair(instr, + InstructionInfo(id++, + *initialFile, + initialLine, + assemblyLine))); + } +#else // It may be better to look for the closest stoppoint to the entry // following the CFG, but it is not clear that it ever matters in // practice. @@ -118,7 +138,7 @@ InstructionInfoTable::InstructionInfoTable(Module *m) it != ie; ++it) if (getInstructionDebugInfo(&*it, initialFile, initialLine)) break; - + typedef std::map > sourceinfo_ty; sourceinfo_ty sourceInfo; @@ -167,6 +187,7 @@ InstructionInfoTable::InstructionInfoTable(Module *m) } } while (!worklist.empty()); } +#endif } } -- cgit 1.4.1 From 17ec611bb5ada13350a72f2e1de439499128c62f Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Wed, 13 Nov 2013 23:53:46 +0100 Subject: Allow to specify KLEE-internal functions KLEE provides runtime library functions to do detection of bugs (e.g. overflow). This runtime functions are not the location of the bugs but it is the next non-runtime library function from the stack. Use the caller inside that function to indicate where the bug is. --- include/klee/Internal/Module/KModule.h | 7 ++++++ lib/Core/Executor.cpp | 42 ++++++++++++++++++++++++++++++++-- lib/Core/Executor.h | 5 ++++ lib/Module/KModule.cpp | 24 +++++++++++-------- 4 files changed, 67 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/include/klee/Internal/Module/KModule.h b/include/klee/Internal/Module/KModule.h index 86be131b..80672b5e 100644 --- a/include/klee/Internal/Module/KModule.h +++ b/include/klee/Internal/Module/KModule.h @@ -110,6 +110,13 @@ namespace klee { Cell *constantTable; + // Functions which are part of KLEE runtime + std::set internalFunctions; + + private: + // Mark function with functionName as part of the KLEE runtime + void addInternalFunction(const char* functionName); + public: KModule(llvm::Module *_module); ~KModule(); diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index ef55f21f..f01fa4ee 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -2729,16 +2729,54 @@ void Executor::terminateStateOnExit(ExecutionState &state) { terminateState(state); } +const InstructionInfo & Executor::getLastNonKleeInternalInstruction(const ExecutionState &state, + Instruction ** lastInstruction) { + // unroll the stack of the applications state and find + // the last instruction which is not inside a KLEE internal function + ExecutionState::stack_ty::const_reverse_iterator it = state.stack.rbegin(), + itE = state.stack.rend(); + + // don't check beyond the outermost function (i.e. main()) + itE--; + + const InstructionInfo * ii = 0; + if (kmodule->internalFunctions.count(it->kf->function) == 0){ + ii = state.prevPC->info; + *lastInstruction = state.prevPC->inst; + } + + // wind up the stack and check if we are in a KLEE internal function + for (;it != itE; ++it) { + // check calling instruction and if it is contained in a KLEE internal function + const Function * f = (*it->caller).inst->getParent()->getParent(); + if (kmodule->internalFunctions.count(f)){ + ii = 0; + continue; + } + if (!ii){ + ii = (*it->caller).info; + *lastInstruction = (*it->caller).inst; + } + } + + if (!ii) { + // something went wrong, play safe and return the current instruction info + *lastInstruction = state.prevPC->inst; + return *state.prevPC->info; + } + return *ii; +} void Executor::terminateStateOnError(ExecutionState &state, const llvm::Twine &messaget, const char *suffix, const llvm::Twine &info) { std::string message = messaget.str(); static std::set< std::pair > emittedErrors; - const InstructionInfo &ii = *state.prevPC->info; + Instruction * lastInst; + const InstructionInfo &ii = getLastNonKleeInternalInstruction(state, &lastInst); if (EmitAllErrors || - emittedErrors.insert(std::make_pair(state.prevPC->inst, message)).second) { + emittedErrors.insert(std::make_pair(lastInst, message)).second) { if (ii.file != "") { klee_message("ERROR: %s:%d: %s", ii.file.c_str(), ii.line, message.c_str()); } else { diff --git a/lib/Core/Executor.h b/lib/Core/Executor.h index b7318a2c..7d82332c 100644 --- a/lib/Core/Executor.h +++ b/lib/Core/Executor.h @@ -340,6 +340,11 @@ private: /// Get textual information regarding a memory address. std::string getAddressInfo(ExecutionState &state, ref address) const; + // Determines the \param lastInstruction of the \param state which is not KLEE + // internal and returns its InstructionInfo + const InstructionInfo & getLastNonKleeInternalInstruction(const ExecutionState &state, + llvm::Instruction** lastInstruction); + // remove state from queue and delete void terminateState(ExecutionState &state); // call exit handler and terminate state diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp index d889b51f..4bc10604 100644 --- a/lib/Module/KModule.cpp +++ b/lib/Module/KModule.cpp @@ -269,6 +269,17 @@ static void inlineChecks(Module *module, const char * functionName) { DEBUG( klee_message("Tried to inline calls to %s. %u successes, %u failures",functionName, successCount, failCount) ); } +void KModule::addInternalFunction(const char* functionName){ + Function* internalFunction = module->getFunction(functionName); + if (!internalFunction) { + DEBUG_WITH_TYPE("KModule", klee_warning( + "Failed to add internal function %s. Not found.", functionName)); + return ; + } + DEBUG( klee_message("Added function %s.",functionName)); + internalFunctions.insert(internalFunction); +} + void KModule::prepare(const Interpreter::ModuleOptions &opts, InterpreterHandler *ih) { if (!MergeAtExit.empty()) { @@ -374,17 +385,12 @@ void KModule::prepare(const Interpreter::ModuleOptions &opts, #endif module = linkWithLibrary(module, path.c_str()); - /* In order for KLEE to report ALL errors at instrumented - * locations the instrumentation call (e.g. "klee_div_zero_check") - * must be inlined. Otherwise one of the instructions in the - * instrumentation function will be used as the the location of - * the error which means that the error cannot be recorded again - * ( unless -emit-all-errors is used). - */ + // Add internal functions which are not used to check if instructions + // have been already visited if (opts.CheckDivZero) - inlineChecks(module, "klee_div_zero_check"); + addInternalFunction("klee_div_zero_check"); if (opts.CheckOvershift) - inlineChecks(module, "klee_overshift_check"); + addInternalFunction("klee_overshift_check"); // Needs to happen after linking (since ctors/dtors can be modified) -- cgit 1.4.1 From f8a0a98bfdeb3c9bb903a549042c2da322c753b5 Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Wed, 13 Nov 2013 23:57:41 +0100 Subject: Replicate debug information from checked instructions to checker call. --- lib/Module/Checks.cpp | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/Module/Checks.cpp b/lib/Module/Checks.cpp index 79fd4afc..bf37eea2 100644 --- a/lib/Module/Checks.cpp +++ b/lib/Module/Checks.cpp @@ -82,8 +82,13 @@ bool DivCheckPass::runOnModule(Module &M) { NULL); divZeroCheckFunction = cast(fc); } - +#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0) + CallInst * ci = +#endif CallInst::Create(divZeroCheckFunction, denominator, "", &*i); +#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0) + ci->setDebugLoc(binOp->getDebugLoc()); +#endif moduleChanged = true; } } @@ -139,7 +144,9 @@ bool OvershiftCheckPass::runOnModule(Module &M) { // Inject CallInstr to check if overshifting possible #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0) - CallInst::Create(overshiftCheckFunction, args, "", &*i); + CallInst * ci = CallInst::Create(overshiftCheckFunction, args, "", &*i); + // set debug information from binary operand to preserve it + ci->setDebugLoc(binOp->getDebugLoc()); #else CallInst::Create(overshiftCheckFunction, args.begin(), args.end(), "", &*i); #endif -- cgit 1.4.1 From 9809e76ec82c7bd70b8cb8b735be294ffb96d7bc Mon Sep 17 00:00:00 2001 From: Martin Nowack Date: Thu, 14 Nov 2013 08:10:07 +0100 Subject: Optimize inlineChecks function * Just iterate over the instructions which use the function to be inlined * Handle each callsite (e.g. CallInst and InvokeInst) --- lib/Module/KModule.cpp | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-) (limited to 'lib') diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp index 4bc10604..34e5f60c 100644 --- a/lib/Module/KModule.cpp +++ b/lib/Module/KModule.cpp @@ -229,7 +229,7 @@ static void forceImport(Module *m, const char *name, LLVM_TYPE_Q Type *retType, /// It is intended that this function be used for inling calls to /// check functions like klee_div_zero_check() static void inlineChecks(Module *module, const char * functionName) { - std::vector checkCalls; + std::vector checkCalls; Function* runtimeCheckCall = module->getFunction(functionName); if (runtimeCheckCall == 0) { @@ -237,22 +237,19 @@ static void inlineChecks(Module *module, const char * functionName) { return; } - // Iterate through instructions in module and collect all - // call instructions to "functionName" that we care about. - for (Module::iterator f = module->begin(), fe = module->end(); f != fe; ++f) { - for (inst_iterator i=inst_begin(f), ie = inst_end(f); i != ie; ++i) { - if ( CallInst* ci = dyn_cast(&*i) ) - { - if ( ci->getCalledFunction() == runtimeCheckCall) - checkCalls.push_back(ci); - } + for (Value::use_iterator i = runtimeCheckCall->use_begin(), + e = runtimeCheckCall->use_end(); i != e; ++i) + if (isa(*i) || isa(*i)) { + CallSite cs(*i); + if (!cs.getCalledFunction()) + continue; + checkCalls.push_back(cs); } - } unsigned int successCount=0; unsigned int failCount=0; InlineFunctionInfo IFI(0,0); - for ( std::vector::iterator ci = checkCalls.begin(), + for ( std::vector::iterator ci = checkCalls.begin(), cie = checkCalls.end(); ci != cie; ++ci) { -- cgit 1.4.1 From 58de8cdce75bcee981ec813c57fb2ed7e83e9878 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 11 Dec 2013 16:01:51 +0000 Subject: Remove old algorithm for acquiring debug info. Since LLVM 2.7, debug information is attached directly to most instructions so the simpler algorithm added in 5ecfd6e2fd5becc10be355b3a20d014e76e40518 can be used. Since support for LLVM version < 2.9 has been removed the old algorithm should be removed. This has been tested with LLVM 2.9 and LLVM 3.3 --- lib/Module/Checks.cpp | 19 ++++++------ lib/Module/InstructionInfoTable.cpp | 61 ------------------------------------- 2 files changed, 10 insertions(+), 70 deletions(-) (limited to 'lib') diff --git a/lib/Module/Checks.cpp b/lib/Module/Checks.cpp index bf37eea2..80b6b245 100644 --- a/lib/Module/Checks.cpp +++ b/lib/Module/Checks.cpp @@ -82,13 +82,13 @@ bool DivCheckPass::runOnModule(Module &M) { NULL); divZeroCheckFunction = cast(fc); } -#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0) - CallInst * ci = -#endif - CallInst::Create(divZeroCheckFunction, denominator, "", &*i); -#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0) + + CallInst * ci = CallInst::Create(divZeroCheckFunction, denominator, "", &*i); + + // Set debug location of checking call to that of the div/rem + // operation so error locations are reported in the correct + // location. ci->setDebugLoc(binOp->getDebugLoc()); -#endif moduleChanged = true; } } @@ -143,13 +143,14 @@ bool OvershiftCheckPass::runOnModule(Module &M) { } // Inject CallInstr to check if overshifting possible + CallInst* ci = #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0) - CallInst * ci = CallInst::Create(overshiftCheckFunction, args, "", &*i); - // set debug information from binary operand to preserve it - ci->setDebugLoc(binOp->getDebugLoc()); + CallInst::Create(overshiftCheckFunction, args, "", &*i); #else CallInst::Create(overshiftCheckFunction, args.begin(), args.end(), "", &*i); #endif + // set debug information from binary operand to preserve it + ci->setDebugLoc(binOp->getDebugLoc()); moduleChanged = true; } } diff --git a/lib/Module/InstructionInfoTable.cpp b/lib/Module/InstructionInfoTable.cpp index 4285c6b0..204457d2 100644 --- a/lib/Module/InstructionInfoTable.cpp +++ b/lib/Module/InstructionInfoTable.cpp @@ -108,10 +108,7 @@ InstructionInfoTable::InstructionInfoTable(Module *m) for (Module::iterator fnIt = m->begin(), fn_ie = m->end(); fnIt != fn_ie; ++fnIt) { - const std::string *initialFile = &dummyString; - unsigned initialLine = 0; -#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3) for (inst_iterator it = inst_begin(fnIt), ie = inst_end(fnIt); it != ie; ++it) { const std::string *initialFile = &dummyString; @@ -130,64 +127,6 @@ InstructionInfoTable::InstructionInfoTable(Module *m) initialLine, assemblyLine))); } -#else - // It may be better to look for the closest stoppoint to the entry - // following the CFG, but it is not clear that it ever matters in - // practice. - for (inst_iterator it = inst_begin(fnIt), ie = inst_end(fnIt); - it != ie; ++it) - if (getInstructionDebugInfo(&*it, initialFile, initialLine)) - break; - - typedef std::map > - sourceinfo_ty; - sourceinfo_ty sourceInfo; - for (llvm::Function::iterator bbIt = fnIt->begin(), bbie = fnIt->end(); - bbIt != bbie; ++bbIt) { - std::pair - res = sourceInfo.insert(std::make_pair(bbIt, - std::make_pair(initialFile, - initialLine))); - if (!res.second) - continue; - - std::vector worklist; - worklist.push_back(bbIt); - - do { - BasicBlock *bb = worklist.back(); - worklist.pop_back(); - - sourceinfo_ty::iterator si = sourceInfo.find(bb); - assert(si != sourceInfo.end()); - const std::string *file = si->second.first; - unsigned line = si->second.second; - - for (BasicBlock::iterator it = bb->begin(), ie = bb->end(); - it != ie; ++it) { - Instruction *instr = it; - unsigned assemblyLine = 0; - std::map::const_iterator ltit = - lineTable.find(instr); - if (ltit!=lineTable.end()) - assemblyLine = ltit->second; - getInstructionDebugInfo(instr, file, line); - infos.insert(std::make_pair(instr, - InstructionInfo(id++, - *file, - line, - assemblyLine))); - } - - for (succ_iterator it = succ_begin(bb), ie = succ_end(bb); - it != ie; ++it) { - if (sourceInfo.insert(std::make_pair(*it, - std::make_pair(file, line))).second) - worklist.push_back(*it); - } - } while (!worklist.empty()); - } -#endif } } -- cgit 1.4.1 From 6829fb93ce36afc852c97928b94ab9ad5e221aec Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 11 Dec 2013 16:23:10 +0000 Subject: Only record debug info into InstructionInfoTable if debug information is actually available. In addition if doing a DEBUG build then the command line flag -debug-only=klee_missing_debug shows the instructions missing debug information and -debug-only=klee_obtained_debug show the instructions with debug information. --- lib/Module/InstructionInfoTable.cpp | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/Module/InstructionInfoTable.cpp b/lib/Module/InstructionInfoTable.cpp index 204457d2..19d7e511 100644 --- a/lib/Module/InstructionInfoTable.cpp +++ b/lib/Module/InstructionInfoTable.cpp @@ -33,6 +33,7 @@ #include "llvm/Analysis/DebugInfo.h" #endif #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Support/Debug.h" #include #include @@ -120,12 +121,23 @@ InstructionInfoTable::InstructionInfoTable(Module *m) lineTable.find(instr); if (ltit!=lineTable.end()) assemblyLine = ltit->second; - getInstructionDebugInfo(instr, initialFile, initialLine); - infos.insert(std::make_pair(instr, - InstructionInfo(id++, - *initialFile, - initialLine, - assemblyLine))); + if (getInstructionDebugInfo(instr, initialFile, initialLine)) + { + infos.insert(std::make_pair(instr, + InstructionInfo(id++, + *initialFile, + initialLine, + assemblyLine))); + DEBUG_WITH_TYPE("klee_obtained_debug", dbgs() << + "Instruction: \"" << *instr << "\" (assembly line " << assemblyLine << + ") has debug location " << *initialFile << ":" << initialLine << "\n"); + } + else + { + DEBUG_WITH_TYPE("klee_missing_debug", dbgs() << + "Instruction: \"" << *instr << "\" (assembly line " << assemblyLine << + ") is missing debug info.\n"); + } } } } -- cgit 1.4.1 From 92a6ba10d2c125f5301613369a0f17856e637808 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 11 Dec 2013 16:39:35 +0000 Subject: If error location information is missing be explicit about it. This is more helpful because often the next message is "Now ignoring error at this location". Which is slightly confusing when no location is shown. --- lib/Core/Executor.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index f01fa4ee..371aa7f1 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -2780,7 +2780,7 @@ void Executor::terminateStateOnError(ExecutionState &state, if (ii.file != "") { klee_message("ERROR: %s:%d: %s", ii.file.c_str(), ii.line, message.c_str()); } else { - klee_message("ERROR: %s", message.c_str()); + klee_message("ERROR: (location information missing) %s", message.c_str()); } if (!EmitAllErrors) klee_message("NOTE: now ignoring this error at this location"); -- cgit 1.4.1 From cca3536a76d877c5441e54e093a5808cd05c4f86 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 11 Dec 2013 16:45:42 +0000 Subject: When writing stack traces for bugs write the location in the assembly.ll file as well. --- lib/Core/Executor.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index 371aa7f1..767a5602 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -2790,6 +2790,7 @@ void Executor::terminateStateOnError(ExecutionState &state, if (ii.file != "") { msg << "File: " << ii.file << "\n"; msg << "Line: " << ii.line << "\n"; + msg << "assembly.ll line: " << ii.assemblyLine << "\n"; } msg << "Stack: \n"; state.dumpStack(msg); -- cgit 1.4.1 From 5b2dcbbcf91062e463a040d58302706c612f03bd Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Fri, 13 Dec 2013 19:07:30 +0000 Subject: Added a few comments to Executor::getLastNonKleeInternalInstruction() emphasising that the function cannot be returned from early. --- lib/Core/Executor.cpp | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index 767a5602..bf672bb7 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -2743,9 +2743,14 @@ const InstructionInfo & Executor::getLastNonKleeInternalInstruction(const Execut if (kmodule->internalFunctions.count(it->kf->function) == 0){ ii = state.prevPC->info; *lastInstruction = state.prevPC->inst; + // Cannot return yet because even though + // it->function is not an internal function it might of + // been called from an internal function. } - // wind up the stack and check if we are in a KLEE internal function + // Wind up the stack and check if we are in a KLEE internal function. + // We visit the entire stack because we want to return a CallInstruction + // that was not reached via any KLEE internal functions. for (;it != itE; ++it) { // check calling instruction and if it is contained in a KLEE internal function const Function * f = (*it->caller).inst->getParent()->getParent(); -- cgit 1.4.1