Implement signed 64-bit shift right for wasm2asm (#1544)

Mostly piggy-back pon the previous 64-bit shift lowering code, just filling in a
few gaps.

3 files changed, 268 insertions, 6 deletions

diff --git a/src/passes/I64ToI32Lowering.cpp b/src/passes/I64ToI32Lowering.cpp
index b051642f6..759e5e265 100644
--- a/src/passes/I64ToI32Lowering.cpp
+++ b/src/passes/I64ToI32Lowering.cpp
@@ -971,6 +971,30 @@ struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
     );
   }
 
+  // a >> b where `b` >= 32
+  //
+  // implement as:
+  //
+  // hi = leftHigh >> 31 // copy sign bit
+  // lo = leftHigh >> (b - 32)
+  Block* makeLargeShrS(Index highBits, Index leftHigh, Index shift) {
+    return builder->blockify(
+      builder->makeSetLocal(
+        highBits,
+        builder->makeBinary(
+          ShrSInt32,
+          builder->makeGetLocal(leftHigh, i32),
+          builder->makeConst(Literal(int32_t(31)))
+        )
+      ),
+      builder->makeBinary(
+        ShrSInt32,
+        builder->makeGetLocal(leftHigh, i32),
+        builder->makeGetLocal(shift, i32)
+      )
+    );
+  }
+
   Block* makeLargeShrU(Index highBits, Index leftHigh, Index shift) {
     return builder->blockify(
       builder->makeSetLocal(highBits, builder->makeConst(Literal(int32_t(0)))),
@@ -1011,6 +1035,41 @@ struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
     );
   }
 
+  // a >> b where `b` < 32
+  //
+  // implement as:
+  //
+  // hi = leftHigh >> b
+  // lo = (leftLow >>> b) | (leftHigh << (32 - b))
+  Block* makeSmallShrS(Index highBits, Index leftLow, Index leftHigh,
+                       Index shift, Binary* shiftMask, Binary* widthLessShift) {
+    Binary* shiftedInBits = builder->makeBinary(
+      ShlInt32,
+      builder->makeBinary(
+        AndInt32,
+        shiftMask,
+        builder->makeGetLocal(leftHigh, i32)
+      ),
+      widthLessShift
+    );
+    Binary* shiftLow = builder->makeBinary(
+      ShrUInt32,
+      builder->makeGetLocal(leftLow, i32),
+      builder->makeGetLocal(shift, i32)
+    );
+    return builder->blockify(
+      builder->makeSetLocal(
+        highBits,
+        builder->makeBinary(
+          ShrSInt32,
+          builder->makeGetLocal(leftHigh, i32),
+          builder->makeGetLocal(shift, i32)
+        )
+      ),
+      builder->makeBinary(OrInt32, shiftedInBits, shiftLow)
+    );
+  }
+
   Block* makeSmallShrU(Index highBits, Index leftLow, Index leftHigh,
                        Index shift, Binary* shiftMask, Binary* widthLessShift) {
     Binary* shiftedInBits = builder->makeBinary(
@@ -1040,9 +1099,9 @@ struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
     );
   }
 
