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_UNIFICATION_H_ 21 #define STG_UNIFICATION_H_ 22 23 #include "graph.h" 24 #include "runtime.h" 25 26 namespace stg { 27 28 // Keep track of which nodes are pending substitution and rewrite the graph on 29 // destruction. 30 class Unification { 31 public: 32 Unification(Runtime& runtime, Graph& graph, Id start, Id limit); 33 34 ~Unification() noexcept(false); 35 36 // id2 will always be preferred as a parent node; interpreted as a 37 // substitution, id1 will be replaced by id2 38 void Union(Id id1, Id id2); 39 40 Id Find(Id id); 41 42 // attempt to unify, recursively, allowing types declarations to be replaced 43 // by definitions 44 bool Unify(Id id1, Id id2); 45 46 private: 47 Graph& graph_; 48 Id start_; 49 DenseIdMapping mapping_; 50 Runtime& runtime_; 51 Counter find_query_; 52 Counter find_halved_; 53 Counter union_known_; 54 Counter union_unknown_; 55 }; 56 57 } // namespace stg 58 59 #endif // STG_UNIFICATION_H_ 60