add a small basic block fuzzer that has already found a few bugs
the tool is called quick-fuzz instead of bb-fuzz because I'd like
to add a few more little fuzzers like this to it in the future
also factor out some common machinery from alive-tv.cpp
MODIFY
CMakeLists.txt
CMakeLists.txt
@@ -183,6 +183,7 @@ if (BUILD_LLVM_UTILS OR BUILD_TV)
add_definitions(${LLVM_DEFINITIONS})
set(LLVM_UTIL_SRCS
+ "llvm_util/compare.cpp"
"llvm_util/known_fns.cpp"
"llvm_util/llvm_optimizer.cpp"
"llvm_util/llvm2alive.cpp"
@@ -198,6 +199,10 @@ if (BUILD_LLVM_UTILS OR BUILD_TV)
"tools/alive-tv.cpp"
)
+ add_llvm_executable(quick-fuzz
+ "tools/quick-fuzz.cpp"
+ )
+
add_llvm_executable(alive-exec
"tools/alive-exec.cpp"
)
@@ -243,9 +248,10 @@ add_executable(alive-jobserver
#add_library(alive2 SHARED ${IR_SRCS} ${SMT_SRCS} ${TOOLS_SRCS} ${UTIL_SRCS} ${LLVM_UTIL_SRCS})
if (BUILD_LLVM_UTILS OR BUILD_TV)
- llvm_map_components_to_libnames(llvm_libs support core irreader analysis passes transformutils)
+ llvm_map_components_to_libnames(llvm_libs support core irreader bitwriter analysis passes transformutils)
# target_link_libraries(alive2 PRIVATE ${llvm_libs})
target_link_libraries(alive-tv PRIVATE ${ALIVE_LIBS_LLVM} ${Z3_LIBRARIES} ${HIREDIS_LIBRARIES} ${llvm_libs})
+ target_link_libraries(quick-fuzz PRIVATE ${ALIVE_LIBS_LLVM} ${Z3_LIBRARIES} ${HIREDIS_LIBRARIES} ${llvm_libs})
target_link_libraries(alive-exec PRIVATE ${ALIVE_LIBS_LLVM} ${Z3_LIBRARIES} ${HIREDIS_LIBRARIES} ${llvm_libs})
endif()
@@ -269,5 +275,5 @@ add_custom_target("check"
)
if (BUILD_TV)
- add_dependencies("check" "alive-tv" "tv")
+ add_dependencies("check" "alive-tv" "quick-fuzz" "tv")
endif()

ADD
llvm_util/compare.cpp
+#include "llvm_util/compare.h"
+#include "llvm_util/llvm2alive.h"
+#include "llvm_util/llvm_optimizer.h"
+#include "smt/smt.h"
+#include "tools/transform.h"
+#include "util/version.h"
+
+#include <sstream>
+#include <utility>
+
+using namespace tools;
+using namespace util;
+using namespace std;
+using namespace llvm_util;
+
+namespace {
+
+llvm::ExitOnError ExitOnErr;
+
+struct Results {
+ Transform t;
+ string error;
+ Errors errs;
+ enum {
+ ERROR,
+ TYPE_CHECKER_FAILED,
+ SYNTACTIC_EQ,
+ CORRECT,
+ UNSOUND,
+ FAILED_TO_PROVE
+ } status;
+
+ static Results Error(string &&err) {
+ Results r;
+ r.status = ERROR;
+ r.error = std::move(err);
+ return r;
+ }
+};
+
+Results verify(llvm::Function &F1, llvm::Function &F2,
+ llvm::TargetLibraryInfoWrapperPass &TLI,
+ smt::smt_initializer &smt_init, ostream *out,
+ bool print_transform = false, bool always_verify = false) {
+ auto fn1 = llvm2alive(F1, TLI.getTLI(F1), true);
+ if (!fn1)
+ return Results::Error("Could not translate '" + F1.getName().str() +
+ "' to Alive IR\n");
+
+ auto fn2 = llvm2alive(F2, TLI.getTLI(F2), false, fn1->getGlobalVarNames());
+ if (!fn2)
+ return Results::Error("Could not translate '" + F2.getName().str() +
+ "' to Alive IR\n");
+
+ Results r;
+ r.t.src = std::move(*fn1);
+ r.t.tgt = std::move(*fn2);
+
+ if (!always_verify) {
+ stringstream ss1, ss2;
+ r.t.src.print(ss1);
+ r.t.tgt.print(ss2);
+ if (std::move(ss1).str() == std::move(ss2).str()) {
+ if (print_transform)
+ r.t.print(*out, {});
+ r.status = Results::SYNTACTIC_EQ;
+ return r;
+ }
+ }
+
+ smt_init.reset();
+ r.t.preprocess();
+ TransformVerify verifier(r.t, false);
+
+ if (print_transform)
+ r.t.print(*out, {});
+
+ {
+ auto types = verifier.getTypings();
+ if (!types) {
+ r.status = Results::TYPE_CHECKER_FAILED;
+ return r;
+ }
+ assert(types.hasSingleTyping());
+ }
+
+ r.errs = verifier.verify();
+ if (r.errs) {
+ r.status = r.errs.isUnsound() ? Results::UNSOUND : Results::FAILED_TO_PROVE;
+ } else {
+ r.status = Results::CORRECT;
+ }
+ return r;
+}
+
+} // namespace
+
+bool compareFunctions(llvm::Function &F1, llvm::Function &F2,
+ llvm::TargetLibraryInfoWrapperPass &TLI,
+ smt::smt_initializer &smt_init, tv_stats &stats,
+ const tv_opts &opts, ostream *out) {
+ auto r = verify(F1, F2, TLI, smt_init, out, !opts.quiet, opts.always_verify);
+ if (r.status == Results::ERROR) {
+ *out << "ERROR: " << r.error;
+ ++stats.num_errors;
+ return true;
+ }
+
+ if (opts.print_dot) {
+ r.t.src.writeDot("src");
+ r.t.tgt.writeDot("tgt");
+ }
+
+ switch (r.status) {
+ case Results::ERROR:
+ UNREACHABLE();
+ break;
+
+ case Results::SYNTACTIC_EQ:
+ *out << "Transformation seems to be correct! (syntactically equal)\n\n";
+ ++stats.num_correct;
+ break;
+
+ case Results::CORRECT:
+ *out << "Transformation seems to be correct!\n\n";
+ ++stats.num_correct;
+ break;
+
+ case Results::TYPE_CHECKER_FAILED:
+ *out << "Transformation doesn't verify!\n"
+ "ERROR: program doesn't type check!\n\n";
+ ++stats.num_errors;
+ return true;
+
+ case Results::UNSOUND:
+ *out << "Transformation doesn't verify!\n\n";
+ if (!opts.quiet)
+ *out << r.errs << endl;
+ ++stats.num_unsound;
+ return false;
+
+ case Results::FAILED_TO_PROVE:
+ *out << r.errs << endl;
+ ++stats.num_failed;
+ return true;
+ }
+
+ if (opts.bidirectional) {
+ r = verify(F2, F1, TLI, smt_init, out, false, opts.always_verify);
+ switch (r.status) {
+ case Results::ERROR:
+ case Results::TYPE_CHECKER_FAILED:
+ UNREACHABLE();
+ break;
+
+ case Results::SYNTACTIC_EQ:
+ case Results::CORRECT:
+ *out << "These functions seem to be equivalent!\n\n";
+ return true;
+
+ case Results::FAILED_TO_PROVE:
+ *out << "Failed to verify the reverse transformation\n\n";
+ if (!opts.quiet)
+ *out << r.errs << endl;
+ return true;
+
+ case Results::UNSOUND:
+ *out << "Reverse transformation doesn't verify!\n\n";
+ if (!opts.quiet)
+ *out << r.errs << endl;
+ return false;
+ }
+ }
+ return true;
+}

ADD
llvm_util/compare.h
+#include "smt/smt.h"
+
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/Function.h"
+
+struct tv_stats {
+ unsigned num_correct, num_unsound, num_failed, num_errors;
+};
+
+struct tv_opts {
+ tv_opts(bool quiet, bool always_verify, bool print_dot, bool bidirectional)
+ : quiet(quiet), always_verify(always_verify), print_dot(print_dot),
+ bidirectional(bidirectional) {}
+ bool quiet, always_verify, print_dot, bidirectional;
+};
+
+bool compareFunctions(llvm::Function &F1, llvm::Function &F2,
+ llvm::TargetLibraryInfoWrapperPass &TLI,
+ smt::smt_initializer &smt_init, tv_stats &stats,
+ const tv_opts &opts, std::ostream *out);

MODIFY
tools/alive-tv.cpp
tools/alive-tv.cpp
// Distributed under the MIT license that can be found in the LICENSE file.
#include "cache/cache.h"
+#include "llvm_util/compare.h"
#include "llvm_util/llvm2alive.h"
#include "llvm_util/llvm_optimizer.h"
#include "smt/smt.h"
@@ -89,164 +90,7 @@ std::unique_ptr<llvm::Module> openInputFile(llvm::LLVMContext &Context,
optional<smt::smt_initializer> smt_init;
unique_ptr<Cache> cache;
-
-struct Results {
- Transform t;
- string error;
- Errors errs;
- enum {
- ERROR,
- TYPE_CHECKER_FAILED,
- SYNTACTIC_EQ,
- CORRECT,
- UNSOUND,
- FAILED_TO_PROVE
- } status;
-
- static Results Error(string &&err) {
- Results r;
- r.status = ERROR;
- r.error = std::move(err);
- return r;
- }
-};
-
-Results verify(llvm::Function &F1, llvm::Function &F2,
- llvm::TargetLibraryInfoWrapperPass &TLI,
- bool print_transform = false,
- bool always_verify = false) {
- auto fn1 = llvm2alive(F1, TLI.getTLI(F1), true);
- if (!fn1)
- return Results::Error("Could not translate '" + F1.getName().str() +
- "' to Alive IR\n");
-
- auto fn2 = llvm2alive(F2, TLI.getTLI(F2), false, fn1->getGlobalVarNames());
- if (!fn2)
- return Results::Error("Could not translate '" + F2.getName().str() +
- "' to Alive IR\n");
-
- Results r;
- r.t.src = std::move(*fn1);
- r.t.tgt = std::move(*fn2);
-
- if (!always_verify) {
- stringstream ss1, ss2;
- r.t.src.print(ss1);
- r.t.tgt.print(ss2);
- if (std::move(ss1).str() == std::move(ss2).str()) {
- if (print_transform)
- r.t.print(*out, {});
- r.status = Results::SYNTACTIC_EQ;
- return r;
- }
- }
-
- smt_init->reset();
- r.t.preprocess();
- TransformVerify verifier(r.t, false);
-
- if (print_transform)
- r.t.print(*out, {});
-
- {
- auto types = verifier.getTypings();
- if (!types) {
- r.status = Results::TYPE_CHECKER_FAILED;
- return r;
- }
- assert(types.hasSingleTyping());
- }
-
- r.errs = verifier.verify();
- if (r.errs) {
- r.status = r.errs.isUnsound() ? Results::UNSOUND : Results::FAILED_TO_PROVE;
- } else {
- r.status = Results::CORRECT;
- }
- return r;
-}
-
-unsigned num_correct = 0;
-unsigned num_unsound = 0;
-unsigned num_failed = 0;
-unsigned num_errors = 0;
-
-bool compareFunctions(llvm::Function &F1, llvm::Function &F2,
- llvm::TargetLibraryInfoWrapperPass &TLI) {
- auto r = verify(F1, F2, TLI, !opt_quiet, opt_always_verify);
- if (r.status == Results::ERROR) {
- *out << "ERROR: " << r.error;
- ++num_errors;
- return true;
- }
-
- if (opt_print_dot) {
- r.t.src.writeDot("src");
- r.t.tgt.writeDot("tgt");
- }
-
- switch (r.status) {
- case Results::ERROR:
- UNREACHABLE();
- break;
-
- case Results::SYNTACTIC_EQ:
- *out << "Transformation seems to be correct! (syntactically equal)\n\n";
- ++num_correct;
- break;
-
- case Results::CORRECT:
- *out << "Transformation seems to be correct!\n\n";
- ++num_correct;
- break;
-
- case Results::TYPE_CHECKER_FAILED:
- *out << "Transformation doesn't verify!\n"
- "ERROR: program doesn't type check!\n\n";
- ++num_errors;
- return true;
-
- case Results::UNSOUND:
- *out << "Transformation doesn't verify!\n\n";
- if (!opt_quiet)
- *out << r.errs << endl;
- ++num_unsound;
- return false;
-
- case Results::FAILED_TO_PROVE:
- *out << r.errs << endl;
- ++num_failed;
- return true;
- }
-
- if (opt_bidirectional) {
- r = verify(F2, F1, TLI, false, opt_always_verify);
- switch (r.status) {
- case Results::ERROR:
- case Results::TYPE_CHECKER_FAILED:
- UNREACHABLE();
- break;
-
- case Results::SYNTACTIC_EQ:
- case Results::CORRECT:
- *out << "These functions seem to be equivalent!\n\n";
- return true;
-
- case Results::FAILED_TO_PROVE:
- *out << "Failed to verify the reverse transformation\n\n";
- if (!opt_quiet)
- *out << r.errs << endl;
- return true;
-
- case Results::UNSOUND:
- *out << "Reverse transformation doesn't verify!\n\n";
- if (!opt_quiet)
- *out << r.errs << endl;
- return false;
- }
- }
- return true;
-}
+tv_stats stats;
llvm::Function *findFunction(llvm::Module &M, const string &FName) {
for (auto &F : M) {
@@ -297,6 +141,7 @@ convenient way to demonstrate an existing optimizer bug.
llvm::cl::HideUnrelatedOptions(alive_cmdargs);
llvm::cl::ParseCommandLineOptions(argc, argv, Usage);
+ const tv_opts opts(opt_quiet, opt_always_verify, opt_print_dot, opt_bidirectional);
auto M1 = openInputFile(Context, opt_file1);
if (!M1.get()) {
@@ -319,7 +164,7 @@ convenient way to demonstrate an existing optimizer bug.
auto SRC = findFunction(*M1, opt_src_fn);
auto TGT = findFunction(*M1, opt_tgt_fn);
if (SRC && TGT) {
- compareFunctions(*SRC, *TGT, TLI);
+ compareFunctions(*SRC, *TGT, TLI, *smt_init, stats, opts, out);
goto end;
} else {
M2 = CloneModule(*M1);
@@ -359,7 +204,7 @@ convenient way to demonstrate an existing optimizer bug.
M2_anon_count++;
if ((F1.getName().empty() && (M1_anon_count == M2_anon_count)) ||
(F1.getName() == F2.getName())) {
- if (!compareFunctions(F1, F2, TLI))
+ if (!compareFunctions(F1, F2, TLI, *smt_init, stats, opts, out))
if (opt_error_fatal)
goto end;
break;
@@ -368,10 +213,10 @@ convenient way to demonstrate an existing optimizer bug.
}
*out << "Summary:\n"
- " " << num_correct << " correct transformations\n"
- " " << num_unsound << " incorrect transformations\n"
- " " << num_failed << " failed-to-prove transformations\n"
- " " << num_errors << " Alive2 errors\n";
+ " " << stats.num_correct << " correct transformations\n"
+ " " << stats.num_unsound << " incorrect transformations\n"
+ " " << stats.num_failed << " failed-to-prove transformations\n"
+ " " << stats.num_errors << " Alive2 errors\n";
end:
if (opt_smt_stats)
@@ -382,5 +227,5 @@ end:
if (opt_alias_stats)
IR::Memory::printAliasStats(*out);
- return num_errors > 0;
+ return stats.num_errors > 0;
}

ADD
tools/quick-fuzz.cpp
+// Copyright (c) 2018-present The Alive2 Authors.
+// Distributed under the MIT license that can be found in the LICENSE file.
+
+#include "cache/cache.h"
+#include "llvm_util/compare.h"
+#include "llvm_util/llvm2alive.h"
+#include "llvm_util/llvm_optimizer.h"
+#include "smt/smt.h"
+#include "tools/transform.h"
+#include "util/version.h"
+
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Bitcode/BitcodeReader.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Passes/PassBuilder.h"
+#include "llvm/Support/PrettyStackTrace.h"
+#include "llvm/Support/Signals.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+#include <fstream>
+#include <iostream>
+#include <random>
+#include <sstream>
+#include <utility>
+
+using namespace tools;
+using namespace util;
+using namespace std;
+using namespace llvm_util;
+
+#define LLVM_ARGS_PREFIX ""
+#define ARGS_SRC_TGT
+#define ARGS_REFINEMENT
+#include "llvm_util/cmd_args_list.h"
+
+namespace {
+
+llvm::cl::opt<long> opt_rand_seed(
+ LLVM_ARGS_PREFIX "seed",
+ llvm::cl::desc("Random seed (default = different every time)"),
+ llvm::cl::cat(alive_cmdargs), llvm::cl::init(0));
+
+llvm::cl::opt<long> opt_num_reps(
+ LLVM_ARGS_PREFIX "num-reps",
+ llvm::cl::desc(
+ "Number of times to generate and test a function (default=10)"),
+ llvm::cl::cat(alive_cmdargs), llvm::cl::init(10));
+
+llvm::cl::opt<bool>
+ opt_skip_alive(LLVM_ARGS_PREFIX "skip-alive",
+ llvm::cl::desc("Generate IR but then don't invoke Alive"),
+ llvm::cl::cat(alive_cmdargs), llvm::cl::init(false));
+
+llvm::cl::opt<bool> opt_run_sroa(
+ LLVM_ARGS_PREFIX "run-sroa",
+ llvm::cl::desc(
+ "Run SROA before llvm2alive, this reduces timeouts by reducing "
+ "the load on Alive's memory model"),
+ llvm::cl::cat(alive_cmdargs), llvm::cl::init(false));
+
+llvm::cl::opt<string> optPass(
+ LLVM_ARGS_PREFIX "passes", llvm::cl::value_desc("optimization passes"),
+ llvm::cl::desc("Specify which LLVM passes to run (default=O2). "
+ "The syntax is described at "
+ "https://llvm.org/docs/NewPassManager.html#invoking-opt"),
+ llvm::cl::cat(alive_cmdargs), llvm::cl::init("O2"));
+
+optional<smt::smt_initializer> smt_init;
+unique_ptr<Cache> cache;
+tv_stats stats;
+
+// FIXME we might want to be able to specify these on the command
+// line, but these should be pretty good defaults
+const int MaxBBs = 50;
+const int MaxWidth = 20;
+const int MaxCounters = 16;
+const int MaxBoolParams = 16;
+
+std::unique_ptr<std::mt19937_64> Rand;
+
+long choose(long Choices) {
+ std::uniform_int_distribution<int> Dist(0, Choices - 1);
+ return Dist(*Rand);
+}
+
+void init() {
+ auto Seed = (opt_rand_seed == 0) ? (std::random_device{}()) : opt_rand_seed;
+ cout << "seed = " << Seed << endl;
+ Rand = std::make_unique<std::mt19937_64>(Seed);
+}
+
+llvm::CmpInst::Predicate random_pred() {
+ return (llvm::CmpInst::Predicate)(
+ llvm::CmpInst::FIRST_ICMP_PREDICATE +
+ choose(llvm::CmpInst::LAST_ICMP_PREDICATE + 1 -
+ llvm::CmpInst::FIRST_ICMP_PREDICATE));
+}
+
+void generate(llvm::Module *M) {
+ auto &Ctx = M->getContext();
+
+ const int NumCounters = 1 + choose(MaxCounters);
+ const int NumBoolParams = 1 + choose(MaxBoolParams);
+ const int NumBBs = 2 + choose(MaxBBs);
+ const int Width = 1 + choose(MaxWidth);
+ auto *IntTy = llvm::Type::getIntNTy(Ctx, Width);
+
+ auto *Callee1Ty =
+ llvm::FunctionType::get(llvm::Type::getVoidTy(Ctx), {}, false);
+ auto *Callee1 = llvm::Function::Create(
+ Callee1Ty, llvm::GlobalValue::ExternalLinkage, 0, "c1", M);
+
+ auto *Callee2Ty =
+ llvm::FunctionType::get(llvm::Type::getVoidTy(Ctx), {IntTy}, false);
+ auto *Callee2 = llvm::Function::Create(
+ Callee2Ty, llvm::GlobalValue::ExternalLinkage, 0, "c2", M);
+
+ vector<llvm::Type *> ParamsTy;
+ auto *BoolTy = llvm::Type::getInt1Ty(Ctx);
+ for (int i = 0; i < NumBoolParams; ++i)
+ ParamsTy.push_back(BoolTy);
+ auto *FTy = llvm::FunctionType::get(IntTy, ParamsTy, false);
+ auto *F = llvm::Function::Create(FTy, llvm::GlobalValue::ExternalLinkage, 0,
+ "f", M);
+ vector<llvm::Argument *> Args;
+ for (auto &arg : F->args())
+ Args.push_back(&arg);
+ int FirstBoolParamIdx = 0;
+
+ vector<llvm::BasicBlock *> BBs;
+ for (int i = 0; i < NumBBs; ++i)
+ BBs.push_back(llvm::BasicBlock::Create(Ctx, "", F));
+
+ vector<llvm::Value *> Counters;
+ auto *Zero = llvm::ConstantInt::get(IntTy, 0);
+ auto *One = llvm::ConstantInt::get(IntTy, 1);
+ for (int i = 0; i < NumCounters; ++i) {
+ Counters.push_back(new llvm::AllocaInst(IntTy, 0, One, "", BBs[0]));
+ new llvm::StoreInst(Zero, Counters[i], BBs[0]);
+ }
+
+ for (int i = 0; i < NumBBs; ++i) {
+ if (choose(10) == 0) {
+ if (choose(2) == 0) {
+ auto idx = choose(NumCounters);
+ auto *Load = new llvm::LoadInst(IntTy, Counters[idx], "", BBs[i]);
+ llvm::CallInst::Create(Callee2Ty, Callee2, {Load}, "", BBs[i]);
+ } else {
+ llvm::CallInst::Create(Callee1Ty, Callee1, {}, "", BBs[i]);
+ }
+ } else {
+ auto idx = choose(NumCounters);
+ auto *Load = new llvm::LoadInst(IntTy, Counters[idx], "", BBs[i]);
+ auto *Inc = llvm::BinaryOperator::Create(llvm::Instruction::Add, Load,
+ One, "", BBs[i]);
+ if (choose(2) == 0)
+ Inc->setHasNoUnsignedWrap();
+ if (choose(2) == 0)
+ Inc->setHasNoSignedWrap();
+ new llvm::StoreInst(Inc, Counters[idx], BBs[i]);
+ }
+ }
+
+ for (int i = 0; i < NumBBs; ++i) {
+ again:
+ switch (choose(4)) {
+ case 0: {
+ if (i == 0 || (choose(100) > 25))
+ goto again;
+ auto idx = choose(NumCounters);
+ auto *Load = new llvm::LoadInst(IntTy, Counters[idx], "", BBs[i]);
+ llvm::ReturnInst::Create(Ctx, Load, BBs[i]);
+ } break;
+ case 1: {
+ auto *Dest = BBs[1 + choose(NumBBs - 1)];
+ llvm::BranchInst::Create(Dest, BBs[i]);
+ } break;
+ case 2: {
+ auto *Dest1 = BBs[1 + choose(NumBBs - 1)];
+ auto *Dest2 = BBs[1 + choose(NumBBs - 1)];
+ llvm::Value *Cond = nullptr;
+ if (choose(2) == 0) {
+ Cond = Args[FirstBoolParamIdx + choose(NumBoolParams)];
+ } else {
+ auto *LHS = new llvm::LoadInst(IntTy, Counters[choose(NumCounters)], "",
+ BBs[i]);
+ auto *RHS =
+ (choose(2) == 0)
+ ? new llvm::LoadInst(IntTy, Counters[choose(NumCounters)], "",
+ BBs[i])
+ : (llvm::Value *)llvm::ConstantInt::get(IntTy, choose(20));
+ Cond = new llvm::ICmpInst(*BBs[i], random_pred(), LHS, RHS);
+ }
+ llvm::BranchInst::Create(Dest1, Dest2, Cond, BBs[i]);
+ } break;
+ case 3: {
+ unsigned long NumCases = 1 + choose(2 * NumBBs);
+ auto *Load =
+ new llvm::LoadInst(IntTy, Counters[choose(NumCounters)], "", BBs[i]);
+ auto *Swch = llvm::SwitchInst::Create(Load, BBs[1 + choose(NumBBs - 1)],
+ NumCases, BBs[i]);
+ for (unsigned long i = 0; i < NumCases; ++i) {
+ if (i >= (1UL << Width))
+ break;
+ Swch->addCase(llvm::ConstantInt::get(IntTy, i),
+ BBs[1 + choose(NumBBs - 1)]);
+ if (choose(4) == 0)
+ i += choose(4);
+ }
+ } break;
+ default:
+ assert(false);
+ }
+ }
+
+ if (llvm::verifyModule(*M, &llvm::errs()))
+ llvm::report_fatal_error("Broken module found, this should not happen");
+}
+
+} // namespace
+
+int main(int argc, char **argv) {
+ llvm::sys::PrintStackTraceOnErrorSignal(argv[0]);
+ llvm::PrettyStackTraceProgram X(argc, argv);
+ llvm::EnableDebugBuffering = true;
+ llvm::llvm_shutdown_obj llvm_shutdown; // Call llvm_shutdown() on exit.
+ llvm::LLVMContext Context;
+
+ std::string Usage =
+ R"EOF(Alive2 simple generative fuzzer:
+version )EOF";
+ Usage += alive_version;
+ Usage += R"EOF(
+see quick-fuzz --version for LLVM version info,
+
+This program stress-tests LLVM and Alive2 by performing randomized
+generation of LLVM functions, optimizing them, and then checking
+refinement.
+
+It currently contains a single, simple generator that exercises loop
+and control flow optimizations, but additional generators are planned.
+
+The recommended workflow is to run quick-fuzz until it finds an issue,
+and then re-run with the same seed and also the --save-ir command line
+option, in order to get a standalone test case, which can then be
+reduced using llvm-reduce.
+)EOF";
+
+ llvm::cl::HideUnrelatedOptions(alive_cmdargs);
+ llvm::cl::ParseCommandLineOptions(argc, argv, Usage);
+ tv_opts opts(opt_quiet, opt_always_verify, opt_print_dot, opt_bidirectional);
+
+ unique_ptr<llvm::Module> MDummy;
+#define ARGS_MODULE_VAR MDummy
+#include "llvm_util/cmd_args_def.h"
+
+ init();
+
+ for (int rep = 0; rep < opt_num_reps; ++rep) {
+ auto M1 = make_unique<llvm::Module>("fuzz", Context);
+ generate(&*M1);
+
+ if (opt_run_sroa) {
+ auto err = optimize_module(M1.get(), "sroa,dse");
+ assert(err.empty());
+ }
+
+ if (opt_save_ir) {
+ stringstream output_fn;
+ output_fn << "file_" << rep << ".bc";
+ *out << "saving IR as '" << output_fn.str() << "'\n";
+ std::error_code EC;
+ llvm::raw_fd_ostream output_file(output_fn.str(), EC);
+ if (EC)
+ llvm::report_fatal_error("Couldn't open output file, exiting");
+ llvm::WriteBitcodeToFile(*M1.get(), output_file);
+ }
+
+ if (opt_skip_alive)
+ continue;
+
+ auto &DL = M1.get()->getDataLayout();
+ llvm::Triple targetTriple(M1.get()->getTargetTriple());
+ llvm::TargetLibraryInfoWrapperPass TLI(targetTriple);
+
+ llvm_util::initializer llvm_util_init(*out, DL);
+ smt_init.emplace();
+
+ unique_ptr<llvm::Module> M2;
+ M2 = CloneModule(*M1);
+ auto err = optimize_module(M2.get(), optPass);
+ if (!err.empty()) {
+ *out << "Error parsing list of LLVM passes: " << err << '\n';
+ return -1;
+ }
+
+ if (M1.get()->getTargetTriple() != M2.get()->getTargetTriple()) {
+ *out << "Modules have different target triples\n";
+ return -1;
+ }
+
+ auto *F1 = M1->getFunction("f");
+ auto *F2 = M2->getFunction("f");
+ assert(F1 && F2);
+
+ if (!compareFunctions(*F1, *F2, TLI, *smt_init, stats, opts, out))
+ if (opt_error_fatal)
+ goto end;
+ }
+
+ *out << "Summary:\n"
+ " "
+ << stats.num_correct
+ << " correct transformations\n"
+ " "
+ << stats.num_unsound
+ << " incorrect transformations\n"
+ " "
+ << stats.num_failed
+ << " failed-to-prove transformations\n"
+ " "
+ << stats.num_errors << " Alive2 errors\n";
+
+end:
+ if (opt_smt_stats)
+ smt::solver_print_stats(*out);
+
+ smt_init.reset();
+
+ if (opt_alias_stats)
+ IR::Memory::printAliasStats(*out);
+
+ return stats.num_errors > 0;
+}

add a small basic block fuzzer that has already found a few bugs (#873)

the tool is called quick-fuzz instead of bb-fuzz because I'd like
to add a few more little fuzzers like this to it in the future

also factor out some common machinery from alive-tv.cpp