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