339 строки
13 KiB
C++
339 строки
13 KiB
C++
// Copyright (c) 2020 Stefano Milizia
|
|
//
|
|
// 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_merge_function_returns.h"
|
|
|
|
#include "source/fuzz/fuzzer_util.h"
|
|
#include "source/fuzz/instruction_descriptor.h"
|
|
#include "source/fuzz/transformation_add_early_terminator_wrapper.h"
|
|
#include "source/fuzz/transformation_merge_function_returns.h"
|
|
#include "source/fuzz/transformation_wrap_early_terminator_in_function.h"
|
|
|
|
namespace spvtools {
|
|
namespace fuzz {
|
|
|
|
FuzzerPassMergeFunctionReturns::FuzzerPassMergeFunctionReturns(
|
|
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 FuzzerPassMergeFunctionReturns::Apply() {
|
|
// The pass might add new functions to the module (due to wrapping early
|
|
// terminator instructions in function calls), so we record the functions that
|
|
// are currently present and then iterate over them.
|
|
std::vector<opt::Function*> functions;
|
|
for (auto& function : *GetIRContext()->module()) {
|
|
functions.emplace_back(&function);
|
|
}
|
|
|
|
for (auto* function : functions) {
|
|
// Randomly decide whether to consider this function.
|
|
if (GetFuzzerContext()->ChoosePercentage(
|
|
GetFuzzerContext()->GetChanceOfMergingFunctionReturns())) {
|
|
continue;
|
|
}
|
|
|
|
// We skip wrappers for early terminators, since this fuzzer pass introduces
|
|
// such wrappers to eliminate early terminators.
|
|
if (IsEarlyTerminatorWrapper(*function)) {
|
|
continue;
|
|
}
|
|
|
|
// Only consider functions that have early returns.
|
|
if (!function->HasEarlyReturn()) {
|
|
continue;
|
|
}
|
|
|
|
// Wrap early terminators in function calls.
|
|
ForEachInstructionWithInstructionDescriptor(
|
|
function,
|
|
[this, function](
|
|
opt::BasicBlock* /*unused*/, opt::BasicBlock::iterator inst_it,
|
|
const protobufs::InstructionDescriptor& instruction_descriptor) {
|
|
const spv::Op opcode = inst_it->opcode();
|
|
switch (opcode) {
|
|
case spv::Op::OpKill:
|
|
case spv::Op::OpUnreachable:
|
|
case spv::Op::OpTerminateInvocation: {
|
|
// This is an early termination instruction - we need to wrap it
|
|
// so that it becomes a return.
|
|
if (TransformationWrapEarlyTerminatorInFunction::
|
|
MaybeGetWrapperFunction(GetIRContext(), opcode) ==
|
|
nullptr) {
|
|
// We don't have a suitable wrapper function, so create one.
|
|
ApplyTransformation(TransformationAddEarlyTerminatorWrapper(
|
|
GetFuzzerContext()->GetFreshId(),
|
|
GetFuzzerContext()->GetFreshId(), opcode));
|
|
}
|
|
// If the function has non-void return type then we need a
|
|
// suitable value to use in an OpReturnValue instruction.
|
|
opt::Instruction* function_return_type =
|
|
GetIRContext()->get_def_use_mgr()->GetDef(
|
|
function->type_id());
|
|
uint32_t returned_value_id;
|
|
if (function_return_type->opcode() == spv::Op::OpTypeVoid) {
|
|
// No value is needed.
|
|
returned_value_id = 0;
|
|
} else if (fuzzerutil::CanCreateConstant(
|
|
GetIRContext(),
|
|
function_return_type->result_id())) {
|
|
// We favour returning an irrelevant zero.
|
|
returned_value_id = FindOrCreateZeroConstant(
|
|
function_return_type->result_id(), true);
|
|
} else {
|
|
// It's not possible to use an irrelevant zero, so we use an
|
|
// OpUndef instead.
|
|
returned_value_id =
|
|
FindOrCreateGlobalUndef(function_return_type->result_id());
|
|
}
|
|
// Wrap the early termination instruction in a function call.
|
|
ApplyTransformation(TransformationWrapEarlyTerminatorInFunction(
|
|
GetFuzzerContext()->GetFreshId(), instruction_descriptor,
|
|
returned_value_id));
|
|
break;
|
|
}
|
|
default:
|
|
break;
|
|
}
|
|
});
|
|
|
|
// Get the return blocks.
|
|
auto return_blocks = fuzzerutil::GetReachableReturnBlocks(
|
|
GetIRContext(), function->result_id());
|
|
|
|
// Only go ahead if there is more than one reachable return block.
|
|
if (return_blocks.size() <= 1) {
|
|
continue;
|
|
}
|
|
|
|
// Make sure that OpConstantTrue and OpConstantFalse are in the module.
|
|
FindOrCreateBoolConstant(true, false);
|
|
FindOrCreateBoolConstant(false, false);
|
|
|
|
// Collect the ids available after the entry block of the function.
|
|
auto ids_available_after_entry_block =
|
|
GetTypesToIdsAvailableAfterEntryBlock(function);
|
|
|
|
// If the entry block does not branch unconditionally to another block,
|
|
// split it.
|
|
if (function->entry()->terminator()->opcode() != spv::Op::OpBranch) {
|
|
SplitBlockAfterOpPhiOrOpVariable(function->entry()->id());
|
|
}
|
|
|
|
// Collect the merge blocks of the function whose corresponding loops
|
|
// contain return blocks.
|
|
auto merge_blocks = GetMergeBlocksOfLoopsContainingBlocks(return_blocks);
|
|
|
|
// Split the merge blocks, if they contain instructions different from
|
|
// OpLabel, OpPhi and OpBranch. Collect the new ids of merge blocks.
|
|
std::vector<uint32_t> actual_merge_blocks;
|
|
for (uint32_t merge_block : merge_blocks) {
|
|
opt::BasicBlock* block = GetIRContext()->get_instr_block(merge_block);
|
|
|
|
// We don't need to split blocks that are already suitable (they only
|
|
// contain OpLabel, OpPhi or OpBranch instructions).
|
|
if (GetIRContext()
|
|
->get_instr_block(merge_block)
|
|
->WhileEachInst([](opt::Instruction* inst) {
|
|
return inst->opcode() == spv::Op::OpLabel ||
|
|
inst->opcode() == spv::Op::OpPhi ||
|
|
inst->opcode() == spv::Op::OpBranch;
|
|
})) {
|
|
actual_merge_blocks.emplace_back(merge_block);
|
|
continue;
|
|
}
|
|
|
|
// If the merge block is also a loop header, we need to add a preheader,
|
|
// which will be the new merge block.
|
|
if (block->IsLoopHeader()) {
|
|
actual_merge_blocks.emplace_back(
|
|
GetOrCreateSimpleLoopPreheader(merge_block)->id());
|
|
continue;
|
|
}
|
|
|
|
// If the merge block is not a loop header, we must split it after the
|
|
// last OpPhi instruction. The merge block will be the first of the pair
|
|
// of blocks obtained after splitting, and it keeps the original id.
|
|
SplitBlockAfterOpPhiOrOpVariable(merge_block);
|
|
actual_merge_blocks.emplace_back(merge_block);
|
|
}
|
|
|
|
// Get the ids needed by the transformation.
|
|
const uint32_t outer_header_id = GetFuzzerContext()->GetFreshId();
|
|
const uint32_t unreachable_continue_id = GetFuzzerContext()->GetFreshId();
|
|
const uint32_t outer_return_id = GetFuzzerContext()->GetFreshId();
|
|
|
|
bool function_is_void =
|
|
GetIRContext()->get_type_mgr()->GetType(function->type_id())->AsVoid();
|
|
|
|
// We only need a return value if the function is not void.
|
|
uint32_t return_val_id =
|
|
function_is_void ? 0 : GetFuzzerContext()->GetFreshId();
|
|
|
|
// We only need a placeholder for the return value if the function is not
|
|
// void and there is at least one relevant merge block.
|
|
uint32_t returnable_val_id = 0;
|
|
if (!function_is_void && !actual_merge_blocks.empty()) {
|
|
// If there is an id of the suitable type, choose one at random.
|
|
if (ids_available_after_entry_block.count(function->type_id())) {
|
|
const auto& candidates =
|
|
ids_available_after_entry_block[function->type_id()];
|
|
returnable_val_id =
|
|
candidates[GetFuzzerContext()->RandomIndex(candidates)];
|
|
} else {
|
|
// If there is no id, add a global OpUndef.
|
|
uint32_t suitable_id = FindOrCreateGlobalUndef(function->type_id());
|
|
// Add the new id to the map of available ids.
|
|
ids_available_after_entry_block.emplace(
|
|
function->type_id(), std::vector<uint32_t>({suitable_id}));
|
|
returnable_val_id = suitable_id;
|
|
}
|
|
}
|
|
|
|
// Collect all the ids needed for merge blocks.
|
|
auto merge_blocks_info = GetInfoNeededForMergeBlocks(
|
|
actual_merge_blocks, &ids_available_after_entry_block);
|
|
|
|
// Apply the transformation if it is applicable (it could be inapplicable if
|
|
// adding new predecessors to merge blocks breaks dominance rules).
|
|
MaybeApplyTransformation(TransformationMergeFunctionReturns(
|
|
function->result_id(), outer_header_id, unreachable_continue_id,
|
|
outer_return_id, return_val_id, returnable_val_id, merge_blocks_info));
|
|
}
|
|
}
|
|
|
|
std::map<uint32_t, std::vector<uint32_t>>
|
|
FuzzerPassMergeFunctionReturns::GetTypesToIdsAvailableAfterEntryBlock(
|
|
opt::Function* function) const {
|
|
std::map<uint32_t, std::vector<uint32_t>> result;
|
|
// Consider all global declarations
|
|
for (auto& global : GetIRContext()->module()->types_values()) {
|
|
if (global.HasResultId() && global.type_id()) {
|
|
if (!result.count(global.type_id())) {
|
|
result.emplace(global.type_id(), std::vector<uint32_t>());
|
|
}
|
|
result[global.type_id()].emplace_back(global.result_id());
|
|
}
|
|
}
|
|
|
|
// Consider all function parameters
|
|
function->ForEachParam([&result](opt::Instruction* param) {
|
|
if (param->HasResultId() && param->type_id()) {
|
|
if (!result.count(param->type_id())) {
|
|
result.emplace(param->type_id(), std::vector<uint32_t>());
|
|
}
|
|
|
|
result[param->type_id()].emplace_back(param->result_id());
|
|
}
|
|
});
|
|
|
|
// Consider all the instructions in the entry block.
|
|
for (auto& inst : *function->entry()) {
|
|
if (inst.HasResultId() && inst.type_id()) {
|
|
if (!result.count(inst.type_id())) {
|
|
result.emplace(inst.type_id(), std::vector<uint32_t>());
|
|
}
|
|
result[inst.type_id()].emplace_back(inst.result_id());
|
|
}
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
std::set<uint32_t>
|
|
FuzzerPassMergeFunctionReturns::GetMergeBlocksOfLoopsContainingBlocks(
|
|
const std::set<uint32_t>& blocks) const {
|
|
std::set<uint32_t> result;
|
|
for (uint32_t block : blocks) {
|
|
uint32_t merge_block =
|
|
GetIRContext()->GetStructuredCFGAnalysis()->LoopMergeBlock(block);
|
|
|
|
while (merge_block != 0 && !result.count(merge_block)) {
|
|
// Add a new entry.
|
|
result.emplace(merge_block);
|
|
|
|
// Walk up the loop tree.
|
|
block = merge_block;
|
|
merge_block = GetIRContext()->GetStructuredCFGAnalysis()->LoopMergeBlock(
|
|
merge_block);
|
|
}
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
std::vector<protobufs::ReturnMergingInfo>
|
|
FuzzerPassMergeFunctionReturns::GetInfoNeededForMergeBlocks(
|
|
const std::vector<uint32_t>& merge_blocks,
|
|
std::map<uint32_t, std::vector<uint32_t>>*
|
|
ids_available_after_entry_block) {
|
|
std::vector<protobufs::ReturnMergingInfo> result;
|
|
for (uint32_t merge_block : merge_blocks) {
|
|
protobufs::ReturnMergingInfo info;
|
|
info.set_merge_block_id(merge_block);
|
|
info.set_is_returning_id(this->GetFuzzerContext()->GetFreshId());
|
|
info.set_maybe_return_val_id(this->GetFuzzerContext()->GetFreshId());
|
|
|
|
// Add all the ids needed for the OpPhi instructions.
|
|
this->GetIRContext()
|
|
->get_instr_block(merge_block)
|
|
->ForEachPhiInst([this, &info, &ids_available_after_entry_block](
|
|
opt::Instruction* phi_inst) {
|
|
protobufs::UInt32Pair entry;
|
|
entry.set_first(phi_inst->result_id());
|
|
|
|
// If there is an id of the suitable type, choose one at random.
|
|
if (ids_available_after_entry_block->count(phi_inst->type_id())) {
|
|
auto& candidates =
|
|
ids_available_after_entry_block->at(phi_inst->type_id());
|
|
entry.set_second(
|
|
candidates[this->GetFuzzerContext()->RandomIndex(candidates)]);
|
|
} else {
|
|
// If there is no id, add a global OpUndef.
|
|
uint32_t suitable_id =
|
|
this->FindOrCreateGlobalUndef(phi_inst->type_id());
|
|
// Add the new id to the map of available ids.
|
|
ids_available_after_entry_block->emplace(
|
|
phi_inst->type_id(), std::vector<uint32_t>({suitable_id}));
|
|
entry.set_second(suitable_id);
|
|
}
|
|
|
|
// Add the entry to the list.
|
|
*info.add_opphi_to_suitable_id() = entry;
|
|
});
|
|
|
|
result.emplace_back(info);
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
bool FuzzerPassMergeFunctionReturns::IsEarlyTerminatorWrapper(
|
|
const opt::Function& function) const {
|
|
for (spv::Op opcode : {spv::Op::OpKill, spv::Op::OpUnreachable,
|
|
spv::Op::OpTerminateInvocation}) {
|
|
if (TransformationWrapEarlyTerminatorInFunction::MaybeGetWrapperFunction(
|
|
GetIRContext(), opcode) == &function) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
} // namespace fuzz
|
|
} // namespace spvtools
|