| // 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, |
| bool ignore_inapplicable_transformations) |
| : FuzzerPass(ir_context, transformation_context, fuzzer_context, |
| transformations, ignore_inapplicable_transformations) {} |
| |
| 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 not be dead. |
| if (GetTransformationContext()->GetFactManager()->BlockIsDead( |
| block.id())) { |
| 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; |
| } |
| |
| // Exclude OpFunction and OpUndef instructions, because: |
| // - OpFunction does not yield a value; |
| // - OpUndef yields an undefined value at each use, so it should never be a |
| // synonym of another id. |
| if (pair.second->opcode() == SpvOpFunction || |
| pair.second->opcode() == SpvOpUndef) { |
| 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 |