diff options
| -rw-r--r-- | src/ir/module-utils.h | 2 | ||||
| -rw-r--r-- | src/wasm/wasm-type.cpp | 14 | ||||
| -rw-r--r-- | test/lit/recursive-type-sort.wast | 29 |
3 files changed, 37 insertions, 8 deletions
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h index 4792c5d23..371239e19 100644 --- a/src/ir/module-utils.h +++ b/src/ir/module-utils.h @@ -550,7 +550,7 @@ inline void collectHeapTypes(Module& wasm, // Sort by frequency and then simplicity. std::vector<std::pair<HeapType, size_t>> sorted(counts.begin(), counts.end()); - std::sort(sorted.begin(), sorted.end(), [&](auto a, auto b) { + std::stable_sort(sorted.begin(), sorted.end(), [&](auto a, auto b) { if (a.second != b.second) { return a.second > b.second; } diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp index 8546e3fc9..e4e7d31a4 100644 --- a/src/wasm/wasm-type.cpp +++ b/src/wasm/wasm-type.cpp @@ -100,8 +100,8 @@ struct HeapTypeInfo { // Helper for coinductively comparing Types and HeapTypes according to some // arbitrary notion of complexity. struct TypeComparator { - // Set of HeapTypes we are assuming satisfy the relation as long as we cannot - // prove otherwise. + // Set of HeapTypes we are assuming are equivalent as long as we cannot prove + // otherwise. std::unordered_set<std::pair<HeapType, HeapType>> seen; bool lessThan(Type a, Type b); bool lessThan(HeapType a, HeapType b); @@ -118,8 +118,8 @@ struct TypeComparator { // Helper for coinductively checking whether a pair of Types or HeapTypes are in // a subtype relation. struct SubTyper { - // Set of HeapTypes we are assuming satisfy the relation as long as we cannot - // prove otherwise. + // Set of HeapTypes we are assuming are equivalent as long as we cannot prove + // otherwise. std::unordered_set<std::pair<HeapType, HeapType>> seen; bool isSubType(Type a, Type b); bool isSubType(HeapType a, HeapType b); @@ -858,9 +858,9 @@ bool TypeComparator::lessThan(HeapType a, HeapType b) { return false; } if (seen.count({a, b})) { - // We weren't able to disprove that a < b since we last saw them, so the - // relation holds coinductively. - return true; + // We weren't able to disprove that a == b since we last saw them, so it + // holds coinductively that a < b is false. + return false; } if (a.isBasic() && b.isBasic()) { return a.getBasic() < b.getBasic(); diff --git a/test/lit/recursive-type-sort.wast b/test/lit/recursive-type-sort.wast new file mode 100644 index 000000000..087cb7fe6 --- /dev/null +++ b/test/lit/recursive-type-sort.wast @@ -0,0 +1,29 @@ +;; Test that multiple recursive types are sorted and emitted properly. +;; Regression test for a bug in TypeComparator that made it fail to properly +;; implement the C++ Compare requirements. See #3648. + +;; RUN: wasm-opt %s -all --roundtrip -S -o - | filecheck %s + +;; Check that there's no crash. +;; CHECK: module + +(module + (type $a (func (param (ref null $b)))) + (type $b (struct (field (ref null $i)))) + (type $c (struct (field (ref null $l)))) + (type $d (func (param (ref null $b)))) + (type $e (func (result (ref null $g)))) + (type $f (func (result (ref null $c)))) + (type $g (struct (field (ref null $j)))) + (type $h (struct (field (ref null $k)))) + (type $i (struct (field (mut (ref null $a))))) + (type $j (struct (field (mut (ref null $a))) (field (mut (ref null $a))))) + (type $k (struct (field (mut (ref null $a))) (field (mut (ref null $a))) (field (mut (ref null $e))))) + (type $l (struct (field (mut (ref null $a))) (field (mut (ref null $d))) (field (mut (ref null $f))))) + + (func $foo + (local $1 (ref null $h)) + (local $2 (ref null $b)) + (local $3 (ref null $c)) + ) +) |