CBE: implement clz, ctz for ints <= 128 bits

3 files changed, 54 insertions, 4 deletions

diff --git a/src/codegen/c.zig b/src/codegen/c.zig
index c179b65046..f1da1fdc0c 100644
--- a/src/codegen/c.zig
+++ b/src/codegen/c.zig
@@ -1708,8 +1708,8 @@ fn genBody(f: *Function, body: []const Air.Inst.Index) error{ AnalysisFail, OutO
             .memcpy           => try airMemcpy(f, inst),
             .set_union_tag    => try airSetUnionTag(f, inst),
             .get_union_tag    => try airGetUnionTag(f, inst),
-            .clz              => try airBuiltinCall(f, inst, "clz"),
-            .ctz              => try airBuiltinCall(f, inst, "ctz"),
+            .clz              => try airCountZeroes(f, inst, "clz"),
+            .ctz              => try airCountZeroes(f, inst, "ctz"),
             .popcount         => try airBuiltinCall(f, inst, "popcount"),
             .byte_swap        => try airBuiltinCall(f, inst, "byte_swap"),
             .bit_reverse      => try airBuiltinCall(f, inst, "bit_reverse"),
@@ -3349,6 +3349,26 @@ fn airBuiltinCall(f: *Function, inst: Air.Inst.Index, fn_name: [*:0]const u8) !C
     return local;
 }
 
+fn airCountZeroes(f: *Function, inst: Air.Inst.Index, fn_name: [*:0]const u8) !CValue {
+    if (f.liveness.isUnused(inst)) return CValue.none;
+
+    const inst_ty = f.air.typeOfIndex(inst);
+    const local = try f.allocLocal(inst_ty, .Const);
+    const operand = f.air.instructions.items(.data)[inst].ty_op.operand;
+    const operand_ty = f.air.typeOf(operand);
+    const target = f.object.dg.module.getTarget();
+    const writer = f.object.writer();
+
+    const zig_bits = operand_ty.intInfo(target).bits;
+    _ = toCIntBits(zig_bits) orelse
+        return f.fail("TODO: C backend: implement integer types larger than 128 bits", .{});
+
+    try writer.print(" = zig_{s}(", .{fn_name});
+    try f.writeCValue(writer, try f.resolveInst(operand));
+    try writer.print(", {d});\n", .{zig_bits});
+    return local;
+}
+
 fn airCmpxchg(f: *Function, inst: Air.Inst.Index, flavor: [*:0]const u8) !CValue {
     const ty_pl = f.air.instructions.items(.data)[inst].ty_pl;
     const extra = f.air.extraData(Air.Cmpxchg, ty_pl.payload).data;
diff --git a/src/link/C/zig.h b/src/link/C/zig.h
index 873daafd51..a5534f86aa 100644
--- a/src/link/C/zig.h
+++ b/src/link/C/zig.h
@@ -500,3 +500,21 @@ zig_shl_sat_s(isize, intptr_t, ((sizeof(intptr_t)) * CHAR_BIT - 1))
 zig_shl_sat_s(short,    short, ((sizeof(short   )) * CHAR_BIT - 1))
 zig_shl_sat_s(int,        int, ((sizeof(int     )) * CHAR_BIT - 1))
 zig_shl_sat_s(long,      long, ((sizeof(long    )) * CHAR_BIT - 1))
+
+#define zig_bitsizeof(T) (CHAR_BIT * sizeof(T))
+
+static inline int zig_clz(uint64_t value, uint8_t zig_type_bit_width) {
+    if (value == 0) return zig_type_bit_width;
+    if (zig_type_bit_width <= zig_bitsizeof(unsigned int))
+        return (__builtin_clz(value) - zig_bitsizeof(unsigned int) + zig_type_bit_width);
+    if (zig_type_bit_width <= zig_bitsizeof(unsigned long))
+        return (__builtin_clzl(value) - zig_bitsizeof(unsigned long) + zig_type_bit_width);
+    return (__builtin_clzll(value) - zig_bitsizeof(unsigned long long) + zig_type_bit_width);
+}
+
+static inline int zig_ctz(uint64_t value, uint8_t zig_type_bit_width) {
+    if (value == 0) return zig_type_bit_width;
+    if (zig_type_bit_width <= zig_bitsizeof(unsigned int)) return __builtin_ctz(value);
+    if (zig_type_bit_width <= zig_bitsizeof(unsigned long)) return __builtin_ctzl(value);
+    return __builtin_ctzll(value);
+}
diff --git a/test/behavior/math.zig b/test/behavior/math.zig
index e06d1bf01a..a8daac54b5 100644
--- a/test/behavior/math.zig
+++ b/test/behavior/math.zig
@@ -65,7 +65,6 @@ test "@clz" {
     if (builtin.zig_backend == .stage2_x86_64) return error.SkipZigTest; // TODO
     if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest; // TODO
     if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest; // TODO
-    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest; // TODO
 
     try testClz();
     comptime try testClz();
@@ -76,6 +75,20 @@ fn testClz() !void {
     try expect(testOneClz(u8, 0b00001010) == 4);
     try expect(testOneClz(u8, 0b00011010) == 3);
     try expect(testOneClz(u8, 0b00000000) == 8);
+}
+
+test "@clz big ints" {
+    if (builtin.zig_backend == .stage2_wasm) return error.SkipZigTest; // TODO
+    if (builtin.zig_backend == .stage2_x86_64) return error.SkipZigTest; // TODO
+    if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest; // TODO
+    if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest; // TODO
+    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest; // TODO
+
+    try testClzBigInts();
+    comptime try testClzBigInts();
+}
+
+fn testClzBigInts() !void {
     try expect(testOneClz(u128, 0xffffffffffffffff) == 64);
     try expect(testOneClz(u128, 0x10000000000000000) == 63);
 }
@@ -130,7 +143,6 @@ test "@ctz" {
     if (builtin.zig_backend == .stage2_x86_64) return error.SkipZigTest; // TODO
     if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest; // TODO
     if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest; // TODO
-    if (builtin.zig_backend == .stage2_c) return error.SkipZigTest; // TODO
 
     try testCtz();
     comptime try testCtz();