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