Replace the old topological sort everywhere (#6902)

To avoid having two separate topological sort utilities in the code
base, replace remaining uses of the old DFS-based, CRTP topological sort
with the newer Kahn's algorithm implementation.

This would be NFC, except that the new topological sort produces a
different order than the old topological sort, so the output of some
passes is reordered.

6 files changed, 121 insertions, 224 deletions

diff --git a/src/ir/subtypes.h b/src/ir/subtypes.h
index 47ee51ac3..c69250043 100644
--- a/src/ir/subtypes.h
+++ b/src/ir/subtypes.h
@@ -18,7 +18,7 @@
 #define wasm_ir_subtypes_h
 
 #include "ir/module-utils.h"
-#include "support/old_topological_sort.h"
+#include "support/topological_sort.h"
 #include "wasm.h"
 
 namespace wasm {
@@ -79,29 +79,19 @@ struct SubTypes {
   }
 
   // A topological sort that visits subtypes first.
-  auto getSubTypesFirstSort() const {
-    struct SubTypesFirstSort : OldTopologicalSort<HeapType, SubTypesFirstSort> {
-      const SubTypes& parent;
-
-      SubTypesFirstSort(const SubTypes& parent) : parent(parent) {
-        for (auto type : parent.types) {
-          // The roots are types with no supertype.
-          if (!type.getDeclaredSuperType()) {
-            push(type);
-          }
-        }
-      }
-
-      void pushPredecessors(HeapType type) {
-        // Things we need to process before each type are its subtypes. Once we
-        // know their depth, we can easily compute our own.
-        for (auto pred : parent.getImmediateSubTypes(type)) {
-          push(pred);
-        }
+  std::vector<HeapType> getSubTypesFirstSort() const {
+    std::vector<std::pair<HeapType, std::vector<HeapType>>> graph;
+    graph.reserve(types.size());
+    for (auto type : types) {
+      if (auto it = typeSubTypes.find(type); it != typeSubTypes.end()) {
+        graph.emplace_back(*it);
+      } else {
+        graph.emplace_back(type, std::vector<HeapType>{});
       }
-    };
-
-    return SubTypesFirstSort(*this);
+    }
+    auto sorted = TopologicalSort::sortOf(graph.begin(), graph.end());
+    std::reverse(sorted.begin(), sorted.end());
+    return sorted;
   }
 
   // Computes the depth of children for each type. This is 0 if the type has no
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index 467971989..dedbb6316 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -40,118 +40,72 @@ GlobalTypeRewriter::TypeMap GlobalTypeRewriter::rebuildTypes(
   // world scenario, don't modify public types because we assume that they may
   // be reflected on or used for linking. Figure out where each private type
   // will be located in the builder.
-  //
-  // There are two code paths here: a new one that is used when there are type
-  // indices to preserve and an old one that is used otherwise. The old code
-  // path is kept around to avoid unnecessary changes to test outputs while we
-  // incrementally add --preserve-type-order to tests that could benefit from
-  // it. Once we are done adding --preserve-type-order to tests, we should
-  // remove the old code path here since the new code path is strictly better.
-  if (wasm.typeIndices.size()) {
-    // New code path, currently used only with --preserve-type-order.
-    auto typeInfo = ModuleUtils::collectHeapTypeInfo(
-      wasm,
-      ModuleUtils::TypeInclusion::UsedIRTypes,
-      ModuleUtils::VisibilityHandling::FindVisibility);
-
-    std::unordered_set<HeapType> additionalSet(additionalPrivateTypes.begin(),
-                                               additionalPrivateTypes.end());
-
-    std::vector<std::pair<HeapType, SmallVector<HeapType, 1>>>
-      privateSupertypes;
-    privateSupertypes.reserve(typeInfo.size());
-    for (auto& [type, info] : typeInfo) {
-      if (info.visibility != ModuleUtils::Visibility::Private &&
-          !additionalSet.count(type)) {
-        continue;
-      }
-      privateSupertypes.push_back({type, {}});
-
-      if (auto super = getDeclaredSuperType(type)) {
-        auto it = typeInfo.find(*super);
-        // Record the supertype only if it is among the private types.
-        if ((it != typeInfo.end() &&
-             it->second.visibility == ModuleUtils::Visibility::Private) ||
-            additionalSet.count(*super)) {
-          privateSupertypes.back().second.push_back(*super);
-        }
-      }
-    }
-
-    // Topological sort to have subtypes first. This is the opposite of the
-    // order we need, so the comparison is the opposite of what we ultimately
-    // want.
-    std::vector<HeapType> sorted;
-    if (wasm.typeIndices.empty()) {
-      sorted = TopologicalSort::sortOf(privateSupertypes.begin(),
-                                       privateSupertypes.end());
-    } else {
-      sorted =
-        TopologicalSort::minSortOf(privateSupertypes.begin(),
-                                   privateSupertypes.end(),
-                                   [&](Index a, Index b) {
-                                     auto typeA = privateSupertypes[a].first;
-                                     auto typeB = privateSupertypes[b].first;
-                                     // Preserve type order.
-                                     auto itA = wasm.typeIndices.find(typeA);
-                                     auto itB = wasm.typeIndices.find(typeB);
-                                     bool hasA = itA != wasm.typeIndices.end();
-                                     bool hasB = itB != wasm.typeIndices.end();
-                                     if (hasA != hasB) {
-                                       // Types with preserved indices must be
-                                       // sorted before (after in this reversed
-                                       // comparison) types without indices to
-                                       // maintain transitivity.
-                                       return !hasA;
-                                     }
-                                     if (hasA && *itA != *itB) {
-                                       return !(itA->second < itB->second);
-                                     }
-                                     // Break ties by the arbitrary order we
-                                     // have collected the types in.
-                                     return a > b;
-                                   });
-    }
-    std::reverse(sorted.begin(), sorted.end());
-    Index i = 0;
-    for (auto type : sorted) {
-      typeIndices[type] = i++;
+  auto typeInfo = ModuleUtils::collectHeapTypeInfo(
+    wasm,
+    ModuleUtils::TypeInclusion::UsedIRTypes,
+    ModuleUtils::VisibilityHandling::FindVisibility);
+
+  std::unordered_set<HeapType> additionalSet(additionalPrivateTypes.begin(),
+                                             additionalPrivateTypes.end());
+
+  std::vector<std::pair<HeapType, SmallVector<HeapType, 1>>> privateSupertypes;
+  privateSupertypes.reserve(typeInfo.size());
+  for (auto& [type, info] : typeInfo) {
+    if (info.visibility != ModuleUtils::Visibility::Private &&
+        !additionalSet.count(type)) {
+      continue;
     }
-  } else {
-    // Old code path.
-
-    auto privateTypes = ModuleUtils::getPrivateHeapTypes(wasm);
-
-    if (!additionalPrivateTypes.empty()) {
-      // Only add additional private types that are not already in the list.
-      std::unordered_set<HeapType> privateTypesSet(privateTypes.begin(),
-                                                   privateTypes.end());
+    privateSupertypes.push_back({type, {}});
 
-      for (auto t : additionalPrivateTypes) {
-        if (!privateTypesSet.count(t)) {
-          privateTypes.push_back(t);
-          privateTypesSet.insert(t);
-        }
+    if (auto super = getDeclaredSuperType(type)) {
+      auto it = typeInfo.find(*super);
+      // Record the supertype only if it is among the private types.
+      if ((it != typeInfo.end() &&
+           it->second.visibility == ModuleUtils::Visibility::Private) ||
+          additionalSet.count(*super)) {
+        privateSupertypes.back().second.push_back(*super);
       }
     }
+  }
 
-    // Topological sort to have supertypes first, but we have to account for the
-    // fact that we may be replacing the supertypes to get the order correct.
-    struct SupertypesFirst
-      : HeapTypeOrdering::SupertypesFirstBase<SupertypesFirst> {
-      GlobalTypeRewriter& parent;
-
-      SupertypesFirst(GlobalTypeRewriter& parent) : parent(parent) {}
-      std::optional<HeapType> getDeclaredSuperType(HeapType type) {
-        return parent.getDeclaredSuperType(type);
-      }
-    };
-
-    SupertypesFirst sortedTypes(*this);
-    Index i = 0;
-    for (auto type : sortedTypes.sort(privateTypes)) {
-      typeIndices[type] = i++;
-    }
+  // Topological sort to have subtypes first. This is the opposite of the
+  // order we need, so the comparison is the opposite of what we ultimately
+  // want.
+  std::vector<HeapType> sorted;
+  if (wasm.typeIndices.empty()) {
+    sorted = TopologicalSort::sortOf(privateSupertypes.begin(),
+                                     privateSupertypes.end());
+  } else {
+    sorted =
+      TopologicalSort::minSortOf(privateSupertypes.begin(),
+                                 privateSupertypes.end(),
+                                 [&](Index a, Index b) {
+                                   auto typeA = privateSupertypes[a].first;
+                                   auto typeB = privateSupertypes[b].first;
+                                   // Preserve type order.
+                                   auto itA = wasm.typeIndices.find(typeA);
+                                   auto itB = wasm.typeIndices.find(typeB);
+                                   bool hasA = itA != wasm.typeIndices.end();
+                                   bool hasB = itB != wasm.typeIndices.end();
+                                   if (hasA != hasB) {
+                                     // Types with preserved indices must be
+                                     // sorted before (after in this reversed
+                                     // comparison) types without indices to
+                                     // maintain transitivity.
+                                     return !hasA;
+                                   }
+                                   if (hasA && *itA != *itB) {
+                                     return !(itA->second < itB->second);
+                                   }
+                                   // Break ties by the arbitrary order we
+                                   // have collected the types in.
+                                   return a > b;
+                                 });
+  }
+  std::reverse(sorted.begin(), sorted.end());
+  Index i = 0;
+  for (auto type : sorted) {
+    typeIndices[type] = i++;
   }
 
   if (typeIndices.size() == 0) {
@@ -168,7 +122,7 @@ GlobalTypeRewriter::TypeMap GlobalTypeRewriter::rebuildTypes(
   typeBuilder.createRecGroup(0, typeBuilder.size());
 
   // Create the temporary heap types.
-  Index i = 0;
+  i = 0;
   auto map = [&](HeapType type) -> HeapType {
     if (auto it = typeIndices.find(type); it != typeIndices.end()) {
       return typeBuilder[it->second];
diff --git a/src/passes/GlobalTypeOptimization.cpp b/src/passes/GlobalTypeOptimization.cpp
index eec8e206d..dac6fd7b6 100644
--- a/src/passes/GlobalTypeOptimization.cpp
+++ b/src/passes/GlobalTypeOptimization.cpp
@@ -171,8 +171,8 @@ struct GlobalTypeOptimization : public Pass {
     // fields in a supertype is a constraint on what subtypes can do. That is,
     // we decide for each supertype what the optimal order is, and consider that
     // fixed, and then subtypes can decide how to sort fields that they append.
-    HeapTypeOrdering::SupertypesFirst sorted;
-    for (auto type : sorted.sort(propagator.subTypes.types)) {
+    for (auto type :
+         HeapTypeOrdering::supertypesFirst(propagator.subTypes.types)) {
       if (!type.isStruct()) {
         continue;
       }
diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp
index 1cac7732f..206addd2f 100644
--- a/src/passes/TypeMerging.cpp
+++ b/src/passes/TypeMerging.cpp
@@ -142,6 +142,17 @@ struct TypeMerging : public Pass {
     return type;
   }
 
+  std::vector<HeapType>
+  mergeableSupertypesFirst(const std::vector<HeapType>& types) {
+    return HeapTypeOrdering::supertypesFirst(
+      types, [&](HeapType type) -> std::optional<HeapType> {
+        if (auto super = type.getDeclaredSuperType()) {
+          return getMerged(*super);
+        }
+        return std::nullopt;
+      });
+  }
+
   void run(Module* module_) override;
 
   // We will do two different kinds of merging: First, we will merge types into
@@ -163,20 +174,6 @@ struct TypeMerging : public Pass {
   void applyMerges();
 };
 
-struct MergeableSupertypesFirst
-  : HeapTypeOrdering::SupertypesFirstBase<MergeableSupertypesFirst> {
-  TypeMerging& merging;
-
-  MergeableSupertypesFirst(TypeMerging& merging) : merging(merging) {}
-
-  std::optional<HeapType> getDeclaredSuperType(HeapType type) {
-    if (auto super = type.getDeclaredSuperType()) {
-      return merging.getMerged(*super);
-    }
-    return std::nullopt;
-  }
-};
-
 // Hash and equality-compare HeapTypes based on their top-level structure (i.e.
 // "shape"), ignoring nontrivial heap type children that will not be
 // differentiated between until we run the DFA partition refinement.
@@ -305,8 +302,7 @@ bool TypeMerging::merge(MergeKind kind) {
 
   // For each type, either create a new partition or add to its supertype's
   // partition.
-  MergeableSupertypesFirst sortedTypes(*this);
-  for (auto type : sortedTypes.sort(mergeable)) {
+  for (auto type : mergeableSupertypesFirst(mergeable)) {
     // We need partitions for any public children of this type since those
     // children will participate in the DFA we're creating.
     for (auto child : getPublicChildren(type)) {
@@ -414,7 +410,7 @@ bool TypeMerging::merge(MergeKind kind) {
   std::vector<HeapType> newMergeable;
   bool merged = false;
   for (const auto& partition : refinedPartitions) {
-    auto target = *MergeableSupertypesFirst(*this).sort(partition).begin();
+    auto target = mergeableSupertypesFirst(partition).front();
     newMergeable.push_back(target);
     for (auto type : partition) {
       if (type != target) {
@@ -452,8 +448,7 @@ TypeMerging::splitSupertypePartition(const std::vector<HeapType>& types) {
   std::unordered_set<HeapType> includedTypes(types.begin(), types.end());
   std::vector<std::vector<HeapType>> partitions;
   std::unordered_map<HeapType, Index> partitionIndices;
-  MergeableSupertypesFirst sortedTypes(*this);
-  for (auto type : sortedTypes.sort(types)) {
+  for (auto type : mergeableSupertypesFirst(types)) {
     auto super = type.getDeclaredSuperType();
     if (super && includedTypes.count(*super)) {
       // We must already have a partition for the supertype we can add to.
diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp
index d74790b2a..464654d4f 100644
--- a/src/tools/wasm-ctor-eval.cpp
+++ b/src/tools/wasm-ctor-eval.cpp
@@ -36,9 +36,9 @@
 #include "support/colors.h"
 #include "support/file.h"
 #include "support/insert_ordered.h"
-#include "support/old_topological_sort.h"
 #include "support/small_set.h"
 #include "support/string.h"
+#include "support/topological_sort.h"
 #include "tool-options.h"
 #include "wasm-builder.h"
 #include "wasm-interpreter.h"
@@ -609,9 +609,9 @@ private:
     Builder builder(*wasm);
 
     // First, find what constraints we have on the ordering of the globals. We
-    // will build up a map of each global to the globals it must be after.
-    using MustBeAfter = InsertOrderedMap<Name, InsertOrderedSet<Name>>;
-    MustBeAfter mustBeAfter;
+    // will build up a map of each global to the globals it must be before.
+    using MustBeBefore = InsertOrderedMap<Name, InsertOrderedSet<Name>>;
+    MustBeBefore mustBeBefore;
 
     for (auto& global : wasm->globals) {
       if (!global->init) {
@@ -672,31 +672,12 @@ private:
 
       // Any global.gets that cannot be fixed up are constraints.
       for (auto* get : scanner.unfixableGets) {
-        mustBeAfter[global->name].insert(get->name);
+        mustBeBefore[global->name];
+        mustBeBefore[get->name].insert(global->name);
       }
     }
 
-    if (!mustBeAfter.empty()) {
-      // We found constraints that require reordering, so do so.
-      struct MustBeAfterSort : OldTopologicalSort<Name, MustBeAfterSort> {
-        MustBeAfter& mustBeAfter;
-
-        MustBeAfterSort(MustBeAfter& mustBeAfter) : mustBeAfter(mustBeAfter) {
-          for (auto& [global, _] : mustBeAfter) {
-            push(global);
-          }
-        }
-
-        void pushPredecessors(Name global) {
-          auto iter = mustBeAfter.find(global);
-          if (iter != mustBeAfter.end()) {
-            for (auto other : iter->second) {
-              push(other);
-            }
-          }
-        }
-      };
-
+    if (!mustBeBefore.empty()) {
       auto oldGlobals = std::move(wasm->globals);
       // After clearing the globals vector, clear the map as well.
       wasm->updateMaps();
@@ -706,7 +687,8 @@ private:
         globalIndexes[oldGlobals[i]->name] = i;
       }
       // Add the globals that had an important ordering, in the right order.
-      for (auto global : MustBeAfterSort(mustBeAfter)) {
+      for (auto global :
+           TopologicalSort::sortOf(mustBeBefore.begin(), mustBeBefore.end())) {
         wasm->addGlobal(std::move(oldGlobals[globalIndexes[global]]));
       }
       // Add all other globals after them.
diff --git a/src/wasm-type-ordering.h b/src/wasm-type-ordering.h
index 9ccf4c568..0f23b4953 100644
--- a/src/wasm-type-ordering.h
+++ b/src/wasm-type-ordering.h
@@ -20,58 +20,34 @@
 #include <unordered_set>
 
 #include "support/insert_ordered.h"
-#include "support/old_topological_sort.h"
+#include "support/topological_sort.h"
 #include "wasm-type.h"
 
 namespace wasm::HeapTypeOrdering {
 
-// Given a collection of types, iterate through it such that each type in the
-// collection is visited only after its immediate supertype in the collection is
-// visited.
-template<typename SupertypeProvider>
-struct SupertypesFirstBase
-  : OldTopologicalSort<HeapType, SupertypesFirstBase<SupertypeProvider>> {
-  // For each type in the input collection, whether it is a supertype. Used to
-  // track membership in the input collection.
-  InsertOrderedMap<HeapType, bool> typeSet;
-
-  SupertypeProvider& self() { return *static_cast<SupertypeProvider*>(this); }
-
-  template<typename T> SupertypeProvider& sort(const T& types) {
-    for (auto type : types) {
-      typeSet[type] = false;
-    }
-    // Find the supertypes that are in the collection.
-    for (auto [type, _] : typeSet) {
-      if (auto super = self().getDeclaredSuperType(type)) {
-        if (auto it = typeSet.find(*super); it != typeSet.end()) {
-          it->second = true;
-        }
-      }
-    }
-    // Types that are not supertypes of others are the roots.
-    for (auto [type, isSuper] : typeSet) {
-      if (!isSuper) {
-        this->push(type);
-      }
-    }
-    return self();
+// Given a collection of types, return a sequence of the types such that each
+// type in the sequence comes only after its immediate supertype in the
+// collection is visited.
+template<typename T>
+std::vector<HeapType> supertypesFirst(
+  const T& types,
+  std::function<std::optional<HeapType>(HeapType)> getSuper =
+    [](HeapType type) { return type.getDeclaredSuperType(); }) {
+
+  InsertOrderedMap<HeapType, std::vector<HeapType>> subtypes;
+  for (auto type : types) {
+    subtypes.insert({type, {}});
   }
-
-  void pushPredecessors(HeapType type) {
-    // Do not visit types that weren't in the input collection.
-    if (auto super = self().getDeclaredSuperType(type);
-        super && typeSet.count(*super)) {
-      this->push(*super);
+  // Find the supertypes that are in the collection.
+  for (auto [type, _] : subtypes) {
+    if (auto super = getSuper(type)) {
+      if (auto it = subtypes.find(*super); it != subtypes.end()) {
+        it->second.push_back(type);
+      }
     }
   }
-};
-
-struct SupertypesFirst : SupertypesFirstBase<SupertypesFirst> {
-  std::optional<HeapType> getDeclaredSuperType(HeapType type) {
-    return type.getDeclaredSuperType();
-  }
-};
+  return TopologicalSort::sortOf(subtypes.begin(), subtypes.end());
+}
 
 } // namespace wasm::HeapTypeOrdering