spirv-fuzz: Fix the bug in TransformationReplaceBranchFromDeadBlockWithExit (#4140)
Fixes #4136.
diff --git a/source/fuzz/fuzzer_util.cpp b/source/fuzz/fuzzer_util.cpp
index 8a23392..15c7246 100644
--- a/source/fuzz/fuzzer_util.cpp
+++ b/source/fuzz/fuzzer_util.cpp
@@ -25,6 +25,25 @@
namespace fuzzerutil {
namespace {
+// A utility class that uses RAII to change and restore the terminator
+// instruction of the |block|.
+class ChangeTerminatorRAII {
+ public:
+ explicit ChangeTerminatorRAII(opt::BasicBlock* block,
+ opt::Instruction new_terminator)
+ : block_(block), old_terminator_(std::move(*block->terminator())) {
+ *block_->terminator() = std::move(new_terminator);
+ }
+
+ ~ChangeTerminatorRAII() {
+ *block_->terminator() = std::move(old_terminator_);
+ }
+
+ private:
+ opt::BasicBlock* block_;
+ opt::Instruction old_terminator_;
+};
+
uint32_t MaybeGetOpConstant(opt::IRContext* ir_context,
const TransformationContext& transformation_context,
const std::vector<uint32_t>& words,
@@ -163,35 +182,46 @@
return true;
}
-void AddUnreachableEdgeAndUpdateOpPhis(
- opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
- uint32_t bool_id,
- const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids) {
- assert(PhiIdsOkForNewEdge(context, bb_from, bb_to, phi_ids) &&
- "Precondition on phi_ids is not satisfied");
+opt::Instruction CreateUnreachableEdgeInstruction(opt::IRContext* ir_context,
+ uint32_t bb_from_id,
+ uint32_t bb_to_id,
+ uint32_t bool_id) {
+ const auto* bb_from = MaybeFindBlock(ir_context, bb_from_id);
+ assert(bb_from && "|bb_from_id| is invalid");
+ assert(MaybeFindBlock(ir_context, bb_to_id) && "|bb_to_id| is invalid");
assert(bb_from->terminator()->opcode() == SpvOpBranch &&
"Precondition on terminator of bb_from is not satisfied");
// Get the id of the boolean constant to be used as the condition.
- auto condition_inst = context->get_def_use_mgr()->GetDef(bool_id);
+ auto condition_inst = ir_context->get_def_use_mgr()->GetDef(bool_id);
assert(condition_inst &&
(condition_inst->opcode() == SpvOpConstantTrue ||
condition_inst->opcode() == SpvOpConstantFalse) &&
"|bool_id| is invalid");
auto condition_value = condition_inst->opcode() == SpvOpConstantTrue;
-
- const bool from_to_edge_already_exists = bb_from->IsSuccessor(bb_to);
- auto successor = bb_from->terminator()->GetSingleWordInOperand(0);
+ auto successor_id = bb_from->terminator()->GetSingleWordInOperand(0);
// Add the dead branch, by turning OpBranch into OpBranchConditional, and
// ordering the targets depending on whether the given boolean corresponds to
// true or false.
- bb_from->terminator()->SetOpcode(SpvOpBranchConditional);
- bb_from->terminator()->SetInOperands(
+ return opt::Instruction(
+ ir_context, SpvOpBranchConditional, 0, 0,
{{SPV_OPERAND_TYPE_ID, {bool_id}},
- {SPV_OPERAND_TYPE_ID, {condition_value ? successor : bb_to->id()}},
- {SPV_OPERAND_TYPE_ID, {condition_value ? bb_to->id() : successor}}});
+ {SPV_OPERAND_TYPE_ID, {condition_value ? successor_id : bb_to_id}},
+ {SPV_OPERAND_TYPE_ID, {condition_value ? bb_to_id : successor_id}}});
+}
+
+void AddUnreachableEdgeAndUpdateOpPhis(
+ opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
+ uint32_t bool_id,
+ const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids) {
+ assert(PhiIdsOkForNewEdge(context, bb_from, bb_to, phi_ids) &&
+ "Precondition on phi_ids is not satisfied");
+
+ const bool from_to_edge_already_exists = bb_from->IsSuccessor(bb_to);
+ *bb_from->terminator() = CreateUnreachableEdgeInstruction(
+ context, bb_from->id(), bb_to->id(), bool_id);
// Update OpPhi instructions in the target block if this branch adds a
// previously non-existent edge from source to target.
@@ -1856,6 +1886,104 @@
return result;
}
+bool NewTerminatorPreservesDominationRules(opt::IRContext* ir_context,
+ uint32_t block_id,
+ opt::Instruction new_terminator) {
+ auto* mutated_block = MaybeFindBlock(ir_context, block_id);
+ assert(mutated_block && "|block_id| is invalid");
+
+ ChangeTerminatorRAII change_terminator_raii(mutated_block,
+ std::move(new_terminator));
+ opt::DominatorAnalysis dominator_analysis;
+ dominator_analysis.InitializeTree(*ir_context->cfg(),
+ mutated_block->GetParent());
+
+ // Check that each dominator appears before each dominated block.
+ std::unordered_map<uint32_t, size_t> positions;
+ for (const auto& block : *mutated_block->GetParent()) {
+ positions[block.id()] = positions.size();
+ }
+
+ std::queue<uint32_t> q({mutated_block->GetParent()->begin()->id()});
+ std::unordered_set<uint32_t> visited;
+ while (!q.empty()) {
+ auto block = q.front();
+ q.pop();
+ visited.insert(block);
+
+ auto success = ir_context->cfg()->block(block)->WhileEachSuccessorLabel(
+ [&positions, &visited, &dominator_analysis, block, &q](uint32_t id) {
+ if (id == block) {
+ // Handle the case when loop header and continue target are the same
+ // block.
+ return true;
+ }
+
+ if (dominator_analysis.Dominates(block, id) &&
+ positions[block] > positions[id]) {
+ // |block| dominates |id| but appears after |id| - violates
+ // domination rules.
+ return false;
+ }
+
+ if (!visited.count(id)) {
+ q.push(id);
+ }
+
+ return true;
+ });
+
+ if (!success) {
+ return false;
+ }
+ }
+
+ // For each instruction in the |block->GetParent()| function check whether
+ // all its dependencies satisfy domination rules (i.e. all id operands
+ // dominate that instruction).
+ for (const auto& block : *mutated_block->GetParent()) {
+ if (!dominator_analysis.IsReachable(&block)) {
+ // If some block is not reachable then we don't need to worry about the
+ // preservation of domination rules for its instructions.
+ continue;
+ }
+
+ for (const auto& inst : block) {
+ for (uint32_t i = 0; i < inst.NumInOperands();
+ i += inst.opcode() == SpvOpPhi ? 2 : 1) {
+ const auto& operand = inst.GetInOperand(i);
+ if (!spvIsInIdType(operand.type)) {
+ continue;
+ }
+
+ if (MaybeFindBlock(ir_context, operand.words[0])) {
+ // Ignore operands that refer to OpLabel instructions.
+ continue;
+ }
+
+ const auto* dependency_block =
+ ir_context->get_instr_block(operand.words[0]);
+ if (!dependency_block) {
+ // A global instruction always dominates all instructions in any
+ // function.
+ continue;
+ }
+
+ auto domination_target_id = inst.opcode() == SpvOpPhi
+ ? inst.GetSingleWordInOperand(i + 1)
+ : block.id();
+
+ if (!dominator_analysis.Dominates(dependency_block->id(),
+ domination_target_id)) {
+ return false;
+ }
+ }
+ }
+ }
+
+ return true;
+}
+
} // namespace fuzzerutil
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/fuzzer_util.h b/source/fuzz/fuzzer_util.h
index 3bb1aa6..cc212bc 100644
--- a/source/fuzz/fuzzer_util.h
+++ b/source/fuzz/fuzzer_util.h
@@ -68,6 +68,16 @@
opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids);
+// Returns an OpBranchConditional instruction that will create an unreachable
+// branch from |bb_from_id| to |bb_to_id|. |bool_id| must be a result id of
+// either OpConstantTrue or OpConstantFalse. Based on the opcode of |bool_id|,
+// operands of the returned instruction will be positioned in a way that the
+// branch from |bb_from_id| to |bb_to_id| is always unreachable.
+opt::Instruction CreateUnreachableEdgeInstruction(opt::IRContext* ir_context,
+ uint32_t bb_from_id,
+ uint32_t bb_to_id,
+ uint32_t bool_id);
+
// Requires that |bool_id| is a valid result id of either OpConstantTrue or
// OpConstantFalse, that PhiIdsOkForNewEdge(context, bb_from, bb_to, phi_ids)
// holds, and that bb_from ends with "OpBranch %some_block". Turns OpBranch
@@ -597,6 +607,14 @@
std::set<uint32_t> GetReachableReturnBlocks(opt::IRContext* ir_context,
uint32_t function_id);
+// Returns true if changing terminator instruction to |new_terminator| in the
+// basic block with id |block_id| preserves domination rules and valid block
+// order (i.e. dominator must always appear before dominated in the CFG).
+// Returns false otherwise.
+bool NewTerminatorPreservesDominationRules(opt::IRContext* ir_context,
+ uint32_t block_id,
+ opt::Instruction new_terminator);
+
} // namespace fuzzerutil
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/transformation_add_dead_break.cpp b/source/fuzz/transformation_add_dead_break.cpp
index bc938d4..56cd92b 100644
--- a/source/fuzz/transformation_add_dead_break.cpp
+++ b/source/fuzz/transformation_add_dead_break.cpp
@@ -112,9 +112,10 @@
const TransformationContext& transformation_context) const {
// First, we check that a constant with the same value as
// |message_.break_condition_value| is present.
- if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
- message_.break_condition_value(),
- false)) {
+ const auto bool_id =
+ fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
+ message_.break_condition_value(), false);
+ if (!bool_id) {
// The required constant is not present, so the transformation cannot be
// applied.
return false;
@@ -171,25 +172,23 @@
}
// Adding the dead break is only valid if SPIR-V rules related to dominance
- // hold. Rather than checking these rules explicitly, we defer to the
- // validator. We make a clone of the module, apply the transformation to the
- // clone, and check whether the transformed clone is valid.
- //
- // In principle some of the above checks could be removed, with more reliance
- // being places on the validator. This should be revisited if we are sure
- // the validator is complete with respect to checking structured control flow
- // rules.
- auto cloned_context = fuzzerutil::CloneIRContext(ir_context);
- ApplyImpl(cloned_context.get(), transformation_context);
- return fuzzerutil::IsValid(cloned_context.get(),
- transformation_context.GetValidatorOptions(),
- fuzzerutil::kSilentMessageConsumer);
+ // hold.
+ return fuzzerutil::NewTerminatorPreservesDominationRules(
+ ir_context, message_.from_block(),
+ fuzzerutil::CreateUnreachableEdgeInstruction(
+ ir_context, message_.from_block(), message_.to_block(), bool_id));
}
void TransformationAddDeadBreak::Apply(
opt::IRContext* ir_context,
TransformationContext* transformation_context) const {
- ApplyImpl(ir_context, *transformation_context);
+ fuzzerutil::AddUnreachableEdgeAndUpdateOpPhis(
+ ir_context, ir_context->cfg()->block(message_.from_block()),
+ ir_context->cfg()->block(message_.to_block()),
+ fuzzerutil::MaybeGetBoolConstant(ir_context, *transformation_context,
+ message_.break_condition_value(), false),
+ message_.phi_id());
+
// Invalidate all analyses
ir_context->InvalidateAnalysesExceptFor(
opt::IRContext::Analysis::kAnalysisNone);
@@ -201,17 +200,6 @@
return result;
}
-void TransformationAddDeadBreak::ApplyImpl(
- spvtools::opt::IRContext* ir_context,
- const TransformationContext& transformation_context) const {
- fuzzerutil::AddUnreachableEdgeAndUpdateOpPhis(
- ir_context, ir_context->cfg()->block(message_.from_block()),
- ir_context->cfg()->block(message_.to_block()),
- fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
- message_.break_condition_value(), false),
- message_.phi_id());
-}
-
std::unordered_set<uint32_t> TransformationAddDeadBreak::GetFreshIds() const {
return std::unordered_set<uint32_t>();
}
diff --git a/source/fuzz/transformation_add_dead_break.h b/source/fuzz/transformation_add_dead_break.h
index afb8dc7..b050260 100644
--- a/source/fuzz/transformation_add_dead_break.h
+++ b/source/fuzz/transformation_add_dead_break.h
@@ -71,15 +71,6 @@
bool AddingBreakRespectsStructuredControlFlow(opt::IRContext* ir_context,
opt::BasicBlock* bb_from) const;
- // Used by 'Apply' to actually apply the transformation to the module of
- // interest, and by 'IsApplicable' to do a dry-run of the transformation on a
- // cloned module, in order to check that the transformation leads to a valid
- // module. This is only invoked by 'IsApplicable' after certain basic
- // applicability checks have been made, ensuring that the invocation of this
- // method is legal.
- void ApplyImpl(opt::IRContext* ir_context,
- const TransformationContext& transformation_context) const;
-
protobufs::TransformationAddDeadBreak message_;
};
diff --git a/source/fuzz/transformation_add_dead_continue.cpp b/source/fuzz/transformation_add_dead_continue.cpp
index 18b3c39..c3bdb4a 100644
--- a/source/fuzz/transformation_add_dead_continue.cpp
+++ b/source/fuzz/transformation_add_dead_continue.cpp
@@ -38,9 +38,10 @@
const TransformationContext& transformation_context) const {
// First, we check that a constant with the same value as
// |message_.continue_condition_value| is present.
- if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
- message_.continue_condition_value(),
- false)) {
+ const auto bool_id = fuzzerutil::MaybeGetBoolConstant(
+ ir_context, transformation_context, message_.continue_condition_value(),
+ false);
+ if (!bool_id) {
// The required constant is not present, so the transformation cannot be
// applied.
return false;
@@ -111,39 +112,16 @@
}
// Adding the dead break is only valid if SPIR-V rules related to dominance
- // hold. Rather than checking these rules explicitly, we defer to the
- // validator. We make a clone of the module, apply the transformation to the
- // clone, and check whether the transformed clone is valid.
- //
- // In principle some of the above checks could be removed, with more reliance
- // being placed on the validator. This should be revisited if we are sure
- // the validator is complete with respect to checking structured control flow
- // rules.
- auto cloned_context = fuzzerutil::CloneIRContext(ir_context);
- ApplyImpl(cloned_context.get(), transformation_context);
- return fuzzerutil::IsValid(cloned_context.get(),
- transformation_context.GetValidatorOptions(),
- fuzzerutil::kSilentMessageConsumer);
+ // hold.
+ return fuzzerutil::NewTerminatorPreservesDominationRules(
+ ir_context, message_.from_block(),
+ fuzzerutil::CreateUnreachableEdgeInstruction(
+ ir_context, message_.from_block(), continue_block, bool_id));
}
void TransformationAddDeadContinue::Apply(
opt::IRContext* ir_context,
TransformationContext* transformation_context) const {
- ApplyImpl(ir_context, *transformation_context);
- // Invalidate all analyses
- ir_context->InvalidateAnalysesExceptFor(
- opt::IRContext::Analysis::kAnalysisNone);
-}
-
-protobufs::Transformation TransformationAddDeadContinue::ToMessage() const {
- protobufs::Transformation result;
- *result.mutable_add_dead_continue() = message_;
- return result;
-}
-
-void TransformationAddDeadContinue::ApplyImpl(
- spvtools::opt::IRContext* ir_context,
- const TransformationContext& transformation_context) const {
auto bb_from = ir_context->cfg()->block(message_.from_block());
auto continue_block =
bb_from->IsLoopHeader()
@@ -153,10 +131,20 @@
assert(continue_block && "message_.from_block must be in a loop.");
fuzzerutil::AddUnreachableEdgeAndUpdateOpPhis(
ir_context, bb_from, ir_context->cfg()->block(continue_block),
- fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
+ fuzzerutil::MaybeGetBoolConstant(ir_context, *transformation_context,
message_.continue_condition_value(),
false),
message_.phi_id());
+
+ // Invalidate all analyses
+ ir_context->InvalidateAnalysesExceptFor(
+ opt::IRContext::Analysis::kAnalysisNone);
+}
+
+protobufs::Transformation TransformationAddDeadContinue::ToMessage() const {
+ protobufs::Transformation result;
+ *result.mutable_add_dead_continue() = message_;
+ return result;
}
std::unordered_set<uint32_t> TransformationAddDeadContinue::GetFreshIds()
diff --git a/source/fuzz/transformation_add_dead_continue.h b/source/fuzz/transformation_add_dead_continue.h
index 27527e7..c78b907 100644
--- a/source/fuzz/transformation_add_dead_continue.h
+++ b/source/fuzz/transformation_add_dead_continue.h
@@ -68,15 +68,6 @@
protobufs::Transformation ToMessage() const override;
private:
- // Used by 'Apply' to actually apply the transformation to the module of
- // interest, and by 'IsApplicable' to do a dry-run of the transformation on a
- // cloned module, in order to check that the transformation leads to a valid
- // module. This is only invoked by 'IsApplicable' after certain basic
- // applicability checks have been made, ensuring that the invocation of this
- // method is legal.
- void ApplyImpl(opt::IRContext* ir_context,
- const TransformationContext& transformation_context) const;
-
protobufs::TransformationAddDeadContinue message_;
};
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
index e809012..78b54c4 100644
--- a/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp
+++ b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.cpp
@@ -162,7 +162,10 @@
if (ir_context->cfg()->preds(successor->id()).size() < 2) {
return false;
}
- return true;
+ // Make sure that domination rules are satisfied when we remove the branch
+ // from the |block| to its |successor|.
+ return fuzzerutil::NewTerminatorPreservesDominationRules(
+ ir_context, block.id(), {ir_context, SpvOpUnreachable});
}
} // namespace fuzz
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
index e1418c9..e0f596e 100644
--- a/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h
+++ b/source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h
@@ -41,13 +41,17 @@
// predecessor
// - |message_.opcode()| must be one of OpKill, OpReturn, OpReturnValue and
// OpUnreachable
- // - |message_.opcode()| can only be OpKill the module's entry points all
+ // - |message_.opcode()| can only be OpKill if 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
+ // - Domination rules should be preserved when we apply this transformation.
+ // In particular, if some block appears after the |block_id|'s successor in
+ // the CFG, then that block cannot dominate |block_id|'s successor when this
+ // transformation is applied.
bool IsApplicable(
opt::IRContext* ir_context,
const TransformationContext& transformation_context) const override;
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
index 4532503..6bba14f 100644
--- 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
@@ -566,6 +566,302 @@
ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
}
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest,
+ DominatorAfterDeadBlockSuccessor) {
+ 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
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %8 None
+ OpBranchConditional %7 %9 %10
+ %9 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ %12 = OpCopyObject %6 %7
+ OpBranch %8
+ %10 = OpLabel
+ OpBranch %13
+ %8 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ OpBranch %8
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ spvtools::ValidatorOptions validator_options;
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ transformation_context.GetFactManager()->AddFactBlockIsDead(9);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(11);
+
+ ASSERT_FALSE(
+ TransformationReplaceBranchFromDeadBlockWithExit(11, SpvOpUnreachable, 0)
+ .IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest,
+ UnreachableSuccessor) {
+ 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
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %8 None
+ OpBranchConditional %7 %9 %10
+ %9 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ %12 = OpCopyObject %6 %7
+ OpBranch %8
+ %10 = OpLabel
+ OpReturn
+ %8 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ OpBranch %8
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ spvtools::ValidatorOptions validator_options;
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ transformation_context.GetFactManager()->AddFactBlockIsDead(9);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(11);
+
+ TransformationReplaceBranchFromDeadBlockWithExit transformation(
+ 11, SpvOpUnreachable, 0);
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ transformation.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+
+ 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
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %8 None
+ OpBranchConditional %7 %9 %10
+ %9 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ %12 = OpCopyObject %6 %7
+ OpUnreachable
+ %10 = OpLabel
+ OpReturn
+ %8 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ OpBranch %8
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest,
+ DeadBlockAfterItsSuccessor) {
+ 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 = OpConstantTrue %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %8 None
+ OpBranchConditional %7 %9 %10
+ %9 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ %12 = OpCopyObject %6 %7
+ OpBranch %8
+ %10 = OpLabel
+ OpBranch %13
+ %8 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ OpBranch %8
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ spvtools::ValidatorOptions validator_options;
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ transformation_context.GetFactManager()->AddFactBlockIsDead(10);
+ transformation_context.GetFactManager()->AddFactBlockIsDead(13);
+
+ TransformationReplaceBranchFromDeadBlockWithExit transformation(
+ 13, SpvOpUnreachable, 0);
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ transformation.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+
+ 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 = OpConstantTrue %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %8 None
+ OpBranchConditional %7 %9 %10
+ %9 = OpLabel
+ OpBranch %11
+ %11 = OpLabel
+ %12 = OpCopyObject %6 %7
+ OpBranch %8
+ %10 = OpLabel
+ OpBranch %13
+ %8 = OpLabel
+ OpReturn
+ %13 = OpLabel
+ OpUnreachable
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationReplaceBranchFromDeadBlockWithExitTest,
+ BranchToOuterMergeBlock) {
+ 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 = OpConstantTrue %6
+ %15 = OpTypeInt 32 0
+ %14 = OpUndef %15
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %8 None
+ OpSwitch %14 %9 1 %8
+ %9 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %7 %11 %10
+ %8 = OpLabel
+ OpReturn
+ %11 = OpLabel
+ OpBranch %8
+ %10 = OpLabel
+ OpBranch %8
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_4;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ spvtools::ValidatorOptions validator_options;
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ transformation_context.GetFactManager()->AddFactBlockIsDead(10);
+
+ TransformationReplaceBranchFromDeadBlockWithExit transformation(
+ 10, SpvOpUnreachable, 0);
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ transformation.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
+ kConsoleMessageConsumer));
+
+ 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 = OpConstantTrue %6
+ %15 = OpTypeInt 32 0
+ %14 = OpUndef %15
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %8 None
+ OpSwitch %14 %9 1 %8
+ %9 = OpLabel
+ OpSelectionMerge %10 None
+ OpBranchConditional %7 %11 %10
+ %8 = OpLabel
+ OpReturn
+ %11 = OpLabel
+ OpBranch %8
+ %10 = OpLabel
+ OpUnreachable
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
} // namespace
} // namespace fuzz
} // namespace spvtools