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/ir_context.h"
16
17#include <cstring>
18
19#include "source/latest_version_glsl_std_450_header.h"
20#include "source/opt/log.h"
21#include "source/opt/mem_pass.h"
22#include "source/opt/reflect.h"
23
24namespace {
25
26static const int kSpvDecorateTargetIdInIdx = 0;
27static const int kSpvDecorateDecorationInIdx = 1;
28static const int kSpvDecorateBuiltinInIdx = 2;
29static const int kEntryPointInterfaceInIdx = 3;
30static const int kEntryPointFunctionIdInIdx = 1;
31
32} // anonymous namespace
33
34namespace spvtools {
35namespace opt {
36
37void IRContext::BuildInvalidAnalyses(IRContext::Analysis set) {
38 if (set & kAnalysisDefUse) {
39 BuildDefUseManager();
40 }
41 if (set & kAnalysisInstrToBlockMapping) {
42 BuildInstrToBlockMapping();
43 }
44 if (set & kAnalysisDecorations) {
45 BuildDecorationManager();
46 }
47 if (set & kAnalysisCFG) {
48 BuildCFG();
49 }
50 if (set & kAnalysisDominatorAnalysis) {
51 ResetDominatorAnalysis();
52 }
53 if (set & kAnalysisLoopAnalysis) {
54 ResetLoopAnalysis();
55 }
56 if (set & kAnalysisBuiltinVarId) {
57 ResetBuiltinAnalysis();
58 }
59 if (set & kAnalysisNameMap) {
60 BuildIdToNameMap();
61 }
62 if (set & kAnalysisScalarEvolution) {
63 BuildScalarEvolutionAnalysis();
64 }
65 if (set & kAnalysisRegisterPressure) {
66 BuildRegPressureAnalysis();
67 }
68 if (set & kAnalysisValueNumberTable) {
69 BuildValueNumberTable();
70 }
71 if (set & kAnalysisStructuredCFG) {
72 BuildStructuredCFGAnalysis();
73 }
74 if (set & kAnalysisIdToFuncMapping) {
75 BuildIdToFuncMapping();
76 }
77 if (set & kAnalysisConstants) {
78 BuildConstantManager();
79 }
80 if (set & kAnalysisTypes) {
81 BuildTypeManager();
82 }
83}
84
85void IRContext::InvalidateAnalysesExceptFor(
86 IRContext::Analysis preserved_analyses) {
87 uint32_t analyses_to_invalidate = valid_analyses_ & (~preserved_analyses);
88 InvalidateAnalyses(static_cast<IRContext::Analysis>(analyses_to_invalidate));
89}
90
91void IRContext::InvalidateAnalyses(IRContext::Analysis analyses_to_invalidate) {
92 // The ConstantManager contains Type pointers. If the TypeManager goes
93 // away, the ConstantManager has to go away.
94 if (analyses_to_invalidate & kAnalysisTypes) {
95 analyses_to_invalidate |= kAnalysisConstants;
96 }
97
98 // The dominator analysis hold the psuedo entry and exit nodes from the CFG.
99 // Also if the CFG change the dominators many changed as well, so the
100 // dominator analysis should be invalidated as well.
101 if (analyses_to_invalidate & kAnalysisCFG) {
102 analyses_to_invalidate |= kAnalysisDominatorAnalysis;
103 }
104
105 if (analyses_to_invalidate & kAnalysisDefUse) {
106 def_use_mgr_.reset(nullptr);
107 }
108 if (analyses_to_invalidate & kAnalysisInstrToBlockMapping) {
109 instr_to_block_.clear();
110 }
111 if (analyses_to_invalidate & kAnalysisDecorations) {
112 decoration_mgr_.reset(nullptr);
113 }
114 if (analyses_to_invalidate & kAnalysisCombinators) {
115 combinator_ops_.clear();
116 }
117 if (analyses_to_invalidate & kAnalysisBuiltinVarId) {
118 builtin_var_id_map_.clear();
119 }
120 if (analyses_to_invalidate & kAnalysisCFG) {
121 cfg_.reset(nullptr);
122 }
123 if (analyses_to_invalidate & kAnalysisDominatorAnalysis) {
124 dominator_trees_.clear();
125 post_dominator_trees_.clear();
126 }
127 if (analyses_to_invalidate & kAnalysisNameMap) {
128 id_to_name_.reset(nullptr);
129 }
130 if (analyses_to_invalidate & kAnalysisValueNumberTable) {
131 vn_table_.reset(nullptr);
132 }
133 if (analyses_to_invalidate & kAnalysisStructuredCFG) {
134 struct_cfg_analysis_.reset(nullptr);
135 }
136 if (analyses_to_invalidate & kAnalysisIdToFuncMapping) {
137 id_to_func_.clear();
138 }
139 if (analyses_to_invalidate & kAnalysisConstants) {
140 constant_mgr_.reset(nullptr);
141 }
142 if (analyses_to_invalidate & kAnalysisTypes) {
143 type_mgr_.reset(nullptr);
144 }
145
146 valid_analyses_ = Analysis(valid_analyses_ & ~analyses_to_invalidate);
147}
148
149Instruction* IRContext::KillInst(Instruction* inst) {
150 if (!inst) {
151 return nullptr;
152 }
153
154 KillNamesAndDecorates(inst);
155
156 if (AreAnalysesValid(kAnalysisDefUse)) {
157 get_def_use_mgr()->ClearInst(inst);
158 }
159 if (AreAnalysesValid(kAnalysisInstrToBlockMapping)) {
160 instr_to_block_.erase(inst);
161 }
162 if (AreAnalysesValid(kAnalysisDecorations)) {
163 if (inst->IsDecoration()) {
164 decoration_mgr_->RemoveDecoration(inst);
165 }
166 }
167 if (type_mgr_ && IsTypeInst(inst->opcode())) {
168 type_mgr_->RemoveId(inst->result_id());
169 }
170 if (constant_mgr_ && IsConstantInst(inst->opcode())) {
171 constant_mgr_->RemoveId(inst->result_id());
172 }
173 if (inst->opcode() == SpvOpCapability || inst->opcode() == SpvOpExtension) {
174 // We reset the feature manager, instead of updating it, because it is just
175 // as much work. We would have to remove all capabilities implied by this
176 // capability that are not also implied by the remaining OpCapability
177 // instructions. We could update extensions, but we will see if it is
178 // needed.
179 ResetFeatureManager();
180 }
181
182 RemoveFromIdToName(inst);
183
184 Instruction* next_instruction = nullptr;
185 if (inst->IsInAList()) {
186 next_instruction = inst->NextNode();
187 inst->RemoveFromList();
188 delete inst;
189 } else {
190 // Needed for instructions that are not part of a list like OpLabels,
191 // OpFunction, OpFunctionEnd, etc..
192 inst->ToNop();
193 }
194 return next_instruction;
195}
196
197bool IRContext::KillDef(uint32_t id) {
198 Instruction* def = get_def_use_mgr()->GetDef(id);
199 if (def != nullptr) {
200 KillInst(def);
201 return true;
202 }
203 return false;
204}
205
206bool IRContext::ReplaceAllUsesWith(uint32_t before, uint32_t after) {
207 return ReplaceAllUsesWithPredicate(
208 before, after, [](Instruction*, uint32_t) { return true; });
209}
210
211bool IRContext::ReplaceAllUsesWithPredicate(
212 uint32_t before, uint32_t after,
213 const std::function<bool(Instruction*, uint32_t)>& predicate) {
214 if (before == after) return false;
215
216 // Ensure that |after| has been registered as def.
217 assert(get_def_use_mgr()->GetDef(after) &&
218 "'after' is not a registered def.");
219
220 std::vector<std::pair<Instruction*, uint32_t>> uses_to_update;
221 get_def_use_mgr()->ForEachUse(
222 before, [&predicate, &uses_to_update](Instruction* user, uint32_t index) {
223 if (predicate(user, index)) {
224 uses_to_update.emplace_back(user, index);
225 }
226 });
227
228 Instruction* prev = nullptr;
229 for (auto p : uses_to_update) {
230 Instruction* user = p.first;
231 uint32_t index = p.second;
232 if (prev == nullptr || prev != user) {
233 ForgetUses(user);
234 prev = user;
235 }
236 const uint32_t type_result_id_count =
237 (user->result_id() != 0) + (user->type_id() != 0);
238
239 if (index < type_result_id_count) {
240 // Update the type_id. Note that result id is immutable so it should
241 // never be updated.
242 if (user->type_id() != 0 && index == 0) {
243 user->SetResultType(after);
244 } else if (user->type_id() == 0) {
245 SPIRV_ASSERT(consumer_, false,
246 "Result type id considered as use while the instruction "
247 "doesn't have a result type id.");
248 (void)consumer_; // Makes the compiler happy for release build.
249 } else {
250 SPIRV_ASSERT(consumer_, false,
251 "Trying setting the immutable result id.");
252 }
253 } else {
254 // Update an in-operand.
255 uint32_t in_operand_pos = index - type_result_id_count;
256 // Make the modification in the instruction.
257 user->SetInOperand(in_operand_pos, {after});
258 }
259 AnalyzeUses(user);
260 }
261
262 return true;
263}
264
265bool IRContext::IsConsistent() {
266#ifndef SPIRV_CHECK_CONTEXT
267 return true;
268#endif
269 if (AreAnalysesValid(kAnalysisDefUse)) {
270 analysis::DefUseManager new_def_use(module());
271 if (*get_def_use_mgr() != new_def_use) {
272 return false;
273 }
274 }
275
276 if (AreAnalysesValid(kAnalysisIdToFuncMapping)) {
277 for (auto& fn : *module_) {
278 if (id_to_func_[fn.result_id()] != &fn) {
279 return false;
280 }
281 }
282 }
283
284 if (AreAnalysesValid(kAnalysisInstrToBlockMapping)) {
285 for (auto& func : *module()) {
286 for (auto& block : func) {
287 if (!block.WhileEachInst([this, &block](Instruction* inst) {
288 if (get_instr_block(inst) != &block) {
289 return false;
290 }
291 return true;
292 }))
293 return false;
294 }
295 }
296 }
297
298 if (!CheckCFG()) {
299 return false;
300 }
301
302 if (AreAnalysesValid(kAnalysisDecorations)) {
303 analysis::DecorationManager* dec_mgr = get_decoration_mgr();
304 analysis::DecorationManager current(module());
305
306 if (*dec_mgr != current) {
307 return false;
308 }
309 }
310
311 if (feature_mgr_ != nullptr) {
312 FeatureManager current(grammar_);
313 current.Analyze(module());
314
315 if (current != *feature_mgr_) {
316 return false;
317 }
318 }
319 return true;
320}
321
322void IRContext::ForgetUses(Instruction* inst) {
323 if (AreAnalysesValid(kAnalysisDefUse)) {
324 get_def_use_mgr()->EraseUseRecordsOfOperandIds(inst);
325 }
326 if (AreAnalysesValid(kAnalysisDecorations)) {
327 if (inst->IsDecoration()) {
328 get_decoration_mgr()->RemoveDecoration(inst);
329 }
330 }
331 RemoveFromIdToName(inst);
332}
333
334void IRContext::AnalyzeUses(Instruction* inst) {
335 if (AreAnalysesValid(kAnalysisDefUse)) {
336 get_def_use_mgr()->AnalyzeInstUse(inst);
337 }
338 if (AreAnalysesValid(kAnalysisDecorations)) {
339 if (inst->IsDecoration()) {
340 get_decoration_mgr()->AddDecoration(inst);
341 }
342 }
343 if (id_to_name_ &&
344 (inst->opcode() == SpvOpName || inst->opcode() == SpvOpMemberName)) {
345 id_to_name_->insert({inst->GetSingleWordInOperand(0), inst});
346 }
347}
348
349void IRContext::KillNamesAndDecorates(uint32_t id) {
350 analysis::DecorationManager* dec_mgr = get_decoration_mgr();
351 dec_mgr->RemoveDecorationsFrom(id);
352
353 std::vector<Instruction*> name_to_kill;
354 for (auto name : GetNames(id)) {
355 name_to_kill.push_back(name.second);
356 }
357 for (Instruction* name_inst : name_to_kill) {
358 KillInst(name_inst);
359 }
360}
361
362void IRContext::KillNamesAndDecorates(Instruction* inst) {
363 const uint32_t rId = inst->result_id();
364 if (rId == 0) return;
365 KillNamesAndDecorates(rId);
366}
367
368void IRContext::AddCombinatorsForCapability(uint32_t capability) {
369 if (capability == SpvCapabilityShader) {
370 combinator_ops_[0].insert({SpvOpNop,
371 SpvOpUndef,
372 SpvOpConstant,
373 SpvOpConstantTrue,
374 SpvOpConstantFalse,
375 SpvOpConstantComposite,
376 SpvOpConstantSampler,
377 SpvOpConstantNull,
378 SpvOpTypeVoid,
379 SpvOpTypeBool,
380 SpvOpTypeInt,
381 SpvOpTypeFloat,
382 SpvOpTypeVector,
383 SpvOpTypeMatrix,
384 SpvOpTypeImage,
385 SpvOpTypeSampler,
386 SpvOpTypeSampledImage,
387 SpvOpTypeAccelerationStructureNV,
388 SpvOpTypeAccelerationStructureKHR,
389 SpvOpTypeRayQueryProvisionalKHR,
390 SpvOpTypeArray,
391 SpvOpTypeRuntimeArray,
392 SpvOpTypeStruct,
393 SpvOpTypeOpaque,
394 SpvOpTypePointer,
395 SpvOpTypeFunction,
396 SpvOpTypeEvent,
397 SpvOpTypeDeviceEvent,
398 SpvOpTypeReserveId,
399 SpvOpTypeQueue,
400 SpvOpTypePipe,
401 SpvOpTypeForwardPointer,
402 SpvOpVariable,
403 SpvOpImageTexelPointer,
404 SpvOpLoad,
405 SpvOpAccessChain,
406 SpvOpInBoundsAccessChain,
407 SpvOpArrayLength,
408 SpvOpVectorExtractDynamic,
409 SpvOpVectorInsertDynamic,
410 SpvOpVectorShuffle,
411 SpvOpCompositeConstruct,
412 SpvOpCompositeExtract,
413 SpvOpCompositeInsert,
414 SpvOpCopyObject,
415 SpvOpTranspose,
416 SpvOpSampledImage,
417 SpvOpImageSampleImplicitLod,
418 SpvOpImageSampleExplicitLod,
419 SpvOpImageSampleDrefImplicitLod,
420 SpvOpImageSampleDrefExplicitLod,
421 SpvOpImageSampleProjImplicitLod,
422 SpvOpImageSampleProjExplicitLod,
423 SpvOpImageSampleProjDrefImplicitLod,
424 SpvOpImageSampleProjDrefExplicitLod,
425 SpvOpImageFetch,
426 SpvOpImageGather,
427 SpvOpImageDrefGather,
428 SpvOpImageRead,
429 SpvOpImage,
430 SpvOpImageQueryFormat,
431 SpvOpImageQueryOrder,
432 SpvOpImageQuerySizeLod,
433 SpvOpImageQuerySize,
434 SpvOpImageQueryLevels,
435 SpvOpImageQuerySamples,
436 SpvOpConvertFToU,
437 SpvOpConvertFToS,
438 SpvOpConvertSToF,
439 SpvOpConvertUToF,
440 SpvOpUConvert,
441 SpvOpSConvert,
442 SpvOpFConvert,
443 SpvOpQuantizeToF16,
444 SpvOpBitcast,
445 SpvOpSNegate,
446 SpvOpFNegate,
447 SpvOpIAdd,
448 SpvOpFAdd,
449 SpvOpISub,
450 SpvOpFSub,
451 SpvOpIMul,
452 SpvOpFMul,
453 SpvOpUDiv,
454 SpvOpSDiv,
455 SpvOpFDiv,
456 SpvOpUMod,
457 SpvOpSRem,
458 SpvOpSMod,
459 SpvOpFRem,
460 SpvOpFMod,
461 SpvOpVectorTimesScalar,
462 SpvOpMatrixTimesScalar,
463 SpvOpVectorTimesMatrix,
464 SpvOpMatrixTimesVector,
465 SpvOpMatrixTimesMatrix,
466 SpvOpOuterProduct,
467 SpvOpDot,
468 SpvOpIAddCarry,
469 SpvOpISubBorrow,
470 SpvOpUMulExtended,
471 SpvOpSMulExtended,
472 SpvOpAny,
473 SpvOpAll,
474 SpvOpIsNan,
475 SpvOpIsInf,
476 SpvOpLogicalEqual,
477 SpvOpLogicalNotEqual,
478 SpvOpLogicalOr,
479 SpvOpLogicalAnd,
480 SpvOpLogicalNot,
481 SpvOpSelect,
482 SpvOpIEqual,
483 SpvOpINotEqual,
484 SpvOpUGreaterThan,
485 SpvOpSGreaterThan,
486 SpvOpUGreaterThanEqual,
487 SpvOpSGreaterThanEqual,
488 SpvOpULessThan,
489 SpvOpSLessThan,
490 SpvOpULessThanEqual,
491 SpvOpSLessThanEqual,
492 SpvOpFOrdEqual,
493 SpvOpFUnordEqual,
494 SpvOpFOrdNotEqual,
495 SpvOpFUnordNotEqual,
496 SpvOpFOrdLessThan,
497 SpvOpFUnordLessThan,
498 SpvOpFOrdGreaterThan,
499 SpvOpFUnordGreaterThan,
500 SpvOpFOrdLessThanEqual,
501 SpvOpFUnordLessThanEqual,
502 SpvOpFOrdGreaterThanEqual,
503 SpvOpFUnordGreaterThanEqual,
504 SpvOpShiftRightLogical,
505 SpvOpShiftRightArithmetic,
506 SpvOpShiftLeftLogical,
507 SpvOpBitwiseOr,
508 SpvOpBitwiseXor,
509 SpvOpBitwiseAnd,
510 SpvOpNot,
511 SpvOpBitFieldInsert,
512 SpvOpBitFieldSExtract,
513 SpvOpBitFieldUExtract,
514 SpvOpBitReverse,
515 SpvOpBitCount,
516 SpvOpPhi,
517 SpvOpImageSparseSampleImplicitLod,
518 SpvOpImageSparseSampleExplicitLod,
519 SpvOpImageSparseSampleDrefImplicitLod,
520 SpvOpImageSparseSampleDrefExplicitLod,
521 SpvOpImageSparseSampleProjImplicitLod,
522 SpvOpImageSparseSampleProjExplicitLod,
523 SpvOpImageSparseSampleProjDrefImplicitLod,
524 SpvOpImageSparseSampleProjDrefExplicitLod,
525 SpvOpImageSparseFetch,
526 SpvOpImageSparseGather,
527 SpvOpImageSparseDrefGather,
528 SpvOpImageSparseTexelsResident,
529 SpvOpImageSparseRead,
530 SpvOpSizeOf});
531 }
532}
533
534void IRContext::AddCombinatorsForExtension(Instruction* extension) {
535 assert(extension->opcode() == SpvOpExtInstImport &&
536 "Expecting an import of an extension's instruction set.");
537 const char* extension_name =
538 reinterpret_cast<const char*>(&extension->GetInOperand(0).words[0]);
539 if (!strcmp(extension_name, "GLSL.std.450")) {
540 combinator_ops_[extension->result_id()] = {GLSLstd450Round,
541 GLSLstd450RoundEven,
542 GLSLstd450Trunc,
543 GLSLstd450FAbs,
544 GLSLstd450SAbs,
545 GLSLstd450FSign,
546 GLSLstd450SSign,
547 GLSLstd450Floor,
548 GLSLstd450Ceil,
549 GLSLstd450Fract,
550 GLSLstd450Radians,
551 GLSLstd450Degrees,
552 GLSLstd450Sin,
553 GLSLstd450Cos,
554 GLSLstd450Tan,
555 GLSLstd450Asin,
556 GLSLstd450Acos,
557 GLSLstd450Atan,
558 GLSLstd450Sinh,
559 GLSLstd450Cosh,
560 GLSLstd450Tanh,
561 GLSLstd450Asinh,
562 GLSLstd450Acosh,
563 GLSLstd450Atanh,
564 GLSLstd450Atan2,
565 GLSLstd450Pow,
566 GLSLstd450Exp,
567 GLSLstd450Log,
568 GLSLstd450Exp2,
569 GLSLstd450Log2,
570 GLSLstd450Sqrt,
571 GLSLstd450InverseSqrt,
572 GLSLstd450Determinant,
573 GLSLstd450MatrixInverse,
574 GLSLstd450ModfStruct,
575 GLSLstd450FMin,
576 GLSLstd450UMin,
577 GLSLstd450SMin,
578 GLSLstd450FMax,
579 GLSLstd450UMax,
580 GLSLstd450SMax,
581 GLSLstd450FClamp,
582 GLSLstd450UClamp,
583 GLSLstd450SClamp,
584 GLSLstd450FMix,
585 GLSLstd450IMix,
586 GLSLstd450Step,
587 GLSLstd450SmoothStep,
588 GLSLstd450Fma,
589 GLSLstd450FrexpStruct,
590 GLSLstd450Ldexp,
591 GLSLstd450PackSnorm4x8,
592 GLSLstd450PackUnorm4x8,
593 GLSLstd450PackSnorm2x16,
594 GLSLstd450PackUnorm2x16,
595 GLSLstd450PackHalf2x16,
596 GLSLstd450PackDouble2x32,
597 GLSLstd450UnpackSnorm2x16,
598 GLSLstd450UnpackUnorm2x16,
599 GLSLstd450UnpackHalf2x16,
600 GLSLstd450UnpackSnorm4x8,
601 GLSLstd450UnpackUnorm4x8,
602 GLSLstd450UnpackDouble2x32,
603 GLSLstd450Length,
604 GLSLstd450Distance,
605 GLSLstd450Cross,
606 GLSLstd450Normalize,
607 GLSLstd450FaceForward,
608 GLSLstd450Reflect,
609 GLSLstd450Refract,
610 GLSLstd450FindILsb,
611 GLSLstd450FindSMsb,
612 GLSLstd450FindUMsb,
613 GLSLstd450InterpolateAtCentroid,
614 GLSLstd450InterpolateAtSample,
615 GLSLstd450InterpolateAtOffset,
616 GLSLstd450NMin,
617 GLSLstd450NMax,
618 GLSLstd450NClamp};
619 } else {
620 // Map the result id to the empty set.
621 combinator_ops_[extension->result_id()];
622 }
623}
624
625void IRContext::InitializeCombinators() {
626 get_feature_mgr()->GetCapabilities()->ForEach(
627 [this](SpvCapability cap) { AddCombinatorsForCapability(cap); });
628
629 for (auto& extension : module()->ext_inst_imports()) {
630 AddCombinatorsForExtension(&extension);
631 }
632
633 valid_analyses_ |= kAnalysisCombinators;
634}
635
636void IRContext::RemoveFromIdToName(const Instruction* inst) {
637 if (id_to_name_ &&
638 (inst->opcode() == SpvOpName || inst->opcode() == SpvOpMemberName)) {
639 auto range = id_to_name_->equal_range(inst->GetSingleWordInOperand(0));
640 for (auto it = range.first; it != range.second; ++it) {
641 if (it->second == inst) {
642 id_to_name_->erase(it);
643 break;
644 }
645 }
646 }
647}
648
649LoopDescriptor* IRContext::GetLoopDescriptor(const Function* f) {
650 if (!AreAnalysesValid(kAnalysisLoopAnalysis)) {
651 ResetLoopAnalysis();
652 }
653
654 std::unordered_map<const Function*, LoopDescriptor>::iterator it =
655 loop_descriptors_.find(f);
656 if (it == loop_descriptors_.end()) {
657 return &loop_descriptors_
658 .emplace(std::make_pair(f, LoopDescriptor(this, f)))
659 .first->second;
660 }
661
662 return &it->second;
663}
664
665uint32_t IRContext::FindBuiltinInputVar(uint32_t builtin) {
666 for (auto& a : module_->annotations()) {
667 if (a.opcode() != SpvOpDecorate) continue;
668 if (a.GetSingleWordInOperand(kSpvDecorateDecorationInIdx) !=
669 SpvDecorationBuiltIn)
670 continue;
671 if (a.GetSingleWordInOperand(kSpvDecorateBuiltinInIdx) != builtin) continue;
672 uint32_t target_id = a.GetSingleWordInOperand(kSpvDecorateTargetIdInIdx);
673 Instruction* b_var = get_def_use_mgr()->GetDef(target_id);
674 if (b_var->opcode() != SpvOpVariable) continue;
675 if (b_var->GetSingleWordInOperand(0) != SpvStorageClassInput) continue;
676 return target_id;
677 }
678 return 0;
679}
680
681void IRContext::AddVarToEntryPoints(uint32_t var_id) {
682 uint32_t ocnt = 0;
683 for (auto& e : module()->entry_points()) {
684 bool found = false;
685 e.ForEachInOperand([&ocnt, &found, &var_id](const uint32_t* idp) {
686 if (ocnt >= kEntryPointInterfaceInIdx) {
687 if (*idp == var_id) found = true;
688 }
689 ++ocnt;
690 });
691 if (!found) {
692 e.AddOperand({SPV_OPERAND_TYPE_ID, {var_id}});
693 get_def_use_mgr()->AnalyzeInstDefUse(&e);
694 }
695 }
696}
697
698uint32_t IRContext::GetBuiltinInputVarId(uint32_t builtin) {
699 if (!AreAnalysesValid(kAnalysisBuiltinVarId)) ResetBuiltinAnalysis();
700 // If cached, return it.
701 std::unordered_map<uint32_t, uint32_t>::iterator it =
702 builtin_var_id_map_.find(builtin);
703 if (it != builtin_var_id_map_.end()) return it->second;
704 // Look for one in shader
705 uint32_t var_id = FindBuiltinInputVar(builtin);
706 if (var_id == 0) {
707 // If not found, create it
708 // TODO(greg-lunarg): Add support for all builtins
709 analysis::TypeManager* type_mgr = get_type_mgr();
710 analysis::Type* reg_type;
711 switch (builtin) {
712 case SpvBuiltInFragCoord: {
713 analysis::Float float_ty(32);
714 analysis::Type* reg_float_ty = type_mgr->GetRegisteredType(&float_ty);
715 analysis::Vector v4float_ty(reg_float_ty, 4);
716 reg_type = type_mgr->GetRegisteredType(&v4float_ty);
717 break;
718 }
719 case SpvBuiltInVertexIndex:
720 case SpvBuiltInInstanceIndex:
721 case SpvBuiltInPrimitiveId:
722 case SpvBuiltInInvocationId:
723 case SpvBuiltInSubgroupLocalInvocationId: {
724 analysis::Integer uint_ty(32, false);
725 reg_type = type_mgr->GetRegisteredType(&uint_ty);
726 break;
727 }
728 case SpvBuiltInGlobalInvocationId:
729 case SpvBuiltInLaunchIdNV: {
730 analysis::Integer uint_ty(32, false);
731 analysis::Type* reg_uint_ty = type_mgr->GetRegisteredType(&uint_ty);
732 analysis::Vector v3uint_ty(reg_uint_ty, 3);
733 reg_type = type_mgr->GetRegisteredType(&v3uint_ty);
734 break;
735 }
736 case SpvBuiltInTessCoord: {
737 analysis::Float float_ty(32);
738 analysis::Type* reg_float_ty = type_mgr->GetRegisteredType(&float_ty);
739 analysis::Vector v3float_ty(reg_float_ty, 3);
740 reg_type = type_mgr->GetRegisteredType(&v3float_ty);
741 break;
742 }
743 case SpvBuiltInSubgroupLtMask: {
744 analysis::Integer uint_ty(32, false);
745 analysis::Type* reg_uint_ty = type_mgr->GetRegisteredType(&uint_ty);
746 analysis::Vector v4uint_ty(reg_uint_ty, 4);
747 reg_type = type_mgr->GetRegisteredType(&v4uint_ty);
748 break;
749 }
750 default: {
751 assert(false && "unhandled builtin");
752 return 0;
753 }
754 }
755 uint32_t type_id = type_mgr->GetTypeInstruction(reg_type);
756 uint32_t varTyPtrId =
757 type_mgr->FindPointerToType(type_id, SpvStorageClassInput);
758 // TODO(1841): Handle id overflow.
759 var_id = TakeNextId();
760 std::unique_ptr<Instruction> newVarOp(
761 new Instruction(this, SpvOpVariable, varTyPtrId, var_id,
762 {{spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER,
763 {SpvStorageClassInput}}}));
764 get_def_use_mgr()->AnalyzeInstDefUse(&*newVarOp);
765 module()->AddGlobalValue(std::move(newVarOp));
766 get_decoration_mgr()->AddDecorationVal(var_id, SpvDecorationBuiltIn,
767 builtin);
768 AddVarToEntryPoints(var_id);
769 }
770 builtin_var_id_map_[builtin] = var_id;
771 return var_id;
772}
773
774void IRContext::AddCalls(const Function* func, std::queue<uint32_t>* todo) {
775 for (auto bi = func->begin(); bi != func->end(); ++bi)
776 for (auto ii = bi->begin(); ii != bi->end(); ++ii)
777 if (ii->opcode() == SpvOpFunctionCall)
778 todo->push(ii->GetSingleWordInOperand(0));
779}
780
781bool IRContext::ProcessEntryPointCallTree(ProcessFunction& pfn) {
782 // Collect all of the entry points as the roots.
783 std::queue<uint32_t> roots;
784 for (auto& e : module()->entry_points()) {
785 roots.push(e.GetSingleWordInOperand(kEntryPointFunctionIdInIdx));
786 }
787 return ProcessCallTreeFromRoots(pfn, &roots);
788}
789
790bool IRContext::ProcessReachableCallTree(ProcessFunction& pfn) {
791 std::queue<uint32_t> roots;
792
793 // Add all entry points since they can be reached from outside the module.
794 for (auto& e : module()->entry_points())
795 roots.push(e.GetSingleWordInOperand(kEntryPointFunctionIdInIdx));
796
797 // Add all exported functions since they can be reached from outside the
798 // module.
799 for (auto& a : annotations()) {
800 // TODO: Handle group decorations as well. Currently not generate by any
801 // front-end, but could be coming.
802 if (a.opcode() == SpvOp::SpvOpDecorate) {
803 if (a.GetSingleWordOperand(1) ==
804 SpvDecoration::SpvDecorationLinkageAttributes) {
805 uint32_t lastOperand = a.NumOperands() - 1;
806 if (a.GetSingleWordOperand(lastOperand) ==
807 SpvLinkageType::SpvLinkageTypeExport) {
808 uint32_t id = a.GetSingleWordOperand(0);
809 if (GetFunction(id)) {
810 roots.push(id);
811 }
812 }
813 }
814 }
815 }
816
817 return ProcessCallTreeFromRoots(pfn, &roots);
818}
819
820bool IRContext::ProcessCallTreeFromRoots(ProcessFunction& pfn,
821 std::queue<uint32_t>* roots) {
822 // Process call tree
823 bool modified = false;
824 std::unordered_set<uint32_t> done;
825
826 while (!roots->empty()) {
827 const uint32_t fi = roots->front();
828 roots->pop();
829 if (done.insert(fi).second) {
830 Function* fn = GetFunction(fi);
831 assert(fn && "Trying to process a function that does not exist.");
832 modified = pfn(fn) || modified;
833 AddCalls(fn, roots);
834 }
835 }
836 return modified;
837}
838
839void IRContext::EmitErrorMessage(std::string message, Instruction* inst) {
840 if (!consumer()) {
841 return;
842 }
843
844 Instruction* line_inst = inst;
845 while (line_inst != nullptr) { // Stop at the beginning of the basic block.
846 if (!line_inst->dbg_line_insts().empty()) {
847 line_inst = &line_inst->dbg_line_insts().back();
848 if (line_inst->opcode() == SpvOpNoLine) {
849 line_inst = nullptr;
850 }
851 break;
852 }
853 line_inst = line_inst->PreviousNode();
854 }
855
856 uint32_t line_number = 0;
857 uint32_t col_number = 0;
858 char* source = nullptr;
859 if (line_inst != nullptr) {
860 Instruction* file_name =
861 get_def_use_mgr()->GetDef(line_inst->GetSingleWordInOperand(0));
862 source = reinterpret_cast<char*>(&file_name->GetInOperand(0).words[0]);
863
864 // Get the line number and column number.
865 line_number = line_inst->GetSingleWordInOperand(1);
866 col_number = line_inst->GetSingleWordInOperand(2);
867 }
868
869 message +=
870 "\n " + inst->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES);
871 consumer()(SPV_MSG_ERROR, source, {line_number, col_number, 0},
872 message.c_str());
873}
874
875// Gets the dominator analysis for function |f|.
876DominatorAnalysis* IRContext::GetDominatorAnalysis(const Function* f) {
877 if (!AreAnalysesValid(kAnalysisDominatorAnalysis)) {
878 ResetDominatorAnalysis();
879 }
880
881 if (dominator_trees_.find(f) == dominator_trees_.end()) {
882 dominator_trees_[f].InitializeTree(*cfg(), f);
883 }
884
885 return &dominator_trees_[f];
886}
887
888// Gets the postdominator analysis for function |f|.
889PostDominatorAnalysis* IRContext::GetPostDominatorAnalysis(const Function* f) {
890 if (!AreAnalysesValid(kAnalysisDominatorAnalysis)) {
891 ResetDominatorAnalysis();
892 }
893
894 if (post_dominator_trees_.find(f) == post_dominator_trees_.end()) {
895 post_dominator_trees_[f].InitializeTree(*cfg(), f);
896 }
897
898 return &post_dominator_trees_[f];
899}
900
901bool IRContext::CheckCFG() {
902 std::unordered_map<uint32_t, std::vector<uint32_t>> real_preds;
903 if (!AreAnalysesValid(kAnalysisCFG)) {
904 return true;
905 }
906
907 for (Function& function : *module()) {
908 for (const auto& bb : function) {
909 bb.ForEachSuccessorLabel([&bb, &real_preds](const uint32_t lab_id) {
910 real_preds[lab_id].push_back(bb.id());
911 });
912 }
913
914 for (auto& bb : function) {
915 std::vector<uint32_t> preds = cfg()->preds(bb.id());
916 std::vector<uint32_t> real = real_preds[bb.id()];
917 std::sort(preds.begin(), preds.end());
918 std::sort(real.begin(), real.end());
919
920 bool same = true;
921 if (preds.size() != real.size()) {
922 same = false;
923 }
924
925 for (size_t i = 0; i < real.size() && same; i++) {
926 if (preds[i] != real[i]) {
927 same = false;
928 }
929 }
930
931 if (!same) {
932 std::cerr << "Predecessors for " << bb.id() << " are different:\n";
933
934 std::cerr << "Real:";
935 for (uint32_t i : real) {
936 std::cerr << ' ' << i;
937 }
938 std::cerr << std::endl;
939
940 std::cerr << "Recorded:";
941 for (uint32_t i : preds) {
942 std::cerr << ' ' << i;
943 }
944 std::cerr << std::endl;
945 }
946 if (!same) return false;
947 }
948 }
949
950 return true;
951}
952} // namespace opt
953} // namespace spvtools
954