diff options
| -rw-r--r-- | include/klee/Internal/Module/KModule.h | 7 | ||||
| -rw-r--r-- | lib/Core/Executor.cpp | 50 | ||||
| -rw-r--r-- | lib/Core/Executor.h | 5 | ||||
| -rw-r--r-- | lib/Module/Checks.cpp | 10 | ||||
| -rw-r--r-- | lib/Module/InstructionInfoTable.cpp | 88 | ||||
| -rw-r--r-- | lib/Module/KModule.cpp | 45 |
6 files changed, 122 insertions, 83 deletions
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<const llvm::Function*> 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..bf672bb7 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -2729,20 +2729,63 @@ 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; + // 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. + // 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(); + 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<Instruction*, std::string> > 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 { - 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"); @@ -2752,6 +2795,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); 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<Expr> 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/Checks.cpp b/lib/Module/Checks.cpp index 79fd4afc..80b6b245 100644 --- a/lib/Module/Checks.cpp +++ b/lib/Module/Checks.cpp @@ -83,7 +83,12 @@ bool DivCheckPass::runOnModule(Module &M) { divZeroCheckFunction = cast<Function>(fc); } - CallInst::Create(divZeroCheckFunction, denominator, "", &*i); + 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()); moduleChanged = true; } } @@ -138,11 +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::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 301db1ff..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 <map> #include <string> @@ -108,64 +109,35 @@ 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; - - // 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<BasicBlock*, std::pair<const std::string*,unsigned> > - sourceinfo_ty; - sourceinfo_ty sourceInfo; - for (llvm::Function::iterator bbIt = fnIt->begin(), bbie = fnIt->end(); - bbIt != bbie; ++bbIt) { - std::pair<sourceinfo_ty::iterator, bool> - res = sourceInfo.insert(std::make_pair(bbIt, - std::make_pair(initialFile, - initialLine))); - if (!res.second) - continue; - - std::vector<BasicBlock*> 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 Instruction*, unsigned>::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()); + + 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 Instruction*, unsigned>::const_iterator ltit = + lineTable.find(instr); + if (ltit!=lineTable.end()) + assemblyLine = ltit->second; + 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"); + } } } } diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp index d889b51f..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 <tt>klee_div_zero_check()</tt> static void inlineChecks(Module *module, const char * functionName) { - std::vector<CallInst*> checkCalls; + std::vector<CallSite> 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<CallInst>(&*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<InvokeInst>(*i) || isa<CallInst>(*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<CallInst*>::iterator ci = checkCalls.begin(), + for ( std::vector<CallSite>::iterator ci = checkCalls.begin(), cie = checkCalls.end(); ci != cie; ++ci) { @@ -269,6 +266,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 +382,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) |