spirv-fuzz: Add FuzzerPassAddCompositeExtract (#3904)
Fixes #3806.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index c936ca8..a0e7ed8 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -54,6 +54,7 @@
fuzzer_pass.h
fuzzer_pass_add_access_chains.h
fuzzer_pass_add_bit_instruction_synonyms.h
+ fuzzer_pass_add_composite_extract.h
fuzzer_pass_add_composite_inserts.h
fuzzer_pass_add_composite_types.h
fuzzer_pass_add_copy_memory.h
@@ -241,6 +242,7 @@
fuzzer_pass.cpp
fuzzer_pass_add_access_chains.cpp
fuzzer_pass_add_bit_instruction_synonyms.cpp
+ fuzzer_pass_add_composite_extract.cpp
fuzzer_pass_add_composite_inserts.cpp
fuzzer_pass_add_composite_types.cpp
fuzzer_pass_add_copy_memory.cpp
diff --git a/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.cpp b/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.cpp
index 0308d50..ad4cd0c 100644
--- a/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.cpp
+++ b/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.cpp
@@ -909,6 +909,17 @@
return result;
}
+std::vector<const protobufs::DataDescriptor*>
+DataSynonymAndIdEquationFacts::GetAllKnownSynonyms() const {
+ std::vector<const protobufs::DataDescriptor*> result;
+ for (const auto* dd : synonymous_.GetAllKnownValues()) {
+ if (ObjectStillExists(*dd)) {
+ result.push_back(dd);
+ }
+ }
+ return result;
+}
+
bool DataSynonymAndIdEquationFacts::IsSynonymous(
const protobufs::DataDescriptor& data_descriptor1,
const protobufs::DataDescriptor& data_descriptor2) const {
diff --git a/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.h b/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.h
index f8a0123..6652f30 100644
--- a/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.h
+++ b/source/fuzz/fact_manager/data_synonym_and_id_equation_facts.h
@@ -66,6 +66,9 @@
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;
diff --git a/source/fuzz/fact_manager/fact_manager.cpp b/source/fuzz/fact_manager/fact_manager.cpp
index 29050e9..40c0865 100644
--- a/source/fuzz/fact_manager/fact_manager.cpp
+++ b/source/fuzz/fact_manager/fact_manager.cpp
@@ -177,6 +177,11 @@
return data_synonym_and_id_equation_facts_.GetIdsForWhichSynonymsAreKnown();
}
+std::vector<const protobufs::DataDescriptor*> FactManager::GetAllSynonyms()
+ const {
+ return data_synonym_and_id_equation_facts_.GetAllKnownSynonyms();
+}
+
std::vector<const protobufs::DataDescriptor*>
FactManager::GetSynonymsForDataDescriptor(
const protobufs::DataDescriptor& data_descriptor) const {
diff --git a/source/fuzz/fact_manager/fact_manager.h b/source/fuzz/fact_manager/fact_manager.h
index 78769c1..5cf5b18 100644
--- a/source/fuzz/fact_manager/fact_manager.h
+++ b/source/fuzz/fact_manager/fact_manager.h
@@ -149,6 +149,10 @@
// this piece of data" is known.
std::vector<uint32_t> GetIdsForWhichSynonymsAreKnown() const;
+ // Returns a vector of all data descriptors that participate in DataSynonym
+ // facts. All descriptors are guaranteed to exist in the |ir_context_|.
+ std::vector<const protobufs::DataDescriptor*> GetAllSynonyms() const;
+
// Returns the equivalence class of all known synonyms of |id|, or an empty
// set if no synonyms are known.
std::vector<const protobufs::DataDescriptor*> GetSynonymsForId(
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 64b0772..f326656 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -23,6 +23,7 @@
#include "source/fuzz/fuzzer_context.h"
#include "source/fuzz/fuzzer_pass_add_access_chains.h"
#include "source/fuzz/fuzzer_pass_add_bit_instruction_synonyms.h"
+#include "source/fuzz/fuzzer_pass_add_composite_extract.h"
#include "source/fuzz/fuzzer_pass_add_composite_inserts.h"
#include "source/fuzz/fuzzer_pass_add_composite_types.h"
#include "source/fuzz/fuzzer_pass_add_copy_memory.h"
@@ -228,6 +229,7 @@
// if it is enabled.
MaybeAddRepeatedPass<FuzzerPassAddAccessChains>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassAddBitInstructionSynonyms>(&pass_instances);
+ MaybeAddRepeatedPass<FuzzerPassAddCompositeExtract>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassAddCompositeInserts>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassAddCompositeTypes>(&pass_instances);
MaybeAddRepeatedPass<FuzzerPassAddCopyMemory>(&pass_instances);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 19d4ca5..3a27d6f 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -35,6 +35,7 @@
20};
const std::pair<uint32_t, uint32_t>
kChanceOfAddingBothBranchesWhenReplacingOpSelect = {40, 60};
+const std::pair<uint32_t, uint32_t> kChanceOfAddingCompositeExtract = {20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfAddingCompositeInsert = {20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfAddingCopyMemory = {20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfAddingDeadBlock = {20, 90};
@@ -82,6 +83,8 @@
20, 50};
const std::pair<uint32_t, uint32_t> kChanceOfFlatteningConditionalBranch = {45,
95};
+const std::pair<uint32_t, uint32_t> kChanceOfGoingDeeperToExtractComposite = {
+ 30, 70};
const std::pair<uint32_t, uint32_t> kChanceOfGoingDeeperToInsertInComposite = {
30, 70};
const std::pair<uint32_t, uint32_t> kChanceOfGoingDeeperWhenMakingAccessChain =
@@ -197,6 +200,8 @@
ChooseBetweenMinAndMax(kChanceOfAddingBitInstructionSynonym);
chance_of_adding_both_branches_when_replacing_opselect_ =
ChooseBetweenMinAndMax(kChanceOfAddingBothBranchesWhenReplacingOpSelect);
+ chance_of_adding_composite_extract_ =
+ ChooseBetweenMinAndMax(kChanceOfAddingCompositeExtract);
chance_of_adding_composite_insert_ =
ChooseBetweenMinAndMax(kChanceOfAddingCompositeInsert);
chance_of_adding_copy_memory_ =
@@ -263,6 +268,8 @@
ChooseBetweenMinAndMax(kChanceOfDuplicatingRegionWithSelection);
chance_of_flattening_conditional_branch_ =
ChooseBetweenMinAndMax(kChanceOfFlatteningConditionalBranch);
+ chance_of_going_deeper_to_extract_composite_ =
+ ChooseBetweenMinAndMax(kChanceOfGoingDeeperToExtractComposite);
chance_of_going_deeper_to_insert_in_composite_ =
ChooseBetweenMinAndMax(kChanceOfGoingDeeperToInsertInComposite);
chance_of_going_deeper_when_making_access_chain_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 147c66d..b230af3 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -127,6 +127,9 @@
uint32_t GetChanceOfAddingBothBranchesWhenReplacingOpSelect() {
return chance_of_adding_both_branches_when_replacing_opselect_;
}
+ uint32_t GetChanceOfAddingCompositeExtract() {
+ return chance_of_adding_composite_extract_;
+ }
uint32_t GetChanceOfAddingCompositeInsert() {
return chance_of_adding_composite_insert_;
}
@@ -216,6 +219,9 @@
uint32_t GetChanceOfFlatteningConditionalBranch() {
return chance_of_flattening_conditional_branch_;
}
+ uint32_t GetChanceOfGoingDeeperToExtractComposite() {
+ return chance_of_going_deeper_to_extract_composite_;
+ }
uint32_t GetChanceOfGoingDeeperToInsertInComposite() {
return chance_of_going_deeper_to_insert_in_composite_;
}
@@ -354,6 +360,10 @@
return components;
}
+ uint32_t GetRandomCompositeExtractIndex(uint32_t number_of_members) {
+ assert(number_of_members > 0 && "Composite object must have some members");
+ return ChooseBetweenMinAndMax({0, number_of_members - 1});
+ }
uint32_t GetRandomIndexForAccessChain(uint32_t composite_size_bound) {
return random_generator_->RandomUint32(composite_size_bound);
}
@@ -416,6 +426,7 @@
uint32_t chance_of_adding_array_or_struct_type_;
uint32_t chance_of_adding_bit_instruction_synonym_;
uint32_t chance_of_adding_both_branches_when_replacing_opselect_;
+ uint32_t chance_of_adding_composite_extract_;
uint32_t chance_of_adding_composite_insert_;
uint32_t chance_of_adding_copy_memory_;
uint32_t chance_of_adding_dead_block_;
@@ -451,6 +462,7 @@
uint32_t chance_of_donating_additional_module_;
uint32_t chance_of_duplicating_region_with_selection_;
uint32_t chance_of_flattening_conditional_branch_;
+ uint32_t chance_of_going_deeper_to_extract_composite_;
uint32_t chance_of_going_deeper_to_insert_in_composite_;
uint32_t chance_of_going_deeper_when_making_access_chain_;
uint32_t chance_of_having_two_blocks_in_loop_to_create_int_synonym_;
diff --git a/source/fuzz/fuzzer_pass_add_composite_extract.cpp b/source/fuzz/fuzzer_pass_add_composite_extract.cpp
new file mode 100644
index 0000000..3b40d5f
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_composite_extract.cpp
@@ -0,0 +1,162 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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.
+
+#include "source/fuzz/fuzzer_pass_add_composite_extract.h"
+
+#include "source/fuzz/fuzzer_context.h"
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "source/fuzz/transformation_composite_extract.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassAddCompositeExtract::FuzzerPassAddCompositeExtract(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, transformation_context, fuzzer_context,
+ transformations) {}
+
+FuzzerPassAddCompositeExtract::~FuzzerPassAddCompositeExtract() = default;
+
+void FuzzerPassAddCompositeExtract::Apply() {
+ std::vector<const protobufs::DataDescriptor*> composite_synonyms;
+ for (const auto* dd :
+ GetTransformationContext()->GetFactManager()->GetAllSynonyms()) {
+ // |dd| must describe a component of a composite.
+ if (!dd->index().empty()) {
+ composite_synonyms.push_back(dd);
+ }
+ }
+
+ // We don't want to invalidate the module every time we apply this
+ // transformation since rebuilding DominatorAnalysis can be expensive, so we
+ // collect up the transformations we wish to apply and apply them all later.
+ std::vector<TransformationCompositeExtract> transformations;
+
+ ForEachInstructionWithInstructionDescriptor(
+ [this, &composite_synonyms, &transformations](
+ opt::Function* function, opt::BasicBlock* block,
+ opt::BasicBlock::iterator inst_it,
+ const protobufs::InstructionDescriptor& instruction_descriptor) {
+ if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(SpvOpCompositeExtract,
+ inst_it)) {
+ return;
+ }
+
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfAddingCompositeExtract())) {
+ return;
+ }
+
+ auto available_composites = FindAvailableInstructions(
+ function, block, inst_it,
+ [](opt::IRContext* ir_context, opt::Instruction* inst) {
+ return inst->type_id() && inst->result_id() &&
+ fuzzerutil::IsCompositeType(
+ ir_context->get_type_mgr()->GetType(inst->type_id()));
+ });
+
+ std::vector<const protobufs::DataDescriptor*> available_synonyms;
+ for (const auto* dd : composite_synonyms) {
+ if (fuzzerutil::IdIsAvailableBeforeInstruction(
+ GetIRContext(), &*inst_it, dd->object())) {
+ available_synonyms.push_back(dd);
+ }
+ }
+
+ if (available_synonyms.empty() && available_composites.empty()) {
+ return;
+ }
+
+ uint32_t composite_id = 0;
+ std::vector<uint32_t> indices;
+
+ if (available_synonyms.empty() || (!available_composites.empty() &&
+ GetFuzzerContext()->ChooseEven())) {
+ const auto* inst =
+ available_composites[GetFuzzerContext()->RandomIndex(
+ available_composites)];
+ composite_id = inst->result_id();
+
+ const auto* type =
+ GetIRContext()->get_type_mgr()->GetType(inst->type_id());
+ assert(type && "Composite instruction has invalid type id");
+
+ do {
+ uint32_t number_of_members = 0;
+
+ if (const auto* array_type = type->AsArray()) {
+ const auto* type_inst =
+ GetIRContext()->get_def_use_mgr()->GetDef(inst->type_id());
+ assert(type_inst && "Type instruction must exist");
+
+ number_of_members =
+ fuzzerutil::GetArraySize(*type_inst, GetIRContext());
+ type = array_type->element_type();
+ } else if (const auto* vector_type = type->AsVector()) {
+ number_of_members = vector_type->element_count();
+ type = vector_type->element_type();
+ } else if (const auto* matrix_type = type->AsMatrix()) {
+ number_of_members = matrix_type->element_count();
+ type = matrix_type->element_type();
+ } else if (const auto* struct_type = type->AsStruct()) {
+ number_of_members =
+ static_cast<uint32_t>(struct_type->element_types().size());
+ // The next value of |type| will be assigned when we know the
+ // index of the OpTypeStruct's operand.
+ } else {
+ assert(false && "|inst| is not a composite");
+ return;
+ }
+
+ if (number_of_members == 0) {
+ return;
+ }
+
+ indices.push_back(
+ GetFuzzerContext()->GetRandomCompositeExtractIndex(
+ number_of_members));
+
+ if (const auto* struct_type = type->AsStruct()) {
+ type = struct_type->element_types()[indices.back()];
+ }
+ } while (fuzzerutil::IsCompositeType(type) &&
+ GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()
+ ->GetChanceOfGoingDeeperToExtractComposite()));
+ } else {
+ const auto* dd = available_synonyms[GetFuzzerContext()->RandomIndex(
+ available_synonyms)];
+
+ composite_id = dd->object();
+ indices.assign(dd->index().begin(), dd->index().end());
+ }
+
+ assert(composite_id != 0 && !indices.empty() &&
+ "Composite object should have been chosen correctly");
+
+ transformations.emplace_back(instruction_descriptor,
+ GetFuzzerContext()->GetFreshId(),
+ composite_id, indices);
+ });
+
+ for (const auto& transformation : transformations) {
+ ApplyTransformation(transformation);
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_add_composite_extract.h b/source/fuzz/fuzzer_pass_add_composite_extract.h
new file mode 100644
index 0000000..8bcb825
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_composite_extract.h
@@ -0,0 +1,40 @@
+// Copyright (c) 2020 Vasyl Teliman
+//
+// 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_FUZZER_PASS_ADD_COMPOSITE_EXTRACT_H_
+#define SOURCE_FUZZ_FUZZER_PASS_ADD_COMPOSITE_EXTRACT_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Randomly decides whether to add OpCompositeExtract before some instruction
+// in the module.
+class FuzzerPassAddCompositeExtract : public FuzzerPass {
+ public:
+ FuzzerPassAddCompositeExtract(
+ opt::IRContext* ir_context, TransformationContext* transformation_context,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassAddCompositeExtract() override;
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_ADD_COMPOSITE_EXTRACT_H_
diff --git a/source/fuzz/pass_management/repeated_pass_instances.h b/source/fuzz/pass_management/repeated_pass_instances.h
index 6809d07..5f479fb 100644
--- a/source/fuzz/pass_management/repeated_pass_instances.h
+++ b/source/fuzz/pass_management/repeated_pass_instances.h
@@ -17,6 +17,7 @@
#include "source/fuzz/fuzzer_pass_add_access_chains.h"
#include "source/fuzz/fuzzer_pass_add_bit_instruction_synonyms.h"
+#include "source/fuzz/fuzzer_pass_add_composite_extract.h"
#include "source/fuzz/fuzzer_pass_add_composite_inserts.h"
#include "source/fuzz/fuzzer_pass_add_composite_types.h"
#include "source/fuzz/fuzzer_pass_add_copy_memory.h"
@@ -110,6 +111,7 @@
REPEATED_PASS_INSTANCE(AddAccessChains);
REPEATED_PASS_INSTANCE(AddBitInstructionSynonyms);
+ REPEATED_PASS_INSTANCE(AddCompositeExtract);
REPEATED_PASS_INSTANCE(AddCompositeInserts);
REPEATED_PASS_INSTANCE(AddCompositeTypes);
REPEATED_PASS_INSTANCE(AddCopyMemory);
diff --git a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
index 060c743..7121c33 100644
--- a/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
+++ b/source/fuzz/pass_management/repeated_pass_recommender_standard.cpp
@@ -40,6 +40,10 @@
// - Adding bit instruction synonyms creates opportunities to apply synonyms
return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()});
}
+ if (&pass == pass_instances_->GetAddCompositeExtract()) {
+ // - This transformation can introduce synonyms to the fact manager.
+ return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()});
+ }
if (&pass == pass_instances_->GetAddCompositeInserts()) {
// - Having added inserts we will have more vectors, so there is scope for
// vector shuffling
diff --git a/source/fuzz/transformation_composite_extract.cpp b/source/fuzz/transformation_composite_extract.cpp
index 291331c..2aff02f 100644
--- a/source/fuzz/transformation_composite_extract.cpp
+++ b/source/fuzz/transformation_composite_extract.cpp
@@ -55,19 +55,14 @@
if (!composite_instruction) {
return false;
}
- if (auto block = ir_context->get_instr_block(composite_instruction)) {
- if (composite_instruction == instruction_to_insert_before ||
- !ir_context->GetDominatorAnalysis(block->GetParent())
- ->Dominates(composite_instruction, instruction_to_insert_before)) {
- return false;
- }
+ if (!fuzzerutil::IdIsAvailableBeforeInstruction(
+ ir_context, instruction_to_insert_before, message_.composite_id())) {
+ return false;
}
- assert(composite_instruction->type_id() &&
- "An instruction in a block cannot have a result id but no type id.");
auto composite_type =
ir_context->get_type_mgr()->GetType(composite_instruction->type_id());
- if (!composite_type) {
+ if (!fuzzerutil::IsCompositeType(composite_type)) {
return false;
}
@@ -133,19 +128,14 @@
// Add the fact that the id storing the extracted element is synonymous with
// the index into the structure.
- if (!transformation_context->GetFactManager()->IdIsIrrelevant(
- message_.composite_id())) {
- std::vector<uint32_t> indices;
- for (auto an_index : message_.index()) {
- indices.push_back(an_index);
- }
- protobufs::DataDescriptor data_descriptor_for_extracted_element =
- MakeDataDescriptor(message_.composite_id(), indices);
- protobufs::DataDescriptor data_descriptor_for_result_id =
- MakeDataDescriptor(message_.fresh_id(), {});
- transformation_context->GetFactManager()->AddFactDataSynonym(
- data_descriptor_for_extracted_element, data_descriptor_for_result_id);
- }
+ std::vector<uint32_t> indices(message_.index().begin(),
+ message_.index().end());
+ auto data_descriptor_for_extracted_element =
+ MakeDataDescriptor(message_.composite_id(), indices);
+ auto data_descriptor_for_result_id =
+ MakeDataDescriptor(message_.fresh_id(), {});
+ transformation_context->GetFactManager()->AddFactDataSynonym(
+ data_descriptor_for_extracted_element, data_descriptor_for_result_id);
}
} // namespace fuzz
diff --git a/test/fuzz/transformation_composite_extract_test.cpp b/test/fuzz/transformation_composite_extract_test.cpp
index 1ee62f5..383a4db 100644
--- a/test/fuzz/transformation_composite_extract_test.cpp
+++ b/test/fuzz/transformation_composite_extract_test.cpp
@@ -107,9 +107,10 @@
.IsApplicable(context.get(), transformation_context));
// Id for composite is not a composite.
- ASSERT_FALSE(TransformationCompositeExtract(
- MakeInstructionDescriptor(36, SpvOpIAdd, 0), 200, 27, {})
- .IsApplicable(context.get(), transformation_context));
+ ASSERT_FALSE(
+ TransformationCompositeExtract(
+ MakeInstructionDescriptor(37, SpvOpAccessChain, 0), 200, 32, {})
+ .IsApplicable(context.get(), transformation_context));
// Composite does not dominate instruction being inserted before.
ASSERT_FALSE(