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( 29 opt::IRContext* ir_context, TransformationContext* transformation_context, 30 FuzzerContext* fuzzer_context, 31 protobufs::TransformationSequence* transformations); 32 33 ~FuzzerPassAddOpPhiSynonyms() override; 34 35 void Apply() override; 36 37 // Computes the equivalence classes for the non-pointer and non-irrelevant ids 38 // in the module, where two ids are considered equivalent iff they have been 39 // declared synonymous and they have the same type. 40 std::vector<std::set<uint32_t>> GetIdEquivalenceClasses(); 41 42 // Returns true iff |equivalence_class| contains at least 43 // |distinct_ids_required| ids so that all of these ids are available at the 44 // end of at least one predecessor of the block with label |block_id|. 45 // Assumes that the block has at least one predecessor. 46 bool EquivalenceClassIsSuitableForBlock( 47 const std::set<uint32_t>& equivalence_class, uint32_t block_id, 48 uint32_t distinct_ids_required); 49 50 // Returns a vector with the ids that are available to use at the end of the 51 // block with id |pred_id|, selected among the given |ids|. Assumes that 52 // |pred_id| is the label of a block and all ids in |ids| exist in the module. 53 std::vector<uint32_t> GetSuitableIds(const std::set<uint32_t>& ids, 54 uint32_t pred_id); 55 56 private: 57 // Randomly chooses one of the equivalence classes in |candidates|, so that it 58 // satisfies all of the following conditions: 59 // - For each of the predecessors of the |block_id| block, there is at least 60 // one id in the chosen equivalence class that is available at the end of 61 // it. 62 // - There are at least |distinct_ids_required| ids available at the end of 63 // some predecessor. 64 // Returns nullptr if no equivalence class in |candidates| satisfies the 65 // requirements. 66 std::set<uint32_t>* MaybeFindSuitableEquivalenceClassRandomly( 67 const std::vector<std::set<uint32_t>*>& candidates, uint32_t block_id, 68 uint32_t distinct_ids_required); 69 }; 70 } // namespace fuzz 71 } // namespace spvtools 72 73 #endif // SOURCE_FUZZ_FUZZER_PASS_ADD_OPPHI_SYNONYMS_H_ 74