Add support for InsertValue and ExtractValue instructions

git-svn-id: https://llvm.org/svn/llvm-project/klee/trunk@107912 91177308-0d34-0410-b5e6-96231b3b80d8

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
+}