spirv-fuzz: Transformation to flatten conditional branch (#3667)
This transformation, given the header of a selection construct with
branching instruction OpBranchConditional, flattens it.
Side-effecting operations such as OpLoad, OpStore and OpFunctionCall
are enclosed within smaller conditionals.
It is applicable if the construct does not contain inner selection
constructs or loops, or atomic or barrier instructions.
The corresponding fuzzer pass looks for selection headers and
tries to flatten them.
Needed for the issue #3544, but it does not fix it completely.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index e1cc925..ca4b221 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -37,6 +37,7 @@
set(SPIRV_TOOLS_FUZZ_SOURCES
call_graph.h
+ comparator_deep_blocks_first.h
counter_overflow_id_source.h
data_descriptor.h
equivalence_relation.h
@@ -81,6 +82,7 @@
fuzzer_pass_copy_objects.h
fuzzer_pass_donate_modules.h
fuzzer_pass_duplicate_regions_with_selections.h
+ fuzzer_pass_flatten_conditional_branches.h
fuzzer_pass_inline_functions.h
fuzzer_pass_invert_comparison_operators.h
fuzzer_pass_interchange_signedness_of_integer_operands.h
@@ -159,6 +161,7 @@
transformation_context.h
transformation_duplicate_region_with_selection.h
transformation_equation_instruction.h
+ transformation_flatten_conditional_branch.h
transformation_function_call.h
transformation_inline_function.h
transformation_invert_comparison_operator.h
@@ -244,6 +247,7 @@
fuzzer_pass_copy_objects.cpp
fuzzer_pass_donate_modules.cpp
fuzzer_pass_duplicate_regions_with_selections.cpp
+ fuzzer_pass_flatten_conditional_branches.cpp
fuzzer_pass_inline_functions.cpp
fuzzer_pass_invert_comparison_operators.cpp
fuzzer_pass_interchange_signedness_of_integer_operands.cpp
@@ -321,6 +325,7 @@
transformation_context.cpp
transformation_duplicate_region_with_selection.cpp
transformation_equation_instruction.cpp
+ transformation_flatten_conditional_branch.cpp
transformation_function_call.cpp
transformation_inline_function.cpp
transformation_invert_comparison_operator.cpp
diff --git a/source/fuzz/comparator_deep_blocks_first.h b/source/fuzz/comparator_deep_blocks_first.h
new file mode 100644
index 0000000..be63d1a
--- /dev/null
+++ b/source/fuzz/comparator_deep_blocks_first.h
@@ -0,0 +1,53 @@
+// 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_COMPARATOR_BLOCKS_DEEP_FIRST_H_
+#define SOURCE_FUZZ_COMPARATOR_BLOCKS_DEEP_FIRST_H_
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Comparator for blocks, comparing them based on how deep they are nested
+// inside selection or loop constructs. Deeper blocks are considered less than
+// ones that are not as deep. The blocks are required to be in the same
+// function.
+class ComparatorDeepBlocksFirst {
+ public:
+ explicit ComparatorDeepBlocksFirst(opt::IRContext* ir_context)
+ : ir_context_(ir_context) {}
+
+ bool operator()(uint32_t bb1, uint32_t bb2) const {
+ return this->operator()(fuzzerutil::MaybeFindBlock(ir_context_, bb1),
+ fuzzerutil::MaybeFindBlock(ir_context_, bb2));
+ }
+
+ bool operator()(const opt::BasicBlock* bb1, opt::BasicBlock* bb2) const {
+ assert(bb1 && bb2 && "The blocks must exist.");
+ assert(bb1->GetParent() == bb2->GetParent() &&
+ "The blocks must be in the same functions.");
+ return ir_context_->GetStructuredCFGAnalysis()->NestingDepth(bb1->id()) >
+ ir_context_->GetStructuredCFGAnalysis()->NestingDepth(bb2->id());
+ }
+
+ private:
+ opt::IRContext* ir_context_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_COMPARATOR_BLOCKS_DEEP_FIRST_H_
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 8b9c9cb..5c4ceca 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -50,6 +50,7 @@
#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_flatten_conditional_branches.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"
@@ -276,6 +277,9 @@
MaybeAddPass<FuzzerPassDuplicateRegionsWithSelections>(
&passes, ir_context.get(), &transformation_context, &fuzzer_context,
transformation_sequence_out);
+ MaybeAddPass<FuzzerPassFlattenConditionalBranches>(
+ &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 869cb5a..1f3baeb 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -72,6 +72,8 @@
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> kChanceOfFlatteningConditionalBranch = {45,
+ 95};
const std::pair<uint32_t, uint32_t> kChanceOfGoingDeeperToInsertInComposite = {
30, 70};
const std::pair<uint32_t, uint32_t> kChanceOfGoingDeeperWhenMakingAccessChain =
@@ -234,6 +236,8 @@
ChooseBetweenMinAndMax(kChanceOfDonatingAdditionalModule);
chance_of_duplicating_region_with_selection_ =
ChooseBetweenMinAndMax(kChanceOfDuplicatingRegionWithSelection);
+ chance_of_flattening_conditional_branch_ =
+ ChooseBetweenMinAndMax(kChanceOfFlatteningConditionalBranch);
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 8f045c3..898db1f 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -201,6 +201,9 @@
uint32_t GetChanceOfDuplicatingRegionWithSelection() {
return chance_of_duplicating_region_with_selection_;
}
+ uint32_t GetChanceOfFlatteningConditionalBranch() {
+ return chance_of_flattening_conditional_branch_;
+ }
uint32_t GetChanceOfGoingDeeperToInsertInComposite() {
return chance_of_going_deeper_to_insert_in_composite_;
}
@@ -410,6 +413,7 @@
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_flattening_conditional_branch_;
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.cpp b/source/fuzz/fuzzer_pass.cpp
index a30d790..a6a698e 100644
--- a/source/fuzz/fuzzer_pass.cpp
+++ b/source/fuzz/fuzzer_pass.cpp
@@ -516,6 +516,26 @@
}
}
+bool FuzzerPass::CanFindOrCreateZeroConstant(const opt::analysis::Type& type) {
+ switch (type.kind()) {
+ case opt::analysis::Type::kBool:
+ case opt::analysis::Type::kInteger:
+ case opt::analysis::Type::kFloat:
+ case opt::analysis::Type::kArray:
+ case opt::analysis::Type::kMatrix:
+ case opt::analysis::Type::kVector:
+ return true;
+ case opt::analysis::Type::kStruct:
+ return std::all_of(type.AsStruct()->element_types().begin(),
+ type.AsStruct()->element_types().end(),
+ [this](const opt::analysis::Type* element_type) {
+ return CanFindOrCreateZeroConstant(*element_type);
+ });
+ default:
+ return false;
+ }
+}
+
void FuzzerPass::MaybeAddUseToReplace(
opt::Instruction* use_inst, uint32_t use_index, uint32_t replacement_id,
std::vector<std::pair<protobufs::IdUseDescriptor, uint32_t>>*
diff --git a/source/fuzz/fuzzer_pass.h b/source/fuzz/fuzzer_pass.h
index 423b443..1e6992a 100644
--- a/source/fuzz/fuzzer_pass.h
+++ b/source/fuzz/fuzzer_pass.h
@@ -273,6 +273,9 @@
uint32_t FindOrCreateZeroConstant(uint32_t scalar_or_composite_type_id,
bool is_irrelevant);
+ // Checks if FindOrCreateZeroConstant can be called on this type.
+ bool CanFindOrCreateZeroConstant(const opt::analysis::Type& type);
+
// Adds a pair (id_use_descriptor, |replacement_id|) to the vector
// |uses_to_replace|, where id_use_descriptor is the id use descriptor
// representing the usage of an id in the |use_inst| instruction, at operand
diff --git a/source/fuzz/fuzzer_pass_flatten_conditional_branches.cpp b/source/fuzz/fuzzer_pass_flatten_conditional_branches.cpp
new file mode 100644
index 0000000..69cd0aa
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_flatten_conditional_branches.cpp
@@ -0,0 +1,124 @@
+// 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_flatten_conditional_branches.h"
+
+#include "source/fuzz/comparator_deep_blocks_first.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "source/fuzz/transformation_flatten_conditional_branch.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass that randomly selects conditional branches to flatten and
+// flattens them, if possible.
+FuzzerPassFlattenConditionalBranches::FuzzerPassFlattenConditionalBranches(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassFlattenConditionalBranches::~FuzzerPassFlattenConditionalBranches() =
+ default;
+
+void FuzzerPassFlattenConditionalBranches::Apply() {
+ // Get all the selection headers that we want to flatten. We need to collect
+ // all of them first, because, since we are changing the structure of the
+ // module, it's not safe to modify them while iterating.
+ std::vector<opt::BasicBlock*> selection_headers;
+ for (auto& function : *GetIRContext()->module()) {
+ for (auto& block : function) {
+ // Randomly decide whether to consider this block.
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfFlatteningConditionalBranch())) {
+ continue;
+ }
+
+ // Only consider this block if it is the header of a conditional.
+ if (block.GetMergeInst() &&
+ block.GetMergeInst()->opcode() == SpvOpSelectionMerge &&
+ block.terminator()->opcode() == SpvOpBranchConditional) {
+ selection_headers.emplace_back(&block);
+ }
+ }
+ }
+
+ // Sort the headers so that those that are more deeply nested are considered
+ // first, possibly enabling outer conditionals to be flattened.
+ std::sort(selection_headers.begin(), selection_headers.end(),
+ ComparatorDeepBlocksFirst(GetIRContext()));
+
+ // Apply the transformation to the headers which can be flattened.
+ for (auto header : selection_headers) {
+ // Make a set to keep track of the instructions that need fresh ids.
+ std::set<opt::Instruction*> instructions_that_need_ids;
+
+ // Do not consider this header if the conditional cannot be flattened.
+ if (!TransformationFlattenConditionalBranch::
+ GetProblematicInstructionsIfConditionalCanBeFlattened(
+ GetIRContext(), header, &instructions_that_need_ids)) {
+ continue;
+ }
+
+ // Some instructions will require to be enclosed inside conditionals because
+ // they have side effects (for example, loads and stores). Some of this have
+ // no result id, so we require instruction descriptors to identify them.
+ // Each of them is associated with the necessary ids for it via a
+ // SideEffectWrapperInfo message.
+ std::vector<protobufs::SideEffectWrapperInfo> wrappers_info;
+
+ for (auto instruction : instructions_that_need_ids) {
+ protobufs::SideEffectWrapperInfo wrapper_info;
+ *wrapper_info.mutable_instruction() =
+ MakeInstructionDescriptor(GetIRContext(), instruction);
+ wrapper_info.set_merge_block_id(GetFuzzerContext()->GetFreshId());
+ wrapper_info.set_execute_block_id(GetFuzzerContext()->GetFreshId());
+
+ // If the instruction has a non-void result id, we need to define more
+ // fresh ids and provide an id of the suitable type whose value can be
+ // copied in order to create a placeholder id.
+ if (TransformationFlattenConditionalBranch::InstructionNeedsPlaceholder(
+ GetIRContext(), *instruction)) {
+ wrapper_info.set_actual_result_id(GetFuzzerContext()->GetFreshId());
+ wrapper_info.set_alternative_block_id(GetFuzzerContext()->GetFreshId());
+ wrapper_info.set_placeholder_result_id(
+ GetFuzzerContext()->GetFreshId());
+
+ // The id will be a zero constant if the type allows it, and an OpUndef
+ // otherwise. We want to avoid using OpUndef, if possible, to avoid
+ // undefined behaviour in the module as much as possible.
+ if (CanFindOrCreateZeroConstant(
+ *GetIRContext()->get_type_mgr()->GetType(
+ instruction->type_id()))) {
+ wrapper_info.set_value_to_copy_id(
+ FindOrCreateZeroConstant(instruction->type_id(), true));
+ } else {
+ wrapper_info.set_value_to_copy_id(
+ FindOrCreateGlobalUndef(instruction->type_id()));
+ }
+ }
+
+ wrappers_info.emplace_back(wrapper_info);
+ }
+
+ // Apply the transformation, evenly choosing whether to lay out the true
+ // branch or the false branch first.
+ ApplyTransformation(TransformationFlattenConditionalBranch(
+ header->id(), GetFuzzerContext()->ChooseEven(), wrappers_info));
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_flatten_conditional_branches.h b/source/fuzz/fuzzer_pass_flatten_conditional_branches.h
new file mode 100644
index 0000000..715385a
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_flatten_conditional_branches.h
@@ -0,0 +1,36 @@
+// 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_FLATTEN_CONDITIONAL_BRANCHES_H
+#define SOURCE_FUZZ_FUZZER_PASS_FLATTEN_CONDITIONAL_BRANCHES_H
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class FuzzerPassFlattenConditionalBranches : public FuzzerPass {
+ public:
+ FuzzerPassFlattenConditionalBranches(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassFlattenConditionalBranches() override;
+
+ void Apply() override;
+};
+} // namespace fuzz
+} // namespace spvtools
+#endif // SOURCE_FUZZ_FUZZER_PASS_FLATTEN_CONDITIONAL_BRANCHES_H
diff --git a/source/fuzz/fuzzer_util.cpp b/source/fuzz/fuzzer_util.cpp
index c6d18c0..e765fe9 100644
--- a/source/fuzz/fuzzer_util.cpp
+++ b/source/fuzz/fuzzer_util.cpp
@@ -1519,6 +1519,118 @@
return false;
}
+bool InstructionHasNoSideEffects(const opt::Instruction& instruction) {
+ switch (instruction.opcode()) {
+ case SpvOpUndef:
+ case SpvOpAccessChain:
+ case SpvOpInBoundsAccessChain:
+ case SpvOpArrayLength:
+ case SpvOpVectorExtractDynamic:
+ case SpvOpVectorInsertDynamic:
+ case SpvOpVectorShuffle:
+ case SpvOpCompositeConstruct:
+ case SpvOpCompositeExtract:
+ case SpvOpCompositeInsert:
+ case SpvOpCopyObject:
+ case SpvOpTranspose:
+ case SpvOpConvertFToU:
+ case SpvOpConvertFToS:
+ case SpvOpConvertSToF:
+ case SpvOpConvertUToF:
+ case SpvOpUConvert:
+ case SpvOpSConvert:
+ case SpvOpFConvert:
+ case SpvOpQuantizeToF16:
+ case SpvOpSatConvertSToU:
+ case SpvOpSatConvertUToS:
+ case SpvOpBitcast:
+ case SpvOpSNegate:
+ case SpvOpFNegate:
+ case SpvOpIAdd:
+ case SpvOpFAdd:
+ case SpvOpISub:
+ case SpvOpFSub:
+ case SpvOpIMul:
+ case SpvOpFMul:
+ case SpvOpUDiv:
+ case SpvOpSDiv:
+ case SpvOpFDiv:
+ case SpvOpUMod:
+ case SpvOpSRem:
+ case SpvOpSMod:
+ case SpvOpFRem:
+ case SpvOpFMod:
+ case SpvOpVectorTimesScalar:
+ case SpvOpMatrixTimesScalar:
+ case SpvOpVectorTimesMatrix:
+ case SpvOpMatrixTimesVector:
+ case SpvOpMatrixTimesMatrix:
+ case SpvOpOuterProduct:
+ case SpvOpDot:
+ case SpvOpIAddCarry:
+ case SpvOpISubBorrow:
+ case SpvOpUMulExtended:
+ case SpvOpSMulExtended:
+ case SpvOpAny:
+ case SpvOpAll:
+ case SpvOpIsNan:
+ case SpvOpIsInf:
+ case SpvOpIsFinite:
+ case SpvOpIsNormal:
+ case SpvOpSignBitSet:
+ case SpvOpLessOrGreater:
+ case SpvOpOrdered:
+ case SpvOpUnordered:
+ case SpvOpLogicalEqual:
+ case SpvOpLogicalNotEqual:
+ case SpvOpLogicalOr:
+ case SpvOpLogicalAnd:
+ case SpvOpLogicalNot:
+ case SpvOpSelect:
+ case SpvOpIEqual:
+ case SpvOpINotEqual:
+ case SpvOpUGreaterThan:
+ case SpvOpSGreaterThan:
+ case SpvOpUGreaterThanEqual:
+ case SpvOpSGreaterThanEqual:
+ case SpvOpULessThan:
+ case SpvOpSLessThan:
+ case SpvOpULessThanEqual:
+ case SpvOpSLessThanEqual:
+ case SpvOpFOrdEqual:
+ case SpvOpFUnordEqual:
+ case SpvOpFOrdNotEqual:
+ case SpvOpFUnordNotEqual:
+ case SpvOpFOrdLessThan:
+ case SpvOpFUnordLessThan:
+ case SpvOpFOrdGreaterThan:
+ case SpvOpFUnordGreaterThan:
+ case SpvOpFOrdLessThanEqual:
+ case SpvOpFUnordLessThanEqual:
+ case SpvOpFOrdGreaterThanEqual:
+ case SpvOpFUnordGreaterThanEqual:
+ case SpvOpShiftRightLogical:
+ case SpvOpShiftRightArithmetic:
+ case SpvOpShiftLeftLogical:
+ case SpvOpBitwiseOr:
+ case SpvOpBitwiseXor:
+ case SpvOpBitwiseAnd:
+ case SpvOpNot:
+ case SpvOpBitFieldInsert:
+ case SpvOpBitFieldSExtract:
+ case SpvOpBitFieldUExtract:
+ case SpvOpBitReverse:
+ case SpvOpBitCount:
+ case SpvOpCopyLogical:
+ case SpvOpPhi:
+ case SpvOpPtrEqual:
+ case SpvOpPtrNotEqual:
+ return true;
+ default:
+ return false;
+ }
+}
+
} // namespace fuzzerutil
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/fuzzer_util.h b/source/fuzz/fuzzer_util.h
index 2496c11..5f1e3f7 100644
--- a/source/fuzz/fuzzer_util.h
+++ b/source/fuzz/fuzzer_util.h
@@ -529,6 +529,12 @@
bool SplittingBeforeInstructionSeparatesOpSampledImageDefinitionFromUse(
opt::BasicBlock* block_to_split, opt::Instruction* split_before);
+// Returns true if the instruction given has no side effects.
+// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3758): Add any
+// missing instructions to the list. In particular, GLSL extended instructions
+// (called using OpExtInst) have not been considered.
+bool InstructionHasNoSideEffects(const opt::Instruction& instruction);
+
} // namespace fuzzerutil
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index f1fa6ac..f273bbc 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -306,6 +306,81 @@
}
+message SideEffectWrapperInfo {
+ // When flattening a conditional branch, it is necessary to enclose
+ // instructions that have side effects inside conditionals, so that
+ // they are only executed if the condition holds. Otherwise, there
+ // might be unintended changes in memory, or crashes that would not
+ // originally happen.
+ // For example, the instruction %id = OpLoad %type %ptr, found in
+ // the true branch of the conditional, will be enclosed in a new
+ // conditional (assuming that the block containing it can be split
+ // around it) as follows:
+ //
+ // [previous instructions in the block]
+ // OpSelectionMerge %merge_block_id None
+ // OpBranchConditional %cond %execute_block_id %alternative_block_id
+ // %execute_block_id = OpLabel
+ // %actual_result_id = OpLoad %type %ptr
+ // OpBranch %merge_block_id
+ // %alternative_block_id = OpLabel
+ // %placeholder_result_id = OpCopyObject %type %value_to_copy_id
+ // OpBranch %merge_block_id
+ // %merge_block_id = OpLabel
+ // %id = OpPhi %type %actual_result_id %execute_block_id %placeholder_result_id %alternative_block_id
+ // [following instructions from the original block]
+ //
+ // If the instruction does not have a result id, this is simplified.
+ // For example, OpStore %ptr %value, found in the true branch of a
+ // conditional, is enclosed as follows:
+ //
+ // [previous instructions in the block]
+ // OpSelectionMerge %merge_block None
+ // OpBranchConditional %cond %execute_block_id %merge_block_id
+ // %execute_block_id = OpLabel
+ // OpStore %ptr %value
+ // OpBranch %merge_block_id
+ // %merge_block_id = OpLabel
+ // [following instructions from the original block]
+ //
+ // The same happens if the instruction is found in the false branch
+ // of the conditional being flattened, except that the label ids in
+ // the OpBranchConditional are swapped.
+
+
+ // An instruction descriptor for identifying the instruction to be
+ // enclosed inside a conditional. An instruction descriptor is
+ // necessary because the instruction might not have a result id.
+ InstructionDescriptor instruction = 1;
+
+ // A fresh id for the new merge block.
+ uint32 merge_block_id = 2;
+
+ // A fresh id for the new block where the actual instruction is
+ // executed.
+ uint32 execute_block_id = 3;
+
+ // The following fields are only needed if the original instruction has a
+ // result id. They can be set to 0 if not needed.
+
+ // A fresh id for the result id of the instruction (the original
+ // one is used by the OpPhi instruction).
+ uint32 actual_result_id = 4;
+
+ // A fresh id for the new block where the placeholder instruction
+ // is placed.
+ uint32 alternative_block_id = 5;
+
+ // A fresh id for the placeholder instruction.
+ uint32 placeholder_result_id = 6;
+
+ // An id present in the module, available to use at this point in
+ // the program and with the same type as the original instruction,
+ // that can be used to create a placeholder OpCopyObject
+ // instruction.
+ uint32 value_to_copy_id = 7;
+}
+
message LoopLimiterInfo {
// Structure capturing the information required to manipulate a loop limiter
@@ -420,6 +495,7 @@
TransformationReplaceOpPhiIdFromDeadPredecessor replace_opphi_id_from_dead_predecessor = 73;
TransformationReplaceOpSelectWithConditionalBranch replace_opselect_with_conditional_branch = 74;
TransformationDuplicateRegionWithSelection duplicate_region_with_selection = 75;
+ TransformationFlattenConditionalBranch flatten_conditional_branch = 76;
// Add additional option using the next available number.
}
}
@@ -1140,6 +1216,63 @@
}
+message TransformationFlattenConditionalBranch {
+
+ // A transformation that takes a selection construct with a header
+ // containing an OpBranchConditional instruction and flattens it.
+ // For example, something of the form:
+ //
+ // %1 = OpLabel
+ // [header instructions]
+ // OpSelectionMerge %4 None
+ // OpBranchConditional %cond %2 %3
+ // %2 = OpLabel
+ // [true branch instructions]
+ // OpBranch %4
+ // %3 = OpLabel
+ // [false branch instructions]
+ // OpBranch %4
+ // %4 = OpLabel
+ // ...
+ //
+ // becomes:
+ //
+ // %1 = OpLabel
+ // [header instructions]
+ // OpBranch %2
+ // %2 = OpLabel
+ // [true branch instructions]
+ // OpBranch %3
+ // %3 = OpLabel
+ // [false branch instructions]
+ // OpBranch %4
+ // %4 = OpLabel
+ // ...
+ //
+ // If all of the instructions in the true or false branches have
+ // no side effects, this is semantics-preserving.
+ // Side-effecting instructions will instead be enclosed by smaller
+ // conditionals. For more details, look at the definition for the
+ // SideEffectWrapperInfo message.
+ //
+ // Nested conditionals or loops are not supported. The false branch
+ // could also be executed before the true branch, depending on the
+ // |true_branch_first| field.
+
+ // The label id of the header block
+ uint32 header_block_id = 1;
+
+ // A boolean field deciding the order in which the original branches
+ // will be laid out: the true branch will be laid out first iff this
+ // field is true.
+ bool true_branch_first = 2;
+
+ // A list of instructions with side effects, which must be enclosed
+ // inside smaller conditionals before flattening the main one, and
+ // the corresponding fresh ids and module ids needed.
+ repeated SideEffectWrapperInfo side_effect_wrapper_info = 3;
+}
+
message TransformationFunctionCall {
// A transformation that introduces an OpFunctionCall instruction. The call
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index 2f00dc3..bd924f9 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -54,6 +54,7 @@
#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_flatten_conditional_branch.h"
#include "source/fuzz/transformation_function_call.h"
#include "source/fuzz/transformation_inline_function.h"
#include "source/fuzz/transformation_invert_comparison_operator.h"
@@ -204,6 +205,10 @@
case protobufs::Transformation::TransformationCase::kEquationInstruction:
return MakeUnique<TransformationEquationInstruction>(
message.equation_instruction());
+ case protobufs::Transformation::TransformationCase::
+ kFlattenConditionalBranch:
+ return MakeUnique<TransformationFlattenConditionalBranch>(
+ message.flatten_conditional_branch());
case protobufs::Transformation::TransformationCase::kFunctionCall:
return MakeUnique<TransformationFunctionCall>(message.function_call());
case protobufs::Transformation::TransformationCase::kInlineFunction:
diff --git a/source/fuzz/transformation_flatten_conditional_branch.cpp b/source/fuzz/transformation_flatten_conditional_branch.cpp
new file mode 100644
index 0000000..f551923
--- /dev/null
+++ b/source/fuzz/transformation_flatten_conditional_branch.cpp
@@ -0,0 +1,686 @@
+// 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_flatten_conditional_branch.h"
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/instruction_descriptor.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationFlattenConditionalBranch::TransformationFlattenConditionalBranch(
+ const protobufs::TransformationFlattenConditionalBranch& message)
+ : message_(message) {}
+
+TransformationFlattenConditionalBranch::TransformationFlattenConditionalBranch(
+ uint32_t header_block_id, bool true_branch_first,
+ const std::vector<protobufs::SideEffectWrapperInfo>&
+ side_effect_wrappers_info) {
+ message_.set_header_block_id(header_block_id);
+ message_.set_true_branch_first(true_branch_first);
+ for (auto const& side_effect_wrapper_info : side_effect_wrappers_info) {
+ *message_.add_side_effect_wrapper_info() = side_effect_wrapper_info;
+ }
+}
+
+bool TransformationFlattenConditionalBranch::IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const {
+ uint32_t header_block_id = message_.header_block_id();
+ auto header_block = fuzzerutil::MaybeFindBlock(ir_context, header_block_id);
+
+ // The block must have been found and it must be a selection header.
+ if (!header_block || !header_block->GetMergeInst() ||
+ header_block->GetMergeInst()->opcode() != SpvOpSelectionMerge) {
+ return false;
+ }
+
+ // The header block must end with an OpBranchConditional instruction.
+ if (header_block->terminator()->opcode() != SpvOpBranchConditional) {
+ return false;
+ }
+
+ // Use a set to keep track of the instructions that require fresh ids.
+ std::set<opt::Instruction*> instructions_that_need_ids;
+
+ // Check that, if there are enough ids, the conditional can be flattened and,
+ // if so, add all the problematic instructions that need to be enclosed inside
+ // conditionals to |instructions_that_need_ids|.
+ if (!GetProblematicInstructionsIfConditionalCanBeFlattened(
+ ir_context, header_block, &instructions_that_need_ids)) {
+ return false;
+ }
+
+ // Get the mapping from instructions to the fresh ids needed to enclose them
+ // inside conditionals.
+ auto insts_to_wrapper_info = GetInstructionsToWrapperInfo(ir_context);
+
+ {
+ std::set<uint32_t> used_fresh_ids;
+
+ // Check the ids in the map.
+ for (const auto& inst_to_info : insts_to_wrapper_info) {
+ // Check the fresh ids needed for all of the instructions that need to be
+ // enclosed inside a conditional.
+ for (uint32_t id : {inst_to_info.second.merge_block_id(),
+ inst_to_info.second.execute_block_id()}) {
+ if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation(
+ id, ir_context, &used_fresh_ids)) {
+ return false;
+ }
+ }
+
+ // Check the other ids needed, if the instruction needs a placeholder.
+ if (InstructionNeedsPlaceholder(ir_context, *inst_to_info.first)) {
+ // Check the fresh ids.
+ for (uint32_t id : {inst_to_info.second.actual_result_id(),
+ inst_to_info.second.alternative_block_id(),
+ inst_to_info.second.placeholder_result_id()}) {
+ if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation(
+ id, ir_context, &used_fresh_ids)) {
+ return false;
+ }
+ }
+
+ // Check that the placeholder value id exists, has the right type and is
+ // available to use at this point.
+ auto value_def = ir_context->get_def_use_mgr()->GetDef(
+ inst_to_info.second.value_to_copy_id());
+ if (!value_def ||
+ value_def->type_id() != inst_to_info.first->type_id() ||
+ !fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, inst_to_info.first,
+ inst_to_info.second.value_to_copy_id())) {
+ return false;
+ }
+ }
+ }
+ }
+
+ // If some instructions that require ids are not in the map, the
+ // transformation needs overflow ids to be applicable.
+ for (auto instruction : instructions_that_need_ids) {
+ if (insts_to_wrapper_info.count(instruction) == 0 &&
+ !transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
+ return false;
+ }
+ }
+
+ // All checks were passed.
+ return true;
+}
+
+void TransformationFlattenConditionalBranch::Apply(
+ opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const {
+ uint32_t header_block_id = message_.header_block_id();
+ auto header_block = ir_context->cfg()->block(header_block_id);
+
+ // Find the first block where flow converges (it is not necessarily the merge
+ // block) by walking the true branch until reaching a block that
+ // post-dominates the header.
+ // This is necessary because a potential common set of blocks at the end of
+ // the construct should not be duplicated.
+ uint32_t convergence_block_id =
+ header_block->terminator()->GetSingleWordInOperand(1);
+ auto postdominator_analysis =
+ ir_context->GetPostDominatorAnalysis(header_block->GetParent());
+ while (!postdominator_analysis->Dominates(convergence_block_id,
+ header_block_id)) {
+ auto current_block = ir_context->get_instr_block(convergence_block_id);
+ // If the transformation is applicable, the terminator is OpBranch.
+ convergence_block_id =
+ current_block->terminator()->GetSingleWordInOperand(0);
+ }
+
+ // Get the mapping from instructions to fresh ids.
+ auto insts_to_info = GetInstructionsToWrapperInfo(ir_context);
+
+ auto branch_instruction = header_block->terminator();
+
+ // Get a reference to the last block in the first branch that will be laid out
+ // (this depends on |message_.true_branch_first|). The last block is the block
+ // in the branch just before flow converges (it might not exist).
+ opt::BasicBlock* last_block_first_branch = nullptr;
+
+ // branch = 1 corresponds to the true branch, branch = 2 corresponds to the
+ // false branch. If the true branch is to be laid out first, we need to visit
+ // the false branch first, because each branch is moved to right after the
+ // header while it is visited.
+ std::vector<uint32_t> branches = {2, 1};
+ if (!message_.true_branch_first()) {
+ // Similarly, we need to visit the true branch first, if we want it to be
+ // laid out after the false branch.
+ branches = {1, 2};
+ }
+
+ // Adjust the conditional branches by enclosing problematic instructions
+ // within conditionals and get references to the last block in each branch.
+ for (uint32_t branch : branches) {
+ auto current_block = header_block;
+ // Get the id of the first block in this branch.
+ uint32_t next_block_id = branch_instruction->GetSingleWordInOperand(branch);
+
+ // Consider all blocks in the branch until the convergence block is reached.
+ while (next_block_id != convergence_block_id) {
+ // Move the next block to right after the current one.
+ current_block->GetParent()->MoveBasicBlockToAfter(next_block_id,
+ current_block);
+
+ // Move forward in the branch.
+ current_block = ir_context->cfg()->block(next_block_id);
+
+ // Find all the instructions in the current block which need to be
+ // enclosed inside conditionals.
+ std::vector<opt::Instruction*> problematic_instructions;
+
+ current_block->ForEachInst(
+ [&problematic_instructions](opt::Instruction* instruction) {
+ if (instruction->opcode() != SpvOpLabel &&
+ instruction->opcode() != SpvOpBranch &&
+ !fuzzerutil::InstructionHasNoSideEffects(*instruction)) {
+ problematic_instructions.push_back(instruction);
+ }
+ });
+
+ uint32_t condition_id =
+ header_block->terminator()->GetSingleWordInOperand(0);
+
+ // Enclose all of the problematic instructions in conditionals, with the
+ // same condition as the selection construct being flattened.
+ for (auto instruction : problematic_instructions) {
+ // Get the info needed by this instruction to wrap it inside a
+ // conditional.
+ protobufs::SideEffectWrapperInfo wrapper_info;
+
+ if (insts_to_info.count(instruction) != 0) {
+ // Get the fresh ids from the map, if present.
+ wrapper_info = insts_to_info[instruction];
+ } else {
+ // If we could not get it from the map, use overflow ids. We don't
+ // need to set |wrapper_info.instruction|, as it will not be used.
+ wrapper_info.set_merge_block_id(
+ transformation_context->GetOverflowIdSource()
+ ->GetNextOverflowId());
+ wrapper_info.set_execute_block_id(
+ transformation_context->GetOverflowIdSource()
+ ->GetNextOverflowId());
+
+ if (InstructionNeedsPlaceholder(ir_context, *instruction)) {
+ // Ge the fresh ids from the overflow ids.
+ wrapper_info.set_actual_result_id(
+ transformation_context->GetOverflowIdSource()
+ ->GetNextOverflowId());
+ wrapper_info.set_alternative_block_id(
+ transformation_context->GetOverflowIdSource()
+ ->GetNextOverflowId());
+ wrapper_info.set_placeholder_result_id(
+ transformation_context->GetOverflowIdSource()
+ ->GetNextOverflowId());
+
+ // Try to find a zero constant. It does not matter whether it is
+ // relevant or irrelevant.
+ for (bool is_irrelevant : {true, false}) {
+ wrapper_info.set_value_to_copy_id(
+ fuzzerutil::MaybeGetZeroConstant(
+ ir_context, *transformation_context,
+ instruction->type_id(), is_irrelevant));
+ if (wrapper_info.value_to_copy_id()) {
+ break;
+ }
+ }
+ }
+ }
+
+ // Enclose the instruction in a conditional and get the merge block
+ // generated by this operation (this is where all the following
+ // instructions will be).
+ current_block = EncloseInstructionInConditional(
+ ir_context, transformation_context, current_block, instruction,
+ wrapper_info, condition_id, branch == 1);
+ }
+
+ next_block_id = current_block->terminator()->GetSingleWordInOperand(0);
+
+ // If the next block is the convergence block and this the branch that
+ // will be laid out right after the header, record this as the last block
+ // in the first branch.
+ if (next_block_id == convergence_block_id && branch == branches[1]) {
+ last_block_first_branch = current_block;
+ }
+ }
+ }
+
+ // Get the condition operand and the ids of the starting blocks of the first
+ // and last branches to be laid out. The first branch is the true branch iff
+ // |message_.true_branch_first| is true.
+ auto condition_operand = branch_instruction->GetInOperand(0);
+ uint32_t first_block_first_branch_id =
+ branch_instruction->GetSingleWordInOperand(branches[1]);
+ uint32_t first_block_last_branch_id =
+ branch_instruction->GetSingleWordInOperand(branches[0]);
+
+ // The current header should unconditionally branch to the starting block in
+ // the first branch to be laid out, if such a branch exists (i.e. the header
+ // does not branch directly to the convergence block), and to the starting
+ // block in the last branch to be laid out otherwise.
+ uint32_t after_header = first_block_first_branch_id != convergence_block_id
+ ? first_block_first_branch_id
+ : first_block_last_branch_id;
+
+ // Kill the merge instruction and the branch instruction in the current
+ // header.
+ auto merge_inst = header_block->GetMergeInst();
+ ir_context->KillInst(branch_instruction);
+ ir_context->KillInst(merge_inst);
+
+ // Add a new, unconditional, branch instruction from the current header to
+ // |after_header|.
+ header_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpBranch, 0, 0,
+ opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {after_header}}}));
+
+ // If the first branch to be laid out exists, change the branch instruction so
+ // that the last block in such branch unconditionally branches to the first
+ // block in the other branch (or the convergence block if there is no other
+ // branch) and change the OpPhi instructions in the last branch accordingly
+ // (the predecessor changed).
+ if (last_block_first_branch) {
+ last_block_first_branch->terminator()->SetInOperand(
+ 0, {first_block_last_branch_id});
+
+ // Change the OpPhi instructions of the last branch (if there is another
+ // branch) so that the predecessor is now the last block of the first
+ // branch. The block must have a single predecessor, so the operand
+ // specifying the predecessor is always in the same position.
+ if (first_block_last_branch_id != convergence_block_id) {
+ ir_context->get_instr_block(first_block_last_branch_id)
+ ->ForEachPhiInst(
+ [&last_block_first_branch](opt::Instruction* phi_inst) {
+ // The operand specifying the predecessor is the second input
+ // operand.
+ phi_inst->SetInOperand(1, {last_block_first_branch->id()});
+ });
+ }
+ }
+
+ // If the OpBranchConditional instruction in the header branches to the same
+ // block for both values of the condition, this is the convergence block (the
+ // flow does not actually diverge) and the OpPhi instructions in it are still
+ // valid, so we do not need to make any changes.
+ if (first_block_first_branch_id != first_block_last_branch_id) {
+ // Replace all of the current OpPhi instructions in the convergence block
+ // with OpSelect.
+
+ ir_context->get_instr_block(convergence_block_id)
+ ->ForEachPhiInst([&condition_operand](opt::Instruction* phi_inst) {
+ phi_inst->SetOpcode(SpvOpSelect);
+ std::vector<opt::Operand> operands;
+ operands.emplace_back(condition_operand);
+ // Only consider the operands referring to the instructions ids, as
+ // the block labels are not necessary anymore.
+ for (uint32_t i = 0; i < phi_inst->NumInOperands(); i += 2) {
+ operands.emplace_back(phi_inst->GetInOperand(i));
+ }
+
+ phi_inst->SetInOperands(std::move(operands));
+ });
+ }
+
+ // Invalidate all analyses
+ ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+protobufs::Transformation TransformationFlattenConditionalBranch::ToMessage()
+ const {
+ protobufs::Transformation result;
+ *result.mutable_flatten_conditional_branch() = message_;
+ return result;
+}
+
+bool TransformationFlattenConditionalBranch::
+ GetProblematicInstructionsIfConditionalCanBeFlattened(
+ opt::IRContext* ir_context, opt::BasicBlock* header,
+ std::set<opt::Instruction*>* instructions_that_need_ids) {
+ uint32_t merge_block_id = header->MergeBlockIdIfAny();
+ assert(merge_block_id &&
+ header->GetMergeInst()->opcode() == SpvOpSelectionMerge &&
+ header->terminator()->opcode() == SpvOpBranchConditional &&
+ "|header| must be the header of a conditional.");
+
+ auto enclosing_function = header->GetParent();
+ auto dominator_analysis =
+ ir_context->GetDominatorAnalysis(enclosing_function);
+ auto postdominator_analysis =
+ ir_context->GetPostDominatorAnalysis(enclosing_function);
+
+ // Check that the header and the merge block describe a single-entry,
+ // single-exit region.
+ if (!dominator_analysis->Dominates(header->id(), merge_block_id) ||
+ !postdominator_analysis->Dominates(merge_block_id, header->id())) {
+ return false;
+ }
+
+ // Traverse the CFG starting from the header and check that, for all the
+ // blocks that can be reached by the header before the flow converges:
+ // - they don't contain merge, barrier or OpSampledImage instructions
+ // - they branch unconditionally to another block
+ // Add any side-effecting instruction, requiring fresh ids, to
+ // |instructions_that_need_ids|
+ std::list<uint32_t> to_check;
+ header->ForEachSuccessorLabel(
+ [&to_check](uint32_t label) { to_check.push_back(label); });
+
+ while (!to_check.empty()) {
+ uint32_t block_id = to_check.front();
+ to_check.pop_front();
+
+ // If the block post-dominates the header, this is where flow converges, and
+ // we don't need to check this branch any further, because the
+ // transformation will only change the part of the graph where flow is
+ // divergent.
+ if (postdominator_analysis->Dominates(block_id, header->id())) {
+ continue;
+ }
+
+ auto block = ir_context->cfg()->block(block_id);
+
+ // The block must not have a merge instruction, because inner constructs are
+ // not allowed.
+ if (block->GetMergeInst()) {
+ return false;
+ }
+
+ // The terminator instruction for the block must be OpBranch.
+ if (block->terminator()->opcode() != SpvOpBranch) {
+ return false;
+ }
+
+ // Check all of the instructions in the block.
+ bool all_instructions_compatible =
+ block->WhileEachInst([ir_context, instructions_that_need_ids](
+ opt::Instruction* instruction) {
+ // We can ignore OpLabel instructions.
+ if (instruction->opcode() == SpvOpLabel) {
+ return true;
+ }
+
+ // If the instruction is a branch, it must be an unconditional branch.
+ if (instruction->IsBranch()) {
+ return instruction->opcode() == SpvOpBranch;
+ }
+
+ // We cannot go ahead if we encounter an instruction that cannot be
+ // handled.
+ if (!InstructionCanBeHandled(ir_context, *instruction)) {
+ return false;
+ }
+
+ // If the instruction has side effects, add it to the
+ // |instructions_that_need_ids| set.
+ if (!fuzzerutil::InstructionHasNoSideEffects(*instruction)) {
+ instructions_that_need_ids->emplace(instruction);
+ }
+
+ return true;
+ });
+
+ if (!all_instructions_compatible) {
+ return false;
+ }
+
+ // Add the successor of this block to the list of blocks that need to be
+ // checked.
+ to_check.push_back(block->terminator()->GetSingleWordInOperand(0));
+ }
+
+ // All the blocks are compatible with the transformation and this is indeed a
+ // single-entry, single-exit region.
+ return true;
+}
+
+bool TransformationFlattenConditionalBranch::InstructionNeedsPlaceholder(
+ opt::IRContext* ir_context, const opt::Instruction& instruction) {
+ assert(!fuzzerutil::InstructionHasNoSideEffects(instruction) &&
+ InstructionCanBeHandled(ir_context, instruction) &&
+ "The instruction must have side effects and it must be possible to "
+ "enclose it inside a conditional.");
+
+ if (instruction.HasResultId()) {
+ // We need a placeholder iff the type is not Void.
+ auto type = ir_context->get_type_mgr()->GetType(instruction.type_id());
+ return type && !type->AsVoid();
+ }
+
+ return false;
+}
+
+std::unordered_map<opt::Instruction*, protobufs::SideEffectWrapperInfo>
+TransformationFlattenConditionalBranch::GetInstructionsToWrapperInfo(
+ opt::IRContext* ir_context) const {
+ std::unordered_map<opt::Instruction*, protobufs::SideEffectWrapperInfo>
+ instructions_to_ids;
+ for (const auto& wrapper_info : message_.side_effect_wrapper_info()) {
+ auto instruction = FindInstruction(wrapper_info.instruction(), ir_context);
+ if (instruction) {
+ instructions_to_ids.emplace(instruction, wrapper_info);
+ }
+ }
+
+ return instructions_to_ids;
+}
+
+opt::BasicBlock*
+TransformationFlattenConditionalBranch::EncloseInstructionInConditional(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ opt::BasicBlock* block, opt::Instruction* instruction,
+ const protobufs::SideEffectWrapperInfo& wrapper_info, uint32_t condition_id,
+ bool exec_if_cond_true) const {
+ // Get the next instruction (it will be useful for splitting).
+ auto next_instruction = instruction->NextNode();
+
+ // Update the module id bound.
+ for (uint32_t id :
+ {wrapper_info.merge_block_id(), wrapper_info.execute_block_id()}) {
+ fuzzerutil::UpdateModuleIdBound(ir_context, id);
+ }
+
+ // Create the block where the instruction is executed by splitting the
+ // original block.
+ auto execute_block = block->SplitBasicBlock(
+ ir_context, wrapper_info.execute_block_id(),
+ fuzzerutil::GetIteratorForInstruction(block, instruction));
+
+ // Create the merge block for the conditional that we are about to create by
+ // splitting execute_block (this will leave |instruction| as the only
+ // instruction in |execute_block|).
+ auto merge_block = execute_block->SplitBasicBlock(
+ ir_context, wrapper_info.merge_block_id(),
+ fuzzerutil::GetIteratorForInstruction(execute_block, next_instruction));
+
+ // Propagate the fact that the block is dead to the newly-created blocks.
+ if (transformation_context->GetFactManager()->BlockIsDead(block->id())) {
+ transformation_context->GetFactManager()->AddFactBlockIsDead(
+ execute_block->id());
+ transformation_context->GetFactManager()->AddFactBlockIsDead(
+ merge_block->id());
+ }
+
+ // Initially, consider the merge block as the alternative block to branch to
+ // if the instruction should not be executed.
+ auto alternative_block = merge_block;
+
+ // Add an unconditional branch from |execute_block| to |merge_block|.
+ execute_block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpBranch, 0, 0,
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_ID, {merge_block->id()}}}));
+
+ // If the instruction requires a placeholder, it means that it has a result id
+ // and its result needs to be able to be used later on, and we need to:
+ // - add an additional block |ids.alternative_block_id| where a placeholder
+ // result id (using fresh id |ids.placeholder_result_id|) is obtained either
+ // by using OpCopyObject and copying |ids.value_to_copy_id| or, if such id
+ // was not given and a suitable constant was not found, by using OpUndef.
+ // - mark |ids.placeholder_result_id| as irrelevant
+ // - change the result id of the instruction to a fresh id
+ // (|ids.actual_result_id|).
+ // - add an OpPhi instruction, which will have the original result id of the
+ // instruction, in the merge block.
+ if (InstructionNeedsPlaceholder(ir_context, *instruction)) {
+ // Update the module id bound with the additional ids.
+ for (uint32_t id :
+ {wrapper_info.actual_result_id(), wrapper_info.alternative_block_id(),
+ wrapper_info.placeholder_result_id()}) {
+ fuzzerutil::UpdateModuleIdBound(ir_context, id);
+ }
+
+ // Create a new block using |fresh_ids.alternative_block_id| for its label.
+ auto alternative_block_temp =
+ MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpLabel, 0, wrapper_info.alternative_block_id(),
+ opt::Instruction::OperandList{}));
+
+ // Keep the original result id of the instruction in a variable.
+ uint32_t original_result_id = instruction->result_id();
+
+ // Set the result id of the instruction to be |ids.actual_result_id|.
+ instruction->SetResultId(wrapper_info.actual_result_id());
+
+ // Add a placeholder instruction, with the same type as the original
+ // instruction and id |ids.placeholder_result_id|, to the new block.
+ if (wrapper_info.value_to_copy_id()) {
+ // If there is an available id to copy from, the placeholder instruction
+ // will be %placeholder_result_id = OpCopyObject %type %value_to_copy_id
+ alternative_block_temp->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpCopyObject, instruction->type_id(),
+ wrapper_info.placeholder_result_id(),
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_ID, {wrapper_info.value_to_copy_id()}}}));
+ } else {
+ // If there is no such id, use an OpUndef instruction.
+ alternative_block_temp->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpUndef, instruction->type_id(),
+ wrapper_info.placeholder_result_id(),
+ opt::Instruction::OperandList{}));
+ }
+
+ // Mark |ids.placeholder_result_id| as irrelevant.
+ transformation_context->GetFactManager()->AddFactIdIsIrrelevant(
+ wrapper_info.placeholder_result_id());
+
+ // Add an unconditional branch from the new block to the merge block.
+ alternative_block_temp->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpBranch, 0, 0,
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_ID, {merge_block->id()}}}));
+
+ // Insert the block before the merge block.
+ alternative_block = block->GetParent()->InsertBasicBlockBefore(
+ std::move(alternative_block_temp), merge_block);
+
+ // Using the original instruction result id, add an OpPhi instruction to the
+ // merge block, which will either take the value of the result of the
+ // instruction or the placeholder value defined in the alternative block.
+ merge_block->begin().InsertBefore(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpPhi, instruction->type_id(), original_result_id,
+ opt::Instruction::OperandList{
+ {SPV_OPERAND_TYPE_ID, {instruction->result_id()}},
+ {SPV_OPERAND_TYPE_ID, {execute_block->id()}},
+ {SPV_OPERAND_TYPE_ID, {wrapper_info.placeholder_result_id()}},
+ {SPV_OPERAND_TYPE_ID, {alternative_block->id()}}}));
+
+ // Propagate the fact that the block is dead to the new block.
+ if (transformation_context->GetFactManager()->BlockIsDead(block->id())) {
+ transformation_context->GetFactManager()->AddFactBlockIsDead(
+ alternative_block->id());
+ }
+ }
+
+ // Depending on whether the instruction should be executed in the if branch or
+ // in the else branch, get the corresponding ids.
+ auto if_block_id = (exec_if_cond_true ? execute_block : alternative_block)
+ ->GetLabel()
+ ->result_id();
+ auto else_block_id = (exec_if_cond_true ? alternative_block : execute_block)
+ ->GetLabel()
+ ->result_id();
+
+ // Add an OpSelectionMerge instruction to the block.
+ block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpSelectionMerge, 0, 0,
+ opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {merge_block->id()}},
+ {SPV_OPERAND_TYPE_SELECTION_CONTROL,
+ {SpvSelectionControlMaskNone}}}));
+
+ // Add an OpBranchConditional, to the block, using |condition_id| as the
+ // condition and branching to |if_block_id| if the condition is true and to
+ // |else_block_id| if the condition is false.
+ block->AddInstruction(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpBranchConditional, 0, 0,
+ opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {condition_id}},
+ {SPV_OPERAND_TYPE_ID, {if_block_id}},
+ {SPV_OPERAND_TYPE_ID, {else_block_id}}}));
+
+ return merge_block;
+}
+
+bool TransformationFlattenConditionalBranch::InstructionCanBeHandled(
+ opt::IRContext* ir_context, const opt::Instruction& instruction) {
+ // We can handle all instructions with no side effects.
+ if (fuzzerutil::InstructionHasNoSideEffects(instruction)) {
+ return true;
+ }
+
+ // We cannot handle barrier instructions, while we should be able to handle
+ // all other instructions by enclosing them inside a conditional.
+ if (instruction.opcode() == SpvOpControlBarrier ||
+ instruction.opcode() == SpvOpMemoryBarrier ||
+ instruction.opcode() == SpvOpNamedBarrierInitialize ||
+ instruction.opcode() == SpvOpMemoryNamedBarrier ||
+ instruction.opcode() == SpvOpTypeNamedBarrier) {
+ return false;
+ }
+
+ // We cannot handle OpSampledImage instructions, as they need to be in the
+ // same block as their use.
+ if (instruction.opcode() == SpvOpSampledImage) {
+ return false;
+ }
+
+ // We cannot handle instructions with an id which return a void type, if the
+ // result id is used in the module (e.g. a function call to a function that
+ // returns nothing).
+ if (instruction.HasResultId()) {
+ auto type = ir_context->get_type_mgr()->GetType(instruction.type_id());
+ assert(type && "The type should be found in the module");
+
+ if (type->AsVoid() &&
+ !ir_context->get_def_use_mgr()->WhileEachUse(
+ instruction.result_id(),
+ [](opt::Instruction* use_inst, uint32_t use_index) {
+ // Return false if the id is used as an input operand.
+ return use_index <
+ use_inst->NumOperands() - use_inst->NumInOperands();
+ })) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_flatten_conditional_branch.h b/source/fuzz/transformation_flatten_conditional_branch.h
new file mode 100644
index 0000000..802a0bb
--- /dev/null
+++ b/source/fuzz/transformation_flatten_conditional_branch.h
@@ -0,0 +1,113 @@
+// 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_FLATTEN_CONDITIONAL_BRANCH_H
+#define SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H
+
+#include "source/fuzz/transformation.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationFlattenConditionalBranch : public Transformation {
+ public:
+ explicit TransformationFlattenConditionalBranch(
+ const protobufs::TransformationFlattenConditionalBranch& message);
+
+ TransformationFlattenConditionalBranch(
+ uint32_t header_block_id, bool true_branch_first,
+ const std::vector<protobufs::SideEffectWrapperInfo>&
+ side_effect_wrappers_info);
+
+ // - |message_.header_block_id| must be the label id of a reachable selection
+ // header, which ends with an OpBranchConditional instruction.
+ // - The header block and the merge block must describe a single-entry,
+ // single-exit region.
+ // - The region must not contain barrier or OpSampledImage instructions.
+ // - The region must not contain selection or loop constructs.
+ // - For each instruction that requires additional fresh ids, then:
+ // - if the instruction is mapped to the required ids for enclosing it by
+ // |message_.side_effect_wrapper_info|, these must be valid (the
+ // fresh ids must be non-zero, fresh and distinct);
+ // - if there is no such mapping, the transformation context must have
+ // overflow ids available.
+ bool IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const override;
+
+ // Flattens the selection construct with header |message_.header_block_id|,
+ // changing any OpPhi in the block where the flow converges to OpSelect and
+ // enclosing any instruction with side effects in conditionals so that
+ // they are only executed when they should.
+ void Apply(opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const override;
+
+ protobufs::Transformation ToMessage() const override;
+
+ // Returns true if the conditional headed by |header| can be flattened,
+ // according to the conditions of the IsApplicable method, assuming that
+ // enough fresh ids would be provided. In this case, it fills the
+ // |instructions_that_need_ids| set with all the instructions that would
+ // require fresh ids.
+ // Returns false otherwise.
+ // Assumes that |header| is the header of a conditional, so its last two
+ // instructions are OpSelectionMerge and OpBranchConditional.
+ static bool GetProblematicInstructionsIfConditionalCanBeFlattened(
+ opt::IRContext* ir_context, opt::BasicBlock* header,
+ std::set<opt::Instruction*>* instructions_that_need_ids);
+
+ // Returns true iff the given instruction needs a placeholder to be enclosed
+ // inside a conditional. So, it returns:
+ // - true if the instruction has a non-void result id,
+ // - false if the instruction does not have a result id or has a void result
+ // id.
+ // Assumes that the instruction has side effects, requiring it to be enclosed
+ // inside a conditional, and that it can be enclosed inside a conditional
+ // keeping the module valid. Assumes that, if the instruction has a void
+ // result type, its result id is not used in the module.
+ static bool InstructionNeedsPlaceholder(opt::IRContext* ir_context,
+ const opt::Instruction& instruction);
+
+ private:
+ // Returns an unordered_map mapping instructions to the info required to
+ // enclose them inside a conditional. It maps the instructions to the
+ // corresponding entry in |message_.side_effect_wrapper_info|.
+ std::unordered_map<opt::Instruction*, protobufs::SideEffectWrapperInfo>
+ GetInstructionsToWrapperInfo(opt::IRContext* ir_context) const;
+
+ // Splits the given block, adding a new selection construct so that the given
+ // instruction is only executed if the boolean value of |condition_id| matches
+ // the value of |exec_if_cond_true|.
+ // Assumes that all parameters are consistent.
+ // 2 fresh ids are required if the instruction does not have a result id (the
+ // first two ids in |wrapper_info| must be valid fresh ids), 5 otherwise.
+ // Returns the merge block created.
+ opt::BasicBlock* EncloseInstructionInConditional(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ opt::BasicBlock* block, opt::Instruction* instruction,
+ const protobufs::SideEffectWrapperInfo& wrapper_info,
+ uint32_t condition_id, bool exec_if_cond_true) const;
+
+ // Returns true if the given instruction either has no side effects or it can
+ // be handled by being enclosed in a conditional.
+ static bool InstructionCanBeHandled(opt::IRContext* ir_context,
+ const opt::Instruction& instruction);
+
+ protobufs::TransformationFlattenConditionalBranch message_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_FLATTEN_CONDITIONAL_BRANCH_H
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index f4add4c..3d2b569 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -18,6 +18,7 @@
fuzz_test_util.h
call_graph_test.cpp
+ comparator_deep_blocks_first_test.cpp
data_synonym_transformation_test.cpp
equivalence_relation_test.cpp
fact_manager_test.cpp
@@ -64,6 +65,7 @@
transformation_compute_data_synonym_fact_closure_test.cpp
transformation_duplicate_region_with_selection_test.cpp
transformation_equation_instruction_test.cpp
+ transformation_flatten_conditional_branch_test.cpp
transformation_function_call_test.cpp
transformation_inline_function_test.cpp
transformation_invert_comparison_operator_test.cpp
diff --git a/test/fuzz/comparator_deep_blocks_first_test.cpp b/test/fuzz/comparator_deep_blocks_first_test.cpp
new file mode 100644
index 0000000..2d98d71
--- /dev/null
+++ b/test/fuzz/comparator_deep_blocks_first_test.cpp
@@ -0,0 +1,134 @@
+// 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/comparator_deep_blocks_first.h"
+#include "source/fuzz/fact_manager/fact_manager.h"
+#include "source/fuzz/pseudo_random_generator.h"
+#include "source/fuzz/transformation_context.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpTypeInt 32 1
+ %8 = OpTypePointer Function %7
+ %9 = OpConstant %7 1
+ %10 = OpConstant %7 10
+ %11 = OpConstant %7 2
+ %2 = OpFunction %3 None %4
+ %12 = OpLabel
+ OpSelectionMerge %13 None
+ OpBranchConditional %6 %14 %15
+ %14 = OpLabel
+ OpBranch %13
+ %15 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ OpLoopMerge %17 %18 None
+ OpBranch %19
+ %19 = OpLabel
+ OpBranchConditional %6 %20 %17
+ %20 = OpLabel
+ OpSelectionMerge %21 None
+ OpBranchConditional %6 %22 %23
+ %22 = OpLabel
+ OpBranch %21
+ %23 = OpLabel
+ OpBranch %21
+ %21 = OpLabel
+ OpBranch %18
+ %18 = OpLabel
+ OpBranch %16
+ %17 = OpLabel
+ OpBranch %13
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+TEST(ComparatorDeepBlocksFirstTest, Compare) {
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ 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);
+
+ auto is_deeper = ComparatorDeepBlocksFirst(context.get());
+
+ // The block ids and the corresponding depths are:
+ // 12, 13 -> depth 0
+ // 14, 15, 16, 17 -> depth 1
+ // 18, 19, 20, 21 -> depth 2
+ // 22, 23 -> depth 3
+
+ // Perform some comparisons and check that they return true iff the first
+ // block is deeper than the second.
+ ASSERT_FALSE(is_deeper(12, 12));
+ ASSERT_FALSE(is_deeper(12, 13));
+ ASSERT_FALSE(is_deeper(12, 14));
+ ASSERT_FALSE(is_deeper(12, 18));
+ ASSERT_FALSE(is_deeper(12, 22));
+ ASSERT_TRUE(is_deeper(14, 12));
+ ASSERT_FALSE(is_deeper(14, 15));
+ ASSERT_FALSE(is_deeper(15, 14));
+ ASSERT_FALSE(is_deeper(14, 18));
+ ASSERT_TRUE(is_deeper(18, 12));
+ ASSERT_TRUE(is_deeper(18, 16));
+}
+
+TEST(ComparatorDeepBlocksFirstTest, Sort) {
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ 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);
+
+ // Check that, sorting using the comparator, the blocks are ordered from more
+ // deeply nested to less deeply nested.
+ // 17 has depth 1, 20 has depth 2, 13 has depth 0.
+ std::vector<opt::BasicBlock*> blocks = {context->get_instr_block(17),
+ context->get_instr_block(20),
+ context->get_instr_block(13)};
+
+ std::sort(blocks.begin(), blocks.end(),
+ ComparatorDeepBlocksFirst(context.get()));
+
+ // Check that the blocks are in the correct order.
+ ASSERT_EQ(blocks[0]->id(), 20);
+ ASSERT_EQ(blocks[1]->id(), 17);
+ ASSERT_EQ(blocks[2]->id(), 13);
+}
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
diff --git a/test/fuzz/transformation_flatten_conditional_branch_test.cpp b/test/fuzz/transformation_flatten_conditional_branch_test.cpp
new file mode 100644
index 0000000..095acbc
--- /dev/null
+++ b/test/fuzz/transformation_flatten_conditional_branch_test.cpp
@@ -0,0 +1,793 @@
+// 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_flatten_conditional_branch.h"
+
+#include "source/fuzz/counter_overflow_id_source.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+protobufs::SideEffectWrapperInfo MakeSideEffectWrapperInfo(
+ const protobufs::InstructionDescriptor& instruction,
+ uint32_t merge_block_id, uint32_t execute_block_id,
+ uint32_t actual_result_id = 0, uint32_t alternative_block_id = 0,
+ uint32_t placeholder_result_id = 0, uint32_t value_to_copy_id = 0) {
+ protobufs::SideEffectWrapperInfo result;
+ *result.mutable_instruction() = instruction;
+ result.set_merge_block_id(merge_block_id);
+ result.set_execute_block_id(execute_block_id);
+ result.set_actual_result_id(actual_result_id);
+ result.set_alternative_block_id(alternative_block_id);
+ result.set_placeholder_result_id(placeholder_result_id);
+ result.set_value_to_copy_id(value_to_copy_id);
+ return result;
+}
+
+TEST(TransformationFlattenConditionalBranchTest, Inapplicable) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main" %3
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %4 = OpTypeVoid
+ %5 = OpTypeFunction %4
+ %6 = OpTypeInt 32 1
+ %7 = OpTypeInt 32 0
+ %8 = OpConstant %7 0
+ %9 = OpTypeBool
+ %10 = OpConstantTrue %9
+ %11 = OpTypePointer Function %6
+ %12 = OpTypePointer Workgroup %6
+ %3 = OpVariable %12 Workgroup
+ %13 = OpConstant %6 2
+ %2 = OpFunction %4 None %5
+ %14 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ OpSelectionMerge %16 None
+ OpSwitch %13 %17 2 %18
+ %17 = OpLabel
+ OpBranch %16
+ %18 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ OpLoopMerge %19 %16 None
+ OpBranchConditional %10 %16 %19
+ %19 = OpLabel
+ OpSelectionMerge %20 None
+ OpBranchConditional %10 %21 %20
+ %21 = OpLabel
+ OpReturn
+ %20 = OpLabel
+ OpSelectionMerge %22 None
+ OpBranchConditional %10 %23 %22
+ %23 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %10 %25 %24
+ %25 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpBranch %22
+ %22 = OpLabel
+ OpSelectionMerge %26 None
+ OpBranchConditional %10 %26 %27
+ %27 = OpLabel
+ OpBranch %28
+ %28 = OpLabel
+ OpLoopMerge %29 %28 None
+ OpBranchConditional %10 %28 %29
+ %29 = OpLabel
+ OpBranch %26
+ %26 = OpLabel
+ OpSelectionMerge %30 None
+ OpBranchConditional %10 %30 %31
+ %31 = OpLabel
+ OpBranch %32
+ %32 = OpLabel
+ %33 = OpAtomicLoad %6 %3 %8 %8
+ OpBranch %30
+ %30 = OpLabel
+ OpSelectionMerge %34 None
+ OpBranchConditional %10 %35 %34
+ %35 = OpLabel
+ OpMemoryBarrier %8 %8
+ OpBranch %34
+ %34 = OpLabel
+ OpLoopMerge %40 %39 None
+ OpBranchConditional %10 %36 %40
+ %36 = OpLabel
+ OpSelectionMerge %38 None
+ OpBranchConditional %10 %37 %38
+ %37 = OpLabel
+ OpBranch %40
+ %38 = OpLabel
+ OpBranch %39
+ %39 = OpLabel
+ OpBranch %34
+ %40 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ 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);
+
+ // Block %15 does not end with OpBranchConditional.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(15, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %17 is not a selection header.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(17, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %16 is a loop header, not a selection header.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(16, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %19 and the corresponding merge block do not describe a single-entry,
+ // single-exit region, because there is a return instruction in %21.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(19, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %20 is the header of a construct containing an inner selection
+ // construct.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(20, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %22 is the header of a construct containing an inner loop.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(22, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %30 is the header of a construct containing a barrier instruction.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(30, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %33 is not a block.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(33, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %36 and the corresponding merge block do not describe a single-entry,
+ // single-exit region, because block %37 breaks out of the outer loop.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(36, true, {})
+ .IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationFlattenConditionalBranchTest, Simple) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeBool
+ %4 = OpConstantTrue %3
+ %5 = OpTypeVoid
+ %6 = OpTypeFunction %5
+ %2 = OpFunction %5 None %6
+ %7 = OpLabel
+ OpSelectionMerge %8 None
+ OpBranchConditional %4 %9 %10
+ %10 = OpLabel
+ %26 = OpPhi %3 %4 %7
+ OpBranch %8
+ %9 = OpLabel
+ %27 = OpPhi %3 %4 %7
+ %11 = OpCopyObject %3 %4
+ OpBranch %8
+ %8 = OpLabel
+ %12 = OpPhi %3 %11 %9 %4 %10
+ %23 = OpPhi %3 %4 %9 %4 %10
+ OpBranch %13
+ %13 = OpLabel
+ %14 = OpCopyObject %3 %4
+ OpSelectionMerge %15 None
+ OpBranchConditional %4 %16 %17
+ %16 = OpLabel
+ %28 = OpPhi %3 %4 %13
+ OpBranch %18
+ %18 = OpLabel
+ OpBranch %19
+ %17 = OpLabel
+ %29 = OpPhi %3 %4 %13
+ %20 = OpCopyObject %3 %4
+ OpBranch %19
+ %19 = OpLabel
+ %21 = OpPhi %3 %4 %18 %20 %17
+ OpBranch %15
+ %15 = OpLabel
+ OpSelectionMerge %22 None
+ OpBranchConditional %4 %22 %22
+ %22 = OpLabel
+ %30 = OpPhi %3 %4 %15
+ OpSelectionMerge %25 None
+ OpBranchConditional %4 %24 %24
+ %24 = OpLabel
+ OpBranch %25
+ %25 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ 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);
+
+ auto transformation1 = TransformationFlattenConditionalBranch(7, true, {});
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ transformation1.Apply(context.get(), &transformation_context);
+
+ auto transformation2 = TransformationFlattenConditionalBranch(13, false, {});
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), transformation_context));
+ transformation2.Apply(context.get(), &transformation_context);
+
+ auto transformation3 = TransformationFlattenConditionalBranch(15, true, {});
+ ASSERT_TRUE(
+ transformation3.IsApplicable(context.get(), transformation_context));
+ transformation3.Apply(context.get(), &transformation_context);
+
+ auto transformation4 = TransformationFlattenConditionalBranch(22, false, {});
+ ASSERT_TRUE(
+ transformation4.IsApplicable(context.get(), transformation_context));
+ transformation4.Apply(context.get(), &transformation_context);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformations = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeBool
+ %4 = OpConstantTrue %3
+ %5 = OpTypeVoid
+ %6 = OpTypeFunction %5
+ %2 = OpFunction %5 None %6
+ %7 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ %27 = OpPhi %3 %4 %7
+ %11 = OpCopyObject %3 %4
+ OpBranch %10
+ %10 = OpLabel
+ %26 = OpPhi %3 %4 %9
+ OpBranch %8
+ %8 = OpLabel
+ %12 = OpSelect %3 %4 %11 %4
+ %23 = OpSelect %3 %4 %4 %4
+ OpBranch %13
+ %13 = OpLabel
+ %14 = OpCopyObject %3 %4
+ OpBranch %17
+ %17 = OpLabel
+ %29 = OpPhi %3 %4 %13
+ %20 = OpCopyObject %3 %4
+ OpBranch %16
+ %16 = OpLabel
+ %28 = OpPhi %3 %4 %17
+ OpBranch %18
+ %18 = OpLabel
+ OpBranch %19
+ %19 = OpLabel
+ %21 = OpSelect %3 %4 %4 %20
+ OpBranch %15
+ %15 = OpLabel
+ OpBranch %22
+ %22 = OpLabel
+ %30 = OpPhi %3 %4 %15
+ OpBranch %24
+ %24 = OpLabel
+ OpBranch %25
+ %25 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformations, context.get()));
+}
+
+TEST(TransformationFlattenConditionalBranchTest, LoadStoreFunctionCall) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %9 = OpTypeVoid
+ %10 = OpTypeFunction %9
+ %11 = OpTypeInt 32 1
+ %12 = OpTypeVector %11 4
+ %13 = OpTypeFunction %11
+ %70 = OpConstant %11 0
+ %14 = OpConstant %11 1
+ %15 = OpTypeFloat 32
+ %16 = OpTypeVector %15 2
+ %17 = OpConstant %15 1
+ %18 = OpConstantComposite %16 %17 %17
+ %19 = OpTypeBool
+ %20 = OpConstantTrue %19
+ %21 = OpTypePointer Function %11
+ %22 = OpTypeSampler
+ %23 = OpTypeImage %9 2D 2 0 0 1 Unknown
+ %24 = OpTypeSampledImage %23
+ %25 = OpTypePointer Function %23
+ %26 = OpTypePointer Function %22
+ %27 = OpTypeInt 32 0
+ %28 = OpConstant %27 2
+ %29 = OpTypeArray %11 %28
+ %30 = OpTypePointer Function %29
+ %2 = OpFunction %9 None %10
+ %31 = OpLabel
+ %4 = OpVariable %21 Function
+ %5 = OpVariable %30 Function
+ %32 = OpVariable %25 Function
+ %33 = OpVariable %26 Function
+ %34 = OpLoad %23 %32
+ %35 = OpLoad %22 %33
+ OpSelectionMerge %36 None
+ OpBranchConditional %20 %37 %36
+ %37 = OpLabel
+ %6 = OpLoad %11 %4
+ %7 = OpIAdd %11 %6 %14
+ OpStore %4 %7
+ OpBranch %36
+ %36 = OpLabel
+ %42 = OpPhi %11 %14 %37 %14 %31
+ OpSelectionMerge %43 None
+ OpBranchConditional %20 %44 %45
+ %44 = OpLabel
+ %8 = OpFunctionCall %11 %3
+ OpStore %4 %8
+ OpBranch %46
+ %45 = OpLabel
+ %47 = OpAccessChain %21 %5 %14
+ OpStore %47 %14
+ OpBranch %46
+ %46 = OpLabel
+ OpStore %4 %14
+ OpBranch %43
+ %43 = OpLabel
+ OpStore %4 %14
+ OpSelectionMerge %48 None
+ OpBranchConditional %20 %49 %48
+ %49 = OpLabel
+ OpBranch %48
+ %48 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %20 %51 %50
+ %51 = OpLabel
+ %52 = OpSampledImage %24 %34 %35
+ %53 = OpLoad %11 %4
+ %54 = OpImageSampleImplicitLod %12 %52 %18
+ OpBranch %50
+ %50 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %3 = OpFunction %11 None %13
+ %55 = OpLabel
+ OpReturnValue %14
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ 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);
+
+#ifndef NDEBUG
+ // The following checks lead to assertion failures, since some entries
+ // requiring fresh ids are not present in the map, and the transformation
+ // context does not have a source overflow ids.
+
+ ASSERT_DEATH(TransformationFlattenConditionalBranch(31, true, {})
+ .IsApplicable(context.get(), transformation_context),
+ "Bad attempt to query whether overflow ids are available.");
+
+ ASSERT_DEATH(TransformationFlattenConditionalBranch(
+ 31, true,
+ {{MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(6, SpvOpLoad, 0), 100, 101,
+ 102, 103, 104, 14)}})
+ .IsApplicable(context.get(), transformation_context),
+ "Bad attempt to query whether overflow ids are available.");
+#endif
+
+ // The map maps from an instruction to a list with not enough fresh ids.
+ ASSERT_FALSE(
+ TransformationFlattenConditionalBranch(
+ 31, true,
+ {{MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(6, SpvOpLoad, 0), 100, 101, 102, 103)}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Not all fresh ids given are distinct.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(
+ 31, true,
+ {{MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(6, SpvOpLoad, 0), 100, 100,
+ 102, 103, 104)}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %48 heads a construct containing an OpSampledImage instruction.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(
+ 48, true,
+ {{MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(53, SpvOpLoad, 0), 100, 101,
+ 102, 103, 104)}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %0 is not a valid id.
+ ASSERT_FALSE(
+ TransformationFlattenConditionalBranch(
+ 31, true,
+ {MakeSideEffectWrapperInfo(MakeInstructionDescriptor(6, SpvOpLoad, 0),
+ 104, 100, 101, 102, 103, 0),
+ MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(6, SpvOpStore, 0), 106, 105)})
+ .IsApplicable(context.get(), transformation_context));
+
+ // %17 is a float constant, while %6 has int type.
+ ASSERT_FALSE(
+ TransformationFlattenConditionalBranch(
+ 31, true,
+ {MakeSideEffectWrapperInfo(MakeInstructionDescriptor(6, SpvOpLoad, 0),
+ 104, 100, 101, 102, 103, 17),
+ MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(6, SpvOpStore, 0), 106, 105)})
+ .IsApplicable(context.get(), transformation_context));
+
+ auto transformation1 = TransformationFlattenConditionalBranch(
+ 31, true,
+ {MakeSideEffectWrapperInfo(MakeInstructionDescriptor(6, SpvOpLoad, 0),
+ 104, 100, 101, 102, 103, 70),
+ MakeSideEffectWrapperInfo(MakeInstructionDescriptor(6, SpvOpStore, 0),
+ 106, 105)});
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ transformation1.Apply(context.get(), &transformation_context);
+
+ // Check that the placeholder id was marked as irrelevant.
+ ASSERT_TRUE(transformation_context.GetFactManager()->IdIsIrrelevant(103));
+
+ // Make a new transformation context with a source of overflow ids.
+ TransformationContext new_transformation_context(
+ &fact_manager, validator_options,
+ MakeUnique<CounterOverflowIdSource>(1000));
+
+ auto transformation2 = TransformationFlattenConditionalBranch(
+ 36, false,
+ {MakeSideEffectWrapperInfo(MakeInstructionDescriptor(8, SpvOpStore, 0),
+ 114, 113)});
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), new_transformation_context));
+ transformation2.Apply(context.get(), &new_transformation_context);
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformations = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %9 = OpTypeVoid
+ %10 = OpTypeFunction %9
+ %11 = OpTypeInt 32 1
+ %12 = OpTypeVector %11 4
+ %13 = OpTypeFunction %11
+ %70 = OpConstant %11 0
+ %14 = OpConstant %11 1
+ %15 = OpTypeFloat 32
+ %16 = OpTypeVector %15 2
+ %17 = OpConstant %15 1
+ %18 = OpConstantComposite %16 %17 %17
+ %19 = OpTypeBool
+ %20 = OpConstantTrue %19
+ %21 = OpTypePointer Function %11
+ %22 = OpTypeSampler
+ %23 = OpTypeImage %9 2D 2 0 0 1 Unknown
+ %24 = OpTypeSampledImage %23
+ %25 = OpTypePointer Function %23
+ %26 = OpTypePointer Function %22
+ %27 = OpTypeInt 32 0
+ %28 = OpConstant %27 2
+ %29 = OpTypeArray %11 %28
+ %30 = OpTypePointer Function %29
+ %2 = OpFunction %9 None %10
+ %31 = OpLabel
+ %4 = OpVariable %21 Function
+ %5 = OpVariable %30 Function
+ %32 = OpVariable %25 Function
+ %33 = OpVariable %26 Function
+ %34 = OpLoad %23 %32
+ %35 = OpLoad %22 %33
+ OpBranch %37
+ %37 = OpLabel
+ OpSelectionMerge %104 None
+ OpBranchConditional %20 %100 %102
+ %100 = OpLabel
+ %101 = OpLoad %11 %4
+ OpBranch %104
+ %102 = OpLabel
+ %103 = OpCopyObject %11 %70
+ OpBranch %104
+ %104 = OpLabel
+ %6 = OpPhi %11 %101 %100 %103 %102
+ %7 = OpIAdd %11 %6 %14
+ OpSelectionMerge %106 None
+ OpBranchConditional %20 %105 %106
+ %105 = OpLabel
+ OpStore %4 %7
+ OpBranch %106
+ %106 = OpLabel
+ OpBranch %36
+ %36 = OpLabel
+ %42 = OpSelect %11 %20 %14 %14
+ OpBranch %45
+ %45 = OpLabel
+ %47 = OpAccessChain %21 %5 %14
+ OpSelectionMerge %1005 None
+ OpBranchConditional %20 %1005 %1006
+ %1006 = OpLabel
+ OpStore %47 %14
+ OpBranch %1005
+ %1005 = OpLabel
+ OpBranch %44
+ %44 = OpLabel
+ OpSelectionMerge %1000 None
+ OpBranchConditional %20 %1001 %1003
+ %1001 = OpLabel
+ %1002 = OpFunctionCall %11 %3
+ OpBranch %1000
+ %1003 = OpLabel
+ %1004 = OpCopyObject %11 %70
+ OpBranch %1000
+ %1000 = OpLabel
+ %8 = OpPhi %11 %1002 %1001 %1004 %1003
+ OpSelectionMerge %114 None
+ OpBranchConditional %20 %113 %114
+ %113 = OpLabel
+ OpStore %4 %8
+ OpBranch %114
+ %114 = OpLabel
+ OpBranch %46
+ %46 = OpLabel
+ OpStore %4 %14
+ OpBranch %43
+ %43 = OpLabel
+ OpStore %4 %14
+ OpSelectionMerge %48 None
+ OpBranchConditional %20 %49 %48
+ %49 = OpLabel
+ OpBranch %48
+ %48 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %20 %51 %50
+ %51 = OpLabel
+ %52 = OpSampledImage %24 %34 %35
+ %53 = OpLoad %11 %4
+ %54 = OpImageSampleImplicitLod %12 %52 %18
+ OpBranch %50
+ %50 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %3 = OpFunction %11 None %13
+ %55 = OpLabel
+ OpReturnValue %14
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformations, context.get()));
+} // namespace
+
+TEST(TransformationFlattenConditionalBranchTest, EdgeCases) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeBool
+ %5 = OpConstantTrue %4
+ %6 = OpTypeFunction %3
+ %2 = OpFunction %3 None %6
+ %7 = OpLabel
+ OpSelectionMerge %8 None
+ OpBranchConditional %5 %9 %8
+ %9 = OpLabel
+ %10 = OpFunctionCall %3 %11
+ OpBranch %8
+ %8 = OpLabel
+ OpSelectionMerge %12 None
+ OpBranchConditional %5 %13 %12
+ %13 = OpLabel
+ %14 = OpFunctionCall %3 %11
+ %15 = OpCopyObject %3 %14
+ OpBranch %12
+ %12 = OpLabel
+ OpReturn
+ %16 = OpLabel
+ OpSelectionMerge %17 None
+ OpBranchConditional %5 %18 %17
+ %18 = OpLabel
+ OpBranch %17
+ %17 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %11 = OpFunction %3 None %6
+ %19 = OpLabel
+ OpBranch %20
+ %20 = OpLabel
+ OpSelectionMerge %25 None
+ OpBranchConditional %5 %21 %22
+ %21 = OpLabel
+ OpBranch %22
+ %22 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %5 %24 %23
+ %23 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpBranch %25
+ %25 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ 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);
+
+#ifndef NDEBUG
+ // The selection construct headed by %7 requires fresh ids because it contains
+ // a function call. This causes an assertion failure because transformation
+ // context does not have a source of overflow ids.
+ ASSERT_DEATH(TransformationFlattenConditionalBranch(7, true, {})
+ .IsApplicable(context.get(), transformation_context),
+ "Bad attempt to query whether overflow ids are available.");
+#endif
+
+ auto transformation1 = TransformationFlattenConditionalBranch(
+ 7, true,
+ {{MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(10, SpvOpFunctionCall, 0), 100, 101)}});
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ transformation1.Apply(context.get(), &transformation_context);
+
+ // The selection construct headed by %8 cannot be flattened because it
+ // contains a function call returning void, whose result id is used.
+ ASSERT_FALSE(
+ TransformationFlattenConditionalBranch(
+ 7, true,
+ {{MakeSideEffectWrapperInfo(
+ MakeInstructionDescriptor(14, SpvOpFunctionCall, 0), 102, 103)}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %16 is unreachable.
+ ASSERT_FALSE(TransformationFlattenConditionalBranch(16, true, {})
+ .IsApplicable(context.get(), transformation_context));
+
+ auto transformation2 = TransformationFlattenConditionalBranch(20, false, {});
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), transformation_context));
+ transformation2.Apply(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 %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %3 = OpTypeVoid
+ %4 = OpTypeBool
+ %5 = OpConstantTrue %4
+ %6 = OpTypeFunction %3
+ %2 = OpFunction %3 None %6
+ %7 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpSelectionMerge %100 None
+ OpBranchConditional %5 %101 %100
+ %101 = OpLabel
+ %10 = OpFunctionCall %3 %11
+ OpBranch %100
+ %100 = OpLabel
+ OpBranch %8
+ %8 = OpLabel
+ OpSelectionMerge %12 None
+ OpBranchConditional %5 %13 %12
+ %13 = OpLabel
+ %14 = OpFunctionCall %3 %11
+ %15 = OpCopyObject %3 %14
+ OpBranch %12
+ %12 = OpLabel
+ OpReturn
+ %16 = OpLabel
+ OpSelectionMerge %17 None
+ OpBranchConditional %5 %18 %17
+ %18 = OpLabel
+ OpBranch %17
+ %17 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %11 = OpFunction %3 None %6
+ %19 = OpLabel
+ OpBranch %20
+ %20 = OpLabel
+ OpBranch %21
+ %21 = OpLabel
+ OpBranch %22
+ %22 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %5 %24 %23
+ %23 = OpLabel
+ OpBranch %24
+ %24 = OpLabel
+ OpBranch %25
+ %25 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
