1 // Copyright (c) 2020 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef SOURCE_FUZZ_FUZZER_PASS_ADD_OPPHI_SYNONYMS_H_ 16 #define SOURCE_FUZZ_FUZZER_PASS_ADD_OPPHI_SYNONYMS_H_ 17 18 #include "source/fuzz/fuzzer_pass.h" 19 20 namespace spvtools { 21 namespace fuzz { 22 23 // A fuzzer pass to add OpPhi instructions which can take the values of ids that 24 // have been marked as synonymous. This instruction will itself be marked as 25 // synonymous with the others. 26 class FuzzerPassAddOpPhiSynonyms : public FuzzerPass { 27 public: 28 FuzzerPassAddOpPhiSynonyms(opt::IRContext* ir_context, 29 TransformationContext* transformation_context, 30 FuzzerContext* fuzzer_context, 31 protobufs::TransformationSequence* transformations, 32 bool ignore_inapplicable_transformations); 33 34 void Apply() override; 35 36 // Computes the equivalence classes for the non-pointer and non-irrelevant ids 37 // in the module, where two ids are considered equivalent iff they have been 38 // declared synonymous and they have the same type. 39 std::vector<std::set<uint32_t>> GetIdEquivalenceClasses(); 40 41 // Returns true iff |equivalence_class| contains at least 42 // |distinct_ids_required| ids so that all of these ids are available at the 43 // end of at least one predecessor of the block with label |block_id|. 44 // Assumes that the block has at least one predecessor. 45 bool EquivalenceClassIsSuitableForBlock( 46 const std::set<uint32_t>& equivalence_class, uint32_t block_id, 47 uint32_t distinct_ids_required); 48 49 // Returns a vector with the ids that are available to use at the end of the 50 // block with id |pred_id|, selected among the given |ids|. Assumes that 51 // |pred_id| is the label of a block and all ids in |ids| exist in the module. 52 std::vector<uint32_t> GetSuitableIds(const std::set<uint32_t>& ids, 53 uint32_t pred_id); 54 55 private: 56 // Randomly chooses one of the equivalence classes in |candidates|, so that it 57 // satisfies all of the following conditions: 58 // - For each of the predecessors of the |block_id| block, there is at least 59 // one id in the chosen equivalence class that is available at the end of 60 // it. 61 // - There are at least |distinct_ids_required| ids available at the end of 62 // some predecessor. 63 // Returns nullptr if no equivalence class in |candidates| satisfies the 64 // requirements. 65 std::set<uint32_t>* MaybeFindSuitableEquivalenceClassRandomly( 66 const std::vector<std::set<uint32_t>*>& candidates, uint32_t block_id, 67 uint32_t distinct_ids_required); 68 }; 69 } // namespace fuzz 70 } // namespace spvtools 71 72 #endif // SOURCE_FUZZ_FUZZER_PASS_ADD_OPPHI_SYNONYMS_H_ 73