| 1 |
// Copyright (c) 2019 Google LLC |
| 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_outline_function.h" |
| 16 |
|
| 17 |
#include <set> |
| 18 |
|
| 19 |
#include "source/fuzz/fuzzer_util.h" |
| 20 |
|
| 21 |
namespace spvtools { |
| 22 |
namespace fuzz { |
| 23 |
|
| 24 |
TransformationOutlineFunction::TransformationOutlineFunction( |
| 25 |
const spvtools::fuzz::protobufs::TransformationOutlineFunction& message) |
| 26 |
: message_(message) {} |
| 27 |
|
| 28 |
TransformationOutlineFunction::TransformationOutlineFunction( |
| 29 |
uint32_t entry_block, uint32_t exit_block, |
| 30 |
uint32_t new_function_struct_return_type_id, uint32_t new_function_type_id, |
| 31 |
uint32_t new_function_id, uint32_t new_function_region_entry_block, |
| 32 |
uint32_t new_caller_result_id, uint32_t new_callee_result_id, |
| 33 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id, |
| 34 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id) { |
| 35 |
message_.set_entry_block(entry_block); |
| 36 |
message_.set_exit_block(exit_block); |
| 37 |
message_.set_new_function_struct_return_type_id( |
| 38 |
new_function_struct_return_type_id); |
| 39 |
message_.set_new_function_type_id(new_function_type_id); |
| 40 |
message_.set_new_function_id(new_function_id); |
| 41 |
message_.set_new_function_region_entry_block(new_function_region_entry_block); |
| 42 |
message_.set_new_caller_result_id(new_caller_result_id); |
| 43 |
message_.set_new_callee_result_id(new_callee_result_id); |
| 44 |
*message_.mutable_input_id_to_fresh_id() = |
| 45 |
fuzzerutil::MapToRepeatedUInt32Pair(input_id_to_fresh_id); |
| 46 |
*message_.mutable_output_id_to_fresh_id() = |
| 47 |
fuzzerutil::MapToRepeatedUInt32Pair(output_id_to_fresh_id); |
| 48 |
} |
| 49 |
|
| 50 |
bool TransformationOutlineFunction::IsApplicable( |
| 51 |
opt::IRContext* ir_context, |
| 52 |
const TransformationContext& transformation_context) const { |
| 53 |
std::set<uint32_t> ids_used_by_this_transformation; |
| 54 |
|
| 55 |
// The various new ids used by the transformation must be fresh and distinct. |
| 56 |
|
| 57 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 58 |
message_.new_function_struct_return_type_id(), ir_context, |
| 59 |
&ids_used_by_this_transformation)) { |
| 60 |
return false; |
| 61 |
} |
| 62 |
|
| 63 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 64 |
message_.new_function_type_id(), ir_context, |
| 65 |
&ids_used_by_this_transformation)) { |
| 66 |
return false; |
| 67 |
} |
| 68 |
|
| 69 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 70 |
message_.new_function_id(), ir_context, |
| 71 |
&ids_used_by_this_transformation)) { |
| 72 |
return false; |
| 73 |
} |
| 74 |
|
| 75 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 76 |
message_.new_function_region_entry_block(), ir_context, |
| 77 |
&ids_used_by_this_transformation)) { |
| 78 |
return false; |
| 79 |
} |
| 80 |
|
| 81 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 82 |
message_.new_caller_result_id(), ir_context, |
| 83 |
&ids_used_by_this_transformation)) { |
| 84 |
return false; |
| 85 |
} |
| 86 |
|
| 87 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 88 |
message_.new_callee_result_id(), ir_context, |
| 89 |
&ids_used_by_this_transformation)) { |
| 90 |
return false; |
| 91 |
} |
| 92 |
|
| 93 |
for (auto& pair : message_.input_id_to_fresh_id()) { |
| 94 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 95 |
pair.second(), ir_context, &ids_used_by_this_transformation)) { |
| 96 |
return false; |
| 97 |
} |
| 98 |
} |
| 99 |
|
| 100 |
for (auto& pair : message_.output_id_to_fresh_id()) { |
| 101 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 102 |
pair.second(), ir_context, &ids_used_by_this_transformation)) { |
| 103 |
return false; |
| 104 |
} |
| 105 |
} |
| 106 |
|
| 107 |
// The entry and exit block ids must indeed refer to blocks. |
| 108 |
for (auto block_id : {message_.entry_block(), message_.exit_block()}) { |
| 109 |
auto block_label = ir_context->get_def_use_mgr()->GetDef(block_id); |
| 110 |
if (!block_label || block_label->opcode() != SpvOpLabel) { |
| 111 |
return false; |
| 112 |
} |
| 113 |
} |
| 114 |
|
| 115 |
auto entry_block = ir_context->cfg()->block(message_.entry_block()); |
| 116 |
auto exit_block = ir_context->cfg()->block(message_.exit_block()); |
| 117 |
|
| 118 |
// The entry block cannot start with OpVariable - this would mean that |
| 119 |
// outlining would remove a variable from the function containing the region |
| 120 |
// being outlined. |
| 121 |
if (entry_block->begin()->opcode() == SpvOpVariable) { |
| 122 |
return false; |
| 123 |
} |
| 124 |
|
| 125 |
// For simplicity, we do not allow the entry block to be a loop header. |
| 126 |
if (entry_block->GetLoopMergeInst()) { |
| 127 |
return false; |
| 128 |
} |
| 129 |
|
| 130 |
// For simplicity, we do not allow the exit block to be a merge block or |
| 131 |
// continue target. |
| 132 |
if (fuzzerutil::IsMergeOrContinue(ir_context, exit_block->id())) { |
| 133 |
return false; |
| 134 |
} |
| 135 |
|
| 136 |
// The entry block cannot start with OpPhi. This is to keep the |
| 137 |
// transformation logic simple. (Another transformation to split the OpPhis |
| 138 |
// from a block could be applied to avoid this scenario.) |
| 139 |
if (entry_block->begin()->opcode() == SpvOpPhi) { |
| 140 |
return false; |
| 141 |
} |
| 142 |
|
| 143 |
// The block must be in the same function. |
| 144 |
if (entry_block->GetParent() != exit_block->GetParent()) { |
| 145 |
return false; |
| 146 |
} |
| 147 |
|
| 148 |
// The entry block must dominate the exit block. |
| 149 |
auto dominator_analysis = |
| 150 |
ir_context->GetDominatorAnalysis(entry_block->GetParent()); |
| 151 |
if (!dominator_analysis->Dominates(entry_block, exit_block)) { |
| 152 |
return false; |
| 153 |
} |
| 154 |
|
| 155 |
// The exit block must post-dominate the entry block. |
| 156 |
auto postdominator_analysis = |
| 157 |
ir_context->GetPostDominatorAnalysis(entry_block->GetParent()); |
| 158 |
if (!postdominator_analysis->Dominates(exit_block, entry_block)) { |
| 159 |
return false; |
| 160 |
} |
| 161 |
|
| 162 |
// Find all the blocks dominated by |message_.entry_block| and post-dominated |
| 163 |
// by |message_.exit_block|. |
| 164 |
auto region_set = GetRegionBlocks( |
| 165 |
ir_context, |
| 166 |
entry_block = ir_context->cfg()->block(message_.entry_block()), |
| 167 |
exit_block = ir_context->cfg()->block(message_.exit_block())); |
| 168 |
|
| 169 |
// Check whether |region_set| really is a single-entry single-exit region, and |
| 170 |
// also check whether structured control flow constructs and their merge |
| 171 |
// and continue constructs are either wholly in or wholly out of the region - |
| 172 |
// e.g. avoid the situation where the region contains the head of a loop but |
| 173 |
// not the loop's continue construct. |
| 174 |
// |
| 175 |
// This is achieved by going through every block in the function that contains |
| 176 |
// the region. |
| 177 |
for (auto& block : *entry_block->GetParent()) { |
| 178 |
if (&block == exit_block) { |
| 179 |
// It is OK (and typically expected) for the exit block of the region to |
| 180 |
// have successors outside the region. |
| 181 |
// |
| 182 |
// It is also OK for the exit block to head a selection construct: the |
| 183 |
// block containing the call to the outlined function will end up heading |
| 184 |
// this construct if outlining takes place. However, it is not OK for |
| 185 |
// the exit block to head a loop construct. |
| 186 |
if (block.GetLoopMergeInst()) { |
| 187 |
return false; |
| 188 |
} |
| 189 |
continue; |
| 190 |
} |
| 191 |
|
| 192 |
if (region_set.count(&block) != 0) { |
| 193 |
// The block is in the region and is not the region's exit block. Let's |
| 194 |
// see whether all of the block's successors are in the region. If they |
| 195 |
// are not, the region is not single-entry single-exit. |
| 196 |
bool all_successors_in_region = true; |
| 197 |
block.WhileEachSuccessorLabel([&all_successors_in_region, ir_context, |
| 198 |
®ion_set](uint32_t successor) -> bool { |
| 199 |
if (region_set.count(ir_context->cfg()->block(successor)) == 0) { |
| 200 |
all_successors_in_region = false; |
| 201 |
return false; |
| 202 |
} |
| 203 |
return true; |
| 204 |
}); |
| 205 |
if (!all_successors_in_region) { |
| 206 |
return false; |
| 207 |
} |
| 208 |
} |
| 209 |
|
| 210 |
if (auto merge = block.GetMergeInst()) { |
| 211 |
// The block is a loop or selection header -- the header and its |
| 212 |
// associated merge block had better both be in the region or both be |
| 213 |
// outside the region. |
| 214 |
auto merge_block = |
| 215 |
ir_context->cfg()->block(merge->GetSingleWordOperand(0)); |
| 216 |
if (region_set.count(&block) != region_set.count(merge_block)) { |
| 217 |
return false; |
| 218 |
} |
| 219 |
} |
| 220 |
|
| 221 |
if (auto loop_merge = block.GetLoopMergeInst()) { |
| 222 |
// Similar to the above, but for the continue target of a loop. |
| 223 |
auto continue_target = |
| 224 |
ir_context->cfg()->block(loop_merge->GetSingleWordOperand(1)); |
| 225 |
if (continue_target != exit_block && |
| 226 |
region_set.count(&block) != region_set.count(continue_target)) { |
| 227 |
return false; |
| 228 |
} |
| 229 |
} |
| 230 |
} |
| 231 |
|
| 232 |
// For each region input id, i.e. every id defined outside the region but |
| 233 |
// used inside the region, ... |
| 234 |
auto input_id_to_fresh_id_map = |
| 235 |
fuzzerutil::RepeatedUInt32PairToMap(message_.input_id_to_fresh_id()); |
| 236 |
for (auto id : GetRegionInputIds(ir_context, region_set, exit_block)) { |
| 237 |
// There needs to be a corresponding fresh id to be used as a function |
| 238 |
// parameter, or overflow ids need to be available. |
| 239 |
if (input_id_to_fresh_id_map.count(id) == 0 && |
| 240 |
!transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| 241 |
return false; |
| 242 |
} |
| 243 |
// Furthermore, if the input id has pointer type it must be an OpVariable |
| 244 |
// or OpFunctionParameter. |
| 245 |
auto input_id_inst = ir_context->get_def_use_mgr()->GetDef(id); |
| 246 |
if (ir_context->get_def_use_mgr() |
| 247 |
->GetDef(input_id_inst->type_id()) |
| 248 |
->opcode() == SpvOpTypePointer) { |
| 249 |
switch (input_id_inst->opcode()) { |
| 250 |
case SpvOpFunctionParameter: |
| 251 |
case SpvOpVariable: |
| 252 |
// These are OK. |
| 253 |
break; |
| 254 |
default: |
| 255 |
// Anything else is not OK. |
| 256 |
return false; |
| 257 |
} |
| 258 |
} |
| 259 |
} |
| 260 |
|
| 261 |
// For each region output id -- i.e. every id defined inside the region but |
| 262 |
// used outside the region, ... |
| 263 |
auto output_id_to_fresh_id_map = |
| 264 |
fuzzerutil::RepeatedUInt32PairToMap(message_.output_id_to_fresh_id()); |
| 265 |
for (auto id : GetRegionOutputIds(ir_context, region_set, exit_block)) { |
| 266 |
if ( |
| 267 |
// ... there needs to be a corresponding fresh id that can hold the |
| 268 |
// value for this id computed in the outlined function (or overflow ids |
| 269 |
// must be available), and ... |
| 270 |
(output_id_to_fresh_id_map.count(id) == 0 && |
| 271 |
!transformation_context.GetOverflowIdSource()->HasOverflowIds()) |
| 272 |
// ... the output id must not have pointer type (to avoid creating a |
| 273 |
// struct with pointer members to pass data out of the outlined |
| 274 |
// function) |
| 275 |
|| ir_context->get_def_use_mgr() |
| 276 |
->GetDef(fuzzerutil::GetTypeId(ir_context, id)) |
| 277 |
->opcode() == SpvOpTypePointer) { |
| 278 |
return false; |
| 279 |
} |
| 280 |
} |
| 281 |
|
| 282 |
return true; |
| 283 |
} |
| 284 |
|
| 285 |
void TransformationOutlineFunction::Apply( |
| 286 |
opt::IRContext* ir_context, |
| 287 |
TransformationContext* transformation_context) const { |
| 288 |
// The entry block for the region before outlining. |
| 289 |
auto original_region_entry_block = |
| 290 |
ir_context->cfg()->block(message_.entry_block()); |
| 291 |
|
| 292 |
// The exit block for the region before outlining. |
| 293 |
auto original_region_exit_block = |
| 294 |
ir_context->cfg()->block(message_.exit_block()); |
| 295 |
|
| 296 |
// The single-entry single-exit region defined by |message_.entry_block| and |
| 297 |
// |message_.exit_block|. |
| 298 |
std::set<opt::BasicBlock*> region_blocks = GetRegionBlocks( |
| 299 |
ir_context, original_region_entry_block, original_region_exit_block); |
| 300 |
|
| 301 |
// Input and output ids for the region being outlined. |
| 302 |
std::vector<uint32_t> region_input_ids = |
| 303 |
GetRegionInputIds(ir_context, region_blocks, original_region_exit_block); |
| 304 |
std::vector<uint32_t> region_output_ids = |
| 305 |
GetRegionOutputIds(ir_context, region_blocks, original_region_exit_block); |
| 306 |
|
| 307 |
// Maps from input and output ids to fresh ids. |
| 308 |
auto input_id_to_fresh_id_map = |
| 309 |
fuzzerutil::RepeatedUInt32PairToMap(message_.input_id_to_fresh_id()); |
| 310 |
auto output_id_to_fresh_id_map = |
| 311 |
fuzzerutil::RepeatedUInt32PairToMap(message_.output_id_to_fresh_id()); |
| 312 |
|
| 313 |
// Use overflow ids to augment these maps at any locations where fresh ids are |
| 314 |
// required but not provided. |
| 315 |
for (uint32_t id : region_input_ids) { |
| 316 |
if (input_id_to_fresh_id_map.count(id) == 0) { |
| 317 |
input_id_to_fresh_id_map.insert( |
| 318 |
{id, |
| 319 |
transformation_context->GetOverflowIdSource()->GetNextOverflowId()}); |
| 320 |
} |
| 321 |
} |
| 322 |
for (uint32_t id : region_output_ids) { |
| 323 |
if (output_id_to_fresh_id_map.count(id) == 0) { |
| 324 |
output_id_to_fresh_id_map.insert( |
| 325 |
{id, |
| 326 |
transformation_context->GetOverflowIdSource()->GetNextOverflowId()}); |
| 327 |
} |
| 328 |
} |
| 329 |
|
| 330 |
UpdateModuleIdBoundForFreshIds(ir_context, input_id_to_fresh_id_map, |
| 331 |
output_id_to_fresh_id_map); |
| 332 |
|
| 333 |
// Construct a map that associates each output id with its type id. |
| 334 |
std::map<uint32_t, uint32_t> output_id_to_type_id; |
| 335 |
for (uint32_t output_id : region_output_ids) { |
| 336 |
output_id_to_type_id[output_id] = |
| 337 |
ir_context->get_def_use_mgr()->GetDef(output_id)->type_id(); |
| 338 |
} |
| 339 |
|
| 340 |
// The region will be collapsed to a single block that calls a function |
| 341 |
// containing the outlined region. This block needs to end with whatever |
| 342 |
// the exit block of the region ended with before outlining. We thus clone |
| 343 |
// the terminator of the region's exit block, and the merge instruction for |
| 344 |
// the block if there is one, so that we can append them to the end of the |
| 345 |
// collapsed block later. |
| 346 |
std::unique_ptr<opt::Instruction> cloned_exit_block_terminator = |
| 347 |
std::unique_ptr<opt::Instruction>( |
| 348 |
original_region_exit_block->terminator()->Clone(ir_context)); |
| 349 |
std::unique_ptr<opt::Instruction> cloned_exit_block_merge = |
| 350 |
original_region_exit_block->GetMergeInst() |
| 351 |
? std::unique_ptr<opt::Instruction>( |
| 352 |
original_region_exit_block->GetMergeInst()->Clone(ir_context)) |
| 353 |
: nullptr; |
| 354 |
|
| 355 |
// Make a function prototype for the outlined function, which involves |
| 356 |
// figuring out its required type. |
| 357 |
std::unique_ptr<opt::Function> outlined_function = PrepareFunctionPrototype( |
| 358 |
region_input_ids, region_output_ids, input_id_to_fresh_id_map, ir_context, |
| 359 |
transformation_context); |
| 360 |
|
| 361 |
// Adapt the region to be outlined so that its input ids are replaced with the |
| 362 |
// ids of the outlined function's input parameters, and so that output ids |
| 363 |
// are similarly remapped. |
| 364 |
RemapInputAndOutputIdsInRegion( |
| 365 |
ir_context, *original_region_exit_block, region_blocks, region_input_ids, |
| 366 |
region_output_ids, input_id_to_fresh_id_map, output_id_to_fresh_id_map); |
| 367 |
|
| 368 |
// Fill out the body of the outlined function according to the region that is |
| 369 |
// being outlined. |
| 370 |
PopulateOutlinedFunction( |
| 371 |
*original_region_entry_block, *original_region_exit_block, region_blocks, |
| 372 |
region_output_ids, output_id_to_type_id, output_id_to_fresh_id_map, |
| 373 |
ir_context, outlined_function.get()); |
| 374 |
|
| 375 |
// Collapse the region that has been outlined into a function down to a single |
| 376 |
// block that calls said function. |
| 377 |
ShrinkOriginalRegion( |
| 378 |
ir_context, region_blocks, region_input_ids, region_output_ids, |
| 379 |
output_id_to_type_id, outlined_function->type_id(), |
| 380 |
std::move(cloned_exit_block_merge), |
| 381 |
std::move(cloned_exit_block_terminator), original_region_entry_block); |
| 382 |
|
| 383 |
// Add the outlined function to the module. |
| 384 |
const auto* outlined_function_ptr = outlined_function.get(); |
| 385 |
ir_context->module()->AddFunction(std::move(outlined_function)); |
| 386 |
|
| 387 |
// Major surgery has been conducted on the module, so invalidate all analyses. |
| 388 |
ir_context->InvalidateAnalysesExceptFor( |
| 389 |
opt::IRContext::Analysis::kAnalysisNone); |
| 390 |
|
| 391 |
// If the original function was livesafe, the new function should also be |
| 392 |
// livesafe. |
| 393 |
if (transformation_context->GetFactManager()->FunctionIsLivesafe( |
| 394 |
original_region_entry_block->GetParent()->result_id())) { |
| 395 |
transformation_context->GetFactManager()->AddFactFunctionIsLivesafe( |
| 396 |
message_.new_function_id()); |
| 397 |
} |
| 398 |
|
| 399 |
// Record the fact that all blocks in the outlined region are dead if the |
| 400 |
// first block is dead. |
| 401 |
if (transformation_context->GetFactManager()->BlockIsDead( |
| 402 |
original_region_entry_block->id())) { |
| 403 |
transformation_context->GetFactManager()->AddFactBlockIsDead( |
| 404 |
outlined_function_ptr->entry()->id()); |
| 405 |
} |
| 406 |
} |
| 407 |
|
| 408 |
protobufs::Transformation TransformationOutlineFunction::ToMessage() const { |
| 409 |
protobufs::Transformation result; |
| 410 |
*result.mutable_outline_function() = message_; |
| 411 |
return result; |
| 412 |
} |
| 413 |
|
| 414 |
std::vector<uint32_t> TransformationOutlineFunction::GetRegionInputIds( |
| 415 |
opt::IRContext* ir_context, const std::set<opt::BasicBlock*>& region_set, |
| 416 |
opt::BasicBlock* region_exit_block) { |
| 417 |
std::vector<uint32_t> result; |
| 418 |
|
| 419 |
auto enclosing_function = region_exit_block->GetParent(); |
| 420 |
|
| 421 |
// Consider each parameter of the function containing the region. |
| 422 |
enclosing_function->ForEachParam( |
| 423 |
[ir_context, ®ion_set, &result](opt::Instruction* function_parameter) { |
| 424 |
// Consider every use of the parameter. |
| 425 |
ir_context->get_def_use_mgr()->WhileEachUse( |
| 426 |
function_parameter, |
| 427 |
[ir_context, function_parameter, ®ion_set, &result]( |
| 428 |
opt::Instruction* use, uint32_t /*unused*/) { |
| 429 |
// Get the block, if any, in which the parameter is used. |
| 430 |
auto use_block = ir_context->get_instr_block(use); |
| 431 |
// If the use is in a block that lies within the region, the |
| 432 |
// parameter is an input id for the region. |
| 433 |
if (use_block && region_set.count(use_block) != 0) { |
| 434 |
result.push_back(function_parameter->result_id()); |
| 435 |
return false; |
| 436 |
} |
| 437 |
return true; |
| 438 |
}); |
| 439 |
}); |
| 440 |
|
| 441 |
// Consider all definitions in the function that might turn out to be input |
| 442 |
// ids. |
| 443 |
for (auto& block : *enclosing_function) { |
| 444 |
std::vector<opt::Instruction*> candidate_input_ids_for_block; |
| 445 |
if (region_set.count(&block) == 0) { |
| 446 |
// All instructions in blocks outside the region are candidate's for |
| 447 |
// generating input ids. |
| 448 |
for (auto& inst : block) { |
| 449 |
candidate_input_ids_for_block.push_back(&inst); |
| 450 |
} |
| 451 |
} else { |
| 452 |
// Blocks in the region cannot generate input ids. |
| 453 |
continue; |
| 454 |
} |
| 455 |
|
| 456 |
// Consider each candidate input id to check whether it is used in the |
| 457 |
// region. |
| 458 |
for (auto& inst : candidate_input_ids_for_block) { |
| 459 |
ir_context->get_def_use_mgr()->WhileEachUse( |
| 460 |
inst, |
| 461 |
[ir_context, &inst, region_exit_block, ®ion_set, &result]( |
| 462 |
opt::Instruction* use, uint32_t /*unused*/) -> bool { |
| 463 |
// Find the block in which this id use occurs, recording the id as |
| 464 |
// an input id if the block is outside the region, with some |
| 465 |
// exceptions detailed below. |
| 466 |
auto use_block = ir_context->get_instr_block(use); |
| 467 |
|
| 468 |
if (!use_block) { |
| 469 |
// There might be no containing block, e.g. if the use is in a |
| 470 |
// decoration. |
| 471 |
return true; |
| 472 |
} |
| 473 |
|
| 474 |
if (region_set.count(use_block) == 0) { |
| 475 |
// The use is not in the region: this does not make it an input |
| 476 |
// id. |
| 477 |
return true; |
| 478 |
} |
| 479 |
|
| 480 |
if (use_block == region_exit_block && use->IsBlockTerminator()) { |
| 481 |
// We do not regard uses in the exit block terminator as input |
| 482 |
// ids, as this terminator does not get outlined. |
| 483 |
return true; |
| 484 |
} |
| 485 |
|
| 486 |
result.push_back(inst->result_id()); |
| 487 |
return false; |
| 488 |
}); |
| 489 |
} |
| 490 |
} |
| 491 |
return result; |
| 492 |
} |
| 493 |
|
| 494 |
std::vector<uint32_t> TransformationOutlineFunction::GetRegionOutputIds( |
| 495 |
opt::IRContext* ir_context, const std::set<opt::BasicBlock*>& region_set, |
| 496 |
opt::BasicBlock* region_exit_block) { |
| 497 |
std::vector<uint32_t> result; |
| 498 |
|
| 499 |
// Consider each block in the function containing the region. |
| 500 |
for (auto& block : *region_exit_block->GetParent()) { |
| 501 |
if (region_set.count(&block) == 0) { |
| 502 |
// Skip blocks that are not in the region. |
| 503 |
continue; |
| 504 |
} |
| 505 |
// Consider each use of each instruction defined in the block. |
| 506 |
for (auto& inst : block) { |
| 507 |
ir_context->get_def_use_mgr()->WhileEachUse( |
| 508 |
&inst, |
| 509 |
[®ion_set, ir_context, &inst, region_exit_block, &result]( |
| 510 |
opt::Instruction* use, uint32_t /*unused*/) -> bool { |
| 511 |
// Find the block in which this id use occurs, recording the id as |
| 512 |
// an output id if the block is outside the region, with some |
| 513 |
// exceptions detailed below. |
| 514 |
auto use_block = ir_context->get_instr_block(use); |
| 515 |
|
| 516 |
if (!use_block) { |
| 517 |
// There might be no containing block, e.g. if the use is in a |
| 518 |
// decoration. |
| 519 |
return true; |
| 520 |
} |
| 521 |
|
| 522 |
if (region_set.count(use_block) != 0) { |
| 523 |
// The use is in the region. |
| 524 |
if (use_block != region_exit_block || !use->IsBlockTerminator()) { |
| 525 |
// Furthermore, the use is not in the terminator of the region's |
| 526 |
// exit block. |
| 527 |
return true; |
| 528 |
} |
| 529 |
} |
| 530 |
|
| 531 |
result.push_back(inst.result_id()); |
| 532 |
return false; |
| 533 |
}); |
| 534 |
} |
| 535 |
} |
| 536 |
return result; |
| 537 |
} |
| 538 |
|
| 539 |
std::set<opt::BasicBlock*> TransformationOutlineFunction::GetRegionBlocks( |
| 540 |
opt::IRContext* ir_context, opt::BasicBlock* entry_block, |
| 541 |
opt::BasicBlock* exit_block) { |
| 542 |
auto enclosing_function = entry_block->GetParent(); |
| 543 |
auto dominator_analysis = |
| 544 |
ir_context->GetDominatorAnalysis(enclosing_function); |
| 545 |
auto postdominator_analysis = |
| 546 |
ir_context->GetPostDominatorAnalysis(enclosing_function); |
| 547 |
|
| 548 |
std::set<opt::BasicBlock*> result; |
| 549 |
for (auto& block : *enclosing_function) { |
| 550 |
if (dominator_analysis->Dominates(entry_block, &block) && |
| 551 |
postdominator_analysis->Dominates(exit_block, &block)) { |
| 552 |
result.insert(&block); |
| 553 |
} |
| 554 |
} |
| 555 |
return result; |
| 556 |
} |
| 557 |
|
| 558 |
std::unique_ptr<opt::Function> |
| 559 |
TransformationOutlineFunction::PrepareFunctionPrototype( |
| 560 |
const std::vector<uint32_t>& region_input_ids, |
| 561 |
const std::vector<uint32_t>& region_output_ids, |
| 562 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id_map, |
| 563 |
opt::IRContext* ir_context, |
| 564 |
TransformationContext* transformation_context) const { |
| 565 |
uint32_t return_type_id = 0; |
| 566 |
uint32_t function_type_id = 0; |
| 567 |
|
| 568 |
// First, try to find an existing function type that is suitable. This is |
| 569 |
// only possible if the region generates no output ids; if it generates output |
| 570 |
// ids we are going to make a new struct for those, and since that struct does |
| 571 |
// not exist there cannot already be a function type with this struct as its |
| 572 |
// return type. |
| 573 |
if (region_output_ids.empty()) { |
| 574 |
std::vector<uint32_t> return_and_parameter_types; |
| 575 |
opt::analysis::Void void_type; |
| 576 |
return_type_id = ir_context->get_type_mgr()->GetId(&void_type); |
| 577 |
return_and_parameter_types.push_back(return_type_id); |
| 578 |
for (auto id : region_input_ids) { |
| 579 |
return_and_parameter_types.push_back( |
| 580 |
ir_context->get_def_use_mgr()->GetDef(id)->type_id()); |
| 581 |
} |
| 582 |
function_type_id = |
| 583 |
fuzzerutil::FindFunctionType(ir_context, return_and_parameter_types); |
| 584 |
} |
| 585 |
|
| 586 |
// If no existing function type was found, we need to create one. |
| 587 |
if (function_type_id == 0) { |
| 588 |
assert( |
| 589 |
((return_type_id == 0) == !region_output_ids.empty()) && |
| 590 |
"We should only have set the return type if there are no output ids."); |
| 591 |
// If the region generates output ids, we need to make a struct with one |
| 592 |
// field per output id. |
| 593 |
if (!region_output_ids.empty()) { |
| 594 |
opt::Instruction::OperandList struct_member_types; |
| 595 |
for (uint32_t output_id : region_output_ids) { |
| 596 |
auto output_id_type = |
| 597 |
ir_context->get_def_use_mgr()->GetDef(output_id)->type_id(); |
| 598 |
if (ir_context->get_def_use_mgr()->GetDef(output_id_type)->opcode() == |
| 599 |
SpvOpTypeVoid) { |
| 600 |
// We cannot add a void field to a struct. We instead use OpUndef to |
| 601 |
// handle void output ids. |
| 602 |
continue; |
| 603 |
} |
| 604 |
struct_member_types.push_back({SPV_OPERAND_TYPE_ID, {output_id_type}}); |
| 605 |
} |
| 606 |
// Add a new struct type to the module. |
| 607 |
ir_context->module()->AddType(MakeUnique<opt::Instruction>( |
| 608 |
ir_context, SpvOpTypeStruct, 0, |
| 609 |
message_.new_function_struct_return_type_id(), |
| 610 |
std::move(struct_member_types))); |
| 611 |
// The return type for the function is the newly-created struct. |
| 612 |
return_type_id = message_.new_function_struct_return_type_id(); |
| 613 |
} |
| 614 |
assert( |
| 615 |
return_type_id != 0 && |
| 616 |
"We should either have a void return type, or have created a struct."); |
| 617 |
|
| 618 |
// The region's input ids dictate the parameter types to the function. |
| 619 |
opt::Instruction::OperandList function_type_operands; |
| 620 |
function_type_operands.push_back({SPV_OPERAND_TYPE_ID, {return_type_id}}); |
| 621 |
for (auto id : region_input_ids) { |
| 622 |
function_type_operands.push_back( |
| 623 |
{SPV_OPERAND_TYPE_ID, |
| 624 |
{ir_context->get_def_use_mgr()->GetDef(id)->type_id()}}); |
| 625 |
} |
| 626 |
// Add a new function type to the module, and record that this is the type |
| 627 |
// id for the new function. |
| 628 |
ir_context->module()->AddType(MakeUnique<opt::Instruction>( |
| 629 |
ir_context, SpvOpTypeFunction, 0, message_.new_function_type_id(), |
| 630 |
function_type_operands)); |
| 631 |
function_type_id = message_.new_function_type_id(); |
| 632 |
} |
| 633 |
|
| 634 |
// Create a new function with |message_.new_function_id| as the function id, |
| 635 |
// and the return type and function type prepared above. |
| 636 |
std::unique_ptr<opt::Function> outlined_function = |
| 637 |
MakeUnique<opt::Function>(MakeUnique<opt::Instruction>( |
| 638 |
ir_context, SpvOpFunction, return_type_id, message_.new_function_id(), |
| 639 |
opt::Instruction::OperandList( |
| 640 |
{{spv_operand_type_t ::SPV_OPERAND_TYPE_LITERAL_INTEGER, |
| 641 |
{SpvFunctionControlMaskNone}}, |
| 642 |
{spv_operand_type_t::SPV_OPERAND_TYPE_ID, |
| 643 |
{function_type_id}}}))); |
| 644 |
|
| 645 |
// Add one parameter to the function for each input id, using the fresh ids |
| 646 |
// provided in |input_id_to_fresh_id_map|, or overflow ids if needed. |
| 647 |
for (auto id : region_input_ids) { |
| 648 |
uint32_t fresh_id = input_id_to_fresh_id_map.at(id); |
| 649 |
outlined_function->AddParameter(MakeUnique<opt::Instruction>( |
| 650 |
ir_context, SpvOpFunctionParameter, |
| 651 |
ir_context->get_def_use_mgr()->GetDef(id)->type_id(), fresh_id, |
| 652 |
opt::Instruction::OperandList())); |
| 653 |
|
| 654 |
// Analyse the use of the new parameter instruction. |
| 655 |
outlined_function->ForEachParam( |
| 656 |
[fresh_id, ir_context](opt::Instruction* inst) { |
| 657 |
if (inst->result_id() == fresh_id) { |
| 658 |
ir_context->AnalyzeDefUse(inst); |
| 659 |
} |
| 660 |
}); |
| 661 |
|
| 662 |
// If the input id is an irrelevant-valued variable, the same should be true |
| 663 |
// of the corresponding parameter. |
| 664 |
if (transformation_context->GetFactManager()->PointeeValueIsIrrelevant( |
| 665 |
id)) { |
| 666 |
transformation_context->GetFactManager() |
| 667 |
->AddFactValueOfPointeeIsIrrelevant(input_id_to_fresh_id_map.at(id)); |
| 668 |
} |
| 669 |
} |
| 670 |
|
| 671 |
return outlined_function; |
| 672 |
} |
| 673 |
|
| 674 |
void TransformationOutlineFunction::UpdateModuleIdBoundForFreshIds( |
| 675 |
opt::IRContext* ir_context, |
| 676 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id_map, |
| 677 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id_map) const { |
| 678 |
// Enlarge the module's id bound as needed to accommodate the various fresh |
| 679 |
// ids associated with the transformation. |
| 680 |
fuzzerutil::UpdateModuleIdBound( |
| 681 |
ir_context, message_.new_function_struct_return_type_id()); |
| 682 |
fuzzerutil::UpdateModuleIdBound(ir_context, message_.new_function_type_id()); |
| 683 |
fuzzerutil::UpdateModuleIdBound(ir_context, message_.new_function_id()); |
| 684 |
fuzzerutil::UpdateModuleIdBound(ir_context, |
| 685 |
message_.new_function_region_entry_block()); |
| 686 |
fuzzerutil::UpdateModuleIdBound(ir_context, message_.new_caller_result_id()); |
| 687 |
fuzzerutil::UpdateModuleIdBound(ir_context, message_.new_callee_result_id()); |
| 688 |
|
| 689 |
for (auto& entry : input_id_to_fresh_id_map) { |
| 690 |
fuzzerutil::UpdateModuleIdBound(ir_context, entry.second); |
| 691 |
} |
| 692 |
|
| 693 |
for (auto& entry : output_id_to_fresh_id_map) { |
| 694 |
fuzzerutil::UpdateModuleIdBound(ir_context, entry.second); |
| 695 |
} |
| 696 |
} |
| 697 |
|
| 698 |
void TransformationOutlineFunction::RemapInputAndOutputIdsInRegion( |
| 699 |
opt::IRContext* ir_context, |
| 700 |
const opt::BasicBlock& original_region_exit_block, |
| 701 |
const std::set<opt::BasicBlock*>& region_blocks, |
| 702 |
const std::vector<uint32_t>& region_input_ids, |
| 703 |
const std::vector<uint32_t>& region_output_ids, |
| 704 |
const std::map<uint32_t, uint32_t>& input_id_to_fresh_id_map, |
| 705 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id_map) const { |
| 706 |
// Change all uses of input ids inside the region to the corresponding fresh |
| 707 |
// ids that will ultimately be parameters of the outlined function. |
| 708 |
// This is done by considering each region input id in turn. |
| 709 |
for (uint32_t id : region_input_ids) { |
| 710 |
// We then consider each use of the input id. |
| 711 |
ir_context->get_def_use_mgr()->ForEachUse( |
| 712 |
id, [ir_context, id, &input_id_to_fresh_id_map, region_blocks]( |
| 713 |
opt::Instruction* use, uint32_t operand_index) { |
| 714 |
// Find the block in which this use of the input id occurs. |
| 715 |
opt::BasicBlock* use_block = ir_context->get_instr_block(use); |
| 716 |
// We want to rewrite the use id if its block occurs in the outlined |
| 717 |
// region. |
| 718 |
if (region_blocks.count(use_block) != 0) { |
| 719 |
// Rewrite this use of the input id. |
| 720 |
use->SetOperand(operand_index, {input_id_to_fresh_id_map.at(id)}); |
| 721 |
} |
| 722 |
}); |
| 723 |
} |
| 724 |
|
| 725 |
// Change each definition of a region output id to define the corresponding |
| 726 |
// fresh ids that will store intermediate value for the output ids. Also |
| 727 |
// change all uses of the output id located in the outlined region. |
| 728 |
// This is done by considering each region output id in turn. |
| 729 |
for (uint32_t id : region_output_ids) { |
| 730 |
// First consider each use of the output id and update the relevant uses. |
| 731 |
ir_context->get_def_use_mgr()->ForEachUse( |
| 732 |
id, [ir_context, &original_region_exit_block, id, |
| 733 |
&output_id_to_fresh_id_map, |
| 734 |
region_blocks](opt::Instruction* use, uint32_t operand_index) { |
| 735 |
// Find the block in which this use of the output id occurs. |
| 736 |
auto use_block = ir_context->get_instr_block(use); |
| 737 |
// We want to rewrite the use id if its block occurs in the outlined |
| 738 |
// region, with one exception: the terminator of the exit block of |
| 739 |
// the region is going to remain in the original function, so if the |
| 740 |
// use appears in such a terminator instruction we leave it alone. |
| 741 |
if ( |
| 742 |
// The block is in the region ... |
| 743 |
region_blocks.count(use_block) != 0 && |
| 744 |
// ... and the use is not in the terminator instruction of the |
| 745 |
// region's exit block. |
| 746 |
!(use_block == &original_region_exit_block && |
| 747 |
use->IsBlockTerminator())) { |
| 748 |
// Rewrite this use of the output id. |
| 749 |
use->SetOperand(operand_index, {output_id_to_fresh_id_map.at(id)}); |
| 750 |
} |
| 751 |
}); |
| 752 |
|
| 753 |
// Now change the instruction that defines the output id so that it instead |
| 754 |
// defines the corresponding fresh id. We do this after changing all the |
| 755 |
// uses so that the definition of the original id is still registered when |
| 756 |
// we analyse its uses. |
| 757 |
ir_context->get_def_use_mgr()->GetDef(id)->SetResultId( |
| 758 |
output_id_to_fresh_id_map.at(id)); |
| 759 |
} |
| 760 |
} |
| 761 |
|
| 762 |
void TransformationOutlineFunction::PopulateOutlinedFunction( |
| 763 |
const opt::BasicBlock& original_region_entry_block, |
| 764 |
const opt::BasicBlock& original_region_exit_block, |
| 765 |
const std::set<opt::BasicBlock*>& region_blocks, |
| 766 |
const std::vector<uint32_t>& region_output_ids, |
| 767 |
const std::map<uint32_t, uint32_t>& output_id_to_type_id, |
| 768 |
const std::map<uint32_t, uint32_t>& output_id_to_fresh_id_map, |
| 769 |
opt::IRContext* ir_context, opt::Function* outlined_function) const { |
| 770 |
// When we create the exit block for the outlined region, we use this pointer |
| 771 |
// to track of it so that we can manipulate it later. |
| 772 |
opt::BasicBlock* outlined_region_exit_block = nullptr; |
| 773 |
|
| 774 |
// The region entry block in the new function is identical to the entry block |
| 775 |
// of the region being outlined, except that it has |
| 776 |
// |message_.new_function_region_entry_block| as its id. |
| 777 |
std::unique_ptr<opt::BasicBlock> outlined_region_entry_block = |
| 778 |
MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>( |
| 779 |
ir_context, SpvOpLabel, 0, message_.new_function_region_entry_block(), |
| 780 |
opt::Instruction::OperandList())); |
| 781 |
outlined_region_entry_block->SetParent(outlined_function); |
| 782 |
|
| 783 |
if (&original_region_entry_block == &original_region_exit_block) { |
| 784 |
outlined_region_exit_block = outlined_region_entry_block.get(); |
| 785 |
} |
| 786 |
|
| 787 |
for (auto& inst : original_region_entry_block) { |
| 788 |
outlined_region_entry_block->AddInstruction( |
| 789 |
std::unique_ptr<opt::Instruction>(inst.Clone(ir_context))); |
| 790 |
} |
| 791 |
outlined_function->AddBasicBlock(std::move(outlined_region_entry_block)); |
| 792 |
|
| 793 |
// We now go through the single-entry single-exit region defined by the entry |
| 794 |
// and exit blocks, adding clones of all blocks to the new function. |
| 795 |
|
| 796 |
// Consider every block in the enclosing function. |
| 797 |
auto enclosing_function = original_region_entry_block.GetParent(); |
| 798 |
for (auto block_it = enclosing_function->begin(); |
| 799 |
block_it != enclosing_function->end();) { |
| 800 |
// Skip the region's entry block - we already dealt with it above. |
| 801 |
if (region_blocks.count(&*block_it) == 0 || |
| 802 |
&*block_it == &original_region_entry_block) { |
| 803 |
++block_it; |
| 804 |
continue; |
| 805 |
} |
| 806 |
// Clone the block so that it can be added to the new function. |
| 807 |
auto cloned_block = |
| 808 |
std::unique_ptr<opt::BasicBlock>(block_it->Clone(ir_context)); |
| 809 |
|
| 810 |
// If this is the region's exit block, then the cloned block is the outlined |
| 811 |
// region's exit block. |
| 812 |
if (&*block_it == &original_region_exit_block) { |
| 813 |
assert(outlined_region_exit_block == nullptr && |
| 814 |
"We should not yet have encountered the exit block."); |
| 815 |
outlined_region_exit_block = cloned_block.get(); |
| 816 |
} |
| 817 |
|
| 818 |
cloned_block->SetParent(outlined_function); |
| 819 |
|
| 820 |
// Redirect any OpPhi operands whose predecessors are the original region |
| 821 |
// entry block to become the new function entry block. |
| 822 |
cloned_block->ForEachPhiInst([this](opt::Instruction* phi_inst) { |
| 823 |
for (uint32_t predecessor_index = 1; |
| 824 |
predecessor_index < phi_inst->NumInOperands(); |
| 825 |
predecessor_index += 2) { |
| 826 |
if (phi_inst->GetSingleWordInOperand(predecessor_index) == |
| 827 |
message_.entry_block()) { |
| 828 |
phi_inst->SetInOperand(predecessor_index, |
| 829 |
{message_.new_function_region_entry_block()}); |
| 830 |
} |
| 831 |
} |
| 832 |
}); |
| 833 |
|
| 834 |
outlined_function->AddBasicBlock(std::move(cloned_block)); |
| 835 |
block_it = block_it.Erase(); |
| 836 |
} |
| 837 |
assert(outlined_region_exit_block != nullptr && |
| 838 |
"We should have encountered the region's exit block when iterating " |
| 839 |
"through the function"); |
| 840 |
|
| 841 |
// We now need to adapt the exit block for the region - in the new function - |
| 842 |
// so that it ends with a return. |
| 843 |
|
| 844 |
// We first eliminate the merge instruction (if any) and the terminator for |
| 845 |
// the cloned exit block. |
| 846 |
for (auto inst_it = outlined_region_exit_block->begin(); |
| 847 |
inst_it != outlined_region_exit_block->end();) { |
| 848 |
if (inst_it->opcode() == SpvOpLoopMerge || |
| 849 |
inst_it->opcode() == SpvOpSelectionMerge) { |
| 850 |
inst_it = inst_it.Erase(); |
| 851 |
} else if (inst_it->IsBlockTerminator()) { |
| 852 |
inst_it = inst_it.Erase(); |
| 853 |
} else { |
| 854 |
++inst_it; |
| 855 |
} |
| 856 |
} |
| 857 |
|
| 858 |
// We now add either OpReturn or OpReturnValue as the cloned exit block's |
| 859 |
// terminator. |
| 860 |
if (region_output_ids.empty()) { |
| 861 |
// The case where there are no region output ids is simple: we just add |
| 862 |
// OpReturn. |
| 863 |
outlined_region_exit_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 864 |
ir_context, SpvOpReturn, 0, 0, opt::Instruction::OperandList())); |
| 865 |
} else { |
| 866 |
// In the case where there are output ids, we add an OpCompositeConstruct |
| 867 |
// instruction to pack all the non-void output values into a struct, and |
| 868 |
// then an OpReturnValue instruction to return this struct. |
| 869 |
opt::Instruction::OperandList struct_member_operands; |
| 870 |
for (uint32_t id : region_output_ids) { |
| 871 |
if (ir_context->get_def_use_mgr() |
| 872 |
->GetDef(output_id_to_type_id.at(id)) |
| 873 |
->opcode() != SpvOpTypeVoid) { |
| 874 |
struct_member_operands.push_back( |
| 875 |
{SPV_OPERAND_TYPE_ID, {output_id_to_fresh_id_map.at(id)}}); |
| 876 |
} |
| 877 |
} |
| 878 |
outlined_region_exit_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 879 |
ir_context, SpvOpCompositeConstruct, |
| 880 |
message_.new_function_struct_return_type_id(), |
| 881 |
message_.new_callee_result_id(), struct_member_operands)); |
| 882 |
outlined_region_exit_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 883 |
ir_context, SpvOpReturnValue, 0, 0, |
| 884 |
opt::Instruction::OperandList( |
| 885 |
{{SPV_OPERAND_TYPE_ID, {message_.new_callee_result_id()}}}))); |
| 886 |
} |
| 887 |
|
| 888 |
outlined_function->SetFunctionEnd(MakeUnique<opt::Instruction>( |
| 889 |
ir_context, SpvOpFunctionEnd, 0, 0, opt::Instruction::OperandList())); |
| 890 |
} |
| 891 |
|
| 892 |
void TransformationOutlineFunction::ShrinkOriginalRegion( |
| 893 |
opt::IRContext* ir_context, const std::set<opt::BasicBlock*>& region_blocks, |
| 894 |
const std::vector<uint32_t>& region_input_ids, |
| 895 |
const std::vector<uint32_t>& region_output_ids, |
| 896 |
const std::map<uint32_t, uint32_t>& output_id_to_type_id, |
| 897 |
uint32_t return_type_id, |
| 898 |
std::unique_ptr<opt::Instruction> cloned_exit_block_merge, |
| 899 |
std::unique_ptr<opt::Instruction> cloned_exit_block_terminator, |
| 900 |
opt::BasicBlock* original_region_entry_block) const { |
| 901 |
// Erase all blocks from the original function that are in the outlined |
| 902 |
// region, except for the region's entry block. |
| 903 |
// |
| 904 |
// In the process, identify all references to the exit block of the region, |
| 905 |
// as merge blocks, continue targets, or OpPhi predecessors, and rewrite them |
| 906 |
// to refer to the region entry block (the single block to which we are |
| 907 |
// shrinking the region). |
| 908 |
auto enclosing_function = original_region_entry_block->GetParent(); |
| 909 |
for (auto block_it = enclosing_function->begin(); |
| 910 |
block_it != enclosing_function->end();) { |
| 911 |
if (&*block_it == original_region_entry_block) { |
| 912 |
++block_it; |
| 913 |
} else if (region_blocks.count(&*block_it) == 0) { |
| 914 |
// The block is not in the region. Check whether it has the last block |
| 915 |
// of the region as an OpPhi predecessor, and if so change the |
| 916 |
// predecessor to be the first block of the region (i.e. the block |
| 917 |
// containing the call to what was outlined). |
| 918 |
assert(block_it->MergeBlockIdIfAny() != message_.exit_block() && |
| 919 |
"Outlined region must not end with a merge block"); |
| 920 |
assert(block_it->ContinueBlockIdIfAny() != message_.exit_block() && |
| 921 |
"Outlined region must not end with a continue target"); |
| 922 |
block_it->ForEachPhiInst([this](opt::Instruction* phi_inst) { |
| 923 |
for (uint32_t predecessor_index = 1; |
| 924 |
predecessor_index < phi_inst->NumInOperands(); |
| 925 |
predecessor_index += 2) { |
| 926 |
if (phi_inst->GetSingleWordInOperand(predecessor_index) == |
| 927 |
message_.exit_block()) { |
| 928 |
phi_inst->SetInOperand(predecessor_index, {message_.entry_block()}); |
| 929 |
} |
| 930 |
} |
| 931 |
}); |
| 932 |
++block_it; |
| 933 |
} else { |
| 934 |
// The block is in the region and is not the region's entry block: kill |
| 935 |
// it. |
| 936 |
block_it = block_it.Erase(); |
| 937 |
} |
| 938 |
} |
| 939 |
|
| 940 |
// Now erase all instructions from the region's entry block, as they have |
| 941 |
// been outlined. |
| 942 |
for (auto inst_it = original_region_entry_block->begin(); |
| 943 |
inst_it != original_region_entry_block->end();) { |
| 944 |
inst_it = inst_it.Erase(); |
| 945 |
} |
| 946 |
|
| 947 |
// Now we add a call to the outlined function to the region's entry block. |
| 948 |
opt::Instruction::OperandList function_call_operands; |
| 949 |
function_call_operands.push_back( |
| 950 |
{SPV_OPERAND_TYPE_ID, {message_.new_function_id()}}); |
| 951 |
// The function parameters are the region input ids. |
| 952 |
for (auto input_id : region_input_ids) { |
| 953 |
function_call_operands.push_back({SPV_OPERAND_TYPE_ID, {input_id}}); |
| 954 |
} |
| 955 |
|
| 956 |
original_region_entry_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 957 |
ir_context, SpvOpFunctionCall, return_type_id, |
| 958 |
message_.new_caller_result_id(), function_call_operands)); |
| 959 |
|
| 960 |
// If there are output ids, the function call will return a struct. For each |
| 961 |
// output id, we add an extract operation to pull the appropriate struct |
| 962 |
// member out into an output id. The exception is for output ids with void |
| 963 |
// type. There are no struct entries for these, so we use an OpUndef of void |
| 964 |
// type instead. |
| 965 |
uint32_t struct_member_index = 0; |
| 966 |
for (uint32_t output_id : region_output_ids) { |
| 967 |
uint32_t output_type_id = output_id_to_type_id.at(output_id); |
| 968 |
if (ir_context->get_def_use_mgr()->GetDef(output_type_id)->opcode() == |
| 969 |
SpvOpTypeVoid) { |
| 970 |
original_region_entry_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 971 |
ir_context, SpvOpUndef, output_type_id, output_id, |
| 972 |
opt::Instruction::OperandList())); |
| 973 |
// struct_member_index is not incremented since there was no struct member |
| 974 |
// associated with this void-typed output id. |
| 975 |
} else { |
| 976 |
original_region_entry_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 977 |
ir_context, SpvOpCompositeExtract, output_type_id, output_id, |
| 978 |
opt::Instruction::OperandList( |
| 979 |
{{SPV_OPERAND_TYPE_ID, {message_.new_caller_result_id()}}, |
| 980 |
{SPV_OPERAND_TYPE_LITERAL_INTEGER, {struct_member_index}}}))); |
| 981 |
struct_member_index++; |
| 982 |
} |
| 983 |
} |
| 984 |
|
| 985 |
// Finally, we terminate the block with the merge instruction (if any) that |
| 986 |
// used to belong to the region's exit block, and the terminator that used |
| 987 |
// to belong to the region's exit block. |
| 988 |
if (cloned_exit_block_merge != nullptr) { |
| 989 |
original_region_entry_block->AddInstruction( |
| 990 |
std::move(cloned_exit_block_merge)); |
| 991 |
} |
| 992 |
original_region_entry_block->AddInstruction( |
| 993 |
std::move(cloned_exit_block_terminator)); |
| 994 |
} |
| 995 |
|
| 996 |
std::unordered_set<uint32_t> TransformationOutlineFunction::GetFreshIds() |
| 997 |
const { |
| 998 |
std::unordered_set<uint32_t> result = { |
| 999 |
message_.new_function_struct_return_type_id(), |
| 1000 |
message_.new_function_type_id(), |
| 1001 |
message_.new_function_id(), |
| 1002 |
message_.new_function_region_entry_block(), |
| 1003 |
message_.new_caller_result_id(), |
| 1004 |
message_.new_callee_result_id()}; |
| 1005 |
for (auto& pair : message_.input_id_to_fresh_id()) { |
| 1006 |
result.insert(pair.second()); |
| 1007 |
} |
| 1008 |
for (auto& pair : message_.output_id_to_fresh_id()) { |
| 1009 |
result.insert(pair.second()); |
| 1010 |
} |
| 1011 |
return result; |
| 1012 |
} |
| 1013 |
|
| 1014 |
} // namespace fuzz |
| 1015 |
} // namespace spvtools |