1 // Copyright (c) 2020 Stefano Milizia
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_merge_function_returns.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/instruction_descriptor.h"
19 #include "source/fuzz/transformation_add_early_terminator_wrapper.h"
20 #include "source/fuzz/transformation_merge_function_returns.h"
21 #include "source/fuzz/transformation_wrap_early_terminator_in_function.h"
22
23 namespace spvtools {
24 namespace fuzz {
25
FuzzerPassMergeFunctionReturns(opt::IRContext * ir_context,TransformationContext * transformation_context,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformations,bool ignore_inapplicable_transformations)26 FuzzerPassMergeFunctionReturns::FuzzerPassMergeFunctionReturns(
27 opt::IRContext* ir_context, TransformationContext* transformation_context,
28 FuzzerContext* fuzzer_context,
29 protobufs::TransformationSequence* transformations,
30 bool ignore_inapplicable_transformations)
31 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
32 transformations, ignore_inapplicable_transformations) {}
33
Apply()34 void FuzzerPassMergeFunctionReturns::Apply() {
35 // The pass might add new functions to the module (due to wrapping early
36 // terminator instructions in function calls), so we record the functions that
37 // are currently present and then iterate over them.
38 std::vector<opt::Function*> functions;
39 for (auto& function : *GetIRContext()->module()) {
40 functions.emplace_back(&function);
41 }
42
43 for (auto* function : functions) {
44 // Randomly decide whether to consider this function.
45 if (GetFuzzerContext()->ChoosePercentage(
46 GetFuzzerContext()->GetChanceOfMergingFunctionReturns())) {
47 continue;
48 }
49
50 // We skip wrappers for early terminators, since this fuzzer pass introduces
51 // such wrappers to eliminate early terminators.
52 if (IsEarlyTerminatorWrapper(*function)) {
53 continue;
54 }
55
56 // Only consider functions that have early returns.
57 if (!function->HasEarlyReturn()) {
58 continue;
59 }
60
61 // Wrap early terminators in function calls.
62 ForEachInstructionWithInstructionDescriptor(
63 function,
64 [this, function](
65 opt::BasicBlock* /*unused*/, opt::BasicBlock::iterator inst_it,
66 const protobufs::InstructionDescriptor& instruction_descriptor) {
67 const SpvOp opcode = inst_it->opcode();
68 switch (opcode) {
69 case SpvOpKill:
70 case SpvOpUnreachable:
71 case SpvOpTerminateInvocation: {
72 // This is an early termination instruction - we need to wrap it
73 // so that it becomes a return.
74 if (TransformationWrapEarlyTerminatorInFunction::
75 MaybeGetWrapperFunction(GetIRContext(), opcode) ==
76 nullptr) {
77 // We don't have a suitable wrapper function, so create one.
78 ApplyTransformation(TransformationAddEarlyTerminatorWrapper(
79 GetFuzzerContext()->GetFreshId(),
80 GetFuzzerContext()->GetFreshId(), opcode));
81 }
82 // If the function has non-void return type then we need a
83 // suitable value to use in an OpReturnValue instruction.
84 opt::Instruction* function_return_type =
85 GetIRContext()->get_def_use_mgr()->GetDef(
86 function->type_id());
87 uint32_t returned_value_id;
88 if (function_return_type->opcode() == SpvOpTypeVoid) {
89 // No value is needed.
90 returned_value_id = 0;
91 } else if (fuzzerutil::CanCreateConstant(
92 GetIRContext(),
93 function_return_type->result_id())) {
94 // We favour returning an irrelevant zero.
95 returned_value_id = FindOrCreateZeroConstant(
96 function_return_type->result_id(), true);
97 } else {
98 // It's not possible to use an irrelevant zero, so we use an
99 // OpUndef instead.
100 returned_value_id =
101 FindOrCreateGlobalUndef(function_return_type->result_id());
102 }
103 // Wrap the early termination instruction in a function call.
104 ApplyTransformation(TransformationWrapEarlyTerminatorInFunction(
105 GetFuzzerContext()->GetFreshId(), instruction_descriptor,
106 returned_value_id));
107 break;
108 }
109 default:
110 break;
111 }
112 });
113
114 // Get the return blocks.
115 auto return_blocks = fuzzerutil::GetReachableReturnBlocks(
116 GetIRContext(), function->result_id());
117
118 // Only go ahead if there is more than one reachable return block.
119 if (return_blocks.size() <= 1) {
120 continue;
121 }
122
123 // Make sure that OpConstantTrue and OpConstantFalse are in the module.
124 FindOrCreateBoolConstant(true, false);
125 FindOrCreateBoolConstant(false, false);
126
127 // Collect the ids available after the entry block of the function.
128 auto ids_available_after_entry_block =
129 GetTypesToIdsAvailableAfterEntryBlock(function);
130
131 // If the entry block does not branch unconditionally to another block,
132 // split it.
133 if (function->entry()->terminator()->opcode() != SpvOpBranch) {
134 SplitBlockAfterOpPhiOrOpVariable(function->entry()->id());
135 }
136
137 // Collect the merge blocks of the function whose corresponding loops
138 // contain return blocks.
139 auto merge_blocks = GetMergeBlocksOfLoopsContainingBlocks(return_blocks);
140
141 // Split the merge blocks, if they contain instructions different from
142 // OpLabel, OpPhi and OpBranch. Collect the new ids of merge blocks.
143 std::vector<uint32_t> actual_merge_blocks;
144 for (uint32_t merge_block : merge_blocks) {
145 opt::BasicBlock* block = GetIRContext()->get_instr_block(merge_block);
146
147 // We don't need to split blocks that are already suitable (they only
148 // contain OpLabel, OpPhi or OpBranch instructions).
149 if (GetIRContext()
150 ->get_instr_block(merge_block)
151 ->WhileEachInst([](opt::Instruction* inst) {
152 return inst->opcode() == SpvOpLabel ||
153 inst->opcode() == SpvOpPhi ||
154 inst->opcode() == SpvOpBranch;
155 })) {
156 actual_merge_blocks.emplace_back(merge_block);
157 continue;
158 }
159
160 // If the merge block is also a loop header, we need to add a preheader,
161 // which will be the new merge block.
162 if (block->IsLoopHeader()) {
163 actual_merge_blocks.emplace_back(
164 GetOrCreateSimpleLoopPreheader(merge_block)->id());
165 continue;
166 }
167
168 // If the merge block is not a loop header, we must split it after the
169 // last OpPhi instruction. The merge block will be the first of the pair
170 // of blocks obtained after splitting, and it keeps the original id.
171 SplitBlockAfterOpPhiOrOpVariable(merge_block);
172 actual_merge_blocks.emplace_back(merge_block);
173 }
174
175 // Get the ids needed by the transformation.
176 const uint32_t outer_header_id = GetFuzzerContext()->GetFreshId();
177 const uint32_t unreachable_continue_id = GetFuzzerContext()->GetFreshId();
178 const uint32_t outer_return_id = GetFuzzerContext()->GetFreshId();
179
180 bool function_is_void =
181 GetIRContext()->get_type_mgr()->GetType(function->type_id())->AsVoid();
182
183 // We only need a return value if the function is not void.
184 uint32_t return_val_id =
185 function_is_void ? 0 : GetFuzzerContext()->GetFreshId();
186
187 // We only need a placeholder for the return value if the function is not
188 // void and there is at least one relevant merge block.
189 uint32_t returnable_val_id = 0;
190 if (!function_is_void && !actual_merge_blocks.empty()) {
191 // If there is an id of the suitable type, choose one at random.
192 if (ids_available_after_entry_block.count(function->type_id())) {
193 const auto& candidates =
194 ids_available_after_entry_block[function->type_id()];
195 returnable_val_id =
196 candidates[GetFuzzerContext()->RandomIndex(candidates)];
197 } else {
198 // If there is no id, add a global OpUndef.
199 uint32_t suitable_id = FindOrCreateGlobalUndef(function->type_id());
200 // Add the new id to the map of available ids.
201 ids_available_after_entry_block.emplace(
202 function->type_id(), std::vector<uint32_t>({suitable_id}));
203 returnable_val_id = suitable_id;
204 }
205 }
206
207 // Collect all the ids needed for merge blocks.
208 auto merge_blocks_info = GetInfoNeededForMergeBlocks(
209 actual_merge_blocks, &ids_available_after_entry_block);
210
211 // Apply the transformation if it is applicable (it could be inapplicable if
212 // adding new predecessors to merge blocks breaks dominance rules).
213 MaybeApplyTransformation(TransformationMergeFunctionReturns(
214 function->result_id(), outer_header_id, unreachable_continue_id,
215 outer_return_id, return_val_id, returnable_val_id, merge_blocks_info));
216 }
217 }
218
219 std::map<uint32_t, std::vector<uint32_t>>
GetTypesToIdsAvailableAfterEntryBlock(opt::Function * function) const220 FuzzerPassMergeFunctionReturns::GetTypesToIdsAvailableAfterEntryBlock(
221 opt::Function* function) const {
222 std::map<uint32_t, std::vector<uint32_t>> result;
223 // Consider all global declarations
224 for (auto& global : GetIRContext()->module()->types_values()) {
225 if (global.HasResultId() && global.type_id()) {
226 if (!result.count(global.type_id())) {
227 result.emplace(global.type_id(), std::vector<uint32_t>());
228 }
229 result[global.type_id()].emplace_back(global.result_id());
230 }
231 }
232
233 // Consider all function parameters
234 function->ForEachParam([&result](opt::Instruction* param) {
235 if (param->HasResultId() && param->type_id()) {
236 if (!result.count(param->type_id())) {
237 result.emplace(param->type_id(), std::vector<uint32_t>());
238 }
239
240 result[param->type_id()].emplace_back(param->result_id());
241 }
242 });
243
244 // Consider all the instructions in the entry block.
245 for (auto& inst : *function->entry()) {
246 if (inst.HasResultId() && inst.type_id()) {
247 if (!result.count(inst.type_id())) {
248 result.emplace(inst.type_id(), std::vector<uint32_t>());
249 }
250 result[inst.type_id()].emplace_back(inst.result_id());
251 }
252 }
253
254 return result;
255 }
256
257 std::set<uint32_t>
GetMergeBlocksOfLoopsContainingBlocks(const std::set<uint32_t> & blocks) const258 FuzzerPassMergeFunctionReturns::GetMergeBlocksOfLoopsContainingBlocks(
259 const std::set<uint32_t>& blocks) const {
260 std::set<uint32_t> result;
261 for (uint32_t block : blocks) {
262 uint32_t merge_block =
263 GetIRContext()->GetStructuredCFGAnalysis()->LoopMergeBlock(block);
264
265 while (merge_block != 0 && !result.count(merge_block)) {
266 // Add a new entry.
267 result.emplace(merge_block);
268
269 // Walk up the loop tree.
270 block = merge_block;
271 merge_block = GetIRContext()->GetStructuredCFGAnalysis()->LoopMergeBlock(
272 merge_block);
273 }
274 }
275
276 return result;
277 }
278
279 std::vector<protobufs::ReturnMergingInfo>
GetInfoNeededForMergeBlocks(const std::vector<uint32_t> & merge_blocks,std::map<uint32_t,std::vector<uint32_t>> * ids_available_after_entry_block)280 FuzzerPassMergeFunctionReturns::GetInfoNeededForMergeBlocks(
281 const std::vector<uint32_t>& merge_blocks,
282 std::map<uint32_t, std::vector<uint32_t>>*
283 ids_available_after_entry_block) {
284 std::vector<protobufs::ReturnMergingInfo> result;
285 for (uint32_t merge_block : merge_blocks) {
286 protobufs::ReturnMergingInfo info;
287 info.set_merge_block_id(merge_block);
288 info.set_is_returning_id(this->GetFuzzerContext()->GetFreshId());
289 info.set_maybe_return_val_id(this->GetFuzzerContext()->GetFreshId());
290
291 // Add all the ids needed for the OpPhi instructions.
292 this->GetIRContext()
293 ->get_instr_block(merge_block)
294 ->ForEachPhiInst([this, &info, &ids_available_after_entry_block](
295 opt::Instruction* phi_inst) {
296 protobufs::UInt32Pair entry;
297 entry.set_first(phi_inst->result_id());
298
299 // If there is an id of the suitable type, choose one at random.
300 if (ids_available_after_entry_block->count(phi_inst->type_id())) {
301 auto& candidates =
302 ids_available_after_entry_block->at(phi_inst->type_id());
303 entry.set_second(
304 candidates[this->GetFuzzerContext()->RandomIndex(candidates)]);
305 } else {
306 // If there is no id, add a global OpUndef.
307 uint32_t suitable_id =
308 this->FindOrCreateGlobalUndef(phi_inst->type_id());
309 // Add the new id to the map of available ids.
310 ids_available_after_entry_block->emplace(
311 phi_inst->type_id(), std::vector<uint32_t>({suitable_id}));
312 entry.set_second(suitable_id);
313 }
314
315 // Add the entry to the list.
316 *info.add_opphi_to_suitable_id() = entry;
317 });
318
319 result.emplace_back(info);
320 }
321
322 return result;
323 }
324
IsEarlyTerminatorWrapper(const opt::Function & function) const325 bool FuzzerPassMergeFunctionReturns::IsEarlyTerminatorWrapper(
326 const opt::Function& function) const {
327 for (SpvOp opcode : {SpvOpKill, SpvOpUnreachable, SpvOpTerminateInvocation}) {
328 if (TransformationWrapEarlyTerminatorInFunction::MaybeGetWrapperFunction(
329 GetIRContext(), opcode) == &function) {
330 return true;
331 }
332 }
333 return false;
334 }
335
336 } // namespace fuzz
337 } // namespace spvtools
338