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.h"
16
17 #include <set>
18
19 #include "source/fuzz/fuzzer_util.h"
20 #include "source/fuzz/id_use_descriptor.h"
21 #include "source/fuzz/instruction_descriptor.h"
22 #include "source/fuzz/transformation_add_constant_boolean.h"
23 #include "source/fuzz/transformation_add_constant_composite.h"
24 #include "source/fuzz/transformation_add_constant_null.h"
25 #include "source/fuzz/transformation_add_constant_scalar.h"
26 #include "source/fuzz/transformation_add_global_undef.h"
27 #include "source/fuzz/transformation_add_global_variable.h"
28 #include "source/fuzz/transformation_add_local_variable.h"
29 #include "source/fuzz/transformation_add_loop_preheader.h"
30 #include "source/fuzz/transformation_add_type_boolean.h"
31 #include "source/fuzz/transformation_add_type_float.h"
32 #include "source/fuzz/transformation_add_type_function.h"
33 #include "source/fuzz/transformation_add_type_int.h"
34 #include "source/fuzz/transformation_add_type_matrix.h"
35 #include "source/fuzz/transformation_add_type_pointer.h"
36 #include "source/fuzz/transformation_add_type_struct.h"
37 #include "source/fuzz/transformation_add_type_vector.h"
38 #include "source/fuzz/transformation_split_block.h"
39
40 namespace spvtools {
41 namespace fuzz {
42
FuzzerPass(opt::IRContext * ir_context,TransformationContext * transformation_context,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformations)43 FuzzerPass::FuzzerPass(opt::IRContext* ir_context,
44 TransformationContext* transformation_context,
45 FuzzerContext* fuzzer_context,
46 protobufs::TransformationSequence* transformations)
47 : ir_context_(ir_context),
48 transformation_context_(transformation_context),
49 fuzzer_context_(fuzzer_context),
50 transformations_(transformations) {}
51
52 FuzzerPass::~FuzzerPass() = default;
53
FindAvailableInstructions(opt::Function * function,opt::BasicBlock * block,const opt::BasicBlock::iterator & inst_it,std::function<bool (opt::IRContext *,opt::Instruction *)> instruction_is_relevant) const54 std::vector<opt::Instruction*> FuzzerPass::FindAvailableInstructions(
55 opt::Function* function, opt::BasicBlock* block,
56 const opt::BasicBlock::iterator& inst_it,
57 std::function<bool(opt::IRContext*, opt::Instruction*)>
58 instruction_is_relevant) const {
59 // TODO(afd) The following is (relatively) simple, but may end up being
60 // prohibitively inefficient, as it walks the whole dominator tree for
61 // every instruction that is considered.
62
63 std::vector<opt::Instruction*> result;
64 // Consider all global declarations
65 for (auto& global : GetIRContext()->module()->types_values()) {
66 if (instruction_is_relevant(GetIRContext(), &global)) {
67 result.push_back(&global);
68 }
69 }
70
71 // Consider all function parameters
72 function->ForEachParam(
73 [this, &instruction_is_relevant, &result](opt::Instruction* param) {
74 if (instruction_is_relevant(GetIRContext(), param)) {
75 result.push_back(param);
76 }
77 });
78
79 // Consider all previous instructions in this block
80 for (auto prev_inst_it = block->begin(); prev_inst_it != inst_it;
81 ++prev_inst_it) {
82 if (instruction_is_relevant(GetIRContext(), &*prev_inst_it)) {
83 result.push_back(&*prev_inst_it);
84 }
85 }
86
87 // Walk the dominator tree to consider all instructions from dominating
88 // blocks
89 auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(function);
90 for (auto next_dominator = dominator_analysis->ImmediateDominator(block);
91 next_dominator != nullptr;
92 next_dominator =
93 dominator_analysis->ImmediateDominator(next_dominator)) {
94 for (auto& dominating_inst : *next_dominator) {
95 if (instruction_is_relevant(GetIRContext(), &dominating_inst)) {
96 result.push_back(&dominating_inst);
97 }
98 }
99 }
100 return result;
101 }
102
ForEachInstructionWithInstructionDescriptor(opt::Function * function,std::function<void (opt::BasicBlock * block,opt::BasicBlock::iterator inst_it,const protobufs::InstructionDescriptor & instruction_descriptor)> action)103 void FuzzerPass::ForEachInstructionWithInstructionDescriptor(
104 opt::Function* function,
105 std::function<
106 void(opt::BasicBlock* block, opt::BasicBlock::iterator inst_it,
107 const protobufs::InstructionDescriptor& instruction_descriptor)>
108 action) {
109 // Consider only reachable blocks. We do this in a separate loop to avoid
110 // recomputing the dominator analysis every time |action| changes the
111 // module.
112 std::vector<opt::BasicBlock*> reachable_blocks;
113
114 const auto* dominator_analysis =
115 GetIRContext()->GetDominatorAnalysis(function);
116 for (auto& block : *function) {
117 if (dominator_analysis->IsReachable(&block)) {
118 reachable_blocks.push_back(&block);
119 }
120 }
121
122 for (auto* block : reachable_blocks) {
123 // We now consider every instruction in the block, randomly deciding
124 // whether to apply a transformation before it.
125
126 // In order for transformations to insert new instructions, they need to
127 // be able to identify the instruction to insert before. We describe an
128 // instruction via its opcode, 'opc', a base instruction 'base' that has a
129 // result id, and the number of instructions with opcode 'opc' that we
130 // should skip when searching from 'base' for the desired instruction.
131 // (An instruction that has a result id is represented by its own opcode,
132 // itself as 'base', and a skip-count of 0.)
133 std::vector<std::tuple<uint32_t, SpvOp, uint32_t>> base_opcode_skip_triples;
134
135 // The initial base instruction is the block label.
136 uint32_t base = block->id();
137
138 // Counts the number of times we have seen each opcode since we reset the
139 // base instruction.
140 std::map<SpvOp, uint32_t> skip_count;
141
142 // Consider every instruction in the block. The label is excluded: it is
143 // only necessary to consider it as a base in case the first instruction
144 // in the block does not have a result id.
145 for (auto inst_it = block->begin(); inst_it != block->end(); ++inst_it) {
146 if (inst_it->HasResultId()) {
147 // In the case that the instruction has a result id, we use the
148 // instruction as its own base, and clear the skip counts we have
149 // collected.
150 base = inst_it->result_id();
151 skip_count.clear();
152 }
153 const SpvOp opcode = inst_it->opcode();
154
155 // Invoke the provided function, which might apply a transformation.
156 action(block, inst_it,
157 MakeInstructionDescriptor(
158 base, opcode,
159 skip_count.count(opcode) ? skip_count.at(opcode) : 0));
160
161 if (!inst_it->HasResultId()) {
162 skip_count[opcode] =
163 skip_count.count(opcode) ? skip_count.at(opcode) + 1 : 1;
164 }
165 }
166 }
167 }
168
ForEachInstructionWithInstructionDescriptor(std::function<void (opt::Function * function,opt::BasicBlock * block,opt::BasicBlock::iterator inst_it,const protobufs::InstructionDescriptor & instruction_descriptor)> action)169 void FuzzerPass::ForEachInstructionWithInstructionDescriptor(
170 std::function<
171 void(opt::Function* function, opt::BasicBlock* block,
172 opt::BasicBlock::iterator inst_it,
173 const protobufs::InstructionDescriptor& instruction_descriptor)>
174 action) {
175 // Consider every block in every function.
176 for (auto& function : *GetIRContext()->module()) {
177 ForEachInstructionWithInstructionDescriptor(
178 &function,
179 [&action, &function](
180 opt::BasicBlock* block, opt::BasicBlock::iterator inst_it,
181 const protobufs::InstructionDescriptor& instruction_descriptor) {
182 action(&function, block, inst_it, instruction_descriptor);
183 });
184 }
185 }
186
FindOrCreateBoolType()187 uint32_t FuzzerPass::FindOrCreateBoolType() {
188 if (auto existing_id = fuzzerutil::MaybeGetBoolType(GetIRContext())) {
189 return existing_id;
190 }
191 auto result = GetFuzzerContext()->GetFreshId();
192 ApplyTransformation(TransformationAddTypeBoolean(result));
193 return result;
194 }
195
FindOrCreateIntegerType(uint32_t width,bool is_signed)196 uint32_t FuzzerPass::FindOrCreateIntegerType(uint32_t width, bool is_signed) {
197 opt::analysis::Integer int_type(width, is_signed);
198 auto existing_id = GetIRContext()->get_type_mgr()->GetId(&int_type);
199 if (existing_id) {
200 return existing_id;
201 }
202 auto result = GetFuzzerContext()->GetFreshId();
203 ApplyTransformation(TransformationAddTypeInt(result, width, is_signed));
204 return result;
205 }
206
FindOrCreateFloatType(uint32_t width)207 uint32_t FuzzerPass::FindOrCreateFloatType(uint32_t width) {
208 opt::analysis::Float float_type(width);
209 auto existing_id = GetIRContext()->get_type_mgr()->GetId(&float_type);
210 if (existing_id) {
211 return existing_id;
212 }
213 auto result = GetFuzzerContext()->GetFreshId();
214 ApplyTransformation(TransformationAddTypeFloat(result, width));
215 return result;
216 }
217
FindOrCreateFunctionType(uint32_t return_type_id,const std::vector<uint32_t> & argument_id)218 uint32_t FuzzerPass::FindOrCreateFunctionType(
219 uint32_t return_type_id, const std::vector<uint32_t>& argument_id) {
220 // FindFunctionType has a sigle argument for OpTypeFunction operands
221 // so we will have to copy them all in this vector
222 std::vector<uint32_t> type_ids(argument_id.size() + 1);
223 type_ids[0] = return_type_id;
224 std::copy(argument_id.begin(), argument_id.end(), type_ids.begin() + 1);
225
226 // Check if type exists
227 auto existing_id = fuzzerutil::FindFunctionType(GetIRContext(), type_ids);
228 if (existing_id) {
229 return existing_id;
230 }
231
232 auto result = GetFuzzerContext()->GetFreshId();
233 ApplyTransformation(
234 TransformationAddTypeFunction(result, return_type_id, argument_id));
235 return result;
236 }
237
FindOrCreateVectorType(uint32_t component_type_id,uint32_t component_count)238 uint32_t FuzzerPass::FindOrCreateVectorType(uint32_t component_type_id,
239 uint32_t component_count) {
240 assert(component_count >= 2 && component_count <= 4 &&
241 "Precondition: component count must be in range [2, 4].");
242 opt::analysis::Type* component_type =
243 GetIRContext()->get_type_mgr()->GetType(component_type_id);
244 assert(component_type && "Precondition: the component type must exist.");
245 opt::analysis::Vector vector_type(component_type, component_count);
246 auto existing_id = GetIRContext()->get_type_mgr()->GetId(&vector_type);
247 if (existing_id) {
248 return existing_id;
249 }
250 auto result = GetFuzzerContext()->GetFreshId();
251 ApplyTransformation(
252 TransformationAddTypeVector(result, component_type_id, component_count));
253 return result;
254 }
255
FindOrCreateMatrixType(uint32_t column_count,uint32_t row_count)256 uint32_t FuzzerPass::FindOrCreateMatrixType(uint32_t column_count,
257 uint32_t row_count) {
258 assert(column_count >= 2 && column_count <= 4 &&
259 "Precondition: column count must be in range [2, 4].");
260 assert(row_count >= 2 && row_count <= 4 &&
261 "Precondition: row count must be in range [2, 4].");
262 uint32_t column_type_id =
263 FindOrCreateVectorType(FindOrCreateFloatType(32), row_count);
264 opt::analysis::Type* column_type =
265 GetIRContext()->get_type_mgr()->GetType(column_type_id);
266 opt::analysis::Matrix matrix_type(column_type, column_count);
267 auto existing_id = GetIRContext()->get_type_mgr()->GetId(&matrix_type);
268 if (existing_id) {
269 return existing_id;
270 }
271 auto result = GetFuzzerContext()->GetFreshId();
272 ApplyTransformation(
273 TransformationAddTypeMatrix(result, column_type_id, column_count));
274 return result;
275 }
276
FindOrCreateStructType(const std::vector<uint32_t> & component_type_ids)277 uint32_t FuzzerPass::FindOrCreateStructType(
278 const std::vector<uint32_t>& component_type_ids) {
279 if (auto existing_id =
280 fuzzerutil::MaybeGetStructType(GetIRContext(), component_type_ids)) {
281 return existing_id;
282 }
283 auto new_id = GetFuzzerContext()->GetFreshId();
284 ApplyTransformation(TransformationAddTypeStruct(new_id, component_type_ids));
285 return new_id;
286 }
287
FindOrCreatePointerType(uint32_t base_type_id,SpvStorageClass storage_class)288 uint32_t FuzzerPass::FindOrCreatePointerType(uint32_t base_type_id,
289 SpvStorageClass storage_class) {
290 // We do not use the type manager here, due to problems related to isomorphic
291 // but distinct structs not being regarded as different.
292 auto existing_id = fuzzerutil::MaybeGetPointerType(
293 GetIRContext(), base_type_id, storage_class);
294 if (existing_id) {
295 return existing_id;
296 }
297 auto result = GetFuzzerContext()->GetFreshId();
298 ApplyTransformation(
299 TransformationAddTypePointer(result, storage_class, base_type_id));
300 return result;
301 }
302
FindOrCreatePointerToIntegerType(uint32_t width,bool is_signed,SpvStorageClass storage_class)303 uint32_t FuzzerPass::FindOrCreatePointerToIntegerType(
304 uint32_t width, bool is_signed, SpvStorageClass storage_class) {
305 return FindOrCreatePointerType(FindOrCreateIntegerType(width, is_signed),
306 storage_class);
307 }
308
FindOrCreateIntegerConstant(const std::vector<uint32_t> & words,uint32_t width,bool is_signed,bool is_irrelevant)309 uint32_t FuzzerPass::FindOrCreateIntegerConstant(
310 const std::vector<uint32_t>& words, uint32_t width, bool is_signed,
311 bool is_irrelevant) {
312 auto int_type_id = FindOrCreateIntegerType(width, is_signed);
313 if (auto constant_id = fuzzerutil::MaybeGetScalarConstant(
314 GetIRContext(), *GetTransformationContext(), words, int_type_id,
315 is_irrelevant)) {
316 return constant_id;
317 }
318 auto result = GetFuzzerContext()->GetFreshId();
319 ApplyTransformation(TransformationAddConstantScalar(result, int_type_id,
320 words, is_irrelevant));
321 return result;
322 }
323
FindOrCreateFloatConstant(const std::vector<uint32_t> & words,uint32_t width,bool is_irrelevant)324 uint32_t FuzzerPass::FindOrCreateFloatConstant(
325 const std::vector<uint32_t>& words, uint32_t width, bool is_irrelevant) {
326 auto float_type_id = FindOrCreateFloatType(width);
327 if (auto constant_id = fuzzerutil::MaybeGetScalarConstant(
328 GetIRContext(), *GetTransformationContext(), words, float_type_id,
329 is_irrelevant)) {
330 return constant_id;
331 }
332 auto result = GetFuzzerContext()->GetFreshId();
333 ApplyTransformation(TransformationAddConstantScalar(result, float_type_id,
334 words, is_irrelevant));
335 return result;
336 }
337
FindOrCreateBoolConstant(bool value,bool is_irrelevant)338 uint32_t FuzzerPass::FindOrCreateBoolConstant(bool value, bool is_irrelevant) {
339 auto bool_type_id = FindOrCreateBoolType();
340 if (auto constant_id = fuzzerutil::MaybeGetScalarConstant(
341 GetIRContext(), *GetTransformationContext(), {value ? 1u : 0u},
342 bool_type_id, is_irrelevant)) {
343 return constant_id;
344 }
345 auto result = GetFuzzerContext()->GetFreshId();
346 ApplyTransformation(
347 TransformationAddConstantBoolean(result, value, is_irrelevant));
348 return result;
349 }
350
FindOrCreateConstant(const std::vector<uint32_t> & words,uint32_t type_id,bool is_irrelevant)351 uint32_t FuzzerPass::FindOrCreateConstant(const std::vector<uint32_t>& words,
352 uint32_t type_id,
353 bool is_irrelevant) {
354 assert(type_id && "Constant's type id can't be 0.");
355
356 const auto* type = GetIRContext()->get_type_mgr()->GetType(type_id);
357 assert(type && "Type does not exist.");
358
359 if (type->AsBool()) {
360 assert(words.size() == 1);
361 return FindOrCreateBoolConstant(words[0], is_irrelevant);
362 } else if (const auto* integer = type->AsInteger()) {
363 return FindOrCreateIntegerConstant(words, integer->width(),
364 integer->IsSigned(), is_irrelevant);
365 } else if (const auto* floating = type->AsFloat()) {
366 return FindOrCreateFloatConstant(words, floating->width(), is_irrelevant);
367 }
368
369 // This assertion will fail in debug build but not in release build
370 // so we return 0 to make compiler happy.
371 assert(false && "Constant type is not supported");
372 return 0;
373 }
374
FindOrCreateCompositeConstant(const std::vector<uint32_t> & component_ids,uint32_t type_id,bool is_irrelevant)375 uint32_t FuzzerPass::FindOrCreateCompositeConstant(
376 const std::vector<uint32_t>& component_ids, uint32_t type_id,
377 bool is_irrelevant) {
378 if (auto existing_constant = fuzzerutil::MaybeGetCompositeConstant(
379 GetIRContext(), *GetTransformationContext(), component_ids, type_id,
380 is_irrelevant)) {
381 return existing_constant;
382 }
383 uint32_t result = GetFuzzerContext()->GetFreshId();
384 ApplyTransformation(TransformationAddConstantComposite(
385 result, type_id, component_ids, is_irrelevant));
386 return result;
387 }
388
FindOrCreateGlobalUndef(uint32_t type_id)389 uint32_t FuzzerPass::FindOrCreateGlobalUndef(uint32_t type_id) {
390 for (auto& inst : GetIRContext()->types_values()) {
391 if (inst.opcode() == SpvOpUndef && inst.type_id() == type_id) {
392 return inst.result_id();
393 }
394 }
395 auto result = GetFuzzerContext()->GetFreshId();
396 ApplyTransformation(TransformationAddGlobalUndef(result, type_id));
397 return result;
398 }
399
FindOrCreateNullConstant(uint32_t type_id)400 uint32_t FuzzerPass::FindOrCreateNullConstant(uint32_t type_id) {
401 // Find existing declaration
402 opt::analysis::NullConstant null_constant(
403 GetIRContext()->get_type_mgr()->GetType(type_id));
404 auto existing_constant =
405 GetIRContext()->get_constant_mgr()->FindConstant(&null_constant);
406
407 // Return if found
408 if (existing_constant) {
409 return GetIRContext()
410 ->get_constant_mgr()
411 ->GetDefiningInstruction(existing_constant)
412 ->result_id();
413 }
414
415 // Create new if not found
416 auto result = GetFuzzerContext()->GetFreshId();
417 ApplyTransformation(TransformationAddConstantNull(result, type_id));
418 return result;
419 }
420
421 std::pair<std::vector<uint32_t>, std::map<uint32_t, std::vector<uint32_t>>>
GetAvailableBasicTypesAndPointers(SpvStorageClass storage_class) const422 FuzzerPass::GetAvailableBasicTypesAndPointers(
423 SpvStorageClass storage_class) const {
424 // Records all of the basic types available in the module.
425 std::set<uint32_t> basic_types;
426
427 // For each basic type, records all the associated pointer types that target
428 // the basic type and that have |storage_class| as their storage class.
429 std::map<uint32_t, std::vector<uint32_t>> basic_type_to_pointers;
430
431 for (auto& inst : GetIRContext()->types_values()) {
432 // For each basic type that we come across, record type, and the fact that
433 // we cannot yet have seen any pointers that use the basic type as its
434 // pointee type.
435 //
436 // For pointer types with basic pointee types, associate the pointer type
437 // with the basic type.
438 switch (inst.opcode()) {
439 case SpvOpTypeBool:
440 case SpvOpTypeFloat:
441 case SpvOpTypeInt:
442 case SpvOpTypeMatrix:
443 case SpvOpTypeVector:
444 // These are all basic types.
445 basic_types.insert(inst.result_id());
446 basic_type_to_pointers.insert({inst.result_id(), {}});
447 break;
448 case SpvOpTypeArray:
449 // An array type is basic if its base type is basic.
450 if (basic_types.count(inst.GetSingleWordInOperand(0))) {
451 basic_types.insert(inst.result_id());
452 basic_type_to_pointers.insert({inst.result_id(), {}});
453 }
454 break;
455 case SpvOpTypeStruct: {
456 // A struct type is basic if it does not have the Block/BufferBlock
457 // decoration, and if all of its members are basic.
458 if (!fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(),
459 inst.result_id())) {
460 bool all_members_are_basic_types = true;
461 for (uint32_t i = 0; i < inst.NumInOperands(); i++) {
462 if (!basic_types.count(inst.GetSingleWordInOperand(i))) {
463 all_members_are_basic_types = false;
464 break;
465 }
466 }
467 if (all_members_are_basic_types) {
468 basic_types.insert(inst.result_id());
469 basic_type_to_pointers.insert({inst.result_id(), {}});
470 }
471 }
472 break;
473 }
474 case SpvOpTypePointer: {
475 // We are interested in the pointer if its pointee type is basic and it
476 // has the right storage class.
477 auto pointee_type = inst.GetSingleWordInOperand(1);
478 if (inst.GetSingleWordInOperand(0) == storage_class &&
479 basic_types.count(pointee_type)) {
480 // The pointer has the desired storage class, and its pointee type is
481 // a basic type, so we are interested in it. Associate it with its
482 // basic type.
483 basic_type_to_pointers.at(pointee_type).push_back(inst.result_id());
484 }
485 break;
486 }
487 default:
488 break;
489 }
490 }
491 return {{basic_types.begin(), basic_types.end()}, basic_type_to_pointers};
492 }
493
FindOrCreateZeroConstant(uint32_t scalar_or_composite_type_id,bool is_irrelevant)494 uint32_t FuzzerPass::FindOrCreateZeroConstant(
495 uint32_t scalar_or_composite_type_id, bool is_irrelevant) {
496 auto type_instruction =
497 GetIRContext()->get_def_use_mgr()->GetDef(scalar_or_composite_type_id);
498 assert(type_instruction && "The type instruction must exist.");
499 switch (type_instruction->opcode()) {
500 case SpvOpTypeBool:
501 return FindOrCreateBoolConstant(false, is_irrelevant);
502 case SpvOpTypeFloat: {
503 auto width = type_instruction->GetSingleWordInOperand(0);
504 auto num_words = (width + 32 - 1) / 32;
505 return FindOrCreateFloatConstant(std::vector<uint32_t>(num_words, 0),
506 width, is_irrelevant);
507 }
508 case SpvOpTypeInt: {
509 auto width = type_instruction->GetSingleWordInOperand(0);
510 auto num_words = (width + 32 - 1) / 32;
511 return FindOrCreateIntegerConstant(
512 std::vector<uint32_t>(num_words, 0), width,
513 type_instruction->GetSingleWordInOperand(1), is_irrelevant);
514 }
515 case SpvOpTypeArray: {
516 auto component_type_id = type_instruction->GetSingleWordInOperand(0);
517 auto num_components =
518 fuzzerutil::GetArraySize(*type_instruction, GetIRContext());
519 return FindOrCreateCompositeConstant(
520 std::vector<uint32_t>(
521 num_components,
522 FindOrCreateZeroConstant(component_type_id, is_irrelevant)),
523 scalar_or_composite_type_id, is_irrelevant);
524 }
525 case SpvOpTypeMatrix:
526 case SpvOpTypeVector: {
527 auto component_type_id = type_instruction->GetSingleWordInOperand(0);
528 auto num_components = type_instruction->GetSingleWordInOperand(1);
529 return FindOrCreateCompositeConstant(
530 std::vector<uint32_t>(
531 num_components,
532 FindOrCreateZeroConstant(component_type_id, is_irrelevant)),
533 scalar_or_composite_type_id, is_irrelevant);
534 }
535 case SpvOpTypeStruct: {
536 assert(!fuzzerutil::HasBlockOrBufferBlockDecoration(
537 GetIRContext(), scalar_or_composite_type_id) &&
538 "We do not construct constants of struct types decorated with "
539 "Block or BufferBlock.");
540 std::vector<uint32_t> field_zero_ids;
541 for (uint32_t index = 0; index < type_instruction->NumInOperands();
542 index++) {
543 field_zero_ids.push_back(FindOrCreateZeroConstant(
544 type_instruction->GetSingleWordInOperand(index), is_irrelevant));
545 }
546 return FindOrCreateCompositeConstant(
547 field_zero_ids, scalar_or_composite_type_id, is_irrelevant);
548 }
549 default:
550 assert(false && "Unknown type.");
551 return 0;
552 }
553 }
554
MaybeAddUseToReplace(opt::Instruction * use_inst,uint32_t use_index,uint32_t replacement_id,std::vector<std::pair<protobufs::IdUseDescriptor,uint32_t>> * uses_to_replace)555 void FuzzerPass::MaybeAddUseToReplace(
556 opt::Instruction* use_inst, uint32_t use_index, uint32_t replacement_id,
557 std::vector<std::pair<protobufs::IdUseDescriptor, uint32_t>>*
558 uses_to_replace) {
559 // Only consider this use if it is in a block
560 if (!GetIRContext()->get_instr_block(use_inst)) {
561 return;
562 }
563
564 // Get the index of the operand restricted to input operands.
565 uint32_t in_operand_index =
566 fuzzerutil::InOperandIndexFromOperandIndex(*use_inst, use_index);
567 auto id_use_descriptor =
568 MakeIdUseDescriptorFromUse(GetIRContext(), use_inst, in_operand_index);
569 uses_to_replace->emplace_back(
570 std::make_pair(id_use_descriptor, replacement_id));
571 }
572
GetOrCreateSimpleLoopPreheader(uint32_t header_id)573 opt::BasicBlock* FuzzerPass::GetOrCreateSimpleLoopPreheader(
574 uint32_t header_id) {
575 auto header_block = fuzzerutil::MaybeFindBlock(GetIRContext(), header_id);
576
577 assert(header_block && header_block->IsLoopHeader() &&
578 "|header_id| should be the label id of a loop header");
579
580 auto predecessors = GetIRContext()->cfg()->preds(header_id);
581
582 assert(predecessors.size() >= 2 &&
583 "The block |header_id| should be reachable.");
584
585 auto function = header_block->GetParent();
586
587 if (predecessors.size() == 2) {
588 // The header has a single out-of-loop predecessor, which could be a
589 // preheader.
590
591 opt::BasicBlock* maybe_preheader;
592
593 if (GetIRContext()->GetDominatorAnalysis(function)->Dominates(
594 header_id, predecessors[0])) {
595 // The first predecessor is the back-edge block, because the header
596 // dominates it, so the second one is out of the loop.
597 maybe_preheader = &*function->FindBlock(predecessors[1]);
598 } else {
599 // The first predecessor is out of the loop.
600 maybe_preheader = &*function->FindBlock(predecessors[0]);
601 }
602
603 // |maybe_preheader| is a preheader if it branches unconditionally to
604 // the header. We also require it not to be a loop header.
605 if (maybe_preheader->terminator()->opcode() == SpvOpBranch &&
606 !maybe_preheader->IsLoopHeader()) {
607 return maybe_preheader;
608 }
609 }
610
611 // We need to add a preheader.
612
613 // Get a fresh id for the preheader.
614 uint32_t preheader_id = GetFuzzerContext()->GetFreshId();
615
616 // Get a fresh id for each OpPhi instruction, if there is more than one
617 // out-of-loop predecessor.
618 std::vector<uint32_t> phi_ids;
619 if (predecessors.size() > 2) {
620 header_block->ForEachPhiInst(
621 [this, &phi_ids](opt::Instruction* /* unused */) {
622 phi_ids.push_back(GetFuzzerContext()->GetFreshId());
623 });
624 }
625
626 // Add the preheader.
627 ApplyTransformation(
628 TransformationAddLoopPreheader(header_id, preheader_id, phi_ids));
629
630 // Make the newly-created preheader the new entry block.
631 return &*function->FindBlock(preheader_id);
632 }
633
SplitBlockAfterOpPhiOrOpVariable(uint32_t block_id)634 opt::BasicBlock* FuzzerPass::SplitBlockAfterOpPhiOrOpVariable(
635 uint32_t block_id) {
636 auto block = fuzzerutil::MaybeFindBlock(GetIRContext(), block_id);
637 assert(block && "|block_id| must be a block label");
638 assert(!block->IsLoopHeader() && "|block_id| cannot be a loop header");
639
640 // Find the first non-OpPhi and non-OpVariable instruction.
641 auto non_phi_or_var_inst = &*block->begin();
642 while (non_phi_or_var_inst->opcode() == SpvOpPhi ||
643 non_phi_or_var_inst->opcode() == SpvOpVariable) {
644 non_phi_or_var_inst = non_phi_or_var_inst->NextNode();
645 }
646
647 // Split the block.
648 uint32_t new_block_id = GetFuzzerContext()->GetFreshId();
649 ApplyTransformation(TransformationSplitBlock(
650 MakeInstructionDescriptor(GetIRContext(), non_phi_or_var_inst),
651 new_block_id));
652
653 // We need to return the newly-created block.
654 return &*block->GetParent()->FindBlock(new_block_id);
655 }
656
FindOrCreateLocalVariable(uint32_t pointer_type_id,uint32_t function_id,bool pointee_value_is_irrelevant)657 uint32_t FuzzerPass::FindOrCreateLocalVariable(
658 uint32_t pointer_type_id, uint32_t function_id,
659 bool pointee_value_is_irrelevant) {
660 auto pointer_type = GetIRContext()->get_type_mgr()->GetType(pointer_type_id);
661 // No unused variables in release mode.
662 (void)pointer_type;
663 assert(pointer_type && pointer_type->AsPointer() &&
664 pointer_type->AsPointer()->storage_class() ==
665 SpvStorageClassFunction &&
666 "The pointer_type_id must refer to a defined pointer type with "
667 "storage class Function");
668 auto function = fuzzerutil::FindFunction(GetIRContext(), function_id);
669 assert(function && "The function must be defined.");
670
671 // First we try to find a suitable existing variable.
672 // All of the local variable declarations are located in the first block.
673 for (auto& instruction : *function->begin()) {
674 if (instruction.opcode() != SpvOpVariable) {
675 continue;
676 }
677 // The existing OpVariable must have type |pointer_type_id|.
678 if (instruction.type_id() != pointer_type_id) {
679 continue;
680 }
681 // Check if the found variable is marked with PointeeValueIsIrrelevant
682 // according to |pointee_value_is_irrelevant|.
683 if (GetTransformationContext()->GetFactManager()->PointeeValueIsIrrelevant(
684 instruction.result_id()) != pointee_value_is_irrelevant) {
685 continue;
686 }
687 return instruction.result_id();
688 }
689
690 // No such variable was found. Apply a transformation to get one.
691 uint32_t pointee_type_id = fuzzerutil::GetPointeeTypeIdFromPointerType(
692 GetIRContext(), pointer_type_id);
693 uint32_t result_id = GetFuzzerContext()->GetFreshId();
694 ApplyTransformation(TransformationAddLocalVariable(
695 result_id, pointer_type_id, function_id,
696 FindOrCreateZeroConstant(pointee_type_id, pointee_value_is_irrelevant),
697 pointee_value_is_irrelevant));
698 return result_id;
699 }
700
FindOrCreateGlobalVariable(uint32_t pointer_type_id,bool pointee_value_is_irrelevant)701 uint32_t FuzzerPass::FindOrCreateGlobalVariable(
702 uint32_t pointer_type_id, bool pointee_value_is_irrelevant) {
703 auto pointer_type = GetIRContext()->get_type_mgr()->GetType(pointer_type_id);
704 // No unused variables in release mode.
705 (void)pointer_type;
706 assert(
707 pointer_type && pointer_type->AsPointer() &&
708 (pointer_type->AsPointer()->storage_class() == SpvStorageClassPrivate ||
709 pointer_type->AsPointer()->storage_class() ==
710 SpvStorageClassWorkgroup) &&
711 "The pointer_type_id must refer to a defined pointer type with storage "
712 "class Private or Workgroup");
713
714 // First we try to find a suitable existing variable.
715 for (auto& instruction : GetIRContext()->module()->types_values()) {
716 if (instruction.opcode() != SpvOpVariable) {
717 continue;
718 }
719 // The existing OpVariable must have type |pointer_type_id|.
720 if (instruction.type_id() != pointer_type_id) {
721 continue;
722 }
723 // Check if the found variable is marked with PointeeValueIsIrrelevant
724 // according to |pointee_value_is_irrelevant|.
725 if (GetTransformationContext()->GetFactManager()->PointeeValueIsIrrelevant(
726 instruction.result_id()) != pointee_value_is_irrelevant) {
727 continue;
728 }
729 return instruction.result_id();
730 }
731
732 // No such variable was found. Apply a transformation to get one.
733 uint32_t pointee_type_id = fuzzerutil::GetPointeeTypeIdFromPointerType(
734 GetIRContext(), pointer_type_id);
735 auto storage_class = fuzzerutil::GetStorageClassFromPointerType(
736 GetIRContext(), pointer_type_id);
737 uint32_t result_id = GetFuzzerContext()->GetFreshId();
738
739 // A variable with storage class Workgroup shouldn't have an initializer.
740 if (storage_class == SpvStorageClassWorkgroup) {
741 ApplyTransformation(TransformationAddGlobalVariable(
742 result_id, pointer_type_id, SpvStorageClassWorkgroup, 0,
743 pointee_value_is_irrelevant));
744 } else {
745 ApplyTransformation(TransformationAddGlobalVariable(
746 result_id, pointer_type_id, SpvStorageClassPrivate,
747 FindOrCreateZeroConstant(pointee_type_id, pointee_value_is_irrelevant),
748 pointee_value_is_irrelevant));
749 }
750 return result_id;
751 }
752
753 } // namespace fuzz
754 } // namespace spvtools
755