spirv-fuzz: Replace dead-block terminators with OpKill etc. (#3882)
Fixes #3615.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 2a9a95d..6843eb8 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -104,6 +104,7 @@
fuzzer_pass_propagate_instructions_up.h
fuzzer_pass_push_ids_through_variables.h
fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h
+ fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h
fuzzer_pass_replace_copy_memories_with_loads_stores.h
fuzzer_pass_replace_copy_objects_with_stores_loads.h
fuzzer_pass_replace_irrelevant_ids.h
@@ -197,6 +198,7 @@
transformation_record_synonymous_constants.h
transformation_replace_add_sub_mul_with_carrying_extended.h
transformation_replace_boolean_constant_with_constant_binary.h
+ transformation_replace_branch_from_dead_block_with_exit.h
transformation_replace_constant_with_uniform.h
transformation_replace_copy_memory_with_load_store.h
transformation_replace_copy_object_with_store_load.h
@@ -288,6 +290,7 @@
fuzzer_pass_propagate_instructions_up.cpp
fuzzer_pass_push_ids_through_variables.cpp
fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.cpp
+ fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp
fuzzer_pass_replace_copy_memories_with_loads_stores.cpp
fuzzer_pass_replace_copy_objects_with_stores_loads.cpp
fuzzer_pass_replace_irrelevant_ids.cpp
@@ -379,6 +382,7 @@
transformation_record_synonymous_constants.cpp
transformation_replace_add_sub_mul_with_carrying_extended.cpp
transformation_replace_boolean_constant_with_constant_binary.cpp
+ transformation_replace_branch_from_dead_block_with_exit.cpp
transformation_replace_constant_with_uniform.cpp
transformation_replace_copy_memory_with_load_store.cpp
transformation_replace_copy_object_with_store_load.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 7d9c9c4..218c059 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -72,6 +72,7 @@
#include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
#include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
#include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
+#include "source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
#include "source/fuzz/fuzzer_pass_replace_copy_memories_with_loads_stores.h"
#include "source/fuzz/fuzzer_pass_replace_copy_objects_with_stores_loads.h"
#include "source/fuzz/fuzzer_pass_replace_irrelevant_ids.h"
@@ -282,6 +283,8 @@
MaybeAddRepeatedPass<FuzzerPassPushIdsThroughVariables>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassReplaceAddsSubsMulsWithCarryingExtended>(
&pass_instances);
+ MaybeAddRepeatedPass<FuzzerPassReplaceBranchesFromDeadBlocksWithExits>(
+ &pass_instances);
MaybeAddRepeatedPass<FuzzerPassReplaceCopyMemoriesWithLoadsStores>(
&pass_instances);
MaybeAddRepeatedPass<FuzzerPassReplaceCopyObjectsWithStoresLoads>(
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 1250cba..3f0d10e 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -114,6 +114,8 @@
const std::pair<uint32_t, uint32_t> kChanceOfPushingIdThroughVariable = {5, 50};
const std::pair<uint32_t, uint32_t>
kChanceOfReplacingAddSubMulWithCarryingExtended = {20, 70};
+const std::pair<uint32_t, uint32_t>
+ kChanceOfReplacingBranchFromDeadBlockWithExit = {10, 65};
const std::pair<uint32_t, uint32_t> kChanceOfReplacingCopyMemoryWithLoadStore =
{20, 90};
const std::pair<uint32_t, uint32_t> kChanceOfReplacingCopyObjectWithStoreLoad =
@@ -304,6 +306,8 @@
ChooseBetweenMinAndMax(kChanceOfPushingIdThroughVariable);
chance_of_replacing_add_sub_mul_with_carrying_extended_ =
ChooseBetweenMinAndMax(kChanceOfReplacingAddSubMulWithCarryingExtended);
+ chance_of_replacing_branch_from_dead_block_with_exit_ =
+ ChooseBetweenMinAndMax(kChanceOfReplacingBranchFromDeadBlockWithExit);
chance_of_replacing_copy_memory_with_load_store_ =
ChooseBetweenMinAndMax(kChanceOfReplacingCopyMemoryWithLoadStore);
chance_of_replacing_copyobject_with_store_load_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 01a92f7..147c66d 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -276,6 +276,9 @@
uint32_t GetChanceOfReplacingAddSubMulWithCarryingExtended() {
return chance_of_replacing_add_sub_mul_with_carrying_extended_;
}
+ uint32_t GetChanceOfReplacingBranchFromDeadBlockWithExit() {
+ return chance_of_replacing_branch_from_dead_block_with_exit_;
+ }
uint32_t GetChanceOfReplacingCopyMemoryWithLoadStore() {
return chance_of_replacing_copy_memory_with_load_store_;
}
@@ -470,6 +473,7 @@
uint32_t chance_of_propagating_instructions_up_;
uint32_t chance_of_pushing_id_through_variable_;
uint32_t chance_of_replacing_add_sub_mul_with_carrying_extended_;
+ uint32_t chance_of_replacing_branch_from_dead_block_with_exit_;
uint32_t chance_of_replacing_copy_memory_with_load_store_;
uint32_t chance_of_replacing_copyobject_with_store_load_;
uint32_t chance_of_replacing_id_with_synonym_;
diff --git a/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp
new file mode 100644
index 0000000..200aaad
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.cpp
@@ -0,0 +1,132 @@
+// 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_replace_branches_from_dead_blocks_with_exits.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassReplaceBranchesFromDeadBlocksWithExits::
+ FuzzerPassReplaceBranchesFromDeadBlocksWithExits(
+ opt::IRContext* ir_context,
+ TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassReplaceBranchesFromDeadBlocksWithExits::
+ ~FuzzerPassReplaceBranchesFromDeadBlocksWithExits() = default;
+
+void FuzzerPassReplaceBranchesFromDeadBlocksWithExits::Apply() {
+ // OpKill can only be used as a terminator in a function that is guaranteed
+ // to be executed with the Fragment execution model. We conservatively only
+ // allow OpKill if every entry point in the module has the Fragment execution
+ // model.
+ auto fragment_execution_model_guaranteed =
+ std::all_of(GetIRContext()->module()->entry_points().begin(),
+ GetIRContext()->module()->entry_points().end(),
+ [](const opt::Instruction& entry_point) -> bool {
+ return entry_point.GetSingleWordInOperand(0) ==
+ SpvExecutionModelFragment;
+ });
+
+ // Transformations of this type can disable one another. To avoid ordering
+ // bias, we therefore build a set of candidate transformations to apply, and
+ // subsequently apply them in a random order, skipping any that cease to be
+ // applicable.
+ std::vector<TransformationReplaceBranchFromDeadBlockWithExit>
+ candidate_transformations;
+
+ // Consider every block in every function.
+ for (auto& function : *GetIRContext()->module()) {
+ for (auto& block : function) {
+ // Probabilistically decide whether to skip this block.
+ if (GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()
+ ->GetChanceOfReplacingBranchFromDeadBlockWithExit())) {
+ continue;
+ }
+ // Check whether the block is suitable for having its terminator replaced.
+ if (!TransformationReplaceBranchFromDeadBlockWithExit::BlockIsSuitable(
+ GetIRContext(), *GetTransformationContext(), block)) {
+ continue;
+ }
+ // We can always use OpUnreachable to replace a block's terminator.
+ // Whether we can use OpKill depends on the execution model, and which of
+ // OpReturn and OpReturnValue we can use depends on the return type of the
+ // enclosing function.
+ std::vector<SpvOp> opcodes = {SpvOpUnreachable};
+ if (fragment_execution_model_guaranteed) {
+ opcodes.emplace_back(SpvOpKill);
+ }
+ auto function_return_type =
+ GetIRContext()->get_type_mgr()->GetType(function.type_id());
+ if (function_return_type->AsVoid()) {
+ opcodes.emplace_back(SpvOpReturn);
+ } else if (fuzzerutil::CanCreateConstant(*function_return_type)) {
+ // For simplicity we only allow OpReturnValue if the function return
+ // type is a type for which we can create a constant. This allows us a
+ // zero of the given type as a default return value.
+ opcodes.emplace_back(SpvOpReturnValue);
+ }
+ // Choose one of the available terminator opcodes at random and create a
+ // candidate transformation.
+ auto opcode = opcodes[GetFuzzerContext()->RandomIndex(opcodes)];
+ candidate_transformations.emplace_back(
+ TransformationReplaceBranchFromDeadBlockWithExit(
+ block.id(), opcode,
+ opcode == SpvOpReturnValue
+ ? FindOrCreateZeroConstant(function.type_id(), true)
+ : 0));
+ }
+ }
+
+ // Process the candidate transformations in a random order.
+ while (!candidate_transformations.empty()) {
+ // Transformations of this type can disable one another. For example,
+ // suppose we have dead blocks A, B, C, D arranged as follows:
+ //
+ // A |
+ // / \ |
+ // B C |
+ // \ / |
+ // D |
+ //
+ // Here we can replace the terminator of either B or C with an early exit,
+ // because D has two predecessors. But if we replace the terminator of B,
+ // say, we get:
+ //
+ // A |
+ // / \ |
+ // B C |
+ // / |
+ // D |
+ //
+ // and now it is no longer OK to replace the terminator of C as D only has
+ // one predecessor and we do not want to make D unreachable in the control
+ // flow graph.
+ MaybeApplyTransformation(
+ GetFuzzerContext()->RemoveAtRandomIndex(&candidate_transformations));
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h
new file mode 100644
index 0000000..62164b3
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h
@@ -0,0 +1,41 @@
+// 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_REPLACE_BRANCHES_FROM_DEAD_BLOCKS_WITH_EXITS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_REPLACE_BRANCHES_FROM_DEAD_BLOCKS_WITH_EXITS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Fuzzer pass that, under the right conditions, replaces branch instructions
+// from dead blocks with non-branching "exit" terminators, such as OpKill and
+// OpReturn.
+class FuzzerPassReplaceBranchesFromDeadBlocksWithExits : public FuzzerPass {
+ public:
+ FuzzerPassReplaceBranchesFromDeadBlocksWithExits(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassReplaceBranchesFromDeadBlocksWithExits() override;
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_REPLACE_BRANCHES_FROM_DEAD_BLOCKS_WITH_EXITS_H_
diff --git a/source/fuzz/pass_management/repeated_pass_instances.h b/source/fuzz/pass_management/repeated_pass_instances.h
index 8d2c0f8..6809d07 100644
--- a/source/fuzz/pass_management/repeated_pass_instances.h
+++ b/source/fuzz/pass_management/repeated_pass_instances.h
@@ -58,6 +58,7 @@
#include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
#include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
#include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
+#include "source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
#include "source/fuzz/fuzzer_pass_replace_copy_memories_with_loads_stores.h"
#include "source/fuzz/fuzzer_pass_replace_copy_objects_with_stores_loads.h"
#include "source/fuzz/fuzzer_pass_replace_irrelevant_ids.h"
@@ -150,6 +151,7 @@
REPEATED_PASS_INSTANCE(PropagateInstructionsUp);
REPEATED_PASS_INSTANCE(PushIdsThroughVariables);
REPEATED_PASS_INSTANCE(ReplaceAddsSubsMulsWithCarryingExtended);
+ REPEATED_PASS_INSTANCE(ReplaceBranchesFromDeadBlocksWithExits);
REPEATED_PASS_INSTANCE(ReplaceCopyMemoriesWithLoadsStores);
REPEATED_PASS_INSTANCE(ReplaceCopyObjectsWithStoresLoads);
REPEATED_PASS_INSTANCE(ReplaceLoadsStoresWithCopyMemories);
diff --git a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
index a6f024b..060c743 100644
--- a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
+++ b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
@@ -63,10 +63,12 @@
// - Dead blocks are great for adding function calls
// - Dead blocks are also great for adding loads and stores
// - The guard associated with a dead block can be obfuscated
- return RandomOrderAndNonNull({pass_instances_->GetAddFunctionCalls(),
- pass_instances_->GetAddLoads(),
- pass_instances_->GetAddStores(),
- pass_instances_->GetObfuscateConstants()});
+ // - Branches from dead blocks may be replaced with exits
+ return RandomOrderAndNonNull(
+ {pass_instances_->GetAddFunctionCalls(), pass_instances_->GetAddLoads(),
+ pass_instances_->GetAddStores(),
+ pass_instances_->GetObfuscateConstants(),
+ pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()});
}
if (&pass == pass_instances_->GetAddDeadBreaks()) {
// - The guard of the dead break is a good candidate for obfuscation
@@ -189,9 +191,12 @@
// - New functions in the module can be called
// - Donated dead functions produce irrelevant ids, which can be replaced
// - Donated functions are good candidates for having their returns merged
- return RandomOrderAndNonNull({pass_instances_->GetAddFunctionCalls(),
- pass_instances_->GetReplaceIrrelevantIds(),
- pass_instances_->GetMergeFunctionReturns()});
+ // - Donated dead functions may allow branches to be replaced with exits
+ return RandomOrderAndNonNull(
+ {pass_instances_->GetAddFunctionCalls(),
+ pass_instances_->GetReplaceIrrelevantIds(),
+ pass_instances_->GetMergeFunctionReturns(),
+ pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()});
}
if (&pass == pass_instances_->GetDuplicateRegionsWithSelections()) {
// - Parts of duplicated regions can be outlined
@@ -274,6 +279,11 @@
// No obvious follow-on passes
return {};
}
+ if (&pass == pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()) {
+ // - Changing a branch to OpReturnValue introduces an irrelevant id, which
+ // can be replaced
+ return RandomOrderAndNonNull({pass_instances_->GetReplaceIrrelevantIds()});
+ }
if (&pass == pass_instances_->GetReplaceCopyMemoriesWithLoadsStores()) {
// No obvious follow-on passes
return {};
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 20ab98e..e99d5f0 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -553,6 +553,7 @@
TransformationWrapRegionInSelection wrap_region_in_selection = 79;
TransformationAddEarlyTerminatorWrapper add_early_terminator_wrapper = 80;
TransformationPropagateInstructionDown propagate_instruction_down = 81;
+ TransformationReplaceBranchFromDeadBlockWithExit replace_branch_from_dead_block_with_exit = 82;
// Add additional option using the next available number.
}
}
@@ -1863,6 +1864,24 @@
}
+message TransformationReplaceBranchFromDeadBlockWithExit {
+
+ // Given a dead block that ends with OpBranch, replaces OpBranch with an
+ // "exit" instruction; one of OpReturn/OpReturnValue, OpKill (in a fragment
+ // shader) or OpUnreachable.
+
+ // The dead block whose terminator is to be replaced.
+ uint32 block_id = 1;
+
+ // The opcode of the new terminator.
+ uint32 opcode = 2;
+
+ // Ignored unless opcode is OpReturnValue, in which case this field provides
+ // a suitable result id to be returned.
+ uint32 return_value_id = 3;
+
+}
+
message TransformationReplaceParameterWithGlobal {
// Removes parameter with result id |parameter_id| from its function
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index cc3d010..28903a2 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -76,6 +76,7 @@
#include "source/fuzz/transformation_record_synonymous_constants.h"
#include "source/fuzz/transformation_replace_add_sub_mul_with_carrying_extended.h"
#include "source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h"
+#include "source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h"
#include "source/fuzz/transformation_replace_constant_with_uniform.h"
#include "source/fuzz/transformation_replace_copy_memory_with_load_store.h"
#include "source/fuzz/transformation_replace_copy_object_with_store_load.h"
@@ -283,6 +284,10 @@
return MakeUnique<TransformationReplaceBooleanConstantWithConstantBinary>(
message.replace_boolean_constant_with_constant_binary());
case protobufs::Transformation::TransformationCase::
+ kReplaceBranchFromDeadBlockWithExit:
+ return MakeUnique<TransformationReplaceBranchFromDeadBlockWithExit>(
+ message.replace_branch_from_dead_block_with_exit());
+ case protobufs::Transformation::TransformationCase::
kReplaceConstantWithUniform:
return MakeUnique<TransformationReplaceConstantWithUniform>(
message.replace_constant_with_uniform());
diff --git a/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp
new file mode 100644
index 0000000..561e8b6
--- /dev/null
+++ b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp
@@ -0,0 +1,169 @@
+// 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_replace_branch_from_dead_block_with_exit.h"
+
+#include "source/fuzz/fuzzer_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationReplaceBranchFromDeadBlockWithExit::
+ TransformationReplaceBranchFromDeadBlockWithExit(
+ const spvtools::fuzz::protobufs::
+ TransformationReplaceBranchFromDeadBlockWithExit& message)
+ : message_(message) {}
+
+TransformationReplaceBranchFromDeadBlockWithExit::
+ TransformationReplaceBranchFromDeadBlockWithExit(uint32_t block_id,
+ SpvOp opcode,
+ uint32_t return_value_id) {
+ message_.set_block_id(block_id);
+ message_.set_opcode(opcode);
+ message_.set_return_value_id(return_value_id);
+}
+
+bool TransformationReplaceBranchFromDeadBlockWithExit::IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const {
+ // The block whose terminator is to be changed must exist.
+ auto block = ir_context->get_instr_block(message_.block_id());
+ if (!block) {
+ return false;
+ }
+ if (!BlockIsSuitable(ir_context, transformation_context, *block)) {
+ return false;
+ }
+ auto function_return_type_id = block->GetParent()->type_id();
+ switch (message_.opcode()) {
+ case SpvOpKill:
+ for (auto& entry_point : ir_context->module()->entry_points()) {
+ if (entry_point.GetSingleWordInOperand(0) !=
+ SpvExecutionModelFragment) {
+ // OpKill is only allowed in a fragment shader. This is a
+ // conservative check: if the module contains a non-fragment entry
+ // point then adding an OpKill might lead to OpKill being used in a
+ // non-fragment shader.
+ return false;
+ }
+ }
+ break;
+ case SpvOpReturn:
+ if (ir_context->get_def_use_mgr()
+ ->GetDef(function_return_type_id)
+ ->opcode() != SpvOpTypeVoid) {
+ // OpReturn is only allowed in a function with void return type.
+ return false;
+ }
+ break;
+ case SpvOpReturnValue: {
+ // If the terminator is to be changed to OpReturnValue, with
+ // |message_.return_value_id| being the value that will be returned, then
+ // |message_.return_value_id| must have a compatible type and be available
+ // at the block terminator.
+ auto return_value =
+ ir_context->get_def_use_mgr()->GetDef(message_.return_value_id());
+ if (!return_value || return_value->type_id() != function_return_type_id) {
+ return false;
+ }
+ if (!fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, block->terminator(), message_.return_value_id())) {
+ return false;
+ }
+ break;
+ }
+ default:
+ assert(message_.opcode() == SpvOpUnreachable &&
+ "Invalid early exit opcode.");
+ break;
+ }
+ return true;
+}
+
+void TransformationReplaceBranchFromDeadBlockWithExit::Apply(
+ opt::IRContext* ir_context, TransformationContext* /*unused*/) const {
+ // If the successor block has OpPhi instructions then arguments related to
+ // |message_.block_id| need to be removed from these instruction.
+ auto block = ir_context->get_instr_block(message_.block_id());
+ assert(block->terminator()->opcode() == SpvOpBranch &&
+ "Precondition: the block must end with OpBranch.");
+ auto successor = ir_context->get_instr_block(
+ block->terminator()->GetSingleWordInOperand(0));
+ successor->ForEachPhiInst([block](opt::Instruction* phi_inst) {
+ opt::Instruction::OperandList new_phi_in_operands;
+ for (uint32_t i = 0; i < phi_inst->NumInOperands(); i += 2) {
+ if (phi_inst->GetSingleWordInOperand(i + 1) == block->id()) {
+ continue;
+ }
+ new_phi_in_operands.emplace_back(phi_inst->GetInOperand(i));
+ new_phi_in_operands.emplace_back(phi_inst->GetInOperand(i + 1));
+ }
+ assert(new_phi_in_operands.size() == phi_inst->NumInOperands() - 2);
+ phi_inst->SetInOperands(std::move(new_phi_in_operands));
+ });
+
+ // Rewrite the terminator of |message_.block_id|.
+ opt::Instruction::OperandList new_terminator_in_operands;
+ if (message_.opcode() == SpvOpReturnValue) {
+ new_terminator_in_operands.push_back(
+ {SPV_OPERAND_TYPE_TYPE_ID, {message_.return_value_id()}});
+ }
+ auto terminator = block->terminator();
+ terminator->SetOpcode(static_cast<SpvOp>(message_.opcode()));
+ terminator->SetInOperands(std::move(new_terminator_in_operands));
+ ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+std::unordered_set<uint32_t>
+TransformationReplaceBranchFromDeadBlockWithExit::GetFreshIds() const {
+ return std::unordered_set<uint32_t>();
+}
+
+protobufs::Transformation
+TransformationReplaceBranchFromDeadBlockWithExit::ToMessage() const {
+ protobufs::Transformation result;
+ *result.mutable_replace_branch_from_dead_block_with_exit() = message_;
+ return result;
+}
+
+bool TransformationReplaceBranchFromDeadBlockWithExit::BlockIsSuitable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context,
+ const opt::BasicBlock& block) {
+ // The block must be dead.
+ if (!transformation_context.GetFactManager()->BlockIsDead(block.id())) {
+ return false;
+ }
+ // The block's terminator must be OpBranch.
+ if (block.terminator()->opcode() != SpvOpBranch) {
+ return false;
+ }
+ if (ir_context->GetStructuredCFGAnalysis()->IsInContinueConstruct(
+ block.id())) {
+ // Early exits from continue constructs are not allowed as they would break
+ // the SPIR-V structured control flow rules.
+ return false;
+ }
+ // We only allow changing OpBranch to an early terminator if the target of the
+ // OpBranch has at least one other predecessor.
+ auto successor = ir_context->get_instr_block(
+ block.terminator()->GetSingleWordInOperand(0));
+ if (ir_context->cfg()->preds(successor->id()).size() < 2) {
+ return false;
+ }
+ return true;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h
new file mode 100644
index 0000000..e1418c9
--- /dev/null
+++ b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h
@@ -0,0 +1,84 @@
+// 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_REPLACE_BRANCH_FROM_DEAD_BLOCK_WITH_EXIT_H_
+#define SOURCE_FUZZ_TRANSFORMATION_REPLACE_BRANCH_FROM_DEAD_BLOCK_WITH_EXIT_H_
+
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/fuzz/transformation_context.h"
+#include "source/opt/basic_block.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationReplaceBranchFromDeadBlockWithExit : public Transformation {
+ public:
+ explicit TransformationReplaceBranchFromDeadBlockWithExit(
+ const protobufs::TransformationReplaceBranchFromDeadBlockWithExit&
+ message);
+
+ TransformationReplaceBranchFromDeadBlockWithExit(uint32_t block_id,
+ SpvOp opcode,
+ uint32_t return_value_id);
+
+ // - |message_.block_id| must be the id of a dead block that is not part of
+ // a continue construct
+ // - |message_.block_id| must end with OpBranch
+ // - The successor of |message_.block_id| must have at least one other
+ // predecessor
+ // - |message_.opcode()| must be one of OpKill, OpReturn, OpReturnValue and
+ // OpUnreachable
+ // - |message_.opcode()| can only be OpKill the module's entry points all
+ // have Fragment execution mode
+ // - |message_.opcode()| can only be OpReturn if the return type of the
+ // function containing the block is void
+ // - If |message_.opcode()| is OpReturnValue then |message_.return_value_id|
+ // must be an id that is available at the block terminator and that matches
+ // the return type of the enclosing function
+ bool IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const override;
+
+ // Changes the terminator of |message_.block_id| to have opcode
+ // |message_.opcode|, additionally with input operand
+ // |message_.return_value_id| in the case that |message_.opcode| is
+ // OpReturnValue.
+ //
+ // If |message_.block_id|'s successor starts with OpPhi instructions these are
+ // updated so that they no longer refer to |message_.block_id|.
+ void Apply(opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const override;
+
+ std::unordered_set<uint32_t> GetFreshIds() const override;
+
+ protobufs::Transformation ToMessage() const override;
+
+ // Returns true if and only if |block| meets the criteria for having its
+ // terminator replaced with an early exit (see IsApplicable for details of the
+ // criteria.)
+ static bool BlockIsSuitable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context,
+ const opt::BasicBlock& block);
+
+ private:
+ protobufs::TransformationReplaceBranchFromDeadBlockWithExit message_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_REPLACE_BRANCH_FROM_DEAD_BLOCK_WITH_EXIT_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index c42bd2d..d586425 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -92,6 +92,7 @@
transformation_push_id_through_variable_test.cpp
transformation_replace_add_sub_mul_with_carrying_extended_test.cpp
transformation_replace_boolean_constant_with_constant_binary_test.cpp
+ transformation_replace_branch_from_dead_block_with_exit_test.cpp
transformation_replace_copy_object_with_store_load_test.cpp
transformation_replace_constant_with_uniform_test.cpp
transformation_replace_copy_memory_with_load_store_test.cpp
diff --git a/test/fuzz/transformation_replace_branch_from_dead_block_with_exit_test.cpp b/test/fuzz/transformation_replace_branch_from_dead_block_with_exit_test.cpp
new file mode 100644
index 0000000..ee1252d
--- /dev/null
+++ b/test/fuzz/transformation_replace_branch_from_dead_block_with_exit_test.cpp
@@ -0,0 +1,560 @@
+// 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_replace_branch_from_dead_block_with_exit.h"
+
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest, BasicTest) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeBool
+ %7 = OpConstantFalse %6
+ %12 = OpTypeInt 32 1
+ %13 = OpTypePointer Function %12
+ %15 = OpConstant %12 1
+ %17 = OpConstant %12 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %14 = OpVariable %13 Function
+ OpSelectionMerge %9 None
+ OpBranchConditional %7 %8 %21
+ %8 = OpLabel
+ OpSelectionMerge %11 None
+ OpBranchConditional %7 %10 %16
+ %10 = OpLabel
+ OpStore %14 %15
+ OpBranch %20
+ %20 = OpLabel
+ OpBranch %11
+ %16 = OpLabel
+ OpStore %14 %17
+ OpBranch %11
+ %11 = OpLabel
+ OpBranch %9
+ %21 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ transformation_context.GetFactManager()->AddFactBlockIsDead(8);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(10);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(11);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(16);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(20);
+
+ // Bad: 4 is not a block
+ ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(4, SpvOpKill, 0)
+ .IsApplicable(context.get(), transformation_context));
+ // Bad: 200 does not exist
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(200, SpvOpKill, 0)
+ .IsApplicable(context.get(), transformation_context));
+ // Bad: 21 is not a dead block
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(21, SpvOpKill, 0)
+ .IsApplicable(context.get(), transformation_context));
+ // Bad: terminator of 8 is not OpBranch
+ ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(8, SpvOpKill, 0)
+ .IsApplicable(context.get(), transformation_context));
+ // Bad: 10's successor only has 10 as a predecessor
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(10, SpvOpKill, 0)
+ .IsApplicable(context.get(), transformation_context));
+
+#ifndef NDEBUG
+ ASSERT_DEATH(
+ TransformationReplaceBranchFromDeadBlockWithExit(20, SpvOpSwitch, 0)
+ .IsApplicable(context.get(), transformation_context),
+ "Invalid early exit opcode.");
+#endif
+
+ auto transformation1 =
+ TransformationReplaceBranchFromDeadBlockWithExit(20, SpvOpKill, 0);
+ auto transformation2 =
+ TransformationReplaceBranchFromDeadBlockWithExit(16, SpvOpKill, 0);
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), transformation_context));
+
+ ApplyAndCheckFreshIds(transformation1, context.get(),
+ &transformation_context);
+ // Applying transformation 1 should disable transformation 2
+ ASSERT_FALSE(
+ transformation2.IsApplicable(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 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeBool
+ %7 = OpConstantFalse %6
+ %12 = OpTypeInt 32 1
+ %13 = OpTypePointer Function %12
+ %15 = OpConstant %12 1
+ %17 = OpConstant %12 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %14 = OpVariable %13 Function
+ OpSelectionMerge %9 None
+ OpBranchConditional %7 %8 %21
+ %8 = OpLabel
+ OpSelectionMerge %11 None
+ OpBranchConditional %7 %10 %16
+ %10 = OpLabel
+ OpStore %14 %15
+ OpBranch %20
+ %20 = OpLabel
+ OpKill
+ %16 = OpLabel
+ OpStore %14 %17
+ OpBranch %11
+ %11 = OpLabel
+ OpBranch %9
+ %21 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest,
+ VertexShaderWithLoopInContinueConstruct) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Vertex %4 "main"
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypeFunction %6
+ %12 = OpTypePointer Function %6
+ %14 = OpConstant %6 0
+ %22 = OpConstant %6 10
+ %23 = OpTypeBool
+ %26 = OpConstant %6 1
+ %40 = OpConstant %6 100
+ %48 = OpConstantFalse %23
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %48 %49 %50
+ %49 = OpLabel
+ %51 = OpFunctionCall %6 %10
+ OpBranch %50
+ %50 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %6 None %7
+ %11 = OpLabel
+ %13 = OpVariable %12 Function
+ %15 = OpVariable %12 Function
+ %33 = OpVariable %12 Function
+ OpStore %33 %14
+ OpBranch %34
+ %34 = OpLabel
+ OpLoopMerge %36 %37 None
+ OpBranch %38
+ %38 = OpLabel
+ %39 = OpLoad %6 %33
+ %41 = OpSLessThan %23 %39 %40
+ OpBranchConditional %41 %35 %36
+ %35 = OpLabel
+ OpSelectionMerge %202 None
+ OpBranchConditional %48 %200 %201
+ %200 = OpLabel
+ OpBranch %202
+ %201 = OpLabel
+ %400 = OpCopyObject %6 %14
+ OpBranch %202
+ %202 = OpLabel
+ OpBranch %37
+ %37 = OpLabel
+ OpStore %13 %14
+ OpStore %15 %14
+ OpBranch %16
+ %16 = OpLabel
+ OpLoopMerge %18 %19 None
+ OpBranch %20
+ %20 = OpLabel
+ OpSelectionMerge %102 None
+ OpBranchConditional %48 %100 %101
+ %100 = OpLabel
+ OpBranch %102
+ %101 = OpLabel
+ OpBranch %102
+ %102 = OpLabel
+ %21 = OpLoad %6 %15
+ %24 = OpSLessThan %23 %21 %22
+ OpBranchConditional %24 %17 %18
+ %17 = OpLabel
+ OpSelectionMerge %302 None
+ OpBranchConditional %48 %300 %301
+ %300 = OpLabel
+ OpBranch %302
+ %301 = OpLabel
+ OpBranch %302
+ %302 = OpLabel
+ %25 = OpLoad %6 %13
+ %27 = OpIAdd %6 %25 %26
+ OpStore %13 %27
+ OpBranch %19
+ %19 = OpLabel
+ %28 = OpLoad %6 %15
+ %29 = OpIAdd %6 %28 %26
+ OpStore %15 %29
+ OpBranch %16
+ %18 = OpLabel
+ %30 = OpLoad %6 %13
+ %42 = OpCopyObject %6 %30
+ %43 = OpLoad %6 %33
+ %44 = OpIAdd %6 %43 %42
+ OpStore %33 %44
+ OpBranch %34
+ %36 = OpLabel
+ %45 = OpLoad %6 %33
+ OpReturnValue %45
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ for (auto block : {16, 17, 18, 19, 20, 34, 35, 36, 37, 38,
+ 49, 100, 101, 102, 200, 201, 202, 300, 301, 302}) {
+ transformation_context.GetFactManager()->AddFactBlockIsDead(block);
+ }
+
+ // Bad: OpKill not allowed in vertex shader
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(201, SpvOpKill, 0)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Bad: OpReturn is not allowed in function that expects a returned value.
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(200, SpvOpReturn, 0)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Bad: Return value id does not exist
+ ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+ 201, SpvOpReturnValue, 1000)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Bad: Return value id does not have a type
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(200, SpvOpReturnValue, 6)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Bad: Return value id does not have the right type
+ ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+ 201, SpvOpReturnValue, 48)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Bad: Return value id is not available
+ ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+ 200, SpvOpReturnValue, 400)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Bad: Early exit now allowed in continue construct
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(101, SpvOpUnreachable, 0)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Bad: Early exit now allowed in continue construct (again)
+ ASSERT_FALSE(TransformationReplaceBranchFromDeadBlockWithExit(
+ 300, SpvOpReturnValue, 14)
+ .IsApplicable(context.get(), transformation_context));
+
+ auto transformation1 = TransformationReplaceBranchFromDeadBlockWithExit(
+ 200, SpvOpUnreachable, 0);
+ auto transformation2 = TransformationReplaceBranchFromDeadBlockWithExit(
+ 201, SpvOpReturnValue, 400);
+
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), transformation_context));
+
+ ApplyAndCheckFreshIds(transformation2, context.get(),
+ &transformation_context);
+ ASSERT_FALSE(
+ transformation1.IsApplicable(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 Vertex %4 "main"
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypeFunction %6
+ %12 = OpTypePointer Function %6
+ %14 = OpConstant %6 0
+ %22 = OpConstant %6 10
+ %23 = OpTypeBool
+ %26 = OpConstant %6 1
+ %40 = OpConstant %6 100
+ %48 = OpConstantFalse %23
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %50 None
+ OpBranchConditional %48 %49 %50
+ %49 = OpLabel
+ %51 = OpFunctionCall %6 %10
+ OpBranch %50
+ %50 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ %10 = OpFunction %6 None %7
+ %11 = OpLabel
+ %13 = OpVariable %12 Function
+ %15 = OpVariable %12 Function
+ %33 = OpVariable %12 Function
+ OpStore %33 %14
+ OpBranch %34
+ %34 = OpLabel
+ OpLoopMerge %36 %37 None
+ OpBranch %38
+ %38 = OpLabel
+ %39 = OpLoad %6 %33
+ %41 = OpSLessThan %23 %39 %40
+ OpBranchConditional %41 %35 %36
+ %35 = OpLabel
+ OpSelectionMerge %202 None
+ OpBranchConditional %48 %200 %201
+ %200 = OpLabel
+ OpBranch %202
+ %201 = OpLabel
+ %400 = OpCopyObject %6 %14
+ OpReturnValue %400
+ %202 = OpLabel
+ OpBranch %37
+ %37 = OpLabel
+ OpStore %13 %14
+ OpStore %15 %14
+ OpBranch %16
+ %16 = OpLabel
+ OpLoopMerge %18 %19 None
+ OpBranch %20
+ %20 = OpLabel
+ OpSelectionMerge %102 None
+ OpBranchConditional %48 %100 %101
+ %100 = OpLabel
+ OpBranch %102
+ %101 = OpLabel
+ OpBranch %102
+ %102 = OpLabel
+ %21 = OpLoad %6 %15
+ %24 = OpSLessThan %23 %21 %22
+ OpBranchConditional %24 %17 %18
+ %17 = OpLabel
+ OpSelectionMerge %302 None
+ OpBranchConditional %48 %300 %301
+ %300 = OpLabel
+ OpBranch %302
+ %301 = OpLabel
+ OpBranch %302
+ %302 = OpLabel
+ %25 = OpLoad %6 %13
+ %27 = OpIAdd %6 %25 %26
+ OpStore %13 %27
+ OpBranch %19
+ %19 = OpLabel
+ %28 = OpLoad %6 %15
+ %29 = OpIAdd %6 %28 %26
+ OpStore %15 %29
+ OpBranch %16
+ %18 = OpLabel
+ %30 = OpLoad %6 %13
+ %42 = OpCopyObject %6 %30
+ %43 = OpLoad %6 %33
+ %44 = OpIAdd %6 %43 %42
+ OpStore %33 %44
+ OpBranch %34
+ %36 = OpLabel
+ %45 = OpLoad %6 %33
+ OpReturnValue %45
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest, OpPhi) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeBool
+ %7 = OpConstantFalse %6
+ %12 = OpTypeInt 32 1
+ %13 = OpTypePointer Function %12
+ %15 = OpConstant %12 1
+ %17 = OpConstant %12 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %14 = OpVariable %13 Function
+ OpSelectionMerge %9 None
+ OpBranchConditional %7 %8 %21
+ %8 = OpLabel
+ OpSelectionMerge %11 None
+ OpBranchConditional %7 %10 %16
+ %10 = OpLabel
+ OpStore %14 %15
+ OpBranch %20
+ %20 = OpLabel
+ %48 = OpCopyObject %12 %15
+ OpBranch %11
+ %16 = OpLabel
+ OpStore %14 %17
+ %49 = OpCopyObject %12 %17
+ OpBranch %11
+ %11 = OpLabel
+ %50 = OpPhi %12 %48 %20 %49 %16
+ OpBranch %9
+ %21 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ transformation_context.GetFactManager()->AddFactBlockIsDead(8);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(10);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(11);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(16);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(20);
+
+ auto transformation1 =
+ TransformationReplaceBranchFromDeadBlockWithExit(20, SpvOpKill, 0);
+ auto transformation2 =
+ TransformationReplaceBranchFromDeadBlockWithExit(16, SpvOpKill, 0);
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), transformation_context));
+
+ ApplyAndCheckFreshIds(transformation1, context.get(),
+ &transformation_context);
+ // Applying transformation 1 should disable transformation 2
+ ASSERT_FALSE(
+ transformation2.IsApplicable(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 320
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeBool
+ %7 = OpConstantFalse %6
+ %12 = OpTypeInt 32 1
+ %13 = OpTypePointer Function %12
+ %15 = OpConstant %12 1
+ %17 = OpConstant %12 2
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %14 = OpVariable %13 Function
+ OpSelectionMerge %9 None
+ OpBranchConditional %7 %8 %21
+ %8 = OpLabel
+ OpSelectionMerge %11 None
+ OpBranchConditional %7 %10 %16
+ %10 = OpLabel
+ OpStore %14 %15
+ OpBranch %20
+ %20 = OpLabel
+ %48 = OpCopyObject %12 %15
+ OpKill
+ %16 = OpLabel
+ OpStore %14 %17
+ %49 = OpCopyObject %12 %17
+ OpBranch %11
+ %11 = OpLabel
+ %50 = OpPhi %12 %49 %16
+ OpBranch %9
+ %21 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
