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_SCALAR_REPLACEMENT_PASS_H_ 16 #define SOURCE_OPT_SCALAR_REPLACEMENT_PASS_H_ 17 18 #include <cstdio> 19 #include <memory> 20 #include <queue> 21 #include <unordered_map> 22 #include <unordered_set> 23 #include <vector> 24 25 #include "source/opt/function.h" 26 #include "source/opt/pass.h" 27 #include "source/opt/type_manager.h" 28 29 namespace spvtools { 30 namespace opt { 31 32 // Documented in optimizer.hpp 33 class ScalarReplacementPass : public Pass { 34 private: 35 static const uint32_t kDefaultLimit = 100; 36 37 public: 38 ScalarReplacementPass(uint32_t limit = kDefaultLimit) max_num_elements_(limit)39 : max_num_elements_(limit) { 40 name_[0] = '\0'; 41 strcat(name_, "scalar-replacement="); 42 sprintf(&name_[strlen(name_)], "%d", max_num_elements_); 43 } 44 name()45 const char* name() const override { return name_; } 46 47 // Attempts to scalarize all appropriate function scope variables. Returns 48 // SuccessWithChange if any change is made. 49 Status Process() override; 50 GetPreservedAnalyses()51 IRContext::Analysis GetPreservedAnalyses() override { 52 return IRContext::kAnalysisDefUse | 53 IRContext::kAnalysisInstrToBlockMapping | 54 IRContext::kAnalysisDecorations | IRContext::kAnalysisCombinators | 55 IRContext::kAnalysisCFG | IRContext::kAnalysisNameMap | 56 IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; 57 } 58 59 private: 60 // Small container for tracking statistics about variables. 61 // 62 // TODO(alanbaker): Develop some useful heuristics to tune this pass. 63 struct VariableStats { 64 uint32_t num_partial_accesses; 65 uint32_t num_full_accesses; 66 }; 67 68 // Attempts to scalarize all appropriate function scope variables in 69 // |function|. Returns SuccessWithChange if any changes are mode. 70 Status ProcessFunction(Function* function); 71 72 // Returns true if |varInst| can be scalarized. 73 // 74 // Examines the use chain of |varInst| to verify all uses are valid for 75 // scalarization. 76 bool CanReplaceVariable(const Instruction* varInst) const; 77 78 // Returns true if |typeInst| is an acceptable type to scalarize. 79 // 80 // Allows all aggregate types except runtime arrays. Additionally, checks the 81 // that the number of elements that would be scalarized is within bounds. 82 bool CheckType(const Instruction* typeInst) const; 83 84 // Returns true if all the decorations for |varInst| are acceptable for 85 // scalarization. 86 bool CheckAnnotations(const Instruction* varInst) const; 87 88 // Returns true if all the decorations for |typeInst| are acceptable for 89 // scalarization. 90 bool CheckTypeAnnotations(const Instruction* typeInst) const; 91 92 // Returns true if the uses of |inst| are acceptable for scalarization. 93 // 94 // Recursively checks all the uses of |inst|. For |inst| specifically, only 95 // allows SpvOpAccessChain, SpvOpInBoundsAccessChain, SpvOpLoad and 96 // SpvOpStore. Access chains must have the first index be a compile-time 97 // constant. Subsequent uses of access chains (including other access chains) 98 // are checked in a more relaxed manner. 99 bool CheckUses(const Instruction* inst) const; 100 101 // Helper function for the above |CheckUses|. 102 // 103 // This version tracks some stats about the current OpVariable. These stats 104 // are used to drive heuristics about when to scalarize. 105 bool CheckUses(const Instruction* inst, VariableStats* stats) const; 106 107 // Relaxed helper function for |CheckUses|. 108 bool CheckUsesRelaxed(const Instruction* inst) const; 109 110 // Transfers appropriate decorations from |source| to |replacements|. 111 void TransferAnnotations(const Instruction* source, 112 std::vector<Instruction*>* replacements); 113 114 // Scalarizes |inst| and updates its uses. 115 // 116 // |inst| must be an OpVariable. It is replaced with an OpVariable for each 117 // for element of the composite type. Uses of |inst| are updated as 118 // appropriate. If the replacement variables are themselves scalarizable, they 119 // get added to |worklist| for further processing. If any replacement 120 // variable ends up with no uses it is erased. Returns 121 // - Status::SuccessWithoutChange if the variable could not be replaced. 122 // - Status::SuccessWithChange if it made replacements. 123 // - Status::Failure if it couldn't create replacement variables. 124 Pass::Status ReplaceVariable(Instruction* inst, 125 std::queue<Instruction*>* worklist); 126 127 // Returns the underlying storage type for |inst|. 128 // 129 // |inst| must be an OpVariable. Returns the type that is pointed to by 130 // |inst|. 131 Instruction* GetStorageType(const Instruction* inst) const; 132 133 // Returns true if the load can be scalarized. 134 // 135 // |inst| must be an OpLoad. Returns true if |index| is the pointer operand of 136 // |inst| and the load is not from volatile memory. 137 bool CheckLoad(const Instruction* inst, uint32_t index) const; 138 139 // Returns true if the store can be scalarized. 140 // 141 // |inst| must be an OpStore. Returns true if |index| is the pointer operand 142 // of |inst| and the store is not to volatile memory. 143 bool CheckStore(const Instruction* inst, uint32_t index) const; 144 145 // Returns true if |index| is the pointer operand of an OpImageTexelPointer 146 // instruction. 147 bool CheckImageTexelPointer(uint32_t index) const; 148 149 // Creates a variable of type |typeId| from the |index|'th element of 150 // |varInst|. The new variable is added to |replacements|. If the variable 151 // could not be created, then |nullptr| is appended to |replacements|. 152 void CreateVariable(uint32_t typeId, Instruction* varInst, uint32_t index, 153 std::vector<Instruction*>* replacements); 154 155 // Populates |replacements| with a new OpVariable for each element of |inst|. 156 // Returns true if the replacement variables were successfully created. 157 // 158 // |inst| must be an OpVariable of a composite type. New variables are 159 // initialized the same as the corresponding index in |inst|. |replacements| 160 // will contain a variable for each element of the composite with matching 161 // indexes (i.e. the 0'th element of |inst| is the 0'th entry of 162 // |replacements|). 163 bool CreateReplacementVariables(Instruction* inst, 164 std::vector<Instruction*>* replacements); 165 166 // Returns the array length for |arrayInst|. 167 uint64_t GetArrayLength(const Instruction* arrayInst) const; 168 169 // Returns the number of elements in |type|. 170 // 171 // |type| must be a vector or matrix type. 172 uint64_t GetNumElements(const Instruction* type) const; 173 174 // Returns true if |id| is a specialization constant. 175 // 176 // |id| must be registered definition. 177 bool IsSpecConstant(uint32_t id) const; 178 179 // Returns an id for a pointer to |id|. 180 uint32_t GetOrCreatePointerType(uint32_t id); 181 182 // Creates the initial value for the |index| element of |source| in |newVar|. 183 // 184 // If there is an initial value for |source| for element |index|, it is 185 // appended as an operand on |newVar|. If the initial value is OpUndef, no 186 // initial value is added to |newVar|. 187 void GetOrCreateInitialValue(Instruction* source, uint32_t index, 188 Instruction* newVar); 189 190 // Replaces the load to the entire composite. 191 // 192 // Generates a load for each replacement variable and then creates a new 193 // composite by combining all of the loads. 194 // 195 // |load| must be a load. Returns true if successful. 196 bool ReplaceWholeLoad(Instruction* load, 197 const std::vector<Instruction*>& replacements); 198 199 // Replaces the store to the entire composite. 200 // 201 // Generates a composite extract and store for each element in the scalarized 202 // variable from the original store data input. Returns true if successful. 203 bool ReplaceWholeStore(Instruction* store, 204 const std::vector<Instruction*>& replacements); 205 206 // Replaces the DebugDeclare to the entire composite. 207 // 208 // Generates a DebugValue with Deref operation for each element in the 209 // scalarized variable from the original DebugDeclare. Returns true if 210 // successful. 211 bool ReplaceWholeDebugDeclare(Instruction* dbg_decl, 212 const std::vector<Instruction*>& replacements); 213 214 // Replaces the DebugValue to the entire composite. 215 // 216 // Generates a DebugValue for each element in the scalarized variable from 217 // the original DebugValue. Returns true if successful. 218 bool ReplaceWholeDebugValue(Instruction* dbg_value, 219 const std::vector<Instruction*>& replacements); 220 221 // Replaces an access chain to the composite variable with either a direct use 222 // of the appropriate replacement variable or another access chain with the 223 // replacement variable as the base and one fewer indexes. Returns true if 224 // successful. 225 bool ReplaceAccessChain(Instruction* chain, 226 const std::vector<Instruction*>& replacements); 227 228 // Returns a set containing the which components of the result of |inst| are 229 // potentially used. If the return value is |nullptr|, then every components 230 // is possibly used. 231 std::unique_ptr<std::unordered_set<int64_t>> GetUsedComponents( 232 Instruction* inst); 233 234 // Returns an instruction defining a null constant with type |type_id|. If 235 // one already exists, it is returned. Otherwise a new one is created. 236 // Returns |nullptr| if the new constant could not be created. 237 Instruction* CreateNullConstant(uint32_t type_id); 238 239 // Maps storage type to a pointer type enclosing that type. 240 std::unordered_map<uint32_t, uint32_t> pointee_to_pointer_; 241 242 // Maps type id to OpConstantNull for that type. 243 std::unordered_map<uint32_t, uint32_t> type_to_null_; 244 245 // Returns the number of elements in the variable |var_inst|. 246 uint64_t GetMaxLegalIndex(const Instruction* var_inst) const; 247 248 // Returns true if |length| is larger than limit on the size of the variable 249 // that we will be willing to split. 250 bool IsLargerThanSizeLimit(uint64_t length) const; 251 252 // Limit on the number of members in an object that will be replaced. 253 // 0 means there is no limit. 254 uint32_t max_num_elements_; 255 char name_[55]; 256 }; 257 258 } // namespace opt 259 } // namespace spvtools 260 261 #endif // SOURCE_OPT_SCALAR_REPLACEMENT_PASS_H_ 262