1// Copyright (c) 2018 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/vector_dce.h"
16
17#include <utility>
18
19namespace spvtools {
20namespace opt {
21namespace {
22
23const uint32_t kExtractCompositeIdInIdx = 0;
24const uint32_t kInsertObjectIdInIdx = 0;
25const uint32_t kInsertCompositeIdInIdx = 1;
26
27} // namespace
28
29Pass::Status VectorDCE::Process() {
30 bool modified = false;
31 for (Function& function : *get_module()) {
32 modified |= VectorDCEFunction(&function);
33 }
34 return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
35}
36
37bool VectorDCE::VectorDCEFunction(Function* function) {
38 LiveComponentMap live_components;
39 FindLiveComponents(function, &live_components);
40 return RewriteInstructions(function, live_components);
41}
42
43void VectorDCE::FindLiveComponents(Function* function,
44 LiveComponentMap* live_components) {
45 std::vector<WorkListItem> work_list;
46
47 // Prime the work list. We will assume that any instruction that does
48 // not result in a vector is live.
49 //
50 // Extending to structures and matrices is not as straight forward because of
51 // the nesting. We cannot simply us a bit vector to keep track of which
52 // components are live because of arbitrary nesting of structs.
53 function->ForEachInst(
54 [&work_list, this, live_components](Instruction* current_inst) {
55 if (!HasVectorOrScalarResult(current_inst) ||
56 !context()->IsCombinatorInstruction(current_inst)) {
57 MarkUsesAsLive(current_inst, all_components_live_, live_components,
58 &work_list);
59 }
60 });
61
62 // Process the work list propagating liveness.
63 for (uint32_t i = 0; i < work_list.size(); i++) {
64 WorkListItem current_item = work_list[i];
65 Instruction* current_inst = current_item.instruction;
66
67 switch (current_inst->opcode()) {
68 case SpvOpCompositeExtract:
69 MarkExtractUseAsLive(current_inst, current_item.components,
70 live_components, &work_list);
71 break;
72 case SpvOpCompositeInsert:
73 MarkInsertUsesAsLive(current_item, live_components, &work_list);
74 break;
75 case SpvOpVectorShuffle:
76 MarkVectorShuffleUsesAsLive(current_item, live_components, &work_list);
77 break;
78 case SpvOpCompositeConstruct:
79 MarkCompositeContructUsesAsLive(current_item, live_components,
80 &work_list);
81 break;
82 default:
83 if (current_inst->IsScalarizable()) {
84 MarkUsesAsLive(current_inst, current_item.components, live_components,
85 &work_list);
86 } else {
87 MarkUsesAsLive(current_inst, all_components_live_, live_components,
88 &work_list);
89 }
90 break;
91 }
92 }
93}
94
95void VectorDCE::MarkExtractUseAsLive(const Instruction* current_inst,
96 const utils::BitVector& live_elements,
97 LiveComponentMap* live_components,
98 std::vector<WorkListItem>* work_list) {
99 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
100 uint32_t operand_id =
101 current_inst->GetSingleWordInOperand(kExtractCompositeIdInIdx);
102 Instruction* operand_inst = def_use_mgr->GetDef(operand_id);
103
104 if (HasVectorOrScalarResult(operand_inst)) {
105 WorkListItem new_item;
106 new_item.instruction = operand_inst;
107 if (current_inst->NumInOperands() < 2) {
108 new_item.components = live_elements;
109 } else {
110 new_item.components.Set(current_inst->GetSingleWordInOperand(1));
111 }
112 AddItemToWorkListIfNeeded(new_item, live_components, work_list);
113 }
114}
115
116void VectorDCE::MarkInsertUsesAsLive(
117 const VectorDCE::WorkListItem& current_item,
118 LiveComponentMap* live_components,
119 std::vector<VectorDCE::WorkListItem>* work_list) {
120 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
121
122 if (current_item.instruction->NumInOperands() > 2) {
123 uint32_t insert_position =
124 current_item.instruction->GetSingleWordInOperand(2);
125
126 // Add the elements of the composite object that are used.
127 uint32_t operand_id = current_item.instruction->GetSingleWordInOperand(
128 kInsertCompositeIdInIdx);
129 Instruction* operand_inst = def_use_mgr->GetDef(operand_id);
130
131 WorkListItem new_item;
132 new_item.instruction = operand_inst;
133 new_item.components = current_item.components;
134 new_item.components.Clear(insert_position);
135
136 AddItemToWorkListIfNeeded(new_item, live_components, work_list);
137
138 // Add the element being inserted if it is used.
139 if (current_item.components.Get(insert_position)) {
140 uint32_t obj_operand_id =
141 current_item.instruction->GetSingleWordInOperand(
142 kInsertObjectIdInIdx);
143 Instruction* obj_operand_inst = def_use_mgr->GetDef(obj_operand_id);
144 WorkListItem new_item_for_obj;
145 new_item_for_obj.instruction = obj_operand_inst;
146 new_item_for_obj.components.Set(0);
147 AddItemToWorkListIfNeeded(new_item_for_obj, live_components, work_list);
148 }
149 } else {
150 // If there are no indices, then this is a copy of the object being
151 // inserted.
152 uint32_t object_id =
153 current_item.instruction->GetSingleWordInOperand(kInsertObjectIdInIdx);
154 Instruction* object_inst = def_use_mgr->GetDef(object_id);
155
156 WorkListItem new_item;
157 new_item.instruction = object_inst;
158 new_item.components = current_item.components;
159 AddItemToWorkListIfNeeded(new_item, live_components, work_list);
160 }
161}
162
163void VectorDCE::MarkVectorShuffleUsesAsLive(
164 const WorkListItem& current_item,
165 VectorDCE::LiveComponentMap* live_components,
166 std::vector<WorkListItem>* work_list) {
167 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
168
169 WorkListItem first_operand;
170 first_operand.instruction =
171 def_use_mgr->GetDef(current_item.instruction->GetSingleWordInOperand(0));
172 WorkListItem second_operand;
173 second_operand.instruction =
174 def_use_mgr->GetDef(current_item.instruction->GetSingleWordInOperand(1));
175
176 analysis::TypeManager* type_mgr = context()->get_type_mgr();
177 analysis::Vector* first_type =
178 type_mgr->GetType(first_operand.instruction->type_id())->AsVector();
179 uint32_t size_of_first_operand = first_type->element_count();
180
181 for (uint32_t in_op = 2; in_op < current_item.instruction->NumInOperands();
182 ++in_op) {
183 uint32_t index = current_item.instruction->GetSingleWordInOperand(in_op);
184 if (current_item.components.Get(in_op - 2)) {
185 if (index < size_of_first_operand) {
186 first_operand.components.Set(index);
187 } else {
188 second_operand.components.Set(index - size_of_first_operand);
189 }
190 }
191 }
192
193 AddItemToWorkListIfNeeded(first_operand, live_components, work_list);
194 AddItemToWorkListIfNeeded(second_operand, live_components, work_list);
195}
196
197void VectorDCE::MarkCompositeContructUsesAsLive(
198 VectorDCE::WorkListItem work_item,
199 VectorDCE::LiveComponentMap* live_components,
200 std::vector<VectorDCE::WorkListItem>* work_list) {
201 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
202 analysis::TypeManager* type_mgr = context()->get_type_mgr();
203
204 uint32_t current_component = 0;
205 Instruction* current_inst = work_item.instruction;
206 uint32_t num_in_operands = current_inst->NumInOperands();
207 for (uint32_t i = 0; i < num_in_operands; ++i) {
208 uint32_t id = current_inst->GetSingleWordInOperand(i);
209 Instruction* op_inst = def_use_mgr->GetDef(id);
210
211 if (HasScalarResult(op_inst)) {
212 WorkListItem new_work_item;
213 new_work_item.instruction = op_inst;
214 if (work_item.components.Get(current_component)) {
215 new_work_item.components.Set(0);
216 }
217 AddItemToWorkListIfNeeded(new_work_item, live_components, work_list);
218 current_component++;
219 } else {
220 assert(HasVectorResult(op_inst));
221 WorkListItem new_work_item;
222 new_work_item.instruction = op_inst;
223 uint32_t op_vector_size =
224 type_mgr->GetType(op_inst->type_id())->AsVector()->element_count();
225
226 for (uint32_t op_vector_idx = 0; op_vector_idx < op_vector_size;
227 op_vector_idx++, current_component++) {
228 if (work_item.components.Get(current_component)) {
229 new_work_item.components.Set(op_vector_idx);
230 }
231 }
232 AddItemToWorkListIfNeeded(new_work_item, live_components, work_list);
233 }
234 }
235}
236
237void VectorDCE::MarkUsesAsLive(
238 Instruction* current_inst, const utils::BitVector& live_elements,
239 LiveComponentMap* live_components,
240 std::vector<VectorDCE::WorkListItem>* work_list) {
241 analysis::DefUseManager* def_use_mgr = context()->get_def_use_mgr();
242
243 current_inst->ForEachInId([&work_list, &live_elements, this, live_components,
244 def_use_mgr](uint32_t* operand_id) {
245 Instruction* operand_inst = def_use_mgr->GetDef(*operand_id);
246
247 if (HasVectorResult(operand_inst)) {
248 WorkListItem new_item;
249 new_item.instruction = operand_inst;
250 new_item.components = live_elements;
251 AddItemToWorkListIfNeeded(new_item, live_components, work_list);
252 } else if (HasScalarResult(operand_inst)) {
253 WorkListItem new_item;
254 new_item.instruction = operand_inst;
255 new_item.components.Set(0);
256 AddItemToWorkListIfNeeded(new_item, live_components, work_list);
257 }
258 });
259}
260
261bool VectorDCE::HasVectorOrScalarResult(const Instruction* inst) const {
262 return HasScalarResult(inst) || HasVectorResult(inst);
263}
264
265bool VectorDCE::HasVectorResult(const Instruction* inst) const {
266 analysis::TypeManager* type_mgr = context()->get_type_mgr();
267 if (inst->type_id() == 0) {
268 return false;
269 }
270
271 const analysis::Type* current_type = type_mgr->GetType(inst->type_id());
272 switch (current_type->kind()) {
273 case analysis::Type::kVector:
274 return true;
275 default:
276 return false;
277 }
278}
279
280bool VectorDCE::HasScalarResult(const Instruction* inst) const {
281 analysis::TypeManager* type_mgr = context()->get_type_mgr();
282 if (inst->type_id() == 0) {
283 return false;
284 }
285
286 const analysis::Type* current_type = type_mgr->GetType(inst->type_id());
287 switch (current_type->kind()) {
288 case analysis::Type::kBool:
289 case analysis::Type::kInteger:
290 case analysis::Type::kFloat:
291 return true;
292 default:
293 return false;
294 }
295}
296
297bool VectorDCE::RewriteInstructions(
298 Function* function, const VectorDCE::LiveComponentMap& live_components) {
299 bool modified = false;
300 function->ForEachInst(
301 [&modified, this, live_components](Instruction* current_inst) {
302 if (!context()->IsCombinatorInstruction(current_inst)) {
303 return;
304 }
305
306 auto live_component = live_components.find(current_inst->result_id());
307 if (live_component == live_components.end()) {
308 // If this instruction is not in live_components then it does not
309 // produce a vector, or it is never referenced and ADCE will remove
310 // it. No point in trying to differentiate.
311 return;
312 }
313
314 // If no element in the current instruction is used replace it with an
315 // OpUndef.
316 if (live_component->second.Empty()) {
317 modified = true;
318 uint32_t undef_id = this->Type2Undef(current_inst->type_id());
319 context()->KillNamesAndDecorates(current_inst);
320 context()->ReplaceAllUsesWith(current_inst->result_id(), undef_id);
321 context()->KillInst(current_inst);
322 return;
323 }
324
325 switch (current_inst->opcode()) {
326 case SpvOpCompositeInsert:
327 modified |=
328 RewriteInsertInstruction(current_inst, live_component->second);
329 break;
330 case SpvOpCompositeConstruct:
331 // TODO: The members that are not live can be replaced by an undef
332 // or constant. This will remove uses of those values, and possibly
333 // create opportunities for ADCE.
334 break;
335 default:
336 // Do nothing.
337 break;
338 }
339 });
340 return modified;
341}
342
343bool VectorDCE::RewriteInsertInstruction(
344 Instruction* current_inst, const utils::BitVector& live_components) {
345 // If the value being inserted is not live, then we can skip the insert.
346
347 if (current_inst->NumInOperands() == 2) {
348 // If there are no indices, then this is the same as a copy.
349 context()->KillNamesAndDecorates(current_inst->result_id());
350 uint32_t object_id =
351 current_inst->GetSingleWordInOperand(kInsertObjectIdInIdx);
352 context()->ReplaceAllUsesWith(current_inst->result_id(), object_id);
353 return true;
354 }
355
356 uint32_t insert_index = current_inst->GetSingleWordInOperand(2);
357 if (!live_components.Get(insert_index)) {
358 context()->KillNamesAndDecorates(current_inst->result_id());
359 uint32_t composite_id =
360 current_inst->GetSingleWordInOperand(kInsertCompositeIdInIdx);
361 context()->ReplaceAllUsesWith(current_inst->result_id(), composite_id);
362 return true;
363 }
364
365 // If the values already in the composite are not used, then replace it with
366 // an undef.
367 utils::BitVector temp = live_components;
368 temp.Clear(insert_index);
369 if (temp.Empty()) {
370 context()->ForgetUses(current_inst);
371 uint32_t undef_id = Type2Undef(current_inst->type_id());
372 current_inst->SetInOperand(kInsertCompositeIdInIdx, {undef_id});
373 context()->AnalyzeUses(current_inst);
374 return true;
375 }
376
377 return false;
378}
379
380void VectorDCE::AddItemToWorkListIfNeeded(
381 WorkListItem work_item, VectorDCE::LiveComponentMap* live_components,
382 std::vector<WorkListItem>* work_list) {
383 Instruction* current_inst = work_item.instruction;
384 auto it = live_components->find(current_inst->result_id());
385 if (it == live_components->end()) {
386 live_components->emplace(
387 std::make_pair(current_inst->result_id(), work_item.components));
388 work_list->emplace_back(work_item);
389 } else {
390 if (it->second.Or(work_item.components)) {
391 work_list->emplace_back(work_item);
392 }
393 }
394}
395
396} // namespace opt
397} // namespace spvtools
398