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