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
29namespace spvtools {
30namespace opt {
31
32// Documented in optimizer.hpp
33class 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 an access chain to the composite variable with either a direct use
203 // of the appropriate replacement variable or another access chain with the
204 // replacement variable as the base and one fewer indexes. Returns true if
205 // successful.
206 bool ReplaceAccessChain(Instruction* chain,
207 const std::vector<Instruction*>& replacements);
208
209 // Returns a set containing the which components of the result of |inst| are
210 // potentially used. If the return value is |nullptr|, then every components
211 // is possibly used.
212 std::unique_ptr<std::unordered_set<int64_t>> GetUsedComponents(
213 Instruction* inst);
214
215 // Returns an instruction defining a null constant with type |type_id|. If
216 // one already exists, it is returned. Otherwise a new one is created.
217 // Returns |nullptr| if the new constant could not be created.
218 Instruction* CreateNullConstant(uint32_t type_id);
219
220 // Maps storage type to a pointer type enclosing that type.
221 std::unordered_map<uint32_t, uint32_t> pointee_to_pointer_;
222
223 // Maps type id to OpConstantNull for that type.
224 std::unordered_map<uint32_t, uint32_t> type_to_null_;
225
226 // Returns the number of elements in the variable |var_inst|.
227 uint64_t GetMaxLegalIndex(const Instruction* var_inst) const;
228
229 // Returns true if |length| is larger than limit on the size of the variable
230 // that we will be willing to split.
231 bool IsLargerThanSizeLimit(uint64_t length) const;
232
233 // Limit on the number of members in an object that will be replaced.
234 // 0 means there is no limit.
235 uint32_t max_num_elements_;
236 char name_[55];
237};
238
239} // namespace opt
240} // namespace spvtools
241
242#endif // SOURCE_OPT_SCALAR_REPLACEMENT_PASS_H_
243