diff options
| -rw-r--r-- | include/klee/util/GetElementPtrTypeIterator.h | 150 | ||||
| -rw-r--r-- | lib/Core/Executor.cpp | 64 | ||||
| -rw-r--r-- | lib/Core/Executor.h | 3 | ||||
| -rw-r--r-- | lib/Core/ExecutorUtil.cpp | 3 | ||||
| -rw-r--r-- | lib/Module/KModule.cpp | 2 | ||||
| -rw-r--r-- | test/Feature/InsertExtractValue.ll | 32 |
6 files changed, 244 insertions, 10 deletions
diff --git a/include/klee/util/GetElementPtrTypeIterator.h b/include/klee/util/GetElementPtrTypeIterator.h new file mode 100644 index 00000000..690aaa95 --- /dev/null +++ b/include/klee/util/GetElementPtrTypeIterator.h @@ -0,0 +1,150 @@ +//===- klee/util/GetElementPtrTypeIterator.h --------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements an iterator for walking through the types indexed by +// getelementptr, insertvalue and extractvalue instructions. +// +// It is an enhanced version of llvm::gep_type_iterator which only handles +// getelementptr. +// +//===----------------------------------------------------------------------===// + +#ifndef KLEE_UTIL_GETELEMENTPTRTYPE_H +#define KLEE_UTIL_GETELEMENTPTRTYPE_H + +#include "llvm/User.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Instructions.h" + +namespace klee { + template<typename ItTy = llvm::User::const_op_iterator> + class generic_gep_type_iterator + : public std::iterator<std::forward_iterator_tag, const llvm::Type *, ptrdiff_t> { + typedef std::iterator<std::forward_iterator_tag, + const llvm::Type *, ptrdiff_t> super; + + ItTy OpIt; + const llvm::Type *CurTy; + generic_gep_type_iterator() {} + + llvm::Value *asValue(llvm::Value *V) const { return V; } + llvm::Value *asValue(unsigned U) const { + return llvm::ConstantInt::get(CurTy->getContext(), llvm::APInt(32, U)); + } + + public: + + static generic_gep_type_iterator begin(const llvm::Type *Ty, ItTy It) { + generic_gep_type_iterator I; + I.CurTy = Ty; + I.OpIt = It; + return I; + } + static generic_gep_type_iterator end(ItTy It) { + generic_gep_type_iterator I; + I.CurTy = 0; + I.OpIt = It; + return I; + } + + bool operator==(const generic_gep_type_iterator& x) const { + return OpIt == x.OpIt; + } + bool operator!=(const generic_gep_type_iterator& x) const { + return !operator==(x); + } + + const llvm::Type *operator*() const { + return CurTy; + } + + const llvm::Type *getIndexedType() const { + const llvm::CompositeType *CT = cast<llvm::CompositeType>(CurTy); + return CT->getTypeAtIndex(getOperand()); + } + + // This is a non-standard operator->. It allows you to call methods on the + // current type directly. + const llvm::Type *operator->() const { return operator*(); } + + llvm::Value *getOperand() const { return asValue(*OpIt); } + + generic_gep_type_iterator& operator++() { // Preincrement + if (const llvm::CompositeType *CT = dyn_cast<llvm::CompositeType>(CurTy)) { + CurTy = CT->getTypeAtIndex(getOperand()); + } else { + CurTy = 0; + } + ++OpIt; + return *this; + } + + generic_gep_type_iterator operator++(int) { // Postincrement + generic_gep_type_iterator tmp = *this; ++*this; return tmp; + } + }; + + typedef generic_gep_type_iterator<> gep_type_iterator; + typedef generic_gep_type_iterator<llvm::ExtractValueInst::idx_iterator> ev_type_iterator; + typedef generic_gep_type_iterator<llvm::InsertValueInst::idx_iterator> iv_type_iterator; + typedef generic_gep_type_iterator<llvm::SmallVector<unsigned, 4>::const_iterator> vce_type_iterator; + + inline gep_type_iterator gep_type_begin(const llvm::User *GEP) { + return gep_type_iterator::begin(GEP->getOperand(0)->getType(), + GEP->op_begin()+1); + } + inline gep_type_iterator gep_type_end(const llvm::User *GEP) { + return gep_type_iterator::end(GEP->op_end()); + } + inline gep_type_iterator gep_type_begin(const llvm::User &GEP) { + return gep_type_iterator::begin(GEP.getOperand(0)->getType(), + GEP.op_begin()+1); + } + inline gep_type_iterator gep_type_end(const llvm::User &GEP) { + return gep_type_iterator::end(GEP.op_end()); + } + + inline ev_type_iterator ev_type_begin(const llvm::ExtractValueInst *EV) { + return ev_type_iterator::begin(EV->getOperand(0)->getType(), + EV->idx_begin()); + } + inline ev_type_iterator ev_type_end(const llvm::ExtractValueInst *EV) { + return ev_type_iterator::end(EV->idx_end()); + } + + inline iv_type_iterator iv_type_begin(const llvm::InsertValueInst *IV) { + return iv_type_iterator::begin(IV->getType(), + IV->idx_begin()); + } + inline iv_type_iterator iv_type_end(const llvm::InsertValueInst *IV) { + return iv_type_iterator::end(IV->idx_end()); + } + + inline vce_type_iterator vce_type_begin(const llvm::ConstantExpr *CE) { + return vce_type_iterator::begin(CE->getOperand(0)->getType(), + CE->getIndices().begin()); + } + inline vce_type_iterator vce_type_end(const llvm::ConstantExpr *CE) { + return vce_type_iterator::end(CE->getIndices().end()); + } + + template<typename ItTy> + inline generic_gep_type_iterator<ItTy> + gep_type_begin(const llvm::Type *Op0, ItTy I, ItTy E) { + return generic_gep_type_iterator<ItTy>::begin(Op0, I); + } + + template<typename ItTy> + inline generic_gep_type_iterator<ItTy> + gep_type_end(const llvm::Type *Op0, ItTy I, ItTy E) { + return generic_gep_type_iterator<ItTy>::end(E); + } +} // end namespace klee + +#endif diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp index 02abc75b..5632b208 100644 --- a/lib/Core/Executor.cpp +++ b/lib/Core/Executor.cpp @@ -33,6 +33,7 @@ #include "klee/util/Assignment.h" #include "klee/util/ExprPPrinter.h" #include "klee/util/ExprUtil.h" +#include "klee/util/GetElementPtrTypeIterator.h" #include "klee/Config/config.h" #include "klee/Internal/ADT/KTest.h" #include "klee/Internal/ADT/RNG.h" @@ -56,7 +57,6 @@ #include "llvm/ADT/StringExtras.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Support/raw_ostream.h" #include "llvm/System/Process.h" #include "llvm/Target/TargetData.h" @@ -2203,6 +2203,43 @@ void Executor::executeInstruction(ExecutionState &state, KInstruction *ki) { bindLocal(ki, state, ConstantExpr::alloc(Result, Expr::Bool)); break; } + case Instruction::InsertValue: { + KGEPInstruction *kgepi = static_cast<KGEPInstruction*>(ki); + + ref<Expr> agg = eval(ki, 0, state).value; + ref<Expr> val = eval(ki, 1, state).value; + + ref<Expr> l = NULL, r = NULL; + unsigned lOffset = kgepi->offset*8, rOffset = kgepi->offset*8 + val->getWidth(); + + if (lOffset > 0) + l = ExtractExpr::create(agg, 0, lOffset); + if (rOffset < agg->getWidth()) + r = ExtractExpr::create(agg, rOffset, agg->getWidth() - rOffset); + + ref<Expr> result; + if (!l.isNull() && !r.isNull()) + result = ConcatExpr::create(r, ConcatExpr::create(val, l)); + else if (!l.isNull()) + result = ConcatExpr::create(val, l); + else if (!r.isNull()) + result = ConcatExpr::create(r, val); + else + result = val; + + bindLocal(ki, state, result); + break; + } + case Instruction::ExtractValue: { + KGEPInstruction *kgepi = static_cast<KGEPInstruction*>(ki); + + ref<Expr> agg = eval(ki, 0, state).value; + + ref<Expr> result = ExtractExpr::create(agg, kgepi->offset*8, getWidthForLLVMType(i->getType())); + + bindLocal(ki, state, result); + break; + } // Other instructions... // Unhandled @@ -2244,17 +2281,12 @@ void Executor::updateStates(ExecutionState *current) { removedStates.clear(); } -void Executor::bindInstructionConstants(KInstruction *KI) { - GetElementPtrInst *gepi = dyn_cast<GetElementPtrInst>(KI->inst); - if (!gepi) - return; - - KGEPInstruction *kgepi = static_cast<KGEPInstruction*>(KI); +template <typename TypeIt> +void Executor::computeOffsets(KGEPInstruction *kgepi, TypeIt ib, TypeIt ie) { ref<ConstantExpr> constantOffset = ConstantExpr::alloc(0, Context::get().getPointerWidth()); uint64_t index = 1; - for (gep_type_iterator ii = gep_type_begin(gepi), ie = gep_type_end(gepi); - ii != ie; ++ii) { + for (TypeIt ii = ib; ii != ie; ++ii) { if (const StructType *st = dyn_cast<StructType>(*ii)) { const StructLayout *sl = kmodule->targetData->getStructLayout(st); const ConstantInt *ci = cast<ConstantInt>(ii.getOperand()); @@ -2282,6 +2314,20 @@ void Executor::bindInstructionConstants(KInstruction *KI) { kgepi->offset = constantOffset->getZExtValue(); } +void Executor::bindInstructionConstants(KInstruction *KI) { + KGEPInstruction *kgepi = static_cast<KGEPInstruction*>(KI); + + if (GetElementPtrInst *gepi = dyn_cast<GetElementPtrInst>(KI->inst)) { + computeOffsets(kgepi, gep_type_begin(gepi), gep_type_end(gepi)); + } else if (InsertValueInst *ivi = dyn_cast<InsertValueInst>(KI->inst)) { + computeOffsets(kgepi, iv_type_begin(ivi), iv_type_end(ivi)); + assert(kgepi->indices.empty() && "InsertValue constant offset expected"); + } else if (ExtractValueInst *evi = dyn_cast<ExtractValueInst>(KI->inst)) { + computeOffsets(kgepi, ev_type_begin(evi), ev_type_end(evi)); + assert(kgepi->indices.empty() && "ExtractValue constant offset expected"); + } +} + void Executor::bindModuleConstants() { for (std::vector<KFunction*>::iterator it = kmodule->functions.begin(), ie = kmodule->functions.end(); it != ie; ++it) { diff --git a/lib/Core/Executor.h b/lib/Core/Executor.h index e6f7c63e..d211b8ce 100644 --- a/lib/Core/Executor.h +++ b/lib/Core/Executor.h @@ -355,6 +355,9 @@ private: /// bindModuleConstants - Initialize the module constant table. void bindModuleConstants(); + template <typename TypeIt> + void computeOffsets(KGEPInstruction *kgepi, TypeIt ib, TypeIt ie); + /// bindInstructionConstants - Initialize any necessary per instruction /// constant values. void bindInstructionConstants(KInstruction *KI); diff --git a/lib/Core/ExecutorUtil.cpp b/lib/Core/ExecutorUtil.cpp index 04264164..5f974725 100644 --- a/lib/Core/ExecutorUtil.cpp +++ b/lib/Core/ExecutorUtil.cpp @@ -17,6 +17,8 @@ #include "klee/Internal/Module/KModule.h" +#include "klee/util/GetElementPtrTypeIterator.h" + #include "llvm/Constants.h" #include "llvm/Function.h" #include "llvm/Instructions.h" @@ -25,7 +27,6 @@ #include "llvm/ModuleProvider.h" #endif #include "llvm/Support/CallSite.h" -#include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Target/TargetData.h" #include <iostream> #include <cassert> diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp index 76291cdc..2982ad67 100644 --- a/lib/Module/KModule.cpp +++ b/lib/Module/KModule.cpp @@ -517,6 +517,8 @@ KFunction::KFunction(llvm::Function *_function, switch(it->getOpcode()) { case Instruction::GetElementPtr: + case Instruction::InsertValue: + case Instruction::ExtractValue: ki = new KGEPInstruction(); break; default: ki = new KInstruction(); break; diff --git a/test/Feature/InsertExtractValue.ll b/test/Feature/InsertExtractValue.ll new file mode 100644 index 00000000..e8b80383 --- /dev/null +++ b/test/Feature/InsertExtractValue.ll @@ -0,0 +1,32 @@ +; RUN: llvm-as %s -o %t1.bc +; RUN: %klee -disable-opt %t1.bc > %t2 +; RUN: grep PASS %t2 + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" +target triple = "x86_64-unknown-linux-gnu" + +%struct.sfoo = type { i32, i32 } + +declare i32 @puts(i8*) + +@.passstr = private constant [5 x i8] c"PASS\00", align 1 +@.failstr = private constant [5 x i8] c"FAIL\00", align 1 + +define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone { +entry: + %s0 = insertvalue %struct.sfoo undef, i32 3, 0 + %s1 = insertvalue %struct.sfoo %s0, i32 1, 1 + %f0 = extractvalue %struct.sfoo %s1, 0 + %f1 = extractvalue %struct.sfoo %s1, 1 + %f0mf1 = sub i32 %f0, %f1 + %r = icmp eq i32 %f0mf1, 2 + br i1 %r, label %bbtrue, label %bbfalse + +bbtrue: + %0 = call i32 @puts(i8* getelementptr inbounds ([5 x i8]* @.passstr, i64 0, i64 0)) nounwind + ret i32 0 + +bbfalse: + %1 = call i32 @puts(i8* getelementptr inbounds ([5 x i8]* @.failstr, i64 0, i64 0)) nounwind + ret i32 0 +} |