spirv-fuzz: Efficiency improvements to fuzzer pass (#4188)
FuzzerPassConstructComposites is adapted to use AvailableInstructions
to manage available instructions, and to use zero constants when
trying to construct a composite for which not all fields can otherwise
be constructed. The change uncovered some cases where we create
structs and arrays with struct fields or components that are
block-decorated; these possibilities have been eliminated.
diff --git a/source/fuzz/fuzzer_pass_add_composite_types.cpp b/source/fuzz/fuzzer_pass_add_composite_types.cpp
index a59cbfa..3dfbd69 100644
--- a/source/fuzz/fuzzer_pass_add_composite_types.cpp
+++ b/source/fuzz/fuzzer_pass_add_composite_types.cpp
@@ -123,7 +123,9 @@
break;
case SpvOpTypeStruct: {
if (!fuzzerutil::MembersHaveBuiltInDecoration(GetIRContext(),
- inst.result_id())) {
+ inst.result_id()) &&
+ !fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(),
+ inst.result_id())) {
candidates.push_back(inst.result_id());
}
} break;
diff --git a/source/fuzz/fuzzer_pass_construct_composites.cpp b/source/fuzz/fuzzer_pass_construct_composites.cpp
index dc02424..1a174cf 100644
--- a/source/fuzz/fuzzer_pass_construct_composites.cpp
+++ b/source/fuzz/fuzzer_pass_construct_composites.cpp
@@ -16,6 +16,7 @@
#include <memory>
+#include "source/fuzz/available_instructions.h"
#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/transformation_composite_construct.h"
@@ -42,12 +43,40 @@
}
}
+ if (composite_type_ids.empty()) {
+ // There are no composite types, so this fuzzer pass cannot do anything.
+ return;
+ }
+
+ AvailableInstructions available_composite_constituents(
+ GetIRContext(),
+ [this](opt::IRContext* ir_context, opt::Instruction* inst) -> bool {
+ if (!inst->result_id() || !inst->type_id()) {
+ return false;
+ }
+
+ // If the id is irrelevant, we can use it since it will not
+ // participate in DataSynonym fact. Otherwise, we should be able
+ // to produce a synonym out of the id.
+ return GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
+ inst->result_id()) ||
+ fuzzerutil::CanMakeSynonymOf(ir_context,
+ *GetTransformationContext(), inst);
+ });
+
ForEachInstructionWithInstructionDescriptor(
- [this, &composite_type_ids](
- opt::Function* function, opt::BasicBlock* block,
+ [this, &available_composite_constituents, &composite_type_ids](
+ opt::Function* /*unused*/, opt::BasicBlock* /*unused*/,
opt::BasicBlock::iterator inst_it,
const protobufs::InstructionDescriptor& instruction_descriptor)
-> void {
+ // Randomly decide whether to try inserting a composite construction
+ // here.
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfConstructingComposite())) {
+ return;
+ }
+
// Check whether it is legitimate to insert a composite construction
// before the instruction.
if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
@@ -55,36 +84,21 @@
return;
}
- // Randomly decide whether to try inserting an object copy here.
- if (!GetFuzzerContext()->ChoosePercentage(
- GetFuzzerContext()->GetChanceOfConstructingComposite())) {
- return;
- }
-
// For each instruction that is available at this program point (i.e. an
// instruction that is global or whose definition strictly dominates the
// program point) and suitable for making a synonym of, associate it
// with the id of its result type.
TypeIdToInstructions type_id_to_available_instructions;
- auto available_instructions = FindAvailableInstructions(
- function, block, inst_it,
- [this](opt::IRContext* ir_context, opt::Instruction* inst) {
- if (!inst->result_id() || !inst->type_id()) {
- return false;
- }
-
- // If the id is irrelevant, we can use it since it will not
- // participate in DataSynonym fact. Otherwise, we should be able
- // to produce a synonym out of the id.
- return GetTransformationContext()
- ->GetFactManager()
- ->IdIsIrrelevant(inst->result_id()) ||
- fuzzerutil::CanMakeSynonymOf(
- ir_context, *GetTransformationContext(), inst);
- });
- for (auto instruction : available_instructions) {
- RecordAvailableInstruction(instruction,
- &type_id_to_available_instructions);
+ auto available_instructions =
+ available_composite_constituents.GetAvailableBeforeInstruction(
+ &*inst_it);
+ for (uint32_t available_instruction_index = 0;
+ available_instruction_index < available_instructions.size();
+ available_instruction_index++) {
+ opt::Instruction* inst =
+ available_instructions[available_instruction_index];
+ type_id_to_available_instructions[inst->type_id()].push_back(
+ inst->result_id());
}
// At this point, |composite_type_ids| captures all the composite types
@@ -92,68 +106,41 @@
// captures all the available result ids we might use, organized by
// type.
- // Now we try to find a composite that we can construct. We might not
- // manage, if there is a paucity of available ingredients in the module
- // (e.g. if our only available composite was a boolean vector and we had
- // no instructions generating boolean result types available).
- //
- // If we succeed, |chosen_composite_type| will end up being non-zero,
- // and |constructor_arguments| will end up giving us result ids suitable
- // for constructing a composite of that type. Otherwise these variables
- // will remain 0 and null respectively.
- uint32_t chosen_composite_type = 0;
+ // Now we choose a composite type to construct, building it from
+ // available constituent components and using zero constants if suitable
+ // components are not available.
+
std::vector<uint32_t> constructor_arguments;
+ uint32_t chosen_composite_type =
+ composite_type_ids[GetFuzzerContext()->RandomIndex(
+ composite_type_ids)];
- // Initially, all composite type ids are available for us to try. Keep
- // trying until we run out of options.
- auto composites_to_try_constructing = composite_type_ids;
- while (!composites_to_try_constructing.empty()) {
- // Remove a composite type from the composite types left for us to
- // try.
- auto next_composite_to_try_constructing =
- GetFuzzerContext()->RemoveAtRandomIndex(
- &composites_to_try_constructing);
-
- // Now try to construct a composite of this type, using an appropriate
- // helper method depending on the kind of composite type.
- auto composite_type_inst = GetIRContext()->get_def_use_mgr()->GetDef(
- next_composite_to_try_constructing);
- switch (composite_type_inst->opcode()) {
- case SpvOpTypeArray:
- constructor_arguments = FindComponentsToConstructArray(
- *composite_type_inst, type_id_to_available_instructions);
- break;
- case SpvOpTypeMatrix:
- constructor_arguments = FindComponentsToConstructMatrix(
- *composite_type_inst, type_id_to_available_instructions);
- break;
- case SpvOpTypeStruct:
- constructor_arguments = FindComponentsToConstructStruct(
- *composite_type_inst, type_id_to_available_instructions);
- break;
- case SpvOpTypeVector:
- constructor_arguments = FindComponentsToConstructVector(
- *composite_type_inst, type_id_to_available_instructions);
- break;
- default:
- assert(false &&
- "The space of possible composite types should be covered "
- "by the above cases.");
- break;
- }
- if (!constructor_arguments.empty()) {
- // We succeeded! Note the composite type we finally settled on, and
- // exit from the loop.
- chosen_composite_type = next_composite_to_try_constructing;
+ // Construct a composite of this type, using an appropriate helper
+ // method depending on the kind of composite type.
+ auto composite_type_inst =
+ GetIRContext()->get_def_use_mgr()->GetDef(chosen_composite_type);
+ switch (composite_type_inst->opcode()) {
+ case SpvOpTypeArray:
+ constructor_arguments = FindComponentsToConstructArray(
+ *composite_type_inst, type_id_to_available_instructions);
break;
- }
- }
-
- if (!chosen_composite_type) {
- // We did not manage to make a composite; return 0 to indicate that no
- // instructions were added.
- assert(constructor_arguments.empty());
- return;
+ case SpvOpTypeMatrix:
+ constructor_arguments = FindComponentsToConstructMatrix(
+ *composite_type_inst, type_id_to_available_instructions);
+ break;
+ case SpvOpTypeStruct:
+ constructor_arguments = FindComponentsToConstructStruct(
+ *composite_type_inst, type_id_to_available_instructions);
+ break;
+ case SpvOpTypeVector:
+ constructor_arguments = FindComponentsToConstructVector(
+ *composite_type_inst, type_id_to_available_instructions);
+ break;
+ default:
+ assert(false &&
+ "The space of possible composite types should be covered "
+ "by the above cases.");
+ break;
}
assert(!constructor_arguments.empty());
@@ -164,15 +151,6 @@
});
}
-void FuzzerPassConstructComposites::RecordAvailableInstruction(
- opt::Instruction* inst,
- TypeIdToInstructions* type_id_to_available_instructions) {
- if (type_id_to_available_instructions->count(inst->type_id()) == 0) {
- (*type_id_to_available_instructions)[inst->type_id()] = {};
- }
- type_id_to_available_instructions->at(inst->type_id()).push_back(inst);
-}
-
std::vector<uint32_t>
FuzzerPassConstructComposites::FindComponentsToConstructArray(
const opt::Instruction& array_type_instruction,
@@ -188,13 +166,6 @@
auto available_instructions =
type_id_to_available_instructions.find(element_type_id);
- if (available_instructions == type_id_to_available_instructions.cend()) {
- // If there are not any instructions available that compute the element type
- // of the array then we are not in a position to construct a composite with
- // this array type.
- return {};
- }
-
uint32_t array_length =
GetIRContext()
->get_def_use_mgr()
@@ -203,10 +174,14 @@
std::vector<uint32_t> result;
for (uint32_t index = 0; index < array_length; index++) {
- result.push_back(available_instructions
- ->second[GetFuzzerContext()->RandomIndex(
- available_instructions->second)]
- ->result_id());
+ if (available_instructions == type_id_to_available_instructions.cend()) {
+ // No suitable instructions are available, so use a zero constant
+ result.push_back(FindOrCreateZeroConstant(element_type_id, true));
+ } else {
+ result.push_back(
+ available_instructions->second[GetFuzzerContext()->RandomIndex(
+ available_instructions->second)]);
+ }
}
return result;
}
@@ -226,19 +201,17 @@
auto available_instructions =
type_id_to_available_instructions.find(element_type_id);
- if (available_instructions == type_id_to_available_instructions.cend()) {
- // If there are not any instructions available that compute the element type
- // of the matrix then we are not in a position to construct a composite with
- // this matrix type.
- return {};
- }
std::vector<uint32_t> result;
for (uint32_t index = 0;
index < matrix_type_instruction.GetSingleWordInOperand(1); index++) {
- result.push_back(available_instructions
- ->second[GetFuzzerContext()->RandomIndex(
- available_instructions->second)]
- ->result_id());
+ if (available_instructions == type_id_to_available_instructions.cend()) {
+ // No suitable components are available, so use a zero constant.
+ result.push_back(FindOrCreateZeroConstant(element_type_id, true));
+ } else {
+ result.push_back(
+ available_instructions->second[GetFuzzerContext()->RandomIndex(
+ available_instructions->second)]);
+ }
}
return result;
}
@@ -261,14 +234,14 @@
auto available_instructions =
type_id_to_available_instructions.find(element_type_id);
if (available_instructions == type_id_to_available_instructions.cend()) {
- // If there are no such instructions, we cannot construct a composite of
- // this struct type.
- return {};
+ // No suitable component is available for this element type, so use a zero
+ // constant.
+ result.push_back(FindOrCreateZeroConstant(element_type_id, true));
+ } else {
+ result.push_back(
+ available_instructions->second[GetFuzzerContext()->RandomIndex(
+ available_instructions->second)]);
}
- result.push_back(available_instructions
- ->second[GetFuzzerContext()->RandomIndex(
- available_instructions->second)]
- ->result_id());
}
return result;
}
@@ -323,12 +296,13 @@
// (otherwise there will not be space left for a vec3).
uint32_t vector_slots_used = 0;
- // The instructions we will use to construct the vector, in no particular
- // order at this stage.
- std::vector<opt::Instruction*> instructions_to_use;
+
+ // The instructions result ids we will use to construct the vector, in no
+ // particular order at this stage.
+ std::vector<uint32_t> result;
while (vector_slots_used < element_count) {
- std::vector<opt::Instruction*> instructions_to_choose_from;
+ std::vector<uint32_t> instructions_to_choose_from;
for (auto& entry : smaller_vector_type_id_to_width) {
if (entry.second >
std::min(element_count - 1, element_count - vector_slots_used)) {
@@ -343,19 +317,16 @@
available_instructions->second.begin(),
available_instructions->second.end());
}
- if (instructions_to_choose_from.empty()) {
- // We may get unlucky and find that there are not any instructions to
- // choose from. In this case we give up constructing a composite of this
- // vector type. It might be that we could construct the composite in
- // another manner, so we could opt to retry a few times here, but it is
- // simpler to just give up on the basis that this will not happen
- // frequently.
- return {};
- }
- auto instruction_to_use =
- instructions_to_choose_from[GetFuzzerContext()->RandomIndex(
- instructions_to_choose_from)];
- instructions_to_use.push_back(instruction_to_use);
+ // If there are no instructions to choose from then use a zero constant,
+ // otherwise select one of the instructions at random.
+ uint32_t id_of_instruction_to_use =
+ instructions_to_choose_from.empty()
+ ? FindOrCreateZeroConstant(element_type_id, true)
+ : instructions_to_choose_from[GetFuzzerContext()->RandomIndex(
+ instructions_to_choose_from)];
+ opt::Instruction* instruction_to_use =
+ GetIRContext()->get_def_use_mgr()->GetDef(id_of_instruction_to_use);
+ result.push_back(instruction_to_use->result_id());
auto chosen_type =
GetIRContext()->get_type_mgr()->GetType(instruction_to_use->type_id());
if (chosen_type->AsVector()) {
@@ -371,14 +342,7 @@
}
assert(vector_slots_used == element_count);
- std::vector<uint32_t> result;
- std::vector<uint32_t> operands;
- while (!instructions_to_use.empty()) {
- auto index = GetFuzzerContext()->RandomIndex(instructions_to_use);
- result.push_back(instructions_to_use[index]->result_id());
- instructions_to_use.erase(instructions_to_use.begin() + index);
- }
- assert(result.size() > 1);
+ GetFuzzerContext()->Shuffle(&result);
return result;
}
diff --git a/source/fuzz/fuzzer_pass_construct_composites.h b/source/fuzz/fuzzer_pass_construct_composites.h
index cc5f98b..333ac93 100644
--- a/source/fuzz/fuzzer_pass_construct_composites.h
+++ b/source/fuzz/fuzzer_pass_construct_composites.h
@@ -15,7 +15,7 @@
#ifndef SOURCE_FUZZ_FUZZER_PASS_CONSTRUCT_COMPOSITES_H_
#define SOURCE_FUZZ_FUZZER_PASS_CONSTRUCT_COMPOSITES_H_
-#include <map>
+#include <unordered_map>
#include <vector>
#include "source/fuzz/fuzzer_pass.h"
@@ -34,18 +34,9 @@
void Apply() override;
private:
- // Used to map a type id to relevant instructions whose result type matches
- // the type id.
- typedef std::map<uint32_t, std::vector<opt::Instruction*>>
- TypeIdToInstructions;
-
- // Considers all instructions that are available at |inst| - instructions
- // whose results could be packed into a composite - and updates
- // |type_id_to_available_instructions| so that each such instruction is
- // associated with its the id of its result type.
- void RecordAvailableInstruction(
- opt::Instruction* inst,
- TypeIdToInstructions* type_id_to_available_instructions);
+ // Used to map a type id to the ids of relevant instructions of the type.
+ using TypeIdToInstructions =
+ std::unordered_map<uint32_t, std::vector<uint32_t>>;
// Requires that |array_type_instruction| has opcode OpTypeArray.
// Attempts to find suitable instruction result ids from the values of
diff --git a/source/fuzz/transformation_add_type_array.cpp b/source/fuzz/transformation_add_type_array.cpp
index 87b4447..45bc8df 100644
--- a/source/fuzz/transformation_add_type_array.cpp
+++ b/source/fuzz/transformation_add_type_array.cpp
@@ -39,9 +39,11 @@
}
auto element_type =
ir_context->get_type_mgr()->GetType(message_.element_type_id());
- if (!element_type || element_type->AsFunction()) {
- // The element type id either does not refer to a type, or refers to a
- // function type; both are illegal.
+ if (!element_type || element_type->AsFunction() ||
+ fuzzerutil::HasBlockOrBufferBlockDecoration(ir_context,
+ message_.element_type_id())) {
+ // The element type id either does not refer to a type, refers to a function
+ // type, or refers to a block-decorated struct. These cases are all illegal.
return false;
}
auto constant =
diff --git a/source/fuzz/transformation_add_type_array.h b/source/fuzz/transformation_add_type_array.h
index 4767fb8..3162497 100644
--- a/source/fuzz/transformation_add_type_array.h
+++ b/source/fuzz/transformation_add_type_array.h
@@ -33,8 +33,10 @@
// - |message_.fresh_id| must be fresh
// - |message_.element_type_id| must be the id of a non-function type
+ // - |message_.member_type_id| must not be the result id of an OpTypeStruct
+ // instruction that has the Block or BufferBlock decoration
// - |message_.size_id| must be the id of a 32-bit integer constant that is
- // positive when interpreted as signed.
+ // positive when interpreted as signed
bool IsApplicable(
opt::IRContext* ir_context,
const TransformationContext& transformation_context) const override;
diff --git a/source/fuzz/transformation_add_type_struct.cpp b/source/fuzz/transformation_add_type_struct.cpp
index 3d5e15a..d7f0711 100644
--- a/source/fuzz/transformation_add_type_struct.cpp
+++ b/source/fuzz/transformation_add_type_struct.cpp
@@ -39,9 +39,11 @@
}
for (auto member_type : message_.member_type_id()) {
auto type = ir_context->get_type_mgr()->GetType(member_type);
- if (!type || type->AsFunction()) {
- // The member type id either does not refer to a type, or refers to a
- // function type; both are illegal.
+ if (!type || type->AsFunction() ||
+ fuzzerutil::HasBlockOrBufferBlockDecoration(ir_context, member_type)) {
+ // The member type id either does not refer to a type, refers to a
+ // function type, or refers to a block-decorated struct. These cases are
+ // all illegal.
return false;
}
diff --git a/source/fuzz/transformation_add_type_struct.h b/source/fuzz/transformation_add_type_struct.h
index ea30d9b..6a8dce7 100644
--- a/source/fuzz/transformation_add_type_struct.h
+++ b/source/fuzz/transformation_add_type_struct.h
@@ -37,7 +37,9 @@
// - |message_.member_type_id| must be a sequence of non-function type ids
// - |message_.member_type_id| may not contain a result id of an OpTypeStruct
// instruction with BuiltIn members (i.e. members of the struct are
- // decorated via OpMemberDecorate with BuiltIn decoration).
+ // decorated via OpMemberDecorate with BuiltIn decoration)
+ // - |message_.member_type_id| may not contain a result id of an OpTypeStruct
+ // instruction that has the Block or BufferBlock decoration
bool IsApplicable(
opt::IRContext* ir_context,
const TransformationContext& transformation_context) const override;
