| 1 |
// Copyright (c) 2020 André Perez Maselco |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
#include "source/fuzz/transformation_inline_function.h" |
| 16 |
|
| 17 |
#include "source/fuzz/fuzzer_util.h" |
| 18 |
#include "source/fuzz/instruction_descriptor.h" |
| 19 |
|
| 20 |
namespace spvtools { |
| 21 |
namespace fuzz { |
| 22 |
|
| 23 |
TransformationInlineFunction::TransformationInlineFunction( |
| 24 |
const spvtools::fuzz::protobufs::TransformationInlineFunction& message) |
| 25 |
: message_(message) {} |
| 26 |
|
| 27 |
TransformationInlineFunction::TransformationInlineFunction( |
| 28 |
uint32_t function_call_id, |
| 29 |
const std::map<uint32_t, uint32_t>& result_id_map) { |
| 30 |
message_.set_function_call_id(function_call_id); |
| 31 |
*message_.mutable_result_id_map() = |
| 32 |
fuzzerutil::MapToRepeatedUInt32Pair(result_id_map); |
| 33 |
} |
| 34 |
|
| 35 |
bool TransformationInlineFunction::IsApplicable( |
| 36 |
opt::IRContext* ir_context, |
| 37 |
const TransformationContext& transformation_context) const { |
| 38 |
// The values in the |message_.result_id_map| must be all fresh and all |
| 39 |
// distinct. |
| 40 |
const auto result_id_map = |
| 41 |
fuzzerutil::RepeatedUInt32PairToMap(message_.result_id_map()); |
| 42 |
std::set<uint32_t> ids_used_by_this_transformation; |
| 43 |
for (auto& pair : result_id_map) { |
| 44 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 45 |
pair.second, ir_context, &ids_used_by_this_transformation)) { |
| 46 |
return false; |
| 47 |
} |
| 48 |
} |
| 49 |
|
| 50 |
// |function_call_instruction| must be suitable for inlining. |
| 51 |
auto* function_call_instruction = |
| 52 |
ir_context->get_def_use_mgr()->GetDef(message_.function_call_id()); |
| 53 |
if (!IsSuitableForInlining(ir_context, function_call_instruction)) { |
| 54 |
return false; |
| 55 |
} |
| 56 |
|
| 57 |
// |function_call_instruction| must be the penultimate instruction in its |
| 58 |
// block and its block termination instruction must be an OpBranch. This |
| 59 |
// avoids the case where the penultimate instruction is an OpLoopMerge, which |
| 60 |
// would make the back-edge block not branch to the loop header. |
| 61 |
auto* function_call_instruction_block = |
| 62 |
ir_context->get_instr_block(function_call_instruction); |
| 63 |
if (function_call_instruction != |
| 64 |
&*--function_call_instruction_block->tail() || |
| 65 |
function_call_instruction_block->terminator()->opcode() != SpvOpBranch) { |
| 66 |
return false; |
| 67 |
} |
| 68 |
|
| 69 |
auto* called_function = fuzzerutil::FindFunction( |
| 70 |
ir_context, function_call_instruction->GetSingleWordInOperand(0)); |
| 71 |
for (auto& block : *called_function) { |
| 72 |
// Since the entry block label will not be inlined, only the remaining |
| 73 |
// labels must have a corresponding value in the map. |
| 74 |
if (&block != &*called_function->entry() && |
| 75 |
!result_id_map.count(block.id()) && |
| 76 |
!transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| 77 |
return false; |
| 78 |
} |
| 79 |
|
| 80 |
// |result_id_map| must have an entry for every result id in the called |
| 81 |
// function. |
| 82 |
for (auto& instruction : block) { |
| 83 |
// If |instruction| has result id, then it must have a mapped id in |
| 84 |
// |result_id_map|. |
| 85 |
if (instruction.HasResultId() && |
| 86 |
!result_id_map.count(instruction.result_id()) && |
| 87 |
!transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| 88 |
return false; |
| 89 |
} |
| 90 |
} |
| 91 |
} |
| 92 |
|
| 93 |
// |result_id_map| must not contain an entry for any parameter of the function |
| 94 |
// that is being inlined. |
| 95 |
bool found_entry_for_parameter = false; |
| 96 |
called_function->ForEachParam( |
| 97 |
[&result_id_map, &found_entry_for_parameter](opt::Instruction* param) { |
| 98 |
if (result_id_map.count(param->result_id())) { |
| 99 |
found_entry_for_parameter = true; |
| 100 |
} |
| 101 |
}); |
| 102 |
return !found_entry_for_parameter; |
| 103 |
} |
| 104 |
|
| 105 |
void TransformationInlineFunction::Apply( |
| 106 |
opt::IRContext* ir_context, |
| 107 |
TransformationContext* transformation_context) const { |
| 108 |
auto* function_call_instruction = |
| 109 |
ir_context->get_def_use_mgr()->GetDef(message_.function_call_id()); |
| 110 |
auto* caller_function = |
| 111 |
ir_context->get_instr_block(function_call_instruction)->GetParent(); |
| 112 |
auto* called_function = fuzzerutil::FindFunction( |
| 113 |
ir_context, function_call_instruction->GetSingleWordInOperand(0)); |
| 114 |
std::map<uint32_t, uint32_t> result_id_map = |
| 115 |
fuzzerutil::RepeatedUInt32PairToMap(message_.result_id_map()); |
| 116 |
|
| 117 |
// If there are gaps in the result id map, fill them using overflow ids. |
| 118 |
for (auto& block : *called_function) { |
| 119 |
if (&block != &*called_function->entry() && |
| 120 |
!result_id_map.count(block.id())) { |
| 121 |
result_id_map.insert( |
| 122 |
{block.id(), |
| 123 |
transformation_context->GetOverflowIdSource()->GetNextOverflowId()}); |
| 124 |
} |
| 125 |
for (auto& instruction : block) { |
| 126 |
// If |instruction| has result id, then it must have a mapped id in |
| 127 |
// |result_id_map|. |
| 128 |
if (instruction.HasResultId() && |
| 129 |
!result_id_map.count(instruction.result_id())) { |
| 130 |
result_id_map.insert({instruction.result_id(), |
| 131 |
transformation_context->GetOverflowIdSource() |
| 132 |
->GetNextOverflowId()}); |
| 133 |
} |
| 134 |
} |
| 135 |
} |
| 136 |
|
| 137 |
auto* successor_block = ir_context->cfg()->block( |
| 138 |
ir_context->get_instr_block(function_call_instruction) |
| 139 |
->terminator() |
| 140 |
->GetSingleWordInOperand(0)); |
| 141 |
|
| 142 |
// Inline the |called_function| entry block. |
| 143 |
for (auto& entry_block_instruction : *called_function->entry()) { |
| 144 |
opt::Instruction* inlined_instruction; |
| 145 |
|
| 146 |
if (entry_block_instruction.opcode() == SpvOpVariable) { |
| 147 |
// All OpVariable instructions in a function must be in the first block |
| 148 |
// in the function. |
| 149 |
inlined_instruction = caller_function->begin()->begin()->InsertBefore( |
| 150 |
std::unique_ptr<opt::Instruction>( |
| 151 |
entry_block_instruction.Clone(ir_context))); |
| 152 |
} else { |
| 153 |
inlined_instruction = function_call_instruction->InsertBefore( |
| 154 |
std::unique_ptr<opt::Instruction>( |
| 155 |
entry_block_instruction.Clone(ir_context))); |
| 156 |
} |
| 157 |
|
| 158 |
AdaptInlinedInstruction(result_id_map, ir_context, inlined_instruction); |
| 159 |
} |
| 160 |
|
| 161 |
// If the function call's successor block contains OpPhi instructions that |
| 162 |
// refer to the block containing the call then these will need to be rewritten |
| 163 |
// to instead refer to the block associated with "returning" from the inlined |
| 164 |
// function, as this block will be the predecessor of what used to be the |
| 165 |
// function call's successor block. We look out for this block. |
| 166 |
uint32_t new_return_block_id = 0; |
| 167 |
|
| 168 |
// Inline the |called_function| non-entry blocks. |
| 169 |
for (auto& block : *called_function) { |
| 170 |
if (&block == &*called_function->entry()) { |
| 171 |
continue; |
| 172 |
} |
| 173 |
|
| 174 |
// Check whether this is the function's return block. Take note if it is, |
| 175 |
// so that OpPhi instructions in the successor of the original function call |
| 176 |
// block can be re-written. |
| 177 |
if (block.terminator()->IsReturn()) { |
| 178 |
assert(new_return_block_id == 0 && |
| 179 |
"There should be only one return block."); |
| 180 |
new_return_block_id = result_id_map.at(block.id()); |
| 181 |
} |
| 182 |
|
| 183 |
auto* cloned_block = block.Clone(ir_context); |
| 184 |
cloned_block = caller_function->InsertBasicBlockBefore( |
| 185 |
std::unique_ptr<opt::BasicBlock>(cloned_block), successor_block); |
| 186 |
cloned_block->SetParent(caller_function); |
| 187 |
cloned_block->GetLabel()->SetResultId(result_id_map.at(cloned_block->id())); |
| 188 |
fuzzerutil::UpdateModuleIdBound(ir_context, cloned_block->id()); |
| 189 |
|
| 190 |
for (auto& inlined_instruction : *cloned_block) { |
| 191 |
AdaptInlinedInstruction(result_id_map, ir_context, &inlined_instruction); |
| 192 |
} |
| 193 |
} |
| 194 |
|
| 195 |
opt::BasicBlock* block_containing_function_call = |
| 196 |
ir_context->get_instr_block(function_call_instruction); |
| 197 |
|
| 198 |
assert(((new_return_block_id == 0) == |
| 199 |
called_function->entry()->terminator()->IsReturn()) && |
| 200 |
"We should have found a return block unless the function being " |
| 201 |
"inlined returns in its first block."); |
| 202 |
if (new_return_block_id != 0) { |
| 203 |
// Rewrite any OpPhi instructions in the successor block so that they refer |
| 204 |
// to the new return block instead of the block that originally contained |
| 205 |
// the function call. |
| 206 |
ir_context->get_def_use_mgr()->ForEachUse( |
| 207 |
block_containing_function_call->id(), |
| 208 |
[ir_context, new_return_block_id, successor_block]( |
| 209 |
opt::Instruction* use_instruction, uint32_t operand_index) { |
| 210 |
if (use_instruction->opcode() == SpvOpPhi && |
| 211 |
ir_context->get_instr_block(use_instruction) == successor_block) { |
| 212 |
use_instruction->SetOperand(operand_index, {new_return_block_id}); |
| 213 |
} |
| 214 |
}); |
| 215 |
} |
| 216 |
|
| 217 |
// Removes the function call instruction and its block termination instruction |
| 218 |
// from |caller_function|. |
| 219 |
ir_context->KillInst(block_containing_function_call->terminator()); |
| 220 |
ir_context->KillInst(function_call_instruction); |
| 221 |
|
| 222 |
// Since the SPIR-V module has changed, no analyses must be validated. |
| 223 |
ir_context->InvalidateAnalysesExceptFor( |
| 224 |
opt::IRContext::Analysis::kAnalysisNone); |
| 225 |
} |
| 226 |
|
| 227 |
protobufs::Transformation TransformationInlineFunction::ToMessage() const { |
| 228 |
protobufs::Transformation result; |
| 229 |
*result.mutable_inline_function() = message_; |
| 230 |
return result; |
| 231 |
} |
| 232 |
|
| 233 |
bool TransformationInlineFunction::IsSuitableForInlining( |
| 234 |
opt::IRContext* ir_context, opt::Instruction* function_call_instruction) { |
| 235 |
// |function_call_instruction| must be defined and must be an OpFunctionCall |
| 236 |
// instruction. |
| 237 |
if (!function_call_instruction || |
| 238 |
function_call_instruction->opcode() != SpvOpFunctionCall) { |
| 239 |
return false; |
| 240 |
} |
| 241 |
|
| 242 |
// If |function_call_instruction| return type is void, then |
| 243 |
// |function_call_instruction| must not have uses. |
| 244 |
if (ir_context->get_type_mgr() |
| 245 |
->GetType(function_call_instruction->type_id()) |
| 246 |
->AsVoid() && |
| 247 |
ir_context->get_def_use_mgr()->NumUses(function_call_instruction) != 0) { |
| 248 |
return false; |
| 249 |
} |
| 250 |
|
| 251 |
// |called_function| must not have an early return. |
| 252 |
auto called_function = fuzzerutil::FindFunction( |
| 253 |
ir_context, function_call_instruction->GetSingleWordInOperand(0)); |
| 254 |
if (called_function->HasEarlyReturn()) { |
| 255 |
return false; |
| 256 |
} |
| 257 |
|
| 258 |
// |called_function| must not use OpKill or OpUnreachable. |
| 259 |
if (fuzzerutil::FunctionContainsOpKillOrUnreachable(*called_function)) { |
| 260 |
return false; |
| 261 |
} |
| 262 |
|
| 263 |
return true; |
| 264 |
} |
| 265 |
|
| 266 |
void TransformationInlineFunction::AdaptInlinedInstruction( |
| 267 |
const std::map<uint32_t, uint32_t>& result_id_map, |
| 268 |
opt::IRContext* ir_context, |
| 269 |
opt::Instruction* instruction_to_be_inlined) const { |
| 270 |
auto* function_call_instruction = |
| 271 |
ir_context->get_def_use_mgr()->GetDef(message_.function_call_id()); |
| 272 |
auto* called_function = fuzzerutil::FindFunction( |
| 273 |
ir_context, function_call_instruction->GetSingleWordInOperand(0)); |
| 274 |
|
| 275 |
const auto* function_call_block = |
| 276 |
ir_context->get_instr_block(function_call_instruction); |
| 277 |
assert(function_call_block && "OpFunctionCall must belong to some block"); |
| 278 |
|
| 279 |
// Replaces the operand ids with their mapped result ids. |
| 280 |
instruction_to_be_inlined->ForEachInId( |
| 281 |
[called_function, function_call_instruction, &result_id_map, |
| 282 |
function_call_block](uint32_t* id) { |
| 283 |
// We are not inlining the entry block of the |called_function|. |
| 284 |
// |
| 285 |
// We must check this condition first since we can't use the fresh id |
| 286 |
// from |result_id_map| even if it has one. This is because that fresh |
| 287 |
// id will never be added to the module since entry blocks are not |
| 288 |
// inlined. |
| 289 |
if (*id == called_function->entry()->id()) { |
| 290 |
*id = function_call_block->id(); |
| 291 |
return; |
| 292 |
} |
| 293 |
|
| 294 |
// If |id| is mapped, then set it to its mapped value. |
| 295 |
if (result_id_map.count(*id)) { |
| 296 |
*id = result_id_map.at(*id); |
| 297 |
return; |
| 298 |
} |
| 299 |
|
| 300 |
uint32_t parameter_index = 0; |
| 301 |
called_function->ForEachParam( |
| 302 |
[id, function_call_instruction, |
| 303 |
¶meter_index](opt::Instruction* parameter_instruction) { |
| 304 |
// If the id is a function parameter, then set it to the |
| 305 |
// parameter value passed in the function call instruction. |
| 306 |
if (*id == parameter_instruction->result_id()) { |
| 307 |
// We do + 1 because the first in-operand for OpFunctionCall is |
| 308 |
// the function id that is being called. |
| 309 |
*id = function_call_instruction->GetSingleWordInOperand( |
| 310 |
parameter_index + 1); |
| 311 |
} |
| 312 |
parameter_index++; |
| 313 |
}); |
| 314 |
}); |
| 315 |
|
| 316 |
// If |instruction_to_be_inlined| has result id, then set it to its mapped |
| 317 |
// value. |
| 318 |
if (instruction_to_be_inlined->HasResultId()) { |
| 319 |
assert(result_id_map.count(instruction_to_be_inlined->result_id()) && |
| 320 |
"Result id must be mapped to a fresh id."); |
| 321 |
instruction_to_be_inlined->SetResultId( |
| 322 |
result_id_map.at(instruction_to_be_inlined->result_id())); |
| 323 |
fuzzerutil::UpdateModuleIdBound(ir_context, |
| 324 |
instruction_to_be_inlined->result_id()); |
| 325 |
} |
| 326 |
|
| 327 |
// The return instruction will be changed into an OpBranch to the basic |
| 328 |
// block that follows the block containing the function call. |
| 329 |
if (spvOpcodeIsReturn(instruction_to_be_inlined->opcode())) { |
| 330 |
uint32_t successor_block_id = |
| 331 |
ir_context->get_instr_block(function_call_instruction) |
| 332 |
->terminator() |
| 333 |
->GetSingleWordInOperand(0); |
| 334 |
switch (instruction_to_be_inlined->opcode()) { |
| 335 |
case SpvOpReturn: |
| 336 |
instruction_to_be_inlined->AddOperand( |
| 337 |
{SPV_OPERAND_TYPE_ID, {successor_block_id}}); |
| 338 |
break; |
| 339 |
case SpvOpReturnValue: { |
| 340 |
instruction_to_be_inlined->InsertBefore(MakeUnique<opt::Instruction>( |
| 341 |
ir_context, SpvOpCopyObject, function_call_instruction->type_id(), |
| 342 |
function_call_instruction->result_id(), |
| 343 |
opt::Instruction::OperandList( |
| 344 |
{{SPV_OPERAND_TYPE_ID, |
| 345 |
{instruction_to_be_inlined->GetSingleWordOperand(0)}}}))); |
| 346 |
instruction_to_be_inlined->SetInOperand(0, {successor_block_id}); |
| 347 |
break; |
| 348 |
} |
| 349 |
default: |
| 350 |
break; |
| 351 |
} |
| 352 |
instruction_to_be_inlined->SetOpcode(SpvOpBranch); |
| 353 |
} |
| 354 |
} |
| 355 |
|
| 356 |
std::unordered_set<uint32_t> TransformationInlineFunction::GetFreshIds() const { |
| 357 |
std::unordered_set<uint32_t> result; |
| 358 |
for (auto& pair : message_.result_id_map()) { |
| 359 |
result.insert(pair.second()); |
| 360 |
} |
| 361 |
return result; |
| 362 |
} |
| 363 |
|
| 364 |
} // namespace fuzz |
| 365 |
} // namespace spvtools |