From bd27fe2bf58d72dd0cdef73dd4040f2747215b78 Mon Sep 17 00:00:00 2001
From: Luuk de Gram <luuk@degram.dev>
Date: Sat, 2 Apr 2022 17:34:24 +0200
Subject: wasm: Implement `@clz`

Implements the `clz` AIR instruction for integers with bitsize <= 64.
When the bitsize of the integer is not the same as wasm's bitsize,
we substract the difference in bits as those will always be 0 for the integer, but should
not be counted towards the end result. We also wrap the result to ensure it fits
in the result type as documented in the language reference.
---
 src/arch/wasm/CodeGen.zig | 48 ++++++++++++++++++++++++++++++++++++++++++++++-
 src/arch/wasm/Emit.zig    |  4 ++++
 src/arch/wasm/Mir.zig     |  8 ++++++++
 3 files changed, 59 insertions(+), 1 deletion(-)

(limited to 'src')

diff --git a/src/arch/wasm/CodeGen.zig b/src/arch/wasm/CodeGen.zig
index 9cb61ca4ee..cd1aa286e1 100644
--- a/src/arch/wasm/CodeGen.zig
+++ b/src/arch/wasm/CodeGen.zig
@@ -1316,6 +1316,8 @@ fn genInst(self: *Self, inst: Air.Inst.Index) !WValue {
         .shl_with_overflow => self.airBinOpOverflow(inst, .shl),
         .mul_with_overflow => self.airBinOpOverflow(inst, .mul),
 
+        .clz => self.airClz(inst),
+
         .cmp_eq => self.airCmp(inst, .eq),
         .cmp_gte => self.airCmp(inst, .gte),
         .cmp_gt => self.airCmp(inst, .gt),
@@ -1438,7 +1440,6 @@ fn genInst(self: *Self, inst: Air.Inst.Index) !WValue {
         .shl_sat,
         .ret_addr,
         .frame_addr,
-        .clz,
         .ctz,
         .byte_swap,
         .bit_reverse,
@@ -3932,3 +3933,48 @@ fn airMulAdd(self: *Self, inst: Air.Inst.Index) InnerError!WValue {
     const mul_result = try self.binOp(lhs, rhs, ty, .mul);
     return self.binOp(mul_result, addend, ty, .add);
 }
+
+fn airClz(self: *Self, inst: Air.Inst.Index) InnerError!WValue {
+    if (self.liveness.isUnused(inst)) return WValue{ .none = {} };
+    const ty_op = self.air.instructions.items(.data)[inst].ty_op;
+    const ty = self.air.typeOf(ty_op.operand);
+    const result_ty = self.air.typeOfIndex(inst);
+    if (ty.zigTypeTag() == .Vector) {
+        return self.fail("TODO: `@clz` for vectors", .{});
+    }
+
+    const operand = try self.resolveInst(ty_op.operand);
+    const int_info = ty.intInfo(self.target);
+    const wasm_bits = toWasmBits(int_info.bits) orelse {
+        return self.fail("TODO: `@clz` for integers with bitsize '{d}'", .{int_info.bits});
+    };
+
+    try self.emitWValue(operand);
+    switch (wasm_bits) {
+        32 => {
+            try self.addTag(.i32_clz);
+
+            if (wasm_bits != int_info.bits) {
+                const tmp = try self.allocLocal(ty);
+                try self.addLabel(.local_set, tmp.local);
+                const val: i32 = -@intCast(i32, wasm_bits - int_info.bits);
+                return self.wrapBinOp(tmp, .{ .imm32 = @bitCast(u32, val) }, ty, .add);
+            }
+        },
+        64 => {
+            try self.addTag(.i64_clz);
+
+            if (wasm_bits != int_info.bits) {
+                const tmp = try self.allocLocal(ty);
+                try self.addLabel(.local_set, tmp.local);
+                const val: i64 = -@intCast(i64, wasm_bits - int_info.bits);
+                return self.wrapBinOp(tmp, .{ .imm64 = @bitCast(u64, val) }, ty, .add);
+            }
+        },
+        else => unreachable,
+    }
+
+    const result = try self.allocLocal(result_ty);
+    try self.addLabel(.local_set, result.local);
+    return result;
+}
diff --git a/src/arch/wasm/Emit.zig b/src/arch/wasm/Emit.zig
index 7487b014be..6fc2dfa3b3 100644
--- a/src/arch/wasm/Emit.zig
+++ b/src/arch/wasm/Emit.zig
@@ -217,6 +217,10 @@ pub fn emitMir(emit: *Emit) InnerError!void {
             .i64_rem_u => try emit.emitTag(tag),
             .i32_popcnt => try emit.emitTag(tag),
             .i64_popcnt => try emit.emitTag(tag),
+            .i32_clz => try emit.emitTag(tag),
+            .i32_ctz => try emit.emitTag(tag),
+            .i64_clz => try emit.emitTag(tag),
+            .i64_ctz => try emit.emitTag(tag),
 
             .extended => try emit.emitExtended(inst),
         }
diff --git a/src/arch/wasm/Mir.zig b/src/arch/wasm/Mir.zig
index 395e9bb17c..27f683cf1e 100644
--- a/src/arch/wasm/Mir.zig
+++ b/src/arch/wasm/Mir.zig
@@ -317,6 +317,10 @@ pub const Inst = struct {
         /// Uses `tag`
         f64_ge = 0x66,
         /// Uses `tag`
+        i32_clz = 0x67,
+        /// Uses `tag`
+        i32_ctz = 0x68,
+        /// Uses `tag`
         i32_popcnt = 0x69,
         /// Uses `tag`
         i32_add = 0x6A,
@@ -345,6 +349,10 @@ pub const Inst = struct {
         /// Uses `tag`
         i32_shr_u = 0x76,
         /// Uses `tag`
+        i64_clz = 0x79,
+        /// Uses `tag`
+        i64_ctz = 0x7A,
+        /// Uses `tag`
         i64_popcnt = 0x7B,
         /// Uses `tag`
         i64_add = 0x7C,
-- 
cgit v1.2.3