Add spirv-fuzz pass to permute blocks. (#2642)
The blocks within each function in the module will be permuted in a
randomized manner that respects dominance.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index a4cbf8e..6ef1f6a 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -30,11 +30,13 @@
fuzzer.h
fuzzer_context.h
fuzzer_pass.h
+ fuzzer_pass_permute_blocks.h
fuzzer_pass_split_blocks.h
fuzzer_util.h
protobufs/spirvfuzz_protobufs.h
pseudo_random_generator.h
random_generator.h
+ transformation_move_block_down.h
transformation_split_block.h
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
@@ -42,10 +44,12 @@
fuzzer.cpp
fuzzer_context.cpp
fuzzer_pass.cpp
+ fuzzer_pass_permute_blocks.cpp
fuzzer_pass_split_blocks.cpp
fuzzer_util.cpp
pseudo_random_generator.cpp
random_generator.cpp
+ transformation_move_block_down.cpp
transformation_split_block.cpp
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.cc
)
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 559602c..f013070 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -19,6 +19,7 @@
#include "source/fuzz/fact_manager.h"
#include "source/fuzz/fuzzer_context.h"
+#include "source/fuzz/fuzzer_pass_permute_blocks.h"
#include "source/fuzz/fuzzer_pass_split_blocks.h"
#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
#include "source/fuzz/pseudo_random_generator.h"
@@ -102,6 +103,13 @@
transformation_sequence_out)
.Apply();
+ // TODO(afd) Various other passes will be added.
+
+ // Finally, give the blocks in the module a good shake-up.
+ FuzzerPassPermuteBlocks(ir_context.get(), &fact_manager, &fuzzer_context,
+ transformation_sequence_out)
+ .Apply();
+
// Encode the module as a binary.
ir_context->module()->ToBinary(binary_out, false);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 959f25a..c2ffb62 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -22,6 +22,7 @@
// All values are percentages.
// Keep them in alphabetical order.
+const uint32_t kDefaultChanceOfMovingBlockDown = 25;
const uint32_t kDefaultChanceOfSplittingBlock = 20;
} // namespace
@@ -30,6 +31,7 @@
uint32_t min_fresh_id)
: random_generator_(random_generator),
next_fresh_id_(min_fresh_id),
+ chance_of_moving_block_down_(kDefaultChanceOfMovingBlockDown),
chance_of_splitting_block_(kDefaultChanceOfSplittingBlock) {}
FuzzerContext::~FuzzerContext() = default;
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index fbd9c45..2c6bf9c 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -42,6 +42,7 @@
// Probabilities associated with applying various transformations.
// Keep them in alphabetical order.
uint32_t GetChanceOfSplittingBlock() { return chance_of_splitting_block_; }
+ uint32_t GetChanceOfMovingBlockDown() { return chance_of_moving_block_down_; }
private:
// The source of randomness.
@@ -51,6 +52,7 @@
// Probabilities associated with applying various transformations.
// Keep them in alphabetical order.
+ uint32_t chance_of_moving_block_down_;
uint32_t chance_of_splitting_block_;
};
diff --git a/source/fuzz/fuzzer_pass_permute_blocks.cpp b/source/fuzz/fuzzer_pass_permute_blocks.cpp
new file mode 100644
index 0000000..34131dc
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_permute_blocks.cpp
@@ -0,0 +1,85 @@
+// 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/fuzz/fuzzer_pass_permute_blocks.h"
+
+#include "source/fuzz/transformation_move_block_down.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassPermuteBlocks::FuzzerPassPermuteBlocks(
+ opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}
+
+FuzzerPassPermuteBlocks::~FuzzerPassPermuteBlocks() = default;
+
+void FuzzerPassPermuteBlocks::Apply() {
+ // For now we do something very simple: we randomly decide whether to move a
+ // block, and for each block that we do move, we push it down as far as we
+ // legally can.
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2635): it would be
+ // nice to randomly sample from the set of legal block permutations and then
+ // encode the chosen permutation via a series of move-block-down
+ // transformations. This should be possible but will require some thought.
+
+ for (auto& function : *GetIRContext()->module()) {
+ std::vector<uint32_t> block_ids;
+ // Collect all block ids for the function before messing with block
+ // ordering.
+ for (auto& block : function) {
+ block_ids.push_back(block.id());
+ }
+ // Now consider each block id. We consider block ids in reverse, because
+ // e.g. in code generated from the following:
+ //
+ // if (...) {
+ // A
+ // B
+ // } else {
+ // C
+ // }
+ //
+ // block A cannot be moved down, but B has freedom to move and that movement
+ // would provide more freedom for A to move.
+ for (auto id = block_ids.rbegin(); id != block_ids.rend(); ++id) {
+ // Randomly decide whether to ignore the block id.
+ if (GetFuzzerContext()->GetRandomGenerator()->RandomPercentage() >
+ GetFuzzerContext()->GetChanceOfMovingBlockDown()) {
+ continue;
+ }
+ // Keep pushing the block down, until pushing down fails.
+ // The loop is guaranteed to terminate because a block cannot be pushed
+ // down indefinitely.
+ while (true) {
+ protobufs::TransformationMoveBlockDown message;
+ message.set_block_id(*id);
+ if (transformation::IsApplicable(message, GetIRContext(),
+ *GetFactManager())) {
+ transformation::Apply(message, GetIRContext(), GetFactManager());
+ *GetTransformations()
+ ->add_transformation()
+ ->mutable_move_block_down() = message;
+ } else {
+ break;
+ }
+ }
+ }
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_permute_blocks.h b/source/fuzz/fuzzer_pass_permute_blocks.h
new file mode 100644
index 0000000..d8aed72
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_permute_blocks.h
@@ -0,0 +1,39 @@
+// 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_FUZZ_FUZZER_PASS_PERMUTE_BLOCKS_
+#define SOURCE_FUZZ_FUZZER_PASS_PERMUTE_BLOCKS_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass for shuffling the blocks of the module in a validity-preserving
+// manner.
+class FuzzerPassPermuteBlocks : public FuzzerPass {
+ public:
+ FuzzerPassPermuteBlocks(opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassPermuteBlocks() override;
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // #define SOURCE_FUZZ_FUZZER_PASS_PERMUTE_BLOCKS_
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 8f1975b..c760b02 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -35,11 +35,20 @@
message Transformation {
oneof transformation {
- TransformationSplitBlock split_block = 1;
+ TransformationMoveBlockDown move_block_down = 1;
+ TransformationSplitBlock split_block = 2;
}
// Currently there are no transformations.
}
+message TransformationMoveBlockDown {
+ // A transformation that moves a basic block to be one position lower in
+ // program order.
+
+ // The id of the block to move down.
+ uint32 block_id = 1;
+}
+
message TransformationSplitBlock {
// A transformation that splits a basic block into two basic blocks.
diff --git a/source/fuzz/transformation_move_block_down.cpp b/source/fuzz/transformation_move_block_down.cpp
new file mode 100644
index 0000000..858af74
--- /dev/null
+++ b/source/fuzz/transformation_move_block_down.cpp
@@ -0,0 +1,102 @@
+// 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/fuzz/transformation_move_block_down.h"
+
+#include "source/opt/basic_block.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace transformation {
+
+using opt::BasicBlock;
+using opt::IRContext;
+
+bool IsApplicable(const protobufs::TransformationMoveBlockDown& message,
+ IRContext* context, const FactManager& /*unused*/) {
+ // Go through every block in every function, looking for a block whose id
+ // matches that of the block we want to consider moving down.
+ for (auto& function : *context->module()) {
+ for (auto block_it = function.begin(); block_it != function.end();
+ ++block_it) {
+ if (block_it->id() == message.block_id()) {
+ // We have found a match.
+ if (block_it == function.begin()) {
+ // The block is the first one appearing in the function. We are not
+ // allowed to move this block down.
+ return false;
+ }
+ // Record the block we would like to consider moving down.
+ BasicBlock* block_matching_id = &*block_it;
+ // Now see whether there is some block following that block in program
+ // order.
+ ++block_it;
+ if (block_it == function.end()) {
+ // There is no such block; i.e., the block we are considering moving
+ // is the last one in the function. The transformation thus does not
+ // apply.
+ return false;
+ }
+ BasicBlock* next_block_in_program_order = &*block_it;
+ // We can move the block of interest down if and only if it does not
+ // dominate the block that comes next.
+ return !context->GetDominatorAnalysis(&function)->Dominates(
+ block_matching_id, next_block_in_program_order);
+ }
+ }
+ }
+
+ // We did not find a matching block, so the transformation is not applicable:
+ // there is no relevant block to move.
+ return false;
+}
+
+void Apply(const protobufs::TransformationMoveBlockDown& message,
+ IRContext* context, FactManager* /*unused*/) {
+ // Go through every block in every function, looking for a block whose id
+ // matches that of the block we want to move down.
+ for (auto& function : *context->module()) {
+ for (auto block_it = function.begin(); block_it != function.end();
+ ++block_it) {
+ if (block_it->id() == message.block_id()) {
+ ++block_it;
+ assert(block_it != function.end() &&
+ "To be able to move a block down, it needs to have a "
+ "program-order successor.");
+ function.MoveBasicBlockToAfter(message.block_id(), &*block_it);
+ // It is prudent to invalidate analyses after changing block ordering in
+ // case any of them depend on it, but the ones that definitely do not
+ // depend on ordering can be preserved. These include the following,
+ // which can likely be extended.
+ context->InvalidateAnalysesExceptFor(
+ IRContext::Analysis::kAnalysisDefUse |
+ IRContext::Analysis::kAnalysisDominatorAnalysis);
+
+ return;
+ }
+ }
+ }
+ assert(false && "No block was found to move down.");
+}
+
+protobufs::TransformationMoveBlockDown MakeTransformationMoveBlockDown(
+ uint32_t id) {
+ protobufs::TransformationMoveBlockDown result;
+ result.set_block_id(id);
+ return result;
+}
+
+} // namespace transformation
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_move_block_down.h b/source/fuzz/transformation_move_block_down.h
new file mode 100644
index 0000000..072ad53
--- /dev/null
+++ b/source/fuzz/transformation_move_block_down.h
@@ -0,0 +1,46 @@
+// 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_FUZZ_TRANSFORMATION_MOVE_BLOCK_DOWN_H_
+#define SOURCE_FUZZ_TRANSFORMATION_MOVE_BLOCK_DOWN_H_
+
+#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace transformation {
+
+// - |block_id| must be the id of a block b in the given module.
+// - b must not be the first nor last block appearing, in program order,
+// in a function.
+// - b must not dominate the block that follows it in program order.
+bool IsApplicable(const protobufs::TransformationMoveBlockDown& message,
+ opt::IRContext* context, const FactManager& fact_manager);
+
+// The block with id |block_id| is moved down; i.e. the program order
+// between it and the block that follows it is swapped.
+void Apply(const protobufs::TransformationMoveBlockDown& message,
+ opt::IRContext* context, FactManager* fact_manager);
+
+// Creates a protobuf message to move down the block with id |id|.
+protobufs::TransformationMoveBlockDown MakeTransformationMoveBlockDown(
+ uint32_t id);
+
+} // namespace transformation
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_MOVE_BLOCK_DOWN_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 9165026..62ea641 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -18,6 +18,7 @@
fuzz_test_util.h
fuzz_test_util.cpp
+ transformation_move_block_down_test.cpp
transformation_split_block_test.cpp)
add_spvtools_unittest(TARGET fuzz
diff --git a/test/fuzz/transformation_move_block_down_test.cpp b/test/fuzz/transformation_move_block_down_test.cpp
new file mode 100644
index 0000000..122d007
--- /dev/null
+++ b/test/fuzz/transformation_move_block_down_test.cpp
@@ -0,0 +1,830 @@
+// 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/fuzz/transformation_move_block_down.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationMoveBlockDownTest, NoMovePossible1) {
+ // Block 11 cannot be moved down as it dominates block 12.
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpDecorate %8 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %10 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpBranch %11
+ %11 = OpLabel
+ OpStore %8 %9
+ OpBranch %12
+ %12 = OpLabel
+ OpStore %8 %10
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ auto transformation = transformation::MakeTransformationMoveBlockDown(11);
+ ASSERT_FALSE(transformation::IsApplicable(transformation, context.get(),
+ fact_manager));
+}
+
+TEST(TransformationMoveBlockDownTest, NoMovePossible2) {
+ // Block 5 cannot be moved down as it is the entry block.
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpDecorate %8 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %10 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %8 %10
+ OpReturn
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ auto transformation = transformation::MakeTransformationMoveBlockDown(5);
+ ASSERT_FALSE(transformation::IsApplicable(transformation, context.get(),
+ fact_manager));
+}
+
+TEST(TransformationMoveBlockDownTest, NoMovePossible3) {
+ // Block 100 does not exist, so cannot be moved down.
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpDecorate %8 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %10 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpBranch %11
+ %11 = OpLabel
+ OpStore %8 %9
+ OpBranch %12
+ %12 = OpLabel
+ OpStore %8 %10
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ auto transformation = transformation::MakeTransformationMoveBlockDown(100);
+ ASSERT_FALSE(transformation::IsApplicable(transformation, context.get(),
+ fact_manager));
+}
+
+TEST(TransformationMoveBlockDownTest, NoMovePossible4) {
+ // Block 12 is the last block in its function, so cannot be moved down.
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpDecorate %8 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %10 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpBranch %11
+ %11 = OpLabel
+ OpStore %8 %9
+ OpBranch %12
+ %12 = OpLabel
+ OpStore %8 %10
+ OpReturn
+ OpFunctionEnd
+ %13 = OpFunction %2 None %3
+ %14 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ auto transformation = transformation::MakeTransformationMoveBlockDown(12);
+ ASSERT_FALSE(transformation::IsApplicable(transformation, context.get(),
+ fact_manager));
+}
+
+TEST(TransformationMoveBlockDownTest, MovePossible) {
+ // Block 11 can be moved down as it does not dominate block 12 (both are
+ // unreachable).
+ std::string before_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpDecorate %8 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %10 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %8 %10
+ OpReturn
+ %11 = OpLabel
+ OpReturn
+ %12 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpDecorate %8 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 1
+ %10 = OpConstant %6 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %8 %10
+ OpReturn
+ %12 = OpLabel
+ OpReturn
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, before_transformation, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ auto transformation = transformation::MakeTransformationMoveBlockDown(11);
+ ASSERT_TRUE(transformation::IsApplicable(transformation, context.get(),
+ fact_manager));
+ transformation::Apply(transformation, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMoveBlockDownTest, ManyMovesPossible) {
+ // The SPIR-V arising from this shader has lots of opportunities for moving
+ // blocks around.
+ //
+ // void main() {
+ // int x;
+ // int y;
+ // if (x < y) {
+ // x = 1;
+ // if (y == x) {
+ // x = 3;
+ // } else {
+ // x = 4;
+ // }
+ // } else {
+ // if (y < x) {
+ // x = 5;
+ // } else {
+ // x = 6;
+ // }
+ // }
+ // }
+
+ std::string before_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %10 "y"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %9 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %17 RelaxedPrecision
+ OpDecorate %18 RelaxedPrecision
+ OpDecorate %26 RelaxedPrecision
+ OpDecorate %27 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %12 = OpTypeBool
+ %16 = OpConstant %6 1
+ %22 = OpConstant %6 3
+ %24 = OpConstant %6 4
+ %31 = OpConstant %6 5
+ %33 = OpConstant %6 6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %9 = OpLoad %6 %8
+ %11 = OpLoad %6 %10
+ %13 = OpSLessThan %12 %9 %11
+ OpSelectionMerge %15 None
+ OpBranchConditional %13 %14 %25
+ %14 = OpLabel
+ OpStore %8 %16
+ %17 = OpLoad %6 %10
+ %18 = OpLoad %6 %8
+ %19 = OpIEqual %12 %17 %18
+ OpSelectionMerge %21 None
+ OpBranchConditional %19 %20 %23
+ %20 = OpLabel
+ OpStore %8 %22
+ OpBranch %21
+ %23 = OpLabel
+ OpStore %8 %24
+ OpBranch %21
+ %21 = OpLabel
+ OpBranch %15
+ %25 = OpLabel
+ %26 = OpLoad %6 %10
+ %27 = OpLoad %6 %8
+ %28 = OpSLessThan %12 %26 %27
+ OpSelectionMerge %30 None
+ OpBranchConditional %28 %29 %32
+ %29 = OpLabel
+ OpStore %8 %31
+ OpBranch %30
+ %32 = OpLabel
+ OpStore %8 %33
+ OpBranch %30
+ %30 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, before_transformation, kFuzzAssembleOption);
+
+ FactManager fact_manager;
+
+ // The block ids are: 5 14 20 23 21 25 29 32 30 15
+ // We make a transformation to move each of them down, plus a transformation
+ // to move a non-block, 27, down.
+ auto move_down_5 = transformation::MakeTransformationMoveBlockDown(5);
+ auto move_down_14 = transformation::MakeTransformationMoveBlockDown(14);
+ auto move_down_20 = transformation::MakeTransformationMoveBlockDown(20);
+ auto move_down_23 = transformation::MakeTransformationMoveBlockDown(23);
+ auto move_down_21 = transformation::MakeTransformationMoveBlockDown(21);
+ auto move_down_25 = transformation::MakeTransformationMoveBlockDown(25);
+ auto move_down_29 = transformation::MakeTransformationMoveBlockDown(29);
+ auto move_down_32 = transformation::MakeTransformationMoveBlockDown(32);
+ auto move_down_30 = transformation::MakeTransformationMoveBlockDown(30);
+ auto move_down_15 = transformation::MakeTransformationMoveBlockDown(15);
+ auto move_down_27 = transformation::MakeTransformationMoveBlockDown(27);
+
+ // Dominance is as follows:
+ // 5 dominates everything else
+ // 14 dominates 20, 23, 21
+ // 20 dominates nothing
+ // 23 dominates nothing
+ // 21 dominates nothing
+ // 25 dominates 29, 32, 30
+ // 29 dominates nothing
+ // 32 dominates nothing
+ // 30 dominates nothing
+ // 15 dominates nothing
+
+ // Current ordering: 5 14 20 23 21 25 29 32 30 15
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+
+ // Let's bubble 20 all the way down.
+
+ transformation::Apply(move_down_20, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 23 20 21 25 29 32 30 15
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+
+ transformation::Apply(move_down_20, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 23 21 20 25 29 32 30 15
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+
+ transformation::Apply(move_down_20, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 23 21 25 20 29 32 30 15
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+
+ transformation::Apply(move_down_20, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 23 21 25 29 20 32 30 15
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+
+ transformation::Apply(move_down_20, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 23 21 25 29 32 20 30 15
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+
+ transformation::Apply(move_down_20, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 23 21 25 29 32 30 20 15
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+
+ transformation::Apply(move_down_20, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_bubbling_20_down = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %10 "y"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %9 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %17 RelaxedPrecision
+ OpDecorate %18 RelaxedPrecision
+ OpDecorate %26 RelaxedPrecision
+ OpDecorate %27 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %12 = OpTypeBool
+ %16 = OpConstant %6 1
+ %22 = OpConstant %6 3
+ %24 = OpConstant %6 4
+ %31 = OpConstant %6 5
+ %33 = OpConstant %6 6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %9 = OpLoad %6 %8
+ %11 = OpLoad %6 %10
+ %13 = OpSLessThan %12 %9 %11
+ OpSelectionMerge %15 None
+ OpBranchConditional %13 %14 %25
+ %14 = OpLabel
+ OpStore %8 %16
+ %17 = OpLoad %6 %10
+ %18 = OpLoad %6 %8
+ %19 = OpIEqual %12 %17 %18
+ OpSelectionMerge %21 None
+ OpBranchConditional %19 %20 %23
+ %23 = OpLabel
+ OpStore %8 %24
+ OpBranch %21
+ %21 = OpLabel
+ OpBranch %15
+ %25 = OpLabel
+ %26 = OpLoad %6 %10
+ %27 = OpLoad %6 %8
+ %28 = OpSLessThan %12 %26 %27
+ OpSelectionMerge %30 None
+ OpBranchConditional %28 %29 %32
+ %29 = OpLabel
+ OpStore %8 %31
+ OpBranch %30
+ %32 = OpLabel
+ OpStore %8 %33
+ OpBranch %30
+ %30 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ OpReturn
+ %20 = OpLabel
+ OpStore %8 %22
+ OpBranch %21
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_bubbling_20_down, context.get()));
+
+ // Current ordering: 5 14 23 21 25 29 32 30 15 20
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+
+ transformation::Apply(move_down_23, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 21 23 25 29 32 30 15 20
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+
+ transformation::Apply(move_down_23, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 21 25 23 29 32 30 15 20
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+
+ transformation::Apply(move_down_21, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ // Current ordering: 5 14 25 21 23 29 32 30 15 20
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+
+ transformation::Apply(move_down_14, context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_more_shuffling = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %10 "y"
+ OpDecorate %8 RelaxedPrecision
+ OpDecorate %9 RelaxedPrecision
+ OpDecorate %10 RelaxedPrecision
+ OpDecorate %11 RelaxedPrecision
+ OpDecorate %17 RelaxedPrecision
+ OpDecorate %18 RelaxedPrecision
+ OpDecorate %26 RelaxedPrecision
+ OpDecorate %27 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %12 = OpTypeBool
+ %16 = OpConstant %6 1
+ %22 = OpConstant %6 3
+ %24 = OpConstant %6 4
+ %31 = OpConstant %6 5
+ %33 = OpConstant %6 6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ %9 = OpLoad %6 %8
+ %11 = OpLoad %6 %10
+ %13 = OpSLessThan %12 %9 %11
+ OpSelectionMerge %15 None
+ OpBranchConditional %13 %14 %25
+ %25 = OpLabel
+ %26 = OpLoad %6 %10
+ %27 = OpLoad %6 %8
+ %28 = OpSLessThan %12 %26 %27
+ OpSelectionMerge %30 None
+ OpBranchConditional %28 %29 %32
+ %14 = OpLabel
+ OpStore %8 %16
+ %17 = OpLoad %6 %10
+ %18 = OpLoad %6 %8
+ %19 = OpIEqual %12 %17 %18
+ OpSelectionMerge %21 None
+ OpBranchConditional %19 %20 %23
+ %21 = OpLabel
+ OpBranch %15
+ %23 = OpLabel
+ OpStore %8 %24
+ OpBranch %21
+ %29 = OpLabel
+ OpStore %8 %31
+ OpBranch %30
+ %32 = OpLabel
+ OpStore %8 %33
+ OpBranch %30
+ %30 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ OpReturn
+ %20 = OpLabel
+ OpStore %8 %22
+ OpBranch %21
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_more_shuffling, context.get()));
+
+ // Final ordering: 5 25 14 21 23 29 32 30 15 20
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_5, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_25, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_14, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_21, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_23, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_29, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_32, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_30, context.get(), fact_manager));
+ ASSERT_TRUE(
+ transformation::IsApplicable(move_down_15, context.get(), fact_manager));
+ ASSERT_FALSE(
+ transformation::IsApplicable(move_down_20, context.get(), fact_manager));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
