spirv-fuzz: TransformationPropagateInstructionDown (#3692)
Fixes #3691.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 5d4f428..2a9a95d 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -100,6 +100,7 @@
fuzzer_pass_permute_function_parameters.h
fuzzer_pass_permute_instructions.h
fuzzer_pass_permute_phi_operands.h
+ fuzzer_pass_propagate_instructions_down.h
fuzzer_pass_propagate_instructions_up.h
fuzzer_pass_push_ids_through_variables.h
fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h
@@ -190,6 +191,7 @@
transformation_outline_function.h
transformation_permute_function_parameters.h
transformation_permute_phi_operands.h
+ transformation_propagate_instruction_down.h
transformation_propagate_instruction_up.h
transformation_push_id_through_variable.h
transformation_record_synonymous_constants.h
@@ -282,6 +284,7 @@
fuzzer_pass_permute_function_parameters.cpp
fuzzer_pass_permute_instructions.cpp
fuzzer_pass_permute_phi_operands.cpp
+ fuzzer_pass_propagate_instructions_down.cpp
fuzzer_pass_propagate_instructions_up.cpp
fuzzer_pass_push_ids_through_variables.cpp
fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.cpp
@@ -370,6 +373,7 @@
transformation_outline_function.cpp
transformation_permute_function_parameters.cpp
transformation_permute_phi_operands.cpp
+ transformation_propagate_instruction_down.cpp
transformation_propagate_instruction_up.cpp
transformation_push_id_through_variable.cpp
transformation_record_synonymous_constants.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 6fa542c..7d9c9c4 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -68,6 +68,7 @@
#include "source/fuzz/fuzzer_pass_permute_function_parameters.h"
#include "source/fuzz/fuzzer_pass_permute_instructions.h"
#include "source/fuzz/fuzzer_pass_permute_phi_operands.h"
+#include "source/fuzz/fuzzer_pass_propagate_instructions_down.h"
#include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
#include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
#include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
@@ -276,6 +277,7 @@
MaybeAddRepeatedPass<FuzzerPassPermuteBlocks>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassPermuteFunctionParameters>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassPermuteInstructions>(&pass_instances);
+ MaybeAddRepeatedPass<FuzzerPassPropagateInstructionsDown>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassPropagateInstructionsUp>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassPushIdsThroughVariables>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassReplaceAddsSubsMulsWithCarryingExtended>(
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 34f25cd..1250cba 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -107,6 +107,8 @@
const std::pair<uint32_t, uint32_t> kChanceOfPermutingInstructions = {20, 70};
const std::pair<uint32_t, uint32_t> kChanceOfPermutingParameters = {30, 90};
const std::pair<uint32_t, uint32_t> kChanceOfPermutingPhiOperands = {30, 90};
+const std::pair<uint32_t, uint32_t> kChanceOfPropagatingInstructionsDown = {20,
+ 70};
const std::pair<uint32_t, uint32_t> kChanceOfPropagatingInstructionsUp = {20,
70};
const std::pair<uint32_t, uint32_t> kChanceOfPushingIdThroughVariable = {5, 50};
@@ -294,6 +296,8 @@
ChooseBetweenMinAndMax(kChanceOfPermutingParameters);
chance_of_permuting_phi_operands_ =
ChooseBetweenMinAndMax(kChanceOfPermutingPhiOperands);
+ chance_of_propagating_instructions_down_ =
+ ChooseBetweenMinAndMax(kChanceOfPropagatingInstructionsDown);
chance_of_propagating_instructions_up_ =
ChooseBetweenMinAndMax(kChanceOfPropagatingInstructionsUp);
chance_of_pushing_id_through_variable_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 4436b2b..01a92f7 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -264,6 +264,9 @@
uint32_t GetChanceOfPermutingPhiOperands() {
return chance_of_permuting_phi_operands_;
}
+ uint32_t GetChanceOfPropagatingInstructionsDown() {
+ return chance_of_propagating_instructions_down_;
+ }
uint32_t GetChanceOfPropagatingInstructionsUp() {
return chance_of_propagating_instructions_up_;
}
@@ -463,6 +466,7 @@
uint32_t chance_of_permuting_instructions_;
uint32_t chance_of_permuting_parameters_;
uint32_t chance_of_permuting_phi_operands_;
+ uint32_t chance_of_propagating_instructions_down_;
uint32_t chance_of_propagating_instructions_up_;
uint32_t chance_of_pushing_id_through_variable_;
uint32_t chance_of_replacing_add_sub_mul_with_carrying_extended_;
diff --git a/source/fuzz/fuzzer_pass_propagate_instructions_down.cpp b/source/fuzz/fuzzer_pass_propagate_instructions_down.cpp
new file mode 100644
index 0000000..7a115ae
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_propagate_instructions_down.cpp
@@ -0,0 +1,68 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/fuzzer_pass_propagate_instructions_down.h"
+
+#include "source/fuzz/fuzzer_context.h"
+#include "source/fuzz/transformation_propagate_instruction_down.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassPropagateInstructionsDown::FuzzerPassPropagateInstructionsDown(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassPropagateInstructionsDown::~FuzzerPassPropagateInstructionsDown() =
+ default;
+
+void FuzzerPassPropagateInstructionsDown::Apply() {
+ for (const auto& function : *GetIRContext()->module()) {
+ std::vector<const opt::BasicBlock*> reachable_blocks;
+ for (const auto& block : function) {
+ if (GetIRContext()->GetDominatorAnalysis(&function)->IsReachable(
+ &block)) {
+ reachable_blocks.push_back(&block);
+ }
+ }
+
+ for (const auto* block : reachable_blocks) {
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfPropagatingInstructionsDown())) {
+ continue;
+ }
+
+ if (TransformationPropagateInstructionDown::IsApplicableToBlock(
+ GetIRContext(), block->id())) {
+ // Record fresh ids for every successor of the |block| that we can
+ // propagate an instruction into.
+ std::map<uint32_t, uint32_t> fresh_ids;
+ for (auto id :
+ TransformationPropagateInstructionDown::GetAcceptableSuccessors(
+ GetIRContext(), block->id())) {
+ fresh_ids[id] = GetFuzzerContext()->GetFreshId();
+ }
+
+ ApplyTransformation(TransformationPropagateInstructionDown(
+ block->id(), GetFuzzerContext()->GetFreshId(), fresh_ids));
+ }
+ }
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_propagate_instructions_down.h b/source/fuzz/fuzzer_pass_propagate_instructions_down.h
new file mode 100644
index 0000000..536bf00
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_propagate_instructions_down.h
@@ -0,0 +1,39 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_FUZZ_FUZZER_PASS_PROPAGATE_INSTRUCTIONS_DOWN_H_
+#define SOURCE_FUZZ_FUZZER_PASS_PROPAGATE_INSTRUCTIONS_DOWN_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Randomly propagates instructions from some block into the block's successors.
+class FuzzerPassPropagateInstructionsDown : public FuzzerPass {
+ public:
+ FuzzerPassPropagateInstructionsDown(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassPropagateInstructionsDown() override;
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_PROPAGATE_INSTRUCTIONS_DOWN_H_
diff --git a/source/fuzz/pass_management/repeated_pass_instances.h b/source/fuzz/pass_management/repeated_pass_instances.h
index 51ff2ae..8d2c0f8 100644
--- a/source/fuzz/pass_management/repeated_pass_instances.h
+++ b/source/fuzz/pass_management/repeated_pass_instances.h
@@ -54,6 +54,7 @@
#include "source/fuzz/fuzzer_pass_permute_blocks.h"
#include "source/fuzz/fuzzer_pass_permute_function_parameters.h"
#include "source/fuzz/fuzzer_pass_permute_instructions.h"
+#include "source/fuzz/fuzzer_pass_propagate_instructions_down.h"
#include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
#include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
#include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
@@ -145,6 +146,7 @@
REPEATED_PASS_INSTANCE(PermuteBlocks);
REPEATED_PASS_INSTANCE(PermuteFunctionParameters);
REPEATED_PASS_INSTANCE(PermuteInstructions);
+ REPEATED_PASS_INSTANCE(PropagateInstructionsDown);
REPEATED_PASS_INSTANCE(PropagateInstructionsUp);
REPEATED_PASS_INSTANCE(PushIdsThroughVariables);
REPEATED_PASS_INSTANCE(ReplaceAddsSubsMulsWithCarryingExtended);
diff --git a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
index 8894353..a6f024b 100644
--- a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
+++ b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
@@ -255,6 +255,13 @@
// No obvious follow-on passes
return {};
}
+ if (&pass == pass_instances_->GetPropagateInstructionsDown()) {
+ // - This fuzzer pass might create new synonyms that can later be applied.
+ // - This fuzzer pass might create irrelevant ids that can later be
+ // replaced.
+ return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms(),
+ pass_instances_->GetReplaceIrrelevantIds()});
+ }
if (&pass == pass_instances_->GetPropagateInstructionsUp()) {
// No obvious follow-on passes
return {};
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index eb01b97..20ab98e 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -552,6 +552,7 @@
TransformationAddLoopToCreateIntConstantSynonym add_loop_to_create_int_constant_synonym = 78;
TransformationWrapRegionInSelection wrap_region_in_selection = 79;
TransformationAddEarlyTerminatorWrapper add_early_terminator_wrapper = 80;
+ TransformationPropagateInstructionDown propagate_instruction_down = 81;
// Add additional option using the next available number.
}
}
@@ -1745,6 +1746,38 @@
}
+message TransformationPropagateInstructionDown {
+
+ // Propagates an instruction from |block_id| into its successors.
+ // Concretely, the transformation clones the propagated instruction
+ // into some of the successors of |block_id| and removes the original
+ // instruction. Additionally, an OpPhi instruction may be added to make sure
+ // that the transformation can be applied in various scenarios.
+ //
+ // Note that the instruction might not be propagated down into every successor
+ // of |block_id| since it might make the module invalid.
+
+ // Id of the block to propagate an instruction from. The decision on what
+ // instruction to propagate is made based on whether the instruction interacts
+ // with memory, whether that instruction is used in its block etc (see the
+ // transformation class for more details).
+ uint32 block_id = 1;
+
+ // A fresh id for an OpPhi instruction. This might not be used by the
+ // transformation since an OpPhi instruction is created only if needed
+ // (e.g. an instruction is propagated into divergent blocks).
+ uint32 phi_fresh_id = 2;
+
+ // A map from the id of some successor of the |block_id| to the fresh id.
+ // The map contains a fresh id for at least every successor of the |block_id|.
+ // Every fresh id in the map corresponds to the result id of the clone,
+ // propagated into the corresponding successor block. This transformation
+ // might use overflow ids if they are available and this field doesn't account
+ // for every successor of |block_id|.
+ repeated UInt32Pair successor_id_to_fresh_id = 3;
+
+}
+
message TransformationPropagateInstructionUp {
// Propagates an instruction in the block into the block's predecessors.
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index f03d6a9..cc3d010 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -70,6 +70,7 @@
#include "source/fuzz/transformation_outline_function.h"
#include "source/fuzz/transformation_permute_function_parameters.h"
#include "source/fuzz/transformation_permute_phi_operands.h"
+#include "source/fuzz/transformation_propagate_instruction_down.h"
#include "source/fuzz/transformation_propagate_instruction_up.h"
#include "source/fuzz/transformation_push_id_through_variable.h"
#include "source/fuzz/transformation_record_synonymous_constants.h"
@@ -259,6 +260,10 @@
case protobufs::Transformation::TransformationCase::kPermutePhiOperands:
return MakeUnique<TransformationPermutePhiOperands>(
message.permute_phi_operands());
+ case protobufs::Transformation::TransformationCase::
+ kPropagateInstructionDown:
+ return MakeUnique<TransformationPropagateInstructionDown>(
+ message.propagate_instruction_down());
case protobufs::Transformation::TransformationCase::kPropagateInstructionUp:
return MakeUnique<TransformationPropagateInstructionUp>(
message.propagate_instruction_up());
diff --git a/source/fuzz/transformation_propagate_instruction_down.cpp b/source/fuzz/transformation_propagate_instruction_down.cpp
new file mode 100644
index 0000000..ba22e39
--- /dev/null
+++ b/source/fuzz/transformation_propagate_instruction_down.cpp
@@ -0,0 +1,592 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/transformation_propagate_instruction_down.h"
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/instruction_descriptor.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationPropagateInstructionDown::TransformationPropagateInstructionDown(
+ const protobufs::TransformationPropagateInstructionDown& message)
+ : message_(message) {}
+
+TransformationPropagateInstructionDown::TransformationPropagateInstructionDown(
+ uint32_t block_id, uint32_t phi_fresh_id,
+ const std::map<uint32_t, uint32_t>& successor_id_to_fresh_id) {
+ message_.set_block_id(block_id);
+ message_.set_phi_fresh_id(phi_fresh_id);
+ *message_.mutable_successor_id_to_fresh_id() =
+ fuzzerutil::MapToRepeatedUInt32Pair(successor_id_to_fresh_id);
+}
+
+bool TransformationPropagateInstructionDown::IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const {
+ // Check that we can apply this transformation to the |block_id|.
+ if (!IsApplicableToBlock(ir_context, message_.block_id())) {
+ return false;
+ }
+
+ const auto successor_id_to_fresh_id =
+ fuzzerutil::RepeatedUInt32PairToMap(message_.successor_id_to_fresh_id());
+
+ for (auto id : GetAcceptableSuccessors(ir_context, message_.block_id())) {
+ // Each successor must have a fresh id in the |successor_id_to_fresh_id|
+ // map, unless overflow ids are available.
+ if (!successor_id_to_fresh_id.count(id) &&
+ !transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
+ return false;
+ }
+ }
+
+ std::vector<uint32_t> maybe_fresh_ids = {message_.phi_fresh_id()};
+ maybe_fresh_ids.reserve(successor_id_to_fresh_id.size());
+ for (const auto& entry : successor_id_to_fresh_id) {
+ maybe_fresh_ids.push_back(entry.second);
+ }
+
+ // All ids must be unique and fresh.
+ return !fuzzerutil::HasDuplicates(maybe_fresh_ids) &&
+ std::all_of(maybe_fresh_ids.begin(), maybe_fresh_ids.end(),
+ [ir_context](uint32_t id) {
+ return fuzzerutil::IsFreshId(ir_context, id);
+ });
+}
+
+void TransformationPropagateInstructionDown::Apply(
+ opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const {
+ // Get instruction to propagate down. There must be one.
+ auto* inst_to_propagate =
+ GetInstructionToPropagate(ir_context, message_.block_id());
+ assert(inst_to_propagate && "There must be an instruction to propagate");
+
+ auto successor_id_to_fresh_id =
+ fuzzerutil::RepeatedUInt32PairToMap(message_.successor_id_to_fresh_id());
+ std::vector<uint32_t> created_inst_ids;
+ auto successor_ids = GetAcceptableSuccessors(ir_context, message_.block_id());
+
+ // Clone |inst_to_propagate| into every successor.
+ for (auto successor_id : successor_ids) {
+ std::unique_ptr<opt::Instruction> clone(
+ inst_to_propagate->Clone(ir_context));
+
+ uint32_t new_result_id;
+ if (successor_id_to_fresh_id.count(successor_id)) {
+ new_result_id = successor_id_to_fresh_id.at(successor_id);
+ } else {
+ assert(transformation_context->GetOverflowIdSource()->HasOverflowIds() &&
+ "Overflow ids must be available");
+ new_result_id =
+ transformation_context->GetOverflowIdSource()->GetNextOverflowId();
+ successor_id_to_fresh_id[successor_id] = new_result_id;
+ }
+
+ clone->SetResultId(new_result_id);
+ fuzzerutil::UpdateModuleIdBound(ir_context, new_result_id);
+
+ auto* insert_before_inst = GetFirstInsertBeforeInstruction(
+ ir_context, successor_id, clone->opcode());
+ assert(insert_before_inst && "Can't insert into one of the successors");
+
+ insert_before_inst->InsertBefore(std::move(clone));
+ created_inst_ids.push_back(new_result_id);
+ }
+
+ // Add an OpPhi instruction into the module if possible.
+ if (auto merge_block_id = GetOpPhiBlockId(
+ ir_context, message_.block_id(), *inst_to_propagate, successor_ids)) {
+ opt::Instruction::OperandList in_operands;
+ std::unordered_set<uint32_t> visited_predecessors;
+ for (auto predecessor_id : ir_context->cfg()->preds(merge_block_id)) {
+ if (visited_predecessors.count(predecessor_id)) {
+ // Merge block might have multiple identical predecessors.
+ continue;
+ }
+
+ visited_predecessors.insert(predecessor_id);
+
+ const auto* dominator_analysis = ir_context->GetDominatorAnalysis(
+ ir_context->cfg()->block(message_.block_id())->GetParent());
+
+ // Find the successor of |source_block| that dominates the predecessor of
+ // the merge block |predecessor_id|.
+ auto it = std::find_if(
+ successor_ids.begin(), successor_ids.end(),
+ [predecessor_id, dominator_analysis](uint32_t successor_id) {
+ return dominator_analysis->Dominates(successor_id, predecessor_id);
+ });
+
+ // OpPhi requires a single operand pair for every predecessor of the
+ // OpPhi's block.
+ assert(it != successor_ids.end() && "Unable to insert OpPhi");
+
+ in_operands.push_back(
+ {SPV_OPERAND_TYPE_ID, {successor_id_to_fresh_id.at(*it)}});
+ in_operands.push_back({SPV_OPERAND_TYPE_ID, {predecessor_id}});
+ }
+
+ ir_context->cfg()
+ ->block(merge_block_id)
+ ->begin()
+ ->InsertBefore(MakeUnique<opt::Instruction>(
+ ir_context, SpvOpPhi, inst_to_propagate->type_id(),
+ message_.phi_fresh_id(), std::move(in_operands)));
+
+ fuzzerutil::UpdateModuleIdBound(ir_context, message_.phi_fresh_id());
+ created_inst_ids.push_back(message_.phi_fresh_id());
+ }
+
+ // Make sure analyses are updated when we adjust users of |inst_to_propagate|.
+ ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+
+ // Copy decorations from the original instructions to its propagated copies.
+ for (auto id : created_inst_ids) {
+ ir_context->get_decoration_mgr()->CloneDecorations(
+ inst_to_propagate->result_id(), id);
+ }
+
+ // Remove all decorations from the original instruction.
+ ir_context->get_decoration_mgr()->RemoveDecorationsFrom(
+ inst_to_propagate->result_id());
+
+ // Update every use of the |inst_to_propagate| with a result id of some of the
+ // newly created instructions.
+ ir_context->get_def_use_mgr()->ForEachUse(
+ inst_to_propagate, [ir_context, &created_inst_ids](
+ opt::Instruction* user, uint32_t operand_index) {
+ assert(ir_context->get_instr_block(user) &&
+ "All decorations should have already been adjusted");
+
+ auto in_operand_index =
+ fuzzerutil::InOperandIndexFromOperandIndex(*user, operand_index);
+ for (auto id : created_inst_ids) {
+ if (fuzzerutil::IdIsAvailableAtUse(ir_context, user, in_operand_index,
+ id)) {
+ user->SetInOperand(in_operand_index, {id});
+ return;
+ }
+ }
+
+ // Every user of |inst_to_propagate| must be updated since we will
+ // remove that instruction from the module.
+ assert(false && "Every user of |inst_to_propagate| must be updated");
+ });
+
+ // Add synonyms about newly created instructions.
+ assert(inst_to_propagate->HasResultId() &&
+ "Result id is required to add facts");
+ if (transformation_context->GetFactManager()->IdIsIrrelevant(
+ inst_to_propagate->result_id())) {
+ for (auto id : created_inst_ids) {
+ transformation_context->GetFactManager()->AddFactIdIsIrrelevant(id);
+ }
+ } else {
+ std::vector<uint32_t> non_irrelevant_ids;
+ for (auto id : created_inst_ids) {
+ // |id| can be irrelevant implicitly (e.g. if we propagate it into a dead
+ // block).
+ if (!transformation_context->GetFactManager()->IdIsIrrelevant(id)) {
+ non_irrelevant_ids.push_back(id);
+ }
+ }
+
+ if (transformation_context->GetFactManager()->PointeeValueIsIrrelevant(
+ inst_to_propagate->result_id())) {
+ for (auto id : non_irrelevant_ids) {
+ transformation_context->GetFactManager()
+ ->AddFactValueOfPointeeIsIrrelevant(id);
+ }
+ }
+
+ for (auto id : non_irrelevant_ids) {
+ transformation_context->GetFactManager()->AddFactDataSynonym(
+ MakeDataDescriptor(id, {}),
+ MakeDataDescriptor(non_irrelevant_ids[0], {}));
+ }
+ }
+
+ // Remove the propagated instruction from the module.
+ ir_context->KillInst(inst_to_propagate);
+
+ // We've adjusted all users - make sure these changes are analyzed.
+ ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+protobufs::Transformation TransformationPropagateInstructionDown::ToMessage()
+ const {
+ protobufs::Transformation result;
+ *result.mutable_propagate_instruction_down() = message_;
+ return result;
+}
+
+bool TransformationPropagateInstructionDown::IsOpcodeSupported(SpvOp opcode) {
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3605):
+ // We only support "simple" instructions that don't work with memory.
+ // We should extend this so that we support the ones that modify the memory
+ // too.
+ switch (opcode) {
+ case SpvOpUndef:
+ case SpvOpAccessChain:
+ case SpvOpInBoundsAccessChain:
+ case SpvOpArrayLength:
+ case SpvOpVectorExtractDynamic:
+ case SpvOpVectorInsertDynamic:
+ case SpvOpVectorShuffle:
+ case SpvOpCompositeConstruct:
+ case SpvOpCompositeExtract:
+ case SpvOpCompositeInsert:
+ case SpvOpCopyObject:
+ case SpvOpTranspose:
+ case SpvOpConvertFToU:
+ case SpvOpConvertFToS:
+ case SpvOpConvertSToF:
+ case SpvOpConvertUToF:
+ case SpvOpUConvert:
+ case SpvOpSConvert:
+ case SpvOpFConvert:
+ case SpvOpQuantizeToF16:
+ case SpvOpSatConvertSToU:
+ case SpvOpSatConvertUToS:
+ case SpvOpBitcast:
+ case SpvOpSNegate:
+ case SpvOpFNegate:
+ case SpvOpIAdd:
+ case SpvOpFAdd:
+ case SpvOpISub:
+ case SpvOpFSub:
+ case SpvOpIMul:
+ case SpvOpFMul:
+ case SpvOpUDiv:
+ case SpvOpSDiv:
+ case SpvOpFDiv:
+ case SpvOpUMod:
+ case SpvOpSRem:
+ case SpvOpSMod:
+ case SpvOpFRem:
+ case SpvOpFMod:
+ case SpvOpVectorTimesScalar:
+ case SpvOpMatrixTimesScalar:
+ case SpvOpVectorTimesMatrix:
+ case SpvOpMatrixTimesVector:
+ case SpvOpMatrixTimesMatrix:
+ case SpvOpOuterProduct:
+ case SpvOpDot:
+ case SpvOpIAddCarry:
+ case SpvOpISubBorrow:
+ case SpvOpUMulExtended:
+ case SpvOpSMulExtended:
+ case SpvOpAny:
+ case SpvOpAll:
+ case SpvOpIsNan:
+ case SpvOpIsInf:
+ case SpvOpIsFinite:
+ case SpvOpIsNormal:
+ case SpvOpSignBitSet:
+ case SpvOpLessOrGreater:
+ case SpvOpOrdered:
+ case SpvOpUnordered:
+ case SpvOpLogicalEqual:
+ case SpvOpLogicalNotEqual:
+ case SpvOpLogicalOr:
+ case SpvOpLogicalAnd:
+ case SpvOpLogicalNot:
+ case SpvOpSelect:
+ case SpvOpIEqual:
+ case SpvOpINotEqual:
+ case SpvOpUGreaterThan:
+ case SpvOpSGreaterThan:
+ case SpvOpUGreaterThanEqual:
+ case SpvOpSGreaterThanEqual:
+ case SpvOpULessThan:
+ case SpvOpSLessThan:
+ case SpvOpULessThanEqual:
+ case SpvOpSLessThanEqual:
+ case SpvOpFOrdEqual:
+ case SpvOpFUnordEqual:
+ case SpvOpFOrdNotEqual:
+ case SpvOpFUnordNotEqual:
+ case SpvOpFOrdLessThan:
+ case SpvOpFUnordLessThan:
+ case SpvOpFOrdGreaterThan:
+ case SpvOpFUnordGreaterThan:
+ case SpvOpFOrdLessThanEqual:
+ case SpvOpFUnordLessThanEqual:
+ case SpvOpFOrdGreaterThanEqual:
+ case SpvOpFUnordGreaterThanEqual:
+ case SpvOpShiftRightLogical:
+ case SpvOpShiftRightArithmetic:
+ case SpvOpShiftLeftLogical:
+ case SpvOpBitwiseOr:
+ case SpvOpBitwiseXor:
+ case SpvOpBitwiseAnd:
+ case SpvOpNot:
+ case SpvOpBitFieldInsert:
+ case SpvOpBitFieldSExtract:
+ case SpvOpBitFieldUExtract:
+ case SpvOpBitReverse:
+ case SpvOpBitCount:
+ case SpvOpCopyLogical:
+ case SpvOpPtrEqual:
+ case SpvOpPtrNotEqual:
+ return true;
+ default:
+ return false;
+ }
+}
+
+opt::Instruction*
+TransformationPropagateInstructionDown::GetInstructionToPropagate(
+ opt::IRContext* ir_context, uint32_t block_id) {
+ auto* block = ir_context->cfg()->block(block_id);
+ assert(block && "|block_id| is invalid");
+
+ for (auto it = block->rbegin(); it != block->rend(); ++it) {
+ if (!it->result_id() || !it->type_id() ||
+ !IsOpcodeSupported(it->opcode())) {
+ continue;
+ }
+
+ auto all_users_from_different_blocks =
+ ir_context->get_def_use_mgr()->WhileEachUser(
+ &*it, [ir_context, block](opt::Instruction* user) {
+ return ir_context->get_instr_block(user) != block;
+ });
+
+ if (!all_users_from_different_blocks) {
+ // We can't propagate an instruction if it's used in the same block.
+ continue;
+ }
+
+ return &*it;
+ }
+
+ return nullptr;
+}
+
+bool TransformationPropagateInstructionDown::IsApplicableToBlock(
+ opt::IRContext* ir_context, uint32_t block_id) {
+ // Check that |block_id| is valid.
+ const auto* block = fuzzerutil::MaybeFindBlock(ir_context, block_id);
+ if (!block) {
+ return false;
+ }
+
+ const auto* dominator_analysis =
+ ir_context->GetDominatorAnalysis(block->GetParent());
+
+ // |block| must be reachable.
+ if (!dominator_analysis->IsReachable(block)) {
+ return false;
+ }
+
+ // The block must have an instruction to propagate.
+ const auto* inst_to_propagate =
+ GetInstructionToPropagate(ir_context, block_id);
+ if (!inst_to_propagate) {
+ return false;
+ }
+
+ // Check that |block| has successors.
+ auto successor_ids = GetAcceptableSuccessors(ir_context, block_id);
+ if (successor_ids.empty()) {
+ return false;
+ }
+
+ // Check that |successor_block| doesn't have any OpPhi instructions that
+ // use |inst|.
+ for (auto successor_id : successor_ids) {
+ for (const auto& maybe_phi_inst : *ir_context->cfg()->block(successor_id)) {
+ if (maybe_phi_inst.opcode() != SpvOpPhi) {
+ // OpPhis can be intermixed with OpLine and OpNoLine.
+ continue;
+ }
+
+ for (uint32_t i = 0; i < maybe_phi_inst.NumInOperands(); i += 2) {
+ if (maybe_phi_inst.GetSingleWordInOperand(i) ==
+ inst_to_propagate->result_id()) {
+ return false;
+ }
+ }
+ }
+ }
+
+ // Get the result id of the block we will insert OpPhi instruction into.
+ // This is either 0 or a result id of some merge block in the function.
+ auto phi_block_id =
+ GetOpPhiBlockId(ir_context, block_id, *inst_to_propagate, successor_ids);
+
+ // Make sure we can adjust all users of the propagated instruction.
+ return ir_context->get_def_use_mgr()->WhileEachUse(
+ inst_to_propagate,
+ [ir_context, &successor_ids, dominator_analysis, phi_block_id](
+ opt::Instruction* user, uint32_t index) {
+ const auto* user_block = ir_context->get_instr_block(user);
+
+ if (!user_block) {
+ // |user| might be a global instruction (e.g. OpDecorate).
+ return true;
+ }
+
+ // Check that at least one of the ids in |successor_ids| or a
+ // |phi_block_id| dominates |user|'s block (or its predecessor if the
+ // user is an OpPhi). We can't use fuzzerutil::IdIsAvailableAtUse since
+ // the id in question hasn't yet been created in the module.
+ auto block_id_to_dominate = user->opcode() == SpvOpPhi
+ ? user->GetSingleWordOperand(index + 1)
+ : user_block->id();
+
+ if (phi_block_id != 0 &&
+ dominator_analysis->Dominates(phi_block_id, block_id_to_dominate)) {
+ return true;
+ }
+
+ return std::any_of(
+ successor_ids.begin(), successor_ids.end(),
+ [dominator_analysis, block_id_to_dominate](uint32_t id) {
+ return dominator_analysis->Dominates(id, block_id_to_dominate);
+ });
+ });
+}
+
+opt::Instruction*
+TransformationPropagateInstructionDown::GetFirstInsertBeforeInstruction(
+ opt::IRContext* ir_context, uint32_t block_id, SpvOp opcode) {
+ auto* block = ir_context->cfg()->block(block_id);
+
+ auto it = block->begin();
+
+ while (it != block->end() &&
+ !fuzzerutil::CanInsertOpcodeBeforeInstruction(opcode, it)) {
+ ++it;
+ }
+
+ return it == block->end() ? nullptr : &*it;
+}
+
+std::unordered_set<uint32_t>
+TransformationPropagateInstructionDown::GetAcceptableSuccessors(
+ opt::IRContext* ir_context, uint32_t block_id) {
+ const auto* block = ir_context->cfg()->block(block_id);
+ assert(block && "|block_id| is invalid");
+
+ const auto* inst = GetInstructionToPropagate(ir_context, block_id);
+ assert(inst && "The block must have an instruction to propagate");
+
+ std::unordered_set<uint32_t> result;
+ block->ForEachSuccessorLabel([ir_context, &result,
+ inst](uint32_t successor_id) {
+ if (result.count(successor_id)) {
+ return;
+ }
+
+ auto* successor_block = ir_context->cfg()->block(successor_id);
+
+ // We can't propagate |inst| into |successor_block| if the latter is not
+ // dominated by the |inst|'s dependencies.
+ if (!inst->WhileEachInId([ir_context, successor_block](const uint32_t* id) {
+ return fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, &*successor_block->begin(), *id);
+ })) {
+ return;
+ }
+
+ // We don't propagate any "special" instructions (e.g. OpSelectionMerge
+ // etc), thus, insertion point must always exist if the module is valid.
+ assert(GetFirstInsertBeforeInstruction(ir_context, successor_id,
+ inst->opcode()) &&
+ "There must exist an insertion point.");
+
+ result.insert(successor_id);
+ });
+
+ return result;
+}
+
+uint32_t TransformationPropagateInstructionDown::GetOpPhiBlockId(
+ opt::IRContext* ir_context, uint32_t block_id,
+ const opt::Instruction& inst_to_propagate,
+ const std::unordered_set<uint32_t>& successor_ids) {
+ const auto* block = ir_context->cfg()->block(block_id);
+
+ // |block_id| must belong to some construct.
+ auto merge_block_id =
+ block->GetMergeInst()
+ ? block->GetMergeInst()->GetSingleWordInOperand(0)
+ : ir_context->GetStructuredCFGAnalysis()->MergeBlock(block_id);
+ if (!merge_block_id) {
+ return 0;
+ }
+
+ const auto* dominator_analysis =
+ ir_context->GetDominatorAnalysis(block->GetParent());
+
+ // Check that |merge_block_id| is reachable in the CFG and |block_id|
+ // dominates |merge_block_id|.
+ if (!dominator_analysis->IsReachable(merge_block_id) ||
+ !dominator_analysis->Dominates(block_id, merge_block_id)) {
+ return 0;
+ }
+
+ // We can't insert an OpPhi into |merge_block_id| if it's an acceptable
+ // successor of |block_id|.
+ if (successor_ids.count(merge_block_id)) {
+ return 0;
+ }
+
+ // All predecessors of the merge block must be dominated by at least one
+ // successor of the |block_id|.
+ assert(!ir_context->cfg()->preds(merge_block_id).empty() &&
+ "Merge block must be reachable");
+ for (auto predecessor_id : ir_context->cfg()->preds(merge_block_id)) {
+ if (std::none_of(
+ successor_ids.begin(), successor_ids.end(),
+ [dominator_analysis, predecessor_id](uint32_t successor_id) {
+ return dominator_analysis->Dominates(successor_id,
+ predecessor_id);
+ })) {
+ return 0;
+ }
+ }
+
+ const auto* propagate_type =
+ ir_context->get_type_mgr()->GetType(inst_to_propagate.type_id());
+ assert(propagate_type && "|inst_to_propagate| must have a valid type");
+
+ // VariablePointers capability implicitly declares
+ // VariablePointersStorageBuffer. We need those capabilities since otherwise
+ // OpPhi instructions cannot have operands of pointer types.
+ if (propagate_type->AsPointer() &&
+ !ir_context->get_feature_mgr()->HasCapability(
+ SpvCapabilityVariablePointersStorageBuffer)) {
+ return 0;
+ }
+
+ return merge_block_id;
+}
+
+std::unordered_set<uint32_t>
+TransformationPropagateInstructionDown::GetFreshIds() const {
+ std::unordered_set<uint32_t> result = {message_.phi_fresh_id()};
+ for (const auto& pair : message_.successor_id_to_fresh_id()) {
+ result.insert(pair.second());
+ }
+ return result;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_propagate_instruction_down.h b/source/fuzz/transformation_propagate_instruction_down.h
new file mode 100644
index 0000000..7eca1ad
--- /dev/null
+++ b/source/fuzz/transformation_propagate_instruction_down.h
@@ -0,0 +1,184 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_FUZZ_TRANSFORMATION_PROPAGATE_INSTRUCTION_DOWN_H_
+#define SOURCE_FUZZ_TRANSFORMATION_PROPAGATE_INSTRUCTION_DOWN_H_
+
+#include <map>
+
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/fuzz/transformation_context.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationPropagateInstructionDown : public Transformation {
+ public:
+ explicit TransformationPropagateInstructionDown(
+ const protobufs::TransformationPropagateInstructionDown& message);
+
+ TransformationPropagateInstructionDown(
+ uint32_t block_id, uint32_t phi_fresh_id,
+ const std::map<uint32_t, uint32_t>& successor_id_to_fresh_id);
+
+ // - It should be possible to apply this transformation to |block_id| (see
+ // IsApplicableToBlock method).
+ // - Every acceptable successor of |block_id| (see GetAcceptableSuccessors
+ // method) must have an entry in the |successor_id_to_fresh_id| map unless
+ // overflow ids are available.
+ // - All values in |successor_id_to_fresh_id| and |phi_fresh_id| must be
+ // unique and fresh.
+ bool IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const override;
+
+ // - Adds a clone of the propagated instruction into every acceptable
+ // successor of |block_id|.
+ // - Removes the original instruction.
+ // - Creates an OpPhi instruction if possible, that tries to group created
+ // clones.
+ // - If the original instruction's id was irrelevant - marks created
+ // instructions as irrelevant. Otherwise, marks the created instructions as
+ // synonymous to each other if possible (i.e. skips instructions, copied
+ // into dead blocks).
+ void Apply(opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const override;
+
+ protobufs::Transformation ToMessage() const override;
+
+ // Returns true if this transformation can be applied to the block with id
+ // |block_id|. Concretely, returns true iff:
+ // - |block_id| is a result id of some reachable basic block in the module.
+ // - the block has an instruction to propagate (see
+ // GetInstructionToPropagate method).
+ // - the block has at least one acceptable successor (see
+ // GetAcceptableSuccessors method).
+ // - none of the acceptable successors have OpPhi instructions that use the
+ // original instruction.
+ // - it is possible to replace every use of the original instruction with some
+ // of the propagated instructions (or an OpPhi if we can create it - see
+ // GetOpPhiBlockId method).
+ static bool IsApplicableToBlock(opt::IRContext* ir_context,
+ uint32_t block_id);
+
+ // Returns ids of successors of |block_id|, that can be used to propagate an
+ // instruction into. Concretely, a successor block is acceptable if all
+ // dependencies of the propagated instruction dominate it. Note that this
+ // implies that an acceptable successor must be reachable in the CFG.
+ // For example:
+ // %1 = OpLabel
+ // OpSelectionMerge %2 None
+ // OpBranchConditional %cond %2 %3
+ // %3 = OpLabel
+ // %4 = OpUndef %int
+ // %5 = OpCopyObject %int %4
+ // OpBranch %2
+ // %2 = OpLabel
+ // ...
+ // In this example, %2 is not an acceptable successor of %3 since one of the
+ // dependencies (%4) of the propagated instruction (%5) does not dominate it.
+ static std::unordered_set<uint32_t> GetAcceptableSuccessors(
+ opt::IRContext* ir_context, uint32_t block_id);
+
+ std::unordered_set<uint32_t> GetFreshIds() const override;
+
+ private:
+ // Returns the last possible instruction in the |block_id| that satisfies the
+ // following properties:
+ // - has result id
+ // - has type id
+ // - has supported opcode (see IsOpcodeSupported method)
+ // - has no users in its basic block.
+ // Returns nullptr if no such an instruction exists. For example:
+ // %1 = OpLabel
+ // %2 = OpUndef %int
+ // %3 = OpUndef %int
+ // OpStore %var %3
+ // OpBranch %some_block
+ // In this example:
+ // - We cannot propagate OpBranch nor OpStore since they both have unsupported
+ // opcodes and have neither result ids nor type ids.
+ // - We cannot propagate %3 either since it is used by OpStore.
+ // - We can propagate %2 since it satisfies all our conditions.
+ // The basic idea behind this method it to make sure that the returned
+ // instruction will not break domination rules in its original block when
+ // propagated.
+ static opt::Instruction* GetInstructionToPropagate(opt::IRContext* ir_context,
+ uint32_t block_id);
+
+ // Returns true if |opcode| is supported by this transformation.
+ static bool IsOpcodeSupported(SpvOp opcode);
+
+ // Returns the first instruction in the |block| that allows us to insert
+ // |opcode| above itself. Returns nullptr is no such instruction exists.
+ static opt::Instruction* GetFirstInsertBeforeInstruction(
+ opt::IRContext* ir_context, uint32_t block_id, SpvOp opcode);
+
+ // Returns a result id of a basic block, where an OpPhi instruction can be
+ // inserted. Returns nullptr if it's not possible to create an OpPhi. The
+ // created OpPhi instruction groups all the propagated clones of the original
+ // instruction. |block_id| is a result id of the block we propagate the
+ // instruction from. |successor_ids| contains result ids of the successors we
+ // propagate the instruction into. Concretely, returns a non-null value if:
+ // - |block_id| is in some construct.
+ // - The merge block of that construct is reachable.
+ // - |block_id| dominates that merge block.
+ // - That merge block may not be an acceptable successor of |block_id|.
+ // - There must be at least one |block_id|'s acceptable successor for every
+ // predecessor of the merge block, dominating that predecessor.
+ // - We can't create an OpPhi if the module has neither VariablePointers nor
+ // VariablePointersStorageBuffer capabilities.
+ // A simple example of when we can insert an OpPhi instruction is:
+ // - This snippet of code:
+ // %1 = OpLabel
+ // %2 = OpUndef %int
+ // OpSelectionMerge %5 None
+ // OpBranchConditional %cond %3 %4
+ // %3 = OpLabel
+ // OpBranch %5
+ // %4 = OpLabel
+ // OpBranch %5
+ // %5 = OpLabel
+ // ...
+ // will be transformed into the following one (if %2 is propagated):
+ // %1 = OpLabel
+ // OpSelectionMerge %5 None
+ // OpBranchConditional %cond %3 %4
+ // %3 = OpLabel
+ // %6 = OpUndef %int
+ // OpBranch %5
+ // %4 = OpLabel
+ // %7 = OpUndef %int
+ // OpBranch %5
+ // %5 = OpLabel
+ // %8 = OpPhi %int %6 %3 %7 %4
+ // ...
+ // The fact that we introduce an OpPhi allows us to increase the applicability
+ // of the transformation. Concretely, we wouldn't be able to apply it in the
+ // example above if %2 were used in %5. Some more complicated examples can be
+ // found in unit tests.
+ static uint32_t GetOpPhiBlockId(
+ opt::IRContext* ir_context, uint32_t block_id,
+ const opt::Instruction& inst_to_propagate,
+ const std::unordered_set<uint32_t>& successor_ids);
+
+ protobufs::TransformationPropagateInstructionDown message_;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_PROPAGATE_INSTRUCTION_DOWN_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index ecccaa3..c42bd2d 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -87,6 +87,7 @@
transformation_outline_function_test.cpp
transformation_permute_function_parameters_test.cpp
transformation_permute_phi_operands_test.cpp
+ transformation_propagate_instruction_down_test.cpp
transformation_propagate_instruction_up_test.cpp
transformation_push_id_through_variable_test.cpp
transformation_replace_add_sub_mul_with_carrying_extended_test.cpp
diff --git a/test/fuzz/fuzz_test_util.cpp b/test/fuzz/fuzz_test_util.cpp
index c48e5fc..b875402 100644
--- a/test/fuzz/fuzz_test_util.cpp
+++ b/test/fuzz/fuzz_test_util.cpp
@@ -158,12 +158,5 @@
}
}
-void ApplyAndCheckFreshIds(const Transformation& transformation,
- opt::IRContext* ir_context,
- TransformationContext* transformation_context) {
- ApplyAndCheckFreshIds(transformation, ir_context, transformation_context,
- std::unordered_set<uint32_t>());
-}
-
} // namespace fuzz
} // namespace spvtools
diff --git a/test/fuzz/fuzz_test_util.h b/test/fuzz/fuzz_test_util.h
index b094a1d..5d02ef6 100644
--- a/test/fuzz/fuzz_test_util.h
+++ b/test/fuzz/fuzz_test_util.h
@@ -120,12 +120,7 @@
void ApplyAndCheckFreshIds(
const Transformation& transformation, opt::IRContext* ir_context,
TransformationContext* transformation_context,
- const std::unordered_set<uint32_t>& issued_overflow_ids);
-
-// Invokes ApplyAndCheckFreshIds above, with an empty set of overflow ids.
-void ApplyAndCheckFreshIds(const Transformation& transformation,
- opt::IRContext* ir_context,
- TransformationContext* transformation_context);
+ const std::unordered_set<uint32_t>& issued_overflow_ids = {{}});
} // namespace fuzz
} // namespace spvtools
diff --git a/test/fuzz/transformation_propagate_instruction_down_test.cpp b/test/fuzz/transformation_propagate_instruction_down_test.cpp
new file mode 100644
index 0000000..ecb4a67
--- /dev/null
+++ b/test/fuzz/transformation_propagate_instruction_down_test.cpp
@@ -0,0 +1,1124 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/transformation_propagate_instruction_down.h"
+
+#include "source/fuzz/counter_overflow_id_source.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationPropagateInstructionDownTest, BasicTest) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %9 = OpTypePointer Function %6
+ %4 = OpFunction %2 None %3
+
+ ; Has no instruction to propagate
+ %5 = OpLabel
+ %10 = OpVariable %9 Function
+ %8 = OpCopyObject %6 %7
+ OpStore %10 %8
+ OpBranch %11
+
+ ; Unreachable block
+ %100 = OpLabel
+ %101 = OpCopyObject %6 %7
+ OpBranch %11
+
+ ; Selection header
+ ;
+ ; One of acceptable successors has an OpPhi that uses propagated
+ ; instruction's id
+ %11 = OpLabel
+ %19 = OpCopyObject %6 %7
+ OpSelectionMerge %18 None
+ OpBranchConditional %13 %14 %18
+
+ ; %16 has no acceptable successors
+ %14 = OpLabel
+ %20 = OpPhi %6 %19 %11
+ %15 = OpCopyObject %6 %7 ; dependency
+ OpBranch %16
+ %16 = OpLabel
+ %17 = OpCopyObject %6 %15
+ OpBranch %18
+
+ ; Can be applied
+ %18 = OpLabel
+ %21 = OpCopyObject %6 %7
+ OpSelectionMerge %24 None
+ OpBranchConditional %13 %22 %23
+ %22 = OpLabel
+ %29 = OpPhi %6 %7 %18
+ OpStore %10 %21
+ OpBranch %24
+ %23 = OpLabel
+ OpStore %10 %21
+ OpBranch %24
+ %24 = OpLabel
+ OpStore %10 %21
+ OpBranch %32
+
+ ; Can't replace all uses of the propagated instruction: %30 is
+ ; propagated into %27.
+ %32 = OpLabel
+ OpLoopMerge %28 %27 None
+ OpBranchConditional %13 %26 %28
+ %26 = OpLabel
+ %25 = OpCopyObject %6 %7
+ %30 = OpCopyObject %6 %25
+ OpBranchConditional %13 %27 %28
+ %27 = OpLabel
+ OpBranch %32
+ %28 = OpLabel
+ %31 = OpPhi %6 %30 %26 %7 %32 ; Can't replace this use
+ OpReturn
+
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ // Invalid block id.
+ ASSERT_FALSE(TransformationPropagateInstructionDown(200, 200, {{}})
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationPropagateInstructionDown(101, 200, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // The block is unreachable.
+ ASSERT_FALSE(TransformationPropagateInstructionDown(100, 200, {{}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // The block has no instruction to propagate.
+ ASSERT_FALSE(TransformationPropagateInstructionDown(5, 200, {{{11, 201}}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // The block has no acceptable successors.
+ ASSERT_FALSE(TransformationPropagateInstructionDown(16, 200, {{{18, 201}}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // One of acceptable successors has an OpPhi that uses propagated
+ // instruction's id.
+ ASSERT_FALSE(
+ TransformationPropagateInstructionDown(11, 200, {{{14, 201}, {18, 202}}})
+ .IsApplicable(context.get(), transformation_context));
+
+#ifndef NDEBUG
+ // Not all fresh ids are provided.
+ ASSERT_DEATH(
+ TransformationPropagateInstructionDown(18, 200, {{{22, 201}, {202, 203}}})
+ .IsApplicable(context.get(), transformation_context),
+ "Bad attempt to query whether overflow ids are available.");
+#endif
+
+ // Not all fresh ids are fresh.
+ ASSERT_FALSE(TransformationPropagateInstructionDown(
+ 18, 18, {{{22, 201}, {23, 202}, {202, 203}}})
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationPropagateInstructionDown(
+ 18, 200, {{{22, 22}, {23, 202}, {202, 203}}})
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationPropagateInstructionDown(
+ 18, 18, {{{22, 22}, {23, 202}, {202, 203}}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Not all fresh ids are unique.
+ ASSERT_FALSE(TransformationPropagateInstructionDown(
+ 18, 200, {{{22, 200}, {23, 202}, {202, 200}}})
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationPropagateInstructionDown(
+ 18, 200, {{{22, 201}, {23, 202}, {202, 200}}})
+ .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(TransformationPropagateInstructionDown(
+ 18, 200, {{{22, 201}, {23, 201}, {202, 203}}})
+ .IsApplicable(context.get(), transformation_context));
+
+ // Can't replace all uses of the propagated instruction: %30 is propagated
+ // into %27.
+ ASSERT_FALSE(TransformationPropagateInstructionDown(26, 200, {{{27, 201}}})
+ .IsApplicable(context.get(), transformation_context));
+
+ {
+ TransformationPropagateInstructionDown transformation(
+ 18, 200, {{{22, 201}, {23, 202}, {202, 203}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ ASSERT_TRUE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(201, {}), MakeDataDescriptor(202, {})));
+ ASSERT_TRUE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(201, {}), MakeDataDescriptor(200, {})));
+ }
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %9 = OpTypePointer Function %6
+ %4 = OpFunction %2 None %3
+
+ ; Has no instruction to propagate
+ %5 = OpLabel
+ %10 = OpVariable %9 Function
+ %8 = OpCopyObject %6 %7
+ OpStore %10 %8
+ OpBranch %11
+
+ ; Unreachable block
+ %100 = OpLabel
+ %101 = OpCopyObject %6 %7
+ OpBranch %11
+
+ ; Selection header
+ ;
+ ; One of acceptable successors has an OpPhi that uses propagated
+ ; instruction's id
+ %11 = OpLabel
+ %19 = OpCopyObject %6 %7
+ OpSelectionMerge %18 None
+ OpBranchConditional %13 %14 %18
+
+ ; %16 has no acceptable successors
+ %14 = OpLabel
+ %20 = OpPhi %6 %19 %11
+ %15 = OpCopyObject %6 %7 ; dependency
+ OpBranch %16
+ %16 = OpLabel
+ %17 = OpCopyObject %6 %15
+ OpBranch %18
+
+ ; Can be applied
+ %18 = OpLabel
+ OpSelectionMerge %24 None
+ OpBranchConditional %13 %22 %23
+ %22 = OpLabel
+ %29 = OpPhi %6 %7 %18
+ %201 = OpCopyObject %6 %7
+ OpStore %10 %201
+ OpBranch %24
+ %23 = OpLabel
+ %202 = OpCopyObject %6 %7
+ OpStore %10 %202
+ OpBranch %24
+ %24 = OpLabel
+ %200 = OpPhi %6 %201 %22 %202 %23
+ OpStore %10 %200
+ OpBranch %32
+
+ ; Can't replace all uses of the propagated instruction: %30 is
+ ; propagated into %27.
+ %32 = OpLabel
+ OpLoopMerge %28 %27 None
+ OpBranchConditional %13 %26 %28
+ %26 = OpLabel
+ %25 = OpCopyObject %6 %7
+ %30 = OpCopyObject %6 %25
+ OpBranchConditional %13 %27 %28
+ %27 = OpLabel
+ OpBranch %32
+ %28 = OpLabel
+ %31 = OpPhi %6 %30 %26 %7 %32 ; Can't replace this use
+ OpReturn
+
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationPropagateInstructionDownTest, CantCreateOpPhiTest) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+
+ ; %5 doesn't belong to any construct
+ %5 = OpLabel
+ %15 = OpCopyObject %6 %7
+ OpBranch %16
+
+ ; The merge block (%19) is unreachable
+ %16 = OpLabel
+ %17 = OpCopyObject %6 %7
+ OpSelectionMerge %19 None
+ OpBranchConditional %13 %18 %18
+
+ ; %21 doesn't dominate the merge block - %20
+ %18 = OpLabel
+ OpSelectionMerge %20 None
+ OpBranchConditional %13 %20 %21
+ %21 = OpLabel
+ %22 = OpCopyObject %6 %7
+ OpBranch %20
+
+ ; The merge block (%24) is an acceptable successor of the propagated
+ ; instruction's block
+ %20 = OpLabel
+ %23 = OpCopyObject %6 %7
+ OpSelectionMerge %24 None
+ OpBranchConditional %13 %24 %30
+ %30 = OpLabel
+ OpBranch %24
+
+ ; One of the predecessors of the merge block is not dominated by any
+ ; successor of the propagated instruction's block
+ %24 = OpLabel
+ %26 = OpCopyObject %6 %7
+ OpLoopMerge %29 %25 None
+ OpBranch %25
+ %25 = OpLabel
+ OpBranchConditional %13 %24 %29
+ %28 = OpLabel ; unreachable predecessor of %29
+ OpBranch %29
+ %29 = OpLabel
+ OpReturn
+
+ %19 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ TransformationPropagateInstructionDown transformations[] = {
+ // %5 doesn't belong to any construct.
+ {5, 200, {{{16, 201}}}},
+
+ // The merge block (%19) is unreachable.
+ {16, 200, {{{18, 202}}}},
+
+ // %21 doesn't dominate the merge block - %20.
+ {21, 200, {{{20, 203}}}},
+
+ // The merge block (%24) is an acceptable successor of the propagated
+ // instruction's block.
+ {20, 200, {{{24, 204}, {30, 205}}}},
+
+ // One of the predecessors of the merge block is not dominated by any
+ // successor of the propagated instruction's block.
+ {24, 200, {{{25, 206}}}},
+ };
+
+ for (const auto& transformation : transformations) {
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+
+ // No transformation has introduced an OpPhi instruction.
+ ASSERT_FALSE(context->get_def_use_mgr()->GetDef(200));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+
+ ; %5 doesn't belong to any construct
+ %5 = OpLabel
+ OpBranch %16
+
+ ; The merge block (%19) is unreachable
+ %16 = OpLabel
+ %201 = OpCopyObject %6 %7
+ OpSelectionMerge %19 None
+ OpBranchConditional %13 %18 %18
+
+ ; %21 doesn't dominate the merge block - %20
+ %18 = OpLabel
+ %202 = OpCopyObject %6 %7
+ OpSelectionMerge %20 None
+ OpBranchConditional %13 %20 %21
+ %21 = OpLabel
+ OpBranch %20
+
+ ; The merge block (%24) is an acceptable successor of the propagated
+ ; instruction's block
+ %20 = OpLabel
+ %203 = OpCopyObject %6 %7
+ OpSelectionMerge %24 None
+ OpBranchConditional %13 %24 %30
+ %30 = OpLabel
+ %205 = OpCopyObject %6 %7
+ OpBranch %24
+
+ ; One of the predecessors of the merge block is not dominated by any
+ ; successor of the propagated instruction's block
+ %24 = OpLabel
+ %204 = OpCopyObject %6 %7
+ OpLoopMerge %29 %25 None
+ OpBranch %25
+ %25 = OpLabel
+ %206 = OpCopyObject %6 %7
+ OpBranchConditional %13 %24 %29
+ %28 = OpLabel ; unreachable predecessor of %29
+ OpBranch %29
+ %29 = OpLabel
+ OpReturn
+
+ %19 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationPropagateInstructionDownTest, VariablePointersCapability) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %10 = OpTypePointer Workgroup %6
+ %11 = OpVariable %10 Workgroup
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %18 = OpCopyObject %10 %11
+ %14 = OpCopyObject %10 %11
+ OpSelectionMerge %17 None
+ OpBranchConditional %13 %15 %16
+ %15 = OpLabel
+ OpBranch %17
+ %16 = OpLabel
+ OpBranch %17
+ %17 = OpLabel
+ OpStore %18 %7
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ {
+ // Can propagate a pointer only if we don't have to create an OpPhi.
+ TransformationPropagateInstructionDown transformation(
+ 5, 200, {{{15, 201}, {16, 202}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ ASSERT_FALSE(context->get_def_use_mgr()->GetDef(200));
+ }
+ {
+ // Can't propagate a pointer if there is no VariablePointersStorageBuffer
+ // capability and we need to create an OpPhi.
+ TransformationPropagateInstructionDown transformation(
+ 5, 200, {{{15, 203}, {16, 204}}});
+ ASSERT_FALSE(context->get_feature_mgr()->HasCapability(
+ SpvCapabilityVariablePointersStorageBuffer));
+ ASSERT_FALSE(
+ transformation.IsApplicable(context.get(), transformation_context));
+
+ context->AddCapability(SpvCapabilityVariablePointers);
+ ASSERT_TRUE(context->get_feature_mgr()->HasCapability(
+ SpvCapabilityVariablePointersStorageBuffer));
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %10 = OpTypePointer Workgroup %6
+ %11 = OpVariable %10 Workgroup
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %17 None
+ OpBranchConditional %13 %15 %16
+ %15 = OpLabel
+ %203 = OpCopyObject %10 %11
+ %201 = OpCopyObject %10 %11
+ OpBranch %17
+ %16 = OpLabel
+ %204 = OpCopyObject %10 %11
+ %202 = OpCopyObject %10 %11
+ OpBranch %17
+ %17 = OpLabel
+ %200 = OpPhi %10 %203 %15 %204 %16
+ OpStore %200 %7
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationPropagateInstructionDownTest, UseOverflowIdsTest) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %10 = OpTypePointer Private %6
+ %11 = OpVariable %10 Private
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %20 = OpCopyObject %6 %7
+ OpSelectionMerge %23 None
+ OpBranchConditional %13 %21 %22
+ %21 = OpLabel
+ OpStore %11 %20
+ OpBranch %23
+ %22 = OpLabel
+ OpStore %11 %20
+ OpBranch %23
+ %23 = OpLabel
+ OpStore %11 %20
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options,
+ MakeUnique<CounterOverflowIdSource>(300));
+
+ TransformationPropagateInstructionDown transformation(5, 200, {{{21, 201}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context,
+ {300});
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %10 = OpTypePointer Private %6
+ %11 = OpVariable %10 Private
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %23 None
+ OpBranchConditional %13 %21 %22
+ %21 = OpLabel
+ %201 = OpCopyObject %6 %7
+ OpStore %11 %201
+ OpBranch %23
+ %22 = OpLabel
+ %300 = OpCopyObject %6 %7
+ OpStore %11 %300
+ OpBranch %23
+ %23 = OpLabel
+ %200 = OpPhi %6 %201 %21 %300 %22
+ OpStore %11 %200
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationPropagateInstructionDownTest, TestCreatedFacts) {
+ std::string shader = R"(
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %10 = OpTypePointer Private %6
+ %11 = OpVariable %10 Private
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %20 = OpCopyObject %6 %7
+ %24 = OpCopyObject %6 %7 ; Irrelevant id
+ %25 = OpCopyObject %10 %11 ; Pointee is irrelevant
+ OpSelectionMerge %23 None
+ OpBranchConditional %13 %21 %22
+ %21 = OpLabel
+ OpStore %25 %20
+ OpBranch %23
+ %22 = OpLabel ; Dead block
+ OpStore %25 %20
+ OpBranch %23
+ %23 = OpLabel
+ OpStore %25 %20
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ transformation_context.GetFactManager()->AddFactBlockIsDead(22);
+ transformation_context.GetFactManager()->AddFactIdIsIrrelevant(24);
+ transformation_context.GetFactManager()->AddFactValueOfPointeeIsIrrelevant(
+ 25);
+
+ {
+ // Propagate pointer with PointeeIsIrrelevant fact.
+ TransformationPropagateInstructionDown transformation(
+ 5, 200, {{{21, 201}, {22, 202}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ ASSERT_FALSE(transformation_context.GetFactManager()->IdIsIrrelevant(201));
+ ASSERT_FALSE(transformation_context.GetFactManager()->IdIsIrrelevant(202));
+ ASSERT_FALSE(transformation_context.GetFactManager()->IdIsIrrelevant(200));
+
+ ASSERT_TRUE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(201));
+ ASSERT_TRUE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(202));
+ ASSERT_TRUE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(200));
+
+ ASSERT_TRUE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(201, {}), MakeDataDescriptor(202, {})));
+ ASSERT_TRUE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(201, {}), MakeDataDescriptor(200, {})));
+ }
+ {
+ // Propagate an irrelevant id.
+ TransformationPropagateInstructionDown transformation(
+ 5, 203, {{{21, 204}, {22, 205}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ ASSERT_TRUE(transformation_context.GetFactManager()->IdIsIrrelevant(203));
+ ASSERT_TRUE(transformation_context.GetFactManager()->IdIsIrrelevant(204));
+ ASSERT_TRUE(transformation_context.GetFactManager()->IdIsIrrelevant(205));
+
+ ASSERT_FALSE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(203));
+ ASSERT_FALSE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(204));
+ ASSERT_FALSE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(205));
+
+ ASSERT_FALSE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(204, {}), MakeDataDescriptor(205, {})));
+ ASSERT_FALSE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(204, {}), MakeDataDescriptor(203, {})));
+ }
+ {
+ // Propagate a regular id.
+ TransformationPropagateInstructionDown transformation(
+ 5, 206, {{{21, 207}, {22, 208}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ ASSERT_FALSE(transformation_context.GetFactManager()->IdIsIrrelevant(206));
+ ASSERT_FALSE(transformation_context.GetFactManager()->IdIsIrrelevant(207));
+ ASSERT_TRUE(transformation_context.GetFactManager()->IdIsIrrelevant(208));
+
+ ASSERT_FALSE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(206));
+ ASSERT_FALSE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(207));
+ ASSERT_FALSE(
+ transformation_context.GetFactManager()->PointeeValueIsIrrelevant(208));
+
+ ASSERT_TRUE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(206, {}), MakeDataDescriptor(207, {})));
+ ASSERT_FALSE(transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(206, {}), MakeDataDescriptor(208, {})));
+ }
+
+ std::string after_transformation = R"(
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %10 = OpTypePointer Private %6
+ %11 = OpVariable %10 Private
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpSelectionMerge %23 None
+ OpBranchConditional %13 %21 %22
+ %21 = OpLabel
+ %207 = OpCopyObject %6 %7
+ %204 = OpCopyObject %6 %7 ; Irrelevant id
+ %201 = OpCopyObject %10 %11 ; Pointee is irrelevant
+ OpStore %201 %207
+ OpBranch %23
+ %22 = OpLabel ; Dead block
+ %208 = OpCopyObject %6 %7
+ %205 = OpCopyObject %6 %7 ; Irrelevant id
+ %202 = OpCopyObject %10 %11 ; Pointee is irrelevant
+ OpStore %202 %208
+ OpBranch %23
+ %23 = OpLabel
+ %206 = OpPhi %6 %207 %21 %208 %22
+ %203 = OpPhi %6 %204 %21 %205 %22 ; Irrelevant id
+ %200 = OpPhi %10 %201 %21 %202 %22 ; Pointee is irrelevant
+ OpStore %200 %206
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationPropagateInstructionDownTest, TestLoops1) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %26 %25 None
+ OpBranch %21
+
+ %21 = OpLabel
+ %22 = OpCopyObject %6 %7
+ %31 = OpCopyObject %6 %7
+ OpSelectionMerge %35 None
+ OpBranchConditional %13 %23 %24
+
+ %23 = OpLabel
+ %27 = OpCopyObject %6 %22
+ %32 = OpCopyObject %6 %31
+ OpBranch %26
+ %24 = OpLabel
+ %28 = OpCopyObject %6 %22
+ %33 = OpCopyObject %6 %31
+ OpBranchConditional %13 %26 %25
+
+ %35 = OpLabel
+ OpBranch %25
+
+ %25 = OpLabel
+ %29 = OpCopyObject %6 %22
+ %34 = OpCopyObject %6 %31
+ OpBranch %20
+ %26 = OpLabel
+ %30 = OpCopyObject %6 %22
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ {
+ TransformationPropagateInstructionDown transformation(
+ 21, 200, {{{23, 201}, {24, 202}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+
+ // Can't replace usage of %22 in %26.
+ ASSERT_FALSE(
+ TransformationPropagateInstructionDown(21, 200, {{{23, 201}, {24, 202}}})
+ .IsApplicable(context.get(), transformation_context));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ OpLoopMerge %26 %25 None
+ OpBranch %21
+
+ %21 = OpLabel
+ %22 = OpCopyObject %6 %7
+ OpSelectionMerge %35 None
+ OpBranchConditional %13 %23 %24
+ %23 = OpLabel
+ %201 = OpCopyObject %6 %7
+ %27 = OpCopyObject %6 %22
+ %32 = OpCopyObject %6 %201
+ OpBranch %26
+ %24 = OpLabel
+ %202 = OpCopyObject %6 %7
+ %28 = OpCopyObject %6 %22
+ %33 = OpCopyObject %6 %202
+ OpBranchConditional %13 %26 %25
+
+ %35 = OpLabel
+ OpBranch %25
+
+ %25 = OpLabel
+ %29 = OpCopyObject %6 %22
+ %34 = OpCopyObject %6 %202
+ OpBranch %20
+ %26 = OpLabel
+ %30 = OpCopyObject %6 %22
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationPropagateInstructionDownTest, TestLoops2) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ %23 = OpPhi %6 %7 %5 %24 %21
+ OpLoopMerge %22 %21 None
+ OpBranch %21
+
+ %21 = OpLabel
+ %24 = OpCopyObject %6 %23
+ %25 = OpCopyObject %6 %7
+ OpBranchConditional %13 %22 %20
+
+ %22 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ {
+ // Can propagate %25 from %21 into %20.
+ TransformationPropagateInstructionDown transformation(
+ 21, 200, {{{20, 201}, {22, 202}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+ {
+ // Can propagate %201 from %20 into %21.
+ TransformationPropagateInstructionDown transformation(20, 200,
+ {{{21, 203}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+
+ // Can't propagate %24 from %21 into %20.
+ ASSERT_FALSE(
+ TransformationPropagateInstructionDown(21, 200, {{{20, 204}, {22, 205}}})
+ .IsApplicable(context.get(), transformation_context));
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ %23 = OpPhi %6 %7 %5 %24 %21
+ OpLoopMerge %22 %21 None
+ OpBranch %21
+
+ %21 = OpLabel
+ %203 = OpCopyObject %6 %7
+ %24 = OpCopyObject %6 %23
+ OpBranchConditional %13 %22 %20
+
+ %22 = OpLabel
+ %200 = OpPhi %6 %203 %21
+ %202 = OpCopyObject %6 %7
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationPropagateInstructionDownTest, TestLoops3) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ %27 = OpPhi %6 %7 %5 %26 %20
+ %25 = OpCopyObject %6 %7
+ %26 = OpCopyObject %6 %7
+ OpLoopMerge %22 %20 None
+ OpBranchConditional %13 %20 %22
+
+ %22 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(
+ MakeUnique<FactManager>(context.get()), validator_options);
+
+ {
+ // Propagate %25 into %20 and %22. Not that we are skipping %26 since not
+ // all of its users are in different blocks (%27).h
+ TransformationPropagateInstructionDown transformation(
+ 20, 200, {{{20, 201}, {22, 202}}});
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ ApplyAndCheckFreshIds(transformation, context.get(),
+ &transformation_context);
+ ASSERT_TRUE(IsValid(env, context.get()));
+ }
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main"
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %7 = OpConstant %6 1
+ %12 = OpTypeBool
+ %13 = OpConstantTrue %12
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %20
+
+ %20 = OpLabel
+ %27 = OpPhi %6 %7 %5 %26 %20
+ %201 = OpCopyObject %6 %7
+ %26 = OpCopyObject %6 %7
+ OpLoopMerge %22 %20 None
+ OpBranchConditional %13 %20 %22
+
+ %22 = OpLabel
+ %202 = OpCopyObject %6 %7
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
