blob: 995657cc133452ec9f2916caaf385c0180f3e53c [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_branches_from_dead_blocks_with_exits.h"
#include <algorithm>
#include <vector>
#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/transformation_replace_branch_from_dead_block_with_exit.h"
namespace spvtools {
namespace fuzz {
FuzzerPassReplaceBranchesFromDeadBlocksWithExits::
FuzzerPassReplaceBranchesFromDeadBlocksWithExits(
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 FuzzerPassReplaceBranchesFromDeadBlocksWithExits::Apply() {
// OpKill can only be used as a terminator in a function that is guaranteed
// to be executed with the Fragment execution model. We conservatively only
// allow OpKill if every entry point in the module has the Fragment execution
// model.
auto fragment_execution_model_guaranteed =
std::all_of(GetIRContext()->module()->entry_points().begin(),
GetIRContext()->module()->entry_points().end(),
[](const opt::Instruction& entry_point) -> bool {
return entry_point.GetSingleWordInOperand(0) ==
SpvExecutionModelFragment;
});
// Transformations of this type can disable one another. To avoid ordering
// bias, we therefore build a set of candidate transformations to apply, and
// subsequently apply them in a random order, skipping any that cease to be
// applicable.
std::vector<TransformationReplaceBranchFromDeadBlockWithExit>
candidate_transformations;
// Consider every block in every function.
for (auto& function : *GetIRContext()->module()) {
for (auto& block : function) {
// Probabilistically decide whether to skip this block.
if (GetFuzzerContext()->ChoosePercentage(
GetFuzzerContext()
->GetChanceOfReplacingBranchFromDeadBlockWithExit())) {
continue;
}
// Check whether the block is suitable for having its terminator replaced.
if (!TransformationReplaceBranchFromDeadBlockWithExit::BlockIsSuitable(
GetIRContext(), *GetTransformationContext(), block)) {
continue;
}
// We can always use OpUnreachable to replace a block's terminator.
// Whether we can use OpKill depends on the execution model, and which of
// OpReturn and OpReturnValue we can use depends on the return type of the
// enclosing function.
std::vector<SpvOp> opcodes = {SpvOpUnreachable};
if (fragment_execution_model_guaranteed) {
opcodes.emplace_back(SpvOpKill);
}
auto function_return_type =
GetIRContext()->get_type_mgr()->GetType(function.type_id());
if (function_return_type->AsVoid()) {
opcodes.emplace_back(SpvOpReturn);
} else if (fuzzerutil::CanCreateConstant(GetIRContext(),
function.type_id())) {
// For simplicity we only allow OpReturnValue if the function return
// type is a type for which we can create a constant. This allows us a
// zero of the given type as a default return value.
opcodes.emplace_back(SpvOpReturnValue);
}
// Choose one of the available terminator opcodes at random and create a
// candidate transformation.
auto opcode = opcodes[GetFuzzerContext()->RandomIndex(opcodes)];
candidate_transformations.emplace_back(
TransformationReplaceBranchFromDeadBlockWithExit(
block.id(), opcode,
opcode == SpvOpReturnValue
? FindOrCreateZeroConstant(function.type_id(), true)
: 0));
}
}
// Process the candidate transformations in a random order.
while (!candidate_transformations.empty()) {
// Transformations of this type can disable one another. For example,
// suppose we have dead blocks A, B, C, D arranged as follows:
//
// A |
// / \ |
// B C |
// \ / |
// D |
//
// Here we can replace the terminator of either B or C with an early exit,
// because D has two predecessors. But if we replace the terminator of B,
// say, we get:
//
// A |
// / \ |
// B C |
// / |
// D |
//
// and now it is no longer OK to replace the terminator of C as D only has
// one predecessor and we do not want to make D unreachable in the control
// flow graph.
MaybeApplyTransformation(
GetFuzzerContext()->RemoveAtRandomIndex(&candidate_transformations));
}
}
} // namespace fuzz
} // namespace spvtools