reduce: add remove_selection_reduction_opportunity (#2485)
Fix #2484
diff --git a/source/reduce/CMakeLists.txt b/source/reduce/CMakeLists.txt
index 4680231..4a5d540 100644
--- a/source/reduce/CMakeLists.txt
+++ b/source/reduce/CMakeLists.txt
@@ -30,6 +30,8 @@
remove_function_reduction_opportunity.h
remove_function_reduction_opportunity_finder.h
remove_opname_instruction_reduction_opportunity_finder.h
+ remove_selection_reduction_opportunity.h
+ remove_selection_reduction_opportunity_finder.h
remove_unreferenced_instruction_reduction_opportunity_finder.h
structured_loop_to_selection_reduction_opportunity.h
structured_loop_to_selection_reduction_opportunity_finder.h
@@ -50,6 +52,8 @@
remove_function_reduction_opportunity.cpp
remove_function_reduction_opportunity_finder.cpp
remove_instruction_reduction_opportunity.cpp
+ remove_selection_reduction_opportunity.cpp
+ remove_selection_reduction_opportunity_finder.cpp
remove_unreferenced_instruction_reduction_opportunity_finder.cpp
remove_opname_instruction_reduction_opportunity_finder.cpp
structured_loop_to_selection_reduction_opportunity.cpp
diff --git a/source/reduce/reducer.cpp b/source/reduce/reducer.cpp
index 462c13c..80c7349 100644
--- a/source/reduce/reducer.cpp
+++ b/source/reduce/reducer.cpp
@@ -21,6 +21,7 @@
#include "source/reduce/operand_to_undef_reduction_opportunity_finder.h"
#include "source/reduce/remove_function_reduction_opportunity_finder.h"
#include "source/reduce/remove_opname_instruction_reduction_opportunity_finder.h"
+#include "source/reduce/remove_selection_reduction_opportunity_finder.h"
#include "source/reduce/remove_unreferenced_instruction_reduction_opportunity_finder.h"
#include "source/reduce/structured_loop_to_selection_reduction_opportunity_finder.h"
#include "source/spirv_reducer_options.h"
@@ -185,6 +186,8 @@
spvtools::MakeUnique<MergeBlocksReductionOpportunityFinder>());
AddReductionPass(
spvtools::MakeUnique<RemoveFunctionReductionOpportunityFinder>());
+ AddReductionPass(
+ spvtools::MakeUnique<RemoveSelectionReductionOpportunityFinder>());
}
void Reducer::AddReductionPass(
diff --git a/source/reduce/remove_selection_reduction_opportunity.cpp b/source/reduce/remove_selection_reduction_opportunity.cpp
new file mode 100644
index 0000000..96f0147
--- /dev/null
+++ b/source/reduce/remove_selection_reduction_opportunity.cpp
@@ -0,0 +1,31 @@
+// Copyright (c) 2019 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/reduce/remove_selection_reduction_opportunity.h"
+
+#include "source/opt/basic_block.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace reduce {
+
+bool RemoveSelectionReductionOpportunity::PreconditionHolds() { return true; }
+
+void RemoveSelectionReductionOpportunity::Apply() {
+ auto merge_instruction = header_block_->GetMergeInst();
+ merge_instruction->context()->KillInst(merge_instruction);
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/remove_selection_reduction_opportunity.h b/source/reduce/remove_selection_reduction_opportunity.h
new file mode 100644
index 0000000..892618e
--- /dev/null
+++ b/source/reduce/remove_selection_reduction_opportunity.h
@@ -0,0 +1,47 @@
+// Copyright (c) 2019 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_SELECTION_REDUCTION_OPPORTUNITY_H_
+#define SOURCE_REDUCE_REMOVE_SELECTION_REDUCTION_OPPORTUNITY_H_
+
+#include "source/opt/basic_block.h"
+#include "source/reduce/reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+// An opportunity for removing a selection construct by simply removing the
+// OpSelectionMerge instruction; thus, the selection must have already been
+// simplified to a point where the instruction can be trivially removed.
+class RemoveSelectionReductionOpportunity : public ReductionOpportunity {
+ public:
+ // Constructs a reduction opportunity from the selection header |block| in
+ // |function|.
+ RemoveSelectionReductionOpportunity(opt::BasicBlock* header_block)
+ : header_block_(header_block) {}
+
+ bool PreconditionHolds() override;
+
+ protected:
+ void Apply() override;
+
+ private:
+ // The header block of the selection.
+ opt::BasicBlock* header_block_;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REMOVE_SELECTION_REDUCTION_OPPORTUNITY_H_
diff --git a/source/reduce/remove_selection_reduction_opportunity_finder.cpp b/source/reduce/remove_selection_reduction_opportunity_finder.cpp
new file mode 100644
index 0000000..d2994c2
--- /dev/null
+++ b/source/reduce/remove_selection_reduction_opportunity_finder.cpp
@@ -0,0 +1,148 @@
+// Copyright (c) 2019 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/remove_selection_reduction_opportunity_finder.h"
+
+#include "source/reduce/remove_selection_reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+using namespace opt;
+
+namespace {
+const uint32_t kMergeNodeIndex = 0;
+const uint32_t kContinueNodeIndex = 1;
+} // namespace
+
+std::string RemoveSelectionReductionOpportunityFinder::GetName() const {
+ return "RemoveSelectionReductionOpportunityFinder";
+}
+
+std::vector<std::unique_ptr<ReductionOpportunity>>
+RemoveSelectionReductionOpportunityFinder::GetAvailableOpportunities(
+ opt::IRContext* context) const {
+ // Get all loop merge and continue blocks so we can check for these later.
+ std::unordered_set<uint32_t> merge_and_continue_blocks_from_loops;
+ for (auto& function : *context->module()) {
+ for (auto& block : function) {
+ if (auto merge_instruction = block.GetMergeInst()) {
+ if (merge_instruction->opcode() == SpvOpLoopMerge) {
+ uint32_t merge_block_id =
+ merge_instruction->GetSingleWordOperand(kMergeNodeIndex);
+ uint32_t continue_block_id =
+ merge_instruction->GetSingleWordOperand(kContinueNodeIndex);
+ merge_and_continue_blocks_from_loops.insert(merge_block_id);
+ merge_and_continue_blocks_from_loops.insert(continue_block_id);
+ }
+ }
+ }
+ }
+
+ // Return all selection headers where the OpSelectionMergeInstruction can be
+ // removed.
+ std::vector<std::unique_ptr<ReductionOpportunity>> result;
+ for (auto& function : *context->module()) {
+ for (auto& block : function) {
+ if (auto merge_instruction = block.GetMergeInst()) {
+ if (merge_instruction->opcode() == SpvOpSelectionMerge) {
+ if (CanOpSelectionMergeBeRemoved(
+ context, block, merge_instruction,
+ merge_and_continue_blocks_from_loops)) {
+ result.push_back(
+ MakeUnique<RemoveSelectionReductionOpportunity>(&block));
+ }
+ }
+ }
+ }
+ }
+ return result;
+}
+
+bool RemoveSelectionReductionOpportunityFinder::CanOpSelectionMergeBeRemoved(
+ opt::IRContext* context, const opt::BasicBlock& header_block,
+ opt::Instruction* merge_instruction,
+ std::unordered_set<uint32_t> merge_and_continue_blocks_from_loops) {
+ assert(header_block.GetMergeInst() == merge_instruction &&
+ "CanOpSelectionMergeBeRemoved(...): header block and merge "
+ "instruction mismatch");
+
+ // The OpSelectionMerge instruction is needed if either of the following are
+ // true.
+ //
+ // 1. The header block has at least two (unique) successors that are not
+ // merge or continue blocks of a loop.
+ //
+ // 2. The predecessors of the merge block are "using" the merge block to avoid
+ // divergence. In other words, there exists a predecessor of the merge block
+ // that has a successor that is not the merge block of this construct and not
+ // a merge or continue block of a loop.
+
+ // 1.
+ {
+ uint32_t divergent_successor_count = 0;
+
+ std::unordered_set<uint32_t> seen_successors;
+
+ header_block.ForEachSuccessorLabel(
+ [&seen_successors, &merge_and_continue_blocks_from_loops,
+ &divergent_successor_count](uint32_t successor) {
+ // Not already seen.
+ if (seen_successors.find(successor) == seen_successors.end()) {
+ seen_successors.insert(successor);
+ // Not a loop continue or merge.
+ if (merge_and_continue_blocks_from_loops.find(successor) ==
+ merge_and_continue_blocks_from_loops.end()) {
+ ++divergent_successor_count;
+ }
+ }
+ });
+
+ if (divergent_successor_count > 1) {
+ return false;
+ }
+ }
+
+ // 2.
+ {
+ uint32_t merge_block_id =
+ merge_instruction->GetSingleWordOperand(kMergeNodeIndex);
+ for (uint32_t predecessor_block_id :
+ context->cfg()->preds(merge_block_id)) {
+ const BasicBlock* predecessor_block =
+ context->cfg()->block(predecessor_block_id);
+ assert(predecessor_block);
+ bool found_divergent_successor = false;
+ predecessor_block->ForEachSuccessorLabel(
+ [&found_divergent_successor, merge_block_id,
+ &merge_and_continue_blocks_from_loops](uint32_t successor_id) {
+ // The successor is not the merge block, nor a loop merge or
+ // continue.
+ if (successor_id != merge_block_id &&
+ merge_and_continue_blocks_from_loops.find(successor_id) ==
+ merge_and_continue_blocks_from_loops.end()) {
+ found_divergent_successor = true;
+ }
+ });
+ if (found_divergent_successor) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/remove_selection_reduction_opportunity_finder.h b/source/reduce/remove_selection_reduction_opportunity_finder.h
new file mode 100644
index 0000000..848122b
--- /dev/null
+++ b/source/reduce/remove_selection_reduction_opportunity_finder.h
@@ -0,0 +1,49 @@
+// Copyright (c) 2019 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_SELECTION_REDUCTION_OPPORTUNITY_FINDER_H_
+#define SOURCE_REDUCE_REMOVE_SELECTION_REDUCTION_OPPORTUNITY_FINDER_H_
+
+#include "source/reduce/reduction_opportunity_finder.h"
+
+namespace spvtools {
+namespace reduce {
+
+// A finder for opportunities for removing a selection construct by simply
+// removing the OpSelectionMerge instruction; thus, the selections must have
+// already been simplified to a point where they can be trivially removed.
+class RemoveSelectionReductionOpportunityFinder
+ : public ReductionOpportunityFinder {
+ public:
+ RemoveSelectionReductionOpportunityFinder() = default;
+
+ ~RemoveSelectionReductionOpportunityFinder() override = default;
+
+ std::string GetName() const final;
+
+ std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
+ opt::IRContext* context) const final;
+
+ // Returns true if the OpSelectionMerge instruction |merge_instruction| in
+ // block |header_block| can be removed.
+ static bool CanOpSelectionMergeBeRemoved(
+ opt::IRContext* context, const opt::BasicBlock& header_block,
+ opt::Instruction* merge_instruction,
+ std::unordered_set<uint32_t> merge_and_continue_blocks_from_loops);
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REMOVE_SELECTION_REDUCTION_OPPORTUNITY_FINDER_H_
diff --git a/test/reduce/CMakeLists.txt b/test/reduce/CMakeLists.txt
index 4acab56..ce8c003 100644
--- a/test/reduce/CMakeLists.txt
+++ b/test/reduce/CMakeLists.txt
@@ -23,6 +23,7 @@
remove_block_test.cpp
remove_function_test.cpp
remove_opname_instruction_test.cpp
+ remove_selection_test.cpp
remove_unreferenced_instruction_test.cpp
structured_loop_to_selection_test.cpp
validation_during_reduction_test.cpp
diff --git a/test/reduce/remove_selection_test.cpp b/test/reduce/remove_selection_test.cpp
new file mode 100644
index 0000000..40ac028
--- /dev/null
+++ b/test/reduce/remove_selection_test.cpp
@@ -0,0 +1,557 @@
+// Copyright (c) 2019 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/build_module.h"
+#include "source/reduce/reduction_opportunity.h"
+#include "source/reduce/reduction_pass.h"
+#include "source/reduce/remove_selection_reduction_opportunity_finder.h"
+#include "test/reduce/reduce_test_util.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+TEST(RemoveSelectionTest, OpportunityBecauseSameTargetBlock) {
+ // A test with the following structure. The OpSelectionMerge instruction
+ // should be removed.
+ //
+ // header
+ // ||
+ // block
+ // |
+ // merge
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %11 %11
+ %11 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+
+ auto ops =
+ RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+
+ ASSERT_EQ(1, ops.size());
+
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ CheckValid(env, context.get());
+
+ std::string after = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpBranchConditional %8 %11 %11
+ %11 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ CheckEqual(env, after, context.get());
+
+ ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+TEST(RemoveSelectionTest, OpportunityBecauseSameTargetBlockMerge) {
+ // A test with the following structure. The OpSelectionMerge instruction
+ // should be removed.
+ //
+ // header
+ // ||
+ // merge
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %10 %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+
+ auto ops =
+ RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+
+ ASSERT_EQ(1, ops.size());
+
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ CheckValid(env, context.get());
+
+ std::string after = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpBranchConditional %8 %10 %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ CheckEqual(env, after, context.get());
+
+ ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+TEST(RemoveSelectionTest, NoOpportunityBecauseDifferentTargetBlocksOneMerge) {
+ // A test with the following structure. The OpSelectionMerge instruction
+ // should NOT be removed.
+ //
+ // header
+ // | |
+ // | block
+ // | |
+ // merge
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %10 %11
+ %11 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+
+ auto ops =
+ RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+TEST(RemoveSelectionTest, NoOpportunityBecauseDifferentTargetBlocks) {
+ // A test with the following structure. The OpSelectionMerge instruction
+ // should NOT be removed.
+ //
+ // header
+ // | |
+ // b b
+ // | |
+ // merge
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %11 %12
+ %11 = OpLabel
+ OpBranch %10
+ %12 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+
+ auto ops =
+ RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+TEST(RemoveSelectionTest, NoOpportunityBecauseMergeUsed) {
+ // A test with the following structure. The OpSelectionMerge instruction
+ // should NOT be removed.
+ //
+ // header
+ // ||
+ // block
+ // | |
+ // | block
+ // | |
+ // merge
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %11 %12
+ %11 = OpLabel
+ OpBranchConditional %8 %10 %12
+ %12 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+
+ auto ops =
+ RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+TEST(RemoveSelectionTest, OpportunityBecauseLoopMergeUsed) {
+ // A test with the following structure. The OpSelectionMerge instruction
+ // should be removed.
+ //
+ // loop header
+ // |
+ // |
+ // s.header
+ // ||
+ // block
+ // | |
+ // | |
+ // | | ^ (to loop header)
+ // s.merge | |
+ // | / loop continue target (unreachable)
+ // loop merge
+ //
+ //
+ // which becomes:
+ //
+ // loop header
+ // |
+ // |
+ // block
+ // ||
+ // block
+ // | |
+ // | |
+ // | | ^ (to loop header)
+ // block | |
+ // | / loop continue target (unreachable)
+ // loop merge
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpLoopMerge %11 %12 None
+ OpBranch %13
+ %13 = OpLabel
+ OpSelectionMerge %14 None
+ OpBranchConditional %8 %15 %15
+ %15 = OpLabel
+ OpBranchConditional %8 %14 %11
+ %14 = OpLabel
+ OpBranch %11
+ %12 = OpLabel
+ OpBranch %10
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+
+ CheckValid(env, context.get());
+
+ auto ops =
+ RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+
+ ASSERT_EQ(1, ops.size());
+
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ CheckValid(env, context.get());
+
+ std::string after = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpLoopMerge %11 %12 None
+ OpBranch %13
+ %13 = OpLabel
+ OpBranchConditional %8 %15 %15
+ %15 = OpLabel
+ OpBranchConditional %8 %14 %11
+ %14 = OpLabel
+ OpBranch %11
+ %12 = OpLabel
+ OpBranch %10
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ CheckEqual(env, after, context.get());
+
+ ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+TEST(RemoveSelectionTest, OpportunityBecauseLoopContinueUsed) {
+ // A test with the following structure. The OpSelectionMerge instruction
+ // should be removed.
+ //
+ // loop header
+ // |
+ // |
+ // s.header
+ // ||
+ // block
+ // | |
+ // | |
+ // | | ^ (to loop header)
+ // s.merge | |
+ // | loop continue target
+ // loop merge
+ //
+ //
+ // which becomes:
+ //
+ // loop header
+ // |
+ // |
+ // block
+ // ||
+ // block
+ // | |
+ // | |
+ // | | ^ (to loop header)
+ // block | |
+ // | loop continue target
+ // loop merge
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpLoopMerge %11 %12 None
+ OpBranch %13
+ %13 = OpLabel
+ OpSelectionMerge %14 None
+ OpBranchConditional %8 %15 %15
+ %15 = OpLabel
+ OpBranchConditional %8 %14 %12
+ %14 = OpLabel
+ OpBranch %11
+ %12 = OpLabel
+ OpBranch %10
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+
+ CheckValid(env, context.get());
+
+ auto ops =
+ RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+
+ ASSERT_EQ(1, ops.size());
+
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ CheckValid(env, context.get());
+
+ std::string after = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeInt 32 1
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpLoopMerge %11 %12 None
+ OpBranch %13
+ %13 = OpLabel
+ OpBranchConditional %8 %15 %15
+ %15 = OpLabel
+ OpBranchConditional %8 %14 %12
+ %14 = OpLabel
+ OpBranch %11
+ %12 = OpLabel
+ OpBranch %10
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ CheckEqual(env, after, context.get());
+
+ ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
+ context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+} // namespace
+} // namespace reduce
+} // namespace spvtools
