| 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_flatten_conditional_branch.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 |
TransformationFlattenConditionalBranch::TransformationFlattenConditionalBranch( |
| 24 |
const protobufs::TransformationFlattenConditionalBranch& message) |
| 25 |
: message_(message) {} |
| 26 |
|
| 27 |
TransformationFlattenConditionalBranch::TransformationFlattenConditionalBranch( |
| 28 |
uint32_t header_block_id, bool true_branch_first, |
| 29 |
uint32_t fresh_id_for_bvec2_selector, uint32_t fresh_id_for_bvec3_selector, |
| 30 |
uint32_t fresh_id_for_bvec4_selector, |
| 31 |
const std::vector<protobufs::SideEffectWrapperInfo>& |
| 32 |
side_effect_wrappers_info) { |
| 33 |
message_.set_header_block_id(header_block_id); |
| 34 |
message_.set_true_branch_first(true_branch_first); |
| 35 |
message_.set_fresh_id_for_bvec2_selector(fresh_id_for_bvec2_selector); |
| 36 |
message_.set_fresh_id_for_bvec3_selector(fresh_id_for_bvec3_selector); |
| 37 |
message_.set_fresh_id_for_bvec4_selector(fresh_id_for_bvec4_selector); |
| 38 |
for (auto const& side_effect_wrapper_info : side_effect_wrappers_info) { |
| 39 |
*message_.add_side_effect_wrapper_info() = side_effect_wrapper_info; |
| 40 |
} |
| 41 |
} |
| 42 |
|
| 43 |
bool TransformationFlattenConditionalBranch::IsApplicable( |
| 44 |
opt::IRContext* ir_context, |
| 45 |
const TransformationContext& transformation_context) const { |
| 46 |
auto header_block = |
| 47 |
fuzzerutil::MaybeFindBlock(ir_context, message_.header_block_id()); |
| 48 |
|
| 49 |
// The block must have been found and it must be a selection header. |
| 50 |
if (!header_block || !header_block->GetMergeInst() || |
| 51 |
header_block->GetMergeInst()->opcode() != SpvOpSelectionMerge) { |
| 52 |
return false; |
| 53 |
} |
| 54 |
|
| 55 |
// The header block must end with an OpBranchConditional instruction. |
| 56 |
if (header_block->terminator()->opcode() != SpvOpBranchConditional) { |
| 57 |
return false; |
| 58 |
} |
| 59 |
|
| 60 |
// The branch condition cannot be irrelevant: we will make reference to it |
| 61 |
// multiple times and we need to be guaranteed that these references will |
| 62 |
// yield the same result; if they are replaced by other ids that will not |
| 63 |
// work. |
| 64 |
if (transformation_context.GetFactManager()->IdIsIrrelevant( |
| 65 |
header_block->terminator()->GetSingleWordInOperand(0))) { |
| 66 |
return false; |
| 67 |
} |
| 68 |
|
| 69 |
std::set<uint32_t> used_fresh_ids; |
| 70 |
|
| 71 |
// If ids have been provided to be used as vector guards for OpSelect |
| 72 |
// instructions then they must be fresh. |
| 73 |
for (uint32_t fresh_id_for_bvec_selector : |
| 74 |
{message_.fresh_id_for_bvec2_selector(), |
| 75 |
message_.fresh_id_for_bvec3_selector(), |
| 76 |
message_.fresh_id_for_bvec4_selector()}) { |
| 77 |
if (fresh_id_for_bvec_selector != 0) { |
| 78 |
if (!CheckIdIsFreshAndNotUsedByThisTransformation( |
| 79 |
fresh_id_for_bvec_selector, ir_context, &used_fresh_ids)) { |
| 80 |
return false; |
| 81 |
} |
| 82 |
} |
| 83 |
} |
| 84 |
|
| 85 |
// Use a set to keep track of the instructions that require fresh ids. |
| 86 |
std::set<opt::Instruction*> instructions_that_need_ids; |
| 87 |
|
| 88 |
// Check that, if there are enough ids, the conditional can be flattened and, |
| 89 |
// if so, add all the problematic instructions that need to be enclosed inside |
| 90 |
// conditionals to |instructions_that_need_ids|. |
| 91 |
if (!GetProblematicInstructionsIfConditionalCanBeFlattened( |
| 92 |
ir_context, header_block, transformation_context, |
| 93 |
&instructions_that_need_ids)) { |
| 94 |
return false; |
| 95 |
} |
| 96 |
|
| 97 |
// Get the mapping from instructions to the fresh ids needed to enclose them |
| 98 |
// inside conditionals. |
| 99 |
auto insts_to_wrapper_info = GetInstructionsToWrapperInfo(ir_context); |
| 100 |
|
| 101 |
{ |
| 102 |
// Check the ids in the map. |
| 103 |
for (const auto& inst_to_info : insts_to_wrapper_info) { |
| 104 |
// Check the fresh ids needed for all of the instructions that need to be |
| 105 |
// enclosed inside a conditional. |
| 106 |
for (uint32_t id : {inst_to_info.second.merge_block_id(), |
| 107 |
inst_to_info.second.execute_block_id()}) { |
| 108 |
if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation( |
| 109 |
id, ir_context, &used_fresh_ids)) { |
| 110 |
return false; |
| 111 |
} |
| 112 |
} |
| 113 |
|
| 114 |
// Check the other ids needed, if the instruction needs a placeholder. |
| 115 |
if (InstructionNeedsPlaceholder(ir_context, *inst_to_info.first)) { |
| 116 |
// Check the fresh ids. |
| 117 |
for (uint32_t id : {inst_to_info.second.actual_result_id(), |
| 118 |
inst_to_info.second.alternative_block_id(), |
| 119 |
inst_to_info.second.placeholder_result_id()}) { |
| 120 |
if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation( |
| 121 |
id, ir_context, &used_fresh_ids)) { |
| 122 |
return false; |
| 123 |
} |
| 124 |
} |
| 125 |
|
| 126 |
// Check that the placeholder value id exists, has the right type and is |
| 127 |
// available to use at this point. |
| 128 |
auto value_def = ir_context->get_def_use_mgr()->GetDef( |
| 129 |
inst_to_info.second.value_to_copy_id()); |
| 130 |
if (!value_def || |
| 131 |
value_def->type_id() != inst_to_info.first->type_id() || |
| 132 |
!fuzzerutil::IdIsAvailableBeforeInstruction( |
| 133 |
ir_context, inst_to_info.first, |
| 134 |
inst_to_info.second.value_to_copy_id())) { |
| 135 |
return false; |
| 136 |
} |
| 137 |
} |
| 138 |
} |
| 139 |
} |
| 140 |
|
| 141 |
// If some instructions that require ids are not in the map, the |
| 142 |
// transformation needs overflow ids to be applicable. |
| 143 |
for (auto instruction : instructions_that_need_ids) { |
| 144 |
if (insts_to_wrapper_info.count(instruction) == 0 && |
| 145 |
!transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| 146 |
return false; |
| 147 |
} |
| 148 |
} |
| 149 |
|
| 150 |
if (OpSelectArgumentsAreRestricted(ir_context)) { |
| 151 |
// OpPhi instructions at the convergence block for the selection are handled |
| 152 |
// by turning them into OpSelect instructions. As the SPIR-V version in use |
| 153 |
// has restrictions on the arguments that OpSelect can take, we must check |
| 154 |
// that any OpPhi instructions are compatible with these restrictions. |
| 155 |
uint32_t convergence_block_id = |
| 156 |
FindConvergenceBlock(ir_context, *header_block); |
| 157 |
// Consider every OpPhi instruction at the convergence block. |
| 158 |
if (!ir_context->cfg() |
| 159 |
->block(convergence_block_id) |
| 160 |
->WhileEachPhiInst([this, |
| 161 |
ir_context](opt::Instruction* inst) -> bool { |
| 162 |
// Decide whether the OpPhi can be handled based on its result |
| 163 |
// type. |
| 164 |
opt::Instruction* phi_result_type = |
| 165 |
ir_context->get_def_use_mgr()->GetDef(inst->type_id()); |
| 166 |
switch (phi_result_type->opcode()) { |
| 167 |
case SpvOpTypeBool: |
| 168 |
case SpvOpTypeInt: |
| 169 |
case SpvOpTypeFloat: |
| 170 |
case SpvOpTypePointer: |
| 171 |
// Fine: OpSelect can work directly on scalar and pointer |
| 172 |
// types. |
| 173 |
return true; |
| 174 |
case SpvOpTypeVector: { |
| 175 |
// In its restricted form, OpSelect can only select between |
| 176 |
// vectors if the condition of the select is a boolean |
| 177 |
// boolean vector. We thus require the appropriate boolean |
| 178 |
// vector type to be present. |
| 179 |
uint32_t bool_type_id = |
| 180 |
fuzzerutil::MaybeGetBoolType(ir_context); |
| 181 |
if (!bool_type_id) { |
| 182 |
return false; |
| 183 |
} |
| 184 |
|
| 185 |
uint32_t dimension = |
| 186 |
phi_result_type->GetSingleWordInOperand(1); |
| 187 |
if (fuzzerutil::MaybeGetVectorType(ir_context, bool_type_id, |
| 188 |
dimension) == 0) { |
| 189 |
// The required boolean vector type is not present. |
| 190 |
return false; |
| 191 |
} |
| 192 |
// The transformation needs to be equipped with a fresh id |
| 193 |
// in which to store the vectorized version of the selection |
| 194 |
// construct's condition. |
| 195 |
switch (dimension) { |
| 196 |
case 2: |
| 197 |
return message_.fresh_id_for_bvec2_selector() != 0; |
| 198 |
case 3: |
| 199 |
return message_.fresh_id_for_bvec3_selector() != 0; |
| 200 |
default: |
| 201 |
assert(dimension == 4 && "Invalid vector dimension."); |
| 202 |
return message_.fresh_id_for_bvec4_selector() != 0; |
| 203 |
} |
| 204 |
} |
| 205 |
default: |
| 206 |
return false; |
| 207 |
} |
| 208 |
})) { |
| 209 |
return false; |
| 210 |
} |
| 211 |
} |
| 212 |
|
| 213 |
// All checks were passed. |
| 214 |
return true; |
| 215 |
} |
| 216 |
|
| 217 |
void TransformationFlattenConditionalBranch::Apply( |
| 218 |
opt::IRContext* ir_context, |
| 219 |
TransformationContext* transformation_context) const { |
| 220 |
// branch = 1 corresponds to the true branch, branch = 2 corresponds to the |
| 221 |
// false branch. If the true branch is to be laid out first, we need to visit |
| 222 |
// the false branch first, because each branch is moved to right after the |
| 223 |
// header while it is visited. |
| 224 |
std::vector<uint32_t> branches = {2, 1}; |
| 225 |
if (!message_.true_branch_first()) { |
| 226 |
// Similarly, we need to visit the true branch first, if we want it to be |
| 227 |
// laid out after the false branch. |
| 228 |
branches = {1, 2}; |
| 229 |
} |
| 230 |
|
| 231 |
auto header_block = ir_context->cfg()->block(message_.header_block_id()); |
| 232 |
|
| 233 |
// Get the ids of the starting blocks of the first and last branches to be |
| 234 |
// laid out. The first branch is the true branch iff |
| 235 |
// |message_.true_branch_first| is true. |
| 236 |
auto branch_instruction = header_block->terminator(); |
| 237 |
uint32_t first_block_first_branch_id = |
| 238 |
branch_instruction->GetSingleWordInOperand(branches[1]); |
| 239 |
uint32_t first_block_last_branch_id = |
| 240 |
branch_instruction->GetSingleWordInOperand(branches[0]); |
| 241 |
|
| 242 |
uint32_t convergence_block_id = |
| 243 |
FindConvergenceBlock(ir_context, *header_block); |
| 244 |
|
| 245 |
// If the OpBranchConditional instruction in the header branches to the same |
| 246 |
// block for both values of the condition, this is the convergence block (the |
| 247 |
// flow does not actually diverge) and the OpPhi instructions in it are still |
| 248 |
// valid, so we do not need to make any changes. |
| 249 |
if (first_block_first_branch_id != first_block_last_branch_id) { |
| 250 |
RewriteOpPhiInstructionsAtConvergenceBlock( |
| 251 |
*header_block, convergence_block_id, ir_context); |
| 252 |
} |
| 253 |
|
| 254 |
// Get the mapping from instructions to fresh ids. |
| 255 |
auto insts_to_info = GetInstructionsToWrapperInfo(ir_context); |
| 256 |
|
| 257 |
// Get a reference to the last block in the first branch that will be laid out |
| 258 |
// (this depends on |message_.true_branch_first|). The last block is the block |
| 259 |
// in the branch just before flow converges (it might not exist). |
| 260 |
opt::BasicBlock* last_block_first_branch = nullptr; |
| 261 |
|
| 262 |
// Keep track of blocks and ids for which we should later add dead block and |
| 263 |
// irrelevant id facts. We wait until we have finished applying the |
| 264 |
// transformation before adding these facts, so that the fact manager has |
| 265 |
// access to the fully up-to-date module. |
| 266 |
std::vector<uint32_t> dead_blocks; |
| 267 |
std::vector<uint32_t> irrelevant_ids; |
| 268 |
|
| 269 |
// Adjust the conditional branches by enclosing problematic instructions |
| 270 |
// within conditionals and get references to the last block in each branch. |
| 271 |
for (uint32_t branch : branches) { |
| 272 |
auto current_block = header_block; |
| 273 |
// Get the id of the first block in this branch. |
| 274 |
uint32_t next_block_id = branch_instruction->GetSingleWordInOperand(branch); |
| 275 |
|
| 276 |
// Consider all blocks in the branch until the convergence block is reached. |
| 277 |
while (next_block_id != convergence_block_id) { |
| 278 |
// Move the next block to right after the current one. |
| 279 |
current_block->GetParent()->MoveBasicBlockToAfter(next_block_id, |
| 280 |
current_block); |
| 281 |
|
| 282 |
// Move forward in the branch. |
| 283 |
current_block = ir_context->cfg()->block(next_block_id); |
| 284 |
|
| 285 |
// Find all the instructions in the current block which need to be |
| 286 |
// enclosed inside conditionals. |
| 287 |
std::vector<opt::Instruction*> problematic_instructions; |
| 288 |
|
| 289 |
current_block->ForEachInst( |
| 290 |
[&problematic_instructions](opt::Instruction* instruction) { |
| 291 |
if (instruction->opcode() != SpvOpLabel && |
| 292 |
instruction->opcode() != SpvOpBranch && |
| 293 |
!fuzzerutil::InstructionHasNoSideEffects(*instruction)) { |
| 294 |
problematic_instructions.push_back(instruction); |
| 295 |
} |
| 296 |
}); |
| 297 |
|
| 298 |
uint32_t condition_id = |
| 299 |
header_block->terminator()->GetSingleWordInOperand(0); |
| 300 |
|
| 301 |
// Enclose all of the problematic instructions in conditionals, with the |
| 302 |
// same condition as the selection construct being flattened. |
| 303 |
for (auto instruction : problematic_instructions) { |
| 304 |
// Get the info needed by this instruction to wrap it inside a |
| 305 |
// conditional. |
| 306 |
protobufs::SideEffectWrapperInfo wrapper_info; |
| 307 |
|
| 308 |
if (insts_to_info.count(instruction) != 0) { |
| 309 |
// Get the fresh ids from the map, if present. |
| 310 |
wrapper_info = insts_to_info[instruction]; |
| 311 |
} else { |
| 312 |
// If we could not get it from the map, use overflow ids. We don't |
| 313 |
// need to set |wrapper_info.instruction|, as it will not be used. |
| 314 |
wrapper_info.set_merge_block_id( |
| 315 |
transformation_context->GetOverflowIdSource() |
| 316 |
->GetNextOverflowId()); |
| 317 |
wrapper_info.set_execute_block_id( |
| 318 |
transformation_context->GetOverflowIdSource() |
| 319 |
->GetNextOverflowId()); |
| 320 |
|
| 321 |
if (InstructionNeedsPlaceholder(ir_context, *instruction)) { |
| 322 |
// Ge the fresh ids from the overflow ids. |
| 323 |
wrapper_info.set_actual_result_id( |
| 324 |
transformation_context->GetOverflowIdSource() |
| 325 |
->GetNextOverflowId()); |
| 326 |
wrapper_info.set_alternative_block_id( |
| 327 |
transformation_context->GetOverflowIdSource() |
| 328 |
->GetNextOverflowId()); |
| 329 |
wrapper_info.set_placeholder_result_id( |
| 330 |
transformation_context->GetOverflowIdSource() |
| 331 |
->GetNextOverflowId()); |
| 332 |
|
| 333 |
// Try to find a zero constant. It does not matter whether it is |
| 334 |
// relevant or irrelevant. |
| 335 |
for (bool is_irrelevant : {true, false}) { |
| 336 |
wrapper_info.set_value_to_copy_id( |
| 337 |
fuzzerutil::MaybeGetZeroConstant( |
| 338 |
ir_context, *transformation_context, |
| 339 |
instruction->type_id(), is_irrelevant)); |
| 340 |
if (wrapper_info.value_to_copy_id()) { |
| 341 |
break; |
| 342 |
} |
| 343 |
} |
| 344 |
} |
| 345 |
} |
| 346 |
|
| 347 |
// Enclose the instruction in a conditional and get the merge block |
| 348 |
// generated by this operation (this is where all the following |
| 349 |
// instructions will be). |
| 350 |
current_block = EncloseInstructionInConditional( |
| 351 |
ir_context, *transformation_context, current_block, instruction, |
| 352 |
wrapper_info, condition_id, branch == 1, &dead_blocks, |
| 353 |
&irrelevant_ids); |
| 354 |
} |
| 355 |
|
| 356 |
next_block_id = current_block->terminator()->GetSingleWordInOperand(0); |
| 357 |
|
| 358 |
// If the next block is the convergence block and this the branch that |
| 359 |
// will be laid out right after the header, record this as the last block |
| 360 |
// in the first branch. |
| 361 |
if (next_block_id == convergence_block_id && branch == branches[1]) { |
| 362 |
last_block_first_branch = current_block; |
| 363 |
} |
| 364 |
} |
| 365 |
} |
| 366 |
|
| 367 |
// The current header should unconditionally branch to the starting block in |
| 368 |
// the first branch to be laid out, if such a branch exists (i.e. the header |
| 369 |
// does not branch directly to the convergence block), and to the starting |
| 370 |
// block in the last branch to be laid out otherwise. |
| 371 |
uint32_t after_header = first_block_first_branch_id != convergence_block_id |
| 372 |
? first_block_first_branch_id |
| 373 |
: first_block_last_branch_id; |
| 374 |
|
| 375 |
// Kill the merge instruction and the branch instruction in the current |
| 376 |
// header. |
| 377 |
auto merge_inst = header_block->GetMergeInst(); |
| 378 |
ir_context->KillInst(branch_instruction); |
| 379 |
ir_context->KillInst(merge_inst); |
| 380 |
|
| 381 |
// Add a new, unconditional, branch instruction from the current header to |
| 382 |
// |after_header|. |
| 383 |
header_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 384 |
ir_context, SpvOpBranch, 0, 0, |
| 385 |
opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {after_header}}})); |
| 386 |
|
| 387 |
// If the first branch to be laid out exists, change the branch instruction so |
| 388 |
// that the last block in such branch unconditionally branches to the first |
| 389 |
// block in the other branch (or the convergence block if there is no other |
| 390 |
// branch) and change the OpPhi instructions in the last branch accordingly |
| 391 |
// (the predecessor changed). |
| 392 |
if (last_block_first_branch) { |
| 393 |
last_block_first_branch->terminator()->SetInOperand( |
| 394 |
0, {first_block_last_branch_id}); |
| 395 |
|
| 396 |
// Change the OpPhi instructions of the last branch (if there is another |
| 397 |
// branch) so that the predecessor is now the last block of the first |
| 398 |
// branch. The block must have a single predecessor, so the operand |
| 399 |
// specifying the predecessor is always in the same position. |
| 400 |
if (first_block_last_branch_id != convergence_block_id) { |
| 401 |
ir_context->get_instr_block(first_block_last_branch_id) |
| 402 |
->ForEachPhiInst( |
| 403 |
[&last_block_first_branch](opt::Instruction* phi_inst) { |
| 404 |
// The operand specifying the predecessor is the second input |
| 405 |
// operand. |
| 406 |
phi_inst->SetInOperand(1, {last_block_first_branch->id()}); |
| 407 |
}); |
| 408 |
} |
| 409 |
} |
| 410 |
|
| 411 |
// Invalidate all analyses |
| 412 |
ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone); |
| 413 |
|
| 414 |
// Now that we have finished adding blocks and ids to the module and |
| 415 |
// invalidated existing analyses, update the fact manager regarding dead |
| 416 |
// blocks and irrelevant ids. |
| 417 |
for (auto dead_block : dead_blocks) { |
| 418 |
transformation_context->GetFactManager()->AddFactBlockIsDead(dead_block); |
| 419 |
} |
| 420 |
for (auto irrelevant_id : irrelevant_ids) { |
| 421 |
transformation_context->GetFactManager()->AddFactIdIsIrrelevant( |
| 422 |
irrelevant_id); |
| 423 |
} |
| 424 |
} |
| 425 |
|
| 426 |
protobufs::Transformation TransformationFlattenConditionalBranch::ToMessage() |
| 427 |
const { |
| 428 |
protobufs::Transformation result; |
| 429 |
*result.mutable_flatten_conditional_branch() = message_; |
| 430 |
return result; |
| 431 |
} |
| 432 |
|
| 433 |
bool TransformationFlattenConditionalBranch:: |
| 434 |
GetProblematicInstructionsIfConditionalCanBeFlattened( |
| 435 |
opt::IRContext* ir_context, opt::BasicBlock* header, |
| 436 |
const TransformationContext& transformation_context, |
| 437 |
std::set<opt::Instruction*>* instructions_that_need_ids) { |
| 438 |
uint32_t merge_block_id = header->MergeBlockIdIfAny(); |
| 439 |
assert(merge_block_id && |
| 440 |
header->GetMergeInst()->opcode() == SpvOpSelectionMerge && |
| 441 |
header->terminator()->opcode() == SpvOpBranchConditional && |
| 442 |
"|header| must be the header of a conditional."); |
| 443 |
|
| 444 |
auto enclosing_function = header->GetParent(); |
| 445 |
auto dominator_analysis = |
| 446 |
ir_context->GetDominatorAnalysis(enclosing_function); |
| 447 |
auto postdominator_analysis = |
| 448 |
ir_context->GetPostDominatorAnalysis(enclosing_function); |
| 449 |
|
| 450 |
// |header| must be reachable. |
| 451 |
if (!dominator_analysis->IsReachable(header)) { |
| 452 |
return false; |
| 453 |
} |
| 454 |
|
| 455 |
// Check that the header and the merge block describe a single-entry, |
| 456 |
// single-exit region. |
| 457 |
if (!dominator_analysis->Dominates(header->id(), merge_block_id) || |
| 458 |
!postdominator_analysis->Dominates(merge_block_id, header->id())) { |
| 459 |
return false; |
| 460 |
} |
| 461 |
|
| 462 |
// Traverse the CFG starting from the header and check that, for all the |
| 463 |
// blocks that can be reached by the header before the flow converges: |
| 464 |
// - they don't contain merge, barrier or OpSampledImage instructions |
| 465 |
// - they branch unconditionally to another block |
| 466 |
// Add any side-effecting instruction, requiring fresh ids, to |
| 467 |
// |instructions_that_need_ids| |
| 468 |
std::queue<uint32_t> to_check; |
| 469 |
header->ForEachSuccessorLabel( |
| 470 |
[&to_check](uint32_t label) { to_check.push(label); }); |
| 471 |
|
| 472 |
auto* structured_cfg = ir_context->GetStructuredCFGAnalysis(); |
| 473 |
while (!to_check.empty()) { |
| 474 |
uint32_t block_id = to_check.front(); |
| 475 |
to_check.pop(); |
| 476 |
|
| 477 |
if (structured_cfg->ContainingConstruct(block_id) != header->id() && |
| 478 |
block_id != merge_block_id) { |
| 479 |
// This block can be reached from the |header| but doesn't belong to its |
| 480 |
// selection construct. This might be a continue target of some loop - |
| 481 |
// we can't flatten the |header|. |
| 482 |
return false; |
| 483 |
} |
| 484 |
|
| 485 |
// If the block post-dominates the header, this is where flow converges, and |
| 486 |
// we don't need to check this branch any further, because the |
| 487 |
// transformation will only change the part of the graph where flow is |
| 488 |
// divergent. |
| 489 |
if (postdominator_analysis->Dominates(block_id, header->id())) { |
| 490 |
continue; |
| 491 |
} |
| 492 |
|
| 493 |
if (!transformation_context.GetFactManager()->BlockIsDead(header->id()) && |
| 494 |
transformation_context.GetFactManager()->BlockIsDead(block_id)) { |
| 495 |
// The |header| is not dead but the |block_id| is. Since |block_id| |
| 496 |
// doesn't postdominate the |header|, CFG hasn't converged yet. Thus, we |
| 497 |
// don't flatten the construct to prevent |block_id| from becoming |
| 498 |
// executable. |
| 499 |
return false; |
| 500 |
} |
| 501 |
|
| 502 |
auto block = ir_context->cfg()->block(block_id); |
| 503 |
|
| 504 |
// The block must not have a merge instruction, because inner constructs are |
| 505 |
// not allowed. |
| 506 |
if (block->GetMergeInst()) { |
| 507 |
return false; |
| 508 |
} |
| 509 |
|
| 510 |
// The terminator instruction for the block must be OpBranch. |
| 511 |
if (block->terminator()->opcode() != SpvOpBranch) { |
| 512 |
return false; |
| 513 |
} |
| 514 |
|
| 515 |
// Check all of the instructions in the block. |
| 516 |
bool all_instructions_compatible = |
| 517 |
block->WhileEachInst([ir_context, instructions_that_need_ids]( |
| 518 |
opt::Instruction* instruction) { |
| 519 |
// We can ignore OpLabel instructions. |
| 520 |
if (instruction->opcode() == SpvOpLabel) { |
| 521 |
return true; |
| 522 |
} |
| 523 |
|
| 524 |
// If the instruction is a branch, it must be an unconditional branch. |
| 525 |
if (instruction->IsBranch()) { |
| 526 |
return instruction->opcode() == SpvOpBranch; |
| 527 |
} |
| 528 |
|
| 529 |
// We cannot go ahead if we encounter an instruction that cannot be |
| 530 |
// handled. |
| 531 |
if (!InstructionCanBeHandled(ir_context, *instruction)) { |
| 532 |
return false; |
| 533 |
} |
| 534 |
|
| 535 |
// If the instruction has side effects, add it to the |
| 536 |
// |instructions_that_need_ids| set. |
| 537 |
if (!fuzzerutil::InstructionHasNoSideEffects(*instruction)) { |
| 538 |
instructions_that_need_ids->emplace(instruction); |
| 539 |
} |
| 540 |
|
| 541 |
return true; |
| 542 |
}); |
| 543 |
|
| 544 |
if (!all_instructions_compatible) { |
| 545 |
return false; |
| 546 |
} |
| 547 |
|
| 548 |
// Add the successor of this block to the list of blocks that need to be |
| 549 |
// checked. |
| 550 |
to_check.push(block->terminator()->GetSingleWordInOperand(0)); |
| 551 |
} |
| 552 |
|
| 553 |
// All the blocks are compatible with the transformation and this is indeed a |
| 554 |
// single-entry, single-exit region. |
| 555 |
return true; |
| 556 |
} |
| 557 |
|
| 558 |
bool TransformationFlattenConditionalBranch::InstructionNeedsPlaceholder( |
| 559 |
opt::IRContext* ir_context, const opt::Instruction& instruction) { |
| 560 |
assert(!fuzzerutil::InstructionHasNoSideEffects(instruction) && |
| 561 |
InstructionCanBeHandled(ir_context, instruction) && |
| 562 |
"The instruction must have side effects and it must be possible to " |
| 563 |
"enclose it inside a conditional."); |
| 564 |
|
| 565 |
if (instruction.HasResultId()) { |
| 566 |
// We need a placeholder iff the type is not Void. |
| 567 |
auto type = ir_context->get_type_mgr()->GetType(instruction.type_id()); |
| 568 |
return type && !type->AsVoid(); |
| 569 |
} |
| 570 |
|
| 571 |
return false; |
| 572 |
} |
| 573 |
|
| 574 |
std::unordered_map<opt::Instruction*, protobufs::SideEffectWrapperInfo> |
| 575 |
TransformationFlattenConditionalBranch::GetInstructionsToWrapperInfo( |
| 576 |
opt::IRContext* ir_context) const { |
| 577 |
std::unordered_map<opt::Instruction*, protobufs::SideEffectWrapperInfo> |
| 578 |
instructions_to_ids; |
| 579 |
for (const auto& wrapper_info : message_.side_effect_wrapper_info()) { |
| 580 |
auto instruction = FindInstruction(wrapper_info.instruction(), ir_context); |
| 581 |
if (instruction) { |
| 582 |
instructions_to_ids.emplace(instruction, wrapper_info); |
| 583 |
} |
| 584 |
} |
| 585 |
|
| 586 |
return instructions_to_ids; |
| 587 |
} |
| 588 |
|
| 589 |
opt::BasicBlock* |
| 590 |
TransformationFlattenConditionalBranch::EncloseInstructionInConditional( |
| 591 |
opt::IRContext* ir_context, |
| 592 |
const TransformationContext& transformation_context, opt::BasicBlock* block, |
| 593 |
opt::Instruction* instruction, |
| 594 |
const protobufs::SideEffectWrapperInfo& wrapper_info, uint32_t condition_id, |
| 595 |
bool exec_if_cond_true, std::vector<uint32_t>* dead_blocks, |
| 596 |
std::vector<uint32_t>* irrelevant_ids) { |
| 597 |
// Get the next instruction (it will be useful for splitting). |
| 598 |
auto next_instruction = instruction->NextNode(); |
| 599 |
|
| 600 |
// Update the module id bound. |
| 601 |
for (uint32_t id : |
| 602 |
{wrapper_info.merge_block_id(), wrapper_info.execute_block_id()}) { |
| 603 |
fuzzerutil::UpdateModuleIdBound(ir_context, id); |
| 604 |
} |
| 605 |
|
| 606 |
// Create the block where the instruction is executed by splitting the |
| 607 |
// original block. |
| 608 |
auto execute_block = block->SplitBasicBlock( |
| 609 |
ir_context, wrapper_info.execute_block_id(), |
| 610 |
fuzzerutil::GetIteratorForInstruction(block, instruction)); |
| 611 |
|
| 612 |
// Create the merge block for the conditional that we are about to create by |
| 613 |
// splitting execute_block (this will leave |instruction| as the only |
| 614 |
// instruction in |execute_block|). |
| 615 |
auto merge_block = execute_block->SplitBasicBlock( |
| 616 |
ir_context, wrapper_info.merge_block_id(), |
| 617 |
fuzzerutil::GetIteratorForInstruction(execute_block, next_instruction)); |
| 618 |
|
| 619 |
// Propagate the fact that the block is dead to the newly-created blocks. |
| 620 |
if (transformation_context.GetFactManager()->BlockIsDead(block->id())) { |
| 621 |
dead_blocks->emplace_back(execute_block->id()); |
| 622 |
dead_blocks->emplace_back(merge_block->id()); |
| 623 |
} |
| 624 |
|
| 625 |
// Initially, consider the merge block as the alternative block to branch to |
| 626 |
// if the instruction should not be executed. |
| 627 |
auto alternative_block = merge_block; |
| 628 |
|
| 629 |
// Add an unconditional branch from |execute_block| to |merge_block|. |
| 630 |
execute_block->AddInstruction(MakeUnique<opt::Instruction>( |
| 631 |
ir_context, SpvOpBranch, 0, 0, |
| 632 |
opt::Instruction::OperandList{ |
| 633 |
{SPV_OPERAND_TYPE_ID, {merge_block->id()}}})); |
| 634 |
|
| 635 |
// If the instruction requires a placeholder, it means that it has a result id |
| 636 |
// and its result needs to be able to be used later on, and we need to: |
| 637 |
// - add an additional block |ids.alternative_block_id| where a placeholder |
| 638 |
// result id (using fresh id |ids.placeholder_result_id|) is obtained either |
| 639 |
// by using OpCopyObject and copying |ids.value_to_copy_id| or, if such id |
| 640 |
// was not given and a suitable constant was not found, by using OpUndef. |
| 641 |
// - mark |ids.placeholder_result_id| as irrelevant |
| 642 |
// - change the result id of the instruction to a fresh id |
| 643 |
// (|ids.actual_result_id|). |
| 644 |
// - add an OpPhi instruction, which will have the original result id of the |
| 645 |
// instruction, in the merge block. |
| 646 |
if (InstructionNeedsPlaceholder(ir_context, *instruction)) { |
| 647 |
// Update the module id bound with the additional ids. |
| 648 |
for (uint32_t id : |
| 649 |
{wrapper_info.actual_result_id(), wrapper_info.alternative_block_id(), |
| 650 |
wrapper_info.placeholder_result_id()}) { |
| 651 |
fuzzerutil::UpdateModuleIdBound(ir_context, id); |
| 652 |
} |
| 653 |
|
| 654 |
// Create a new block using |fresh_ids.alternative_block_id| for its label. |
| 655 |
auto alternative_block_temp = |
| 656 |
MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>( |
| 657 |
ir_context, SpvOpLabel, 0, wrapper_info.alternative_block_id(), |
| 658 |
opt::Instruction::OperandList{})); |
| 659 |
|
| 660 |
// Keep the original result id of the instruction in a variable. |
| 661 |
uint32_t original_result_id = instruction->result_id(); |
| 662 |
|
| 663 |
// Set the result id of the instruction to be |ids.actual_result_id|. |
| 664 |
instruction->SetResultId(wrapper_info.actual_result_id()); |
| 665 |
|
| 666 |
// Add a placeholder instruction, with the same type as the original |
| 667 |
// instruction and id |ids.placeholder_result_id|, to the new block. |
| 668 |
if (wrapper_info.value_to_copy_id()) { |
| 669 |
// If there is an available id to copy from, the placeholder instruction |
| 670 |
// will be %placeholder_result_id = OpCopyObject %type %value_to_copy_id |
| 671 |
alternative_block_temp->AddInstruction(MakeUnique<opt::Instruction>( |
| 672 |
ir_context, SpvOpCopyObject, instruction->type_id(), |
| 673 |
wrapper_info.placeholder_result_id(), |
| 674 |
opt::Instruction::OperandList{ |
| 675 |
{SPV_OPERAND_TYPE_ID, {wrapper_info.value_to_copy_id()}}})); |
| 676 |
} else { |
| 677 |
// If there is no such id, use an OpUndef instruction. |
| 678 |
alternative_block_temp->AddInstruction(MakeUnique<opt::Instruction>( |
| 679 |
ir_context, SpvOpUndef, instruction->type_id(), |
| 680 |
wrapper_info.placeholder_result_id(), |
| 681 |
opt::Instruction::OperandList{})); |
| 682 |
} |
| 683 |
|
| 684 |
// Mark |ids.placeholder_result_id| as irrelevant. |
| 685 |
irrelevant_ids->emplace_back(wrapper_info.placeholder_result_id()); |
| 686 |
|
| 687 |
// Add an unconditional branch from the new block to the merge block. |
| 688 |
alternative_block_temp->AddInstruction(MakeUnique<opt::Instruction>( |
| 689 |
ir_context, SpvOpBranch, 0, 0, |
| 690 |
opt::Instruction::OperandList{ |
| 691 |
{SPV_OPERAND_TYPE_ID, {merge_block->id()}}})); |
| 692 |
|
| 693 |
// Insert the block before the merge block. |
| 694 |
alternative_block = block->GetParent()->InsertBasicBlockBefore( |
| 695 |
std::move(alternative_block_temp), merge_block); |
| 696 |
|
| 697 |
// Using the original instruction result id, add an OpPhi instruction to the |
| 698 |
// merge block, which will either take the value of the result of the |
| 699 |
// instruction or the placeholder value defined in the alternative block. |
| 700 |
merge_block->begin().InsertBefore(MakeUnique<opt::Instruction>( |
| 701 |
ir_context, SpvOpPhi, instruction->type_id(), original_result_id, |
| 702 |
opt::Instruction::OperandList{ |
| 703 |
{SPV_OPERAND_TYPE_ID, {instruction->result_id()}}, |
| 704 |
{SPV_OPERAND_TYPE_ID, {execute_block->id()}}, |
| 705 |
{SPV_OPERAND_TYPE_ID, {wrapper_info.placeholder_result_id()}}, |
| 706 |
{SPV_OPERAND_TYPE_ID, {alternative_block->id()}}})); |
| 707 |
|
| 708 |
// Propagate the fact that the block is dead to the new block. |
| 709 |
if (transformation_context.GetFactManager()->BlockIsDead(block->id())) { |
| 710 |
dead_blocks->emplace_back(alternative_block->id()); |
| 711 |
} |
| 712 |
} |
| 713 |
|
| 714 |
// Depending on whether the instruction should be executed in the if branch or |
| 715 |
// in the else branch, get the corresponding ids. |
| 716 |
auto if_block_id = (exec_if_cond_true ? execute_block : alternative_block) |
| 717 |
->GetLabel() |
| 718 |
->result_id(); |
| 719 |
auto else_block_id = (exec_if_cond_true ? alternative_block : execute_block) |
| 720 |
->GetLabel() |
| 721 |
->result_id(); |
| 722 |
|
| 723 |
// Add an OpSelectionMerge instruction to the block. |
| 724 |
block->AddInstruction(MakeUnique<opt::Instruction>( |
| 725 |
ir_context, SpvOpSelectionMerge, 0, 0, |
| 726 |
opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {merge_block->id()}}, |
| 727 |
{SPV_OPERAND_TYPE_SELECTION_CONTROL, |
| 728 |
{SpvSelectionControlMaskNone}}})); |
| 729 |
|
| 730 |
// Add an OpBranchConditional, to the block, using |condition_id| as the |
| 731 |
// condition and branching to |if_block_id| if the condition is true and to |
| 732 |
// |else_block_id| if the condition is false. |
| 733 |
block->AddInstruction(MakeUnique<opt::Instruction>( |
| 734 |
ir_context, SpvOpBranchConditional, 0, 0, |
| 735 |
opt::Instruction::OperandList{{SPV_OPERAND_TYPE_ID, {condition_id}}, |
| 736 |
{SPV_OPERAND_TYPE_ID, {if_block_id}}, |
| 737 |
{SPV_OPERAND_TYPE_ID, {else_block_id}}})); |
| 738 |
|
| 739 |
return merge_block; |
| 740 |
} |
| 741 |
|
| 742 |
bool TransformationFlattenConditionalBranch::InstructionCanBeHandled( |
| 743 |
opt::IRContext* ir_context, const opt::Instruction& instruction) { |
| 744 |
// We can handle all instructions with no side effects. |
| 745 |
if (fuzzerutil::InstructionHasNoSideEffects(instruction)) { |
| 746 |
return true; |
| 747 |
} |
| 748 |
|
| 749 |
// We cannot handle barrier instructions, while we should be able to handle |
| 750 |
// all other instructions by enclosing them inside a conditional. |
| 751 |
if (instruction.opcode() == SpvOpControlBarrier || |
| 752 |
instruction.opcode() == SpvOpMemoryBarrier || |
| 753 |
instruction.opcode() == SpvOpNamedBarrierInitialize || |
| 754 |
instruction.opcode() == SpvOpMemoryNamedBarrier || |
| 755 |
instruction.opcode() == SpvOpTypeNamedBarrier) { |
| 756 |
return false; |
| 757 |
} |
| 758 |
|
| 759 |
// We cannot handle OpSampledImage instructions, as they need to be in the |
| 760 |
// same block as their use. |
| 761 |
if (instruction.opcode() == SpvOpSampledImage) { |
| 762 |
return false; |
| 763 |
} |
| 764 |
|
| 765 |
// We cannot handle a sampled image load, because we re-work loads using |
| 766 |
// conditional branches and OpPhi instructions, and the result type of OpPhi |
| 767 |
// cannot be OpTypeSampledImage. |
| 768 |
if (instruction.opcode() == SpvOpLoad && |
| 769 |
ir_context->get_def_use_mgr()->GetDef(instruction.type_id())->opcode() == |
| 770 |
SpvOpTypeSampledImage) { |
| 771 |
return false; |
| 772 |
} |
| 773 |
|
| 774 |
// We cannot handle instructions with an id which return a void type, if the |
| 775 |
// result id is used in the module (e.g. a function call to a function that |
| 776 |
// returns nothing). |
| 777 |
if (instruction.HasResultId()) { |
| 778 |
auto type = ir_context->get_type_mgr()->GetType(instruction.type_id()); |
| 779 |
assert(type && "The type should be found in the module"); |
| 780 |
|
| 781 |
if (type->AsVoid() && |
| 782 |
!ir_context->get_def_use_mgr()->WhileEachUse( |
| 783 |
instruction.result_id(), |
| 784 |
[](opt::Instruction* use_inst, uint32_t use_index) { |
| 785 |
// Return false if the id is used as an input operand. |
| 786 |
return use_index < |
| 787 |
use_inst->NumOperands() - use_inst->NumInOperands(); |
| 788 |
})) { |
| 789 |
return false; |
| 790 |
} |
| 791 |
} |
| 792 |
|
| 793 |
return true; |
| 794 |
} |
| 795 |
|
| 796 |
std::unordered_set<uint32_t> |
| 797 |
TransformationFlattenConditionalBranch::GetFreshIds() const { |
| 798 |
std::unordered_set<uint32_t> result = { |
| 799 |
message_.fresh_id_for_bvec2_selector(), |
| 800 |
message_.fresh_id_for_bvec3_selector(), |
| 801 |
message_.fresh_id_for_bvec4_selector()}; |
| 802 |
for (auto& side_effect_wrapper_info : message_.side_effect_wrapper_info()) { |
| 803 |
result.insert(side_effect_wrapper_info.merge_block_id()); |
| 804 |
result.insert(side_effect_wrapper_info.execute_block_id()); |
| 805 |
result.insert(side_effect_wrapper_info.actual_result_id()); |
| 806 |
result.insert(side_effect_wrapper_info.alternative_block_id()); |
| 807 |
result.insert(side_effect_wrapper_info.placeholder_result_id()); |
| 808 |
} |
| 809 |
return result; |
| 810 |
} |
| 811 |
|
| 812 |
uint32_t TransformationFlattenConditionalBranch::FindConvergenceBlock( |
| 813 |
opt::IRContext* ir_context, const opt::BasicBlock& header_block) { |
| 814 |
uint32_t result = header_block.terminator()->GetSingleWordInOperand(1); |
| 815 |
auto postdominator_analysis = |
| 816 |
ir_context->GetPostDominatorAnalysis(header_block.GetParent()); |
| 817 |
while (!postdominator_analysis->Dominates(result, header_block.id())) { |
| 818 |
auto current_block = ir_context->get_instr_block(result); |
| 819 |
// If the transformation is applicable, the terminator is OpBranch. |
| 820 |
result = current_block->terminator()->GetSingleWordInOperand(0); |
| 821 |
} |
| 822 |
return result; |
| 823 |
} |
| 824 |
|
| 825 |
bool TransformationFlattenConditionalBranch::OpSelectArgumentsAreRestricted( |
| 826 |
opt::IRContext* ir_context) { |
| 827 |
switch (ir_context->grammar().target_env()) { |
| 828 |
case SPV_ENV_UNIVERSAL_1_0: |
| 829 |
case SPV_ENV_UNIVERSAL_1_1: |
| 830 |
case SPV_ENV_UNIVERSAL_1_2: |
| 831 |
case SPV_ENV_UNIVERSAL_1_3: { |
| 832 |
return true; |
| 833 |
} |
| 834 |
default: |
| 835 |
return false; |
| 836 |
} |
| 837 |
} |
| 838 |
|
| 839 |
void TransformationFlattenConditionalBranch::AddBooleanVectorConstructorToBlock( |
| 840 |
uint32_t fresh_id, uint32_t dimension, |
| 841 |
const opt::Operand& branch_condition_operand, opt::IRContext* ir_context, |
| 842 |
opt::BasicBlock* block) { |
| 843 |
opt::Instruction::OperandList in_operands; |
| 844 |
for (uint32_t i = 0; i < dimension; i++) { |
| 845 |
in_operands.emplace_back(branch_condition_operand); |
| 846 |
} |
| 847 |
block->begin()->InsertBefore(MakeUnique<opt::Instruction>( |
| 848 |
ir_context, SpvOpCompositeConstruct, |
| 849 |
fuzzerutil::MaybeGetVectorType( |
| 850 |
ir_context, fuzzerutil::MaybeGetBoolType(ir_context), dimension), |
| 851 |
fresh_id, in_operands)); |
| 852 |
fuzzerutil::UpdateModuleIdBound(ir_context, fresh_id); |
| 853 |
} |
| 854 |
|
| 855 |
void TransformationFlattenConditionalBranch:: |
| 856 |
RewriteOpPhiInstructionsAtConvergenceBlock( |
| 857 |
const opt::BasicBlock& header_block, uint32_t convergence_block_id, |
| 858 |
opt::IRContext* ir_context) const { |
| 859 |
const opt::Instruction& branch_instruction = *header_block.terminator(); |
| 860 |
|
| 861 |
const opt::Operand& branch_condition_operand = |
| 862 |
branch_instruction.GetInOperand(0); |
| 863 |
|
| 864 |
// If we encounter OpPhi instructions on vector types then we may need to |
| 865 |
// introduce vector versions of the selection construct's condition to use |
| 866 |
// in corresponding OpSelect instructions. These booleans track whether we |
| 867 |
// need to introduce such boolean vectors. |
| 868 |
bool require_2d_boolean_vector = false; |
| 869 |
bool require_3d_boolean_vector = false; |
| 870 |
bool require_4d_boolean_vector = false; |
| 871 |
|
| 872 |
// Consider every OpPhi instruction at the convergence block. |
| 873 |
opt::BasicBlock* convergence_block = |
| 874 |
ir_context->get_instr_block(convergence_block_id); |
| 875 |
convergence_block->ForEachPhiInst( |
| 876 |
[this, &branch_condition_operand, branch_instruction, |
| 877 |
convergence_block_id, &header_block, ir_context, |
| 878 |
&require_2d_boolean_vector, &require_3d_boolean_vector, |
| 879 |
&require_4d_boolean_vector](opt::Instruction* phi_inst) { |
| 880 |
assert(phi_inst->NumInOperands() == 4 && |
| 881 |
"We are going to replace an OpPhi with an OpSelect. This " |
| 882 |
"only makes sense if the block has two distinct " |
| 883 |
"predecessors."); |
| 884 |
// We are going to replace the OpPhi with an OpSelect. By default, |
| 885 |
// the condition for the OpSelect will be the branch condition's |
| 886 |
// operand. However, if the OpPhi has vector result type we may need |
| 887 |
// to use a boolean vector as the condition instead. |
| 888 |
opt::Operand selector_operand = branch_condition_operand; |
| 889 |
opt::Instruction* type_inst = |
| 890 |
ir_context->get_def_use_mgr()->GetDef(phi_inst->type_id()); |
| 891 |
if (type_inst->opcode() == SpvOpTypeVector) { |
| 892 |
uint32_t dimension = type_inst->GetSingleWordInOperand(1); |
| 893 |
switch (dimension) { |
| 894 |
case 2: |
| 895 |
// The OpPhi's result type is a 2D vector. If a fresh id for a |
| 896 |
// bvec2 selector was provided then we should use it as the |
| 897 |
// OpSelect's condition, and note the fact that we will need to |
| 898 |
// add an instruction to bring this bvec2 into existence. |
| 899 |
if (message_.fresh_id_for_bvec2_selector() != 0) { |
| 900 |
selector_operand = {SPV_OPERAND_TYPE_ID, |
| 901 |
{message_.fresh_id_for_bvec2_selector()}}; |
| 902 |
require_2d_boolean_vector = true; |
| 903 |
} |
| 904 |
break; |
| 905 |
case 3: |
| 906 |
// Similar to the 2D case. |
| 907 |
if (message_.fresh_id_for_bvec3_selector() != 0) { |
| 908 |
selector_operand = {SPV_OPERAND_TYPE_ID, |
| 909 |
{message_.fresh_id_for_bvec3_selector()}}; |
| 910 |
require_3d_boolean_vector = true; |
| 911 |
} |
| 912 |
break; |
| 913 |
case 4: |
| 914 |
// Similar to the 2D case. |
| 915 |
if (message_.fresh_id_for_bvec4_selector() != 0) { |
| 916 |
selector_operand = {SPV_OPERAND_TYPE_ID, |
| 917 |
{message_.fresh_id_for_bvec4_selector()}}; |
| 918 |
require_4d_boolean_vector = true; |
| 919 |
} |
| 920 |
break; |
| 921 |
default: |
| 922 |
assert(dimension == 4 && "Invalid vector dimension."); |
| 923 |
break; |
| 924 |
} |
| 925 |
} |
| 926 |
std::vector<opt::Operand> operands; |
| 927 |
operands.emplace_back(selector_operand); |
| 928 |
|
| 929 |
uint32_t branch_instruction_true_block_id = |
| 930 |
branch_instruction.GetSingleWordInOperand(1); |
| 931 |
uint32_t branch_instruction_false_block_id = |
| 932 |
branch_instruction.GetSingleWordInOperand(2); |
| 933 |
|
| 934 |
// The OpPhi takes values from two distinct predecessors. One |
| 935 |
// predecessor is associated with the "true" path of the conditional |
| 936 |
// we are flattening, the other with the "false" path, but these |
| 937 |
// predecessors can appear in either order as operands to the OpPhi |
| 938 |
// instruction. We determine in which order the OpPhi inputs should |
| 939 |
// appear as OpSelect arguments by first checking whether the |
| 940 |
// convergence block is a direct successor of the selection header, and |
| 941 |
// otherwise checking dominance of the true and false immediate |
| 942 |
// successors of the header block. |
| 943 |
if (branch_instruction_true_block_id == convergence_block_id) { |
| 944 |
// The branch instruction's true block is the convergence block. This |
| 945 |
// means that the OpPhi's value associated with the branch |
| 946 |
// instruction's block should the "true" result of the OpSelect. |
| 947 |
assert(branch_instruction_false_block_id != convergence_block_id && |
| 948 |
"Control should not reach here if both branches target the " |
| 949 |
"convergence block."); |
| 950 |
if (phi_inst->GetSingleWordInOperand(1) == |
| 951 |
message_.header_block_id()) { |
| 952 |
operands.emplace_back(phi_inst->GetInOperand(0)); |
| 953 |
operands.emplace_back(phi_inst->GetInOperand(2)); |
| 954 |
} else { |
| 955 |
assert(phi_inst->GetSingleWordInOperand(3) == |
| 956 |
message_.header_block_id() && |
| 957 |
"Since the convergence block has the header block as one of " |
| 958 |
"two predecessors, if it is not handled by the first pair " |
| 959 |
"of operands of this OpPhi instruction it should be handled " |
| 960 |
"by the second pair."); |
| 961 |
operands.emplace_back(phi_inst->GetInOperand(2)); |
| 962 |
operands.emplace_back(phi_inst->GetInOperand(0)); |
| 963 |
} |
| 964 |
} else if (branch_instruction_false_block_id == convergence_block_id) { |
| 965 |
// The branch instruction's false block is the convergence block. This |
| 966 |
// means that the OpPhi's value associated with the branch |
| 967 |
// instruction's block should the "false" result of the OpSelect. |
| 968 |
if (phi_inst->GetSingleWordInOperand(1) == |
| 969 |
message_.header_block_id()) { |
| 970 |
operands.emplace_back(phi_inst->GetInOperand(2)); |
| 971 |
operands.emplace_back(phi_inst->GetInOperand(0)); |
| 972 |
} else { |
| 973 |
assert(phi_inst->GetSingleWordInOperand(3) == |
| 974 |
message_.header_block_id() && |
| 975 |
"Since the convergence block has the header block as one of " |
| 976 |
"two predecessors, if it is not handled by the first pair " |
| 977 |
"of operands of this OpPhi instruction it should be handled " |
| 978 |
"by the second pair."); |
| 979 |
operands.emplace_back(phi_inst->GetInOperand(0)); |
| 980 |
operands.emplace_back(phi_inst->GetInOperand(2)); |
| 981 |
} |
| 982 |
} else if (ir_context->GetDominatorAnalysis(header_block.GetParent()) |
| 983 |
->Dominates(branch_instruction_true_block_id, |
| 984 |
phi_inst->GetSingleWordInOperand(1))) { |
| 985 |
// The "true" branch of the conditional is handled first in the |
| 986 |
// OpPhi's operands; we thus provide operands to OpSelect in the same |
| 987 |
// order that they appear in the OpPhi. |
| 988 |
operands.emplace_back(phi_inst->GetInOperand(0)); |
| 989 |
operands.emplace_back(phi_inst->GetInOperand(2)); |
| 990 |
} else { |
| 991 |
// The "false" branch of the conditional is handled first in the |
| 992 |
// OpPhi's operands; we thus provide operands to OpSelect in reverse |
| 993 |
// of the order that they appear in the OpPhi. |
| 994 |
operands.emplace_back(phi_inst->GetInOperand(2)); |
| 995 |
operands.emplace_back(phi_inst->GetInOperand(0)); |
| 996 |
} |
| 997 |
phi_inst->SetOpcode(SpvOpSelect); |
| 998 |
phi_inst->SetInOperands(std::move(operands)); |
| 999 |
}); |
| 1000 |
|
| 1001 |
// Add boolean vector instructions to the start of the block as required. |
| 1002 |
if (require_2d_boolean_vector) { |
| 1003 |
AddBooleanVectorConstructorToBlock(message_.fresh_id_for_bvec2_selector(), |
| 1004 |
2, branch_condition_operand, ir_context, |
| 1005 |
convergence_block); |
| 1006 |
} |
| 1007 |
if (require_3d_boolean_vector) { |
| 1008 |
AddBooleanVectorConstructorToBlock(message_.fresh_id_for_bvec3_selector(), |
| 1009 |
3, branch_condition_operand, ir_context, |
| 1010 |
convergence_block); |
| 1011 |
} |
| 1012 |
if (require_4d_boolean_vector) { |
| 1013 |
AddBooleanVectorConstructorToBlock(message_.fresh_id_for_bvec4_selector(), |
| 1014 |
4, branch_condition_operand, ir_context, |
| 1015 |
convergence_block); |
| 1016 |
} |
| 1017 |
} |
| 1018 |
|
| 1019 |
} // namespace fuzz |
| 1020 |
} // namespace spvtools |