1 // Copyright (c) 2019 Google LLC 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_CODE_SINK_H_ 16 #define SOURCE_OPT_CODE_SINK_H_ 17 18 #include <unordered_map> 19 20 #include "source/opt/ir_context.h" 21 #include "source/opt/module.h" 22 #include "source/opt/pass.h" 23 24 namespace spvtools { 25 namespace opt { 26 27 // This pass does code sinking for OpAccessChain and OpLoad on variables in 28 // uniform storage or in read only memory. Code sinking is a transformation 29 // where an instruction is moved into a more deeply nested construct. 30 // 31 // The goal is to move these instructions as close as possible to their uses 32 // without having to execute them more often or to replicate the instruction. 33 // Moving the instruction in this way can lead to shorter live ranges, which can 34 // lead to less register pressure. It can also cause instructions to be 35 // executed less often because they could be moved into one path of a selection 36 // construct. 37 // 38 // This optimization can cause register pressure to rise if the operands of the 39 // instructions go dead after the instructions being moved. That is why we only 40 // move certain OpLoad and OpAccessChain instructions. They generally have 41 // constants, loop induction variables, and global pointers as operands. The 42 // operands are live for a longer time in most cases. 43 class CodeSinkingPass : public Pass { 44 public: name()45 const char* name() const override { return "code-sink"; } 46 Status Process() override; 47 48 // Return the mask of preserved Analyses. GetPreservedAnalyses()49 IRContext::Analysis GetPreservedAnalyses() override { 50 return IRContext::kAnalysisDefUse | 51 IRContext::kAnalysisInstrToBlockMapping | 52 IRContext::kAnalysisCombinators | IRContext::kAnalysisCFG | 53 IRContext::kAnalysisDominatorAnalysis | 54 IRContext::kAnalysisLoopAnalysis | IRContext::kAnalysisNameMap | 55 IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; 56 } 57 58 private: 59 // Sinks the instructions in |bb| as much as possible. Returns true if 60 // something changes. 61 bool SinkInstructionsInBB(BasicBlock* bb); 62 63 // Tries the sink |inst| as much as possible. Returns true if the instruction 64 // is moved. 65 bool SinkInstruction(Instruction* inst); 66 67 // Returns the basic block in which to move |inst| to move is as close as 68 // possible to the uses of |inst| without increasing the number of times 69 // |inst| will be executed. Return |nullptr| if there is no need to move 70 // |inst|. 71 BasicBlock* FindNewBasicBlockFor(Instruction* inst); 72 73 // Return true if |inst| reference memory and it is possible that the data in 74 // the memory changes at some point. 75 bool ReferencesMutableMemory(Instruction* inst); 76 77 // Returns true if the module contains an instruction that has a memory 78 // semantics id as an operand, and the memory semantics enforces a 79 // synchronization of uniform memory. See section 3.25 of the SPIR-V 80 // specification. 81 bool HasUniformMemorySync(); 82 83 // Returns true if there may be a store to the variable |var_inst|. 84 bool HasPossibleStore(Instruction* var_inst); 85 86 // Returns true if one of the basic blocks in |set| exists on a path from the 87 // basic block |start| to |end|. 88 bool IntersectsPath(uint32_t start, uint32_t end, 89 const std::unordered_set<uint32_t>& set); 90 91 // Returns true if |mem_semantics_id| is the id of a constant that, when 92 // interpreted as a memory semantics mask enforces synchronization of uniform 93 // memory. See section 3.25 of the SPIR-V specification. 94 bool IsSyncOnUniform(uint32_t mem_semantics_id) const; 95 96 // True if a check has for uniform storage has taken place. 97 bool checked_for_uniform_sync_; 98 99 // Cache of whether or not the module has a memory sync on uniform storage. 100 // only valid if |check_for_uniform_sync_| is true. 101 bool has_uniform_sync_; 102 }; 103 104 } // namespace opt 105 } // namespace spvtools 106 107 #endif // SOURCE_OPT_CODE_SINK_H_ 108