Debian Codegraph @

third_party/spirv-tools/source/fuzz/transformation_add_function.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/transformation_add_function.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/instruction_message.h"
19
20 namespace spvtools {
21 namespace fuzz {
22
23 TransformationAddFunction::TransformationAddFunction(
24 const spvtools::fuzz::protobufs::TransformationAddFunction& message)
25 : message_(message) {}
26
27 TransformationAddFunction::TransformationAddFunction(
28 const std::vector<protobufs::Instruction>& instructions) {
29 for (auto& instruction : instructions) {
30 *message_.add_instruction() = instruction;
31 }
32 message_.set_is_livesafe(false);
33 }
34
35 TransformationAddFunction::TransformationAddFunction(
36 const std::vector<protobufs::Instruction>& instructions,
37 uint32_t loop_limiter_variable_id, uint32_t loop_limit_constant_id,
38 const std::vector<protobufs::LoopLimiterInfo>& loop_limiters,
39 uint32_t kill_unreachable_return_value_id,
40 const std::vector<protobufs::AccessChainClampingInfo>&
41 access_chain_clampers) {
42 for (auto& instruction : instructions) {
43 *message_.add_instruction() = instruction;
44 }
45 message_.set_is_livesafe(true);
46 message_.set_loop_limiter_variable_id(loop_limiter_variable_id);
47 message_.set_loop_limit_constant_id(loop_limit_constant_id);
48 for (auto& loop_limiter : loop_limiters) {
49 *message_.add_loop_limiter_info() = loop_limiter;
50 }
51 message_.set_kill_unreachable_return_value_id(
52 kill_unreachable_return_value_id);
53 for (auto& access_clamper : access_chain_clampers) {
54 *message_.add_access_chain_clamping_info() = access_clamper;
55 }
56 }
57
58 bool TransformationAddFunction::IsApplicable(
59 opt::IRContext* ir_context,
60 const TransformationContext& transformation_context) const {
61 // This transformation may use a lot of ids, all of which need to be fresh
62 // and distinct. This set tracks them.
63 std::set<uint32_t> ids_used_by_this_transformation;
64
65 // Ensure that all result ids in the new function are fresh and distinct.
66 for (auto& instruction : message_.instruction()) {
67 if (instruction.result_id()) {
68 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
69 instruction.result_id(), ir_context,
70 &ids_used_by_this_transformation)) {
71 return false;
72 }
73 }
74 }
75
76 if (message_.is_livesafe()) {
77 // Ensure that all ids provided for making the function livesafe are fresh
78 // and distinct.
79 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
80 message_.loop_limiter_variable_id(), ir_context,
81 &ids_used_by_this_transformation)) {
82 return false;
83 }
84 for (auto& loop_limiter_info : message_.loop_limiter_info()) {
85 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
86 loop_limiter_info.load_id(), ir_context,
87 &ids_used_by_this_transformation)) {
88 return false;
89 }
90 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
91 loop_limiter_info.increment_id(), ir_context,
92 &ids_used_by_this_transformation)) {
93 return false;
94 }
95 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
96 loop_limiter_info.compare_id(), ir_context,
97 &ids_used_by_this_transformation)) {
98 return false;
99 }
100 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
101 loop_limiter_info.logical_op_id(), ir_context,
102 &ids_used_by_this_transformation)) {
103 return false;
104 }
105 }
106 for (auto& access_chain_clamping_info :
107 message_.access_chain_clamping_info()) {
108 for (auto& pair : access_chain_clamping_info.compare_and_select_ids()) {
109 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
110 pair.first(), ir_context, &ids_used_by_this_transformation)) {
111 return false;
112 }
113 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
114 pair.second(), ir_context, &ids_used_by_this_transformation)) {
115 return false;
116 }
117 }
118 }
119 }
120
121 // Because checking all the conditions for a function to be valid is a big
122 // job that the SPIR-V validator can already do, a "try it and see" approach
123 // is taken here.
124
125 // We first clone the current module, so that we can try adding the new
126 // function without risking wrecking |ir_context|.
127 auto cloned_module = fuzzerutil::CloneIRContext(ir_context);
128
129 // We try to add a function to the cloned module, which may fail if
130 // |message_.instruction| is not sufficiently well-formed.
131 if (!TryToAddFunction(cloned_module.get())) {
132 return false;
133 }
134
135 // Check whether the cloned module is still valid after adding the function.
136 // If it is not, the transformation is not applicable.
137 if (!fuzzerutil::IsValid(cloned_module.get(),
138 transformation_context.GetValidatorOptions(),
139 fuzzerutil::kSilentMessageConsumer)) {
140 return false;
141 }
142
143 if (message_.is_livesafe()) {
144 if (!TryToMakeFunctionLivesafe(cloned_module.get(),
145 transformation_context)) {
146 return false;
147 }
148 // After making the function livesafe, we check validity of the module
149 // again. This is because the turning of OpKill, OpUnreachable and OpReturn
150 // instructions into branches changes control flow graph reachability, which
151 // has the potential to make the module invalid when it was otherwise valid.
152 // It is simpler to rely on the validator to guard against this than to
153 // consider all scenarios when making a function livesafe.
154 if (!fuzzerutil::IsValid(cloned_module.get(),
155 transformation_context.GetValidatorOptions(),
156 fuzzerutil::kSilentMessageConsumer)) {
157 return false;
158 }
159 }
160 return true;
161 }
162
163 void TransformationAddFunction::Apply(
164 opt::IRContext* ir_context,
165 TransformationContext* transformation_context) const {
166 // Add the function to the module. As the transformation is applicable, this
167 // should succeed.
168 bool success = TryToAddFunction(ir_context);
169 assert(success && "The function should be successfully added.");
170 (void)(success); // Keep release builds happy (otherwise they may complain
171 // that |success| is not used).
172
173 if (message_.is_livesafe()) {
174 // Make the function livesafe, which also should succeed.
175 success = TryToMakeFunctionLivesafe(ir_context, *transformation_context);
176 assert(success && "It should be possible to make the function livesafe.");
177 (void)(success); // Keep release builds happy.
178 }
179 ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
180
181 assert(message_.instruction(0).opcode() == SpvOpFunction &&
182 "The first instruction of an 'add function' transformation must be "
183 "OpFunction.");
184
185 if (message_.is_livesafe()) {
186 // Inform the fact manager that the function is livesafe.
187 transformation_context->GetFactManager()->AddFactFunctionIsLivesafe(
188 message_.instruction(0).result_id());
189 } else {
190 // Inform the fact manager that all blocks in the function are dead.
191 for (auto& inst : message_.instruction()) {
192 if (inst.opcode() == SpvOpLabel) {
193 transformation_context->GetFactManager()->AddFactBlockIsDead(
194 inst.result_id());
195 }
196 }
197 }
198
199 // Record the fact that all pointer parameters and variables declared in the
200 // function should be regarded as having irrelevant values. This allows other
201 // passes to store arbitrarily to such variables, and to pass them freely as
202 // parameters to other functions knowing that it is OK if they get
203 // over-written.
204 for (auto& instruction : message_.instruction()) {
205 switch (instruction.opcode()) {
206 case SpvOpFunctionParameter:
207 if (ir_context->get_def_use_mgr()
208 ->GetDef(instruction.result_type_id())
209 ->opcode() == SpvOpTypePointer) {
210 transformation_context->GetFactManager()
211 ->AddFactValueOfPointeeIsIrrelevant(instruction.result_id());
212 }
213 break;
214 case SpvOpVariable:
215 transformation_context->GetFactManager()
216 ->AddFactValueOfPointeeIsIrrelevant(instruction.result_id());
217 break;
218 default:
219 break;
220 }
221 }
222 }
223
224 protobufs::Transformation TransformationAddFunction::ToMessage() const {
225 protobufs::Transformation result;
226 *result.mutable_add_function() = message_;
227 return result;
228 }
229
230 bool TransformationAddFunction::TryToAddFunction(
231 opt::IRContext* ir_context) const {
232 // This function returns false if |message_.instruction| was not well-formed
233 // enough to actually create a function and add it to |ir_context|.
234
235 // A function must have at least some instructions.
236 if (message_.instruction().empty()) {
237 return false;
238 }
239
240 // A function must start with OpFunction.
241 auto function_begin = message_.instruction(0);
242 if (function_begin.opcode() != SpvOpFunction) {
243 return false;
244 }
245
246 // Make a function, headed by the OpFunction instruction.
247 std::unique_ptr<opt::Function> new_function = MakeUnique<opt::Function>(
248 InstructionFromMessage(ir_context, function_begin));
249
250 // Keeps track of which instruction protobuf message we are currently
251 // considering.
252 uint32_t instruction_index = 1;
253 const auto num_instructions =
254 static_cast<uint32_t>(message_.instruction().size());
255
256 // Iterate through all function parameter instructions, adding parameters to
257 // the new function.
258 while (instruction_index < num_instructions &&
259 message_.instruction(instruction_index).opcode() ==
260 SpvOpFunctionParameter) {
261 new_function->AddParameter(InstructionFromMessage(
262 ir_context, message_.instruction(instruction_index)));
263 instruction_index++;
264 }
265
266 // After the parameters, there needs to be a label.
267 if (instruction_index == num_instructions ||
268 message_.instruction(instruction_index).opcode() != SpvOpLabel) {
269 return false;
270 }
271
272 // Iterate through the instructions block by block until the end of the
273 // function is reached.
274 while (instruction_index < num_instructions &&
275 message_.instruction(instruction_index).opcode() != SpvOpFunctionEnd) {
276 // Invariant: we should always be at a label instruction at this point.
277 assert(message_.instruction(instruction_index).opcode() == SpvOpLabel);
278
279 // Make a basic block using the label instruction, with the new function
280 // as its parent.
281 std::unique_ptr<opt::BasicBlock> block =
282 MakeUnique<opt::BasicBlock>(InstructionFromMessage(
283 ir_context, message_.instruction(instruction_index)));
284 block->SetParent(new_function.get());
285
286 // Consider successive instructions until we hit another label or the end
287 // of the function, adding each such instruction to the block.
288 instruction_index++;
289 while (instruction_index < num_instructions &&
290 message_.instruction(instruction_index).opcode() !=
291 SpvOpFunctionEnd &&
292 message_.instruction(instruction_index).opcode() != SpvOpLabel) {
293 block->AddInstruction(InstructionFromMessage(
294 ir_context, message_.instruction(instruction_index)));
295 instruction_index++;
296 }
297 // Add the block to the new function.
298 new_function->AddBasicBlock(std::move(block));
299 }
300 // Having considered all the blocks, we should be at the last instruction and
301 // it needs to be OpFunctionEnd.
302 if (instruction_index != num_instructions - 1 ||
303 message_.instruction(instruction_index).opcode() != SpvOpFunctionEnd) {
304 return false;
305 }
306 // Set the function's final instruction, add the function to the module and
307 // report success.
308 new_function->SetFunctionEnd(InstructionFromMessage(
309 ir_context, message_.instruction(instruction_index)));
310 ir_context->AddFunction(std::move(new_function));
311
312 ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
313
314 return true;
315 }
316
317 bool TransformationAddFunction::TryToMakeFunctionLivesafe(
318 opt::IRContext* ir_context,
319 const TransformationContext& transformation_context) const {
320 assert(message_.is_livesafe() && "Precondition: is_livesafe must hold.");
321
322 // Get a pointer to the added function.
323 opt::Function* added_function = nullptr;
324 for (auto& function : *ir_context->module()) {
325 if (function.result_id() == message_.instruction(0).result_id()) {
326 added_function = &function;
327 break;
328 }
329 }
330 assert(added_function && "The added function should have been found.");
331
332 if (!TryToAddLoopLimiters(ir_context, added_function)) {
333 // Adding loop limiters did not work; bail out.
334 return false;
335 }
336
337 // Consider all the instructions in the function, and:
338 // - attempt to replace OpKill and OpUnreachable with return instructions
339 // - attempt to clamp access chains to be within bounds
340 // - check that OpFunctionCall instructions are only to livesafe functions
341 for (auto& block : *added_function) {
342 for (auto& inst : block) {
343 switch (inst.opcode()) {
344 case SpvOpKill:
345 case SpvOpUnreachable:
346 if (!TryToTurnKillOrUnreachableIntoReturn(ir_context, added_function,
347 &inst)) {
348 return false;
349 }
350 break;
351 case SpvOpAccessChain:
352 case SpvOpInBoundsAccessChain:
353 if (!TryToClampAccessChainIndices(ir_context, &inst)) {
354 return false;
355 }
356 break;
357 case SpvOpFunctionCall:
358 // A livesafe function my only call other livesafe functions.
359 if (!transformation_context.GetFactManager()->FunctionIsLivesafe(
360 inst.GetSingleWordInOperand(0))) {
361 return false;
362 }
363 default:
364 break;
365 }
366 }
367 }
368 return true;
369 }
370
371 uint32_t TransformationAddFunction::GetBackEdgeBlockId(
372 opt::IRContext* ir_context, uint32_t loop_header_block_id) {
373 const auto* loop_header_block =
374 ir_context->cfg()->block(loop_header_block_id);
375 assert(loop_header_block && "|loop_header_block_id| is invalid");
376
377 for (auto pred : ir_context->cfg()->preds(loop_header_block_id)) {
378 if (ir_context->GetDominatorAnalysis(loop_header_block->GetParent())
379 ->Dominates(loop_header_block_id, pred)) {
380 return pred;
381 }
382 }
383
384 return 0;
385 }
386
387 bool TransformationAddFunction::TryToAddLoopLimiters(
388 opt::IRContext* ir_context, opt::Function* added_function) const {
389 // Collect up all the loop headers so that we can subsequently add loop
390 // limiting logic.
391 std::vector<opt::BasicBlock*> loop_headers;
392 for (auto& block : *added_function) {
393 if (block.IsLoopHeader()) {
394 loop_headers.push_back(&block);
395 }
396 }
397
398 if (loop_headers.empty()) {
399 // There are no loops, so no need to add any loop limiters.
400 return true;
401 }
402
403 // Check that the module contains appropriate ingredients for declaring and
404 // manipulating a loop limiter.
405
406 auto loop_limit_constant_id_instr =
407 ir_context->get_def_use_mgr()->GetDef(message_.loop_limit_constant_id());
408 if (!loop_limit_constant_id_instr ||
409 loop_limit_constant_id_instr->opcode() != SpvOpConstant) {
410 // The loop limit constant id instruction must exist and have an
411 // appropriate opcode.
412 return false;
413 }
414
415 auto loop_limit_type = ir_context->get_def_use_mgr()->GetDef(
416 loop_limit_constant_id_instr->type_id());
417 if (loop_limit_type->opcode() != SpvOpTypeInt ||
418 loop_limit_type->GetSingleWordInOperand(0) != 32) {
419 // The type of the loop limit constant must be 32-bit integer. It
420 // doesn't actually matter whether the integer is signed or not.
421 return false;
422 }
423
424 // Find the id of the "unsigned int" type.
425 opt::analysis::Integer unsigned_int_type(32, false);
426 uint32_t unsigned_int_type_id =
427 ir_context->get_type_mgr()->GetId(&unsigned_int_type);
428 if (!unsigned_int_type_id) {
429 // Unsigned int is not available; we need this type in order to add loop
430 // limiters.
431 return false;
432 }
433 auto registered_unsigned_int_type =
434 ir_context->get_type_mgr()->GetRegisteredType(&unsigned_int_type);
435
436 // Look for 0 of type unsigned int.
437 opt::analysis::IntConstant zero(registered_unsigned_int_type->AsInteger(),
438 {0});
439 auto registered_zero = ir_context->get_constant_mgr()->FindConstant(&zero);
440 if (!registered_zero) {
441 // We need 0 in order to be able to initialize loop limiters.
442 return false;
443 }
444 uint32_t zero_id = ir_context->get_constant_mgr()
445 ->GetDefiningInstruction(registered_zero)
446 ->result_id();
447
448 // Look for 1 of type unsigned int.
449 opt::analysis::IntConstant one(registered_unsigned_int_type->AsInteger(),
450 {1});
451 auto registered_one = ir_context->get_constant_mgr()->FindConstant(&one);
452 if (!registered_one) {
453 // We need 1 in order to be able to increment loop limiters.
454 return false;
455 }
456 uint32_t one_id = ir_context->get_constant_mgr()
457 ->GetDefiningInstruction(registered_one)
458 ->result_id();
459
460 // Look for pointer-to-unsigned int type.
461 opt::analysis::Pointer pointer_to_unsigned_int_type(
462 registered_unsigned_int_type, SpvStorageClassFunction);
463 uint32_t pointer_to_unsigned_int_type_id =
464 ir_context->get_type_mgr()->GetId(&pointer_to_unsigned_int_type);
465 if (!pointer_to_unsigned_int_type_id) {
466 // We need pointer-to-unsigned int in order to declare the loop limiter
467 // variable.
468 return false;
469 }
470
471 // Look for bool type.
472 opt::analysis::Bool bool_type;
473 uint32_t bool_type_id = ir_context->get_type_mgr()->GetId(&bool_type);
474 if (!bool_type_id) {
475 // We need bool in order to compare the loop limiter's value with the loop
476 // limit constant.
477 return false;
478 }
479
480 // Declare the loop limiter variable at the start of the function's entry
481 // block, via an instruction of the form:
482 // %loop_limiter_var = SpvOpVariable %ptr_to_uint Function %zero
483 added_function->begin()->begin()->InsertBefore(MakeUnique<opt::Instruction>(
484 ir_context, SpvOpVariable, pointer_to_unsigned_int_type_id,
485 message_.loop_limiter_variable_id(),
486 opt::Instruction::OperandList(
487 {{SPV_OPERAND_TYPE_STORAGE_CLASS, {SpvStorageClassFunction}},
488 {SPV_OPERAND_TYPE_ID, {zero_id}}})));
489 // Update the module's id bound since we have added the loop limiter
490 // variable id.
491 fuzzerutil::UpdateModuleIdBound(ir_context,
492 message_.loop_limiter_variable_id());
493
494 // Consider each loop in turn.
495 for (auto loop_header : loop_headers) {
496 // Look for the loop's back-edge block. This is a predecessor of the loop
497 // header that is dominated by the loop header.
498 const auto back_edge_block_id =
499 GetBackEdgeBlockId(ir_context, loop_header->id());
500 if (!back_edge_block_id) {
501 // The loop's back-edge block must be unreachable. This means that the
502 // loop cannot iterate, so there is no need to make it lifesafe; we can
503 // move on from this loop.
504 continue;
505 }
506
507 // If the loop's merge block is unreachable, then there are no constraints
508 // on where the merge block appears in relation to the blocks of the loop.
509 // This means we need to be careful when adding a branch from the back-edge
510 // block to the merge block: the branch might make the loop merge reachable,
511 // and it might then be dominated by the loop header and possibly by other
512 // blocks in the loop. Since a block needs to appear before those blocks it
513 // strictly dominates, this could make the module invalid. To avoid this
514 // problem we bail out in the case where the loop header does not dominate
515 // the loop merge.
516 if (!ir_context->GetDominatorAnalysis(added_function)
517 ->Dominates(loop_header->id(), loop_header->MergeBlockId())) {
518 return false;
519 }
520
521 // Go through the sequence of loop limiter infos and find the one
522 // corresponding to this loop.
523 bool found = false;
524 protobufs::LoopLimiterInfo loop_limiter_info;
525 for (auto& info : message_.loop_limiter_info()) {
526 if (info.loop_header_id() == loop_header->id()) {
527 loop_limiter_info = info;
528 found = true;
529 break;
530 }
531 }
532 if (!found) {
533 // We don't have loop limiter info for this loop header.
534 return false;
535 }
536
537 // The back-edge block either has the form:
538 //
539 // (1)
540 //
541 // %l = OpLabel
542 // ... instructions ...
543 // OpBranch %loop_header
544 //
545 // (2)
546 //
547 // %l = OpLabel
548 // ... instructions ...
549 // OpBranchConditional %c %loop_header %loop_merge
550 //
551 // (3)
552 //
553 // %l = OpLabel
554 // ... instructions ...
555 // OpBranchConditional %c %loop_merge %loop_header
556 //
557 // We turn these into the following:
558 //
559 // (1)
560 //
561 // %l = OpLabel
562 // ... instructions ...
563 // %t1 = OpLoad %uint32 %loop_limiter
564 // %t2 = OpIAdd %uint32 %t1 %one
565 // OpStore %loop_limiter %t2
566 // %t3 = OpUGreaterThanEqual %bool %t1 %loop_limit
567 // OpBranchConditional %t3 %loop_merge %loop_header
568 //
569 // (2)
570 //
571 // %l = OpLabel
572 // ... instructions ...
573 // %t1 = OpLoad %uint32 %loop_limiter
574 // %t2 = OpIAdd %uint32 %t1 %one
575 // OpStore %loop_limiter %t2
576 // %t3 = OpULessThan %bool %t1 %loop_limit
577 // %t4 = OpLogicalAnd %bool %c %t3
578 // OpBranchConditional %t4 %loop_header %loop_merge
579 //
580 // (3)
581 //
582 // %l = OpLabel
583 // ... instructions ...
584 // %t1 = OpLoad %uint32 %loop_limiter
585 // %t2 = OpIAdd %uint32 %t1 %one
586 // OpStore %loop_limiter %t2
587 // %t3 = OpUGreaterThanEqual %bool %t1 %loop_limit
588 // %t4 = OpLogicalOr %bool %c %t3
589 // OpBranchConditional %t4 %loop_merge %loop_header
590
591 auto back_edge_block = ir_context->cfg()->block(back_edge_block_id);
592 auto back_edge_block_terminator = back_edge_block->terminator();
593 bool compare_using_greater_than_equal;
594 if (back_edge_block_terminator->opcode() == SpvOpBranch) {
595 compare_using_greater_than_equal = true;
596 } else {
597 assert(back_edge_block_terminator->opcode() == SpvOpBranchConditional);
598 assert(((back_edge_block_terminator->GetSingleWordInOperand(1) ==
599 loop_header->id() &&
600 back_edge_block_terminator->GetSingleWordInOperand(2) ==
601 loop_header->MergeBlockId()) ||
602 (back_edge_block_terminator->GetSingleWordInOperand(2) ==
603 loop_header->id() &&
604 back_edge_block_terminator->GetSingleWordInOperand(1) ==
605 loop_header->MergeBlockId())) &&
606 "A back edge edge block must branch to"
607 " either the loop header or merge");
608 compare_using_greater_than_equal =
609 back_edge_block_terminator->GetSingleWordInOperand(1) ==
610 loop_header->MergeBlockId();
611 }
612
613 std::vector<std::unique_ptr<opt::Instruction>> new_instructions;
614
615 // Add a load from the loop limiter variable, of the form:
616 // %t1 = OpLoad %uint32 %loop_limiter
617 new_instructions.push_back(MakeUnique<opt::Instruction>(
618 ir_context, SpvOpLoad, unsigned_int_type_id,
619 loop_limiter_info.load_id(),
620 opt::Instruction::OperandList(
621 {{SPV_OPERAND_TYPE_ID, {message_.loop_limiter_variable_id()}}})));
622
623 // Increment the loaded value:
624 // %t2 = OpIAdd %uint32 %t1 %one
625 new_instructions.push_back(MakeUnique<opt::Instruction>(
626 ir_context, SpvOpIAdd, unsigned_int_type_id,
627 loop_limiter_info.increment_id(),
628 opt::Instruction::OperandList(
629 {{SPV_OPERAND_TYPE_ID, {loop_limiter_info.load_id()}},
630 {SPV_OPERAND_TYPE_ID, {one_id}}})));
631
632 // Store the incremented value back to the loop limiter variable:
633 // OpStore %loop_limiter %t2
634 new_instructions.push_back(MakeUnique<opt::Instruction>(
635 ir_context, SpvOpStore, 0, 0,
636 opt::Instruction::OperandList(
637 {{SPV_OPERAND_TYPE_ID, {message_.loop_limiter_variable_id()}},
638 {SPV_OPERAND_TYPE_ID, {loop_limiter_info.increment_id()}}})));
639
640 // Compare the loaded value with the loop limit; either:
641 // %t3 = OpUGreaterThanEqual %bool %t1 %loop_limit
642 // or
643 // %t3 = OpULessThan %bool %t1 %loop_limit
644 new_instructions.push_back(MakeUnique<opt::Instruction>(
645 ir_context,
646 compare_using_greater_than_equal ? SpvOpUGreaterThanEqual
647 : SpvOpULessThan,
648 bool_type_id, loop_limiter_info.compare_id(),
649 opt::Instruction::OperandList(
650 {{SPV_OPERAND_TYPE_ID, {loop_limiter_info.load_id()}},
651 {SPV_OPERAND_TYPE_ID, {message_.loop_limit_constant_id()}}})));
652
653 if (back_edge_block_terminator->opcode() == SpvOpBranchConditional) {
654 new_instructions.push_back(MakeUnique<opt::Instruction>(
655 ir_context,
656 compare_using_greater_than_equal ? SpvOpLogicalOr : SpvOpLogicalAnd,
657 bool_type_id, loop_limiter_info.logical_op_id(),
658 opt::Instruction::OperandList(
659 {{SPV_OPERAND_TYPE_ID,
660 {back_edge_block_terminator->GetSingleWordInOperand(0)}},
661 {SPV_OPERAND_TYPE_ID, {loop_limiter_info.compare_id()}}})));
662 }
663
664 // Add the new instructions at the end of the back edge block, before the
665 // terminator and any loop merge instruction (as the back edge block can
666 // be the loop header).
667 if (back_edge_block->GetLoopMergeInst()) {
668 back_edge_block->GetLoopMergeInst()->InsertBefore(
669 std::move(new_instructions));
670 } else {
671 back_edge_block_terminator->InsertBefore(std::move(new_instructions));
672 }
673
674 if (back_edge_block_terminator->opcode() == SpvOpBranchConditional) {
675 back_edge_block_terminator->SetInOperand(
676 0, {loop_limiter_info.logical_op_id()});
677 } else {
678 assert(back_edge_block_terminator->opcode() == SpvOpBranch &&
679 "Back-edge terminator must be OpBranch or OpBranchConditional");
680
681 // Check that, if the merge block starts with OpPhi instructions, suitable
682 // ids have been provided to give these instructions a value corresponding
683 // to the new incoming edge from the back edge block.
684 auto merge_block = ir_context->cfg()->block(loop_header->MergeBlockId());
685 if (!fuzzerutil::PhiIdsOkForNewEdge(ir_context, back_edge_block,
686 merge_block,
687 loop_limiter_info.phi_id())) {
688 return false;
689 }
690
691 // Augment OpPhi instructions at the loop merge with the given ids.
692 uint32_t phi_index = 0;
693 for (auto& inst : *merge_block) {
694 if (inst.opcode() != SpvOpPhi) {
695 break;
696 }
697 assert(phi_index <
698 static_cast<uint32_t>(loop_limiter_info.phi_id().size()) &&
699 "There should be at least one phi id per OpPhi instruction.");
700 inst.AddOperand(
701 {SPV_OPERAND_TYPE_ID, {loop_limiter_info.phi_id(phi_index)}});
702 inst.AddOperand({SPV_OPERAND_TYPE_ID, {back_edge_block_id}});
703 phi_index++;
704 }
705
706 // Add the new edge, by changing OpBranch to OpBranchConditional.
707 back_edge_block_terminator->SetOpcode(SpvOpBranchConditional);
708 back_edge_block_terminator->SetInOperands(opt::Instruction::OperandList(
709 {{SPV_OPERAND_TYPE_ID, {loop_limiter_info.compare_id()}},
710 {SPV_OPERAND_TYPE_ID, {loop_header->MergeBlockId()}},
711 {SPV_OPERAND_TYPE_ID, {loop_header->id()}}}));
712 }
713
714 // Update the module's id bound with respect to the various ids that
715 // have been used for loop limiter manipulation.
716 fuzzerutil::UpdateModuleIdBound(ir_context, loop_limiter_info.load_id());
717 fuzzerutil::UpdateModuleIdBound(ir_context,
718 loop_limiter_info.increment_id());
719 fuzzerutil::UpdateModuleIdBound(ir_context, loop_limiter_info.compare_id());
720 fuzzerutil::UpdateModuleIdBound(ir_context,
721 loop_limiter_info.logical_op_id());
722 }
723 return true;
724 }
725
726 bool TransformationAddFunction::TryToTurnKillOrUnreachableIntoReturn(
727 opt::IRContext* ir_context, opt::Function* added_function,
728 opt::Instruction* kill_or_unreachable_inst) const {
729 assert((kill_or_unreachable_inst->opcode() == SpvOpKill ||
730 kill_or_unreachable_inst->opcode() == SpvOpUnreachable) &&
731 "Precondition: instruction must be OpKill or OpUnreachable.");
732
733 // Get the function's return type.
734 auto function_return_type_inst =
735 ir_context->get_def_use_mgr()->GetDef(added_function->type_id());
736
737 if (function_return_type_inst->opcode() == SpvOpTypeVoid) {
738 // The function has void return type, so change this instruction to
739 // OpReturn.
740 kill_or_unreachable_inst->SetOpcode(SpvOpReturn);
741 } else {
742 // The function has non-void return type, so change this instruction
743 // to OpReturnValue, using the value id provided with the
744 // transformation.
745
746 // We first check that the id, %id, provided with the transformation
747 // specifically to turn OpKill and OpUnreachable instructions into
748 // OpReturnValue %id has the same type as the function's return type.
749 if (ir_context->get_def_use_mgr()
750 ->GetDef(message_.kill_unreachable_return_value_id())
751 ->type_id() != function_return_type_inst->result_id()) {
752 return false;
753 }
754 kill_or_unreachable_inst->SetOpcode(SpvOpReturnValue);
755 kill_or_unreachable_inst->SetInOperands(
756 {{SPV_OPERAND_TYPE_ID, {message_.kill_unreachable_return_value_id()}}});
757 }
758 return true;
759 }
760
761 bool TransformationAddFunction::TryToClampAccessChainIndices(
762 opt::IRContext* ir_context, opt::Instruction* access_chain_inst) const {
763 assert((access_chain_inst->opcode() == SpvOpAccessChain ||
764 access_chain_inst->opcode() == SpvOpInBoundsAccessChain) &&
765 "Precondition: instruction must be OpAccessChain or "
766 "OpInBoundsAccessChain.");
767
768 // Find the AccessChainClampingInfo associated with this access chain.
769 const protobufs::AccessChainClampingInfo* access_chain_clamping_info =
770 nullptr;
771 for (auto& clamping_info : message_.access_chain_clamping_info()) {
772 if (clamping_info.access_chain_id() == access_chain_inst->result_id()) {
773 access_chain_clamping_info = &clamping_info;
774 break;
775 }
776 }
777 if (!access_chain_clamping_info) {
778 // No access chain clamping information was found; the function cannot be
779 // made livesafe.
780 return false;
781 }
782
783 // Check that there is a (compare_id, select_id) pair for every
784 // index associated with the instruction.
785 if (static_cast<uint32_t>(
786 access_chain_clamping_info->compare_and_select_ids().size()) !=
787 access_chain_inst->NumInOperands() - 1) {
788 return false;
789 }
790
791 // Walk the access chain, clamping each index to be within bounds if it is
792 // not a constant.
793 auto base_object = ir_context->get_def_use_mgr()->GetDef(
794 access_chain_inst->GetSingleWordInOperand(0));
795 assert(base_object && "The base object must exist.");
796 auto pointer_type =
797 ir_context->get_def_use_mgr()->GetDef(base_object->type_id());
798 assert(pointer_type && pointer_type->opcode() == SpvOpTypePointer &&
799 "The base object must have pointer type.");
800 auto should_be_composite_type = ir_context->get_def_use_mgr()->GetDef(
801 pointer_type->GetSingleWordInOperand(1));
802
803 // Consider each index input operand in turn (operand 0 is the base object).
804 for (uint32_t index = 1; index < access_chain_inst->NumInOperands();
805 index++) {
806 // We are going to turn:
807 //
808 // %result = OpAccessChain %type %object ... %index ...
809 //
810 // into:
811 //
812 // %t1 = OpULessThanEqual %bool %index %bound_minus_one
813 // %t2 = OpSelect %int_type %t1 %index %bound_minus_one
814 // %result = OpAccessChain %type %object ... %t2 ...
815 //
816 // ... unless %index is already a constant.
817
818 // Get the bound for the composite being indexed into; e.g. the number of
819 // columns of matrix or the size of an array.
820 uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
821 *should_be_composite_type, ir_context);
822
823 // Get the instruction associated with the index and figure out its integer
824 // type.
825 const uint32_t index_id = access_chain_inst->GetSingleWordInOperand(index);
826 auto index_inst = ir_context->get_def_use_mgr()->GetDef(index_id);
827 auto index_type_inst =
828 ir_context->get_def_use_mgr()->GetDef(index_inst->type_id());
829 assert(index_type_inst->opcode() == SpvOpTypeInt);
830 assert(index_type_inst->GetSingleWordInOperand(0) == 32);
831 opt::analysis::Integer* index_int_type =
832 ir_context->get_type_mgr()
833 ->GetType(index_type_inst->result_id())
834 ->AsInteger();
835
836 if (index_inst->opcode() != SpvOpConstant ||
837 index_inst->GetSingleWordInOperand(0) >= bound) {
838 // The index is either non-constant or an out-of-bounds constant, so we
839 // need to clamp it.
840 assert(should_be_composite_type->opcode() != SpvOpTypeStruct &&
841 "Access chain indices into structures are required to be "
842 "constants.");
843 opt::analysis::IntConstant bound_minus_one(index_int_type, {bound - 1});
844 if (!ir_context->get_constant_mgr()->FindConstant(&bound_minus_one)) {
845 // We do not have an integer constant whose value is |bound| -1.
846 return false;
847 }
848
849 opt::analysis::Bool bool_type;
850 uint32_t bool_type_id = ir_context->get_type_mgr()->GetId(&bool_type);
851 if (!bool_type_id) {
852 // Bool type is not declared; we cannot do a comparison.
853 return false;
854 }
855
856 uint32_t bound_minus_one_id =
857 ir_context->get_constant_mgr()
858 ->GetDefiningInstruction(&bound_minus_one)
859 ->result_id();
860
861 uint32_t compare_id =
862 access_chain_clamping_info->compare_and_select_ids(index - 1).first();
863 uint32_t select_id =
864 access_chain_clamping_info->compare_and_select_ids(index - 1)
865 .second();
866 std::vector<std::unique_ptr<opt::Instruction>> new_instructions;
867
868 // Compare the index with the bound via an instruction of the form:
869 // %t1 = OpULessThanEqual %bool %index %bound_minus_one
870 new_instructions.push_back(MakeUnique<opt::Instruction>(
871 ir_context, SpvOpULessThanEqual, bool_type_id, compare_id,
872 opt::Instruction::OperandList(
873 {{SPV_OPERAND_TYPE_ID, {index_inst->result_id()}},
874 {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));
875
876 // Select the index if in-bounds, otherwise one less than the bound:
877 // %t2 = OpSelect %int_type %t1 %index %bound_minus_one
878 new_instructions.push_back(MakeUnique<opt::Instruction>(
879 ir_context, SpvOpSelect, index_type_inst->result_id(), select_id,
880 opt::Instruction::OperandList(
881 {{SPV_OPERAND_TYPE_ID, {compare_id}},
882 {SPV_OPERAND_TYPE_ID, {index_inst->result_id()}},
883 {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));
884
885 // Add the new instructions before the access chain
886 access_chain_inst->InsertBefore(std::move(new_instructions));
887
888 // Replace %index with %t2.
889 access_chain_inst->SetInOperand(index, {select_id});
890 fuzzerutil::UpdateModuleIdBound(ir_context, compare_id);
891 fuzzerutil::UpdateModuleIdBound(ir_context, select_id);
892 }
893 should_be_composite_type =
894 FollowCompositeIndex(ir_context, *should_be_composite_type, index_id);
895 }
896 return true;
897 }
898
899 opt::Instruction* TransformationAddFunction::FollowCompositeIndex(
900 opt::IRContext* ir_context, const opt::Instruction& composite_type_inst,
901 uint32_t index_id) {
902 uint32_t sub_object_type_id;
903 switch (composite_type_inst.opcode()) {
904 case SpvOpTypeArray:
905 case SpvOpTypeRuntimeArray:
906 sub_object_type_id = composite_type_inst.GetSingleWordInOperand(0);
907 break;
908 case SpvOpTypeMatrix:
909 case SpvOpTypeVector:
910 sub_object_type_id = composite_type_inst.GetSingleWordInOperand(0);
911 break;
912 case SpvOpTypeStruct: {
913 auto index_inst = ir_context->get_def_use_mgr()->GetDef(index_id);
914 assert(index_inst->opcode() == SpvOpConstant);
915 assert(ir_context->get_def_use_mgr()
916 ->GetDef(index_inst->type_id())
917 ->opcode() == SpvOpTypeInt);
918 assert(ir_context->get_def_use_mgr()
919 ->GetDef(index_inst->type_id())
920 ->GetSingleWordInOperand(0) == 32);
921 uint32_t index_value = index_inst->GetSingleWordInOperand(0);
922 sub_object_type_id =
923 composite_type_inst.GetSingleWordInOperand(index_value);
924 break;
925 }
926 default:
927 assert(false && "Unknown composite type.");
928 sub_object_type_id = 0;
929 break;
930 }
931 assert(sub_object_type_id && "No sub-object found.");
932 return ir_context->get_def_use_mgr()->GetDef(sub_object_type_id);
933 }
934
935 std::unordered_set<uint32_t> TransformationAddFunction::GetFreshIds() const {
936 std::unordered_set<uint32_t> result;
937 for (auto& instruction : message_.instruction()) {
938 result.insert(instruction.result_id());
939 }
940 if (message_.is_livesafe()) {
941 result.insert(message_.loop_limiter_variable_id());
942 for (auto& loop_limiter_info : message_.loop_limiter_info()) {
943 result.insert(loop_limiter_info.load_id());
944 result.insert(loop_limiter_info.increment_id());
945 result.insert(loop_limiter_info.compare_id());
946 result.insert(loop_limiter_info.logical_op_id());
947 }
948 for (auto& access_chain_clamping_info :
949 message_.access_chain_clamping_info()) {
950 for (auto& pair : access_chain_clamping_info.compare_and_select_ids()) {
951 result.insert(pair.first());
952 result.insert(pair.second());
953 }
954 }
955 }
956 return result;
957 }
958
959 } // namespace fuzz
960 } // namespace spvtools