[OptimizeInstructions] Fix fuzz bug with shifts (#3376)

The code there looks for a "sign-extend": (x << a) >> b where the
right shift is signed. If a = b = 24 for example then that is a sign
extend of an 8-bit value (it works by shifting the 8-bit value's sign bit
to the position of the 32-bit value's sign bit, then shifting all the way
back, which fills everything above 8 bits with the sign bit). The tricky
thing is that in some cases we can handle a != b - but we forgot a
place to check that. Specifically, a repeated sign-extend is not
necessary, but if the outer one has extra shifts, we can't do it.

This is annoyingly complex code, but for purposes of reviewing this
PR, you can see (unless I messed up) that the only change is to
ensure that when we look for a repeated sign extend, then we
only optimize that case when there are no extra shifts. And a
repeated sign-extend is obviously ok to remove,

(((x << a) >> a) << a) >> a   =>   (x << a) >> a

This is an ancient bug, showing how hard it can be to find certain
patterns either by fuzzing or in the real world...

Fixes #3362

1 files changed, 25 insertions, 0 deletions

diff --git a/test/passes/optimize-instructions_fuzz-exec.wast b/test/passes/optimize-instructions_fuzz-exec.wast
index 8bd43b694..87b6eb594 100644
--- a/test/passes/optimize-instructions_fuzz-exec.wast
+++ b/test/passes/optimize-instructions_fuzz-exec.wast
@@ -287,6 +287,31 @@
    )
   )
  )
+ (func $shift (param $0 i32)
+  (call $log
+   ;; x << 24 >> 24 << 30 >> 24 - the extra shifts make it invalid to do the
+   ;; optimization of not repeating a sign-extend. That is, this would be valid
+   ;; if the 30 were replaced by a 24.
+   (i32.shr_s
+    (i32.shl
+     (i32.shr_s
+      (i32.shl
+       (local.get $0)
+       (i32.const 24)
+      )
+      (i32.const 24)
+     )
+     (i32.const 30)
+    )
+    (i32.const 24)
+   )
+  )
+ )
+ (func "do-shift"
+  (call $shift
+   (i32.const 65419)
+  )
+ )
  ;; similar, but with the value compared to having the sign bit set but no
  ;; upper bits
  (func $compare-maybe-signed-eq (param $0 i32) (result i32)