Debian Codegraph @

third_party/spirv-tools/source/fuzz/fuzzer_pass_donate_modules.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_donate_modules.h"
16
17 #include <map>
18 #include <queue>
19 #include <set>
20
21 #include "source/fuzz/call_graph.h"
22 #include "source/fuzz/instruction_message.h"
23 #include "source/fuzz/transformation_add_constant_boolean.h"
24 #include "source/fuzz/transformation_add_constant_composite.h"
25 #include "source/fuzz/transformation_add_constant_null.h"
26 #include "source/fuzz/transformation_add_constant_scalar.h"
27 #include "source/fuzz/transformation_add_function.h"
28 #include "source/fuzz/transformation_add_global_undef.h"
29 #include "source/fuzz/transformation_add_global_variable.h"
30 #include "source/fuzz/transformation_add_spec_constant_op.h"
31 #include "source/fuzz/transformation_add_type_array.h"
32 #include "source/fuzz/transformation_add_type_boolean.h"
33 #include "source/fuzz/transformation_add_type_float.h"
34 #include "source/fuzz/transformation_add_type_function.h"
35 #include "source/fuzz/transformation_add_type_int.h"
36 #include "source/fuzz/transformation_add_type_matrix.h"
37 #include "source/fuzz/transformation_add_type_pointer.h"
38 #include "source/fuzz/transformation_add_type_struct.h"
39 #include "source/fuzz/transformation_add_type_vector.h"
40
41 namespace spvtools {
42 namespace fuzz {
43
44 FuzzerPassDonateModules::FuzzerPassDonateModules(
45 opt::IRContext* ir_context, TransformationContext* transformation_context,
46 FuzzerContext* fuzzer_context,
47 protobufs::TransformationSequence* transformations,
48 const std::vector<fuzzerutil::ModuleSupplier>& donor_suppliers)
49 : FuzzerPass(ir_context, transformation_context, fuzzer_context,
50 transformations),
51 donor_suppliers_(donor_suppliers) {}
52
53 FuzzerPassDonateModules::~FuzzerPassDonateModules() = default;
54
55 void FuzzerPassDonateModules::Apply() {
56 // If there are no donor suppliers, this fuzzer pass is a no-op.
57 if (donor_suppliers_.empty()) {
58 return;
59 }
60
61 // Donate at least one module, and probabilistically decide when to stop
62 // donating modules.
63 do {
64 // Choose a donor supplier at random, and get the module that it provides.
65 std::unique_ptr<opt::IRContext> donor_ir_context = donor_suppliers_.at(
66 GetFuzzerContext()->RandomIndex(donor_suppliers_))();
67 assert(donor_ir_context != nullptr && "Supplying of donor failed");
68 assert(
69 fuzzerutil::IsValid(donor_ir_context.get(),
70 GetTransformationContext()->GetValidatorOptions(),
71 fuzzerutil::kSilentMessageConsumer) &&
72 "The donor module must be valid");
73 // Donate the supplied module.
74 //
75 // Randomly decide whether to make the module livesafe (see
76 // FactFunctionIsLivesafe); doing so allows it to be used for live code
77 // injection but restricts its behaviour to allow this, and means that its
78 // functions cannot be transformed as if they were arbitrary dead code.
79 bool make_livesafe = GetFuzzerContext()->ChoosePercentage(
80 GetFuzzerContext()->ChanceOfMakingDonorLivesafe());
81 DonateSingleModule(donor_ir_context.get(), make_livesafe);
82 } while (GetFuzzerContext()->ChoosePercentage(
83 GetFuzzerContext()->GetChanceOfDonatingAdditionalModule()));
84 }
85
86 void FuzzerPassDonateModules::DonateSingleModule(
87 opt::IRContext* donor_ir_context, bool make_livesafe) {
88 // Check that the donated module has capabilities, supported by the recipient
89 // module.
90 for (const auto& capability_inst : donor_ir_context->capabilities()) {
91 auto capability =
92 static_cast<SpvCapability>(capability_inst.GetSingleWordInOperand(0));
93 if (!GetIRContext()->get_feature_mgr()->HasCapability(capability)) {
94 return;
95 }
96 }
97
98 // The ids used by the donor module may very well clash with ids defined in
99 // the recipient module. Furthermore, some instructions defined in the donor
100 // module will be equivalent to instructions defined in the recipient module,
101 // and it is not always legal to re-declare equivalent instructions. For
102 // example, OpTypeVoid cannot be declared twice.
103 //
104 // To handle this, we maintain a mapping from an id used in the donor module
105 // to the corresponding id that will be used by the donated code when it
106 // appears in the recipient module.
107 //
108 // This mapping is populated in two ways:
109 // (1) by mapping a donor instruction's result id to the id of some equivalent
110 // existing instruction in the recipient (e.g. this has to be done for
111 // OpTypeVoid)
112 // (2) by mapping a donor instruction's result id to a freshly chosen id that
113 // is guaranteed to be different from any id already used by the recipient
114 // (or from any id already chosen to handle a previous donor id)
115 std::map<uint32_t, uint32_t> original_id_to_donated_id;
116
117 HandleExternalInstructionImports(donor_ir_context,
118 &original_id_to_donated_id);
119 HandleTypesAndValues(donor_ir_context, &original_id_to_donated_id);
120 HandleFunctions(donor_ir_context, &original_id_to_donated_id, make_livesafe);
121
122 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3115) Handle some
123 // kinds of decoration.
124 }
125
126 SpvStorageClass FuzzerPassDonateModules::AdaptStorageClass(
127 SpvStorageClass donor_storage_class) {
128 switch (donor_storage_class) {
129 case SpvStorageClassFunction:
130 case SpvStorageClassPrivate:
131 case SpvStorageClassWorkgroup:
132 // We leave these alone
133 return donor_storage_class;
134 case SpvStorageClassInput:
135 case SpvStorageClassOutput:
136 case SpvStorageClassUniform:
137 case SpvStorageClassUniformConstant:
138 case SpvStorageClassPushConstant:
139 case SpvStorageClassImage:
140 case SpvStorageClassStorageBuffer:
141 // We change these to Private
142 return SpvStorageClassPrivate;
143 default:
144 // Handle other cases on demand.
145 assert(false && "Currently unsupported storage class.");
146 return SpvStorageClassMax;
147 }
148 }
149
150 void FuzzerPassDonateModules::HandleExternalInstructionImports(
151 opt::IRContext* donor_ir_context,
152 std::map<uint32_t, uint32_t>* original_id_to_donated_id) {
153 // Consider every external instruction set import in the donor module.
154 for (auto& donor_import : donor_ir_context->module()->ext_inst_imports()) {
155 const auto& donor_import_name_words = donor_import.GetInOperand(0).words;
156 // Look for an identical import in the recipient module.
157 for (auto& existing_import : GetIRContext()->module()->ext_inst_imports()) {
158 const auto& existing_import_name_words =
159 existing_import.GetInOperand(0).words;
160 if (donor_import_name_words == existing_import_name_words) {
161 // A matching import has found. Map the result id for the donor import
162 // to the id of the existing import, so that when donor instructions
163 // rely on the import they will be rewritten to use the existing import.
164 original_id_to_donated_id->insert(
165 {donor_import.result_id(), existing_import.result_id()});
166 break;
167 }
168 }
169 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3116): At present
170 // we do not handle donation of instruction imports, i.e. we do not allow
171 // the donor to import instruction sets that the recipient did not already
172 // import. It might be a good idea to allow this, but it requires some
173 // thought.
174 assert(original_id_to_donated_id->count(donor_import.result_id()) &&
175 "Donation of imports is not yet supported.");
176 }
177 }
178
179 void FuzzerPassDonateModules::HandleTypesAndValues(
180 opt::IRContext* donor_ir_context,
181 std::map<uint32_t, uint32_t>* original_id_to_donated_id) {
182 // Consider every type/global/constant/undef in the module.
183 for (auto& type_or_value : donor_ir_context->module()->types_values()) {
184 HandleTypeOrValue(type_or_value, original_id_to_donated_id);
185 }
186 }
187
188 void FuzzerPassDonateModules::HandleTypeOrValue(
189 const opt::Instruction& type_or_value,
190 std::map<uint32_t, uint32_t>* original_id_to_donated_id) {
191 // The type/value instruction generates a result id, and we need to associate
192 // the donor's result id with a new result id. That new result id will either
193 // be the id of some existing instruction, or a fresh id. This variable
194 // captures it.
195 uint32_t new_result_id;
196
197 // Decide how to handle each kind of instruction on a case-by-case basis.
198 //
199 // Because the donor module is required to be valid, when we encounter a
200 // type comprised of component types (e.g. an aggregate or pointer), we know
201 // that its component types will have been considered previously, and that
202 // |original_id_to_donated_id| will already contain an entry for them.
203 switch (type_or_value.opcode()) {
204 case SpvOpTypeImage:
205 case SpvOpTypeSampledImage:
206 case SpvOpTypeSampler:
207 // We do not donate types and variables that relate to images and
208 // samplers, so we skip these types and subsequently skip anything that
209 // depends on them.
210 return;
211 case SpvOpTypeVoid: {
212 // Void has to exist already in order for us to have an entry point.
213 // Get the existing id of void.
214 opt::analysis::Void void_type;
215 new_result_id = GetIRContext()->get_type_mgr()->GetId(&void_type);
216 assert(new_result_id &&
217 "The module being transformed will always have 'void' type "
218 "declared.");
219 } break;
220 case SpvOpTypeBool: {
221 // Bool cannot be declared multiple times, so use its existing id if
222 // present, or add a declaration of Bool with a fresh id if not.
223 opt::analysis::Bool bool_type;
224 auto bool_type_id = GetIRContext()->get_type_mgr()->GetId(&bool_type);
225 if (bool_type_id) {
226 new_result_id = bool_type_id;
227 } else {
228 new_result_id = GetFuzzerContext()->GetFreshId();
229 ApplyTransformation(TransformationAddTypeBoolean(new_result_id));
230 }
231 } break;
232 case SpvOpTypeInt: {
233 // Int cannot be declared multiple times with the same width and
234 // signedness, so check whether an existing identical Int type is
235 // present and use its id if so. Otherwise add a declaration of the
236 // Int type used by the donor, with a fresh id.
237 const uint32_t width = type_or_value.GetSingleWordInOperand(0);
238 const bool is_signed =
239 static_cast<bool>(type_or_value.GetSingleWordInOperand(1));
240 opt::analysis::Integer int_type(width, is_signed);
241 auto int_type_id = GetIRContext()->get_type_mgr()->GetId(&int_type);
242 if (int_type_id) {
243 new_result_id = int_type_id;
244 } else {
245 new_result_id = GetFuzzerContext()->GetFreshId();
246 ApplyTransformation(
247 TransformationAddTypeInt(new_result_id, width, is_signed));
248 }
249 } break;
250 case SpvOpTypeFloat: {
251 // Similar to SpvOpTypeInt.
252 const uint32_t width = type_or_value.GetSingleWordInOperand(0);
253 opt::analysis::Float float_type(width);
254 auto float_type_id = GetIRContext()->get_type_mgr()->GetId(&float_type);
255 if (float_type_id) {
256 new_result_id = float_type_id;
257 } else {
258 new_result_id = GetFuzzerContext()->GetFreshId();
259 ApplyTransformation(TransformationAddTypeFloat(new_result_id, width));
260 }
261 } break;
262 case SpvOpTypeVector: {
263 // It is not legal to have two Vector type declarations with identical
264 // element types and element counts, so check whether an existing
265 // identical Vector type is present and use its id if so. Otherwise add
266 // a declaration of the Vector type used by the donor, with a fresh id.
267
268 // When considering the vector's component type id, we look up the id
269 // use in the donor to find the id to which this has been remapped.
270 uint32_t component_type_id = original_id_to_donated_id->at(
271 type_or_value.GetSingleWordInOperand(0));
272 auto component_type =
273 GetIRContext()->get_type_mgr()->GetType(component_type_id);
274 assert(component_type && "The base type should be registered.");
275 auto component_count = type_or_value.GetSingleWordInOperand(1);
276 opt::analysis::Vector vector_type(component_type, component_count);
277 auto vector_type_id = GetIRContext()->get_type_mgr()->GetId(&vector_type);
278 if (vector_type_id) {
279 new_result_id = vector_type_id;
280 } else {
281 new_result_id = GetFuzzerContext()->GetFreshId();
282 ApplyTransformation(TransformationAddTypeVector(
283 new_result_id, component_type_id, component_count));
284 }
285 } break;
286 case SpvOpTypeMatrix: {
287 // Similar to SpvOpTypeVector.
288 uint32_t column_type_id = original_id_to_donated_id->at(
289 type_or_value.GetSingleWordInOperand(0));
290 auto column_type =
291 GetIRContext()->get_type_mgr()->GetType(column_type_id);
292 assert(column_type && column_type->AsVector() &&
293 "The column type should be a registered vector type.");
294 auto column_count = type_or_value.GetSingleWordInOperand(1);
295 opt::analysis::Matrix matrix_type(column_type, column_count);
296 auto matrix_type_id = GetIRContext()->get_type_mgr()->GetId(&matrix_type);
297 if (matrix_type_id) {
298 new_result_id = matrix_type_id;
299 } else {
300 new_result_id = GetFuzzerContext()->GetFreshId();
301 ApplyTransformation(TransformationAddTypeMatrix(
302 new_result_id, column_type_id, column_count));
303 }
304
305 } break;
306 case SpvOpTypeArray: {
307 // It is OK to have multiple structurally identical array types, so
308 // we go ahead and add a remapped version of the type declared by the
309 // donor.
310 uint32_t component_type_id = type_or_value.GetSingleWordInOperand(0);
311 if (!original_id_to_donated_id->count(component_type_id)) {
312 // We did not donate the component type of this array type, so we
313 // cannot donate the array type.
314 return;
315 }
316 new_result_id = GetFuzzerContext()->GetFreshId();
317 ApplyTransformation(TransformationAddTypeArray(
318 new_result_id, original_id_to_donated_id->at(component_type_id),
319 original_id_to_donated_id->at(
320 type_or_value.GetSingleWordInOperand(1))));
321 } break;
322 case SpvOpTypeRuntimeArray: {
323 // A runtime array is allowed as the final member of an SSBO. During
324 // donation we turn runtime arrays into fixed-size arrays. For dead
325 // code donations this is OK because the array is never indexed into at
326 // runtime, so it does not matter what its size is. For live-safe code,
327 // all accesses are made in-bounds, so this is also OK.
328 //
329 // The special OpArrayLength instruction, which works on runtime arrays,
330 // is rewritten to yield the fixed length that is used for the array.
331
332 uint32_t component_type_id = type_or_value.GetSingleWordInOperand(0);
333 if (!original_id_to_donated_id->count(component_type_id)) {
334 // We did not donate the component type of this runtime array type, so
335 // we cannot donate it as a fixed-size array.
336 return;
337 }
338 new_result_id = GetFuzzerContext()->GetFreshId();
339 ApplyTransformation(TransformationAddTypeArray(
340 new_result_id, original_id_to_donated_id->at(component_type_id),
341 FindOrCreateIntegerConstant(
342 {GetFuzzerContext()->GetRandomSizeForNewArray()}, 32, false,
343 false)));
344 } break;
345 case SpvOpTypeStruct: {
346 // Similar to SpvOpTypeArray.
347 std::vector<uint32_t> member_type_ids;
348 for (uint32_t i = 0; i < type_or_value.NumInOperands(); i++) {
349 auto component_type_id = type_or_value.GetSingleWordInOperand(i);
350 if (!original_id_to_donated_id->count(component_type_id)) {
351 // We did not donate every member type for this struct type, so we
352 // cannot donate the struct type.
353 return;
354 }
355 member_type_ids.push_back(
356 original_id_to_donated_id->at(component_type_id));
357 }
358 new_result_id = GetFuzzerContext()->GetFreshId();
359 ApplyTransformation(
360 TransformationAddTypeStruct(new_result_id, member_type_ids));
361 } break;
362 case SpvOpTypePointer: {
363 // Similar to SpvOpTypeArray.
364 uint32_t pointee_type_id = type_or_value.GetSingleWordInOperand(1);
365 if (!original_id_to_donated_id->count(pointee_type_id)) {
366 // We did not donate the pointee type for this pointer type, so we
367 // cannot donate the pointer type.
368 return;
369 }
370 new_result_id = GetFuzzerContext()->GetFreshId();
371 ApplyTransformation(TransformationAddTypePointer(
372 new_result_id,
373 AdaptStorageClass(static_cast<SpvStorageClass>(
374 type_or_value.GetSingleWordInOperand(0))),
375 original_id_to_donated_id->at(pointee_type_id)));
376 } break;
377 case SpvOpTypeFunction: {
378 // It is not OK to have multiple function types that use identical ids
379 // for their return and parameter types. We thus go through all
380 // existing function types to look for a match. We do not use the
381 // type manager here because we want to regard two function types that
382 // are structurally identical but that differ with respect to the
383 // actual ids used for pointer types as different.
384 //
385 // Example:
386 //
387 // %1 = OpTypeVoid
388 // %2 = OpTypeInt 32 0
389 // %3 = OpTypePointer Function %2
390 // %4 = OpTypePointer Function %2
391 // %5 = OpTypeFunction %1 %3
392 // %6 = OpTypeFunction %1 %4
393 //
394 // We regard %5 and %6 as distinct function types here, even though
395 // they both have the form "uint32* -> void"
396
397 std::vector<uint32_t> return_and_parameter_types;
398 for (uint32_t i = 0; i < type_or_value.NumInOperands(); i++) {
399 uint32_t return_or_parameter_type =
400 type_or_value.GetSingleWordInOperand(i);
401 if (!original_id_to_donated_id->count(return_or_parameter_type)) {
402 // We did not donate every return/parameter type for this function
403 // type, so we cannot donate the function type.
404 return;
405 }
406 return_and_parameter_types.push_back(
407 original_id_to_donated_id->at(return_or_parameter_type));
408 }
409 uint32_t existing_function_id = fuzzerutil::FindFunctionType(
410 GetIRContext(), return_and_parameter_types);
411 if (existing_function_id) {
412 new_result_id = existing_function_id;
413 } else {
414 // No match was found, so add a remapped version of the function type
415 // to the module, with a fresh id.
416 new_result_id = GetFuzzerContext()->GetFreshId();
417 std::vector<uint32_t> argument_type_ids;
418 for (uint32_t i = 1; i < type_or_value.NumInOperands(); i++) {
419 argument_type_ids.push_back(original_id_to_donated_id->at(
420 type_or_value.GetSingleWordInOperand(i)));
421 }
422 ApplyTransformation(TransformationAddTypeFunction(
423 new_result_id,
424 original_id_to_donated_id->at(
425 type_or_value.GetSingleWordInOperand(0)),
426 argument_type_ids));
427 }
428 } break;
429 case SpvOpSpecConstantOp: {
430 new_result_id = GetFuzzerContext()->GetFreshId();
431 auto type_id = original_id_to_donated_id->at(type_or_value.type_id());
432 auto opcode = static_cast<SpvOp>(type_or_value.GetSingleWordInOperand(0));
433
434 // Make sure we take into account |original_id_to_donated_id| when
435 // computing operands for OpSpecConstantOp.
436 opt::Instruction::OperandList operands;
437 for (uint32_t i = 1; i < type_or_value.NumInOperands(); ++i) {
438 const auto& operand = type_or_value.GetInOperand(i);
439 auto data =
440 operand.type == SPV_OPERAND_TYPE_ID
441 ? opt::Operand::OperandData{original_id_to_donated_id->at(
442 operand.words[0])}
443 : operand.words;
444
445 operands.push_back({operand.type, std::move(data)});
446 }
447
448 ApplyTransformation(TransformationAddSpecConstantOp(
449 new_result_id, type_id, opcode, std::move(operands)));
450 } break;
451 case SpvOpSpecConstantTrue:
452 case SpvOpSpecConstantFalse:
453 case SpvOpConstantTrue:
454 case SpvOpConstantFalse: {
455 // It is OK to have duplicate definitions of True and False, so add
456 // these to the module, using a remapped Bool type.
457 new_result_id = GetFuzzerContext()->GetFreshId();
458 auto value = type_or_value.opcode() == SpvOpConstantTrue ||
459 type_or_value.opcode() == SpvOpSpecConstantTrue;
460 ApplyTransformation(
461 TransformationAddConstantBoolean(new_result_id, value, false));
462 } break;
463 case SpvOpSpecConstant:
464 case SpvOpConstant: {
465 // It is OK to have duplicate constant definitions, so add this to the
466 // module using a remapped result type.
467 new_result_id = GetFuzzerContext()->GetFreshId();
468 std::vector<uint32_t> data_words;
469 type_or_value.ForEachInOperand([&data_words](const uint32_t* in_operand) {
470 data_words.push_back(*in_operand);
471 });
472 ApplyTransformation(TransformationAddConstantScalar(
473 new_result_id, original_id_to_donated_id->at(type_or_value.type_id()),
474 data_words, false));
475 } break;
476 case SpvOpSpecConstantComposite:
477 case SpvOpConstantComposite: {
478 assert(original_id_to_donated_id->count(type_or_value.type_id()) &&
479 "Composite types for which it is possible to create a constant "
480 "should have been donated.");
481
482 // It is OK to have duplicate constant composite definitions, so add
483 // this to the module using remapped versions of all consituent ids and
484 // the result type.
485 new_result_id = GetFuzzerContext()->GetFreshId();
486 std::vector<uint32_t> constituent_ids;
487 type_or_value.ForEachInId([&constituent_ids, &original_id_to_donated_id](
488 const uint32_t* constituent_id) {
489 assert(original_id_to_donated_id->count(*constituent_id) &&
490 "The constants used to construct this composite should "
491 "have been donated.");
492 constituent_ids.push_back(
493 original_id_to_donated_id->at(*constituent_id));
494 });
495 ApplyTransformation(TransformationAddConstantComposite(
496 new_result_id, original_id_to_donated_id->at(type_or_value.type_id()),
497 constituent_ids, false));
498 } break;
499 case SpvOpConstantNull: {
500 if (!original_id_to_donated_id->count(type_or_value.type_id())) {
501 // We did not donate the type associated with this null constant, so
502 // we cannot donate the null constant.
503 return;
504 }
505
506 // It is fine to have multiple OpConstantNull instructions of the same
507 // type, so we just add this to the recipient module.
508 new_result_id = GetFuzzerContext()->GetFreshId();
509 ApplyTransformation(TransformationAddConstantNull(
510 new_result_id,
511 original_id_to_donated_id->at(type_or_value.type_id())));
512 } break;
513 case SpvOpVariable: {
514 if (!original_id_to_donated_id->count(type_or_value.type_id())) {
515 // We did not donate the pointer type associated with this variable,
516 // so we cannot donate the variable.
517 return;
518 }
519
520 // This is a global variable that could have one of various storage
521 // classes. However, we change all global variable pointer storage
522 // classes (such as Uniform, Input and Output) to private when donating
523 // pointer types, with the exception of the Workgroup storage class.
524 //
525 // Thus this variable's pointer type is guaranteed to have storage class
526 // Private or Workgroup.
527 //
528 // We add a global variable with either Private or Workgroup storage
529 // class, using remapped versions of the result type and initializer ids
530 // for the global variable in the donor.
531 //
532 // We regard the added variable as having an irrelevant value. This
533 // means that future passes can add stores to the variable in any
534 // way they wish, and pass them as pointer parameters to functions
535 // without worrying about whether their data might get modified.
536 new_result_id = GetFuzzerContext()->GetFreshId();
537 uint32_t remapped_pointer_type =
538 original_id_to_donated_id->at(type_or_value.type_id());
539 uint32_t initializer_id;
540 SpvStorageClass storage_class =
541 static_cast<SpvStorageClass>(type_or_value.GetSingleWordInOperand(
542 0)) == SpvStorageClassWorkgroup
543 ? SpvStorageClassWorkgroup
544 : SpvStorageClassPrivate;
545 if (type_or_value.NumInOperands() == 1) {
546 // The variable did not have an initializer. Initialize it to zero
547 // if it has Private storage class (to limit problems associated with
548 // uninitialized data), and leave it uninitialized if it has Workgroup
549 // storage class (as Workgroup variables cannot have initializers).
550
551 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3275): we
552 // could initialize Workgroup variables at the start of an entry
553 // point, and should do so if their uninitialized nature proves
554 // problematic.
555 initializer_id = storage_class == SpvStorageClassWorkgroup
556 ? 0
557 : FindOrCreateZeroConstant(
558 fuzzerutil::GetPointeeTypeIdFromPointerType(
559 GetIRContext(), remapped_pointer_type),
560 false);
561 } else {
562 // The variable already had an initializer; use its remapped id.
563 initializer_id = original_id_to_donated_id->at(
564 type_or_value.GetSingleWordInOperand(1));
565 }
566 ApplyTransformation(
567 TransformationAddGlobalVariable(new_result_id, remapped_pointer_type,
568 storage_class, initializer_id, true));
569 } break;
570 case SpvOpUndef: {
571 if (!original_id_to_donated_id->count(type_or_value.type_id())) {
572 // We did not donate the type associated with this undef, so we cannot
573 // donate the undef.
574 return;
575 }
576
577 // It is fine to have multiple Undef instructions of the same type, so
578 // we just add this to the recipient module.
579 new_result_id = GetFuzzerContext()->GetFreshId();
580 ApplyTransformation(TransformationAddGlobalUndef(
581 new_result_id,
582 original_id_to_donated_id->at(type_or_value.type_id())));
583 } break;
584 default: {
585 assert(0 && "Unknown type/value.");
586 new_result_id = 0;
587 } break;
588 }
589
590 // Update the id mapping to associate the instruction's result id with its
591 // corresponding id in the recipient.
592 original_id_to_donated_id->insert({type_or_value.result_id(), new_result_id});
593 }
594
595 void FuzzerPassDonateModules::HandleFunctions(
596 opt::IRContext* donor_ir_context,
597 std::map<uint32_t, uint32_t>* original_id_to_donated_id,
598 bool make_livesafe) {
599 // Get the ids of functions in the donor module, topologically sorted
600 // according to the donor's call graph.
601 auto topological_order =
602 CallGraph(donor_ir_context).GetFunctionsInTopologicalOrder();
603
604 // Donate the functions in reverse topological order. This ensures that a
605 // function gets donated before any function that depends on it. This allows
606 // donation of the functions to be separated into a number of transformations,
607 // each adding one function, such that every prefix of transformations leaves
608 // the module valid.
609 for (auto function_id = topological_order.rbegin();
610 function_id != topological_order.rend(); ++function_id) {
611 // Find the function to be donated.
612 opt::Function* function_to_donate = nullptr;
613 for (auto& function : *donor_ir_context->module()) {
614 if (function.result_id() == *function_id) {
615 function_to_donate = &function;
616 break;
617 }
618 }
619 assert(function_to_donate && "Function to be donated was not found.");
620
621 if (!original_id_to_donated_id->count(
622 function_to_donate->DefInst().GetSingleWordInOperand(1))) {
623 // We were not able to donate this function's type, so we cannot donate
624 // the function.
625 continue;
626 }
627
628 // We will collect up protobuf messages representing the donor function's
629 // instructions here, and use them to create an AddFunction transformation.
630 std::vector<protobufs::Instruction> donated_instructions;
631
632 // This set tracks the ids of those instructions for which donation was
633 // completely skipped: neither the instruction nor a substitute for it was
634 // donated.
635 std::set<uint32_t> skipped_instructions;
636
637 // Consider every instruction of the donor function.
638 function_to_donate->ForEachInst(
639 [this, &donated_instructions, donor_ir_context,
640 &original_id_to_donated_id,
641 &skipped_instructions](const opt::Instruction* instruction) {
642 if (instruction->opcode() == SpvOpArrayLength) {
643 // We treat OpArrayLength specially.
644 HandleOpArrayLength(*instruction, original_id_to_donated_id,
645 &donated_instructions);
646 } else if (!CanDonateInstruction(donor_ir_context, *instruction,
647 *original_id_to_donated_id,
648 skipped_instructions)) {
649 // This is an instruction that we cannot directly donate.
650 HandleDifficultInstruction(*instruction, original_id_to_donated_id,
651 &donated_instructions,
652 &skipped_instructions);
653 } else {
654 PrepareInstructionForDonation(*instruction, donor_ir_context,
655 original_id_to_donated_id,
656 &donated_instructions);
657 }
658 });
659
660 // If |make_livesafe| is true, try to add the function in a livesafe manner.
661 // Otherwise (if |make_lifesafe| is false or an attempt to make the function
662 // livesafe has failed), add the function in a non-livesafe manner.
663 if (!make_livesafe ||
664 !MaybeAddLivesafeFunction(*function_to_donate, donor_ir_context,
665 *original_id_to_donated_id,
666 donated_instructions)) {
667 ApplyTransformation(TransformationAddFunction(donated_instructions));
668 }
669 }
670 }
671
672 bool FuzzerPassDonateModules::CanDonateInstruction(
673 opt::IRContext* donor_ir_context, const opt::Instruction& instruction,
674 const std::map<uint32_t, uint32_t>& original_id_to_donated_id,
675 const std::set<uint32_t>& skipped_instructions) const {
676 if (instruction.type_id() &&
677 !original_id_to_donated_id.count(instruction.type_id())) {
678 // We could not donate the result type of this instruction, so we cannot
679 // donate the instruction.
680 return false;
681 }
682
683 // Now consider instructions we specifically want to skip because we do not
684 // yet support them.
685 switch (instruction.opcode()) {
686 case SpvOpAtomicLoad:
687 case SpvOpAtomicStore:
688 case SpvOpAtomicExchange:
689 case SpvOpAtomicCompareExchange:
690 case SpvOpAtomicCompareExchangeWeak:
691 case SpvOpAtomicIIncrement:
692 case SpvOpAtomicIDecrement:
693 case SpvOpAtomicIAdd:
694 case SpvOpAtomicISub:
695 case SpvOpAtomicSMin:
696 case SpvOpAtomicUMin:
697 case SpvOpAtomicSMax:
698 case SpvOpAtomicUMax:
699 case SpvOpAtomicAnd:
700 case SpvOpAtomicOr:
701 case SpvOpAtomicXor:
702 // We conservatively ignore all atomic instructions at present.
703 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3276): Consider
704 // being less conservative here.
705 case SpvOpImageSampleImplicitLod:
706 case SpvOpImageSampleExplicitLod:
707 case SpvOpImageSampleDrefImplicitLod:
708 case SpvOpImageSampleDrefExplicitLod:
709 case SpvOpImageSampleProjImplicitLod:
710 case SpvOpImageSampleProjExplicitLod:
711 case SpvOpImageSampleProjDrefImplicitLod:
712 case SpvOpImageSampleProjDrefExplicitLod:
713 case SpvOpImageFetch:
714 case SpvOpImageGather:
715 case SpvOpImageDrefGather:
716 case SpvOpImageRead:
717 case SpvOpImageWrite:
718 case SpvOpImageSparseSampleImplicitLod:
719 case SpvOpImageSparseSampleExplicitLod:
720 case SpvOpImageSparseSampleDrefImplicitLod:
721 case SpvOpImageSparseSampleDrefExplicitLod:
722 case SpvOpImageSparseSampleProjImplicitLod:
723 case SpvOpImageSparseSampleProjExplicitLod:
724 case SpvOpImageSparseSampleProjDrefImplicitLod:
725 case SpvOpImageSparseSampleProjDrefExplicitLod:
726 case SpvOpImageSparseFetch:
727 case SpvOpImageSparseGather:
728 case SpvOpImageSparseDrefGather:
729 case SpvOpImageSparseRead:
730 case SpvOpImageSampleFootprintNV:
731 case SpvOpImage:
732 case SpvOpImageQueryFormat:
733 case SpvOpImageQueryLevels:
734 case SpvOpImageQueryLod:
735 case SpvOpImageQueryOrder:
736 case SpvOpImageQuerySamples:
737 case SpvOpImageQuerySize:
738 case SpvOpImageQuerySizeLod:
739 case SpvOpSampledImage:
740 // We ignore all instructions related to accessing images, since we do not
741 // donate images.
742 return false;
743 case SpvOpLoad:
744 switch (donor_ir_context->get_def_use_mgr()
745 ->GetDef(instruction.type_id())
746 ->opcode()) {
747 case SpvOpTypeImage:
748 case SpvOpTypeSampledImage:
749 case SpvOpTypeSampler:
750 // Again, we ignore instructions that relate to accessing images.
751 return false;
752 default:
753 break;
754 }
755 default:
756 break;
757 }
758
759 // Examine each id input operand to the instruction. If it turns out that we
760 // have skipped any of these operands then we cannot donate the instruction.
761 bool result = true;
762 instruction.WhileEachInId(
763 [donor_ir_context, &original_id_to_donated_id, &result,
764 &skipped_instructions](const uint32_t* in_id) -> bool {
765 if (!original_id_to_donated_id.count(*in_id)) {
766 // We do not have a mapped result id for this id operand. That either
767 // means that it is a forward reference (which is OK), that we skipped
768 // the instruction that generated it (which is not OK), or that it is
769 // the id of a function or global value that we did not donate (which
770 // is not OK). We check for the latter two cases.
771 if (skipped_instructions.count(*in_id) ||
772 // A function or global value does not have an associated basic
773 // block.
774 !donor_ir_context->get_instr_block(*in_id)) {
775 result = false;
776 return false;
777 }
778 }
779 return true;
780 });
781 return result;
782 }
783
784 bool FuzzerPassDonateModules::IsBasicType(
785 const opt::Instruction& instruction) const {
786 switch (instruction.opcode()) {
787 case SpvOpTypeArray:
788 case SpvOpTypeBool:
789 case SpvOpTypeFloat:
790 case SpvOpTypeInt:
791 case SpvOpTypeMatrix:
792 case SpvOpTypeStruct:
793 case SpvOpTypeVector:
794 return true;
795 default:
796 return false;
797 }
798 }
799
800 void FuzzerPassDonateModules::HandleOpArrayLength(
801 const opt::Instruction& instruction,
802 std::map<uint32_t, uint32_t>* original_id_to_donated_id,
803 std::vector<protobufs::Instruction>* donated_instructions) const {
804 assert(instruction.opcode() == SpvOpArrayLength &&
805 "Precondition: instruction must be OpArrayLength.");
806 uint32_t donated_variable_id =
807 original_id_to_donated_id->at(instruction.GetSingleWordInOperand(0));
808 auto donated_variable_instruction =
809 GetIRContext()->get_def_use_mgr()->GetDef(donated_variable_id);
810 auto pointer_to_struct_instruction =
811 GetIRContext()->get_def_use_mgr()->GetDef(
812 donated_variable_instruction->type_id());
813 assert(pointer_to_struct_instruction->opcode() == SpvOpTypePointer &&
814 "Type of variable must be pointer.");
815 auto donated_struct_type_instruction =
816 GetIRContext()->get_def_use_mgr()->GetDef(
817 pointer_to_struct_instruction->GetSingleWordInOperand(1));
818 assert(donated_struct_type_instruction->opcode() == SpvOpTypeStruct &&
819 "Pointee type of pointer used by OpArrayLength must be struct.");
820 assert(donated_struct_type_instruction->NumInOperands() ==
821 instruction.GetSingleWordInOperand(1) + 1 &&
822 "OpArrayLength must refer to the final member of the given "
823 "struct.");
824 uint32_t fixed_size_array_type_id =
825 donated_struct_type_instruction->GetSingleWordInOperand(
826 donated_struct_type_instruction->NumInOperands() - 1);
827 auto fixed_size_array_type_instruction =
828 GetIRContext()->get_def_use_mgr()->GetDef(fixed_size_array_type_id);
829 assert(fixed_size_array_type_instruction->opcode() == SpvOpTypeArray &&
830 "The donated array type must be fixed-size.");
831 auto array_size_id =
832 fixed_size_array_type_instruction->GetSingleWordInOperand(1);
833
834 if (instruction.result_id() &&
835 !original_id_to_donated_id->count(instruction.result_id())) {
836 original_id_to_donated_id->insert(
837 {instruction.result_id(), GetFuzzerContext()->GetFreshId()});
838 }
839
840 donated_instructions->push_back(MakeInstructionMessage(
841 SpvOpCopyObject, original_id_to_donated_id->at(instruction.type_id()),
842 original_id_to_donated_id->at(instruction.result_id()),
843 opt::Instruction::OperandList({{SPV_OPERAND_TYPE_ID, {array_size_id}}})));
844 }
845
846 void FuzzerPassDonateModules::HandleDifficultInstruction(
847 const opt::Instruction& instruction,
848 std::map<uint32_t, uint32_t>* original_id_to_donated_id,
849 std::vector<protobufs::Instruction>* donated_instructions,
850 std::set<uint32_t>* skipped_instructions) {
851 if (!instruction.result_id()) {
852 // It does not generate a result id, so it can be ignored.
853 return;
854 }
855 if (!original_id_to_donated_id->count(instruction.type_id())) {
856 // We cannot handle this instruction's result type, so we need to skip it
857 // all together.
858 skipped_instructions->insert(instruction.result_id());
859 return;
860 }
861
862 // We now attempt to replace the instruction with an OpCopyObject.
863 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3278): We could do
864 // something more refined here - we could check which operands to the
865 // instruction could not be donated and replace those operands with
866 // references to other ids (such as constants), so that we still get an
867 // instruction with the opcode and easy-to-handle operands of the donor
868 // instruction.
869 auto remapped_type_id = original_id_to_donated_id->at(instruction.type_id());
870 if (!IsBasicType(
871 *GetIRContext()->get_def_use_mgr()->GetDef(remapped_type_id))) {
872 // The instruction has a non-basic result type, so we cannot replace it with
873 // an object copy of a constant. We thus skip it completely.
874 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3279): We could
875 // instead look for an available id of the right type and generate an
876 // OpCopyObject of that id.
877 skipped_instructions->insert(instruction.result_id());
878 return;
879 }
880
881 // We are going to add an OpCopyObject instruction. Add a mapping for the
882 // result id of the original instruction if does not already exist (it may
883 // exist in the case that it has been forward-referenced).
884 if (!original_id_to_donated_id->count(instruction.result_id())) {
885 original_id_to_donated_id->insert(
886 {instruction.result_id(), GetFuzzerContext()->GetFreshId()});
887 }
888
889 // We find or add a zero constant to the receiving module for the type in
890 // question, and add an OpCopyObject instruction that copies this zero.
891 //
892 // We mark the constant as irrelevant so that we can replace it with a
893 // more interesting value later.
894 auto zero_constant = FindOrCreateZeroConstant(remapped_type_id, true);
895 donated_instructions->push_back(MakeInstructionMessage(
896 SpvOpCopyObject, remapped_type_id,
897 original_id_to_donated_id->at(instruction.result_id()),
898 opt::Instruction::OperandList({{SPV_OPERAND_TYPE_ID, {zero_constant}}})));
899 }
900
901 void FuzzerPassDonateModules::PrepareInstructionForDonation(
902 const opt::Instruction& instruction, opt::IRContext* donor_ir_context,
903 std::map<uint32_t, uint32_t>* original_id_to_donated_id,
904 std::vector<protobufs::Instruction>* donated_instructions) {
905 // Get the instruction's input operands into donation-ready form,
906 // remapping any id uses in the process.
907 opt::Instruction::OperandList input_operands;
908
909 // Consider each input operand in turn.
910 for (uint32_t in_operand_index = 0;
911 in_operand_index < instruction.NumInOperands(); in_operand_index++) {
912 std::vector<uint32_t> operand_data;
913 const opt::Operand& in_operand = instruction.GetInOperand(in_operand_index);
914 // Check whether this operand is an id.
915 if (spvIsIdType(in_operand.type)) {
916 // This is an id operand - it consists of a single word of data,
917 // which needs to be remapped so that it is replaced with the
918 // donated form of the id.
919 auto operand_id = in_operand.words[0];
920 if (!original_id_to_donated_id->count(operand_id)) {
921 // This is a forward reference. We will choose a corresponding
922 // donor id for the referenced id and update the mapping to
923 // reflect it.
924
925 // Keep release compilers happy because |donor_ir_context| is only used
926 // in this assertion.
927 (void)(donor_ir_context);
928 assert((donor_ir_context->get_def_use_mgr()
929 ->GetDef(operand_id)
930 ->opcode() == SpvOpLabel ||
931 instruction.opcode() == SpvOpPhi) &&
932 "Unsupported forward reference.");
933 original_id_to_donated_id->insert(
934 {operand_id, GetFuzzerContext()->GetFreshId()});
935 }
936 operand_data.push_back(original_id_to_donated_id->at(operand_id));
937 } else {
938 // For non-id operands, we just add each of the data words.
939 for (auto word : in_operand.words) {
940 operand_data.push_back(word);
941 }
942 }
943 input_operands.push_back({in_operand.type, operand_data});
944 }
945
946 if (instruction.opcode() == SpvOpVariable &&
947 instruction.NumInOperands() == 1) {
948 // This is an uninitialized local variable. Initialize it to zero.
949 input_operands.push_back(
950 {SPV_OPERAND_TYPE_ID,
951 {FindOrCreateZeroConstant(
952 fuzzerutil::GetPointeeTypeIdFromPointerType(
953 GetIRContext(),
954 original_id_to_donated_id->at(instruction.type_id())),
955 false)}});
956 }
957
958 if (instruction.result_id() &&
959 !original_id_to_donated_id->count(instruction.result_id())) {
960 original_id_to_donated_id->insert(
961 {instruction.result_id(), GetFuzzerContext()->GetFreshId()});
962 }
963
964 // Remap the result type and result id (if present) of the
965 // instruction, and turn it into a protobuf message.
966 donated_instructions->push_back(MakeInstructionMessage(
967 instruction.opcode(),
968 instruction.type_id()
969 ? original_id_to_donated_id->at(instruction.type_id())
970 : 0,
971 instruction.result_id()
972 ? original_id_to_donated_id->at(instruction.result_id())
973 : 0,
974 input_operands));
975 }
976
977 bool FuzzerPassDonateModules::CreateLoopLimiterInfo(
978 opt::IRContext* donor_ir_context, const opt::BasicBlock& loop_header,
979 const std::map<uint32_t, uint32_t>& original_id_to_donated_id,
980 protobufs::LoopLimiterInfo* out) {
981 assert(loop_header.IsLoopHeader() && "|loop_header| is not a loop header");
982
983 // Grab the loop header's id, mapped to its donated value.
984 out->set_loop_header_id(original_id_to_donated_id.at(loop_header.id()));
985
986 // Get fresh ids that will be used to load the loop limiter, increment
987 // it, compare it with the loop limit, and an id for a new block that
988 // will contain the loop's original terminator.
989 out->set_load_id(GetFuzzerContext()->GetFreshId());
990 out->set_increment_id(GetFuzzerContext()->GetFreshId());
991 out->set_compare_id(GetFuzzerContext()->GetFreshId());
992 out->set_logical_op_id(GetFuzzerContext()->GetFreshId());
993
994 // We are creating a branch from the back-edge block to the merge block. Thus,
995 // if merge block has any OpPhi instructions, we might need to adjust
996 // them.
997
998 // Note that the loop might have an unreachable back-edge block. This means
999 // that the loop can't iterate, so we don't need to adjust anything.
1000 const auto back_edge_block_id = TransformationAddFunction::GetBackEdgeBlockId(
1001 donor_ir_context, loop_header.id());
1002 if (!back_edge_block_id) {
1003 return true;
1004 }
1005
1006 auto* back_edge_block = donor_ir_context->cfg()->block(back_edge_block_id);
1007 assert(back_edge_block && "|back_edge_block_id| is invalid");
1008
1009 const auto* merge_block =
1010 donor_ir_context->cfg()->block(loop_header.MergeBlockId());
1011 assert(merge_block && "Loop header has invalid merge block id");
1012
1013 // We don't need to adjust anything if there is already a branch from
1014 // the back-edge block to the merge block.
1015 if (back_edge_block->IsSuccessor(merge_block)) {
1016 return true;
1017 }
1018
1019 // Adjust OpPhi instructions in the |merge_block|.
1020 for (const auto& inst : *merge_block) {
1021 if (inst.opcode() != SpvOpPhi) {
1022 break;
1023 }
1024
1025 // There is no simple way to ensure that a chosen operand for the OpPhi
1026 // instruction will never cause any problems (e.g. if we choose an
1027 // integer id, it might have a zero value when we branch from the back
1028 // edge block. This might cause a division by 0 later in the function.).
1029 // Thus, we ignore possible problems and proceed as follows:
1030 // - if any of the existing OpPhi operands dominates the back-edge
1031 // block - use it
1032 // - if OpPhi has a basic type (see IsBasicType method) - create
1033 // a zero constant
1034 // - otherwise, we can't add a livesafe function.
1035 uint32_t suitable_operand_id = 0;
1036 for (uint32_t i = 0; i < inst.NumInOperands(); i += 2) {
1037 auto dependency_inst_id = inst.GetSingleWordInOperand(i);
1038
1039 if (fuzzerutil::IdIsAvailableBeforeInstruction(
1040 donor_ir_context, back_edge_block->terminator(),
1041 dependency_inst_id)) {
1042 suitable_operand_id = original_id_to_donated_id.at(dependency_inst_id);
1043 break;
1044 }
1045 }
1046
1047 if (suitable_operand_id == 0 &&
1048 IsBasicType(
1049 *donor_ir_context->get_def_use_mgr()->GetDef(inst.type_id()))) {
1050 // We mark this constant as irrelevant so that we can replace it
1051 // with more interesting value later.
1052 suitable_operand_id = FindOrCreateZeroConstant(
1053 original_id_to_donated_id.at(inst.type_id()), true);
1054 }
1055
1056 if (suitable_operand_id == 0) {
1057 return false;
1058 }
1059
1060 out->add_phi_id(suitable_operand_id);
1061 }
1062
1063 return true;
1064 }
1065
1066 bool FuzzerPassDonateModules::MaybeAddLivesafeFunction(
1067 const opt::Function& function_to_donate, opt::IRContext* donor_ir_context,
1068 const std::map<uint32_t, uint32_t>& original_id_to_donated_id,
1069 const std::vector<protobufs::Instruction>& donated_instructions) {
1070 // Various types and constants must be in place for a function to be made
1071 // live-safe. Add them if not already present.
1072 FindOrCreateBoolType(); // Needed for comparisons
1073 FindOrCreatePointerToIntegerType(
1074 32, false, SpvStorageClassFunction); // Needed for adding loop limiters
1075 FindOrCreateIntegerConstant({0}, 32, false,
1076 false); // Needed for initializing loop limiters
1077 FindOrCreateIntegerConstant({1}, 32, false,
1078 false); // Needed for incrementing loop limiters
1079
1080 // Get a fresh id for the variable that will be used as a loop limiter.
1081 const uint32_t loop_limiter_variable_id = GetFuzzerContext()->GetFreshId();
1082 // Choose a random loop limit, and add the required constant to the
1083 // module if not already there.
1084 const uint32_t loop_limit = FindOrCreateIntegerConstant(
1085 {GetFuzzerContext()->GetRandomLoopLimit()}, 32, false, false);
1086
1087 // Consider every loop header in the function to donate, and create a
1088 // structure capturing the ids to be used for manipulating the loop
1089 // limiter each time the loop is iterated.
1090 std::vector<protobufs::LoopLimiterInfo> loop_limiters;
1091 for (auto& block : function_to_donate) {
1092 if (block.IsLoopHeader()) {
1093 protobufs::LoopLimiterInfo loop_limiter;
1094
1095 if (!CreateLoopLimiterInfo(donor_ir_context, block,
1096 original_id_to_donated_id, &loop_limiter)) {
1097 return false;
1098 }
1099
1100 loop_limiters.emplace_back(std::move(loop_limiter));
1101 }
1102 }
1103
1104 // Consider every access chain in the function to donate, and create a
1105 // structure containing the ids necessary to clamp the access chain
1106 // indices to be in-bounds.
1107 std::vector<protobufs::AccessChainClampingInfo> access_chain_clamping_info;
1108 for (auto& block : function_to_donate) {
1109 for (auto& inst : block) {
1110 switch (inst.opcode()) {
1111 case SpvOpAccessChain:
1112 case SpvOpInBoundsAccessChain: {
1113 protobufs::AccessChainClampingInfo clamping_info;
1114 clamping_info.set_access_chain_id(
1115 original_id_to_donated_id.at(inst.result_id()));
1116
1117 auto base_object = donor_ir_context->get_def_use_mgr()->GetDef(
1118 inst.GetSingleWordInOperand(0));
1119 assert(base_object && "The base object must exist.");
1120 auto pointer_type = donor_ir_context->get_def_use_mgr()->GetDef(
1121 base_object->type_id());
1122 assert(pointer_type && pointer_type->opcode() == SpvOpTypePointer &&
1123 "The base object must have pointer type.");
1124
1125 auto should_be_composite_type =
1126 donor_ir_context->get_def_use_mgr()->GetDef(
1127 pointer_type->GetSingleWordInOperand(1));
1128
1129 // Walk the access chain, creating fresh ids to facilitate
1130 // clamping each index. For simplicity we do this for every
1131 // index, even though constant indices will not end up being
1132 // clamped.
1133 for (uint32_t index = 1; index < inst.NumInOperands(); index++) {
1134 auto compare_and_select_ids =
1135 clamping_info.add_compare_and_select_ids();
1136 compare_and_select_ids->set_first(GetFuzzerContext()->GetFreshId());
1137 compare_and_select_ids->set_second(
1138 GetFuzzerContext()->GetFreshId());
1139
1140 // Get the bound for the component being indexed into.
1141 uint32_t bound;
1142 if (should_be_composite_type->opcode() == SpvOpTypeRuntimeArray) {
1143 // The donor is indexing into a runtime array. We do not
1144 // donate runtime arrays. Instead, we donate a corresponding
1145 // fixed-size array for every runtime array. We should thus
1146 // find that donor composite type's result id maps to a fixed-
1147 // size array.
1148 auto fixed_size_array_type =
1149 GetIRContext()->get_def_use_mgr()->GetDef(
1150 original_id_to_donated_id.at(
1151 should_be_composite_type->result_id()));
1152 assert(fixed_size_array_type->opcode() == SpvOpTypeArray &&
1153 "A runtime array type in the donor should have been "
1154 "replaced by a fixed-sized array in the recipient.");
1155 // The size of this fixed-size array is a suitable bound.
1156 bound = fuzzerutil::GetBoundForCompositeIndex(
1157 *fixed_size_array_type, GetIRContext());
1158 } else {
1159 bound = fuzzerutil::GetBoundForCompositeIndex(
1160 *should_be_composite_type, donor_ir_context);
1161 }
1162 const uint32_t index_id = inst.GetSingleWordInOperand(index);
1163 auto index_inst =
1164 donor_ir_context->get_def_use_mgr()->GetDef(index_id);
1165 auto index_type_inst = donor_ir_context->get_def_use_mgr()->GetDef(
1166 index_inst->type_id());
1167 assert(index_type_inst->opcode() == SpvOpTypeInt);
1168 opt::analysis::Integer* index_int_type =
1169 donor_ir_context->get_type_mgr()
1170 ->GetType(index_type_inst->result_id())
1171 ->AsInteger();
1172 if (index_inst->opcode() != SpvOpConstant) {
1173 // We will have to clamp this index, so we need a constant
1174 // whose value is one less than the bound, to compare
1175 // against and to use as the clamped value.
1176 FindOrCreateIntegerConstant({bound - 1}, 32,
1177 index_int_type->IsSigned(), false);
1178 }
1179 should_be_composite_type =
1180 TransformationAddFunction::FollowCompositeIndex(
1181 donor_ir_context, *should_be_composite_type, index_id);
1182 }
1183 access_chain_clamping_info.push_back(clamping_info);
1184 break;
1185 }
1186 default:
1187 break;
1188 }
1189 }
1190 }
1191
1192 // If |function_to_donate| has non-void return type and contains an
1193 // OpKill/OpUnreachable instruction, then a value is needed in order to turn
1194 // these into instructions of the form OpReturnValue %value_id.
1195 uint32_t kill_unreachable_return_value_id = 0;
1196 auto function_return_type_inst =
1197 donor_ir_context->get_def_use_mgr()->GetDef(function_to_donate.type_id());
1198 if (function_return_type_inst->opcode() != SpvOpTypeVoid &&
1199 fuzzerutil::FunctionContainsOpKillOrUnreachable(function_to_donate)) {
1200 kill_unreachable_return_value_id = FindOrCreateZeroConstant(
1201 original_id_to_donated_id.at(function_return_type_inst->result_id()),
1202 false);
1203 }
1204
1205 // Add the function in a livesafe manner.
1206 ApplyTransformation(TransformationAddFunction(
1207 donated_instructions, loop_limiter_variable_id, loop_limit, loop_limiters,
1208 kill_unreachable_return_value_id, access_chain_clamping_info));
1209 return true;
1210 }
1211
1212 } // namespace fuzz
1213 } // namespace spvtools