1 // Copyright (c) 2016 Google Inc.
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/def_use_manager.h"
16
17 #include <iostream>
18
19 #include "source/opt/log.h"
20 #include "source/opt/reflect.h"
21
22 namespace spvtools {
23 namespace opt {
24 namespace analysis {
25
AnalyzeInstDef(Instruction * inst)26 void DefUseManager::AnalyzeInstDef(Instruction* inst) {
27 const uint32_t def_id = inst->result_id();
28 if (def_id != 0) {
29 auto iter = id_to_def_.find(def_id);
30 if (iter != id_to_def_.end()) {
31 // Clear the original instruction that defining the same result id of the
32 // new instruction.
33 ClearInst(iter->second);
34 }
35 id_to_def_[def_id] = inst;
36 } else {
37 ClearInst(inst);
38 }
39 }
40
AnalyzeInstUse(Instruction * inst)41 void DefUseManager::AnalyzeInstUse(Instruction* inst) {
42 // Create entry for the given instruction. Note that the instruction may
43 // not have any in-operands. In such cases, we still need a entry for those
44 // instructions so this manager knows it has seen the instruction later.
45 auto* used_ids = &inst_to_used_ids_[inst];
46 if (used_ids->size()) {
47 EraseUseRecordsOfOperandIds(inst);
48 used_ids = &inst_to_used_ids_[inst];
49 }
50 used_ids->clear(); // It might have existed before.
51
52 for (uint32_t i = 0; i < inst->NumOperands(); ++i) {
53 switch (inst->GetOperand(i).type) {
54 // For any id type but result id type
55 case SPV_OPERAND_TYPE_ID:
56 case SPV_OPERAND_TYPE_TYPE_ID:
57 case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
58 case SPV_OPERAND_TYPE_SCOPE_ID: {
59 uint32_t use_id = inst->GetSingleWordOperand(i);
60 Instruction* def = GetDef(use_id);
61 if (!def) assert(false && "Definition is not registered.");
62 id_to_users_.insert(UserEntry(def, inst));
63 used_ids->push_back(use_id);
64 } break;
65 default:
66 break;
67 }
68 }
69 }
70
AnalyzeInstDefUse(Instruction * inst)71 void DefUseManager::AnalyzeInstDefUse(Instruction* inst) {
72 AnalyzeInstDef(inst);
73 AnalyzeInstUse(inst);
74 // Analyze lines last otherwise they will be cleared when inst is
75 // cleared by preceding two calls
76 for (auto& l_inst : inst->dbg_line_insts()) AnalyzeInstDefUse(&l_inst);
77 }
78
UpdateDefUse(Instruction * inst)79 void DefUseManager::UpdateDefUse(Instruction* inst) {
80 const uint32_t def_id = inst->result_id();
81 if (def_id != 0) {
82 auto iter = id_to_def_.find(def_id);
83 if (iter == id_to_def_.end()) {
84 AnalyzeInstDef(inst);
85 }
86 }
87 AnalyzeInstUse(inst);
88 }
89
GetDef(uint32_t id)90 Instruction* DefUseManager::GetDef(uint32_t id) {
91 auto iter = id_to_def_.find(id);
92 if (iter == id_to_def_.end()) return nullptr;
93 return iter->second;
94 }
95
GetDef(uint32_t id) const96 const Instruction* DefUseManager::GetDef(uint32_t id) const {
97 const auto iter = id_to_def_.find(id);
98 if (iter == id_to_def_.end()) return nullptr;
99 return iter->second;
100 }
101
UsersBegin(const Instruction * def) const102 DefUseManager::IdToUsersMap::const_iterator DefUseManager::UsersBegin(
103 const Instruction* def) const {
104 return id_to_users_.lower_bound(
105 UserEntry(const_cast<Instruction*>(def), nullptr));
106 }
107
UsersNotEnd(const IdToUsersMap::const_iterator & iter,const IdToUsersMap::const_iterator & cached_end,const Instruction * inst) const108 bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
109 const IdToUsersMap::const_iterator& cached_end,
110 const Instruction* inst) const {
111 return (iter != cached_end && iter->first == inst);
112 }
113
UsersNotEnd(const IdToUsersMap::const_iterator & iter,const Instruction * inst) const114 bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
115 const Instruction* inst) const {
116 return UsersNotEnd(iter, id_to_users_.end(), inst);
117 }
118
WhileEachUser(const Instruction * def,const std::function<bool (Instruction *)> & f) const119 bool DefUseManager::WhileEachUser(
120 const Instruction* def, const std::function<bool(Instruction*)>& f) const {
121 // Ensure that |def| has been registered.
122 assert(def && (!def->HasResultId() || def == GetDef(def->result_id())) &&
123 "Definition is not registered.");
124 if (!def->HasResultId()) return true;
125
126 auto end = id_to_users_.end();
127 for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
128 if (!f(iter->second)) return false;
129 }
130 return true;
131 }
132
WhileEachUser(uint32_t id,const std::function<bool (Instruction *)> & f) const133 bool DefUseManager::WhileEachUser(
134 uint32_t id, const std::function<bool(Instruction*)>& f) const {
135 return WhileEachUser(GetDef(id), f);
136 }
137
ForEachUser(const Instruction * def,const std::function<void (Instruction *)> & f) const138 void DefUseManager::ForEachUser(
139 const Instruction* def, const std::function<void(Instruction*)>& f) const {
140 WhileEachUser(def, [&f](Instruction* user) {
141 f(user);
142 return true;
143 });
144 }
145
ForEachUser(uint32_t id,const std::function<void (Instruction *)> & f) const146 void DefUseManager::ForEachUser(
147 uint32_t id, const std::function<void(Instruction*)>& f) const {
148 ForEachUser(GetDef(id), f);
149 }
150
WhileEachUse(const Instruction * def,const std::function<bool (Instruction *,uint32_t)> & f) const151 bool DefUseManager::WhileEachUse(
152 const Instruction* def,
153 const std::function<bool(Instruction*, uint32_t)>& f) const {
154 // Ensure that |def| has been registered.
155 assert(def && (!def->HasResultId() || def == GetDef(def->result_id())) &&
156 "Definition is not registered.");
157 if (!def->HasResultId()) return true;
158
159 auto end = id_to_users_.end();
160 for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
161 Instruction* user = iter->second;
162 for (uint32_t idx = 0; idx != user->NumOperands(); ++idx) {
163 const Operand& op = user->GetOperand(idx);
164 if (op.type != SPV_OPERAND_TYPE_RESULT_ID && spvIsIdType(op.type)) {
165 if (def->result_id() == op.words[0]) {
166 if (!f(user, idx)) return false;
167 }
168 }
169 }
170 }
171 return true;
172 }
173
WhileEachUse(uint32_t id,const std::function<bool (Instruction *,uint32_t)> & f) const174 bool DefUseManager::WhileEachUse(
175 uint32_t id, const std::function<bool(Instruction*, uint32_t)>& f) const {
176 return WhileEachUse(GetDef(id), f);
177 }
178
ForEachUse(const Instruction * def,const std::function<void (Instruction *,uint32_t)> & f) const179 void DefUseManager::ForEachUse(
180 const Instruction* def,
181 const std::function<void(Instruction*, uint32_t)>& f) const {
182 WhileEachUse(def, [&f](Instruction* user, uint32_t index) {
183 f(user, index);
184 return true;
185 });
186 }
187
ForEachUse(uint32_t id,const std::function<void (Instruction *,uint32_t)> & f) const188 void DefUseManager::ForEachUse(
189 uint32_t id, const std::function<void(Instruction*, uint32_t)>& f) const {
190 ForEachUse(GetDef(id), f);
191 }
192
NumUsers(const Instruction * def) const193 uint32_t DefUseManager::NumUsers(const Instruction* def) const {
194 uint32_t count = 0;
195 ForEachUser(def, [&count](Instruction*) { ++count; });
196 return count;
197 }
198
NumUsers(uint32_t id) const199 uint32_t DefUseManager::NumUsers(uint32_t id) const {
200 return NumUsers(GetDef(id));
201 }
202
NumUses(const Instruction * def) const203 uint32_t DefUseManager::NumUses(const Instruction* def) const {
204 uint32_t count = 0;
205 ForEachUse(def, [&count](Instruction*, uint32_t) { ++count; });
206 return count;
207 }
208
NumUses(uint32_t id) const209 uint32_t DefUseManager::NumUses(uint32_t id) const {
210 return NumUses(GetDef(id));
211 }
212
GetAnnotations(uint32_t id) const213 std::vector<Instruction*> DefUseManager::GetAnnotations(uint32_t id) const {
214 std::vector<Instruction*> annos;
215 const Instruction* def = GetDef(id);
216 if (!def) return annos;
217
218 ForEachUser(def, [&annos](Instruction* user) {
219 if (IsAnnotationInst(user->opcode())) {
220 annos.push_back(user);
221 }
222 });
223 return annos;
224 }
225
AnalyzeDefUse(Module * module)226 void DefUseManager::AnalyzeDefUse(Module* module) {
227 if (!module) return;
228 // Analyze all the defs before any uses to catch forward references.
229 module->ForEachInst(
230 std::bind(&DefUseManager::AnalyzeInstDef, this, std::placeholders::_1),
231 true);
232 module->ForEachInst(
233 std::bind(&DefUseManager::AnalyzeInstUse, this, std::placeholders::_1),
234 true);
235 }
236
ClearInst(Instruction * inst)237 void DefUseManager::ClearInst(Instruction* inst) {
238 auto iter = inst_to_used_ids_.find(inst);
239 if (iter != inst_to_used_ids_.end()) {
240 EraseUseRecordsOfOperandIds(inst);
241 if (inst->result_id() != 0) {
242 // Remove all uses of this inst.
243 auto users_begin = UsersBegin(inst);
244 auto end = id_to_users_.end();
245 auto new_end = users_begin;
246 for (; UsersNotEnd(new_end, end, inst); ++new_end) {
247 }
248 id_to_users_.erase(users_begin, new_end);
249 id_to_def_.erase(inst->result_id());
250 }
251 }
252 }
253
EraseUseRecordsOfOperandIds(const Instruction * inst)254 void DefUseManager::EraseUseRecordsOfOperandIds(const Instruction* inst) {
255 // Go through all ids used by this instruction, remove this instruction's
256 // uses of them.
257 auto iter = inst_to_used_ids_.find(inst);
258 if (iter != inst_to_used_ids_.end()) {
259 for (auto use_id : iter->second) {
260 id_to_users_.erase(
261 UserEntry(GetDef(use_id), const_cast<Instruction*>(inst)));
262 }
263 inst_to_used_ids_.erase(inst);
264 }
265 }
266
operator ==(const DefUseManager & lhs,const DefUseManager & rhs)267 bool operator==(const DefUseManager& lhs, const DefUseManager& rhs) {
268 if (lhs.id_to_def_ != rhs.id_to_def_) {
269 for (auto p : lhs.id_to_def_) {
270 if (rhs.id_to_def_.find(p.first) == rhs.id_to_def_.end()) {
271 return false;
272 }
273 }
274 for (auto p : rhs.id_to_def_) {
275 if (lhs.id_to_def_.find(p.first) == lhs.id_to_def_.end()) {
276 return false;
277 }
278 }
279 return false;
280 }
281
282 if (lhs.id_to_users_ != rhs.id_to_users_) {
283 for (auto p : lhs.id_to_users_) {
284 if (rhs.id_to_users_.count(p) == 0) {
285 return false;
286 }
287 }
288 for (auto p : rhs.id_to_users_) {
289 if (lhs.id_to_users_.count(p) == 0) {
290 return false;
291 }
292 }
293 return false;
294 }
295
296 if (lhs.inst_to_used_ids_ != rhs.inst_to_used_ids_) {
297 for (auto p : lhs.inst_to_used_ids_) {
298 if (rhs.inst_to_used_ids_.count(p.first) == 0) {
299 return false;
300 }
301 }
302 for (auto p : rhs.inst_to_used_ids_) {
303 if (lhs.inst_to_used_ids_.count(p.first) == 0) {
304 return false;
305 }
306 }
307 return false;
308 }
309 return true;
310 }
311
312 } // namespace analysis
313 } // namespace opt
314 } // namespace spvtools
315