Merge pull request #742 from ccadar/fold

Added checks for div/mod by zero and overshifts in constant expressio…

3 files changed, 116 insertions, 58 deletions

diff --git a/lib/Core/ExecutorUtil.cpp b/lib/Core/ExecutorUtil.cpp
index 0a8f08ed..53f4c5b8 100644
--- a/lib/Core/ExecutorUtil.cpp
+++ b/lib/Core/ExecutorUtil.cpp
@@ -36,87 +36,87 @@ using namespace llvm;
 namespace klee {
 
   ref<klee::ConstantExpr> Executor::evalConstant(const Constant *c,
-						 const KInstruction *ki) {
+                                                 const KInstruction *ki) {
     if (!ki) {
       KConstant* kc = kmodule->getKConstant(c);
       if (kc)
-	ki = kc->ki;
+        ki = kc->ki;
     }
 
     if (const llvm::ConstantExpr *ce = dyn_cast<llvm::ConstantExpr>(c)) {
       return evalConstantExpr(ce, ki);
     } else {
       if (const ConstantInt *ci = dyn_cast<ConstantInt>(c)) {
-	return ConstantExpr::alloc(ci->getValue());
+        return ConstantExpr::alloc(ci->getValue());
       } else if (const ConstantFP *cf = dyn_cast<ConstantFP>(c)) {
-	return ConstantExpr::alloc(cf->getValueAPF().bitcastToAPInt());
+        return ConstantExpr::alloc(cf->getValueAPF().bitcastToAPInt());
       } else if (const GlobalValue *gv = dyn_cast<GlobalValue>(c)) {
-	return globalAddresses.find(gv)->second;
+        return globalAddresses.find(gv)->second;
       } else if (isa<ConstantPointerNull>(c)) {
-	return Expr::createPointer(0);
+        return Expr::createPointer(0);
       } else if (isa<UndefValue>(c) || isa<ConstantAggregateZero>(c)) {
-	return ConstantExpr::create(0, getWidthForLLVMType(c->getType()));
+        return ConstantExpr::create(0, getWidthForLLVMType(c->getType()));
       } else if (const ConstantDataSequential *cds =
                  dyn_cast<ConstantDataSequential>(c)) {
-	std::vector<ref<Expr> > kids;
-	for (unsigned i = 0, e = cds->getNumElements(); i != e; ++i) {
-	  ref<Expr> kid = evalConstant(cds->getElementAsConstant(i), ki);
-	  kids.push_back(kid);
-	}
-	ref<Expr> res = ConcatExpr::createN(kids.size(), kids.data());
-	return cast<ConstantExpr>(res);
+        std::vector<ref<Expr> > kids;
+        for (unsigned i = 0, e = cds->getNumElements(); i != e; ++i) {
+          ref<Expr> kid = evalConstant(cds->getElementAsConstant(i), ki);
+          kids.push_back(kid);
+        }
+        ref<Expr> res = ConcatExpr::createN(kids.size(), kids.data());
+        return cast<ConstantExpr>(res);
       } else if (const ConstantStruct *cs = dyn_cast<ConstantStruct>(c)) {
-	const StructLayout *sl = kmodule->targetData->getStructLayout(cs->getType());
-	llvm::SmallVector<ref<Expr>, 4> kids;
-	for (unsigned i = cs->getNumOperands(); i != 0; --i) {
-	  unsigned op = i-1;
-	  ref<Expr> kid = evalConstant(cs->getOperand(op), ki);
-
-	  uint64_t thisOffset = sl->getElementOffsetInBits(op),
-	    nextOffset = (op == cs->getNumOperands() - 1)
-	    ? sl->getSizeInBits()
-	    : sl->getElementOffsetInBits(op+1);
-	  if (nextOffset-thisOffset > kid->getWidth()) {
-	    uint64_t paddingWidth = nextOffset-thisOffset-kid->getWidth();
-	    kids.push_back(ConstantExpr::create(0, paddingWidth));
-	  }
-
-	  kids.push_back(kid);
-	}
-	ref<Expr> res = ConcatExpr::createN(kids.size(), kids.data());
-	return cast<ConstantExpr>(res);
+        const StructLayout *sl = kmodule->targetData->getStructLayout(cs->getType());
+        llvm::SmallVector<ref<Expr>, 4> kids;
+        for (unsigned i = cs->getNumOperands(); i != 0; --i) {
+          unsigned op = i-1;
+          ref<Expr> kid = evalConstant(cs->getOperand(op), ki);
+
+          uint64_t thisOffset = sl->getElementOffsetInBits(op),
+            nextOffset = (op == cs->getNumOperands() - 1)
+            ? sl->getSizeInBits()
+            : sl->getElementOffsetInBits(op+1);
+          if (nextOffset-thisOffset > kid->getWidth()) {
+            uint64_t paddingWidth = nextOffset-thisOffset-kid->getWidth();
+            kids.push_back(ConstantExpr::create(0, paddingWidth));
+          }
+
+          kids.push_back(kid);
+        }
+        ref<Expr> res = ConcatExpr::createN(kids.size(), kids.data());
+        return cast<ConstantExpr>(res);
       } else if (const ConstantArray *ca = dyn_cast<ConstantArray>(c)){
-	llvm::SmallVector<ref<Expr>, 4> kids;
-	for (unsigned i = ca->getNumOperands(); i != 0; --i) {
-	  unsigned op = i-1;
-	  ref<Expr> kid = evalConstant(ca->getOperand(op), ki);
-	  kids.push_back(kid);
-	}
-	ref<Expr> res = ConcatExpr::createN(kids.size(), kids.data());
-	return cast<ConstantExpr>(res);
+        llvm::SmallVector<ref<Expr>, 4> kids;
+        for (unsigned i = ca->getNumOperands(); i != 0; --i) {
+          unsigned op = i-1;
+          ref<Expr> kid = evalConstant(ca->getOperand(op), ki);
+          kids.push_back(kid);
+        }
+        ref<Expr> res = ConcatExpr::createN(kids.size(), kids.data());
+        return cast<ConstantExpr>(res);
       } else if (const ConstantVector *cv = dyn_cast<ConstantVector>(c)) {
-	llvm::SmallVector<ref<Expr>, 8> kids;
-	const size_t numOperands = cv->getNumOperands();
-	kids.reserve(numOperands);
-	for (unsigned i = 0; i < numOperands; ++i) {
-	  kids.push_back(evalConstant(cv->getOperand(i), ki));
-	}
-	ref<Expr> res = ConcatExpr::createN(numOperands, kids.data());
-	assert(isa<ConstantExpr>(res) &&
-	       "result of constant vector built is not a constant");
-	return cast<ConstantExpr>(res);
+        llvm::SmallVector<ref<Expr>, 8> kids;
+        const size_t numOperands = cv->getNumOperands();
+        kids.reserve(numOperands);
+        for (unsigned i = 0; i < numOperands; ++i) {
+          kids.push_back(evalConstant(cv->getOperand(i), ki));
+        }
+        ref<Expr> res = ConcatExpr::createN(numOperands, kids.data());
+        assert(isa<ConstantExpr>(res) &&
+               "result of constant vector built is not a constant");
+        return cast<ConstantExpr>(res);
       } else {
-	std::string msg("Cannot handle constant ");
-	llvm::raw_string_ostream os(msg);
-	os << "'" << *c << "' at location "
-	   << (ki ? ki->printFileLine().c_str() : "[unknown]");
-	klee_error("%s", os.str().c_str());
+        std::string msg("Cannot handle constant ");
+        llvm::raw_string_ostream os(msg);
+        os << "'" << *c << "' at location "
+           << (ki ? ki->printFileLine().c_str() : "[unknown]");
+        klee_error("%s", os.str().c_str());
       }
     }
   }
 
   ref<ConstantExpr> Executor::evalConstantExpr(const llvm::ConstantExpr *ce,
-					       const KInstruction *ki) {
+                                               const KInstruction *ki) {
     llvm::Type *type = ce->getType();
 
     ref<ConstantExpr> op1(0), op2(0), op3(0);
@@ -126,13 +126,37 @@ namespace klee {
     if (numOperands > 1) op2 = evalConstant(ce->getOperand(1), ki);
     if (numOperands > 2) op3 = evalConstant(ce->getOperand(2), ki);
 
+    /* Checking for possible errors during constant folding */
+    switch (ce->getOpcode()) {
+    case Instruction::SDiv:
+    case Instruction::UDiv:
+    case Instruction::SRem:
+    case Instruction::URem:
+      if (op2->getLimitedValue() == 0) {
+        std::string msg("Division/modulo by zero during constant folding at location ");
+        llvm::raw_string_ostream os(msg);
+        os << (ki ? ki->printFileLine().c_str() : "[unknown]");
+        klee_error("%s", os.str().c_str());
+      }
+      break;
+    case Instruction::Shl:
+    case Instruction::LShr:
+    case Instruction::AShr:
+      if (op2->getLimitedValue() >= op1->getWidth()) {
+        std::string msg("Overshift during constant folding at location ");
+        llvm::raw_string_ostream os(msg);
+        os << (ki ? ki->printFileLine().c_str() : "[unknown]");
+        klee_error("%s", os.str().c_str());
+      }
+    }
+
     std::string msg("Unknown ConstantExpr type");
     llvm::raw_string_ostream os(msg);
 
     switch (ce->getOpcode()) {
     default :
       os << "'" << *ce << "' at location "
-	 << (ki ? ki->printFileLine().c_str() : "[unknown]");
+         << (ki ? ki->printFileLine().c_str() : "[unknown]");
       klee_error("%s", os.str().c_str());
 
     case Instruction::Trunc: 
diff --git a/test/Feature/ConstExprWithDivZero.ll b/test/Feature/ConstExprWithDivZero.ll
new file mode 100644
index 00000000..f430dad9
--- /dev/null
+++ b/test/Feature/ConstExprWithDivZero.ll
@@ -0,0 +1,18 @@
+; REQUIRES: llvm-3.4
+; RUN: llvm-as %s -f -o %t.bc
+; RUN: rm -rf %t.klee-out
+; RUN: not %klee --output-dir=%t.klee-out %t.bc 2> %t.log
+; RUN: FileCheck --input-file %t.log %s
+
+; See https://github.com/klee/klee/issues/268
+
+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-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+@a = internal global i32 0, align 4
+@b = internal global [1 x i32] [i32 1], align 4
+
+define i32 @main() {
+; CHECK: Division/modulo by zero during constant folding
+  ret i32 trunc (i64 sdiv (i64 2036854775807, i64 sext (i32 select (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @a), i32 1, i32 0) to i64)) to i32)
+}
diff --git a/test/Feature/ConstExprWithOvershift.ll b/test/Feature/ConstExprWithOvershift.ll
new file mode 100644
index 00000000..7d4a1284
--- /dev/null
+++ b/test/Feature/ConstExprWithOvershift.ll
@@ -0,0 +1,16 @@
+; REQUIRES: llvm-3.4
+; RUN: llvm-as %s -f -o %t.bc
+; RUN: rm -rf %t.klee-out
+; RUN: not %klee --output-dir=%t.klee-out %t.bc 2> %t.log
+; RUN: FileCheck --input-file %t.log %s
+
+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-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+@a = internal global i32 0, align 4
+@b = internal global [1 x i32] [i32 1], align 4
+
+define i32 @main() {
+; CHECK: Overshift during constant folding
+  ret i32 ashr (i32 zext (i1 icmp ne (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @a) to i32), i32 trunc (i64 add (i64 zext (i1 icmp ne (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @a) to i64), i64 31) to i32))
+}