Commit `bd27fe2bf5`

Luuk de Gram <luuk@degram.dev>

2022-04-02 17:34:24

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.

master

1 parent 5ba0336

Changed files (3)

src

arch

wasm

CodeGen.zig

Emit.zig

Mir.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;
+}

@@ -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),
         }

@@ -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,

Commit bd27fe2bf5

Commit `bd27fe2bf5`