spirv-reduce: Eliminate skeletal structured control flow construct (#4360)
This change allows spriv-reduce to get rid of a selection, switch or
loop construct if none of the instructions defined in the construct
are used outside the construct.
diff --git a/BUILD.gn b/BUILD.gn
index 9587f6a..996905a 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -803,6 +803,10 @@
"source/reduce/simple_conditional_branch_to_branch_opportunity_finder.h",
"source/reduce/simple_conditional_branch_to_branch_reduction_opportunity.cpp",
"source/reduce/simple_conditional_branch_to_branch_reduction_opportunity.h",
+ "source/reduce/structured_construct_to_block_reduction_opportunity.cpp",
+ "source/reduce/structured_construct_to_block_reduction_opportunity.h",
+ "source/reduce/structured_construct_to_block_reduction_opportunity_finder.cpp",
+ "source/reduce/structured_construct_to_block_reduction_opportunity_finder.h",
"source/reduce/structured_loop_to_selection_reduction_opportunity.cpp",
"source/reduce/structured_loop_to_selection_reduction_opportunity.h",
"source/reduce/structured_loop_to_selection_reduction_opportunity_finder.cpp",
diff --git a/source/reduce/CMakeLists.txt b/source/reduce/CMakeLists.txt
index 3043243..6fd8409 100644
--- a/source/reduce/CMakeLists.txt
+++ b/source/reduce/CMakeLists.txt
@@ -38,6 +38,8 @@
remove_unused_struct_member_reduction_opportunity_finder.h
simple_conditional_branch_to_branch_opportunity_finder.h
simple_conditional_branch_to_branch_reduction_opportunity.h
+ structured_construct_to_block_reduction_opportunity.h
+ structured_construct_to_block_reduction_opportunity_finder.h
structured_loop_to_selection_reduction_opportunity.h
structured_loop_to_selection_reduction_opportunity_finder.h
@@ -67,6 +69,8 @@
remove_unused_struct_member_reduction_opportunity_finder.cpp
simple_conditional_branch_to_branch_opportunity_finder.cpp
simple_conditional_branch_to_branch_reduction_opportunity.cpp
+ structured_construct_to_block_reduction_opportunity.cpp
+ structured_construct_to_block_reduction_opportunity_finder.cpp
structured_loop_to_selection_reduction_opportunity.cpp
structured_loop_to_selection_reduction_opportunity_finder.cpp
)
diff --git a/source/reduce/reducer.cpp b/source/reduce/reducer.cpp
index 16bb94f..b752f41 100644
--- a/source/reduce/reducer.cpp
+++ b/source/reduce/reducer.cpp
@@ -28,6 +28,7 @@
#include "source/reduce/remove_unused_instruction_reduction_opportunity_finder.h"
#include "source/reduce/remove_unused_struct_member_reduction_opportunity_finder.h"
#include "source/reduce/simple_conditional_branch_to_branch_opportunity_finder.h"
+#include "source/reduce/structured_construct_to_block_reduction_opportunity_finder.h"
#include "source/reduce/structured_loop_to_selection_reduction_opportunity_finder.h"
#include "source/spirv_reducer_options.h"
@@ -113,6 +114,8 @@
AddReductionPass(
spvtools::MakeUnique<OperandToDominatingIdReductionOpportunityFinder>());
AddReductionPass(spvtools::MakeUnique<
+ StructuredConstructToBlockReductionOpportunityFinder>());
+ AddReductionPass(spvtools::MakeUnique<
StructuredLoopToSelectionReductionOpportunityFinder>());
AddReductionPass(
spvtools::MakeUnique<MergeBlocksReductionOpportunityFinder>());
@@ -141,7 +144,7 @@
std::unique_ptr<ReductionOpportunityFinder> finder) {
passes_.push_back(
spvtools::MakeUnique<ReductionPass>(target_env_, std::move(finder)));
-}
+}
void Reducer::AddCleanupReductionPass(
std::unique_ptr<ReductionOpportunityFinder> finder) {
diff --git a/source/reduce/structured_construct_to_block_reduction_opportunity.cpp b/source/reduce/structured_construct_to_block_reduction_opportunity.cpp
new file mode 100644
index 0000000..ed73841
--- /dev/null
+++ b/source/reduce/structured_construct_to_block_reduction_opportunity.cpp
@@ -0,0 +1,67 @@
+// Copyright (c) 2021 Alastair F. Donaldson
+//
+// 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/structured_construct_to_block_reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+bool StructuredConstructToBlockReductionOpportunity::PreconditionHolds() {
+ return context_->get_def_use_mgr()->GetDef(construct_header_) != nullptr;
+}
+
+void StructuredConstructToBlockReductionOpportunity::Apply() {
+ auto header_block = context_->cfg()->block(construct_header_);
+ auto merge_block = context_->cfg()->block(header_block->MergeBlockId());
+
+ auto* enclosing_function = header_block->GetParent();
+
+ // A region of blocks is defined in terms of dominators and post-dominators,
+ // so we compute these for the enclosing function.
+ auto* dominators = context_->GetDominatorAnalysis(enclosing_function);
+ auto* postdominators = context_->GetPostDominatorAnalysis(enclosing_function);
+
+ // For each block in the function, determine whether it is inside the region.
+ // If it is, delete it.
+ for (auto block_it = enclosing_function->begin();
+ block_it != enclosing_function->end();) {
+ if (header_block != &*block_it && merge_block != &*block_it &&
+ dominators->Dominates(header_block, &*block_it) &&
+ postdominators->Dominates(merge_block, &*block_it)) {
+ block_it = block_it.Erase();
+ } else {
+ ++block_it;
+ }
+ }
+ // Having removed some blocks from the module it is necessary to invalidate
+ // analyses, since the remaining patch-up work depends on various analyses
+ // which will otherwise reference blocks that have been deleted.
+ context_->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+
+ // We demote the header of the region to a regular block by deleting its merge
+ // instruction.
+ context_->KillInst(header_block->GetMergeInst());
+
+ // The terminator for the header block is changed to be an unconditional
+ // branch to the merge block.
+ header_block->terminator()->SetOpcode(SpvOpBranch);
+ header_block->terminator()->SetInOperands(
+ {{SPV_OPERAND_TYPE_ID, {merge_block->id()}}});
+
+ // This is an intrusive change, so we invalidate all analyses.
+ context_->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/structured_construct_to_block_reduction_opportunity.h b/source/reduce/structured_construct_to_block_reduction_opportunity.h
new file mode 100644
index 0000000..f461a2f
--- /dev/null
+++ b/source/reduce/structured_construct_to_block_reduction_opportunity.h
@@ -0,0 +1,49 @@
+// Copyright (c) 2021 Alastair F. Donaldson
+//
+// 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_STRUCTURED_CONSTRUCT_TO_BLOCK_REDUCTION_OPPORTUNITY_H_
+#define SOURCE_REDUCE_STRUCTURED_CONSTRUCT_TO_BLOCK_REDUCTION_OPPORTUNITY_H_
+
+#include "source/opt/ir_context.h"
+#include "source/reduce/reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+// An opportunity to replace a skeletal structured control flow construct with a
+// single block.
+class StructuredConstructToBlockReductionOpportunity
+ : public ReductionOpportunity {
+ public:
+ // Constructs an opportunity from a header block id.
+ StructuredConstructToBlockReductionOpportunity(opt::IRContext* context,
+ uint32_t construct_header)
+ : context_(context), construct_header_(construct_header) {}
+
+ // Returns true if and only if |construct_header_| exists in the module -
+ // another opportunity may have removed it.
+ bool PreconditionHolds() override;
+
+ protected:
+ void Apply() override;
+
+ private:
+ opt::IRContext* context_;
+ uint32_t construct_header_;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_STRUCTURED_CONSTRUCT_TO_BLOCK_REDUCTION_OPPORTUNITY_H_
diff --git a/source/reduce/structured_construct_to_block_reduction_opportunity_finder.cpp b/source/reduce/structured_construct_to_block_reduction_opportunity_finder.cpp
new file mode 100644
index 0000000..dc20f68
--- /dev/null
+++ b/source/reduce/structured_construct_to_block_reduction_opportunity_finder.cpp
@@ -0,0 +1,185 @@
+// Copyright (c) 2021 Alastair F. Donaldson
+//
+// 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/structured_construct_to_block_reduction_opportunity_finder.h"
+
+#include <unordered_set>
+
+#include "source/reduce/structured_construct_to_block_reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+std::vector<std::unique_ptr<ReductionOpportunity>>
+StructuredConstructToBlockReductionOpportunityFinder::GetAvailableOpportunities(
+ opt::IRContext* context, uint32_t target_function) const {
+ std::vector<std::unique_ptr<ReductionOpportunity>> result;
+
+ // Consider every function in the module.
+ for (auto* function : GetTargetFunctions(context, target_function)) {
+ // For every header block in the function, there is potentially a region of
+ // blocks that could be collapsed.
+ std::unordered_map<opt::BasicBlock*, std::unordered_set<opt::BasicBlock*>>
+ regions;
+
+ // Regions are identified using dominators and postdominators, so we compute
+ // those for the function.
+ auto* dominators = context->GetDominatorAnalysis(function);
+ auto* postdominators = context->GetPostDominatorAnalysis(function);
+
+ // Consider every block in the function.
+ for (auto& block : *function) {
+ // If a block has an unreachable predecessor then folding away a region in
+ // which that block is contained gets complicated, so we ignore regions
+ // that contain such blocks. We note whether this block suffers from this
+ // problem.
+ bool has_unreachable_predecessor =
+ HasUnreachablePredecessor(block, context);
+
+ // Look through all the regions we have identified so far to see whether
+ // this block is part of a region, or spoils a region (by having an
+ // unreachable predecessor).
+ for (auto entry = regions.begin(); entry != regions.end();) {
+ // |block| is in this region if it is dominated by the header,
+ // post-dominated by the merge, and different from the merge.
+ assert(&block != entry->first &&
+ "The block should not be the region's header because we only "
+ "make a region when we encounter its header.");
+ if (entry->first->MergeBlockId() != block.id() &&
+ dominators->Dominates(entry->first, &block) &&
+ postdominators->Dominates(
+ entry->first->GetMergeInst()->GetSingleWordInOperand(0),
+ block.id())) {
+ if (has_unreachable_predecessor) {
+ // The block would be in this region, but it has an unreachable
+ // predecessor. This spoils the region, so we remove it.
+ entry = regions.erase(entry);
+ continue;
+ } else {
+ // Add the block to the region.
+ entry->second.insert(&block);
+ }
+ }
+ ++entry;
+ }
+ if (block.MergeBlockIdIfAny() == 0) {
+ // The block isn't a header, so it doesn't constitute a new region.
+ continue;
+ }
+ if (!context->IsReachable(block)) {
+ // The block isn't reachable, so it doesn't constitute a new region.
+ continue;
+ }
+ auto* merge_block = context->cfg()->block(
+ block.GetMergeInst()->GetSingleWordInOperand(0));
+ if (!context->IsReachable(*merge_block)) {
+ // The block's merge is unreachable, so it doesn't constitute a new
+ // region.
+ continue;
+ }
+ assert(dominators->Dominates(&block, merge_block) &&
+ "The merge block is reachable, so the header must dominate it");
+ if (!postdominators->Dominates(merge_block, &block)) {
+ // The block is not post-dominated by its merge. This happens for
+ // instance when there is a break from a conditional, or an early exit.
+ // This also means that we don't add a region.
+ continue;
+ }
+ // We have a reachable header block with a rechable merge that
+ // postdominates the header: this means we have a new region.
+ regions.emplace(&block, std::unordered_set<opt::BasicBlock*>());
+ }
+
+ // Now that we have found all the regions and blocks within them, we check
+ // whether any region defines an id that is used outside the region. If this
+ // is *not* the case, then we have an opportunity to collapse the region
+ // down to its header block and merge block.
+ for (auto& entry : regions) {
+ if (DefinitionsRestrictedToRegion(*entry.first, entry.second, context)) {
+ result.emplace_back(
+ MakeUnique<StructuredConstructToBlockReductionOpportunity>(
+ context, entry.first->id()));
+ }
+ }
+ }
+ return result;
+}
+
+bool StructuredConstructToBlockReductionOpportunityFinder::
+ DefinitionsRestrictedToRegion(
+ const opt::BasicBlock& header,
+ const std::unordered_set<opt::BasicBlock*>& region,
+ opt::IRContext* context) {
+ // Consider every block in the region.
+ for (auto& block : region) {
+ // Consider every instruction in the block - this includes the label
+ // instruction
+ if (!block->WhileEachInst(
+ [context, &header, ®ion](opt::Instruction* inst) -> bool {
+ if (inst->result_id() == 0) {
+ // The instruction does not genreate a result id, thus it cannot
+ // be referred to outside the region - this is fine.
+ return true;
+ }
+ // Consider every use of the instruction's result id.
+ if (!context->get_def_use_mgr()->WhileEachUse(
+ inst->result_id(),
+ [context, &header, ®ion](opt::Instruction* user,
+ uint32_t) -> bool {
+ auto user_block = context->get_instr_block(user);
+ if (user == header.GetMergeInst() ||
+ user == header.terminator()) {
+ // We are going to delete the header's merge
+ // instruction and rewrite its terminator, so it does
+ // not matter if the user is one of these
+ // instructions.
+ return true;
+ }
+ if (user_block == nullptr ||
+ region.count(user_block) == 0) {
+ // The user is either a global instruction, or an
+ // instruction in a block outside the region. Removing
+ // the region would invalidate this user.
+ return false;
+ }
+ return true;
+ })) {
+ return false;
+ }
+ return true;
+ })) {
+ return false;
+ }
+ }
+ return true;
+}
+
+bool StructuredConstructToBlockReductionOpportunityFinder::
+ HasUnreachablePredecessor(const opt::BasicBlock& block,
+ opt::IRContext* context) {
+ for (auto pred : context->cfg()->preds(block.id())) {
+ if (!context->IsReachable(*context->cfg()->block(pred))) {
+ return true;
+ }
+ }
+ return false;
+}
+
+std::string StructuredConstructToBlockReductionOpportunityFinder::GetName()
+ const {
+ return "StructuredConstructToBlockReductionOpportunityFinder";
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/structured_construct_to_block_reduction_opportunity_finder.h b/source/reduce/structured_construct_to_block_reduction_opportunity_finder.h
new file mode 100644
index 0000000..28bbc17
--- /dev/null
+++ b/source/reduce/structured_construct_to_block_reduction_opportunity_finder.h
@@ -0,0 +1,57 @@
+// Copyright (c) 2021 Alastair F. Donaldson
+//
+// 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_STRUCTURED_CONSTRUCT_TO_BLOCK_REDUCTION_OPPORTUNITY_FINDER_H
+#define SOURCE_REDUCE_STRUCTURED_CONSTRUCT_TO_BLOCK_REDUCTION_OPPORTUNITY_FINDER_H
+
+#include "source/reduce/reduction_opportunity_finder.h"
+
+namespace spvtools {
+namespace reduce {
+
+// A finder for opportunities to replace a skeletal structured control flow
+// construct - that is, a construct that does not define anything that's used
+// outside the construct - into its header block.
+class StructuredConstructToBlockReductionOpportunityFinder
+ : public ReductionOpportunityFinder {
+ public:
+ StructuredConstructToBlockReductionOpportunityFinder() = default;
+
+ ~StructuredConstructToBlockReductionOpportunityFinder() override = default;
+
+ std::string GetName() const final;
+
+ std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
+ opt::IRContext* context, uint32_t target_function) const final;
+
+ private:
+ // Returns true if and only if all instructions defined in |region| are used
+ // only inside |region|, with the exception that they may be used by the merge
+ // or terminator instruction of |header|, which must be the header block for
+ // the region.
+ static bool DefinitionsRestrictedToRegion(
+ const opt::BasicBlock& header,
+ const std::unordered_set<opt::BasicBlock*>& region,
+ opt::IRContext* context);
+
+ // Returns true if and only if |block| has at least one predecessor that is
+ // unreachable in the control flow graph of its function.
+ static bool HasUnreachablePredecessor(const opt::BasicBlock& block,
+ opt::IRContext* context);
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_STRUCTURED_CONSTRUCT_TO_BLOCK_REDUCTION_OPPORTUNITY_FINDER_H
diff --git a/test/reduce/CMakeLists.txt b/test/reduce/CMakeLists.txt
index 652f0ab..121cd4f 100644
--- a/test/reduce/CMakeLists.txt
+++ b/test/reduce/CMakeLists.txt
@@ -14,6 +14,7 @@
add_spvtools_unittest(TARGET reduce
SRCS
+ conditional_branch_to_simple_conditional_branch_test.cpp
merge_blocks_test.cpp
operand_to_constant_test.cpp
operand_to_undef_test.cpp
@@ -26,10 +27,10 @@
remove_selection_test.cpp
remove_unused_instruction_test.cpp
remove_unused_struct_member_test.cpp
+ simple_conditional_branch_to_branch_test.cpp
+ structured_construct_to_block_test.cpp
structured_loop_to_selection_test.cpp
validation_during_reduction_test.cpp
- conditional_branch_to_simple_conditional_branch_test.cpp
- simple_conditional_branch_to_branch_test.cpp
LIBS SPIRV-Tools-reduce
)
diff --git a/test/reduce/reduce_test_util.cpp b/test/reduce/reduce_test_util.cpp
index 0c23411..4271660 100644
--- a/test/reduce/reduce_test_util.cpp
+++ b/test/reduce/reduce_test_util.cpp
@@ -21,6 +21,29 @@
namespace spvtools {
namespace reduce {
+const spvtools::MessageConsumer kConsoleMessageConsumer =
+ [](spv_message_level_t level, const char*, const spv_position_t& position,
+ const char* message) -> void {
+ switch (level) {
+ case SPV_MSG_FATAL:
+ case SPV_MSG_INTERNAL_ERROR:
+ case SPV_MSG_ERROR:
+ std::cerr << "error: line " << position.index << ": " << message
+ << std::endl;
+ break;
+ case SPV_MSG_WARNING:
+ std::cout << "warning: line " << position.index << ": " << message
+ << std::endl;
+ break;
+ case SPV_MSG_INFO:
+ std::cout << "info: line " << position.index << ": " << message
+ << std::endl;
+ break;
+ default:
+ break;
+ }
+};
+
void CheckEqual(const spv_target_env env,
const std::vector<uint32_t>& expected_binary,
const std::vector<uint32_t>& actual_binary) {
@@ -55,8 +78,9 @@
void CheckValid(spv_target_env env, const opt::IRContext* ir) {
std::vector<uint32_t> binary;
ir->module()->ToBinary(&binary, false);
- SpirvTools t(env);
- ASSERT_TRUE(t.Validate(binary));
+ SpirvTools tools(env);
+ tools.SetMessageConsumer(kConsoleMessageConsumer);
+ ASSERT_TRUE(tools.Validate(binary));
}
std::string ToString(spv_target_env env, const opt::IRContext* ir) {
diff --git a/test/reduce/structured_construct_to_block_test.cpp b/test/reduce/structured_construct_to_block_test.cpp
new file mode 100644
index 0000000..9500966
--- /dev/null
+++ b/test/reduce/structured_construct_to_block_test.cpp
@@ -0,0 +1,245 @@
+// Copyright (c) 2021 Alastair F. Donaldson
+//
+// 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/structured_construct_to_block_reduction_opportunity_finder.h"
+
+#include "source/opt/build_module.h"
+#include "source/reduce/reduction_opportunity.h"
+#include "test/reduce/reduce_test_util.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+TEST(StructuredConstructToBlockReductionPassTest, SimpleTest) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 0
+ %10 = OpTypeBool
+ %11 = OpConstantTrue %10
+ %19 = OpConstant %6 3
+ %29 = OpConstant %6 1
+ %31 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpStore %8 %9
+ OpSelectionMerge %13 None
+ OpBranchConditional %11 %12 %13
+ %12 = OpLabel
+ OpBranch %13
+ %13 = OpLabel
+ OpBranch %14
+ %14 = OpLabel
+ OpLoopMerge %16 %17 None
+ OpBranch %15
+ %15 = OpLabel
+ %18 = OpLoad %6 %8
+ %20 = OpSGreaterThan %10 %18 %19
+ OpSelectionMerge %22 None
+ OpBranchConditional %20 %21 %22
+ %21 = OpLabel
+ OpBranch %16
+ %22 = OpLabel
+ OpBranch %17
+ %17 = OpLabel
+ OpBranch %14
+ %16 = OpLabel
+ %24 = OpLoad %6 %8
+ OpSelectionMerge %28 None
+ OpSwitch %24 %27 1 %25 2 %26
+ %27 = OpLabel
+ OpStore %8 %19
+ OpBranch %28
+ %25 = OpLabel
+ OpStore %8 %29
+ OpBranch %28
+ %26 = OpLabel
+ OpStore %8 %31
+ OpBranch %28
+ %28 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+ const auto ops = StructuredConstructToBlockReductionOpportunityFinder()
+ .GetAvailableOpportunities(context.get(), 0);
+ ASSERT_EQ(3, ops.size());
+
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ CheckValid(env, context.get());
+
+ ASSERT_TRUE(ops[1]->PreconditionHolds());
+ ops[1]->TryToApply();
+ CheckValid(env, context.get());
+
+ ASSERT_TRUE(ops[2]->PreconditionHolds());
+ ops[2]->TryToApply();
+ CheckValid(env, context.get());
+
+ std::string expected = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 0
+ %10 = OpTypeBool
+ %11 = OpConstantTrue %10
+ %19 = OpConstant %6 3
+ %29 = OpConstant %6 1
+ %31 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpStore %8 %9
+ OpBranch %13
+ %13 = OpLabel
+ OpBranch %14
+ %14 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ %24 = OpLoad %6 %8
+ OpBranch %28
+ %28 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ CheckEqual(env, expected, context.get());
+}
+
+TEST(StructuredConstructToBlockReductionPassTest, CannotBeRemovedDueToUses) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ OpName %100 "temp"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 0
+ %10 = OpTypeBool
+ %11 = OpConstantTrue %10
+ %19 = OpConstant %6 3
+ %29 = OpConstant %6 1
+ %31 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpStore %8 %9
+ OpSelectionMerge %13 None
+ OpBranchConditional %11 %12 %13
+ %12 = OpLabel
+ %100 = OpCopyObject %10 %11
+ OpBranch %13
+ %13 = OpLabel
+ OpBranch %14
+ %14 = OpLabel
+ OpLoopMerge %16 %17 None
+ OpBranch %15
+ %15 = OpLabel
+ %18 = OpLoad %6 %8
+ %20 = OpSGreaterThan %10 %18 %19
+ OpSelectionMerge %22 None
+ OpBranchConditional %20 %21 %22
+ %21 = OpLabel
+ OpBranch %16
+ %22 = OpLabel
+ OpBranch %17
+ %17 = OpLabel
+ OpBranch %14
+ %16 = OpLabel
+ %101 = OpCopyObject %6 %18
+ %24 = OpLoad %6 %8
+ OpSelectionMerge %28 None
+ OpSwitch %24 %27 1 %25 2 %26
+ %27 = OpLabel
+ OpStore %8 %19
+ %102 = OpCopyObject %10 %11
+ OpBranch %28
+ %25 = OpLabel
+ OpStore %8 %29
+ OpBranch %28
+ %26 = OpLabel
+ OpStore %8 %31
+ OpBranch %28
+ %28 = OpLabel
+ %103 = OpPhi %10 %102 %27 %11 %25 %11 %26
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+ const auto ops = StructuredConstructToBlockReductionOpportunityFinder()
+ .GetAvailableOpportunities(context.get(), 0);
+ ASSERT_TRUE(ops.empty());
+}
+
+TEST(StructuredConstructToBlockReductionPassTest,
+ CannotBeRemovedDueToOpPhiAtMerge) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %10 = OpTypeBool
+ %11 = OpConstantTrue %10
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %13 None
+ OpBranchConditional %11 %12 %13
+ %12 = OpLabel
+ OpBranch %13
+ %13 = OpLabel
+ %101 = OpPhi %10 %11 %5 %11 %12
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
+ const auto ops = StructuredConstructToBlockReductionOpportunityFinder()
+ .GetAvailableOpportunities(context.get(), 0);
+ ASSERT_TRUE(ops.empty());
+}
+
+} // namespace
+} // namespace reduce
+} // namespace spvtools
