spirv-fuzz: TransformationWrapRegionInSelection (#3674)
Fixes #3675.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index cea05cf..61c9fb3 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -114,6 +114,7 @@
fuzzer_pass_swap_commutable_operands.h
fuzzer_pass_swap_conditional_branch_operands.h
fuzzer_pass_toggle_access_chain_instruction.h
+ fuzzer_pass_wrap_regions_in_selections.h
fuzzer_util.h
id_use_descriptor.h
instruction_descriptor.h
@@ -211,6 +212,7 @@
transformation_swap_conditional_branch_operands.h
transformation_toggle_access_chain_instruction.h
transformation_vector_shuffle.h
+ transformation_wrap_region_in_selection.h
uniform_buffer_element_descriptor.h
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
@@ -290,6 +292,7 @@
fuzzer_pass_swap_commutable_operands.cpp
fuzzer_pass_swap_conditional_branch_operands.cpp
fuzzer_pass_toggle_access_chain_instruction.cpp
+ fuzzer_pass_wrap_regions_in_selections.cpp
fuzzer_util.cpp
id_use_descriptor.cpp
instruction_descriptor.cpp
@@ -385,6 +388,7 @@
transformation_swap_conditional_branch_operands.cpp
transformation_toggle_access_chain_instruction.cpp
transformation_vector_shuffle.cpp
+ transformation_wrap_region_in_selection.cpp
uniform_buffer_element_descriptor.cpp
${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.cc
)
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 4c196b6..9680dda 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -83,6 +83,7 @@
#include "source/fuzz/fuzzer_pass_swap_commutable_operands.h"
#include "source/fuzz/fuzzer_pass_swap_conditional_branch_operands.h"
#include "source/fuzz/fuzzer_pass_toggle_access_chain_instruction.h"
+#include "source/fuzz/fuzzer_pass_wrap_regions_in_selections.h"
#include "source/fuzz/pass_management/repeated_pass_manager.h"
#include "source/fuzz/pass_management/repeated_pass_manager_looped_with_recommendations.h"
#include "source/fuzz/pass_management/repeated_pass_manager_random_with_recommendations.h"
@@ -294,6 +295,7 @@
MaybeAddRepeatedPass<FuzzerPassSplitBlocks>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassSwapBranchConditionalOperands>(
&pass_instances);
+ MaybeAddRepeatedPass<FuzzerPassWrapRegionsInSelections>(&pass_instances);
// There is a theoretical possibility that no pass instances were created
// until now; loop again if so.
} while (pass_instances.GetPasses().empty());
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 9e9e78d..5151117 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -134,6 +134,8 @@
{10, 70};
const std::pair<uint32_t, uint32_t> kChanceOfTogglingAccessChainInstruction = {
20, 90};
+const std::pair<uint32_t, uint32_t> kChanceOfWrappingRegionInSelection = {70,
+ 90};
// Default limits for various quantities that are chosen during fuzzing.
// Keep them in alphabetical order.
@@ -320,6 +322,8 @@
ChooseBetweenMinAndMax(kChanceOfSwappingConditionalBranchOperands);
chance_of_toggling_access_chain_instruction_ =
ChooseBetweenMinAndMax(kChanceOfTogglingAccessChainInstruction);
+ chance_of_wrapping_region_in_selection_ =
+ ChooseBetweenMinAndMax(kChanceOfWrappingRegionInSelection);
}
FuzzerContext::~FuzzerContext() = default;
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index b6f466f..213d51b 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -307,6 +307,9 @@
uint32_t GetChanceOfTogglingAccessChainInstruction() {
return chance_of_toggling_access_chain_instruction_;
}
+ uint32_t GetChanceOfWrappingRegionInSelection() {
+ return chance_of_wrapping_region_in_selection_;
+ }
// Other functions to control transformations. Keep them in alphabetical
// order.
@@ -472,6 +475,7 @@
uint32_t chance_of_splitting_block_;
uint32_t chance_of_swapping_conditional_branch_operands_;
uint32_t chance_of_toggling_access_chain_instruction_;
+ uint32_t chance_of_wrapping_region_in_selection_;
// Limits associated with various quantities for which random values are
// chosen during fuzzing.
diff --git a/source/fuzz/fuzzer_pass_wrap_regions_in_selections.cpp b/source/fuzz/fuzzer_pass_wrap_regions_in_selections.cpp
new file mode 100644
index 0000000..e6cdca4
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_wrap_regions_in_selections.cpp
@@ -0,0 +1,140 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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_wrap_regions_in_selections.h"
+
+#include "source/fuzz/fuzzer_context.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "source/fuzz/transformation_split_block.h"
+#include "source/fuzz/transformation_wrap_region_in_selection.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassWrapRegionsInSelections::FuzzerPassWrapRegionsInSelections(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassWrapRegionsInSelections::~FuzzerPassWrapRegionsInSelections() =
+ default;
+
+void FuzzerPassWrapRegionsInSelections::Apply() {
+ for (auto& function : *GetIRContext()->module()) {
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfWrappingRegionInSelection())) {
+ continue;
+ }
+
+ // It is easier to select an element at random from a vector than from an
+ // instruction list.
+ std::vector<opt::BasicBlock*> header_block_candidates;
+ for (auto& block : function) {
+ header_block_candidates.push_back(&block);
+ }
+
+ if (header_block_candidates.empty()) {
+ continue;
+ }
+
+ // Try to get a header block candidate that will increase the chances of the
+ // transformation being applicable.
+ auto* header_block_candidate = MaybeGetHeaderBlockCandidate(
+ header_block_candidates[GetFuzzerContext()->RandomIndex(
+ header_block_candidates)]);
+ if (!header_block_candidate) {
+ continue;
+ }
+
+ std::vector<opt::BasicBlock*> merge_block_candidates;
+ for (auto& block : function) {
+ if (GetIRContext()->GetDominatorAnalysis(&function)->StrictlyDominates(
+ header_block_candidate, &block) &&
+ GetIRContext()
+ ->GetPostDominatorAnalysis(&function)
+ ->StrictlyDominates(&block, header_block_candidate)) {
+ merge_block_candidates.push_back(&block);
+ }
+ }
+
+ if (merge_block_candidates.empty()) {
+ continue;
+ }
+
+ // Try to get a merge block candidate that will increase the chances of the
+ // transformation being applicable.
+ auto* merge_block_candidate = MaybeGetMergeBlockCandidate(
+ merge_block_candidates[GetFuzzerContext()->RandomIndex(
+ merge_block_candidates)]);
+ if (!merge_block_candidate) {
+ continue;
+ }
+
+ if (!TransformationWrapRegionInSelection::IsApplicableToBlockRange(
+ GetIRContext(), header_block_candidate->id(),
+ merge_block_candidate->id())) {
+ continue;
+ }
+
+ // This boolean constant will be used as a condition for the
+ // OpBranchConditional instruction. We mark it as irrelevant to be able to
+ // replace it with a more interesting value later.
+ auto branch_condition = GetFuzzerContext()->ChooseEven();
+ FindOrCreateBoolConstant(branch_condition, true);
+
+ ApplyTransformation(TransformationWrapRegionInSelection(
+ header_block_candidate->id(), merge_block_candidate->id(),
+ branch_condition));
+ }
+}
+
+opt::BasicBlock*
+FuzzerPassWrapRegionsInSelections::MaybeGetHeaderBlockCandidate(
+ opt::BasicBlock* header_block_candidate) {
+ // Try to create a preheader if |header_block_candidate| is a loop header.
+ if (header_block_candidate->IsLoopHeader()) {
+ // GetOrCreateSimpleLoopPreheader only supports reachable blocks.
+ return GetIRContext()->cfg()->preds(header_block_candidate->id()).size() ==
+ 1
+ ? nullptr
+ : GetOrCreateSimpleLoopPreheader(header_block_candidate->id());
+ }
+
+ // Try to split |header_block_candidate| if it's already a header block.
+ if (header_block_candidate->GetMergeInst()) {
+ SplitBlockAfterOpPhiOrOpVariable(header_block_candidate->id());
+ }
+
+ return header_block_candidate;
+}
+
+opt::BasicBlock* FuzzerPassWrapRegionsInSelections::MaybeGetMergeBlockCandidate(
+ opt::BasicBlock* merge_block_candidate) {
+ // If |merge_block_candidate| is a merge block of some construct, try to split
+ // it and return a newly created block.
+ if (GetIRContext()->GetStructuredCFGAnalysis()->IsMergeBlock(
+ merge_block_candidate->id())) {
+ // We can't split a merge block if it's also a loop header.
+ return merge_block_candidate->IsLoopHeader()
+ ? nullptr
+ : SplitBlockAfterOpPhiOrOpVariable(merge_block_candidate->id());
+ }
+
+ return merge_block_candidate;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_wrap_regions_in_selections.h b/source/fuzz/fuzzer_pass_wrap_regions_in_selections.h
new file mode 100644
index 0000000..eb28d20
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_wrap_regions_in_selections.h
@@ -0,0 +1,55 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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_WRAP_REGIONS_IN_SELECTIONS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_WRAP_REGIONS_IN_SELECTIONS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Randomly wraps a region of blocks in every function into a selection
+// construct.
+class FuzzerPassWrapRegionsInSelections : public FuzzerPass {
+ public:
+ FuzzerPassWrapRegionsInSelections(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassWrapRegionsInSelections() override;
+
+ void Apply() override;
+
+ private:
+ // Tries to adjust |header_block_candidate| such that
+ // TransformationWrapRegionInSelection has higher chances of being
+ // applied. In particular, tries to split |header_block_candidate| if it's
+ // already a header block of some other construct.
+ opt::BasicBlock* MaybeGetHeaderBlockCandidate(
+ opt::BasicBlock* header_block_candidate);
+
+ // Tries to adjust |merge_block_candidate| such that
+ // TransformationWrapRegionInSelection has higher chances of being
+ // applied. In particular, tries to split |merge_block_candidate| if it's
+ // already a merge block of some other construct.
+ opt::BasicBlock* MaybeGetMergeBlockCandidate(
+ opt::BasicBlock* merge_block_candidate);
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_WRAP_REGIONS_IN_SELECTIONS_H_
diff --git a/source/fuzz/pass_management/repeated_pass_instances.h b/source/fuzz/pass_management/repeated_pass_instances.h
index 57820a2..ed55741 100644
--- a/source/fuzz/pass_management/repeated_pass_instances.h
+++ b/source/fuzz/pass_management/repeated_pass_instances.h
@@ -67,6 +67,7 @@
#include "source/fuzz/fuzzer_pass_replace_params_with_struct.h"
#include "source/fuzz/fuzzer_pass_split_blocks.h"
#include "source/fuzz/fuzzer_pass_swap_conditional_branch_operands.h"
+#include "source/fuzz/fuzzer_pass_wrap_regions_in_selections.h"
namespace spvtools {
namespace fuzz {
@@ -156,6 +157,7 @@
REPEATED_PASS_INSTANCE(ReplaceParamsWithStruct);
REPEATED_PASS_INSTANCE(SplitBlocks);
REPEATED_PASS_INSTANCE(SwapBranchConditionalOperands);
+ REPEATED_PASS_INSTANCE(WrapRegionsInSelections);
#undef REPEATED_PASS_INSTANCE
public:
diff --git a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
index 8c03807..8597de2 100644
--- a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
+++ b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
@@ -120,7 +120,8 @@
// outlining functions.
return RandomOrderAndNonNull(
{pass_instances_->GetDuplicateRegionsWithSelections(),
- pass_instances_->GetOutlineFunctions()});
+ pass_instances_->GetOutlineFunctions(),
+ pass_instances_->GetWrapRegionsInSelections()});
}
if (&pass == pass_instances_->GetAddLoopsToCreateIntConstantSynonyms()) {
// - New synonyms can be applied
@@ -308,6 +309,16 @@
// No obvious follow-on passes
return {};
}
+ if (&pass == pass_instances_->GetWrapRegionsInSelections()) {
+ // - This pass uses an irrelevant boolean constant - we can replace it with
+ // something more interesting.
+ // - We can obfuscate that very constant as well.
+ // - We can flatten created selection construct.
+ return RandomOrderAndNonNull(
+ {pass_instances_->GetObfuscateConstants(),
+ pass_instances_->GetReplaceIrrelevantIds(),
+ pass_instances_->GetFlattenConditionalBranches()});
+ }
assert(false && "Unreachable: every fuzzer pass should be dealt with.");
return {};
}
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 3c8ab9b..de2f843 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -498,6 +498,7 @@
TransformationFlattenConditionalBranch flatten_conditional_branch = 76;
TransformationAddBitInstructionSynonym add_bit_instruction_synonym = 77;
TransformationAddLoopToCreateIntConstantSynonym add_loop_to_create_int_constant_synonym = 78;
+ TransformationWrapRegionInSelection wrap_region_in_selection = 79;
// Add additional option using the next available number.
}
}
@@ -2072,3 +2073,33 @@
repeated uint32 component = 5;
}
+
+message TransformationWrapRegionInSelection {
+
+ // Transforms a single-entry-single-exit region R into
+ // if (|branch_condition|) { R } else { R }
+ // The entry block for R becomes a selection header and
+ // the exit block - a selection merge.
+ //
+ // Note that the region R is not duplicated. Thus, the effect of
+ // this transformation can be represented as follows:
+ // entry
+ // entry / \
+ // | \ /
+ // R --> R
+ // | |
+ // exit exit
+
+ // This behaviour is different from TransformationDuplicateRegionWithSelection
+ // that copies the blocks in R.
+
+ // The entry block for the region R.
+ uint32 region_entry_block_id = 1;
+
+ // The exit block for the region R.
+ uint32 region_exit_block_id = 2;
+
+ // Boolean value for the condition expression.
+ bool branch_condition = 3;
+
+}
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index 7301a89..ea7c97c 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -95,6 +95,7 @@
#include "source/fuzz/transformation_swap_conditional_branch_operands.h"
#include "source/fuzz/transformation_toggle_access_chain_instruction.h"
#include "source/fuzz/transformation_vector_shuffle.h"
+#include "source/fuzz/transformation_wrap_region_in_selection.h"
#include "source/util/make_unique.h"
namespace spvtools {
@@ -342,6 +343,9 @@
message.toggle_access_chain_instruction());
case protobufs::Transformation::TransformationCase::kVectorShuffle:
return MakeUnique<TransformationVectorShuffle>(message.vector_shuffle());
+ case protobufs::Transformation::TransformationCase::kWrapRegionInSelection:
+ return MakeUnique<TransformationWrapRegionInSelection>(
+ message.wrap_region_in_selection());
case protobufs::Transformation::TRANSFORMATION_NOT_SET:
assert(false && "An unset transformation was encountered.");
return nullptr;
diff --git a/source/fuzz/transformation_wrap_region_in_selection.cpp b/source/fuzz/transformation_wrap_region_in_selection.cpp
new file mode 100644
index 0000000..9924e36
--- /dev/null
+++ b/source/fuzz/transformation_wrap_region_in_selection.cpp
@@ -0,0 +1,166 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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_wrap_region_in_selection.h"
+
+#include "source/fuzz/fuzzer_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationWrapRegionInSelection::TransformationWrapRegionInSelection(
+ const protobufs::TransformationWrapRegionInSelection& message)
+ : message_(message) {}
+
+TransformationWrapRegionInSelection::TransformationWrapRegionInSelection(
+ uint32_t region_entry_block_id, uint32_t region_exit_block_id,
+ bool branch_condition) {
+ message_.set_region_entry_block_id(region_entry_block_id);
+ message_.set_region_exit_block_id(region_exit_block_id);
+ message_.set_branch_condition(branch_condition);
+}
+
+bool TransformationWrapRegionInSelection::IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const {
+ // Check that it is possible to outline a region of blocks without breaking
+ // domination and structured control flow rules.
+ if (!IsApplicableToBlockRange(ir_context, message_.region_entry_block_id(),
+ message_.region_exit_block_id())) {
+ return false;
+ }
+
+ // There must exist an irrelevant boolean constant to be used as a condition
+ // in the OpBranchConditional instruction.
+ return fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
+ message_.branch_condition(),
+ true) != 0;
+}
+
+void TransformationWrapRegionInSelection::Apply(
+ opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const {
+ auto* new_header_block =
+ ir_context->cfg()->block(message_.region_entry_block_id());
+ assert(new_header_block->terminator()->opcode() == SpvOpBranch &&
+ "This condition should have been checked in the IsApplicable");
+
+ const auto successor_id =
+ new_header_block->terminator()->GetSingleWordInOperand(0);
+
+ // Change |entry_block|'s terminator to |OpBranchConditional|.
+ new_header_block->terminator()->SetOpcode(SpvOpBranchConditional);
+ new_header_block->terminator()->SetInOperands(
+ {{SPV_OPERAND_TYPE_ID,
+ {fuzzerutil::MaybeGetBoolConstant(ir_context, *transformation_context,
+ message_.branch_condition(), true)}},
+ {SPV_OPERAND_TYPE_ID, {successor_id}},
+ {SPV_OPERAND_TYPE_ID, {successor_id}}});
+
+ // Insert OpSelectionMerge before the terminator.
+ new_header_block->terminator()->InsertBefore(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpSelectionMerge, 0, 0,
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_ID, {message_.region_exit_block_id()}},
+ {SPV_OPERAND_TYPE_SELECTION_CONTROL,
+ {SpvSelectionControlMaskNone}}}));
+
+ // We've change the module so we must invalidate analyses.
+ ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+protobufs::Transformation TransformationWrapRegionInSelection::ToMessage()
+ const {
+ protobufs::Transformation result;
+ *result.mutable_wrap_region_in_selection() = message_;
+ return result;
+}
+
+bool TransformationWrapRegionInSelection::IsApplicableToBlockRange(
+ opt::IRContext* ir_context, uint32_t header_block_candidate_id,
+ uint32_t merge_block_candidate_id) {
+ // Check that |header_block_candidate_id| and |merge_block_candidate_id| are
+ // valid.
+ const auto* header_block_candidate =
+ fuzzerutil::MaybeFindBlock(ir_context, header_block_candidate_id);
+ if (!header_block_candidate) {
+ return false;
+ }
+
+ const auto* merge_block_candidate =
+ fuzzerutil::MaybeFindBlock(ir_context, merge_block_candidate_id);
+ if (!merge_block_candidate) {
+ return false;
+ }
+
+ // |header_block_candidate| and |merge_block_candidate| must be from the same
+ // function.
+ if (header_block_candidate->GetParent() !=
+ merge_block_candidate->GetParent()) {
+ return false;
+ }
+
+ const auto* dominator_analysis =
+ ir_context->GetDominatorAnalysis(header_block_candidate->GetParent());
+ const auto* postdominator_analysis =
+ ir_context->GetPostDominatorAnalysis(header_block_candidate->GetParent());
+
+ if (!dominator_analysis->StrictlyDominates(header_block_candidate,
+ merge_block_candidate) ||
+ !postdominator_analysis->StrictlyDominates(merge_block_candidate,
+ header_block_candidate)) {
+ return false;
+ }
+
+ // |header_block_candidate| can't be a header since we are about to make it
+ // one.
+ if (header_block_candidate->GetMergeInst()) {
+ return false;
+ }
+
+ // |header_block_candidate| must have an OpBranch terminator.
+ if (header_block_candidate->terminator()->opcode() != SpvOpBranch) {
+ return false;
+ }
+
+ // Every header block must have a unique merge block. Thus,
+ // |merge_block_candidate| can't be a merge block of some other header.
+ auto* structured_cfg = ir_context->GetStructuredCFGAnalysis();
+ if (structured_cfg->IsMergeBlock(merge_block_candidate_id)) {
+ return false;
+ }
+
+ // |header_block_candidate|'s containing construct must also contain
+ // |merge_block_candidate|.
+ //
+ // ContainingConstruct will return the id of a loop header for a block in the
+ // loop's continue construct. Thus, we must also check the case when one of
+ // the candidates is in continue construct and the other one is not.
+ if (structured_cfg->ContainingConstruct(header_block_candidate_id) !=
+ structured_cfg->ContainingConstruct(merge_block_candidate_id) ||
+ structured_cfg->IsInContinueConstruct(header_block_candidate_id) !=
+ structured_cfg->IsInContinueConstruct(merge_block_candidate_id)) {
+ return false;
+ }
+
+ return true;
+}
+
+std::unordered_set<uint32_t> TransformationWrapRegionInSelection::GetFreshIds()
+ const {
+ return std::unordered_set<uint32_t>();
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_wrap_region_in_selection.h b/source/fuzz/transformation_wrap_region_in_selection.h
new file mode 100644
index 0000000..57f4f64
--- /dev/null
+++ b/source/fuzz/transformation_wrap_region_in_selection.h
@@ -0,0 +1,88 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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_WRAP_REGION_IN_SELECTION_H_
+#define SOURCE_FUZZ_TRANSFORMATION_WRAP_REGION_IN_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 TransformationWrapRegionInSelection : public Transformation {
+ public:
+ explicit TransformationWrapRegionInSelection(
+ const protobufs::TransformationWrapRegionInSelection& message);
+
+ TransformationWrapRegionInSelection(uint32_t region_entry_block_id,
+ uint32_t region_exit_block_id,
+ bool branch_condition);
+
+ // - It should be possible to apply this transformation to a
+ // single-exit-single-entry region of blocks dominated by
+ // |region_entry_block_id| and postdominated by |region_exit_block_id|
+ // (see IsApplicableToBlockRange method for further details).
+ //
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3828):
+ // Consider applying this transformation to non-single-entry-single-exit
+ // regions of blocks.
+ // - There must exist an irrelevant boolean constant with value
+ // |branch_condition|.
+ bool IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const override;
+
+ // - Transforms |region_entry_block_id| into a selection header with both
+ // branches pointing to the block's successor.
+ // - |branch_condition| is used as a condition in the header's
+ // OpBranchConditional instruction.
+ // - Transforms |region_exit_block_id| into a merge block of the selection's
+ // header.
+ void Apply(opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const override;
+
+ protobufs::Transformation ToMessage() const override;
+
+ // Returns true if it's possible to apply this transformation to the
+ // single-exit-single-entry region of blocks starting with
+ // |header_block_candidate_id| and ending with |merge_block_candidate_id|.
+ // Concretely:
+ // - Both |header_block_candidate_id| and |merge_block_candidate_id| must be
+ // result ids of some blocks in the module.
+ // - Both blocks must belong to the same function.
+ // - |header_block_candidate_id| must strictly dominate
+ // |merge_block_candidate_id| and |merge_block_candidate_id| must strictly
+ // postdominate |header_block_candidate_id|.
+ // - |header_block_candidate_id| can't be a header block of any construct.
+ // - |header_block_candidate_id|'s terminator must be an OpBranch.
+ // - |merge_block_candidate_id| can't be a merge block of any other construct.
+ // - Both |header_block_candidate_id| and |merge_block_candidate_id| must be
+ // inside the same construct if any.
+ static bool IsApplicableToBlockRange(opt::IRContext* ir_context,
+ uint32_t header_block_candidate_id,
+ uint32_t merge_block_candidate_id);
+
+ std::unordered_set<uint32_t> GetFreshIds() const override;
+
+ private:
+ protobufs::TransformationWrapRegionInSelection message_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_WRAP_REGION_IN_SELECTION_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index a918b24..924addb 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -107,6 +107,7 @@
transformation_toggle_access_chain_instruction_test.cpp
transformation_record_synonymous_constants_test.cpp
transformation_vector_shuffle_test.cpp
+ transformation_wrap_region_in_selection_test.cpp
uniform_buffer_element_descriptor_test.cpp)
if (${SPIRV_ENABLE_LONG_FUZZER_TESTS})
diff --git a/test/fuzz/transformation_wrap_region_in_selection_test.cpp b/test/fuzz/transformation_wrap_region_in_selection_test.cpp
new file mode 100644
index 0000000..5881b3b
--- /dev/null
+++ b/test/fuzz/transformation_wrap_region_in_selection_test.cpp
@@ -0,0 +1,262 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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_wrap_region_in_selection.h"
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationWrapRegionInSelectionTest, BasicTest) {
+ 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
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %6
+
+ %6 = OpLabel
+ OpSelectionMerge %12 None
+ OpBranchConditional %8 %11 %12
+ %11 = OpLabel
+ OpReturn
+
+ %12 = OpLabel
+ OpSelectionMerge %15 None
+ OpBranchConditional %8 %13 %14
+ %13 = OpLabel
+ OpBranch %15
+ %14 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ OpBranch %16
+
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+
+ %9 = OpFunction %2 None %3
+ %10 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %23 %22 None
+ OpBranch %21
+ %21 = OpLabel
+ OpBranchConditional %8 %24 %23
+ %24 = OpLabel
+ OpBranch %22
+
+ ; continue target
+ %22 = OpLabel
+ OpLoopMerge %25 %28 None
+ OpBranchConditional %8 %27 %25
+ %27 = OpLabel
+ OpBranch %28
+ %28 = OpLabel
+ OpBranch %22
+ %25 = OpLabel
+ OpBranch %20
+
+ ; merge block
+ %23 = OpLabel
+ OpBranch %26
+
+ %26 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // Boolean constant does not exist.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(5, 6, false)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Irrelevant constant does not exist.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(5, 6, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ transformation_context.GetFactManager()->AddFactIdIsIrrelevant(8);
+
+ // Block ids are invalid.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(100, 6, true)
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationWrapRegionInSelection(5, 100, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Blocks are from different functions.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(5, 10, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Header block candidate does not dominate merge block candidate.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(13, 16, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Header block candidate does not *strictly* dominate merge block candidate.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(5, 5, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Merge block candidate does not postdominate header block candidate.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(5, 16, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Header block candidate is already a header block of some other construct.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(12, 16, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Header block's terminator is not an OpBranch.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(21, 24, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Merge block candidate is already a merge block of some other construct.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(5, 15, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Header block candidate and merge block candidate are in different
+ // constructs.
+ ASSERT_FALSE(TransformationWrapRegionInSelection(10, 21, true)
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationWrapRegionInSelection(24, 25, true)
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationWrapRegionInSelection(24, 22, true)
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationWrapRegionInSelection(24, 27, true)
+ .IsApplicable(context.get(), transformation_context));
+
+ {
+ // Header block candidate can be a merge block of some existing construct.
+ TransformationWrapRegionInSelection transformation(15, 16, true);
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+ {
+ // Merge block candidate can be a header block of some existing construct.
+ TransformationWrapRegionInSelection transformation(5, 6, true);
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+ {
+ // Wrap a loop construct.
+ TransformationWrapRegionInSelection transformation(10, 26, true);
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ 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
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %6 None
+ OpBranchConditional %8 %6 %6
+
+ %6 = OpLabel
+ OpSelectionMerge %12 None
+ OpBranchConditional %8 %11 %12
+ %11 = OpLabel
+ OpReturn
+
+ %12 = OpLabel
+ OpSelectionMerge %15 None
+ OpBranchConditional %8 %13 %14
+ %13 = OpLabel
+ OpBranch %15
+ %14 = OpLabel
+ OpBranch %15
+
+ %15 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %8 %16 %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+
+ %9 = OpFunction %2 None %3
+ %10 = OpLabel
+ OpSelectionMerge %26 None
+ OpBranchConditional %8 %20 %20
+
+ %20 = OpLabel
+ OpLoopMerge %23 %22 None
+ OpBranch %21
+ %21 = OpLabel
+ OpBranchConditional %8 %24 %23
+ %24 = OpLabel
+ OpBranch %22
+
+ ; continue target
+ %22 = OpLabel
+ OpLoopMerge %25 %28 None
+ OpBranchConditional %8 %27 %25
+ %27 = OpLabel
+ OpBranch %28
+ %28 = OpLabel
+ OpBranch %22
+ %25 = OpLabel
+ OpBranch %20
+
+ ; merge block
+ %23 = OpLabel
+ OpBranch %26
+
+ %26 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
