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/fuzzer_pass_duplicate_regions_with_selections.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/transformation_duplicate_region_with_selection.h"
19
20 namespace spvtools {
21 namespace fuzz {
22
23 FuzzerPassDuplicateRegionsWithSelections::
FuzzerPassDuplicateRegionsWithSelections(opt::IRContext * ir_context,TransformationContext * transformation_context,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformations,bool ignore_inapplicable_transformations)24 FuzzerPassDuplicateRegionsWithSelections(
25 opt::IRContext* ir_context,
26 TransformationContext* transformation_context,
27 FuzzerContext* fuzzer_context,
28 protobufs::TransformationSequence* transformations,
29 bool ignore_inapplicable_transformations)
30 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
31 transformations, ignore_inapplicable_transformations) {}
32
Apply()33 void FuzzerPassDuplicateRegionsWithSelections::Apply() {
34 // Iterate over all of the functions in the module.
35 for (auto& function : *GetIRContext()->module()) {
36 // Randomly decide whether to apply the transformation.
37 if (!GetFuzzerContext()->ChoosePercentage(
38 GetFuzzerContext()->GetChanceOfDuplicatingRegionWithSelection())) {
39 continue;
40 }
41 std::vector<opt::BasicBlock*> candidate_entry_blocks;
42 for (auto& block : function) {
43 // We don't consider the first block to be the entry block, since it
44 // could contain OpVariable instructions that would require additional
45 // operations to be reassigned.
46 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3778):
47 // Consider extending this fuzzer pass to allow the first block to be
48 // used in duplication.
49 if (&block == &*function.begin()) {
50 continue;
51 }
52 candidate_entry_blocks.push_back(&block);
53 }
54 if (candidate_entry_blocks.empty()) {
55 continue;
56 }
57 // Randomly choose the entry block.
58 auto entry_block = candidate_entry_blocks[GetFuzzerContext()->RandomIndex(
59 candidate_entry_blocks)];
60 auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(&function);
61 auto postdominator_analysis =
62 GetIRContext()->GetPostDominatorAnalysis(&function);
63 std::vector<opt::BasicBlock*> candidate_exit_blocks;
64 for (auto postdominates_entry_block = entry_block;
65 postdominates_entry_block != nullptr;
66 postdominates_entry_block = postdominator_analysis->ImmediateDominator(
67 postdominates_entry_block)) {
68 // The candidate exit block must be dominated by the entry block and the
69 // entry block must be post-dominated by the candidate exit block. Ignore
70 // the block if it heads a selection construct or a loop construct.
71 if (dominator_analysis->Dominates(entry_block,
72 postdominates_entry_block) &&
73 !postdominates_entry_block->GetMergeInst()) {
74 candidate_exit_blocks.push_back(postdominates_entry_block);
75 }
76 }
77 if (candidate_exit_blocks.empty()) {
78 continue;
79 }
80 // Randomly choose the exit block.
81 auto exit_block = candidate_exit_blocks[GetFuzzerContext()->RandomIndex(
82 candidate_exit_blocks)];
83
84 auto region_blocks =
85 TransformationDuplicateRegionWithSelection::GetRegionBlocks(
86 GetIRContext(), entry_block, exit_block);
87
88 // Construct |original_label_to_duplicate_label| by iterating over all
89 // blocks in the region. Construct |original_id_to_duplicate_id| and
90 // |original_id_to_phi_id| by iterating over all instructions in each block.
91 std::map<uint32_t, uint32_t> original_label_to_duplicate_label;
92 std::map<uint32_t, uint32_t> original_id_to_duplicate_id;
93 std::map<uint32_t, uint32_t> original_id_to_phi_id;
94 for (auto& block : region_blocks) {
95 original_label_to_duplicate_label[block->id()] =
96 GetFuzzerContext()->GetFreshId();
97 for (auto& instr : *block) {
98 if (instr.result_id()) {
99 original_id_to_duplicate_id[instr.result_id()] =
100 GetFuzzerContext()->GetFreshId();
101 auto final_instruction = &*exit_block->tail();
102 // &*exit_block->tail() is the final instruction of the region.
103 // The instruction is available at the end of the region if and only
104 // if it is available before this final instruction or it is the final
105 // instruction.
106 if ((&instr == final_instruction ||
107 fuzzerutil::IdIsAvailableBeforeInstruction(
108 GetIRContext(), final_instruction, instr.result_id()))) {
109 original_id_to_phi_id[instr.result_id()] =
110 GetFuzzerContext()->GetFreshId();
111 }
112 }
113 }
114 }
115 // Randomly decide between value "true" or "false" for a bool constant.
116 // Make sure the transformation has access to a bool constant to be used
117 // while creating conditional construct.
118 auto condition_id =
119 FindOrCreateBoolConstant(GetFuzzerContext()->ChooseEven(), true);
120
121 TransformationDuplicateRegionWithSelection transformation =
122 TransformationDuplicateRegionWithSelection(
123 GetFuzzerContext()->GetFreshId(), condition_id,
124 GetFuzzerContext()->GetFreshId(), entry_block->id(),
125 exit_block->id(), original_label_to_duplicate_label,
126 original_id_to_duplicate_id, original_id_to_phi_id);
127 MaybeApplyTransformation(transformation);
128 }
129 }
130 } // namespace fuzz
131 } // namespace spvtools
132