blob: 4d55ae840d457d2f0d9bb92699b49465f527026f [file] [log] [blame] [edit]
// Copyright (c) 2020 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.
#include "source/fuzz/fuzzer_pass_replace_irrelevant_ids.h"
#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/id_use_descriptor.h"
#include "source/fuzz/transformation_replace_irrelevant_id.h"
namespace spvtools {
namespace fuzz {
// A fuzzer pass that, for every use of an id that has been recorded as
// irrelevant, randomly decides whether to replace it with another id of the
// same type.
FuzzerPassReplaceIrrelevantIds::FuzzerPassReplaceIrrelevantIds(
opt::IRContext* ir_context, TransformationContext* transformation_context,
FuzzerContext* fuzzer_context,
protobufs::TransformationSequence* transformations,
bool ignore_inapplicable_transformations)
: FuzzerPass(ir_context, transformation_context, fuzzer_context,
transformations, ignore_inapplicable_transformations) {}
void FuzzerPassReplaceIrrelevantIds::Apply() {
// Keep track of the irrelevant ids. This includes all the ids that are
// irrelevant according to the fact manager and that are still present in the
// module (some of them may have been removed by previously-run
// transformations).
std::vector<uint32_t> irrelevant_ids;
// Keep a map from the type ids of irrelevant ids to all the ids with that
// type.
std::unordered_map<uint32_t, std::vector<uint32_t>> types_to_ids;
// Find all the irrelevant ids that still exist in the module and all the
// types for which irrelevant ids exist.
for (auto id :
GetTransformationContext()->GetFactManager()->GetIrrelevantIds()) {
// Check that the id still exists in the module.
auto declaration = GetIRContext()->get_def_use_mgr()->GetDef(id);
if (!declaration) {
continue;
}
irrelevant_ids.push_back(id);
// If the type of this id has not been seen before, add a mapping from this
// type id to an empty list in |types_to_ids|. The list will be filled later
// on.
if (types_to_ids.count(declaration->type_id()) == 0) {
types_to_ids.insert({declaration->type_id(), {}});
}
}
// If no irrelevant ids were found, return.
if (irrelevant_ids.empty()) {
return;
}
// For every type for which we have at least one irrelevant id, record all ids
// in the module which have that type. Skip ids of OpFunction instructions as
// we cannot use these as replacements.
for (const auto& pair : GetIRContext()->get_def_use_mgr()->id_to_defs()) {
uint32_t type_id = pair.second->type_id();
if (pair.second->opcode() != SpvOpFunction && type_id &&
types_to_ids.count(type_id)) {
types_to_ids[type_id].push_back(pair.first);
}
}
// Keep a list of all the transformations to perform. We avoid applying the
// transformations while traversing the uses since applying the transformation
// invalidates all analyses, and we want to avoid invalidating and recomputing
// them every time.
std::vector<TransformationReplaceIrrelevantId> transformations_to_apply;
// Loop through all the uses of irrelevant ids, check that the id can be
// replaced and randomly decide whether to apply the transformation.
for (auto irrelevant_id : irrelevant_ids) {
uint32_t type_id =
GetIRContext()->get_def_use_mgr()->GetDef(irrelevant_id)->type_id();
GetIRContext()->get_def_use_mgr()->ForEachUse(
irrelevant_id, [this, &irrelevant_id, &type_id, &types_to_ids,
&transformations_to_apply](opt::Instruction* use_inst,
uint32_t use_index) {
// Randomly decide whether to consider this use.
if (!GetFuzzerContext()->ChoosePercentage(
GetFuzzerContext()->GetChanceOfReplacingIrrelevantId())) {
return;
}
// The id must be used as an input operand.
if (use_index < use_inst->NumOperands() - use_inst->NumInOperands()) {
// The id is used as an output operand, so we cannot replace this
// usage.
return;
}
// Get the input operand index for this use, from the absolute operand
// index.
uint32_t in_index =
fuzzerutil::InOperandIndexFromOperandIndex(*use_inst, use_index);
// Only go ahead if this id use can be replaced in principle.
if (!fuzzerutil::IdUseCanBeReplaced(GetIRContext(),
*GetTransformationContext(),
use_inst, in_index)) {
return;
}
// Find out which ids could be used to replace this use.
std::vector<uint32_t> available_replacement_ids;
for (auto replacement_id : types_to_ids[type_id]) {
// It would be pointless to replace an id with itself.
if (replacement_id == irrelevant_id) {
continue;
}
// We cannot replace a variable initializer with a non-constant.
if (TransformationReplaceIrrelevantId::
AttemptsToReplaceVariableInitializerWithNonConstant(
*use_inst, *GetIRContext()->get_def_use_mgr()->GetDef(
replacement_id))) {
continue;
}
// Only consider this replacement if the use point is within a basic
// block and the id is available at the use point.
//
// There might be opportunities for replacing a non-block use of an
// irrelevant id - such as the initializer of a global variable -
// with another id, but it would require some care (e.g. to ensure
// that the replacement id is defined earlier) and does not seem
// worth doing.
if (GetIRContext()->get_instr_block(use_inst) &&
fuzzerutil::IdIsAvailableAtUse(GetIRContext(), use_inst,
in_index, replacement_id)) {
available_replacement_ids.push_back(replacement_id);
}
}
// Only go ahead if there is at least one id with which this use can
// be replaced.
if (available_replacement_ids.empty()) {
return;
}
// Choose the replacement id randomly.
uint32_t replacement_id =
available_replacement_ids[GetFuzzerContext()->RandomIndex(
available_replacement_ids)];
// Add this replacement to the list of transformations to apply.
transformations_to_apply.emplace_back(
TransformationReplaceIrrelevantId(
MakeIdUseDescriptorFromUse(GetIRContext(), use_inst,
in_index),
replacement_id));
});
}
// Apply all the transformations.
for (const auto& transformation : transformations_to_apply) {
ApplyTransformation(transformation);
}
}
} // namespace fuzz
} // namespace spvtools