-  Block* lowerShU(BinaryOp op, Block* result, TempVar&& leftLow,
-                  TempVar&& leftHigh, TempVar&& rightLow, TempVar&& rightHigh) {
-    assert(op == ShlInt64 || op == ShrUInt64);
+  Block* lowerShift(BinaryOp op, Block* result, TempVar&& leftLow,
+                    TempVar&& leftHigh, TempVar&& rightLow, TempVar&& rightHigh) {
+    assert(op == ShlInt64 || op == ShrUInt64 || op == ShrSInt64);
     // shift left lowered as:
     // if 32 <= rightLow % 64:
     //     high = leftLow << k; low = 0
@@ -1072,6 +1131,8 @@ struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
     switch (op) {
       case ShlInt64:
         largeShiftBlock = makeLargeShl(rightHigh, leftLow, shift); break;
+      case ShrSInt64:
+        largeShiftBlock = makeLargeShrS(rightHigh, leftHigh, shift); break;
       case ShrUInt64:
         largeShiftBlock = makeLargeShrU(rightHigh, leftHigh, shift); break;
       default: abort();
@@ -1097,6 +1158,11 @@ struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
                                        shift, shiftMask, widthLessShift);
         break;
       }
+      case ShrSInt64: {
+        smallShiftBlock = makeSmallShrS(rightHigh, leftLow, leftHigh,
+                                        shift, shiftMask, widthLessShift);
+        break;
+      }
       case ShrUInt64: {
         smallShiftBlock = makeSmallShrU(rightHigh, leftLow, leftHigh,
                                         shift, shiftMask, widthLessShift);
@@ -1328,14 +1394,14 @@ struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
         break;
       }
       case ShlInt64:
+      case ShrSInt64:
       case ShrUInt64: {
         replaceCurrent(
-          lowerShU(curr->op, result, std::move(leftLow), std::move(leftHigh),
-                   std::move(rightLow), std::move(rightHigh))
+          lowerShift(curr->op, result, std::move(leftLow), std::move(leftHigh),
+                     std::move(rightLow), std::move(rightHigh))
         );
         break;
       }
-      case ShrSInt64:
       case RotLInt64:
       case RotRInt64: goto err;
       case EqInt64: {
diff --git a/test/i64-shifts.2asm.js b/test/i64-shifts.2asm.js
new file mode 100644
index 000000000..aa2c53512
--- /dev/null
+++ b/test/i64-shifts.2asm.js
@@ -0,0 +1,115 @@
+function asmFunc(global, env, buffer) {
+ "use asm";
+ var HEAP8 = new global.Int8Array(buffer);
+ var HEAP16 = new global.Int16Array(buffer);
+ var HEAP32 = new global.Int32Array(buffer);
+ var HEAPU8 = new global.Uint8Array(buffer);
+ var HEAPU16 = new global.Uint16Array(buffer);
+ var HEAPU32 = new global.Uint32Array(buffer);
+ var HEAPF32 = new global.Float32Array(buffer);
+ var HEAPF64 = new global.Float64Array(buffer);
+ var Math_imul = global.Math.imul;
+ var Math_fround = global.Math.fround;
+ var Math_abs = global.Math.abs;
+ var Math_clz32 = global.Math.clz32;
+ var Math_min = global.Math.min;
+ var Math_max = global.Math.max;
+ var i64toi32_i32$HIGH_BITS = 0;
+ function dummy() {
+  
+ }
+ 
+ function $1($0, $0$hi, $1, $1$hi, $2, $2$hi) {
+  $0 = $0 | 0;
+  $0$hi = $0$hi | 0;
+  $1 = $1 | 0;
+  $1$hi = $1$hi | 0;
+  $2 = $2 | 0;
+  $2$hi = $2$hi | 0;
+  var i64toi32_i32$2 = 0, i64toi32_i32$4 = 0, i64toi32_i32$3 = 0, i64toi32_i32$0 = 0, i64toi32_i32$1 = 0, $11 = 0;
+  i64toi32_i32$0 = $0$hi;
+  i64toi32_i32$2 = $0;
+  i64toi32_i32$1 = $1$hi;
+  i64toi32_i32$3 = $1;
+  i64toi32_i32$4 = i64toi32_i32$3 & 31 | 0;
+  if (32 >>> 0 <= (i64toi32_i32$3 & 63 | 0) >>> 0) {
+   i64toi32_i32$1 = i64toi32_i32$2 << i64toi32_i32$4 | 0;
+   $11 = 0;
+  } else {
+   i64toi32_i32$1 = ((1 << i64toi32_i32$4 | 0) - 1 | 0) & (i64toi32_i32$2 >>> (32 - i64toi32_i32$4 | 0) | 0) | 0 | (i64toi32_i32$0 << i64toi32_i32$4 | 0) | 0;
+   $11 = i64toi32_i32$2 << i64toi32_i32$4 | 0;
+  }
+  i64toi32_i32$0 = $11;
+  i64toi32_i32$2 = $2$hi;
+  i64toi32_i32$3 = $2;
+  return (i64toi32_i32$0 | 0) == (i64toi32_i32$3 | 0) & (i64toi32_i32$1 | 0) == (i64toi32_i32$2 | 0) | 0 | 0;
+ }
+ 
+ function $2($0, $0$hi, $1, $1$hi, $2, $2$hi) {
+  $0 = $0 | 0;
+  $0$hi = $0$hi | 0;
+  $1 = $1 | 0;
+  $1$hi = $1$hi | 0;
+  $2 = $2 | 0;
+  $2$hi = $2$hi | 0;
+  var i64toi32_i32$0 = 0, i64toi32_i32$4 = 0, i64toi32_i32$3 = 0, i64toi32_i32$2 = 0, i64toi32_i32$1 = 0, $11 = 0;
+  i64toi32_i32$0 = $0$hi;
+  i64toi32_i32$2 = $0;
+  i64toi32_i32$1 = $1$hi;
+  i64toi32_i32$3 = $1;
+  i64toi32_i32$4 = i64toi32_i32$3 & 31 | 0;
+  if (32 >>> 0 <= (i64toi32_i32$3 & 63 | 0) >>> 0) {
+   i64toi32_i32$1 = i64toi32_i32$0 >> 31 | 0;
+   $11 = i64toi32_i32$0 >> i64toi32_i32$4 | 0;
+  } else {
+   i64toi32_i32$1 = i64toi32_i32$0 >> i64toi32_i32$4 | 0;
+   $11 = (((1 << i64toi32_i32$4 | 0) - 1 | 0) & i64toi32_i32$0 | 0) << (32 - i64toi32_i32$4 | 0) | 0 | (i64toi32_i32$2 >>> i64toi32_i32$4 | 0) | 0;
+  }
+  i64toi32_i32$0 = $11;
+  i64toi32_i32$2 = $2$hi;
+  i64toi32_i32$3 = $2;
+  return (i64toi32_i32$0 | 0) == (i64toi32_i32$3 | 0) & (i64toi32_i32$1 | 0) == (i64toi32_i32$2 | 0) | 0 | 0;
+ }
+ 
+ function __wasm_ctz_i32(x) {
+  x = x | 0;
+  var $1 = 0;
+  if ((x | 0) == (0 | 0)) $1 = 32; else $1 = 31 - Math_clz32(x ^ (x - 1 | 0) | 0) | 0;
+  return $1 | 0;
+ }
+ 
+ function __wasm_popcnt_i32(x) {
+  x = x | 0;
+  var count = 0, $2 = 0;
+  count = 0;
+  b : {
+   l : do {
+    $2 = count;
+    if ((x | 0) == (0 | 0)) break b;
+    x = x & (x - 1 | 0) | 0;
+    count = count + 1 | 0;
+    continue l;
+    break l;
+   } while (1);
+  };
+  return $2 | 0;
+ }
+ 
+ function __wasm_rotl_i32(x, k) {
+  x = x | 0;
+  k = k | 0;
+  return ((4294967295 >>> (k & 31 | 0) | 0) & x | 0) << (k & 31 | 0) | 0 | (((4294967295 << (32 - (k & 31 | 0) | 0) | 0) & x | 0) >>> (32 - (k & 31 | 0) | 0) | 0) | 0 | 0;
+ }
+ 
+ function __wasm_rotr_i32(x, k) {
+  x = x | 0;
+  k = k | 0;
+  return ((4294967295 << (k & 31 | 0) | 0) & x | 0) >>> (k & 31 | 0) | 0 | (((4294967295 >>> (32 - (k & 31 | 0) | 0) | 0) & x | 0) << (32 - (k & 31 | 0) | 0) | 0) | 0 | 0;
+ }
+ 
+ return {
+  shl_i64: $1, 
+  shr_i64: $2
+ };
+}
+
diff --git a/test/wasm2asm/i64-shifts.wast b/test/wasm2asm/i64-shifts.wast
new file mode 100644
index 000000000..d13c700ef
--- /dev/null
+++ b/test/wasm2asm/i64-shifts.wast
@@ -0,0 +1,81 @@
+;; Testing i64 shifts
+
+(module
+  (func $dummy)
+
+  (func (export "shl_i64") (param $0 i64) (param $1 i64) (param $2 i64) (result i32)
+    (i64.eq (i64.shl (get_local $0) (get_local $1)) (get_local $2)))
+  (func (export "shr_i64") (param $0 i64) (param $1 i64) (param $2 i64) (result i32)
+    (i64.eq (i64.shr_s (get_local $0) (get_local $1)) (get_local $2)))
+)
+
+(assert_return (invoke "shl_i64" (i32.const 0) (i32.const 0)
+                                 (i32.const 0) (i32.const 0)
+                                 (i32.const 0) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shl_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 1) (i32.const 0)
+                                 (i32.const 2) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shl_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 0) (i32.const 0)
+                                 (i32.const 1) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shl_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 32) (i32.const 0)
+                                 (i32.const 0) (i32.const 1))
+               (i32.const 1))
+(assert_return (invoke "shl_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 63) (i32.const 0)
+                                 (i32.const 0) (i32.const 2147483648))
+               (i32.const 1))
+(assert_return (invoke "shl_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 64) (i32.const 0)
+                                 (i32.const 1) (i32.const 0))
+               (i32.const 1))
+
+(assert_return (invoke "shr_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 0) (i32.const 0)
+                                 (i32.const 1) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 32) (i32.const 0)
+                                 (i32.const 0) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 0) (i32.const 1)
+                                 (i32.const 32) (i32.const 0)
+                                 (i32.const 1) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 0) (i32.const 2)
+                                 (i32.const 33) (i32.const 0)
+                                 (i32.const 1) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 0) (i32.const 2147483648)
+                                 (i32.const 32) (i32.const 0)
+                                 (i32.const 2147483648) (i32.const -1))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 0) (i32.const 2147483648)
+                                 (i32.const 33) (i32.const 0)
+                                 (i32.const 3221225472) (i32.const -1))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 0) (i32.const 2147483648)
+                                 (i32.const 63) (i32.const 0)
+                                 (i32.const -1) (i32.const -1))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 1) (i32.const 0)
+                                 (i32.const 0) (i32.const 0))
+               (i32.const 1))
+
+(assert_return (invoke "shr_i64" (i32.const 1) (i32.const 0)
+                                 (i32.const 2) (i32.const 0)
+                                 (i32.const 0) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 2) (i32.const 1)
+                                 (i32.const 1) (i32.const 0)
+                                 (i32.const -2147483647) (i32.const 0))
+               (i32.const 1))
+(assert_return (invoke "shr_i64" (i32.const 2) (i32.const 1)
+                                 (i32.const 2) (i32.const 0)
+                                 (i32.const 1073741824) (i32.const 0))
+               (i32.const 1))