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#ifndef SOURCE_OPT_IR_CONTEXT_H_
16#define SOURCE_OPT_IR_CONTEXT_H_
17
18#include <algorithm>
19#include <iostream>
20#include <limits>
21#include <map>
22#include <memory>
23#include <queue>
24#include <unordered_map>
25#include <unordered_set>
26#include <utility>
27#include <vector>
28
29#include "source/assembly_grammar.h"
30#include "source/opt/cfg.h"
31#include "source/opt/constants.h"
32#include "source/opt/decoration_manager.h"
33#include "source/opt/def_use_manager.h"
34#include "source/opt/dominator_analysis.h"
35#include "source/opt/feature_manager.h"
36#include "source/opt/fold.h"
37#include "source/opt/loop_descriptor.h"
38#include "source/opt/module.h"
39#include "source/opt/register_pressure.h"
40#include "source/opt/scalar_analysis.h"
41#include "source/opt/struct_cfg_analysis.h"
42#include "source/opt/type_manager.h"
43#include "source/opt/value_number_table.h"
44#include "source/util/make_unique.h"
45
46namespace spvtools {
47namespace opt {
48
49class IRContext {
50 public:
51 // Available analyses.
52 //
53 // When adding a new analysis:
54 //
55 // 1. Enum values should be powers of 2. These are cast into uint32_t
56 // bitmasks, so we can have at most 31 analyses represented.
57 //
58 // 2. Make sure it gets invalidated or preserved by IRContext methods that add
59 // or remove IR elements (e.g., KillDef, KillInst, ReplaceAllUsesWith).
60 //
61 // 3. Add handling code in BuildInvalidAnalyses and InvalidateAnalyses
62 enum Analysis {
63 kAnalysisNone = 0 << 0,
64 kAnalysisBegin = 1 << 0,
65 kAnalysisDefUse = kAnalysisBegin,
66 kAnalysisInstrToBlockMapping = 1 << 1,
67 kAnalysisDecorations = 1 << 2,
68 kAnalysisCombinators = 1 << 3,
69 kAnalysisCFG = 1 << 4,
70 kAnalysisDominatorAnalysis = 1 << 5,
71 kAnalysisLoopAnalysis = 1 << 6,
72 kAnalysisNameMap = 1 << 7,
73 kAnalysisScalarEvolution = 1 << 8,
74 kAnalysisRegisterPressure = 1 << 9,
75 kAnalysisValueNumberTable = 1 << 10,
76 kAnalysisStructuredCFG = 1 << 11,
77 kAnalysisBuiltinVarId = 1 << 12,
78 kAnalysisIdToFuncMapping = 1 << 13,
79 kAnalysisConstants = 1 << 14,
80 kAnalysisTypes = 1 << 15,
81 kAnalysisEnd = 1 << 16
82 };
83
84 using ProcessFunction = std::function<bool(Function*)>;
85
86 friend inline Analysis operator|(Analysis lhs, Analysis rhs);
87 friend inline Analysis& operator|=(Analysis& lhs, Analysis rhs);
88 friend inline Analysis operator<<(Analysis a, int shift);
89 friend inline Analysis& operator<<=(Analysis& a, int shift);
90
91 // Creates an |IRContext| that contains an owned |Module|
92 IRContext(spv_target_env env, MessageConsumer c)
93 : syntax_context_(spvContextCreate(env)),
94 grammar_(syntax_context_),
95 unique_id_(0),
96 module_(new Module()),
97 consumer_(std::move(c)),
98 def_use_mgr_(nullptr),
99 valid_analyses_(kAnalysisNone),
100 constant_mgr_(nullptr),
101 type_mgr_(nullptr),
102 id_to_name_(nullptr),
103 max_id_bound_(kDefaultMaxIdBound),
104 preserve_bindings_(false),
105 preserve_spec_constants_(false) {
106 SetContextMessageConsumer(syntax_context_, consumer_);
107 module_->SetContext(this);
108 }
109
110 IRContext(spv_target_env env, std::unique_ptr<Module>&& m, MessageConsumer c)
111 : syntax_context_(spvContextCreate(env)),
112 grammar_(syntax_context_),
113 unique_id_(0),
114 module_(std::move(m)),
115 consumer_(std::move(c)),
116 def_use_mgr_(nullptr),
117 valid_analyses_(kAnalysisNone),
118 type_mgr_(nullptr),
119 id_to_name_(nullptr),
120 max_id_bound_(kDefaultMaxIdBound),
121 preserve_bindings_(false),
122 preserve_spec_constants_(false) {
123 SetContextMessageConsumer(syntax_context_, consumer_);
124 module_->SetContext(this);
125 InitializeCombinators();
126 }
127
128 ~IRContext() { spvContextDestroy(syntax_context_); }
129
130 Module* module() const { return module_.get(); }
131
132 // Returns a vector of pointers to constant-creation instructions in this
133 // context.
134 inline std::vector<Instruction*> GetConstants();
135 inline std::vector<const Instruction*> GetConstants() const;
136
137 // Iterators for annotation instructions contained in this context.
138 inline Module::inst_iterator annotation_begin();
139 inline Module::inst_iterator annotation_end();
140 inline IteratorRange<Module::inst_iterator> annotations();
141 inline IteratorRange<Module::const_inst_iterator> annotations() const;
142
143 // Iterators for capabilities instructions contained in this module.
144 inline Module::inst_iterator capability_begin();
145 inline Module::inst_iterator capability_end();
146 inline IteratorRange<Module::inst_iterator> capabilities();
147 inline IteratorRange<Module::const_inst_iterator> capabilities() const;
148
149 // Iterators for types, constants and global variables instructions.
150 inline Module::inst_iterator types_values_begin();
151 inline Module::inst_iterator types_values_end();
152 inline IteratorRange<Module::inst_iterator> types_values();
153 inline IteratorRange<Module::const_inst_iterator> types_values() const;
154
155 // Iterators for extension instructions contained in this module.
156 inline Module::inst_iterator ext_inst_import_begin();
157 inline Module::inst_iterator ext_inst_import_end();
158 inline IteratorRange<Module::inst_iterator> ext_inst_imports();
159 inline IteratorRange<Module::const_inst_iterator> ext_inst_imports() const;
160
161 // There are several kinds of debug instructions, according to where they can
162 // appear in the logical layout of a module:
163 // - Section 7a: OpString, OpSourceExtension, OpSource, OpSourceContinued
164 // - Section 7b: OpName, OpMemberName
165 // - Section 7c: OpModuleProcessed
166 // - Mostly anywhere: OpLine and OpNoLine
167 //
168
169 // Iterators for debug 1 instructions (excluding OpLine & OpNoLine) contained
170 // in this module. These are for layout section 7a.
171 inline Module::inst_iterator debug1_begin();
172 inline Module::inst_iterator debug1_end();
173 inline IteratorRange<Module::inst_iterator> debugs1();
174 inline IteratorRange<Module::const_inst_iterator> debugs1() const;
175
176 // Iterators for debug 2 instructions (excluding OpLine & OpNoLine) contained
177 // in this module. These are for layout section 7b.
178 inline Module::inst_iterator debug2_begin();
179 inline Module::inst_iterator debug2_end();
180 inline IteratorRange<Module::inst_iterator> debugs2();
181 inline IteratorRange<Module::const_inst_iterator> debugs2() const;
182
183 // Iterators for debug 3 instructions (excluding OpLine & OpNoLine) contained
184 // in this module. These are for layout section 7c.
185 inline Module::inst_iterator debug3_begin();
186 inline Module::inst_iterator debug3_end();
187 inline IteratorRange<Module::inst_iterator> debugs3();
188 inline IteratorRange<Module::const_inst_iterator> debugs3() const;
189
190 // Iterators for debug info instructions (excluding OpLine & OpNoLine)
191 // contained in this module. These are OpExtInst for OpenCL.DebugInfo.100
192 // or DebugInfo extension placed between section 9 and 10.
193 inline Module::inst_iterator ext_inst_debuginfo_begin();
194 inline Module::inst_iterator ext_inst_debuginfo_end();
195 inline IteratorRange<Module::inst_iterator> ext_inst_debuginfo();
196 inline IteratorRange<Module::const_inst_iterator> ext_inst_debuginfo() const;
197
198 // Add |capability| to the module, if it is not already enabled.
199 inline void AddCapability(SpvCapability capability);
200
201 // Appends a capability instruction to this module.
202 inline void AddCapability(std::unique_ptr<Instruction>&& c);
203 // Appends an extension instruction to this module.
204 inline void AddExtension(const std::string& ext_name);
205 inline void AddExtension(std::unique_ptr<Instruction>&& e);
206 // Appends an extended instruction set instruction to this module.
207 inline void AddExtInstImport(const std::string& name);
208 inline void AddExtInstImport(std::unique_ptr<Instruction>&& e);
209 // Set the memory model for this module.
210 inline void SetMemoryModel(std::unique_ptr<Instruction>&& m);
211 // Appends an entry point instruction to this module.
212 inline void AddEntryPoint(std::unique_ptr<Instruction>&& e);
213 // Appends an execution mode instruction to this module.
214 inline void AddExecutionMode(std::unique_ptr<Instruction>&& e);
215 // Appends a debug 1 instruction (excluding OpLine & OpNoLine) to this module.
216 // "debug 1" instructions are the ones in layout section 7.a), see section
217 // 2.4 Logical Layout of a Module from the SPIR-V specification.
218 inline void AddDebug1Inst(std::unique_ptr<Instruction>&& d);
219 // Appends a debug 2 instruction (excluding OpLine & OpNoLine) to this module.
220 // "debug 2" instructions are the ones in layout section 7.b), see section
221 // 2.4 Logical Layout of a Module from the SPIR-V specification.
222 inline void AddDebug2Inst(std::unique_ptr<Instruction>&& d);
223 // Appends a debug 3 instruction (OpModuleProcessed) to this module.
224 // This is due to decision by the SPIR Working Group, pending publication.
225 inline void AddDebug3Inst(std::unique_ptr<Instruction>&& d);
226 // Appends a OpExtInst for DebugInfo to this module.
227 inline void AddExtInstDebugInfo(std::unique_ptr<Instruction>&& d);
228 // Appends an annotation instruction to this module.
229 inline void AddAnnotationInst(std::unique_ptr<Instruction>&& a);
230 // Appends a type-declaration instruction to this module.
231 inline void AddType(std::unique_ptr<Instruction>&& t);
232 // Appends a constant, global variable, or OpUndef instruction to this module.
233 inline void AddGlobalValue(std::unique_ptr<Instruction>&& v);
234 // Appends a function to this module.
235 inline void AddFunction(std::unique_ptr<Function>&& f);
236
237 // Returns a pointer to a def-use manager. If the def-use manager is
238 // invalid, it is rebuilt first.
239 analysis::DefUseManager* get_def_use_mgr() {
240 if (!AreAnalysesValid(kAnalysisDefUse)) {
241 BuildDefUseManager();
242 }
243 return def_use_mgr_.get();
244 }
245
246 // Returns a pointer to a value number table. If the liveness analysis is
247 // invalid, it is rebuilt first.
248 ValueNumberTable* GetValueNumberTable() {
249 if (!AreAnalysesValid(kAnalysisValueNumberTable)) {
250 BuildValueNumberTable();
251 }
252 return vn_table_.get();
253 }
254
255 // Returns a pointer to a StructuredCFGAnalysis. If the analysis is invalid,
256 // it is rebuilt first.
257 StructuredCFGAnalysis* GetStructuredCFGAnalysis() {
258 if (!AreAnalysesValid(kAnalysisStructuredCFG)) {
259 BuildStructuredCFGAnalysis();
260 }
261 return struct_cfg_analysis_.get();
262 }
263
264 // Returns a pointer to a liveness analysis. If the liveness analysis is
265 // invalid, it is rebuilt first.
266 LivenessAnalysis* GetLivenessAnalysis() {
267 if (!AreAnalysesValid(kAnalysisRegisterPressure)) {
268 BuildRegPressureAnalysis();
269 }
270 return reg_pressure_.get();
271 }
272
273 // Returns the basic block for instruction |instr|. Re-builds the instruction
274 // block map, if needed.
275 BasicBlock* get_instr_block(Instruction* instr) {
276 if (!AreAnalysesValid(kAnalysisInstrToBlockMapping)) {
277 BuildInstrToBlockMapping();
278 }
279 auto entry = instr_to_block_.find(instr);
280 return (entry != instr_to_block_.end()) ? entry->second : nullptr;
281 }
282
283 // Returns the basic block for |id|. Re-builds the instruction block map, if
284 // needed.
285 //
286 // |id| must be a registered definition.
287 BasicBlock* get_instr_block(uint32_t id) {
288 Instruction* def = get_def_use_mgr()->GetDef(id);
289 return get_instr_block(def);
290 }
291
292 // Sets the basic block for |inst|. Re-builds the mapping if it has become
293 // invalid.
294 void set_instr_block(Instruction* inst, BasicBlock* block) {
295 if (AreAnalysesValid(kAnalysisInstrToBlockMapping)) {
296 instr_to_block_[inst] = block;
297 }
298 }
299
300 // Returns a pointer the decoration manager. If the decoration manger is
301 // invalid, it is rebuilt first.
302 analysis::DecorationManager* get_decoration_mgr() {
303 if (!AreAnalysesValid(kAnalysisDecorations)) {
304 BuildDecorationManager();
305 }
306 return decoration_mgr_.get();
307 }
308
309 // Returns a pointer to the constant manager. If no constant manager has been
310 // created yet, it creates one. NOTE: Once created, the constant manager
311 // remains active and it is never re-built.
312 analysis::ConstantManager* get_constant_mgr() {
313 if (!AreAnalysesValid(kAnalysisConstants)) {
314 BuildConstantManager();
315 }
316 return constant_mgr_.get();
317 }
318
319 // Returns a pointer to the type manager. If no type manager has been created
320 // yet, it creates one. NOTE: Once created, the type manager remains active it
321 // is never re-built.
322 analysis::TypeManager* get_type_mgr() {
323 if (!AreAnalysesValid(kAnalysisTypes)) {
324 BuildTypeManager();
325 }
326 return type_mgr_.get();
327 }
328
329 // Returns a pointer to the scalar evolution analysis. If it is invalid it
330 // will be rebuilt first.
331 ScalarEvolutionAnalysis* GetScalarEvolutionAnalysis() {
332 if (!AreAnalysesValid(kAnalysisScalarEvolution)) {
333 BuildScalarEvolutionAnalysis();
334 }
335 return scalar_evolution_analysis_.get();
336 }
337
338 // Build the map from the ids to the OpName and OpMemberName instruction
339 // associated with it.
340 inline void BuildIdToNameMap();
341
342 // Returns a range of instrucions that contain all of the OpName and
343 // OpMemberNames associated with the given id.
344 inline IteratorRange<std::multimap<uint32_t, Instruction*>::iterator>
345 GetNames(uint32_t id);
346
347 // Sets the message consumer to the given |consumer|. |consumer| which will be
348 // invoked every time there is a message to be communicated to the outside.
349 void SetMessageConsumer(MessageConsumer c) { consumer_ = std::move(c); }
350
351 // Returns the reference to the message consumer for this pass.
352 const MessageConsumer& consumer() const { return consumer_; }
353
354 // Rebuilds the analyses in |set| that are invalid.
355 void BuildInvalidAnalyses(Analysis set);
356
357 // Invalidates all of the analyses except for those in |preserved_analyses|.
358 void InvalidateAnalysesExceptFor(Analysis preserved_analyses);
359
360 // Invalidates the analyses marked in |analyses_to_invalidate|.
361 void InvalidateAnalyses(Analysis analyses_to_invalidate);
362
363 // Deletes the instruction defining the given |id|. Returns true on
364 // success, false if the given |id| is not defined at all. This method also
365 // erases the name, decorations, and defintion of |id|.
366 //
367 // Pointers and iterators pointing to the deleted instructions become invalid.
368 // However other pointers and iterators are still valid.
369 bool KillDef(uint32_t id);
370
371 // Deletes the given instruction |inst|. This method erases the
372 // information of the given instruction's uses of its operands. If |inst|
373 // defines a result id, its name and decorations will also be deleted.
374 //
375 // Pointer and iterator pointing to the deleted instructions become invalid.
376 // However other pointers and iterators are still valid.
377 //
378 // Note that if an instruction is not in an instruction list, the memory may
379 // not be safe to delete, so the instruction is turned into a OpNop instead.
380 // This can happen with OpLabel.
381 //
382 // Returns a pointer to the instruction after |inst| or |nullptr| if no such
383 // instruction exists.
384 Instruction* KillInst(Instruction* inst);
385
386 // Returns true if all of the given analyses are valid.
387 bool AreAnalysesValid(Analysis set) { return (set & valid_analyses_) == set; }
388
389 // Replaces all uses of |before| id with |after| id. Returns true if any
390 // replacement happens. This method does not kill the definition of the
391 // |before| id. If |after| is the same as |before|, does nothing and returns
392 // false.
393 //
394 // |before| and |after| must be registered definitions in the DefUseManager.
395 bool ReplaceAllUsesWith(uint32_t before, uint32_t after);
396
397 // Replace all uses of |before| id with |after| id if those uses
398 // (instruction, operand pair) return true for |predicate|. Returns true if
399 // any replacement happens. This method does not kill the definition of the
400 // |before| id. If |after| is the same as |before|, does nothing and return
401 // false.
402 bool ReplaceAllUsesWithPredicate(
403 uint32_t before, uint32_t after,
404 const std::function<bool(Instruction*, uint32_t)>& predicate);
405
406 // Returns true if all of the analyses that are suppose to be valid are
407 // actually valid.
408 bool IsConsistent();
409
410 // The IRContext will look at the def and uses of |inst| and update any valid
411 // analyses will be updated accordingly.
412 inline void AnalyzeDefUse(Instruction* inst);
413
414 // Informs the IRContext that the uses of |inst| are going to change, and that
415 // is should forget everything it know about the current uses. Any valid
416 // analyses will be updated accordingly.
417 void ForgetUses(Instruction* inst);
418
419 // The IRContext will look at the uses of |inst| and update any valid analyses
420 // will be updated accordingly.
421 void AnalyzeUses(Instruction* inst);
422
423 // Kill all name and decorate ops targeting |id|.
424 void KillNamesAndDecorates(uint32_t id);
425
426 // Kill all name and decorate ops targeting the result id of |inst|.
427 void KillNamesAndDecorates(Instruction* inst);
428
429 // Returns the next unique id for use by an instruction.
430 inline uint32_t TakeNextUniqueId() {
431 assert(unique_id_ != std::numeric_limits<uint32_t>::max());
432
433 // Skip zero.
434 return ++unique_id_;
435 }
436
437 // Returns true if |inst| is a combinator in the current context.
438 // |combinator_ops_| is built if it has not been already.
439 inline bool IsCombinatorInstruction(const Instruction* inst) {
440 if (!AreAnalysesValid(kAnalysisCombinators)) {
441 InitializeCombinators();
442 }
443 const uint32_t kExtInstSetIdInIndx = 0;
444 const uint32_t kExtInstInstructionInIndx = 1;
445
446 if (inst->opcode() != SpvOpExtInst) {
447 return combinator_ops_[0].count(inst->opcode()) != 0;
448 } else {
449 uint32_t set = inst->GetSingleWordInOperand(kExtInstSetIdInIndx);
450 uint32_t op = inst->GetSingleWordInOperand(kExtInstInstructionInIndx);
451 return combinator_ops_[set].count(op) != 0;
452 }
453 }
454
455 // Returns a pointer to the CFG for all the functions in |module_|.
456 CFG* cfg() {
457 if (!AreAnalysesValid(kAnalysisCFG)) {
458 BuildCFG();
459 }
460 return cfg_.get();
461 }
462
463 // Gets the loop descriptor for function |f|.
464 LoopDescriptor* GetLoopDescriptor(const Function* f);
465
466 // Gets the dominator analysis for function |f|.
467 DominatorAnalysis* GetDominatorAnalysis(const Function* f);
468
469 // Gets the postdominator analysis for function |f|.
470 PostDominatorAnalysis* GetPostDominatorAnalysis(const Function* f);
471
472 // Remove the dominator tree of |f| from the cache.
473 inline void RemoveDominatorAnalysis(const Function* f) {
474 dominator_trees_.erase(f);
475 }
476
477 // Remove the postdominator tree of |f| from the cache.
478 inline void RemovePostDominatorAnalysis(const Function* f) {
479 post_dominator_trees_.erase(f);
480 }
481
482 // Return the next available SSA id and increment it. Returns 0 if the
483 // maximum SSA id has been reached.
484 inline uint32_t TakeNextId() {
485 uint32_t next_id = module()->TakeNextIdBound();
486 if (next_id == 0) {
487 if (consumer()) {
488 std::string message = "ID overflow. Try running compact-ids.";
489 consumer()(SPV_MSG_ERROR, "", {0, 0, 0}, message.c_str());
490 }
491 }
492 return next_id;
493 }
494
495 FeatureManager* get_feature_mgr() {
496 if (!feature_mgr_.get()) {
497 AnalyzeFeatures();
498 }
499 return feature_mgr_.get();
500 }
501
502 void ResetFeatureManager() { feature_mgr_.reset(nullptr); }
503
504 // Returns the grammar for this context.
505 const AssemblyGrammar& grammar() const { return grammar_; }
506
507 // If |inst| has not yet been analysed by the def-use manager, then analyse
508 // its definitions and uses.
509 inline void UpdateDefUse(Instruction* inst);
510
511 const InstructionFolder& get_instruction_folder() {
512 if (!inst_folder_) {
513 inst_folder_ = MakeUnique<InstructionFolder>(this);
514 }
515 return *inst_folder_;
516 }
517
518 uint32_t max_id_bound() const { return max_id_bound_; }
519 void set_max_id_bound(uint32_t new_bound) { max_id_bound_ = new_bound; }
520
521 bool preserve_bindings() const { return preserve_bindings_; }
522 void set_preserve_bindings(bool should_preserve_bindings) {
523 preserve_bindings_ = should_preserve_bindings;
524 }
525
526 bool preserve_spec_constants() const { return preserve_spec_constants_; }
527 void set_preserve_spec_constants(bool should_preserve_spec_constants) {
528 preserve_spec_constants_ = should_preserve_spec_constants;
529 }
530
531 // Return id of input variable only decorated with |builtin|, if in module.
532 // Create variable and return its id otherwise. If builtin not currently
533 // supported, return 0.
534 uint32_t GetBuiltinInputVarId(uint32_t builtin);
535
536 // Returns the function whose id is |id|, if one exists. Returns |nullptr|
537 // otherwise.
538 Function* GetFunction(uint32_t id) {
539 if (!AreAnalysesValid(kAnalysisIdToFuncMapping)) {
540 BuildIdToFuncMapping();
541 }
542 auto entry = id_to_func_.find(id);
543 return (entry != id_to_func_.end()) ? entry->second : nullptr;
544 }
545
546 Function* GetFunction(Instruction* inst) {
547 if (inst->opcode() != SpvOpFunction) {
548 return nullptr;
549 }
550 return GetFunction(inst->result_id());
551 }
552
553 // Add to |todo| all ids of functions called directly from |func|.
554 void AddCalls(const Function* func, std::queue<uint32_t>* todo);
555
556 // Applies |pfn| to every function in the call trees that are rooted at the
557 // entry points. Returns true if any call |pfn| returns true. By convention
558 // |pfn| should return true if it modified the module.
559 bool ProcessEntryPointCallTree(ProcessFunction& pfn);
560
561 // Applies |pfn| to every function in the call trees rooted at the entry
562 // points and exported functions. Returns true if any call |pfn| returns
563 // true. By convention |pfn| should return true if it modified the module.
564 bool ProcessReachableCallTree(ProcessFunction& pfn);
565
566 // Applies |pfn| to every function in the call trees rooted at the elements of
567 // |roots|. Returns true if any call to |pfn| returns true. By convention
568 // |pfn| should return true if it modified the module. After returning
569 // |roots| will be empty.
570 bool ProcessCallTreeFromRoots(ProcessFunction& pfn,
571 std::queue<uint32_t>* roots);
572
573 // Emmits a error message to the message consumer indicating the error
574 // described by |message| occurred in |inst|.
575 void EmitErrorMessage(std::string message, Instruction* inst);
576
577 private:
578 // Builds the def-use manager from scratch, even if it was already valid.
579 void BuildDefUseManager() {
580 def_use_mgr_ = MakeUnique<analysis::DefUseManager>(module());
581 valid_analyses_ = valid_analyses_ | kAnalysisDefUse;
582 }
583
584 // Builds the instruction-block map for the whole module.
585 void BuildInstrToBlockMapping() {
586 instr_to_block_.clear();
587 for (auto& fn : *module_) {
588 for (auto& block : fn) {
589 block.ForEachInst([this, &block](Instruction* inst) {
590 instr_to_block_[inst] = &block;
591 });
592 }
593 }
594 valid_analyses_ = valid_analyses_ | kAnalysisInstrToBlockMapping;
595 }
596
597 // Builds the instruction-function map for the whole module.
598 void BuildIdToFuncMapping() {
599 id_to_func_.clear();
600 for (auto& fn : *module_) {
601 id_to_func_[fn.result_id()] = &fn;
602 }
603 valid_analyses_ = valid_analyses_ | kAnalysisIdToFuncMapping;
604 }
605
606 void BuildDecorationManager() {
607 decoration_mgr_ = MakeUnique<analysis::DecorationManager>(module());
608 valid_analyses_ = valid_analyses_ | kAnalysisDecorations;
609 }
610
611 void BuildCFG() {
612 cfg_ = MakeUnique<CFG>(module());
613 valid_analyses_ = valid_analyses_ | kAnalysisCFG;
614 }
615
616 void BuildScalarEvolutionAnalysis() {
617 scalar_evolution_analysis_ = MakeUnique<ScalarEvolutionAnalysis>(this);
618 valid_analyses_ = valid_analyses_ | kAnalysisScalarEvolution;
619 }
620
621 // Builds the liveness analysis from scratch, even if it was already valid.
622 void BuildRegPressureAnalysis() {
623 reg_pressure_ = MakeUnique<LivenessAnalysis>(this);
624 valid_analyses_ = valid_analyses_ | kAnalysisRegisterPressure;
625 }
626
627 // Builds the value number table analysis from scratch, even if it was already
628 // valid.
629 void BuildValueNumberTable() {
630 vn_table_ = MakeUnique<ValueNumberTable>(this);
631 valid_analyses_ = valid_analyses_ | kAnalysisValueNumberTable;
632 }
633
634 // Builds the structured CFG analysis from scratch, even if it was already
635 // valid.
636 void BuildStructuredCFGAnalysis() {
637 struct_cfg_analysis_ = MakeUnique<StructuredCFGAnalysis>(this);
638 valid_analyses_ = valid_analyses_ | kAnalysisStructuredCFG;
639 }
640
641 // Builds the constant manager from scratch, even if it was already
642 // valid.
643 void BuildConstantManager() {
644 constant_mgr_ = MakeUnique<analysis::ConstantManager>(this);
645 valid_analyses_ = valid_analyses_ | kAnalysisConstants;
646 }
647
648 // Builds the type manager from scratch, even if it was already
649 // valid.
650 void BuildTypeManager() {
651 type_mgr_ = MakeUnique<analysis::TypeManager>(consumer(), this);
652 valid_analyses_ = valid_analyses_ | kAnalysisTypes;
653 }
654
655 // Removes all computed dominator and post-dominator trees. This will force
656 // the context to rebuild the trees on demand.
657 void ResetDominatorAnalysis() {
658 // Clear the cache.
659 dominator_trees_.clear();
660 post_dominator_trees_.clear();
661 valid_analyses_ = valid_analyses_ | kAnalysisDominatorAnalysis;
662 }
663
664 // Removes all computed loop descriptors.
665 void ResetLoopAnalysis() {
666 // Clear the cache.
667 loop_descriptors_.clear();
668 valid_analyses_ = valid_analyses_ | kAnalysisLoopAnalysis;
669 }
670
671 // Removes all computed loop descriptors.
672 void ResetBuiltinAnalysis() {
673 // Clear the cache.
674 builtin_var_id_map_.clear();
675 valid_analyses_ = valid_analyses_ | kAnalysisBuiltinVarId;
676 }
677
678 // Analyzes the features in the owned module. Builds the manager if required.
679 void AnalyzeFeatures() {
680 feature_mgr_ = MakeUnique<FeatureManager>(grammar_);
681 feature_mgr_->Analyze(module());
682 }
683
684 // Scans a module looking for it capabilities, and initializes combinator_ops_
685 // accordingly.
686 void InitializeCombinators();
687
688 // Add the combinator opcode for the given capability to combinator_ops_.
689 void AddCombinatorsForCapability(uint32_t capability);
690
691 // Add the combinator opcode for the given extension to combinator_ops_.
692 void AddCombinatorsForExtension(Instruction* extension);
693
694 // Remove |inst| from |id_to_name_| if it is in map.
695 void RemoveFromIdToName(const Instruction* inst);
696
697 // Returns true if it is suppose to be valid but it is incorrect. Returns
698 // true if the cfg is invalidated.
699 bool CheckCFG();
700
701 // Return id of input variable only decorated with |builtin|, if in module.
702 // Return 0 otherwise.
703 uint32_t FindBuiltinInputVar(uint32_t builtin);
704
705 // Add |var_id| to all entry points in module.
706 void AddVarToEntryPoints(uint32_t var_id);
707
708 // The SPIR-V syntax context containing grammar tables for opcodes and
709 // operands.
710 spv_context syntax_context_;
711
712 // Auxiliary object for querying SPIR-V grammar facts.
713 AssemblyGrammar grammar_;
714
715 // An unique identifier for instructions in |module_|. Can be used to order
716 // instructions in a container.
717 //
718 // This member is initialized to 0, but always issues this value plus one.
719 // Therefore, 0 is not a valid unique id for an instruction.
720 uint32_t unique_id_;
721
722 // The module being processed within this IR context.
723 std::unique_ptr<Module> module_;
724
725 // A message consumer for diagnostics.
726 MessageConsumer consumer_;
727
728 // The def-use manager for |module_|.
729 std::unique_ptr<analysis::DefUseManager> def_use_mgr_;
730
731 // The instruction decoration manager for |module_|.
732 std::unique_ptr<analysis::DecorationManager> decoration_mgr_;
733 std::unique_ptr<FeatureManager> feature_mgr_;
734
735 // A map from instructions to the basic block they belong to. This mapping is
736 // built on-demand when get_instr_block() is called.
737 //
738 // NOTE: Do not traverse this map. Ever. Use the function and basic block
739 // iterators to traverse instructions.
740 std::unordered_map<Instruction*, BasicBlock*> instr_to_block_;
741
742 // A map from ids to the function they define. This mapping is
743 // built on-demand when GetFunction() is called.
744 //
745 // NOTE: Do not traverse this map. Ever. Use the function and basic block
746 // iterators to traverse instructions.
747 std::unordered_map<uint32_t, Function*> id_to_func_;
748
749 // A bitset indicating which analyes are currently valid.
750 Analysis valid_analyses_;
751
752 // Opcodes of shader capability core executable instructions
753 // without side-effect.
754 std::unordered_map<uint32_t, std::unordered_set<uint32_t>> combinator_ops_;
755
756 // Opcodes of shader capability core executable instructions
757 // without side-effect.
758 std::unordered_map<uint32_t, uint32_t> builtin_var_id_map_;
759
760 // The CFG for all the functions in |module_|.
761 std::unique_ptr<CFG> cfg_;
762
763 // Each function in the module will create its own dominator tree. We cache
764 // the result so it doesn't need to be rebuilt each time.
765 std::map<const Function*, DominatorAnalysis> dominator_trees_;
766 std::map<const Function*, PostDominatorAnalysis> post_dominator_trees_;
767
768 // Cache of loop descriptors for each function.
769 std::unordered_map<const Function*, LoopDescriptor> loop_descriptors_;
770
771 // Constant manager for |module_|.
772 std::unique_ptr<analysis::ConstantManager> constant_mgr_;
773
774 // Type manager for |module_|.
775 std::unique_ptr<analysis::TypeManager> type_mgr_;
776
777 // A map from an id to its corresponding OpName and OpMemberName instructions.
778 std::unique_ptr<std::multimap<uint32_t, Instruction*>> id_to_name_;
779
780 // The cache scalar evolution analysis node.
781 std::unique_ptr<ScalarEvolutionAnalysis> scalar_evolution_analysis_;
782
783 // The liveness analysis |module_|.
784 std::unique_ptr<LivenessAnalysis> reg_pressure_;
785
786 std::unique_ptr<ValueNumberTable> vn_table_;
787
788 std::unique_ptr<InstructionFolder> inst_folder_;
789
790 std::unique_ptr<StructuredCFGAnalysis> struct_cfg_analysis_;
791
792 // The maximum legal value for the id bound.
793 uint32_t max_id_bound_;
794
795 // Whether all bindings within |module_| should be preserved.
796 bool preserve_bindings_;
797
798 // Whether all specialization constants within |module_|
799 // should be preserved.
800 bool preserve_spec_constants_;
801};
802
803inline IRContext::Analysis operator|(IRContext::Analysis lhs,
804 IRContext::Analysis rhs) {
805 return static_cast<IRContext::Analysis>(static_cast<int>(lhs) |
806 static_cast<int>(rhs));
807}
808
809inline IRContext::Analysis& operator|=(IRContext::Analysis& lhs,
810 IRContext::Analysis rhs) {
811 lhs = static_cast<IRContext::Analysis>(static_cast<int>(lhs) |
812 static_cast<int>(rhs));
813 return lhs;
814}
815
816inline IRContext::Analysis operator<<(IRContext::Analysis a, int shift) {
817 return static_cast<IRContext::Analysis>(static_cast<int>(a) << shift);
818}
819
820inline IRContext::Analysis& operator<<=(IRContext::Analysis& a, int shift) {
821 a = static_cast<IRContext::Analysis>(static_cast<int>(a) << shift);
822 return a;
823}
824
825std::vector<Instruction*> IRContext::GetConstants() {
826 return module()->GetConstants();
827}
828
829std::vector<const Instruction*> IRContext::GetConstants() const {
830 return ((const Module*)module())->GetConstants();
831}
832
833Module::inst_iterator IRContext::annotation_begin() {
834 return module()->annotation_begin();
835}
836
837Module::inst_iterator IRContext::annotation_end() {
838 return module()->annotation_end();
839}
840
841IteratorRange<Module::inst_iterator> IRContext::annotations() {
842 return module_->annotations();
843}
844
845IteratorRange<Module::const_inst_iterator> IRContext::annotations() const {
846 return ((const Module*)module_.get())->annotations();
847}
848
849Module::inst_iterator IRContext::capability_begin() {
850 return module()->capability_begin();
851}
852
853Module::inst_iterator IRContext::capability_end() {
854 return module()->capability_end();
855}
856
857IteratorRange<Module::inst_iterator> IRContext::capabilities() {
858 return module()->capabilities();
859}
860
861IteratorRange<Module::const_inst_iterator> IRContext::capabilities() const {
862 return ((const Module*)module())->capabilities();
863}
864
865Module::inst_iterator IRContext::types_values_begin() {
866 return module()->types_values_begin();
867}
868
869Module::inst_iterator IRContext::types_values_end() {
870 return module()->types_values_end();
871}
872
873IteratorRange<Module::inst_iterator> IRContext::types_values() {
874 return module()->types_values();
875}
876
877IteratorRange<Module::const_inst_iterator> IRContext::types_values() const {
878 return ((const Module*)module_.get())->types_values();
879}
880
881Module::inst_iterator IRContext::ext_inst_import_begin() {
882 return module()->ext_inst_import_begin();
883}
884
885Module::inst_iterator IRContext::ext_inst_import_end() {
886 return module()->ext_inst_import_end();
887}
888
889IteratorRange<Module::inst_iterator> IRContext::ext_inst_imports() {
890 return module()->ext_inst_imports();
891}
892
893IteratorRange<Module::const_inst_iterator> IRContext::ext_inst_imports() const {
894 return ((const Module*)module_.get())->ext_inst_imports();
895}
896
897Module::inst_iterator IRContext::debug1_begin() {
898 return module()->debug1_begin();
899}
900
901Module::inst_iterator IRContext::debug1_end() { return module()->debug1_end(); }
902
903IteratorRange<Module::inst_iterator> IRContext::debugs1() {
904 return module()->debugs1();
905}
906
907IteratorRange<Module::const_inst_iterator> IRContext::debugs1() const {
908 return ((const Module*)module_.get())->debugs1();
909}
910
911Module::inst_iterator IRContext::debug2_begin() {
912 return module()->debug2_begin();
913}
914Module::inst_iterator IRContext::debug2_end() { return module()->debug2_end(); }
915
916IteratorRange<Module::inst_iterator> IRContext::debugs2() {
917 return module()->debugs2();
918}
919
920IteratorRange<Module::const_inst_iterator> IRContext::debugs2() const {
921 return ((const Module*)module_.get())->debugs2();
922}
923
924Module::inst_iterator IRContext::debug3_begin() {
925 return module()->debug3_begin();
926}
927
928Module::inst_iterator IRContext::debug3_end() { return module()->debug3_end(); }
929
930IteratorRange<Module::inst_iterator> IRContext::debugs3() {
931 return module()->debugs3();
932}
933
934IteratorRange<Module::const_inst_iterator> IRContext::debugs3() const {
935 return ((const Module*)module_.get())->debugs3();
936}
937
938Module::inst_iterator IRContext::ext_inst_debuginfo_begin() {
939 return module()->ext_inst_debuginfo_begin();
940}
941
942Module::inst_iterator IRContext::ext_inst_debuginfo_end() {
943 return module()->ext_inst_debuginfo_end();
944}
945
946IteratorRange<Module::inst_iterator> IRContext::ext_inst_debuginfo() {
947 return module()->ext_inst_debuginfo();
948}
949
950IteratorRange<Module::const_inst_iterator> IRContext::ext_inst_debuginfo()
951 const {
952 return ((const Module*)module_.get())->ext_inst_debuginfo();
953}
954
955void IRContext::AddCapability(SpvCapability capability) {
956 if (!get_feature_mgr()->HasCapability(capability)) {
957 std::unique_ptr<Instruction> capability_inst(new Instruction(
958 this, SpvOpCapability, 0, 0,
959 {{SPV_OPERAND_TYPE_CAPABILITY, {static_cast<uint32_t>(capability)}}}));
960 AddCapability(std::move(capability_inst));
961 }
962}
963
964void IRContext::AddCapability(std::unique_ptr<Instruction>&& c) {
965 AddCombinatorsForCapability(c->GetSingleWordInOperand(0));
966 if (feature_mgr_ != nullptr) {
967 feature_mgr_->AddCapability(
968 static_cast<SpvCapability>(c->GetSingleWordInOperand(0)));
969 }
970 if (AreAnalysesValid(kAnalysisDefUse)) {
971 get_def_use_mgr()->AnalyzeInstDefUse(c.get());
972 }
973 module()->AddCapability(std::move(c));
974}
975
976void IRContext::AddExtension(const std::string& ext_name) {
977 const auto num_chars = ext_name.size();
978 // Compute num words, accommodate the terminating null character.
979 const auto num_words = (num_chars + 1 + 3) / 4;
980 std::vector<uint32_t> ext_words(num_words, 0u);
981 std::memcpy(ext_words.data(), ext_name.data(), num_chars);
982 AddExtension(std::unique_ptr<Instruction>(
983 new Instruction(this, SpvOpExtension, 0u, 0u,
984 {{SPV_OPERAND_TYPE_LITERAL_STRING, ext_words}})));
985}
986
987void IRContext::AddExtension(std::unique_ptr<Instruction>&& e) {
988 if (AreAnalysesValid(kAnalysisDefUse)) {
989 get_def_use_mgr()->AnalyzeInstDefUse(e.get());
990 }
991 if (feature_mgr_ != nullptr) {
992 feature_mgr_->AddExtension(&*e);
993 }
994 module()->AddExtension(std::move(e));
995}
996
997void IRContext::AddExtInstImport(const std::string& name) {
998 const auto num_chars = name.size();
999 // Compute num words, accommodate the terminating null character.
1000 const auto num_words = (num_chars + 1 + 3) / 4;
1001 std::vector<uint32_t> ext_words(num_words, 0u);
1002 std::memcpy(ext_words.data(), name.data(), num_chars);
1003 AddExtInstImport(std::unique_ptr<Instruction>(
1004 new Instruction(this, SpvOpExtInstImport, 0u, TakeNextId(),
1005 {{SPV_OPERAND_TYPE_LITERAL_STRING, ext_words}})));
1006}
1007
1008void IRContext::AddExtInstImport(std::unique_ptr<Instruction>&& e) {
1009 AddCombinatorsForExtension(e.get());
1010 if (AreAnalysesValid(kAnalysisDefUse)) {
1011 get_def_use_mgr()->AnalyzeInstDefUse(e.get());
1012 }
1013 module()->AddExtInstImport(std::move(e));
1014 if (feature_mgr_ != nullptr) {
1015 feature_mgr_->AddExtInstImportIds(module());
1016 }
1017}
1018
1019void IRContext::SetMemoryModel(std::unique_ptr<Instruction>&& m) {
1020 module()->SetMemoryModel(std::move(m));
1021}
1022
1023void IRContext::AddEntryPoint(std::unique_ptr<Instruction>&& e) {
1024 module()->AddEntryPoint(std::move(e));
1025}
1026
1027void IRContext::AddExecutionMode(std::unique_ptr<Instruction>&& e) {
1028 module()->AddExecutionMode(std::move(e));
1029}
1030
1031void IRContext::AddDebug1Inst(std::unique_ptr<Instruction>&& d) {
1032 module()->AddDebug1Inst(std::move(d));
1033}
1034
1035void IRContext::AddDebug2Inst(std::unique_ptr<Instruction>&& d) {
1036 if (AreAnalysesValid(kAnalysisNameMap)) {
1037 if (d->opcode() == SpvOpName || d->opcode() == SpvOpMemberName) {
1038 id_to_name_->insert({d->result_id(), d.get()});
1039 }
1040 }
1041 module()->AddDebug2Inst(std::move(d));
1042}
1043
1044void IRContext::AddDebug3Inst(std::unique_ptr<Instruction>&& d) {
1045 module()->AddDebug3Inst(std::move(d));
1046}
1047
1048void IRContext::AddExtInstDebugInfo(std::unique_ptr<Instruction>&& d) {
1049 module()->AddExtInstDebugInfo(std::move(d));
1050}
1051
1052void IRContext::AddAnnotationInst(std::unique_ptr<Instruction>&& a) {
1053 if (AreAnalysesValid(kAnalysisDecorations)) {
1054 get_decoration_mgr()->AddDecoration(a.get());
1055 }
1056 if (AreAnalysesValid(kAnalysisDefUse)) {
1057 get_def_use_mgr()->AnalyzeInstDefUse(a.get());
1058 }
1059 module()->AddAnnotationInst(std::move(a));
1060}
1061
1062void IRContext::AddType(std::unique_ptr<Instruction>&& t) {
1063 module()->AddType(std::move(t));
1064 if (AreAnalysesValid(kAnalysisDefUse)) {
1065 get_def_use_mgr()->AnalyzeInstDefUse(&*(--types_values_end()));
1066 }
1067}
1068
1069void IRContext::AddGlobalValue(std::unique_ptr<Instruction>&& v) {
1070 if (AreAnalysesValid(kAnalysisDefUse)) {
1071 get_def_use_mgr()->AnalyzeInstDefUse(&*v);
1072 }
1073 module()->AddGlobalValue(std::move(v));
1074}
1075
1076void IRContext::AddFunction(std::unique_ptr<Function>&& f) {
1077 module()->AddFunction(std::move(f));
1078}
1079
1080void IRContext::AnalyzeDefUse(Instruction* inst) {
1081 if (AreAnalysesValid(kAnalysisDefUse)) {
1082 get_def_use_mgr()->AnalyzeInstDefUse(inst);
1083 }
1084}
1085
1086void IRContext::UpdateDefUse(Instruction* inst) {
1087 if (AreAnalysesValid(kAnalysisDefUse)) {
1088 get_def_use_mgr()->UpdateDefUse(inst);
1089 }
1090}
1091
1092void IRContext::BuildIdToNameMap() {
1093 id_to_name_ = MakeUnique<std::multimap<uint32_t, Instruction*>>();
1094 for (Instruction& debug_inst : debugs2()) {
1095 if (debug_inst.opcode() == SpvOpMemberName ||
1096 debug_inst.opcode() == SpvOpName) {
1097 id_to_name_->insert({debug_inst.GetSingleWordInOperand(0), &debug_inst});
1098 }
1099 }
1100 valid_analyses_ = valid_analyses_ | kAnalysisNameMap;
1101}
1102
1103IteratorRange<std::multimap<uint32_t, Instruction*>::iterator>
1104IRContext::GetNames(uint32_t id) {
1105 if (!AreAnalysesValid(kAnalysisNameMap)) {
1106 BuildIdToNameMap();
1107 }
1108 auto result = id_to_name_->equal_range(id);
1109 return make_range(std::move(result.first), std::move(result.second));
1110}
1111
1112} // namespace opt
1113} // namespace spvtools
1114
1115#endif // SOURCE_OPT_IR_CONTEXT_H_
1116