Debian Codegraph @

third_party/spirv-tools/source/fuzz/fact_manager/fact_manager.h

raw
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_FACT_MANAGER_H_
16 #define SOURCE_FUZZ_FACT_MANAGER_FACT_MANAGER_H_
17
18 #include <set>
19 #include <utility>
20 #include <vector>
21
22 #include "source/fuzz/data_descriptor.h"
23 #include "source/fuzz/fact_manager/constant_uniform_facts.h"
24 #include "source/fuzz/fact_manager/data_synonym_and_id_equation_facts.h"
25 #include "source/fuzz/fact_manager/dead_block_facts.h"
26 #include "source/fuzz/fact_manager/irrelevant_value_facts.h"
27 #include "source/fuzz/fact_manager/livesafe_function_facts.h"
28 #include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
29 #include "source/opt/constants.h"
30
31 namespace spvtools {
32 namespace fuzz {
33
34 // Keeps track of facts about the module being transformed on which the fuzzing
35 // process can depend. Some initial facts can be provided, for example about
36 // guarantees on the values of inputs to SPIR-V entry points. Transformations
37 // may then rely on these facts, can add further facts that they establish.
38 // Facts are intended to be simple properties that either cannot be deduced from
39 // the module (such as properties that are guaranteed to hold for entry point
40 // inputs), or that are established by transformations, likely to be useful for
41 // future transformations, and not completely trivial to deduce straight from
42 // the module.
43 class FactManager {
44 public:
45 explicit FactManager(opt::IRContext* ir_context);
46
47 // Adds all the facts from |facts|, checking them for validity with respect to
48 // |ir_context_|. Warnings about invalid facts are communicated via
49 // |message_consumer|; such facts are otherwise ignored.
50 void AddInitialFacts(const MessageConsumer& message_consumer,
51 const protobufs::FactSequence& facts);
52
53 // Checks the fact for validity with respect to |ir_context_|. Returns false,
54 // with no side effects, if the fact is invalid. Otherwise adds |fact| to the
55 // fact manager.
56 bool MaybeAddFact(const protobufs::Fact& fact);
57
58 // Record the fact that |data1| and |data2| are synonymous. Neither |data1|
59 // nor |data2| may contain an irrelevant id.
60 void AddFactDataSynonym(const protobufs::DataDescriptor& data1,
61 const protobufs::DataDescriptor& data2);
62
63 // Records the fact that |block_id| is dead. |block_id| must be a result id
64 // of some OpLabel instruction in the |ir_context_|.
65 void AddFactBlockIsDead(uint32_t block_id);
66
67 // Records the fact that |function_id| is livesafe. |function_id| must be a
68 // result id of some non-entry-point function in the module.
69 void AddFactFunctionIsLivesafe(uint32_t function_id);
70
71 // Records the fact that the value of the pointee associated with |pointer_id|
72 // is irrelevant: it does not affect the observable behaviour of the module.
73 // |pointer_id| must exist in the module and actually be a pointer.
74 void AddFactValueOfPointeeIsIrrelevant(uint32_t pointer_id);
75
76 // Records a fact that the |result_id| is irrelevant (i.e. it doesn't affect
77 // the semantics of the module).
78 // |result_id| must exist in the module and it may not be a pointer.
79 void AddFactIdIsIrrelevant(uint32_t result_id);
80
81 // Records the fact that |lhs_id| is defined by the equation:
82 //
83 // |lhs_id| = |opcode| |rhs_id[0]| ... |rhs_id[N-1]|
84 //
85 // Neither |lhs_id| nor any of |rhs_id| may be irrelevant.
86 void AddFactIdEquation(uint32_t lhs_id, SpvOp opcode,
87 const std::vector<uint32_t>& rhs_id);
88
89 // Inspects all known facts and adds corollary facts; e.g. if we know that
90 // a.x == b.x and a.y == b.y, where a and b have vec2 type, we can record
91 // that a == b holds.
92 //
93 // This method is expensive, and should only be called (by applying a
94 // transformation) at the start of a fuzzer pass that depends on data
95 // synonym facts, rather than calling it every time a new data synonym fact
96 // is added.
97 //
98 // The parameter |maximum_equivalence_class_size| specifies the size beyond
99 // which equivalence classes should not be mined for new facts, to avoid
100 // excessively-long closure computations.
101 void ComputeClosureOfFacts(uint32_t maximum_equivalence_class_size);
102
103 // The fact manager is responsible for managing a few distinct categories of
104 // facts. In principle there could be different fact managers for each kind
105 // of fact, but in practice providing one 'go to' place for facts is
106 // convenient. To keep some separation, the public methods of the fact
107 // manager should be grouped according to the kind of fact to which they
108 // relate.
109
110 //==============================
111 // Querying facts about uniform constants
112
113 // Provides the distinct type ids for which at least one "constant ==
114 // uniform element" fact is known.
115 std::vector<uint32_t> GetTypesForWhichUniformValuesAreKnown() const;
116
117 // Provides distinct constant ids with type |type_id| for which at least one
118 // "constant == uniform element" fact is known. If multiple identically-
119 // valued constants are relevant, only one will appear in the sequence.
120 std::vector<uint32_t> GetConstantsAvailableFromUniformsForType(
121 uint32_t type_id) const;
122
123 // Provides details of all uniform elements that are known to be equal to the
124 // constant associated with |constant_id| in |ir_context_|.
125 std::vector<protobufs::UniformBufferElementDescriptor>
126 GetUniformDescriptorsForConstant(uint32_t constant_id) const;
127
128 // Returns the id of a constant whose value is known to match that of
129 // |uniform_descriptor|, and whose type matches the type of the uniform
130 // element. If multiple such constant is exist, the one that is returned
131 // is arbitrary. Returns 0 if no such constant id exists.
132 uint32_t GetConstantFromUniformDescriptor(
133 const protobufs::UniformBufferElementDescriptor& uniform_descriptor)
134 const;
135
136 // Returns all "constant == uniform element" facts known to the fact
137 // manager, pairing each fact with id of the type that is associated with
138 // both the constant and the uniform element.
139 const std::vector<std::pair<protobufs::FactConstantUniform, uint32_t>>&
140 GetConstantUniformFactsAndTypes() const;
141
142 // End of uniform constant facts
143 //==============================
144
145 //==============================
146 // Querying facts about id synonyms
147
148 // Returns every id for which a fact of the form "this id is synonymous with
149 // this piece of data" is known.
150 std::vector<uint32_t> GetIdsForWhichSynonymsAreKnown() const;
151
152 // Returns a vector of all data descriptors that participate in DataSynonym
153 // facts. All descriptors are guaranteed to exist in the |ir_context_|.
154 std::vector<const protobufs::DataDescriptor*> GetAllSynonyms() const;
155
156 // Returns the equivalence class of all known synonyms of |id|, or an empty
157 // set if no synonyms are known.
158 std::vector<const protobufs::DataDescriptor*> GetSynonymsForId(
159 uint32_t id) const;
160
161 // Returns the equivalence class of all known synonyms of |data_descriptor|,
162 // or empty if no synonyms are known.
163 std::vector<const protobufs::DataDescriptor*> GetSynonymsForDataDescriptor(
164 const protobufs::DataDescriptor& data_descriptor) const;
165
166 // Returns true if and ony if |data_descriptor1| and |data_descriptor2| are
167 // known to be synonymous.
168 bool IsSynonymous(const protobufs::DataDescriptor& data_descriptor1,
169 const protobufs::DataDescriptor& data_descriptor2) const;
170
171 // End of id synonym facts
172 //==============================
173
174 //==============================
175 // Querying facts about dead blocks
176
177 // Returns true if and ony if |block_id| is the id of a block known to be
178 // dynamically unreachable.
179 bool BlockIsDead(uint32_t block_id) const;
180
181 // End of dead block facts
182 //==============================
183
184 //==============================
185 // Querying facts about livesafe function
186
187 // Returns true if and ony if |function_id| is the id of a function known
188 // to be livesafe.
189 bool FunctionIsLivesafe(uint32_t function_id) const;
190
191 // End of dead livesafe function facts
192 //==============================
193
194 //==============================
195 // Querying facts about irrelevant values
196
197 // Returns true if and ony if the value of the pointee associated with
198 // |pointer_id| is irrelevant.
199 bool PointeeValueIsIrrelevant(uint32_t pointer_id) const;
200
201 // Returns true if there exists a fact that the |result_id| is irrelevant or
202 // if |result_id| is declared in a block that has been declared dead.
203 bool IdIsIrrelevant(uint32_t result_id) const;
204
205 // Returns a set of all the ids which have been declared irrelevant, or which
206 // have been declared inside a dead block.
207 std::unordered_set<uint32_t> GetIrrelevantIds() const;
208
209 // End of irrelevant value facts
210 //==============================
211
212 private:
213 // Keep these in alphabetical order.
214 fact_manager::ConstantUniformFacts constant_uniform_facts_;
215 fact_manager::DataSynonymAndIdEquationFacts
216 data_synonym_and_id_equation_facts_;
217 fact_manager::DeadBlockFacts dead_block_facts_;
218 fact_manager::LivesafeFunctionFacts livesafe_function_facts_;
219 fact_manager::IrrelevantValueFacts irrelevant_value_facts_;
220 };
221
222 } // namespace fuzz
223 } // namespace spvtools
224
225 #endif // SOURCE_FUZZ_FACT_MANAGER_FACT_MANAGER_H_