| 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_ |