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/remove_duplicates_pass.h" 16 17 #include <algorithm> 18 #include <cstring> 19 #include <limits> 20 #include <string> 21 #include <unordered_map> 22 #include <unordered_set> 23 #include <vector> 24 25 #include "source/opcode.h" 26 #include "source/opt/decoration_manager.h" 27 #include "source/opt/ir_context.h" 28 #include "source/opt/reflect.h" 29 30 namespace spvtools { 31 namespace opt { 32 33 Pass::Status RemoveDuplicatesPass::Process() { 34 bool modified = RemoveDuplicateCapabilities(); 35 modified |= RemoveDuplicatesExtInstImports(); 36 modified |= RemoveDuplicateTypes(); 37 modified |= RemoveDuplicateDecorations(); 38 39 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; 40 } 41 42 bool RemoveDuplicatesPass::RemoveDuplicateCapabilities() const { 43 bool modified = false; 44 45 if (context()->capabilities().empty()) { 46 return modified; 47 } 48 49 std::unordered_set<uint32_t> capabilities; 50 for (auto* i = &*context()->capability_begin(); i;) { 51 auto res = capabilities.insert(i->GetSingleWordOperand(0u)); 52 53 if (res.second) { 54 // Never seen before, keep it. 55 i = i->NextNode(); 56 } else { 57 // It's a duplicate, remove it. 58 i = context()->KillInst(i); 59 modified = true; 60 } 61 } 62 63 return modified; 64 } 65 66 bool RemoveDuplicatesPass::RemoveDuplicatesExtInstImports() const { 67 bool modified = false; 68 69 if (context()->ext_inst_imports().empty()) { 70 return modified; 71 } 72 73 std::unordered_map<std::string, SpvId> ext_inst_imports; 74 for (auto* i = &*context()->ext_inst_import_begin(); i;) { 75 auto res = ext_inst_imports.emplace( 76 reinterpret_cast<const char*>(i->GetInOperand(0u).words.data()), 77 i->result_id()); 78 if (res.second) { 79 // Never seen before, keep it. 80 i = i->NextNode(); 81 } else { 82 // It's a duplicate, remove it. 83 context()->ReplaceAllUsesWith(i->result_id(), res.first->second); 84 i = context()->KillInst(i); 85 modified = true; 86 } 87 } 88 89 return modified; 90 } 91 92 bool RemoveDuplicatesPass::RemoveDuplicateTypes() const { 93 bool modified = false; 94 95 if (context()->types_values().empty()) { 96 return modified; 97 } 98 99 std::vector<Instruction*> visited_types; 100 std::vector<Instruction*> to_delete; 101 for (auto* i = &*context()->types_values_begin(); i; i = i->NextNode()) { 102 // We only care about types. 103 if (!spvOpcodeGeneratesType((i->opcode())) && 104 i->opcode() != SpvOpTypeForwardPointer) { 105 continue; 106 } 107 108 // Is the current type equal to one of the types we have aready visited? 109 SpvId id_to_keep = 0u; 110 // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the 111 // ResultIdTrie from unify_const_pass.cpp for this. 112 for (auto j : visited_types) { 113 if (AreTypesEqual(*i, *j, context())) { 114 id_to_keep = j->result_id(); 115 break; 116 } 117 } 118 119 if (id_to_keep == 0u) { 120 // This is a never seen before type, keep it around. 121 visited_types.emplace_back(i); 122 } else { 123 // The same type has already been seen before, remove this one. 124 context()->KillNamesAndDecorates(i->result_id()); 125 context()->ReplaceAllUsesWith(i->result_id(), id_to_keep); 126 modified = true; 127 to_delete.emplace_back(i); 128 } 129 } 130 131 for (auto i : to_delete) { 132 context()->KillInst(i); 133 } 134 135 return modified; 136 } 137 138 // TODO(pierremoreau): Duplicate decoration groups should be removed. For 139 // example, in 140 // OpDecorate %1 Constant 141 // %1 = OpDecorationGroup 142 // OpDecorate %2 Constant 143 // %2 = OpDecorationGroup 144 // OpGroupDecorate %1 %3 145 // OpGroupDecorate %2 %4 146 // group %2 could be removed. 147 bool RemoveDuplicatesPass::RemoveDuplicateDecorations() const { 148 bool modified = false; 149 150 std::vector<const Instruction*> visited_decorations; 151 152 analysis::DecorationManager decoration_manager(context()->module()); 153 for (auto* i = &*context()->annotation_begin(); i;) { 154 // Is the current decoration equal to one of the decorations we have aready 155 // visited? 156 bool already_visited = false; 157 // TODO(dneto0): Use a trie to avoid quadratic behaviour? Extract the 158 // ResultIdTrie from unify_const_pass.cpp for this. 159 for (const Instruction* j : visited_decorations) { 160 if (decoration_manager.AreDecorationsTheSame(&*i, j, false)) { 161 already_visited = true; 162 break; 163 } 164 } 165 166 if (!already_visited) { 167 // This is a never seen before decoration, keep it around. 168 visited_decorations.emplace_back(&*i); 169 i = i->NextNode(); 170 } else { 171 // The same decoration has already been seen before, remove this one. 172 modified = true; 173 i = context()->KillInst(i); 174 } 175 } 176 177 return modified; 178 } 179 180 bool RemoveDuplicatesPass::AreTypesEqual(const Instruction& inst1, 181 const Instruction& inst2, 182 IRContext* context) { 183 if (inst1.opcode() != inst2.opcode()) return false; 184 if (!IsTypeInst(inst1.opcode())) return false; 185 186 const analysis::Type* type1 = 187 context->get_type_mgr()->GetType(inst1.result_id()); 188 const analysis::Type* type2 = 189 context->get_type_mgr()->GetType(inst2.result_id()); 190 if (type1 && type2 && *type1 == *type2) return true; 191 192 return false; 193 } 194 195 } // namespace opt 196 } // namespace spvtools 197