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