Ordering correction fix in OptimizeInstructions for #3047 (#3195)

(found by the fuzzer)

It is not valid to replace x | (y | x) ==> y | x, if x, y cannot be reordered.

It is also not valid to replace x ^ (y ^ x) ==> y, if x, y cannot be reordered,
for a more subtle reason: if they cannot be reordered then y can affect the
value of x (the opposite is not possible as we checked x for side effects so
that we could remove one copy). If so, then the second appearance of x
could be different, if e.g. it reads a local y writes to. Whereas, if it's ok to
reorder, then it's ok to do x ^ (y ^ x) ==> x ^ (x ^ y) ==> y.

3 files changed, 103 insertions, 3 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 869512774..79315ac6d 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -1591,14 +1591,22 @@ private:
                 return inner;
               }
             }
-            if (ExpressionAnalyzer::equal(inner->right, outer->left)) {
+            if (ExpressionAnalyzer::equal(inner->right, outer->left) &&
+                canReorder(outer->left, inner->left)) {
               // x ^ (y ^ x)  ==>   y
+              // (note that we need the check for reordering here because if
+              // e.g. y writes to a local that x reads, the second appearance
+              // of x would be different from the first)
               if (outer->op == Abstract::getBinary(type, Abstract::Xor)) {
                 return inner->left;
               }
 
               // x & (y & x)  ==>   y & x
               // x | (y | x)  ==>   y | x
+              // (here we need the check for reordering for the more obvious
+              // reason that previously x appeared before y, and now y appears
+              // first; or, if we tried to emit x [&|] y here, reversing the
+              // order, we'd be in the same situation as the previous comment)
               if (outer->op == Abstract::getBinary(type, Abstract::And) ||
                   outer->op == Abstract::getBinary(type, Abstract::Or)) {
                 return inner;
@@ -1627,7 +1635,9 @@ private:
                 return inner;
               }
             }
-            if (ExpressionAnalyzer::equal(inner->left, outer->right)) {
+            // See comments in the parallel code earlier about ordering here.
+            if (ExpressionAnalyzer::equal(inner->left, outer->right) &&
+                canReorder(inner->left, inner->right)) {
               // (x ^ y) ^ x  ==>   y
               if (outer->op == Abstract::getBinary(type, Abstract::Xor)) {
                 return inner->right;
diff --git a/test/passes/optimize-instructions_all-features.txt b/test/passes/optimize-instructions_all-features.txt
index 5bbaccfea..ee6b1162a 100644
--- a/test/passes/optimize-instructions_all-features.txt
+++ b/test/passes/optimize-instructions_all-features.txt
@@ -4319,6 +4319,50 @@
     )
    )
   )
+  (drop
+   (i32.or
+    (local.get $x)
+    (i32.or
+     (local.tee $x
+      (i32.const 1)
+     )
+     (local.get $x)
+    )
+   )
+  )
+  (drop
+   (i32.or
+    (i32.or
+     (local.get $x)
+     (local.tee $x
+      (i32.const 1)
+     )
+    )
+    (local.get $x)
+   )
+  )
+  (drop
+   (i32.xor
+    (local.get $x)
+    (i32.xor
+     (local.tee $x
+      (i32.const 1)
+     )
+     (local.get $x)
+    )
+   )
+  )
+  (drop
+   (i32.xor
+    (i32.xor
+     (local.get $x)
+     (local.tee $x
+      (i32.const 1)
+     )
+    )
+    (local.get $x)
+   )
+  )
  )
  (func $optimize-bulk-memory-copy (param $dst i32) (param $src i32) (param $sz i32)
   (memory.copy
diff --git a/test/passes/optimize-instructions_all-features.wast b/test/passes/optimize-instructions_all-features.wast
index c8a48391c..71646de93 100644
--- a/test/passes/optimize-instructions_all-features.wast
+++ b/test/passes/optimize-instructions_all-features.wast
@@ -4805,7 +4805,53 @@
         (local.get $x)
         (local.get $y)
       )
-    ))
+     ))
+    ;; x | (y | x)   where x and y cannot be reordered  -  skip
+    (drop
+      (i32.or
+        (local.get $x)
+        (i32.or
+          (local.tee $x
+            (i32.const 1)
+          )
+          (local.get $x)
+        )
+      )
+    )
+    (drop
+      (i32.or
+        (i32.or
+          (local.get $x)
+          (local.tee $x
+            (i32.const 1)
+          )
+        )
+        (local.get $x)
+      )
+    )
+    ;; x ^ (y ^ x)   where x and y cannot be reordered  -  skip
+    (drop
+      (i32.xor
+        (local.get $x)
+        (i32.xor
+          (local.tee $x
+            (i32.const 1)
+          )
+          (local.get $x)
+        )
+      )
+    )
+    (drop
+      (i32.xor
+        (i32.xor
+          (local.get $x)
+          (local.tee $x
+            (i32.const 1)
+          )
+        )
+        (local.get $x)
+      )
+    )
   )
   (func $optimize-bulk-memory-copy (param $dst i32) (param $src i32) (param $sz i32)
     (memory.copy  ;; skip