determinism fix for code-folding (#1852)

Don't depend on the hash values for ordering - use a fixed order based on order of appearance.

4 files changed, 109 insertions, 10 deletions

diff --git a/src/passes/CodeFolding.cpp b/src/passes/CodeFolding.cpp
index b639c7681..a79980cfe 100644
--- a/src/passes/CodeFolding.cpp
+++ b/src/passes/CodeFolding.cpp
@@ -524,13 +524,21 @@ private:
     // if we have enough to investigate, do so
     if (next.size() >= 2) {
       // now we want to find a mergeable item - any item that is equal among a subset
-      std::map<uint32_t, std::vector<Expression*>> hashed; // hash value => expressions with that hash
+      std::map<Expression*, HashType> hashes; // expression => hash value
+      std::map<HashType, std::vector<Expression*>> hashed; // hash value => expressions with that hash
       for (auto& tail : next) {
         auto* item = getItem(tail, num);
-        hashed[ExpressionAnalyzer::hash(item)].push_back(item);
+        auto hash = hashes[item] = ExpressionAnalyzer::hash(item);
+        hashed[hash].push_back(item);
       }
-      for (auto& iter : hashed) {
-        auto& items = iter.second;
+      // look at each hash value exactly once. we do this in a deterministic order.
+      std::set<HashType> seen;
+      for (auto& tail : next) {
+        auto* item = getItem(tail, num);
+        auto hash = hashes[item];
+        if (seen.count(hash)) continue;
+        seen.insert(hash);
+        auto& items = hashed[hash];
         if (items.size() == 1) continue;
         assert(items.size() > 0);
         // look for an item that has another match.
diff --git a/test/passes/code-folding.txt b/test/passes/code-folding.txt
index bb7e765ef..f879217aa 100644
--- a/test/passes/code-folding.txt
+++ b/test/passes/code-folding.txt
@@ -140,3 +140,45 @@
   )
  )
 )
+(module
+ (type $0 (func))
+ (global $global$0 (mut i32) (i32.const 10))
+ (func $determinism (; 0 ;) (type $0)
+  (block $folding-inner0
+   (block
+    (block $label$1
+     (br_if $label$1
+      (i32.const 1)
+     )
+     (br $folding-inner0)
+    )
+    (block $label$2
+     (br_if $label$2
+      (i32.const 0)
+     )
+     (if
+      (get_global $global$0)
+      (block $block
+       (br $folding-inner0)
+      )
+     )
+     (unreachable)
+    )
+    (if
+     (get_global $global$0)
+     (block $block1
+      (br $folding-inner0)
+     )
+    )
+    (unreachable)
+   )
+  )
+  (set_global $global$0
+   (i32.sub
+    (get_global $global$0)
+    (i32.const 1)
+   )
+  )
+  (unreachable)
+ )
+)
diff --git a/test/passes/code-folding.wast b/test/passes/code-folding.wast
index 9a893a347..2034f1452 100644
--- a/test/passes/code-folding.wast
+++ b/test/passes/code-folding.wast
@@ -150,4 +150,53 @@
   )
  )
 )
+(module
+ (type $0 (func))
+ (global $global$0 (mut i32) (i32.const 10))
+ (func $determinism (; 0 ;) (type $0)
+  (block $label$1
+   (br_if $label$1
+    (i32.const 1)
+   )
+   (set_global $global$0
+    (i32.sub
+     (get_global $global$0)
+     (i32.const 1)
+    )
+   )
+   (unreachable)
+  )
+  (block $label$2
+   (br_if $label$2
+    (i32.const 0)
+   )
+   (if
+    (get_global $global$0)
+    (block
+     (set_global $global$0
+      (i32.sub
+       (get_global $global$0)
+       (i32.const 1)
+      )
+     )
+     (unreachable)
+    )
+   )
+   (unreachable)
+  )
+  (if
+   (get_global $global$0)
+   (block
+    (set_global $global$0
+     (i32.sub
+      (get_global $global$0)
+      (i32.const 1)
+     )
+    )
+    (unreachable)
+   )
+  )
+  (unreachable)
+ )
+)
 
diff --git a/test/passes/remove-unused-names_code-folding.txt b/test/passes/remove-unused-names_code-folding.txt
index 8590836ee..85750e06d 100644
--- a/test/passes/remove-unused-names_code-folding.txt
+++ b/test/passes/remove-unused-names_code-folding.txt
@@ -1069,19 +1069,19 @@
      (block
       (if
        (i32.const 1)
-       (br $folding-inner1)
+       (br $folding-inner0)
       )
       (if
        (i32.const 1)
-       (br $folding-inner1)
+       (br $folding-inner0)
       )
       (if
        (i32.const 1)
-       (br $folding-inner0)
+       (br $folding-inner1)
       )
       (if
        (i32.const 1)
-       (br $folding-inner0)
+       (br $folding-inner1)
       )
      )
      (return)
@@ -1098,7 +1098,7 @@
     (nop)
     (nop)
     (drop
-     (i32.const 2)
+     (i32.const 1)
     )
     (unreachable)
    )
@@ -1115,7 +1115,7 @@
   (nop)
   (nop)
   (drop
-   (i32.const 1)
+   (i32.const 2)
   )
   (unreachable)
  )