spirv-fuzz: Create synonym via OpPhi and existing synonyms (#3701)
A transformation that adds new OpPhi instructions to blocks with >=1
predecessors, so that its value depends on previously-defined ids of
the right type, which are all synonymous. This instruction is also
recorded as synonymous to the others.
The related fuzzer pass still needs to be implemented.
Fixes #3592 .
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index ab7e985..905d535 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -59,6 +59,7 @@
fuzzer_pass_add_local_variables.h
fuzzer_pass_add_loop_preheaders.h
fuzzer_pass_add_no_contraction_decorations.h
+ fuzzer_pass_add_opphi_synonyms.h
fuzzer_pass_add_parameters.h
fuzzer_pass_add_relaxed_decorations.h
fuzzer_pass_add_stores.h
@@ -124,6 +125,7 @@
transformation_add_local_variable.h
transformation_add_loop_preheader.h
transformation_add_no_contraction_decoration.h
+ transformation_add_opphi_synonym.h
transformation_add_parameter.h
transformation_add_relaxed_decoration.h
transformation_add_spec_constant_op.h
@@ -210,6 +212,7 @@
fuzzer_pass_add_local_variables.cpp
fuzzer_pass_add_loop_preheaders.cpp
fuzzer_pass_add_no_contraction_decorations.cpp
+ fuzzer_pass_add_opphi_synonyms.cpp
fuzzer_pass_add_parameters.cpp
fuzzer_pass_add_relaxed_decorations.cpp
fuzzer_pass_add_stores.cpp
@@ -274,6 +277,7 @@
transformation_add_local_variable.cpp
transformation_add_loop_preheader.cpp
transformation_add_no_contraction_decoration.cpp
+ transformation_add_opphi_synonym.cpp
transformation_add_parameter.cpp
transformation_add_relaxed_decoration.cpp
transformation_add_spec_constant_op.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index fea031c..e35fc8b 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -35,6 +35,7 @@
#include "source/fuzz/fuzzer_pass_add_local_variables.h"
#include "source/fuzz/fuzzer_pass_add_loop_preheaders.h"
#include "source/fuzz/fuzzer_pass_add_no_contraction_decorations.h"
+#include "source/fuzz/fuzzer_pass_add_opphi_synonyms.h"
#include "source/fuzz/fuzzer_pass_add_parameters.h"
#include "source/fuzz/fuzzer_pass_add_relaxed_decorations.h"
#include "source/fuzz/fuzzer_pass_add_stores.h"
@@ -256,6 +257,9 @@
MaybeAddPass<FuzzerPassAddLoopPreheaders>(
&passes, ir_context.get(), &transformation_context, &fuzzer_context,
transformation_sequence_out);
+ MaybeAddPass<FuzzerPassAddOpPhiSynonyms>(
+ &passes, ir_context.get(), &transformation_context, &fuzzer_context,
+ transformation_sequence_out);
MaybeAddPass<FuzzerPassAddParameters>(
&passes, ir_context.get(), &transformation_context, &fuzzer_context,
transformation_sequence_out);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index ee8db86..6f76bbb 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -43,6 +43,7 @@
const std::pair<uint32_t, uint32_t> kChanceOfAddingMatrixType = {20, 70};
const std::pair<uint32_t, uint32_t> kChanceOfAddingNoContractionDecoration = {
5, 70};
+const std::pair<uint32_t, uint32_t> kChanceOfAddingOpPhiSynonym = {5, 70};
const std::pair<uint32_t, uint32_t> kChanceOfAddingParameters = {5, 70};
const std::pair<uint32_t, uint32_t> kChanceOfAddingRelaxedDecoration = {20, 90};
const std::pair<uint32_t, uint32_t> kChanceOfAddingStore = {5, 50};
@@ -182,6 +183,8 @@
ChooseBetweenMinAndMax(kChanceOfAddingMatrixType);
chance_of_adding_no_contraction_decoration_ =
ChooseBetweenMinAndMax(kChanceOfAddingNoContractionDecoration);
+ chance_of_adding_opphi_synonym_ =
+ ChooseBetweenMinAndMax(kChanceOfAddingOpPhiSynonym);
chance_of_adding_parameters =
ChooseBetweenMinAndMax(kChanceOfAddingParameters);
chance_of_adding_relaxed_decoration_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 9f85b13..bc98bc0 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -148,6 +148,9 @@
uint32_t GetChanceOfAddingNoContractionDecoration() {
return chance_of_adding_no_contraction_decoration_;
}
+ uint32_t GetChanceOfAddingOpPhiSynonym() {
+ return chance_of_adding_opphi_synonym_;
+ }
uint32_t GetChanceOfAddingParameters() { return chance_of_adding_parameters; }
uint32_t GetChanceOfAddingRelaxedDecoration() {
return chance_of_adding_relaxed_decoration_;
@@ -367,6 +370,7 @@
uint32_t chance_of_adding_loop_preheader_;
uint32_t chance_of_adding_matrix_type_;
uint32_t chance_of_adding_no_contraction_decoration_;
+ uint32_t chance_of_adding_opphi_synonym_;
uint32_t chance_of_adding_parameters;
uint32_t chance_of_adding_relaxed_decoration_;
uint32_t chance_of_adding_store_;
diff --git a/source/fuzz/fuzzer_pass_add_opphi_synonyms.cpp b/source/fuzz/fuzzer_pass_add_opphi_synonyms.cpp
new file mode 100644
index 0000000..97adfb2
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_opphi_synonyms.cpp
@@ -0,0 +1,297 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/fuzzer_pass_add_opphi_synonyms.h"
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/transformation_add_opphi_synonym.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassAddOpPhiSynonyms::FuzzerPassAddOpPhiSynonyms(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassAddOpPhiSynonyms::~FuzzerPassAddOpPhiSynonyms() = default;
+
+void FuzzerPassAddOpPhiSynonyms::Apply() {
+ // Get a list of synonymous ids with the same type that can be used in the
+ // same OpPhi instruction.
+ auto equivalence_classes = GetIdEquivalenceClasses();
+
+ // Make a list of references, to avoid copying sets unnecessarily.
+ std::vector<std::set<uint32_t>*> equivalence_class_pointers;
+ for (auto& set : equivalence_classes) {
+ equivalence_class_pointers.push_back(&set);
+ }
+
+ // Keep a list of transformations to apply at the end.
+ std::vector<TransformationAddOpPhiSynonym> transformations_to_apply;
+
+ for (auto& function : *GetIRContext()->module()) {
+ for (auto& block : function) {
+ // Randomly decide whether to consider this block.
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfAddingOpPhiSynonym())) {
+ continue;
+ }
+
+ // The block must have at least one predecessor.
+ size_t num_preds = GetIRContext()->cfg()->preds(block.id()).size();
+ if (num_preds == 0) {
+ continue;
+ }
+
+ std::set<uint32_t>* chosen_equivalence_class = nullptr;
+
+ if (num_preds > 1) {
+ // If the block has more than one predecessor, prioritise sets with at
+ // least 2 ids available at some predecessor.
+ chosen_equivalence_class = MaybeFindSuitableEquivalenceClassRandomly(
+ equivalence_class_pointers, block.id(), 2);
+ }
+
+ // If a set was not already chosen, choose one with at least one available
+ // id.
+ if (!chosen_equivalence_class) {
+ chosen_equivalence_class = MaybeFindSuitableEquivalenceClassRandomly(
+ equivalence_class_pointers, block.id(), 1);
+ }
+
+ // If no suitable set was found, we cannot apply the transformation to
+ // this block.
+ if (!chosen_equivalence_class) {
+ continue;
+ }
+
+ // Initialise the map from predecessor labels to ids.
+ std::map<uint32_t, uint32_t> preds_to_ids;
+
+ // Keep track of the ids used and of the id of a predecessor with at least
+ // two ids to choose from. This is to ensure that, if possible, at least
+ // two distinct ids will be used.
+ std::set<uint32_t> ids_chosen;
+ uint32_t pred_with_alternatives = 0;
+
+ // Choose an id for each predecessor.
+ for (uint32_t pred_id : GetIRContext()->cfg()->preds(block.id())) {
+ auto suitable_ids = GetSuitableIds(*chosen_equivalence_class, pred_id);
+ assert(!suitable_ids.empty() &&
+ "We must be able to find at least one suitable id because the "
+ "equivalence class was chosen among suitable ones.");
+
+ // If this predecessor has more than one id to choose from and it is the
+ // first one of this kind that we found, remember its id.
+ if (suitable_ids.size() > 1 && !pred_with_alternatives) {
+ pred_with_alternatives = pred_id;
+ }
+
+ uint32_t chosen_id =
+ suitable_ids[GetFuzzerContext()->RandomIndex(suitable_ids)];
+
+ // Add this id to the set of ids chosen.
+ ids_chosen.emplace(chosen_id);
+
+ // Add the pair (predecessor, chosen id) to the map.
+ preds_to_ids[pred_id] = chosen_id;
+ }
+
+ // If:
+ // - the block has more than one predecessor
+ // - at least one predecessor has more than one alternative
+ // - the same id has been chosen by all the predecessors
+ // then choose another one for the predecessor with more than one
+ // alternative.
+ if (num_preds > 1 && pred_with_alternatives != 0 &&
+ ids_chosen.size() == 1) {
+ auto suitable_ids =
+ GetSuitableIds(*chosen_equivalence_class, pred_with_alternatives);
+ uint32_t chosen_id =
+ GetFuzzerContext()->RemoveAtRandomIndex(&suitable_ids);
+ if (chosen_id == preds_to_ids[pred_with_alternatives]) {
+ chosen_id = GetFuzzerContext()->RemoveAtRandomIndex(&suitable_ids);
+ }
+
+ preds_to_ids[pred_with_alternatives] = chosen_id;
+ }
+
+ // Add the transformation to the list of transformations to apply.
+ transformations_to_apply.emplace_back(block.id(), preds_to_ids,
+ GetFuzzerContext()->GetFreshId());
+ }
+ }
+
+ // Apply the transformations.
+ for (const auto& transformation : transformations_to_apply) {
+ ApplyTransformation(transformation);
+ }
+}
+
+std::vector<std::set<uint32_t>>
+FuzzerPassAddOpPhiSynonyms::GetIdEquivalenceClasses() {
+ std::vector<std::set<uint32_t>> id_equivalence_classes;
+
+ // Keep track of all the ids that have already be assigned to a class.
+ std::set<uint32_t> already_in_a_class;
+
+ for (const auto& pair : GetIRContext()->get_def_use_mgr()->id_to_defs()) {
+ // Exclude ids that have already been assigned to a class.
+ if (already_in_a_class.count(pair.first)) {
+ continue;
+ }
+
+ // Exclude irrelevant ids.
+ if (GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
+ pair.first)) {
+ continue;
+ }
+
+ // Exclude ids having a type that is not allowed by the transformation.
+ if (!TransformationAddOpPhiSynonym::CheckTypeIsAllowed(
+ GetIRContext(), pair.second->type_id())) {
+ continue;
+ }
+
+ // We need a new equivalence class for this id.
+ std::set<uint32_t> new_equivalence_class;
+
+ // Add this id to the class.
+ new_equivalence_class.emplace(pair.first);
+ already_in_a_class.emplace(pair.first);
+
+ // Add all the synonyms with the same type to this class.
+ for (auto synonym :
+ GetTransformationContext()->GetFactManager()->GetSynonymsForId(
+ pair.first)) {
+ // The synonym must be a plain id - it cannot be an indexed access into a
+ // composite.
+ if (synonym->index_size() > 0) {
+ continue;
+ }
+
+ // The synonym must not be irrelevant.
+ if (GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
+ synonym->object())) {
+ continue;
+ }
+
+ auto synonym_def =
+ GetIRContext()->get_def_use_mgr()->GetDef(synonym->object());
+ // The synonym must exist and have the same type as the id we are
+ // considering.
+ if (!synonym_def || synonym_def->type_id() != pair.second->type_id()) {
+ continue;
+ }
+
+ // We can add this synonym to the new equivalence class.
+ new_equivalence_class.emplace(synonym->object());
+ already_in_a_class.emplace(synonym->object());
+ }
+
+ // Add the new equivalence class to the list of equivalence classes.
+ id_equivalence_classes.emplace_back(std::move(new_equivalence_class));
+ }
+
+ return id_equivalence_classes;
+}
+
+bool FuzzerPassAddOpPhiSynonyms::EquivalenceClassIsSuitableForBlock(
+ const std::set<uint32_t>& equivalence_class, uint32_t block_id,
+ uint32_t distinct_ids_required) {
+ bool at_least_one_id_for_each_pred = true;
+
+ // Keep a set of the suitable ids found.
+ std::set<uint32_t> suitable_ids_found;
+
+ // Loop through all the predecessors of the block.
+ for (auto pred_id : GetIRContext()->cfg()->preds(block_id)) {
+ // Find the last instruction in the predecessor block.
+ auto last_instruction =
+ GetIRContext()->get_instr_block(pred_id)->terminator();
+
+ // Initially assume that there is not a suitable id for this predecessor.
+ bool at_least_one_suitable_id_found = false;
+ for (uint32_t id : equivalence_class) {
+ if (fuzzerutil::IdIsAvailableBeforeInstruction(GetIRContext(),
+ last_instruction, id)) {
+ // We have found a suitable id.
+ at_least_one_suitable_id_found = true;
+ suitable_ids_found.emplace(id);
+
+ // If we have already found enough distinct suitable ids, we don't need
+ // to check the remaining ones for this predecessor.
+ if (suitable_ids_found.size() >= distinct_ids_required) {
+ break;
+ }
+ }
+ }
+ // If no suitable id was found for this predecessor, this equivalence class
+ // is not suitable and we don't need to check the other predecessors.
+ if (!at_least_one_suitable_id_found) {
+ at_least_one_id_for_each_pred = false;
+ break;
+ }
+ }
+
+ // The equivalence class is suitable if at least one suitable id was found for
+ // each predecessor and we have found at least |distinct_ids_required|
+ // distinct suitable ids in general.
+ return at_least_one_id_for_each_pred &&
+ suitable_ids_found.size() >= distinct_ids_required;
+}
+
+std::vector<uint32_t> FuzzerPassAddOpPhiSynonyms::GetSuitableIds(
+ const std::set<uint32_t>& ids, uint32_t pred_id) {
+ // Initialise an empty vector of suitable ids.
+ std::vector<uint32_t> suitable_ids;
+
+ // Get the predecessor block.
+ auto predecessor = fuzzerutil::MaybeFindBlock(GetIRContext(), pred_id);
+
+ // Loop through the ids to find the suitable ones.
+ for (uint32_t id : ids) {
+ if (fuzzerutil::IdIsAvailableBeforeInstruction(
+ GetIRContext(), predecessor->terminator(), id)) {
+ suitable_ids.push_back(id);
+ }
+ }
+
+ return suitable_ids;
+}
+
+std::set<uint32_t>*
+FuzzerPassAddOpPhiSynonyms::MaybeFindSuitableEquivalenceClassRandomly(
+ const std::vector<std::set<uint32_t>*>& candidates, uint32_t block_id,
+ uint32_t distinct_ids_required) {
+ auto remaining_candidates = candidates;
+ while (!remaining_candidates.empty()) {
+ // Choose one set randomly and return it if it is suitable.
+ auto chosen =
+ GetFuzzerContext()->RemoveAtRandomIndex(&remaining_candidates);
+ if (EquivalenceClassIsSuitableForBlock(*chosen, block_id,
+ distinct_ids_required)) {
+ return chosen;
+ }
+ }
+
+ // No suitable sets were found.
+ return nullptr;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_add_opphi_synonyms.h b/source/fuzz/fuzzer_pass_add_opphi_synonyms.h
new file mode 100644
index 0000000..ed61c020
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_opphi_synonyms.h
@@ -0,0 +1,73 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_FUZZ_FUZZER_PASS_ADD_OPPHI_SYNONYMS_
+#define SOURCE_FUZZ_FUZZER_PASS_ADD_OPPHI_SYNONYMS_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass to add OpPhi instructions which can take the values of ids that
+// have been marked as synonymous. This instruction will itself be marked as
+// synonymous with the others.
+class FuzzerPassAddOpPhiSynonyms : public FuzzerPass {
+ public:
+ FuzzerPassAddOpPhiSynonyms(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassAddOpPhiSynonyms() override;
+
+ void Apply() override;
+
+ // Computes the equivalence classes for the non-pointer and non-irrelevant ids
+ // in the module, where two ids are considered equivalent iff they have been
+ // declared synonymous and they have the same type.
+ std::vector<std::set<uint32_t>> GetIdEquivalenceClasses();
+
+ // Returns true iff |equivalence_class| contains at least
+ // |distinct_ids_required| ids so that all of these ids are available at the
+ // end of at least one predecessor of the block with label |block_id|.
+ // Assumes that the block has at least one predecessor.
+ bool EquivalenceClassIsSuitableForBlock(
+ const std::set<uint32_t>& equivalence_class, uint32_t block_id,
+ uint32_t distinct_ids_required);
+
+ // Returns a vector with the ids that are available to use at the end of the
+ // block with id |pred_id|, selected among the given |ids|. Assumes that
+ // |pred_id| is the label of a block and all ids in |ids| exist in the module.
+ std::vector<uint32_t> GetSuitableIds(const std::set<uint32_t>& ids,
+ uint32_t pred_id);
+
+ private:
+ // Randomly chooses one of the equivalence classes in |candidates|, so that it
+ // satisfies all of the following conditions:
+ // - For each of the predecessors of the |block_id| block, there is at least
+ // one id in the chosen equivalence class that is available at the end of
+ // it.
+ // - There are at least |distinct_ids_required| ids available at the end of
+ // some predecessor.
+ // Returns nullptr if no equivalence class in |candidates| satisfies the
+ // requirements.
+ std::set<uint32_t>* MaybeFindSuitableEquivalenceClassRandomly(
+ const std::vector<std::set<uint32_t>*>& candidates, uint32_t block_id,
+ uint32_t distinct_ids_required);
+};
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_ADD_OPPHI_SYNONYMS_
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index c20fa99..ed3ce0e 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -414,6 +414,7 @@
TransformationPropagateInstructionUp propagate_instruction_up = 67;
TransformationCompositeInsert composite_insert = 68;
TransformationInlineFunction inline_function = 69;
+ TransformationAddOpPhiSynonym add_opphi_synonym = 70;
// Add additional option using the next available number.
}
}
@@ -746,6 +747,24 @@
}
+message TransformationAddOpPhiSynonym {
+
+ // Adds an OpPhi instruction at the start of a block with n predecessors (pred_1, pred_2, ..., pred_n)
+ // and n related ids (id_1, id_2, ..., id_n) which are pairwise synonymous.
+ // The instruction will be of the form:
+ // %fresh_id = OpPhi %type %id_1 %pred_1 %id_2 %pred_2 ... %id_n %pred_n
+ // and fresh_id will be recorded as being synonymous with all the other ids.
+
+ // Label id of the block
+ uint32 block_id = 1;
+
+ // Pairs (pred_i, id_i)
+ repeated UInt32Pair pred_to_id = 2;
+
+ // Fresh id for the new instruction
+ uint32 fresh_id = 3;
+}
+
message TransformationAddParameter {
// Adds a new parameter into the function.
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index 0df47d5..3cadac9 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -33,6 +33,7 @@
#include "source/fuzz/transformation_add_local_variable.h"
#include "source/fuzz/transformation_add_loop_preheader.h"
#include "source/fuzz/transformation_add_no_contraction_decoration.h"
+#include "source/fuzz/transformation_add_opphi_synonym.h"
#include "source/fuzz/transformation_add_parameter.h"
#include "source/fuzz/transformation_add_relaxed_decoration.h"
#include "source/fuzz/transformation_add_spec_constant_op.h"
@@ -141,6 +142,9 @@
kAddNoContractionDecoration:
return MakeUnique<TransformationAddNoContractionDecoration>(
message.add_no_contraction_decoration());
+ case protobufs::Transformation::TransformationCase::kAddOpphiSynonym:
+ return MakeUnique<TransformationAddOpPhiSynonym>(
+ message.add_opphi_synonym());
case protobufs::Transformation::TransformationCase::kAddParameter:
return MakeUnique<TransformationAddParameter>(message.add_parameter());
case protobufs::Transformation::TransformationCase::kAddRelaxedDecoration:
diff --git a/source/fuzz/transformation_add_opphi_synonym.cpp b/source/fuzz/transformation_add_opphi_synonym.cpp
new file mode 100644
index 0000000..3436dd7
--- /dev/null
+++ b/source/fuzz/transformation_add_opphi_synonym.cpp
@@ -0,0 +1,200 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/transformation_add_opphi_synonym.h"
+
+#include "source/fuzz/fuzzer_util.h"
+
+namespace spvtools {
+namespace fuzz {
+TransformationAddOpPhiSynonym::TransformationAddOpPhiSynonym(
+ const protobufs::TransformationAddOpPhiSynonym& message)
+ : message_(message) {}
+
+TransformationAddOpPhiSynonym::TransformationAddOpPhiSynonym(
+ uint32_t block_id, const std::map<uint32_t, uint32_t>& preds_to_ids,
+ uint32_t fresh_id) {
+ message_.set_block_id(block_id);
+ *message_.mutable_pred_to_id() =
+ fuzzerutil::MapToRepeatedUInt32Pair(preds_to_ids);
+ message_.set_fresh_id(fresh_id);
+}
+
+bool TransformationAddOpPhiSynonym::IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const {
+ // Check that |message_.block_id| is a block label id.
+ auto block = fuzzerutil::MaybeFindBlock(ir_context, message_.block_id());
+ if (!block) {
+ return false;
+ }
+
+ // Check that |message_.fresh_id| is actually fresh.
+ if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) {
+ return false;
+ }
+
+ // Check that |message_.pred_to_id| contains a mapping for all of the block's
+ // predecessors.
+ std::vector<uint32_t> predecessors = ir_context->cfg()->preds(block->id());
+
+ // There must be at least one predecessor.
+ if (predecessors.empty()) {
+ return false;
+ }
+
+ std::map<uint32_t, uint32_t> preds_to_ids =
+ fuzzerutil::RepeatedUInt32PairToMap(message_.pred_to_id());
+
+ // There must not be repeated key values in |message_.pred_to_id|.
+ if (preds_to_ids.size() != static_cast<size_t>(message_.pred_to_id_size())) {
+ return false;
+ }
+
+ // Check that each predecessor has a corresponding mapping and all of the
+ // corresponding ids exist.
+ for (uint32_t pred : predecessors) {
+ if (preds_to_ids.count(pred) == 0) {
+ return false;
+ }
+
+ // Check that the id exists in the module.
+ if (!ir_context->get_def_use_mgr()->GetDef(preds_to_ids[pred])) {
+ return false;
+ }
+ }
+
+ // Get the first id and its type (which should be the same as all the other
+ // ones) and check that the transformation supports this type.
+ uint32_t first_id = preds_to_ids[predecessors[0]];
+ uint32_t type_id = ir_context->get_def_use_mgr()->GetDef(first_id)->type_id();
+ if (!CheckTypeIsAllowed(ir_context, type_id)) {
+ return false;
+ }
+
+ // Check that the ids corresponding to predecessors are all synonymous, have
+ // the same type and are available to use at the end of the predecessor.
+ for (uint32_t pred : predecessors) {
+ auto id = preds_to_ids[pred];
+
+ // Check that the id has the same type as the other ones.
+ if (ir_context->get_def_use_mgr()->GetDef(id)->type_id() != type_id) {
+ return false;
+ }
+
+ // Check that the id is synonymous with the others by checking that it is
+ // synonymous with the first one (or it is the same id).
+ if (id != first_id &&
+ !transformation_context.GetFactManager()->IsSynonymous(
+ MakeDataDescriptor(id, {}), MakeDataDescriptor(first_id, {}))) {
+ return false;
+ }
+
+ // Check that the id is available at the end of the corresponding
+ // predecessor block.
+
+ auto pred_block = ir_context->get_instr_block(pred);
+
+ // We should always be able to find the predecessor block, since it is in
+ // the predecessors list of |block|.
+ assert(pred_block && "Could not find one of the predecessor blocks.");
+
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3722): This
+ // function always returns false if the block is unreachable, so it may
+ // need to be refactored.
+ if (!fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, pred_block->terminator(), id)) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+void TransformationAddOpPhiSynonym::Apply(
+ opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const {
+ // Get the type id from one of the ids.
+ uint32_t first_id = message_.pred_to_id(0).second();
+ uint32_t type_id = ir_context->get_def_use_mgr()->GetDef(first_id)->type_id();
+
+ // Define the operand list.
+ opt::Instruction::OperandList operand_list;
+
+ // For each predecessor, add the corresponding operands.
+ for (auto& pair : message_.pred_to_id()) {
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_ID, {pair.second()}});
+ operand_list.emplace_back(
+ opt::Operand{SPV_OPERAND_TYPE_ID, {pair.first()}});
+ }
+
+ // Add a new OpPhi instructions at the beginning of the block.
+ ir_context->get_instr_block(message_.block_id())
+ ->begin()
+ .InsertBefore(MakeUnique<opt::Instruction>(ir_context, SpvOpPhi, type_id,
+ message_.fresh_id(),
+ std::move(operand_list)));
+
+ // Update the module id bound.
+ fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
+
+ // Invalidate all analyses, since we added an instruction to the module.
+ ir_context->InvalidateAnalysesExceptFor(
+ opt::IRContext::Analysis::kAnalysisNone);
+
+ // Record the fact that the new id is synonym with the other ones by declaring
+ // that it is a synonym of the first one.
+ transformation_context->GetFactManager()->AddFactDataSynonym(
+ MakeDataDescriptor(message_.fresh_id(), {}),
+ MakeDataDescriptor(first_id, {}), ir_context);
+}
+
+protobufs::Transformation TransformationAddOpPhiSynonym::ToMessage() const {
+ protobufs::Transformation result;
+ *result.mutable_add_opphi_synonym() = message_;
+ return result;
+}
+
+bool TransformationAddOpPhiSynonym::CheckTypeIsAllowed(
+ opt::IRContext* ir_context, uint32_t type_id) {
+ auto type = ir_context->get_type_mgr()->GetType(type_id);
+ if (!type) {
+ return false;
+ }
+
+ // We allow the following types: Bool, Integer, Float, Vector, Matrix, Array,
+ // Struct.
+ if (type->AsBool() || type->AsInteger() || type->AsFloat() ||
+ type->AsVector() || type->AsMatrix() || type->AsArray() ||
+ type->AsStruct()) {
+ return true;
+ }
+
+ // We allow pointer types if the VariablePointers capability is enabled and
+ // the pointer has the correct storage class (Workgroup or StorageBuffer).
+ if (type->AsPointer()) {
+ auto storage_class = type->AsPointer()->storage_class();
+ return ir_context->get_feature_mgr()->HasCapability(
+ SpvCapabilityVariablePointers) &&
+ (storage_class == SpvStorageClassWorkgroup ||
+ storage_class == SpvStorageClassStorageBuffer);
+ }
+
+ // We do not allow other types.
+ return false;
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/transformation_add_opphi_synonym.h b/source/fuzz/transformation_add_opphi_synonym.h
new file mode 100644
index 0000000..dc0e6d9
--- /dev/null
+++ b/source/fuzz/transformation_add_opphi_synonym.h
@@ -0,0 +1,72 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_FUZZ_TRANSFORMATION_ADD_OPPHI_SYNONYM_H_
+#define SOURCE_FUZZ_TRANSFORMATION_ADD_OPPHI_SYNONYM_H_
+
+#include "source/fuzz/transformation.h"
+
+namespace spvtools {
+namespace fuzz {
+class TransformationAddOpPhiSynonym : public Transformation {
+ public:
+ explicit TransformationAddOpPhiSynonym(
+ const protobufs::TransformationAddOpPhiSynonym& message);
+
+ TransformationAddOpPhiSynonym(
+ uint32_t block_id, const std::map<uint32_t, uint32_t>& preds_to_ids,
+ uint32_t fresh_id);
+
+ // - |message_.block_id| is the label of a block with at least one
+ // predecessor.
+ // - |message_.pred_to_id| contains a mapping from each of the predecessors of
+ // the block to an id that is available at the end of the predecessor.
+ // - All the ids corresponding to a predecessor in |message_.pred_to_id|:
+ // - have been recorded as synonymous and all have the same type.
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3726): if a
+ // predecessor is a dead block, any id of the right type could be used,
+ // even if it is not synonym with the others.
+ // - have one of the following types: Bool, Integer, Float, Vector, Matrix,
+ // Array, Struct. Pointer types are also allowed if the VariablePointers
+ // capability is enabled and the storage class is Workgroup or
+ // StorageBuffer.
+ // - |message_.fresh_id| is a fresh id.
+ bool IsApplicable(
+ opt::IRContext* ir_context,
+ const TransformationContext& transformation_context) const override;
+
+ // Given a block with n predecessors, with n >= 1, and n corresponding
+ // synonymous ids of the same type, each available to use at the end of the
+ // corresponding predecessor, adds an OpPhi instruction at the beginning of
+ // the block of the form:
+ // %fresh_id = OpPhi %type %id_1 %pred_1 %id_2 %pred_2 ... %id_n %pred_n
+ // This instruction is then marked as synonymous with the ids.
+ void Apply(opt::IRContext* ir_context,
+ TransformationContext* transformation_context) const override;
+
+ // Returns true if |type_id| is the id of a type in the module, which is one
+ // of the following: Bool, Integer, Float, Vector, Matrix, Array, Struct.
+ // Pointer types are also allowed if the VariablePointers capability is
+ // enabled and the storage class is Workgroup or StorageBuffer.
+ static bool CheckTypeIsAllowed(opt::IRContext* ir_context, uint32_t type_id);
+
+ protobufs::Transformation ToMessage() const override;
+
+ private:
+ protobufs::TransformationAddOpPhiSynonym message_;
+};
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_TRANSFORMATION_ADD_OPPHI_SYNONYM_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 7204f69..1322dad 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -21,6 +21,7 @@
equivalence_relation_test.cpp
fact_manager_test.cpp
fuzz_test_util.cpp
+ fuzzer_pass_add_opphi_synonyms_test.cpp
fuzzer_pass_construct_composites_test.cpp
fuzzer_pass_donate_modules_test.cpp
fuzzer_pass_outline_functions_test.cpp
@@ -42,6 +43,7 @@
transformation_add_local_variable_test.cpp
transformation_add_loop_preheader_test.cpp
transformation_add_no_contraction_decoration_test.cpp
+ transformation_add_opphi_synonym_test.cpp
transformation_add_parameter_test.cpp
transformation_add_relaxed_decoration_test.cpp
transformation_add_synonym_test.cpp
diff --git a/test/fuzz/fuzzer_pass_add_opphi_synonyms_test.cpp b/test/fuzz/fuzzer_pass_add_opphi_synonyms_test.cpp
new file mode 100644
index 0000000..9341b56
--- /dev/null
+++ b/test/fuzz/fuzzer_pass_add_opphi_synonyms_test.cpp
@@ -0,0 +1,170 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/fuzzer_pass_add_opphi_synonyms.h"
+#include "source/fuzz/pseudo_random_generator.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+protobufs::Fact MakeSynonymFact(uint32_t first, uint32_t second) {
+ protobufs::FactDataSynonym data_synonym_fact;
+ *data_synonym_fact.mutable_data1() = MakeDataDescriptor(first, {});
+ *data_synonym_fact.mutable_data2() = MakeDataDescriptor(second, {});
+ protobufs::Fact result;
+ *result.mutable_data_synonym_fact() = data_synonym_fact;
+ return result;
+}
+
+// Adds synonym facts to the fact manager.
+void SetUpIdSynonyms(FactManager* fact_manager, opt::IRContext* context) {
+ // Synonyms {9, 11, 15, 16, 21, 22}
+ fact_manager->AddFact(MakeSynonymFact(11, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(15, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(16, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(21, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(22, 9), context);
+
+ // Synonyms {10, 23}
+ fact_manager->AddFact(MakeSynonymFact(10, 23), context);
+
+ // Synonyms {14, 27}
+ fact_manager->AddFact(MakeSynonymFact(14, 27), context);
+
+ // Synonyms {24, 26, 30}
+ fact_manager->AddFact(MakeSynonymFact(26, 24), context);
+ fact_manager->AddFact(MakeSynonymFact(30, 24), context);
+}
+
+// Returns true if the given lists have the same elements, regardless of their
+// order.
+template <typename T>
+bool ListsHaveTheSameElements(const std::vector<T>& list1,
+ const std::vector<T>& list2) {
+ auto sorted1 = list1;
+ std::sort(sorted1.begin(), sorted1.end());
+
+ auto sorted2 = list2;
+ std::sort(sorted2.begin(), sorted2.end());
+
+ return sorted1 == sorted2;
+}
+
+std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpTypeInt 32 1
+ %8 = OpTypeInt 32 0
+ %9 = OpConstant %7 1
+ %10 = OpConstant %7 2
+ %11 = OpConstant %8 1
+ %12 = OpTypePointer Function %7
+ %2 = OpFunction %3 None %4
+ %13 = OpLabel
+ %14 = OpVariable %12 Function
+ %15 = OpCopyObject %7 %9
+ %16 = OpCopyObject %8 %11
+ OpBranch %17
+ %17 = OpLabel
+ OpSelectionMerge %18 None
+ OpBranchConditional %6 %19 %20
+ %19 = OpLabel
+ %21 = OpCopyObject %7 %15
+ %22 = OpCopyObject %8 %16
+ %23 = OpCopyObject %7 %10
+ %24 = OpIAdd %7 %9 %10
+ OpBranch %18
+ %20 = OpLabel
+ OpBranch %18
+ %18 = OpLabel
+ %26 = OpIAdd %7 %15 %10
+ %27 = OpCopyObject %12 %14
+ OpSelectionMerge %28 None
+ OpBranchConditional %6 %29 %28
+ %29 = OpLabel
+ %30 = OpCopyObject %7 %26
+ OpBranch %28
+ %28 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+TEST(FuzzerPassAddOpPhiSynonymsTest, HelperFunctions) {
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ PseudoRandomGenerator prng(0);
+ FuzzerContext fuzzer_context(&prng, 100);
+ protobufs::TransformationSequence transformation_sequence;
+
+ FuzzerPassAddOpPhiSynonyms fuzzer_pass(context.get(), &transformation_context,
+ &fuzzer_context,
+ &transformation_sequence);
+
+ SetUpIdSynonyms(&fact_manager, context.get());
+
+ std::vector<std::set<uint32_t>> expected_equivalence_classes = {
+ {9, 15, 21}, {11, 16, 22}, {10, 23}, {6}, {24, 26, 30}};
+
+ ASSERT_TRUE(ListsHaveTheSameElements<std::set<uint32_t>>(
+ fuzzer_pass.GetIdEquivalenceClasses(), expected_equivalence_classes));
+
+ // The set {24, 26, 30} is not suitable for 18 (none if the ids is available
+ // for predecessor 20).
+ ASSERT_FALSE(
+ fuzzer_pass.EquivalenceClassIsSuitableForBlock({24, 26, 30}, 18, 1));
+
+ // The set {6} is not suitable for 18 if we require at least 2 distinct
+ // available ids.
+ ASSERT_FALSE(fuzzer_pass.EquivalenceClassIsSuitableForBlock({6}, 18, 2));
+
+ // Only id 26 from the set {24, 26, 30} is available to use for the
+ // transformation at block 29, so the set is not suitable if we want at least
+ // 2 available ids.
+ ASSERT_FALSE(
+ fuzzer_pass.EquivalenceClassIsSuitableForBlock({24, 26, 30}, 29, 2));
+
+ ASSERT_TRUE(
+ fuzzer_pass.EquivalenceClassIsSuitableForBlock({24, 26, 30}, 29, 1));
+
+ // %21 is not available at the end of block 20.
+ ASSERT_TRUE(ListsHaveTheSameElements<uint32_t>(
+ fuzzer_pass.GetSuitableIds({9, 15, 21}, 20), {9, 15}));
+
+ // %24 and %30 are not available at the end of block 18.
+ ASSERT_TRUE(ListsHaveTheSameElements<uint32_t>(
+ fuzzer_pass.GetSuitableIds({24, 26, 30}, 18), {26}));
+}
+
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
diff --git a/test/fuzz/transformation_add_opphi_synonym_test.cpp b/test/fuzz/transformation_add_opphi_synonym_test.cpp
new file mode 100644
index 0000000..2dad010
--- /dev/null
+++ b/test/fuzz/transformation_add_opphi_synonym_test.cpp
@@ -0,0 +1,423 @@
+// Copyright (c) 2020 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/fuzz/transformation_add_opphi_synonym.h"
+
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+protobufs::Fact MakeSynonymFact(uint32_t first, uint32_t second) {
+ protobufs::FactDataSynonym data_synonym_fact;
+ *data_synonym_fact.mutable_data1() = MakeDataDescriptor(first, {});
+ *data_synonym_fact.mutable_data2() = MakeDataDescriptor(second, {});
+ protobufs::Fact result;
+ *result.mutable_data_synonym_fact() = data_synonym_fact;
+ return result;
+}
+
+// Adds synonym facts to the fact manager.
+void SetUpIdSynonyms(FactManager* fact_manager, opt::IRContext* context) {
+ fact_manager->AddFact(MakeSynonymFact(11, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(13, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(14, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(19, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(20, 9), context);
+ fact_manager->AddFact(MakeSynonymFact(10, 21), context);
+}
+
+TEST(TransformationAddOpPhiSynonymTest, Inapplicable) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpTypeInt 32 1
+ %8 = OpTypeInt 32 0
+ %22 = OpTypePointer Function %7
+ %9 = OpConstant %7 1
+ %10 = OpConstant %7 2
+ %11 = OpConstant %8 1
+ %2 = OpFunction %3 None %4
+ %12 = OpLabel
+ %23 = OpVariable %22 Function
+ %13 = OpCopyObject %7 %9
+ %14 = OpCopyObject %8 %11
+ OpBranch %15
+ %15 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %6 %17 %18
+ %17 = OpLabel
+ %19 = OpCopyObject %7 %13
+ %20 = OpCopyObject %8 %14
+ %21 = OpCopyObject %7 %10
+ OpBranch %16
+ %18 = OpLabel
+ %24 = OpCopyObject %22 %23
+ OpBranch %16
+ %16 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ SetUpIdSynonyms(&fact_manager, context.get());
+ fact_manager.AddFact(MakeSynonymFact(23, 24), context.get());
+
+ // %13 is not a block label.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(13, {{}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Block %12 does not have a predecessor.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(12, {{}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Not all predecessors of %16 (%17 and %18) are considered in the map.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{17, 19}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %30 does not exist in the module.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{30, 19}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %20 is not a block label.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{20, 19}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %15 is not the id of one of the predecessors of the block.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{15, 19}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %30 does not exist in the module.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{17, 30}, {18, 13}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %19 and %10 are not synonymous.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{17, 19}, {18, 10}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %19 and %14 do not have the same type.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{17, 19}, {18, 14}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %19 is not available at the end of %18.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{17, 9}, {18, 19}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %21 is not a fresh id.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{17, 9}, {18, 9}}}, 21)
+ .IsApplicable(context.get(), transformation_context));
+
+ // %23 and %24 have pointer id.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(16, {{{17, 23}, {18, 24}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+}
+
+TEST(TransformationAddOpPhiSynonymTest, Apply) {
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpTypeInt 32 1
+ %8 = OpTypeInt 32 0
+ %9 = OpConstant %7 1
+ %10 = OpConstant %7 2
+ %11 = OpConstant %8 1
+ %2 = OpFunction %3 None %4
+ %12 = OpLabel
+ %13 = OpCopyObject %7 %9
+ %14 = OpCopyObject %8 %11
+ OpBranch %15
+ %15 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %6 %17 %18
+ %17 = OpLabel
+ %19 = OpCopyObject %7 %13
+ %20 = OpCopyObject %8 %14
+ %21 = OpCopyObject %7 %10
+ OpBranch %16
+ %18 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ OpBranch %22
+ %22 = OpLabel
+ OpLoopMerge %23 %24 None
+ OpBranchConditional %6 %25 %23
+ %25 = OpLabel
+ OpSelectionMerge %26 None
+ OpBranchConditional %6 %27 %26
+ %27 = OpLabel
+ %28 = OpCopyObject %7 %13
+ OpBranch %23
+ %26 = OpLabel
+ OpSelectionMerge %29 None
+ OpBranchConditional %6 %29 %24
+ %29 = OpLabel
+ %30 = OpCopyObject %7 %13
+ OpBranch %23
+ %24 = OpLabel
+ OpBranch %22
+ %23 = OpLabel
+ OpSelectionMerge %31 None
+ OpBranchConditional %6 %31 %31
+ %31 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ SetUpIdSynonyms(&fact_manager, context.get());
+
+ // Add some further synonym facts.
+ fact_manager.AddFact(MakeSynonymFact(28, 9), context.get());
+ fact_manager.AddFact(MakeSynonymFact(30, 9), context.get());
+
+ auto transformation1 = TransformationAddOpPhiSynonym(17, {{{15, 13}}}, 100);
+ ASSERT_TRUE(
+ transformation1.IsApplicable(context.get(), transformation_context));
+ transformation1.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(fact_manager.IsSynonymous(MakeDataDescriptor(100, {}),
+ MakeDataDescriptor(9, {})));
+
+ auto transformation2 =
+ TransformationAddOpPhiSynonym(16, {{{17, 19}, {18, 13}}}, 101);
+ ASSERT_TRUE(
+ transformation2.IsApplicable(context.get(), transformation_context));
+ transformation2.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(fact_manager.IsSynonymous(MakeDataDescriptor(101, {}),
+ MakeDataDescriptor(9, {})));
+
+ auto transformation3 =
+ TransformationAddOpPhiSynonym(23, {{{22, 13}, {27, 28}, {29, 30}}}, 102);
+ ASSERT_TRUE(
+ transformation3.IsApplicable(context.get(), transformation_context));
+ transformation3.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(fact_manager.IsSynonymous(MakeDataDescriptor(102, {}),
+ MakeDataDescriptor(9, {})));
+
+ auto transformation4 = TransformationAddOpPhiSynonym(31, {{{23, 13}}}, 103);
+ ASSERT_TRUE(
+ transformation4.IsApplicable(context.get(), transformation_context));
+ transformation4.Apply(context.get(), &transformation_context);
+ ASSERT_TRUE(fact_manager.IsSynonymous(MakeDataDescriptor(103, {}),
+ MakeDataDescriptor(9, {})));
+
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ std::string after_transformations = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %2 "main"
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeBool
+ %6 = OpConstantTrue %5
+ %7 = OpTypeInt 32 1
+ %8 = OpTypeInt 32 0
+ %9 = OpConstant %7 1
+ %10 = OpConstant %7 2
+ %11 = OpConstant %8 1
+ %2 = OpFunction %3 None %4
+ %12 = OpLabel
+ %13 = OpCopyObject %7 %9
+ %14 = OpCopyObject %8 %11
+ OpBranch %15
+ %15 = OpLabel
+ OpSelectionMerge %16 None
+ OpBranchConditional %6 %17 %18
+ %17 = OpLabel
+ %100 = OpPhi %7 %13 %15
+ %19 = OpCopyObject %7 %13
+ %20 = OpCopyObject %8 %14
+ %21 = OpCopyObject %7 %10
+ OpBranch %16
+ %18 = OpLabel
+ OpBranch %16
+ %16 = OpLabel
+ %101 = OpPhi %7 %19 %17 %13 %18
+ OpBranch %22
+ %22 = OpLabel
+ OpLoopMerge %23 %24 None
+ OpBranchConditional %6 %25 %23
+ %25 = OpLabel
+ OpSelectionMerge %26 None
+ OpBranchConditional %6 %27 %26
+ %27 = OpLabel
+ %28 = OpCopyObject %7 %13
+ OpBranch %23
+ %26 = OpLabel
+ OpSelectionMerge %29 None
+ OpBranchConditional %6 %29 %24
+ %29 = OpLabel
+ %30 = OpCopyObject %7 %13
+ OpBranch %23
+ %24 = OpLabel
+ OpBranch %22
+ %23 = OpLabel
+ %102 = OpPhi %7 %13 %22 %28 %27 %30 %29
+ OpSelectionMerge %31 None
+ OpBranchConditional %6 %31 %31
+ %31 = OpLabel
+ %103 = OpPhi %7 %13 %23
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformations, context.get()));
+}
+
+TEST(TransformationAddOpPhiSynonymTest, VariablePointers) {
+ std::string shader = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main" %3
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %4 = OpTypeVoid
+ %5 = OpTypeFunction %4
+ %6 = OpTypeBool
+ %7 = OpConstantTrue %6
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %10 = OpTypePointer Workgroup %8
+ %3 = OpVariable %10 Workgroup
+ %2 = OpFunction %4 None %5
+ %11 = OpLabel
+ %12 = OpVariable %9 Function
+ OpSelectionMerge %13 None
+ OpBranchConditional %7 %14 %13
+ %14 = OpLabel
+ %15 = OpCopyObject %10 %3
+ %16 = OpCopyObject %9 %12
+ OpBranch %13
+ %13 = OpLabel
+ OpReturn
+ OpFunctionEnd
+)";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_5;
+ const auto consumer = nullptr;
+ const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+ ASSERT_TRUE(IsValid(env, context.get()));
+
+ FactManager fact_manager;
+ spvtools::ValidatorOptions validator_options;
+ TransformationContext transformation_context(&fact_manager,
+ validator_options);
+
+ // Declare synonyms
+ fact_manager.AddFact(MakeSynonymFact(3, 15), context.get());
+ fact_manager.AddFact(MakeSynonymFact(12, 16), context.get());
+
+ // Remove the VariablePointers capability.
+ context.get()->get_feature_mgr()->RemoveCapability(
+ SpvCapabilityVariablePointers);
+
+ // The VariablePointers capability is required to add an OpPhi instruction of
+ // pointer type.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(13, {{{11, 3}, {14, 15}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ // Add the VariablePointers capability back.
+ context.get()->get_feature_mgr()->AddCapability(
+ SpvCapabilityVariablePointers);
+
+ // If the ids have pointer type, the storage class must be Workgroup or
+ // StorageBuffer, but it is Function in this case.
+ ASSERT_FALSE(TransformationAddOpPhiSynonym(13, {{{11, 12}, {14, 16}}}, 100)
+ .IsApplicable(context.get(), transformation_context));
+
+ auto transformation =
+ TransformationAddOpPhiSynonym(13, {{{11, 3}, {14, 15}}}, 100);
+ ASSERT_TRUE(
+ transformation.IsApplicable(context.get(), transformation_context));
+ transformation.Apply(context.get(), &transformation_context);
+
+ std::string after_transformation = R"(
+ OpCapability Shader
+ OpCapability VariablePointers
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main" %3
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource ESSL 310
+ %4 = OpTypeVoid
+ %5 = OpTypeFunction %4
+ %6 = OpTypeBool
+ %7 = OpConstantTrue %6
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %10 = OpTypePointer Workgroup %8
+ %3 = OpVariable %10 Workgroup
+ %2 = OpFunction %4 None %5
+ %11 = OpLabel
+ %12 = OpVariable %9 Function
+ OpSelectionMerge %13 None
+ OpBranchConditional %7 %14 %13
+ %14 = OpLabel
+ %15 = OpCopyObject %10 %3
+ %16 = OpCopyObject %9 %12
+ OpBranch %13
+ %13 = OpLabel
+ %100 = OpPhi %10 %3 %11 %15 %14
+ OpReturn
+ OpFunctionEnd
+)";
+
+ ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+} // namespace
+} // namespace fuzz
+} // namespace spvtools
