blob: 6652f30aa850b35f23694ee066da0d93ec4bc3bc [file] [log] [blame]
// Copyright (c) 2019 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef SOURCE_FUZZ_FACT_MANAGER_DATA_SYNONYM_AND_ID_EQUATION_FACTS_H_
#define SOURCE_FUZZ_FACT_MANAGER_DATA_SYNONYM_AND_ID_EQUATION_FACTS_H_
#include <unordered_set>
#include <vector>
#include "source/fuzz/data_descriptor.h"
#include "source/fuzz/equivalence_relation.h"
#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
#include "source/opt/ir_context.h"
namespace spvtools {
namespace fuzz {
namespace fact_manager {
// Forward reference to the DeadBlockFacts class.
class DeadBlockFacts;
// Forward reference to the IrrelevantValueFacts class.
class IrrelevantValueFacts;
// The purpose of this class is to group the fields and data used to represent
// facts about data synonyms and id equations.
class DataSynonymAndIdEquationFacts {
public:
explicit DataSynonymAndIdEquationFacts(opt::IRContext* ir_context);
// See method in FactManager which delegates to this method. Returns true if
// neither |fact.data1()| nor |fact.data2()| contain an
// irrelevant id. Otherwise, returns false. |dead_block_facts| and
// |irrelevant_value_facts| are passed for consistency checks.
bool MaybeAddFact(const protobufs::FactDataSynonym& fact,
const DeadBlockFacts& dead_block_facts,
const IrrelevantValueFacts& irrelevant_value_facts);
// See method in FactManager which delegates to this method. Returns true if
// neither |fact.lhs_id()| nor any of |fact.rhs_id()| is irrelevant. Returns
// false otherwise. |dead_block_facts| and |irrelevant_value_facts| are passed
// for consistency checks.
bool MaybeAddFact(const protobufs::FactIdEquation& fact,
const DeadBlockFacts& dead_block_facts,
const IrrelevantValueFacts& irrelevant_value_facts);
// See method in FactManager which delegates to this method.
std::vector<const protobufs::DataDescriptor*> GetSynonymsForId(
uint32_t id) const;
// See method in FactManager which delegates to this method.
std::vector<const protobufs::DataDescriptor*> GetSynonymsForDataDescriptor(
const protobufs::DataDescriptor& data_descriptor) const;
// See method in FactManager which delegates to this method.
std::vector<uint32_t> GetIdsForWhichSynonymsAreKnown() const;
// See method in FactManager which delegates to this method.
std::vector<const protobufs::DataDescriptor*> GetAllKnownSynonyms() const;
// See method in FactManager which delegates to this method.
bool IsSynonymous(const protobufs::DataDescriptor& data_descriptor1,
const protobufs::DataDescriptor& data_descriptor2) const;
// See method in FactManager which delegates to this method.
void ComputeClosureOfFacts(uint32_t maximum_equivalence_class_size);
private:
// This helper struct represents the right hand side of an equation as an
// operator applied to a number of data descriptor operands.
struct Operation {
SpvOp opcode;
std::vector<const protobufs::DataDescriptor*> operands;
};
// Hashing for operations, to allow deterministic unordered sets.
struct OperationHash {
size_t operator()(const Operation& operation) const;
};
// Equality for operations, to allow deterministic unordered sets.
struct OperationEquals {
bool operator()(const Operation& first, const Operation& second) const;
};
using OperationSet =
std::unordered_set<Operation, OperationHash, OperationEquals>;
// Adds the synonym |dd1| = |dd2| to the set of managed facts, and recurses
// into sub-components of the data descriptors, if they are composites, to
// record that their components are pairwise-synonymous.
void AddDataSynonymFactRecursive(const protobufs::DataDescriptor& dd1,
const protobufs::DataDescriptor& dd2);
// Computes various corollary facts from the data descriptor |dd| if members
// of its equivalence class participate in equation facts with OpConvert*
// opcodes. The descriptor should be registered in the equivalence relation.
void ComputeConversionDataSynonymFacts(const protobufs::DataDescriptor& dd);
// Recurses into sub-components of the data descriptors, if they are
// composites, to record that their components are pairwise-synonymous.
void ComputeCompositeDataSynonymFacts(const protobufs::DataDescriptor& dd1,
const protobufs::DataDescriptor& dd2);
// Records the fact that |dd1| and |dd2| are equivalent, and merges the sets
// of equations that are known about them.
void MakeEquivalent(const protobufs::DataDescriptor& dd1,
const protobufs::DataDescriptor& dd2);
// Registers a data descriptor in the equivalence relation if it hasn't been
// registered yet, and returns its representative.
const protobufs::DataDescriptor* RegisterDataDescriptor(
const protobufs::DataDescriptor& dd);
// Trivially returns true if either |dd1| or |dd2|'s objects are not present
// in the module.
//
// Otherwise, returns true if and only if |dd1| and |dd2| are valid data
// descriptors whose associated data have compatible types. Two types are
// compatible if:
// - they are the same
// - they both are numerical or vectors of numerical components with the same
// number of components and the same bit count per component
bool DataDescriptorsAreWellFormedAndComparable(
const protobufs::DataDescriptor& dd1,
const protobufs::DataDescriptor& dd2) const;
OperationSet GetEquations(const protobufs::DataDescriptor* lhs) const;
// Requires that |lhs_dd| and every element of |rhs_dds| is present in the
// |synonymous_| equivalence relation, but is not necessarily its own
// representative. Records the fact that the equation
// "|lhs_dd| |opcode| |rhs_dds_non_canonical|" holds, and adds any
// corollaries, in the form of data synonym or equation facts, that follow
// from this and other known facts.
void AddEquationFactRecursive(
const protobufs::DataDescriptor& lhs_dd, SpvOp opcode,
const std::vector<const protobufs::DataDescriptor*>& rhs_dds);
// Returns true if and only if |dd.object()| still exists in the module.
bool ObjectStillExists(const protobufs::DataDescriptor& dd) const;
// The data descriptors that are known to be synonymous with one another are
// captured by this equivalence relation.
EquivalenceRelation<protobufs::DataDescriptor, DataDescriptorHash,
DataDescriptorEquals>
synonymous_;
// When a new synonym fact is added, it may be possible to deduce further
// synonym facts by computing a closure of all known facts. However, this is
// an expensive operation, so it should be performed sparingly and only there
// is some chance of new facts being deduced. This boolean tracks whether a
// closure computation is required - i.e., whether a new fact has been added
// since the last time such a computation was performed.
bool closure_computation_required_ = false;
// Represents a set of equations on data descriptors as a map indexed by
// left-hand-side, mapping a left-hand-side to a set of operations, each of
// which (together with the left-hand-side) defines an equation.
//
// All data descriptors occurring in equations are required to be present in
// the |synonymous_| equivalence relation, and to be their own representatives
// in that relation.
std::unordered_map<const protobufs::DataDescriptor*, OperationSet>
id_equations_;
// Pointer to the SPIR-V module we store facts about.
opt::IRContext* ir_context_;
};
} // namespace fact_manager
} // namespace fuzz
} // namespace spvtools
#endif // SOURCE_FUZZ_FACT_MANAGER_DATA_SYNONYM_AND_ID_EQUATION_FACTS_H_