1 // Copyright (c) 2016 The Khronos Group Inc. 2 // Copyright (c) 2016 Valve Corporation 3 // Copyright (c) 2016 LunarG Inc. 4 // 5 // Licensed under the Apache License, Version 2.0 (the "License"); 6 // you may not use this file except in compliance with the License. 7 // You may obtain a copy of the License at 8 // 9 // http://www.apache.org/licenses/LICENSE-2.0 10 // 11 // Unless required by applicable law or agreed to in writing, software 12 // distributed under the License is distributed on an "AS IS" BASIS, 13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 // See the License for the specific language governing permissions and 15 // limitations under the License. 16 17 #ifndef SOURCE_OPT_COMMON_UNIFORM_ELIM_PASS_H_ 18 #define SOURCE_OPT_COMMON_UNIFORM_ELIM_PASS_H_ 19 20 #include <algorithm> 21 #include <list> 22 #include <map> 23 #include <memory> 24 #include <queue> 25 #include <string> 26 #include <unordered_map> 27 #include <unordered_set> 28 #include <utility> 29 #include <vector> 30 31 #include "source/opt/basic_block.h" 32 #include "source/opt/decoration_manager.h" 33 #include "source/opt/def_use_manager.h" 34 #include "source/opt/ir_context.h" 35 #include "source/opt/module.h" 36 #include "source/opt/pass.h" 37 38 namespace spvtools { 39 namespace opt { 40 41 // See optimizer.hpp for documentation. 42 class CommonUniformElimPass : public Pass { 43 using cbb_ptr = const BasicBlock*; 44 45 public: 46 using GetBlocksFunction = 47 std::function<std::vector<BasicBlock*>*(const BasicBlock*)>; 48 49 CommonUniformElimPass(); 50 name()51 const char* name() const override { return "eliminate-common-uniform"; } 52 Status Process() override; 53 54 private: 55 // Returns true if |opcode| is a non-ptr access chain op 56 bool IsNonPtrAccessChain(const SpvOp opcode) const; 57 58 // Returns true if |typeInst| is a sampler or image type or a struct 59 // containing one, recursively. 60 bool IsSamplerOrImageType(const Instruction* typeInst) const; 61 62 // Returns true if |varId| is a variable containing a sampler or image. 63 bool IsSamplerOrImageVar(uint32_t varId) const; 64 65 // Given a load or store pointed at by |ip|, return the top-most 66 // non-CopyObj in its pointer operand. Also return the base pointer 67 // in |objId|. 68 Instruction* GetPtr(Instruction* ip, uint32_t* objId); 69 70 // Return true if variable is uniform 71 bool IsUniformVar(uint32_t varId); 72 73 // Given the type id for a struct type, checks if the struct type 74 // or any struct member is volatile decorated 75 bool IsVolatileStruct(uint32_t type_id); 76 77 // Given an OpAccessChain instruction, return true 78 // if the accessed variable belongs to a volatile 79 // decorated object or member of a struct type 80 bool IsAccessChainToVolatileStructType(const Instruction& AccessChainInst); 81 82 // Given an OpLoad instruction, return true if 83 // OpLoad has a Volatile Memory Access flag or if 84 // the resulting type is a volatile decorated struct 85 bool IsVolatileLoad(const Instruction& loadInst); 86 87 // Return true if any uses of |id| are decorate ops. 88 bool HasUnsupportedDecorates(uint32_t id) const; 89 90 // Return true if all uses of |id| are only name or decorate ops. 91 bool HasOnlyNamesAndDecorates(uint32_t id) const; 92 93 // Delete inst if it has no uses. Assumes inst has a resultId. 94 void DeleteIfUseless(Instruction* inst); 95 96 // Replace all instances of load's id with replId and delete load 97 // and its access chain, if any 98 Instruction* ReplaceAndDeleteLoad(Instruction* loadInst, uint32_t replId, 99 Instruction* ptrInst); 100 101 // For the (constant index) access chain ptrInst, create an 102 // equivalent load and extract 103 void GenACLoadRepl(const Instruction* ptrInst, 104 std::vector<std::unique_ptr<Instruction>>* newInsts, 105 uint32_t* resultId); 106 107 // Return true if all indices are constant 108 bool IsConstantIndexAccessChain(Instruction* acp); 109 110 // Convert all uniform access chain loads into load/extract. 111 bool UniformAccessChainConvert(Function* func); 112 113 // Compute structured successors for function |func|. 114 // A block's structured successors are the blocks it branches to 115 // together with its declared merge block if it has one. 116 // When order matters, the merge block always appears first. 117 // This assures correct depth first search in the presence of early 118 // returns and kills. If the successor vector contain duplicates 119 // if the merge block, they are safely ignored by DFS. 120 // 121 // TODO(dnovillo): This pass computes structured successors slightly different 122 // than the implementation in class Pass. Can this be re-factored? 123 void ComputeStructuredSuccessors(Function* func); 124 125 // Compute structured block order for |func| into |structuredOrder|. This 126 // order has the property that dominators come before all blocks they 127 // dominate and merge blocks come after all blocks that are in the control 128 // constructs of their header. 129 // 130 // TODO(dnovillo): This pass computes structured order slightly different 131 // than the implementation in class Pass. Can this be re-factored? 132 void ComputeStructuredOrder(Function* func, std::list<BasicBlock*>* order); 133 134 // Eliminate loads of uniform variables which have previously been loaded. 135 // If first load is in control flow, move it to first block of function. 136 // Most effective if preceded by UniformAccessChainRemoval(). 137 bool CommonUniformLoadElimination(Function* func); 138 139 // Eliminate loads of uniform sampler and image variables which have 140 // previously 141 // been loaded in the same block for types whose loads cannot cross blocks. 142 bool CommonUniformLoadElimBlock(Function* func); 143 144 // Eliminate duplicated extracts of same id. Extract may be moved to same 145 // block as the id definition. This is primarily intended for extracts 146 // from uniform loads. Most effective if preceded by 147 // CommonUniformLoadElimination(). 148 bool CommonExtractElimination(Function* func); 149 150 // For function |func|, first change all uniform constant index 151 // access chain loads into equivalent composite extracts. Then consolidate 152 // identical uniform loads into one uniform load. Finally, consolidate 153 // identical uniform extracts into one uniform extract. This may require 154 // moving a load or extract to a point which dominates all uses. 155 // Return true if func is modified. 156 // 157 // This pass requires the function to have structured control flow ie shader 158 // capability. It also requires logical addressing ie Addresses capability 159 // is not enabled. It also currently does not support any extensions. 160 // 161 // This function currently only optimizes loads with a single index. 162 bool EliminateCommonUniform(Function* func); 163 164 // Initialize extensions whitelist 165 void InitExtensions(); 166 167 // Return true if all extensions in this module are allowed by this pass. 168 bool AllExtensionsSupported() const; 169 170 // Return true if |op| is a decorate for non-type instruction IsNonTypeDecorate(uint32_t op)171 inline bool IsNonTypeDecorate(uint32_t op) const { 172 return (op == SpvOpDecorate || op == SpvOpDecorateId); 173 } 174 175 // Return true if |inst| is an instruction that loads uniform variable and 176 // can be replaced with other uniform load instruction. IsUniformLoadToBeRemoved(Instruction * inst)177 bool IsUniformLoadToBeRemoved(Instruction* inst) { 178 if (inst->opcode() == SpvOpLoad) { 179 uint32_t varId; 180 Instruction* ptrInst = GetPtr(inst, &varId); 181 if (ptrInst->opcode() == SpvOpVariable && IsUniformVar(varId) && 182 !IsSamplerOrImageVar(varId) && 183 !HasUnsupportedDecorates(inst->result_id()) && !IsVolatileLoad(*inst)) 184 return true; 185 } 186 return false; 187 } 188 189 void Initialize(); 190 Pass::Status ProcessImpl(); 191 192 // Map from uniform variable id to its common load id 193 std::unordered_map<uint32_t, uint32_t> uniform2load_id_; 194 195 // Map of extract composite ids to map of indices to insts 196 // TODO(greg-lunarg): Consider std::vector. 197 std::unordered_map<uint32_t, 198 std::unordered_map<uint32_t, std::list<Instruction*>>> 199 comp2idx2inst_; 200 201 // Extensions supported by this pass. 202 std::unordered_set<std::string> extensions_whitelist_; 203 204 // Map from block to its structured successor blocks. See 205 // ComputeStructuredSuccessors() for definition. 206 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>> 207 block2structured_succs_; 208 }; 209 210 } // namespace opt 211 } // namespace spvtools 212 213 #endif // SOURCE_OPT_COMMON_UNIFORM_ELIM_PASS_H_ 214