blob: a48b81796ceb4a461df40bc0b8fb42dd65c2c2b0 [file] [log] [blame] [edit]
// Copyright (c) 2020 André Perez Maselco
//
// 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/transformation_inline_function.h"
#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/instruction_descriptor.h"
namespace spvtools {
namespace fuzz {
TransformationInlineFunction::TransformationInlineFunction(
protobufs::TransformationInlineFunction message)
: message_(std::move(message)) {}
TransformationInlineFunction::TransformationInlineFunction(
uint32_t function_call_id,
const std::map<uint32_t, uint32_t>& result_id_map) {
message_.set_function_call_id(function_call_id);
*message_.mutable_result_id_map() =
fuzzerutil::MapToRepeatedUInt32Pair(result_id_map);
}
bool TransformationInlineFunction::IsApplicable(
opt::IRContext* ir_context,
const TransformationContext& transformation_context) const {
// The values in the |message_.result_id_map| must be all fresh and all
// distinct.
const auto result_id_map =
fuzzerutil::RepeatedUInt32PairToMap(message_.result_id_map());
std::set<uint32_t> ids_used_by_this_transformation;
for (auto& pair : result_id_map) {
if (!CheckIdIsFreshAndNotUsedByThisTransformation(
pair.second, ir_context, &ids_used_by_this_transformation)) {
return false;
}
}
// |function_call_instruction| must be suitable for inlining.
auto* function_call_instruction =
ir_context->get_def_use_mgr()->GetDef(message_.function_call_id());
if (!IsSuitableForInlining(ir_context, function_call_instruction)) {
return false;
}
// |function_call_instruction| must be the penultimate instruction in its
// block and its block termination instruction must be an OpBranch. This
// avoids the case where the penultimate instruction is an OpLoopMerge, which
// would make the back-edge block not branch to the loop header.
auto* function_call_instruction_block =
ir_context->get_instr_block(function_call_instruction);
if (function_call_instruction !=
&*--function_call_instruction_block->tail() ||
function_call_instruction_block->terminator()->opcode() != SpvOpBranch) {
return false;
}
auto* called_function = fuzzerutil::FindFunction(
ir_context, function_call_instruction->GetSingleWordInOperand(0));
for (auto& block : *called_function) {
// Since the entry block label will not be inlined, only the remaining
// labels must have a corresponding value in the map.
if (&block != &*called_function->entry() &&
!result_id_map.count(block.id()) &&
!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
return false;
}
// |result_id_map| must have an entry for every result id in the called
// function.
for (auto& instruction : block) {
// If |instruction| has result id, then it must have a mapped id in
// |result_id_map|.
if (instruction.HasResultId() &&
!result_id_map.count(instruction.result_id()) &&
!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
return false;
}
}
}
// |result_id_map| must not contain an entry for any parameter of the function
// that is being inlined.
bool found_entry_for_parameter = false;
called_function->ForEachParam(
[&result_id_map, &found_entry_for_parameter](opt::Instruction* param) {
if (result_id_map.count(param->result_id())) {
found_entry_for_parameter = true;
}
});
return !found_entry_for_parameter;
}
void TransformationInlineFunction::Apply(
opt::IRContext* ir_context,
TransformationContext* transformation_context) const {
auto* function_call_instruction =
ir_context->get_def_use_mgr()->GetDef(message_.function_call_id());
auto* caller_function =
ir_context->get_instr_block(function_call_instruction)->GetParent();
auto* called_function = fuzzerutil::FindFunction(
ir_context, function_call_instruction->GetSingleWordInOperand(0));
std::map<uint32_t, uint32_t> result_id_map =
fuzzerutil::RepeatedUInt32PairToMap(message_.result_id_map());
// If there are gaps in the result id map, fill them using overflow ids.
for (auto& block : *called_function) {
if (&block != &*called_function->entry() &&
!result_id_map.count(block.id())) {
result_id_map.insert(
{block.id(),
transformation_context->GetOverflowIdSource()->GetNextOverflowId()});
}
for (auto& instruction : block) {
// If |instruction| has result id, then it must have a mapped id in
// |result_id_map|.
if (instruction.HasResultId() &&
!result_id_map.count(instruction.result_id())) {
result_id_map.insert({instruction.result_id(),
transformation_context->GetOverflowIdSource()
->GetNextOverflowId()});
}
}
}
auto* successor_block = ir_context->cfg()->block(
ir_context->get_instr_block(function_call_instruction)
->terminator()
->GetSingleWordInOperand(0));
// Inline the |called_function| entry block.
for (auto& entry_block_instruction : *called_function->entry()) {
opt::Instruction* inlined_instruction;
if (entry_block_instruction.opcode() == SpvOpVariable) {
// All OpVariable instructions in a function must be in the first block
// in the function.
inlined_instruction = caller_function->begin()->begin()->InsertBefore(
std::unique_ptr<opt::Instruction>(
entry_block_instruction.Clone(ir_context)));
} else {
inlined_instruction = function_call_instruction->InsertBefore(
std::unique_ptr<opt::Instruction>(
entry_block_instruction.Clone(ir_context)));
}
AdaptInlinedInstruction(result_id_map, ir_context, inlined_instruction);
}
// If the function call's successor block contains OpPhi instructions that
// refer to the block containing the call then these will need to be rewritten
// to instead refer to the block associated with "returning" from the inlined
// function, as this block will be the predecessor of what used to be the
// function call's successor block. We look out for this block.
uint32_t new_return_block_id = 0;
// Inline the |called_function| non-entry blocks.
for (auto& block : *called_function) {
if (&block == &*called_function->entry()) {
continue;
}
// Check whether this is the function's return block. Take note if it is,
// so that OpPhi instructions in the successor of the original function call
// block can be re-written.
if (block.terminator()->IsReturn()) {
assert(new_return_block_id == 0 &&
"There should be only one return block.");
new_return_block_id = result_id_map.at(block.id());
}
auto* cloned_block = block.Clone(ir_context);
cloned_block = caller_function->InsertBasicBlockBefore(
std::unique_ptr<opt::BasicBlock>(cloned_block), successor_block);
cloned_block->GetLabel()->SetResultId(result_id_map.at(cloned_block->id()));
fuzzerutil::UpdateModuleIdBound(ir_context, cloned_block->id());
for (auto& inlined_instruction : *cloned_block) {
AdaptInlinedInstruction(result_id_map, ir_context, &inlined_instruction);
}
}
opt::BasicBlock* block_containing_function_call =
ir_context->get_instr_block(function_call_instruction);
assert(((new_return_block_id == 0) ==
called_function->entry()->terminator()->IsReturn()) &&
"We should have found a return block unless the function being "
"inlined returns in its first block.");
if (new_return_block_id != 0) {
// Rewrite any OpPhi instructions in the successor block so that they refer
// to the new return block instead of the block that originally contained
// the function call.
ir_context->get_def_use_mgr()->ForEachUse(
block_containing_function_call->id(),
[ir_context, new_return_block_id, successor_block](
opt::Instruction* use_instruction, uint32_t operand_index) {
if (use_instruction->opcode() == SpvOpPhi &&
ir_context->get_instr_block(use_instruction) == successor_block) {
use_instruction->SetOperand(operand_index, {new_return_block_id});
}
});
}
// Removes the function call instruction and its block termination instruction
// from |caller_function|.
ir_context->KillInst(block_containing_function_call->terminator());
ir_context->KillInst(function_call_instruction);
// Since the SPIR-V module has changed, no analyses must be validated.
ir_context->InvalidateAnalysesExceptFor(
opt::IRContext::Analysis::kAnalysisNone);
}
protobufs::Transformation TransformationInlineFunction::ToMessage() const {
protobufs::Transformation result;
*result.mutable_inline_function() = message_;
return result;
}
bool TransformationInlineFunction::IsSuitableForInlining(
opt::IRContext* ir_context, opt::Instruction* function_call_instruction) {
// |function_call_instruction| must be defined and must be an OpFunctionCall
// instruction.
if (!function_call_instruction ||
function_call_instruction->opcode() != SpvOpFunctionCall) {
return false;
}
// If |function_call_instruction| return type is void, then
// |function_call_instruction| must not have uses.
if (ir_context->get_type_mgr()
->GetType(function_call_instruction->type_id())
->AsVoid() &&
ir_context->get_def_use_mgr()->NumUses(function_call_instruction) != 0) {
return false;
}
// |called_function| must not have an early return.
auto called_function = fuzzerutil::FindFunction(
ir_context, function_call_instruction->GetSingleWordInOperand(0));
if (called_function->HasEarlyReturn()) {
return false;
}
// |called_function| must not use OpKill or OpUnreachable.
if (fuzzerutil::FunctionContainsOpKillOrUnreachable(*called_function)) {
return false;
}
return true;
}
void TransformationInlineFunction::AdaptInlinedInstruction(
const std::map<uint32_t, uint32_t>& result_id_map,
opt::IRContext* ir_context,
opt::Instruction* instruction_to_be_inlined) const {
auto* function_call_instruction =
ir_context->get_def_use_mgr()->GetDef(message_.function_call_id());
auto* called_function = fuzzerutil::FindFunction(
ir_context, function_call_instruction->GetSingleWordInOperand(0));
const auto* function_call_block =
ir_context->get_instr_block(function_call_instruction);
assert(function_call_block && "OpFunctionCall must belong to some block");
// Replaces the operand ids with their mapped result ids.
instruction_to_be_inlined->ForEachInId(
[called_function, function_call_instruction, &result_id_map,
function_call_block](uint32_t* id) {
// We are not inlining the entry block of the |called_function|.
//
// We must check this condition first since we can't use the fresh id
// from |result_id_map| even if it has one. This is because that fresh
// id will never be added to the module since entry blocks are not
// inlined.
if (*id == called_function->entry()->id()) {
*id = function_call_block->id();
return;
}
// If |id| is mapped, then set it to its mapped value.
if (result_id_map.count(*id)) {
*id = result_id_map.at(*id);
return;
}
uint32_t parameter_index = 0;
called_function->ForEachParam(
[id, function_call_instruction,
&parameter_index](opt::Instruction* parameter_instruction) {
// If the id is a function parameter, then set it to the
// parameter value passed in the function call instruction.
if (*id == parameter_instruction->result_id()) {
// We do + 1 because the first in-operand for OpFunctionCall is
// the function id that is being called.
*id = function_call_instruction->GetSingleWordInOperand(
parameter_index + 1);
}
parameter_index++;
});
});
// If |instruction_to_be_inlined| has result id, then set it to its mapped
// value.
if (instruction_to_be_inlined->HasResultId()) {
assert(result_id_map.count(instruction_to_be_inlined->result_id()) &&
"Result id must be mapped to a fresh id.");
instruction_to_be_inlined->SetResultId(
result_id_map.at(instruction_to_be_inlined->result_id()));
fuzzerutil::UpdateModuleIdBound(ir_context,
instruction_to_be_inlined->result_id());
}
// The return instruction will be changed into an OpBranch to the basic
// block that follows the block containing the function call.
if (spvOpcodeIsReturn(instruction_to_be_inlined->opcode())) {
uint32_t successor_block_id =
ir_context->get_instr_block(function_call_instruction)
->terminator()
->GetSingleWordInOperand(0);
switch (instruction_to_be_inlined->opcode()) {
case SpvOpReturn:
instruction_to_be_inlined->AddOperand(
{SPV_OPERAND_TYPE_ID, {successor_block_id}});
break;
case SpvOpReturnValue: {
instruction_to_be_inlined->InsertBefore(MakeUnique<opt::Instruction>(
ir_context, SpvOpCopyObject, function_call_instruction->type_id(),
function_call_instruction->result_id(),
opt::Instruction::OperandList(
{{SPV_OPERAND_TYPE_ID,
{instruction_to_be_inlined->GetSingleWordOperand(0)}}})));
instruction_to_be_inlined->SetInOperand(0, {successor_block_id});
break;
}
default:
break;
}
instruction_to_be_inlined->SetOpcode(SpvOpBranch);
}
}
std::unordered_set<uint32_t> TransformationInlineFunction::GetFreshIds() const {
std::unordered_set<uint32_t> result;
for (auto& pair : message_.result_id_map()) {
result.insert(pair.second());
}
return result;
}
} // namespace fuzz
} // namespace spvtools