spirv-fuzz: Fuzzer pass to merge blocks (#3097)
This change adds a transformation and associated fuzzer pass for
merging adjacent blocks in a module, re-using block merging code from
the optimizer.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 09272bb..d824d46 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -47,6 +47,7 @@
fuzzer_pass_apply_id_synonyms.h
fuzzer_pass_construct_composites.h
fuzzer_pass_copy_objects.h
+ fuzzer_pass_merge_blocks.h
fuzzer_pass_obfuscate_constants.h
fuzzer_pass_outline_functions.h
fuzzer_pass_permute_blocks.h
@@ -72,6 +73,7 @@
transformation_composite_construct.h
transformation_composite_extract.h
transformation_copy_object.h
+ transformation_merge_blocks.h
transformation_move_block_down.h
transformation_outline_function.h
transformation_replace_boolean_constant_with_constant_binary.h
@@ -103,6 +105,7 @@
fuzzer_pass_apply_id_synonyms.cpp
fuzzer_pass_construct_composites.cpp
fuzzer_pass_copy_objects.cpp
+ fuzzer_pass_merge_blocks.cpp
fuzzer_pass_obfuscate_constants.cpp
fuzzer_pass_outline_functions.cpp
fuzzer_pass_permute_blocks.cpp
@@ -127,6 +130,7 @@
transformation_composite_construct.cpp
transformation_composite_extract.cpp
transformation_copy_object.cpp
+ transformation_merge_blocks.cpp
transformation_move_block_down.cpp
transformation_outline_function.cpp
transformation_replace_boolean_constant_with_constant_binary.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 6b4d54a..95913d0 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -31,6 +31,7 @@
#include "source/fuzz/fuzzer_pass_apply_id_synonyms.h"
#include "source/fuzz/fuzzer_pass_construct_composites.h"
#include "source/fuzz/fuzzer_pass_copy_objects.h"
+#include "source/fuzz/fuzzer_pass_merge_blocks.h"
#include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
#include "source/fuzz/fuzzer_pass_outline_functions.h"
#include "source/fuzz/fuzzer_pass_permute_blocks.h"
@@ -183,6 +184,9 @@
MaybeAddPass<FuzzerPassCopyObjects>(&passes, ir_context.get(),
&fact_manager, &fuzzer_context,
transformation_sequence_out);
+ MaybeAddPass<FuzzerPassMergeBlocks>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
MaybeAddPass<FuzzerPassObfuscateConstants>(&passes, ir_context.get(),
&fact_manager, &fuzzer_context,
transformation_sequence_out);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index b9d0ff9..98585d9 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -34,8 +34,9 @@
90};
const std::pair<uint32_t, uint32_t> kChanceOfAdjustingSelectionControl = {20,
90};
-const std::pair<uint32_t, uint32_t> kChanceOfCopyingObject = {20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfConstructingComposite = {20, 50};
+const std::pair<uint32_t, uint32_t> kChanceOfCopyingObject = {20, 50};
+const std::pair<uint32_t, uint32_t> kChanceOfMergingBlocks = {20, 95};
const std::pair<uint32_t, uint32_t> kChanceOfMovingBlockDown = {20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfObfuscatingConstant = {10, 90};
const std::pair<uint32_t, uint32_t> kChanceOfOutliningFunction = {10, 90};
@@ -82,6 +83,7 @@
chance_of_constructing_composite_ =
ChooseBetweenMinAndMax(kChanceOfConstructingComposite);
chance_of_copying_object_ = ChooseBetweenMinAndMax(kChanceOfCopyingObject);
+ chance_of_merging_blocks_ = ChooseBetweenMinAndMax(kChanceOfMergingBlocks);
chance_of_moving_block_down_ =
ChooseBetweenMinAndMax(kChanceOfMovingBlockDown);
chance_of_obfuscating_constant_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 584c6cb..619c131 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -81,6 +81,7 @@
return chance_of_constructing_composite_;
}
uint32_t GetChanceOfCopyingObject() { return chance_of_copying_object_; }
+ uint32_t GetChanceOfMergingBlocks() { return chance_of_merging_blocks_; }
uint32_t GetChanceOfMovingBlockDown() { return chance_of_moving_block_down_; }
uint32_t GetChanceOfObfuscatingConstant() {
return chance_of_obfuscating_constant_;
@@ -122,6 +123,7 @@
uint32_t chance_of_adjusting_selection_control_;
uint32_t chance_of_constructing_composite_;
uint32_t chance_of_copying_object_;
+ uint32_t chance_of_merging_blocks_;
uint32_t chance_of_moving_block_down_;
uint32_t chance_of_obfuscating_constant_;
uint32_t chance_of_outlining_function_;
diff --git a/source/fuzz/fuzzer_pass_merge_blocks.cpp b/source/fuzz/fuzzer_pass_merge_blocks.cpp
new file mode 100644
index 0000000..ca1bfb3
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_merge_blocks.cpp
@@ -0,0 +1,65 @@
+// 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_merge_blocks.h"
+
+#include <vector>
+
+#include "source/fuzz/transformation_merge_blocks.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassMergeBlocks::FuzzerPassMergeBlocks(
+ opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}
+
+FuzzerPassMergeBlocks::~FuzzerPassMergeBlocks() = default;
+
+void FuzzerPassMergeBlocks::Apply() {
+ // First we populate a sequence of transformations that we might consider
+ // applying.
+ std::vector<TransformationMergeBlocks> potential_transformations;
+ // We do this by considering every block of every function.
+ for (auto& function : *GetIRContext()->module()) {
+ for (auto& block : function) {
+ // We probabilistically decide to ignore some blocks.
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfMergingBlocks())) {
+ continue;
+ }
+ // For other blocks, we add a transformation to merge the block into its
+ // predecessor if that transformation would be applicable.
+ TransformationMergeBlocks transformation(block.id());
+ if (transformation.IsApplicable(GetIRContext(), *GetFactManager())) {
+ potential_transformations.push_back(transformation);
+ }
+ }
+ }
+
+ while (!potential_transformations.empty()) {
+ uint32_t index = GetFuzzerContext()->RandomIndex(potential_transformations);
+ auto transformation = potential_transformations.at(index);
+ potential_transformations.erase(potential_transformations.begin() + index);
+ if (transformation.IsApplicable(GetIRContext(), *GetFactManager())) {
+ transformation.Apply(GetIRContext(), GetFactManager());
+ *GetTransformations()->add_transformation() = transformation.ToMessage();
+ }
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_merge_blocks.h b/source/fuzz/fuzzer_pass_merge_blocks.h
new file mode 100644
index 0000000..457e591
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_merge_blocks.h
@@ -0,0 +1,38 @@
+// 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_MERGE_BLOCKS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_MERGE_BLOCKS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass for merging blocks in the module.
+class FuzzerPassMergeBlocks : public FuzzerPass {
+ public:
+ FuzzerPassMergeBlocks(opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassMergeBlocks();
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_MERGE_BLOCKS_H_
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index ba3a013..3271672 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -201,6 +201,7 @@
TransformationCompositeExtract composite_extract = 21;
TransformationVectorShuffle vector_shuffle = 22;
TransformationOutlineFunction outline_function = 23;
+ TransformationMergeBlocks merge_blocks = 24;
// Add additional option using the next available number.
}
}
@@ -391,6 +392,16 @@
}
+message TransformationMergeBlocks {
+
+ // A transformation that merges a block with its predecessor.
+
+ // The id of the block that is to be merged with its predecessor; the merged
+ // block will have the *predecessor's* id.
+ uint32 block_id = 1;
+
+}
+
message TransformationMoveBlockDown {
// A transformation that moves a basic block to be one position lower in
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index 531cfa1..39325c2 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -28,6 +28,7 @@
#include "source/fuzz/transformation_composite_construct.h"
#include "source/fuzz/transformation_composite_extract.h"
#include "source/fuzz/transformation_copy_object.h"
+#include "source/fuzz/transformation_merge_blocks.h"
#include "source/fuzz/transformation_move_block_down.h"
#include "source/fuzz/transformation_outline_function.h"
#include "source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h"
@@ -82,6 +83,8 @@
message.composite_extract());
case protobufs::Transformation::TransformationCase::kCopyObject:
return MakeUnique<TransformationCopyObject>(message.copy_object());
+ case protobufs::Transformation::TransformationCase::kMergeBlocks:
+ return MakeUnique<TransformationMergeBlocks>(message.merge_blocks());
case protobufs::Transformation::TransformationCase::kMoveBlockDown:
return MakeUnique<TransformationMoveBlockDown>(message.move_block_down());
case protobufs::Transformation::TransformationCase::kOutlineFunction:
diff --git a/source/fuzz/transformation_merge_blocks.cpp b/source/fuzz/transformation_merge_blocks.cpp
new file mode 100644
index 0000000..316e80d
--- /dev/null
+++ b/source/fuzz/transformation_merge_blocks.cpp
@@ -0,0 +1,81 @@
+// 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_merge_blocks.h"
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/opt/block_merge_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationMergeBlocks::TransformationMergeBlocks(
+ const spvtools::fuzz::protobufs::TransformationMergeBlocks& message)
+ : message_(message) {}
+
+TransformationMergeBlocks::TransformationMergeBlocks(uint32_t block_id) {
+ message_.set_block_id(block_id);
+}
+
+bool TransformationMergeBlocks::IsApplicable(
+ opt::IRContext* context,
+ const spvtools::fuzz::FactManager& /*unused*/) const {
+ auto second_block = fuzzerutil::MaybeFindBlock(context, message_.block_id());
+ // The given block must exist.
+ if (!second_block) {
+ return false;
+ }
+ // The block must have just one predecessor.
+ auto predecessors = context->cfg()->preds(second_block->id());
+ if (predecessors.size() != 1) {
+ return false;
+ }
+ auto first_block = context->cfg()->block(predecessors.at(0));
+
+ return opt::blockmergeutil::CanMergeWithSuccessor(context, first_block);
+}
+
+void TransformationMergeBlocks::Apply(
+ opt::IRContext* context, spvtools::fuzz::FactManager* /*unused*/) const {
+ auto second_block = fuzzerutil::MaybeFindBlock(context, message_.block_id());
+ auto first_block =
+ context->cfg()->block(context->cfg()->preds(second_block->id()).at(0));
+
+ auto function = first_block->GetParent();
+ // We need an iterator pointing to the predecessor, hence the loop.
+ for (auto bi = function->begin(); bi != function->end(); ++bi) {
+ if (bi->id() == first_block->id()) {
+ assert(opt::blockmergeutil::CanMergeWithSuccessor(context, &*bi) &&
+ "Because 'Apply' should only be invoked if 'IsApplicable' holds, "
+ "it must be possible to merge |bi| with its successor.");
+ opt::blockmergeutil::MergeWithSuccessor(context, function, bi);
+ // Invalidate all analyses, since we have changed the module
+ // significantly.
+ context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+ return;
+ }
+ }
+ assert(false &&
+ "Control should not reach here - we should always find the desired "
+ "block");
+}
+
+protobufs::Transformation TransformationMergeBlocks::ToMessage() const {
+ protobufs::Transformation result;
+ *result.mutable_merge_blocks() = message_;
+ return result;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_merge_blocks.h b/source/fuzz/transformation_merge_blocks.h
new file mode 100644
index 0000000..86216db
--- /dev/null
+++ b/source/fuzz/transformation_merge_blocks.h
@@ -0,0 +1,54 @@
+// 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_MERGE_BLOCKS_H_
+#define SOURCE_FUZZ_TRANSFORMATION_MERGE_BLOCKS_H_
+
+#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationMergeBlocks : public Transformation {
+ public:
+ explicit TransformationMergeBlocks(
+ const protobufs::TransformationMergeBlocks& message);
+
+ TransformationMergeBlocks(uint32_t block_id);
+
+ // - |message_.block_id| must be the id of a block, b
+ // - b must have a single predecessor, a
+ // - b must be the sole successor of a
+ // - Replacing a with the merge of a and b (and removing b) must lead to a
+ // valid module
+ bool IsApplicable(opt::IRContext* context,
+ const FactManager& fact_manager) const override;
+
+ // The contents of b are merged into a, and a's terminator is replaced with
+ // the terminator of b. Block b is removed from the module.
+ void Apply(opt::IRContext* context, FactManager* fact_manager) const override;
+
+ protobufs::Transformation ToMessage() const override;
+
+ private:
+ protobufs::TransformationMergeBlocks message_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_MERGE_BLOCKS_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index a36027b..ba8468b 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -35,6 +35,7 @@
transformation_composite_construct_test.cpp
transformation_composite_extract_test.cpp
transformation_copy_object_test.cpp
+ transformation_merge_blocks_test.cpp
transformation_move_block_down_test.cpp
transformation_outline_function_test.cpp
transformation_replace_boolean_constant_with_constant_binary_test.cpp
diff --git a/test/fuzz/transformation_merge_blocks_test.cpp b/test/fuzz/transformation_merge_blocks_test.cpp
new file mode 100644
index 0000000..e2b4aa6
--- /dev/null
+++ b/test/fuzz/transformation_merge_blocks_test.cpp
@@ -0,0 +1,675 @@
+// 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_merge_blocks.h"
+
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationMergeBlocksTest, BlockDoesNotExist) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %6
+ %6 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ ASSERT_FALSE(
+ TransformationMergeBlocks(3).IsApplicable(context.get(), fact_manager));
+ ASSERT_FALSE(
+ TransformationMergeBlocks(7).IsApplicable(context.get(), fact_manager));
+}
+
+TEST(TransformationMergeBlocksTest, DoNotMergeFirstBlockHasMultipleSuccessors) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %6 %9
+ %6 = OpLabel
+ OpBranch %10
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ ASSERT_FALSE(
+ TransformationMergeBlocks(6).IsApplicable(context.get(), fact_manager));
+}
+
+TEST(TransformationMergeBlocksTest,
+ DoNotMergeSecondBlockHasMultiplePredecessors) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %6 %9
+ %6 = OpLabel
+ OpBranch %10
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ ASSERT_FALSE(
+ TransformationMergeBlocks(10).IsApplicable(context.get(), fact_manager));
+}
+
+TEST(TransformationMergeBlocksTest, MergeWhenSecondBlockIsSelectionMerge) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %8 %6 %9
+ %6 = OpLabel
+ OpBranch %11
+ %9 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ TransformationMergeBlocks transformation(10);
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ 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
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %11 None
+ OpBranchConditional %8 %6 %9
+ %6 = OpLabel
+ OpBranch %11
+ %9 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeBlocksTest, MergeWhenSecondBlockIsLoopMerge) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %12 = OpLabel
+ OpBranch %5
+ %5 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %6
+ %6 = OpLabel
+ OpBranchConditional %8 %9 %11
+ %9 = OpLabel
+ OpBranch %10
+ %11 = OpLabel
+ OpBranch %5
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ TransformationMergeBlocks transformation(10);
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ 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
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %12 = OpLabel
+ OpBranch %5
+ %5 = OpLabel
+ OpLoopMerge %9 %11 None
+ OpBranch %6
+ %6 = OpLabel
+ OpBranchConditional %8 %9 %11
+ %9 = OpLabel
+ OpReturn
+ %11 = OpLabel
+ OpBranch %5
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeBlocksTest, MergeWhenSecondBlockIsLoopContinue) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %13 = OpLabel
+ OpBranch %5
+ %5 = OpLabel
+ OpLoopMerge %10 %11 None
+ OpBranch %6
+ %6 = OpLabel
+ OpSelectionMerge %9 None
+ OpBranchConditional %8 %9 %12
+ %12 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ OpBranch %5
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ TransformationMergeBlocks transformation(11);
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ 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
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %3 = OpTypeFunction %2
+ %4 = OpFunction %2 None %3
+ %13 = OpLabel
+ OpBranch %5
+ %5 = OpLabel
+ OpLoopMerge %10 %12 None
+ OpBranch %6
+ %6 = OpLabel
+ OpSelectionMerge %9 None
+ OpBranchConditional %8 %9 %12
+ %12 = OpLabel
+ OpBranch %5
+ %9 = OpLabel
+ OpBranch %10
+ %10 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeBlocksTest, MergeWhenSecondBlockStartsWithOpPhi) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %7 = OpTypeBool
+ %8 = OpUndef %7
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %6
+ %6 = OpLabel
+ %9 = OpPhi %7 %8 %5
+ %10 = OpCopyObject %7 %9
+ OpBranch %11
+ %11 = OpLabel
+ %12 = OpCopyObject %7 %9
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ TransformationMergeBlocks transformation(6);
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ 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
+ OpName %4 "main"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %7 = OpTypeBool
+ %8 = OpUndef %7
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %10 = OpCopyObject %7 %8
+ OpBranch %11
+ %11 = OpLabel
+ %12 = OpCopyObject %7 %8
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeBlocksTest, BasicMerge) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %11 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpBranch %100
+ %100 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ %13 = OpLoad %6 %8
+ OpBranch %101
+ %101 = OpLabel
+ %14 = OpIAdd %6 %13 %12
+ OpStore %8 %14
+ %15 = OpLoad %6 %8
+ OpBranch %102
+ %102 = OpLabel
+ %16 = OpLoad %6 %10
+ %17 = OpIMul %6 %16 %15
+ OpBranch %103
+ %103 = OpLabel
+ OpStore %10 %17
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ for (auto& transformation :
+ {TransformationMergeBlocks(100), TransformationMergeBlocks(101),
+ TransformationMergeBlocks(102), TransformationMergeBlocks(103)}) {
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+
+ 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
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %11 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ %13 = OpLoad %6 %8
+ %14 = OpIAdd %6 %13 %12
+ OpStore %8 %14
+ %15 = OpLoad %6 %8
+ %16 = OpLoad %6 %10
+ %17 = OpIMul %6 %16 %15
+ OpStore %10 %17
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeBlocksTest, MergeWhenSecondBlockIsSelectionHeader) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %11 = OpConstant %6 3
+ %50 = OpTypeBool
+ %51 = OpConstantTrue %50
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpBranch %100
+ %100 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ %13 = OpLoad %6 %8
+ OpBranch %101
+ %101 = OpLabel
+ OpSelectionMerge %103 None
+ OpBranchConditional %51 %102 %103
+ %102 = OpLabel
+ %14 = OpIAdd %6 %13 %12
+ OpStore %8 %14
+ OpBranch %103
+ %103 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ for (auto& transformation :
+ {TransformationMergeBlocks(101), TransformationMergeBlocks(100)}) {
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+
+ 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
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %11 = OpConstant %6 3
+ %50 = OpTypeBool
+ %51 = OpConstantTrue %50
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %10 %11
+ %12 = OpLoad %6 %10
+ %13 = OpLoad %6 %8
+ OpSelectionMerge %103 None
+ OpBranchConditional %51 %102 %103
+ %102 = OpLabel
+ %14 = OpIAdd %6 %13 %12
+ OpStore %8 %14
+ OpBranch %103
+ %103 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationMergeBlocksTest,
+ MergeWhenFirstBlockIsLoopMergeFollowedByUnconditionalBranch) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %11 = OpConstant %6 3
+ %50 = OpTypeBool
+ %51 = OpConstantTrue %50
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpBranch %100
+ %100 = OpLabel
+ OpLoopMerge %102 %103 None
+ OpBranch %101
+ %101 = OpLabel
+ %200 = OpCopyObject %6 %9
+ OpBranchConditional %51 %102 %103
+ %103 = OpLabel
+ OpBranch %100
+ %102 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ TransformationMergeBlocks transformation(101);
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ 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
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %11 = OpConstant %6 3
+ %50 = OpTypeBool
+ %51 = OpConstantTrue %50
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpBranch %100
+ %100 = OpLabel
+ %200 = OpCopyObject %6 %9
+ OpLoopMerge %102 %103 None
+ OpBranchConditional %51 %102 %103
+ %103 = OpLabel
+ OpBranch %100
+ %102 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
