| // Copyright (c) 2017 Pierre Moreau | |
| // | |
| // Licensed under the Apache License, Version 2.0 (the "License"); | |
| // you may not use this file except in compliance with the License. | |
| // You may obtain a copy of the License at | |
| // | |
| // http://www.apache.org/licenses/LICENSE-2.0 | |
| // | |
| // Unless required by applicable law or agreed to in writing, software | |
| // distributed under the License is distributed on an "AS IS" BASIS, | |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| // See the License for the specific language governing permissions and | |
| // limitations under the License. | |
| #include "source/opt/remove_duplicates_pass.h" | |
| #include <algorithm> | |
| #include <string> | |
| #include <unordered_map> | |
| #include <unordered_set> | |
| #include <vector> | |
| #include "source/opcode.h" | |
| #include "source/opt/decoration_manager.h" | |
| #include "source/opt/ir_context.h" | |
| namespace spvtools { | |
| namespace opt { | |
| Pass::Status RemoveDuplicatesPass::Process() { | |
| bool modified = RemoveDuplicateCapabilities(); | |
| modified |= RemoveDuplicateExtensions(); | |
| modified |= RemoveDuplicatesExtInstImports(); | |
| modified |= RemoveDuplicateTypes(); | |
| modified |= RemoveDuplicateDecorations(); | |
| return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; | |
| } | |
| bool RemoveDuplicatesPass::RemoveDuplicateExtensions() const { | |
| bool modified = false; | |
| if (context()->extensions().empty()) { | |
| return modified; | |
| } | |
| // set of {condition ID, extension name} | |
| // ID 0 means unconditional extension, ie., OpExtension, otherwise the ID is | |
| // the condition operand of OpConditionalExtensionINTEL. | |
| std::set<std::pair<uint32_t, std::string>> extensions; | |
| for (auto* inst = &*context()->extension_begin(); inst;) { | |
| uint32_t cond_id = 0; | |
| uint32_t i_name = 0; | |
| if (inst->opcode() == spv::Op::OpConditionalExtensionINTEL) { | |
| cond_id = inst->GetOperand(0).AsId(); | |
| i_name = 1; | |
| } | |
| auto res = | |
| extensions.insert({cond_id, inst->GetOperand(i_name).AsString()}); | |
| if (res.second) { | |
| // Never seen before, keep it. | |
| inst = inst->NextNode(); | |
| } else { | |
| // It's a duplicate, remove it. | |
| inst = context()->KillInst(inst); | |
| modified = true; | |
| } | |
| } | |
| return modified; | |
| } | |
| bool RemoveDuplicatesPass::RemoveDuplicateCapabilities() const { | |
| bool modified = false; | |
| if (context()->capabilities().empty()) { | |
| return modified; | |
| } | |
| // set of {condition ID, capability} | |
| // ID 0 means unconditional capability, ie., OpCapability, otherwise the ID is | |
| // the condition operand of OpConditionalCapabilityINTEL. | |
| std::set<std::pair<uint32_t, uint32_t>> capabilities; | |
| for (auto* inst = &*context()->capability_begin(); inst;) { | |
| uint32_t cond_id = 0; | |
| uint32_t i_cap = 0; | |
| if (inst->opcode() == spv::Op::OpConditionalCapabilityINTEL) { | |
| cond_id = inst->GetOperand(0).AsId(); | |
| i_cap = 1; | |
| } | |
| auto res = | |
| capabilities.insert({cond_id, inst->GetSingleWordOperand(i_cap)}); | |
| if (res.second) { | |
| // Never seen before, keep it. | |
| inst = inst->NextNode(); | |
| } else { | |
| // It's a duplicate, remove it. | |
| inst = context()->KillInst(inst); | |
| modified = true; | |
| } | |
| } | |
| return modified; | |
| } | |
| bool RemoveDuplicatesPass::RemoveDuplicatesExtInstImports() const { | |
| bool modified = false; | |
| if (context()->ext_inst_imports().empty()) { | |
| return modified; | |
| } | |
| std::unordered_map<std::string, spv::Id> ext_inst_imports; | |
| for (auto* i = &*context()->ext_inst_import_begin(); i;) { | |
| auto res = ext_inst_imports.emplace(i->GetInOperand(0u).AsString(), | |
| i->result_id()); | |
| if (res.second) { | |
| // Never seen before, keep it. | |
| i = i->NextNode(); | |
| } else { | |
| // It's a duplicate, remove it. | |
| context()->ReplaceAllUsesWith(i->result_id(), res.first->second); | |
| i = context()->KillInst(i); | |
| modified = true; | |
| } | |
| } | |
| return modified; | |
| } | |
| bool RemoveDuplicatesPass::RemoveDuplicateTypes() const { | |
| bool modified = false; | |
| if (context()->types_values().empty()) { | |
| return modified; | |
| } | |
| analysis::TypeManager type_manager(context()->consumer(), context()); | |
| std::vector<Instruction*> visited_types; | |
| std::vector<analysis::ForwardPointer> visited_forward_pointers; | |
| std::vector<Instruction*> to_delete; | |
| for (auto* i = &*context()->types_values_begin(); i; i = i->NextNode()) { | |
| const bool is_i_forward_pointer = | |
| i->opcode() == spv::Op::OpTypeForwardPointer; | |
| // We only care about types. | |
| if (!spvOpcodeGeneratesType(i->opcode()) && !is_i_forward_pointer) { | |
| continue; | |
| } | |
| if (!is_i_forward_pointer) { | |
| // Is the current type equal to one of the types we have already visited? | |
| spv::Id id_to_keep = 0u; | |
| analysis::Type* i_type = type_manager.GetType(i->result_id()); | |
| assert(i_type); | |
| // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the | |
| // ResultIdTrie from unify_const_pass.cpp for this. | |
| for (auto j : visited_types) { | |
| analysis::Type* j_type = type_manager.GetType(j->result_id()); | |
| assert(j_type); | |
| if (*i_type == *j_type) { | |
| id_to_keep = j->result_id(); | |
| break; | |
| } | |
| } | |
| if (id_to_keep == 0u) { | |
| // This is a never seen before type, keep it around. | |
| visited_types.emplace_back(i); | |
| } else { | |
| // The same type has already been seen before, remove this one. | |
| context()->KillNamesAndDecorates(i->result_id()); | |
| context()->ReplaceAllUsesWith(i->result_id(), id_to_keep); | |
| modified = true; | |
| to_delete.emplace_back(i); | |
| } | |
| } else { | |
| analysis::ForwardPointer i_type( | |
| i->GetSingleWordInOperand(0u), | |
| (spv::StorageClass)i->GetSingleWordInOperand(1u)); | |
| i_type.SetTargetPointer( | |
| type_manager.GetType(i_type.target_id())->AsPointer()); | |
| // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the | |
| // ResultIdTrie from unify_const_pass.cpp for this. | |
| const bool found_a_match = | |
| std::find(std::begin(visited_forward_pointers), | |
| std::end(visited_forward_pointers), | |
| i_type) != std::end(visited_forward_pointers); | |
| if (!found_a_match) { | |
| // This is a never seen before type, keep it around. | |
| visited_forward_pointers.emplace_back(i_type); | |
| } else { | |
| // The same type has already been seen before, remove this one. | |
| modified = true; | |
| to_delete.emplace_back(i); | |
| } | |
| } | |
| } | |
| for (auto i : to_delete) { | |
| context()->KillInst(i); | |
| } | |
| return modified; | |
| } | |
| // TODO(pierremoreau): Duplicate decoration groups should be removed. For | |
| // example, in | |
| // OpDecorate %1 Constant | |
| // %1 = OpDecorationGroup | |
| // OpDecorate %2 Constant | |
| // %2 = OpDecorationGroup | |
| // OpGroupDecorate %1 %3 | |
| // OpGroupDecorate %2 %4 | |
| // group %2 could be removed. | |
| bool RemoveDuplicatesPass::RemoveDuplicateDecorations() const { | |
| bool modified = false; | |
| std::vector<const Instruction*> visited_decorations; | |
| analysis::DecorationManager decoration_manager(context()->module()); | |
| for (auto* i = &*context()->annotation_begin(); i;) { | |
| // Is the current decoration equal to one of the decorations we have | |
| // already visited? | |
| bool already_visited = false; | |
| // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the | |
| // ResultIdTrie from unify_const_pass.cpp for this. | |
| for (const Instruction* j : visited_decorations) { | |
| if (decoration_manager.AreDecorationsTheSame(&*i, j, false)) { | |
| already_visited = true; | |
| break; | |
| } | |
| } | |
| if (!already_visited) { | |
| // This is a never seen before decoration, keep it around. | |
| visited_decorations.emplace_back(&*i); | |
| i = i->NextNode(); | |
| } else { | |
| // The same decoration has already been seen before, remove this one. | |
| modified = true; | |
| i = context()->KillInst(i); | |
| } | |
| } | |
| return modified; | |
| } | |
| } // namespace opt | |
| } // namespace spvtools |