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