Concretize constants using seed values, when available. Added two tests (w/ and w/o seed extension) based on FP concretization.

4 files changed, 92 insertions, 9 deletions

diff --git a/lib/Core/Executor.cpp b/lib/Core/Executor.cpp
index 7fe20bb8..e4fba39b 100644
--- a/lib/Core/Executor.cpp
+++ b/lib/Core/Executor.cpp
@@ -1329,16 +1329,21 @@ Executor::toConstant(ExecutionState &state,
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(e))
     return CE;
 
-  ref<ConstantExpr> value;
-  bool success =
-      solver->getValue(state.constraints, e, value, state.queryMetaData);
-  assert(success && "FIXME: Unhandled solver failure");
-  (void) success;
+  ref<Expr> value;
+  if (auto found = seedMap.find(&state); found != seedMap.end())
+    value = getValueFromSeeds(found->second, e);
+  /* If no seed evaluation results in a constant, call the solver */
+  ref<ConstantExpr> cvalue = llvm::dyn_cast_or_null<ConstantExpr>(value);
+  if (!cvalue) {
+    [[maybe_unused]] bool success =
+        solver->getValue(state.constraints, e, cvalue, state.queryMetaData);
+    assert(success && "FIXME: Unhandled solver failure");
+  }
 
   std::string str;
   llvm::raw_string_ostream os(str);
   os << "silently concretizing (reason: " << reason << ") expression " << e
-     << " to value " << value << " (" << (*(state.pc)).info->file << ":"
+     << " to value " << cvalue << " (" << (*(state.pc)).info->file << ":"
      << (*(state.pc)).info->line << ")";
 
   if (ExternalCallWarnings == ExtCallWarnings::All)
@@ -1346,9 +1351,20 @@ Executor::toConstant(ExecutionState &state,
   else
     klee_warning_once(reason, "%s", os.str().c_str());
 
-  addConstraint(state, EqExpr::create(e, value));
-    
-  return value;
+  addConstraint(state, EqExpr::create(e, cvalue));
+
+  return cvalue;
+}
+
+ref<klee::Expr>
+Executor::getValueFromSeeds(std::vector<SeedInfo> &seeds, ref<Expr> e) {
+  assert(!seeds.empty());
+  for (auto seed:seeds) {
+    auto value = seed.assignment.evaluate(e);
+    if (isa<ConstantExpr>(value))
+      return value;
+  }
+  return nullptr;
 }
 
 void Executor::executeGetValue(ExecutionState &state,
diff --git a/lib/Core/Executor.h b/lib/Core/Executor.h
index f7f84101..bf773fa5 100644
--- a/lib/Core/Executor.h
+++ b/lib/Core/Executor.h
@@ -396,6 +396,13 @@ private:
   ref<klee::ConstantExpr> toConstant(ExecutionState &state, ref<Expr> e, 
                                      const char *purpose);
 
+  /// Evaluate the given expression under each seed, and return the
+  /// first one that results in a constant, if such a seed exist.  Otherwise,
+  /// return the non-constant evaluation of the expression under one of the
+  /// seeds.
+  ref<klee::Expr> getValueFromSeeds(std::vector<SeedInfo> &seeds,
+                                            ref<Expr> e);
+
   /// Bind a constant value for e to the given target. NOTE: This
   /// function may fork state if the state has multiple seeds.
   void executeGetValue(ExecutionState &state, ref<Expr> e, KInstruction *target);
diff --git a/test/Feature/SeedConcretizeFP.c b/test/Feature/SeedConcretizeFP.c
new file mode 100644
index 00000000..bc5246ad
--- /dev/null
+++ b/test/Feature/SeedConcretizeFP.c
@@ -0,0 +1,27 @@
+// RUN: %clang -emit-llvm -c -g %s -o %t.bc
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out --entry-point=TestGen %t.bc
+// RUN: test -f %t.klee-out/test000001.ktest
+// RUN: not test -f %t.klee-out/test000002.ktest
+
+// RUN: rm -rf %t.klee-out-2
+// RUN: %klee --exit-on-error --output-dir=%t.klee-out-2 --seed-file %t.klee-out/test000001.ktest %t.bc 2>&1 | FileCheck %s
+
+#include "klee/klee.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+void TestGen() {
+  unsigned x;
+  klee_make_symbolic(&x, sizeof(x), "x");
+  klee_assume(x == 12345678);
+}
+
+int main() {
+  unsigned i;
+  klee_make_symbolic(&i, sizeof(i), "i");
+  double d = i;
+  // CHECK: concretizing (reason: floating point)
+  assert((unsigned) d == 12345678);
+}
diff --git a/test/Feature/SeedConcretizePatchedFP.c b/test/Feature/SeedConcretizePatchedFP.c
new file mode 100644
index 00000000..b8b758b5
--- /dev/null
+++ b/test/Feature/SeedConcretizePatchedFP.c
@@ -0,0 +1,33 @@
+/* This test checks the case where the seed needs to be patched on re-run */
+
+// RUN: %clang -emit-llvm -c %O0opt -g %s -o %t.bc
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out --entry-point=TestGen %t.bc
+// RUN: test -f %t.klee-out/test000001.ktest
+// RUN: not test -f %t.klee-out/test000002.ktest
+
+// RUN: rm -rf %t.klee-out-2
+// RUN: %klee --exit-on-error --output-dir=%t.klee-out-2 --seed-file %t.klee-out/test000001.ktest --allow-seed-extension --zero-seed-extension %t.bc 2>&1 | FileCheck %s
+
+#include "klee/klee.h"
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+void TestGen() {
+  uint16_t x;
+  klee_make_symbolic(&x, sizeof(x), "x");
+  klee_assume(x == 1234);
+}
+
+int main() {
+  uint32_t i;
+  klee_make_symbolic(&i, sizeof(i), "i");
+
+  if (i < 5000) {
+    double d = i;
+    // CHECK: concretizing (reason: floating point)
+    assert((unsigned) d < 5001);
+  }
+}