OptimizeInstructions: Fix regression from #3303 / #3275 (#3338)

X - Y <= 0

=>

X <= Y

That is true mathematically, but not in the case of an overflow, e.g.
X=10, Y=0x8000000000000000. X - Y is a negative number, so
X - Y <= 0 is true. But it is not true that X <= Y (as Y is negative, but
X is not).

See discussion in #3303 (comment)

The actual regression was in #3275, but the fuzzer had an easier time
finding it due to #3303

4 files changed, 107 insertions, 15 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 51a188c15..83bee9a0f 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -1965,17 +1965,16 @@ private:
           curr->left = inner->left;
           return curr;
         }
-        // signed(x - y) <=> 0  =>  x <=> y
+        // x - y == 0  =>  x == y
+        // x - y != 0  =>  x != y
+        // This is not true for signed comparisons like x -y < 0 due to overflow
+        // effects (e.g. 8 - 0x80000000 < 0 is not the same as 8 < 0x80000000).
         if (matches(curr,
                     binary(&op,
                            binary(&inner, Abstract::Sub, any(), any()),
                            ival(0))) &&
             (op == Abstract::getBinary(type, Abstract::Eq) ||
-             op == Abstract::getBinary(type, Abstract::Ne) ||
-             op == Abstract::getBinary(type, Abstract::LeS) ||
-             op == Abstract::getBinary(type, Abstract::LtS) ||
-             op == Abstract::getBinary(type, Abstract::GeS) ||
-             op == Abstract::getBinary(type, Abstract::GtS))) {
+             op == Abstract::getBinary(type, Abstract::Ne))) {
           curr->right = inner->right;
           curr->left = inner->left;
           return curr;
diff --git a/test/passes/optimize-instructions_all-features.txt b/test/passes/optimize-instructions_all-features.txt
index 88b053835..7d223020f 100644
--- a/test/passes/optimize-instructions_all-features.txt
+++ b/test/passes/optimize-instructions_all-features.txt
@@ -4784,14 +4784,20 @@
   )
   (drop
    (i32.gt_s
-    (local.get $x)
-    (local.get $y)
+    (i32.sub
+     (local.get $x)
+     (local.get $y)
+    )
+    (i32.const 0)
    )
   )
   (drop
    (i32.ge_s
-    (local.get $x)
-    (local.get $y)
+    (i32.sub
+     (local.get $x)
+     (local.get $y)
+    )
+    (i32.const 0)
    )
   )
   (drop
@@ -4808,14 +4814,20 @@
   )
   (drop
    (i32.lt_s
-    (local.get $x)
-    (local.get $y)
+    (i32.sub
+     (local.get $x)
+     (local.get $y)
+    )
+    (i32.const 0)
    )
   )
   (drop
    (i32.le_s
-    (local.get $x)
-    (local.get $y)
+    (i32.sub
+     (local.get $x)
+     (local.get $y)
+    )
+    (i32.const 0)
    )
   )
   (drop
diff --git a/test/passes/optimize-instructions_fuzz-exec.txt b/test/passes/optimize-instructions_fuzz-exec.txt
index 548148e09..5da803fb1 100644
--- a/test/passes/optimize-instructions_fuzz-exec.txt
+++ b/test/passes/optimize-instructions_fuzz-exec.txt
@@ -253,3 +253,41 @@
 [LoggingExternalInterface logging nan:0x400000]
 [LoggingExternalInterface logging nan:0x400000]
 [LoggingExternalInterface logging nan:0x400000]
+[fuzz-exec] calling foo
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
+(module
+ (type $i32_=>_none (func (param i32)))
+ (import "fuzzing-support" "log-i32" (func $log (param i32)))
+ (export "foo" (func $0))
+ (func $0 (param $0 i32)
+  (call $log
+   (i32.le_s
+    (i32.sub
+     (i32.const 8)
+     (block $label$1 (result i32)
+      (i32.const -2147483648)
+     )
+    )
+    (i32.const 0)
+   )
+  )
+  (call $log
+   (i32.le_s
+    (i32.const -2147483640)
+    (i32.const 0)
+   )
+  )
+  (call $log
+   (i32.eq
+    (i32.const 8)
+    (i32.const -2147483648)
+   )
+  )
+ )
+)
+[fuzz-exec] calling foo
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
diff --git a/test/passes/optimize-instructions_fuzz-exec.wast b/test/passes/optimize-instructions_fuzz-exec.wast
index 317db04e4..8d2e1beee 100644
--- a/test/passes/optimize-instructions_fuzz-exec.wast
+++ b/test/passes/optimize-instructions_fuzz-exec.wast
@@ -203,4 +203,47 @@
   )
  )
 )
-
+(module
+ (import "fuzzing-support" "log-i32" (func $log (param i32)))
+ (func "foo" (param $0 i32)
+  ;; 8 - 0x80000000 < 0
+  ;;
+  ;; is not the same as
+  ;;
+  ;; 8 < 0x80000000
+  ;;
+  ;; because of overflow. the former is true, the latter is false
+  (call $log
+   (i32.le_s
+    (i32.sub
+     (i32.const 8)
+     (block $label$1 (result i32) ;; the block prevents us from optimizing this
+                                  ;; which would avoid the issue. a global or a
+                                  ;; call would do the same, all would make the
+                                  ;; value only visible at runtime
+      (i32.const 0x80000000)
+     )
+    )
+    (i32.const 0)
+   )
+  )
+  ;; for comparison, without the block.
+  (call $log
+   (i32.le_s
+    (i32.sub
+     (i32.const 8)
+     (i32.const 0x80000000)
+    )
+    (i32.const 0)
+   )
+  )
+  ;; for comparison, what X - Y < 0 => X < Y would lead to, which has a
+  ;; different value
+  (call $log
+   (i32.le_s
+    (i32.const 8)
+    (i32.const 0x80000000)
+   )
+  )
+ )
+)