Debian Codegraph @

third_party/spirv-tools/source/fuzz/transformation_flatten_conditional_branch.cpp

raw
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