Fix overshift check

Shifting by bitwidth-1 is valid

3 files changed, 31 insertions, 2 deletions

diff --git a/lib/Solver/MetaSMTBuilder.h b/lib/Solver/MetaSMTBuilder.h
index b5c99907..92b26926 100644
--- a/lib/Solver/MetaSMTBuilder.h
+++ b/lib/Solver/MetaSMTBuilder.h
@@ -284,7 +284,7 @@ typename SolverContext::result_type MetaSMTBuilder<SolverContext>::constructAShr
     if (shift == 0) {
         res = expr;
     }
-    else if (shift >= width - 1) {
+    else if (shift >= width) {
         res = evaluate(_solver, metaSMT::logic::Ite(isSigned, bvMinusOne(width), bvZero(width)));
     }
     else {
diff --git a/lib/Solver/STPBuilder.cpp b/lib/Solver/STPBuilder.cpp
index 34ce0ede..6d7dd8b7 100644
--- a/lib/Solver/STPBuilder.cpp
+++ b/lib/Solver/STPBuilder.cpp
@@ -283,7 +283,7 @@ ExprHandle STPBuilder::constructAShrByConstant(ExprHandle expr,
 
   if (shift==0) {
     return expr;
-  } else if (shift>=width-1) {
+  } else if (shift>=width) {
     return bvZero(width); // Overshift to zero
   } else {
     return vc_iteExpr(vc,
diff --git a/test/regression/2014-12-08-ashr.c b/test/regression/2014-12-08-ashr.c
new file mode 100644
index 00000000..3fe7f62b
--- /dev/null
+++ b/test/regression/2014-12-08-ashr.c
@@ -0,0 +1,29 @@
+// RUN: %llvmgcc %s -emit-llvm -g -O0 -c -o %t.bc
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -exit-on-error %t.bc
+
+#include <assert.h>
+#include <klee/klee.h>
+
+int f1(int a, int b) {
+  return a + b;
+}
+
+int f2(int a, int b) {
+  int i;
+  for (i = 0; i < sizeof(b) * 8; i++)
+    a += (((b >> i) & 1) << i);
+
+  return a;
+}
+
+int main(int argc, char **argv) {
+  int a, b;
+  klee_make_symbolic(&a, sizeof(a), "a");
+  klee_make_symbolic(&b, sizeof(b), "b");
+
+  klee_assert(f1(a, b) == f2(a, b));
+
+  return 0;
+}
+