1*9e3b08aeSAndroid Build Coastguard Worker // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 2*9e3b08aeSAndroid Build Coastguard Worker // -*- mode: C++ -*- 3*9e3b08aeSAndroid Build Coastguard Worker // 4*9e3b08aeSAndroid Build Coastguard Worker // Copyright 2022 Google LLC 5*9e3b08aeSAndroid Build Coastguard Worker // 6*9e3b08aeSAndroid Build Coastguard Worker // Licensed under the Apache License v2.0 with LLVM Exceptions (the 7*9e3b08aeSAndroid Build Coastguard Worker // "License"); you may not use this file except in compliance with the 8*9e3b08aeSAndroid Build Coastguard Worker // License. You may obtain a copy of the License at 9*9e3b08aeSAndroid Build Coastguard Worker // 10*9e3b08aeSAndroid Build Coastguard Worker // https://llvm.org/LICENSE.txt 11*9e3b08aeSAndroid Build Coastguard Worker // 12*9e3b08aeSAndroid Build Coastguard Worker // Unless required by applicable law or agreed to in writing, software 13*9e3b08aeSAndroid Build Coastguard Worker // distributed under the License is distributed on an "AS IS" BASIS, 14*9e3b08aeSAndroid Build Coastguard Worker // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15*9e3b08aeSAndroid Build Coastguard Worker // See the License for the specific language governing permissions and 16*9e3b08aeSAndroid Build Coastguard Worker // limitations under the License. 17*9e3b08aeSAndroid Build Coastguard Worker // 18*9e3b08aeSAndroid Build Coastguard Worker // Author: Giuliano Procida 19*9e3b08aeSAndroid Build Coastguard Worker 20*9e3b08aeSAndroid Build Coastguard Worker #ifndef STG_FINGERPRINT_H_ 21*9e3b08aeSAndroid Build Coastguard Worker #define STG_FINGERPRINT_H_ 22*9e3b08aeSAndroid Build Coastguard Worker 23*9e3b08aeSAndroid Build Coastguard Worker #include <unordered_map> 24*9e3b08aeSAndroid Build Coastguard Worker 25*9e3b08aeSAndroid Build Coastguard Worker #include "graph.h" 26*9e3b08aeSAndroid Build Coastguard Worker #include "hashing.h" 27*9e3b08aeSAndroid Build Coastguard Worker #include "runtime.h" 28*9e3b08aeSAndroid Build Coastguard Worker 29*9e3b08aeSAndroid Build Coastguard Worker namespace stg { 30*9e3b08aeSAndroid Build Coastguard Worker 31*9e3b08aeSAndroid Build Coastguard Worker // Fingerprint is a node hasher that hashes all nodes reachable from a given 32*9e3b08aeSAndroid Build Coastguard Worker // root node. It will almost always succeed in distinguishing unequal nodes. 33*9e3b08aeSAndroid Build Coastguard Worker // 34*9e3b08aeSAndroid Build Coastguard Worker // Given any mutual dependencies between hashes, it falls back to a very poor 35*9e3b08aeSAndroid Build Coastguard Worker // but safe hash for the affected nodes: the size of the SCC. 36*9e3b08aeSAndroid Build Coastguard Worker std::unordered_map<Id, HashValue> Fingerprint( 37*9e3b08aeSAndroid Build Coastguard Worker Runtime& runtime, const Graph& graph, Id root); 38*9e3b08aeSAndroid Build Coastguard Worker 39*9e3b08aeSAndroid Build Coastguard Worker } // namespace stg 40*9e3b08aeSAndroid Build Coastguard Worker 41*9e3b08aeSAndroid Build Coastguard Worker #endif // STG_FINGERPRINT_H_ 42