1 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 2 // -*- mode: C++ -*- 3 // 4 // Copyright 2022-2024 Google LLC 5 // 6 // Licensed under the Apache License v2.0 with LLVM Exceptions (the 7 // "License"); you may not use this file except in compliance with the 8 // License. You may obtain a copy of the License at 9 // 10 // https://llvm.org/LICENSE.txt 11 // 12 // Unless required by applicable law or agreed to in writing, software 13 // distributed under the License is distributed on an "AS IS" BASIS, 14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 // See the License for the specific language governing permissions and 16 // limitations under the License. 17 // 18 // Author: Giuliano Procida 19 20 #ifndef STG_EQUALITY_H_ 21 #define STG_EQUALITY_H_ 22 23 #include <cstddef> 24 #include <map> 25 #include <optional> 26 #include <vector> 27 28 #include "graph.h" 29 #include "scc.h" 30 31 namespace stg { 32 33 // Node equality algorithm. This only cares about node and edge attributes and 34 // is blind to node identity. It is generic over the equality cache which is fed 35 // information about equality results and queried for the same. Different 36 // implementations are possible depending on the needs of the caller and the 37 // guaranteed invariants. 38 template <typename EqualityCache> 39 struct Equals { EqualsEquals40 Equals(const Graph& graph, EqualityCache& equality_cache) 41 : graph(graph), equality_cache(equality_cache) {} 42 operatorEquals43 bool operator()(Id id1, Id id2) { 44 const Pair comparison = {id1, id2}; 45 46 // Check if the comparison has an already known result. 47 const auto check = equality_cache.Query(comparison); 48 if (check.has_value()) { 49 return check.value(); 50 } 51 52 // Record the comparison with Strongly-Connected Component finder. 53 auto handle = scc.Open(comparison); 54 if (!handle) { 55 // Already open. 56 // 57 // Return a dummy true outcome. 58 return true; 59 } 60 // Comparison opened, need to close it before returning. 61 62 const auto result = graph.Apply2(*this, id1, id2); 63 64 // Check for a complete Strongly-Connected Component. 65 auto comparisons = scc.Close(*handle); 66 if (comparisons.empty()) { 67 // Note that result is tentative as the SCC is still open. 68 return result; 69 } 70 71 // Closed SCC. 72 // 73 // Note that result is the conjunction of every equality in the SCC via the 74 // DFS spanning tree. 75 if (result) { 76 equality_cache.AllSame(comparisons); 77 } else { 78 equality_cache.AllDifferent(comparisons); 79 } 80 return result; 81 } 82 operatorEquals83 bool operator()(const std::optional<Id>& opt1, 84 const std::optional<Id>& opt2) { 85 if (opt1.has_value() && opt2.has_value()) { 86 return (*this)(opt1.value(), opt2.value()); 87 } 88 return opt1.has_value() == opt2.has_value(); 89 } 90 operatorEquals91 bool operator()(const std::vector<Id>& ids1, const std::vector<Id>& ids2) { 92 bool result = ids1.size() == ids2.size(); 93 for (size_t ix = 0; result && ix < ids1.size(); ++ix) { 94 result = (*this)(ids1[ix], ids2[ix]); 95 } 96 return result; 97 } 98 99 template <typename Key> operatorEquals100 bool operator()(const std::map<Key, Id>& ids1, 101 const std::map<Key, Id>& ids2) { 102 bool result = ids1.size() == ids2.size(); 103 auto it1 = ids1.begin(); 104 auto it2 = ids2.begin(); 105 const auto end1 = ids1.end(); 106 const auto end2 = ids2.end(); 107 while (result && it1 != end1 && it2 != end2) { 108 result = it1->first == it2->first 109 && (*this)(it1->second, it2->second); 110 ++it1; 111 ++it2; 112 } 113 return result && it1 == end1 && it2 == end2; 114 } 115 operatorEquals116 bool operator()(const Special& x1, const Special& x2) { 117 return x1.kind == x2.kind; 118 } 119 operatorEquals120 bool operator()(const PointerReference& x1, 121 const PointerReference& x2) { 122 return x1.kind == x2.kind 123 && (*this)(x1.pointee_type_id, x2.pointee_type_id); 124 } 125 operatorEquals126 bool operator()(const PointerToMember& x1, const PointerToMember& x2) { 127 return (*this)(x1.containing_type_id, x2.containing_type_id) 128 && (*this)(x1.pointee_type_id, x2.pointee_type_id); 129 } 130 operatorEquals131 bool operator()(const Typedef& x1, const Typedef& x2) { 132 return x1.name == x2.name 133 && (*this)(x1.referred_type_id, x2.referred_type_id); 134 } 135 operatorEquals136 bool operator()(const Qualified& x1, const Qualified& x2) { 137 return x1.qualifier == x2.qualifier 138 && (*this)(x1.qualified_type_id, x2.qualified_type_id); 139 } 140 operatorEquals141 bool operator()(const Primitive& x1, const Primitive& x2) { 142 return x1.name == x2.name 143 && x1.encoding == x2.encoding 144 && x1.bytesize == x2.bytesize; 145 } 146 operatorEquals147 bool operator()(const Array& x1, const Array& x2) { 148 return x1.number_of_elements == x2.number_of_elements 149 && (*this)(x1.element_type_id, x2.element_type_id); 150 } 151 operatorEquals152 bool operator()(const BaseClass& x1, const BaseClass& x2) { 153 return x1.offset == x2.offset 154 && x1.inheritance == x2.inheritance 155 && (*this)(x1.type_id, x2.type_id); 156 } 157 operatorEquals158 bool operator()(const Method& x1, const Method& x2) { 159 return x1.mangled_name == x2.mangled_name 160 && x1.name == x2.name 161 && x1.vtable_offset == x2.vtable_offset 162 && (*this)(x1.type_id, x2.type_id); 163 } 164 operatorEquals165 bool operator()(const Member& x1, const Member& x2) { 166 return x1.name == x2.name 167 && x1.offset == x2.offset 168 && x1.bitsize == x2.bitsize 169 && (*this)(x1.type_id, x2.type_id); 170 } 171 operatorEquals172 bool operator()(const VariantMember& x1, const VariantMember& x2) { 173 return x1.name == x2.name 174 && x1.discriminant_value == x2.discriminant_value 175 && (*this)(x1.type_id, x2.type_id); 176 } 177 operatorEquals178 bool operator()(const StructUnion& x1, const StructUnion& x2) { 179 const auto& definition1 = x1.definition; 180 const auto& definition2 = x2.definition; 181 bool result = x1.kind == x2.kind 182 && x1.name == x2.name 183 && definition1.has_value() == definition2.has_value(); 184 if (result && definition1.has_value()) { 185 result = definition1->bytesize == definition2->bytesize 186 && (*this)(definition1->base_classes, definition2->base_classes) 187 && (*this)(definition1->methods, definition2->methods) 188 && (*this)(definition1->members, definition2->members); 189 } 190 return result; 191 } 192 operatorEquals193 bool operator()(const Enumeration& x1, const Enumeration& x2) { 194 const auto& definition1 = x1.definition; 195 const auto& definition2 = x2.definition; 196 bool result = x1.name == x2.name 197 && definition1.has_value() == definition2.has_value(); 198 if (result && definition1.has_value()) { 199 result = (*this)(definition1->underlying_type_id, 200 definition2->underlying_type_id) 201 && definition1->enumerators == definition2->enumerators; 202 } 203 return result; 204 } 205 operatorEquals206 bool operator()(const Variant& x1, const Variant& x2) { 207 return x1.name == x2.name 208 && x1.bytesize == x2.bytesize 209 && (*this)(x1.discriminant, x2.discriminant) 210 && (*this)(x1.members, x2.members); 211 } 212 operatorEquals213 bool operator()(const Function& x1, const Function& x2) { 214 return (*this)(x1.parameters, x2.parameters) 215 && (*this)(x1.return_type_id, x2.return_type_id); 216 } 217 operatorEquals218 bool operator()(const ElfSymbol& x1, const ElfSymbol& x2) { 219 bool result = x1.symbol_name == x2.symbol_name 220 && x1.version_info == x2.version_info 221 && x1.is_defined == x2.is_defined 222 && x1.symbol_type == x2.symbol_type 223 && x1.binding == x2.binding 224 && x1.visibility == x2.visibility 225 && x1.crc == x2.crc 226 && x1.ns == x2.ns 227 && x1.full_name == x2.full_name 228 && x1.type_id.has_value() == x2.type_id.has_value(); 229 if (result && x1.type_id.has_value()) { 230 result = (*this)(x1.type_id.value(), x2.type_id.value()); 231 } 232 return result; 233 } 234 operatorEquals235 bool operator()(const Interface& x1, const Interface& x2) { 236 return (*this)(x1.symbols, x2.symbols) 237 && (*this)(x1.types, x2.types); 238 } 239 MismatchEquals240 bool Mismatch() { 241 return false; 242 } 243 244 const Graph& graph; 245 EqualityCache& equality_cache; 246 SCC<Pair> scc; 247 }; 248 249 } // namespace stg 250 251 #endif // STG_EQUALITY_H_ 252