Debian Codegraph @

third_party/spirv-tools/source/opt/scalar_replacement_pass.cpp

raw
1 // Copyright (c) 2017 Google Inc.
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/opt/scalar_replacement_pass.h"
16
17 #include <algorithm>
18 #include <queue>
19 #include <tuple>
20 #include <utility>
21
22 #include "source/enum_string_mapping.h"
23 #include "source/extensions.h"
24 #include "source/opt/reflect.h"
25 #include "source/opt/types.h"
26 #include "source/util/make_unique.h"
27
28 static const uint32_t kDebugDeclareOperandLocalVariableIndex = 4;
29 static const uint32_t kDebugValueOperandValueIndex = 5;
30 static const uint32_t kDebugValueOperandExpressionIndex = 6;
31
32 namespace spvtools {
33 namespace opt {
34
35 Pass::Status ScalarReplacementPass::Process() {
36 Status status = Status::SuccessWithoutChange;
37 for (auto& f : *get_module()) {
38 Status functionStatus = ProcessFunction(&f);
39 if (functionStatus == Status::Failure)
40 return functionStatus;
41 else if (functionStatus == Status::SuccessWithChange)
42 status = functionStatus;
43 }
44
45 return status;
46 }
47
48 Pass::Status ScalarReplacementPass::ProcessFunction(Function* function) {
49 std::queue<Instruction*> worklist;
50 BasicBlock& entry = *function->begin();
51 for (auto iter = entry.begin(); iter != entry.end(); ++iter) {
52 // Function storage class OpVariables must appear as the first instructions
53 // of the entry block.
54 if (iter->opcode() != SpvOpVariable) break;
55
56 Instruction* varInst = &*iter;
57 if (CanReplaceVariable(varInst)) {
58 worklist.push(varInst);
59 }
60 }
61
62 Status status = Status::SuccessWithoutChange;
63 while (!worklist.empty()) {
64 Instruction* varInst = worklist.front();
65 worklist.pop();
66
67 Status var_status = ReplaceVariable(varInst, &worklist);
68 if (var_status == Status::Failure)
69 return var_status;
70 else if (var_status == Status::SuccessWithChange)
71 status = var_status;
72 }
73
74 return status;
75 }
76
77 Pass::Status ScalarReplacementPass::ReplaceVariable(
78 Instruction* inst, std::queue<Instruction*>* worklist) {
79 std::vector<Instruction*> replacements;
80 if (!CreateReplacementVariables(inst, &replacements)) {
81 return Status::Failure;
82 }
83
84 std::vector<Instruction*> dead;
85 bool replaced_all_uses = get_def_use_mgr()->WhileEachUser(
86 inst, [this, &replacements, &dead](Instruction* user) {
87 if (user->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugDeclare) {
88 if (ReplaceWholeDebugDeclare(user, replacements)) {
89 dead.push_back(user);
90 return true;
91 }
92 return false;
93 }
94 if (user->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugValue) {
95 if (ReplaceWholeDebugValue(user, replacements)) {
96 dead.push_back(user);
97 return true;
98 }
99 return false;
100 }
101 if (!IsAnnotationInst(user->opcode())) {
102 switch (user->opcode()) {
103 case SpvOpLoad:
104 if (ReplaceWholeLoad(user, replacements)) {
105 dead.push_back(user);
106 } else {
107 return false;
108 }
109 break;
110 case SpvOpStore:
111 if (ReplaceWholeStore(user, replacements)) {
112 dead.push_back(user);
113 } else {
114 return false;
115 }
116 break;
117 case SpvOpAccessChain:
118 case SpvOpInBoundsAccessChain:
119 if (ReplaceAccessChain(user, replacements))
120 dead.push_back(user);
121 else
122 return false;
123 break;
124 case SpvOpName:
125 case SpvOpMemberName:
126 break;
127 default:
128 assert(false && "Unexpected opcode");
129 break;
130 }
131 }
132 return true;
133 });
134
135 if (replaced_all_uses) {
136 dead.push_back(inst);
137 } else {
138 return Status::Failure;
139 }
140
141 // If there are no dead instructions to clean up, return with no changes.
142 if (dead.empty()) return Status::SuccessWithoutChange;
143
144 // Clean up some dead code.
145 while (!dead.empty()) {
146 Instruction* toKill = dead.back();
147 dead.pop_back();
148 context()->KillInst(toKill);
149 }
150
151 // Attempt to further scalarize.
152 for (auto var : replacements) {
153 if (var->opcode() == SpvOpVariable) {
154 if (get_def_use_mgr()->NumUsers(var) == 0) {
155 context()->KillInst(var);
156 } else if (CanReplaceVariable(var)) {
157 worklist->push(var);
158 }
159 }
160 }
161
162 return Status::SuccessWithChange;
163 }
164
165 bool ScalarReplacementPass::ReplaceWholeDebugDeclare(
166 Instruction* dbg_decl, const std::vector<Instruction*>& replacements) {
167 // Insert Deref operation to the front of the operation list of |dbg_decl|.
168 Instruction* dbg_expr = context()->get_def_use_mgr()->GetDef(
169 dbg_decl->GetSingleWordOperand(kDebugValueOperandExpressionIndex));
170 auto* deref_expr =
171 context()->get_debug_info_mgr()->DerefDebugExpression(dbg_expr);
172
173 // Add DebugValue instruction with Indexes operand and Deref operation.
174 int32_t idx = 0;
175 for (const auto* var : replacements) {
176 uint32_t dbg_local_variable =
177 dbg_decl->GetSingleWordOperand(kDebugDeclareOperandLocalVariableIndex);
178 uint32_t index_id = context()->get_constant_mgr()->GetSIntConst(idx);
179
180 Instruction* added_dbg_value =
181 context()->get_debug_info_mgr()->AddDebugValueWithIndex(
182 dbg_local_variable,
183 /*value_id=*/var->result_id(), /*expr_id=*/deref_expr->result_id(),
184 index_id, /*insert_before=*/var->NextNode());
185 if (added_dbg_value == nullptr) return false;
186 added_dbg_value->UpdateDebugInfoFrom(dbg_decl);
187 ++idx;
188 }
189 return true;
190 }
191
192 bool ScalarReplacementPass::ReplaceWholeDebugValue(
193 Instruction* dbg_value, const std::vector<Instruction*>& replacements) {
194 int32_t idx = 0;
195 BasicBlock* block = context()->get_instr_block(dbg_value);
196 for (auto var : replacements) {
197 // Clone the DebugValue.
198 std::unique_ptr<Instruction> new_dbg_value(dbg_value->Clone(context()));
199 uint32_t new_id = TakeNextId();
200 if (new_id == 0) return false;
201 new_dbg_value->SetResultId(new_id);
202 // Update 'Value' operand to the |replacements|.
203 new_dbg_value->SetOperand(kDebugValueOperandValueIndex, {var->result_id()});
204 // Append 'Indexes' operand.
205 new_dbg_value->AddOperand(
206 {SPV_OPERAND_TYPE_ID,
207 {context()->get_constant_mgr()->GetSIntConst(idx)}});
208 // Insert the new DebugValue to the basic block.
209 auto* added_instr = dbg_value->InsertBefore(std::move(new_dbg_value));
210 get_def_use_mgr()->AnalyzeInstDefUse(added_instr);
211 context()->set_instr_block(added_instr, block);
212 ++idx;
213 }
214 return true;
215 }
216
217 bool ScalarReplacementPass::ReplaceWholeLoad(
218 Instruction* load, const std::vector<Instruction*>& replacements) {
219 // Replaces the load of the entire composite with a load from each replacement
220 // variable followed by a composite construction.
221 BasicBlock* block = context()->get_instr_block(load);
222 std::vector<Instruction*> loads;
223 loads.reserve(replacements.size());
224 BasicBlock::iterator where(load);
225 for (auto var : replacements) {
226 // Create a load of each replacement variable.
227 if (var->opcode() != SpvOpVariable) {
228 loads.push_back(var);
229 continue;
230 }
231
232 Instruction* type = GetStorageType(var);
233 uint32_t loadId = TakeNextId();
234 if (loadId == 0) {
235 return false;
236 }
237 std::unique_ptr<Instruction> newLoad(
238 new Instruction(context(), SpvOpLoad, type->result_id(), loadId,
239 std::initializer_list<Operand>{
240 {SPV_OPERAND_TYPE_ID, {var->result_id()}}}));
241 // Copy memory access attributes which start at index 1. Index 0 is the
242 // pointer to load.
243 for (uint32_t i = 1; i < load->NumInOperands(); ++i) {
244 Operand copy(load->GetInOperand(i));
245 newLoad->AddOperand(std::move(copy));
246 }
247 where = where.InsertBefore(std::move(newLoad));
248 get_def_use_mgr()->AnalyzeInstDefUse(&*where);
249 context()->set_instr_block(&*where, block);
250 where->UpdateDebugInfoFrom(load);
251 loads.push_back(&*where);
252 }
253
254 // Construct a new composite.
255 uint32_t compositeId = TakeNextId();
256 if (compositeId == 0) {
257 return false;
258 }
259 where = load;
260 std::unique_ptr<Instruction> compositeConstruct(new Instruction(
261 context(), SpvOpCompositeConstruct, load->type_id(), compositeId, {}));
262 for (auto l : loads) {
263 Operand op(SPV_OPERAND_TYPE_ID,
264 std::initializer_list<uint32_t>{l->result_id()});
265 compositeConstruct->AddOperand(std::move(op));
266 }
267 where = where.InsertBefore(std::move(compositeConstruct));
268 get_def_use_mgr()->AnalyzeInstDefUse(&*where);
269 where->UpdateDebugInfoFrom(load);
270 context()->set_instr_block(&*where, block);
271 context()->ReplaceAllUsesWith(load->result_id(), compositeId);
272 return true;
273 }
274
275 bool ScalarReplacementPass::ReplaceWholeStore(
276 Instruction* store, const std::vector<Instruction*>& replacements) {
277 // Replaces a store to the whole composite with a series of extract and stores
278 // to each element.
279 uint32_t storeInput = store->GetSingleWordInOperand(1u);
280 BasicBlock* block = context()->get_instr_block(store);
281 BasicBlock::iterator where(store);
282 uint32_t elementIndex = 0;
283 for (auto var : replacements) {
284 // Create the extract.
285 if (var->opcode() != SpvOpVariable) {
286 elementIndex++;
287 continue;
288 }
289
290 Instruction* type = GetStorageType(var);
291 uint32_t extractId = TakeNextId();
292 if (extractId == 0) {
293 return false;
294 }
295 std::unique_ptr<Instruction> extract(new Instruction(
296 context(), SpvOpCompositeExtract, type->result_id(), extractId,
297 std::initializer_list<Operand>{
298 {SPV_OPERAND_TYPE_ID, {storeInput}},
299 {SPV_OPERAND_TYPE_LITERAL_INTEGER, {elementIndex++}}}));
300 auto iter = where.InsertBefore(std::move(extract));
301 iter->UpdateDebugInfoFrom(store);
302 get_def_use_mgr()->AnalyzeInstDefUse(&*iter);
303 context()->set_instr_block(&*iter, block);
304
305 // Create the store.
306 std::unique_ptr<Instruction> newStore(
307 new Instruction(context(), SpvOpStore, 0, 0,
308 std::initializer_list<Operand>{
309 {SPV_OPERAND_TYPE_ID, {var->result_id()}},
310 {SPV_OPERAND_TYPE_ID, {extractId}}}));
311 // Copy memory access attributes which start at index 2. Index 0 is the
312 // pointer and index 1 is the data.
313 for (uint32_t i = 2; i < store->NumInOperands(); ++i) {
314 Operand copy(store->GetInOperand(i));
315 newStore->AddOperand(std::move(copy));
316 }
317 iter = where.InsertBefore(std::move(newStore));
318 iter->UpdateDebugInfoFrom(store);
319 get_def_use_mgr()->AnalyzeInstDefUse(&*iter);
320 context()->set_instr_block(&*iter, block);
321 }
322 return true;
323 }
324
325 bool ScalarReplacementPass::ReplaceAccessChain(
326 Instruction* chain, const std::vector<Instruction*>& replacements) {
327 // Replaces the access chain with either another access chain (with one fewer
328 // indexes) or a direct use of the replacement variable.
329 uint32_t indexId = chain->GetSingleWordInOperand(1u);
330 const Instruction* index = get_def_use_mgr()->GetDef(indexId);
331 int64_t indexValue = context()
332 ->get_constant_mgr()
333 ->GetConstantFromInst(index)
334 ->GetSignExtendedValue();
335 if (indexValue < 0 ||
336 indexValue >= static_cast<int64_t>(replacements.size())) {
337 // Out of bounds access, this is illegal IR. Notice that OpAccessChain
338 // indexing is 0-based, so we should also reject index == size-of-array.
339 return false;
340 } else {
341 const Instruction* var = replacements[static_cast<size_t>(indexValue)];
342 if (chain->NumInOperands() > 2) {
343 // Replace input access chain with another access chain.
344 BasicBlock::iterator chainIter(chain);
345 uint32_t replacementId = TakeNextId();
346 if (replacementId == 0) {
347 return false;
348 }
349 std::unique_ptr<Instruction> replacementChain(new Instruction(
350 context(), chain->opcode(), chain->type_id(), replacementId,
351 std::initializer_list<Operand>{
352 {SPV_OPERAND_TYPE_ID, {var->result_id()}}}));
353 // Add the remaining indexes.
354 for (uint32_t i = 2; i < chain->NumInOperands(); ++i) {
355 Operand copy(chain->GetInOperand(i));
356 replacementChain->AddOperand(std::move(copy));
357 }
358 replacementChain->UpdateDebugInfoFrom(chain);
359 auto iter = chainIter.InsertBefore(std::move(replacementChain));
360 get_def_use_mgr()->AnalyzeInstDefUse(&*iter);
361 context()->set_instr_block(&*iter, context()->get_instr_block(chain));
362 context()->ReplaceAllUsesWith(chain->result_id(), replacementId);
363 } else {
364 // Replace with a use of the variable.
365 context()->ReplaceAllUsesWith(chain->result_id(), var->result_id());
366 }
367 }
368
369 return true;
370 }
371
372 bool ScalarReplacementPass::CreateReplacementVariables(
373 Instruction* inst, std::vector<Instruction*>* replacements) {
374 Instruction* type = GetStorageType(inst);
375
376 std::unique_ptr<std::unordered_set<int64_t>> components_used =
377 GetUsedComponents(inst);
378
379 uint32_t elem = 0;
380 switch (type->opcode()) {
381 case SpvOpTypeStruct:
382 type->ForEachInOperand(
383 [this, inst, &elem, replacements, &components_used](uint32_t* id) {
384 if (!components_used || components_used->count(elem)) {
385 CreateVariable(*id, inst, elem, replacements);
386 } else {
387 replacements->push_back(CreateNullConstant(*id));
388 }
389 elem++;
390 });
391 break;
392 case SpvOpTypeArray:
393 for (uint32_t i = 0; i != GetArrayLength(type); ++i) {
394 if (!components_used || components_used->count(i)) {
395 CreateVariable(type->GetSingleWordInOperand(0u), inst, i,
396 replacements);
397 } else {
398 replacements->push_back(
399 CreateNullConstant(type->GetSingleWordInOperand(0u)));
400 }
401 }
402 break;
403
404 case SpvOpTypeMatrix:
405 case SpvOpTypeVector:
406 for (uint32_t i = 0; i != GetNumElements(type); ++i) {
407 CreateVariable(type->GetSingleWordInOperand(0u), inst, i, replacements);
408 }
409 break;
410
411 default:
412 assert(false && "Unexpected type.");
413 break;
414 }
415
416 TransferAnnotations(inst, replacements);
417 return std::find(replacements->begin(), replacements->end(), nullptr) ==
418 replacements->end();
419 }
420
421 void ScalarReplacementPass::TransferAnnotations(
422 const Instruction* source, std::vector<Instruction*>* replacements) {
423 // Only transfer invariant and restrict decorations on the variable. There are
424 // no type or member decorations that are necessary to transfer.
425 for (auto inst :
426 get_decoration_mgr()->GetDecorationsFor(source->result_id(), false)) {
427 assert(inst->opcode() == SpvOpDecorate);
428 uint32_t decoration = inst->GetSingleWordInOperand(1u);
429 if (decoration == SpvDecorationInvariant ||
430 decoration == SpvDecorationRestrict) {
431 for (auto var : *replacements) {
432 if (var == nullptr) {
433 continue;
434 }
435
436 std::unique_ptr<Instruction> annotation(
437 new Instruction(context(), SpvOpDecorate, 0, 0,
438 std::initializer_list<Operand>{
439 {SPV_OPERAND_TYPE_ID, {var->result_id()}},
440 {SPV_OPERAND_TYPE_DECORATION, {decoration}}}));
441 for (uint32_t i = 2; i < inst->NumInOperands(); ++i) {
442 Operand copy(inst->GetInOperand(i));
443 annotation->AddOperand(std::move(copy));
444 }
445 context()->AddAnnotationInst(std::move(annotation));
446 get_def_use_mgr()->AnalyzeInstUse(&*--context()->annotation_end());
447 }
448 }
449 }
450 }
451
452 void ScalarReplacementPass::CreateVariable(
453 uint32_t typeId, Instruction* varInst, uint32_t index,
454 std::vector<Instruction*>* replacements) {
455 uint32_t ptrId = GetOrCreatePointerType(typeId);
456 uint32_t id = TakeNextId();
457
458 if (id == 0) {
459 replacements->push_back(nullptr);
460 }
461
462 std::unique_ptr<Instruction> variable(new Instruction(
463 context(), SpvOpVariable, ptrId, id,
464 std::initializer_list<Operand>{
465 {SPV_OPERAND_TYPE_STORAGE_CLASS, {SpvStorageClassFunction}}}));
466
467 BasicBlock* block = context()->get_instr_block(varInst);
468 block->begin().InsertBefore(std::move(variable));
469 Instruction* inst = &*block->begin();
470
471 // If varInst was initialized, make sure to initialize its replacement.
472 GetOrCreateInitialValue(varInst, index, inst);
473 get_def_use_mgr()->AnalyzeInstDefUse(inst);
474 context()->set_instr_block(inst, block);
475
476 // Copy decorations from the member to the new variable.
477 Instruction* typeInst = GetStorageType(varInst);
478 for (auto dec_inst :
479 get_decoration_mgr()->GetDecorationsFor(typeInst->result_id(), false)) {
480 uint32_t decoration;
481 if (dec_inst->opcode() != SpvOpMemberDecorate) {
482 continue;
483 }
484
485 if (dec_inst->GetSingleWordInOperand(1) != index) {
486 continue;
487 }
488
489 decoration = dec_inst->GetSingleWordInOperand(2u);
490 switch (decoration) {
491 case SpvDecorationRelaxedPrecision: {
492 std::unique_ptr<Instruction> new_dec_inst(
493 new Instruction(context(), SpvOpDecorate, 0, 0, {}));
494 new_dec_inst->AddOperand(Operand(SPV_OPERAND_TYPE_ID, {id}));
495 for (uint32_t i = 2; i < dec_inst->NumInOperandWords(); ++i) {
496 new_dec_inst->AddOperand(Operand(dec_inst->GetInOperand(i)));
497 }
498 context()->AddAnnotationInst(std::move(new_dec_inst));
499 } break;
500 default:
501 break;
502 }
503 }
504
505 // Update the OpenCL.DebugInfo.100 debug information.
506 inst->UpdateDebugInfoFrom(varInst);
507
508 replacements->push_back(inst);
509 }
510
511 uint32_t ScalarReplacementPass::GetOrCreatePointerType(uint32_t id) {
512 auto iter = pointee_to_pointer_.find(id);
513 if (iter != pointee_to_pointer_.end()) return iter->second;
514
515 analysis::Type* pointeeTy;
516 std::unique_ptr<analysis::Pointer> pointerTy;
517 std::tie(pointeeTy, pointerTy) =
518 context()->get_type_mgr()->GetTypeAndPointerType(id,
519 SpvStorageClassFunction);
520 uint32_t ptrId = 0;
521 if (pointeeTy->IsUniqueType()) {
522 // Non-ambiguous type, just ask the type manager for an id.
523 ptrId = context()->get_type_mgr()->GetTypeInstruction(pointerTy.get());
524 pointee_to_pointer_[id] = ptrId;
525 return ptrId;
526 }
527
528 // Ambiguous type. We must perform a linear search to try and find the right
529 // type.
530 for (auto global : context()->types_values()) {
531 if (global.opcode() == SpvOpTypePointer &&
532 global.GetSingleWordInOperand(0u) == SpvStorageClassFunction &&
533 global.GetSingleWordInOperand(1u) == id) {
534 if (get_decoration_mgr()->GetDecorationsFor(id, false).empty()) {
535 // Only reuse a decoration-less pointer of the correct type.
536 ptrId = global.result_id();
537 break;
538 }
539 }
540 }
541
542 if (ptrId != 0) {
543 pointee_to_pointer_[id] = ptrId;
544 return ptrId;
545 }
546
547 ptrId = TakeNextId();
548 context()->AddType(MakeUnique<Instruction>(
549 context(), SpvOpTypePointer, 0, ptrId,
550 std::initializer_list<Operand>{
551 {SPV_OPERAND_TYPE_STORAGE_CLASS, {SpvStorageClassFunction}},
552 {SPV_OPERAND_TYPE_ID, {id}}}));
553 Instruction* ptr = &*--context()->types_values_end();
554 get_def_use_mgr()->AnalyzeInstDefUse(ptr);
555 pointee_to_pointer_[id] = ptrId;
556 // Register with the type manager if necessary.
557 context()->get_type_mgr()->RegisterType(ptrId, *pointerTy);
558
559 return ptrId;
560 }
561
562 void ScalarReplacementPass::GetOrCreateInitialValue(Instruction* source,
563 uint32_t index,
564 Instruction* newVar) {
565 assert(source->opcode() == SpvOpVariable);
566 if (source->NumInOperands() < 2) return;
567
568 uint32_t initId = source->GetSingleWordInOperand(1u);
569 uint32_t storageId = GetStorageType(newVar)->result_id();
570 Instruction* init = get_def_use_mgr()->GetDef(initId);
571 uint32_t newInitId = 0;
572 // TODO(dnovillo): Refactor this with constant propagation.
573 if (init->opcode() == SpvOpConstantNull) {
574 // Initialize to appropriate NULL.
575 auto iter = type_to_null_.find(storageId);
576 if (iter == type_to_null_.end()) {
577 newInitId = TakeNextId();
578 type_to_null_[storageId] = newInitId;
579 context()->AddGlobalValue(
580 MakeUnique<Instruction>(context(), SpvOpConstantNull, storageId,
581 newInitId, std::initializer_list<Operand>{}));
582 Instruction* newNull = &*--context()->types_values_end();
583 get_def_use_mgr()->AnalyzeInstDefUse(newNull);
584 } else {
585 newInitId = iter->second;
586 }
587 } else if (IsSpecConstantInst(init->opcode())) {
588 // Create a new constant extract.
589 newInitId = TakeNextId();
590 context()->AddGlobalValue(MakeUnique<Instruction>(
591 context(), SpvOpSpecConstantOp, storageId, newInitId,
592 std::initializer_list<Operand>{
593 {SPV_OPERAND_TYPE_SPEC_CONSTANT_OP_NUMBER, {SpvOpCompositeExtract}},
594 {SPV_OPERAND_TYPE_ID, {init->result_id()}},
595 {SPV_OPERAND_TYPE_LITERAL_INTEGER, {index}}}));
596 Instruction* newSpecConst = &*--context()->types_values_end();
597 get_def_use_mgr()->AnalyzeInstDefUse(newSpecConst);
598 } else if (init->opcode() == SpvOpConstantComposite) {
599 // Get the appropriate index constant.
600 newInitId = init->GetSingleWordInOperand(index);
601 Instruction* element = get_def_use_mgr()->GetDef(newInitId);
602 if (element->opcode() == SpvOpUndef) {
603 // Undef is not a valid initializer for a variable.
604 newInitId = 0;
605 }
606 } else {
607 assert(false);
608 }
609
610 if (newInitId != 0) {
611 newVar->AddOperand({SPV_OPERAND_TYPE_ID, {newInitId}});
612 }
613 }
614
615 uint64_t ScalarReplacementPass::GetArrayLength(
616 const Instruction* arrayType) const {
617 assert(arrayType->opcode() == SpvOpTypeArray);
618 const Instruction* length =
619 get_def_use_mgr()->GetDef(arrayType->GetSingleWordInOperand(1u));
620 return context()
621 ->get_constant_mgr()
622 ->GetConstantFromInst(length)
623 ->GetZeroExtendedValue();
624 }
625
626 uint64_t ScalarReplacementPass::GetNumElements(const Instruction* type) const {
627 assert(type->opcode() == SpvOpTypeVector ||
628 type->opcode() == SpvOpTypeMatrix);
629 const Operand& op = type->GetInOperand(1u);
630 assert(op.words.size() <= 2);
631 uint64_t len = 0;
632 for (size_t i = 0; i != op.words.size(); ++i) {
633 len |= (static_cast<uint64_t>(op.words[i]) << (32ull * i));
634 }
635 return len;
636 }
637
638 bool ScalarReplacementPass::IsSpecConstant(uint32_t id) const {
639 const Instruction* inst = get_def_use_mgr()->GetDef(id);
640 assert(inst);
641 return spvOpcodeIsSpecConstant(inst->opcode());
642 }
643
644 Instruction* ScalarReplacementPass::GetStorageType(
645 const Instruction* inst) const {
646 assert(inst->opcode() == SpvOpVariable);
647
648 uint32_t ptrTypeId = inst->type_id();
649 uint32_t typeId =
650 get_def_use_mgr()->GetDef(ptrTypeId)->GetSingleWordInOperand(1u);
651 return get_def_use_mgr()->GetDef(typeId);
652 }
653
654 bool ScalarReplacementPass::CanReplaceVariable(
655 const Instruction* varInst) const {
656 assert(varInst->opcode() == SpvOpVariable);
657
658 // Can only replace function scope variables.
659 if (varInst->GetSingleWordInOperand(0u) != SpvStorageClassFunction) {
660 return false;
661 }
662
663 if (!CheckTypeAnnotations(get_def_use_mgr()->GetDef(varInst->type_id()))) {
664 return false;
665 }
666
667 const Instruction* typeInst = GetStorageType(varInst);
668 if (!CheckType(typeInst)) {
669 return false;
670 }
671
672 if (!CheckAnnotations(varInst)) {
673 return false;
674 }
675
676 if (!CheckUses(varInst)) {
677 return false;
678 }
679
680 return true;
681 }
682
683 bool ScalarReplacementPass::CheckType(const Instruction* typeInst) const {
684 if (!CheckTypeAnnotations(typeInst)) {
685 return false;
686 }
687
688 switch (typeInst->opcode()) {
689 case SpvOpTypeStruct:
690 // Don't bother with empty structs or very large structs.
691 if (typeInst->NumInOperands() == 0 ||
692 IsLargerThanSizeLimit(typeInst->NumInOperands())) {
693 return false;
694 }
695 return true;
696 case SpvOpTypeArray:
697 if (IsSpecConstant(typeInst->GetSingleWordInOperand(1u))) {
698 return false;
699 }
700 if (IsLargerThanSizeLimit(GetArrayLength(typeInst))) {
701 return false;
702 }
703 return true;
704 // TODO(alanbaker): Develop some heuristics for when this should be
705 // re-enabled.
706 //// Specifically including matrix and vector in an attempt to reduce the
707 //// number of vector registers required.
708 // case SpvOpTypeMatrix:
709 // case SpvOpTypeVector:
710 // if (IsLargerThanSizeLimit(GetNumElements(typeInst))) return false;
711 // return true;
712
713 case SpvOpTypeRuntimeArray:
714 default:
715 return false;
716 }
717 }
718
719 bool ScalarReplacementPass::CheckTypeAnnotations(
720 const Instruction* typeInst) const {
721 for (auto inst :
722 get_decoration_mgr()->GetDecorationsFor(typeInst->result_id(), false)) {
723 uint32_t decoration;
724 if (inst->opcode() == SpvOpDecorate) {
725 decoration = inst->GetSingleWordInOperand(1u);
726 } else {
727 assert(inst->opcode() == SpvOpMemberDecorate);
728 decoration = inst->GetSingleWordInOperand(2u);
729 }
730
731 switch (decoration) {
732 case SpvDecorationRowMajor:
733 case SpvDecorationColMajor:
734 case SpvDecorationArrayStride:
735 case SpvDecorationMatrixStride:
736 case SpvDecorationCPacked:
737 case SpvDecorationInvariant:
738 case SpvDecorationRestrict:
739 case SpvDecorationOffset:
740 case SpvDecorationAlignment:
741 case SpvDecorationAlignmentId:
742 case SpvDecorationMaxByteOffset:
743 case SpvDecorationRelaxedPrecision:
744 break;
745 default:
746 return false;
747 }
748 }
749
750 return true;
751 }
752
753 bool ScalarReplacementPass::CheckAnnotations(const Instruction* varInst) const {
754 for (auto inst :
755 get_decoration_mgr()->GetDecorationsFor(varInst->result_id(), false)) {
756 assert(inst->opcode() == SpvOpDecorate);
757 uint32_t decoration = inst->GetSingleWordInOperand(1u);
758 switch (decoration) {
759 case SpvDecorationInvariant:
760 case SpvDecorationRestrict:
761 case SpvDecorationAlignment:
762 case SpvDecorationAlignmentId:
763 case SpvDecorationMaxByteOffset:
764 break;
765 default:
766 return false;
767 }
768 }
769
770 return true;
771 }
772
773 bool ScalarReplacementPass::CheckUses(const Instruction* inst) const {
774 VariableStats stats = {0, 0};
775 bool ok = CheckUses(inst, &stats);
776
777 // TODO(alanbaker/greg-lunarg): Add some meaningful heuristics about when
778 // SRoA is costly, such as when the structure has many (unaccessed?)
779 // members.
780
781 return ok;
782 }
783
784 bool ScalarReplacementPass::CheckUses(const Instruction* inst,
785 VariableStats* stats) const {
786 uint64_t max_legal_index = GetMaxLegalIndex(inst);
787
788 bool ok = true;
789 get_def_use_mgr()->ForEachUse(inst, [this, max_legal_index, stats, &ok](
790 const Instruction* user,
791 uint32_t index) {
792 if (user->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugDeclare ||
793 user->GetOpenCL100DebugOpcode() == OpenCLDebugInfo100DebugValue) {
794 // TODO: include num_partial_accesses if it uses Fragment operation or
795 // DebugValue has Indexes operand.
796 stats->num_full_accesses++;
797 return;
798 }
799
800 // Annotations are check as a group separately.
801 if (!IsAnnotationInst(user->opcode())) {
802 switch (user->opcode()) {
803 case SpvOpAccessChain:
804 case SpvOpInBoundsAccessChain:
805 if (index == 2u && user->NumInOperands() > 1) {
806 uint32_t id = user->GetSingleWordInOperand(1u);
807 const Instruction* opInst = get_def_use_mgr()->GetDef(id);
808 const auto* constant =
809 context()->get_constant_mgr()->GetConstantFromInst(opInst);
810 if (!constant) {
811 ok = false;
812 } else if (constant->GetZeroExtendedValue() >= max_legal_index) {
813 ok = false;
814 } else {
815 if (!CheckUsesRelaxed(user)) ok = false;
816 }
817 stats->num_partial_accesses++;
818 } else {
819 ok = false;
820 }
821 break;
822 case SpvOpLoad:
823 if (!CheckLoad(user, index)) ok = false;
824 stats->num_full_accesses++;
825 break;
826 case SpvOpStore:
827 if (!CheckStore(user, index)) ok = false;
828 stats->num_full_accesses++;
829 break;
830 case SpvOpName:
831 case SpvOpMemberName:
832 break;
833 default:
834 ok = false;
835 break;
836 }
837 }
838 });
839
840 return ok;
841 }
842
843 bool ScalarReplacementPass::CheckUsesRelaxed(const Instruction* inst) const {
844 bool ok = true;
845 get_def_use_mgr()->ForEachUse(
846 inst, [this, &ok](const Instruction* user, uint32_t index) {
847 switch (user->opcode()) {
848 case SpvOpAccessChain:
849 case SpvOpInBoundsAccessChain:
850 if (index != 2u) {
851 ok = false;
852 } else {
853 if (!CheckUsesRelaxed(user)) ok = false;
854 }
855 break;
856 case SpvOpLoad:
857 if (!CheckLoad(user, index)) ok = false;
858 break;
859 case SpvOpStore:
860 if (!CheckStore(user, index)) ok = false;
861 break;
862 default:
863 ok = false;
864 break;
865 }
866 });
867
868 return ok;
869 }
870
871 bool ScalarReplacementPass::CheckLoad(const Instruction* inst,
872 uint32_t index) const {
873 if (index != 2u) return false;
874 if (inst->NumInOperands() >= 2 &&
875 inst->GetSingleWordInOperand(1u) & SpvMemoryAccessVolatileMask)
876 return false;
877 return true;
878 }
879
880 bool ScalarReplacementPass::CheckStore(const Instruction* inst,
881 uint32_t index) const {
882 if (index != 0u) return false;
883 if (inst->NumInOperands() >= 3 &&
884 inst->GetSingleWordInOperand(2u) & SpvMemoryAccessVolatileMask)
885 return false;
886 return true;
887 }
888 bool ScalarReplacementPass::IsLargerThanSizeLimit(uint64_t length) const {
889 if (max_num_elements_ == 0) {
890 return false;
891 }
892 return length > max_num_elements_;
893 }
894
895 std::unique_ptr<std::unordered_set<int64_t>>
896 ScalarReplacementPass::GetUsedComponents(Instruction* inst) {
897 std::unique_ptr<std::unordered_set<int64_t>> result(
898 new std::unordered_set<int64_t>());
899
900 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
901
902 def_use_mgr->WhileEachUser(inst, [&result, def_use_mgr,
903 this](Instruction* use) {
904 switch (use->opcode()) {
905 case SpvOpLoad: {
906 // Look for extract from the load.
907 std::vector<uint32_t> t;
908 if (def_use_mgr->WhileEachUser(use, [&t](Instruction* use2) {
909 if (use2->opcode() != SpvOpCompositeExtract ||
910 use2->NumInOperands() <= 1) {
911 return false;
912 }
913 t.push_back(use2->GetSingleWordInOperand(1));
914 return true;
915 })) {
916 result->insert(t.begin(), t.end());
917 return true;
918 } else {
919 result.reset(nullptr);
920 return false;
921 }
922 }
923 case SpvOpName:
924 case SpvOpMemberName:
925 case SpvOpStore:
926 // No components are used.
927 return true;
928 case SpvOpAccessChain:
929 case SpvOpInBoundsAccessChain: {
930 // Add the first index it if is a constant.
931 // TODO: Could be improved by checking if the address is used in a load.
932 analysis::ConstantManager* const_mgr = context()->get_constant_mgr();
933 uint32_t index_id = use->GetSingleWordInOperand(1);
934 const analysis::Constant* index_const =
935 const_mgr->FindDeclaredConstant(index_id);
936 if (index_const) {
937 result->insert(index_const->GetSignExtendedValue());
938 return true;
939 } else {
940 // Could be any element. Assuming all are used.
941 result.reset(nullptr);
942 return false;
943 }
944 }
945 default:
946 // We do not know what is happening. Have to assume the worst.
947 result.reset(nullptr);
948 return false;
949 }
950 });
951
952 return result;
953 }
954
955 Instruction* ScalarReplacementPass::CreateNullConstant(uint32_t type_id) {
956 analysis::TypeManager* type_mgr = context()->get_type_mgr();
957 analysis::ConstantManager* const_mgr = context()->get_constant_mgr();
958
959 const analysis::Type* type = type_mgr->GetType(type_id);
960 const analysis::Constant* null_const = const_mgr->GetConstant(type, {});
961 Instruction* null_inst =
962 const_mgr->GetDefiningInstruction(null_const, type_id);
963 if (null_inst != nullptr) {
964 context()->UpdateDefUse(null_inst);
965 }
966 return null_inst;
967 }
968
969 uint64_t ScalarReplacementPass::GetMaxLegalIndex(
970 const Instruction* var_inst) const {
971 assert(var_inst->opcode() == SpvOpVariable &&
972 "|var_inst| must be a variable instruction.");
973 Instruction* type = GetStorageType(var_inst);
974 switch (type->opcode()) {
975 case SpvOpTypeStruct:
976 return type->NumInOperands();
977 case SpvOpTypeArray:
978 return GetArrayLength(type);
979 case SpvOpTypeMatrix:
980 case SpvOpTypeVector:
981 return GetNumElements(type);
982 default:
983 return 0;
984 }
985 return 0;
986 }
987
988 } // namespace opt
989 } // namespace spvtools