1 // Copyright (c) 2017 Pierre Moreau
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/decoration_manager.h"
16
17 #include <algorithm>
18 #include <memory>
19 #include <set>
20 #include <stack>
21 #include <utility>
22
23 #include "source/opt/ir_context.h"
24
25 namespace spvtools {
26 namespace opt {
27 namespace analysis {
28
RemoveDecorationsFrom(uint32_t id,std::function<bool (const Instruction &)> pred)29 void DecorationManager::RemoveDecorationsFrom(
30 uint32_t id, std::function<bool(const Instruction&)> pred) {
31 const auto ids_iter = id_to_decoration_insts_.find(id);
32 if (ids_iter == id_to_decoration_insts_.end()) {
33 return;
34 }
35
36 TargetData& decorations_info = ids_iter->second;
37 auto context = module_->context();
38 std::vector<Instruction*> insts_to_kill;
39 const bool is_group = !decorations_info.decorate_insts.empty();
40
41 // Schedule all direct decorations for removal if instructed as such by
42 // |pred|.
43 for (Instruction* inst : decorations_info.direct_decorations)
44 if (pred(*inst)) insts_to_kill.push_back(inst);
45
46 // For all groups being directly applied to |id|, remove |id| (and the
47 // literal if |inst| is an OpGroupMemberDecorate) from the instruction
48 // applying the group.
49 std::unordered_set<const Instruction*> indirect_decorations_to_remove;
50 for (Instruction* inst : decorations_info.indirect_decorations) {
51 assert(inst->opcode() == SpvOpGroupDecorate ||
52 inst->opcode() == SpvOpGroupMemberDecorate);
53
54 std::vector<Instruction*> group_decorations_to_keep;
55 const uint32_t group_id = inst->GetSingleWordInOperand(0u);
56 const auto group_iter = id_to_decoration_insts_.find(group_id);
57 assert(group_iter != id_to_decoration_insts_.end() &&
58 "Unknown decoration group");
59 const auto& group_decorations = group_iter->second.direct_decorations;
60 for (Instruction* decoration : group_decorations) {
61 if (!pred(*decoration)) group_decorations_to_keep.push_back(decoration);
62 }
63
64 // If all decorations should be kept, then we can keep |id| part of the
65 // group. However, if the group itself has no decorations, we should remove
66 // the id from the group. This is needed to make |KillNameAndDecorate| work
67 // correctly when a decoration group has no decorations.
68 if (group_decorations_to_keep.size() == group_decorations.size() &&
69 group_decorations.size() != 0) {
70 continue;
71 }
72
73 // Otherwise, remove |id| from the targets of |group_id|
74 const uint32_t stride = inst->opcode() == SpvOpGroupDecorate ? 1u : 2u;
75 bool was_modified = false;
76 for (uint32_t i = 1u; i < inst->NumInOperands();) {
77 if (inst->GetSingleWordInOperand(i) != id) {
78 i += stride;
79 continue;
80 }
81
82 const uint32_t last_operand_index = inst->NumInOperands() - stride;
83 if (i < last_operand_index)
84 inst->GetInOperand(i) = inst->GetInOperand(last_operand_index);
85 // Remove the associated literal, if it exists.
86 if (stride == 2u) {
87 if (i < last_operand_index)
88 inst->GetInOperand(i + 1u) =
89 inst->GetInOperand(last_operand_index + 1u);
90 inst->RemoveInOperand(last_operand_index + 1u);
91 }
92 inst->RemoveInOperand(last_operand_index);
93 was_modified = true;
94 }
95
96 // If the instruction has no targets left, remove the instruction
97 // altogether.
98 if (inst->NumInOperands() == 1u) {
99 indirect_decorations_to_remove.emplace(inst);
100 insts_to_kill.push_back(inst);
101 } else if (was_modified) {
102 context->ForgetUses(inst);
103 indirect_decorations_to_remove.emplace(inst);
104 context->AnalyzeUses(inst);
105 }
106
107 // If only some of the decorations should be kept, clone them and apply
108 // them directly to |id|.
109 if (!group_decorations_to_keep.empty()) {
110 for (Instruction* decoration : group_decorations_to_keep) {
111 // simply clone decoration and change |group_id| to |id|
112 std::unique_ptr<Instruction> new_inst(
113 decoration->Clone(module_->context()));
114 new_inst->SetInOperand(0, {id});
115 module_->AddAnnotationInst(std::move(new_inst));
116 auto decoration_iter = --module_->annotation_end();
117 context->AnalyzeUses(&*decoration_iter);
118 }
119 }
120 }
121
122 auto& indirect_decorations = decorations_info.indirect_decorations;
123 indirect_decorations.erase(
124 std::remove_if(
125 indirect_decorations.begin(), indirect_decorations.end(),
126 [&indirect_decorations_to_remove](const Instruction* inst) {
127 return indirect_decorations_to_remove.count(inst);
128 }),
129 indirect_decorations.end());
130
131 for (Instruction* inst : insts_to_kill) context->KillInst(inst);
132 insts_to_kill.clear();
133
134 // Schedule all instructions applying the group for removal if this group no
135 // longer applies decorations, either directly or indirectly.
136 if (is_group && decorations_info.direct_decorations.empty() &&
137 decorations_info.indirect_decorations.empty()) {
138 for (Instruction* inst : decorations_info.decorate_insts)
139 insts_to_kill.push_back(inst);
140 }
141 for (Instruction* inst : insts_to_kill) context->KillInst(inst);
142
143 if (decorations_info.direct_decorations.empty() &&
144 decorations_info.indirect_decorations.empty() &&
145 decorations_info.decorate_insts.empty()) {
146 id_to_decoration_insts_.erase(ids_iter);
147 }
148 }
149
GetDecorationsFor(uint32_t id,bool include_linkage)150 std::vector<Instruction*> DecorationManager::GetDecorationsFor(
151 uint32_t id, bool include_linkage) {
152 return InternalGetDecorationsFor<Instruction*>(id, include_linkage);
153 }
154
GetDecorationsFor(uint32_t id,bool include_linkage) const155 std::vector<const Instruction*> DecorationManager::GetDecorationsFor(
156 uint32_t id, bool include_linkage) const {
157 return const_cast<DecorationManager*>(this)
158 ->InternalGetDecorationsFor<const Instruction*>(id, include_linkage);
159 }
160
HaveTheSameDecorations(uint32_t id1,uint32_t id2) const161 bool DecorationManager::HaveTheSameDecorations(uint32_t id1,
162 uint32_t id2) const {
163 using InstructionList = std::vector<const Instruction*>;
164 using DecorationSet = std::set<std::u32string>;
165
166 const InstructionList decorations_for1 = GetDecorationsFor(id1, false);
167 const InstructionList decorations_for2 = GetDecorationsFor(id2, false);
168
169 // This function splits the decoration instructions into different sets,
170 // based on their opcode; only OpDecorate, OpDecorateId,
171 // OpDecorateStringGOOGLE, and OpMemberDecorate are considered, the other
172 // opcodes are ignored.
173 const auto fillDecorationSets =
174 [](const InstructionList& decoration_list, DecorationSet* decorate_set,
175 DecorationSet* decorate_id_set, DecorationSet* decorate_string_set,
176 DecorationSet* member_decorate_set) {
177 for (const Instruction* inst : decoration_list) {
178 std::u32string decoration_payload;
179 // Ignore the opcode and the target as we do not want them to be
180 // compared.
181 for (uint32_t i = 1u; i < inst->NumInOperands(); ++i) {
182 for (uint32_t word : inst->GetInOperand(i).words) {
183 decoration_payload.push_back(word);
184 }
185 }
186
187 switch (inst->opcode()) {
188 case SpvOpDecorate:
189 decorate_set->emplace(std::move(decoration_payload));
190 break;
191 case SpvOpMemberDecorate:
192 member_decorate_set->emplace(std::move(decoration_payload));
193 break;
194 case SpvOpDecorateId:
195 decorate_id_set->emplace(std::move(decoration_payload));
196 break;
197 case SpvOpDecorateStringGOOGLE:
198 decorate_string_set->emplace(std::move(decoration_payload));
199 break;
200 default:
201 break;
202 }
203 }
204 };
205
206 DecorationSet decorate_set_for1;
207 DecorationSet decorate_id_set_for1;
208 DecorationSet decorate_string_set_for1;
209 DecorationSet member_decorate_set_for1;
210 fillDecorationSets(decorations_for1, &decorate_set_for1,
211 &decorate_id_set_for1, &decorate_string_set_for1,
212 &member_decorate_set_for1);
213
214 DecorationSet decorate_set_for2;
215 DecorationSet decorate_id_set_for2;
216 DecorationSet decorate_string_set_for2;
217 DecorationSet member_decorate_set_for2;
218 fillDecorationSets(decorations_for2, &decorate_set_for2,
219 &decorate_id_set_for2, &decorate_string_set_for2,
220 &member_decorate_set_for2);
221
222 const bool result = decorate_set_for1 == decorate_set_for2 &&
223 decorate_id_set_for1 == decorate_id_set_for2 &&
224 member_decorate_set_for1 == member_decorate_set_for2 &&
225 // Compare string sets last in case the strings are long.
226 decorate_string_set_for1 == decorate_string_set_for2;
227 return result;
228 }
229
230 // TODO(pierremoreau): If OpDecorateId is referencing an OpConstant, one could
231 // check that the constants are the same rather than just
232 // looking at the constant ID.
AreDecorationsTheSame(const Instruction * inst1,const Instruction * inst2,bool ignore_target) const233 bool DecorationManager::AreDecorationsTheSame(const Instruction* inst1,
234 const Instruction* inst2,
235 bool ignore_target) const {
236 switch (inst1->opcode()) {
237 case SpvOpDecorate:
238 case SpvOpMemberDecorate:
239 case SpvOpDecorateId:
240 case SpvOpDecorateStringGOOGLE:
241 break;
242 default:
243 return false;
244 }
245
246 if (inst1->opcode() != inst2->opcode() ||
247 inst1->NumInOperands() != inst2->NumInOperands())
248 return false;
249
250 for (uint32_t i = ignore_target ? 1u : 0u; i < inst1->NumInOperands(); ++i)
251 if (inst1->GetInOperand(i) != inst2->GetInOperand(i)) return false;
252
253 return true;
254 }
255
AnalyzeDecorations()256 void DecorationManager::AnalyzeDecorations() {
257 if (!module_) return;
258
259 // For each group and instruction, collect all their decoration instructions.
260 for (Instruction& inst : module_->annotations()) {
261 AddDecoration(&inst);
262 }
263 }
264
AddDecoration(Instruction * inst)265 void DecorationManager::AddDecoration(Instruction* inst) {
266 switch (inst->opcode()) {
267 case SpvOpDecorate:
268 case SpvOpDecorateId:
269 case SpvOpDecorateStringGOOGLE:
270 case SpvOpMemberDecorate: {
271 const auto target_id = inst->GetSingleWordInOperand(0u);
272 id_to_decoration_insts_[target_id].direct_decorations.push_back(inst);
273 break;
274 }
275 case SpvOpGroupDecorate:
276 case SpvOpGroupMemberDecorate: {
277 const uint32_t start = inst->opcode() == SpvOpGroupDecorate ? 1u : 2u;
278 const uint32_t stride = start;
279 for (uint32_t i = start; i < inst->NumInOperands(); i += stride) {
280 const auto target_id = inst->GetSingleWordInOperand(i);
281 TargetData& target_data = id_to_decoration_insts_[target_id];
282 target_data.indirect_decorations.push_back(inst);
283 }
284 const auto target_id = inst->GetSingleWordInOperand(0u);
285 id_to_decoration_insts_[target_id].decorate_insts.push_back(inst);
286 break;
287 }
288 default:
289 break;
290 }
291 }
292
AddDecoration(SpvOp opcode,std::vector<Operand> opnds)293 void DecorationManager::AddDecoration(SpvOp opcode,
294 std::vector<Operand> opnds) {
295 IRContext* ctx = module_->context();
296 std::unique_ptr<Instruction> newDecoOp(
297 new Instruction(ctx, opcode, 0, 0, opnds));
298 ctx->AddAnnotationInst(std::move(newDecoOp));
299 }
300
AddDecoration(uint32_t inst_id,uint32_t decoration)301 void DecorationManager::AddDecoration(uint32_t inst_id, uint32_t decoration) {
302 AddDecoration(
303 SpvOpDecorate,
304 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {inst_id}},
305 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {decoration}}});
306 }
307
AddDecorationVal(uint32_t inst_id,uint32_t decoration,uint32_t decoration_value)308 void DecorationManager::AddDecorationVal(uint32_t inst_id, uint32_t decoration,
309 uint32_t decoration_value) {
310 AddDecoration(
311 SpvOpDecorate,
312 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {inst_id}},
313 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {decoration}},
314 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER,
315 {decoration_value}}});
316 }
317
AddMemberDecoration(uint32_t inst_id,uint32_t member,uint32_t decoration,uint32_t decoration_value)318 void DecorationManager::AddMemberDecoration(uint32_t inst_id, uint32_t member,
319 uint32_t decoration,
320 uint32_t decoration_value) {
321 AddDecoration(
322 SpvOpMemberDecorate,
323 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {inst_id}},
324 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {member}},
325 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {decoration}},
326 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER,
327 {decoration_value}}});
328 }
329
330 template <typename T>
InternalGetDecorationsFor(uint32_t id,bool include_linkage)331 std::vector<T> DecorationManager::InternalGetDecorationsFor(
332 uint32_t id, bool include_linkage) {
333 std::vector<T> decorations;
334
335 const auto ids_iter = id_to_decoration_insts_.find(id);
336 // |id| has no decorations
337 if (ids_iter == id_to_decoration_insts_.end()) return decorations;
338
339 const TargetData& target_data = ids_iter->second;
340
341 const auto process_direct_decorations =
342 [include_linkage,
343 &decorations](const std::vector<Instruction*>& direct_decorations) {
344 for (Instruction* inst : direct_decorations) {
345 const bool is_linkage = inst->opcode() == SpvOpDecorate &&
346 inst->GetSingleWordInOperand(1u) ==
347 SpvDecorationLinkageAttributes;
348 if (include_linkage || !is_linkage) decorations.push_back(inst);
349 }
350 };
351
352 // Process |id|'s decorations.
353 process_direct_decorations(ids_iter->second.direct_decorations);
354
355 // Process the decorations of all groups applied to |id|.
356 for (const Instruction* inst : target_data.indirect_decorations) {
357 const uint32_t group_id = inst->GetSingleWordInOperand(0u);
358 const auto group_iter = id_to_decoration_insts_.find(group_id);
359 assert(group_iter != id_to_decoration_insts_.end() && "Unknown group ID");
360 process_direct_decorations(group_iter->second.direct_decorations);
361 }
362
363 return decorations;
364 }
365
WhileEachDecoration(uint32_t id,uint32_t decoration,std::function<bool (const Instruction &)> f)366 bool DecorationManager::WhileEachDecoration(
367 uint32_t id, uint32_t decoration,
368 std::function<bool(const Instruction&)> f) {
369 for (const Instruction* inst : GetDecorationsFor(id, true)) {
370 switch (inst->opcode()) {
371 case SpvOpMemberDecorate:
372 if (inst->GetSingleWordInOperand(2) == decoration) {
373 if (!f(*inst)) return false;
374 }
375 break;
376 case SpvOpDecorate:
377 case SpvOpDecorateId:
378 case SpvOpDecorateStringGOOGLE:
379 if (inst->GetSingleWordInOperand(1) == decoration) {
380 if (!f(*inst)) return false;
381 }
382 break;
383 default:
384 assert(false && "Unexpected decoration instruction");
385 }
386 }
387 return true;
388 }
389
ForEachDecoration(uint32_t id,uint32_t decoration,std::function<void (const Instruction &)> f)390 void DecorationManager::ForEachDecoration(
391 uint32_t id, uint32_t decoration,
392 std::function<void(const Instruction&)> f) {
393 WhileEachDecoration(id, decoration, [&f](const Instruction& inst) {
394 f(inst);
395 return true;
396 });
397 }
398
CloneDecorations(uint32_t from,uint32_t to)399 void DecorationManager::CloneDecorations(uint32_t from, uint32_t to) {
400 const auto decoration_list = id_to_decoration_insts_.find(from);
401 if (decoration_list == id_to_decoration_insts_.end()) return;
402 auto context = module_->context();
403 for (Instruction* inst : decoration_list->second.direct_decorations) {
404 // simply clone decoration and change |target-id| to |to|
405 std::unique_ptr<Instruction> new_inst(inst->Clone(module_->context()));
406 new_inst->SetInOperand(0, {to});
407 module_->AddAnnotationInst(std::move(new_inst));
408 auto decoration_iter = --module_->annotation_end();
409 context->AnalyzeUses(&*decoration_iter);
410 }
411 // We need to copy the list of instructions as ForgetUses and AnalyzeUses are
412 // going to modify it.
413 std::vector<Instruction*> indirect_decorations =
414 decoration_list->second.indirect_decorations;
415 for (Instruction* inst : indirect_decorations) {
416 switch (inst->opcode()) {
417 case SpvOpGroupDecorate:
418 context->ForgetUses(inst);
419 // add |to| to list of decorated id's
420 inst->AddOperand(
421 Operand(spv_operand_type_t::SPV_OPERAND_TYPE_ID, {to}));
422 context->AnalyzeUses(inst);
423 break;
424 case SpvOpGroupMemberDecorate: {
425 context->ForgetUses(inst);
426 // for each (id == from), add (to, literal) as operands
427 const uint32_t num_operands = inst->NumOperands();
428 for (uint32_t i = 1; i < num_operands; i += 2) {
429 Operand op = inst->GetOperand(i);
430 if (op.words[0] == from) { // add new pair of operands: (to, literal)
431 inst->AddOperand(
432 Operand(spv_operand_type_t::SPV_OPERAND_TYPE_ID, {to}));
433 op = inst->GetOperand(i + 1);
434 inst->AddOperand(std::move(op));
435 }
436 }
437 context->AnalyzeUses(inst);
438 break;
439 }
440 default:
441 assert(false && "Unexpected decoration instruction");
442 }
443 }
444 }
445
CloneDecorations(uint32_t from,uint32_t to,const std::vector<SpvDecoration> & decorations_to_copy)446 void DecorationManager::CloneDecorations(
447 uint32_t from, uint32_t to,
448 const std::vector<SpvDecoration>& decorations_to_copy) {
449 const auto decoration_list = id_to_decoration_insts_.find(from);
450 if (decoration_list == id_to_decoration_insts_.end()) return;
451 auto context = module_->context();
452 for (Instruction* inst : decoration_list->second.direct_decorations) {
453 if (std::find(decorations_to_copy.begin(), decorations_to_copy.end(),
454 inst->GetSingleWordInOperand(1)) ==
455 decorations_to_copy.end()) {
456 continue;
457 }
458
459 // Clone decoration and change |target-id| to |to|.
460 std::unique_ptr<Instruction> new_inst(inst->Clone(module_->context()));
461 new_inst->SetInOperand(0, {to});
462 module_->AddAnnotationInst(std::move(new_inst));
463 auto decoration_iter = --module_->annotation_end();
464 context->AnalyzeUses(&*decoration_iter);
465 }
466
467 // We need to copy the list of instructions as ForgetUses and AnalyzeUses are
468 // going to modify it.
469 std::vector<Instruction*> indirect_decorations =
470 decoration_list->second.indirect_decorations;
471 for (Instruction* inst : indirect_decorations) {
472 switch (inst->opcode()) {
473 case SpvOpGroupDecorate:
474 CloneDecorations(inst->GetSingleWordInOperand(0), to,
475 decorations_to_copy);
476 break;
477 case SpvOpGroupMemberDecorate: {
478 assert(false && "The source id is not suppose to be a type.");
479 break;
480 }
481 default:
482 assert(false && "Unexpected decoration instruction");
483 }
484 }
485 }
486
RemoveDecoration(Instruction * inst)487 void DecorationManager::RemoveDecoration(Instruction* inst) {
488 const auto remove_from_container = [inst](std::vector<Instruction*>& v) {
489 v.erase(std::remove(v.begin(), v.end(), inst), v.end());
490 };
491
492 switch (inst->opcode()) {
493 case SpvOpDecorate:
494 case SpvOpDecorateId:
495 case SpvOpDecorateStringGOOGLE:
496 case SpvOpMemberDecorate: {
497 const auto target_id = inst->GetSingleWordInOperand(0u);
498 auto const iter = id_to_decoration_insts_.find(target_id);
499 if (iter == id_to_decoration_insts_.end()) return;
500 remove_from_container(iter->second.direct_decorations);
501 } break;
502 case SpvOpGroupDecorate:
503 case SpvOpGroupMemberDecorate: {
504 const uint32_t stride = inst->opcode() == SpvOpGroupDecorate ? 1u : 2u;
505 for (uint32_t i = 1u; i < inst->NumInOperands(); i += stride) {
506 const auto target_id = inst->GetSingleWordInOperand(i);
507 auto const iter = id_to_decoration_insts_.find(target_id);
508 if (iter == id_to_decoration_insts_.end()) continue;
509 remove_from_container(iter->second.indirect_decorations);
510 }
511 const auto group_id = inst->GetSingleWordInOperand(0u);
512 auto const iter = id_to_decoration_insts_.find(group_id);
513 if (iter == id_to_decoration_insts_.end()) return;
514 remove_from_container(iter->second.decorate_insts);
515 } break;
516 default:
517 break;
518 }
519 }
520
operator ==(const DecorationManager & lhs,const DecorationManager & rhs)521 bool operator==(const DecorationManager& lhs, const DecorationManager& rhs) {
522 return lhs.id_to_decoration_insts_ == rhs.id_to_decoration_insts_;
523 }
524
525 } // namespace analysis
526 } // namespace opt
527 } // namespace spvtools
528