spirv-fuzz: Integrate spirv-reduce with shrinker (#3849)
This extends shrinking so that spirv-reduce is employed to simplify
the functions that are added by TransformationAddFunction.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index ef699a7..050bd96 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -36,6 +36,7 @@
)
set(SPIRV_TOOLS_FUZZ_SOURCES
+ added_function_reducer.h
call_graph.h
comparator_deep_blocks_first.h
counter_overflow_id_source.h
@@ -218,6 +219,7 @@
uniform_buffer_element_descriptor.h
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
+ added_function_reducer.cpp
call_graph.cpp
counter_overflow_id_source.cpp
data_descriptor.cpp
@@ -429,6 +431,7 @@
target_link_libraries(SPIRV-Tools-fuzz
PUBLIC ${SPIRV_TOOLS}-static
PUBLIC SPIRV-Tools-opt
+ PUBLIC SPIRV-Tools-reduce
PUBLIC protobuf::libprotobuf)
set_property(TARGET SPIRV-Tools-fuzz PROPERTY FOLDER "SPIRV-Tools libraries")
diff --git a/source/fuzz/added_function_reducer.cpp b/source/fuzz/added_function_reducer.cpp
new file mode 100644
index 0000000..0ea88c8
--- /dev/null
+++ b/source/fuzz/added_function_reducer.cpp
@@ -0,0 +1,293 @@
+// Copyright (c) 2020 Google LLC
+//
+// 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 "source/fuzz/added_function_reducer.h"
+
+#include "source/fuzz/instruction_message.h"
+#include "source/fuzz/replayer.h"
+#include "source/fuzz/transformation_add_function.h"
+#include "source/opt/build_module.h"
+#include "source/opt/ir_context.h"
+#include "source/reduce/reducer.h"
+
+namespace spvtools {
+namespace fuzz {
+
+AddedFunctionReducer::AddedFunctionReducer(
+ spv_target_env target_env, MessageConsumer consumer,
+ const std::vector<uint32_t>& binary_in,
+ const protobufs::FactSequence& initial_facts,
+ const protobufs::TransformationSequence& transformation_sequence_in,
+ uint32_t index_of_add_function_transformation,
+ const Shrinker::InterestingnessFunction& shrinker_interestingness_function,
+ bool validate_during_replay, spv_validator_options validator_options,
+ uint32_t shrinker_step_limit, uint32_t num_existing_shrink_attempts)
+ : target_env_(target_env),
+ consumer_(std::move(consumer)),
+ binary_in_(binary_in),
+ initial_facts_(initial_facts),
+ transformation_sequence_in_(transformation_sequence_in),
+ index_of_add_function_transformation_(
+ index_of_add_function_transformation),
+ shrinker_interestingness_function_(shrinker_interestingness_function),
+ validate_during_replay_(validate_during_replay),
+ validator_options_(validator_options),
+ shrinker_step_limit_(shrinker_step_limit),
+ num_existing_shrink_attempts_(num_existing_shrink_attempts),
+ num_reduction_attempts_(0) {}
+
+AddedFunctionReducer::~AddedFunctionReducer() = default;
+
+AddedFunctionReducer::AddedFunctionReducerResult AddedFunctionReducer::Run() {
+ // Replay all transformations before the AddFunction transformation, then
+ // add the raw function associated with the AddFunction transformation.
+ std::vector<uint32_t> binary_to_reduce;
+ std::unordered_set<uint32_t> irrelevant_pointee_global_variables;
+ ReplayPrefixAndAddFunction(&binary_to_reduce,
+ &irrelevant_pointee_global_variables);
+
+ // Set up spirv-reduce to use our very specific interestingness function.
+ reduce::Reducer reducer(target_env_);
+ reducer.SetMessageConsumer(consumer_);
+ reducer.AddDefaultReductionPasses();
+ reducer.SetInterestingnessFunction(
+ [this, &irrelevant_pointee_global_variables](
+ const std::vector<uint32_t>& binary_under_reduction,
+ uint32_t /*unused*/) {
+ return InterestingnessFunctionForReducingAddedFunction(
+ binary_under_reduction, irrelevant_pointee_global_variables);
+ });
+
+ // Instruct spirv-reduce to only target the function with the id associated
+ // with the AddFunction transformation that we care about.
+ spvtools::ReducerOptions reducer_options;
+ reducer_options.set_target_function(GetAddedFunctionId());
+ // Bound the number of reduction steps that spirv-reduce can make according
+ // to the overall shrinker step limit and the number of shrink attempts that
+ // have already been tried.
+ assert(shrinker_step_limit_ > num_existing_shrink_attempts_ &&
+ "The added function reducer should not have been invoked.");
+ reducer_options.set_step_limit(shrinker_step_limit_ -
+ num_existing_shrink_attempts_);
+
+ // Run spirv-reduce.
+ std::vector<uint32_t> reduced_binary;
+ auto reducer_result =
+ reducer.Run(std::move(binary_to_reduce), &reduced_binary, reducer_options,
+ validator_options_);
+ if (reducer_result != reduce::Reducer::kComplete &&
+ reducer_result != reduce::Reducer::kReachedStepLimit) {
+ return {AddedFunctionReducerResultStatus::kReductionFailed,
+ std::vector<uint32_t>(), protobufs::TransformationSequence(), 0};
+ }
+
+ // Provide the outer shrinker with an adapted sequence of transformations in
+ // which the AddFunction transformation of interest has been simplified to use
+ // the version of the added function that appears in |reduced_binary|.
+ std::vector<uint32_t> binary_out;
+ protobufs::TransformationSequence transformation_sequence_out;
+ ReplayAdaptedTransformations(reduced_binary, &binary_out,
+ &transformation_sequence_out);
+ return {AddedFunctionReducerResultStatus::kComplete, std::move(binary_out),
+ std::move(transformation_sequence_out), num_reduction_attempts_};
+}
+
+bool AddedFunctionReducer::InterestingnessFunctionForReducingAddedFunction(
+ const std::vector<uint32_t>& binary_under_reduction,
+ const std::unordered_set<uint32_t>& irrelevant_pointee_global_variables) {
+ uint32_t counter_for_shrinker_interestingness_function =
+ num_existing_shrink_attempts_ + num_reduction_attempts_;
+ num_reduction_attempts_++;
+
+ // The reduced version of the added function must be limited to accessing
+ // global variables appearing in |irrelevant_pointee_global_variables|. This
+ // is to guard against the possibility of spirv-reduce changing a reference
+ // to an irrelevant global to a reference to a regular global variable, which
+ // could cause the added function to change the semantics of the original
+ // module.
+ auto ir_context =
+ BuildModule(target_env_, consumer_, binary_under_reduction.data(),
+ binary_under_reduction.size());
+ assert(ir_context != nullptr && "The binary should be parsable.");
+ for (auto& type_or_value : ir_context->module()->types_values()) {
+ if (type_or_value.opcode() != SpvOpVariable) {
+ continue;
+ }
+ if (irrelevant_pointee_global_variables.count(type_or_value.result_id())) {
+ continue;
+ }
+ if (!ir_context->get_def_use_mgr()->WhileEachUse(
+ &type_or_value,
+ [this, &ir_context](opt::Instruction* user,
+ uint32_t /*unused*/) -> bool {
+ auto block = ir_context->get_instr_block(user);
+ if (block != nullptr &&
+ block->GetParent()->result_id() == GetAddedFunctionId()) {
+ return false;
+ }
+ return true;
+ })) {
+ return false;
+ }
+ }
+
+ // For the binary to be deemed interesting, it must be possible to
+ // successfully apply all the transformations, with the transformation at
+ // index |index_of_add_function_transformation_| simplified to use the version
+ // of the added function from |binary_under_reduction|.
+ //
+ // This might not be the case: spirv-reduce might have removed a chunk of the
+ // added function on which future transformations depend.
+ //
+ // This is an optimization: the assumption is that having already shrunk the
+ // transformation sequence down to minimal form, all transformations have a
+ // role to play, and it's almost certainly a waste of time to invoke the
+ // shrinker's interestingness function if we have eliminated transformations
+ // that the shrinker previously tried to -- but could not -- eliminate.
+ std::vector<uint32_t> binary_out;
+ protobufs::TransformationSequence modified_transformations;
+ ReplayAdaptedTransformations(binary_under_reduction, &binary_out,
+ &modified_transformations);
+ if (transformation_sequence_in_.transformation_size() !=
+ modified_transformations.transformation_size()) {
+ return false;
+ }
+
+ // The resulting binary must be deemed interesting according to the shrinker's
+ // interestingness function.
+ return shrinker_interestingness_function_(
+ binary_out, counter_for_shrinker_interestingness_function);
+}
+
+void AddedFunctionReducer::ReplayPrefixAndAddFunction(
+ std::vector<uint32_t>* binary_out,
+ std::unordered_set<uint32_t>* irrelevant_pointee_global_variables) const {
+ assert(transformation_sequence_in_
+ .transformation(index_of_add_function_transformation_)
+ .has_add_function() &&
+ "A TransformationAddFunction is required at the given index.");
+
+ auto replay_result = Replayer(target_env_, consumer_, binary_in_,
+ initial_facts_, transformation_sequence_in_,
+ index_of_add_function_transformation_,
+ validate_during_replay_, validator_options_)
+ .Run();
+ assert(replay_result.status == Replayer::ReplayerResultStatus::kComplete &&
+ "Replay should succeed");
+ assert(static_cast<uint32_t>(
+ replay_result.applied_transformations.transformation_size()) ==
+ index_of_add_function_transformation_ &&
+ "All requested transformations should have applied.");
+
+ auto* ir_context = replay_result.transformed_module.get();
+
+ for (auto& type_or_value : ir_context->module()->types_values()) {
+ if (type_or_value.opcode() != SpvOpVariable) {
+ continue;
+ }
+ if (replay_result.transformation_context->GetFactManager()
+ ->PointeeValueIsIrrelevant(type_or_value.result_id())) {
+ irrelevant_pointee_global_variables->insert(type_or_value.result_id());
+ }
+ }
+
+ // Add the function associated with the transformation at
+ // |index_of_add_function_transformation| to the module. By construction this
+ // should succeed.
+ const protobufs::TransformationAddFunction&
+ transformation_add_function_message =
+ transformation_sequence_in_
+ .transformation(index_of_add_function_transformation_)
+ .add_function();
+ bool success = TransformationAddFunction(transformation_add_function_message)
+ .TryToAddFunction(ir_context);
+ (void)success; // Keep release mode compilers happy.
+ assert(success && "Addition of the function should have succeeded.");
+
+ // Get the binary representation of the module with this function added.
+ ir_context->module()->ToBinary(binary_out, false);
+}
+
+void AddedFunctionReducer::ReplayAdaptedTransformations(
+ const std::vector<uint32_t>& binary_under_reduction,
+ std::vector<uint32_t>* binary_out,
+ protobufs::TransformationSequence* transformation_sequence_out) const {
+ assert(index_of_add_function_transformation_ <
+ static_cast<uint32_t>(
+ transformation_sequence_in_.transformation_size()) &&
+ "The relevant add function transformation must be present.");
+ std::unique_ptr<opt::IRContext> ir_context_under_reduction =
+ BuildModule(target_env_, consumer_, binary_under_reduction.data(),
+ binary_under_reduction.size());
+ assert(ir_context_under_reduction && "Error building module.");
+
+ protobufs::TransformationSequence modified_transformations;
+ for (uint32_t i = 0;
+ i <
+ static_cast<uint32_t>(transformation_sequence_in_.transformation_size());
+ i++) {
+ if (i == index_of_add_function_transformation_) {
+ protobufs::TransformationAddFunction modified_add_function =
+ transformation_sequence_in_
+ .transformation(index_of_add_function_transformation_)
+ .add_function();
+ assert(GetAddedFunctionId() ==
+ modified_add_function.instruction(0).result_id() &&
+ "Unexpected result id for added function.");
+ modified_add_function.clear_instruction();
+ for (auto& function : *ir_context_under_reduction->module()) {
+ if (function.result_id() != GetAddedFunctionId()) {
+ continue;
+ }
+ function.ForEachInst(
+ [&modified_add_function](const opt::Instruction* instruction) {
+ *modified_add_function.add_instruction() =
+ MakeInstructionMessage(instruction);
+ });
+ }
+ assert(modified_add_function.instruction_size() > 0 &&
+ "Some instructions for the added function should remain.");
+ *modified_transformations.add_transformation()->mutable_add_function() =
+ modified_add_function;
+ } else {
+ *modified_transformations.add_transformation() =
+ transformation_sequence_in_.transformation(i);
+ }
+ }
+ assert(
+ transformation_sequence_in_.transformation_size() ==
+ modified_transformations.transformation_size() &&
+ "The original and modified transformations should have the same size.");
+ auto replay_result = Replayer(target_env_, consumer_, binary_in_,
+ initial_facts_, modified_transformations,
+ modified_transformations.transformation_size(),
+ validate_during_replay_, validator_options_)
+ .Run();
+ assert(replay_result.status == Replayer::ReplayerResultStatus::kComplete &&
+ "Replay should succeed.");
+ replay_result.transformed_module->module()->ToBinary(binary_out, false);
+ *transformation_sequence_out =
+ std::move(replay_result.applied_transformations);
+}
+
+uint32_t AddedFunctionReducer::GetAddedFunctionId() const {
+ return transformation_sequence_in_
+ .transformation(index_of_add_function_transformation_)
+ .add_function()
+ .instruction(0)
+ .result_id();
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/added_function_reducer.h b/source/fuzz/added_function_reducer.h
new file mode 100644
index 0000000..9dcc632
--- /dev/null
+++ b/source/fuzz/added_function_reducer.h
@@ -0,0 +1,192 @@
+// Copyright (c) 2020 Google LLC
+//
+// 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 SOURCE_FUZZ_ADDED_FUNCTION_REDUCER_H_
+#define SOURCE_FUZZ_ADDED_FUNCTION_REDUCER_H_
+
+#include <unordered_set>
+#include <vector>
+
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/shrinker.h"
+#include "spirv-tools/libspirv.hpp"
+
+namespace spvtools {
+namespace fuzz {
+
+// An auxiliary class used by Shrinker, this class takes care of using
+// spirv-reduce to reduce the body of a function encoded in an AddFunction
+// transformation, in case a smaller, simpler function can be added instead.
+class AddedFunctionReducer {
+ public:
+ // Possible statuses that can result from running the shrinker.
+ enum class AddedFunctionReducerResultStatus {
+ kComplete,
+ kReductionFailed,
+ };
+
+ struct AddedFunctionReducerResult {
+ AddedFunctionReducerResultStatus status;
+ std::vector<uint32_t> transformed_binary;
+ protobufs::TransformationSequence applied_transformations;
+ uint32_t num_reduction_attempts;
+ };
+
+ AddedFunctionReducer(
+ spv_target_env target_env, MessageConsumer consumer,
+ const std::vector<uint32_t>& binary_in,
+ const protobufs::FactSequence& initial_facts,
+ const protobufs::TransformationSequence& transformation_sequence_in,
+ uint32_t index_of_add_function_transformation,
+ const Shrinker::InterestingnessFunction&
+ shrinker_interestingness_function,
+ bool validate_during_replay, spv_validator_options validator_options,
+ uint32_t shrinker_step_limit, uint32_t num_existing_shrink_attempts);
+
+ // Disables copy/move constructor/assignment operations.
+ AddedFunctionReducer(const AddedFunctionReducer&) = delete;
+ AddedFunctionReducer(AddedFunctionReducer&&) = delete;
+ AddedFunctionReducer& operator=(const AddedFunctionReducer&) = delete;
+ AddedFunctionReducer& operator=(AddedFunctionReducer&&) = delete;
+
+ ~AddedFunctionReducer();
+
+ // Invokes spirv-reduce on the function in the AddFunction transformation
+ // identified by |index_of_add_function_transformation|. Returns a sequence
+ // of transformations identical to |transformation_sequence_in|, except that
+ // the AddFunction transformation at |index_of_add_function_transformation|
+ // might have been simplified. The binary associated with applying the
+ // resulting sequence of transformations to |binary_in| is also returned, as
+ // well as the number of reduction steps that spirv-reduce made.
+ //
+ // On failure, an empty transformation sequence and binary are returned,
+ // with a placeholder value of 0 for the number of reduction attempts.
+ AddedFunctionReducerResult Run();
+
+ private:
+ // Yields, via |binary_out|, the binary obtained by applying transformations
+ // [0, |index_of_added_function_| - 1] from |transformations_in_| to
+ // |binary_in_|, and then adding the raw function encoded in
+ // |transformations_in_[index_of_added_function_]| (without adapting that
+ // function to make it livesafe). This function has |added_function_id_| as
+ // its result id.
+ //
+ // The ids associated with all global variables in |binary_out| that had the
+ // "irrelevant pointee value" fact are also returned via
+ // |irrelevant_pointee_global_variables|.
+ //
+ // The point of this function is that spirv-reduce can subsequently be applied
+ // to function |added_function_id_| in |binary_out|. By construction,
+ // |added_function_id_| should originally manipulate globals for which
+ // "irrelevant pointee value" facts hold. The set
+ // |irrelevant_pointee_global_variables| can be used to force spirv-reduce
+ // to preserve this, to avoid the reduced function ending up manipulating
+ // other global variables of the SPIR-V module, potentially changing their
+ // value and thus changing the semantics of the module.
+ void ReplayPrefixAndAddFunction(
+ std::vector<uint32_t>* binary_out,
+ std::unordered_set<uint32_t>* irrelevant_pointee_global_variables) const;
+
+ // This is the interestingness function that will be used by spirv-reduce
+ // when shrinking the added function.
+ //
+ // For |binary_under_reduction| to be deemed interesting, the following
+ // conditions must hold:
+ // - The function with id |added_function_id_| in |binary_under_reduction|
+ // must only reference global variables in
+ // |irrelevant_pointee_global_variables|. This avoids the reduced function
+ // changing the semantics of the original SPIR-V module.
+ // - It must be possible to successfully replay the transformations in
+ // |transformation_sequence_in_|, adapted so that the function added by the
+ // transformation at |index_of_add_function_transformation_| is replaced by
+ // the function with id |added_function_id_| in |binary_under_reduction|,
+ // to |binary_in| (starting with initial facts |initial_facts_|).
+ // - All the transformations in this sequence must be successfully applied
+ // during replay.
+ // - The resulting binary must be interesting according to
+ // |shrinker_interestingness_function_|.
+ bool InterestingnessFunctionForReducingAddedFunction(
+ const std::vector<uint32_t>& binary_under_reduction,
+ const std::unordered_set<uint32_t>& irrelevant_pointee_global_variables);
+
+ // Starting with |binary_in_| and |initial_facts_|, the transformations in
+ // |transformation_sequence_in_| are replayed. However, the transformation
+ // at index |index_of_add_function_transformation_| of
+ // |transformation_sequence_in_| -- which is guaranteed to be an AddFunction
+ // transformation -- is adapted so that the function to be added is replaced
+ // with the function in |binary_under_reduction| with id |added_function_id_|.
+ //
+ // The binary resulting from this replay is returned via |binary_out|, and the
+ // adapted transformation sequence via |transformation_sequence_out|.
+ void ReplayAdaptedTransformations(
+ const std::vector<uint32_t>& binary_under_reduction,
+ std::vector<uint32_t>* binary_out,
+ protobufs::TransformationSequence* transformation_sequence_out) const;
+
+ // Returns the id of the function to be added by the AddFunction
+ // transformation at
+ // |transformation_sequence_in_[index_of_add_function_transformation_]|.
+ uint32_t GetAddedFunctionId() const;
+
+ // Target environment.
+ const spv_target_env target_env_;
+
+ // Message consumer.
+ MessageConsumer consumer_;
+
+ // The initial binary to which transformations are applied -- i.e., the
+ // binary to which spirv-fuzz originally applied transformations.
+ const std::vector<uint32_t>& binary_in_;
+
+ // Initial facts about |binary_in_|.
+ const protobufs::FactSequence& initial_facts_;
+
+ // A set of transformations that can be successfully applied to |binary_in_|.
+ const protobufs::TransformationSequence& transformation_sequence_in_;
+
+ // An index into |transformation_sequence_in_| referring to an AddFunction
+ // transformation. This is the transformation to be simplified using
+ // spirv-reduce.
+ const uint32_t index_of_add_function_transformation_;
+
+ // The interestingness function that has been provided to guide the
+ // overall shrinking process. The AddFunction transformation being simplified
+ // by this class should still -- when applied in conjunction with the other
+ // transformations in |transformation_sequence_in_| -- lead to a binary that
+ // is deemed interesting by this function.
+ const Shrinker::InterestingnessFunction& shrinker_interestingness_function_;
+
+ // Determines whether to check for validity during the replaying of
+ // transformations.
+ const bool validate_during_replay_;
+
+ // Options to control validation.
+ spv_validator_options validator_options_;
+
+ // The step limit associated with the overall shrinking process.
+ const uint32_t shrinker_step_limit_;
+
+ // The number of shrink attempts that had been applied prior to invoking this
+ // AddedFunctionReducer instance.
+ const uint32_t num_existing_shrink_attempts_;
+
+ // Tracks the number of attempts that spirv-reduce has made in reducing the
+ // added function.
+ uint32_t num_reduction_attempts_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_ADDED_FUNCTION_REDUCER_H_
diff --git a/source/fuzz/instruction_message.cpp b/source/fuzz/instruction_message.cpp
index 44777ae..9503932 100644
--- a/source/fuzz/instruction_message.cpp
+++ b/source/fuzz/instruction_message.cpp
@@ -36,6 +36,18 @@
return result;
}
+protobufs::Instruction MakeInstructionMessage(
+ const opt::Instruction* instruction) {
+ opt::Instruction::OperandList input_operands;
+ for (uint32_t input_operand_index = 0;
+ input_operand_index < instruction->NumInOperands();
+ input_operand_index++) {
+ input_operands.push_back(instruction->GetInOperand(input_operand_index));
+ }
+ return MakeInstructionMessage(instruction->opcode(), instruction->type_id(),
+ instruction->result_id(), input_operands);
+}
+
std::unique_ptr<opt::Instruction> InstructionFromMessage(
opt::IRContext* ir_context,
const protobufs::Instruction& instruction_message) {
diff --git a/source/fuzz/instruction_message.h b/source/fuzz/instruction_message.h
index c010c2f..fcbb4c7 100644
--- a/source/fuzz/instruction_message.h
+++ b/source/fuzz/instruction_message.h
@@ -29,6 +29,10 @@
SpvOp opcode, uint32_t result_type_id, uint32_t result_id,
const opt::Instruction::OperandList& input_operands);
+// Creates an Instruction protobuf message from a parsed instruction.
+protobufs::Instruction MakeInstructionMessage(
+ const opt::Instruction* instruction);
+
// Creates and returns an opt::Instruction from protobuf message
// |instruction_message|, relative to |ir_context|. In the process, the module
// id bound associated with |ir_context| is updated to be at least as large as
diff --git a/source/fuzz/shrinker.cpp b/source/fuzz/shrinker.cpp
index 1b65e40..c1e2514 100644
--- a/source/fuzz/shrinker.cpp
+++ b/source/fuzz/shrinker.cpp
@@ -16,6 +16,7 @@
#include <sstream>
+#include "source/fuzz/added_function_reducer.h"
#include "source/fuzz/pseudo_random_generator.h"
#include "source/fuzz/replayer.h"
#include "source/opt/build_module.h"
@@ -238,6 +239,51 @@
}
}
+ // We now use spirv-reduce to minimise the functions associated with any
+ // AddFunction transformations that remain.
+ //
+ // Consider every remaining transformation.
+ for (uint32_t transformation_index = 0;
+ attempt < step_limit_ &&
+ transformation_index <
+ static_cast<uint32_t>(
+ current_best_transformations.transformation_size());
+ transformation_index++) {
+ // Skip all transformations apart from TransformationAddFunction.
+ if (!current_best_transformations.transformation(transformation_index)
+ .has_add_function()) {
+ continue;
+ }
+ // Invoke spirv-reduce on the function encoded in this AddFunction
+ // transformation. The details of this are rather involved, and so are
+ // encapsulated in a separate class.
+ auto added_function_reducer_result =
+ AddedFunctionReducer(target_env_, consumer_, binary_in_, initial_facts_,
+ current_best_transformations, transformation_index,
+ interestingness_function_, validate_during_replay_,
+ validator_options_, step_limit_, attempt)
+ .Run();
+ // Reducing the added function should succeed. If it doesn't, we report
+ // a shrinking error.
+ if (added_function_reducer_result.status !=
+ AddedFunctionReducer::AddedFunctionReducerResultStatus::kComplete) {
+ return {ShrinkerResultStatus::kAddedFunctionReductionFailed,
+ std::vector<uint32_t>(), protobufs::TransformationSequence()};
+ }
+ assert(current_best_transformations.transformation_size() ==
+ added_function_reducer_result.applied_transformations
+ .transformation_size() &&
+ "The number of transformations should not have changed.");
+ current_best_binary =
+ std::move(added_function_reducer_result.transformed_binary);
+ current_best_transformations =
+ std::move(added_function_reducer_result.applied_transformations);
+ // The added function reducer reports how many reduction attempts
+ // spirv-reduce took when reducing the function. We regard each of these
+ // as a shrinker attempt.
+ attempt += added_function_reducer_result.num_reduction_attempts;
+ }
+
// Indicate whether shrinking completed or was truncated due to reaching the
// step limit.
//
diff --git a/source/fuzz/shrinker.h b/source/fuzz/shrinker.h
index 982a843..b9015d6 100644
--- a/source/fuzz/shrinker.h
+++ b/source/fuzz/shrinker.h
@@ -37,6 +37,7 @@
kInitialBinaryNotInteresting,
kReplayFailed,
kStepLimitReached,
+ kAddedFunctionReductionFailed,
};
struct ShrinkerResult {
@@ -107,7 +108,7 @@
// The series of transformations to be shrunk.
const protobufs::TransformationSequence& transformation_sequence_in_;
- // Function that decides whether a given binary is interesting.
+ // Function that decides whether a given module is interesting.
const InterestingnessFunction& interestingness_function_;
// Step limit to decide when to terminate shrinking early.
diff --git a/source/fuzz/transformation_add_function.h b/source/fuzz/transformation_add_function.h
index 3a4bd18..e5381d1 100644
--- a/source/fuzz/transformation_add_function.h
+++ b/source/fuzz/transformation_add_function.h
@@ -73,7 +73,6 @@
static uint32_t GetBackEdgeBlockId(opt::IRContext* ir_context,
uint32_t loop_header_block_id);
- private:
// Attempts to create a function from the series of instructions in
// |message_.instruction| and add it to |ir_context|.
//
@@ -94,6 +93,7 @@
// to add the function.
bool TryToAddFunction(opt::IRContext* ir_context) const;
+ private:
// Should only be called if |message_.is_livesafe| holds. Attempts to make
// the function livesafe (see FactFunctionIsLivesafe for a definition).
// Returns false if this is not possible, due to |message_| or |ir_context|
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index e287d8d..89ffa59 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -30,6 +30,7 @@
instruction_descriptor_test.cpp
fuzzer_pass_test.cpp
replayer_test.cpp
+ shrinker_test.cpp
transformation_access_chain_test.cpp
transformation_add_bit_instruction_synonym_test.cpp
transformation_add_constant_boolean_test.cpp
diff --git a/test/fuzz/shrinker_test.cpp b/test/fuzz/shrinker_test.cpp
new file mode 100644
index 0000000..e5e3776
--- /dev/null
+++ b/test/fuzz/shrinker_test.cpp
@@ -0,0 +1,266 @@
+// Copyright (c) 2020 Google LLC
+//
+// 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 "source/fuzz/shrinker.h"
+
+#include "source/fuzz/fact_manager/fact_manager.h"
+#include "source/fuzz/fuzzer_context.h"
+#include "source/fuzz/fuzzer_pass_donate_modules.h"
+#include "source/fuzz/pseudo_random_generator.h"
+#include "source/fuzz/transformation_context.h"
+#include "source/opt/ir_context.h"
+#include "source/util/make_unique.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(ShrinkerTest, ReduceAddedFunctions) {
+ const std::string kReferenceModule = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Private %6
+ %8 = OpVariable %7 Private
+ %9 = OpConstant %6 2
+ %10 = OpTypePointer Function %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %11 = OpVariable %10 Function
+ OpStore %8 %9
+ %12 = OpLoad %6 %8
+ OpStore %11 %12
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const std::string kDonorModule = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %6 %7
+ %12 = OpTypeFunction %2 %7
+ %17 = OpConstant %6 0
+ %26 = OpTypeBool
+ %32 = OpConstant %6 1
+ %46 = OpTypePointer Private %6
+ %47 = OpVariable %46 Private
+ %48 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %49 = OpVariable %7 Function
+ %50 = OpVariable %7 Function
+ %51 = OpLoad %6 %49
+ OpStore %50 %51
+ %52 = OpFunctionCall %2 %14 %50
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %6 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %16 = OpVariable %7 Function
+ %18 = OpVariable %7 Function
+ OpStore %16 %17
+ OpStore %18 %17
+ OpBranch %19
+ %19 = OpLabel
+ OpLoopMerge %21 %22 None
+ OpBranch %23
+ %23 = OpLabel
+ %24 = OpLoad %6 %18
+ %25 = OpLoad %6 %9
+ %27 = OpSLessThan %26 %24 %25
+ OpBranchConditional %27 %20 %21
+ %20 = OpLabel
+ %28 = OpLoad %6 %9
+ %29 = OpLoad %6 %16
+ %30 = OpIAdd %6 %29 %28
+ OpStore %16 %30
+ OpBranch %22
+ %22 = OpLabel
+ %31 = OpLoad %6 %18
+ %33 = OpIAdd %6 %31 %32
+ OpStore %18 %33
+ OpBranch %19
+ %21 = OpLabel
+ %34 = OpLoad %6 %16
+ %35 = OpNot %6 %34
+ OpReturnValue %35
+ OpFunctionEnd
+ %14 = OpFunction %2 None %12
+ %13 = OpFunctionParameter %7
+ %15 = OpLabel
+ %37 = OpVariable %7 Function
+ %38 = OpVariable %7 Function
+ %39 = OpLoad %6 %13
+ OpStore %38 %39
+ %40 = OpFunctionCall %6 %10 %38
+ OpStore %37 %40
+ %41 = OpLoad %6 %37
+ %42 = OpLoad %6 %13
+ %43 = OpSGreaterThan %26 %41 %42
+ OpSelectionMerge %45 None
+ OpBranchConditional %43 %44 %45
+ %44 = OpLabel
+ OpStore %47 %48
+ OpBranch %45
+ %45 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ // Note: |env| should ideally be declared const. However, due to a known
+ // issue with older versions of MSVC we would have to mark |env| as being
+ // captured due to its used in a lambda below, and other compilers would warn
+ // that such capturing is not necessary. Not declaring |env| as const means
+ // that it needs to be captured to be used in the lambda, and thus all
+ // compilers are kept happy. See:
+ // https://developercommunity.visualstudio.com/content/problem/367326/problems-with-capturing-constexpr-in-lambda.html
+ spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = kSilentConsumer;
+
+ SpirvTools tools(env);
+ std::vector<uint32_t> reference_binary;
+ ASSERT_TRUE(
+ tools.Assemble(kReferenceModule, &reference_binary, kFuzzAssembleOption));
+
+ const auto variant_ir_context =
+ BuildModule(env, consumer, kReferenceModule, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, variant_ir_context.get()));
+
+ const auto donor_ir_context =
+ BuildModule(env, consumer, kDonorModule, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, donor_ir_context.get()));
+
+ PseudoRandomGenerator random_generator(0);
+ FuzzerContext fuzzer_context(&random_generator, 100);
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(variant_ir_context.get()), validator_options);
+
+ protobufs::TransformationSequence transformations;
+ FuzzerPassDonateModules pass(variant_ir_context.get(),
+ &transformation_context, &fuzzer_context,
+ &transformations, {});
+ pass.DonateSingleModule(donor_ir_context.get(), true);
+
+ protobufs::FactSequence no_facts;
+
+ Shrinker::InterestingnessFunction interestingness_function =
+ [consumer, env](const std::vector<uint32_t>& binary,
+ uint32_t /*unused*/) -> bool {
+ bool found_op_not = false;
+ uint32_t op_call_count = 0;
+ auto temp_ir_context =
+ BuildModule(env, consumer, binary.data(), binary.size());
+ for (auto& function : *temp_ir_context->module()) {
+ for (auto& block : function) {
+ for (auto& inst : block) {
+ if (inst.opcode() == SpvOpNot) {
+ found_op_not = true;
+ } else if (inst.opcode() == SpvOpFunctionCall) {
+ op_call_count++;
+ }
+ }
+ }
+ }
+ return found_op_not && op_call_count >= 2;
+ };
+
+ auto shrinker_result =
+ Shrinker(env, consumer, reference_binary, no_facts, transformations,
+ interestingness_function, 1000, true, validator_options)
+ .Run();
+ ASSERT_EQ(Shrinker::ShrinkerResultStatus::kComplete, shrinker_result.status);
+
+ // We now check that the module after shrinking looks right.
+ // The entry point should be identical to what it looked like in the
+ // reference, while the other functions should be absolutely minimal,
+ // containing only what is needed to satisfy the interestingness function.
+ auto ir_context_after_shrinking =
+ BuildModule(env, consumer, shrinker_result.transformed_binary.data(),
+ shrinker_result.transformed_binary.size());
+ bool first_function = true;
+ for (auto& function : *ir_context_after_shrinking->module()) {
+ if (first_function) {
+ first_function = false;
+ bool first_block = true;
+ for (auto& block : function) {
+ ASSERT_TRUE(first_block);
+ uint32_t counter = 0;
+ for (auto& inst : block) {
+ switch (counter) {
+ case 0:
+ ASSERT_EQ(SpvOpVariable, inst.opcode());
+ ASSERT_EQ(11, inst.result_id());
+ break;
+ case 1:
+ ASSERT_EQ(SpvOpStore, inst.opcode());
+ break;
+ case 2:
+ ASSERT_EQ(SpvOpLoad, inst.opcode());
+ ASSERT_EQ(12, inst.result_id());
+ break;
+ case 3:
+ ASSERT_EQ(SpvOpStore, inst.opcode());
+ break;
+ case 4:
+ ASSERT_EQ(SpvOpReturn, inst.opcode());
+ break;
+ default:
+ FAIL();
+ }
+ counter++;
+ }
+ }
+ } else {
+ bool first_block = true;
+ for (auto& block : function) {
+ ASSERT_TRUE(first_block);
+ first_block = false;
+ for (auto& inst : block) {
+ switch (inst.opcode()) {
+ case SpvOpVariable:
+ case SpvOpNot:
+ case SpvOpReturn:
+ case SpvOpReturnValue:
+ case SpvOpFunctionCall:
+ // These are the only instructions we expect to see.
+ break;
+ default:
+ FAIL();
+ }
+ }
+ }
+ }
+ }
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
