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/remove_duplicates_pass.h"
16
17 #include <algorithm>
18 #include <cstring>
19 #include <limits>
20 #include <string>
21 #include <unordered_map>
22 #include <unordered_set>
23 #include <vector>
24
25 #include "source/opcode.h"
26 #include "source/opt/decoration_manager.h"
27 #include "source/opt/ir_context.h"
28 #include "source/opt/reflect.h"
29
30 namespace spvtools {
31 namespace opt {
32
Process()33 Pass::Status RemoveDuplicatesPass::Process() {
34 bool modified = RemoveDuplicateCapabilities();
35 modified |= RemoveDuplicatesExtInstImports();
36 modified |= RemoveDuplicateTypes();
37 modified |= RemoveDuplicateDecorations();
38
39 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
40 }
41
RemoveDuplicateCapabilities() const42 bool RemoveDuplicatesPass::RemoveDuplicateCapabilities() const {
43 bool modified = false;
44
45 if (context()->capabilities().empty()) {
46 return modified;
47 }
48
49 std::unordered_set<uint32_t> capabilities;
50 for (auto* i = &*context()->capability_begin(); i;) {
51 auto res = capabilities.insert(i->GetSingleWordOperand(0u));
52
53 if (res.second) {
54 // Never seen before, keep it.
55 i = i->NextNode();
56 } else {
57 // It's a duplicate, remove it.
58 i = context()->KillInst(i);
59 modified = true;
60 }
61 }
62
63 return modified;
64 }
65
RemoveDuplicatesExtInstImports() const66 bool RemoveDuplicatesPass::RemoveDuplicatesExtInstImports() const {
67 bool modified = false;
68
69 if (context()->ext_inst_imports().empty()) {
70 return modified;
71 }
72
73 std::unordered_map<std::string, SpvId> ext_inst_imports;
74 for (auto* i = &*context()->ext_inst_import_begin(); i;) {
75 auto res = ext_inst_imports.emplace(
76 reinterpret_cast<const char*>(i->GetInOperand(0u).words.data()),
77 i->result_id());
78 if (res.second) {
79 // Never seen before, keep it.
80 i = i->NextNode();
81 } else {
82 // It's a duplicate, remove it.
83 context()->ReplaceAllUsesWith(i->result_id(), res.first->second);
84 i = context()->KillInst(i);
85 modified = true;
86 }
87 }
88
89 return modified;
90 }
91
RemoveDuplicateTypes() const92 bool RemoveDuplicatesPass::RemoveDuplicateTypes() const {
93 bool modified = false;
94
95 if (context()->types_values().empty()) {
96 return modified;
97 }
98
99 std::vector<Instruction*> visited_types;
100 std::vector<Instruction*> to_delete;
101 for (auto* i = &*context()->types_values_begin(); i; i = i->NextNode()) {
102 // We only care about types.
103 if (!spvOpcodeGeneratesType((i->opcode())) &&
104 i->opcode() != SpvOpTypeForwardPointer) {
105 continue;
106 }
107
108 // Is the current type equal to one of the types we have aready visited?
109 SpvId id_to_keep = 0u;
110 // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the
111 // ResultIdTrie from unify_const_pass.cpp for this.
112 for (auto j : visited_types) {
113 if (AreTypesEqual(*i, *j, context())) {
114 id_to_keep = j->result_id();
115 break;
116 }
117 }
118
119 if (id_to_keep == 0u) {
120 // This is a never seen before type, keep it around.
121 visited_types.emplace_back(i);
122 } else {
123 // The same type has already been seen before, remove this one.
124 context()->KillNamesAndDecorates(i->result_id());
125 context()->ReplaceAllUsesWith(i->result_id(), id_to_keep);
126 modified = true;
127 to_delete.emplace_back(i);
128 }
129 }
130
131 for (auto i : to_delete) {
132 context()->KillInst(i);
133 }
134
135 return modified;
136 }
137
138 // TODO(pierremoreau): Duplicate decoration groups should be removed. For
139 // example, in
140 // OpDecorate %1 Constant
141 // %1 = OpDecorationGroup
142 // OpDecorate %2 Constant
143 // %2 = OpDecorationGroup
144 // OpGroupDecorate %1 %3
145 // OpGroupDecorate %2 %4
146 // group %2 could be removed.
RemoveDuplicateDecorations() const147 bool RemoveDuplicatesPass::RemoveDuplicateDecorations() const {
148 bool modified = false;
149
150 std::vector<const Instruction*> visited_decorations;
151
152 analysis::DecorationManager decoration_manager(context()->module());
153 for (auto* i = &*context()->annotation_begin(); i;) {
154 // Is the current decoration equal to one of the decorations we have aready
155 // visited?
156 bool already_visited = false;
157 // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the
158 // ResultIdTrie from unify_const_pass.cpp for this.
159 for (const Instruction* j : visited_decorations) {
160 if (decoration_manager.AreDecorationsTheSame(&*i, j, false)) {
161 already_visited = true;
162 break;
163 }
164 }
165
166 if (!already_visited) {
167 // This is a never seen before decoration, keep it around.
168 visited_decorations.emplace_back(&*i);
169 i = i->NextNode();
170 } else {
171 // The same decoration has already been seen before, remove this one.
172 modified = true;
173 i = context()->KillInst(i);
174 }
175 }
176
177 return modified;
178 }
179
AreTypesEqual(const Instruction & inst1,const Instruction & inst2,IRContext * context)180 bool RemoveDuplicatesPass::AreTypesEqual(const Instruction& inst1,
181 const Instruction& inst2,
182 IRContext* context) {
183 if (inst1.opcode() != inst2.opcode()) return false;
184 if (!IsTypeInst(inst1.opcode())) return false;
185
186 const analysis::Type* type1 =
187 context->get_type_mgr()->GetType(inst1.result_id());
188 const analysis::Type* type2 =
189 context->get_type_mgr()->GetType(inst2.result_id());
190 if (type1 && type2 && *type1 == *type2) return true;
191
192 return false;
193 }
194
195 } // namespace opt
196 } // namespace spvtools
197