halide · steven-johnson · May 2, 2023 · May 1, 2023 · nathaniel-brough · May 4, 2023
diff --git a/test/correctness/CMakeLists.txt b/test/correctness/CMakeLists.txt
@@ -114,7 +114,6 @@ tests(GROUPS correctness
       fuse_gpu_threads.cpp
       fused_where_inner_extent_is_zero.cpp
       fuzz_bounds.cpp
-      fuzz_cse.cpp
       fuzz_float_stores.cpp
       gameoflife.cpp
       gather.cpp

diff --git a/test/correctness/fuzz_cse.cpp b/test/correctness/fuzz_cse.cpp
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
@@ -1,6 +1,7 @@
 tests(GROUPS fuzz
       SOURCES
       simplify.cpp
+      cse.cpp
 )
 
 
@@ -13,14 +14,16 @@ tests(GROUPS fuzz
 set(LIB_FUZZING_ENGINE "$ENV{LIB_FUZZING_ENGINE}"
     CACHE STRING "Compiler flags necessary to link the fuzzing engine of choice e.g. libfuzzer, afl etc.")
 
-target_link_libraries(fuzz_simplify PRIVATE Halide::Halide)
+foreach(fuzzer "fuzz_simplify" "fuzz_cse")
+  target_link_libraries(${fuzzer} PRIVATE Halide::Halide)
 
-# Allow OSS-fuzz to manage flags directly
-if (LIB_FUZZING_ENGINE)
-  target_link_libraries(fuzz_simplify PRIVATE "${LIB_FUZZING_ENGINE}")
-else ()
-  # By default just build with address-sanitizers/libfuzzer for local testing
-  target_compile_options(fuzz_simplify PRIVATE -fsanitize=fuzzer-no-link,address)
-  target_link_options(fuzz_simplify PRIVATE -fsanitize=fuzzer,address)
-endif ()
+  # Allow OSS-fuzz to manage flags directly
+  if (LIB_FUZZING_ENGINE)
+    target_link_libraries(${fuzzer} PRIVATE "${LIB_FUZZING_ENGINE}")
+  else ()
+    # By default just build with address-sanitizers/libfuzzer for local testing
+    target_compile_options(${fuzzer} PRIVATE -fsanitize=fuzzer-no-link,address)
+    target_link_options(${fuzzer} PRIVATE -fsanitize=fuzzer,address)
+  endif ()
+endforeach()
 
diff --git a/test/fuzz/cse.cpp b/test/fuzz/cse.cpp
@@ -0,0 +1,87 @@
+#include "Halide.h"
+
+#include <fuzzer/FuzzedDataProvider.h>
+#include <time.h>
+
+using namespace Halide;
+using namespace Halide::Internal;
+using std::vector;
+
+Expr random_expr(FuzzedDataProvider &fdp, int depth, vector<Expr> &exprs) {
+    if (depth <= 0) {
+        return fdp.ConsumeIntegralInRange<int>(-5, 4);
+    }
+
+    if (!exprs.empty() && fdp.ConsumeBool()) {
+        // Reuse an existing expression
+        return exprs[fdp.ConsumeIntegralInRange<size_t>(0, exprs.size() - 1)];
+    }
+
+    Expr next;
+    switch (fdp.ConsumeIntegralInRange<int>(0, 8)) {
+    case 0:
+        next = Var("x");
+        break;
+    case 1:
+        next = Var("y");
+        break;
+    case 2:
+        next = Var("z");
+        break;
+    case 3:
+        // Any binary op is equally good
+        next = random_expr(fdp, depth - 1, exprs);
+        next += random_expr(fdp, depth - 1, exprs);
+        break;
+    case 4: {
+        Expr a = random_expr(fdp, depth - 2, exprs);
+        Expr b = random_expr(fdp, depth - 2, exprs);
+        Expr c = random_expr(fdp, depth - 2, exprs);
+        Expr d = random_expr(fdp, depth - 2, exprs);
+        next = select(a > b, c, d);
+        break;
+    }
+    case 5: {
+        Expr a = random_expr(fdp, depth - 1, exprs);
+        Expr b = random_expr(fdp, depth - 1, exprs);
+        next = Let::make("x", a, b);
+        break;
+    }
+    case 6: {
+        Expr a = random_expr(fdp, depth - 1, exprs);
+        Expr b = random_expr(fdp, depth - 1, exprs);
+        next = Let::make("y", a, b);
+        break;
+    }
+    case 7: {
+        Expr a = random_expr(fdp, depth - 1, exprs);
+        Expr b = random_expr(fdp, depth - 1, exprs);
+        next = Let::make("z", a, b);
+        break;
+    }
+    default:
+        next = fdp.ConsumeIntegralInRange<int>(-5, 4);
+    }
+    exprs.push_back(next);
+    return next;
+}
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
+    FuzzedDataProvider fdp(data, size);
+    vector<Expr> exprs;
+    Expr orig = random_expr(fdp, 5, exprs);
+
+    Expr csed = common_subexpression_elimination(orig);
+
+    Expr check = (orig == csed);
+    check = Let::make("x", 1, check);
+    check = Let::make("y", 2, check);
+    check = Let::make("z", 3, check);
+    Stmt check_stmt = uniquify_variable_names(Evaluate::make(check));
+    check = check_stmt.as<Evaluate>()->value;
+
+    // Don't use can_prove, because it recursively calls cse, which just confuses matters.
+    assert(is_const_one(simplify(check)));
+
+    return 0;
+}