From 257b2fbc313246568833e286d339ef20340d2598 Mon Sep 17 00:00:00 2001 From: Aidan Kirk Date: Wed, 9 Jul 2025 16:08:08 -0700 Subject: [PATCH] Added a test to the IR Fuzzer that verifies the result of IR before and after an optimization pass. A new IrFuzzTest was added which generates random IR, runs the ReassociationPass over it, plugs in parameters into the non-reassociated IR and the reassociated IR, and verifies that the results are the same. To achieve this, I added a function which accepts an optimization pass object and then proceeds to perform all of the logic. Additionally, the IrFuzzDomain was updated to allow you to generate fuzzed integer parameters, with a way to configure how many parameter sets are generated for each IR function. PiperOrigin-RevId: 781249205 --- xls/fuzzer/ir_fuzzer/BUILD | 55 +++++++-- xls/fuzzer/ir_fuzzer/ir_fuzz_builder_test.cc | 3 +- xls/fuzzer/ir_fuzzer/ir_fuzz_domain.cc | 85 +++++++++++++ xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h | 17 ++- xls/fuzzer/ir_fuzzer/ir_fuzz_test.cc | 6 +- xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.cc | 120 +++++++++++++++++++ xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.h | 31 +++++ xls/passes/BUILD | 6 + xls/passes/reassociation_pass_test.cc | 20 ++++ 9 files changed, 329 insertions(+), 14 deletions(-) create mode 100644 xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.cc create mode 100644 xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.h diff --git a/xls/fuzzer/ir_fuzzer/BUILD b/xls/fuzzer/ir_fuzzer/BUILD index a77996673f..7d2f87ece2 100644 --- a/xls/fuzzer/ir_fuzzer/BUILD +++ b/xls/fuzzer/ir_fuzzer/BUILD @@ -23,20 +23,25 @@ package( cc_library( name = "ir_fuzz_domain", - testonly = 1, + testonly = True, srcs = ["ir_fuzz_domain.cc"], hdrs = ["ir_fuzz_domain.h"], deps = [ ":fuzz_program_cc_proto", ":ir_fuzz_builder", + ":ir_fuzz_helpers", "//xls/common/fuzzing:fuzztest", "//xls/common/status:ret_check", "//xls/ir", + "//xls/ir:bits", "//xls/ir:function_builder", "//xls/ir:ir_test_base", + "//xls/ir:value", "//xls/ir:verifier", + "@com_google_absl//absl/log", "@com_google_absl//absl/log:check", "@com_google_absl//absl/status:statusor", + "@com_google_absl//absl/types:span", ], ) @@ -49,6 +54,7 @@ cc_test( "//xls/common/fuzzing:fuzztest", "//xls/common/status:matchers", "//xls/ir", + "//xls/ir:function_builder", "//xls/ir:ir_test_base", "//xls/ir:verifier", "@com_google_absl//absl/log", @@ -105,6 +111,27 @@ cc_library( ], ) +cc_test( + name = "ir_fuzz_builder_test", + srcs = ["ir_fuzz_builder_test.cc"], + deps = [ + ":fuzz_program_cc_proto", + ":ir_fuzz_builder", + "//xls/common:xls_gunit_main", + "//xls/common/fuzzing:fuzztest", + "//xls/common/status:matchers", + "//xls/ir", + "//xls/ir:bits", + "//xls/ir:function_builder", + "//xls/ir:ir_matcher", + "//xls/ir:ir_test_base", + "//xls/ir:verifier", + "@com_google_absl//absl/strings:str_format", + "@com_google_protobuf//:protobuf", + "@googletest//:gtest", + ], +) + cc_library( name = "ir_fuzz_visitor", srcs = ["ir_fuzz_visitor.cc"], @@ -137,23 +164,29 @@ cc_test( ], ) -cc_test( - name = "ir_fuzz_builder_test", - srcs = ["ir_fuzz_builder_test.cc"], +cc_library( + name = "ir_fuzz_test_library", + testonly = True, + srcs = ["ir_fuzz_test_library.cc"], + hdrs = ["ir_fuzz_test_library.h"], deps = [ ":fuzz_program_cc_proto", - ":ir_fuzz_builder", - "//xls/common:xls_gunit_main", + ":ir_fuzz_domain", "//xls/common/fuzzing:fuzztest", "//xls/common/status:matchers", + "//xls/common/status:status_macros", + "//xls/interpreter:ir_interpreter", "//xls/ir", - "//xls/ir:bits", + "//xls/ir:events", "//xls/ir:function_builder", - "//xls/ir:ir_matcher", "//xls/ir:ir_test_base", + "//xls/ir:value", "//xls/ir:verifier", - "@com_google_absl//absl/strings:str_format", - "@com_google_protobuf//:protobuf", - "@googletest//:gtest", + "//xls/passes:optimization_pass", + "//xls/passes:pass_base", + "@com_google_absl//absl/log", + "@com_google_absl//absl/log:check", + "@com_google_absl//absl/status:statusor", + "@com_google_absl//absl/types:span", ], ) diff --git a/xls/fuzzer/ir_fuzzer/ir_fuzz_builder_test.cc b/xls/fuzzer/ir_fuzzer/ir_fuzz_builder_test.cc index f510d9a43e..58a98bdc79 100644 --- a/xls/fuzzer/ir_fuzzer/ir_fuzz_builder_test.cc +++ b/xls/fuzzer/ir_fuzzer/ir_fuzz_builder_test.cc @@ -33,7 +33,8 @@ namespace m = ::xls::op_matchers; // Performs tests on the IrFuzzBuilder by manually creating a FuzzProgramProto, -// instantiating into its IR version, and manually verifying the IR is correct. +// instantiating it into its IR version, and manually verifying the IR is +// correct. namespace xls { namespace { diff --git a/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.cc b/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.cc index c62d6c3af9..de0a6c36e1 100644 --- a/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.cc +++ b/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.cc @@ -15,17 +15,23 @@ #include "xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h" #include +#include #include #include "xls/common/fuzzing/fuzztest.h" #include "absl/log/check.h" +#include "absl/log/log.h" #include "absl/status/statusor.h" +#include "absl/types/span.h" #include "xls/common/status/ret_check.h" #include "xls/fuzzer/ir_fuzzer/fuzz_program.pb.h" #include "xls/fuzzer/ir_fuzzer/ir_fuzz_builder.h" +#include "xls/fuzzer/ir_fuzzer/ir_fuzz_helpers.h" +#include "xls/ir/bits.h" #include "xls/ir/function_builder.h" #include "xls/ir/ir_test_base.h" #include "xls/ir/package.h" +#include "xls/ir/value.h" #include "xls/ir/verifier.h" namespace xls { @@ -44,6 +50,50 @@ absl::StatusOr> BuildPackage( return std::move(p); } +// A domain that expands upon the IrFuzzDomain by returning a vector of bytes +// parameters along with the Package. The strings in the vector correlate to a +// parameter input into the Function. A fuzztest::FlatMap is used in order to +// create the IrFuzzDomain first, then determine the number of parameters in the +// Function in order to randomly generate a vector of strings. +fuzztest::Domain< + std::pair, std::vector>>> +IrFuzzDomainWithBytesParams(int64_t param_set_count) { + return fuzztest::FlatMap( + [param_set_count](std::shared_ptr p) { + Function* f = p->GetFunction(IrTestBase::TestName()).value(); + return fuzztest::PairOf( + // fuzztest::Just does not like to deal with move-only types so we + // are using a shared_ptr for now. + fuzztest::Just(std::move(p)), + // A string represents a byte array. The byte array can be + // interpreted as a large integer. + fuzztest::VectorOf( + fuzztest::VectorOf(fuzztest::Arbitrary()) + // Retrieve the number of parameters in the Function. + .WithSize(f->params().size())) + // Generate param_set_count number of param sets. + .WithSize(param_set_count)); + }, + IrFuzzDomain()); +} + +// Returns a human-readable string representation of the param sets. +std::string StringifyParamSets( + absl::Span> param_sets) { + std::stringstream ss; + ss << "["; + // Iterate over the number of param sets. + for (int64_t i = 0; i < param_sets.size(); i += 1) { + // Iterate over the param set elements. + for (int64_t j = 0; j < param_sets[i].size(); j += 1) { + ss << (param_sets[i][j].ToHumanString()) + << (j != param_sets[i].size() - 1 ? ", " : ""); + } + ss << (i != param_sets.size() - 1 ? "], [" : "]"); + } + return ss.str(); +} + } // namespace // Returns a fuzztest domain, which is a range of possible values that an object @@ -89,4 +139,39 @@ fuzztest::Domain> IrFuzzDomain() { .WithMinSize(1))); } +// A domain that expands upon the IrFuzzDomainWithBytesParams by converting the +// string parameters into a vector of Value objects. This vector can be plugged +// into the Function directly for interpreting the IR. The byte arrays are +// truncated to the bit width of the parameters. The param_set_count parameter +// specifies the number of param sets to generate in case you need multiple sets +// of inputs for testing. +// TODO: Consider using randomly generated parameter values with something like +// absl::BitGen instead of FuzzTest because FuzzTest does not have much of an +// advantage over the simplicity of absl::BitGen in this case. +fuzztest::Domain IrFuzzDomainWithParams( + int64_t param_set_count) { + return fuzztest::Map( + [](std::pair, + std::vector>> + bytes_paramaterized_package) { + auto [p, bytes_param_sets] = bytes_paramaterized_package; + Function* f = p->GetFunction(IrTestBase::TestName()).value(); + std::vector> param_sets(bytes_param_sets.size()); + // Iterate over the number of param sets. + for (int64_t i = 0; i < bytes_param_sets.size(); i += 1) { + // Iterate over the actual function parameters. + for (int64_t j = 0; j < bytes_param_sets[i].size(); j += 1) { + // Truncate the byte arrays to the bit width of the parameters. + int64_t bit_width = f->param(j)->BitCountOrDie(); + Bits value_bits = + ChangeBytesBitWidth(bytes_param_sets[i][j], bit_width); + param_sets[i].push_back(Value(value_bits)); + } + } + VLOG(3) << "2. Param Sets: " << StringifyParamSets(param_sets); + return PackageAndTestParams(p, param_sets); + }, + IrFuzzDomainWithBytesParams(param_set_count)); +} + } // namespace xls diff --git a/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h b/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h index 10c26af52d..9a7bfea52b 100644 --- a/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h +++ b/xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h @@ -15,16 +15,31 @@ #ifndef XLS_FUZZER_IR_FUZZER_IR_FUZZ_DOMAIN_H_ #define XLS_FUZZER_IR_FUZZER_IR_FUZZ_DOMAIN_H_ -#include +#include #include "xls/common/fuzzing/fuzztest.h" #include "xls/ir/package.h" +#include "xls/ir/value.h" + +// Contains functions that return IR fuzz test domains. namespace xls { +// Stores a Package object which contains a function. param_sets contains +// multiple sets of parameter values for the function. +struct PackageAndTestParams { + std::shared_ptr p; + std::vector> param_sets; +}; + +// These functions return a shared_ptr instead of a unique_ptr because the +// IrFuzzDomainWithBytesParams() function in the ir_fuzz_domain.cc file uses +// fuzztest::Just() which refuses to deal with move-only types. // TODO: Implement a clone_ptr class that makes a deep copy of a // unique_ptr to avoid returning a shared_ptr. fuzztest::Domain> IrFuzzDomain(); +fuzztest::Domain IrFuzzDomainWithParams( + int64_t param_set_count = 1); } // namespace xls diff --git a/xls/fuzzer/ir_fuzzer/ir_fuzz_test.cc b/xls/fuzzer/ir_fuzzer/ir_fuzz_test.cc index 65479c9b65..d2d89bdadc 100644 --- a/xls/fuzzer/ir_fuzzer/ir_fuzz_test.cc +++ b/xls/fuzzer/ir_fuzzer/ir_fuzz_test.cc @@ -18,7 +18,11 @@ #include "absl/log/log.h" #include "xls/common/status/matchers.h" #include "xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h" +#include "xls/ir/function.h" +#include "xls/ir/function_builder.h" #include "xls/ir/ir_test_base.h" +#include "xls/ir/node.h" +#include "xls/ir/nodes.h" #include "xls/ir/package.h" #include "xls/ir/verifier.h" @@ -31,7 +35,7 @@ void VerifyIrFuzzPackage(std::shared_ptr p) { XLS_ASSERT_OK(VerifyPackage(p.get())); XLS_ASSERT_OK_AND_ASSIGN(Function * f, p->GetFunction(IrTestBase::TestName())); - VLOG(3) << "3. IR:" << "\n" << f->DumpIr() << "\n"; + VLOG(3) << "2. IR:" << "\n" << f->DumpIr() << "\n"; } // Use of gtest FUZZ_TEST to randomly generate IR while being compatible with // Google infrastructure. The IrFuzzTest function is called and represents the diff --git a/xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.cc b/xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.cc new file mode 100644 index 0000000000..43b6e7e1e6 --- /dev/null +++ b/xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.cc @@ -0,0 +1,120 @@ +// Copyright 2025 The XLS Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.h" + +#include +#include +#include +#include + +#include "xls/common/fuzzing/fuzztest.h" +#include "absl/log/check.h" +#include "absl/log/log.h" +#include "absl/status/statusor.h" +#include "absl/types/span.h" +#include "xls/common/status/matchers.h" +#include "xls/common/status/status_macros.h" +#include "xls/fuzzer/ir_fuzzer/fuzz_program.pb.h" +#include "xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h" +#include "xls/interpreter/function_interpreter.h" +#include "xls/ir/events.h" +#include "xls/ir/function.h" +#include "xls/ir/function_builder.h" +#include "xls/ir/ir_test_base.h" +#include "xls/ir/nodes.h" +#include "xls/ir/package.h" +#include "xls/ir/value.h" +#include "xls/ir/verifier.h" +#include "xls/passes/optimization_pass.h" +#include "xls/passes/pass_base.h" + +namespace xls { +namespace { + +// Evaluates the IR function with a set of parameter values. +absl::StatusOr>> EvaluateParamSets( + Function* f, absl::Span> param_sets) { + std::vector> results; + for (const std::vector& param_set : param_sets) { + XLS_ASSIGN_OR_RETURN(InterpreterResult result, + InterpretFunction(f, param_set)); + results.push_back(result); + } + return results; +} + +// Returns a human-readable string representation of the results. +std::string StringifyResults( + absl::Span> results) { + std::stringstream ss; + ss << "["; + for (int64_t i = 0; i < results.size(); i += 1) { + ss << results[i].value; + ss << (i != results.size() - 1 ? ", " : "]"); + } + return ss.str(); +} + +} // namespace + +// Takes an IR function from a Package object and puts it through an +// optimization pass. It then evaluates the IR function with a set of parameter +// values before and after the pass. It returns the boolean value of whether the +// results changed. +void OptimizationPassChangesOutputs( + const PackageAndTestParams& paramaterized_package, + const OptimizationPass& pass) { + // Verify that valid IR was generated. + XLS_ASSERT_OK(VerifyPackage(paramaterized_package.p.get())); + XLS_ASSERT_OK_AND_ASSIGN(Function * f, paramaterized_package.p->GetFunction( + IrTestBase::TestName())); + VLOG(3) << "3. Before Pass IR:" << "\n" << f->DumpIr() << "\n"; + // Interpret the IR function with the parameters before reassociation. + XLS_ASSERT_OK_AND_ASSIGN( + std::vector> before_pass_results, + EvaluateParamSets(f, paramaterized_package.param_sets)); + // Run the pass over the IR. + PassResults results; + OptimizationContext context; + XLS_ASSERT_OK_AND_ASSIGN( + bool ir_changed, pass.Run(paramaterized_package.p.get(), + OptimizationPassOptions(), &results, context)); + VLOG(3) << "4. After Pass IR:" << "\n" << f->DumpIr() << "\n"; + // Interpret the IR function with the parameters after reassociation. + XLS_ASSERT_OK_AND_ASSIGN( + std::vector> after_pass_results, + EvaluateParamSets(f, paramaterized_package.param_sets)); + VLOG(3) << "5. IR Changed: " << (ir_changed ? "TRUE" : "FALSE") << "\n"; + VLOG(3) << "6. Before Pass Results: " << StringifyResults(before_pass_results) + << "\n"; + VLOG(3) << "7. After Pass Results: " << StringifyResults(after_pass_results) + << "\n"; + // Check if the results are the same before and after reassociation. + bool results_changed = false; + for (int64_t i = 0; i < before_pass_results.size(); i += 1) { + if (before_pass_results[i].value != after_pass_results[i].value) { + results_changed = true; + break; + } + } + VLOG(3) << "8. Results Changed: " << (results_changed ? "TRUE" : "FALSE") + << "\n"; + CHECK_EQ(results_changed, false) + << "\n" + << "Expected: " << StringifyResults(before_pass_results) << "\n" + << "Actual: " << StringifyResults(after_pass_results); +} + +} // namespace xls diff --git a/xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.h b/xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.h new file mode 100644 index 0000000000..f5f34a5b99 --- /dev/null +++ b/xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.h @@ -0,0 +1,31 @@ +// Copyright 2025 The XLS Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef XLS_FUZZER_IR_FUZZER_IR_FUZZ_TEST_LIBRARY_H_ +#define XLS_FUZZER_IR_FUZZER_IR_FUZZ_TEST_LIBRARY_H_ + +#include "xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h" +#include "xls/passes/optimization_pass.h" + +// Contains functions that are used in IR fuzz tests. + +namespace xls { + +void OptimizationPassChangesOutputs( + const PackageAndTestParams& paramaterized_package, + const OptimizationPass& pass); + +} // namespace xls + +#endif // XLS_FUZZER_IR_FUZZER_IR_FUZZ_TEST_LIBRARY_H_ diff --git a/xls/passes/BUILD b/xls/passes/BUILD index 4484038b5c..fa94cc1ce0 100644 --- a/xls/passes/BUILD +++ b/xls/passes/BUILD @@ -3164,8 +3164,12 @@ cc_test( ":pass_test_helpers", ":reassociation_pass", "//xls/common:xls_gunit_main", + "//xls/common/fuzzing:fuzztest", "//xls/common/status:matchers", "//xls/common/status:status_macros", + "//xls/fuzzer/ir_fuzzer:fuzz_program_cc_proto", + "//xls/fuzzer/ir_fuzzer:ir_fuzz_domain", + "//xls/fuzzer/ir_fuzzer:ir_fuzz_test_library", "//xls/ir", "//xls/ir:bits", "//xls/ir:function_builder", @@ -3174,9 +3178,11 @@ cc_test( "//xls/ir:op", "//xls/ir:type", "//xls/ir:value", + "//xls/ir:verifier", "//xls/solvers:z3_ir_equivalence_testutils", "@com_google_absl//absl/algorithm:container", "@com_google_absl//absl/container:flat_hash_map", + "@com_google_absl//absl/log", "@com_google_absl//absl/status:statusor", "@com_google_absl//absl/strings", "@com_google_absl//absl/strings:str_format", diff --git a/xls/passes/reassociation_pass_test.cc b/xls/passes/reassociation_pass_test.cc index 08cdb3b70d..3ef8459fda 100644 --- a/xls/passes/reassociation_pass_test.cc +++ b/xls/passes/reassociation_pass_test.cc @@ -19,8 +19,10 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "xls/common/fuzzing/fuzztest.h" #include "absl/algorithm/container.h" #include "absl/container/flat_hash_map.h" +#include "absl/log/log.h" #include "absl/status/statusor.h" #include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" @@ -28,6 +30,9 @@ #include "absl/types/span.h" #include "xls/common/status/matchers.h" #include "xls/common/status/status_macros.h" +#include "xls/fuzzer/ir_fuzzer/fuzz_program.pb.h" +#include "xls/fuzzer/ir_fuzzer/ir_fuzz_domain.h" +#include "xls/fuzzer/ir_fuzzer/ir_fuzz_test_library.h" #include "xls/ir/bits.h" #include "xls/ir/function.h" #include "xls/ir/function_builder.h" @@ -40,6 +45,7 @@ #include "xls/ir/topo_sort.h" #include "xls/ir/type.h" #include "xls/ir/value.h" +#include "xls/ir/verifier.h" #include "xls/passes/arith_simplification_pass.h" #include "xls/passes/basic_simplification_pass.h" #include "xls/passes/bit_slice_simplification_pass.h" @@ -1334,5 +1340,19 @@ TEST_F(ReassociationPassTest, MulOverflow2) { EXPECT_EQ(MaxOpDepth({Op::kUMul}, f), 4); } +// Generates random IR, runs the ReassociationPass over it, plugs in parameters +// into the non-reassociated IR and the reassociated IR, and verifies that the +// results are the same. +void IrFuzzReassociationPassTest( + const PackageAndTestParams& paramaterized_package) { + ReassociationPass pass; + OptimizationPassChangesOutputs(paramaterized_package, pass); +} +// Use the IrFuzzDomainWithParams domain to generate random integer parameters +// that can be plugged into the IR function. This test generates 10 different +// sets of parameters. +FUZZ_TEST(IrFuzzTest, IrFuzzReassociationPassTest) + .WithDomains(IrFuzzDomainWithParams(10)); + } // namespace } // namespace xls