Add Valmari-Lehtinen DFA minimization as a standalone utility (#5430)

We used to have this algorithm in wasm-type.cpp, where we used it to implement
equirecursive type canonicalization, but we removed it when we removed
equirecursive typing. Bring the algorithm back as a standalone utility for
future use in optimization passes. In particular, it will be useful in
TypeMerging for identifying the greatest fixed point of mergeable types rather
than the smallest fixed point.

1 files changed, 103 insertions, 0 deletions

diff --git a/src/support/dfa_minimization.h b/src/support/dfa_minimization.h
new file mode 100644
index 000000000..a641022a7
--- /dev/null
+++ b/src/support/dfa_minimization.h
@@ -0,0 +1,103 @@
+/*
+ * Copyright 2023 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Use the Valmari-Lehtinen DFA minimization algorithm
+// (https://arxiv.org/pdf/0802.2826.pdf) to find equivalent elements in a
+// user-provided DFA.
+
+#ifndef wasm_support_dfa_minimization_h
+#define wasm_support_dfa_minimization_h
+
+#include <cassert>
+#include <cstddef>
+#include <unordered_map>
+#include <vector>
+
+namespace wasm::DFA {
+
+namespace Internal {
+
+std::vector<std::vector<size_t>>
+refinePartitionsImpl(const std::vector<std::vector<std::vector<size_t>>>&);
+
+} // namespace Internal
+
+// A DFA state with an ordered list of successor states.
+template<typename T> struct State {
+  T val;
+  std::vector<T> succs;
+};
+
+// Given a vector of initial state partitions in which states known to be
+// different are in different partitions, return a vector of refined partitions,
+// each containing a different equivalence class of states. No value should
+// appear more than once in the input. All successor values should appear in
+// some top-level partition.
+template<typename T>
+std::vector<std::vector<T>>
+refinePartitions(const std::vector<std::vector<State<T>>>& partitions) {
+  // Map values to indices and vice versa.
+  std::unordered_map<T, size_t> indices;
+  std::vector<T> values;
+  for (const auto& partition : partitions) {
+    for (const auto& state : partition) {
+      [[maybe_unused]] bool inserted =
+        indices.insert({state.val, indices.size()}).second;
+      assert(inserted && "unexpected repeated value");
+      values.push_back(state.val);
+    }
+  }
+
+  // Create a copy of the DFA that uses indices instead of the original values.
+  std::vector<std::vector<std::vector<size_t>>> indexPartitions;
+  indexPartitions.reserve(partitions.size());
+  for (const auto& partition : partitions) {
+    std::vector<std::vector<size_t>> indexPartition;
+    indexPartition.reserve(partition.size());
+    for (const auto& state : partition) {
+      std::vector<size_t> succIndices;
+      succIndices.reserve(state.succs.size());
+      for (const auto& succ : state.succs) {
+        auto it = indices.find(succ);
+        assert(it != indices.end() && "unknown successor value");
+        succIndices.push_back(it->second);
+      }
+      indexPartition.emplace_back(std::move(succIndices));
+    }
+    indexPartitions.emplace_back(std::move(indexPartition));
+  }
+
+  // Refine the partitions.
+  auto indexResults = Internal::refinePartitionsImpl(indexPartitions);
+
+  // Map the refined partitions of indices back to values.
+  std::vector<std::vector<T>> results;
+  results.reserve(indexResults.size());
+  for (const auto& indexPartition : indexResults) {
+    std::vector<T> partition;
+    partition.reserve(indexPartition.size());
+    for (size_t index : indexPartition) {
+      partition.push_back(values[index]);
+    }
+    results.emplace_back(std::move(partition));
+  }
+
+  return results;
+}
+
+} // namespace wasm::DFA
+
+#endif // wasm_support_dfa_minimization_h