Debian Codegraph @

third_party/spirv-tools/source/opt/scalar_replacement_pass.h

raw
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)
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
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
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_