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
22namespace spvtools {
23namespace opt {
24namespace analysis {
25
26void 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
41void 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 assert(def && "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
71void DefUseManager::AnalyzeInstDefUse(Instruction* inst) {
72 AnalyzeInstDef(inst);
73 AnalyzeInstUse(inst);
74}
75
76void DefUseManager::UpdateDefUse(Instruction* inst) {
77 const uint32_t def_id = inst->result_id();
78 if (def_id != 0) {
79 auto iter = id_to_def_.find(def_id);
80 if (iter == id_to_def_.end()) {
81 AnalyzeInstDef(inst);
82 }
83 }
84 AnalyzeInstUse(inst);
85}
86
87Instruction* DefUseManager::GetDef(uint32_t id) {
88 auto iter = id_to_def_.find(id);
89 if (iter == id_to_def_.end()) return nullptr;
90 return iter->second;
91}
92
93const Instruction* DefUseManager::GetDef(uint32_t id) const {
94 const auto iter = id_to_def_.find(id);
95 if (iter == id_to_def_.end()) return nullptr;
96 return iter->second;
97}
98
99DefUseManager::IdToUsersMap::const_iterator DefUseManager::UsersBegin(
100 const Instruction* def) const {
101 return id_to_users_.lower_bound(
102 UserEntry(const_cast<Instruction*>(def), nullptr));
103}
104
105bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
106 const IdToUsersMap::const_iterator& cached_end,
107 const Instruction* inst) const {
108 return (iter != cached_end && iter->first == inst);
109}
110
111bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter,
112 const Instruction* inst) const {
113 return UsersNotEnd(iter, id_to_users_.end(), inst);
114}
115
116bool DefUseManager::WhileEachUser(
117 const Instruction* def, const std::function<bool(Instruction*)>& f) const {
118 // Ensure that |def| has been registered.
119 assert(def && (!def->HasResultId() || def == GetDef(def->result_id())) &&
120 "Definition is not registered.");
121 if (!def->HasResultId()) return true;
122
123 auto end = id_to_users_.end();
124 for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
125 if (!f(iter->second)) return false;
126 }
127 return true;
128}
129
130bool DefUseManager::WhileEachUser(
131 uint32_t id, const std::function<bool(Instruction*)>& f) const {
132 return WhileEachUser(GetDef(id), f);
133}
134
135void DefUseManager::ForEachUser(
136 const Instruction* def, const std::function<void(Instruction*)>& f) const {
137 WhileEachUser(def, [&f](Instruction* user) {
138 f(user);
139 return true;
140 });
141}
142
143void DefUseManager::ForEachUser(
144 uint32_t id, const std::function<void(Instruction*)>& f) const {
145 ForEachUser(GetDef(id), f);
146}
147
148bool DefUseManager::WhileEachUse(
149 const Instruction* def,
150 const std::function<bool(Instruction*, uint32_t)>& f) const {
151 // Ensure that |def| has been registered.
152 assert(def && (!def->HasResultId() || def == GetDef(def->result_id())) &&
153 "Definition is not registered.");
154 if (!def->HasResultId()) return true;
155
156 auto end = id_to_users_.end();
157 for (auto iter = UsersBegin(def); UsersNotEnd(iter, end, def); ++iter) {
158 Instruction* user = iter->second;
159 for (uint32_t idx = 0; idx != user->NumOperands(); ++idx) {
160 const Operand& op = user->GetOperand(idx);
161 if (op.type != SPV_OPERAND_TYPE_RESULT_ID && spvIsIdType(op.type)) {
162 if (def->result_id() == op.words[0]) {
163 if (!f(user, idx)) return false;
164 }
165 }
166 }
167 }
168 return true;
169}
170
171bool DefUseManager::WhileEachUse(
172 uint32_t id, const std::function<bool(Instruction*, uint32_t)>& f) const {
173 return WhileEachUse(GetDef(id), f);
174}
175
176void DefUseManager::ForEachUse(
177 const Instruction* def,
178 const std::function<void(Instruction*, uint32_t)>& f) const {
179 WhileEachUse(def, [&f](Instruction* user, uint32_t index) {
180 f(user, index);
181 return true;
182 });
183}
184
185void DefUseManager::ForEachUse(
186 uint32_t id, const std::function<void(Instruction*, uint32_t)>& f) const {
187 ForEachUse(GetDef(id), f);
188}
189
190uint32_t DefUseManager::NumUsers(const Instruction* def) const {
191 uint32_t count = 0;
192 ForEachUser(def, [&count](Instruction*) { ++count; });
193 return count;
194}
195
196uint32_t DefUseManager::NumUsers(uint32_t id) const {
197 return NumUsers(GetDef(id));
198}
199
200uint32_t DefUseManager::NumUses(const Instruction* def) const {
201 uint32_t count = 0;
202 ForEachUse(def, [&count](Instruction*, uint32_t) { ++count; });
203 return count;
204}
205
206uint32_t DefUseManager::NumUses(uint32_t id) const {
207 return NumUses(GetDef(id));
208}
209
210std::vector<Instruction*> DefUseManager::GetAnnotations(uint32_t id) const {
211 std::vector<Instruction*> annos;
212 const Instruction* def = GetDef(id);
213 if (!def) return annos;
214
215 ForEachUser(def, [&annos](Instruction* user) {
216 if (IsAnnotationInst(user->opcode())) {
217 annos.push_back(user);
218 }
219 });
220 return annos;
221}
222
223void DefUseManager::AnalyzeDefUse(Module* module) {
224 if (!module) return;
225 // Analyze all the defs before any uses to catch forward references.
226 module->ForEachInst(
227 std::bind(&DefUseManager::AnalyzeInstDef, this, std::placeholders::_1));
228 module->ForEachInst(
229 std::bind(&DefUseManager::AnalyzeInstUse, this, std::placeholders::_1));
230}
231
232void DefUseManager::ClearInst(Instruction* inst) {
233 auto iter = inst_to_used_ids_.find(inst);
234 if (iter != inst_to_used_ids_.end()) {
235 EraseUseRecordsOfOperandIds(inst);
236 if (inst->result_id() != 0) {
237 // Remove all uses of this inst.
238 auto users_begin = UsersBegin(inst);
239 auto end = id_to_users_.end();
240 auto new_end = users_begin;
241 for (; UsersNotEnd(new_end, end, inst); ++new_end) {
242 }
243 id_to_users_.erase(users_begin, new_end);
244 id_to_def_.erase(inst->result_id());
245 }
246 }
247}
248
249void DefUseManager::EraseUseRecordsOfOperandIds(const Instruction* inst) {
250 // Go through all ids used by this instruction, remove this instruction's
251 // uses of them.
252 auto iter = inst_to_used_ids_.find(inst);
253 if (iter != inst_to_used_ids_.end()) {
254 for (auto use_id : iter->second) {
255 id_to_users_.erase(
256 UserEntry(GetDef(use_id), const_cast<Instruction*>(inst)));
257 }
258 inst_to_used_ids_.erase(inst);
259 }
260}
261
262bool operator==(const DefUseManager& lhs, const DefUseManager& rhs) {
263 if (lhs.id_to_def_ != rhs.id_to_def_) {
264 return false;
265 }
266
267 if (lhs.id_to_users_ != rhs.id_to_users_) {
268 for (auto p : lhs.id_to_users_) {
269 if (rhs.id_to_users_.count(p) == 0) {
270 return false;
271 }
272 }
273 for (auto p : rhs.id_to_users_) {
274 if (lhs.id_to_users_.count(p) == 0) {
275 return false;
276 }
277 }
278 return false;
279 }
280
281 if (lhs.inst_to_used_ids_ != rhs.inst_to_used_ids_) {
282 for (auto p : lhs.inst_to_used_ids_) {
283 if (rhs.inst_to_used_ids_.count(p.first) == 0) {
284 return false;
285 }
286 }
287 for (auto p : rhs.inst_to_used_ids_) {
288 if (lhs.inst_to_used_ids_.count(p.first) == 0) {
289 return false;
290 }
291 }
292 return false;
293 }
294 return true;
295}
296
297} // namespace analysis
298} // namespace opt
299} // namespace spvtools
300