New spirv-reduce reduction pass: operand to dominating id. (#2099)
* Added a reduction pass to replace ids with ids of the same type that dominate them.
* Introduce helper method for querying whether an operand type is an input id.
diff --git a/source/operand.cpp b/source/operand.cpp
index c97b13f..923074e 100644
--- a/source/operand.cpp
+++ b/source/operand.cpp
@@ -411,6 +411,21 @@
}
}
+bool spvIsInIdType(spv_operand_type_t type) {
+ if (!spvIsIdType(type)) {
+ // If it is not an ID it cannot be an input ID.
+ return false;
+ }
+ switch (type) {
+ // Blacklist non-input IDs.
+ case SPV_OPERAND_TYPE_TYPE_ID:
+ case SPV_OPERAND_TYPE_RESULT_ID:
+ return false;
+ default:
+ return true;
+ }
+}
+
std::function<bool(unsigned)> spvOperandCanBeForwardDeclaredFunction(
SpvOp opcode) {
std::function<bool(unsigned index)> out;
diff --git a/source/operand.h b/source/operand.h
index 76f16f7..15a1825 100644
--- a/source/operand.h
+++ b/source/operand.h
@@ -131,6 +131,9 @@
// Is the operand an ID?
bool spvIsIdType(spv_operand_type_t type);
+// Is the operand an input ID?
+bool spvIsInIdType(spv_operand_type_t type);
+
// Takes the opcode of an instruction and returns
// a function object that will return true if the index
// of the operand can be forward declared. This function will
diff --git a/source/opt/instruction.h b/source/opt/instruction.h
index 6a9d954..034da76 100644
--- a/source/opt/instruction.h
+++ b/source/opt/instruction.h
@@ -618,15 +618,8 @@
inline bool Instruction::WhileEachInId(
const std::function<bool(uint32_t*)>& f) {
for (auto& opnd : operands_) {
- switch (opnd.type) {
- case SPV_OPERAND_TYPE_RESULT_ID:
- case SPV_OPERAND_TYPE_TYPE_ID:
- break;
- default:
- if (spvIsIdType(opnd.type)) {
- if (!f(&opnd.words[0])) return false;
- }
- break;
+ if (spvIsInIdType(opnd.type)) {
+ if (!f(&opnd.words[0])) return false;
}
}
return true;
@@ -635,15 +628,8 @@
inline bool Instruction::WhileEachInId(
const std::function<bool(const uint32_t*)>& f) const {
for (const auto& opnd : operands_) {
- switch (opnd.type) {
- case SPV_OPERAND_TYPE_RESULT_ID:
- case SPV_OPERAND_TYPE_TYPE_ID:
- break;
- default:
- if (spvIsIdType(opnd.type)) {
- if (!f(&opnd.words[0])) return false;
- }
- break;
+ if (spvIsInIdType(opnd.type)) {
+ if (!f(&opnd.words[0])) return false;
}
}
return true;
diff --git a/source/reduce/CMakeLists.txt b/source/reduce/CMakeLists.txt
index 995e1e6..fc7369f 100644
--- a/source/reduce/CMakeLists.txt
+++ b/source/reduce/CMakeLists.txt
@@ -14,6 +14,7 @@
set(SPIRV_TOOLS_REDUCE_SOURCES
change_operand_reduction_opportunity.h
operand_to_const_reduction_pass.h
+ operand_to_dominating_id_reduction_pass.h
reducer.h
reduction_opportunity.h
reduction_pass.h
@@ -22,6 +23,7 @@
change_operand_reduction_opportunity.cpp
operand_to_const_reduction_pass.cpp
+ operand_to_dominating_id_reduction_pass.cpp
reducer.cpp
reduction_opportunity.cpp
reduction_pass.cpp
diff --git a/source/reduce/change_operand_reduction_opportunity.h b/source/reduce/change_operand_reduction_opportunity.h
index ba67cd0..9e43ec9 100644
--- a/source/reduce/change_operand_reduction_opportunity.h
+++ b/source/reduce/change_operand_reduction_opportunity.h
@@ -34,7 +34,7 @@
uint32_t new_id)
: inst_(inst),
operand_index_(operand_index),
- original_id_(inst_->GetOperand(operand_index_).words[0]),
+ original_id_(inst->GetOperand(operand_index).words[0]),
original_type_(inst->GetOperand(operand_index).type),
new_id_(new_id) {}
diff --git a/source/reduce/operand_to_const_reduction_pass.cpp b/source/reduce/operand_to_const_reduction_pass.cpp
index b1b1385..35c0f4b 100644
--- a/source/reduce/operand_to_const_reduction_pass.cpp
+++ b/source/reduce/operand_to_const_reduction_pass.cpp
@@ -44,11 +44,7 @@
// 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;
- }
+ if (spvIsInIdType(operand.type)) {
const auto id = operand.words[0];
auto def = context->get_def_use_mgr()->GetDef(id);
if (spvOpcodeIsConstant(def->opcode())) {
diff --git a/source/reduce/operand_to_dominating_id_reduction_pass.cpp b/source/reduce/operand_to_dominating_id_reduction_pass.cpp
new file mode 100644
index 0000000..9280a41
--- /dev/null
+++ b/source/reduce/operand_to_dominating_id_reduction_pass.cpp
@@ -0,0 +1,114 @@
+// 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 "operand_to_dominating_id_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>>
+OperandToDominatingIdReductionPass::GetAvailableOpportunities(
+ opt::IRContext* context) const {
+ std::vector<std::unique_ptr<ReductionOpportunity>> result;
+
+ // Go through every instruction in every block, considering it as a potential
+ // dominator of other instructions. We choose this order for two reasons:
+ //
+ // (1) it is profitable for multiple opportunities to replace the same id x by
+ // different dominating ids y and z to be discontiguous, as they are
+ // incompatible.
+ //
+ // (2) We want to prioritise opportunities to replace an id with a more
+ // distant dominator. Intuitively, in a human-readable programming language
+ // if we have a complex expression e with many sub-expressions, we would like
+ // to prioritise replacing e with its smallest sub-expressions; generalising
+ // this idea to dominating ids this roughly corresponds to more distant
+ // dominators.
+ for (auto& function : *context->module()) {
+ for (auto dominating_block = function.begin();
+ dominating_block != function.end(); ++dominating_block) {
+ for (auto& dominating_inst : *dominating_block) {
+ if (dominating_inst.HasResultId() && dominating_inst.type_id()) {
+ // Consider replacing any operand with matching type in a dominated
+ // instruction with the id generated by this instruction.
+ GetOpportunitiesForDominatingInst(
+ &result, &dominating_inst, dominating_block, &function, context);
+ }
+ }
+ }
+ }
+ return result;
+}
+
+void OperandToDominatingIdReductionPass::GetOpportunitiesForDominatingInst(
+ std::vector<std::unique_ptr<ReductionOpportunity>>* opportunities,
+ opt::Instruction* candidate_dominator,
+ opt::Function::iterator candidate_dominator_block, opt::Function* function,
+ opt::IRContext* context) const {
+ assert(candidate_dominator->HasResultId());
+ assert(candidate_dominator->type_id());
+ auto dominator_analysis = context->GetDominatorAnalysis(function);
+ // SPIR-V requires a block to precede all blocks it dominates, so it suffices
+ // to search from the candidate dominator block onwards.
+ for (auto block = candidate_dominator_block; block != function->end();
+ ++block) {
+ if (!dominator_analysis->Dominates(&*candidate_dominator_block, &*block)) {
+ // If the candidate dominator block doesn't dominate this block then there
+ // cannot be any of the desired reduction opportunities in this block.
+ continue;
+ }
+ 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 (spvIsInIdType(operand.type)) {
+ const auto id = operand.words[0];
+ auto def = context->get_def_use_mgr()->GetDef(id);
+ assert(def);
+ if (!context->get_instr_block(def)) {
+ // The definition does not come from a block; e.g. it might be a
+ // constant. It is thus not relevant to this pass.
+ continue;
+ }
+ // Sanity check that we don't get here if the argument is a constant.
+ assert(!context->get_constant_mgr()->GetConstantFromInst(def));
+ if (def->type_id() != candidate_dominator->type_id()) {
+ // The types need to match.
+ continue;
+ }
+ if (candidate_dominator != def &&
+ dominator_analysis->Dominates(candidate_dominator, def)) {
+ // A hit: the candidate dominator strictly dominates the definition.
+ opportunities->push_back(
+ MakeUnique<ChangeOperandReductionOpportunity>(
+ &inst, index, candidate_dominator->result_id()));
+ }
+ }
+ }
+ }
+ }
+}
+
+std::string OperandToDominatingIdReductionPass::GetName() const {
+ return "OperandToDominatingIdReductionPass";
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/operand_to_dominating_id_reduction_pass.h b/source/reduce/operand_to_dominating_id_reduction_pass.h
new file mode 100644
index 0000000..b62b6ae
--- /dev/null
+++ b/source/reduce/operand_to_dominating_id_reduction_pass.h
@@ -0,0 +1,62 @@
+// 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.
+
+#ifndef SOURCE_REDUCE_OPERAND_TO_DOMINATING_ID_REDUCTION_PASS_H_
+#define SOURCE_REDUCE_OPERAND_TO_DOMINATING_ID_REDUCTION_PASS_H_
+
+#include "reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+
+// A reduction pass that aims to bring to SPIR-V (and generalize) the idea from
+// human-readable languages of e.g. replacing an expression with one of its
+// arguments, (x + y) -> x, or with a reference to an identifier that was
+// assigned to higher up in the program. The generalization of this is to
+// replace an id with a different id of the same type defined in some
+// dominating instruction.
+//
+// If id x is defined and then used several times, changing each use of x to
+// some dominating definition may eventually allow the statement defining x
+// to be eliminated by another pass.
+class OperandToDominatingIdReductionPass : public ReductionPass {
+ public:
+ // Creates the reduction pass in the context of the given target environment
+ // |target_env|
+ explicit OperandToDominatingIdReductionPass(const spv_target_env target_env)
+ : ReductionPass(target_env) {}
+
+ ~OperandToDominatingIdReductionPass() override = default;
+
+ // The name of this pass.
+ std::string GetName() const final;
+
+ protected:
+ // Finds all opportunities for replacing an operand with a dominating
+ // instruction in a given module.
+ std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
+ opt::IRContext* context) const final;
+
+ private:
+ void GetOpportunitiesForDominatingInst(
+ std::vector<std::unique_ptr<ReductionOpportunity>>* opportunities,
+ opt::Instruction* dominating_instruction,
+ opt::Function::iterator candidate_dominator_block,
+ opt::Function* function, opt::IRContext* context) const;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_OPERAND_TO_DOMINATING_ID_REDUCTION_PASS_H_
diff --git a/test/reduce/CMakeLists.txt b/test/reduce/CMakeLists.txt
index e3c1e95..828bf68 100644
--- a/test/reduce/CMakeLists.txt
+++ b/test/reduce/CMakeLists.txt
@@ -14,6 +14,7 @@
add_spvtools_unittest(TARGET reduce
SRCS operand_to_constant_reduction_pass_test.cpp
+ operand_to_dominating_id_reduction_pass_test.cpp
reduce_test_util.cpp
reduce_test_util.h
reducer_test.cpp
diff --git a/test/reduce/operand_to_dominating_id_reduction_pass_test.cpp b/test/reduce/operand_to_dominating_id_reduction_pass_test.cpp
new file mode 100644
index 0000000..cc0de65
--- /dev/null
+++ b/test/reduce/operand_to_dominating_id_reduction_pass_test.cpp
@@ -0,0 +1,196 @@
+// 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 "source/reduce/operand_to_dominating_id_reduction_pass.h"
+#include "reduce_test_util.h"
+#include "source/opt/build_module.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+TEST(OperandToDominatingIdReductionPassTest, BasicCheck) {
+ std::string original = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ %12 = OpLoad %6 %8
+ %13 = OpIAdd %6 %11 %12
+ OpStore %10 %13
+ %15 = OpLoad %6 %10
+ OpStore %14 %15
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, original, kReduceAssembleOption);
+ const auto pass = TestSubclass<OperandToDominatingIdReductionPass>(env);
+ const auto ops = pass.WrapGetAvailableOpportunities(context.get());
+ ASSERT_EQ(10, ops.size());
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+
+ std::string after_op_0 = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ %12 = OpLoad %6 %8
+ %13 = OpIAdd %6 %11 %12
+ OpStore %8 %13 ; %10 -> %8
+ %15 = OpLoad %6 %10
+ OpStore %14 %15
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ CheckEqual(env, after_op_0, context.get());
+
+ ASSERT_TRUE(ops[1]->PreconditionHolds());
+ ops[1]->TryToApply();
+
+ std::string after_op_1 = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ %12 = OpLoad %6 %8
+ %13 = OpIAdd %6 %11 %12
+ OpStore %8 %13 ; %10 -> %8
+ %15 = OpLoad %6 %8 ; %10 -> %8
+ OpStore %14 %15
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ CheckEqual(env, after_op_1, context.get());
+
+ ASSERT_TRUE(ops[2]->PreconditionHolds());
+ ops[2]->TryToApply();
+
+ std::string after_op_2 = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ %12 = OpLoad %6 %8
+ %13 = OpIAdd %6 %11 %12
+ OpStore %8 %13 ; %10 -> %8
+ %15 = OpLoad %6 %8 ; %10 -> %8
+ OpStore %8 %15 ; %14 -> %8
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ CheckEqual(env, after_op_2, context.get());
+
+ // The precondition has been disabled by an earlier opportunity's application.
+ ASSERT_FALSE(ops[3]->PreconditionHolds());
+
+ ASSERT_TRUE(ops[4]->PreconditionHolds());
+ ops[4]->TryToApply();
+
+ std::string after_op_4 = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %8 %9
+ %11 = OpLoad %6 %8
+ %12 = OpLoad %6 %8
+ %13 = OpIAdd %6 %11 %11 ; %12 -> %11
+ OpStore %8 %13 ; %10 -> %8
+ %15 = OpLoad %6 %8 ; %10 -> %8
+ OpStore %8 %15 ; %14 -> %8
+ OpReturn
+ OpFunctionEnd
+ )";
+ CheckEqual(env, after_op_4, context.get());
+}
+
+} // namespace
+} // namespace reduce
+} // namespace spvtools
diff --git a/tools/reduce/reduce.cpp b/tools/reduce/reduce.cpp
index ac82d66..6b0af09 100644
--- a/tools/reduce/reduce.cpp
+++ b/tools/reduce/reduce.cpp
@@ -21,6 +21,7 @@
#include "source/opt/ir_context.h"
#include "source/opt/log.h"
#include "source/reduce/operand_to_const_reduction_pass.h"
+#include "source/reduce/operand_to_dominating_id_reduction_pass.h"
#include "source/reduce/reducer.h"
#include "source/reduce/remove_unreferenced_instruction_reduction_pass.h"
#include "source/spirv_reducer_options.h"
@@ -205,6 +206,8 @@
reducer.AddReductionPass(
spvtools::MakeUnique<OperandToConstReductionPass>(target_env));
reducer.AddReductionPass(
+ spvtools::MakeUnique<OperandToDominatingIdReductionPass>(target_env));
+ reducer.AddReductionPass(
spvtools::MakeUnique<RemoveUnreferencedInstructionReductionPass>(
target_env));
