determinism fix for code-folding (WebAssembly#1852)

kripken · web-flow · commit 34fbbb3dde9f · 2019-01-08T09:55:24.000-08:00
Don't depend on the hash values for ordering - use a fixed order based on order of appearance.
diff --git a/src/passes/CodeFolding.cpp b/src/passes/CodeFolding.cpp
@@ -524,13 +524,21 @@ struct CodeFolding : public WalkerPass<ControlFlowWalker<CodeFolding>> {
     // 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
@@ -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
@@ -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
@@ -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)
  )

Original file line number	Diff line number	Diff line change
`@@ -1069,19 +1069,19 @@`
`1069`	`1069`	`(block`
`1070`	`1070`	`(if`
`1071`	`1071`	`(i32.const 1)`
`1072`		`- (br $folding-inner1)`
	`1072`	`+ (br $folding-inner0)`
`1073`	`1073`	`)`
`1074`	`1074`	`(if`
`1075`	`1075`	`(i32.const 1)`
`1076`		`- (br $folding-inner1)`
	`1076`	`+ (br $folding-inner0)`
`1077`	`1077`	`)`
`1078`	`1078`	`(if`
`1079`	`1079`	`(i32.const 1)`
`1080`		`- (br $folding-inner0)`
	`1080`	`+ (br $folding-inner1)`
`1081`	`1081`	`)`
`1082`	`1082`	`(if`
`1083`	`1083`	`(i32.const 1)`
`1084`		`- (br $folding-inner0)`
	`1084`	`+ (br $folding-inner1)`
`1085`	`1085`	`)`
`1086`	`1086`	`)`
`1087`	`1087`	`(return)`
`@@ -1098,7 +1098,7 @@`
`1098`	`1098`	`(nop)`
`1099`	`1099`	`(nop)`
`1100`	`1100`	`(drop`
`1101`		`- (i32.const 2)`
	`1101`	`+ (i32.const 1)`
`1102`	`1102`	`)`
`1103`	`1103`	`(unreachable)`
`1104`	`1104`	`)`
`@@ -1115,7 +1115,7 @@`
`1115`	`1115`	`(nop)`
`1116`	`1116`	`(nop)`
`1117`	`1117`	`(drop`
`1118`		`- (i32.const 1)`
	`1118`	`+ (i32.const 2)`
`1119`	`1119`	`)`
`1120`	`1120`	`(unreachable)`
`1121`	`1121`	`)`