1 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 2 // -*- mode: C++ -*- 3 // 4 // Copyright 2022 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_FINGERPRINT_H_ 21 #define STG_FINGERPRINT_H_ 22 23 #include <cstdint> 24 #include <unordered_map> 25 26 #include "graph.h" 27 #include "hashing.h" 28 #include "runtime.h" 29 30 namespace stg { 31 32 // Fingerprint is a node hasher that hashes all nodes reachable from a given 33 // root node. It will almost always succeed in distinguishing unequal nodes. 34 // 35 // Given any mutual dependencies between hashes, it falls back to a very poor 36 // but safe hash for the affected nodes: the size of the SCC. 37 std::unordered_map<Id, HashValue> Fingerprint( 38 Runtime& runtime, const Graph& graph, Id root); 39 40 } // namespace stg 41 42 #endif // STG_FINGERPRINT_H_ 43