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 // Creates a variable of type |typeId| from the |index|'th element of 146 // |varInst|. The new variable is added to |replacements|. If the variable 147 // could not be created, then |nullptr| is appended to |replacements|. 148 void CreateVariable(uint32_t typeId, Instruction* varInst, uint32_t index, 149 std::vector<Instruction*>* replacements); 150 151 // Populates |replacements| with a new OpVariable for each element of |inst|. 152 // Returns true if the replacement variables were successfully created. 153 // 154 // |inst| must be an OpVariable of a composite type. New variables are 155 // initialized the same as the corresponding index in |inst|. |replacements| 156 // will contain a variable for each element of the composite with matching 157 // indexes (i.e. the 0'th element of |inst| is the 0'th entry of 158 // |replacements|). 159 bool CreateReplacementVariables(Instruction* inst, 160 std::vector<Instruction*>* replacements); 161 162 // Returns the array length for |arrayInst|. 163 uint64_t GetArrayLength(const Instruction* arrayInst) const; 164 165 // Returns the number of elements in |type|. 166 // 167 // |type| must be a vector or matrix type. 168 uint64_t GetNumElements(const Instruction* type) const; 169 170 // Returns true if |id| is a specialization constant. 171 // 172 // |id| must be registered definition. 173 bool IsSpecConstant(uint32_t id) const; 174 175 // Returns an id for a pointer to |id|. 176 uint32_t GetOrCreatePointerType(uint32_t id); 177 178 // Creates the initial value for the |index| element of |source| in |newVar|. 179 // 180 // If there is an initial value for |source| for element |index|, it is 181 // appended as an operand on |newVar|. If the initial value is OpUndef, no 182 // initial value is added to |newVar|. 183 void GetOrCreateInitialValue(Instruction* source, uint32_t index, 184 Instruction* newVar); 185 186 // Replaces the load to the entire composite. 187 // 188 // Generates a load for each replacement variable and then creates a new 189 // composite by combining all of the loads. 190 // 191 // |load| must be a load. Returns true if successful. 192 bool ReplaceWholeLoad(Instruction* load, 193 const std::vector<Instruction*>& replacements); 194 195 // Replaces the store to the entire composite. 196 // 197 // Generates a composite extract and store for each element in the scalarized 198 // variable from the original store data input. Returns true if successful. 199 bool ReplaceWholeStore(Instruction* store, 200 const std::vector<Instruction*>& replacements); 201 202 // Replaces the DebugDeclare to the entire composite. 203 // 204 // Generates a DebugValue with Deref operation for each element in the 205 // scalarized variable from the original DebugDeclare. Returns true if 206 // successful. 207 bool ReplaceWholeDebugDeclare(Instruction* dbg_decl, 208 const std::vector<Instruction*>& replacements); 209 210 // Replaces the DebugValue to the entire composite. 211 // 212 // Generates a DebugValue for each element in the scalarized variable from 213 // the original DebugValue. Returns true if successful. 214 bool ReplaceWholeDebugValue(Instruction* dbg_value, 215 const std::vector<Instruction*>& replacements); 216 217 // Replaces an access chain to the composite variable with either a direct use 218 // of the appropriate replacement variable or another access chain with the 219 // replacement variable as the base and one fewer indexes. Returns true if 220 // successful. 221 bool ReplaceAccessChain(Instruction* chain, 222 const std::vector<Instruction*>& replacements); 223 224 // Returns a set containing the which components of the result of |inst| are 225 // potentially used. If the return value is |nullptr|, then every components 226 // is possibly used. 227 std::unique_ptr<std::unordered_set<int64_t>> GetUsedComponents( 228 Instruction* inst); 229 230 // Returns an instruction defining a null constant with type |type_id|. If 231 // one already exists, it is returned. Otherwise a new one is created. 232 // Returns |nullptr| if the new constant could not be created. 233 Instruction* CreateNullConstant(uint32_t type_id); 234 235 // Maps storage type to a pointer type enclosing that type. 236 std::unordered_map<uint32_t, uint32_t> pointee_to_pointer_; 237 238 // Maps type id to OpConstantNull for that type. 239 std::unordered_map<uint32_t, uint32_t> type_to_null_; 240 241 // Returns the number of elements in the variable |var_inst|. 242 uint64_t GetMaxLegalIndex(const Instruction* var_inst) const; 243 244 // Returns true if |length| is larger than limit on the size of the variable 245 // that we will be willing to split. 246 bool IsLargerThanSizeLimit(uint64_t length) const; 247 248 // Limit on the number of members in an object that will be replaced. 249 // 0 means there is no limit. 250 uint32_t max_num_elements_; 251 char name_[55]; 252 }; 253 254 } // namespace opt 255 } // namespace spvtools 256 257 #endif // SOURCE_OPT_SCALAR_REPLACEMENT_PASS_H_ 258