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 } 57 58 private: 59 // Small container for tracking statistics about variables. 60 // 61 // TODO(alanbaker): Develop some useful heuristics to tune this pass. 62 struct VariableStats { 63 uint32_t num_partial_accesses; 64 uint32_t num_full_accesses; 65 }; 66 67 // Attempts to scalarize all appropriate function scope variables in 68 // |function|. Returns SuccessWithChange if any changes are mode. 69 Status ProcessFunction(Function* function); 70 71 // Returns true if |varInst| can be scalarized. 72 // 73 // Examines the use chain of |varInst| to verify all uses are valid for 74 // scalarization. 75 bool CanReplaceVariable(const Instruction* varInst) const; 76 77 // Returns true if |typeInst| is an acceptable type to scalarize. 78 // 79 // Allows all aggregate types except runtime arrays. Additionally, checks the 80 // that the number of elements that would be scalarized is within bounds. 81 bool CheckType(const Instruction* typeInst) const; 82 83 // Returns true if all the decorations for |varInst| are acceptable for 84 // scalarization. 85 bool CheckAnnotations(const Instruction* varInst) const; 86 87 // Returns true if all the decorations for |typeInst| are acceptable for 88 // scalarization. 89 bool CheckTypeAnnotations(const Instruction* typeInst) const; 90 91 // Returns true if the uses of |inst| are acceptable for scalarization. 92 // 93 // Recursively checks all the uses of |inst|. For |inst| specifically, only 94 // allows SpvOpAccessChain, SpvOpInBoundsAccessChain, SpvOpLoad and 95 // SpvOpStore. Access chains must have the first index be a compile-time 96 // constant. Subsequent uses of access chains (including other access chains) 97 // are checked in a more relaxed manner. 98 bool CheckUses(const Instruction* inst) const; 99 100 // Helper function for the above |CheckUses|. 101 // 102 // This version tracks some stats about the current OpVariable. These stats 103 // are used to drive heuristics about when to scalarize. 104 bool CheckUses(const Instruction* inst, VariableStats* stats) const; 105 106 // Relaxed helper function for |CheckUses|. 107 bool CheckUsesRelaxed(const Instruction* inst) const; 108 109 // Transfers appropriate decorations from |source| to |replacements|. 110 void TransferAnnotations(const Instruction* source, 111 std::vector<Instruction*>* replacements); 112 113 // Scalarizes |inst| and updates its uses. 114 // 115 // |inst| must be an OpVariable. It is replaced with an OpVariable for each 116 // for element of the composite type. Uses of |inst| are updated as 117 // appropriate. If the replacement variables are themselves scalarizable, they 118 // get added to |worklist| for further processing. If any replacement 119 // variable ends up with no uses it is erased. Returns false if any 120 // subsequent access chain is out of bounds. 121 bool ReplaceVariable(Instruction* inst, std::queue<Instruction*>* worklist); 122 123 // Returns the underlying storage type for |inst|. 124 // 125 // |inst| must be an OpVariable. Returns the type that is pointed to by 126 // |inst|. 127 Instruction* GetStorageType(const Instruction* inst) const; 128 129 // Returns true if the load can be scalarized. 130 // 131 // |inst| must be an OpLoad. Returns true if |index| is the pointer operand of 132 // |inst| and the load is not from volatile memory. 133 bool CheckLoad(const Instruction* inst, uint32_t index) const; 134 135 // Returns true if the store can be scalarized. 136 // 137 // |inst| must be an OpStore. Returns true if |index| is the pointer operand 138 // of |inst| and the store is not to volatile memory. 139 bool CheckStore(const Instruction* inst, uint32_t index) const; 140 141 // Creates a variable of type |typeId| from the |index|'th element of 142 // |varInst|. The new variable is added to |replacements|. 143 void CreateVariable(uint32_t typeId, Instruction* varInst, uint32_t index, 144 std::vector<Instruction*>* replacements); 145 146 // Populates |replacements| with a new OpVariable for each element of |inst|. 147 // 148 // |inst| must be an OpVariable of a composite type. New variables are 149 // initialized the same as the corresponding index in |inst|. |replacements| 150 // will contain a variable for each element of the composite with matching 151 // indexes (i.e. the 0'th element of |inst| is the 0'th entry of 152 // |replacements|). 153 void CreateReplacementVariables(Instruction* inst, 154 std::vector<Instruction*>* replacements); 155 156 // Returns the value of an OpConstant of integer type. 157 // 158 // |constant| must use two or fewer words to generate the value. 159 size_t GetConstantInteger(const Instruction* constant) const; 160 161 // Returns the integer literal for |op|. 162 size_t GetIntegerLiteral(const Operand& op) const; 163 164 // Returns the array length for |arrayInst|. 165 size_t GetArrayLength(const Instruction* arrayInst) const; 166 167 // Returns the number of elements in |type|. 168 // 169 // |type| must be a vector or matrix type. 170 size_t GetNumElements(const Instruction* type) const; 171 172 // Returns true if |id| is a specialization constant. 173 // 174 // |id| must be registered definition. 175 bool IsSpecConstant(uint32_t id) const; 176 177 // Returns an id for a pointer to |id|. 178 uint32_t GetOrCreatePointerType(uint32_t id); 179 180 // Creates the initial value for the |index| element of |source| in |newVar|. 181 // 182 // If there is an initial value for |source| for element |index|, it is 183 // appended as an operand on |newVar|. If the initial value is OpUndef, no 184 // initial value is added to |newVar|. 185 void GetOrCreateInitialValue(Instruction* source, uint32_t index, 186 Instruction* newVar); 187 188 // Replaces the load to the entire composite. 189 // 190 // Generates a load for each replacement variable and then creates a new 191 // composite by combining all of the loads. 192 // 193 // |load| must be a load. 194 void ReplaceWholeLoad(Instruction* load, 195 const std::vector<Instruction*>& replacements); 196 197 // Replaces the store to the entire composite. 198 // 199 // Generates a composite extract and store for each element in the scalarized 200 // variable from the original store data input. 201 void ReplaceWholeStore(Instruction* store, 202 const std::vector<Instruction*>& replacements); 203 204 // Replaces an access chain to the composite variable with either a direct use 205 // of the appropriate replacement variable or another access chain with the 206 // replacement variable as the base and one fewer indexes. Returns false if 207 // the chain has an out of bounds access. 208 bool ReplaceAccessChain(Instruction* chain, 209 const std::vector<Instruction*>& replacements); 210 211 // Returns a set containing the which components of the result of |inst| are 212 // potentially used. If the return value is |nullptr|, then every components 213 // is possibly used. 214 std::unique_ptr<std::unordered_set<uint64_t>> GetUsedComponents( 215 Instruction* inst); 216 217 // Returns an instruction defining a null constant with type |type_id|. If 218 // one already exists, it is returned. Otherwise a new one is created. 219 Instruction* CreateNullConstant(uint32_t type_id); 220 221 // Maps storage type to a pointer type enclosing that type. 222 std::unordered_map<uint32_t, uint32_t> pointee_to_pointer_; 223 224 // Maps type id to OpConstantNull for that type. 225 std::unordered_map<uint32_t, uint32_t> type_to_null_; 226 227 // Limit on the number of members in an object that will be replaced. 228 // 0 means there is no limit. 229 uint32_t max_num_elements_; 230 bool IsLargerThanSizeLimit(size_t length) const; 231 char name_[55]; 232 }; 233 234 } // namespace opt 235 } // namespace spvtools 236 237 #endif // SOURCE_OPT_SCALAR_REPLACEMENT_PASS_H_ 238