Debian Codegraph @

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