| 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 |
|
| 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 |
|
| 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 |
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 |
|
| 71 |
void DefUseManager::AnalyzeInstDefUse(Instruction* inst) { |
| 72 |
AnalyzeInstDef(inst); |
| 73 |
AnalyzeInstUse(inst); |
| 74 |
} |
| 75 |
|
| 76 |
void 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 |
|
| 87 |
Instruction* 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 |
|
| 93 |
const 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 |
|
| 99 |
DefUseManager::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 |
|
| 105 |
bool 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 |
|
| 111 |
bool DefUseManager::UsersNotEnd(const IdToUsersMap::const_iterator& iter, |
| 112 |
const Instruction* inst) const { |
| 113 |
return UsersNotEnd(iter, id_to_users_.end(), inst); |
| 114 |
} |
| 115 |
|
| 116 |
bool 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 |
|
| 130 |
bool DefUseManager::WhileEachUser( |
| 131 |
uint32_t id, const std::function<bool(Instruction*)>& f) const { |
| 132 |
return WhileEachUser(GetDef(id), f); |
| 133 |
} |
| 134 |
|
| 135 |
void 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 |
|
| 143 |
void DefUseManager::ForEachUser( |
| 144 |
uint32_t id, const std::function<void(Instruction*)>& f) const { |
| 145 |
ForEachUser(GetDef(id), f); |
| 146 |
} |
| 147 |
|
| 148 |
bool 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 |
|
| 171 |
bool DefUseManager::WhileEachUse( |
| 172 |
uint32_t id, const std::function<bool(Instruction*, uint32_t)>& f) const { |
| 173 |
return WhileEachUse(GetDef(id), f); |
| 174 |
} |
| 175 |
|
| 176 |
void 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 |
|
| 185 |
void DefUseManager::ForEachUse( |
| 186 |
uint32_t id, const std::function<void(Instruction*, uint32_t)>& f) const { |
| 187 |
ForEachUse(GetDef(id), f); |
| 188 |
} |
| 189 |
|
| 190 |
uint32_t DefUseManager::NumUsers(const Instruction* def) const { |
| 191 |
uint32_t count = 0; |
| 192 |
ForEachUser(def, [&count](Instruction*) { ++count; }); |
| 193 |
return count; |
| 194 |
} |
| 195 |
|
| 196 |
uint32_t DefUseManager::NumUsers(uint32_t id) const { |
| 197 |
return NumUsers(GetDef(id)); |
| 198 |
} |
| 199 |
|
| 200 |
uint32_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 |
|
| 206 |
uint32_t DefUseManager::NumUses(uint32_t id) const { |
| 207 |
return NumUses(GetDef(id)); |
| 208 |
} |
| 209 |
|
| 210 |
std::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 |
|
| 223 |
void 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 |
|
| 232 |
void 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 |
|
| 249 |
void 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 |
|
| 262 |
bool 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 |