Sink (#2284)
Add code sinking pass. It will move OpLoad and OpAccessChain instructions as close as possible to their uses.
Part of #1611.
diff --git a/Android.mk b/Android.mk
index 8597c50..179cf26 100644
--- a/Android.mk
+++ b/Android.mk
@@ -80,6 +80,7 @@
source/opt/cfg.cpp \
source/opt/cfg_cleanup_pass.cpp \
source/opt/ccp_pass.cpp \
+ source/opt/code_sink.cpp \
source/opt/combine_access_chains.cpp \
source/opt/common_uniform_elim_pass.cpp \
source/opt/compact_ids_pass.cpp \
diff --git a/BUILD.gn b/BUILD.gn
index 5f0eba9..69e3dc8 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -460,6 +460,8 @@
"source/opt/cfg.h",
"source/opt/cfg_cleanup_pass.cpp",
"source/opt/cfg_cleanup_pass.h",
+ "source/opt/code_sink.cpp",
+ "source/opt/code_sink.h",
"source/opt/combine_access_chains.cpp",
"source/opt/combine_access_chains.h",
"source/opt/common_uniform_elim_pass.cpp",
diff --git a/include/spirv-tools/optimizer.hpp b/include/spirv-tools/optimizer.hpp
index b2865a8..b59329d 100644
--- a/include/spirv-tools/optimizer.hpp
+++ b/include/spirv-tools/optimizer.hpp
@@ -722,6 +722,10 @@
// conform to that model's requirements.
Optimizer::PassToken CreateUpgradeMemoryModelPass();
+// Create a pass to do code sinking. Code sinking is a transformation
+// where an instruction is moved into a more deeply nested construct.
+Optimizer::PassToken CreateCodeSinkingPass();
+
} // namespace spvtools
#endif // INCLUDE_SPIRV_TOOLS_OPTIMIZER_HPP_
diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index 96ee8b3..0f3835c 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -19,6 +19,7 @@
ccp_pass.h
cfg_cleanup_pass.h
cfg.h
+ code_sink.h
combine_access_chains.h
common_uniform_elim_pass.h
compact_ids_pass.h
@@ -111,6 +112,7 @@
ccp_pass.cpp
cfg_cleanup_pass.cpp
cfg.cpp
+ code_sink.cpp
combine_access_chains.cpp
common_uniform_elim_pass.cpp
compact_ids_pass.cpp
diff --git a/source/opt/code_sink.cpp b/source/opt/code_sink.cpp
new file mode 100644
index 0000000..e1e8190
--- /dev/null
+++ b/source/opt/code_sink.cpp
@@ -0,0 +1,316 @@
+// 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 "code_sink.h"
+
+#include <set>
+#include <vector>
+
+#include "source/opt/instruction.h"
+#include "source/opt/ir_builder.h"
+#include "source/opt/ir_context.h"
+#include "source/util/bit_vector.h"
+
+namespace spvtools {
+namespace opt {
+
+Pass::Status CodeSinkingPass::Process() {
+ bool modified = false;
+ for (Function& function : *get_module()) {
+ cfg()->ForEachBlockInPostOrder(function.entry().get(),
+ [&modified, this](BasicBlock* bb) {
+ if (SinkInstructionsInBB(bb)) {
+ modified = true;
+ }
+ });
+ }
+ return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
+}
+
+bool CodeSinkingPass::SinkInstructionsInBB(BasicBlock* bb) {
+ bool modified = false;
+ for (auto inst = bb->rbegin(); inst != bb->rend(); ++inst) {
+ if (SinkInstruction(&*inst)) {
+ inst = bb->rbegin();
+ modified = true;
+ }
+ }
+ return modified;
+}
+
+bool CodeSinkingPass::SinkInstruction(Instruction* inst) {
+ if (inst->opcode() != SpvOpLoad && inst->opcode() != SpvOpAccessChain) {
+ return false;
+ }
+
+ if (ReferencesMutableMemory(inst)) {
+ return false;
+ }
+
+ if (BasicBlock* target_bb = FindNewBasicBlockFor(inst)) {
+ Instruction* pos = &*target_bb->begin();
+ while (pos->opcode() == SpvOpPhi) {
+ pos = pos->NextNode();
+ }
+
+ inst->InsertBefore(pos);
+ context()->set_instr_block(inst, target_bb);
+ return true;
+ }
+ return false;
+}
+
+BasicBlock* CodeSinkingPass::FindNewBasicBlockFor(Instruction* inst) {
+ assert(inst->result_id() != 0 && "Instruction should have a result.");
+ BasicBlock* original_bb = context()->get_instr_block(inst);
+ BasicBlock* bb = original_bb;
+
+ std::unordered_set<uint32_t> bbs_with_uses;
+ get_def_use_mgr()->ForEachUse(
+ inst, [&bbs_with_uses, this](Instruction* use, uint32_t idx) {
+ if (use->opcode() != SpvOpPhi) {
+ bbs_with_uses.insert(context()->get_instr_block(use)->id());
+ } else {
+ bbs_with_uses.insert(use->GetSingleWordOperand(idx + 1));
+ }
+ });
+
+ while (true) {
+ // If |inst| is used in |bb|, then |inst| cannot be moved any further.
+ if (bbs_with_uses.count(bb->id())) {
+ break;
+ }
+
+ // If |bb| has one successor (succ_bb), and |bb| is the only predecessor
+ // of succ_bb, then |inst| can be moved to succ_bb. If succ_bb, has move
+ // then one predecessor, then moving |inst| into succ_bb could cause it to
+ // be executed more often, so the search has to stop.
+ if (bb->terminator()->opcode() == SpvOpBranch) {
+ uint32_t succ_bb_id = bb->terminator()->GetSingleWordInOperand(0);
+ if (cfg()->preds(succ_bb_id).size() == 1) {
+ bb = context()->get_instr_block(succ_bb_id);
+ continue;
+ } else {
+ break;
+ }
+ }
+
+ // The remaining checks need to know the merge node. If there is no merge
+ // instruction or an OpLoopMerge, then it is a break or continue. We could
+ // figure it out, but not worth doing it now.
+ Instruction* merge_inst = bb->GetMergeInst();
+ if (merge_inst == nullptr || merge_inst->opcode() != SpvOpSelectionMerge) {
+ break;
+ }
+
+ // Check all of the successors of |bb| it see which lead to a use of |inst|
+ // before reaching the merge node.
+ bool used_in_multiple_blocks = false;
+ uint32_t bb_used_in = 0;
+ bb->ForEachSuccessorLabel([this, bb, &bb_used_in, &used_in_multiple_blocks,
+ &bbs_with_uses](uint32_t* succ_bb_id) {
+ if (IntersectsPath(*succ_bb_id, bb->MergeBlockIdIfAny(), bbs_with_uses)) {
+ if (bb_used_in == 0) {
+ bb_used_in = *succ_bb_id;
+ } else {
+ used_in_multiple_blocks = true;
+ }
+ }
+ });
+
+ // If more than one successor, which is not the merge block, uses |inst|
+ // then we have to leave |inst| in bb because there is none of the
+ // successors dominate all uses of |inst|.
+ if (used_in_multiple_blocks) {
+ break;
+ }
+
+ if (bb_used_in == 0) {
+ // If |inst| is not used before reaching the merge node, then we can move
+ // |inst| to the merge node.
+ bb = context()->get_instr_block(bb->MergeBlockIdIfAny());
+ } else {
+ // If the only successor that leads to a used of |inst| has more than 1
+ // predecessor, then moving |inst| could cause it to be executed more
+ // often, so we cannot move it.
+ if (cfg()->preds(bb_used_in).size() != 1) {
+ break;
+ }
+
+ // If |inst| is used after the merge block, then |bb_used_in| does not
+ // dominate all of the uses. So we cannot move |inst| any further.
+ if (IntersectsPath(bb->MergeBlockIdIfAny(), original_bb->id(),
+ bbs_with_uses)) {
+ break;
+ }
+
+ // Otherwise, |bb_used_in| dominates all uses, so move |inst| into that
+ // block.
+ bb = context()->get_instr_block(bb_used_in);
+ }
+ continue;
+ }
+ return (bb != original_bb ? bb : nullptr);
+}
+
+bool CodeSinkingPass::ReferencesMutableMemory(Instruction* inst) {
+ if (!inst->IsLoad()) {
+ return false;
+ }
+
+ Instruction* base_ptr = inst->GetBaseAddress();
+ if (base_ptr->opcode() != SpvOpVariable) {
+ return true;
+ }
+
+ if (base_ptr->IsReadOnlyVariable()) {
+ return false;
+ }
+
+ if (HasUniformMemorySync()) {
+ return true;
+ }
+
+ if (base_ptr->GetSingleWordInOperand(0) != SpvStorageClassUniform) {
+ return true;
+ }
+
+ return HasPossibleStore(base_ptr);
+}
+
+bool CodeSinkingPass::HasUniformMemorySync() {
+ if (checked_for_uniform_sync_) {
+ return has_uniform_sync_;
+ }
+
+ bool has_sync = false;
+ get_module()->ForEachInst([this, &has_sync](Instruction* inst) {
+ switch (inst->opcode()) {
+ case SpvOpMemoryBarrier: {
+ uint32_t mem_semantics_id = inst->GetSingleWordInOperand(1);
+ if (IsSyncOnUniform(mem_semantics_id)) {
+ has_sync = true;
+ }
+ break;
+ }
+ case SpvOpControlBarrier:
+ case SpvOpAtomicLoad:
+ case SpvOpAtomicStore:
+ case SpvOpAtomicExchange:
+ case SpvOpAtomicIIncrement:
+ case SpvOpAtomicIDecrement:
+ case SpvOpAtomicIAdd:
+ case SpvOpAtomicISub:
+ case SpvOpAtomicSMin:
+ case SpvOpAtomicUMin:
+ case SpvOpAtomicSMax:
+ case SpvOpAtomicUMax:
+ case SpvOpAtomicAnd:
+ case SpvOpAtomicOr:
+ case SpvOpAtomicXor:
+ case SpvOpAtomicFlagTestAndSet:
+ case SpvOpAtomicFlagClear: {
+ uint32_t mem_semantics_id = inst->GetSingleWordInOperand(2);
+ if (IsSyncOnUniform(mem_semantics_id)) {
+ has_sync = true;
+ }
+ break;
+ }
+ case SpvOpAtomicCompareExchange:
+ case SpvOpAtomicCompareExchangeWeak:
+ if (IsSyncOnUniform(inst->GetSingleWordInOperand(2)) ||
+ IsSyncOnUniform(inst->GetSingleWordInOperand(3))) {
+ has_sync = true;
+ }
+ break;
+ default:
+ break;
+ }
+ });
+ has_uniform_sync_ = has_sync;
+ return has_sync;
+}
+
+bool CodeSinkingPass::IsSyncOnUniform(uint32_t mem_semantics_id) const {
+ const analysis::Constant* mem_semantics_const =
+ context()->get_constant_mgr()->FindDeclaredConstant(mem_semantics_id);
+ assert(mem_semantics_const != nullptr &&
+ "Expecting memory semantics id to be a constant.");
+ assert(mem_semantics_const->AsIntConstant() &&
+ "Memory semantics should be an integer.");
+ uint32_t mem_semantics_int = mem_semantics_const->GetU32();
+
+ // If it does not affect uniform memory, then it is does not apply to uniform
+ // memory.
+ if ((mem_semantics_int & SpvMemorySemanticsUniformMemoryMask) == 0) {
+ return false;
+ }
+
+ // Check if there is an acquire or release. If so not, this it does not add
+ // any memory constraints.
+ return (mem_semantics_int & (SpvMemorySemanticsAcquireMask |
+ SpvMemorySemanticsAcquireReleaseMask |
+ SpvMemorySemanticsReleaseMask)) != 0;
+}
+
+bool CodeSinkingPass::HasPossibleStore(Instruction* var_inst) {
+ assert(var_inst->opcode() == SpvOpVariable ||
+ var_inst->opcode() == SpvOpAccessChain ||
+ var_inst->opcode() == SpvOpPtrAccessChain);
+
+ return get_def_use_mgr()->WhileEachUser(var_inst, [this](Instruction* use) {
+ switch (use->opcode()) {
+ case SpvOpStore:
+ return true;
+ case SpvOpAccessChain:
+ case SpvOpPtrAccessChain:
+ return HasPossibleStore(use);
+ default:
+ return false;
+ }
+ });
+}
+
+bool CodeSinkingPass::IntersectsPath(uint32_t start, uint32_t end,
+ const std::unordered_set<uint32_t>& set) {
+ std::vector<uint32_t> worklist;
+ worklist.push_back(start);
+ std::unordered_set<uint32_t> already_done;
+ already_done.insert(start);
+
+ while (!worklist.empty()) {
+ BasicBlock* bb = context()->get_instr_block(worklist.back());
+ worklist.pop_back();
+
+ if (bb->id() == end) {
+ continue;
+ }
+
+ if (set.count(bb->id())) {
+ return true;
+ }
+
+ bb->ForEachSuccessorLabel([&already_done, &worklist](uint32_t* succ_bb_id) {
+ if (already_done.insert(*succ_bb_id).second) {
+ worklist.push_back(*succ_bb_id);
+ }
+ });
+ }
+ return false;
+}
+
+// namespace opt
+
+} // namespace opt
+} // namespace spvtools
diff --git a/source/opt/code_sink.h b/source/opt/code_sink.h
new file mode 100644
index 0000000..d24df03
--- /dev/null
+++ b/source/opt/code_sink.h
@@ -0,0 +1,107 @@
+// 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_OPT_CODE_SINK_H_
+#define SOURCE_OPT_CODE_SINK_H_
+
+#include <unordered_map>
+
+#include "source/opt/ir_context.h"
+#include "source/opt/module.h"
+#include "source/opt/pass.h"
+
+namespace spvtools {
+namespace opt {
+
+// This pass does code sinking for OpAccessChain and OpLoad on variables in
+// uniform storage or in read only memory. Code sinking is a transformation
+// where an instruction is moved into a more deeply nested construct.
+//
+// The goal is to move these instructions as close as possible to their uses
+// without having to execute them more often or to replicate the instruction.
+// Moving the instruction in this way can lead to shorter live ranges, which can
+// lead to less register pressure. It can also cause instructions to be
+// executed less often because they could be moved into one path of a selection
+// construct.
+//
+// This optimization can cause register pressure to rise if the operands of the
+// instructions go dead after the instructions being moved. That is why we only
+// move certain OpLoad and OpAccessChain instructions. They generally have
+// constants, loop induction variables, and global pointers as operands. The
+// operands are live for a longer time in most cases.
+class CodeSinkingPass : public Pass {
+ public:
+ const char* name() const override { return "code-sink"; }
+ Status Process() override;
+
+ // Return the mask of preserved Analyses.
+ IRContext::Analysis GetPreservedAnalyses() override {
+ return IRContext::kAnalysisDefUse |
+ IRContext::kAnalysisInstrToBlockMapping |
+ IRContext::kAnalysisCombinators | IRContext::kAnalysisCFG |
+ IRContext::kAnalysisDominatorAnalysis |
+ IRContext::kAnalysisLoopAnalysis | IRContext::kAnalysisNameMap |
+ IRContext::kAnalysisConstants | IRContext::kAnalysisTypes;
+ }
+
+ private:
+ // Sinks the instructions in |bb| as much as possible. Returns true if
+ // something changes.
+ bool SinkInstructionsInBB(BasicBlock* bb);
+
+ // Tries the sink |inst| as much as possible. Returns true if the instruction
+ // is moved.
+ bool SinkInstruction(Instruction* inst);
+
+ // Returns the basic block in which to move |inst| to move is as close as
+ // possible to the uses of |inst| without increasing the number of times
+ // |inst| will be executed. Return |nullptr| if there is no need to move
+ // |inst|.
+ BasicBlock* FindNewBasicBlockFor(Instruction* inst);
+
+ // Return true if |inst| reference memory and it is possible that the data in
+ // the memory changes at some point.
+ bool ReferencesMutableMemory(Instruction* inst);
+
+ // Returns true if the module contains an instruction that has a memory
+ // semantics id as an operand, and the memory semantics enforces a
+ // synchronization of uniform memory. See section 3.25 of the SPIR-V
+ // specification.
+ bool HasUniformMemorySync();
+
+ // Returns true if there may be a store to the variable |var_inst|.
+ bool HasPossibleStore(Instruction* var_inst);
+
+ // Returns true if one of the basic blocks in |set| exists on a path from the
+ // basic block |start| to |end|.
+ bool IntersectsPath(uint32_t start, uint32_t end,
+ const std::unordered_set<uint32_t>& set);
+
+ // Returns true if |mem_semantics_id| is the id of a constant that, when
+ // interpreted as a memory semantics mask enforces synchronization of uniform
+ // memory. See section 3.25 of the SPIR-V specification.
+ bool IsSyncOnUniform(uint32_t mem_semantics_id) const;
+
+ // True if a check has for uniform storage has taken place.
+ bool checked_for_uniform_sync_;
+
+ // Cache of whether or not the module has a memory sync on uniform storage.
+ // only valid if |check_for_uniform_sync_| is true.
+ bool has_uniform_sync_;
+};
+
+} // namespace opt
+} // namespace spvtools
+
+#endif // SOURCE_OPT_CODE_SINK_H_
diff --git a/source/opt/optimizer.cpp b/source/opt/optimizer.cpp
index fb58eed..30e80d7 100644
--- a/source/opt/optimizer.cpp
+++ b/source/opt/optimizer.cpp
@@ -21,6 +21,7 @@
#include <vector>
#include <source/spirv_optimizer_options.h>
+#include "code_sink.h"
#include "source/opt/build_module.h"
#include "source/opt/log.h"
#include "source/opt/pass_manager.h"
@@ -181,7 +182,8 @@
.RegisterPass(CreateRedundancyEliminationPass())
.RegisterPass(CreateDeadBranchElimPass())
.RegisterPass(CreateBlockMergePass())
- .RegisterPass(CreateSimplificationPass());
+ .RegisterPass(CreateSimplificationPass())
+ .RegisterPass(CreateCodeSinkingPass());
// Currently exposing driver bugs resulting in crashes (#946)
// .RegisterPass(CreateCommonUniformElimPass())
}
@@ -439,6 +441,8 @@
}
} else if (pass_name == "ccp") {
RegisterPass(CreateCCPPass());
+ } else if (pass_name == "code-sink") {
+ RegisterPass(CreateCodeSinkingPass());
} else if (pass_name == "O") {
RegisterPerformancePasses();
} else if (pass_name == "Os") {
@@ -790,4 +794,9 @@
MakeUnique<opt::InstBindlessCheckPass>(desc_set, shader_id));
}
+Optimizer::PassToken CreateCodeSinkingPass() {
+ return MakeUnique<Optimizer::PassToken::Impl>(
+ MakeUnique<opt::CodeSinkingPass>());
+}
+
} // namespace spvtools
diff --git a/source/opt/passes.h b/source/opt/passes.h
index b9f30ae..f7b675e 100644
--- a/source/opt/passes.h
+++ b/source/opt/passes.h
@@ -21,6 +21,7 @@
#include "source/opt/block_merge_pass.h"
#include "source/opt/ccp_pass.h"
#include "source/opt/cfg_cleanup_pass.h"
+#include "source/opt/code_sink.h"
#include "source/opt/combine_access_chains.h"
#include "source/opt/common_uniform_elim_pass.h"
#include "source/opt/compact_ids_pass.h"
diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt
index 827f501..6315385 100644
--- a/test/opt/CMakeLists.txt
+++ b/test/opt/CMakeLists.txt
@@ -21,6 +21,7 @@
block_merge_test.cpp
ccp_test.cpp
cfg_cleanup_test.cpp
+ code_sink_test.cpp
combine_access_chains_test.cpp
common_uniform_elim_test.cpp
compact_ids_test.cpp
diff --git a/test/opt/code_sink_test.cpp b/test/opt/code_sink_test.cpp
new file mode 100644
index 0000000..9b86c66
--- /dev/null
+++ b/test/opt/code_sink_test.cpp
@@ -0,0 +1,533 @@
+// 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 <string>
+
+#include "gmock/gmock.h"
+#include "test/opt/assembly_builder.h"
+#include "test/opt/pass_fixture.h"
+#include "test/opt/pass_utils.h"
+
+namespace spvtools {
+namespace opt {
+namespace {
+
+using CodeSinkTest = PassTest<::testing::Test>;
+
+TEST_F(CodeSinkTest, MoveToNextBlock) {
+ const std::string text = R"(
+;CHECK: OpFunction
+;CHECK: OpLabel
+;CHECK: OpLabel
+;CHECK: [[ac:%\w+]] = OpAccessChain
+;CHECK: [[ld:%\w+]] = OpLoad %uint [[ac]]
+;CHECK: OpCopyObject %uint [[ld]]
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %9 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %10 = OpTypeFunction %void
+ %1 = OpFunction %void None %10
+ %11 = OpLabel
+ %12 = OpAccessChain %_ptr_Uniform_uint %9 %uint_0
+ %13 = OpLoad %uint %12
+ OpBranch %14
+ %14 = OpLabel
+ %15 = OpCopyObject %uint %13
+ OpReturn
+ OpFunctionEnd
+)";
+
+ SinglePassRunAndMatch<CodeSinkingPass>(text, true);
+}
+
+TEST_F(CodeSinkTest, MovePastSelection) {
+ const std::string text = R"(
+;CHECK: OpFunction
+;CHECK: OpLabel
+;CHECK: OpSelectionMerge [[merge_bb:%\w+]]
+;CHECK: [[merge_bb]] = OpLabel
+;CHECK: [[ac:%\w+]] = OpAccessChain
+;CHECK: [[ld:%\w+]] = OpLoad %uint [[ac]]
+;CHECK: OpCopyObject %uint [[ld]]
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %16
+ %17 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpReturn
+ OpFunctionEnd
+)";
+
+ SinglePassRunAndMatch<CodeSinkingPass>(text, true);
+}
+
+TEST_F(CodeSinkTest, MoveIntoSelection) {
+ const std::string text = R"(
+;CHECK: OpFunction
+;CHECK: OpLabel
+;CHECK: OpSelectionMerge [[merge_bb:%\w+]]
+;CHECK-NEXT: OpBranchConditional %true [[bb:%\w+]] [[merge_bb]]
+;CHECK: [[bb]] = OpLabel
+;CHECK-NEXT: [[ac:%\w+]] = OpAccessChain
+;CHECK-NEXT: [[ld:%\w+]] = OpLoad %uint [[ac]]
+;CHECK-NEXT: OpCopyObject %uint [[ld]]
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ SinglePassRunAndMatch<CodeSinkingPass>(text, true);
+}
+
+TEST_F(CodeSinkTest, LeaveBeforeSelection) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %20
+ %20 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ %19 = OpCopyObject %uint %15
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, LeaveAloneUseInSameBlock) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ %cond = OpIEqual %bool %15 %uint_0
+ OpSelectionMerge %16 None
+ OpBranchConditional %cond %17 %16
+ %17 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ %19 = OpCopyObject %uint %15
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, DontMoveIntoLoop) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpBranch %17
+ %17 = OpLabel
+ OpLoopMerge %merge %cont None
+ OpBranch %cont
+ %cont = OpLabel
+ %cond = OpIEqual %bool %15 %uint_0
+ OpBranchConditional %cond %merge %17
+ %merge = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, DontMoveIntoLoop2) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %16
+ %17 = OpLabel
+ OpLoopMerge %merge %cont None
+ OpBranch %cont
+ %cont = OpLabel
+ %cond = OpIEqual %bool %15 %uint_0
+ OpBranchConditional %cond %merge %17
+ %merge = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, DontMoveSelectionUsedInBothSides) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %20
+ %20 = OpLabel
+ %19 = OpCopyObject %uint %15
+ OpBranch %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, DontMoveBecauseOfStore) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpStore %14 %15
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %20
+ %20 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, MoveReadOnlyLoadWithSync) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%mem_semantics = OpConstant %uint 0x42 ; Uniform memeory arquire
+%_arr_uint_uint_4 = OpTypeArray %uint %uint_4
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpMemoryBarrier %uint_4 %mem_semantics
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %20
+ %20 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, DontMoveBecauseOfSync) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ OpDecorate %_arr_uint_uint_4 BufferBlock
+ OpMemberDecorate %_arr_uint_uint_4 0 Offset 0
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%mem_semantics = OpConstant %uint 0x42 ; Uniform memeory arquire
+%_arr_uint_uint_4 = OpTypeStruct %uint
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ OpMemoryBarrier %uint_4 %mem_semantics
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %20
+ %20 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, DontMoveBecauseOfAtomicWithSync) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ OpDecorate %_arr_uint_uint_4 BufferBlock
+ OpMemberDecorate %_arr_uint_uint_4 0 Offset 0
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%mem_semantics = OpConstant %uint 0x42 ; Uniform memeory arquire
+%_arr_uint_uint_4 = OpTypeStruct %uint
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ %al = OpAtomicLoad %uint %14 %uint_4 %mem_semantics
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %20
+ %20 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+TEST_F(CodeSinkTest, MoveWithAtomicWithoutSync) {
+ const std::string text = R"(
+ OpCapability Shader
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint GLCompute %1 "main"
+ OpDecorate %_arr_uint_uint_4 BufferBlock
+ OpMemberDecorate %_arr_uint_uint_4 0 Offset 0
+ %void = OpTypeVoid
+ %bool = OpTypeBool
+ %true = OpConstantTrue %bool
+ %uint = OpTypeInt 32 0
+ %uint_0 = OpConstant %uint 0
+ %uint_4 = OpConstant %uint 4
+%_arr_uint_uint_4 = OpTypeStruct %uint
+%_ptr_Uniform_uint = OpTypePointer Uniform %uint
+%_ptr_Uniform__arr_uint_uint_4 = OpTypePointer Uniform %_arr_uint_uint_4
+ %11 = OpVariable %_ptr_Uniform__arr_uint_uint_4 Uniform
+ %12 = OpTypeFunction %void
+ %1 = OpFunction %void None %12
+ %13 = OpLabel
+ %14 = OpAccessChain %_ptr_Uniform_uint %11 %uint_0
+ %15 = OpLoad %uint %14
+ %al = OpAtomicLoad %uint %14 %uint_4 %uint_0
+ OpSelectionMerge %16 None
+ OpBranchConditional %true %17 %20
+ %20 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ %18 = OpCopyObject %uint %15
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ auto result = SinglePassRunAndDisassemble<CodeSinkingPass>(
+ text, /* skip_nop = */ true, /* do_validation = */ true);
+ EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
+}
+
+} // namespace
+} // namespace opt
+} // namespace spvtools
