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