Debian Codegraph @

third_party/spirv-tools/source/fuzz/fuzzer_util.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_util.h"
16
17 #include <algorithm>
18 #include <unordered_set>
19
20 #include "source/opt/build_module.h"
21
22 namespace spvtools {
23 namespace fuzz {
24
25 namespace fuzzerutil {
26 namespace {
27
28 uint32_t MaybeGetOpConstant(opt::IRContext* ir_context,
29 const TransformationContext& transformation_context,
30 const std::vector<uint32_t>& words,
31 uint32_t type_id, bool is_irrelevant) {
32 for (const auto& inst : ir_context->types_values()) {
33 if (inst.opcode() == SpvOpConstant && inst.type_id() == type_id &&
34 inst.GetInOperand(0).words == words &&
35 transformation_context.GetFactManager()->IdIsIrrelevant(
36 inst.result_id()) == is_irrelevant) {
37 return inst.result_id();
38 }
39 }
40
41 return 0;
42 }
43
44 } // namespace
45
46 const spvtools::MessageConsumer kSilentMessageConsumer =
47 [](spv_message_level_t, const char*, const spv_position_t&,
48 const char*) -> void {};
49
50 bool IsFreshId(opt::IRContext* context, uint32_t id) {
51 return !context->get_def_use_mgr()->GetDef(id);
52 }
53
54 void UpdateModuleIdBound(opt::IRContext* context, uint32_t id) {
55 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2541) consider the
56 // case where the maximum id bound is reached.
57 context->module()->SetIdBound(
58 std::max(context->module()->id_bound(), id + 1));
59 }
60
61 opt::BasicBlock* MaybeFindBlock(opt::IRContext* context,
62 uint32_t maybe_block_id) {
63 auto inst = context->get_def_use_mgr()->GetDef(maybe_block_id);
64 if (inst == nullptr) {
65 // No instruction defining this id was found.
66 return nullptr;
67 }
68 if (inst->opcode() != SpvOpLabel) {
69 // The instruction defining the id is not a label, so it cannot be a block
70 // id.
71 return nullptr;
72 }
73 return context->cfg()->block(maybe_block_id);
74 }
75
76 bool PhiIdsOkForNewEdge(
77 opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
78 const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids) {
79 if (bb_from->IsSuccessor(bb_to)) {
80 // There is already an edge from |from_block| to |to_block|, so there is
81 // no need to extend OpPhi instructions. Do not allow phi ids to be
82 // present. This might turn out to be too strict; perhaps it would be OK
83 // just to ignore the ids in this case.
84 return phi_ids.empty();
85 }
86 // The edge would add a previously non-existent edge from |from_block| to
87 // |to_block|, so we go through the given phi ids and check that they exactly
88 // match the OpPhi instructions in |to_block|.
89 uint32_t phi_index = 0;
90 // An explicit loop, rather than applying a lambda to each OpPhi in |bb_to|,
91 // makes sense here because we need to increment |phi_index| for each OpPhi
92 // instruction.
93 for (auto& inst : *bb_to) {
94 if (inst.opcode() != SpvOpPhi) {
95 // The OpPhi instructions all occur at the start of the block; if we find
96 // a non-OpPhi then we have seen them all.
97 break;
98 }
99 if (phi_index == static_cast<uint32_t>(phi_ids.size())) {
100 // Not enough phi ids have been provided to account for the OpPhi
101 // instructions.
102 return false;
103 }
104 // Look for an instruction defining the next phi id.
105 opt::Instruction* phi_extension =
106 context->get_def_use_mgr()->GetDef(phi_ids[phi_index]);
107 if (!phi_extension) {
108 // The id given to extend this OpPhi does not exist.
109 return false;
110 }
111 if (phi_extension->type_id() != inst.type_id()) {
112 // The instruction given to extend this OpPhi either does not have a type
113 // or its type does not match that of the OpPhi.
114 return false;
115 }
116
117 if (context->get_instr_block(phi_extension)) {
118 // The instruction defining the phi id has an associated block (i.e., it
119 // is not a global value). Check whether its definition dominates the
120 // exit of |from_block|.
121 auto dominator_analysis =
122 context->GetDominatorAnalysis(bb_from->GetParent());
123 if (!dominator_analysis->Dominates(phi_extension,
124 bb_from->terminator())) {
125 // The given id is no good as its definition does not dominate the exit
126 // of |from_block|
127 return false;
128 }
129 }
130 phi_index++;
131 }
132 // We allow some of the ids provided for extending OpPhi instructions to be
133 // unused. Their presence does no harm, and requiring a perfect match may
134 // make transformations less likely to cleanly apply.
135 return true;
136 }
137
138 void AddUnreachableEdgeAndUpdateOpPhis(
139 opt::IRContext* context, opt::BasicBlock* bb_from, opt::BasicBlock* bb_to,
140 uint32_t bool_id,
141 const google::protobuf::RepeatedField<google::protobuf::uint32>& phi_ids) {
142 assert(PhiIdsOkForNewEdge(context, bb_from, bb_to, phi_ids) &&
143 "Precondition on phi_ids is not satisfied");
144 assert(bb_from->terminator()->opcode() == SpvOpBranch &&
145 "Precondition on terminator of bb_from is not satisfied");
146
147 // Get the id of the boolean constant to be used as the condition.
148 auto condition_inst = context->get_def_use_mgr()->GetDef(bool_id);
149 assert(condition_inst &&
150 (condition_inst->opcode() == SpvOpConstantTrue ||
151 condition_inst->opcode() == SpvOpConstantFalse) &&
152 "|bool_id| is invalid");
153
154 auto condition_value = condition_inst->opcode() == SpvOpConstantTrue;
155
156 const bool from_to_edge_already_exists = bb_from->IsSuccessor(bb_to);
157 auto successor = bb_from->terminator()->GetSingleWordInOperand(0);
158
159 // Add the dead branch, by turning OpBranch into OpBranchConditional, and
160 // ordering the targets depending on whether the given boolean corresponds to
161 // true or false.
162 bb_from->terminator()->SetOpcode(SpvOpBranchConditional);
163 bb_from->terminator()->SetInOperands(
164 {{SPV_OPERAND_TYPE_ID, {bool_id}},
165 {SPV_OPERAND_TYPE_ID, {condition_value ? successor : bb_to->id()}},
166 {SPV_OPERAND_TYPE_ID, {condition_value ? bb_to->id() : successor}}});
167
168 // Update OpPhi instructions in the target block if this branch adds a
169 // previously non-existent edge from source to target.
170 if (!from_to_edge_already_exists) {
171 uint32_t phi_index = 0;
172 for (auto& inst : *bb_to) {
173 if (inst.opcode() != SpvOpPhi) {
174 break;
175 }
176 assert(phi_index < static_cast<uint32_t>(phi_ids.size()) &&
177 "There should be at least one phi id per OpPhi instruction.");
178 inst.AddOperand({SPV_OPERAND_TYPE_ID, {phi_ids[phi_index]}});
179 inst.AddOperand({SPV_OPERAND_TYPE_ID, {bb_from->id()}});
180 phi_index++;
181 }
182 }
183 }
184
185 bool BlockIsBackEdge(opt::IRContext* context, uint32_t block_id,
186 uint32_t loop_header_id) {
187 auto block = context->cfg()->block(block_id);
188 auto loop_header = context->cfg()->block(loop_header_id);
189
190 // |block| and |loop_header| must be defined, |loop_header| must be in fact
191 // loop header and |block| must branch to it.
192 if (!(block && loop_header && loop_header->IsLoopHeader() &&
193 block->IsSuccessor(loop_header))) {
194 return false;
195 }
196
197 // |block_id| must be reachable and be dominated by |loop_header|.
198 opt::DominatorAnalysis* dominator_analysis =
199 context->GetDominatorAnalysis(loop_header->GetParent());
200 return dominator_analysis->IsReachable(block_id) &&
201 dominator_analysis->Dominates(loop_header_id, block_id);
202 }
203
204 bool BlockIsInLoopContinueConstruct(opt::IRContext* context, uint32_t block_id,
205 uint32_t maybe_loop_header_id) {
206 // We deem a block to be part of a loop's continue construct if the loop's
207 // continue target dominates the block.
208 auto containing_construct_block = context->cfg()->block(maybe_loop_header_id);
209 if (containing_construct_block->IsLoopHeader()) {
210 auto continue_target = containing_construct_block->ContinueBlockId();
211 if (context->GetDominatorAnalysis(containing_construct_block->GetParent())
212 ->Dominates(continue_target, block_id)) {
213 return true;
214 }
215 }
216 return false;
217 }
218
219 opt::BasicBlock::iterator GetIteratorForInstruction(
220 opt::BasicBlock* block, const opt::Instruction* inst) {
221 for (auto inst_it = block->begin(); inst_it != block->end(); ++inst_it) {
222 if (inst == &*inst_it) {
223 return inst_it;
224 }
225 }
226 return block->end();
227 }
228
229 bool BlockIsReachableInItsFunction(opt::IRContext* context,
230 opt::BasicBlock* bb) {
231 auto enclosing_function = bb->GetParent();
232 return context->GetDominatorAnalysis(enclosing_function)
233 ->Dominates(enclosing_function->entry().get(), bb);
234 }
235
236 bool CanInsertOpcodeBeforeInstruction(
237 SpvOp opcode, const opt::BasicBlock::iterator& instruction_in_block) {
238 if (instruction_in_block->PreviousNode() &&
239 (instruction_in_block->PreviousNode()->opcode() == SpvOpLoopMerge ||
240 instruction_in_block->PreviousNode()->opcode() == SpvOpSelectionMerge)) {
241 // We cannot insert directly after a merge instruction.
242 return false;
243 }
244 if (opcode != SpvOpVariable &&
245 instruction_in_block->opcode() == SpvOpVariable) {
246 // We cannot insert a non-OpVariable instruction directly before a
247 // variable; variables in a function must be contiguous in the entry block.
248 return false;
249 }
250 // We cannot insert a non-OpPhi instruction directly before an OpPhi, because
251 // OpPhi instructions need to be contiguous at the start of a block.
252 return opcode == SpvOpPhi || instruction_in_block->opcode() != SpvOpPhi;
253 }
254
255 bool CanMakeSynonymOf(opt::IRContext* ir_context,
256 const TransformationContext& transformation_context,
257 opt::Instruction* inst) {
258 if (inst->opcode() == SpvOpSampledImage) {
259 // The SPIR-V data rules say that only very specific instructions may
260 // may consume the result id of an OpSampledImage, and this excludes the
261 // instructions that are used for making synonyms.
262 return false;
263 }
264 if (!inst->HasResultId()) {
265 // We can only make a synonym of an instruction that generates an id.
266 return false;
267 }
268 if (transformation_context.GetFactManager()->IdIsIrrelevant(
269 inst->result_id())) {
270 // An irrelevant id can't be a synonym of anything.
271 return false;
272 }
273 if (!inst->type_id()) {
274 // We can only make a synonym of an instruction that has a type.
275 return false;
276 }
277 auto type_inst = ir_context->get_def_use_mgr()->GetDef(inst->type_id());
278 if (type_inst->opcode() == SpvOpTypeVoid) {
279 // We only make synonyms of instructions that define objects, and an object
280 // cannot have void type.
281 return false;
282 }
283 if (type_inst->opcode() == SpvOpTypePointer) {
284 switch (inst->opcode()) {
285 case SpvOpConstantNull:
286 case SpvOpUndef:
287 // We disallow making synonyms of null or undefined pointers. This is
288 // to provide the property that if the original shader exhibited no bad
289 // pointer accesses, the transformed shader will not either.
290 return false;
291 default:
292 break;
293 }
294 }
295
296 // We do not make synonyms of objects that have decorations: if the synonym is
297 // not decorated analogously, using the original object vs. its synonymous
298 // form may not be equivalent.
299 return ir_context->get_decoration_mgr()
300 ->GetDecorationsFor(inst->result_id(), true)
301 .empty();
302 }
303
304 bool IsCompositeType(const opt::analysis::Type* type) {
305 return type && (type->AsArray() || type->AsMatrix() || type->AsStruct() ||
306 type->AsVector());
307 }
308
309 std::vector<uint32_t> RepeatedFieldToVector(
310 const google::protobuf::RepeatedField<uint32_t>& repeated_field) {
311 std::vector<uint32_t> result;
312 for (auto i : repeated_field) {
313 result.push_back(i);
314 }
315 return result;
316 }
317
318 uint32_t WalkOneCompositeTypeIndex(opt::IRContext* context,
319 uint32_t base_object_type_id,
320 uint32_t index) {
321 auto should_be_composite_type =
322 context->get_def_use_mgr()->GetDef(base_object_type_id);
323 assert(should_be_composite_type && "The type should exist.");
324 switch (should_be_composite_type->opcode()) {
325 case SpvOpTypeArray: {
326 auto array_length = GetArraySize(*should_be_composite_type, context);
327 if (array_length == 0 || index >= array_length) {
328 return 0;
329 }
330 return should_be_composite_type->GetSingleWordInOperand(0);
331 }
332 case SpvOpTypeMatrix:
333 case SpvOpTypeVector: {
334 auto count = should_be_composite_type->GetSingleWordInOperand(1);
335 if (index >= count) {
336 return 0;
337 }
338 return should_be_composite_type->GetSingleWordInOperand(0);
339 }
340 case SpvOpTypeStruct: {
341 if (index >= GetNumberOfStructMembers(*should_be_composite_type)) {
342 return 0;
343 }
344 return should_be_composite_type->GetSingleWordInOperand(index);
345 }
346 default:
347 return 0;
348 }
349 }
350
351 uint32_t WalkCompositeTypeIndices(
352 opt::IRContext* context, uint32_t base_object_type_id,
353 const google::protobuf::RepeatedField<google::protobuf::uint32>& indices) {
354 uint32_t sub_object_type_id = base_object_type_id;
355 for (auto index : indices) {
356 sub_object_type_id =
357 WalkOneCompositeTypeIndex(context, sub_object_type_id, index);
358 if (!sub_object_type_id) {
359 return 0;
360 }
361 }
362 return sub_object_type_id;
363 }
364
365 uint32_t GetNumberOfStructMembers(
366 const opt::Instruction& struct_type_instruction) {
367 assert(struct_type_instruction.opcode() == SpvOpTypeStruct &&
368 "An OpTypeStruct instruction is required here.");
369 return struct_type_instruction.NumInOperands();
370 }
371
372 uint32_t GetArraySize(const opt::Instruction& array_type_instruction,
373 opt::IRContext* context) {
374 auto array_length_constant =
375 context->get_constant_mgr()
376 ->GetConstantFromInst(context->get_def_use_mgr()->GetDef(
377 array_type_instruction.GetSingleWordInOperand(1)))
378 ->AsIntConstant();
379 if (array_length_constant->words().size() != 1) {
380 return 0;
381 }
382 return array_length_constant->GetU32();
383 }
384
385 uint32_t GetBoundForCompositeIndex(const opt::Instruction& composite_type_inst,
386 opt::IRContext* ir_context) {
387 switch (composite_type_inst.opcode()) {
388 case SpvOpTypeArray:
389 return fuzzerutil::GetArraySize(composite_type_inst, ir_context);
390 case SpvOpTypeMatrix:
391 case SpvOpTypeVector:
392 return composite_type_inst.GetSingleWordInOperand(1);
393 case SpvOpTypeStruct: {
394 return fuzzerutil::GetNumberOfStructMembers(composite_type_inst);
395 }
396 case SpvOpTypeRuntimeArray:
397 assert(false &&
398 "GetBoundForCompositeIndex should not be invoked with an "
399 "OpTypeRuntimeArray, which does not have a static bound.");
400 return 0;
401 default:
402 assert(false && "Unknown composite type.");
403 return 0;
404 }
405 }
406
407 bool IsValid(const opt::IRContext* context,
408 spv_validator_options validator_options,
409 MessageConsumer consumer) {
410 std::vector<uint32_t> binary;
411 context->module()->ToBinary(&binary, false);
412 SpirvTools tools(context->grammar().target_env());
413 tools.SetMessageConsumer(consumer);
414 return tools.Validate(binary.data(), binary.size(), validator_options);
415 }
416
417 bool IsValidAndWellFormed(const opt::IRContext* ir_context,
418 spv_validator_options validator_options,
419 MessageConsumer consumer) {
420 if (!IsValid(ir_context, validator_options, consumer)) {
421 // Expression to dump |ir_context| to /data/temp/shader.spv:
422 // DumpShader(ir_context, "/data/temp/shader.spv")
423 consumer(SPV_MSG_INFO, nullptr, {},
424 "Module is invalid (set a breakpoint to inspect).");
425 return false;
426 }
427 // Check that all blocks in the module have appropriate parent functions.
428 for (auto& function : *ir_context->module()) {
429 for (auto& block : function) {
430 if (block.GetParent() == nullptr) {
431 std::stringstream ss;
432 ss << "Block " << block.id() << " has no parent; its parent should be "
433 << function.result_id() << " (set a breakpoint to inspect).";
434 consumer(SPV_MSG_INFO, nullptr, {}, ss.str().c_str());
435 return false;
436 }
437 if (block.GetParent() != &function) {
438 std::stringstream ss;
439 ss << "Block " << block.id() << " should have parent "
440 << function.result_id() << " but instead has parent "
441 << block.GetParent() << " (set a breakpoint to inspect).";
442 consumer(SPV_MSG_INFO, nullptr, {}, ss.str().c_str());
443 return false;
444 }
445 }
446 }
447
448 // Check that all instructions have distinct unique ids. We map each unique
449 // id to the first instruction it is observed to be associated with so that
450 // if we encounter a duplicate we have access to the previous instruction -
451 // this is a useful aid to debugging.
452 std::unordered_map<uint32_t, opt::Instruction*> unique_ids;
453 bool found_duplicate = false;
454 ir_context->module()->ForEachInst([&consumer, &found_duplicate,
455 &unique_ids](opt::Instruction* inst) {
456 if (unique_ids.count(inst->unique_id()) != 0) {
457 consumer(SPV_MSG_INFO, nullptr, {},
458 "Two instructions have the same unique id (set a breakpoint to "
459 "inspect).");
460 found_duplicate = true;
461 }
462 unique_ids.insert({inst->unique_id(), inst});
463 });
464 return !found_duplicate;
465 }
466
467 std::unique_ptr<opt::IRContext> CloneIRContext(opt::IRContext* context) {
468 std::vector<uint32_t> binary;
469 context->module()->ToBinary(&binary, false);
470 return BuildModule(context->grammar().target_env(), nullptr, binary.data(),
471 binary.size());
472 }
473
474 bool IsNonFunctionTypeId(opt::IRContext* ir_context, uint32_t id) {
475 auto type = ir_context->get_type_mgr()->GetType(id);
476 return type && !type->AsFunction();
477 }
478
479 bool IsMergeOrContinue(opt::IRContext* ir_context, uint32_t block_id) {
480 bool result = false;
481 ir_context->get_def_use_mgr()->WhileEachUse(
482 block_id,
483 [&result](const opt::Instruction* use_instruction,
484 uint32_t /*unused*/) -> bool {
485 switch (use_instruction->opcode()) {
486 case SpvOpLoopMerge:
487 case SpvOpSelectionMerge:
488 result = true;
489 return false;
490 default:
491 return true;
492 }
493 });
494 return result;
495 }
496
497 uint32_t GetLoopFromMergeBlock(opt::IRContext* ir_context,
498 uint32_t merge_block_id) {
499 uint32_t result = 0;
500 ir_context->get_def_use_mgr()->WhileEachUse(
501 merge_block_id,
502 [ir_context, &result](opt::Instruction* use_instruction,
503 uint32_t use_index) -> bool {
504 switch (use_instruction->opcode()) {
505 case SpvOpLoopMerge:
506 // The merge block operand is the first operand in OpLoopMerge.
507 if (use_index == 0) {
508 result = ir_context->get_instr_block(use_instruction)->id();
509 return false;
510 }
511 return true;
512 default:
513 return true;
514 }
515 });
516 return result;
517 }
518
519 uint32_t FindFunctionType(opt::IRContext* ir_context,
520 const std::vector<uint32_t>& type_ids) {
521 // Look through the existing types for a match.
522 for (auto& type_or_value : ir_context->types_values()) {
523 if (type_or_value.opcode() != SpvOpTypeFunction) {
524 // We are only interested in function types.
525 continue;
526 }
527 if (type_or_value.NumInOperands() != type_ids.size()) {
528 // Not a match: different numbers of arguments.
529 continue;
530 }
531 // Check whether the return type and argument types match.
532 bool input_operands_match = true;
533 for (uint32_t i = 0; i < type_or_value.NumInOperands(); i++) {
534 if (type_ids[i] != type_or_value.GetSingleWordInOperand(i)) {
535 input_operands_match = false;
536 break;
537 }
538 }
539 if (input_operands_match) {
540 // Everything matches.
541 return type_or_value.result_id();
542 }
543 }
544 // No match was found.
545 return 0;
546 }
547
548 opt::Instruction* GetFunctionType(opt::IRContext* context,
549 const opt::Function* function) {
550 uint32_t type_id = function->DefInst().GetSingleWordInOperand(1);
551 return context->get_def_use_mgr()->GetDef(type_id);
552 }
553
554 opt::Function* FindFunction(opt::IRContext* ir_context, uint32_t function_id) {
555 for (auto& function : *ir_context->module()) {
556 if (function.result_id() == function_id) {
557 return &function;
558 }
559 }
560 return nullptr;
561 }
562
563 bool FunctionContainsOpKillOrUnreachable(const opt::Function& function) {
564 for (auto& block : function) {
565 if (block.terminator()->opcode() == SpvOpKill ||
566 block.terminator()->opcode() == SpvOpUnreachable) {
567 return true;
568 }
569 }
570 return false;
571 }
572
573 bool FunctionIsEntryPoint(opt::IRContext* context, uint32_t function_id) {
574 for (auto& entry_point : context->module()->entry_points()) {
575 if (entry_point.GetSingleWordInOperand(1) == function_id) {
576 return true;
577 }
578 }
579 return false;
580 }
581
582 bool IdIsAvailableAtUse(opt::IRContext* context,
583 opt::Instruction* use_instruction,
584 uint32_t use_input_operand_index, uint32_t id) {
585 assert(context->get_instr_block(use_instruction) &&
586 "|use_instruction| must be in a basic block");
587
588 auto defining_instruction = context->get_def_use_mgr()->GetDef(id);
589 auto enclosing_function =
590 context->get_instr_block(use_instruction)->GetParent();
591 // If the id a function parameter, it needs to be associated with the
592 // function containing the use.
593 if (defining_instruction->opcode() == SpvOpFunctionParameter) {
594 return InstructionIsFunctionParameter(defining_instruction,
595 enclosing_function);
596 }
597 if (!context->get_instr_block(id)) {
598 // The id must be at global scope.
599 return true;
600 }
601 if (defining_instruction == use_instruction) {
602 // It is not OK for a definition to use itself.
603 return false;
604 }
605 auto dominator_analysis = context->GetDominatorAnalysis(enclosing_function);
606 if (!dominator_analysis->IsReachable(
607 context->get_instr_block(use_instruction)) ||
608 !dominator_analysis->IsReachable(context->get_instr_block(id))) {
609 // Skip unreachable blocks.
610 return false;
611 }
612 if (use_instruction->opcode() == SpvOpPhi) {
613 // In the case where the use is an operand to OpPhi, it is actually the
614 // *parent* block associated with the operand that must be dominated by
615 // the synonym.
616 auto parent_block =
617 use_instruction->GetSingleWordInOperand(use_input_operand_index + 1);
618 return dominator_analysis->Dominates(
619 context->get_instr_block(defining_instruction)->id(), parent_block);
620 }
621 return dominator_analysis->Dominates(defining_instruction, use_instruction);
622 }
623
624 bool IdIsAvailableBeforeInstruction(opt::IRContext* context,
625 opt::Instruction* instruction,
626 uint32_t id) {
627 assert(context->get_instr_block(instruction) &&
628 "|instruction| must be in a basic block");
629
630 auto id_definition = context->get_def_use_mgr()->GetDef(id);
631 auto function_enclosing_instruction =
632 context->get_instr_block(instruction)->GetParent();
633 // If the id a function parameter, it needs to be associated with the
634 // function containing the instruction.
635 if (id_definition->opcode() == SpvOpFunctionParameter) {
636 return InstructionIsFunctionParameter(id_definition,
637 function_enclosing_instruction);
638 }
639 if (!context->get_instr_block(id)) {
640 // The id is at global scope.
641 return true;
642 }
643 if (id_definition == instruction) {
644 // The instruction is not available right before its own definition.
645 return false;
646 }
647 const auto* dominator_analysis =
648 context->GetDominatorAnalysis(function_enclosing_instruction);
649 if (dominator_analysis->IsReachable(context->get_instr_block(instruction)) &&
650 dominator_analysis->IsReachable(context->get_instr_block(id)) &&
651 dominator_analysis->Dominates(id_definition, instruction)) {
652 // The id's definition dominates the instruction, and both the definition
653 // and the instruction are in reachable blocks, thus the id is available at
654 // the instruction.
655 return true;
656 }
657 if (id_definition->opcode() == SpvOpVariable &&
658 function_enclosing_instruction ==
659 context->get_instr_block(id)->GetParent()) {
660 assert(!dominator_analysis->IsReachable(
661 context->get_instr_block(instruction)) &&
662 "If the instruction were in a reachable block we should already "
663 "have returned true.");
664 // The id is a variable and it is in the same function as |instruction|.
665 // This is OK despite |instruction| being unreachable.
666 return true;
667 }
668 return false;
669 }
670
671 bool InstructionIsFunctionParameter(opt::Instruction* instruction,
672 opt::Function* function) {
673 if (instruction->opcode() != SpvOpFunctionParameter) {
674 return false;
675 }
676 bool found_parameter = false;
677 function->ForEachParam(
678 [instruction, &found_parameter](opt::Instruction* param) {
679 if (param == instruction) {
680 found_parameter = true;
681 }
682 });
683 return found_parameter;
684 }
685
686 uint32_t GetTypeId(opt::IRContext* context, uint32_t result_id) {
687 const auto* inst = context->get_def_use_mgr()->GetDef(result_id);
688 assert(inst && "|result_id| is invalid");
689 return inst->type_id();
690 }
691
692 uint32_t GetPointeeTypeIdFromPointerType(opt::Instruction* pointer_type_inst) {
693 assert(pointer_type_inst && pointer_type_inst->opcode() == SpvOpTypePointer &&
694 "Precondition: |pointer_type_inst| must be OpTypePointer.");
695 return pointer_type_inst->GetSingleWordInOperand(1);
696 }
697
698 uint32_t GetPointeeTypeIdFromPointerType(opt::IRContext* context,
699 uint32_t pointer_type_id) {
700 return GetPointeeTypeIdFromPointerType(
701 context->get_def_use_mgr()->GetDef(pointer_type_id));
702 }
703
704 SpvStorageClass GetStorageClassFromPointerType(
705 opt::Instruction* pointer_type_inst) {
706 assert(pointer_type_inst && pointer_type_inst->opcode() == SpvOpTypePointer &&
707 "Precondition: |pointer_type_inst| must be OpTypePointer.");
708 return static_cast<SpvStorageClass>(
709 pointer_type_inst->GetSingleWordInOperand(0));
710 }
711
712 SpvStorageClass GetStorageClassFromPointerType(opt::IRContext* context,
713 uint32_t pointer_type_id) {
714 return GetStorageClassFromPointerType(
715 context->get_def_use_mgr()->GetDef(pointer_type_id));
716 }
717
718 uint32_t MaybeGetPointerType(opt::IRContext* context, uint32_t pointee_type_id,
719 SpvStorageClass storage_class) {
720 for (auto& inst : context->types_values()) {
721 switch (inst.opcode()) {
722 case SpvOpTypePointer:
723 if (inst.GetSingleWordInOperand(0) == storage_class &&
724 inst.GetSingleWordInOperand(1) == pointee_type_id) {
725 return inst.result_id();
726 }
727 break;
728 default:
729 break;
730 }
731 }
732 return 0;
733 }
734
735 uint32_t InOperandIndexFromOperandIndex(const opt::Instruction& inst,
736 uint32_t absolute_index) {
737 // Subtract the number of non-input operands from the index
738 return absolute_index - inst.NumOperands() + inst.NumInOperands();
739 }
740
741 bool IsNullConstantSupported(const opt::analysis::Type& type) {
742 return type.AsBool() || type.AsInteger() || type.AsFloat() ||
743 type.AsMatrix() || type.AsVector() || type.AsArray() ||
744 type.AsStruct() || type.AsPointer() || type.AsEvent() ||
745 type.AsDeviceEvent() || type.AsReserveId() || type.AsQueue();
746 }
747
748 bool GlobalVariablesMustBeDeclaredInEntryPointInterfaces(
749 const opt::IRContext* ir_context) {
750 // TODO(afd): We capture the universal environments for which this requirement
751 // holds. The check should be refined on demand for other target
752 // environments.
753 switch (ir_context->grammar().target_env()) {
754 case SPV_ENV_UNIVERSAL_1_0:
755 case SPV_ENV_UNIVERSAL_1_1:
756 case SPV_ENV_UNIVERSAL_1_2:
757 case SPV_ENV_UNIVERSAL_1_3:
758 return false;
759 default:
760 return true;
761 }
762 }
763
764 void AddVariableIdToEntryPointInterfaces(opt::IRContext* context, uint32_t id) {
765 if (GlobalVariablesMustBeDeclaredInEntryPointInterfaces(context)) {
766 // Conservatively add this global to the interface of every entry point in
767 // the module. This means that the global is available for other
768 // transformations to use.
769 //
770 // A downside of this is that the global will be in the interface even if it
771 // ends up never being used.
772 //
773 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3111) revisit
774 // this if a more thorough approach to entry point interfaces is taken.
775 for (auto& entry_point : context->module()->entry_points()) {
776 entry_point.AddOperand({SPV_OPERAND_TYPE_ID, {id}});
777 }
778 }
779 }
780
781 void AddGlobalVariable(opt::IRContext* context, uint32_t result_id,
782 uint32_t type_id, SpvStorageClass storage_class,
783 uint32_t initializer_id) {
784 // Check various preconditions.
785 assert(result_id != 0 && "Result id can't be 0");
786
787 assert((storage_class == SpvStorageClassPrivate ||
788 storage_class == SpvStorageClassWorkgroup) &&
789 "Variable's storage class must be either Private or Workgroup");
790
791 auto* type_inst = context->get_def_use_mgr()->GetDef(type_id);
792 (void)type_inst; // Variable becomes unused in release mode.
793 assert(type_inst && type_inst->opcode() == SpvOpTypePointer &&
794 GetStorageClassFromPointerType(type_inst) == storage_class &&
795 "Variable's type is invalid");
796
797 if (storage_class == SpvStorageClassWorkgroup) {
798 assert(initializer_id == 0);
799 }
800
801 if (initializer_id != 0) {
802 const auto* constant_inst =
803 context->get_def_use_mgr()->GetDef(initializer_id);
804 (void)constant_inst; // Variable becomes unused in release mode.
805 assert(constant_inst && spvOpcodeIsConstant(constant_inst->opcode()) &&
806 GetPointeeTypeIdFromPointerType(type_inst) ==
807 constant_inst->type_id() &&
808 "Initializer is invalid");
809 }
810
811 opt::Instruction::OperandList operands = {
812 {SPV_OPERAND_TYPE_STORAGE_CLASS, {static_cast<uint32_t>(storage_class)}}};
813
814 if (initializer_id) {
815 operands.push_back({SPV_OPERAND_TYPE_ID, {initializer_id}});
816 }
817
818 context->module()->AddGlobalValue(MakeUnique<opt::Instruction>(
819 context, SpvOpVariable, type_id, result_id, std::move(operands)));
820
821 AddVariableIdToEntryPointInterfaces(context, result_id);
822 UpdateModuleIdBound(context, result_id);
823 }
824
825 void AddLocalVariable(opt::IRContext* context, uint32_t result_id,
826 uint32_t type_id, uint32_t function_id,
827 uint32_t initializer_id) {
828 // Check various preconditions.
829 assert(result_id != 0 && "Result id can't be 0");
830
831 auto* type_inst = context->get_def_use_mgr()->GetDef(type_id);
832 (void)type_inst; // Variable becomes unused in release mode.
833 assert(type_inst && type_inst->opcode() == SpvOpTypePointer &&
834 GetStorageClassFromPointerType(type_inst) == SpvStorageClassFunction &&
835 "Variable's type is invalid");
836
837 const auto* constant_inst =
838 context->get_def_use_mgr()->GetDef(initializer_id);
839 (void)constant_inst; // Variable becomes unused in release mode.
840 assert(constant_inst && spvOpcodeIsConstant(constant_inst->opcode()) &&
841 GetPointeeTypeIdFromPointerType(type_inst) ==
842 constant_inst->type_id() &&
843 "Initializer is invalid");
844
845 auto* function = FindFunction(context, function_id);
846 assert(function && "Function id is invalid");
847
848 function->begin()->begin()->InsertBefore(MakeUnique<opt::Instruction>(
849 context, SpvOpVariable, type_id, result_id,
850 opt::Instruction::OperandList{
851 {SPV_OPERAND_TYPE_STORAGE_CLASS, {SpvStorageClassFunction}},
852 {SPV_OPERAND_TYPE_ID, {initializer_id}}}));
853
854 UpdateModuleIdBound(context, result_id);
855 }
856
857 bool HasDuplicates(const std::vector<uint32_t>& arr) {
858 return std::unordered_set<uint32_t>(arr.begin(), arr.end()).size() !=
859 arr.size();
860 }
861
862 bool IsPermutationOfRange(const std::vector<uint32_t>& arr, uint32_t lo,
863 uint32_t hi) {
864 if (arr.empty()) {
865 return lo > hi;
866 }
867
868 if (HasDuplicates(arr)) {
869 return false;
870 }
871
872 auto min_max = std::minmax_element(arr.begin(), arr.end());
873 return arr.size() == hi - lo + 1 && *min_max.first == lo &&
874 *min_max.second == hi;
875 }
876
877 std::vector<opt::Instruction*> GetParameters(opt::IRContext* ir_context,
878 uint32_t function_id) {
879 auto* function = FindFunction(ir_context, function_id);
880 assert(function && "|function_id| is invalid");
881
882 std::vector<opt::Instruction*> result;
883 function->ForEachParam(
884 [&result](opt::Instruction* inst) { result.push_back(inst); });
885
886 return result;
887 }
888
889 void RemoveParameter(opt::IRContext* ir_context, uint32_t parameter_id) {
890 auto* function = GetFunctionFromParameterId(ir_context, parameter_id);
891 assert(function && "|parameter_id| is invalid");
892 assert(!FunctionIsEntryPoint(ir_context, function->result_id()) &&
893 "Can't remove parameter from an entry point function");
894
895 function->RemoveParameter(parameter_id);
896
897 // We've just removed parameters from the function and cleared their memory.
898 // Make sure analyses have no dangling pointers.
899 ir_context->InvalidateAnalysesExceptFor(
900 opt::IRContext::Analysis::kAnalysisNone);
901 }
902
903 std::vector<opt::Instruction*> GetCallers(opt::IRContext* ir_context,
904 uint32_t function_id) {
905 assert(FindFunction(ir_context, function_id) &&
906 "|function_id| is not a result id of a function");
907
908 std::vector<opt::Instruction*> result;
909 ir_context->get_def_use_mgr()->ForEachUser(
910 function_id, [&result, function_id](opt::Instruction* inst) {
911 if (inst->opcode() == SpvOpFunctionCall &&
912 inst->GetSingleWordInOperand(0) == function_id) {
913 result.push_back(inst);
914 }
915 });
916
917 return result;
918 }
919
920 opt::Function* GetFunctionFromParameterId(opt::IRContext* ir_context,
921 uint32_t param_id) {
922 auto* param_inst = ir_context->get_def_use_mgr()->GetDef(param_id);
923 assert(param_inst && "Parameter id is invalid");
924
925 for (auto& function : *ir_context->module()) {
926 if (InstructionIsFunctionParameter(param_inst, &function)) {
927 return &function;
928 }
929 }
930
931 return nullptr;
932 }
933
934 uint32_t UpdateFunctionType(opt::IRContext* ir_context, uint32_t function_id,
935 uint32_t new_function_type_result_id,
936 uint32_t return_type_id,
937 const std::vector<uint32_t>& parameter_type_ids) {
938 // Check some initial constraints.
939 assert(ir_context->get_type_mgr()->GetType(return_type_id) &&
940 "Return type is invalid");
941 for (auto id : parameter_type_ids) {
942 const auto* type = ir_context->get_type_mgr()->GetType(id);
943 (void)type; // Make compilers happy in release mode.
944 // Parameters can't be OpTypeVoid.
945 assert(type && !type->AsVoid() && "Parameter has invalid type");
946 }
947
948 auto* function = FindFunction(ir_context, function_id);
949 assert(function && "|function_id| is invalid");
950
951 auto* old_function_type = GetFunctionType(ir_context, function);
952 assert(old_function_type && "Function has invalid type");
953
954 std::vector<uint32_t> operand_ids = {return_type_id};
955 operand_ids.insert(operand_ids.end(), parameter_type_ids.begin(),
956 parameter_type_ids.end());
957
958 // A trivial case - we change nothing.
959 if (FindFunctionType(ir_context, operand_ids) ==
960 old_function_type->result_id()) {
961 return old_function_type->result_id();
962 }
963
964 if (ir_context->get_def_use_mgr()->NumUsers(old_function_type) == 1 &&
965 FindFunctionType(ir_context, operand_ids) == 0) {
966 // We can change |old_function_type| only if it's used once in the module
967 // and we are certain we won't create a duplicate as a result of the change.
968
969 // Update |old_function_type| in-place.
970 opt::Instruction::OperandList operands;
971 for (auto id : operand_ids) {
972 operands.push_back({SPV_OPERAND_TYPE_ID, {id}});
973 }
974
975 old_function_type->SetInOperands(std::move(operands));
976
977 // |operands| may depend on result ids defined below the |old_function_type|
978 // in the module.
979 old_function_type->RemoveFromList();
980 ir_context->AddType(std::unique_ptr<opt::Instruction>(old_function_type));
981 return old_function_type->result_id();
982 } else {
983 // We can't modify the |old_function_type| so we have to either use an
984 // existing one or create a new one.
985 auto type_id = FindOrCreateFunctionType(
986 ir_context, new_function_type_result_id, operand_ids);
987 assert(type_id != old_function_type->result_id() &&
988 "We should've handled this case above");
989
990 function->DefInst().SetInOperand(1, {type_id});
991
992 // DefUseManager hasn't been updated yet, so if the following condition is
993 // true, then |old_function_type| will have no users when this function
994 // returns. We might as well remove it.
995 if (ir_context->get_def_use_mgr()->NumUsers(old_function_type) == 1) {
996 ir_context->KillInst(old_function_type);
997 }
998
999 return type_id;
1000 }
1001 }
1002
1003 void AddFunctionType(opt::IRContext* ir_context, uint32_t result_id,
1004 const std::vector<uint32_t>& type_ids) {
1005 assert(result_id != 0 && "Result id can't be 0");
1006 assert(!type_ids.empty() &&
1007 "OpTypeFunction always has at least one operand - function's return "
1008 "type");
1009 assert(IsNonFunctionTypeId(ir_context, type_ids[0]) &&
1010 "Return type must not be a function");
1011
1012 for (size_t i = 1; i < type_ids.size(); ++i) {
1013 const auto* param_type = ir_context->get_type_mgr()->GetType(type_ids[i]);
1014 (void)param_type; // Make compiler happy in release mode.
1015 assert(param_type && !param_type->AsVoid() && !param_type->AsFunction() &&
1016 "Function parameter can't have a function or void type");
1017 }
1018
1019 opt::Instruction::OperandList operands;
1020 operands.reserve(type_ids.size());
1021 for (auto id : type_ids) {
1022 operands.push_back({SPV_OPERAND_TYPE_ID, {id}});
1023 }
1024
1025 ir_context->AddType(MakeUnique<opt::Instruction>(
1026 ir_context, SpvOpTypeFunction, 0, result_id, std::move(operands)));
1027
1028 UpdateModuleIdBound(ir_context, result_id);
1029 }
1030
1031 uint32_t FindOrCreateFunctionType(opt::IRContext* ir_context,
1032 uint32_t result_id,
1033 const std::vector<uint32_t>& type_ids) {
1034 if (auto existing_id = FindFunctionType(ir_context, type_ids)) {
1035 return existing_id;
1036 }
1037 AddFunctionType(ir_context, result_id, type_ids);
1038 return result_id;
1039 }
1040
1041 uint32_t MaybeGetIntegerType(opt::IRContext* ir_context, uint32_t width,
1042 bool is_signed) {
1043 opt::analysis::Integer type(width, is_signed);
1044 return ir_context->get_type_mgr()->GetId(&type);
1045 }
1046
1047 uint32_t MaybeGetFloatType(opt::IRContext* ir_context, uint32_t width) {
1048 opt::analysis::Float type(width);
1049 return ir_context->get_type_mgr()->GetId(&type);
1050 }
1051
1052 uint32_t MaybeGetBoolType(opt::IRContext* ir_context) {
1053 opt::analysis::Bool type;
1054 return ir_context->get_type_mgr()->GetId(&type);
1055 }
1056
1057 uint32_t MaybeGetVectorType(opt::IRContext* ir_context,
1058 uint32_t component_type_id,
1059 uint32_t element_count) {
1060 const auto* component_type =
1061 ir_context->get_type_mgr()->GetType(component_type_id);
1062 assert(component_type &&
1063 (component_type->AsInteger() || component_type->AsFloat() ||
1064 component_type->AsBool()) &&
1065 "|component_type_id| is invalid");
1066 assert(element_count >= 2 && element_count <= 4 &&
1067 "Precondition: component count must be in range [2, 4].");
1068 opt::analysis::Vector type(component_type, element_count);
1069 return ir_context->get_type_mgr()->GetId(&type);
1070 }
1071
1072 uint32_t MaybeGetStructType(opt::IRContext* ir_context,
1073 const std::vector<uint32_t>& component_type_ids) {
1074 for (auto& type_or_value : ir_context->types_values()) {
1075 if (type_or_value.opcode() != SpvOpTypeStruct ||
1076 type_or_value.NumInOperands() !=
1077 static_cast<uint32_t>(component_type_ids.size())) {
1078 continue;
1079 }
1080 bool all_components_match = true;
1081 for (uint32_t i = 0; i < component_type_ids.size(); i++) {
1082 if (type_or_value.GetSingleWordInOperand(i) != component_type_ids[i]) {
1083 all_components_match = false;
1084 break;
1085 }
1086 }
1087 if (all_components_match) {
1088 return type_or_value.result_id();
1089 }
1090 }
1091 return 0;
1092 }
1093
1094 uint32_t MaybeGetVoidType(opt::IRContext* ir_context) {
1095 opt::analysis::Void type;
1096 return ir_context->get_type_mgr()->GetId(&type);
1097 }
1098
1099 uint32_t MaybeGetZeroConstant(
1100 opt::IRContext* ir_context,
1101 const TransformationContext& transformation_context,
1102 uint32_t scalar_or_composite_type_id, bool is_irrelevant) {
1103 const auto* type_inst =
1104 ir_context->get_def_use_mgr()->GetDef(scalar_or_composite_type_id);
1105 assert(type_inst && "|scalar_or_composite_type_id| is invalid");
1106
1107 switch (type_inst->opcode()) {
1108 case SpvOpTypeBool:
1109 return MaybeGetBoolConstant(ir_context, transformation_context, false,
1110 is_irrelevant);
1111 case SpvOpTypeFloat:
1112 case SpvOpTypeInt: {
1113 const auto width = type_inst->GetSingleWordInOperand(0);
1114 std::vector<uint32_t> words = {0};
1115 if (width > 32) {
1116 words.push_back(0);
1117 }
1118
1119 return MaybeGetScalarConstant(ir_context, transformation_context, words,
1120 scalar_or_composite_type_id, is_irrelevant);
1121 }
1122 case SpvOpTypeStruct: {
1123 std::vector<uint32_t> component_ids;
1124 for (uint32_t i = 0; i < type_inst->NumInOperands(); ++i) {
1125 const auto component_type_id = type_inst->GetSingleWordInOperand(i);
1126
1127 auto component_id =
1128 MaybeGetZeroConstant(ir_context, transformation_context,
1129 component_type_id, is_irrelevant);
1130
1131 if (component_id == 0 && is_irrelevant) {
1132 // Irrelevant constants can use either relevant or irrelevant
1133 // constituents.
1134 component_id = MaybeGetZeroConstant(
1135 ir_context, transformation_context, component_type_id, false);
1136 }
1137
1138 if (component_id == 0) {
1139 return 0;
1140 }
1141
1142 component_ids.push_back(component_id);
1143 }
1144
1145 return MaybeGetCompositeConstant(
1146 ir_context, transformation_context, component_ids,
1147 scalar_or_composite_type_id, is_irrelevant);
1148 }
1149 case SpvOpTypeMatrix:
1150 case SpvOpTypeVector: {
1151 const auto component_type_id = type_inst->GetSingleWordInOperand(0);
1152
1153 auto component_id = MaybeGetZeroConstant(
1154 ir_context, transformation_context, component_type_id, is_irrelevant);
1155
1156 if (component_id == 0 && is_irrelevant) {
1157 // Irrelevant constants can use either relevant or irrelevant
1158 // constituents.
1159 component_id = MaybeGetZeroConstant(ir_context, transformation_context,
1160 component_type_id, false);
1161 }
1162
1163 if (component_id == 0) {
1164 return 0;
1165 }
1166
1167 const auto component_count = type_inst->GetSingleWordInOperand(1);
1168 return MaybeGetCompositeConstant(
1169 ir_context, transformation_context,
1170 std::vector<uint32_t>(component_count, component_id),
1171 scalar_or_composite_type_id, is_irrelevant);
1172 }
1173 case SpvOpTypeArray: {
1174 const auto component_type_id = type_inst->GetSingleWordInOperand(0);
1175
1176 auto component_id = MaybeGetZeroConstant(
1177 ir_context, transformation_context, component_type_id, is_irrelevant);
1178
1179 if (component_id == 0 && is_irrelevant) {
1180 // Irrelevant constants can use either relevant or irrelevant
1181 // constituents.
1182 component_id = MaybeGetZeroConstant(ir_context, transformation_context,
1183 component_type_id, false);
1184 }
1185
1186 if (component_id == 0) {
1187 return 0;
1188 }
1189
1190 return MaybeGetCompositeConstant(
1191 ir_context, transformation_context,
1192 std::vector<uint32_t>(GetArraySize(*type_inst, ir_context),
1193 component_id),
1194 scalar_or_composite_type_id, is_irrelevant);
1195 }
1196 default:
1197 assert(false && "Type is not supported");
1198 return 0;
1199 }
1200 }
1201
1202 bool CanCreateConstant(opt::IRContext* ir_context, uint32_t type_id) {
1203 opt::Instruction* type_instr = ir_context->get_def_use_mgr()->GetDef(type_id);
1204 assert(type_instr != nullptr && "The type must exist.");
1205 assert(spvOpcodeGeneratesType(type_instr->opcode()) &&
1206 "A type-generating opcode was expected.");
1207 switch (type_instr->opcode()) {
1208 case SpvOpTypeBool:
1209 case SpvOpTypeInt:
1210 case SpvOpTypeFloat:
1211 case SpvOpTypeMatrix:
1212 case SpvOpTypeVector:
1213 return true;
1214 case SpvOpTypeArray:
1215 return CanCreateConstant(ir_context,
1216 type_instr->GetSingleWordInOperand(0));
1217 case SpvOpTypeStruct:
1218 if (HasBlockOrBufferBlockDecoration(ir_context, type_id)) {
1219 return false;
1220 }
1221 for (uint32_t index = 0; index < type_instr->NumInOperands(); index++) {
1222 if (!CanCreateConstant(ir_context,
1223 type_instr->GetSingleWordInOperand(index))) {
1224 return false;
1225 }
1226 }
1227 return true;
1228 default:
1229 return false;
1230 }
1231 }
1232
1233 uint32_t MaybeGetScalarConstant(
1234 opt::IRContext* ir_context,
1235 const TransformationContext& transformation_context,
1236 const std::vector<uint32_t>& words, uint32_t scalar_type_id,
1237 bool is_irrelevant) {
1238 const auto* type = ir_context->get_type_mgr()->GetType(scalar_type_id);
1239 assert(type && "|scalar_type_id| is invalid");
1240
1241 if (const auto* int_type = type->AsInteger()) {
1242 return MaybeGetIntegerConstant(ir_context, transformation_context, words,
1243 int_type->width(), int_type->IsSigned(),
1244 is_irrelevant);
1245 } else if (const auto* float_type = type->AsFloat()) {
1246 return MaybeGetFloatConstant(ir_context, transformation_context, words,
1247 float_type->width(), is_irrelevant);
1248 } else {
1249 assert(type->AsBool() && words.size() == 1 &&
1250 "|scalar_type_id| doesn't represent a scalar type");
1251 return MaybeGetBoolConstant(ir_context, transformation_context, words[0],
1252 is_irrelevant);
1253 }
1254 }
1255
1256 uint32_t MaybeGetCompositeConstant(
1257 opt::IRContext* ir_context,
1258 const TransformationContext& transformation_context,
1259 const std::vector<uint32_t>& component_ids, uint32_t composite_type_id,
1260 bool is_irrelevant) {
1261 const auto* type = ir_context->get_type_mgr()->GetType(composite_type_id);
1262 (void)type; // Make compilers happy in release mode.
1263 assert(IsCompositeType(type) && "|composite_type_id| is invalid");
1264
1265 for (const auto& inst : ir_context->types_values()) {
1266 if (inst.opcode() == SpvOpConstantComposite &&
1267 inst.type_id() == composite_type_id &&
1268 transformation_context.GetFactManager()->IdIsIrrelevant(
1269 inst.result_id()) == is_irrelevant &&
1270 inst.NumInOperands() == component_ids.size()) {
1271 bool is_match = true;
1272
1273 for (uint32_t i = 0; i < inst.NumInOperands(); ++i) {
1274 if (inst.GetSingleWordInOperand(i) != component_ids[i]) {
1275 is_match = false;
1276 break;
1277 }
1278 }
1279
1280 if (is_match) {
1281 return inst.result_id();
1282 }
1283 }
1284 }
1285
1286 return 0;
1287 }
1288
1289 uint32_t MaybeGetIntegerConstant(
1290 opt::IRContext* ir_context,
1291 const TransformationContext& transformation_context,
1292 const std::vector<uint32_t>& words, uint32_t width, bool is_signed,
1293 bool is_irrelevant) {
1294 if (auto type_id = MaybeGetIntegerType(ir_context, width, is_signed)) {
1295 return MaybeGetOpConstant(ir_context, transformation_context, words,
1296 type_id, is_irrelevant);
1297 }
1298
1299 return 0;
1300 }
1301
1302 uint32_t MaybeGetIntegerConstantFromValueAndType(opt::IRContext* ir_context,
1303 uint32_t value,
1304 uint32_t int_type_id) {
1305 auto int_type_inst = ir_context->get_def_use_mgr()->GetDef(int_type_id);
1306
1307 assert(int_type_inst && "The given type id must exist.");
1308
1309 auto int_type = ir_context->get_type_mgr()
1310 ->GetType(int_type_inst->result_id())
1311 ->AsInteger();
1312
1313 assert(int_type && int_type->width() == 32 &&
1314 "The given type id must correspond to an 32-bit integer type.");
1315
1316 opt::analysis::IntConstant constant(int_type, {value});
1317
1318 // Check that the constant exists in the module.
1319 if (!ir_context->get_constant_mgr()->FindConstant(&constant)) {
1320 return 0;
1321 }
1322
1323 return ir_context->get_constant_mgr()
1324 ->GetDefiningInstruction(&constant)
1325 ->result_id();
1326 }
1327
1328 uint32_t MaybeGetFloatConstant(
1329 opt::IRContext* ir_context,
1330 const TransformationContext& transformation_context,
1331 const std::vector<uint32_t>& words, uint32_t width, bool is_irrelevant) {
1332 if (auto type_id = MaybeGetFloatType(ir_context, width)) {
1333 return MaybeGetOpConstant(ir_context, transformation_context, words,
1334 type_id, is_irrelevant);
1335 }
1336
1337 return 0;
1338 }
1339
1340 uint32_t MaybeGetBoolConstant(
1341 opt::IRContext* ir_context,
1342 const TransformationContext& transformation_context, bool value,
1343 bool is_irrelevant) {
1344 if (auto type_id = MaybeGetBoolType(ir_context)) {
1345 for (const auto& inst : ir_context->types_values()) {
1346 if (inst.opcode() == (value ? SpvOpConstantTrue : SpvOpConstantFalse) &&
1347 inst.type_id() == type_id &&
1348 transformation_context.GetFactManager()->IdIsIrrelevant(
1349 inst.result_id()) == is_irrelevant) {
1350 return inst.result_id();
1351 }
1352 }
1353 }
1354
1355 return 0;
1356 }
1357
1358 void AddIntegerType(opt::IRContext* ir_context, uint32_t result_id,
1359 uint32_t width, bool is_signed) {
1360 ir_context->module()->AddType(MakeUnique<opt::Instruction>(
1361 ir_context, SpvOpTypeInt, 0, result_id,
1362 opt::Instruction::OperandList{
1363 {SPV_OPERAND_TYPE_LITERAL_INTEGER, {width}},
1364 {SPV_OPERAND_TYPE_LITERAL_INTEGER, {is_signed ? 1u : 0u}}}));
1365
1366 UpdateModuleIdBound(ir_context, result_id);
1367 }
1368
1369 void AddFloatType(opt::IRContext* ir_context, uint32_t result_id,
1370 uint32_t width) {
1371 ir_context->module()->AddType(MakeUnique<opt::Instruction>(
1372 ir_context, SpvOpTypeFloat, 0, result_id,
1373 opt::Instruction::OperandList{
1374 {SPV_OPERAND_TYPE_LITERAL_INTEGER, {width}}}));
1375
1376 UpdateModuleIdBound(ir_context, result_id);
1377 }
1378
1379 void AddVectorType(opt::IRContext* ir_context, uint32_t result_id,
1380 uint32_t component_type_id, uint32_t element_count) {
1381 const auto* component_type =
1382 ir_context->get_type_mgr()->GetType(component_type_id);
1383 (void)component_type; // Make compiler happy in release mode.
1384 assert(component_type &&
1385 (component_type->AsInteger() || component_type->AsFloat() ||
1386 component_type->AsBool()) &&
1387 "|component_type_id| is invalid");
1388 assert(element_count >= 2 && element_count <= 4 &&
1389 "Precondition: component count must be in range [2, 4].");
1390 ir_context->module()->AddType(MakeUnique<opt::Instruction>(
1391 ir_context, SpvOpTypeVector, 0, result_id,
1392 opt::Instruction::OperandList{
1393 {SPV_OPERAND_TYPE_ID, {component_type_id}},
1394 {SPV_OPERAND_TYPE_LITERAL_INTEGER, {element_count}}}));
1395
1396 UpdateModuleIdBound(ir_context, result_id);
1397 }
1398
1399 void AddStructType(opt::IRContext* ir_context, uint32_t result_id,
1400 const std::vector<uint32_t>& component_type_ids) {
1401 opt::Instruction::OperandList operands;
1402 operands.reserve(component_type_ids.size());
1403
1404 for (auto type_id : component_type_ids) {
1405 const auto* type = ir_context->get_type_mgr()->GetType(type_id);
1406 (void)type; // Make compiler happy in release mode.
1407 assert(type && !type->AsFunction() && "Component's type id is invalid");
1408
1409 if (type->AsStruct()) {
1410 // From the spec for the BuiltIn decoration:
1411 // - When applied to a structure-type member, that structure type cannot
1412 // be contained as a member of another structure type.
1413 assert(!MembersHaveBuiltInDecoration(ir_context, type_id) &&
1414 "A member struct has BuiltIn members");
1415 }
1416
1417 operands.push_back({SPV_OPERAND_TYPE_ID, {type_id}});
1418 }
1419
1420 ir_context->AddType(MakeUnique<opt::Instruction>(
1421 ir_context, SpvOpTypeStruct, 0, result_id, std::move(operands)));
1422
1423 UpdateModuleIdBound(ir_context, result_id);
1424 }
1425
1426 std::vector<uint32_t> IntToWords(uint64_t value, uint32_t width,
1427 bool is_signed) {
1428 assert(width <= 64 && "The bit width should not be more than 64 bits");
1429
1430 // Sign-extend or zero-extend the last |width| bits of |value|, depending on
1431 // |is_signed|.
1432 if (is_signed) {
1433 // Sign-extend by shifting left and then shifting right, interpreting the
1434 // integer as signed.
1435 value = static_cast<int64_t>(value << (64 - width)) >> (64 - width);
1436 } else {
1437 // Zero-extend by shifting left and then shifting right, interpreting the
1438 // integer as unsigned.
1439 value = (value << (64 - width)) >> (64 - width);
1440 }
1441
1442 std::vector<uint32_t> result;
1443 result.push_back(static_cast<uint32_t>(value));
1444 if (width > 32) {
1445 result.push_back(static_cast<uint32_t>(value >> 32));
1446 }
1447 return result;
1448 }
1449
1450 bool TypesAreEqualUpToSign(opt::IRContext* ir_context, uint32_t type1_id,
1451 uint32_t type2_id) {
1452 if (type1_id == type2_id) {
1453 return true;
1454 }
1455
1456 auto type1 = ir_context->get_type_mgr()->GetType(type1_id);
1457 auto type2 = ir_context->get_type_mgr()->GetType(type2_id);
1458
1459 // Integer scalar types must have the same width
1460 if (type1->AsInteger() && type2->AsInteger()) {
1461 return type1->AsInteger()->width() == type2->AsInteger()->width();
1462 }
1463
1464 // Integer vector types must have the same number of components and their
1465 // component types must be integers with the same width.
1466 if (type1->AsVector() && type2->AsVector()) {
1467 auto component_type1 = type1->AsVector()->element_type()->AsInteger();
1468 auto component_type2 = type2->AsVector()->element_type()->AsInteger();
1469
1470 // Only check the component count and width if they are integer.
1471 if (component_type1 && component_type2) {
1472 return type1->AsVector()->element_count() ==
1473 type2->AsVector()->element_count() &&
1474 component_type1->width() == component_type2->width();
1475 }
1476 }
1477
1478 // In all other cases, the types cannot be considered equal.
1479 return false;
1480 }
1481
1482 std::map<uint32_t, uint32_t> RepeatedUInt32PairToMap(
1483 const google::protobuf::RepeatedPtrField<protobufs::UInt32Pair>& data) {
1484 std::map<uint32_t, uint32_t> result;
1485
1486 for (const auto& entry : data) {
1487 result[entry.first()] = entry.second();
1488 }
1489
1490 return result;
1491 }
1492
1493 google::protobuf::RepeatedPtrField<protobufs::UInt32Pair>
1494 MapToRepeatedUInt32Pair(const std::map<uint32_t, uint32_t>& data) {
1495 google::protobuf::RepeatedPtrField<protobufs::UInt32Pair> result;
1496
1497 for (const auto& entry : data) {
1498 protobufs::UInt32Pair pair;
1499 pair.set_first(entry.first);
1500 pair.set_second(entry.second);
1501 *result.Add() = std::move(pair);
1502 }
1503
1504 return result;
1505 }
1506
1507 opt::Instruction* GetLastInsertBeforeInstruction(opt::IRContext* ir_context,
1508 uint32_t block_id,
1509 SpvOp opcode) {
1510 // CFG::block uses std::map::at which throws an exception when |block_id| is
1511 // invalid. The error message is unhelpful, though. Thus, we test that
1512 // |block_id| is valid here.
1513 const auto* label_inst = ir_context->get_def_use_mgr()->GetDef(block_id);
1514 (void)label_inst; // Make compilers happy in release mode.
1515 assert(label_inst && label_inst->opcode() == SpvOpLabel &&
1516 "|block_id| is invalid");
1517
1518 auto* block = ir_context->cfg()->block(block_id);
1519 auto it = block->rbegin();
1520 assert(it != block->rend() && "Basic block can't be empty");
1521
1522 if (block->GetMergeInst()) {
1523 ++it;
1524 assert(it != block->rend() &&
1525 "|block| must have at least two instructions:"
1526 "terminator and a merge instruction");
1527 }
1528
1529 return CanInsertOpcodeBeforeInstruction(opcode, &*it) ? &*it : nullptr;
1530 }
1531
1532 bool IdUseCanBeReplaced(opt::IRContext* ir_context,
1533 const TransformationContext& transformation_context,
1534 opt::Instruction* use_instruction,
1535 uint32_t use_in_operand_index) {
1536 if (spvOpcodeIsAccessChain(use_instruction->opcode()) &&
1537 use_in_operand_index > 0) {
1538 // A replacement for an irrelevant index in OpAccessChain must be clamped
1539 // first.
1540 if (transformation_context.GetFactManager()->IdIsIrrelevant(
1541 use_instruction->GetSingleWordInOperand(use_in_operand_index))) {
1542 return false;
1543 }
1544
1545 // This is an access chain index. If the (sub-)object being accessed by the
1546 // given index has struct type then we cannot replace the use, as it needs
1547 // to be an OpConstant.
1548
1549 // Get the top-level composite type that is being accessed.
1550 auto object_being_accessed = ir_context->get_def_use_mgr()->GetDef(
1551 use_instruction->GetSingleWordInOperand(0));
1552 auto pointer_type =
1553 ir_context->get_type_mgr()->GetType(object_being_accessed->type_id());
1554 assert(pointer_type->AsPointer());
1555 auto composite_type_being_accessed =
1556 pointer_type->AsPointer()->pointee_type();
1557
1558 // Now walk the access chain, tracking the type of each sub-object of the
1559 // composite that is traversed, until the index of interest is reached.
1560 for (uint32_t index_in_operand = 1; index_in_operand < use_in_operand_index;
1561 index_in_operand++) {
1562 // For vectors, matrices and arrays, getting the type of the sub-object is
1563 // trivial. For the struct case, the sub-object type is field-sensitive,
1564 // and depends on the constant index that is used.
1565 if (composite_type_being_accessed->AsVector()) {
1566 composite_type_being_accessed =
1567 composite_type_being_accessed->AsVector()->element_type();
1568 } else if (composite_type_being_accessed->AsMatrix()) {
1569 composite_type_being_accessed =
1570 composite_type_being_accessed->AsMatrix()->element_type();
1571 } else if (composite_type_being_accessed->AsArray()) {
1572 composite_type_being_accessed =
1573 composite_type_being_accessed->AsArray()->element_type();
1574 } else if (composite_type_being_accessed->AsRuntimeArray()) {
1575 composite_type_being_accessed =
1576 composite_type_being_accessed->AsRuntimeArray()->element_type();
1577 } else {
1578 assert(composite_type_being_accessed->AsStruct());
1579 auto constant_index_instruction = ir_context->get_def_use_mgr()->GetDef(
1580 use_instruction->GetSingleWordInOperand(index_in_operand));
1581 assert(constant_index_instruction->opcode() == SpvOpConstant);
1582 uint32_t member_index =
1583 constant_index_instruction->GetSingleWordInOperand(0);
1584 composite_type_being_accessed =
1585 composite_type_being_accessed->AsStruct()
1586 ->element_types()[member_index];
1587 }
1588 }
1589
1590 // We have found the composite type being accessed by the index we are
1591 // considering replacing. If it is a struct, then we cannot do the
1592 // replacement as struct indices must be constants.
1593 if (composite_type_being_accessed->AsStruct()) {
1594 return false;
1595 }
1596 }
1597
1598 if (use_instruction->opcode() == SpvOpFunctionCall &&
1599 use_in_operand_index > 0) {
1600 // This is a function call argument. It is not allowed to have pointer
1601 // type.
1602
1603 // Get the definition of the function being called.
1604 auto function = ir_context->get_def_use_mgr()->GetDef(
1605 use_instruction->GetSingleWordInOperand(0));
1606 // From the function definition, get the function type.
1607 auto function_type = ir_context->get_def_use_mgr()->GetDef(
1608 function->GetSingleWordInOperand(1));
1609 // OpTypeFunction's 0-th input operand is the function return type, and the
1610 // function argument types follow. Because the arguments to OpFunctionCall
1611 // start from input operand 1, we can use |use_in_operand_index| to get the
1612 // type associated with this function argument.
1613 auto parameter_type = ir_context->get_type_mgr()->GetType(
1614 function_type->GetSingleWordInOperand(use_in_operand_index));
1615 if (parameter_type->AsPointer()) {
1616 return false;
1617 }
1618 }
1619
1620 if (use_instruction->opcode() == SpvOpImageTexelPointer &&
1621 use_in_operand_index == 2) {
1622 // The OpImageTexelPointer instruction has a Sample parameter that in some
1623 // situations must be an id for the value 0. To guard against disrupting
1624 // that requirement, we do not replace this argument to that instruction.
1625 return false;
1626 }
1627
1628 return true;
1629 }
1630
1631 bool MembersHaveBuiltInDecoration(opt::IRContext* ir_context,
1632 uint32_t struct_type_id) {
1633 const auto* type_inst = ir_context->get_def_use_mgr()->GetDef(struct_type_id);
1634 assert(type_inst && type_inst->opcode() == SpvOpTypeStruct &&
1635 "|struct_type_id| is not a result id of an OpTypeStruct");
1636
1637 uint32_t builtin_count = 0;
1638 ir_context->get_def_use_mgr()->ForEachUser(
1639 type_inst,
1640 [struct_type_id, &builtin_count](const opt::Instruction* user) {
1641 if (user->opcode() == SpvOpMemberDecorate &&
1642 user->GetSingleWordInOperand(0) == struct_type_id &&
1643 static_cast<SpvDecoration>(user->GetSingleWordInOperand(2)) ==
1644 SpvDecorationBuiltIn) {
1645 ++builtin_count;
1646 }
1647 });
1648
1649 assert((builtin_count == 0 || builtin_count == type_inst->NumInOperands()) &&
1650 "The module is invalid: either none or all of the members of "
1651 "|struct_type_id| may be builtin");
1652
1653 return builtin_count != 0;
1654 }
1655
1656 bool HasBlockOrBufferBlockDecoration(opt::IRContext* ir_context, uint32_t id) {
1657 for (auto decoration : {SpvDecorationBlock, SpvDecorationBufferBlock}) {
1658 if (!ir_context->get_decoration_mgr()->WhileEachDecoration(
1659 id, decoration, [](const opt::Instruction & /*unused*/) -> bool {
1660 return false;
1661 })) {
1662 return true;
1663 }
1664 }
1665 return false;
1666 }
1667
1668 bool SplittingBeforeInstructionSeparatesOpSampledImageDefinitionFromUse(
1669 opt::BasicBlock* block_to_split, opt::Instruction* split_before) {
1670 std::set<uint32_t> sampled_image_result_ids;
1671 bool before_split = true;
1672
1673 // Check all the instructions in the block to split.
1674 for (auto& instruction : *block_to_split) {
1675 if (&instruction == &*split_before) {
1676 before_split = false;
1677 }
1678 if (before_split) {
1679 // If the instruction comes before the split and its opcode is
1680 // OpSampledImage, record its result id.
1681 if (instruction.opcode() == SpvOpSampledImage) {
1682 sampled_image_result_ids.insert(instruction.result_id());
1683 }
1684 } else {
1685 // If the instruction comes after the split, check if ids
1686 // corresponding to OpSampledImage instructions defined before the split
1687 // are used, and return true if they are.
1688 if (!instruction.WhileEachInId(
1689 [&sampled_image_result_ids](uint32_t* id) -> bool {
1690 return !sampled_image_result_ids.count(*id);
1691 })) {
1692 return true;
1693 }
1694 }
1695 }
1696
1697 // No usage that would be separated from the definition has been found.
1698 return false;
1699 }
1700
1701 bool InstructionHasNoSideEffects(const opt::Instruction& instruction) {
1702 switch (instruction.opcode()) {
1703 case SpvOpUndef:
1704 case SpvOpAccessChain:
1705 case SpvOpInBoundsAccessChain:
1706 case SpvOpArrayLength:
1707 case SpvOpVectorExtractDynamic:
1708 case SpvOpVectorInsertDynamic:
1709 case SpvOpVectorShuffle:
1710 case SpvOpCompositeConstruct:
1711 case SpvOpCompositeExtract:
1712 case SpvOpCompositeInsert:
1713 case SpvOpCopyObject:
1714 case SpvOpTranspose:
1715 case SpvOpConvertFToU:
1716 case SpvOpConvertFToS:
1717 case SpvOpConvertSToF:
1718 case SpvOpConvertUToF:
1719 case SpvOpUConvert:
1720 case SpvOpSConvert:
1721 case SpvOpFConvert:
1722 case SpvOpQuantizeToF16:
1723 case SpvOpSatConvertSToU:
1724 case SpvOpSatConvertUToS:
1725 case SpvOpBitcast:
1726 case SpvOpSNegate:
1727 case SpvOpFNegate:
1728 case SpvOpIAdd:
1729 case SpvOpFAdd:
1730 case SpvOpISub:
1731 case SpvOpFSub:
1732 case SpvOpIMul:
1733 case SpvOpFMul:
1734 case SpvOpUDiv:
1735 case SpvOpSDiv:
1736 case SpvOpFDiv:
1737 case SpvOpUMod:
1738 case SpvOpSRem:
1739 case SpvOpSMod:
1740 case SpvOpFRem:
1741 case SpvOpFMod:
1742 case SpvOpVectorTimesScalar:
1743 case SpvOpMatrixTimesScalar:
1744 case SpvOpVectorTimesMatrix:
1745 case SpvOpMatrixTimesVector:
1746 case SpvOpMatrixTimesMatrix:
1747 case SpvOpOuterProduct:
1748 case SpvOpDot:
1749 case SpvOpIAddCarry:
1750 case SpvOpISubBorrow:
1751 case SpvOpUMulExtended:
1752 case SpvOpSMulExtended:
1753 case SpvOpAny:
1754 case SpvOpAll:
1755 case SpvOpIsNan:
1756 case SpvOpIsInf:
1757 case SpvOpIsFinite:
1758 case SpvOpIsNormal:
1759 case SpvOpSignBitSet:
1760 case SpvOpLessOrGreater:
1761 case SpvOpOrdered:
1762 case SpvOpUnordered:
1763 case SpvOpLogicalEqual:
1764 case SpvOpLogicalNotEqual:
1765 case SpvOpLogicalOr:
1766 case SpvOpLogicalAnd:
1767 case SpvOpLogicalNot:
1768 case SpvOpSelect:
1769 case SpvOpIEqual:
1770 case SpvOpINotEqual:
1771 case SpvOpUGreaterThan:
1772 case SpvOpSGreaterThan:
1773 case SpvOpUGreaterThanEqual:
1774 case SpvOpSGreaterThanEqual:
1775 case SpvOpULessThan:
1776 case SpvOpSLessThan:
1777 case SpvOpULessThanEqual:
1778 case SpvOpSLessThanEqual:
1779 case SpvOpFOrdEqual:
1780 case SpvOpFUnordEqual:
1781 case SpvOpFOrdNotEqual:
1782 case SpvOpFUnordNotEqual:
1783 case SpvOpFOrdLessThan:
1784 case SpvOpFUnordLessThan:
1785 case SpvOpFOrdGreaterThan:
1786 case SpvOpFUnordGreaterThan:
1787 case SpvOpFOrdLessThanEqual:
1788 case SpvOpFUnordLessThanEqual:
1789 case SpvOpFOrdGreaterThanEqual:
1790 case SpvOpFUnordGreaterThanEqual:
1791 case SpvOpShiftRightLogical:
1792 case SpvOpShiftRightArithmetic:
1793 case SpvOpShiftLeftLogical:
1794 case SpvOpBitwiseOr:
1795 case SpvOpBitwiseXor:
1796 case SpvOpBitwiseAnd:
1797 case SpvOpNot:
1798 case SpvOpBitFieldInsert:
1799 case SpvOpBitFieldSExtract:
1800 case SpvOpBitFieldUExtract:
1801 case SpvOpBitReverse:
1802 case SpvOpBitCount:
1803 case SpvOpCopyLogical:
1804 case SpvOpPhi:
1805 case SpvOpPtrEqual:
1806 case SpvOpPtrNotEqual:
1807 return true;
1808 default:
1809 return false;
1810 }
1811 }
1812
1813 std::set<uint32_t> GetReachableReturnBlocks(opt::IRContext* ir_context,
1814 uint32_t function_id) {
1815 auto function = ir_context->GetFunction(function_id);
1816 assert(function && "The function |function_id| must exist.");
1817
1818 std::set<uint32_t> result;
1819
1820 ir_context->cfg()->ForEachBlockInPostOrder(function->entry().get(),
1821 [&result](opt::BasicBlock* block) {
1822 if (block->IsReturn()) {
1823 result.emplace(block->id());
1824 }
1825 });
1826
1827 return result;
1828 }
1829
1830 } // namespace fuzzerutil
1831 } // namespace fuzz
1832 } // namespace spvtools