| 1 |
// Copyright (c) 2020 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_duplicate_region_with_selection.h" |
| 16 |
|
| 17 |
#include "source/fuzz/fuzzer_util.h" |
| 18 |
|
| 19 |
namespace spvtools { |
| 20 |
namespace fuzz { |
| 21 |
|
| 22 |
TransformationDuplicateRegionWithSelection:: |
| 23 |
TransformationDuplicateRegionWithSelection( |
| 24 |
const spvtools::fuzz::protobufs:: |
| 25 |
TransformationDuplicateRegionWithSelection& message) |
| 26 |
: message_(message) {} |
| 27 |
|
| 28 |
TransformationDuplicateRegionWithSelection:: |
| 29 |
TransformationDuplicateRegionWithSelection( |
| 30 |
uint32_t new_entry_fresh_id, uint32_t condition_id, |
| 31 |
uint32_t merge_label_fresh_id, uint32_t entry_block_id, |
| 32 |
uint32_t exit_block_id, |
| 33 |
const std::map<uint32_t, uint32_t>& original_label_to_duplicate_label, |
| 34 |
const std::map<uint32_t, uint32_t>& original_id_to_duplicate_id, |
| 35 |
const std::map<uint32_t, uint32_t>& original_id_to_phi_id) { |
| 36 |
message_.set_new_entry_fresh_id(new_entry_fresh_id); |
| 37 |
message_.set_condition_id(condition_id); |
| 38 |
message_.set_merge_label_fresh_id(merge_label_fresh_id); |
| 39 |
message_.set_entry_block_id(entry_block_id); |
| 40 |
message_.set_exit_block_id(exit_block_id); |
| 41 |
*message_.mutable_original_label_to_duplicate_label() = |
| 42 |
fuzzerutil::MapToRepeatedUInt32Pair(original_label_to_duplicate_label); |
| 43 |
*message_.mutable_original_id_to_duplicate_id() = |
| 44 |
fuzzerutil::MapToRepeatedUInt32Pair(original_id_to_duplicate_id); |
| 45 |
*message_.mutable_original_id_to_phi_id() = |
| 46 |
fuzzerutil::MapToRepeatedUInt32Pair(original_id_to_phi_id); |
| 47 |
} |
| 48 |
|
| 49 |
bool TransformationDuplicateRegionWithSelection::IsApplicable( |
| 50 |
opt::IRContext* ir_context, |
| 51 |
const TransformationContext& transformation_context) const { |
| 52 |
// Instruction with the id |condition_id| must exist and must be of a bool |
| 53 |
// type. |
| 54 |
auto bool_instr = |
| 55 |
ir_context->get_def_use_mgr()->GetDef(message_.condition_id()); |
| 56 |
if (bool_instr == nullptr || !bool_instr->type_id()) { |
| 57 |
return false; |
| 58 |
} |
| 59 |
if (!ir_context->get_type_mgr()->GetType(bool_instr->type_id())->AsBool()) { |
| 60 |
return false; |
| 61 |
} |
| 62 |
|
| 63 |
// The |new_entry_fresh_id| must be fresh and distinct. |
| 64 |
std::set<uint32_t> ids_used_by_this_transformation; |
| 65 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 66 |
message_.new_entry_fresh_id(), ir_context, |
| 67 |
&ids_used_by_this_transformation)) { |
| 68 |
return false; |
| 69 |
} |
| 70 |
|
| 71 |
// The |merge_label_fresh_id| must be fresh and distinct. |
| 72 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 73 |
message_.merge_label_fresh_id(), ir_context, |
| 74 |
&ids_used_by_this_transformation)) { |
| 75 |
return false; |
| 76 |
} |
| 77 |
|
| 78 |
// The entry and exit block ids must refer to blocks. |
| 79 |
for (auto block_id : {message_.entry_block_id(), message_.exit_block_id()}) { |
| 80 |
auto block_label = ir_context->get_def_use_mgr()->GetDef(block_id); |
| 81 |
if (!block_label || block_label->opcode() != SpvOpLabel) { |
| 82 |
return false; |
| 83 |
} |
| 84 |
} |
| 85 |
auto entry_block = ir_context->cfg()->block(message_.entry_block_id()); |
| 86 |
auto exit_block = ir_context->cfg()->block(message_.exit_block_id()); |
| 87 |
|
| 88 |
// The |entry_block| and the |exit_block| must be in the same function. |
| 89 |
if (entry_block->GetParent() != exit_block->GetParent()) { |
| 90 |
return false; |
| 91 |
} |
| 92 |
|
| 93 |
// The |entry_block| must dominate the |exit_block|. |
| 94 |
auto dominator_analysis = |
| 95 |
ir_context->GetDominatorAnalysis(entry_block->GetParent()); |
| 96 |
if (!dominator_analysis->Dominates(entry_block, exit_block)) { |
| 97 |
return false; |
| 98 |
} |
| 99 |
|
| 100 |
// The |exit_block| must post-dominate the |entry_block|. |
| 101 |
auto postdominator_analysis = |
| 102 |
ir_context->GetPostDominatorAnalysis(entry_block->GetParent()); |
| 103 |
if (!postdominator_analysis->Dominates(exit_block, entry_block)) { |
| 104 |
return false; |
| 105 |
} |
| 106 |
|
| 107 |
auto enclosing_function = entry_block->GetParent(); |
| 108 |
|
| 109 |
// |entry_block| cannot be the first block of the |enclosing_function|. |
| 110 |
if (&*enclosing_function->begin() == entry_block) { |
| 111 |
return false; |
| 112 |
} |
| 113 |
|
| 114 |
// To make the process of resolving OpPhi instructions easier, we require that |
| 115 |
// the entry block has only one predecessor. |
| 116 |
auto entry_block_preds = ir_context->cfg()->preds(entry_block->id()); |
| 117 |
std::sort(entry_block_preds.begin(), entry_block_preds.end()); |
| 118 |
entry_block_preds.erase( |
| 119 |
std::unique(entry_block_preds.begin(), entry_block_preds.end()), |
| 120 |
entry_block_preds.end()); |
| 121 |
if (entry_block_preds.size() > 1) { |
| 122 |
return false; |
| 123 |
} |
| 124 |
|
| 125 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3785): |
| 126 |
// The following code has been copied from TransformationOutlineFunction. |
| 127 |
// Consider refactoring to avoid duplication. |
| 128 |
auto region_set = GetRegionBlocks(ir_context, entry_block, exit_block); |
| 129 |
|
| 130 |
// Check whether |region_set| really is a single-entry single-exit region, and |
| 131 |
// also check whether structured control flow constructs and their merge |
| 132 |
// and continue constructs are either wholly in or wholly out of the region - |
| 133 |
// e.g. avoid the situation where the region contains the head of a loop but |
| 134 |
// not the loop's continue construct. |
| 135 |
// |
| 136 |
// This is achieved by going through every block in the |enclosing_function| |
| 137 |
for (auto& block : *enclosing_function) { |
| 138 |
if (&block == exit_block) { |
| 139 |
// It is not OK for the exit block to head a loop construct or a |
| 140 |
// conditional construct. |
| 141 |
if (block.GetMergeInst()) { |
| 142 |
return false; |
| 143 |
} |
| 144 |
continue; |
| 145 |
} |
| 146 |
if (region_set.count(&block) != 0) { |
| 147 |
// The block is in the region and is not the region's exit block. Let's |
| 148 |
// see whether all of the block's successors are in the region. If they |
| 149 |
// are not, the region is not single-entry single-exit. |
| 150 |
bool all_successors_in_region = true; |
| 151 |
block.WhileEachSuccessorLabel([&all_successors_in_region, ir_context, |
| 152 |
®ion_set](uint32_t successor) -> bool { |
| 153 |
if (region_set.count(ir_context->cfg()->block(successor)) == 0) { |
| 154 |
all_successors_in_region = false; |
| 155 |
return false; |
| 156 |
} |
| 157 |
return true; |
| 158 |
}); |
| 159 |
if (!all_successors_in_region) { |
| 160 |
return false; |
| 161 |
} |
| 162 |
} |
| 163 |
|
| 164 |
if (auto merge = block.GetMergeInst()) { |
| 165 |
// The block is a loop or selection header. The header and its |
| 166 |
// associated merge block must be both in the region or both be |
| 167 |
// outside the region. |
| 168 |
auto merge_block = |
| 169 |
ir_context->cfg()->block(merge->GetSingleWordOperand(0)); |
| 170 |
if (region_set.count(&block) != region_set.count(merge_block)) { |
| 171 |
return false; |
| 172 |
} |
| 173 |
} |
| 174 |
|
| 175 |
if (auto loop_merge = block.GetLoopMergeInst()) { |
| 176 |
// The continue target of a loop must be within the region if and only if |
| 177 |
// the header of the loop is. |
| 178 |
auto continue_target = |
| 179 |
ir_context->cfg()->block(loop_merge->GetSingleWordOperand(1)); |
| 180 |
// The continue target is a single-entry, single-exit region. Therefore, |
| 181 |
// if the continue target is the exit block, the region might not contain |
| 182 |
// the loop header. However, we would like to exclude this situation, |
| 183 |
// since it would be impossible for the modified exit block to branch to |
| 184 |
// the new selection merge block. In this scenario the exit block is |
| 185 |
// required to branch to the loop header. |
| 186 |
if (region_set.count(&block) != region_set.count(continue_target)) { |
| 187 |
return false; |
| 188 |
} |
| 189 |
} |
| 190 |
} |
| 191 |
|
| 192 |
// Get the maps from the protobuf. |
| 193 |
std::map<uint32_t, uint32_t> original_label_to_duplicate_label = |
| 194 |
fuzzerutil::RepeatedUInt32PairToMap( |
| 195 |
message_.original_label_to_duplicate_label()); |
| 196 |
|
| 197 |
std::map<uint32_t, uint32_t> original_id_to_duplicate_id = |
| 198 |
fuzzerutil::RepeatedUInt32PairToMap( |
| 199 |
message_.original_id_to_duplicate_id()); |
| 200 |
|
| 201 |
std::map<uint32_t, uint32_t> original_id_to_phi_id = |
| 202 |
fuzzerutil::RepeatedUInt32PairToMap(message_.original_id_to_phi_id()); |
| 203 |
|
| 204 |
for (auto block : region_set) { |
| 205 |
// The label of every block in the region must be present in the map |
| 206 |
// |original_label_to_duplicate_label|, unless overflow ids are present. |
| 207 |
if (original_label_to_duplicate_label.count(block->id()) == 0) { |
| 208 |
if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| 209 |
return false; |
| 210 |
} |
| 211 |
} else { |
| 212 |
auto duplicate_label = original_label_to_duplicate_label[block->id()]; |
| 213 |
// Each id assigned to labels in the region must be distinct and fresh. |
| 214 |
if (!duplicate_label || |
| 215 |
!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 216 |
duplicate_label, ir_context, &ids_used_by_this_transformation)) { |
| 217 |
return false; |
| 218 |
} |
| 219 |
} |
| 220 |
for (auto instr : *block) { |
| 221 |
if (!instr.HasResultId()) { |
| 222 |
continue; |
| 223 |
} |
| 224 |
// Every instruction with a result id in the region must be present in the |
| 225 |
// map |original_id_to_duplicate_id|, unless overflow ids are present. |
| 226 |
if (original_id_to_duplicate_id.count(instr.result_id()) == 0) { |
| 227 |
if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| 228 |
return false; |
| 229 |
} |
| 230 |
} else { |
| 231 |
auto duplicate_id = original_id_to_duplicate_id[instr.result_id()]; |
| 232 |
// Id assigned to this result id in the region must be distinct and |
| 233 |
// fresh. |
| 234 |
if (!duplicate_id || |
| 235 |
!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 236 |
duplicate_id, ir_context, &ids_used_by_this_transformation)) { |
| 237 |
return false; |
| 238 |
} |
| 239 |
} |
| 240 |
if (&instr == &*exit_block->tail() || |
| 241 |
fuzzerutil::IdIsAvailableBeforeInstruction( |
| 242 |
ir_context, &*exit_block->tail(), instr.result_id())) { |
| 243 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3787): |
| 244 |
// Consider not adding OpPhi instructions for the pointers and |
| 245 |
// sampled images which are unused after the region, so that the |
| 246 |
// transformation could be still applicable. |
| 247 |
|
| 248 |
// Using pointers with OpPhi requires capability VariablePointers. |
| 249 |
if (ir_context->get_def_use_mgr()->GetDef(instr.type_id())->opcode() == |
| 250 |
SpvOpTypePointer && |
| 251 |
!ir_context->get_feature_mgr()->HasCapability( |
| 252 |
SpvCapabilityVariablePointers)) { |
| 253 |
return false; |
| 254 |
} |
| 255 |
|
| 256 |
// OpTypeSampledImage cannot be the result type of an OpPhi instruction. |
| 257 |
if (ir_context->get_def_use_mgr()->GetDef(instr.type_id())->opcode() == |
| 258 |
SpvOpTypeSampledImage) { |
| 259 |
return false; |
| 260 |
} |
| 261 |
|
| 262 |
// Every instruction with a result id available at the end of the region |
| 263 |
// must be present in the map |original_id_to_phi_id|, unless overflow |
| 264 |
// ids are present. |
| 265 |
if (original_id_to_phi_id.count(instr.result_id()) == 0) { |
| 266 |
if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| 267 |
return false; |
| 268 |
} |
| 269 |
} else { |
| 270 |
auto phi_id = original_id_to_phi_id[instr.result_id()]; |
| 271 |
// Id assigned to this result id in the region must be distinct and |
| 272 |
// fresh. |
| 273 |
if (!phi_id || |
| 274 |
!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 275 |
phi_id, ir_context, &ids_used_by_this_transformation)) { |
| 276 |
return false; |
| 277 |
} |
| 278 |
} |
| 279 |
} |
| 280 |
} |
| 281 |
} |
| 282 |
return true; |
| 283 |
} |
| 284 |
|
| 285 |
void TransformationDuplicateRegionWithSelection::Apply( |
| 286 |
opt::IRContext* ir_context, |
| 287 |
TransformationContext* transformation_context) const { |
| 288 |
fuzzerutil::UpdateModuleIdBound(ir_context, message_.new_entry_fresh_id()); |
| 289 |
fuzzerutil::UpdateModuleIdBound(ir_context, message_.merge_label_fresh_id()); |
| 290 |
|
| 291 |
// Create the new entry block containing the main conditional instruction. Set |
| 292 |
// its parent to the parent of the original entry block, since it is located |
| 293 |
// in the same function. |
| 294 |
std::unique_ptr<opt::BasicBlock> new_entry_block = |
| 295 |
MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>( |
| 296 |
ir_context, SpvOpLabel, 0, message_.new_entry_fresh_id(), |
| 297 |
opt::Instruction::OperandList())); |
| 298 |
auto entry_block = ir_context->cfg()->block(message_.entry_block_id()); |
| 299 |
auto enclosing_function = entry_block->GetParent(); |
| 300 |
auto exit_block = ir_context->cfg()->block(message_.exit_block_id()); |
| 301 |
|
| 302 |
// Get the blocks contained in the region. |
| 303 |
std::set<opt::BasicBlock*> region_blocks = |
| 304 |
GetRegionBlocks(ir_context, entry_block, exit_block); |
| 305 |
|
| 306 |
// Construct the merge block. |
| 307 |
std::unique_ptr<opt::BasicBlock> merge_block = |
| 308 |
MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(opt::Instruction( |
| 309 |
ir_context, SpvOpLabel, 0, message_.merge_label_fresh_id(), |
| 310 |
opt::Instruction::OperandList()))); |
| 311 |
|
| 312 |
// Get the maps from the protobuf. |
| 313 |
std::map<uint32_t, uint32_t> original_label_to_duplicate_label = |
| 314 |
fuzzerutil::RepeatedUInt32PairToMap( |
| 315 |
message_.original_label_to_duplicate_label()); |
| 316 |
|
| 317 |
std::map<uint32_t, uint32_t> original_id_to_duplicate_id = |
| 318 |
fuzzerutil::RepeatedUInt32PairToMap( |
| 319 |
message_.original_id_to_duplicate_id()); |
| 320 |
|
| 321 |
std::map<uint32_t, uint32_t> original_id_to_phi_id = |
| 322 |
fuzzerutil::RepeatedUInt32PairToMap(message_.original_id_to_phi_id()); |
| 323 |
|
| 324 |
// Use oveflow ids to fill in any required ids that are missing from these |
| 325 |
// maps. |
| 326 |
for (auto block : region_blocks) { |
| 327 |
if (original_label_to_duplicate_label.count(block->id()) == 0) { |
| 328 |
original_label_to_duplicate_label.insert( |
| 329 |
{block->id(), |
| 330 |
transformation_context->GetOverflowIdSource()->GetNextOverflowId()}); |
| 331 |
} |
| 332 |
for (auto instr : *block) { |
| 333 |
if (!instr.HasResultId()) { |
| 334 |
continue; |
| 335 |
} |
| 336 |
if (original_id_to_duplicate_id.count(instr.result_id()) == 0) { |
| 337 |
original_id_to_duplicate_id.insert( |
| 338 |
{instr.result_id(), transformation_context->GetOverflowIdSource() |
| 339 |
->GetNextOverflowId()}); |
| 340 |
} |
| 341 |
if (&instr == &*exit_block->tail() || |
| 342 |
fuzzerutil::IdIsAvailableBeforeInstruction( |
| 343 |
ir_context, &*exit_block->tail(), instr.result_id())) { |
| 344 |
if (original_id_to_phi_id.count(instr.result_id()) == 0) { |
| 345 |
original_id_to_phi_id.insert( |
| 346 |
{instr.result_id(), transformation_context->GetOverflowIdSource() |
| 347 |
->GetNextOverflowId()}); |
| 348 |
} |
| 349 |
} |
| 350 |
} |
| 351 |
} |
| 352 |
|
| 353 |
// Before adding duplicate blocks, we need to update the OpPhi instructions in |
| 354 |
// the successors of the |exit_block|. We know that the execution of the |
| 355 |
// transformed region will end in |merge_block|. Hence, we need to change all |
| 356 |
// occurrences of the label id of the |exit_block| to the label id of the |
| 357 |
// |merge_block|. |
| 358 |
exit_block->ForEachSuccessorLabel([this, ir_context](uint32_t label_id) { |
| 359 |
auto block = ir_context->cfg()->block(label_id); |
| 360 |
for (auto& instr : *block) { |
| 361 |
if (instr.opcode() == SpvOpPhi) { |
| 362 |
instr.ForEachId([this](uint32_t* id) { |
| 363 |
if (*id == message_.exit_block_id()) { |
| 364 |
*id = message_.merge_label_fresh_id(); |
| 365 |
} |
| 366 |
}); |
| 367 |
} |
| 368 |
} |
| 369 |
}); |
| 370 |
|
| 371 |
// Get vector of predecessors id of |entry_block|. Remove any duplicate |
| 372 |
// values. |
| 373 |
auto entry_block_preds = ir_context->cfg()->preds(entry_block->id()); |
| 374 |
std::sort(entry_block_preds.begin(), entry_block_preds.end()); |
| 375 |
entry_block_preds.erase( |
| 376 |
unique(entry_block_preds.begin(), entry_block_preds.end()), |
| 377 |
entry_block_preds.end()); |
| 378 |
// We know that |entry_block| has only one predecessor, since the region is |
| 379 |
// single-entry, single-exit and its constructs and their merge blocks must be |
| 380 |
// either wholly within or wholly outside of the region. |
| 381 |
assert(entry_block_preds.size() == 1 && |
| 382 |
"The entry of the region to be duplicated can have only one " |
| 383 |
"predecessor."); |
| 384 |
uint32_t entry_block_pred_id = |
| 385 |
ir_context->get_instr_block(entry_block_preds[0])->id(); |
| 386 |
// Update all the OpPhi instructions in the |entry_block|. Change every |
| 387 |
// occurrence of |entry_block_pred_id| to the id of |new_entry|, because we |
| 388 |
// will insert |new_entry| before |entry_block|. |
| 389 |
for (auto& instr : *entry_block) { |
| 390 |
if (instr.opcode() == SpvOpPhi) { |
| 391 |
instr.ForEachId([this, entry_block_pred_id](uint32_t* id) { |
| 392 |
if (*id == entry_block_pred_id) { |
| 393 |
*id = message_.new_entry_fresh_id(); |
| 394 |
} |
| 395 |
}); |
| 396 |
} |
| 397 |
} |
| 398 |
|
| 399 |
// Duplication of blocks will invalidate iterators. Store all the blocks from |
| 400 |
// the enclosing function. |
| 401 |
std::vector<opt::BasicBlock*> blocks; |
| 402 |
for (auto& block : *enclosing_function) { |
| 403 |
blocks.push_back(&block); |
| 404 |
} |
| 405 |
|
| 406 |
opt::BasicBlock* previous_block = nullptr; |
| 407 |
opt::BasicBlock* duplicated_exit_block = nullptr; |
| 408 |
// Iterate over all blocks of the function to duplicate blocks of the original |
| 409 |
// region and their instructions. |
| 410 |
for (auto& block : blocks) { |
| 411 |
// The block must be contained in the region. |
| 412 |
if (region_blocks.count(block) == 0) { |
| 413 |
continue; |
| 414 |
} |
| 415 |
|
| 416 |
fuzzerutil::UpdateModuleIdBound( |
| 417 |
ir_context, original_label_to_duplicate_label[block->id()]); |
| 418 |
|
| 419 |
std::unique_ptr<opt::BasicBlock> duplicated_block = |
| 420 |
MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>( |
| 421 |
ir_context, SpvOpLabel, 0, |
| 422 |
original_label_to_duplicate_label[block->id()], |
| 423 |
opt::Instruction::OperandList())); |
| 424 |
|
| 425 |
for (auto& instr : *block) { |
| 426 |
// Case where an instruction is the terminator of the exit block is |
| 427 |
// handled separately. |
| 428 |
if (block == exit_block && instr.IsBlockTerminator()) { |
| 429 |
switch (instr.opcode()) { |
| 430 |
case SpvOpBranch: |
| 431 |
case SpvOpBranchConditional: |
| 432 |
case SpvOpReturn: |
| 433 |
case SpvOpReturnValue: |
| 434 |
case SpvOpUnreachable: |
| 435 |
case SpvOpKill: |
| 436 |
continue; |
| 437 |
default: |
| 438 |
assert(false && |
| 439 |
"Unexpected terminator for |exit_block| of the region."); |
| 440 |
} |
| 441 |
} |
| 442 |
// Duplicate the instruction. |
| 443 |
auto cloned_instr = instr.Clone(ir_context); |
| 444 |
duplicated_block->AddInstruction( |
| 445 |
std::unique_ptr<opt::Instruction>(cloned_instr)); |
| 446 |
|
| 447 |
fuzzerutil::UpdateModuleIdBound( |
| 448 |
ir_context, original_id_to_duplicate_id[instr.result_id()]); |
| 449 |
|
| 450 |
// If an id from the original region was used in this instruction, |
| 451 |
// replace it with the value from |original_id_to_duplicate_id|. |
| 452 |
// If a label from the original region was used in this instruction, |
| 453 |
// replace it with the value from |original_label_to_duplicate_label|. |
| 454 |
cloned_instr->ForEachId( |
| 455 |
[original_id_to_duplicate_id, |
| 456 |
original_label_to_duplicate_label](uint32_t* op) { |
| 457 |
if (original_id_to_duplicate_id.count(*op) != 0) { |
| 458 |
*op = original_id_to_duplicate_id.at(*op); |
| 459 |
} |
| 460 |
if (original_label_to_duplicate_label.count(*op) != 0) { |
| 461 |
*op = original_label_to_duplicate_label.at(*op); |
| 462 |
} |
| 463 |
}); |
| 464 |
} |
| 465 |
|
| 466 |
// If the block is the first duplicated block, insert it after the exit |
| 467 |
// block of the original region. Otherwise, insert it after the preceding |
| 468 |
// one. |
| 469 |
auto duplicated_block_ptr = duplicated_block.get(); |
| 470 |
if (previous_block) { |
| 471 |
enclosing_function->InsertBasicBlockAfter(std::move(duplicated_block), |
| 472 |
previous_block); |
| 473 |
} else { |
| 474 |
enclosing_function->InsertBasicBlockAfter(std::move(duplicated_block), |
| 475 |
exit_block); |
| 476 |
} |
| 477 |
previous_block = duplicated_block_ptr; |
| 478 |
if (block == exit_block) { |
| 479 |
// After execution of the loop, this variable stores a pointer to the last |
| 480 |
// duplicated block. |
| 481 |
duplicated_exit_block = duplicated_block_ptr; |
| 482 |
} |
| 483 |
} |
| 484 |
|
| 485 |
for (auto& block : region_blocks) { |
| 486 |
for (auto& instr : *block) { |
| 487 |
if (instr.result_id() != 0 && |
| 488 |
(&instr == &*exit_block->tail() || |
| 489 |
fuzzerutil::IdIsAvailableBeforeInstruction( |
| 490 |
ir_context, &*exit_block->tail(), instr.result_id()))) { |
| 491 |
// Add the OpPhi instruction for every result id that is |
| 492 |
// available at the end of the region (the last instruction |
| 493 |
// of the |exit_block|) |
| 494 |
merge_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 495 |
ir_context, SpvOpPhi, instr.type_id(), |
| 496 |
original_id_to_phi_id[instr.result_id()], |
| 497 |
opt::Instruction::OperandList({ |
| 498 |
{SPV_OPERAND_TYPE_ID, {instr.result_id()}}, |
| 499 |
{SPV_OPERAND_TYPE_ID, {exit_block->id()}}, |
| 500 |
{SPV_OPERAND_TYPE_ID, |
| 501 |
{original_id_to_duplicate_id[instr.result_id()]}}, |
| 502 |
{SPV_OPERAND_TYPE_ID, {duplicated_exit_block->id()}}, |
| 503 |
}))); |
| 504 |
|
| 505 |
fuzzerutil::UpdateModuleIdBound( |
| 506 |
ir_context, original_id_to_phi_id[instr.result_id()]); |
| 507 |
|
| 508 |
// If the instruction has been remapped by an OpPhi, look |
| 509 |
// for all its uses outside of the region and outside of the |
| 510 |
// merge block (to not overwrite just added instructions in |
| 511 |
// the merge block) and replace the original instruction id |
| 512 |
// with the id of the corresponding OpPhi instruction. |
| 513 |
ir_context->get_def_use_mgr()->ForEachUse( |
| 514 |
&instr, |
| 515 |
[ir_context, &instr, region_blocks, original_id_to_phi_id, |
| 516 |
&merge_block](opt::Instruction* user, uint32_t operand_index) { |
| 517 |
auto user_block = ir_context->get_instr_block(user); |
| 518 |
if ((region_blocks.find(user_block) != region_blocks.end()) || |
| 519 |
user_block == merge_block.get()) { |
| 520 |
return; |
| 521 |
} |
| 522 |
user->SetOperand(operand_index, |
| 523 |
{original_id_to_phi_id.at(instr.result_id())}); |
| 524 |
}); |
| 525 |
} |
| 526 |
} |
| 527 |
} |
| 528 |
|
| 529 |
// Construct a conditional instruction in the |new_entry_block|. |
| 530 |
// If the condition is true, the execution proceeds in the |
| 531 |
// |entry_block| of the original region. If the condition is |
| 532 |
// false, the execution proceeds in the first block of the |
| 533 |
// duplicated region. |
| 534 |
new_entry_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 535 |
ir_context, SpvOpSelectionMerge, 0, 0, |
| 536 |
opt::Instruction::OperandList( |
| 537 |
{{SPV_OPERAND_TYPE_ID, {message_.merge_label_fresh_id()}}, |
| 538 |
{SPV_OPERAND_TYPE_SELECTION_CONTROL, |
| 539 |
{SpvSelectionControlMaskNone}}}))); |
| 540 |
|
| 541 |
new_entry_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 542 |
ir_context, SpvOpBranchConditional, 0, 0, |
| 543 |
opt::Instruction::OperandList( |
| 544 |
{{SPV_OPERAND_TYPE_ID, {message_.condition_id()}}, |
| 545 |
{SPV_OPERAND_TYPE_ID, {message_.entry_block_id()}}, |
| 546 |
{SPV_OPERAND_TYPE_ID, |
| 547 |
{original_label_to_duplicate_label[message_.entry_block_id()]}}}))); |
| 548 |
|
| 549 |
// Move the terminator of |exit_block| to the end of |
| 550 |
// |merge_block|. |
| 551 |
auto exit_block_terminator = exit_block->terminator(); |
| 552 |
auto cloned_instr = exit_block_terminator->Clone(ir_context); |
| 553 |
merge_block->AddInstruction(std::unique_ptr<opt::Instruction>(cloned_instr)); |
| 554 |
ir_context->KillInst(exit_block_terminator); |
| 555 |
|
| 556 |
// Add OpBranch instruction to the merge block at the end of |
| 557 |
// |exit_block| and at the end of |duplicated_exit_block|, so that |
| 558 |
// the execution proceeds in the |merge_block|. |
| 559 |
opt::Instruction merge_branch_instr = opt::Instruction( |
| 560 |
ir_context, SpvOpBranch, 0, 0, |
| 561 |
opt::Instruction::OperandList( |
| 562 |
{{SPV_OPERAND_TYPE_ID, {message_.merge_label_fresh_id()}}})); |
| 563 |
exit_block->AddInstruction(MakeUnique<opt::Instruction>(merge_branch_instr)); |
| 564 |
duplicated_exit_block->AddInstruction( |
| 565 |
std::unique_ptr<opt::Instruction>(merge_branch_instr.Clone(ir_context))); |
| 566 |
|
| 567 |
// Execution needs to start in the |new_entry_block|. Change all |
| 568 |
// the uses of |entry_block_label_instr| outside of the original |
| 569 |
// region to |message_.new_entry_fresh_id|. |
| 570 |
auto entry_block_label_instr = |
| 571 |
ir_context->get_def_use_mgr()->GetDef(message_.entry_block_id()); |
| 572 |
ir_context->get_def_use_mgr()->ForEachUse( |
| 573 |
entry_block_label_instr, |
| 574 |
[this, ir_context, region_blocks](opt::Instruction* user, |
| 575 |
uint32_t operand_index) { |
| 576 |
auto user_block = ir_context->get_instr_block(user); |
| 577 |
if ((region_blocks.count(user_block) != 0)) { |
| 578 |
return; |
| 579 |
} |
| 580 |
switch (user->opcode()) { |
| 581 |
case SpvOpSwitch: |
| 582 |
case SpvOpBranch: |
| 583 |
case SpvOpBranchConditional: |
| 584 |
case SpvOpLoopMerge: |
| 585 |
case SpvOpSelectionMerge: { |
| 586 |
user->SetOperand(operand_index, {message_.new_entry_fresh_id()}); |
| 587 |
} break; |
| 588 |
case SpvOpName: |
| 589 |
break; |
| 590 |
default: |
| 591 |
assert(false && |
| 592 |
"The label id cannot be used by instructions " |
| 593 |
"other than " |
| 594 |
"OpSwitch, OpBranch, OpBranchConditional, " |
| 595 |
"OpLoopMerge, " |
| 596 |
"OpSelectionMerge"); |
| 597 |
} |
| 598 |
}); |
| 599 |
|
| 600 |
opt::Instruction* merge_block_terminator = merge_block->terminator(); |
| 601 |
switch (merge_block_terminator->opcode()) { |
| 602 |
case SpvOpReturnValue: |
| 603 |
case SpvOpBranchConditional: { |
| 604 |
uint32_t operand = merge_block_terminator->GetSingleWordInOperand(0); |
| 605 |
if (original_id_to_phi_id.count(operand)) { |
| 606 |
merge_block_terminator->SetInOperand( |
| 607 |
0, {original_id_to_phi_id.at(operand)}); |
| 608 |
} |
| 609 |
break; |
| 610 |
} |
| 611 |
default: |
| 612 |
break; |
| 613 |
} |
| 614 |
|
| 615 |
// Insert the merge block after the |duplicated_exit_block| (the |
| 616 |
// last duplicated block). |
| 617 |
enclosing_function->InsertBasicBlockAfter(std::move(merge_block), |
| 618 |
duplicated_exit_block); |
| 619 |
|
| 620 |
// Insert the |new_entry_block| before the entry block of the |
| 621 |
// original region. |
| 622 |
enclosing_function->InsertBasicBlockBefore(std::move(new_entry_block), |
| 623 |
entry_block); |
| 624 |
|
| 625 |
// Since we have changed the module, most of the analysis are now |
| 626 |
// invalid. We can invalidate analyses now after all of the blocks |
| 627 |
// have been registered. |
| 628 |
ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone); |
| 629 |
} |
| 630 |
|
| 631 |
// TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3785): |
| 632 |
// The following method has been copied from |
| 633 |
// TransformationOutlineFunction. Consider refactoring to avoid |
| 634 |
// duplication. |
| 635 |
std::set<opt::BasicBlock*> |
| 636 |
TransformationDuplicateRegionWithSelection::GetRegionBlocks( |
| 637 |
opt::IRContext* ir_context, opt::BasicBlock* entry_block, |
| 638 |
opt::BasicBlock* exit_block) { |
| 639 |
auto enclosing_function = entry_block->GetParent(); |
| 640 |
auto dominator_analysis = |
| 641 |
ir_context->GetDominatorAnalysis(enclosing_function); |
| 642 |
auto postdominator_analysis = |
| 643 |
ir_context->GetPostDominatorAnalysis(enclosing_function); |
| 644 |
|
| 645 |
// A block belongs to a region between the entry block and the exit |
| 646 |
// block if and only if it is dominated by the entry block and |
| 647 |
// post-dominated by the exit block. |
| 648 |
std::set<opt::BasicBlock*> result; |
| 649 |
for (auto& block : *enclosing_function) { |
| 650 |
if (dominator_analysis->Dominates(entry_block, &block) && |
| 651 |
postdominator_analysis->Dominates(exit_block, &block)) { |
| 652 |
result.insert(&block); |
| 653 |
} |
| 654 |
} |
| 655 |
return result; |
| 656 |
} |
| 657 |
|
| 658 |
protobufs::Transformation |
| 659 |
TransformationDuplicateRegionWithSelection::ToMessage() const { |
| 660 |
protobufs::Transformation result; |
| 661 |
*result.mutable_duplicate_region_with_selection() = message_; |
| 662 |
return result; |
| 663 |
} |
| 664 |
|
| 665 |
std::unordered_set<uint32_t> |
| 666 |
TransformationDuplicateRegionWithSelection::GetFreshIds() const { |
| 667 |
std::unordered_set<uint32_t> result = {message_.new_entry_fresh_id(), |
| 668 |
message_.merge_label_fresh_id()}; |
| 669 |
for (auto& pair : message_.original_label_to_duplicate_label()) { |
| 670 |
result.insert(pair.second()); |
| 671 |
} |
| 672 |
for (auto& pair : message_.original_id_to_duplicate_id()) { |
| 673 |
result.insert(pair.second()); |
| 674 |
} |
| 675 |
for (auto& pair : message_.original_id_to_phi_id()) { |
| 676 |
result.insert(pair.second()); |
| 677 |
} |
| 678 |
return result; |
| 679 |
} |
| 680 |
|
| 681 |
} // namespace fuzz |
| 682 |
} // namespace spvtools |