Initial commit for spirv-reduce. (#2056)
Creates a new tool that can be used to reduce failing testcases, similar to creduce.
diff --git a/.gitignore b/.gitignore
index 4752a33..059b18e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -19,3 +19,7 @@
# Vim
[._]*.s[a-w][a-z]
*~
+
+# C-Lion
+.idea
+cmake-build-debug
\ No newline at end of file
diff --git a/include/spirv-tools/libspirv.h b/include/spirv-tools/libspirv.h
index 4fcd276..496d502 100644
--- a/include/spirv-tools/libspirv.h
+++ b/include/spirv-tools/libspirv.h
@@ -368,6 +368,8 @@
typedef struct spv_optimizer_options_t spv_optimizer_options_t;
+typedef struct spv_reducer_options_t spv_reducer_options_t;
+
// Type Definitions
typedef spv_const_binary_t* spv_const_binary;
@@ -381,6 +383,8 @@
typedef const spv_validator_options_t* spv_const_validator_options;
typedef spv_optimizer_options_t* spv_optimizer_options;
typedef const spv_optimizer_options_t* spv_const_optimizer_options;
+typedef spv_reducer_options_t* spv_reducer_options;
+typedef const spv_reducer_options_t* spv_const_reducer_options;
// Platform API
@@ -541,6 +545,23 @@
SPIRV_TOOLS_EXPORT void spvOptimizerOptionsSetMaxIdBound(
spv_optimizer_options options, uint32_t val);
+// Creates a reducer options object with default options. Returns a valid
+// options object. The object remains valid until it is passed into
+// |spvReducerOptionsDestroy|.
+SPIRV_TOOLS_EXPORT spv_reducer_options spvReducerOptionsCreate();
+
+// Destroys the given reducer options object.
+SPIRV_TOOLS_EXPORT void spvReducerOptionsDestroy(spv_reducer_options options);
+
+// Records the maximum number of reduction steps that should run before the
+// reducer gives up.
+SPIRV_TOOLS_EXPORT void spvReducerOptionsSetStepLimit(
+ spv_reducer_options options, uint32_t step_limit);
+
+// Sets seed for random number generation.
+SPIRV_TOOLS_EXPORT void spvReducerOptionsSetSeed(spv_reducer_options options,
+ uint32_t seed);
+
// Encodes the given SPIR-V assembly text to its binary representation. The
// length parameter specifies the number of bytes for text. Encoded binary will
// be stored into *binary. Any error will be written into *diagnostic if
diff --git a/include/spirv-tools/libspirv.hpp b/include/spirv-tools/libspirv.hpp
index 26c0989..9cb5afe 100644
--- a/include/spirv-tools/libspirv.hpp
+++ b/include/spirv-tools/libspirv.hpp
@@ -144,6 +144,28 @@
spv_optimizer_options options_;
};
+// A C++ wrapper around a reducer options object.
+class ReducerOptions {
+ public:
+ ReducerOptions() : options_(spvReducerOptionsCreate()) {}
+ ~ReducerOptions() { spvReducerOptionsDestroy(options_); }
+
+ // Allow implicit conversion to the underlying object.
+ operator spv_reducer_options() const { return options_; }
+
+ // Records the maximum number of reduction steps that should
+ // run before the reducer gives up.
+ void set_step_limit(uint32_t step_limit) {
+ spvReducerOptionsSetStepLimit(options_, step_limit);
+ }
+
+ // Sets a seed to be used for random number generation.
+ void set_seed(uint32_t seed) { spvReducerOptionsSetSeed(options_, seed); }
+
+ private:
+ spv_reducer_options options_;
+};
+
// C++ interface for SPIRV-Tools functionalities. It wraps the context
// (including target environment and the corresponding SPIR-V grammar) and
// provides methods for assembling, disassembling, and validating.
diff --git a/source/CMakeLists.txt b/source/CMakeLists.txt
index 634dfa5..3f032e1 100644
--- a/source/CMakeLists.txt
+++ b/source/CMakeLists.txt
@@ -216,6 +216,7 @@
add_subdirectory(comp)
add_subdirectory(opt)
+add_subdirectory(reduce)
add_subdirectory(link)
set(SPIRV_SOURCES
@@ -253,6 +254,7 @@
${CMAKE_CURRENT_SOURCE_DIR}/spirv_definition.h
${CMAKE_CURRENT_SOURCE_DIR}/spirv_endian.h
${CMAKE_CURRENT_SOURCE_DIR}/spirv_optimizer_options.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/spirv_reducer_options.h
${CMAKE_CURRENT_SOURCE_DIR}/spirv_target_env.h
${CMAKE_CURRENT_SOURCE_DIR}/spirv_validator_options.h
${CMAKE_CURRENT_SOURCE_DIR}/table.h
@@ -280,6 +282,7 @@
${CMAKE_CURRENT_SOURCE_DIR}/software_version.cpp
${CMAKE_CURRENT_SOURCE_DIR}/spirv_endian.cpp
${CMAKE_CURRENT_SOURCE_DIR}/spirv_optimizer_options.cpp
+ ${CMAKE_CURRENT_SOURCE_DIR}/spirv_reducer_options.cpp
${CMAKE_CURRENT_SOURCE_DIR}/spirv_target_env.cpp
${CMAKE_CURRENT_SOURCE_DIR}/spirv_validator_options.cpp
${CMAKE_CURRENT_SOURCE_DIR}/table.cpp
diff --git a/source/reduce/CMakeLists.txt b/source/reduce/CMakeLists.txt
new file mode 100644
index 0000000..995e1e6
--- /dev/null
+++ b/source/reduce/CMakeLists.txt
@@ -0,0 +1,60 @@
+# Copyright (c) 2018 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.
+set(SPIRV_TOOLS_REDUCE_SOURCES
+ change_operand_reduction_opportunity.h
+ operand_to_const_reduction_pass.h
+ reducer.h
+ reduction_opportunity.h
+ reduction_pass.h
+ remove_instruction_reduction_opportunity.h
+ remove_unreferenced_instruction_reduction_pass.h
+
+ change_operand_reduction_opportunity.cpp
+ operand_to_const_reduction_pass.cpp
+ reducer.cpp
+ reduction_opportunity.cpp
+ reduction_pass.cpp
+ remove_instruction_reduction_opportunity.cpp
+ remove_unreferenced_instruction_reduction_pass.cpp
+ )
+
+if(MSVC)
+ # Enable parallel builds across four cores for this lib
+ add_definitions(/MP4)
+endif()
+
+spvtools_pch(SPIRV_TOOLS_REDUCE_SOURCES pch_source_reduce)
+
+add_library(SPIRV-Tools-reduce ${SPIRV_TOOLS_REDUCE_SOURCES})
+
+spvtools_default_compile_options(SPIRV-Tools-reduce)
+target_include_directories(SPIRV-Tools-reduce
+ PUBLIC ${spirv-tools_SOURCE_DIR}/include
+ PUBLIC ${SPIRV_HEADER_INCLUDE_DIR}
+ PRIVATE ${spirv-tools_BINARY_DIR}
+)
+# The reducer reuses a lot of functionality from the SPIRV-Tools library.
+target_link_libraries(SPIRV-Tools-reduce
+ PUBLIC ${SPIRV_TOOLS}
+ PUBLIC SPIRV-Tools-opt)
+
+set_property(TARGET SPIRV-Tools-reduce PROPERTY FOLDER "SPIRV-Tools libraries")
+spvtools_check_symbol_exports(SPIRV-Tools-reduce)
+
+if(ENABLE_SPIRV_TOOLS_INSTALL)
+ install(TARGETS SPIRV-Tools-reduce
+ RUNTIME DESTINATION ${CMAKE_INSTALL_BINDIR}
+ LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR}
+ ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR})
+endif(ENABLE_SPIRV_TOOLS_INSTALL)
diff --git a/source/reduce/change_operand_reduction_opportunity.cpp b/source/reduce/change_operand_reduction_opportunity.cpp
new file mode 100644
index 0000000..5430d3e
--- /dev/null
+++ b/source/reduce/change_operand_reduction_opportunity.cpp
@@ -0,0 +1,32 @@
+// Copyright (c) 2018 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 "change_operand_reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+bool ChangeOperandReductionOpportunity::PreconditionHolds() {
+ // Check that the instruction still has the original operand.
+ return inst_->NumOperands() > operand_index_ &&
+ inst_->GetOperand(operand_index_).words[0] == original_id_ &&
+ inst_->GetOperand(operand_index_).type == original_type_;
+}
+
+void ChangeOperandReductionOpportunity::Apply() {
+ inst_->SetOperand(operand_index_, {new_id_});
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/change_operand_reduction_opportunity.h b/source/reduce/change_operand_reduction_opportunity.h
new file mode 100644
index 0000000..ba67cd0
--- /dev/null
+++ b/source/reduce/change_operand_reduction_opportunity.h
@@ -0,0 +1,61 @@
+// Copyright (c) 2018 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_REDUCE_CHANGE_OPERAND_REDUCTION_OPPORTUNITY_H_
+#define SOURCE_REDUCE_CHANGE_OPERAND_REDUCTION_OPPORTUNITY_H_
+
+#include "reduction_opportunity.h"
+#include "source/opt/instruction.h"
+#include "spirv-tools/libspirv.h"
+
+namespace spvtools {
+namespace reduce {
+
+using namespace opt;
+
+// Captures the opportunity to change an id operand of an instruction to some
+// other id.
+class ChangeOperandReductionOpportunity : public ReductionOpportunity {
+ public:
+ // Constructs the opportunity to replace operand |operand_index| of |inst|
+ // with |new_id|.
+ ChangeOperandReductionOpportunity(Instruction* inst, uint32_t operand_index,
+ uint32_t new_id)
+ : inst_(inst),
+ operand_index_(operand_index),
+ original_id_(inst_->GetOperand(operand_index_).words[0]),
+ original_type_(inst->GetOperand(operand_index).type),
+ new_id_(new_id) {}
+
+ // Determines whether the opportunity can be applied; it may have been viable
+ // when discovered but later disabled by the application of some other
+ // reduction opportunity.
+ bool PreconditionHolds() override;
+
+ protected:
+ // Apply the change of operand.
+ void Apply() override;
+
+ private:
+ Instruction* const inst_;
+ const uint32_t operand_index_;
+ const uint32_t original_id_;
+ const spv_operand_type_t original_type_;
+ const uint32_t new_id_;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_CHANGE_OPERAND_REDUCTION_OPPORTUNITY_H_
diff --git a/source/reduce/operand_to_const_reduction_pass.cpp b/source/reduce/operand_to_const_reduction_pass.cpp
new file mode 100644
index 0000000..b1b1385
--- /dev/null
+++ b/source/reduce/operand_to_const_reduction_pass.cpp
@@ -0,0 +1,86 @@
+// Copyright (c) 2018 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 "operand_to_const_reduction_pass.h"
+#include "change_operand_reduction_opportunity.h"
+#include "source/opt/instruction.h"
+
+namespace spvtools {
+namespace reduce {
+
+using namespace opt;
+
+std::vector<std::unique_ptr<ReductionOpportunity>>
+OperandToConstReductionPass::GetAvailableOpportunities(
+ opt::IRContext* context) const {
+ std::vector<std::unique_ptr<ReductionOpportunity>> result;
+ assert(result.empty());
+
+ // We first loop over all constants. This means that all the reduction
+ // opportunities to replace an operand with a particular constant will be
+ // contiguous, and in particular it means that multiple, incompatible
+ // reduction opportunities that try to replace the same operand with distinct
+ // constants are likely to be discontiguous. This is good because the
+ // reducer works in the spirit of delta debugging and tries applying large
+ // contiguous blocks of opportunities early on, and we want to avoid having a
+ // large block of incompatible opportunities if possible.
+ for (const auto& constant : context->GetConstants()) {
+ for (auto& function : *context->module()) {
+ for (auto& block : function) {
+ for (auto& inst : block) {
+ // We iterate through the operands using an explicit index (rather
+ // than using a lambda) so that we use said index in the construction
+ // of a ChangeOperandReductionOpportunity
+ for (uint32_t index = 0; index < inst.NumOperands(); index++) {
+ const auto& operand = inst.GetOperand(index);
+ if (spvIsIdType(operand.type)) {
+ if (operand.type == SPV_OPERAND_TYPE_RESULT_ID ||
+ operand.type == SPV_OPERAND_TYPE_TYPE_ID) {
+ continue;
+ }
+ const auto id = operand.words[0];
+ auto def = context->get_def_use_mgr()->GetDef(id);
+ if (spvOpcodeIsConstant(def->opcode())) {
+ // The argument is already a constant.
+ continue;
+ }
+ if (def->opcode() == SpvOpFunction) {
+ // The argument refers to a function, e.g. the function called
+ // by OpFunctionCall; avoid replacing this with a constant of
+ // the function's return type.
+ continue;
+ }
+ auto type_id = def->type_id();
+ if (type_id) {
+ if (constant->type_id() == type_id) {
+ result.push_back(
+ MakeUnique<ChangeOperandReductionOpportunity>(
+ &inst, index, constant->result_id()));
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ return result;
+}
+
+std::string OperandToConstReductionPass::GetName() const {
+ return "OperandToConstReductionPass";
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/operand_to_const_reduction_pass.h b/source/reduce/operand_to_const_reduction_pass.h
new file mode 100644
index 0000000..fd7cfa0
--- /dev/null
+++ b/source/reduce/operand_to_const_reduction_pass.h
@@ -0,0 +1,51 @@
+// Copyright (c) 2018 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_REDUCE_OPERAND_TO_CONST_REDUCTION_PASS_H_
+#define SOURCE_REDUCE_OPERAND_TO_CONST_REDUCTION_PASS_H_
+
+#include "reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+
+// A reduction pass for turning id operands of instructions into ids of
+// constants. This reduces the extent to which ids of non-constants are used,
+// paving the way for instructions that generate them to be eliminated by other
+// passes.
+class OperandToConstReductionPass : public ReductionPass {
+ public:
+ // Creates the reduction pass in the context of the given target environment
+ // |target_env|
+ explicit OperandToConstReductionPass(const spv_target_env target_env)
+ : ReductionPass(target_env) {}
+
+ ~OperandToConstReductionPass() override = default;
+
+ // The name of this pass.
+ std::string GetName() const final;
+
+ protected:
+ // Finds all opportunities for replacing an operand with a constant in the
+ // given module.
+ std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
+ opt::IRContext* context) const final;
+
+ private:
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_OPERAND_TO_CONST_REDUCTION_PASS_H_
diff --git a/source/reduce/reducer.cpp b/source/reduce/reducer.cpp
new file mode 100644
index 0000000..9835069
--- /dev/null
+++ b/source/reduce/reducer.cpp
@@ -0,0 +1,146 @@
+// Copyright (c) 2018 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 <cassert>
+#include <sstream>
+
+#include "source/spirv_reducer_options.h"
+
+#include "reducer.h"
+#include "reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+
+struct Reducer::Impl {
+ explicit Impl(spv_target_env env) : target_env(env) {}
+
+ bool ReachedStepLimit(uint32_t current_step,
+ spv_const_reducer_options options);
+
+ const spv_target_env target_env; // Target environment.
+ MessageConsumer consumer; // Message consumer.
+ InterestingnessFunction interestingness_function;
+ std::vector<std::unique_ptr<ReductionPass>> passes;
+};
+
+Reducer::Reducer(spv_target_env env) : impl_(MakeUnique<Impl>(env)) {}
+
+Reducer::~Reducer() = default;
+
+void Reducer::SetMessageConsumer(MessageConsumer c) {
+ for (auto& pass : impl_->passes) {
+ pass->SetMessageConsumer(c);
+ }
+ impl_->consumer = std::move(c);
+}
+
+void Reducer::SetInterestingnessFunction(
+ Reducer::InterestingnessFunction interestingness_function) {
+ impl_->interestingness_function = std::move(interestingness_function);
+}
+
+Reducer::ReductionResultStatus Reducer::Run(
+ std::vector<uint32_t>&& binary_in, std::vector<uint32_t>* binary_out,
+ spv_const_reducer_options options) const {
+ std::vector<uint32_t> current_binary = binary_in;
+
+ // Keeps track of how many reduction attempts have been tried. Reduction
+ // bails out if this reaches a given limit.
+ uint32_t reductions_applied = 0;
+
+ // Initial state should be interesting.
+ if (!impl_->interestingness_function(current_binary, reductions_applied)) {
+ impl_->consumer(SPV_MSG_INFO, nullptr, {},
+ "Initial state was not interesting; stopping.");
+ return Reducer::ReductionResultStatus::kInitialStateNotInteresting;
+ }
+
+ // Determines whether, on completing one round of reduction passes, it is
+ // worthwhile trying a further round.
+ bool another_round_worthwhile = true;
+
+ // Apply round after round of reduction passes until we hit the reduction
+ // step limit, or deem that another round is not going to be worthwhile.
+ while (!impl_->ReachedStepLimit(reductions_applied, options) &&
+ another_round_worthwhile) {
+ // At the start of a round of reduction passes, assume another round will
+ // not be worthwhile unless we find evidence to the contrary.
+ another_round_worthwhile = false;
+
+ // Iterate through the available passes
+ for (auto& pass : impl_->passes) {
+ // Keep applying this pass at its current granularity until it stops
+ // working or we hit the reduction step limit.
+ impl_->consumer(SPV_MSG_INFO, nullptr, {},
+ ("Trying pass " + pass->GetName() + ".").c_str());
+ do {
+ auto maybe_result = pass->TryApplyReduction(current_binary);
+ if (maybe_result.empty()) {
+ // This pass did not have any impact, so move on to the next pass.
+ // If this pass hasn't reached its minimum granularity then it's
+ // worth eventually doing another round of reductions, in order to
+ // try this pass at a finer granularity.
+ impl_->consumer(
+ SPV_MSG_INFO, nullptr, {},
+ ("Pass " + pass->GetName() + " did not make a reduction step.")
+ .c_str());
+ another_round_worthwhile |= !pass->ReachedMinimumGranularity();
+ break;
+ }
+ std::stringstream stringstream;
+ reductions_applied++;
+ stringstream << "Pass " << pass->GetName() << " made reduction step "
+ << reductions_applied << ".";
+ impl_->consumer(SPV_MSG_INFO, nullptr, {},
+ (stringstream.str().c_str()));
+ if (impl_->interestingness_function(maybe_result, reductions_applied)) {
+ // Success! The binary produced by this reduction step is
+ // interesting, so make it the binary of interest henceforth, and
+ // note that it's worth doing another round of reduction passes.
+ impl_->consumer(SPV_MSG_INFO, nullptr, {},
+ "Reduction step succeeded.");
+ current_binary = std::move(maybe_result);
+ another_round_worthwhile = true;
+ }
+ // Bail out if the reduction step limit has been reached.
+ } while (!impl_->ReachedStepLimit(reductions_applied, options));
+ }
+ }
+
+ *binary_out = std::move(current_binary);
+
+ // Report whether reduction completed, or bailed out early due to reaching
+ // the step limit.
+ if (impl_->ReachedStepLimit(reductions_applied, options)) {
+ impl_->consumer(SPV_MSG_INFO, nullptr, {},
+ "Reached reduction step limit; stopping.");
+ return Reducer::ReductionResultStatus::kReachedStepLimit;
+ }
+ impl_->consumer(SPV_MSG_INFO, nullptr, {}, "No more to reduce; stopping.");
+ return Reducer::ReductionResultStatus::kComplete;
+}
+
+void Reducer::AddReductionPass(
+ std::unique_ptr<ReductionPass>&& reduction_pass) {
+ impl_->passes.push_back(std::move(reduction_pass));
+}
+
+bool Reducer::Impl::ReachedStepLimit(uint32_t current_step,
+ spv_const_reducer_options options) {
+ return current_step >= options->step_limit;
+}
+
+} // namespace reduce
+} // namespace spvtools
\ No newline at end of file
diff --git a/source/reduce/reducer.h b/source/reduce/reducer.h
new file mode 100644
index 0000000..3a4c26c
--- /dev/null
+++ b/source/reduce/reducer.h
@@ -0,0 +1,97 @@
+// Copyright (c) 2018 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_REDUCE_REDUCER_H_
+#define SOURCE_REDUCE_REDUCER_H_
+
+#include <functional>
+#include <string>
+
+#include "spirv-tools/libspirv.hpp"
+
+#include "reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+
+// This class manages the process of applying a reduction -- parameterized by a
+// number of reduction passes and an interestingness test, to a SPIR-V binary.
+class Reducer {
+ public:
+ // Possible statuses that can result from running a reduction.
+ enum ReductionResultStatus {
+ kInitialStateNotInteresting,
+ kReachedStepLimit,
+ kComplete
+ };
+
+ // The type for a function that will take a binary and return true if and
+ // only if the binary is deemed interesting. (The function also takes an
+ // integer argument that will be incremented each time the function is
+ // called; this is for debugging purposes).
+ //
+ // The notion of "interesting" depends on what properties of the binary or
+ // tools that process the binary we are trying to maintain during reduction.
+ using InterestingnessFunction =
+ std::function<bool(const std::vector<uint32_t>&, uint32_t)>;
+
+ // Constructs an instance with the given target |env|, which is used to
+ // decode the binary to be reduced later.
+ //
+ // The constructed instance will have an empty message consumer, which just
+ // ignores all messages from the library. Use SetMessageConsumer() to supply
+ // one if messages are of concern.
+ //
+ // The constructed instance also needs to have an interestingness function
+ // set and some reduction passes added to it in order to be useful.
+ explicit Reducer(spv_target_env env);
+
+ // Disables copy/move constructor/assignment operations.
+ Reducer(const Reducer&) = delete;
+ Reducer(Reducer&&) = delete;
+ Reducer& operator=(const Reducer&) = delete;
+ Reducer& operator=(Reducer&&) = delete;
+
+ // Destructs this instance.
+ ~Reducer();
+
+ // Sets the message consumer to the given |consumer|. The |consumer| will be
+ // invoked once for each message communicated from the library.
+ void SetMessageConsumer(MessageConsumer consumer);
+
+ // Sets the function that will be used to decide whether a reduced binary
+ // turned out to be interesting.
+ void SetInterestingnessFunction(
+ InterestingnessFunction interestingness_function);
+
+ // Adds a reduction pass to the sequence of passes that will be iterated
+ // over.
+ void AddReductionPass(std::unique_ptr<ReductionPass>&& reduction_pass);
+
+ // Reduces the given SPIR-V module |binary_out|.
+ // The reduced binary ends up in |binary_out|.
+ // A status is returned.
+ ReductionResultStatus Run(std::vector<uint32_t>&& binary_in,
+ std::vector<uint32_t>* binary_out,
+ spv_const_reducer_options options) const;
+
+ private:
+ struct Impl; // Opaque struct for holding internal data.
+ std::unique_ptr<Impl> impl_; // Unique pointer to internal data.
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REDUCER_H_
diff --git a/source/reduce/reduction_opportunity.cpp b/source/reduce/reduction_opportunity.cpp
new file mode 100644
index 0000000..f562678
--- /dev/null
+++ b/source/reduce/reduction_opportunity.cpp
@@ -0,0 +1,27 @@
+// Copyright (c) 2018 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 "reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+void ReductionOpportunity::TryToApply() {
+ if (PreconditionHolds()) {
+ Apply();
+ }
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/reduction_opportunity.h b/source/reduce/reduction_opportunity.h
new file mode 100644
index 0000000..da382a2
--- /dev/null
+++ b/source/reduce/reduction_opportunity.h
@@ -0,0 +1,46 @@
+// Copyright (c) 2018 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_REDUCE_REDUCTION_OPPORTUNITY_H_
+#define SOURCE_REDUCE_REDUCTION_OPPORTUNITY_H_
+
+#include "spirv-tools/libspirv.hpp"
+
+namespace spvtools {
+namespace reduce {
+
+// Abstract class capturing an opportunity to apply a reducing transformation.
+class ReductionOpportunity {
+ public:
+ ReductionOpportunity() = default;
+ virtual ~ReductionOpportunity() = default;
+
+ // Determines whether the opportunity can be applied; it may have been viable
+ // when discovered but later disabled by the application of some other
+ // reduction opportunity.
+ virtual bool PreconditionHolds() = 0;
+
+ // A no-op if PreconditoinHolds() returns false; otherwise applies the
+ // opportunity.
+ void TryToApply();
+
+ protected:
+ // Apply the reduction opportunity.
+ virtual void Apply() = 0;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REDUCTION_OPPORTUNITY_H_
diff --git a/source/reduce/reduction_pass.cpp b/source/reduce/reduction_pass.cpp
new file mode 100644
index 0000000..befba8b
--- /dev/null
+++ b/source/reduce/reduction_pass.cpp
@@ -0,0 +1,86 @@
+// Copyright (c) 2018 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 <algorithm>
+
+#include "reduction_pass.h"
+
+#include "source/opt/build_module.h"
+
+namespace spvtools {
+namespace reduce {
+
+std::vector<uint32_t> ReductionPass::TryApplyReduction(
+ const std::vector<uint32_t>& binary) {
+ // We represent modules as binaries because (a) attempts at reduction need to
+ // end up in binary form to be passed on to SPIR-V-consuming tools, and (b)
+ // when we apply a reduction step we need to do it on a fresh version of the
+ // module as if the reduction step proves to be uninteresting we need to
+ // backtrack; re-parsing from binary provides a very clean way of cloning the
+ // module.
+ std::unique_ptr<opt::IRContext> context =
+ BuildModule(target_env_, consumer_, binary.data(), binary.size());
+ assert(context);
+
+ std::vector<std::unique_ptr<ReductionOpportunity>> opportunities =
+ GetAvailableOpportunities(context.get());
+
+ if (!is_initialized_) {
+ is_initialized_ = true;
+ index_ = 0;
+ granularity_ = (uint32_t)opportunities.size();
+ }
+
+ if (opportunities.empty()) {
+ granularity_ = 1;
+ return std::vector<uint32_t>();
+ }
+
+ assert(granularity_ > 0);
+
+ if (index_ >= opportunities.size()) {
+ index_ = 0;
+ granularity_ = std::max((uint32_t)1, granularity_ / 2);
+ return std::vector<uint32_t>();
+ }
+
+ for (uint32_t i = index_;
+ i < std::min(index_ + granularity_, (uint32_t)opportunities.size());
+ ++i) {
+ opportunities[i]->TryToApply();
+ }
+
+ index_ += granularity_;
+
+ std::vector<uint32_t> result;
+ context->module()->ToBinary(&result, false);
+ return result;
+}
+
+void ReductionPass::SetMessageConsumer(MessageConsumer consumer) {
+ consumer_ = std::move(consumer);
+}
+
+bool ReductionPass::ReachedMinimumGranularity() const {
+ if (!is_initialized_) {
+ // Conceptually we can think that if the pass has not yet been initialized,
+ // it is operating at unbounded granularity.
+ return false;
+ }
+ assert(granularity_ != 0);
+ return granularity_ == 1;
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/reduction_pass.h b/source/reduce/reduction_pass.h
new file mode 100644
index 0000000..afb95cc
--- /dev/null
+++ b/source/reduce/reduction_pass.h
@@ -0,0 +1,73 @@
+// Copyright (c) 2018 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_REDUCE_REDUCTION_PASS_H_
+#define SOURCE_REDUCE_REDUCTION_PASS_H_
+
+#include "spirv-tools/libspirv.hpp"
+
+#include "reduction_opportunity.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace reduce {
+
+// Abstract class representing a reduction pass, which can be repeatedly
+// invoked to find and apply particular reduction opportunities to a SPIR-V
+// binary. In the spirit of delta debugging, a pass initially tries to apply
+// large chunks of reduction opportunities, iterating through available
+// opportunities at a given granularity. When an iteration over available
+// opportunities completes, the granularity is reduced and iteration starts
+// again, until the minimum granularity is reached.
+class ReductionPass {
+ public:
+ // Constructs a reduction pass with a given target environment, |target_env|.
+ // Initially the pass is uninitialized.
+ explicit ReductionPass(const spv_target_env target_env)
+ : target_env_(target_env), is_initialized_(false) {}
+
+ virtual ~ReductionPass() = default;
+
+ // Apply the reduction pass to the given binary.
+ std::vector<uint32_t> TryApplyReduction(const std::vector<uint32_t>& binary);
+
+ // Set a consumer to which relevant messages will be directed.
+ void SetMessageConsumer(MessageConsumer consumer);
+
+ // Determines whether the granularity with which reduction opportunities are
+ // applied has reached a minimum.
+ bool ReachedMinimumGranularity() const;
+
+ // Returns the name of the reduction pass (useful for monitoring reduction
+ // progress).
+ virtual std::string GetName() const = 0;
+
+ protected:
+ // Finds the reduction opportunities relevant to this pass that could be
+ // applied to a given SPIR-V module.
+ virtual std::vector<std::unique_ptr<ReductionOpportunity>>
+ GetAvailableOpportunities(opt::IRContext* context) const = 0;
+
+ private:
+ const spv_target_env target_env_;
+ MessageConsumer consumer_;
+ bool is_initialized_;
+ uint32_t index_;
+ uint32_t granularity_;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REDUCTION_PASS_H_
diff --git a/source/reduce/remove_instruction_reduction_opportunity.cpp b/source/reduce/remove_instruction_reduction_opportunity.cpp
new file mode 100644
index 0000000..7b7a74e
--- /dev/null
+++ b/source/reduce/remove_instruction_reduction_opportunity.cpp
@@ -0,0 +1,29 @@
+// Copyright (c) 2018 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/opt/ir_context.h"
+
+#include "remove_instruction_reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+bool RemoveInstructionReductionOpportunity::PreconditionHolds() { return true; }
+
+void RemoveInstructionReductionOpportunity::Apply() {
+ inst_->context()->KillInst(inst_);
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/remove_instruction_reduction_opportunity.h b/source/reduce/remove_instruction_reduction_opportunity.h
new file mode 100644
index 0000000..471ff15
--- /dev/null
+++ b/source/reduce/remove_instruction_reduction_opportunity.h
@@ -0,0 +1,47 @@
+// Copyright (c) 2018 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_REDUCE_REMOVE_INSTRUCTION_REDUCTION_OPPORTUNITY_H_
+#define SOURCE_REDUCE_REMOVE_INSTRUCTION_REDUCTION_OPPORTUNITY_H_
+
+#include "reduction_opportunity.h"
+#include "source/opt/instruction.h"
+
+namespace spvtools {
+namespace reduce {
+
+using namespace opt;
+
+// Captures the opportunity to remove an instruction from the SPIR-V module.
+class RemoveInstructionReductionOpportunity : public ReductionOpportunity {
+ public:
+ // Constructs the opportunity to remove |inst|.
+ explicit RemoveInstructionReductionOpportunity(Instruction* inst)
+ : inst_(inst) {}
+
+ // This kind of opportunity can be unconditionally applied.
+ bool PreconditionHolds() override;
+
+ protected:
+ // Remove the instruction.
+ void Apply() override;
+
+ private:
+ Instruction* inst_;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REMOVE_INSTRUCTION_REDUCTION_OPPORTUNITY_H_
diff --git a/source/reduce/remove_unreferenced_instruction_reduction_pass.cpp b/source/reduce/remove_unreferenced_instruction_reduction_pass.cpp
new file mode 100644
index 0000000..bc4998d
--- /dev/null
+++ b/source/reduce/remove_unreferenced_instruction_reduction_pass.cpp
@@ -0,0 +1,60 @@
+// Copyright (c) 2018 Google Inc.
+//
+// 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 "remove_unreferenced_instruction_reduction_pass.h"
+#include "remove_instruction_reduction_opportunity.h"
+#include "source/opcode.h"
+#include "source/opt/instruction.h"
+
+namespace spvtools {
+namespace reduce {
+
+using namespace opt;
+
+std::vector<std::unique_ptr<ReductionOpportunity>>
+RemoveUnreferencedInstructionReductionPass::GetAvailableOpportunities(
+ opt::IRContext* context) const {
+ std::vector<std::unique_ptr<ReductionOpportunity>> result;
+
+ for (auto& function : *context->module()) {
+ for (auto& block : function) {
+ for (auto& inst : block) {
+ if (context->get_def_use_mgr()->NumUses(&inst) > 0) {
+ continue;
+ }
+ if (spvOpcodeIsBlockTerminator(inst.opcode()) ||
+ inst.opcode() == SpvOpSelectionMerge ||
+ inst.opcode() == SpvOpLoopMerge) {
+ // In this reduction pass we do not want to affect static control
+ // flow.
+ continue;
+ }
+ // Given that we're in a block, we should only get here if the
+ // instruction is not directly related to control flow; i.e., it's
+ // some straightforward instruction with an unused result, like an
+ // arithmetic operation or function call.
+ result.push_back(
+ MakeUnique<RemoveInstructionReductionOpportunity>(&inst));
+ }
+ }
+ }
+ return result;
+}
+
+std::string RemoveUnreferencedInstructionReductionPass::GetName() const {
+ return "RemoveUnreferencedInstructionReductionPass";
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/remove_unreferenced_instruction_reduction_pass.h b/source/reduce/remove_unreferenced_instruction_reduction_pass.h
new file mode 100644
index 0000000..27c3fc2
--- /dev/null
+++ b/source/reduce/remove_unreferenced_instruction_reduction_pass.h
@@ -0,0 +1,53 @@
+// Copyright (c) 2018 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_REDUCE_REMOVE_UNREFERENCED_INSTRUCTION_REDUCTION_PASS_H_
+#define SOURCE_REDUCE_REMOVE_UNREFERENCED_INSTRUCTION_REDUCTION_PASS_H_
+
+#include "reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+
+// A reduction pass for removing non-control-flow instructions in blocks in
+// cases where the instruction's id is not referenced. As well as making the
+// module smaller, removing an instruction that referenced particular ids may
+// create opportunities for subsequently removing the instructions that
+// generated those ids.
+class RemoveUnreferencedInstructionReductionPass : public ReductionPass {
+ public:
+ // Creates the reduction pass in the context of the given target environment
+ // |target_env|
+ explicit RemoveUnreferencedInstructionReductionPass(
+ const spv_target_env target_env)
+ : ReductionPass(target_env) {}
+
+ ~RemoveUnreferencedInstructionReductionPass() override = default;
+
+ // The name of this pass.
+ std::string GetName() const final;
+
+ protected:
+ // Finds all opportunities for removing unreferenced instructions in the
+ // given module.
+ std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
+ opt::IRContext* context) const final;
+
+ private:
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REMOVE_UNREFERENCED_INSTRUCTION_REDUCTION_PASS_H_
diff --git a/source/spirv_reducer_options.cpp b/source/spirv_reducer_options.cpp
new file mode 100644
index 0000000..110ea3e
--- /dev/null
+++ b/source/spirv_reducer_options.cpp
@@ -0,0 +1,31 @@
+// Copyright (c) 2018 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 <cassert>
+#include <cstring>
+
+#include "source/spirv_reducer_options.h"
+
+SPIRV_TOOLS_EXPORT spv_reducer_options spvReducerOptionsCreate() {
+ return new spv_reducer_options_t();
+}
+
+SPIRV_TOOLS_EXPORT void spvReducerOptionsDestroy(spv_reducer_options options) {
+ delete options;
+}
+
+SPIRV_TOOLS_EXPORT void spvReducerOptionsSetStepLimit(
+ spv_reducer_options options, uint32_t step_limit) {
+ options->step_limit = step_limit;
+}
diff --git a/source/spirv_reducer_options.h b/source/spirv_reducer_options.h
new file mode 100644
index 0000000..d48303c
--- /dev/null
+++ b/source/spirv_reducer_options.h
@@ -0,0 +1,35 @@
+// Copyright (c) 2018 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_SPIRV_REDUCER_OPTIONS_H_
+#define SOURCE_SPIRV_REDUCER_OPTIONS_H_
+
+#include "spirv-tools/libspirv.h"
+
+#include <string>
+#include <utility>
+
+// The default maximum number of steps for the reducer to run before giving up.
+const uint32_t kDefaultStepLimit = 250;
+
+// Manages command line options passed to the SPIR-V Reducer. New struct
+// members may be added for any new option.
+struct spv_reducer_options_t {
+ spv_reducer_options_t() : step_limit(kDefaultStepLimit) {}
+
+ // The number of steps the reducer will run for before giving up.
+ uint32_t step_limit;
+};
+
+#endif // SOURCE_SPIRV_REDUCER_OPTIONS_H_
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 53341a7..9226ea7 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -207,6 +207,7 @@
add_subdirectory(comp)
add_subdirectory(link)
add_subdirectory(opt)
+add_subdirectory(reduce)
add_subdirectory(stats)
add_subdirectory(tools)
add_subdirectory(util)
diff --git a/test/reduce/CMakeLists.txt b/test/reduce/CMakeLists.txt
new file mode 100644
index 0000000..e3c1e95
--- /dev/null
+++ b/test/reduce/CMakeLists.txt
@@ -0,0 +1,23 @@
+# Copyright (c) 2018 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.
+
+add_spvtools_unittest(TARGET reduce
+ SRCS operand_to_constant_reduction_pass_test.cpp
+ reduce_test_util.cpp
+ reduce_test_util.h
+ reducer_test.cpp
+ remove_unreferenced_instruction_reduction_pass_test.cpp
+ LIBS SPIRV-Tools-reduce
+ )
+
diff --git a/test/reduce/operand_to_constant_reduction_pass_test.cpp b/test/reduce/operand_to_constant_reduction_pass_test.cpp
new file mode 100644
index 0000000..34cc4a1
--- /dev/null
+++ b/test/reduce/operand_to_constant_reduction_pass_test.cpp
@@ -0,0 +1,156 @@
+// Copyright (c) 2018 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 "reduce_test_util.h"
+#include "source/opt/build_module.h"
+#include "source/reduce/operand_to_const_reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+TEST(OperandToConstantReductionPassTest, BasicCheck) {
+ std::string prologue = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %37
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %9 "buf1"
+ OpMemberName %9 0 "f"
+ OpName %11 ""
+ OpName %24 "buf2"
+ OpMemberName %24 0 "i"
+ OpName %26 ""
+ OpName %37 "_GLF_color"
+ OpMemberDecorate %9 0 Offset 0
+ OpDecorate %9 Block
+ OpDecorate %11 DescriptorSet 0
+ OpDecorate %11 Binding 1
+ OpMemberDecorate %24 0 Offset 0
+ OpDecorate %24 Block
+ OpDecorate %26 DescriptorSet 0
+ OpDecorate %26 Binding 2
+ OpDecorate %37 Location 0
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %9 = OpTypeStruct %6
+ %10 = OpTypePointer Uniform %9
+ %11 = OpVariable %10 Uniform
+ %12 = OpTypeInt 32 1
+ %13 = OpConstant %12 0
+ %14 = OpTypePointer Uniform %6
+ %20 = OpConstant %6 2
+ %24 = OpTypeStruct %12
+ %25 = OpTypePointer Uniform %24
+ %26 = OpVariable %25 Uniform
+ %27 = OpTypePointer Uniform %12
+ %33 = OpConstant %12 3
+ %35 = OpTypeVector %6 4
+ %36 = OpTypePointer Output %35
+ %37 = OpVariable %36 Output
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %15 = OpAccessChain %14 %11 %13
+ %16 = OpLoad %6 %15
+ %19 = OpFAdd %6 %16 %16
+ %21 = OpFAdd %6 %19 %20
+ %28 = OpAccessChain %27 %26 %13
+ %29 = OpLoad %12 %28
+ )";
+
+ std::string epilogue = R"(
+ %45 = OpConvertSToF %6 %34
+ %46 = OpCompositeConstruct %35 %16 %21 %43 %45
+ OpStore %37 %46
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ std::string original = prologue + R"(
+ %32 = OpIAdd %12 %29 %29
+ %34 = OpIAdd %12 %32 %33
+ %43 = OpConvertSToF %6 %29
+ )" + epilogue;
+
+ std::string expected = prologue + R"(
+ %32 = OpIAdd %12 %13 %13 ; %29 -> %13 x 2
+ %34 = OpIAdd %12 %13 %33 ; %32 -> %13
+ %43 = OpConvertSToF %6 %13 ; %29 -> %13
+ )" + epilogue;
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, original, kReduceAssembleOption);
+ const auto pass = TestSubclass<OperandToConstReductionPass>(env);
+ const auto ops = pass.WrapGetAvailableOpportunities(context.get());
+ ASSERT_EQ(17, ops.size());
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ ASSERT_TRUE(ops[1]->PreconditionHolds());
+ ops[1]->TryToApply();
+ ASSERT_TRUE(ops[2]->PreconditionHolds());
+ ops[2]->TryToApply();
+ ASSERT_TRUE(ops[3]->PreconditionHolds());
+ ops[3]->TryToApply();
+
+ CheckEqual(env, expected, context.get());
+}
+
+TEST(OperandToConstantReductionPassTest, WithCalledFunction) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %10 %12
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypeVector %6 4
+ %8 = OpTypeFunction %7
+ %9 = OpTypePointer Output %7
+ %10 = OpVariable %9 Output
+ %11 = OpTypePointer Input %7
+ %12 = OpVariable %11 Input
+ %13 = OpConstant %6 0
+ %14 = OpConstantComposite %7 %13 %13 %13 %13
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %15 = OpFunctionCall %7 %16
+ OpReturn
+ OpFunctionEnd
+ %16 = OpFunction %7 None %8
+ %17 = OpLabel
+ OpReturnValue %14
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, shader, kReduceAssembleOption);
+ const auto pass = TestSubclass<OperandToConstReductionPass>(env);
+ const auto ops = pass.WrapGetAvailableOpportunities(context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+} // namespace
+} // namespace reduce
+} // namespace spvtools
diff --git a/test/reduce/reduce_test_util.cpp b/test/reduce/reduce_test_util.cpp
new file mode 100644
index 0000000..022e7e3
--- /dev/null
+++ b/test/reduce/reduce_test_util.cpp
@@ -0,0 +1,52 @@
+// Copyright (c) 2018 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 "reduce_test_util.h"
+
+namespace spvtools {
+namespace reduce {
+
+void CheckEqual(const spv_target_env env,
+ const std::vector<uint32_t>& expected_binary,
+ const std::vector<uint32_t>& actual_binary) {
+ if (expected_binary != actual_binary) {
+ SpirvTools t(env);
+ std::string expected_disassembled;
+ std::string actual_disassembled;
+ ASSERT_TRUE(t.Disassemble(expected_binary, &expected_disassembled,
+ kReduceDisassembleOption));
+ ASSERT_TRUE(t.Disassemble(actual_binary, &actual_disassembled,
+ kReduceDisassembleOption));
+ ASSERT_EQ(expected_disassembled, actual_disassembled);
+ }
+}
+
+void CheckEqual(const spv_target_env env, const std::string& expected_text,
+ const std::vector<uint32_t>& actual_binary) {
+ std::vector<uint32_t> expected_binary;
+ SpirvTools t(env);
+ ASSERT_TRUE(
+ t.Assemble(expected_text, &expected_binary, kReduceAssembleOption));
+ CheckEqual(env, expected_binary, actual_binary);
+}
+
+void CheckEqual(const spv_target_env env, const std::string& expected_text,
+ const opt::IRContext* actual_ir) {
+ std::vector<uint32_t> actual_binary;
+ actual_ir->module()->ToBinary(&actual_binary, false);
+ CheckEqual(env, expected_text, actual_binary);
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/test/reduce/reduce_test_util.h b/test/reduce/reduce_test_util.h
new file mode 100644
index 0000000..0331799
--- /dev/null
+++ b/test/reduce/reduce_test_util.h
@@ -0,0 +1,70 @@
+// Copyright (c) 2018 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 TEST_REDUCE_REDUCE_TEST_UTIL_H_
+#define TEST_REDUCE_REDUCE_TEST_UTIL_H_
+
+#include "gtest/gtest.h"
+
+#include "source/opt/ir_context.h"
+#include "source/reduce/reduction_opportunity.h"
+#include "spirv-tools/libspirv.h"
+
+namespace spvtools {
+namespace reduce {
+
+// A helper class that subclasses a given reduction pass class in order to
+// provide a wrapper for its protected methods.
+template <class ReductionPassT>
+class TestSubclass : public ReductionPassT {
+ public:
+ // Creates an instance of the reduction pass subclass with respect to target
+ // environment |env|.
+ explicit TestSubclass(const spv_target_env env) : ReductionPassT(env) {}
+ ~TestSubclass() = default;
+
+ // A wrapper for GetAvailableOpportunities(...)
+ std::vector<std::unique_ptr<ReductionOpportunity>>
+ WrapGetAvailableOpportunities(opt::IRContext* context) const {
+ return ReductionPassT::GetAvailableOpportunities(context);
+ }
+};
+
+// Checks whether the given binaries are bit-wise equal.
+void CheckEqual(spv_target_env env,
+ const std::vector<uint32_t>& expected_binary,
+ const std::vector<uint32_t>& actual_binary);
+
+// Assembles the given text and check whether the resulting binary is bit-wise
+// equal to the given binary.
+void CheckEqual(spv_target_env env, const std::string& expected_text,
+ const std::vector<uint32_t>& actual_binary);
+
+// Assembles the given text and turns the given IR into binary, then checks
+// whether the resulting binaries are bit-wise equal.
+void CheckEqual(spv_target_env env, const std::string& expected_text,
+ const opt::IRContext* actual_ir);
+
+// Assembly options for writing reduction tests. It simplifies matters if
+// numeric ids do not change.
+const uint32_t kReduceAssembleOption =
+ SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS;
+// Disassembly options for writing reduction tests.
+const uint32_t kReduceDisassembleOption =
+ SPV_BINARY_TO_TEXT_OPTION_NO_HEADER | SPV_BINARY_TO_TEXT_OPTION_INDENT;
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // TEST_REDUCE_REDUCE_TEST_UTIL_H_
diff --git a/test/reduce/reducer_test.cpp b/test/reduce/reducer_test.cpp
new file mode 100644
index 0000000..5441a56
--- /dev/null
+++ b/test/reduce/reducer_test.cpp
@@ -0,0 +1,243 @@
+// Copyright (c) 2018 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 "reduce_test_util.h"
+
+#include "source/reduce/operand_to_const_reduction_pass.h"
+#include "source/reduce/reducer.h"
+#include "source/reduce/remove_unreferenced_instruction_reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+// Don't print reducer info during testing.
+void NopDiagnostic(spv_message_level_t /*level*/, const char* /*source*/,
+ const spv_position_t& /*position*/,
+ const char* /*message*/) {}
+
+// This changes is its mind each time IsInteresting is invoked as to whether the
+// binary is interesting, until some limit is reached after which the binary is
+// always deemed interesting. This is useful to test that reduction passes
+// interleave in interesting ways for a while, and then always succeed after
+// some point; the latter is important to end up with a predictable final
+// reduced binary for tests.
+class PingPongInteresting {
+ public:
+ explicit PingPongInteresting(uint32_t always_interesting_after)
+ : is_interesting_(true),
+ always_interesting_after_(always_interesting_after),
+ count_(0) {}
+
+ bool IsInteresting(const std::vector<uint32_t>&) {
+ bool result;
+ if (count_ > always_interesting_after_) {
+ result = true;
+ } else {
+ result = is_interesting_;
+ is_interesting_ = !is_interesting_;
+ }
+ count_++;
+ return result;
+ }
+
+ private:
+ bool is_interesting_;
+ const uint32_t always_interesting_after_;
+ uint32_t count_;
+};
+
+TEST(ReducerTest, ExprToConstantAndRemoveUnreferenced) {
+ std::string original = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %60
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %16 "buf2"
+ OpMemberName %16 0 "i"
+ OpName %18 ""
+ OpName %25 "buf1"
+ OpMemberName %25 0 "f"
+ OpName %27 ""
+ OpName %60 "_GLF_color"
+ OpMemberDecorate %16 0 Offset 0
+ OpDecorate %16 Block
+ OpDecorate %18 DescriptorSet 0
+ OpDecorate %18 Binding 2
+ OpMemberDecorate %25 0 Offset 0
+ OpDecorate %25 Block
+ OpDecorate %27 DescriptorSet 0
+ OpDecorate %27 Binding 1
+ OpDecorate %60 Location 0
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %9 = OpConstant %6 0
+ %16 = OpTypeStruct %6
+ %17 = OpTypePointer Uniform %16
+ %18 = OpVariable %17 Uniform
+ %19 = OpTypePointer Uniform %6
+ %22 = OpTypeBool
+ %100 = OpConstantTrue %22
+ %24 = OpTypeFloat 32
+ %25 = OpTypeStruct %24
+ %26 = OpTypePointer Uniform %25
+ %27 = OpVariable %26 Uniform
+ %28 = OpTypePointer Uniform %24
+ %31 = OpConstant %24 2
+ %56 = OpConstant %6 1
+ %58 = OpTypeVector %24 4
+ %59 = OpTypePointer Output %58
+ %60 = OpVariable %59 Output
+ %72 = OpUndef %24
+ %74 = OpUndef %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ %73 = OpPhi %6 %74 %5 %77 %34
+ %71 = OpPhi %24 %72 %5 %76 %34
+ %70 = OpPhi %6 %9 %5 %57 %34
+ %20 = OpAccessChain %19 %18 %9
+ %21 = OpLoad %6 %20
+ %23 = OpSLessThan %22 %70 %21
+ OpLoopMerge %12 %34 None
+ OpBranchConditional %23 %11 %12
+ %11 = OpLabel
+ %29 = OpAccessChain %28 %27 %9
+ %30 = OpLoad %24 %29
+ %32 = OpFOrdGreaterThan %22 %30 %31
+ OpSelectionMerge %34 None
+ OpBranchConditional %32 %33 %46
+ %33 = OpLabel
+ %40 = OpFAdd %24 %71 %30
+ %45 = OpISub %6 %73 %21
+ OpBranch %34
+ %46 = OpLabel
+ %50 = OpFMul %24 %71 %30
+ %54 = OpSDiv %6 %73 %21
+ OpBranch %34
+ %34 = OpLabel
+ %77 = OpPhi %6 %45 %33 %54 %46
+ %76 = OpPhi %24 %40 %33 %50 %46
+ %57 = OpIAdd %6 %70 %56
+ OpBranch %10
+ %12 = OpLabel
+ %61 = OpAccessChain %28 %27 %9
+ %62 = OpLoad %24 %61
+ %66 = OpConvertSToF %24 %21
+ %68 = OpConvertSToF %24 %73
+ %69 = OpCompositeConstruct %58 %62 %71 %66 %68
+ OpStore %60 %69
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ std::string expected = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %60
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %16 "buf2"
+ OpMemberName %16 0 "i"
+ OpName %18 ""
+ OpName %25 "buf1"
+ OpMemberName %25 0 "f"
+ OpName %27 ""
+ OpName %60 "_GLF_color"
+ OpMemberDecorate %16 0 Offset 0
+ OpDecorate %16 Block
+ OpDecorate %18 DescriptorSet 0
+ OpDecorate %18 Binding 2
+ OpMemberDecorate %25 0 Offset 0
+ OpDecorate %25 Block
+ OpDecorate %27 DescriptorSet 0
+ OpDecorate %27 Binding 1
+ OpDecorate %60 Location 0
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %9 = OpConstant %6 0
+ %16 = OpTypeStruct %6
+ %17 = OpTypePointer Uniform %16
+ %18 = OpVariable %17 Uniform
+ %19 = OpTypePointer Uniform %6
+ %22 = OpTypeBool
+ %100 = OpConstantTrue %22
+ %24 = OpTypeFloat 32
+ %25 = OpTypeStruct %24
+ %26 = OpTypePointer Uniform %25
+ %27 = OpVariable %26 Uniform
+ %28 = OpTypePointer Uniform %24
+ %31 = OpConstant %24 2
+ %56 = OpConstant %6 1
+ %58 = OpTypeVector %24 4
+ %59 = OpTypePointer Output %58
+ %60 = OpVariable %59 Output
+ %72 = OpUndef %24
+ %74 = OpUndef %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpLoopMerge %12 %34 None
+ OpBranchConditional %100 %11 %12
+ %11 = OpLabel
+ OpSelectionMerge %34 None
+ OpBranchConditional %100 %33 %46
+ %33 = OpLabel
+ OpBranch %34
+ %46 = OpLabel
+ OpBranch %34
+ %34 = OpLabel
+ OpBranch %10
+ %12 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
+ Reducer reducer(env);
+ PingPongInteresting ping_pong_interesting(10);
+ reducer.SetMessageConsumer(NopDiagnostic);
+ reducer.SetInterestingnessFunction(
+ [&](const std::vector<uint32_t>& binary, uint32_t) -> bool {
+ return ping_pong_interesting.IsInteresting(binary);
+ });
+ reducer.AddReductionPass(MakeUnique<OperandToConstReductionPass>(env));
+ reducer.AddReductionPass(
+ MakeUnique<RemoveUnreferencedInstructionReductionPass>(env));
+
+ std::vector<uint32_t> binary_in;
+ SpirvTools t(env);
+
+ ASSERT_TRUE(t.Assemble(original, &binary_in, kReduceAssembleOption));
+ std::vector<uint32_t> binary_out;
+ spvtools::ReducerOptions reducer_options;
+ reducer_options.set_step_limit(500);
+
+ reducer.Run(std::move(binary_in), &binary_out, reducer_options);
+
+ CheckEqual(env, expected, binary_out);
+}
+
+} // namespace
+} // namespace reduce
+} // namespace spvtools
\ No newline at end of file
diff --git a/test/reduce/remove_unreferenced_instruction_reduction_pass_test.cpp b/test/reduce/remove_unreferenced_instruction_reduction_pass_test.cpp
new file mode 100644
index 0000000..a002fa3
--- /dev/null
+++ b/test/reduce/remove_unreferenced_instruction_reduction_pass_test.cpp
@@ -0,0 +1,230 @@
+// Copyright (c) 2018 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 "reduce_test_util.h"
+
+#include "source/opt/build_module.h"
+#include "source/reduce/reduction_opportunity.h"
+#include "source/reduce/remove_unreferenced_instruction_reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+TEST(RemoveUnreferencedInstructionReductionPassTest, RemoveStores) {
+ const std::string prologue = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "a"
+ OpName %10 "b"
+ OpName %12 "c"
+ OpName %14 "d"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 10
+ %11 = OpConstant %6 20
+ %13 = OpConstant %6 30
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %12 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ )";
+
+ const std::string epilogue = R"(
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const std::string original = prologue + R"(
+ OpStore %8 %9
+ OpStore %10 %11
+ OpStore %12 %13
+ %15 = OpLoad %6 %8
+ OpStore %14 %15
+ )" + epilogue;
+
+ const std::string expected = prologue + R"(
+ OpStore %12 %13
+ %15 = OpLoad %6 %8
+ OpStore %14 %15
+ )" + epilogue;
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, original, kReduceAssembleOption);
+ const auto pass =
+ TestSubclass<RemoveUnreferencedInstructionReductionPass>(env);
+ const auto ops = pass.WrapGetAvailableOpportunities(context.get());
+ ASSERT_EQ(4, ops.size());
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ ASSERT_TRUE(ops[1]->PreconditionHolds());
+ ops[1]->TryToApply();
+
+ CheckEqual(env, expected, context.get());
+}
+
+TEST(RemoveUnreferencedInstructionReductionPassTest, ApplyReduction) {
+ const std::string prologue = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "a"
+ OpName %10 "b"
+ OpName %12 "c"
+ OpName %14 "d"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 10
+ %11 = OpConstant %6 20
+ %13 = OpConstant %6 30
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %12 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ )";
+
+ const std::string epilogue = R"(
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const std::string original = prologue + R"(
+ OpStore %8 %9
+ OpStore %10 %11
+ OpStore %12 %13
+ %15 = OpLoad %6 %8
+ OpStore %14 %15
+ )" + epilogue;
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+
+ std::vector<uint32_t> binary;
+ SpirvTools t(env);
+ ASSERT_TRUE(t.Assemble(original, &binary, kReduceAssembleOption));
+
+ auto pass = TestSubclass<RemoveUnreferencedInstructionReductionPass>(env);
+
+ {
+ // Attempt 1 should remove everything removable.
+ const std::string expected_reduced = prologue + R"(
+ %15 = OpLoad %6 %8
+ )" + epilogue;
+ auto reduced_binary = pass.TryApplyReduction(binary);
+ CheckEqual(env, expected_reduced, reduced_binary);
+ }
+
+ // Attempt 2 should fail as pass with granularity 4 got to end.
+ ASSERT_EQ(0, pass.TryApplyReduction(binary).size());
+
+ {
+ // Attempt 3 should remove first two removable statements.
+ const std::string expected_reduced = prologue + R"(
+ OpStore %12 %13
+ %15 = OpLoad %6 %8
+ OpStore %14 %15
+ )" + epilogue;
+ auto reduced_binary = pass.TryApplyReduction(binary);
+ CheckEqual(env, expected_reduced, reduced_binary);
+ }
+
+ {
+ // Attempt 4 should remove last two removable statements.
+ const std::string expected_reduced = prologue + R"(
+ OpStore %8 %9
+ OpStore %10 %11
+ %15 = OpLoad %6 %8
+ )" + epilogue;
+ auto reduced_binary = pass.TryApplyReduction(binary);
+ CheckEqual(env, expected_reduced, reduced_binary);
+ }
+
+ // Attempt 5 should fail as pass with granularity 2 got to end.
+ ASSERT_EQ(0, pass.TryApplyReduction(binary).size());
+
+ {
+ // Attempt 6 should remove first removable statement.
+ const std::string expected_reduced = prologue + R"(
+ OpStore %10 %11
+ OpStore %12 %13
+ %15 = OpLoad %6 %8
+ OpStore %14 %15
+ )" + epilogue;
+ auto reduced_binary = pass.TryApplyReduction(binary);
+ CheckEqual(env, expected_reduced, reduced_binary);
+ }
+
+ {
+ // Attempt 7 should remove second removable statement.
+ const std::string expected_reduced = prologue + R"(
+ OpStore %8 %9
+ OpStore %12 %13
+ %15 = OpLoad %6 %8
+ OpStore %14 %15
+ )" + epilogue;
+ auto reduced_binary = pass.TryApplyReduction(binary);
+ CheckEqual(env, expected_reduced, reduced_binary);
+ }
+
+ {
+ // Attempt 8 should remove third removable statement.
+ const std::string expected_reduced = prologue + R"(
+ OpStore %8 %9
+ OpStore %10 %11
+ %15 = OpLoad %6 %8
+ OpStore %14 %15
+ )" + epilogue;
+ auto reduced_binary = pass.TryApplyReduction(binary);
+ CheckEqual(env, expected_reduced, reduced_binary);
+ }
+
+ {
+ // Attempt 9 should remove fourth removable statement.
+ const std::string expected_reduced = prologue + R"(
+ OpStore %8 %9
+ OpStore %10 %11
+ OpStore %12 %13
+ %15 = OpLoad %6 %8
+ )" + epilogue;
+ auto reduced_binary = pass.TryApplyReduction(binary);
+ CheckEqual(env, expected_reduced, reduced_binary);
+ }
+
+ // Attempt 10 should fail as pass with granularity 1 got to end.
+ ASSERT_EQ(0, pass.TryApplyReduction(binary).size());
+
+ ASSERT_TRUE(pass.ReachedMinimumGranularity());
+}
+
+} // namespace
+} // namespace reduce
+} // namespace spvtools
diff --git a/tools/CMakeLists.txt b/tools/CMakeLists.txt
index 67143d8..9fb3a91 100644
--- a/tools/CMakeLists.txt
+++ b/tools/CMakeLists.txt
@@ -42,6 +42,7 @@
add_spvtools_tool(TARGET spirv-dis SRCS dis/dis.cpp LIBS ${SPIRV_TOOLS})
add_spvtools_tool(TARGET spirv-val SRCS val/val.cpp util/cli_consumer.cpp LIBS ${SPIRV_TOOLS})
add_spvtools_tool(TARGET spirv-opt SRCS opt/opt.cpp util/cli_consumer.cpp LIBS SPIRV-Tools-opt ${SPIRV_TOOLS})
+ add_spvtools_tool(TARGET spirv-reduce SRCS reduce/reduce.cpp util/cli_consumer.cpp LIBS SPIRV-Tools-reduce ${SPIRV_TOOLS})
add_spvtools_tool(TARGET spirv-link SRCS link/linker.cpp LIBS SPIRV-Tools-link ${SPIRV_TOOLS})
add_spvtools_tool(TARGET spirv-stats
SRCS stats/stats.cpp
@@ -61,7 +62,7 @@
${SPIRV_HEADER_INCLUDE_DIR})
set(SPIRV_INSTALL_TARGETS spirv-as spirv-dis spirv-val spirv-opt spirv-stats
- spirv-cfg spirv-link)
+ spirv-cfg spirv-link spirv-reduce)
if(SPIRV_BUILD_COMPRESSION)
add_spvtools_tool(TARGET spirv-markv
diff --git a/tools/reduce/reduce.cpp b/tools/reduce/reduce.cpp
new file mode 100644
index 0000000..ac82d66
--- /dev/null
+++ b/tools/reduce/reduce.cpp
@@ -0,0 +1,230 @@
+// Copyright (c) 2018 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 <cassert>
+#include <cerrno>
+#include <cstring>
+#include <functional>
+
+#include "source/opt/build_module.h"
+#include "source/opt/ir_context.h"
+#include "source/opt/log.h"
+#include "source/reduce/operand_to_const_reduction_pass.h"
+#include "source/reduce/reducer.h"
+#include "source/reduce/remove_unreferenced_instruction_reduction_pass.h"
+#include "source/spirv_reducer_options.h"
+#include "source/util/make_unique.h"
+#include "source/util/string_utils.h"
+#include "spirv-tools/libspirv.hpp"
+#include "tools/io.h"
+#include "tools/util/cli_consumer.h"
+
+using namespace spvtools::reduce;
+
+namespace {
+
+using ErrorOrInt = std::pair<std::string, int>;
+
+// Check that the std::system function can actually be used.
+bool CheckExecuteCommand() {
+ int res = std::system(nullptr);
+ return res != 0;
+}
+
+// Execute a command using the shell.
+// Returns true if and only if the command's exit status was 0.
+bool ExecuteCommand(const std::string& command) {
+ errno = 0;
+ int status = std::system(command.c_str());
+ assert(errno == 0 && "failed to execute command");
+ // The result returned by 'system' is implementation-defined, but is
+ // usually the case that the returned value is 0 when the command's exit
+ // code was 0. We are assuming that here, and that's all we depend on.
+ return status == 0;
+}
+
+// Status and actions to perform after parsing command-line arguments.
+enum ReduceActions { REDUCE_CONTINUE, REDUCE_STOP };
+
+struct ReduceStatus {
+ ReduceActions action;
+ int code;
+};
+
+void PrintUsage(const char* program) {
+ // NOTE: Please maintain flags in lexicographical order.
+ printf(
+ R"(%s - Reduce a SPIR-V binary file with respect to a user-provided
+ interestingness test.
+
+USAGE: %s [options] <input> <interestingness-test>
+
+The SPIR-V binary is read from <input>.
+
+Whether a binary is interesting is determined by <interestingness-test>, which
+is typically a script.
+
+NOTE: The reducer is a work in progress.
+
+Options (in lexicographical order):
+ -h, --help
+ Print this help.
+ --step-limit
+ 32-bit unsigned integer specifying maximum number of
+ steps the reducer will take before giving up.
+ --version
+ Display reducer version information.
+)",
+ program, program);
+}
+
+// Message consumer for this tool. Used to emit diagnostics during
+// initialization and setup. Note that |source| and |position| are irrelevant
+// here because we are still not processing a SPIR-V input file.
+void ReduceDiagnostic(spv_message_level_t level, const char* /*source*/,
+ const spv_position_t& /*position*/, const char* message) {
+ if (level == SPV_MSG_ERROR) {
+ fprintf(stderr, "error: ");
+ }
+ fprintf(stderr, "%s\n", message);
+}
+
+ReduceStatus ParseFlags(int argc, const char** argv, const char** in_file,
+ const char** interestingness_test,
+ spvtools::ReducerOptions* reducer_options) {
+ uint32_t positional_arg_index = 0;
+
+ for (int argi = 1; argi < argc; ++argi) {
+ const char* cur_arg = argv[argi];
+ if ('-' == cur_arg[0]) {
+ if (0 == strcmp(cur_arg, "--version")) {
+ spvtools::Logf(ReduceDiagnostic, SPV_MSG_INFO, nullptr, {}, "%s\n",
+ spvSoftwareVersionDetailsString());
+ return {REDUCE_STOP, 0};
+ } else if (0 == strcmp(cur_arg, "--help") || 0 == strcmp(cur_arg, "-h")) {
+ PrintUsage(argv[0]);
+ return {REDUCE_STOP, 0};
+ } else if ('\0' == cur_arg[1]) {
+ // We do not support reduction from standard input. We could support
+ // this if there was a compelling use case.
+ PrintUsage(argv[0]);
+ return {REDUCE_STOP, 0};
+ } else if (0 == strncmp(cur_arg,
+ "--step-limit=", sizeof("--step-limit=") - 1)) {
+ const auto split_flag = spvtools::utils::SplitFlagArgs(cur_arg);
+ char* end = nullptr;
+ errno = 0;
+ const auto step_limit =
+ static_cast<uint32_t>(strtol(split_flag.second.c_str(), &end, 10));
+ assert(end != split_flag.second.c_str() && errno == 0);
+ reducer_options->set_step_limit(step_limit);
+ }
+ } else if (positional_arg_index == 0) {
+ // Input file name
+ assert(!*in_file);
+ *in_file = cur_arg;
+ positional_arg_index++;
+ } else if (positional_arg_index == 1) {
+ assert(!*interestingness_test);
+ *interestingness_test = cur_arg;
+ positional_arg_index++;
+ } else {
+ spvtools::Error(ReduceDiagnostic, nullptr, {},
+ "Too many positional arguments specified");
+ return {REDUCE_STOP, 1};
+ }
+ }
+
+ if (!*in_file) {
+ spvtools::Error(ReduceDiagnostic, nullptr, {}, "No input file specified");
+ return {REDUCE_STOP, 1};
+ }
+
+ if (!*interestingness_test) {
+ spvtools::Error(ReduceDiagnostic, nullptr, {},
+ "No interestingness test specified");
+ return {REDUCE_STOP, 1};
+ }
+
+ return {REDUCE_CONTINUE, 0};
+}
+
+} // namespace
+
+const auto kDefaultEnvironment = SPV_ENV_UNIVERSAL_1_3;
+
+int main(int argc, const char** argv) {
+ const char* in_file = nullptr;
+ const char* interestingness_test = nullptr;
+
+ spv_target_env target_env = kDefaultEnvironment;
+ spvtools::ReducerOptions reducer_options;
+
+ ReduceStatus status =
+ ParseFlags(argc, argv, &in_file, &interestingness_test, &reducer_options);
+
+ if (status.action == REDUCE_STOP) {
+ return status.code;
+ }
+
+ if (!CheckExecuteCommand()) {
+ std::cerr << "could not find shell interpreter for executing a command"
+ << std::endl;
+ return 2;
+ }
+
+ Reducer reducer(target_env);
+
+ reducer.SetInterestingnessFunction(
+ [interestingness_test](std::vector<uint32_t> binary,
+ uint32_t reductions_applied) -> bool {
+ std::stringstream ss;
+ ss << "temp_" << std::setw(4) << std::setfill('0') << reductions_applied
+ << ".spv";
+ const auto spv_file = ss.str();
+ const std::string command =
+ std::string(interestingness_test) + " " + spv_file;
+ auto write_file_succeeded =
+ WriteFile(spv_file.c_str(), "wb", &binary[0], binary.size());
+ (void)(write_file_succeeded);
+ assert(write_file_succeeded);
+ return ExecuteCommand(command);
+ });
+
+ reducer.AddReductionPass(
+ spvtools::MakeUnique<OperandToConstReductionPass>(target_env));
+ reducer.AddReductionPass(
+ spvtools::MakeUnique<RemoveUnreferencedInstructionReductionPass>(
+ target_env));
+
+ reducer.SetMessageConsumer(spvtools::utils::CLIMessageConsumer);
+
+ std::vector<uint32_t> binary_in;
+ if (!ReadFile<uint32_t>(in_file, "rb", &binary_in)) {
+ return 1;
+ }
+
+ std::vector<uint32_t> binary_out;
+ const auto reduction_status =
+ reducer.Run(std::move(binary_in), &binary_out, reducer_options);
+
+ if (reduction_status ==
+ Reducer::ReductionResultStatus::kInitialStateNotInteresting ||
+ !WriteFile<uint32_t>("_reduced_final.spv", "wb", binary_out.data(),
+ binary_out.size())) {
+ return 1;
+ }
+
+ return 0;
+}
