spirv-fuzz: Add TransformationDuplicateRegionWithSelection (#3773)
Adds a transformation that inserts a conditional statement with a
boolean expression of arbitrary value and duplicates a given
single-entry, single-exit region, so that it is present in each
conditional branch and will be executed regardless of which branch will
be taken.
Fixes #3614.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 4d9ecdd..e1cc925 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -80,6 +80,7 @@
fuzzer_pass_construct_composites.h
fuzzer_pass_copy_objects.h
fuzzer_pass_donate_modules.h
+ fuzzer_pass_duplicate_regions_with_selections.h
fuzzer_pass_inline_functions.h
fuzzer_pass_invert_comparison_operators.h
fuzzer_pass_interchange_signedness_of_integer_operands.h
@@ -156,6 +157,7 @@
transformation_composite_insert.h
transformation_compute_data_synonym_fact_closure.h
transformation_context.h
+ transformation_duplicate_region_with_selection.h
transformation_equation_instruction.h
transformation_function_call.h
transformation_inline_function.h
@@ -241,6 +243,7 @@
fuzzer_pass_construct_composites.cpp
fuzzer_pass_copy_objects.cpp
fuzzer_pass_donate_modules.cpp
+ fuzzer_pass_duplicate_regions_with_selections.cpp
fuzzer_pass_inline_functions.cpp
fuzzer_pass_invert_comparison_operators.cpp
fuzzer_pass_interchange_signedness_of_integer_operands.cpp
@@ -316,7 +319,7 @@
transformation_composite_insert.cpp
transformation_compute_data_synonym_fact_closure.cpp
transformation_context.cpp
- transformation_replace_opselect_with_conditional_branch.cpp
+ transformation_duplicate_region_with_selection.cpp
transformation_equation_instruction.cpp
transformation_function_call.cpp
transformation_inline_function.cpp
@@ -343,6 +346,7 @@
transformation_replace_linear_algebra_instruction.cpp
transformation_replace_load_store_with_copy_memory.cpp
transformation_replace_opphi_id_from_dead_predecessor.cpp
+ transformation_replace_opselect_with_conditional_branch.cpp
transformation_replace_parameter_with_global.cpp
transformation_replace_params_with_struct.cpp
transformation_set_function_control.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index ee638b6..8b9c9cb 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -49,6 +49,7 @@
#include "source/fuzz/fuzzer_pass_construct_composites.h"
#include "source/fuzz/fuzzer_pass_copy_objects.h"
#include "source/fuzz/fuzzer_pass_donate_modules.h"
+#include "source/fuzz/fuzzer_pass_duplicate_regions_with_selections.h"
#include "source/fuzz/fuzzer_pass_inline_functions.h"
#include "source/fuzz/fuzzer_pass_interchange_signedness_of_integer_operands.h"
#include "source/fuzz/fuzzer_pass_interchange_zero_like_constants.h"
@@ -272,6 +273,9 @@
MaybeAddPass<FuzzerPassDonateModules>(
&passes, ir_context.get(), &transformation_context, &fuzzer_context,
transformation_sequence_out, donor_suppliers);
+ MaybeAddPass<FuzzerPassDuplicateRegionsWithSelections>(
+ &passes, ir_context.get(), &transformation_context, &fuzzer_context,
+ transformation_sequence_out);
MaybeAddPass<FuzzerPassInlineFunctions>(
&passes, ir_context.get(), &transformation_context, &fuzzer_context,
transformation_sequence_out);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 3443a14..869cb5a 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -70,6 +70,8 @@
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> kChanceOfDonatingAdditionalModule = {5, 50};
+const std::pair<uint32_t, uint32_t> kChanceOfDuplicatingRegionWithSelection = {
+ 20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfGoingDeeperToInsertInComposite = {
30, 70};
const std::pair<uint32_t, uint32_t> kChanceOfGoingDeeperWhenMakingAccessChain =
@@ -230,6 +232,8 @@
chance_of_copying_object_ = ChooseBetweenMinAndMax(kChanceOfCopyingObject);
chance_of_donating_additional_module_ =
ChooseBetweenMinAndMax(kChanceOfDonatingAdditionalModule);
+ chance_of_duplicating_region_with_selection_ =
+ ChooseBetweenMinAndMax(kChanceOfDuplicatingRegionWithSelection);
chance_of_going_deeper_to_insert_in_composite_ =
ChooseBetweenMinAndMax(kChanceOfGoingDeeperToInsertInComposite);
chance_of_going_deeper_when_making_access_chain_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 7427a41..8f045c3 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -198,6 +198,9 @@
uint32_t GetChanceOfDonatingAdditionalModule() {
return chance_of_donating_additional_module_;
}
+ uint32_t GetChanceOfDuplicatingRegionWithSelection() {
+ return chance_of_duplicating_region_with_selection_;
+ }
uint32_t GetChanceOfGoingDeeperToInsertInComposite() {
return chance_of_going_deeper_to_insert_in_composite_;
}
@@ -406,6 +409,7 @@
uint32_t chance_of_constructing_composite_;
uint32_t chance_of_copying_object_;
uint32_t chance_of_donating_additional_module_;
+ uint32_t chance_of_duplicating_region_with_selection_;
uint32_t chance_of_going_deeper_to_insert_in_composite_;
uint32_t chance_of_going_deeper_when_making_access_chain_;
uint32_t chance_of_inlining_function_;
diff --git a/source/fuzz/fuzzer_pass_duplicate_regions_with_selections.cpp b/source/fuzz/fuzzer_pass_duplicate_regions_with_selections.cpp
new file mode 100644
index 0000000..45b51ec
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_duplicate_regions_with_selections.cpp
@@ -0,0 +1,133 @@
+// Copyright (c) 2020 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_duplicate_regions_with_selections.h"
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/transformation_duplicate_region_with_selection.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassDuplicateRegionsWithSelections::
+ FuzzerPassDuplicateRegionsWithSelections(
+ opt::IRContext* ir_context,
+ TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassDuplicateRegionsWithSelections::
+ ~FuzzerPassDuplicateRegionsWithSelections() = default;
+
+void FuzzerPassDuplicateRegionsWithSelections::Apply() {
+ // Iterate over all of the functions in the module.
+ for (auto& function : *GetIRContext()->module()) {
+ // Randomly decide whether to apply the transformation.
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfDuplicatingRegionWithSelection())) {
+ continue;
+ }
+ std::vector<opt::BasicBlock*> candidate_entry_blocks;
+ for (auto& block : function) {
+ // We don't consider the first block to be the entry block, since it
+ // could contain OpVariable instructions that would require additional
+ // operations to be reassigned.
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3778):
+ // Consider extending this fuzzer pass to allow the first block to be
+ // used in duplication.
+ if (&block == &*function.begin()) {
+ continue;
+ }
+ candidate_entry_blocks.push_back(&block);
+ }
+ if (candidate_entry_blocks.empty()) {
+ continue;
+ }
+ // Randomly choose the entry block.
+ auto entry_block = candidate_entry_blocks[GetFuzzerContext()->RandomIndex(
+ candidate_entry_blocks)];
+ auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(&function);
+ auto postdominator_analysis =
+ GetIRContext()->GetPostDominatorAnalysis(&function);
+ std::vector<opt::BasicBlock*> candidate_exit_blocks;
+ for (auto postdominates_entry_block = entry_block;
+ postdominates_entry_block != nullptr;
+ postdominates_entry_block = postdominator_analysis->ImmediateDominator(
+ postdominates_entry_block)) {
+ // The candidate exit block must be dominated by the entry block and the
+ // entry block must be post-dominated by the candidate exit block. Ignore
+ // the block if it heads a selection construct or a loop construct.
+ if (dominator_analysis->Dominates(entry_block,
+ postdominates_entry_block) &&
+ !postdominates_entry_block->GetLoopMergeInst()) {
+ candidate_exit_blocks.push_back(postdominates_entry_block);
+ }
+ }
+ if (candidate_exit_blocks.empty()) {
+ continue;
+ }
+ // Randomly choose the exit block.
+ auto exit_block = candidate_exit_blocks[GetFuzzerContext()->RandomIndex(
+ candidate_exit_blocks)];
+
+ auto region_blocks =
+ TransformationDuplicateRegionWithSelection::GetRegionBlocks(
+ GetIRContext(), entry_block, exit_block);
+
+ // Construct |original_label_to_duplicate_label| by iterating over all
+ // blocks in the region. Construct |original_id_to_duplicate_id| and
+ // |original_id_to_phi_id| by iterating over all instructions in each block.
+ std::map<uint32_t, uint32_t> original_label_to_duplicate_label;
+ std::map<uint32_t, uint32_t> original_id_to_duplicate_id;
+ std::map<uint32_t, uint32_t> original_id_to_phi_id;
+ for (auto& block : region_blocks) {
+ original_label_to_duplicate_label[block->id()] =
+ GetFuzzerContext()->GetFreshId();
+ for (auto& instr : *block) {
+ if (instr.result_id()) {
+ original_id_to_duplicate_id[instr.result_id()] =
+ GetFuzzerContext()->GetFreshId();
+ auto final_instruction = &*exit_block->tail();
+ // &*exit_block->tail() is the final instruction of the region.
+ // The instruction is available at the end of the region if and only
+ // if it is available before this final instruction or it is the final
+ // instruction.
+ if ((&instr == final_instruction ||
+ fuzzerutil::IdIsAvailableBeforeInstruction(
+ GetIRContext(), final_instruction, instr.result_id()))) {
+ original_id_to_phi_id[instr.result_id()] =
+ GetFuzzerContext()->GetFreshId();
+ }
+ }
+ }
+ }
+ // Randomly decide between value "true" or "false" for a bool constant.
+ // Make sure the transformation has access to a bool constant to be used
+ // while creating conditional construct.
+ auto condition_id =
+ FindOrCreateBoolConstant(GetFuzzerContext()->ChooseEven(), true);
+
+ TransformationDuplicateRegionWithSelection transformation =
+ TransformationDuplicateRegionWithSelection(
+ GetFuzzerContext()->GetFreshId(), condition_id,
+ GetFuzzerContext()->GetFreshId(), entry_block->id(),
+ exit_block->id(), std::move(original_label_to_duplicate_label),
+ std::move(original_id_to_duplicate_id),
+ std::move(original_id_to_phi_id));
+ MaybeApplyTransformation(transformation);
+ }
+}
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_duplicate_regions_with_selections.h b/source/fuzz/fuzzer_pass_duplicate_regions_with_selections.h
new file mode 100644
index 0000000..3fae698
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_duplicate_regions_with_selections.h
@@ -0,0 +1,42 @@
+// Copyright (c) 2020 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_DUPLICATE_REGIONS_WITH_SELECTIONS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_DUPLICATE_REGIONS_WITH_SELECTIONS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass that iterates over the whole module. For each function it
+// finds a single-entry, single-exit region with its constructs and their merge
+// blocks either completely within or completely outside the region. It
+// duplicates this region using the corresponding transformation.
+class FuzzerPassDuplicateRegionsWithSelections : public FuzzerPass {
+ public:
+ FuzzerPassDuplicateRegionsWithSelections(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassDuplicateRegionsWithSelections() override;
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_DUPLICATE_REGIONS_WITH_SELECTIONS_H_
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 5d27761..f1fa6ac 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -419,6 +419,7 @@
TransformationReplaceIrrelevantId replace_irrelevant_id = 72;
TransformationReplaceOpPhiIdFromDeadPredecessor replace_opphi_id_from_dead_predecessor = 73;
TransformationReplaceOpSelectWithConditionalBranch replace_opselect_with_conditional_branch = 74;
+ TransformationDuplicateRegionWithSelection duplicate_region_with_selection = 75;
// Add additional option using the next available number.
}
}
@@ -1082,6 +1083,41 @@
}
+message TransformationDuplicateRegionWithSelection {
+
+ // A transformation that inserts a conditional statement with a boolean expression
+ // of arbitrary value and duplicates a given single-entry, single-exit region, so
+ // that it is present in each conditional branch and will be executed regardless
+ // of which branch will be taken.
+
+ // Fresh id for a label of the new entry block.
+ uint32 new_entry_fresh_id = 1;
+
+ // Id for a boolean expression.
+ uint32 condition_id = 2;
+
+ // Fresh id for a label of the merge block of the conditional.
+ uint32 merge_label_fresh_id = 3;
+
+ // Block id of the entry block of the original region.
+ uint32 entry_block_id = 4;
+
+ // Block id of the exit block of the original region.
+ uint32 exit_block_id = 5;
+
+ // Map that maps from a label in the original region to the corresponding label
+ // in the duplicated region.
+ repeated UInt32Pair original_label_to_duplicate_label = 6;
+
+ // Map that maps from a result id in the original region to the corresponding
+ // result id in the duplicated region.
+ repeated UInt32Pair original_id_to_duplicate_id = 7;
+
+ // Map that maps from a result id in the original region to the result id of the
+ // corresponding OpPhi instruction.
+ repeated UInt32Pair original_id_to_phi_id = 8;
+}
+
message TransformationEquationInstruction {
// A transformation that adds an instruction to the module that defines an
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index 7156f6e..2f00dc3 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -52,6 +52,7 @@
#include "source/fuzz/transformation_composite_extract.h"
#include "source/fuzz/transformation_composite_insert.h"
#include "source/fuzz/transformation_compute_data_synonym_fact_closure.h"
+#include "source/fuzz/transformation_duplicate_region_with_selection.h"
#include "source/fuzz/transformation_equation_instruction.h"
#include "source/fuzz/transformation_function_call.h"
#include "source/fuzz/transformation_inline_function.h"
@@ -196,6 +197,10 @@
kComputeDataSynonymFactClosure:
return MakeUnique<TransformationComputeDataSynonymFactClosure>(
message.compute_data_synonym_fact_closure());
+ case protobufs::Transformation::TransformationCase::
+ kDuplicateRegionWithSelection:
+ return MakeUnique<TransformationDuplicateRegionWithSelection>(
+ message.duplicate_region_with_selection());
case protobufs::Transformation::TransformationCase::kEquationInstruction:
return MakeUnique<TransformationEquationInstruction>(
message.equation_instruction());
diff --git a/source/fuzz/transformation_duplicate_region_with_selection.cpp b/source/fuzz/transformation_duplicate_region_with_selection.cpp
new file mode 100644
index 0000000..3b6c1df
--- /dev/null
+++ b/source/fuzz/transformation_duplicate_region_with_selection.cpp
@@ -0,0 +1,589 @@
+// Copyright (c) 2020 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_duplicate_region_with_selection.h"
+
+#include "source/fuzz/fuzzer_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationDuplicateRegionWithSelection::
+ TransformationDuplicateRegionWithSelection(
+ const spvtools::fuzz::protobufs::
+ TransformationDuplicateRegionWithSelection& message)
+ : message_(message) {}
+
+TransformationDuplicateRegionWithSelection::
+ TransformationDuplicateRegionWithSelection(
+ uint32_t new_entry_fresh_id, uint32_t condition_id,
+ uint32_t merge_label_fresh_id, uint32_t entry_block_id,
+ uint32_t exit_block_id,
+ const std::map<uint32_t, uint32_t>& original_label_to_duplicate_label,
+ const std::map<uint32_t, uint32_t>& original_id_to_duplicate_id,
+ const std::map<uint32_t, uint32_t>& original_id_to_phi_id) {
+ message_.set_new_entry_fresh_id(new_entry_fresh_id);
+ message_.set_condition_id(condition_id);
+ message_.set_merge_label_fresh_id(merge_label_fresh_id);
+ message_.set_entry_block_id(entry_block_id);
+ message_.set_exit_block_id(exit_block_id);
+ *message_.mutable_original_label_to_duplicate_label() =
+ fuzzerutil::MapToRepeatedUInt32Pair(original_label_to_duplicate_label);
+ *message_.mutable_original_id_to_duplicate_id() =
+ fuzzerutil::MapToRepeatedUInt32Pair(original_id_to_duplicate_id);
+ *message_.mutable_original_id_to_phi_id() =
+ fuzzerutil::MapToRepeatedUInt32Pair(original_id_to_phi_id);
+}
+
+bool TransformationDuplicateRegionWithSelection::IsApplicable(
+ opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
+ // Instruction with the id |condition_id| must exist and must be of a bool
+ // type.
+ auto bool_instr =
+ ir_context->get_def_use_mgr()->GetDef(message_.condition_id());
+ if (bool_instr == nullptr || !bool_instr->type_id()) {
+ return false;
+ }
+ if (!ir_context->get_type_mgr()->GetType(bool_instr->type_id())->AsBool()) {
+ return false;
+ }
+
+ // The |new_entry_fresh_id| must be fresh and distinct.
+ std::set<uint32_t> ids_used_by_this_transformation;
+ if (!CheckIdIsFreshAndNotUsedByThisTransformation(
+ message_.new_entry_fresh_id(), ir_context,
+ &ids_used_by_this_transformation)) {
+ return false;
+ }
+
+ // The |merge_label_fresh_id| must be fresh and distinct.
+ if (!CheckIdIsFreshAndNotUsedByThisTransformation(
+ message_.merge_label_fresh_id(), ir_context,
+ &ids_used_by_this_transformation)) {
+ return false;
+ }
+
+ // The entry and exit block ids must refer to blocks.
+ for (auto block_id : {message_.entry_block_id(), message_.exit_block_id()}) {
+ auto block_label = ir_context->get_def_use_mgr()->GetDef(block_id);
+ if (!block_label || block_label->opcode() != SpvOpLabel) {
+ return false;
+ }
+ }
+ auto entry_block = ir_context->cfg()->block(message_.entry_block_id());
+ auto exit_block = ir_context->cfg()->block(message_.exit_block_id());
+
+ // The |entry_block| and the |exit_block| must be in the same function.
+ if (entry_block->GetParent() != exit_block->GetParent()) {
+ return false;
+ }
+
+ // The |entry_block| must dominate the |exit_block|.
+ auto dominator_analysis =
+ ir_context->GetDominatorAnalysis(entry_block->GetParent());
+ if (!dominator_analysis->Dominates(entry_block, exit_block)) {
+ return false;
+ }
+
+ // The |exit_block| must post-dominate the |entry_block|.
+ auto postdominator_analysis =
+ ir_context->GetPostDominatorAnalysis(entry_block->GetParent());
+ if (!postdominator_analysis->Dominates(exit_block, entry_block)) {
+ return false;
+ }
+
+ auto enclosing_function = entry_block->GetParent();
+
+ // |entry_block| cannot be the first block of the |enclosing_function|.
+ if (&*enclosing_function->begin() == entry_block) {
+ return false;
+ }
+
+ // TODO (https://github.com/KhronosGroup/SPIRV-Tools/issues/3785):
+ // The following code has been copied from TransformationOutlineFunction.
+ // Consider refactoring to avoid duplication.
+ auto region_set = GetRegionBlocks(ir_context, entry_block, exit_block);
+
+ // Check whether |region_set| really is a single-entry single-exit region, and
+ // also check whether structured control flow constructs and their merge
+ // and continue constructs are either wholly in or wholly out of the region -
+ // e.g. avoid the situation where the region contains the head of a loop but
+ // not the loop's continue construct.
+ //
+ // This is achieved by going through every block in the |enclosing_function|
+ for (auto& block : *enclosing_function) {
+ if (&block == exit_block) {
+ // It is not OK for the exit block to head a loop construct or a
+ // conditional construct.
+ if (block.GetMergeInst()) {
+ return false;
+ }
+ continue;
+ }
+ if (region_set.count(&block) != 0) {
+ // The block is in the region and is not the region's exit block. Let's
+ // see whether all of the block's successors are in the region. If they
+ // are not, the region is not single-entry single-exit.
+ bool all_successors_in_region = true;
+ block.WhileEachSuccessorLabel([&all_successors_in_region, ir_context,
+ ®ion_set](uint32_t successor) -> bool {
+ if (region_set.count(ir_context->cfg()->block(successor)) == 0) {
+ all_successors_in_region = false;
+ return false;
+ }
+ return true;
+ });
+ if (!all_successors_in_region) {
+ return false;
+ }
+ }
+
+ if (auto merge = block.GetMergeInst()) {
+ // The block is a loop or selection header. The header and its
+ // associated merge block must be both in the region or both be
+ // outside the region.
+ auto merge_block =
+ ir_context->cfg()->block(merge->GetSingleWordOperand(0));
+ if (region_set.count(&block) != region_set.count(merge_block)) {
+ return false;
+ }
+ }
+
+ if (auto loop_merge = block.GetLoopMergeInst()) {
+ // The continue target of a loop must be within the region if and only if
+ // the header of the loop is.
+ auto continue_target =
+ ir_context->cfg()->block(loop_merge->GetSingleWordOperand(1));
+ // The continue target is a single-entry, single-exit region. Therefore,
+ // if the continue target is the exit block, the region might not contain
+ // the loop header.
+ if (continue_target != exit_block &&
+ region_set.count(&block) != region_set.count(continue_target)) {
+ return false;
+ }
+ }
+ }
+
+ // Get the maps from the protobuf.
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3786):
+ // Consider additionally providing overflow ids to make this
+ // transformation more applicable when shrinking.
+ std::map<uint32_t, uint32_t> original_label_to_duplicate_label =
+ fuzzerutil::RepeatedUInt32PairToMap(
+ message_.original_label_to_duplicate_label());
+
+ std::map<uint32_t, uint32_t> original_id_to_duplicate_id =
+ fuzzerutil::RepeatedUInt32PairToMap(
+ message_.original_id_to_duplicate_id());
+
+ std::map<uint32_t, uint32_t> original_id_to_phi_id =
+ fuzzerutil::RepeatedUInt32PairToMap(message_.original_id_to_phi_id());
+
+ for (auto block : region_set) {
+ auto label =
+ ir_context->get_def_use_mgr()->GetDef(block->id())->result_id();
+ // The label of every block in the region must be present in the map
+ // |original_label_to_duplicate_label|.
+ if (original_label_to_duplicate_label.count(label) == 0) {
+ return false;
+ }
+ auto duplicate_label = original_label_to_duplicate_label[label];
+ // Each id assigned to labels in the region must be distinct and fresh.
+ if (!duplicate_label ||
+ !CheckIdIsFreshAndNotUsedByThisTransformation(
+ duplicate_label, ir_context, &ids_used_by_this_transformation)) {
+ return false;
+ }
+ for (auto instr : *block) {
+ if (!instr.HasResultId()) {
+ continue;
+ }
+ // Every instruction with a result id in the region must be present in the
+ // map |original_id_to_duplicate_id|.
+ if (original_id_to_duplicate_id.count(instr.result_id()) == 0) {
+ return false;
+ }
+ auto duplicate_id = original_id_to_duplicate_id[instr.result_id()];
+ // Id assigned to this result id in the region must be distinct and fresh.
+ if (!duplicate_id ||
+ !CheckIdIsFreshAndNotUsedByThisTransformation(
+ duplicate_id, ir_context, &ids_used_by_this_transformation)) {
+ return false;
+ }
+ if (&instr == &*exit_block->tail() ||
+ fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, &*exit_block->tail(), instr.result_id())) {
+ // Every instruction with a result id available at the end of the region
+ // must be present in the map |original_id_to_phi_id|.
+ if (original_id_to_phi_id.count(instr.result_id()) == 0) {
+ return false;
+ }
+ // Using pointers with OpPhi requires capability VariablePointers.
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3787):
+ // Consider not adding OpPhi instructions for the pointers which are
+ // unused after the region, so that the transformation could be
+ // still applicable.
+ if (ir_context->get_type_mgr()->GetType(instr.type_id())->AsPointer() &&
+ !ir_context->get_feature_mgr()->HasCapability(
+ SpvCapabilityVariablePointers)) {
+ return false;
+ }
+ auto phi_id = original_id_to_phi_id[instr.result_id()];
+ // Id assigned to this result id in the region must be distinct and
+ // fresh.
+ if (!phi_id ||
+ !CheckIdIsFreshAndNotUsedByThisTransformation(
+ phi_id, ir_context, &ids_used_by_this_transformation)) {
+ return false;
+ }
+ }
+ }
+ }
+ return true;
+}
+
+void TransformationDuplicateRegionWithSelection::Apply(
+ opt::IRContext* ir_context, TransformationContext* /*unused*/) const {
+ fuzzerutil::UpdateModuleIdBound(ir_context, message_.new_entry_fresh_id());
+ fuzzerutil::UpdateModuleIdBound(ir_context, message_.merge_label_fresh_id());
+
+ // Create the new entry block containing the main conditional instruction. Set
+ // its parent to the parent of the original entry block, since it is located
+ // in the same function.
+ std::unique_ptr<opt::BasicBlock> new_entry_block =
+ MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpLabel, 0, message_.new_entry_fresh_id(),
+ opt::Instruction::OperandList()));
+ auto entry_block = ir_context->cfg()->block(message_.entry_block_id());
+ auto enclosing_function = entry_block->GetParent();
+ auto exit_block = ir_context->cfg()->block(message_.exit_block_id());
+
+ // Get the blocks contained in the region.
+ std::set<opt::BasicBlock*> region_blocks =
+ GetRegionBlocks(ir_context, entry_block, exit_block);
+
+ // Construct the merge block.
+ std::unique_ptr<opt::BasicBlock> merge_block =
+ MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(opt::Instruction(
+ ir_context, SpvOpLabel, 0, message_.merge_label_fresh_id(),
+ opt::Instruction::OperandList())));
+
+ // Get the maps from the protobuf.
+ std::map<uint32_t, uint32_t> original_label_to_duplicate_label =
+ fuzzerutil::RepeatedUInt32PairToMap(
+ message_.original_label_to_duplicate_label());
+
+ std::map<uint32_t, uint32_t> original_id_to_duplicate_id =
+ fuzzerutil::RepeatedUInt32PairToMap(
+ message_.original_id_to_duplicate_id());
+
+ std::map<uint32_t, uint32_t> original_id_to_phi_id =
+ fuzzerutil::RepeatedUInt32PairToMap(message_.original_id_to_phi_id());
+
+ // Before adding duplicate blocks, we need to update the OpPhi instructions in
+ // the successors of the |exit_block|. We know that the execution of the
+ // transformed region will end in |merge_block|. Hence, we need to change all
+ // occurrences of the label id of the |exit_block| to the label id of the
+ // |merge_block|.
+ exit_block->ForEachSuccessorLabel([this, ir_context](uint32_t label_id) {
+ auto block = ir_context->cfg()->block(label_id);
+ for (auto& instr : *block) {
+ if (instr.opcode() == SpvOpPhi) {
+ instr.ForEachId([this](uint32_t* id) {
+ if (*id == message_.exit_block_id()) {
+ *id = message_.merge_label_fresh_id();
+ }
+ });
+ }
+ }
+ });
+
+ // Get vector of predecessors id of |entry_block|. Remove any duplicate
+ // values.
+ auto entry_block_preds = ir_context->cfg()->preds(entry_block->id());
+ std::sort(entry_block_preds.begin(), entry_block_preds.end());
+ entry_block_preds.erase(
+ unique(entry_block_preds.begin(), entry_block_preds.end()),
+ entry_block_preds.end());
+ // We know that |entry_block| has only one predecessor, since the region is
+ // single-entry, single-exit and its constructs and their merge blocks must be
+ // either wholly within or wholly outside of the region.
+ assert(entry_block_preds.size() == 1 &&
+ "The entry of the region to be duplicated can have only one "
+ "predecessor.");
+ uint32_t entry_block_pred_id =
+ ir_context->get_instr_block(entry_block_preds[0])->id();
+ // Update all the OpPhi instructions in the |entry_block|. Change every
+ // occurence of |entry_block_pred_id| to the id of |new_entry|, because we
+ // will insert |new_entry| before |entry_block|.
+ for (auto& instr : *entry_block) {
+ if (instr.opcode() == SpvOpPhi) {
+ instr.ForEachId([this, entry_block_pred_id](uint32_t* id) {
+ if (*id == entry_block_pred_id) {
+ *id = message_.new_entry_fresh_id();
+ }
+ });
+ }
+ }
+
+ // Duplication of blocks will invalidate iterators. Store all the blocks from
+ // the enclosing function.
+ std::vector<opt::BasicBlock*> blocks;
+ for (auto& block : *enclosing_function) {
+ blocks.push_back(&block);
+ }
+
+ opt::BasicBlock* previous_block = nullptr;
+ // Iterate over all blocks of the function to duplicate blocks of the original
+ // region and their instructions.
+ for (auto& block : blocks) {
+ // The block must be contained in the region.
+ if (region_blocks.count(block) == 0) {
+ continue;
+ }
+
+ fuzzerutil::UpdateModuleIdBound(
+ ir_context, original_label_to_duplicate_label[block->id()]);
+
+ std::unique_ptr<opt::BasicBlock> duplicated_block =
+ MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpLabel, 0,
+ original_label_to_duplicate_label[block->id()],
+ opt::Instruction::OperandList()));
+
+ for (auto& instr : *block) {
+ // Case where an instruction is the terminator of the exit block is
+ // handled separately.
+ if (block == exit_block && instr.IsBlockTerminator()) {
+ switch (instr.opcode()) {
+ case SpvOpBranch:
+ case SpvOpReturn:
+ case SpvOpReturnValue:
+ case SpvOpUnreachable:
+ case SpvOpKill:
+ continue;
+ default:
+ assert(false &&
+ "Unexpected terminator for |exit_block| of the region.");
+ }
+ }
+ // Duplicate the instruction.
+ auto cloned_instr = instr.Clone(ir_context);
+ duplicated_block->AddInstruction(
+ std::unique_ptr<opt::Instruction>(cloned_instr));
+
+ fuzzerutil::UpdateModuleIdBound(
+ ir_context, original_id_to_duplicate_id[instr.result_id()]);
+
+ // If an id from the original region was used in this instruction,
+ // replace it with the value from |original_id_to_duplicate_id|.
+ // If a label from the original region was used in this instruction,
+ // replace it with the value from |original_label_to_duplicate_label|.
+ cloned_instr->ForEachId(
+ [original_id_to_duplicate_id,
+ original_label_to_duplicate_label](uint32_t* op) {
+ if (original_id_to_duplicate_id.count(*op) != 0) {
+ *op = original_id_to_duplicate_id.at(*op);
+ }
+ if (original_label_to_duplicate_label.count(*op) != 0) {
+ *op = original_label_to_duplicate_label.at(*op);
+ }
+ });
+ }
+
+ // If the block is the first duplicated block, insert it after the exit
+ // block of the original region. Otherwise, insert it after the preceding
+ // one.
+ auto duplicated_block_ptr = duplicated_block.get();
+ if (previous_block) {
+ enclosing_function->InsertBasicBlockAfter(std::move(duplicated_block),
+ previous_block);
+ } else {
+ enclosing_function->InsertBasicBlockAfter(std::move(duplicated_block),
+ exit_block);
+ }
+ previous_block = duplicated_block_ptr;
+ }
+
+ // After execution of the loop, this variable stores a pointer to the last
+ // duplicated block.
+ auto duplicated_exit_block = previous_block;
+
+ for (auto& block : region_blocks) {
+ for (auto& instr : *block) {
+ if (instr.result_id() != 0 &&
+ (&instr == &*exit_block->tail() ||
+ fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, &*exit_block->tail(), instr.result_id()))) {
+ // Add the OpPhi instruction for every result id that is
+ // available at the end of the region (the last instruction
+ // of the |exit_block|)
+ merge_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpPhi, instr.type_id(),
+ original_id_to_phi_id[instr.result_id()],
+ opt::Instruction::OperandList({
+ {SPV_OPERAND_TYPE_ID, {instr.result_id()}},
+ {SPV_OPERAND_TYPE_ID, {exit_block->id()}},
+ {SPV_OPERAND_TYPE_ID,
+ {original_id_to_duplicate_id[instr.result_id()]}},
+ {SPV_OPERAND_TYPE_ID, {duplicated_exit_block->id()}},
+ })));
+
+ fuzzerutil::UpdateModuleIdBound(
+ ir_context, original_id_to_phi_id[instr.result_id()]);
+
+ // If the instruction has been remapped by an OpPhi, look
+ // for all its uses outside of the region and outside of the
+ // merge block (to not overwrite just added instructions in
+ // the merge block) and replace the original instruction id
+ // with the id of the corresponding OpPhi instruction.
+ ir_context->get_def_use_mgr()->ForEachUse(
+ &instr,
+ [ir_context, &instr, region_blocks, original_id_to_phi_id,
+ &merge_block](opt::Instruction* user, uint32_t operand_index) {
+ auto user_block = ir_context->get_instr_block(user);
+ if ((region_blocks.find(user_block) != region_blocks.end()) ||
+ user_block == merge_block.get()) {
+ return;
+ }
+ user->SetOperand(operand_index,
+ {original_id_to_phi_id.at(instr.result_id())});
+ });
+ }
+ }
+ }
+
+ // Construct a conditional instruction in the |new_entry_block|.
+ // If the condition is true, the execution proceeds in the
+ // |entry_block| of the original region. If the condition is
+ // false, the execution proceeds in the first block of the
+ // duplicated region.
+ new_entry_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpSelectionMerge, 0, 0,
+ opt::Instruction::OperandList(
+ {{SPV_OPERAND_TYPE_ID, {message_.merge_label_fresh_id()}},
+ {SPV_OPERAND_TYPE_SELECTION_CONTROL,
+ {SpvSelectionControlMaskNone}}})));
+
+ new_entry_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpBranchConditional, 0, 0,
+ opt::Instruction::OperandList(
+ {{SPV_OPERAND_TYPE_ID, {message_.condition_id()}},
+ {SPV_OPERAND_TYPE_ID, {message_.entry_block_id()}},
+ {SPV_OPERAND_TYPE_ID,
+ {original_label_to_duplicate_label[message_.entry_block_id()]}}})));
+
+ // Move the terminator of |exit_block| to the end of
+ // |merge_block|.
+ auto exit_block_terminator = exit_block->terminator();
+ auto cloned_instr = exit_block_terminator->Clone(ir_context);
+ merge_block->AddInstruction(std::unique_ptr<opt::Instruction>(cloned_instr));
+ ir_context->KillInst(exit_block_terminator);
+
+ // Add OpBranch instruction to the merge block at the end of
+ // |exit_block| and at the end of |duplicated_exit_block|, so that
+ // the execution proceeds in the |merge_block|.
+ opt::Instruction merge_branch_instr = opt::Instruction(
+ ir_context, SpvOpBranch, 0, 0,
+ opt::Instruction::OperandList(
+ {{SPV_OPERAND_TYPE_ID, {message_.merge_label_fresh_id()}}}));
+ exit_block->AddInstruction(MakeUnique<opt::Instruction>(merge_branch_instr));
+ duplicated_exit_block->AddInstruction(
+ MakeUnique<opt::Instruction>(merge_branch_instr));
+
+ // Execution needs to start in the |new_entry_block|. Change all
+ // the uses of |entry_block_label_instr| outside of the original
+ // region to |message_.new_entry_fresh_id|.
+ auto entry_block_label_instr =
+ ir_context->get_def_use_mgr()->GetDef(message_.entry_block_id());
+ ir_context->get_def_use_mgr()->ForEachUse(
+ entry_block_label_instr,
+ [this, ir_context, region_blocks](opt::Instruction* user,
+ uint32_t operand_index) {
+ auto user_block = ir_context->get_instr_block(user);
+ if ((region_blocks.count(user_block) != 0)) {
+ return;
+ }
+ switch (user->opcode()) {
+ case SpvOpSwitch:
+ case SpvOpBranch:
+ case SpvOpBranchConditional:
+ case SpvOpLoopMerge:
+ case SpvOpSelectionMerge: {
+ user->SetOperand(operand_index, {message_.new_entry_fresh_id()});
+ } break;
+ case SpvOpName:
+ break;
+ default:
+ assert(false &&
+ "The label id cannot be used by instructions "
+ "other than "
+ "OpSwitch, OpBranch, OpBranchConditional, "
+ "OpLoopMerge, "
+ "OpSelectionMerge");
+ }
+ });
+
+ // Insert the merge block after the |duplicated_exit_block| (the
+ // last duplicated block).
+ enclosing_function->InsertBasicBlockAfter(std::move(merge_block),
+ duplicated_exit_block);
+
+ // Insert the |new_entry_block| before the entry block of the
+ // original region.
+ enclosing_function->InsertBasicBlockBefore(std::move(new_entry_block),
+ entry_block);
+
+ // Since we have changed the module, most of the analysis are now
+ // invalid. We can invalidate analyses now after all of the blocks
+ // have been registered.
+ ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+// TODO (https://github.com/KhronosGroup/SPIRV-Tools/issues/3785):
+// The following method has been copied from
+// TransformationOutlineFunction. Consider refactoring to avoid
+// duplication.
+std::set<opt::BasicBlock*>
+TransformationDuplicateRegionWithSelection::GetRegionBlocks(
+ opt::IRContext* ir_context, opt::BasicBlock* entry_block,
+ opt::BasicBlock* exit_block) {
+ auto enclosing_function = entry_block->GetParent();
+ auto dominator_analysis =
+ ir_context->GetDominatorAnalysis(enclosing_function);
+ auto postdominator_analysis =
+ ir_context->GetPostDominatorAnalysis(enclosing_function);
+
+ // A block belongs to a region between the entry block and the exit
+ // block if and only if it is dominated by the entry block and
+ // post-dominated by the exit block.
+ std::set<opt::BasicBlock*> result;
+ for (auto& block : *enclosing_function) {
+ if (dominator_analysis->Dominates(entry_block, &block) &&
+ postdominator_analysis->Dominates(exit_block, &block)) {
+ result.insert(&block);
+ }
+ }
+ return result;
+}
+
+protobufs::Transformation
+TransformationDuplicateRegionWithSelection::ToMessage() const {
+ protobufs::Transformation result;
+ *result.mutable_duplicate_region_with_selection() = message_;
+ return result;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_duplicate_region_with_selection.h b/source/fuzz/transformation_duplicate_region_with_selection.h
new file mode 100644
index 0000000..a1a2a89
--- /dev/null
+++ b/source/fuzz/transformation_duplicate_region_with_selection.h
@@ -0,0 +1,78 @@
+// Copyright (c) 2020 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_DUPLICATE_REGION_WITH_SELECTION_H_
+#define SOURCE_FUZZ_TRANSFORMATION_DUPLICATE_REGION_WITH_SELECTION_H_
+
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/fuzz/transformation_context.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationDuplicateRegionWithSelection : public Transformation {
+ public:
+ explicit TransformationDuplicateRegionWithSelection(
+ const protobufs::TransformationDuplicateRegionWithSelection& message);
+
+ explicit TransformationDuplicateRegionWithSelection(
+ uint32_t new_entry_fresh_id, uint32_t condition_id,
+ uint32_t merge_label_fresh_id, uint32_t entry_block_id,
+ uint32_t exit_block_id,
+ const std::map<uint32_t, uint32_t>& original_label_to_duplicate_label,
+ const std::map<uint32_t, uint32_t>& original_id_to_duplicate_id,
+ const std::map<uint32_t, uint32_t>& original_id_to_phi_id);
+
+ // - |new_entry_fresh_id|, |merge_label_fresh_id| must be fresh and distinct.
+ // - |condition_id| must refer to a valid instruction of boolean type.
+ // - |entry_block_id| and |exit_block_id| must refer to valid blocks and they
+ // must form a single-entry, single-exit region. Its constructs and their
+ // merge blocks must be either wholly within or wholly outside of the
+ // region.
+ // - |original_label_to_duplicate_label| must contain at least a key for every
+ // block in the original region.
+ // - |original_id_to_duplicate_id| must contain at least a key for every
+ // result id in the original region.
+ // - |original_id_to_phi_id| must contain at least a key for every result id
+ // available at the end of the original region.
+ // - In each of these three maps, each value must be a distinct, fresh id.
+ bool IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const override;
+
+ // A transformation that inserts a conditional statement with a boolean
+ // expression of arbitrary value and duplicates a given single-entry,
+ // single-exit region, so that it is present in each conditional branch and
+ // will be executed regardless of which branch will be taken.
+ void Apply(opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const override;
+
+ // Returns the set of blocks dominated by |entry_block| and post-dominated
+ // by |exit_block|.
+ static std::set<opt::BasicBlock*> GetRegionBlocks(
+ opt::IRContext* ir_context, opt::BasicBlock* entry_block,
+ opt::BasicBlock* exit_block);
+
+ protobufs::Transformation ToMessage() const override;
+
+ private:
+ protobufs::TransformationDuplicateRegionWithSelection message_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_DUPLICATE_REGION_WITH_SELECTION_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 6199e69..f4add4c 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -62,6 +62,7 @@
transformation_composite_extract_test.cpp
transformation_composite_insert_test.cpp
transformation_compute_data_synonym_fact_closure_test.cpp
+ transformation_duplicate_region_with_selection_test.cpp
transformation_equation_instruction_test.cpp
transformation_function_call_test.cpp
transformation_inline_function_test.cpp
diff --git a/test/fuzz/transformation_duplicate_region_with_selection_test.cpp b/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
new file mode 100644
index 0000000..6539c4a
--- /dev/null
+++ b/test/fuzz/transformation_duplicate_region_with_selection_test.cpp
@@ -0,0 +1,1604 @@
+// Copyright (c) 2020 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_duplicate_region_with_selection.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationDuplicateRegionWithSelectionTest, BasicUseTest) {
+ // This test handles a case where the ids from the original region are used in
+ // subsequent block.
+
+ std::string shader = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "b"
+ OpName %18 "c"
+ OpName %20 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %14 = OpConstant %6 2
+ %16 = OpTypeBool
+ %17 = OpTypePointer Function %16
+ %19 = OpConstantTrue %16
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %18 = OpVariable %17 Function
+ %20 = OpVariable %7 Function
+ OpStore %18 %19
+ OpStore %20 %14
+ %21 = OpFunctionCall %2 %10 %20
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpBranch %800
+ %800 = OpLabel
+ %13 = OpLoad %6 %9
+ %15 = OpIAdd %6 %13 %14
+ OpStore %12 %15
+ OpBranch %900
+ %900 = OpLabel
+ %901 = OpIAdd %6 %15 %13
+ %902 = OpISub %6 %13 %15
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ TransformationDuplicateRegionWithSelection transformation_good_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+
+ ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+ transformation_context));
+ transformation_good_1.Apply(context.get(), &transformation_context);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+ std::string expected_shader = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "b"
+ OpName %18 "c"
+ OpName %20 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %14 = OpConstant %6 2
+ %16 = OpTypeBool
+ %17 = OpTypePointer Function %16
+ %19 = OpConstantTrue %16
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %18 = OpVariable %17 Function
+ %20 = OpVariable %7 Function
+ OpStore %18 %19
+ OpStore %20 %14
+ %21 = OpFunctionCall %2 %10 %20
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpBranch %500
+ %500 = OpLabel
+ OpSelectionMerge %501 None
+ OpBranchConditional %19 %800 %100
+ %800 = OpLabel
+ %13 = OpLoad %6 %9
+ %15 = OpIAdd %6 %13 %14
+ OpStore %12 %15
+ OpBranch %501
+ %100 = OpLabel
+ %201 = OpLoad %6 %9
+ %202 = OpIAdd %6 %201 %14
+ OpStore %12 %202
+ OpBranch %501
+ %501 = OpLabel
+ %301 = OpPhi %6 %13 %800 %201 %100
+ %302 = OpPhi %6 %15 %800 %202 %100
+ OpBranch %900
+ %900 = OpLabel
+ %901 = OpIAdd %6 %302 %301
+ %902 = OpISub %6 %301 %302
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest, BasicExitBlockTest) {
+ // This test handles a case where the exit block of the region is the exit
+ // block of the containing function.
+
+ std::string shader = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "b"
+ OpName %18 "c"
+ OpName %20 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %14 = OpConstant %6 2
+ %16 = OpTypeBool
+ %17 = OpTypePointer Function %16
+ %19 = OpConstantTrue %16
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %18 = OpVariable %17 Function
+ %20 = OpVariable %7 Function
+ OpStore %18 %19
+ OpStore %20 %14
+ %21 = OpFunctionCall %2 %10 %20
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpBranch %800
+ %800 = OpLabel
+ %13 = OpLoad %6 %9
+ %15 = OpIAdd %6 %13 %14
+ OpStore %12 %15
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ TransformationDuplicateRegionWithSelection transformation_good_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+
+ ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+ transformation_context));
+ transformation_good_1.Apply(context.get(), &transformation_context);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string expected_shader = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "b"
+ OpName %18 "c"
+ OpName %20 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %14 = OpConstant %6 2
+ %16 = OpTypeBool
+ %17 = OpTypePointer Function %16
+ %19 = OpConstantTrue %16
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %18 = OpVariable %17 Function
+ %20 = OpVariable %7 Function
+ OpStore %18 %19
+ OpStore %20 %14
+ %21 = OpFunctionCall %2 %10 %20
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpBranch %500
+ %500 = OpLabel
+ OpSelectionMerge %501 None
+ OpBranchConditional %19 %800 %100
+ %800 = OpLabel
+ %13 = OpLoad %6 %9
+ %15 = OpIAdd %6 %13 %14
+ OpStore %12 %15
+ OpBranch %501
+ %100 = OpLabel
+ %201 = OpLoad %6 %9
+ %202 = OpIAdd %6 %201 %14
+ OpStore %12 %202
+ OpBranch %501
+ %501 = OpLabel
+ %301 = OpPhi %6 %13 %800 %201 %100
+ %302 = OpPhi %6 %15 %800 %202 %100
+ OpReturn
+ OpFunctionEnd
+
+ )";
+ ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest, NotApplicableCFGTest) {
+ // This test handles few cases where the transformation is not applicable
+ // because of the control flow graph or layout of the blocks.
+
+ 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"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %18 "b"
+ OpName %25 "c"
+ OpName %27 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %13 = OpConstant %6 2
+ %14 = OpTypeBool
+ %24 = OpTypePointer Function %14
+ %26 = OpConstantTrue %14
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %25 = OpVariable %24 Function
+ %27 = OpVariable %7 Function
+ OpStore %25 %26
+ OpStore %27 %13
+ %28 = OpFunctionCall %2 %10 %27
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %18 = OpVariable %7 Function
+ %12 = OpLoad %6 %9
+ %15 = OpSLessThan %14 %12 %13
+ OpSelectionMerge %17 None
+ OpBranchConditional %15 %16 %21
+ %16 = OpLabel
+ %19 = OpLoad %6 %9
+ %20 = OpIAdd %6 %19 %13
+ OpStore %18 %20
+ OpBranch %17
+ %21 = OpLabel
+ %22 = OpLoad %6 %9
+ %23 = OpISub %6 %22 %13
+ OpStore %18 %23
+ OpBranch %17
+ %17 = 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ // Bad: |entry_block_id| refers to the entry block of the function (this
+ // transformation currently avoids such cases).
+ TransformationDuplicateRegionWithSelection transformation_bad_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 26, 501, 11, 11, {{11, 100}}, {{18, 201}, {12, 202}, {15, 203}},
+ {{18, 301}, {12, 302}, {15, 303}});
+ ASSERT_FALSE(
+ transformation_bad_1.IsApplicable(context.get(), transformation_context));
+
+ // Bad: The block with id 16 does not dominate the block with id 21.
+ TransformationDuplicateRegionWithSelection transformation_bad_2 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 26, 501, 16, 21, {{16, 100}, {21, 101}},
+ {{19, 201}, {20, 202}, {22, 203}, {23, 204}},
+ {{19, 301}, {20, 302}, {22, 303}, {23, 304}});
+ ASSERT_FALSE(
+ transformation_bad_2.IsApplicable(context.get(), transformation_context));
+
+ // Bad: The block with id 21 does not post-dominate the block with id 11.
+ TransformationDuplicateRegionWithSelection transformation_bad_3 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 26, 501, 11, 21, {{11, 100}, {21, 101}},
+ {{18, 201}, {12, 202}, {15, 203}, {22, 204}, {23, 205}},
+ {{18, 301}, {12, 302}, {15, 303}, {22, 304}, {23, 305}});
+ ASSERT_FALSE(
+ transformation_bad_3.IsApplicable(context.get(), transformation_context));
+
+ // Bad: The block with id 5 is contained in a different function than the
+ // block with id 11.
+ TransformationDuplicateRegionWithSelection transformation_bad_4 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 26, 501, 5, 11, {{5, 100}, {11, 101}},
+ {{25, 201}, {27, 202}, {28, 203}, {18, 204}, {12, 205}, {15, 206}},
+ {{25, 301}, {27, 302}, {28, 303}, {18, 304}, {12, 305}, {15, 306}});
+ ASSERT_FALSE(
+ transformation_bad_4.IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest, NotApplicableIdTest) {
+ // This test handles a case where the supplied ids are either not fresh, not
+ // distinct, not valid in their context or do not refer to the existing
+ // instructions.
+
+ std::string shader = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "b"
+ OpName %18 "c"
+ OpName %20 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %14 = OpConstant %6 2
+ %16 = OpTypeBool
+ %17 = OpTypePointer Function %16
+ %19 = OpConstantTrue %16
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %18 = OpVariable %17 Function
+ %20 = OpVariable %7 Function
+ OpStore %18 %19
+ OpStore %20 %14
+ %21 = OpFunctionCall %2 %10 %20
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpBranch %800
+ %800 = OpLabel
+ %13 = OpLoad %6 %9
+ %15 = OpIAdd %6 %13 %14
+ OpStore %12 %15
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ // Bad: A value in the |original_label_to_duplicate_label| is not a fresh id.
+ TransformationDuplicateRegionWithSelection transformation_bad_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 800, 800, {{800, 21}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+
+ ASSERT_FALSE(
+ transformation_bad_1.IsApplicable(context.get(), transformation_context));
+
+ // Bad: Values in the |original_id_to_duplicate_id| are not distinct.
+ TransformationDuplicateRegionWithSelection transformation_bad_2 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 201}},
+ {{13, 301}, {15, 302}});
+ ASSERT_FALSE(
+ transformation_bad_2.IsApplicable(context.get(), transformation_context));
+
+ // Bad: Values in the |original_id_to_phi_id| are not fresh and are not
+ // distinct with previous values.
+ TransformationDuplicateRegionWithSelection transformation_bad_3 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 18}, {15, 202}});
+ ASSERT_FALSE(
+ transformation_bad_3.IsApplicable(context.get(), transformation_context));
+
+ // Bad: |entry_block_id| does not refer to an existing instruction.
+ TransformationDuplicateRegionWithSelection transformation_bad_4 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 802, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+ ASSERT_FALSE(
+ transformation_bad_4.IsApplicable(context.get(), transformation_context));
+
+ // Bad: |exit_block_id| does not refer to a block.
+ TransformationDuplicateRegionWithSelection transformation_bad_5 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 800, 9, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+ ASSERT_FALSE(
+ transformation_bad_5.IsApplicable(context.get(), transformation_context));
+
+ // Bad: |new_entry_fresh_id| is not fresh.
+ TransformationDuplicateRegionWithSelection transformation_bad_6 =
+ TransformationDuplicateRegionWithSelection(
+ 20, 19, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+ ASSERT_FALSE(
+ transformation_bad_6.IsApplicable(context.get(), transformation_context));
+
+ // Bad: |merge_label_fresh_id| is not fresh.
+ TransformationDuplicateRegionWithSelection transformation_bad_7 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 20, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+ ASSERT_FALSE(
+ transformation_bad_7.IsApplicable(context.get(), transformation_context));
+
+ // Bad: Instruction with id 15 is from the original region and is available
+ // at the end of the region but it is not present in the
+ // |original_id_to_phi_id|.
+ TransformationDuplicateRegionWithSelection transformation_bad_8 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 19, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}});
+ ASSERT_FALSE(
+ transformation_bad_8.IsApplicable(context.get(), transformation_context));
+
+ // Bad: Instruction with id 15 is from the original region but it is
+ // not present in the |original_id_to_duplicate_id|.
+ TransformationDuplicateRegionWithSelection transformation_bad_9 =
+ TransformationDuplicateRegionWithSelection(500, 19, 501, 800, 800,
+ {{800, 100}}, {{13, 201}},
+ {{13, 301}, {15, 302}});
+ ASSERT_FALSE(
+ transformation_bad_9.IsApplicable(context.get(), transformation_context));
+
+ // Bad: |condition_id| does not refer to the valid instruction.
+ TransformationDuplicateRegionWithSelection transformation_bad_10 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 200, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+
+ ASSERT_FALSE(transformation_bad_10.IsApplicable(context.get(),
+ transformation_context));
+
+ // Bad: |condition_id| does not refer to the instruction of type OpTypeBool
+ TransformationDuplicateRegionWithSelection transformation_bad_11 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 14, 501, 800, 800, {{800, 100}}, {{13, 201}, {15, 202}},
+ {{13, 301}, {15, 302}});
+
+ ASSERT_FALSE(transformation_bad_11.IsApplicable(context.get(),
+ transformation_context));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest, NotApplicableCFGTest2) {
+ // This test handles few cases where the transformation is not applicable
+ // because of the control flow graph or the layout of the blocks.
+
+ 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"
+ OpName %6 "fun("
+ OpName %10 "s"
+ OpName %12 "i"
+ OpName %29 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %11 = OpConstant %8 0
+ %19 = OpConstant %8 10
+ %20 = OpTypeBool
+ %26 = OpConstant %8 1
+ %28 = OpTypePointer Function %20
+ %30 = OpConstantTrue %20
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %29 = OpVariable %28 Function
+ OpStore %29 %30
+ %31 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %10 = OpVariable %9 Function
+ %12 = OpVariable %9 Function
+ OpStore %10 %11
+ OpStore %12 %11
+ OpBranch %13
+ %13 = OpLabel
+ OpLoopMerge %15 %16 None
+ OpBranch %17
+ %17 = OpLabel
+ %18 = OpLoad %8 %12
+ %21 = OpSLessThan %20 %18 %19
+ OpBranchConditional %21 %14 %15
+ %14 = OpLabel
+ %22 = OpLoad %8 %10
+ %23 = OpLoad %8 %12
+ %24 = OpIAdd %8 %22 %23
+ OpStore %10 %24
+ OpBranch %16
+ %16 = OpLabel
+ OpBranch %50
+ %50 = OpLabel
+ %25 = OpLoad %8 %12
+ %27 = OpIAdd %8 %25 %26
+ OpStore %12 %27
+ OpBranch %13
+ %15 = 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+ // Bad: The exit block cannot be a header of a loop, because the region won't
+ // be a single-entry, single-exit region.
+ TransformationDuplicateRegionWithSelection transformation_bad_1 =
+ TransformationDuplicateRegionWithSelection(500, 30, 501, 13, 13,
+ {{13, 100}}, {{}}, {{}});
+ ASSERT_FALSE(
+ transformation_bad_1.IsApplicable(context.get(), transformation_context));
+
+ // Bad: The block with id 13, the loop header, is in the region. The block
+ // with id 15, the loop merge block, is not in the region.
+ TransformationDuplicateRegionWithSelection transformation_bad_2 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 30, 501, 13, 17, {{13, 100}, {17, 101}}, {{18, 201}, {21, 202}},
+ {{18, 301}, {21, 302}});
+ ASSERT_FALSE(
+ transformation_bad_2.IsApplicable(context.get(), transformation_context));
+
+ // Bad: The block with id 13, the loop header, is not in the region. The block
+ // with id 16, the loop continue target, is in the region.
+ TransformationDuplicateRegionWithSelection transformation_bad_3 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 30, 501, 16, 50, {{16, 100}, {50, 101}}, {{25, 201}, {27, 202}},
+ {{25, 301}, {27, 302}});
+ ASSERT_FALSE(
+ transformation_bad_3.IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest, NotApplicableCFGTest3) {
+ // This test handles a case where for the block which is not the exit block,
+ // not all successors are in the region.
+
+ 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"
+ OpName %6 "fun("
+ OpName %14 "a"
+ OpName %19 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeBool
+ %9 = OpConstantTrue %8
+ %12 = OpTypeInt 32 1
+ %13 = OpTypePointer Function %12
+ %15 = OpConstant %12 2
+ %17 = OpConstant %12 3
+ %18 = OpTypePointer Function %8
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %19 = OpVariable %18 Function
+ OpStore %19 %9
+ %20 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %14 = OpVariable %13 Function
+ OpSelectionMerge %11 None
+ OpBranchConditional %9 %10 %16
+ %10 = OpLabel
+ OpStore %14 %15
+ OpBranch %11
+ %16 = OpLabel
+ OpStore %14 %17
+ OpBranch %11
+ %11 = 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+ // Bad: The block with id 7, which is not an exit block, has two successors:
+ // the block with id 10 and the block with id 16. The block with id 16 is not
+ // in the region.
+ TransformationDuplicateRegionWithSelection transformation_bad_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 30, 501, 7, 10, {{13, 100}}, {{14, 201}}, {{14, 301}});
+ ASSERT_FALSE(
+ transformation_bad_1.IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest, MultipleBlocksLoopTest) {
+ // This test handles a case where the region consists of multiple blocks
+ // (they form a loop). The transformation is applicable and the region is
+ // duplicated.
+
+ 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"
+ OpName %6 "fun("
+ OpName %10 "s"
+ OpName %12 "i"
+ OpName %29 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %11 = OpConstant %8 0
+ %19 = OpConstant %8 10
+ %20 = OpTypeBool
+ %26 = OpConstant %8 1
+ %28 = OpTypePointer Function %20
+ %30 = OpConstantTrue %20
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %29 = OpVariable %28 Function
+ OpStore %29 %30
+ %31 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %10 = OpVariable %9 Function
+ %12 = OpVariable %9 Function
+ OpStore %10 %11
+ OpStore %12 %11
+ OpBranch %50
+ %50 = OpLabel
+ OpBranch %13
+ %13 = OpLabel
+ OpLoopMerge %15 %16 None
+ OpBranch %17
+ %17 = OpLabel
+ %18 = OpLoad %8 %12
+ %21 = OpSLessThan %20 %18 %19
+ OpBranchConditional %21 %14 %15
+ %14 = OpLabel
+ %22 = OpLoad %8 %10
+ %23 = OpLoad %8 %12
+ %24 = OpIAdd %8 %22 %23
+ OpStore %10 %24
+ OpBranch %16
+ %16 = OpLabel
+ %25 = OpLoad %8 %12
+ %27 = OpIAdd %8 %25 %26
+ OpStore %12 %27
+ OpBranch %13
+ %15 = 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ TransformationDuplicateRegionWithSelection transformation_good_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 30, 501, 50, 15,
+ {{50, 100}, {13, 101}, {14, 102}, {15, 103}, {16, 104}, {17, 105}},
+ {{22, 201},
+ {23, 202},
+ {24, 203},
+ {25, 204},
+ {27, 205},
+ {18, 206},
+ {21, 207}},
+ {{22, 301},
+ {23, 302},
+ {24, 303},
+ {25, 304},
+ {27, 305},
+ {18, 306},
+ {21, 307}});
+ ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+ transformation_context));
+ transformation_good_1.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string expected_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"
+ OpName %6 "fun("
+ OpName %10 "s"
+ OpName %12 "i"
+ OpName %29 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %11 = OpConstant %8 0
+ %19 = OpConstant %8 10
+ %20 = OpTypeBool
+ %26 = OpConstant %8 1
+ %28 = OpTypePointer Function %20
+ %30 = OpConstantTrue %20
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %29 = OpVariable %28 Function
+ OpStore %29 %30
+ %31 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %10 = OpVariable %9 Function
+ %12 = OpVariable %9 Function
+ OpStore %10 %11
+ OpStore %12 %11
+ OpBranch %500
+ %500 = OpLabel
+ OpSelectionMerge %501 None
+ OpBranchConditional %30 %50 %100
+ %50 = OpLabel
+ OpBranch %13
+ %13 = OpLabel
+ OpLoopMerge %15 %16 None
+ OpBranch %17
+ %17 = OpLabel
+ %18 = OpLoad %8 %12
+ %21 = OpSLessThan %20 %18 %19
+ OpBranchConditional %21 %14 %15
+ %14 = OpLabel
+ %22 = OpLoad %8 %10
+ %23 = OpLoad %8 %12
+ %24 = OpIAdd %8 %22 %23
+ OpStore %10 %24
+ OpBranch %16
+ %16 = OpLabel
+ %25 = OpLoad %8 %12
+ %27 = OpIAdd %8 %25 %26
+ OpStore %12 %27
+ OpBranch %13
+ %15 = OpLabel
+ OpBranch %501
+ %100 = OpLabel
+ OpBranch %101
+ %101 = OpLabel
+ OpLoopMerge %103 %104 None
+ OpBranch %105
+ %105 = OpLabel
+ %206 = OpLoad %8 %12
+ %207 = OpSLessThan %20 %206 %19
+ OpBranchConditional %207 %102 %103
+ %102 = OpLabel
+ %201 = OpLoad %8 %10
+ %202 = OpLoad %8 %12
+ %203 = OpIAdd %8 %201 %202
+ OpStore %10 %203
+ OpBranch %104
+ %104 = OpLabel
+ %204 = OpLoad %8 %12
+ %205 = OpIAdd %8 %204 %26
+ OpStore %12 %205
+ OpBranch %101
+ %103 = OpLabel
+ OpBranch %501
+ %501 = OpLabel
+ %306 = OpPhi %8 %18 %15 %206 %103
+ %307 = OpPhi %20 %21 %15 %207 %103
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest,
+ ResolvingOpPhiExitBlockTest) {
+ // This test handles a case where the region under the transformation is
+ // referenced in OpPhi instructions. Since the new merge block becomes the
+ // exit of the region, these OpPhi instructions need to be updated.
+
+ 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"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "s"
+ OpName %26 "b"
+ OpName %29 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %13 = OpConstant %6 0
+ %15 = OpConstant %6 2
+ %16 = OpTypeBool
+ %25 = OpTypePointer Function %16
+ %27 = OpConstantTrue %16
+ %28 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %26 = OpVariable %25 Function
+ %29 = OpVariable %7 Function
+ OpStore %26 %27
+ OpStore %29 %28
+ %30 = OpFunctionCall %2 %10 %29
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpStore %12 %13
+ %14 = OpLoad %6 %9
+ %17 = OpSLessThan %16 %14 %15
+ OpSelectionMerge %19 None
+ OpBranchConditional %17 %18 %22
+ %18 = OpLabel
+ %20 = OpLoad %6 %9
+ %21 = OpIAdd %6 %20 %15
+ OpStore %12 %21
+ OpBranch %19
+ %22 = OpLabel
+ %23 = OpLoad %6 %9
+ %24 = OpIMul %6 %23 %15
+ OpStore %12 %24
+ OpBranch %19
+ %19 = OpLabel
+ %40 = OpPhi %6 %21 %18 %24 %22
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ TransformationDuplicateRegionWithSelection transformation_good_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 27, 501, 22, 22, {{22, 100}}, {{23, 201}, {24, 202}},
+ {{23, 301}, {24, 302}});
+
+ ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+ transformation_context));
+ transformation_good_1.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string expected_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"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "s"
+ OpName %26 "b"
+ OpName %29 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %13 = OpConstant %6 0
+ %15 = OpConstant %6 2
+ %16 = OpTypeBool
+ %25 = OpTypePointer Function %16
+ %27 = OpConstantTrue %16
+ %28 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %26 = OpVariable %25 Function
+ %29 = OpVariable %7 Function
+ OpStore %26 %27
+ OpStore %29 %28
+ %30 = OpFunctionCall %2 %10 %29
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpStore %12 %13
+ %14 = OpLoad %6 %9
+ %17 = OpSLessThan %16 %14 %15
+ OpSelectionMerge %19 None
+ OpBranchConditional %17 %18 %500
+ %18 = OpLabel
+ %20 = OpLoad %6 %9
+ %21 = OpIAdd %6 %20 %15
+ OpStore %12 %21
+ OpBranch %19
+ %500 = OpLabel
+ OpSelectionMerge %501 None
+ OpBranchConditional %27 %22 %100
+ %22 = OpLabel
+ %23 = OpLoad %6 %9
+ %24 = OpIMul %6 %23 %15
+ OpStore %12 %24
+ OpBranch %501
+ %100 = OpLabel
+ %201 = OpLoad %6 %9
+ %202 = OpIMul %6 %201 %15
+ OpStore %12 %202
+ OpBranch %501
+ %501 = OpLabel
+ %301 = OpPhi %6 %23 %22 %201 %100
+ %302 = OpPhi %6 %24 %22 %202 %100
+ OpBranch %19
+ %19 = OpLabel
+ %40 = OpPhi %6 %21 %18 %302 %501
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest, NotApplicableEarlyReturn) {
+ // This test handles a case where one of the blocks has successor outside of
+ // the region, which has an early return from the function, so that the
+ // transformation is not applicable.
+
+ 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"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "s"
+ OpName %27 "b"
+ OpName %30 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %13 = OpConstant %6 0
+ %15 = OpConstant %6 2
+ %16 = OpTypeBool
+ %26 = OpTypePointer Function %16
+ %28 = OpConstantTrue %16
+ %29 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %27 = OpVariable %26 Function
+ %30 = OpVariable %7 Function
+ OpStore %27 %28
+ OpStore %30 %29
+ %31 = OpFunctionCall %2 %10 %30
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ OpBranch %50
+ %50 = OpLabel
+ OpStore %12 %13
+ %14 = OpLoad %6 %9
+ %17 = OpSLessThan %16 %14 %15
+ OpSelectionMerge %19 None
+ OpBranchConditional %17 %18 %22
+ %18 = OpLabel
+ %20 = OpLoad %6 %9
+ %21 = OpIAdd %6 %20 %15
+ OpStore %12 %21
+ OpBranch %19
+ %22 = OpLabel
+ OpReturn
+ %19 = 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ // Bad: The block with id 50, which is the entry block, has two successors:
+ // the block with id 18 and the block with id 22. The block 22 has an early
+ // return from the function, so that the entry block is not post-dominated by
+ // the exit block.
+ TransformationDuplicateRegionWithSelection transformation_bad_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 28, 501, 50, 19, {{50, 100}, {18, 101}, {22, 102}, {19, 103}},
+ {{14, 202}, {17, 203}, {20, 204}, {21, 205}},
+ {{14, 302}, {17, 303}, {20, 304}, {21, 305}});
+ ASSERT_FALSE(
+ transformation_bad_1.IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest,
+ ResolvingOpPhiEntryBlockOnePredecessor) {
+ // This test handles a case where the entry block has an OpPhi instruction
+ // referring to its predecessor. After transformation, this instruction needs
+ // to be updated.
+
+ 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"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "s"
+ OpName %14 "t"
+ OpName %20 "b"
+ OpName %23 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %13 = OpConstant %6 0
+ %15 = OpConstant %6 2
+ %18 = OpTypeBool
+ %19 = OpTypePointer Function %18
+ %21 = OpConstantTrue %18
+ %22 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %20 = OpVariable %19 Function
+ %23 = OpVariable %7 Function
+ OpStore %20 %21
+ OpStore %23 %22
+ %24 = OpFunctionCall %2 %10 %23
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %12 %13
+ %16 = OpLoad %6 %12
+ %17 = OpIMul %6 %15 %16
+ OpStore %14 %17
+ OpBranch %50
+ %50 = OpLabel
+ %51 = OpPhi %6 %17 %11
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ TransformationDuplicateRegionWithSelection transformation_good_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 21, 501, 50, 50, {{50, 100}}, {{51, 201}}, {{51, 301}});
+ ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+ transformation_context));
+ transformation_good_1.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string expected_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"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "s"
+ OpName %14 "t"
+ OpName %20 "b"
+ OpName %23 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %13 = OpConstant %6 0
+ %15 = OpConstant %6 2
+ %18 = OpTypeBool
+ %19 = OpTypePointer Function %18
+ %21 = OpConstantTrue %18
+ %22 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %20 = OpVariable %19 Function
+ %23 = OpVariable %7 Function
+ OpStore %20 %21
+ OpStore %23 %22
+ %24 = OpFunctionCall %2 %10 %23
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %12 %13
+ %16 = OpLoad %6 %12
+ %17 = OpIMul %6 %15 %16
+ OpStore %14 %17
+ OpBranch %500
+ %500 = OpLabel
+ OpSelectionMerge %501 None
+ OpBranchConditional %21 %50 %100
+ %50 = OpLabel
+ %51 = OpPhi %6 %17 %500
+ OpBranch %501
+ %100 = OpLabel
+ %201 = OpPhi %6 %17 %500
+ OpBranch %501
+ %501 = OpLabel
+ %301 = OpPhi %6 %51 %50 %201 %100
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest,
+ NotApplicableNoVariablePointerCapability) {
+ // This test handles a case where the transformation would create an OpPhi
+ // instruction with pointer operands, however there is no cab
+ // CapabilityVariablePointers. Hence, the transformation is not applicable.
+
+ 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"
+ OpName %10 "fun(i1;"
+ OpName %9 "a"
+ OpName %12 "s"
+ OpName %14 "t"
+ OpName %20 "b"
+ OpName %23 "param"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeFunction %2 %7
+ %13 = OpConstant %6 0
+ %15 = OpConstant %6 2
+ %18 = OpTypeBool
+ %19 = OpTypePointer Function %18
+ %21 = OpConstantTrue %18
+ %22 = OpConstant %6 3
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %20 = OpVariable %19 Function
+ %23 = OpVariable %7 Function
+ OpStore %20 %21
+ OpStore %23 %22
+ %24 = OpFunctionCall %2 %10 %23
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %2 None %8
+ %9 = OpFunctionParameter %7
+ %11 = OpLabel
+ %12 = OpVariable %7 Function
+ %14 = OpVariable %7 Function
+ OpStore %12 %13
+ %16 = OpLoad %6 %12
+ %17 = OpIMul %6 %15 %16
+ OpStore %14 %17
+ OpBranch %50
+ %50 = OpLabel
+ %51 = OpCopyObject %7 %12
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ // Bad: There is no required capability CapabilityVariablePointers
+ TransformationDuplicateRegionWithSelection transformation_bad_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 21, 501, 50, 50, {{50, 100}}, {{51, 201}}, {{51, 301}});
+ ASSERT_FALSE(
+ transformation_bad_1.IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest,
+ ExitBlockTerminatorOpUnreachable) {
+ // This test handles a case where the exit block ends with OpUnreachable.
+
+ 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"
+ OpName %6 "fun("
+ OpName %10 "s"
+ OpName %17 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %11 = OpConstant %8 0
+ %13 = OpConstant %8 2
+ %15 = OpTypeBool
+ %16 = OpTypePointer Function %15
+ %18 = OpConstantTrue %15
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %17 = OpVariable %16 Function
+ OpStore %17 %18
+ %19 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %10 = OpVariable %9 Function
+ OpBranch %50
+ %50 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %8 %10
+ %14 = OpIAdd %8 %12 %13
+ OpStore %10 %14
+ OpUnreachable
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ TransformationDuplicateRegionWithSelection transformation_good_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 18, 501, 50, 50, {{50, 100}}, {{12, 201}, {14, 202}},
+ {{12, 301}, {14, 302}});
+ ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+ transformation_context));
+ transformation_good_1.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string expected_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"
+ OpName %6 "fun("
+ OpName %10 "s"
+ OpName %17 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %11 = OpConstant %8 0
+ %13 = OpConstant %8 2
+ %15 = OpTypeBool
+ %16 = OpTypePointer Function %15
+ %18 = OpConstantTrue %15
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %17 = OpVariable %16 Function
+ OpStore %17 %18
+ %19 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %10 = OpVariable %9 Function
+ OpBranch %500
+ %500 = OpLabel
+ OpSelectionMerge %501 None
+ OpBranchConditional %18 %50 %100
+ %50 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %8 %10
+ %14 = OpIAdd %8 %12 %13
+ OpStore %10 %14
+ OpBranch %501
+ %100 = OpLabel
+ OpStore %10 %11
+ %201 = OpLoad %8 %10
+ %202 = OpIAdd %8 %201 %13
+ OpStore %10 %202
+ OpBranch %501
+ %501 = OpLabel
+ %301 = OpPhi %8 %12 %50 %201 %100
+ %302 = OpPhi %8 %14 %50 %202 %100
+ OpUnreachable
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+TEST(TransformationDuplicateRegionWithSelectionTest,
+ ExitBlockTerminatorOpKill) {
+ // This test handles a case where the exit block ends with OpKill.
+
+ 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"
+ OpName %6 "fun("
+ OpName %10 "s"
+ OpName %17 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %11 = OpConstant %8 0
+ %13 = OpConstant %8 2
+ %15 = OpTypeBool
+ %16 = OpTypePointer Function %15
+ %18 = OpConstantTrue %15
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %17 = OpVariable %16 Function
+ OpStore %17 %18
+ %19 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %10 = OpVariable %9 Function
+ OpBranch %50
+ %50 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %8 %10
+ %14 = OpIAdd %8 %12 %13
+ OpStore %10 %14
+ OpKill
+ 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;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ TransformationDuplicateRegionWithSelection transformation_good_1 =
+ TransformationDuplicateRegionWithSelection(
+ 500, 18, 501, 50, 50, {{50, 100}}, {{12, 201}, {14, 202}},
+ {{12, 301}, {14, 302}});
+ ASSERT_TRUE(transformation_good_1.IsApplicable(context.get(),
+ transformation_context));
+ transformation_good_1.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string expected_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"
+ OpName %6 "fun("
+ OpName %10 "s"
+ OpName %17 "b"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %11 = OpConstant %8 0
+ %13 = OpConstant %8 2
+ %15 = OpTypeBool
+ %16 = OpTypePointer Function %15
+ %18 = OpConstantTrue %15
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %17 = OpVariable %16 Function
+ OpStore %17 %18
+ %19 = OpFunctionCall %2 %6
+ OpReturn
+ OpFunctionEnd
+ %6 = OpFunction %2 None %3
+ %7 = OpLabel
+ %10 = OpVariable %9 Function
+ OpBranch %500
+ %500 = OpLabel
+ OpSelectionMerge %501 None
+ OpBranchConditional %18 %50 %100
+ %50 = OpLabel
+ OpStore %10 %11
+ %12 = OpLoad %8 %10
+ %14 = OpIAdd %8 %12 %13
+ OpStore %10 %14
+ OpBranch %501
+ %100 = OpLabel
+ OpStore %10 %11
+ %201 = OpLoad %8 %10
+ %202 = OpIAdd %8 %201 %13
+ OpStore %10 %202
+ OpBranch %501
+ %501 = OpLabel
+ %301 = OpPhi %8 %12 %50 %201 %100
+ %302 = OpPhi %8 %14 %50 %202 %100
+ OpKill
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, expected_shader, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
