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/decoration_manager.h" 16 17 #include <algorithm> 18 #include <memory> 19 #include <set> 20 #include <stack> 21 #include <utility> 22 23 #include "source/opt/ir_context.h" 24 25 namespace spvtools { 26 namespace opt { 27 namespace analysis { 28 29 void DecorationManager::RemoveDecorationsFrom( 30 uint32_t id, std::function<bool(const Instruction&)> pred) { 31 const auto ids_iter = id_to_decoration_insts_.find(id); 32 if (ids_iter == id_to_decoration_insts_.end()) { 33 return; 34 } 35 36 TargetData& decorations_info = ids_iter->second; 37 auto context = module_->context(); 38 std::vector<Instruction*> insts_to_kill; 39 const bool is_group = !decorations_info.decorate_insts.empty(); 40 41 // Schedule all direct decorations for removal if instructed as such by 42 // |pred|. 43 for (Instruction* inst : decorations_info.direct_decorations) 44 if (pred(*inst)) insts_to_kill.push_back(inst); 45 46 // For all groups being directly applied to |id|, remove |id| (and the 47 // literal if |inst| is an OpGroupMemberDecorate) from the instruction 48 // applying the group. 49 std::unordered_set<const Instruction*> indirect_decorations_to_remove; 50 for (Instruction* inst : decorations_info.indirect_decorations) { 51 assert(inst->opcode() == SpvOpGroupDecorate || 52 inst->opcode() == SpvOpGroupMemberDecorate); 53 54 std::vector<Instruction*> group_decorations_to_keep; 55 const uint32_t group_id = inst->GetSingleWordInOperand(0u); 56 const auto group_iter = id_to_decoration_insts_.find(group_id); 57 assert(group_iter != id_to_decoration_insts_.end() && 58 "Unknown decoration group"); 59 const auto& group_decorations = group_iter->second.direct_decorations; 60 for (Instruction* decoration : group_decorations) { 61 if (!pred(*decoration)) group_decorations_to_keep.push_back(decoration); 62 } 63 64 // If all decorations should be kept, then we can keep |id| part of the 65 // group. However, if the group itself has no decorations, we should remove 66 // the id from the group. This is needed to make |KillNameAndDecorate| work 67 // correctly when a decoration group has no decorations. 68 if (group_decorations_to_keep.size() == group_decorations.size() && 69 group_decorations.size() != 0) { 70 continue; 71 } 72 73 // Otherwise, remove |id| from the targets of |group_id| 74 const uint32_t stride = inst->opcode() == SpvOpGroupDecorate ? 1u : 2u; 75 bool was_modified = false; 76 for (uint32_t i = 1u; i < inst->NumInOperands();) { 77 if (inst->GetSingleWordInOperand(i) != id) { 78 i += stride; 79 continue; 80 } 81 82 const uint32_t last_operand_index = inst->NumInOperands() - stride; 83 if (i < last_operand_index) 84 inst->GetInOperand(i) = inst->GetInOperand(last_operand_index); 85 // Remove the associated literal, if it exists. 86 if (stride == 2u) { 87 if (i < last_operand_index) 88 inst->GetInOperand(i + 1u) = 89 inst->GetInOperand(last_operand_index + 1u); 90 inst->RemoveInOperand(last_operand_index + 1u); 91 } 92 inst->RemoveInOperand(last_operand_index); 93 was_modified = true; 94 } 95 96 // If the instruction has no targets left, remove the instruction 97 // altogether. 98 if (inst->NumInOperands() == 1u) { 99 indirect_decorations_to_remove.emplace(inst); 100 insts_to_kill.push_back(inst); 101 } else if (was_modified) { 102 context->ForgetUses(inst); 103 indirect_decorations_to_remove.emplace(inst); 104 context->AnalyzeUses(inst); 105 } 106 107 // If only some of the decorations should be kept, clone them and apply 108 // them directly to |id|. 109 if (!group_decorations_to_keep.empty()) { 110 for (Instruction* decoration : group_decorations_to_keep) { 111 // simply clone decoration and change |group_id| to |id| 112 std::unique_ptr<Instruction> new_inst( 113 decoration->Clone(module_->context())); 114 new_inst->SetInOperand(0, {id}); 115 module_->AddAnnotationInst(std::move(new_inst)); 116 auto decoration_iter = --module_->annotation_end(); 117 context->AnalyzeUses(&*decoration_iter); 118 } 119 } 120 } 121 122 auto& indirect_decorations = decorations_info.indirect_decorations; 123 indirect_decorations.erase( 124 std::remove_if( 125 indirect_decorations.begin(), indirect_decorations.end(), 126 [&indirect_decorations_to_remove](const Instruction* inst) { 127 return indirect_decorations_to_remove.count(inst); 128 }), 129 indirect_decorations.end()); 130 131 for (Instruction* inst : insts_to_kill) context->KillInst(inst); 132 insts_to_kill.clear(); 133 134 // Schedule all instructions applying the group for removal if this group no 135 // longer applies decorations, either directly or indirectly. 136 if (is_group && decorations_info.direct_decorations.empty() && 137 decorations_info.indirect_decorations.empty()) { 138 for (Instruction* inst : decorations_info.decorate_insts) 139 insts_to_kill.push_back(inst); 140 } 141 for (Instruction* inst : insts_to_kill) context->KillInst(inst); 142 143 if (decorations_info.direct_decorations.empty() && 144 decorations_info.indirect_decorations.empty() && 145 decorations_info.decorate_insts.empty()) { 146 id_to_decoration_insts_.erase(ids_iter); 147 } 148 } 149 150 std::vector<Instruction*> DecorationManager::GetDecorationsFor( 151 uint32_t id, bool include_linkage) { 152 return InternalGetDecorationsFor<Instruction*>(id, include_linkage); 153 } 154 155 std::vector<const Instruction*> DecorationManager::GetDecorationsFor( 156 uint32_t id, bool include_linkage) const { 157 return const_cast<DecorationManager*>(this) 158 ->InternalGetDecorationsFor<const Instruction*>(id, include_linkage); 159 } 160 161 bool DecorationManager::HaveTheSameDecorations(uint32_t id1, 162 uint32_t id2) const { 163 using InstructionList = std::vector<const Instruction*>; 164 using DecorationSet = std::set<std::u32string>; 165 166 const InstructionList decorations_for1 = GetDecorationsFor(id1, false); 167 const InstructionList decorations_for2 = GetDecorationsFor(id2, false); 168 169 // This function splits the decoration instructions into different sets, 170 // based on their opcode; only OpDecorate, OpDecorateId, 171 // OpDecorateStringGOOGLE, and OpMemberDecorate are considered, the other 172 // opcodes are ignored. 173 const auto fillDecorationSets = 174 [](const InstructionList& decoration_list, DecorationSet* decorate_set, 175 DecorationSet* decorate_id_set, DecorationSet* decorate_string_set, 176 DecorationSet* member_decorate_set) { 177 for (const Instruction* inst : decoration_list) { 178 std::u32string decoration_payload; 179 // Ignore the opcode and the target as we do not want them to be 180 // compared. 181 for (uint32_t i = 1u; i < inst->NumInOperands(); ++i) { 182 for (uint32_t word : inst->GetInOperand(i).words) { 183 decoration_payload.push_back(word); 184 } 185 } 186 187 switch (inst->opcode()) { 188 case SpvOpDecorate: 189 decorate_set->emplace(std::move(decoration_payload)); 190 break; 191 case SpvOpMemberDecorate: 192 member_decorate_set->emplace(std::move(decoration_payload)); 193 break; 194 case SpvOpDecorateId: 195 decorate_id_set->emplace(std::move(decoration_payload)); 196 break; 197 case SpvOpDecorateStringGOOGLE: 198 decorate_string_set->emplace(std::move(decoration_payload)); 199 break; 200 default: 201 break; 202 } 203 } 204 }; 205 206 DecorationSet decorate_set_for1; 207 DecorationSet decorate_id_set_for1; 208 DecorationSet decorate_string_set_for1; 209 DecorationSet member_decorate_set_for1; 210 fillDecorationSets(decorations_for1, &decorate_set_for1, 211 &decorate_id_set_for1, &decorate_string_set_for1, 212 &member_decorate_set_for1); 213 214 DecorationSet decorate_set_for2; 215 DecorationSet decorate_id_set_for2; 216 DecorationSet decorate_string_set_for2; 217 DecorationSet member_decorate_set_for2; 218 fillDecorationSets(decorations_for2, &decorate_set_for2, 219 &decorate_id_set_for2, &decorate_string_set_for2, 220 &member_decorate_set_for2); 221 222 const bool result = decorate_set_for1 == decorate_set_for2 && 223 decorate_id_set_for1 == decorate_id_set_for2 && 224 member_decorate_set_for1 == member_decorate_set_for2 && 225 // Compare string sets last in case the strings are long. 226 decorate_string_set_for1 == decorate_string_set_for2; 227 return result; 228 } 229 230 // TODO(pierremoreau): If OpDecorateId is referencing an OpConstant, one could 231 // check that the constants are the same rather than just 232 // looking at the constant ID. 233 bool DecorationManager::AreDecorationsTheSame(const Instruction* inst1, 234 const Instruction* inst2, 235 bool ignore_target) const { 236 switch (inst1->opcode()) { 237 case SpvOpDecorate: 238 case SpvOpMemberDecorate: 239 case SpvOpDecorateId: 240 case SpvOpDecorateStringGOOGLE: 241 break; 242 default: 243 return false; 244 } 245 246 if (inst1->opcode() != inst2->opcode() || 247 inst1->NumInOperands() != inst2->NumInOperands()) 248 return false; 249 250 for (uint32_t i = ignore_target ? 1u : 0u; i < inst1->NumInOperands(); ++i) 251 if (inst1->GetInOperand(i) != inst2->GetInOperand(i)) return false; 252 253 return true; 254 } 255 256 void DecorationManager::AnalyzeDecorations() { 257 if (!module_) return; 258 259 // For each group and instruction, collect all their decoration instructions. 260 for (Instruction& inst : module_->annotations()) { 261 AddDecoration(&inst); 262 } 263 } 264 265 void DecorationManager::AddDecoration(Instruction* inst) { 266 switch (inst->opcode()) { 267 case SpvOpDecorate: 268 case SpvOpDecorateId: 269 case SpvOpDecorateStringGOOGLE: 270 case SpvOpMemberDecorate: { 271 const auto target_id = inst->GetSingleWordInOperand(0u); 272 id_to_decoration_insts_[target_id].direct_decorations.push_back(inst); 273 break; 274 } 275 case SpvOpGroupDecorate: 276 case SpvOpGroupMemberDecorate: { 277 const uint32_t start = inst->opcode() == SpvOpGroupDecorate ? 1u : 2u; 278 const uint32_t stride = start; 279 for (uint32_t i = start; i < inst->NumInOperands(); i += stride) { 280 const auto target_id = inst->GetSingleWordInOperand(i); 281 TargetData& target_data = id_to_decoration_insts_[target_id]; 282 target_data.indirect_decorations.push_back(inst); 283 } 284 const auto target_id = inst->GetSingleWordInOperand(0u); 285 id_to_decoration_insts_[target_id].decorate_insts.push_back(inst); 286 break; 287 } 288 default: 289 break; 290 } 291 } 292 293 void DecorationManager::AddDecoration(SpvOp opcode, 294 std::vector<Operand> opnds) { 295 IRContext* ctx = module_->context(); 296 std::unique_ptr<Instruction> newDecoOp( 297 new Instruction(ctx, opcode, 0, 0, opnds)); 298 ctx->AddAnnotationInst(std::move(newDecoOp)); 299 } 300 301 void DecorationManager::AddDecoration(uint32_t inst_id, uint32_t decoration) { 302 AddDecoration( 303 SpvOpDecorate, 304 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {inst_id}}, 305 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {decoration}}}); 306 } 307 308 void DecorationManager::AddDecorationVal(uint32_t inst_id, uint32_t decoration, 309 uint32_t decoration_value) { 310 AddDecoration( 311 SpvOpDecorate, 312 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {inst_id}}, 313 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {decoration}}, 314 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, 315 {decoration_value}}}); 316 } 317 318 void DecorationManager::AddMemberDecoration(uint32_t inst_id, uint32_t member, 319 uint32_t decoration, 320 uint32_t decoration_value) { 321 AddDecoration( 322 SpvOpMemberDecorate, 323 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {inst_id}}, 324 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {member}}, 325 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, {decoration}}, 326 {spv_operand_type_t::SPV_OPERAND_TYPE_LITERAL_INTEGER, 327 {decoration_value}}}); 328 } 329 330 template <typename T> 331 std::vector<T> DecorationManager::InternalGetDecorationsFor( 332 uint32_t id, bool include_linkage) { 333 std::vector<T> decorations; 334 335 const auto ids_iter = id_to_decoration_insts_.find(id); 336 // |id| has no decorations 337 if (ids_iter == id_to_decoration_insts_.end()) return decorations; 338 339 const TargetData& target_data = ids_iter->second; 340 341 const auto process_direct_decorations = 342 [include_linkage, 343 &decorations](const std::vector<Instruction*>& direct_decorations) { 344 for (Instruction* inst : direct_decorations) { 345 const bool is_linkage = inst->opcode() == SpvOpDecorate && 346 inst->GetSingleWordInOperand(1u) == 347 SpvDecorationLinkageAttributes; 348 if (include_linkage || !is_linkage) decorations.push_back(inst); 349 } 350 }; 351 352 // Process |id|'s decorations. 353 process_direct_decorations(ids_iter->second.direct_decorations); 354 355 // Process the decorations of all groups applied to |id|. 356 for (const Instruction* inst : target_data.indirect_decorations) { 357 const uint32_t group_id = inst->GetSingleWordInOperand(0u); 358 const auto group_iter = id_to_decoration_insts_.find(group_id); 359 assert(group_iter != id_to_decoration_insts_.end() && "Unknown group ID"); 360 process_direct_decorations(group_iter->second.direct_decorations); 361 } 362 363 return decorations; 364 } 365 366 bool DecorationManager::WhileEachDecoration( 367 uint32_t id, uint32_t decoration, 368 std::function<bool(const Instruction&)> f) { 369 for (const Instruction* inst : GetDecorationsFor(id, true)) { 370 switch (inst->opcode()) { 371 case SpvOpMemberDecorate: 372 if (inst->GetSingleWordInOperand(2) == decoration) { 373 if (!f(*inst)) return false; 374 } 375 break; 376 case SpvOpDecorate: 377 case SpvOpDecorateId: 378 case SpvOpDecorateStringGOOGLE: 379 if (inst->GetSingleWordInOperand(1) == decoration) { 380 if (!f(*inst)) return false; 381 } 382 break; 383 default: 384 assert(false && "Unexpected decoration instruction"); 385 } 386 } 387 return true; 388 } 389 390 void DecorationManager::ForEachDecoration( 391 uint32_t id, uint32_t decoration, 392 std::function<void(const Instruction&)> f) { 393 WhileEachDecoration(id, decoration, [&f](const Instruction& inst) { 394 f(inst); 395 return true; 396 }); 397 } 398 399 void DecorationManager::CloneDecorations(uint32_t from, uint32_t to) { 400 const auto decoration_list = id_to_decoration_insts_.find(from); 401 if (decoration_list == id_to_decoration_insts_.end()) return; 402 auto context = module_->context(); 403 for (Instruction* inst : decoration_list->second.direct_decorations) { 404 // simply clone decoration and change |target-id| to |to| 405 std::unique_ptr<Instruction> new_inst(inst->Clone(module_->context())); 406 new_inst->SetInOperand(0, {to}); 407 module_->AddAnnotationInst(std::move(new_inst)); 408 auto decoration_iter = --module_->annotation_end(); 409 context->AnalyzeUses(&*decoration_iter); 410 } 411 // We need to copy the list of instructions as ForgetUses and AnalyzeUses are 412 // going to modify it. 413 std::vector<Instruction*> indirect_decorations = 414 decoration_list->second.indirect_decorations; 415 for (Instruction* inst : indirect_decorations) { 416 switch (inst->opcode()) { 417 case SpvOpGroupDecorate: 418 context->ForgetUses(inst); 419 // add |to| to list of decorated id's 420 inst->AddOperand( 421 Operand(spv_operand_type_t::SPV_OPERAND_TYPE_ID, {to})); 422 context->AnalyzeUses(inst); 423 break; 424 case SpvOpGroupMemberDecorate: { 425 context->ForgetUses(inst); 426 // for each (id == from), add (to, literal) as operands 427 const uint32_t num_operands = inst->NumOperands(); 428 for (uint32_t i = 1; i < num_operands; i += 2) { 429 Operand op = inst->GetOperand(i); 430 if (op.words[0] == from) { // add new pair of operands: (to, literal) 431 inst->AddOperand( 432 Operand(spv_operand_type_t::SPV_OPERAND_TYPE_ID, {to})); 433 op = inst->GetOperand(i + 1); 434 inst->AddOperand(std::move(op)); 435 } 436 } 437 context->AnalyzeUses(inst); 438 break; 439 } 440 default: 441 assert(false && "Unexpected decoration instruction"); 442 } 443 } 444 } 445 446 void DecorationManager::CloneDecorations( 447 uint32_t from, uint32_t to, 448 const std::vector<SpvDecoration>& decorations_to_copy) { 449 const auto decoration_list = id_to_decoration_insts_.find(from); 450 if (decoration_list == id_to_decoration_insts_.end()) return; 451 auto context = module_->context(); 452 for (Instruction* inst : decoration_list->second.direct_decorations) { 453 if (std::find(decorations_to_copy.begin(), decorations_to_copy.end(), 454 inst->GetSingleWordInOperand(1)) == 455 decorations_to_copy.end()) { 456 continue; 457 } 458 459 // Clone decoration and change |target-id| to |to|. 460 std::unique_ptr<Instruction> new_inst(inst->Clone(module_->context())); 461 new_inst->SetInOperand(0, {to}); 462 module_->AddAnnotationInst(std::move(new_inst)); 463 auto decoration_iter = --module_->annotation_end(); 464 context->AnalyzeUses(&*decoration_iter); 465 } 466 467 // We need to copy the list of instructions as ForgetUses and AnalyzeUses are 468 // going to modify it. 469 std::vector<Instruction*> indirect_decorations = 470 decoration_list->second.indirect_decorations; 471 for (Instruction* inst : indirect_decorations) { 472 switch (inst->opcode()) { 473 case SpvOpGroupDecorate: 474 CloneDecorations(inst->GetSingleWordInOperand(0), to, 475 decorations_to_copy); 476 break; 477 case SpvOpGroupMemberDecorate: { 478 assert(false && "The source id is not suppose to be a type."); 479 break; 480 } 481 default: 482 assert(false && "Unexpected decoration instruction"); 483 } 484 } 485 } 486 487 void DecorationManager::RemoveDecoration(Instruction* inst) { 488 const auto remove_from_container = [inst](std::vector<Instruction*>& v) { 489 v.erase(std::remove(v.begin(), v.end(), inst), v.end()); 490 }; 491 492 switch (inst->opcode()) { 493 case SpvOpDecorate: 494 case SpvOpDecorateId: 495 case SpvOpDecorateStringGOOGLE: 496 case SpvOpMemberDecorate: { 497 const auto target_id = inst->GetSingleWordInOperand(0u); 498 auto const iter = id_to_decoration_insts_.find(target_id); 499 if (iter == id_to_decoration_insts_.end()) return; 500 remove_from_container(iter->second.direct_decorations); 501 } break; 502 case SpvOpGroupDecorate: 503 case SpvOpGroupMemberDecorate: { 504 const uint32_t stride = inst->opcode() == SpvOpGroupDecorate ? 1u : 2u; 505 for (uint32_t i = 1u; i < inst->NumInOperands(); i += stride) { 506 const auto target_id = inst->GetSingleWordInOperand(i); 507 auto const iter = id_to_decoration_insts_.find(target_id); 508 if (iter == id_to_decoration_insts_.end()) continue; 509 remove_from_container(iter->second.indirect_decorations); 510 } 511 const auto group_id = inst->GetSingleWordInOperand(0u); 512 auto const iter = id_to_decoration_insts_.find(group_id); 513 if (iter == id_to_decoration_insts_.end()) return; 514 remove_from_container(iter->second.decorate_insts); 515 } break; 516 default: 517 break; 518 } 519 } 520 521 bool operator==(const DecorationManager& lhs, const DecorationManager& rhs) { 522 return lhs.id_to_decoration_insts_ == rhs.id_to_decoration_insts_; 523 } 524 525 } // namespace analysis 526 } // namespace opt 527 } // namespace spvtools 528