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
24 namespace {
25
26 static const int kSpvDecorateTargetIdInIdx = 0;
27 static const int kSpvDecorateDecorationInIdx = 1;
28 static const int kSpvDecorateBuiltinInIdx = 2;
29 static const int kEntryPointInterfaceInIdx = 3;
30 static const int kEntryPointFunctionIdInIdx = 1;
31
32 } // anonymous namespace
33
34 namespace spvtools {
35 namespace opt {
36
BuildInvalidAnalyses(IRContext::Analysis set)37 void 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
InvalidateAnalysesExceptFor(IRContext::Analysis preserved_analyses)85 void 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
InvalidateAnalyses(IRContext::Analysis analyses_to_invalidate)91 void 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
KillInst(Instruction * inst)149 Instruction* 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
KillDef(uint32_t id)197 bool 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
ReplaceAllUsesWith(uint32_t before,uint32_t after)206 bool IRContext::ReplaceAllUsesWith(uint32_t before, uint32_t after) {
207 return ReplaceAllUsesWithPredicate(
208 before, after, [](Instruction*, uint32_t) { return true; });
209 }
210
ReplaceAllUsesWithPredicate(uint32_t before,uint32_t after,const std::function<bool (Instruction *,uint32_t)> & predicate)211 bool 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
IsConsistent()265 bool 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
ForgetUses(Instruction * inst)322 void 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
AnalyzeUses(Instruction * inst)334 void 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
KillNamesAndDecorates(uint32_t id)349 void 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
KillNamesAndDecorates(Instruction * inst)362 void IRContext::KillNamesAndDecorates(Instruction* inst) {
363 const uint32_t rId = inst->result_id();
364 if (rId == 0) return;
365 KillNamesAndDecorates(rId);
366 }
367
AddCombinatorsForCapability(uint32_t capability)368 void 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 SpvOpTypeArray,
389 SpvOpTypeRuntimeArray,
390 SpvOpTypeStruct,
391 SpvOpTypeOpaque,
392 SpvOpTypePointer,
393 SpvOpTypeFunction,
394 SpvOpTypeEvent,
395 SpvOpTypeDeviceEvent,
396 SpvOpTypeReserveId,
397 SpvOpTypeQueue,
398 SpvOpTypePipe,
399 SpvOpTypeForwardPointer,
400 SpvOpVariable,
401 SpvOpImageTexelPointer,
402 SpvOpLoad,
403 SpvOpAccessChain,
404 SpvOpInBoundsAccessChain,
405 SpvOpArrayLength,
406 SpvOpVectorExtractDynamic,
407 SpvOpVectorInsertDynamic,
408 SpvOpVectorShuffle,
409 SpvOpCompositeConstruct,
410 SpvOpCompositeExtract,
411 SpvOpCompositeInsert,
412 SpvOpCopyObject,
413 SpvOpTranspose,
414 SpvOpSampledImage,
415 SpvOpImageSampleImplicitLod,
416 SpvOpImageSampleExplicitLod,
417 SpvOpImageSampleDrefImplicitLod,
418 SpvOpImageSampleDrefExplicitLod,
419 SpvOpImageSampleProjImplicitLod,
420 SpvOpImageSampleProjExplicitLod,
421 SpvOpImageSampleProjDrefImplicitLod,
422 SpvOpImageSampleProjDrefExplicitLod,
423 SpvOpImageFetch,
424 SpvOpImageGather,
425 SpvOpImageDrefGather,
426 SpvOpImageRead,
427 SpvOpImage,
428 SpvOpImageQueryFormat,
429 SpvOpImageQueryOrder,
430 SpvOpImageQuerySizeLod,
431 SpvOpImageQuerySize,
432 SpvOpImageQueryLevels,
433 SpvOpImageQuerySamples,
434 SpvOpConvertFToU,
435 SpvOpConvertFToS,
436 SpvOpConvertSToF,
437 SpvOpConvertUToF,
438 SpvOpUConvert,
439 SpvOpSConvert,
440 SpvOpFConvert,
441 SpvOpQuantizeToF16,
442 SpvOpBitcast,
443 SpvOpSNegate,
444 SpvOpFNegate,
445 SpvOpIAdd,
446 SpvOpFAdd,
447 SpvOpISub,
448 SpvOpFSub,
449 SpvOpIMul,
450 SpvOpFMul,
451 SpvOpUDiv,
452 SpvOpSDiv,
453 SpvOpFDiv,
454 SpvOpUMod,
455 SpvOpSRem,
456 SpvOpSMod,
457 SpvOpFRem,
458 SpvOpFMod,
459 SpvOpVectorTimesScalar,
460 SpvOpMatrixTimesScalar,
461 SpvOpVectorTimesMatrix,
462 SpvOpMatrixTimesVector,
463 SpvOpMatrixTimesMatrix,
464 SpvOpOuterProduct,
465 SpvOpDot,
466 SpvOpIAddCarry,
467 SpvOpISubBorrow,
468 SpvOpUMulExtended,
469 SpvOpSMulExtended,
470 SpvOpAny,
471 SpvOpAll,
472 SpvOpIsNan,
473 SpvOpIsInf,
474 SpvOpLogicalEqual,
475 SpvOpLogicalNotEqual,
476 SpvOpLogicalOr,
477 SpvOpLogicalAnd,
478 SpvOpLogicalNot,
479 SpvOpSelect,
480 SpvOpIEqual,
481 SpvOpINotEqual,
482 SpvOpUGreaterThan,
483 SpvOpSGreaterThan,
484 SpvOpUGreaterThanEqual,
485 SpvOpSGreaterThanEqual,
486 SpvOpULessThan,
487 SpvOpSLessThan,
488 SpvOpULessThanEqual,
489 SpvOpSLessThanEqual,
490 SpvOpFOrdEqual,
491 SpvOpFUnordEqual,
492 SpvOpFOrdNotEqual,
493 SpvOpFUnordNotEqual,
494 SpvOpFOrdLessThan,
495 SpvOpFUnordLessThan,
496 SpvOpFOrdGreaterThan,
497 SpvOpFUnordGreaterThan,
498 SpvOpFOrdLessThanEqual,
499 SpvOpFUnordLessThanEqual,
500 SpvOpFOrdGreaterThanEqual,
501 SpvOpFUnordGreaterThanEqual,
502 SpvOpShiftRightLogical,
503 SpvOpShiftRightArithmetic,
504 SpvOpShiftLeftLogical,
505 SpvOpBitwiseOr,
506 SpvOpBitwiseXor,
507 SpvOpBitwiseAnd,
508 SpvOpNot,
509 SpvOpBitFieldInsert,
510 SpvOpBitFieldSExtract,
511 SpvOpBitFieldUExtract,
512 SpvOpBitReverse,
513 SpvOpBitCount,
514 SpvOpPhi,
515 SpvOpImageSparseSampleImplicitLod,
516 SpvOpImageSparseSampleExplicitLod,
517 SpvOpImageSparseSampleDrefImplicitLod,
518 SpvOpImageSparseSampleDrefExplicitLod,
519 SpvOpImageSparseSampleProjImplicitLod,
520 SpvOpImageSparseSampleProjExplicitLod,
521 SpvOpImageSparseSampleProjDrefImplicitLod,
522 SpvOpImageSparseSampleProjDrefExplicitLod,
523 SpvOpImageSparseFetch,
524 SpvOpImageSparseGather,
525 SpvOpImageSparseDrefGather,
526 SpvOpImageSparseTexelsResident,
527 SpvOpImageSparseRead,
528 SpvOpSizeOf});
529 }
530 }
531
AddCombinatorsForExtension(Instruction * extension)532 void IRContext::AddCombinatorsForExtension(Instruction* extension) {
533 assert(extension->opcode() == SpvOpExtInstImport &&
534 "Expecting an import of an extension's instruction set.");
535 const char* extension_name =
536 reinterpret_cast<const char*>(&extension->GetInOperand(0).words[0]);
537 if (!strcmp(extension_name, "GLSL.std.450")) {
538 combinator_ops_[extension->result_id()] = {GLSLstd450Round,
539 GLSLstd450RoundEven,
540 GLSLstd450Trunc,
541 GLSLstd450FAbs,
542 GLSLstd450SAbs,
543 GLSLstd450FSign,
544 GLSLstd450SSign,
545 GLSLstd450Floor,
546 GLSLstd450Ceil,
547 GLSLstd450Fract,
548 GLSLstd450Radians,
549 GLSLstd450Degrees,
550 GLSLstd450Sin,
551 GLSLstd450Cos,
552 GLSLstd450Tan,
553 GLSLstd450Asin,
554 GLSLstd450Acos,
555 GLSLstd450Atan,
556 GLSLstd450Sinh,
557 GLSLstd450Cosh,
558 GLSLstd450Tanh,
559 GLSLstd450Asinh,
560 GLSLstd450Acosh,
561 GLSLstd450Atanh,
562 GLSLstd450Atan2,
563 GLSLstd450Pow,
564 GLSLstd450Exp,
565 GLSLstd450Log,
566 GLSLstd450Exp2,
567 GLSLstd450Log2,
568 GLSLstd450Sqrt,
569 GLSLstd450InverseSqrt,
570 GLSLstd450Determinant,
571 GLSLstd450MatrixInverse,
572 GLSLstd450ModfStruct,
573 GLSLstd450FMin,
574 GLSLstd450UMin,
575 GLSLstd450SMin,
576 GLSLstd450FMax,
577 GLSLstd450UMax,
578 GLSLstd450SMax,
579 GLSLstd450FClamp,
580 GLSLstd450UClamp,
581 GLSLstd450SClamp,
582 GLSLstd450FMix,
583 GLSLstd450IMix,
584 GLSLstd450Step,
585 GLSLstd450SmoothStep,
586 GLSLstd450Fma,
587 GLSLstd450FrexpStruct,
588 GLSLstd450Ldexp,
589 GLSLstd450PackSnorm4x8,
590 GLSLstd450PackUnorm4x8,
591 GLSLstd450PackSnorm2x16,
592 GLSLstd450PackUnorm2x16,
593 GLSLstd450PackHalf2x16,
594 GLSLstd450PackDouble2x32,
595 GLSLstd450UnpackSnorm2x16,
596 GLSLstd450UnpackUnorm2x16,
597 GLSLstd450UnpackHalf2x16,
598 GLSLstd450UnpackSnorm4x8,
599 GLSLstd450UnpackUnorm4x8,
600 GLSLstd450UnpackDouble2x32,
601 GLSLstd450Length,
602 GLSLstd450Distance,
603 GLSLstd450Cross,
604 GLSLstd450Normalize,
605 GLSLstd450FaceForward,
606 GLSLstd450Reflect,
607 GLSLstd450Refract,
608 GLSLstd450FindILsb,
609 GLSLstd450FindSMsb,
610 GLSLstd450FindUMsb,
611 GLSLstd450InterpolateAtCentroid,
612 GLSLstd450InterpolateAtSample,
613 GLSLstd450InterpolateAtOffset,
614 GLSLstd450NMin,
615 GLSLstd450NMax,
616 GLSLstd450NClamp};
617 } else {
618 // Map the result id to the empty set.
619 combinator_ops_[extension->result_id()];
620 }
621 }
622
InitializeCombinators()623 void IRContext::InitializeCombinators() {
624 get_feature_mgr()->GetCapabilities()->ForEach(
625 [this](SpvCapability cap) { AddCombinatorsForCapability(cap); });
626
627 for (auto& extension : module()->ext_inst_imports()) {
628 AddCombinatorsForExtension(&extension);
629 }
630
631 valid_analyses_ |= kAnalysisCombinators;
632 }
633
RemoveFromIdToName(const Instruction * inst)634 void IRContext::RemoveFromIdToName(const Instruction* inst) {
635 if (id_to_name_ &&
636 (inst->opcode() == SpvOpName || inst->opcode() == SpvOpMemberName)) {
637 auto range = id_to_name_->equal_range(inst->GetSingleWordInOperand(0));
638 for (auto it = range.first; it != range.second; ++it) {
639 if (it->second == inst) {
640 id_to_name_->erase(it);
641 break;
642 }
643 }
644 }
645 }
646
GetLoopDescriptor(const Function * f)647 LoopDescriptor* IRContext::GetLoopDescriptor(const Function* f) {
648 if (!AreAnalysesValid(kAnalysisLoopAnalysis)) {
649 ResetLoopAnalysis();
650 }
651
652 std::unordered_map<const Function*, LoopDescriptor>::iterator it =
653 loop_descriptors_.find(f);
654 if (it == loop_descriptors_.end()) {
655 return &loop_descriptors_
656 .emplace(std::make_pair(f, LoopDescriptor(this, f)))
657 .first->second;
658 }
659
660 return &it->second;
661 }
662
FindBuiltinInputVar(uint32_t builtin)663 uint32_t IRContext::FindBuiltinInputVar(uint32_t builtin) {
664 for (auto& a : module_->annotations()) {
665 if (a.opcode() != SpvOpDecorate) continue;
666 if (a.GetSingleWordInOperand(kSpvDecorateDecorationInIdx) !=
667 SpvDecorationBuiltIn)
668 continue;
669 if (a.GetSingleWordInOperand(kSpvDecorateBuiltinInIdx) != builtin) continue;
670 uint32_t target_id = a.GetSingleWordInOperand(kSpvDecorateTargetIdInIdx);
671 Instruction* b_var = get_def_use_mgr()->GetDef(target_id);
672 if (b_var->opcode() != SpvOpVariable) continue;
673 if (b_var->GetSingleWordInOperand(0) != SpvStorageClassInput) continue;
674 return target_id;
675 }
676 return 0;
677 }
678
AddVarToEntryPoints(uint32_t var_id)679 void IRContext::AddVarToEntryPoints(uint32_t var_id) {
680 uint32_t ocnt = 0;
681 for (auto& e : module()->entry_points()) {
682 bool found = false;
683 e.ForEachInOperand([&ocnt, &found, &var_id](const uint32_t* idp) {
684 if (ocnt >= kEntryPointInterfaceInIdx) {
685 if (*idp == var_id) found = true;
686 }
687 ++ocnt;
688 });
689 if (!found) {
690 e.AddOperand({SPV_OPERAND_TYPE_ID, {var_id}});
691 get_def_use_mgr()->AnalyzeInstDefUse(&e);
692 }
693 }
694 }
695
GetBuiltinInputVarId(uint32_t builtin)696 uint32_t IRContext::GetBuiltinInputVarId(uint32_t builtin) {
697 if (!AreAnalysesValid(kAnalysisBuiltinVarId)) ResetBuiltinAnalysis();
698 // If cached, return it.
699 std::unordered_map<uint32_t, uint32_t>::iterator it =
700 builtin_var_id_map_.find(builtin);
701 if (it != builtin_var_id_map_.end()) return it->second;
702 // Look for one in shader
703 uint32_t var_id = FindBuiltinInputVar(builtin);
704 if (var_id == 0) {
705 // If not found, create it
706 // TODO(greg-lunarg): Add support for all builtins
707 analysis::TypeManager* type_mgr = get_type_mgr();
708 analysis::Type* reg_type;
709 switch (builtin) {
710 case SpvBuiltInFragCoord: {
711 analysis::Float float_ty(32);
712 analysis::Type* reg_float_ty = type_mgr->GetRegisteredType(&float_ty);
713 analysis::Vector v4float_ty(reg_float_ty, 4);
714 reg_type = type_mgr->GetRegisteredType(&v4float_ty);
715 break;
716 }
717 case SpvBuiltInVertexIndex:
718 case SpvBuiltInInstanceIndex:
719 case SpvBuiltInPrimitiveId:
720 case SpvBuiltInInvocationId:
721 case SpvBuiltInSubgroupLocalInvocationId: {
722 analysis::Integer uint_ty(32, false);
723 reg_type = type_mgr->GetRegisteredType(&uint_ty);
724 break;
725 }
726 case SpvBuiltInGlobalInvocationId:
727 case SpvBuiltInLaunchIdNV: {
728 analysis::Integer uint_ty(32, false);
729 analysis::Type* reg_uint_ty = type_mgr->GetRegisteredType(&uint_ty);
730 analysis::Vector v3uint_ty(reg_uint_ty, 3);
731 reg_type = type_mgr->GetRegisteredType(&v3uint_ty);
732 break;
733 }
734 case SpvBuiltInTessCoord: {
735 analysis::Float float_ty(32);
736 analysis::Type* reg_float_ty = type_mgr->GetRegisteredType(&float_ty);
737 analysis::Vector v3float_ty(reg_float_ty, 3);
738 reg_type = type_mgr->GetRegisteredType(&v3float_ty);
739 break;
740 }
741 case SpvBuiltInSubgroupLtMask: {
742 analysis::Integer uint_ty(32, false);
743 analysis::Type* reg_uint_ty = type_mgr->GetRegisteredType(&uint_ty);
744 analysis::Vector v4uint_ty(reg_uint_ty, 4);
745 reg_type = type_mgr->GetRegisteredType(&v4uint_ty);
746 break;
747 }
748 default: {
749 assert(false && "unhandled builtin");
750 return 0;
751 }
752 }
753 uint32_t type_id = type_mgr->GetTypeInstruction(reg_type);
754 uint32_t varTyPtrId =
755 type_mgr->FindPointerToType(type_id, SpvStorageClassInput);
756 // TODO(1841): Handle id overflow.
757 var_id = TakeNextId();
758 std::unique_ptr<Instruction> newVarOp(
759 new Instruction(this, SpvOpVariable, varTyPtrId, var_id,
760 {{spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER,
761 {SpvStorageClassInput}}}));
762 get_def_use_mgr()->AnalyzeInstDefUse(&*newVarOp);
763 module()->AddGlobalValue(std::move(newVarOp));
764 get_decoration_mgr()->AddDecorationVal(var_id, SpvDecorationBuiltIn,
765 builtin);
766 AddVarToEntryPoints(var_id);
767 }
768 builtin_var_id_map_[builtin] = var_id;
769 return var_id;
770 }
771
AddCalls(const Function * func,std::queue<uint32_t> * todo)772 void IRContext::AddCalls(const Function* func, std::queue<uint32_t>* todo) {
773 for (auto bi = func->begin(); bi != func->end(); ++bi)
774 for (auto ii = bi->begin(); ii != bi->end(); ++ii)
775 if (ii->opcode() == SpvOpFunctionCall)
776 todo->push(ii->GetSingleWordInOperand(0));
777 }
778
ProcessEntryPointCallTree(ProcessFunction & pfn)779 bool IRContext::ProcessEntryPointCallTree(ProcessFunction& pfn) {
780 // Collect all of the entry points as the roots.
781 std::queue<uint32_t> roots;
782 for (auto& e : module()->entry_points()) {
783 roots.push(e.GetSingleWordInOperand(kEntryPointFunctionIdInIdx));
784 }
785 return ProcessCallTreeFromRoots(pfn, &roots);
786 }
787
ProcessReachableCallTree(ProcessFunction & pfn)788 bool IRContext::ProcessReachableCallTree(ProcessFunction& pfn) {
789 std::queue<uint32_t> roots;
790
791 // Add all entry points since they can be reached from outside the module.
792 for (auto& e : module()->entry_points())
793 roots.push(e.GetSingleWordInOperand(kEntryPointFunctionIdInIdx));
794
795 // Add all exported functions since they can be reached from outside the
796 // module.
797 for (auto& a : annotations()) {
798 // TODO: Handle group decorations as well. Currently not generate by any
799 // front-end, but could be coming.
800 if (a.opcode() == SpvOp::SpvOpDecorate) {
801 if (a.GetSingleWordOperand(1) ==
802 SpvDecoration::SpvDecorationLinkageAttributes) {
803 uint32_t lastOperand = a.NumOperands() - 1;
804 if (a.GetSingleWordOperand(lastOperand) ==
805 SpvLinkageType::SpvLinkageTypeExport) {
806 uint32_t id = a.GetSingleWordOperand(0);
807 if (GetFunction(id)) {
808 roots.push(id);
809 }
810 }
811 }
812 }
813 }
814
815 return ProcessCallTreeFromRoots(pfn, &roots);
816 }
817
ProcessCallTreeFromRoots(ProcessFunction & pfn,std::queue<uint32_t> * roots)818 bool IRContext::ProcessCallTreeFromRoots(ProcessFunction& pfn,
819 std::queue<uint32_t>* roots) {
820 // Process call tree
821 bool modified = false;
822 std::unordered_set<uint32_t> done;
823
824 while (!roots->empty()) {
825 const uint32_t fi = roots->front();
826 roots->pop();
827 if (done.insert(fi).second) {
828 Function* fn = GetFunction(fi);
829 assert(fn && "Trying to process a function that does not exist.");
830 modified = pfn(fn) || modified;
831 AddCalls(fn, roots);
832 }
833 }
834 return modified;
835 }
836
EmitErrorMessage(std::string message,Instruction * inst)837 void IRContext::EmitErrorMessage(std::string message, Instruction* inst) {
838 if (!consumer()) {
839 return;
840 }
841
842 Instruction* line_inst = inst;
843 while (line_inst != nullptr) { // Stop at the beginning of the basic block.
844 if (!line_inst->dbg_line_insts().empty()) {
845 line_inst = &line_inst->dbg_line_insts().back();
846 if (line_inst->opcode() == SpvOpNoLine) {
847 line_inst = nullptr;
848 }
849 break;
850 }
851 line_inst = line_inst->PreviousNode();
852 }
853
854 uint32_t line_number = 0;
855 uint32_t col_number = 0;
856 char* source = nullptr;
857 if (line_inst != nullptr) {
858 Instruction* file_name =
859 get_def_use_mgr()->GetDef(line_inst->GetSingleWordInOperand(0));
860 source = reinterpret_cast<char*>(&file_name->GetInOperand(0).words[0]);
861
862 // Get the line number and column number.
863 line_number = line_inst->GetSingleWordInOperand(1);
864 col_number = line_inst->GetSingleWordInOperand(2);
865 }
866
867 message +=
868 "\n " + inst->PrettyPrint(SPV_BINARY_TO_TEXT_OPTION_FRIENDLY_NAMES);
869 consumer()(SPV_MSG_ERROR, source, {line_number, col_number, 0},
870 message.c_str());
871 }
872
873 // Gets the dominator analysis for function |f|.
GetDominatorAnalysis(const Function * f)874 DominatorAnalysis* IRContext::GetDominatorAnalysis(const Function* f) {
875 if (!AreAnalysesValid(kAnalysisDominatorAnalysis)) {
876 ResetDominatorAnalysis();
877 }
878
879 if (dominator_trees_.find(f) == dominator_trees_.end()) {
880 dominator_trees_[f].InitializeTree(*cfg(), f);
881 }
882
883 return &dominator_trees_[f];
884 }
885
886 // Gets the postdominator analysis for function |f|.
GetPostDominatorAnalysis(const Function * f)887 PostDominatorAnalysis* IRContext::GetPostDominatorAnalysis(const Function* f) {
888 if (!AreAnalysesValid(kAnalysisDominatorAnalysis)) {
889 ResetDominatorAnalysis();
890 }
891
892 if (post_dominator_trees_.find(f) == post_dominator_trees_.end()) {
893 post_dominator_trees_[f].InitializeTree(*cfg(), f);
894 }
895
896 return &post_dominator_trees_[f];
897 }
898
CheckCFG()899 bool IRContext::CheckCFG() {
900 std::unordered_map<uint32_t, std::vector<uint32_t>> real_preds;
901 if (!AreAnalysesValid(kAnalysisCFG)) {
902 return true;
903 }
904
905 for (Function& function : *module()) {
906 for (const auto& bb : function) {
907 bb.ForEachSuccessorLabel([&bb, &real_preds](const uint32_t lab_id) {
908 real_preds[lab_id].push_back(bb.id());
909 });
910 }
911
912 for (auto& bb : function) {
913 std::vector<uint32_t> preds = cfg()->preds(bb.id());
914 std::vector<uint32_t> real = real_preds[bb.id()];
915 std::sort(preds.begin(), preds.end());
916 std::sort(real.begin(), real.end());
917
918 bool same = true;
919 if (preds.size() != real.size()) {
920 same = false;
921 }
922
923 for (size_t i = 0; i < real.size() && same; i++) {
924 if (preds[i] != real[i]) {
925 same = false;
926 }
927 }
928
929 if (!same) {
930 std::cerr << "Predecessors for " << bb.id() << " are different:\n";
931
932 std::cerr << "Real:";
933 for (uint32_t i : real) {
934 std::cerr << ' ' << i;
935 }
936 std::cerr << std::endl;
937
938 std::cerr << "Recorded:";
939 for (uint32_t i : preds) {
940 std::cerr << ' ' << i;
941 }
942 std::cerr << std::endl;
943 }
944 if (!same) return false;
945 }
946 }
947
948 return true;
949 }
950 } // namespace opt
951 } // namespace spvtools
952