Debian Codegraph @

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

raw
1 // Copyright (c) 2019 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_outline_functions.h"
16
17 #include <vector>
18
19 #include "source/fuzz/fuzzer_util.h"
20 #include "source/fuzz/instruction_descriptor.h"
21 #include "source/fuzz/transformation_outline_function.h"
22 #include "source/fuzz/transformation_split_block.h"
23
24 namespace spvtools {
25 namespace fuzz {
26
27 FuzzerPassOutlineFunctions::FuzzerPassOutlineFunctions(
28 opt::IRContext* ir_context, TransformationContext* transformation_context,
29 FuzzerContext* fuzzer_context,
30 protobufs::TransformationSequence* transformations)
31 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
32 transformations) {}
33
34 FuzzerPassOutlineFunctions::~FuzzerPassOutlineFunctions() = default;
35
36 void FuzzerPassOutlineFunctions::Apply() {
37 std::vector<opt::Function*> original_functions;
38 for (auto& function : *GetIRContext()->module()) {
39 original_functions.push_back(&function);
40 }
41 for (auto& function : original_functions) {
42 if (!GetFuzzerContext()->ChoosePercentage(
43 GetFuzzerContext()->GetChanceOfOutliningFunction())) {
44 continue;
45 }
46 std::vector<opt::BasicBlock*> blocks;
47 for (auto& block : *function) {
48 blocks.push_back(&block);
49 }
50 auto entry_block = MaybeGetEntryBlockSuitableForOutlining(
51 blocks[GetFuzzerContext()->RandomIndex(blocks)]);
52
53 if (!entry_block) {
54 // The chosen block is not suitable to be the entry block of a region that
55 // will be outlined.
56 continue;
57 }
58
59 auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(function);
60 auto postdominator_analysis =
61 GetIRContext()->GetPostDominatorAnalysis(function);
62 std::vector<opt::BasicBlock*> candidate_exit_blocks;
63 for (auto postdominates_entry_block = entry_block;
64 postdominates_entry_block != nullptr;
65 postdominates_entry_block = postdominator_analysis->ImmediateDominator(
66 postdominates_entry_block)) {
67 // Consider the block if it is dominated by the entry block, ignore it if
68 // it is a continue target.
69 if (dominator_analysis->Dominates(entry_block,
70 postdominates_entry_block) &&
71 !GetIRContext()->GetStructuredCFGAnalysis()->IsContinueBlock(
72 postdominates_entry_block->id())) {
73 candidate_exit_blocks.push_back(postdominates_entry_block);
74 }
75 }
76 if (candidate_exit_blocks.empty()) {
77 continue;
78 }
79 auto exit_block = MaybeGetExitBlockSuitableForOutlining(
80 candidate_exit_blocks[GetFuzzerContext()->RandomIndex(
81 candidate_exit_blocks)]);
82
83 if (!exit_block) {
84 // The block chosen is not suitable
85 continue;
86 }
87
88 auto region_blocks = TransformationOutlineFunction::GetRegionBlocks(
89 GetIRContext(), entry_block, exit_block);
90 std::map<uint32_t, uint32_t> input_id_to_fresh_id;
91 for (auto id : TransformationOutlineFunction::GetRegionInputIds(
92 GetIRContext(), region_blocks, exit_block)) {
93 input_id_to_fresh_id[id] = GetFuzzerContext()->GetFreshId();
94 }
95 std::map<uint32_t, uint32_t> output_id_to_fresh_id;
96 for (auto id : TransformationOutlineFunction::GetRegionOutputIds(
97 GetIRContext(), region_blocks, exit_block)) {
98 output_id_to_fresh_id[id] = GetFuzzerContext()->GetFreshId();
99 }
100 TransformationOutlineFunction transformation(
101 entry_block->id(), exit_block->id(),
102 /*new_function_struct_return_type_id*/
103 GetFuzzerContext()->GetFreshId(),
104 /*new_function_type_id*/ GetFuzzerContext()->GetFreshId(),
105 /*new_function_id*/ GetFuzzerContext()->GetFreshId(),
106 /*new_function_region_entry_block*/
107 GetFuzzerContext()->GetFreshId(),
108 /*new_caller_result_id*/ GetFuzzerContext()->GetFreshId(),
109 /*new_callee_result_id*/ GetFuzzerContext()->GetFreshId(),
110 /*input_id_to_fresh_id*/ input_id_to_fresh_id,
111 /*output_id_to_fresh_id*/ output_id_to_fresh_id);
112 MaybeApplyTransformation(transformation);
113 }
114 }
115
116 opt::BasicBlock*
117 FuzzerPassOutlineFunctions::MaybeGetEntryBlockSuitableForOutlining(
118 opt::BasicBlock* entry_block) {
119 // If the entry block is a loop header, we need to get or create its
120 // preheader and make it the entry block, if possible.
121 if (entry_block->IsLoopHeader()) {
122 auto predecessors =
123 GetIRContext()->cfg()->preds(entry_block->GetLabel()->result_id());
124
125 if (predecessors.size() < 2) {
126 // The header only has one predecessor (the back-edge block) and thus
127 // it is unreachable. The block cannot be adjusted to be suitable for
128 // outlining.
129 return nullptr;
130 }
131
132 // Get or create a suitable preheader and make it become the entry block.
133 entry_block =
134 GetOrCreateSimpleLoopPreheader(entry_block->GetLabel()->result_id());
135 }
136
137 assert(!entry_block->IsLoopHeader() &&
138 "The entry block cannot be a loop header at this point.");
139
140 // If the entry block starts with OpPhi or OpVariable, try to split it.
141 if (entry_block->begin()->opcode() == SpvOpPhi ||
142 entry_block->begin()->opcode() == SpvOpVariable) {
143 // Find the first non-OpPhi and non-OpVariable instruction.
144 auto non_phi_or_var_inst = &*entry_block->begin();
145 while (non_phi_or_var_inst->opcode() == SpvOpPhi ||
146 non_phi_or_var_inst->opcode() == SpvOpVariable) {
147 non_phi_or_var_inst = non_phi_or_var_inst->NextNode();
148 }
149
150 // Split the block.
151 uint32_t new_block_id = GetFuzzerContext()->GetFreshId();
152 ApplyTransformation(TransformationSplitBlock(
153 MakeInstructionDescriptor(GetIRContext(), non_phi_or_var_inst),
154 new_block_id));
155
156 // The new entry block is the newly-created block.
157 entry_block = &*entry_block->GetParent()->FindBlock(new_block_id);
158 }
159
160 return entry_block;
161 }
162
163 opt::BasicBlock*
164 FuzzerPassOutlineFunctions::MaybeGetExitBlockSuitableForOutlining(
165 opt::BasicBlock* exit_block) {
166 // The exit block must not be a continue target.
167 assert(!GetIRContext()->GetStructuredCFGAnalysis()->IsContinueBlock(
168 exit_block->id()) &&
169 "A candidate exit block cannot be a continue target.");
170
171 // If the exit block is a merge block, try to split it and return the second
172 // block in the pair as the exit block.
173 if (GetIRContext()->GetStructuredCFGAnalysis()->IsMergeBlock(
174 exit_block->id())) {
175 uint32_t new_block_id = GetFuzzerContext()->GetFreshId();
176
177 // Find the first non-OpPhi instruction, after which to split.
178 auto split_before = &*exit_block->begin();
179 while (split_before->opcode() == SpvOpPhi) {
180 split_before = split_before->NextNode();
181 }
182
183 if (!MaybeApplyTransformation(TransformationSplitBlock(
184 MakeInstructionDescriptor(GetIRContext(), split_before),
185 new_block_id))) {
186 return nullptr;
187 }
188
189 return &*exit_block->GetParent()->FindBlock(new_block_id);
190 }
191
192 return exit_block;
193 }
194
195 } // namespace fuzz
196 } // namespace spvtools