[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, 14 insertions, 8 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 2ca670f89..2b0a95fc7 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -468,9 +468,9 @@ struct OptimizeInstructions
 
     if (auto* binary = curr->dynCast<Binary>()) {
       if (auto* ext = Properties::getAlmostSignExt(binary)) {
-        Index extraShifts;
-        auto bits = Properties::getAlmostSignExtBits(binary, extraShifts);
-        if (extraShifts == 0) {
+        Index extraLeftShifts;
+        auto bits = Properties::getAlmostSignExtBits(binary, extraLeftShifts);
+        if (extraLeftShifts == 0) {
           if (auto* load =
                 Properties::getFallthrough(ext, getPassOptions(), features)
                   ->dynCast<Load>()) {
@@ -488,11 +488,17 @@ struct OptimizeInstructions
             }
           }
         }
-        // if the sign-extend input cannot have a sign bit, we don't need it
-        // we also don't need it if it already has an identical-sized sign
-        // extend
-        if (Bits::getMaxBits(ext, this) + extraShifts < bits ||
-            isSignExted(ext, bits)) {
+        // We can in some cases remove part of a sign extend, that is,
+        //   (x << A) >> B   =>   x << (A - B)
+        // If the sign-extend input cannot have a sign bit, we don't need it.
+        if (Bits::getMaxBits(ext, this) + extraLeftShifts < bits) {
+          return removeAlmostSignExt(binary);
+        }
+        // We also don't need it if it already has an identical-sized sign
+        // extend applied to it. That is, if it is already a sign-extended
+        // value, then another sign extend will do nothing. We do need to be
+        // careful of the extra shifts, though.
+        if (isSignExted(ext, bits) && extraLeftShifts == 0) {
           return removeAlmostSignExt(binary);
         }
       } else if (binary->op == EqInt32 || binary->op == NeInt32) {