Transformation and fuzzer pass to add dead continues (#2758)
Similar to the existing 'add dead breaks' pass, this adds a pass to
add dead continues to blocks in loops where such a transformation is
viable. Various functionality common to this new pass and 'add dead
breaks' has been factored into 'fuzzer_util', and some small
improvements to 'add dead breaks' that were identified while reviewing
that code again have been applied.
Fixes #2719.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 75e2125..fbabba1 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -31,6 +31,7 @@
fuzzer_context.h
fuzzer_pass.h
fuzzer_pass_add_dead_breaks.h
+ fuzzer_pass_add_dead_continues.h
fuzzer_pass_add_useful_constructs.h
fuzzer_pass_obfuscate_constants.h
fuzzer_pass_permute_blocks.h
@@ -46,6 +47,7 @@
transformation_add_constant_boolean.h
transformation_add_constant_scalar.h
transformation_add_dead_break.h
+ transformation_add_dead_continue.h
transformation_add_type_boolean.h
transformation_add_type_float.h
transformation_add_type_int.h
@@ -62,6 +64,7 @@
fuzzer_context.cpp
fuzzer_pass.cpp
fuzzer_pass_add_dead_breaks.cpp
+ fuzzer_pass_add_dead_continues.cpp
fuzzer_pass_add_useful_constructs.cpp
fuzzer_pass_obfuscate_constants.cpp
fuzzer_pass_permute_blocks.cpp
@@ -76,6 +79,7 @@
transformation_add_constant_boolean.cpp
transformation_add_constant_scalar.cpp
transformation_add_dead_break.cpp
+ transformation_add_dead_continue.cpp
transformation_add_type_boolean.cpp
transformation_add_type_float.cpp
transformation_add_type_int.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 0fa645a..89250a0 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -20,6 +20,7 @@
#include "source/fuzz/fact_manager.h"
#include "source/fuzz/fuzzer_context.h"
#include "source/fuzz/fuzzer_pass_add_dead_breaks.h"
+#include "source/fuzz/fuzzer_pass_add_dead_continues.h"
#include "source/fuzz/fuzzer_pass_add_useful_constructs.h"
#include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
#include "source/fuzz/fuzzer_pass_permute_blocks.h"
@@ -112,6 +113,9 @@
FuzzerPassAddDeadBreaks(ir_context.get(), &fact_manager, &fuzzer_context,
transformation_sequence_out)
.Apply();
+ FuzzerPassAddDeadContinues(ir_context.get(), &fact_manager, &fuzzer_context,
+ transformation_sequence_out)
+ .Apply();
FuzzerPassObfuscateConstants(ir_context.get(), &fact_manager, &fuzzer_context,
transformation_sequence_out)
.Apply();
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 9252341..c8e7719 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -25,6 +25,7 @@
// Keep them in alphabetical order.
const uint32_t kDefaultChanceOfAddingDeadBreak = 20;
+const uint32_t kDefaultChanceOfAddingDeadContinue = 20;
const uint32_t kDefaultChanceOfMovingBlockDown = 25;
const uint32_t kDefaultChanceOfObfuscatingConstant = 20;
const uint32_t kDefaultChanceOfSplittingBlock = 20;
@@ -46,6 +47,7 @@
: random_generator_(random_generator),
next_fresh_id_(min_fresh_id),
chance_of_adding_dead_break_(kDefaultChanceOfAddingDeadBreak),
+ chance_of_adding_dead_continue_(kDefaultChanceOfAddingDeadContinue),
chance_of_moving_block_down_(kDefaultChanceOfMovingBlockDown),
chance_of_obfuscating_constant_(kDefaultChanceOfObfuscatingConstant),
chance_of_splitting_block_(kDefaultChanceOfSplittingBlock),
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 2815bf7..3eaefc7 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -44,6 +44,9 @@
// Probabilities associated with applying various transformations.
// Keep them in alphabetical order.
uint32_t GetChanceOfAddingDeadBreak() { return chance_of_adding_dead_break_; }
+ uint32_t GetChanceOfAddingDeadContinue() {
+ return chance_of_adding_dead_continue_;
+ }
uint32_t GetChanceOfMovingBlockDown() { return chance_of_moving_block_down_; }
uint32_t GetChanceOfObfuscatingConstant() {
return chance_of_obfuscating_constant_;
@@ -66,6 +69,7 @@
// Probabilities associated with applying various transformations.
// Keep them in alphabetical order.
uint32_t chance_of_adding_dead_break_;
+ uint32_t chance_of_adding_dead_continue_;
uint32_t chance_of_moving_block_down_;
uint32_t chance_of_obfuscating_constant_;
uint32_t chance_of_splitting_block_;
diff --git a/source/fuzz/fuzzer_pass_add_dead_breaks.cpp b/source/fuzz/fuzzer_pass_add_dead_breaks.cpp
index 62e2a8b..72cd17b 100644
--- a/source/fuzz/fuzzer_pass_add_dead_breaks.cpp
+++ b/source/fuzz/fuzzer_pass_add_dead_breaks.cpp
@@ -50,11 +50,9 @@
// TODO(afd): right now we completely ignore OpPhi instructions at
// merge blocks. This will lead to interesting opportunities being
// missed.
- std::vector<uint32_t> phi_ids;
auto candidate_transformation = TransformationAddDeadBreak(
block.id(), merge_block_id,
- GetFuzzerContext()->GetRandomGenerator()->RandomBool(),
- std::move(phi_ids));
+ GetFuzzerContext()->GetRandomGenerator()->RandomBool(), {});
if (candidate_transformation.IsApplicable(GetIRContext(),
*GetFactManager())) {
// Only consider a transformation as a candidate if it is applicable.
@@ -84,14 +82,11 @@
// Remove the transformation at the chosen index from the sequence.
auto transformation = std::move(candidate_transformations[index]);
candidate_transformations.erase(candidate_transformations.begin() + index);
- // Probabilistically decide whether to try to apply it vs. ignore it.
- if (GetFuzzerContext()->GetRandomGenerator()->RandomPercentage() >
- GetFuzzerContext()->GetChanceOfAddingDeadBreak()) {
- continue;
- }
- // If the transformation can be applied, apply it and add it to the
- // sequence of transformations that have been applied.
- if (transformation.IsApplicable(GetIRContext(), *GetFactManager())) {
+ // Probabilistically decide whether to try to apply it vs. ignore it, in the
+ // case that it is applicable.
+ if (transformation.IsApplicable(GetIRContext(), *GetFactManager()) &&
+ GetFuzzerContext()->GetRandomGenerator()->RandomPercentage() >
+ GetFuzzerContext()->GetChanceOfAddingDeadBreak()) {
transformation.Apply(GetIRContext(), GetFactManager());
*GetTransformations()->add_transformation() = transformation.ToMessage();
}
diff --git a/source/fuzz/fuzzer_pass_add_dead_continues.cpp b/source/fuzz/fuzzer_pass_add_dead_continues.cpp
new file mode 100644
index 0000000..2156d36
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_dead_continues.cpp
@@ -0,0 +1,60 @@
+// Copyright (c) 2019 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_add_dead_continues.h"
+
+#include "source/fuzz/transformation_add_dead_continue.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassAddDeadContinues::FuzzerPassAddDeadContinues(
+ opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}
+
+FuzzerPassAddDeadContinues::~FuzzerPassAddDeadContinues() = default;
+
+void FuzzerPassAddDeadContinues::Apply() {
+ // Consider every block in every function.
+ for (auto& function : *GetIRContext()->module()) {
+ for (auto& block : function) {
+ // Make a transformation to add a dead continue from this node; if the
+ // node turns out to be inappropriate (e.g. by not being in a loop) the
+ // precondition for the transformation will fail and it will be ignored.
+ //
+ // TODO(afd): right now we completely ignore OpPhi instructions at
+ // merge blocks. This will lead to interesting opportunities being
+ // missed.
+ auto candidate_transformation = TransformationAddDeadContinue(
+ block.id(), GetFuzzerContext()->GetRandomGenerator()->RandomBool(),
+ {});
+ // Probabilistically decide whether to apply the transformation in the
+ // case that it is applicable.
+ if (candidate_transformation.IsApplicable(GetIRContext(),
+ *GetFactManager()) &&
+ GetFuzzerContext()->GetRandomGenerator()->RandomPercentage() >
+ GetFuzzerContext()->GetChanceOfAddingDeadContinue()) {
+ candidate_transformation.Apply(GetIRContext(), GetFactManager());
+ *GetTransformations()->add_transformation() =
+ candidate_transformation.ToMessage();
+ }
+ }
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_add_dead_continues.h b/source/fuzz/fuzzer_pass_add_dead_continues.h
new file mode 100644
index 0000000..6cadc97
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_dead_continues.h
@@ -0,0 +1,39 @@
+// Copyright (c) 2019 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_ADD_DEAD_CONTINUES_H_
+#define SOURCE_FUZZ_FUZZER_PASS_ADD_DEAD_CONTINUES_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass for adding dead continue edges to the module.
+class FuzzerPassAddDeadContinues : public FuzzerPass {
+ public:
+ FuzzerPassAddDeadContinues(
+ opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassAddDeadContinues();
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // #define SOURCE_FUZZ_FUZZER_PASS_ADD_DEAD_CONTINUES_H_
diff --git a/source/fuzz/fuzzer_util.cpp b/source/fuzz/fuzzer_util.cpp
index 645c121..9a05c74 100644
--- a/source/fuzz/fuzzer_util.cpp
+++ b/source/fuzz/fuzzer_util.cpp
@@ -30,6 +30,146 @@
std::max(context->module()->id_bound(), id + 1));
}
+opt::BasicBlock* MaybeFindBlock(opt::IRContext* context,
+ uint32_t maybe_block_id) {
+ auto inst = context->get_def_use_mgr()->GetDef(maybe_block_id);
+ if (inst == nullptr) {
+ // No instruction defining this id was found.
+ return nullptr;
+ }
+ if (inst->opcode() != SpvOpLabel) {
+ // The instruction defining the id is not a label, so it cannot be a block
+ // id.
+ return nullptr;
+ }
+ return context->cfg()->block(maybe_block_id);
+}
+
+bool PhiIdsOkForNewEdge(
+ opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
+ const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids) {
+ if (bb_from->IsSuccessor(bb_to)) {
+ // There is already an edge from |from_block| to |to_block|, so there is
+ // no need to extend OpPhi instructions. Do not allow phi ids to be
+ // present. This might turn out to be too strict; perhaps it would be OK
+ // just to ignore the ids in this case.
+ return phi_ids.empty();
+ }
+ // The edge would add a previously non-existent edge from |from_block| to
+ // |to_block|, so we go through the given phi ids and check that they exactly
+ // match the OpPhi instructions in |to_block|.
+ uint32_t phi_index = 0;
+ // An explicit loop, rather than applying a lambda to each OpPhi in |bb_to|,
+ // makes sense here because we need to increment |phi_index| for each OpPhi
+ // instruction.
+ for (auto& inst : *bb_to) {
+ if (inst.opcode() != SpvOpPhi) {
+ // The OpPhi instructions all occur at the start of the block; if we find
+ // a non-OpPhi then we have seen them all.
+ break;
+ }
+ if (phi_index == static_cast<uint32_t>(phi_ids.size())) {
+ // Not enough phi ids have been provided to account for the OpPhi
+ // instructions.
+ return false;
+ }
+ // Look for an instruction defining the next phi id.
+ opt::Instruction* phi_extension =
+ context->get_def_use_mgr()->GetDef(phi_ids[phi_index]);
+ if (!phi_extension) {
+ // The id given to extend this OpPhi does not exist.
+ return false;
+ }
+ if (phi_extension->type_id() != inst.type_id()) {
+ // The instruction given to extend this OpPhi either does not have a type
+ // or its type does not match that of the OpPhi.
+ return false;
+ }
+
+ if (context->get_instr_block(phi_extension)) {
+ // The instruction defining the phi id has an associated block (i.e., it
+ // is not a global value). Check whether its definition dominates the
+ // exit of |from_block|.
+ auto dominator_analysis =
+ context->GetDominatorAnalysis(bb_from->GetParent());
+ if (!dominator_analysis->Dominates(phi_extension,
+ bb_from->terminator())) {
+ // The given id is no good as its definition does not dominate the exit
+ // of |from_block|
+ return false;
+ }
+ }
+ phi_index++;
+ }
+ // Return false if not all of the ids for extending OpPhi instructions are
+ // needed. This might turn out to be stricter than necessary; perhaps it would
+ // be OK just to not use the ids in this case.
+ return phi_index == static_cast<uint32_t>(phi_ids.size());
+}
+
+void AddUnreachableEdgeAndUpdateOpPhis(
+ opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
+ bool condition_value,
+ 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");
+ 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.
+ opt::analysis::Bool bool_type;
+ opt::analysis::BoolConstant bool_constant(
+ context->get_type_mgr()->GetRegisteredType(&bool_type)->AsBool(),
+ condition_value);
+ uint32_t bool_id = context->get_constant_mgr()->FindDeclaredConstant(
+ &bool_constant, context->get_type_mgr()->GetId(&bool_type));
+
+ const bool from_to_edge_already_exists = bb_from->IsSuccessor(bb_to);
+ auto successor = 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(
+ {{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}}});
+
+ // Update OpPhi instructions in the target block if this branch adds a
+ // previously non-existent edge from source to target.
+ if (!from_to_edge_already_exists) {
+ uint32_t phi_index = 0;
+ for (auto& inst : *bb_to) {
+ if (inst.opcode() != SpvOpPhi) {
+ break;
+ }
+ assert(phi_index < static_cast<uint32_t>(phi_ids.size()) &&
+ "There should be exactly one phi id per OpPhi instruction.");
+ inst.AddOperand({SPV_OPERAND_TYPE_ID, {phi_ids[phi_index]}});
+ inst.AddOperand({SPV_OPERAND_TYPE_ID, {bb_from->id()}});
+ phi_index++;
+ }
+ assert(phi_index == static_cast<uint32_t>(phi_ids.size()) &&
+ "There should be exactly one phi id per OpPhi instruction.");
+ }
+}
+
+bool BlockIsInLoopContinueConstruct(opt::IRContext* context, uint32_t block_id,
+ uint32_t maybe_loop_header_id) {
+ // We deem a block to be part of a loop's continue construct if the loop's
+ // continue target dominates the block.
+ auto containing_construct_block = context->cfg()->block(maybe_loop_header_id);
+ if (containing_construct_block->IsLoopHeader()) {
+ auto continue_target = containing_construct_block->ContinueBlockId();
+ if (context->GetDominatorAnalysis(containing_construct_block->GetParent())
+ ->Dominates(continue_target, block_id)) {
+ return true;
+ }
+ }
+ return false;
+}
+
} // namespace fuzzerutil
} // namespace fuzz
diff --git a/source/fuzz/fuzzer_util.h b/source/fuzz/fuzzer_util.h
index 30d870b..15228de 100644
--- a/source/fuzz/fuzzer_util.h
+++ b/source/fuzz/fuzzer_util.h
@@ -15,6 +15,9 @@
#ifndef SOURCE_FUZZ_FUZZER_UTIL_H_
#define SOURCE_FUZZ_FUZZER_UTIL_H_
+#include <vector>
+
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
#include "source/opt/ir_context.h"
namespace spvtools {
@@ -30,6 +33,35 @@
// account for the given id.
void UpdateModuleIdBound(opt::IRContext* context, uint32_t id);
+// Return the block with id |maybe_block_id| if it exists, and nullptr
+// otherwise.
+opt::BasicBlock* MaybeFindBlock(opt::IRContext* context,
+ uint32_t maybe_block_id);
+
+// When adding an edge from |bb_from| to |bb_to| (which are assumed to be blocks
+// in the same function), it is important to supply |bb_to| with ids that can be
+// used to augment OpPhi instructions in the case that there is not already such
+// an edge. This function returns true if and only if the ids provided in
+// |phi_ids| suffice for this purpose,
+bool PhiIdsOkForNewEdge(
+ opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
+ const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids);
+
+// Requires that PhiIdsOkForNewEdge(context, bb_from, bb_to, phi_ids) holds,
+// and that bb_from ends with "OpBranch %some_block". Turns OpBranch into
+// "OpBranchConditional |condition_value| ...", such that control will branch
+// to %some_block, with |bb_to| being the unreachable alternative. Updates
+// OpPhi instructions in |bb_to| using |phi_ids| so that the new edge is valid.
+void AddUnreachableEdgeAndUpdateOpPhis(
+ opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
+ bool condition_value,
+ const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids);
+
+// Returns true if and only if |maybe_loop_header_id| is a loop header and
+// |block_id| is in the continue construct of the associated loop.
+bool BlockIsInLoopContinueConstruct(opt::IRContext* context, uint32_t block_id,
+ uint32_t maybe_loop_header_id);
+
} // namespace fuzzerutil
} // namespace fuzz
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index aecd4c7..13d8a05 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -137,6 +137,7 @@
TransformationReplaceBooleanConstantWithConstantBinary replace_boolean_constant_with_constant_binary = 9;
TransformationAddTypePointer add_type_pointer = 10;
TransformationReplaceConstantWithUniform replace_constant_with_uniform = 11;
+ TransformationAddDeadContinue add_dead_continue = 12;
// Add additional option using the next available number.
}
}
@@ -190,6 +191,25 @@
}
+message TransformationAddDeadContinue {
+
+ // A transformation that turns a basic block appearing in a loop and that
+ // unconditionally branches to its successor into a block that potentially
+ // branches to the continue target of the loop, but in such a manner that the
+ // continue branch cannot actually be taken.
+
+ // The block to continue from
+ uint32 from_block = 1;
+
+ // Determines whether the continue condition is true or false
+ bool continue_condition_value = 2;
+
+ // A sequence of ids suitable for extending OpPhi instructions as a result of
+ // the new break edge
+ repeated uint32 phi_id = 3;
+
+}
+
message TransformationAddTypeBoolean {
// Adds OpTypeBool to the module
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index 18a66d4..a252734 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -20,6 +20,7 @@
#include "transformation_add_constant_boolean.h"
#include "transformation_add_constant_scalar.h"
#include "transformation_add_dead_break.h"
+#include "transformation_add_dead_continue.h"
#include "transformation_add_type_boolean.h"
#include "transformation_add_type_float.h"
#include "transformation_add_type_int.h"
@@ -45,6 +46,9 @@
message.add_constant_scalar());
case protobufs::Transformation::TransformationCase::kAddDeadBreak:
return MakeUnique<TransformationAddDeadBreak>(message.add_dead_break());
+ case protobufs::Transformation::TransformationCase::kAddDeadContinue:
+ return MakeUnique<TransformationAddDeadContinue>(
+ message.add_dead_continue());
case protobufs::Transformation::TransformationCase::kAddTypeBoolean:
return MakeUnique<TransformationAddTypeBoolean>(
message.add_type_boolean());
diff --git a/source/fuzz/transformation_add_dead_break.cpp b/source/fuzz/transformation_add_dead_break.cpp
index 7b55f47..229dc90 100644
--- a/source/fuzz/transformation_add_dead_break.cpp
+++ b/source/fuzz/transformation_add_dead_break.cpp
@@ -15,6 +15,7 @@
#include "source/fuzz/transformation_add_dead_break.h"
#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/fuzzer_util.h"
#include "source/opt/basic_block.h"
#include "source/opt/ir_context.h"
#include "source/opt/struct_cfg_analysis.h"
@@ -37,98 +38,6 @@
}
}
-opt::BasicBlock* TransformationAddDeadBreak::MaybeFindBlock(
- opt::IRContext* context, uint32_t maybe_block_id) const {
- auto inst = context->get_def_use_mgr()->GetDef(maybe_block_id);
- if (inst == nullptr) {
- // No instruction defining this id was found.
- return nullptr;
- }
- if (inst->opcode() != SpvOpLabel) {
- // The instruction defining the id is not a label, so it cannot be a block
- // id.
- return nullptr;
- }
- return context->cfg()->block(maybe_block_id);
-}
-
-bool TransformationAddDeadBreak::PhiIdsOk(opt::IRContext* context,
- opt::BasicBlock* bb_from,
- opt::BasicBlock* bb_to) const {
- if (bb_from->IsSuccessor(bb_to)) {
- // There is already an edge from |from_block| to |to_block|, so there is
- // no need to extend OpPhi instructions. Do not allow phi ids to be
- // present. This might turn out to be too strict; perhaps it would be OK
- // just to ignore the ids in this case.
- return message_.phi_id().empty();
- }
- // The break would add a previously non-existent edge from |from_block| to
- // |to_block|, so we go through the given phi ids and check that they exactly
- // match the OpPhi instructions in |to_block|.
- uint32_t phi_index = 0;
- // An explicit loop, rather than applying a lambda to each OpPhi in |bb_to|,
- // makes sense here because we need to increment |phi_index| for each OpPhi
- // instruction.
- for (auto& inst : *bb_to) {
- if (inst.opcode() != SpvOpPhi) {
- // The OpPhi instructions all occur at the start of the block; if we find
- // a non-OpPhi then we have seen them all.
- break;
- }
- if (phi_index == static_cast<uint32_t>(message_.phi_id().size())) {
- // Not enough phi ids have been provided to account for the OpPhi
- // instructions.
- return false;
- }
- // Look for an instruction defining the next phi id.
- opt::Instruction* phi_extension =
- context->get_def_use_mgr()->GetDef(message_.phi_id()[phi_index]);
- if (!phi_extension) {
- // The id given to extend this OpPhi does not exist.
- return false;
- }
- if (phi_extension->type_id() != inst.type_id()) {
- // The instruction given to extend this OpPhi either does not have a type
- // or its type does not match that of the OpPhi.
- return false;
- }
-
- if (context->get_instr_block(phi_extension)) {
- // The instruction defining the phi id has an associated block (i.e., it
- // is not a global value). Check whether its definition dominates the
- // exit of |from_block|.
- auto dominator_analysis =
- context->GetDominatorAnalysis(bb_from->GetParent());
- if (!dominator_analysis->Dominates(phi_extension,
- bb_from->terminator())) {
- // The given id is no good as its definition does not dominate the exit
- // of |from_block|
- return false;
- }
- }
- phi_index++;
- }
- // Reject the transformation if not all of the ids for extending OpPhi
- // instructions are needed. This might turn out to be stricter than necessary;
- // perhaps it would be OK just to not use the ids in this case.
- return phi_index == static_cast<uint32_t>(message_.phi_id().size());
-}
-
-bool TransformationAddDeadBreak::FromBlockIsInLoopContinueConstruct(
- opt::IRContext* context, uint32_t maybe_loop_header) const {
- // We deem a block to be part of a loop's continue construct if the loop's
- // continue target dominates the block.
- auto containing_construct_block = context->cfg()->block(maybe_loop_header);
- if (containing_construct_block->IsLoopHeader()) {
- auto continue_target = containing_construct_block->ContinueBlockId();
- if (context->GetDominatorAnalysis(containing_construct_block->GetParent())
- ->Dominates(continue_target, message_.from_block())) {
- return true;
- }
- }
- return false;
-}
-
bool TransformationAddDeadBreak::AddingBreakRespectsStructuredControlFlow(
opt::IRContext* context, opt::BasicBlock* bb_from) const {
// Look at the structured control flow associated with |from_block| and
@@ -180,7 +89,8 @@
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2577): We do not
// currently allow a dead break from a back edge block, but we could and
// ultimately should.
- return !FromBlockIsInLoopContinueConstruct(context, containing_construct);
+ return !fuzzerutil::BlockIsInLoopContinueConstruct(
+ context, message_.from_block(), containing_construct);
}
// Case (3) holds if and only if |to_block| is the merge block for this
@@ -191,7 +101,8 @@
if (containing_loop_header &&
message_.to_block() ==
context->cfg()->block(containing_loop_header)->MergeBlockId()) {
- return !FromBlockIsInLoopContinueConstruct(context, containing_loop_header);
+ return !fuzzerutil::BlockIsInLoopContinueConstruct(
+ context, message_.from_block(), containing_loop_header);
}
return false;
}
@@ -199,7 +110,7 @@
bool TransformationAddDeadBreak::IsApplicable(
opt::IRContext* context, const FactManager& /*unused*/) const {
// First, we check that a constant with the same value as
- // |break_condition_value| is present.
+ // |message_.break_condition_value| is present.
opt::analysis::Bool bool_type;
auto registered_bool_type =
context->get_type_mgr()->GetRegisteredType(&bool_type);
@@ -214,17 +125,20 @@
return false;
}
- // Check that |from_block| and |to_block| really are block ids
- opt::BasicBlock* bb_from = MaybeFindBlock(context, message_.from_block());
+ // Check that |message_.from_block| and |message_.to_block| really are block
+ // ids
+ opt::BasicBlock* bb_from =
+ fuzzerutil::MaybeFindBlock(context, message_.from_block());
if (bb_from == nullptr) {
return false;
}
- opt::BasicBlock* bb_to = MaybeFindBlock(context, message_.to_block());
+ opt::BasicBlock* bb_to =
+ fuzzerutil::MaybeFindBlock(context, message_.to_block());
if (bb_to == nullptr) {
return false;
}
- // Check that |from_block| ends with an unconditional branch.
+ // Check that |message_.from_block| ends with an unconditional branch.
if (bb_from->terminator()->opcode() != SpvOpBranch) {
// The block associated with the id does not end with an unconditional
// branch.
@@ -243,7 +157,8 @@
"The id of the block we found should match the target id for the break.");
// Check whether the data passed to extend OpPhi instructions is appropriate.
- if (!PhiIdsOk(context, bb_from, bb_to)) {
+ if (!fuzzerutil::PhiIdsOkForNewEdge(context, bb_from, bb_to,
+ message_.phi_id())) {
return false;
}
@@ -254,50 +169,10 @@
void TransformationAddDeadBreak::Apply(opt::IRContext* context,
FactManager* /*unused*/) const {
- // Get the id of the boolean constant to be used as the break condition.
- opt::analysis::Bool bool_type;
- opt::analysis::BoolConstant bool_constant(
- context->get_type_mgr()->GetRegisteredType(&bool_type)->AsBool(),
- message_.break_condition_value());
- uint32_t bool_id = context->get_constant_mgr()->FindDeclaredConstant(
- &bool_constant, context->get_type_mgr()->GetId(&bool_type));
-
- auto bb_from = context->cfg()->block(message_.from_block());
- auto bb_to = context->cfg()->block(message_.to_block());
- const bool from_to_edge_already_exists = bb_from->IsSuccessor(bb_to);
- auto successor = bb_from->terminator()->GetSingleWordInOperand(0);
- assert(bb_from->terminator()->opcode() == SpvOpBranch &&
- "Precondition for the transformation requires that the source block "
- "ends with OpBranch");
-
- // Add the dead break, 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(
- {{SPV_OPERAND_TYPE_ID, {bool_id}},
- {SPV_OPERAND_TYPE_ID,
- {message_.break_condition_value() ? successor : message_.to_block()}},
- {SPV_OPERAND_TYPE_ID,
- {message_.break_condition_value() ? message_.to_block() : successor}}});
-
- // Update OpPhi instructions in the target block if this break adds a
- // previously non-existent edge from source to target.
- if (!from_to_edge_already_exists) {
- uint32_t phi_index = 0;
- for (auto& inst : *bb_to) {
- if (inst.opcode() != SpvOpPhi) {
- break;
- }
- assert(phi_index < static_cast<uint32_t>(message_.phi_id().size()) &&
- "There should be exactly one phi id per OpPhi instruction.");
- inst.AddOperand({SPV_OPERAND_TYPE_ID, {message_.phi_id()[phi_index]}});
- inst.AddOperand({SPV_OPERAND_TYPE_ID, {message_.from_block()}});
- phi_index++;
- }
- assert(phi_index == static_cast<uint32_t>(message_.phi_id().size()) &&
- "There should be exactly one phi id per OpPhi instruction.");
- }
+ fuzzerutil::AddUnreachableEdgeAndUpdateOpPhis(
+ context, context->cfg()->block(message_.from_block()),
+ context->cfg()->block(message_.to_block()),
+ message_.break_condition_value(), message_.phi_id());
// Invalidate all analyses
context->InvalidateAnalysesExceptFor(opt::IRContext::Analysis::kAnalysisNone);
diff --git a/source/fuzz/transformation_add_dead_break.h b/source/fuzz/transformation_add_dead_break.h
index 23392ba..aeb4dbb 100644
--- a/source/fuzz/transformation_add_dead_break.h
+++ b/source/fuzz/transformation_add_dead_break.h
@@ -34,25 +34,25 @@
bool break_condition_value,
std::vector<uint32_t> phi_id);
- // - |message.from_block| must be the id of a block a in the given module.
- // - |message.to_block| must be the id of a block b in the given module.
- // - if |message.break_condition_value| holds (does not hold) then
+ // - |message_.from_block| must be the id of a block a in the given module.
+ // - |message_.to_block| must be the id of a block b in the given module.
+ // - if |message_.break_condition_value| holds (does not hold) then
// OpConstantTrue (OpConstantFalse) must be present in the module
- // - |message.phi_ids| must be a list of ids that are all available at
- // |message.from_block|
+ // - |message_.phi_ids| must be a list of ids that are all available at
+ // |message_.from_block|
// - a and b must be in the same function.
// - b must be a merge block.
// - a must end with an unconditional branch to some block c.
// - replacing this branch with a conditional branch to b or c, with
- // the boolean constant associated with |message.break_condition_value| as
- // the condition, and the ids in |message.phi_ids| used to extend
+ // the boolean constant associated with |message_.break_condition_value| as
+ // the condition, and the ids in |message_.phi_ids| used to extend
// any OpPhi instructions at b as a result of the edge from a, must
// maintain validity of the module.
bool IsApplicable(opt::IRContext* context,
const FactManager& fact_manager) const override;
// Replaces the terminator of a with a conditional branch to b or c.
- // The boolean constant associated with |message.break_condition_value| is
+ // The boolean constant associated with |message_.break_condition_value| is
// used as the condition, and the order of b and c is arranged such that
// control is guaranteed to jump to c.
void Apply(opt::IRContext* context, FactManager* fact_manager) const override;
@@ -60,21 +60,6 @@
protobufs::Transformation ToMessage() const override;
private:
- // Return the block with id |maybe_block_id| if it exists, and nullptr
- // otherwise.
- opt::BasicBlock* MaybeFindBlock(opt::IRContext* context,
- uint32_t maybe_block_id) const;
-
- // Returns true if and only if the phi ids associated with |message_| are
- // sufficient to allow an edge from |bb_from| to |bb_to| to be added.
- bool PhiIdsOk(opt::IRContext* context, opt::BasicBlock* bb_from,
- opt::BasicBlock* bb_to) const;
-
- // Returns true if and only if |message_.from_block| is in the continue
- // construct of a loop headed at |maybe_loop_header|.
- bool FromBlockIsInLoopContinueConstruct(opt::IRContext* context,
- uint32_t maybe_loop_header) const;
-
// Returns true if and only if adding an edge from |bb_from| to
// |message_.to_block| respects structured control flow.
bool AddingBreakRespectsStructuredControlFlow(opt::IRContext* context,
diff --git a/source/fuzz/transformation_add_dead_continue.cpp b/source/fuzz/transformation_add_dead_continue.cpp
new file mode 100644
index 0000000..e3b3da2
--- /dev/null
+++ b/source/fuzz/transformation_add_dead_continue.cpp
@@ -0,0 +1,133 @@
+// Copyright (c) 2019 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_add_dead_continue.h"
+
+#include "source/fuzz/fuzzer_util.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationAddDeadContinue::TransformationAddDeadContinue(
+ const spvtools::fuzz::protobufs::TransformationAddDeadContinue& message)
+ : message_(message) {}
+
+TransformationAddDeadContinue::TransformationAddDeadContinue(
+ uint32_t from_block, bool continue_condition_value,
+ std::vector<uint32_t> phi_id) {
+ message_.set_from_block(from_block);
+ message_.set_continue_condition_value(continue_condition_value);
+ for (auto id : phi_id) {
+ message_.add_phi_id(id);
+ }
+}
+
+bool TransformationAddDeadContinue::IsApplicable(
+ opt::IRContext* context, const FactManager& /*unused*/) const {
+ // First, we check that a constant with the same value as
+ // |message_.continue_condition_value| is present.
+ opt::analysis::Bool bool_type;
+ auto registered_bool_type =
+ context->get_type_mgr()->GetRegisteredType(&bool_type);
+ if (!registered_bool_type) {
+ return false;
+ }
+ opt::analysis::BoolConstant bool_constant(
+ registered_bool_type->AsBool(), message_.continue_condition_value());
+ if (!context->get_constant_mgr()->FindConstant(&bool_constant)) {
+ // The required constant is not present, so the transformation cannot be
+ // applied.
+ return false;
+ }
+
+ // Check that |message_.from_block| really is a block id.
+ opt::BasicBlock* bb_from =
+ fuzzerutil::MaybeFindBlock(context, message_.from_block());
+ if (bb_from == nullptr) {
+ return false;
+ }
+
+ // Check that |message_.from_block| ends with an unconditional branch.
+ if (bb_from->terminator()->opcode() != SpvOpBranch) {
+ // The block associated with the id does not end with an unconditional
+ // branch.
+ return false;
+ }
+
+ assert(bb_from != nullptr &&
+ "We should have found a block if this line of code is reached.");
+ assert(
+ bb_from->id() == message_.from_block() &&
+ "The id of the block we found should match the source id for the break.");
+
+ // Get the header for the innermost loop containing |message_.from_block|.
+ // Because the structured CFG analysis does not regard a loop header as part
+ // of the loop it heads, we check first whether bb_from is a loop header
+ // before using the structured CFG analysis.
+ auto loop_header = bb_from->IsLoopHeader()
+ ? message_.from_block()
+ : context->GetStructuredCFGAnalysis()->ContainingLoop(
+ message_.from_block());
+ if (!loop_header) {
+ return false;
+ }
+
+ if (fuzzerutil::BlockIsInLoopContinueConstruct(context, message_.from_block(),
+ loop_header)) {
+ // We cannot jump to the continue target from the continue construct.
+ return false;
+ }
+
+ auto continue_block = context->cfg()->block(loop_header)->ContinueBlockId();
+
+ if (context->GetStructuredCFGAnalysis()->IsMergeBlock(continue_block)) {
+ // A branch straight to the continue target that is also a merge block might
+ // break the property that a construct header must dominate its merge block
+ // (if the merge block is reachable).
+ return false;
+ }
+
+ // The transformation is good if and only if the given phi ids are sufficient
+ // to extend relevant OpPhi instructions in the continue block.
+ return fuzzerutil::PhiIdsOkForNewEdge(context, bb_from,
+ context->cfg()->block(continue_block),
+ message_.phi_id());
+}
+
+void TransformationAddDeadContinue::Apply(opt::IRContext* context,
+ FactManager* /*unused*/) const {
+ auto bb_from = context->cfg()->block(message_.from_block());
+ auto continue_block =
+ bb_from->IsLoopHeader()
+ ? bb_from->ContinueBlockId()
+ : context->GetStructuredCFGAnalysis()->LoopContinueBlock(
+ message_.from_block());
+ assert(continue_block &&
+ "Precondition for this transformation requires that "
+ "message_.from_block must be in a loop.");
+ fuzzerutil::AddUnreachableEdgeAndUpdateOpPhis(
+ context, bb_from, context->cfg()->block(continue_block),
+ message_.continue_condition_value(), message_.phi_id());
+ // Invalidate all analyses
+ context->InvalidateAnalysesExceptFor(opt::IRContext::Analysis::kAnalysisNone);
+}
+
+protobufs::Transformation TransformationAddDeadContinue::ToMessage() const {
+ protobufs::Transformation result;
+ *result.mutable_add_dead_continue() = message_;
+ return result;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_add_dead_continue.h b/source/fuzz/transformation_add_dead_continue.h
new file mode 100644
index 0000000..e49e2a8
--- /dev/null
+++ b/source/fuzz/transformation_add_dead_continue.h
@@ -0,0 +1,68 @@
+// Copyright (c) 2019 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_ADD_DEAD_CONTINUE_H_
+#define SOURCE_FUZZ_TRANSFORMATION_ADD_DEAD_CONTINUE_H_
+
+#include <vector>
+
+#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationAddDeadContinue : public Transformation {
+ public:
+ explicit TransformationAddDeadContinue(
+ const protobufs::TransformationAddDeadContinue& message);
+
+ TransformationAddDeadContinue(uint32_t from_block,
+ bool continue_condition_value,
+ std::vector<uint32_t> phi_id);
+
+ // - |message_.from_block| must be the id of a block a in the given module.
+ // - a must be contained in a loop with continue target b
+ // - b must not be the merge block of a selection construct
+ // - if |message_.continue_condition_value| holds (does not hold) then
+ // OpConstantTrue (OpConstantFalse) must be present in the module
+ // - |message_.phi_ids| must be a list of ids that are all available at
+ // |message_.from_block|
+ // - a must end with an unconditional branch to some block c.
+ // - replacing this branch with a conditional branch to b or c, with
+ // the boolean constant associated with |message_.continue_condition_value|
+ // as the condition, and the ids in |message_.phi_ids| used to extend any
+ // OpPhi instructions at b as a result of the edge from a, must maintain
+ // validity of the module.
+ bool IsApplicable(opt::IRContext* context,
+ const FactManager& fact_manager) const override;
+
+ // Replaces the terminator of a with a conditional branch to b or c.
+ // The boolean constant associated with |message_.continue_condition_value| is
+ // used as the condition, and the order of b and c is arranged such that
+ // control is guaranteed to jump to c.
+ void Apply(opt::IRContext* context, FactManager* fact_manager) const override;
+
+ protobufs::Transformation ToMessage() const override;
+
+ private:
+ protobufs::TransformationAddDeadContinue message_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_ADD_DEAD_CONTINUE_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 9e4066b..c0e2925 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -25,6 +25,7 @@
transformation_add_constant_boolean_test.cpp
transformation_add_constant_scalar_test.cpp
transformation_add_dead_break_test.cpp
+ transformation_add_dead_continue_test.cpp
transformation_add_type_boolean_test.cpp
transformation_add_type_float_test.cpp
transformation_add_type_int_test.cpp
diff --git a/test/fuzz/fuzz_test_util.cpp b/test/fuzz/fuzz_test_util.cpp
index 545512f..e2b9518 100644
--- a/test/fuzz/fuzz_test_util.cpp
+++ b/test/fuzz/fuzz_test_util.cpp
@@ -79,6 +79,10 @@
std::string ToString(spv_target_env env, const opt::IRContext* ir) {
std::vector<uint32_t> binary;
ir->module()->ToBinary(&binary, false);
+ return ToString(env, binary);
+}
+
+std::string ToString(spv_target_env env, const std::vector<uint32_t>& binary) {
SpirvTools t(env);
std::string result;
t.Disassemble(binary, &result, kFuzzDisassembleOption);
diff --git a/test/fuzz/fuzz_test_util.h b/test/fuzz/fuzz_test_util.h
index 76b7fc2..88a0b20 100644
--- a/test/fuzz/fuzz_test_util.h
+++ b/test/fuzz/fuzz_test_util.h
@@ -17,6 +17,8 @@
#include "gtest/gtest.h"
+#include <vector>
+
#include "source/opt/build_module.h"
#include "source/opt/ir_context.h"
#include "spirv-tools/libspirv.h"
@@ -51,6 +53,10 @@
// Useful for debugging.
std::string ToString(spv_target_env env, const opt::IRContext* ir);
+// Returns the disassembly of the given binary as a string.
+// Useful for debugging.
+std::string ToString(spv_target_env env, const std::vector<uint32_t>& binary);
+
// Assembly options for writing fuzzer tests. It simplifies matters if
// numeric ids do not change.
const uint32_t kFuzzAssembleOption =
@@ -64,6 +70,29 @@
[](spv_message_level_t, const char*, const spv_position_t&,
const char*) -> void {};
+const spvtools::MessageConsumer kConsoleMessageConsumer =
+ [](spv_message_level_t level, const char*, const spv_position_t& position,
+ const char* message) -> void {
+ switch (level) {
+ case SPV_MSG_FATAL:
+ case SPV_MSG_INTERNAL_ERROR:
+ case SPV_MSG_ERROR:
+ std::cerr << "error: line " << position.index << ": " << message
+ << std::endl;
+ break;
+ case SPV_MSG_WARNING:
+ std::cout << "warning: line " << position.index << ": " << message
+ << std::endl;
+ break;
+ case SPV_MSG_INFO:
+ std::cout << "info: line " << position.index << ": " << message
+ << std::endl;
+ break;
+ default:
+ break;
+ }
+};
+
} // namespace fuzz
} // namespace spvtools
diff --git a/test/fuzz/fuzzer_replayer_test.cpp b/test/fuzz/fuzzer_replayer_test.cpp
index 2cb595a..166e6ea 100644
--- a/test/fuzz/fuzzer_replayer_test.cpp
+++ b/test/fuzz/fuzzer_replayer_test.cpp
@@ -33,6 +33,7 @@
std::vector<uint32_t> binary_in;
SpirvTools t(env);
+ t.SetMessageConsumer(kConsoleMessageConsumer);
ASSERT_TRUE(t.Assemble(shader, &binary_in, kFuzzAssembleOption));
ASSERT_TRUE(t.Validate(binary_in));
diff --git a/test/fuzz/transformation_add_dead_continue_test.cpp b/test/fuzz/transformation_add_dead_continue_test.cpp
new file mode 100644
index 0000000..573db19
--- /dev/null
+++ b/test/fuzz/transformation_add_dead_continue_test.cpp
@@ -0,0 +1,1034 @@
+// Copyright (c) 2019 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_add_dead_continue.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationAddDeadContinueTest, SimpleExample) {
+ // For a simple loop, checks that some dead continue scenarios are possible,
+ // sanity-checks that some illegal scenarios are indeed not allowed, and then
+ // applies a transformation.
+
+ // The SPIR-V for this test is adapted from the following GLSL, by separating
+ // some assignments into their own basic blocks, and adding constants for true
+ // and false:
+ //
+ // void main() {
+ // int x = 0;
+ // for (int i = 0; i < 10; i++) {
+ // x = x + i;
+ // x = x + i;
+ // }
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %10 "i"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 0
+ %17 = OpConstant %6 10
+ %18 = OpTypeBool
+ %41 = OpConstantTrue %18
+ %42 = OpConstantFalse %18
+ %27 = OpConstant %6 1
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %10 %9
+ OpBranch %11
+ %11 = OpLabel
+ OpLoopMerge %13 %14 None
+ OpBranch %15
+ %15 = OpLabel
+ %16 = OpLoad %6 %10
+ %19 = OpSLessThan %18 %16 %17
+ OpBranchConditional %19 %12 %13
+ %12 = OpLabel
+ %20 = OpLoad %6 %8
+ %21 = OpLoad %6 %10
+ %22 = OpIAdd %6 %20 %21
+ OpStore %8 %22
+ OpBranch %40
+ %40 = OpLabel
+ %23 = OpLoad %6 %8
+ %24 = OpLoad %6 %10
+ %25 = OpIAdd %6 %23 %24
+ OpStore %8 %25
+ OpBranch %14
+ %14 = OpLabel
+ %26 = OpLoad %6 %10
+ %28 = OpIAdd %6 %26 %27
+ OpStore %10 %28
+ OpBranch %11
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ FactManager fact_manager;
+
+ // These are all possibilities.
+ ASSERT_TRUE(TransformationAddDeadContinue(11, true, {})
+ .IsApplicable(context.get(), fact_manager));
+ ASSERT_TRUE(TransformationAddDeadContinue(11, false, {})
+ .IsApplicable(context.get(), fact_manager));
+ ASSERT_TRUE(TransformationAddDeadContinue(12, true, {})
+ .IsApplicable(context.get(), fact_manager));
+ ASSERT_TRUE(TransformationAddDeadContinue(12, false, {})
+ .IsApplicable(context.get(), fact_manager));
+ ASSERT_TRUE(TransformationAddDeadContinue(40, true, {})
+ .IsApplicable(context.get(), fact_manager));
+ ASSERT_TRUE(TransformationAddDeadContinue(40, false, {})
+ .IsApplicable(context.get(), fact_manager));
+
+ // Inapplicable: 100 is not a block id.
+ ASSERT_FALSE(TransformationAddDeadContinue(100, true, {})
+ .IsApplicable(context.get(), fact_manager));
+
+ // Inapplicable: 10 is not in a loop.
+ ASSERT_FALSE(TransformationAddDeadContinue(10, true, {})
+ .IsApplicable(context.get(), fact_manager));
+
+ // Inapplicable: 15 does not branch unconditionally to a single successor.
+ ASSERT_FALSE(TransformationAddDeadContinue(15, true, {})
+ .IsApplicable(context.get(), fact_manager));
+
+ // Inapplicable: 13 is not in a loop and has no successor.
+ ASSERT_FALSE(TransformationAddDeadContinue(13, true, {})
+ .IsApplicable(context.get(), fact_manager));
+
+ // Inapplicable: 14 is the loop continue target, so it's not OK to jump to
+ // the loop continue from there.
+ ASSERT_FALSE(TransformationAddDeadContinue(14, false, {})
+ .IsApplicable(context.get(), fact_manager));
+
+ // These are the transformations we will apply.
+ auto transformation1 = TransformationAddDeadContinue(11, true, {});
+ auto transformation2 = TransformationAddDeadContinue(12, false, {});
+ auto transformation3 = TransformationAddDeadContinue(40, true, {});
+
+ ASSERT_TRUE(transformation1.IsApplicable(context.get(), fact_manager));
+ transformation1.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ ASSERT_TRUE(transformation2.IsApplicable(context.get(), fact_manager));
+ transformation2.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ ASSERT_TRUE(transformation3.IsApplicable(context.get(), fact_manager));
+ transformation3.Apply(context.get(), &fact_manager);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %10 "i"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 0
+ %17 = OpConstant %6 10
+ %18 = OpTypeBool
+ %41 = OpConstantTrue %18
+ %42 = OpConstantFalse %18
+ %27 = OpConstant %6 1
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %10 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %10 %9
+ OpBranch %11
+ %11 = OpLabel
+ OpLoopMerge %13 %14 None
+ OpBranchConditional %41 %15 %14
+ %15 = OpLabel
+ %16 = OpLoad %6 %10
+ %19 = OpSLessThan %18 %16 %17
+ OpBranchConditional %19 %12 %13
+ %12 = OpLabel
+ %20 = OpLoad %6 %8
+ %21 = OpLoad %6 %10
+ %22 = OpIAdd %6 %20 %21
+ OpStore %8 %22
+ OpBranchConditional %42 %14 %40
+ %40 = OpLabel
+ %23 = OpLoad %6 %8
+ %24 = OpLoad %6 %10
+ %25 = OpIAdd %6 %23 %24
+ OpStore %8 %25
+ OpBranchConditional %41 %14 %14
+ %14 = OpLabel
+ %26 = OpLoad %6 %10
+ %28 = OpIAdd %6 %26 %27
+ OpStore %10 %28
+ OpBranch %11
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationAddDeadContinueTest,
+ DoNotAllowContinueToMergeBlockOfAnotherLoop) {
+ // A loop header must dominate its merge block if that merge block is
+ // reachable. We are thus not allowed to add a dead continue that would result
+ // in violation of this property. This test checks for such a scenario.
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %16 %139
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeBool
+ %14 = OpTypeVector %6 4
+ %15 = OpTypePointer Input %14
+ %16 = OpVariable %15 Input
+ %138 = OpTypePointer Output %14
+ %139 = OpVariable %138 Output
+ %400 = OpConstantTrue %8
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %500
+ %500 = OpLabel
+ OpLoopMerge %501 %502 None
+ OpBranch %503 ; We are not allowed to change this to OpBranchConditional %400 %503 %502
+ %503 = OpLabel
+ OpLoopMerge %502 %504 None
+ OpBranchConditional %400 %505 %504
+ %505 = OpLabel
+ OpBranch %502
+ %504 = OpLabel
+ OpBranch %503
+ %502 = OpLabel
+ OpBranchConditional %400 %501 %500
+ %501 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ FactManager fact_manager;
+
+ ASSERT_FALSE(TransformationAddDeadContinue(500, true, {})
+ .IsApplicable(context.get(), fact_manager));
+ ASSERT_FALSE(TransformationAddDeadContinue(500, false, {})
+ .IsApplicable(context.get(), fact_manager));
+}
+
+TEST(TransformationAddDeadContinueTest, DoNotAllowContinueToSelectionMerge) {
+ // A selection header must dominate its merge block if that merge block is
+ // reachable. We are thus not allowed to add a dead continue that would result
+ // in violation of this property. This test checks for such a scenario.
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %16 %139
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypePointer Function %6
+ %8 = OpTypeBool
+ %14 = OpTypeVector %6 4
+ %15 = OpTypePointer Input %14
+ %16 = OpVariable %15 Input
+ %138 = OpTypePointer Output %14
+ %139 = OpVariable %138 Output
+ %400 = OpConstantTrue %8
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %500
+ %500 = OpLabel
+ OpLoopMerge %501 %502 None
+ OpBranch %503 ; We are not allowed to change this to OpBranchConditional %400 %503 %502
+ %503 = OpLabel
+ OpSelectionMerge %502 None
+ OpBranchConditional %400 %505 %504
+ %505 = OpLabel
+ OpBranch %502
+ %504 = OpLabel
+ OpBranch %502
+ %502 = OpLabel
+ OpBranchConditional %400 %501 %500
+ %501 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ FactManager fact_manager;
+
+ ASSERT_FALSE(TransformationAddDeadContinue(500, true, {})
+ .IsApplicable(context.get(), fact_manager));
+ ASSERT_FALSE(TransformationAddDeadContinue(500, false, {})
+ .IsApplicable(context.get(), fact_manager));
+}
+
+TEST(TransformationAddDeadContinueTest, LoopNest) {
+ // Checks some allowed and disallowed scenarios for a nest of loops, including
+ // continuing a loop from an if or switch.
+
+ // The SPIR-V for this test is adapted from the following GLSL:
+ //
+ // void main() {
+ // int x, y;
+ // do {
+ // x++;
+ // for (int j = 0; j < 100; j++) {
+ // y++;
+ // if (x == y) {
+ // x++;
+ // if (x == 2) {
+ // y++;
+ // }
+ // switch (x) {
+ // case 0:
+ // x = 2;
+ // default:
+ // break;
+ // }
+ // }
+ // }
+ // } while (x > y);
+ //
+ // for (int i = 0; i < 100; i++) {
+ // x++;
+ // }
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %12 "x"
+ OpName %16 "j"
+ OpName %27 "y"
+ OpName %55 "i"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %10 = OpTypeInt 32 1
+ %11 = OpTypePointer Function %10
+ %14 = OpConstant %10 1
+ %17 = OpConstant %10 0
+ %24 = OpConstant %10 100
+ %25 = OpTypeBool
+ %38 = OpConstant %10 2
+ %67 = OpConstantTrue %25
+ %68 = OpConstantFalse %25
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %12 = OpVariable %11 Function
+ %16 = OpVariable %11 Function
+ %27 = OpVariable %11 Function
+ %55 = OpVariable %11 Function
+ OpBranch %6
+ %6 = OpLabel
+ OpLoopMerge %8 %9 None
+ OpBranch %7
+ %7 = OpLabel
+ %13 = OpLoad %10 %12
+ %15 = OpIAdd %10 %13 %14
+ OpStore %12 %15
+ OpStore %16 %17
+ OpBranch %18
+ %18 = OpLabel
+ OpLoopMerge %20 %21 None
+ OpBranch %22
+ %22 = OpLabel
+ %23 = OpLoad %10 %16
+ %26 = OpSLessThan %25 %23 %24
+ OpBranchConditional %26 %19 %20
+ %19 = OpLabel
+ %28 = OpLoad %10 %27
+ %29 = OpIAdd %10 %28 %14
+ OpStore %27 %29
+ %30 = OpLoad %10 %12
+ %31 = OpLoad %10 %27
+ %32 = OpIEqual %25 %30 %31
+ OpSelectionMerge %34 None
+ OpBranchConditional %32 %33 %34
+ %33 = OpLabel
+ %35 = OpLoad %10 %12
+ %36 = OpIAdd %10 %35 %14
+ OpStore %12 %36
+ %37 = OpLoad %10 %12
+ %39 = OpIEqual %25 %37 %38
+ OpSelectionMerge %41 None
+ OpBranchConditional %39 %40 %41
+ %40 = OpLabel
+ %42 = OpLoad %10 %27
+ %43 = OpIAdd %10 %42 %14
+ OpStore %27 %43
+ OpBranch %41
+ %41 = OpLabel
+ %44 = OpLoad %10 %12
+ OpSelectionMerge %47 None
+ OpSwitch %44 %46 0 %45
+ %46 = OpLabel
+ OpBranch %47
+ %45 = OpLabel
+ OpStore %12 %38
+ OpBranch %46
+ %47 = OpLabel
+ OpBranch %34
+ %34 = OpLabel
+ OpBranch %21
+ %21 = OpLabel
+ %50 = OpLoad %10 %16
+ %51 = OpIAdd %10 %50 %14
+ OpStore %16 %51
+ OpBranch %18
+ %20 = OpLabel
+ OpBranch %9
+ %9 = OpLabel
+ %52 = OpLoad %10 %12
+ %53 = OpLoad %10 %27
+ %54 = OpSGreaterThan %25 %52 %53
+ OpBranchConditional %54 %6 %8
+ %8 = OpLabel
+ OpStore %55 %17
+ OpBranch %56
+ %56 = OpLabel
+ OpLoopMerge %58 %59 None
+ OpBranch %60
+ %60 = OpLabel
+ %61 = OpLoad %10 %55
+ %62 = OpSLessThan %25 %61 %24
+ OpBranchConditional %62 %57 %58
+ %57 = OpLabel
+ %63 = OpLoad %10 %12
+ %64 = OpIAdd %10 %63 %14
+ OpStore %12 %64
+ OpBranch %59
+ %59 = OpLabel
+ %65 = OpLoad %10 %55
+ %66 = OpIAdd %10 %65 %14
+ OpStore %55 %66
+ OpBranch %56
+ %58 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ std::vector<uint32_t> good = {6, 7, 18, 20, 34, 40, 45, 46, 47, 56, 57};
+ std::vector<uint32_t> bad = {5, 8, 9, 19, 21, 22, 33, 41, 58, 59, 60};
+
+ for (uint32_t from_block : bad) {
+ ASSERT_FALSE(TransformationAddDeadContinue(from_block, true, {})
+ .IsApplicable(context.get(), fact_manager));
+ }
+ for (uint32_t from_block : good) {
+ const TransformationAddDeadContinue transformation(from_block, true, {});
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_FALSE(transformation.IsApplicable(context.get(), fact_manager));
+ }
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %12 "x"
+ OpName %16 "j"
+ OpName %27 "y"
+ OpName %55 "i"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %10 = OpTypeInt 32 1
+ %11 = OpTypePointer Function %10
+ %14 = OpConstant %10 1
+ %17 = OpConstant %10 0
+ %24 = OpConstant %10 100
+ %25 = OpTypeBool
+ %38 = OpConstant %10 2
+ %67 = OpConstantTrue %25
+ %68 = OpConstantFalse %25
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %12 = OpVariable %11 Function
+ %16 = OpVariable %11 Function
+ %27 = OpVariable %11 Function
+ %55 = OpVariable %11 Function
+ OpBranch %6
+ %6 = OpLabel
+ OpLoopMerge %8 %9 None
+ OpBranchConditional %67 %7 %9
+ %7 = OpLabel
+ %13 = OpLoad %10 %12
+ %15 = OpIAdd %10 %13 %14
+ OpStore %12 %15
+ OpStore %16 %17
+ OpBranchConditional %67 %18 %9
+ %18 = OpLabel
+ OpLoopMerge %20 %21 None
+ OpBranchConditional %67 %22 %21
+ %22 = OpLabel
+ %23 = OpLoad %10 %16
+ %26 = OpSLessThan %25 %23 %24
+ OpBranchConditional %26 %19 %20
+ %19 = OpLabel
+ %28 = OpLoad %10 %27
+ %29 = OpIAdd %10 %28 %14
+ OpStore %27 %29
+ %30 = OpLoad %10 %12
+ %31 = OpLoad %10 %27
+ %32 = OpIEqual %25 %30 %31
+ OpSelectionMerge %34 None
+ OpBranchConditional %32 %33 %34
+ %33 = OpLabel
+ %35 = OpLoad %10 %12
+ %36 = OpIAdd %10 %35 %14
+ OpStore %12 %36
+ %37 = OpLoad %10 %12
+ %39 = OpIEqual %25 %37 %38
+ OpSelectionMerge %41 None
+ OpBranchConditional %39 %40 %41
+ %40 = OpLabel
+ %42 = OpLoad %10 %27
+ %43 = OpIAdd %10 %42 %14
+ OpStore %27 %43
+ OpBranchConditional %67 %41 %21
+ %41 = OpLabel
+ %44 = OpLoad %10 %12
+ OpSelectionMerge %47 None
+ OpSwitch %44 %46 0 %45
+ %46 = OpLabel
+ OpBranchConditional %67 %47 %21
+ %45 = OpLabel
+ OpStore %12 %38
+ OpBranchConditional %67 %46 %21
+ %47 = OpLabel
+ OpBranchConditional %67 %34 %21
+ %34 = OpLabel
+ OpBranchConditional %67 %21 %21
+ %21 = OpLabel
+ %50 = OpLoad %10 %16
+ %51 = OpIAdd %10 %50 %14
+ OpStore %16 %51
+ OpBranch %18
+ %20 = OpLabel
+ OpBranchConditional %67 %9 %9
+ %9 = OpLabel
+ %52 = OpLoad %10 %12
+ %53 = OpLoad %10 %27
+ %54 = OpSGreaterThan %25 %52 %53
+ OpBranchConditional %54 %6 %8
+ %8 = OpLabel
+ OpStore %55 %17
+ OpBranch %56
+ %56 = OpLabel
+ OpLoopMerge %58 %59 None
+ OpBranchConditional %67 %60 %59
+ %60 = OpLabel
+ %61 = OpLoad %10 %55
+ %62 = OpSLessThan %25 %61 %24
+ OpBranchConditional %62 %57 %58
+ %57 = OpLabel
+ %63 = OpLoad %10 %12
+ %64 = OpIAdd %10 %63 %14
+ OpStore %12 %64
+ OpBranchConditional %67 %59 %59
+ %59 = OpLabel
+ %65 = OpLoad %10 %55
+ %66 = OpIAdd %10 %65 %14
+ OpStore %55 %66
+ OpBranch %56
+ %58 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationAddDeadConditionalTest, LoopInContinueConstruct) {
+ // Considers some scenarios where there is a loop in a loop's continue
+ // construct.
+
+ // The SPIR-V for this test is adapted from the following GLSL, with inlining
+ // applied so that the loop from foo is in the main loop's continue construct:
+ //
+ // int foo() {
+ // int result = 0;
+ // for (int j = 0; j < 10; j++) {
+ // result++;
+ // }
+ // return result;
+ // }
+ //
+ // void main() {
+ // for (int i = 0; i < 100; i += foo()) {
+ // }
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %31 "i"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypeFunction %6
+ %10 = OpTypePointer Function %6
+ %12 = OpConstant %6 0
+ %20 = OpConstant %6 10
+ %21 = OpTypeBool
+ %100 = OpConstantFalse %21
+ %24 = OpConstant %6 1
+ %38 = OpConstant %6 100
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %43 = OpVariable %10 Function
+ %44 = OpVariable %10 Function
+ %45 = OpVariable %10 Function
+ %31 = OpVariable %10 Function
+ OpStore %31 %12
+ OpBranch %32
+ %32 = OpLabel
+ OpLoopMerge %34 %35 None
+ OpBranch %36
+ %36 = OpLabel
+ %37 = OpLoad %6 %31
+ %39 = OpSLessThan %21 %37 %38
+ OpBranchConditional %39 %33 %34
+ %33 = OpLabel
+ OpBranch %35
+ %35 = OpLabel
+ OpStore %43 %12
+ OpStore %44 %12
+ OpBranch %46
+ %46 = OpLabel
+ OpLoopMerge %47 %48 None
+ OpBranch %49
+ %49 = OpLabel
+ %50 = OpLoad %6 %44
+ %51 = OpSLessThan %21 %50 %20
+ OpBranchConditional %51 %52 %47
+ %52 = OpLabel
+ %53 = OpLoad %6 %43
+ OpBranch %101
+ %101 = OpLabel
+ %54 = OpIAdd %6 %53 %24
+ OpStore %43 %54
+ OpBranch %48
+ %48 = OpLabel
+ %55 = OpLoad %6 %44
+ %56 = OpIAdd %6 %55 %24
+ OpStore %44 %56
+ OpBranch %46
+ %47 = OpLabel
+ %57 = OpLoad %6 %43
+ OpStore %45 %57
+ %40 = OpLoad %6 %45
+ %41 = OpLoad %6 %31
+ %42 = OpIAdd %6 %41 %40
+ OpStore %31 %42
+ OpBranch %32
+ %34 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ std::vector<uint32_t> good = {32, 33, 46, 52, 101};
+ std::vector<uint32_t> bad = {5, 34, 36, 35, 47, 49, 48};
+
+ for (uint32_t from_block : bad) {
+ ASSERT_FALSE(TransformationAddDeadContinue(from_block, false, {})
+ .IsApplicable(context.get(), fact_manager));
+ }
+ for (uint32_t from_block : good) {
+ const TransformationAddDeadContinue transformation(from_block, false, {});
+ ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+ transformation.Apply(context.get(), &fact_manager);
+ ASSERT_FALSE(transformation.IsApplicable(context.get(), fact_manager));
+ }
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %31 "i"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypeFunction %6
+ %10 = OpTypePointer Function %6
+ %12 = OpConstant %6 0
+ %20 = OpConstant %6 10
+ %21 = OpTypeBool
+ %100 = OpConstantFalse %21
+ %24 = OpConstant %6 1
+ %38 = OpConstant %6 100
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %43 = OpVariable %10 Function
+ %44 = OpVariable %10 Function
+ %45 = OpVariable %10 Function
+ %31 = OpVariable %10 Function
+ OpStore %31 %12
+ OpBranch %32
+ %32 = OpLabel
+ OpLoopMerge %34 %35 None
+ OpBranchConditional %100 %35 %36
+ %36 = OpLabel
+ %37 = OpLoad %6 %31
+ %39 = OpSLessThan %21 %37 %38
+ OpBranchConditional %39 %33 %34
+ %33 = OpLabel
+ OpBranchConditional %100 %35 %35
+ %35 = OpLabel
+ OpStore %43 %12
+ OpStore %44 %12
+ OpBranch %46
+ %46 = OpLabel
+ OpLoopMerge %47 %48 None
+ OpBranchConditional %100 %48 %49
+ %49 = OpLabel
+ %50 = OpLoad %6 %44
+ %51 = OpSLessThan %21 %50 %20
+ OpBranchConditional %51 %52 %47
+ %52 = OpLabel
+ %53 = OpLoad %6 %43
+ OpBranchConditional %100 %48 %101
+ %101 = OpLabel
+ %54 = OpIAdd %6 %53 %24
+ OpStore %43 %54
+ OpBranchConditional %100 %48 %48
+ %48 = OpLabel
+ %55 = OpLoad %6 %44
+ %56 = OpIAdd %6 %55 %24
+ OpStore %44 %56
+ OpBranch %46
+ %47 = OpLabel
+ %57 = OpLoad %6 %43
+ OpStore %45 %57
+ %40 = OpLoad %6 %45
+ %41 = OpLoad %6 %31
+ %42 = OpIAdd %6 %41 %40
+ OpStore %31 %42
+ OpBranch %32
+ %34 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationAddDeadContinueTest, PhiInstructions) {
+ // Checks that the transformation works in the presence of phi instructions.
+
+ // The SPIR-V for this test is adapted from the following GLSL, with a bit of
+ // extra and artificial work to get some interesting uses of OpPhi:
+ //
+ // void main() {
+ // int x; int y;
+ // float f;
+ // x = 2;
+ // f = 3.0;
+ // if (x > y) {
+ // x = 3;
+ // f = 4.0;
+ // } else {
+ // x = x + 2;
+ // f = f + 10.0;
+ // }
+ // while (x < y) {
+ // x = x + 1;
+ // f = f + 1.0;
+ // }
+ // y = x;
+ // f = f + 3.0;
+ // }
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %12 "f"
+ OpName %15 "y"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %10 = OpTypeFloat 32
+ %11 = OpTypePointer Function %10
+ %13 = OpConstant %10 3
+ %17 = OpTypeBool
+ %80 = OpConstantTrue %17
+ %21 = OpConstant %6 3
+ %22 = OpConstant %10 4
+ %27 = OpConstant %10 10
+ %38 = OpConstant %6 1
+ %41 = OpConstant %10 1
+ %46 = OpUndef %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %12 = OpVariable %11 Function
+ %15 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %12 %13
+ %18 = OpSGreaterThan %17 %9 %46
+ OpSelectionMerge %20 None
+ OpBranchConditional %18 %19 %23
+ %19 = OpLabel
+ OpStore %8 %21
+ OpStore %12 %22
+ OpBranch %20
+ %23 = OpLabel
+ %25 = OpIAdd %6 %9 %9
+ OpStore %8 %25
+ OpBranch %70
+ %70 = OpLabel
+ %28 = OpFAdd %10 %13 %27
+ OpStore %12 %28
+ OpBranch %20
+ %20 = OpLabel
+ %52 = OpPhi %10 %22 %19 %28 %70
+ %48 = OpPhi %6 %21 %19 %25 %70
+ OpBranch %29
+ %29 = OpLabel
+ %51 = OpPhi %10 %52 %20 %100 %32
+ %47 = OpPhi %6 %48 %20 %101 %32
+ OpLoopMerge %31 %32 None
+ OpBranch %33
+ %33 = OpLabel
+ %36 = OpSLessThan %17 %47 %46
+ OpBranchConditional %36 %30 %31
+ %30 = OpLabel
+ %39 = OpIAdd %6 %47 %38
+ OpStore %8 %39
+ OpBranch %75
+ %75 = OpLabel
+ %42 = OpFAdd %10 %51 %41
+ OpStore %12 %42
+ OpBranch %32
+ %32 = OpLabel
+ %100 = OpPhi %10 %42 %75
+ %101 = OpPhi %6 %39 %75
+ OpBranch %29
+ %31 = OpLabel
+ %71 = OpPhi %6 %47 %33
+ %72 = OpPhi %10 %51 %33
+ OpStore %15 %71
+ %45 = OpFAdd %10 %72 %13
+ OpStore %12 %45
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+
+ std::vector<uint32_t> bad = {5, 19, 20, 23, 31, 32, 33, 70};
+
+ std::vector<uint32_t> good = {29, 30, 75};
+
+ for (uint32_t from_block : bad) {
+ ASSERT_FALSE(TransformationAddDeadContinue(from_block, true, {})
+ .IsApplicable(context.get(), fact_manager));
+ }
+ auto transformation1 = TransformationAddDeadContinue(29, true, {13, 21});
+ ASSERT_TRUE(transformation1.IsApplicable(context.get(), fact_manager));
+ transformation1.Apply(context.get(), &fact_manager);
+
+ auto transformation2 = TransformationAddDeadContinue(30, true, {22, 46});
+ ASSERT_TRUE(transformation2.IsApplicable(context.get(), fact_manager));
+ transformation2.Apply(context.get(), &fact_manager);
+
+ // 75 already has the continue block as a successor, so we should not provide
+ // phi ids.
+ auto transformationBad = TransformationAddDeadContinue(75, true, {27, 46});
+ ASSERT_FALSE(transformationBad.IsApplicable(context.get(), fact_manager));
+
+ auto transformation3 = TransformationAddDeadContinue(75, true, {});
+ ASSERT_TRUE(transformation3.IsApplicable(context.get(), fact_manager));
+ transformation3.Apply(context.get(), &fact_manager);
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %8 "x"
+ OpName %12 "f"
+ OpName %15 "y"
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpTypePointer Function %6
+ %9 = OpConstant %6 2
+ %10 = OpTypeFloat 32
+ %11 = OpTypePointer Function %10
+ %13 = OpConstant %10 3
+ %17 = OpTypeBool
+ %80 = OpConstantTrue %17
+ %21 = OpConstant %6 3
+ %22 = OpConstant %10 4
+ %27 = OpConstant %10 10
+ %38 = OpConstant %6 1
+ %41 = OpConstant %10 1
+ %46 = OpUndef %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %8 = OpVariable %7 Function
+ %12 = OpVariable %11 Function
+ %15 = OpVariable %7 Function
+ OpStore %8 %9
+ OpStore %12 %13
+ %18 = OpSGreaterThan %17 %9 %46
+ OpSelectionMerge %20 None
+ OpBranchConditional %18 %19 %23
+ %19 = OpLabel
+ OpStore %8 %21
+ OpStore %12 %22
+ OpBranch %20
+ %23 = OpLabel
+ %25 = OpIAdd %6 %9 %9
+ OpStore %8 %25
+ OpBranch %70
+ %70 = OpLabel
+ %28 = OpFAdd %10 %13 %27
+ OpStore %12 %28
+ OpBranch %20
+ %20 = OpLabel
+ %52 = OpPhi %10 %22 %19 %28 %70
+ %48 = OpPhi %6 %21 %19 %25 %70
+ OpBranch %29
+ %29 = OpLabel
+ %51 = OpPhi %10 %52 %20 %100 %32
+ %47 = OpPhi %6 %48 %20 %101 %32
+ OpLoopMerge %31 %32 None
+ OpBranchConditional %80 %33 %32
+ %33 = OpLabel
+ %36 = OpSLessThan %17 %47 %46
+ OpBranchConditional %36 %30 %31
+ %30 = OpLabel
+ %39 = OpIAdd %6 %47 %38
+ OpStore %8 %39
+ OpBranchConditional %80 %75 %32
+ %75 = OpLabel
+ %42 = OpFAdd %10 %51 %41
+ OpStore %12 %42
+ OpBranchConditional %80 %32 %32
+ %32 = OpLabel
+ %100 = OpPhi %10 %42 %75 %13 %29 %22 %30
+ %101 = OpPhi %6 %39 %75 %21 %29 %46 %30
+ OpBranch %29
+ %31 = OpLabel
+ %71 = OpPhi %6 %47 %33
+ %72 = OpPhi %10 %51 %33
+ OpStore %15 %71
+ %45 = OpFAdd %10 %72 %13
+ OpStore %12 %45
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
