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_merge_function_returns.h"
16
17 #include "source/fuzz/comparator_deep_blocks_first.h"
18 #include "source/fuzz/fuzzer_util.h"
19
20 namespace spvtools {
21 namespace fuzz {
22
TransformationMergeFunctionReturns(const protobufs::TransformationMergeFunctionReturns & message)23 TransformationMergeFunctionReturns::TransformationMergeFunctionReturns(
24 const protobufs::TransformationMergeFunctionReturns& message)
25 : message_(message) {}
26
TransformationMergeFunctionReturns(uint32_t function_id,uint32_t outer_header_id,uint32_t outer_return_id,uint32_t return_val_id,uint32_t any_returnable_val_id,const std::vector<protobufs::ReturnMergingInfo> & returns_merging_info)27 TransformationMergeFunctionReturns::TransformationMergeFunctionReturns(
28 uint32_t function_id, uint32_t outer_header_id, uint32_t outer_return_id,
29 uint32_t return_val_id, uint32_t any_returnable_val_id,
30 const std::vector<protobufs::ReturnMergingInfo>& returns_merging_info) {
31 message_.set_function_id(function_id);
32 message_.set_outer_header_id(outer_header_id);
33 message_.set_outer_return_id(outer_return_id);
34 message_.set_return_val_id(return_val_id);
35 message_.set_any_returnable_val_id(any_returnable_val_id);
36 for (const auto& return_merging_info : returns_merging_info) {
37 *message_.add_return_merging_info() = return_merging_info;
38 }
39 }
40
IsApplicable(opt::IRContext * ir_context,const TransformationContext & transformation_context) const41 bool TransformationMergeFunctionReturns::IsApplicable(
42 opt::IRContext* ir_context,
43 const TransformationContext& transformation_context) const {
44 auto function = ir_context->GetFunction(message_.function_id());
45 // The function must exist.
46 if (!function) {
47 return false;
48 }
49
50 // The entry block must end in an unconditional branch.
51 if (function->entry()->terminator()->opcode() != SpvOpBranch) {
52 return false;
53 }
54
55 // The module must contain an OpConstantTrue instruction.
56 if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
57 true, false)) {
58 return false;
59 }
60
61 // The module must contain an OpConstantFalse instruction.
62 if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
63 false, false)) {
64 return false;
65 }
66
67 // Check that the fresh ids provided are fresh and distinct.
68 std::set<uint32_t> used_fresh_ids;
69 for (uint32_t id : {message_.outer_header_id(), message_.outer_return_id()}) {
70 if (!id || !CheckIdIsFreshAndNotUsedByThisTransformation(id, ir_context,
71 &used_fresh_ids)) {
72 return false;
73 }
74 }
75
76 // Check the additional fresh id required if the function is not void.
77 auto function_type = ir_context->get_type_mgr()->GetType(function->type_id());
78 assert(function_type && "The function type should always exist.");
79
80 if (!function_type->AsVoid() &&
81 (!message_.return_val_id() ||
82 !CheckIdIsFreshAndNotUsedByThisTransformation(
83 message_.return_val_id(), ir_context, &used_fresh_ids))) {
84 return false;
85 }
86
87 // Get a map from the types for which ids are available at the end of the
88 // entry block to one of the ids with that type. We compute this here to avoid
89 // potentially doing it multiple times later on.
90 auto types_to_available_ids =
91 GetTypesToIdAvailableAfterEntryBlock(ir_context);
92
93 // Get the reachable return blocks.
94 auto return_blocks =
95 fuzzerutil::GetReachableReturnBlocks(ir_context, message_.function_id());
96
97 // Map each merge block of loops containing reachable return blocks to the
98 // corresponding returning predecessors (all the blocks that, at the end of
99 // the transformation, will branch to the merge block because the function is
100 // returning).
101 std::map<uint32_t, std::set<uint32_t>> merge_blocks_to_returning_preds;
102 for (uint32_t block : return_blocks) {
103 uint32_t merge_block =
104 ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(block);
105
106 while (merge_block != 0) {
107 // If we have seen this merge block before, update the corresponding set
108 // and break out of the loop.
109 if (merge_blocks_to_returning_preds.count(merge_block)) {
110 merge_blocks_to_returning_preds[merge_block].emplace(block);
111 break;
112 }
113
114 // If we have not seen this merge block before, add a new entry and walk
115 // up the loop tree.
116 merge_blocks_to_returning_preds.emplace(merge_block,
117 std::set<uint32_t>({block}));
118
119 // Walk up the loop tree.
120 block = merge_block;
121 merge_block =
122 ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(merge_block);
123 }
124 }
125
126 // Instructions in the relevant merge blocks must be restricted to OpLabel,
127 // OpPhi and OpBranch.
128 for (const auto& merge_block_entry : merge_blocks_to_returning_preds) {
129 uint32_t merge_block = merge_block_entry.first;
130 bool all_instructions_allowed =
131 ir_context->get_instr_block(merge_block)
132 ->WhileEachInst([](opt::Instruction* inst) {
133 return inst->opcode() == SpvOpLabel ||
134 inst->opcode() == SpvOpPhi ||
135 inst->opcode() == SpvOpBranch;
136 });
137 if (!all_instructions_allowed) {
138 return false;
139 }
140 }
141
142 auto merge_blocks_to_info = GetMappingOfMergeBlocksToInfo();
143
144 // For each relevant merge block, check that the correct ids are available.
145 for (const auto& merge_block_entry : merge_blocks_to_returning_preds) {
146 if (!CheckThatTheCorrectIdsAreGivenForMergeBlock(
147 merge_block_entry.first, merge_blocks_to_info,
148 types_to_available_ids, function_type->AsVoid(), ir_context,
149 transformation_context, &used_fresh_ids)) {
150 return false;
151 }
152 }
153
154 // If the function has a non-void return type, and there are merge loops which
155 // contain return instructions, we need to check that either:
156 // - |message_.any_returnable_val_id| exists. In this case, it must have the
157 // same type as the return type of the function and be available at the end
158 // of the entry block.
159 // - a suitable id, available at the end of the entry block can be found in
160 // the module.
161 if (!function_type->AsVoid() && !merge_blocks_to_returning_preds.empty()) {
162 auto returnable_val_def =
163 ir_context->get_def_use_mgr()->GetDef(message_.any_returnable_val_id());
164 if (!returnable_val_def) {
165 // Check if a suitable id can be found in the module.
166 if (types_to_available_ids.count(function->type_id()) == 0) {
167 return false;
168 }
169 } else if (returnable_val_def->type_id() != function->type_id()) {
170 return false;
171 } else if (!fuzzerutil::IdIsAvailableBeforeInstruction(
172 ir_context, function->entry()->terminator(),
173 message_.any_returnable_val_id())) {
174 // The id must be available at the end of the entry block.
175 return false;
176 }
177 }
178
179 // Check that adding new predecessors to the relevant merge blocks does not
180 // render any instructions invalid (each id definition must still dominate
181 // each of its uses).
182 if (!CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(
183 ir_context, function, merge_blocks_to_returning_preds)) {
184 return false;
185 }
186
187 return true;
188 }
189
Apply(opt::IRContext * ir_context,TransformationContext * transformation_context) const190 void TransformationMergeFunctionReturns::Apply(
191 opt::IRContext* ir_context,
192 TransformationContext* transformation_context) const {
193 auto function = ir_context->GetFunction(message_.function_id());
194 auto function_type = ir_context->get_type_mgr()->GetType(function->type_id());
195
196 // Get a map from the types for which ids are available at the end of the
197 // entry block to one of the ids with that type. We compute this here to avoid
198 // potentially doing it multiple times later on.
199 auto types_to_available_ids =
200 GetTypesToIdAvailableAfterEntryBlock(ir_context);
201
202 uint32_t bool_type = fuzzerutil::MaybeGetBoolType(ir_context);
203
204 uint32_t constant_true = fuzzerutil::MaybeGetBoolConstant(
205 ir_context, *transformation_context, true, false);
206
207 uint32_t constant_false = fuzzerutil::MaybeGetBoolConstant(
208 ir_context, *transformation_context, false, false);
209
210 // Get the reachable return blocks.
211 auto return_blocks =
212 fuzzerutil::GetReachableReturnBlocks(ir_context, message_.function_id());
213
214 // Keep a map from the relevant merge blocks to a mapping from each of the
215 // returning predecessors to the corresponding pair (return value,
216 // boolean specifying whether the function is returning). Returning
217 // predecessors are blocks in the loop (not further nested inside loops),
218 // which either return or are merge blocks of nested loops containing return
219 // instructions.
220 std::map<uint32_t, std::map<uint32_t, std::pair<uint32_t, uint32_t>>>
221 merge_blocks_to_returning_predecessors;
222
223 // Initialise the map, mapping each relevant merge block to an empty map.
224 for (uint32_t ret_block_id : return_blocks) {
225 uint32_t merge_block_id =
226 ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(ret_block_id);
227
228 while (merge_block_id != 0 &&
229 !merge_blocks_to_returning_predecessors.count(merge_block_id)) {
230 merge_blocks_to_returning_predecessors.emplace(
231 merge_block_id, std::map<uint32_t, std::pair<uint32_t, uint32_t>>());
232 merge_block_id = ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(
233 merge_block_id);
234 }
235 }
236
237 // Get a reference to an instruction with the same type id as the function's
238 // return type, if the type of the function is not void and ther are loops
239 // containing return instructions.
240 uint32_t returnable_val_id = 0;
241 if (!function_type->AsVoid() &&
242 !merge_blocks_to_returning_predecessors.empty()) {
243 // If |message.any_returnable_val_id| can be found in the module, use it.
244 // Otherwise, use another suitable id found in the module.
245 auto returnable_val_def =
246 ir_context->get_def_use_mgr()->GetDef(message_.any_returnable_val_id());
247 returnable_val_id = returnable_val_def
248 ? returnable_val_def->result_id()
249 : types_to_available_ids[function->type_id()];
250 }
251
252 // Keep a map from all the new predecessors of the merge block of the new
253 // outer loop, to the related return value ids.
254 std::map<uint32_t, uint32_t> outer_merge_predecessors;
255
256 // Adjust the return blocks and add the related information to the map or
257 // |outer_merge_predecessors| set.
258 for (uint32_t ret_block_id : return_blocks) {
259 auto ret_block = ir_context->get_instr_block(ret_block_id);
260
261 // Get the return value id (if the function is not void).
262 uint32_t ret_val_id =
263 function_type->AsVoid()
264 ? 0
265 : ret_block->terminator()->GetSingleWordInOperand(0);
266
267 uint32_t merge_block_id =
268 ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(ret_block_id);
269
270 // Add a new entry to the map corresponding to the merge block of the
271 // innermost enclosing loop (or that of the new outer loop if there is no
272 // enclosing loop).
273 if (merge_block_id != 0) {
274 merge_blocks_to_returning_predecessors[merge_block_id].emplace(
275 ret_block_id,
276 std::pair<uint32_t, uint32_t>(ret_val_id, constant_true));
277 } else {
278 // If there is no enclosing loop, the block will branch to the merge block
279 // of the new outer loop.
280 merge_block_id = message_.outer_return_id();
281 outer_merge_predecessors.emplace(ret_block_id, ret_val_id);
282 }
283
284 // Replace the return instruction with an unconditional branch.
285 ret_block->terminator()->SetOpcode(SpvOpBranch);
286 ret_block->terminator()->SetInOperands(
287 {{SPV_OPERAND_TYPE_ID, {merge_block_id}}});
288 }
289
290 // Get a list of all the relevant merge blocks.
291 std::vector<uint32_t> merge_blocks;
292 merge_blocks.reserve(merge_blocks_to_returning_predecessors.size());
293 for (const auto& entry : merge_blocks_to_returning_predecessors) {
294 merge_blocks.emplace_back(entry.first);
295 }
296
297 // Sort the list so that deeper merge blocks come first.
298 // We need to consider deeper merge blocks first so that, when a merge block
299 // is considered, all the merge blocks enclosed by the corresponding loop have
300 // already been considered and, thus, the mapping from this merge block to the
301 // returning predecessors is complete.
302 std::sort(merge_blocks.begin(), merge_blocks.end(),
303 ComparatorDeepBlocksFirst(ir_context));
304
305 auto merge_blocks_to_info = GetMappingOfMergeBlocksToInfo();
306
307 // Adjust the merge blocks and add the related information to the map or
308 // |outer_merge_predecessors| set.
309 for (uint32_t merge_block_id : merge_blocks) {
310 // Get the info corresponding to |merge_block| from the map, if a
311 // corresponding entry exists. Otherwise use overflow ids and find suitable
312 // ids in the module.
313 protobufs::ReturnMergingInfo* info =
314 merge_blocks_to_info.count(merge_block_id)
315 ? &merge_blocks_to_info[merge_block_id]
316 : nullptr;
317
318 uint32_t is_returning_id =
319 info ? info->is_returning_id()
320 : transformation_context->GetOverflowIdSource()
321 ->GetNextOverflowId();
322
323 uint32_t maybe_return_val_id = 0;
324 if (!function_type->AsVoid()) {
325 maybe_return_val_id = info ? info->maybe_return_val_id()
326 : transformation_context->GetOverflowIdSource()
327 ->GetNextOverflowId();
328 }
329
330 // Map from existing OpPhi to overflow ids. If there is no mapping, get an
331 // empty map.
332 auto phi_to_id = info ? fuzzerutil::RepeatedUInt32PairToMap(
333 *merge_blocks_to_info[merge_block_id]
334 .mutable_opphi_to_suitable_id())
335 : std::map<uint32_t, uint32_t>();
336
337 // Get a reference to the info related to the returning predecessors.
338 const auto& returning_preds =
339 merge_blocks_to_returning_predecessors[merge_block_id];
340
341 // Get a set of the original predecessors.
342 auto preds_list = ir_context->cfg()->preds(merge_block_id);
343 auto preds = std::set<uint32_t>(preds_list.begin(), preds_list.end());
344
345 auto merge_block = ir_context->get_instr_block(merge_block_id);
346
347 // Adjust the existing OpPhi instructions.
348 merge_block->ForEachPhiInst(
349 [&preds, &returning_preds, &phi_to_id,
350 &types_to_available_ids](opt::Instruction* inst) {
351 // We need a placeholder value id. If |phi_to_id| contains a mapping
352 // for this instruction, we use the given id, otherwise a suitable id
353 // for the instruction's type from |types_to_available_ids|.
354 uint32_t placeholder_val_id =
355 phi_to_id.count(inst->result_id())
356 ? phi_to_id[inst->result_id()]
357 : types_to_available_ids[inst->type_id()];
358 assert(placeholder_val_id &&
359 "We should always be able to find a suitable if the "
360 "transformation is applicable.");
361
362 // Add a pair of operands (placeholder id, new predecessor) for each
363 // new predecessor of the merge block.
364 for (const auto& entry : returning_preds) {
365 // A returning predecessor may already be a predecessor of the
366 // block. In that case, we should not add new operands.
367 // Each entry is in the form (predecessor, {return val, is
368 // returning}).
369 if (!preds.count(entry.first)) {
370 inst->AddOperand({SPV_OPERAND_TYPE_ID, {placeholder_val_id}});
371 inst->AddOperand({SPV_OPERAND_TYPE_ID, {entry.first}});
372 }
373 }
374 });
375
376 // If the function is not void, add a new OpPhi instructions to collect the
377 // return value from the returning predecessors.
378 if (!function_type->AsVoid()) {
379 opt::Instruction::OperandList operand_list;
380
381 // Add two operands (return value, predecessor) for each returning
382 // predecessor.
383 for (auto entry : returning_preds) {
384 // Each entry is in the form (predecessor, {return value,
385 // is returning}).
386 operand_list.emplace_back(
387 opt::Operand{SPV_OPERAND_TYPE_ID, {entry.second.first}});
388 operand_list.emplace_back(
389 opt::Operand{SPV_OPERAND_TYPE_ID, {entry.first}});
390 }
391
392 // Add two operands for each original predecessor from which the function
393 // does not return.
394 for (uint32_t original_pred : preds) {
395 // Only add operands if the function cannot be returning from this
396 // block.
397 if (returning_preds.count(original_pred)) {
398 continue;
399 }
400
401 operand_list.emplace_back(
402 opt::Operand{SPV_OPERAND_TYPE_ID, {returnable_val_id}});
403 operand_list.emplace_back(
404 opt::Operand{SPV_OPERAND_TYPE_ID, {original_pred}});
405 }
406
407 // Insert the instruction.
408 merge_block->begin()->InsertBefore(MakeUnique<opt::Instruction>(
409 ir_context, SpvOpPhi, function->type_id(), maybe_return_val_id,
410 std::move(operand_list)));
411
412 fuzzerutil::UpdateModuleIdBound(ir_context, maybe_return_val_id);
413 }
414
415 // Add an OpPhi instruction deciding whether the function is returning.
416 {
417 opt::Instruction::OperandList operand_list;
418
419 // Add two operands (return value, is returning) for each returning
420 // predecessor.
421 for (auto entry : returning_preds) {
422 // Each entry is in the form (predecessor, {return value,
423 // is returning}).
424 operand_list.emplace_back(
425 opt::Operand{SPV_OPERAND_TYPE_ID, {entry.second.second}});
426 operand_list.emplace_back(
427 opt::Operand{SPV_OPERAND_TYPE_ID, {entry.first}});
428 }
429
430 // Add two operands for each original predecessor from which the function
431 // does not return.
432 for (uint32_t original_pred : preds) {
433 // Only add operands if the function cannot be returning from this
434 // block.
435 if (returning_preds.count(original_pred)) {
436 continue;
437 }
438
439 operand_list.emplace_back(
440 opt::Operand{SPV_OPERAND_TYPE_ID, {constant_false}});
441 operand_list.emplace_back(
442 opt::Operand{SPV_OPERAND_TYPE_ID, {original_pred}});
443 }
444
445 // Insert the instruction.
446 merge_block->begin()->InsertBefore(MakeUnique<opt::Instruction>(
447 ir_context, SpvOpPhi, bool_type, is_returning_id,
448 std::move(operand_list)));
449
450 fuzzerutil::UpdateModuleIdBound(ir_context, is_returning_id);
451 }
452
453 // Change the branching instruction of the block.
454 assert(merge_block->terminator()->opcode() == SpvOpBranch &&
455 "Each block should branch unconditionally to the next.");
456
457 // Add a new entry to the map corresponding to the merge block of the
458 // innermost enclosing loop (or that of the new outer loop if there is no
459 // enclosing loop).
460 uint32_t enclosing_merge =
461 ir_context->GetStructuredCFGAnalysis()->LoopMergeBlock(merge_block_id);
462 if (enclosing_merge == 0) {
463 enclosing_merge = message_.outer_return_id();
464 outer_merge_predecessors.emplace(merge_block_id, maybe_return_val_id);
465 } else {
466 merge_blocks_to_returning_predecessors[enclosing_merge].emplace(
467 merge_block_id,
468 std::pair<uint32_t, uint32_t>(maybe_return_val_id, is_returning_id));
469 }
470
471 // Get the current successor.
472 uint32_t original_succ =
473 merge_block->terminator()->GetSingleWordInOperand(0);
474 // Leave the instruction as it is if the block already branches to the merge
475 // block of the enclosing loop.
476 if (original_succ == enclosing_merge) {
477 continue;
478 }
479
480 // The block should branch to |enclosing_merge| if |is_returning_id| is
481 // true, to |original_succ| otherwise.
482 merge_block->terminator()->SetOpcode(SpvOpBranchConditional);
483 merge_block->terminator()->SetInOperands(
484 {{SPV_OPERAND_TYPE_ID, {is_returning_id}},
485 {SPV_OPERAND_TYPE_ID, {enclosing_merge}},
486 {SPV_OPERAND_TYPE_ID, {original_succ}}});
487 }
488
489 assert(function->entry()->terminator()->opcode() == SpvOpBranch &&
490 "The entry block should branch unconditionally to another block.");
491 uint32_t block_after_entry =
492 function->entry()->terminator()->GetSingleWordInOperand(0);
493
494 // Create the header for the new outer loop.
495 auto outer_loop_header =
496 MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
497 ir_context, SpvOpLabel, 0, message_.outer_header_id(),
498 opt::Instruction::OperandList()));
499
500 fuzzerutil::UpdateModuleIdBound(ir_context, message_.outer_header_id());
501
502 // Add the instruction: OpLoopMerge %outer_return_id %outer_header_id None
503 // The header is the continue block of the outer loop.
504 outer_loop_header->AddInstruction(MakeUnique<opt::Instruction>(
505 ir_context, SpvOpLoopMerge, 0, 0,
506 opt::Instruction::OperandList{
507 {SPV_OPERAND_TYPE_ID, {message_.outer_return_id()}},
508 {SPV_OPERAND_TYPE_ID, {message_.outer_header_id()}},
509 {SPV_OPERAND_TYPE_LOOP_CONTROL, {SpvLoopControlMaskNone}}}));
510
511 // Add conditional branch:
512 // OpBranchConditional %true %block_after_entry %outer_header_id
513 // This will always branch to %block_after_entry, but it also creates a back
514 // edge for the loop (which is never traversed).
515 outer_loop_header->AddInstruction(MakeUnique<opt::Instruction>(
516 ir_context, SpvOpBranchConditional, 0, 0,
517 opt::Instruction::OperandList{
518 {SPV_OPERAND_TYPE_ID, {constant_true}},
519 {SPV_OPERAND_TYPE_ID, {block_after_entry}},
520 {SPV_OPERAND_TYPE_ID, {message_.outer_header_id()}}}));
521
522 // Insert the header right after the entry block.
523 function->InsertBasicBlockAfter(std::move(outer_loop_header),
524 function->entry().get());
525
526 // Update the branching instruction of the entry block.
527 function->entry()->terminator()->SetInOperands(
528 {{SPV_OPERAND_TYPE_ID, {message_.outer_header_id()}}});
529
530 // If the entry block is referenced in an OpPhi instruction, the header for
531 // the new loop should be referenced instead.
532 ir_context->get_def_use_mgr()->ForEachUse(
533 function->entry()->id(),
534 [this](opt::Instruction* use_instruction, uint32_t use_operand_index) {
535 if (use_instruction->opcode() == SpvOpPhi) {
536 use_instruction->SetOperand(use_operand_index,
537 {message_.outer_header_id()});
538 }
539 });
540
541 // Create the merge block for the loop (and return block for the function).
542 auto outer_return_block =
543 MakeUnique<opt::BasicBlock>(MakeUnique<opt::Instruction>(
544 ir_context, SpvOpLabel, 0, message_.outer_return_id(),
545 opt::Instruction::OperandList()));
546
547 fuzzerutil::UpdateModuleIdBound(ir_context, message_.outer_return_id());
548
549 // If the function is not void, insert an instruction to collect the return
550 // value from the predecessors and an OpReturnValue instruction.
551 if (!function_type->AsVoid()) {
552 opt::Instruction::OperandList operand_list;
553
554 // Add two operands (return value, predecessor) for each predecessor.
555 for (auto entry : outer_merge_predecessors) {
556 // Each entry is in the form (predecessor, return value).
557 operand_list.emplace_back(
558 opt::Operand{SPV_OPERAND_TYPE_ID, {entry.second}});
559 operand_list.emplace_back(
560 opt::Operand{SPV_OPERAND_TYPE_ID, {entry.first}});
561 }
562
563 // Insert the OpPhi instruction.
564 outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
565 ir_context, SpvOpPhi, function->type_id(), message_.return_val_id(),
566 std::move(operand_list)));
567
568 fuzzerutil::UpdateModuleIdBound(ir_context, message_.return_val_id());
569
570 // Insert the OpReturnValue instruction.
571 outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
572 ir_context, SpvOpReturnValue, 0, 0,
573 opt::Instruction::OperandList{
574 {SPV_OPERAND_TYPE_ID, {message_.return_val_id()}}}));
575 } else {
576 // Insert an OpReturn instruction (the function is void).
577 outer_return_block->AddInstruction(MakeUnique<opt::Instruction>(
578 ir_context, SpvOpReturn, 0, 0, opt::Instruction::OperandList{}));
579 }
580
581 // Insert the new return block at the end of the function.
582 outer_return_block->SetParent(function);
583 function->AddBasicBlock(std::move(outer_return_block));
584
585 // All analyses must be invalidated because the structure of the module was
586 // changed.
587 ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
588 }
589
GetFreshIds() const590 std::unordered_set<uint32_t> TransformationMergeFunctionReturns::GetFreshIds()
591 const {
592 std::unordered_set<uint32_t> result;
593 result.emplace(message_.outer_header_id());
594 result.emplace(message_.outer_return_id());
595 // |message_.return_val_info| can be 0 if the function is void.
596 if (message_.return_val_id()) {
597 result.emplace(message_.return_val_id());
598 }
599
600 for (auto merging_info : message_.return_merging_info()) {
601 result.emplace(merging_info.is_returning_id());
602 // |maybe_return_val_id| can be 0 if the function is void.
603 if (merging_info.maybe_return_val_id()) {
604 result.emplace(merging_info.maybe_return_val_id());
605 }
606 }
607
608 return result;
609 }
610
ToMessage() const611 protobufs::Transformation TransformationMergeFunctionReturns::ToMessage()
612 const {
613 protobufs::Transformation result;
614 *result.mutable_merge_function_returns() = message_;
615 return result;
616 }
617
618 std::map<uint32_t, protobufs::ReturnMergingInfo>
GetMappingOfMergeBlocksToInfo() const619 TransformationMergeFunctionReturns::GetMappingOfMergeBlocksToInfo() const {
620 std::map<uint32_t, protobufs::ReturnMergingInfo> result;
621 for (const auto& info : message_.return_merging_info()) {
622 result.emplace(info.merge_block_id(), info);
623 }
624 return result;
625 }
626
627 std::map<uint32_t, uint32_t>
GetTypesToIdAvailableAfterEntryBlock(opt::IRContext * ir_context) const628 TransformationMergeFunctionReturns::GetTypesToIdAvailableAfterEntryBlock(
629 opt::IRContext* ir_context) const {
630 std::map<uint32_t, uint32_t> result;
631 // Consider all global declarations
632 for (auto& global : ir_context->module()->types_values()) {
633 if (global.HasResultId() && global.type_id()) {
634 result.emplace(global.type_id(), global.result_id());
635 }
636 }
637
638 auto function = ir_context->GetFunction(message_.function_id());
639 assert(function && "The function must exist.");
640
641 // Consider all function parameters
642 function->ForEachParam([&result](opt::Instruction* param) {
643 if (param->HasResultId() && param->type_id()) {
644 result.emplace(param->type_id(), param->result_id());
645 }
646 });
647
648 // Consider all the instructions in the entry block.
649 for (auto& inst : *function->entry()) {
650 if (inst.HasResultId() && inst.type_id()) {
651 result.emplace(inst.type_id(), inst.result_id());
652 }
653 }
654
655 return result;
656 }
657
658 bool TransformationMergeFunctionReturns::
CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(opt::IRContext * ir_context,const opt::Function * function,const std::map<uint32_t,std::set<uint32_t>> & merge_blocks_to_new_predecessors)659 CheckDefinitionsStillDominateUsesAfterAddingNewPredecessors(
660 opt::IRContext* ir_context, const opt::Function* function,
661 const std::map<uint32_t, std::set<uint32_t>>&
662 merge_blocks_to_new_predecessors) {
663 for (const auto& merge_block_entry : merge_blocks_to_new_predecessors) {
664 uint32_t merge_block = merge_block_entry.first;
665 const auto& returning_preds = merge_block_entry.second;
666
667 // Find a list of blocks in which there might be problematic definitions.
668 // These are all the blocks that dominate the merge block but do not
669 // dominate all of the new predecessors.
670 std::vector<opt::BasicBlock*> problematic_blocks;
671
672 auto dominator_analysis = ir_context->GetDominatorAnalysis(function);
673
674 // Start from the immediate dominator of the merge block.
675 auto current_block = dominator_analysis->ImmediateDominator(merge_block);
676 assert(current_block &&
677 "Each merge block should have at least one dominator.");
678
679 for (uint32_t pred : returning_preds) {
680 while (!dominator_analysis->Dominates(current_block->id(), pred)) {
681 // The current block does not dominate all of the new predecessor
682 // blocks, so it might be problematic.
683 problematic_blocks.emplace_back(current_block);
684
685 // Walk up the dominator tree.
686 current_block = dominator_analysis->ImmediateDominator(current_block);
687 assert(current_block &&
688 "We should be able to find a dominator for all the blocks, "
689 "since they must all be dominated at least by the header.");
690 }
691 }
692
693 // Identify the loop header corresponding to the merge block.
694 uint32_t loop_header =
695 fuzzerutil::GetLoopFromMergeBlock(ir_context, merge_block);
696
697 // For all the ids defined in blocks inside |problematic_blocks|, check that
698 // all their uses are either:
699 // - inside the loop (or in the loop header). If this is the case, the path
700 // from the definition to the use does not go through the merge block, so
701 // adding new predecessor to it is not a problem.
702 // - inside an OpPhi instruction in the merge block. If this is the case,
703 // the definition does not need to dominate the merge block.
704 for (auto block : problematic_blocks) {
705 assert((block->id() == loop_header ||
706 ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
707 block->id()) == loop_header) &&
708 "The problematic blocks should all be inside the loop (also "
709 "considering the header).");
710 bool dominance_rules_maintained =
711 block->WhileEachInst([ir_context, loop_header,
712 merge_block](opt::Instruction* instruction) {
713 // Instruction without a result id do not cause any problems.
714 if (!instruction->HasResultId()) {
715 return true;
716 }
717
718 // Check that all the uses of the id are inside the loop.
719 return ir_context->get_def_use_mgr()->WhileEachUse(
720 instruction->result_id(),
721 [ir_context, loop_header, merge_block](
722 opt::Instruction* inst_use, uint32_t /* unused */) {
723 uint32_t block_use =
724 ir_context->get_instr_block(inst_use)->id();
725
726 // The usage is OK if it is inside the loop (including the
727 // header).
728 if (block_use == loop_header ||
729 ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
730 block_use)) {
731 return true;
732 }
733
734 // The usage is OK if it is inside an OpPhi instruction in the
735 // merge block.
736 return block_use == merge_block &&
737 inst_use->opcode() == SpvOpPhi;
738 });
739 });
740
741 // If not all instructions in the block satisfy the requirement, the
742 // transformation is not applicable.
743 if (!dominance_rules_maintained) {
744 return false;
745 }
746 }
747 }
748
749 return true;
750 }
751
752 bool TransformationMergeFunctionReturns::
CheckThatTheCorrectIdsAreGivenForMergeBlock(uint32_t merge_block,const std::map<uint32_t,protobufs::ReturnMergingInfo> & merge_blocks_to_info,const std::map<uint32_t,uint32_t> & types_to_available_id,bool function_is_void,opt::IRContext * ir_context,const TransformationContext & transformation_context,std::set<uint32_t> * used_fresh_ids)753 CheckThatTheCorrectIdsAreGivenForMergeBlock(
754 uint32_t merge_block,
755 const std::map<uint32_t, protobufs::ReturnMergingInfo>&
756 merge_blocks_to_info,
757 const std::map<uint32_t, uint32_t>& types_to_available_id,
758 bool function_is_void, opt::IRContext* ir_context,
759 const TransformationContext& transformation_context,
760 std::set<uint32_t>* used_fresh_ids) {
761 // A map from OpPhi ids to ids of the same type available at the beginning
762 // of the merge block.
763 std::map<uint32_t, uint32_t> phi_to_id;
764
765 if (merge_blocks_to_info.count(merge_block) > 0) {
766 // If the map contains an entry for the merge block, check that the fresh
767 // ids are fresh and distinct.
768 auto info = merge_blocks_to_info.at(merge_block);
769 if (!info.is_returning_id() ||
770 !CheckIdIsFreshAndNotUsedByThisTransformation(
771 info.is_returning_id(), ir_context, used_fresh_ids)) {
772 return false;
773 }
774
775 if (!function_is_void &&
776 (!info.maybe_return_val_id() ||
777 !CheckIdIsFreshAndNotUsedByThisTransformation(
778 info.maybe_return_val_id(), ir_context, used_fresh_ids))) {
779 return false;
780 }
781
782 // Get the mapping from OpPhis to suitable ids.
783 phi_to_id = fuzzerutil::RepeatedUInt32PairToMap(
784 *info.mutable_opphi_to_suitable_id());
785 } else {
786 // If the map does not contain an entry for the merge block, check that
787 // overflow ids are available.
788 if (!transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
789 return false;
790 }
791 }
792
793 // For each OpPhi instruction, check that a suitable placeholder id is
794 // available.
795 bool suitable_info_for_phi =
796 ir_context->get_instr_block(merge_block)
797 ->WhileEachPhiInst([ir_context, &phi_to_id,
798 &types_to_available_id](opt::Instruction* inst) {
799 if (phi_to_id.count(inst->result_id()) > 0) {
800 // If there exists a mapping for this instruction and the
801 // placeholder id exists in the module, check that it has the
802 // correct type and it is available before the instruction.
803 auto placeholder_def = ir_context->get_def_use_mgr()->GetDef(
804 phi_to_id[inst->result_id()]);
805 if (placeholder_def) {
806 if (inst->type_id() != placeholder_def->type_id()) {
807 return false;
808 }
809 if (!fuzzerutil::IdIsAvailableBeforeInstruction(
810 ir_context, inst, placeholder_def->result_id())) {
811 return false;
812 }
813
814 return true;
815 }
816 }
817
818 // If there is no mapping, check if there is a suitable id
819 // available at the end of the entry block.
820 return types_to_available_id.count(inst->type_id()) > 0;
821 });
822
823 if (!suitable_info_for_phi) {
824 return false;
825 }
826
827 return true;
828 }
829
830 } // namespace fuzz
831 } // namespace spvtools
832