Debian Codegraph @

third_party/spirv-tools/source/opt/desc_sroa.cpp

raw
1 // Copyright (c) 2019 Google LLC
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 #include "source/opt/desc_sroa.h"
16
17 #include "source/util/string_utils.h"
18
19 namespace spvtools {
20 namespace opt {
21
22 Pass::Status DescriptorScalarReplacement::Process() {
23 bool modified = false;
24
25 std::vector<Instruction*> vars_to_kill;
26
27 for (Instruction& var : context()->types_values()) {
28 if (IsCandidate(&var)) {
29 modified = true;
30 if (!ReplaceCandidate(&var)) {
31 return Status::Failure;
32 }
33 vars_to_kill.push_back(&var);
34 }
35 }
36
37 for (Instruction* var : vars_to_kill) {
38 context()->KillInst(var);
39 }
40
41 return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
42 }
43
44 bool DescriptorScalarReplacement::IsCandidate(Instruction* var) {
45 if (var->opcode() != SpvOpVariable) {
46 return false;
47 }
48
49 uint32_t ptr_type_id = var->type_id();
50 Instruction* ptr_type_inst =
51 context()->get_def_use_mgr()->GetDef(ptr_type_id);
52 if (ptr_type_inst->opcode() != SpvOpTypePointer) {
53 return false;
54 }
55
56 uint32_t var_type_id = ptr_type_inst->GetSingleWordInOperand(1);
57 Instruction* var_type_inst =
58 context()->get_def_use_mgr()->GetDef(var_type_id);
59 if (var_type_inst->opcode() != SpvOpTypeArray &&
60 var_type_inst->opcode() != SpvOpTypeStruct) {
61 return false;
62 }
63
64 // All structures with descriptor assignments must be replaced by variables,
65 // one for each of their members - with the exceptions of buffers.
66 // Buffers are represented as structures, but we shouldn't replace a buffer
67 // with its elements. All buffers have offset decorations for members of their
68 // structure types.
69 bool has_offset_decoration = false;
70 context()->get_decoration_mgr()->ForEachDecoration(
71 var_type_inst->result_id(), SpvDecorationOffset,
72 [&has_offset_decoration](const Instruction&) {
73 has_offset_decoration = true;
74 });
75 if (has_offset_decoration) {
76 return false;
77 }
78
79 bool has_desc_set_decoration = false;
80 context()->get_decoration_mgr()->ForEachDecoration(
81 var->result_id(), SpvDecorationDescriptorSet,
82 [&has_desc_set_decoration](const Instruction&) {
83 has_desc_set_decoration = true;
84 });
85 if (!has_desc_set_decoration) {
86 return false;
87 }
88
89 bool has_binding_decoration = false;
90 context()->get_decoration_mgr()->ForEachDecoration(
91 var->result_id(), SpvDecorationBinding,
92 [&has_binding_decoration](const Instruction&) {
93 has_binding_decoration = true;
94 });
95 if (!has_binding_decoration) {
96 return false;
97 }
98
99 return true;
100 }
101
102 bool DescriptorScalarReplacement::ReplaceCandidate(Instruction* var) {
103 std::vector<Instruction*> access_chain_work_list;
104 std::vector<Instruction*> load_work_list;
105 bool failed = !get_def_use_mgr()->WhileEachUser(
106 var->result_id(),
107 [this, &access_chain_work_list, &load_work_list](Instruction* use) {
108 if (use->opcode() == SpvOpName) {
109 return true;
110 }
111
112 if (use->IsDecoration()) {
113 return true;
114 }
115
116 switch (use->opcode()) {
117 case SpvOpAccessChain:
118 case SpvOpInBoundsAccessChain:
119 access_chain_work_list.push_back(use);
120 return true;
121 case SpvOpLoad:
122 load_work_list.push_back(use);
123 return true;
124 default:
125 context()->EmitErrorMessage(
126 "Variable cannot be replaced: invalid instruction", use);
127 return false;
128 }
129 return true;
130 });
131
132 if (failed) {
133 return false;
134 }
135
136 for (Instruction* use : access_chain_work_list) {
137 if (!ReplaceAccessChain(var, use)) {
138 return false;
139 }
140 }
141 for (Instruction* use : load_work_list) {
142 if (!ReplaceLoadedValue(var, use)) {
143 return false;
144 }
145 }
146 return true;
147 }
148
149 bool DescriptorScalarReplacement::ReplaceAccessChain(Instruction* var,
150 Instruction* use) {
151 if (use->NumInOperands() <= 1) {
152 context()->EmitErrorMessage(
153 "Variable cannot be replaced: invalid instruction", use);
154 return false;
155 }
156
157 uint32_t idx_id = use->GetSingleWordInOperand(1);
158 const analysis::Constant* idx_const =
159 context()->get_constant_mgr()->FindDeclaredConstant(idx_id);
160 if (idx_const == nullptr) {
161 context()->EmitErrorMessage("Variable cannot be replaced: invalid index",
162 use);
163 return false;
164 }
165
166 uint32_t idx = idx_const->GetU32();
167 uint32_t replacement_var = GetReplacementVariable(var, idx);
168
169 if (use->NumInOperands() == 2) {
170 // We are not indexing into the replacement variable. We can replaces the
171 // access chain with the replacement varibale itself.
172 context()->ReplaceAllUsesWith(use->result_id(), replacement_var);
173 context()->KillInst(use);
174 return true;
175 }
176
177 // We need to build a new access chain with the replacement variable as the
178 // base address.
179 Instruction::OperandList new_operands;
180
181 // Same result id and result type.
182 new_operands.emplace_back(use->GetOperand(0));
183 new_operands.emplace_back(use->GetOperand(1));
184
185 // Use the replacement variable as the base address.
186 new_operands.push_back({SPV_OPERAND_TYPE_ID, {replacement_var}});
187
188 // Drop the first index because it is consumed by the replacment, and copy the
189 // rest.
190 for (uint32_t i = 4; i < use->NumOperands(); i++) {
191 new_operands.emplace_back(use->GetOperand(i));
192 }
193
194 use->ReplaceOperands(new_operands);
195 context()->UpdateDefUse(use);
196 return true;
197 }
198
199 uint32_t DescriptorScalarReplacement::GetReplacementVariable(Instruction* var,
200 uint32_t idx) {
201 auto replacement_vars = replacement_variables_.find(var);
202 if (replacement_vars == replacement_variables_.end()) {
203 uint32_t ptr_type_id = var->type_id();
204 Instruction* ptr_type_inst = get_def_use_mgr()->GetDef(ptr_type_id);
205 assert(ptr_type_inst->opcode() == SpvOpTypePointer &&
206 "Variable should be a pointer to an array or structure.");
207 uint32_t pointee_type_id = ptr_type_inst->GetSingleWordInOperand(1);
208 Instruction* pointee_type_inst = get_def_use_mgr()->GetDef(pointee_type_id);
209 const bool is_array = pointee_type_inst->opcode() == SpvOpTypeArray;
210 const bool is_struct = pointee_type_inst->opcode() == SpvOpTypeStruct;
211 assert((is_array || is_struct) &&
212 "Variable should be a pointer to an array or structure.");
213
214 // For arrays, each array element should be replaced with a new replacement
215 // variable
216 if (is_array) {
217 uint32_t array_len_id = pointee_type_inst->GetSingleWordInOperand(1);
218 const analysis::Constant* array_len_const =
219 context()->get_constant_mgr()->FindDeclaredConstant(array_len_id);
220 assert(array_len_const != nullptr && "Array length must be a constant.");
221 uint32_t array_len = array_len_const->GetU32();
222
223 replacement_vars = replacement_variables_
224 .insert({var, std::vector<uint32_t>(array_len, 0)})
225 .first;
226 }
227 // For structures, each member should be replaced with a new replacement
228 // variable
229 if (is_struct) {
230 const uint32_t num_members = pointee_type_inst->NumInOperands();
231 replacement_vars =
232 replacement_variables_
233 .insert({var, std::vector<uint32_t>(num_members, 0)})
234 .first;
235 }
236 }
237
238 if (replacement_vars->second[idx] == 0) {
239 replacement_vars->second[idx] = CreateReplacementVariable(var, idx);
240 }
241
242 return replacement_vars->second[idx];
243 }
244
245 uint32_t DescriptorScalarReplacement::CreateReplacementVariable(
246 Instruction* var, uint32_t idx) {
247 // The storage class for the new variable is the same as the original.
248 SpvStorageClass storage_class =
249 static_cast<SpvStorageClass>(var->GetSingleWordInOperand(0));
250
251 // The type for the new variable will be a pointer to type of the elements of
252 // the array.
253 uint32_t ptr_type_id = var->type_id();
254 Instruction* ptr_type_inst = get_def_use_mgr()->GetDef(ptr_type_id);
255 assert(ptr_type_inst->opcode() == SpvOpTypePointer &&
256 "Variable should be a pointer to an array or structure.");
257 uint32_t pointee_type_id = ptr_type_inst->GetSingleWordInOperand(1);
258 Instruction* pointee_type_inst = get_def_use_mgr()->GetDef(pointee_type_id);
259 const bool is_array = pointee_type_inst->opcode() == SpvOpTypeArray;
260 const bool is_struct = pointee_type_inst->opcode() == SpvOpTypeStruct;
261 assert((is_array || is_struct) &&
262 "Variable should be a pointer to an array or structure.");
263
264 uint32_t element_type_id =
265 is_array ? pointee_type_inst->GetSingleWordInOperand(0)
266 : pointee_type_inst->GetSingleWordInOperand(idx);
267
268 uint32_t ptr_element_type_id = context()->get_type_mgr()->FindPointerToType(
269 element_type_id, storage_class);
270
271 // Create the variable.
272 uint32_t id = TakeNextId();
273 std::unique_ptr<Instruction> variable(
274 new Instruction(context(), SpvOpVariable, ptr_element_type_id, id,
275 std::initializer_list<Operand>{
276 {SPV_OPERAND_TYPE_STORAGE_CLASS,
277 {static_cast<uint32_t>(storage_class)}}}));
278 context()->AddGlobalValue(std::move(variable));
279
280 // Copy all of the decorations to the new variable. The only difference is
281 // the Binding decoration needs to be adjusted.
282 for (auto old_decoration :
283 get_decoration_mgr()->GetDecorationsFor(var->result_id(), true)) {
284 assert(old_decoration->opcode() == SpvOpDecorate);
285 std::unique_ptr<Instruction> new_decoration(
286 old_decoration->Clone(context()));
287 new_decoration->SetInOperand(0, {id});
288
289 uint32_t decoration = new_decoration->GetSingleWordInOperand(1u);
290 if (decoration == SpvDecorationBinding) {
291 uint32_t new_binding = new_decoration->GetSingleWordInOperand(2);
292 if (is_array) {
293 new_binding += idx * GetNumBindingsUsedByType(ptr_element_type_id);
294 }
295 if (is_struct) {
296 // The binding offset that should be added is the sum of binding numbers
297 // used by previous members of the current struct.
298 for (uint32_t i = 0; i < idx; ++i) {
299 new_binding += GetNumBindingsUsedByType(
300 pointee_type_inst->GetSingleWordInOperand(i));
301 }
302 }
303 new_decoration->SetInOperand(2, {new_binding});
304 }
305 context()->AddAnnotationInst(std::move(new_decoration));
306 }
307
308 // Create a new OpName for the replacement variable.
309 std::vector<std::unique_ptr<Instruction>> names_to_add;
310 for (auto p : context()->GetNames(var->result_id())) {
311 Instruction* name_inst = p.second;
312 std::string name_str = utils::MakeString(name_inst->GetOperand(1).words);
313 if (is_array) {
314 name_str += "[" + utils::ToString(idx) + "]";
315 }
316 if (is_struct) {
317 Instruction* member_name_inst =
318 context()->GetMemberName(pointee_type_inst->result_id(), idx);
319 name_str += ".";
320 if (member_name_inst)
321 name_str += utils::MakeString(member_name_inst->GetOperand(2).words);
322 else
323 // In case the member does not have a name assigned to it, use the
324 // member index.
325 name_str += utils::ToString(idx);
326 }
327
328 std::unique_ptr<Instruction> new_name(new Instruction(
329 context(), SpvOpName, 0, 0,
330 std::initializer_list<Operand>{
331 {SPV_OPERAND_TYPE_ID, {id}},
332 {SPV_OPERAND_TYPE_LITERAL_STRING, utils::MakeVector(name_str)}}));
333 Instruction* new_name_inst = new_name.get();
334 get_def_use_mgr()->AnalyzeInstDefUse(new_name_inst);
335 names_to_add.push_back(std::move(new_name));
336 }
337
338 // We shouldn't add the new names when we are iterating over name ranges
339 // above. We can add all the new names now.
340 for (auto& new_name : names_to_add)
341 context()->AddDebug2Inst(std::move(new_name));
342
343 return id;
344 }
345
346 uint32_t DescriptorScalarReplacement::GetNumBindingsUsedByType(
347 uint32_t type_id) {
348 Instruction* type_inst = get_def_use_mgr()->GetDef(type_id);
349
350 // If it's a pointer, look at the underlying type.
351 if (type_inst->opcode() == SpvOpTypePointer) {
352 type_id = type_inst->GetSingleWordInOperand(1);
353 type_inst = get_def_use_mgr()->GetDef(type_id);
354 }
355
356 // Arrays consume N*M binding numbers where N is the array length, and M is
357 // the number of bindings used by each array element.
358 if (type_inst->opcode() == SpvOpTypeArray) {
359 uint32_t element_type_id = type_inst->GetSingleWordInOperand(0);
360 uint32_t length_id = type_inst->GetSingleWordInOperand(1);
361 const analysis::Constant* length_const =
362 context()->get_constant_mgr()->FindDeclaredConstant(length_id);
363 // OpTypeArray's length must always be a constant
364 assert(length_const != nullptr);
365 uint32_t num_elems = length_const->GetU32();
366 return num_elems * GetNumBindingsUsedByType(element_type_id);
367 }
368
369 // The number of bindings consumed by a structure is the sum of the bindings
370 // used by its members.
371 if (type_inst->opcode() == SpvOpTypeStruct) {
372 uint32_t sum = 0;
373 for (uint32_t i = 0; i < type_inst->NumInOperands(); i++)
374 sum += GetNumBindingsUsedByType(type_inst->GetSingleWordInOperand(i));
375 return sum;
376 }
377
378 // All other types are considered to take up 1 binding number.
379 return 1;
380 }
381
382 bool DescriptorScalarReplacement::ReplaceLoadedValue(Instruction* var,
383 Instruction* value) {
384 // |var| is the global variable that has to be eliminated (OpVariable).
385 // |value| is the OpLoad instruction that has loaded |var|.
386 // The function expects all users of |value| to be OpCompositeExtract
387 // instructions. Otherwise the function returns false with an error message.
388 assert(value->opcode() == SpvOpLoad);
389 assert(value->GetSingleWordInOperand(0) == var->result_id());
390 std::vector<Instruction*> work_list;
391 bool failed = !get_def_use_mgr()->WhileEachUser(
392 value->result_id(), [this, &work_list](Instruction* use) {
393 if (use->opcode() != SpvOpCompositeExtract) {
394 context()->EmitErrorMessage(
395 "Variable cannot be replaced: invalid instruction", use);
396 return false;
397 }
398 work_list.push_back(use);
399 return true;
400 });
401
402 if (failed) {
403 return false;
404 }
405
406 for (Instruction* use : work_list) {
407 if (!ReplaceCompositeExtract(var, use)) {
408 return false;
409 }
410 }
411
412 // All usages of the loaded value have been killed. We can kill the OpLoad.
413 context()->KillInst(value);
414 return true;
415 }
416
417 bool DescriptorScalarReplacement::ReplaceCompositeExtract(
418 Instruction* var, Instruction* extract) {
419 assert(extract->opcode() == SpvOpCompositeExtract);
420 // We're currently only supporting extractions of one index at a time. If we
421 // need to, we can handle cases with multiple indexes in the future.
422 if (extract->NumInOperands() != 2) {
423 context()->EmitErrorMessage(
424 "Variable cannot be replaced: invalid instruction", extract);
425 return false;
426 }
427
428 uint32_t replacement_var =
429 GetReplacementVariable(var, extract->GetSingleWordInOperand(1));
430
431 // The result type of the OpLoad is the same as the result type of the
432 // OpCompositeExtract.
433 uint32_t load_id = TakeNextId();
434 std::unique_ptr<Instruction> load(
435 new Instruction(context(), SpvOpLoad, extract->type_id(), load_id,
436 std::initializer_list<Operand>{
437 {SPV_OPERAND_TYPE_ID, {replacement_var}}}));
438 Instruction* load_instr = load.get();
439 get_def_use_mgr()->AnalyzeInstDefUse(load_instr);
440 context()->set_instr_block(load_instr, context()->get_instr_block(extract));
441 extract->InsertBefore(std::move(load));
442 context()->ReplaceAllUsesWith(extract->result_id(), load_id);
443 context()->KillInst(extract);
444 return true;
445 }
446
447 } // namespace opt
448 } // namespace spvtools