1 // Copyright (c) 2019 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_FACT_MANAGER_DATA_SYNONYM_AND_ID_EQUATION_FACTS_H_ 16 #define SOURCE_FUZZ_FACT_MANAGER_DATA_SYNONYM_AND_ID_EQUATION_FACTS_H_ 17 18 #include <unordered_set> 19 #include <vector> 20 21 #include "source/fuzz/data_descriptor.h" 22 #include "source/fuzz/equivalence_relation.h" 23 #include "source/fuzz/protobufs/spirvfuzz_protobufs.h" 24 #include "source/opt/ir_context.h" 25 26 namespace spvtools { 27 namespace fuzz { 28 namespace fact_manager { 29 30 // Forward reference to the DeadBlockFacts class. 31 class DeadBlockFacts; 32 // Forward reference to the IrrelevantValueFacts class. 33 class IrrelevantValueFacts; 34 35 // The purpose of this class is to group the fields and data used to represent 36 // facts about data synonyms and id equations. 37 class DataSynonymAndIdEquationFacts { 38 public: 39 explicit DataSynonymAndIdEquationFacts(opt::IRContext* ir_context); 40 41 // See method in FactManager which delegates to this method. Returns true if 42 // neither |fact.data1()| nor |fact.data2()| contain an 43 // irrelevant id. Otherwise, returns false. |dead_block_facts| and 44 // |irrelevant_value_facts| are passed for consistency checks. 45 bool MaybeAddFact(const protobufs::FactDataSynonym& fact, 46 const DeadBlockFacts& dead_block_facts, 47 const IrrelevantValueFacts& irrelevant_value_facts); 48 49 // See method in FactManager which delegates to this method. Returns true if 50 // neither |fact.lhs_id()| nor any of |fact.rhs_id()| is irrelevant. Returns 51 // false otherwise. |dead_block_facts| and |irrelevant_value_facts| are passed 52 // for consistency checks. 53 bool MaybeAddFact(const protobufs::FactIdEquation& fact, 54 const DeadBlockFacts& dead_block_facts, 55 const IrrelevantValueFacts& irrelevant_value_facts); 56 57 // See method in FactManager which delegates to this method. 58 std::vector<const protobufs::DataDescriptor*> GetSynonymsForId( 59 uint32_t id) const; 60 61 // See method in FactManager which delegates to this method. 62 std::vector<const protobufs::DataDescriptor*> GetSynonymsForDataDescriptor( 63 const protobufs::DataDescriptor& data_descriptor) const; 64 65 // See method in FactManager which delegates to this method. 66 std::vector<uint32_t> GetIdsForWhichSynonymsAreKnown() const; 67 68 // See method in FactManager which delegates to this method. 69 std::vector<const protobufs::DataDescriptor*> GetAllKnownSynonyms() const; 70 71 // See method in FactManager which delegates to this method. 72 bool IsSynonymous(const protobufs::DataDescriptor& data_descriptor1, 73 const protobufs::DataDescriptor& data_descriptor2) const; 74 75 // See method in FactManager which delegates to this method. 76 void ComputeClosureOfFacts(uint32_t maximum_equivalence_class_size); 77 78 private: 79 // This helper struct represents the right hand side of an equation as an 80 // operator applied to a number of data descriptor operands. 81 struct Operation { 82 SpvOp opcode; 83 std::vector<const protobufs::DataDescriptor*> operands; 84 }; 85 86 // Hashing for operations, to allow deterministic unordered sets. 87 struct OperationHash { 88 size_t operator()(const Operation& operation) const; 89 }; 90 91 // Equality for operations, to allow deterministic unordered sets. 92 struct OperationEquals { 93 bool operator()(const Operation& first, const Operation& second) const; 94 }; 95 96 using OperationSet = 97 std::unordered_set<Operation, OperationHash, OperationEquals>; 98 99 // Adds the synonym |dd1| = |dd2| to the set of managed facts, and recurses 100 // into sub-components of the data descriptors, if they are composites, to 101 // record that their components are pairwise-synonymous. 102 void AddDataSynonymFactRecursive(const protobufs::DataDescriptor& dd1, 103 const protobufs::DataDescriptor& dd2); 104 105 // Computes various corollary facts from the data descriptor |dd| if members 106 // of its equivalence class participate in equation facts with OpConvert* 107 // opcodes. The descriptor should be registered in the equivalence relation. 108 void ComputeConversionDataSynonymFacts(const protobufs::DataDescriptor& dd); 109 110 // Recurses into sub-components of the data descriptors, if they are 111 // composites, to record that their components are pairwise-synonymous. 112 void ComputeCompositeDataSynonymFacts(const protobufs::DataDescriptor& dd1, 113 const protobufs::DataDescriptor& dd2); 114 115 // Records the fact that |dd1| and |dd2| are equivalent, and merges the sets 116 // of equations that are known about them. 117 void MakeEquivalent(const protobufs::DataDescriptor& dd1, 118 const protobufs::DataDescriptor& dd2); 119 120 // Registers a data descriptor in the equivalence relation if it hasn't been 121 // registered yet, and returns its representative. 122 const protobufs::DataDescriptor* RegisterDataDescriptor( 123 const protobufs::DataDescriptor& dd); 124 125 // Trivially returns true if either |dd1| or |dd2|'s objects are not present 126 // in the module. 127 // 128 // Otherwise, returns true if and only if |dd1| and |dd2| are valid data 129 // descriptors whose associated data have compatible types. Two types are 130 // compatible if: 131 // - they are the same 132 // - they both are numerical or vectors of numerical components with the same 133 // number of components and the same bit count per component 134 bool DataDescriptorsAreWellFormedAndComparable( 135 const protobufs::DataDescriptor& dd1, 136 const protobufs::DataDescriptor& dd2) const; 137 138 OperationSet GetEquations(const protobufs::DataDescriptor* lhs) const; 139 140 // Requires that |lhs_dd| and every element of |rhs_dds| is present in the 141 // |synonymous_| equivalence relation, but is not necessarily its own 142 // representative. Records the fact that the equation 143 // "|lhs_dd| |opcode| |rhs_dds_non_canonical|" holds, and adds any 144 // corollaries, in the form of data synonym or equation facts, that follow 145 // from this and other known facts. 146 void AddEquationFactRecursive( 147 const protobufs::DataDescriptor& lhs_dd, SpvOp opcode, 148 const std::vector<const protobufs::DataDescriptor*>& rhs_dds); 149 150 // Returns true if and only if |dd.object()| still exists in the module. 151 bool ObjectStillExists(const protobufs::DataDescriptor& dd) const; 152 153 // The data descriptors that are known to be synonymous with one another are 154 // captured by this equivalence relation. 155 EquivalenceRelation<protobufs::DataDescriptor, DataDescriptorHash, 156 DataDescriptorEquals> 157 synonymous_; 158 159 // When a new synonym fact is added, it may be possible to deduce further 160 // synonym facts by computing a closure of all known facts. However, this is 161 // an expensive operation, so it should be performed sparingly and only there 162 // is some chance of new facts being deduced. This boolean tracks whether a 163 // closure computation is required - i.e., whether a new fact has been added 164 // since the last time such a computation was performed. 165 bool closure_computation_required_ = false; 166 167 // Represents a set of equations on data descriptors as a map indexed by 168 // left-hand-side, mapping a left-hand-side to a set of operations, each of 169 // which (together with the left-hand-side) defines an equation. 170 // 171 // All data descriptors occurring in equations are required to be present in 172 // the |synonymous_| equivalence relation, and to be their own representatives 173 // in that relation. 174 std::unordered_map<const protobufs::DataDescriptor*, OperationSet> 175 id_equations_; 176 177 // Pointer to the SPIR-V module we store facts about. 178 opt::IRContext* ir_context_; 179 }; 180 181 } // namespace fact_manager 182 } // namespace fuzz 183 } // namespace spvtools 184 185 #endif // SOURCE_FUZZ_FACT_MANAGER_DATA_SYNONYM_AND_ID_EQUATION_FACTS_H_ 186