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
30namespace spvtools {
31namespace opt {
32
33Pass::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
42bool 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
66bool 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
92bool RemoveDuplicatesPass::RemoveDuplicateTypes() const {
93 bool modified = false;
94
95 if (context()->types_values().empty()) {
96 return modified;
97 }
98
99 analysis::TypeManager type_manager(context()->consumer(), context());
100
101 std::vector<Instruction*> visited_types;
102 std::vector<analysis::ForwardPointer> visited_forward_pointers;
103 std::vector<Instruction*> to_delete;
104 for (auto* i = &*context()->types_values_begin(); i; i = i->NextNode()) {
105 const bool is_i_forward_pointer = i->opcode() == SpvOpTypeForwardPointer;
106
107 // We only care about types.
108 if (!spvOpcodeGeneratesType(i->opcode()) && !is_i_forward_pointer) {
109 continue;
110 }
111
112 if (!is_i_forward_pointer) {
113 // Is the current type equal to one of the types we have already visited?
114 SpvId id_to_keep = 0u;
115 analysis::Type* i_type = type_manager.GetType(i->result_id());
116 assert(i_type);
117 // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the
118 // ResultIdTrie from unify_const_pass.cpp for this.
119 for (auto j : visited_types) {
120 analysis::Type* j_type = type_manager.GetType(j->result_id());
121 assert(j_type);
122 if (*i_type == *j_type) {
123 id_to_keep = j->result_id();
124 break;
125 }
126 }
127
128 if (id_to_keep == 0u) {
129 // This is a never seen before type, keep it around.
130 visited_types.emplace_back(i);
131 } else {
132 // The same type has already been seen before, remove this one.
133 context()->KillNamesAndDecorates(i->result_id());
134 context()->ReplaceAllUsesWith(i->result_id(), id_to_keep);
135 modified = true;
136 to_delete.emplace_back(i);
137 }
138 } else {
139 analysis::ForwardPointer i_type(
140 i->GetSingleWordInOperand(0u),
141 (SpvStorageClass)i->GetSingleWordInOperand(1u));
142 i_type.SetTargetPointer(
143 type_manager.GetType(i_type.target_id())->AsPointer());
144
145 // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the
146 // ResultIdTrie from unify_const_pass.cpp for this.
147 const bool found_a_match =
148 std::find(std::begin(visited_forward_pointers),
149 std::end(visited_forward_pointers),
150 i_type) != std::end(visited_forward_pointers);
151
152 if (!found_a_match) {
153 // This is a never seen before type, keep it around.
154 visited_forward_pointers.emplace_back(i_type);
155 } else {
156 // The same type has already been seen before, remove this one.
157 modified = true;
158 to_delete.emplace_back(i);
159 }
160 }
161 }
162
163 for (auto i : to_delete) {
164 context()->KillInst(i);
165 }
166
167 return modified;
168}
169
170// TODO(pierremoreau): Duplicate decoration groups should be removed. For
171// example, in
172// OpDecorate %1 Constant
173// %1 = OpDecorationGroup
174// OpDecorate %2 Constant
175// %2 = OpDecorationGroup
176// OpGroupDecorate %1 %3
177// OpGroupDecorate %2 %4
178// group %2 could be removed.
179bool RemoveDuplicatesPass::RemoveDuplicateDecorations() const {
180 bool modified = false;
181
182 std::vector<const Instruction*> visited_decorations;
183
184 analysis::DecorationManager decoration_manager(context()->module());
185 for (auto* i = &*context()->annotation_begin(); i;) {
186 // Is the current decoration equal to one of the decorations we have
187 // already visited?
188 bool already_visited = false;
189 // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the
190 // ResultIdTrie from unify_const_pass.cpp for this.
191 for (const Instruction* j : visited_decorations) {
192 if (decoration_manager.AreDecorationsTheSame(&*i, j, false)) {
193 already_visited = true;
194 break;
195 }
196 }
197
198 if (!already_visited) {
199 // This is a never seen before decoration, keep it around.
200 visited_decorations.emplace_back(&*i);
201 i = i->NextNode();
202 } else {
203 // The same decoration has already been seen before, remove this one.
204 modified = true;
205 i = context()->KillInst(i);
206 }
207 }
208
209 return modified;
210}
211
212} // namespace opt
213} // namespace spvtools
214