add @ctz, @clz and compiler_rt implementation

4 files changed, 68 insertions, 2 deletions

diff --git a/src/all_types.hpp b/src/all_types.hpp
index adb9b34f95..037d34ddd9 100644
--- a/src/all_types.hpp
+++ b/src/all_types.hpp
@@ -1038,6 +1038,8 @@ enum BuiltinFnId {
     BuiltinFnIdCUndef,
     BuiltinFnIdCompileVar,
     BuiltinFnIdConstEval,
+    BuiltinFnIdCtz,
+    BuiltinFnIdClz,
 };
 
 struct BuiltinFnEntry {
@@ -1161,6 +1163,7 @@ struct CodeGen {
     uint32_t error_value_count;
     TypeTableEntry *err_tag_type;
     LLVMValueRef int_overflow_fns[2][3][4]; // [0-signed,1-unsigned][0-add,1-sub,2-mul][0-8,1-16,2-32,3-64]
+    LLVMValueRef int_builtin_fns[2][4]; // [0-ctz,1-clz][0-8,1-16,2-32,3-64]
 
     const char **clang_argv;
     int clang_argv_len;
diff --git a/src/analyze.cpp b/src/analyze.cpp
index fc438506c4..3e57d646c0 100644
--- a/src/analyze.cpp
+++ b/src/analyze.cpp
@@ -4304,6 +4304,29 @@ static TypeTableEntry *analyze_builtin_fn_call_expr(CodeGen *g, ImportTableEntry
 
                 return resolved_type;
             }
+        case BuiltinFnIdCtz:
+        case BuiltinFnIdClz:
+            {
+                AstNode *type_node = node->data.fn_call_expr.params.at(0);
+                TypeTableEntry *int_type = analyze_type_expr(g, import, context, type_node);
+                if (int_type->id == TypeTableEntryIdInvalid) {
+                    return int_type;
+                } else if (int_type->id == TypeTableEntryIdInt) {
+                    AstNode **expr_node = node->data.fn_call_expr.params.at(1)->parent_field;
+                    TypeTableEntry *resolved_type = analyze_expression(g, import, context, int_type, *expr_node);
+                    if (resolved_type->id == TypeTableEntryIdInvalid) {
+                        return resolved_type;
+                    }
+
+                    // TODO const expr eval
+
+                    return resolved_type;
+                } else {
+                    add_node_error(g, type_node,
+                        buf_sprintf("expected integer type, got '%s'", buf_ptr(&int_type->name)));
+                    return g->builtin_types.entry_invalid;
+                }
+            }
 
     }
     zig_unreachable();
diff --git a/src/codegen.cpp b/src/codegen.cpp
index bf208a527b..7cfd699ce4 100644
--- a/src/codegen.cpp
+++ b/src/codegen.cpp
@@ -227,6 +227,24 @@ static LLVMValueRef get_int_overflow_fn(CodeGen *g, TypeTableEntry *type_entry,
     return *fn;
 }
 
+static LLVMValueRef get_int_builtin_fn(CodeGen *g, TypeTableEntry *int_type, BuiltinFnId fn_id) {
+    // [0-ctz,1-clz][0-8,1-16,2-32,3-64]
+    int index0 = (fn_id == BuiltinFnIdCtz) ? 0 : 1;
+    int index1 = bits_index(int_type->data.integral.bit_count);
+    LLVMValueRef *fn = &g->int_builtin_fns[index0][index1];
+    if (!*fn) {
+        const char *fn_name = (fn_id == BuiltinFnIdCtz) ? "cttz" : "ctlz";
+        Buf *llvm_name = buf_sprintf("llvm.%s.i%d", fn_name, int_type->data.integral.bit_count);
+        LLVMTypeRef param_types[] = {
+            int_type->type_ref,
+            LLVMInt1Type(),
+        };
+        LLVMTypeRef fn_type = LLVMFunctionType(int_type->type_ref, param_types, 2, false);
+        *fn = LLVMAddFunction(g->module, buf_ptr(llvm_name), fn_type);
+    }
+    return *fn;
+}
+
 static LLVMValueRef get_handle_value(CodeGen *g, AstNode *source_node, LLVMValueRef ptr, TypeTableEntry *type) {
     if (handle_is_ptr(type)) {
         return ptr;
@@ -249,6 +267,22 @@ static LLVMValueRef gen_builtin_fn_call_expr(CodeGen *g, AstNode *node) {
         case BuiltinFnIdCDefine:
         case BuiltinFnIdCUndef:
             zig_unreachable();
+        case BuiltinFnIdCtz:
+        case BuiltinFnIdClz:
+            {
+                int fn_call_param_count = node->data.fn_call_expr.params.length;
+                assert(fn_call_param_count == 2);
+                TypeTableEntry *int_type = get_type_for_type_node(node->data.fn_call_expr.params.at(0));
+                assert(int_type->id == TypeTableEntryIdInt);
+                LLVMValueRef fn_val = get_int_builtin_fn(g, int_type, builtin_fn->id);
+                LLVMValueRef operand = gen_expr(g, node->data.fn_call_expr.params.at(1));
+                LLVMValueRef params[] {
+                    operand,
+                    LLVMConstNull(LLVMInt1Type()),
+                };
+                add_debug_source_node(g, node);
+                return LLVMBuildCall(g->builder, fn_val, params, 2, "");
+            }
         case BuiltinFnIdAddWithOverflow:
         case BuiltinFnIdSubWithOverflow:
         case BuiltinFnIdMulWithOverflow:
@@ -1025,11 +1059,12 @@ static LLVMValueRef gen_prefix_op_expr(CodeGen *g, AstNode *node) {
         case PrefixOpDereference:
             {
                 LLVMValueRef expr = gen_expr(g, expr_node);
+                assert(expr_type->id == TypeTableEntryIdPointer);
                 if (!type_has_bits(expr_type)) {
                     return nullptr;
                 } else {
-                    add_debug_source_node(g, node);
-                    return LLVMBuildLoad(g->builder, expr, "");
+                    TypeTableEntry *child_type = expr_type->data.pointer.child_type;
+                    return get_handle_value(g, node, expr, child_type);
                 }
             }
         case PrefixOpMaybe:
@@ -3590,6 +3625,8 @@ static void define_builtin_fns(CodeGen *g) {
     create_builtin_fn_with_arg_count(g, BuiltinFnIdCUndef, "c_undef", 1);
     create_builtin_fn_with_arg_count(g, BuiltinFnIdCompileVar, "compile_var", 1);
     create_builtin_fn_with_arg_count(g, BuiltinFnIdConstEval, "const_eval", 1);
+    create_builtin_fn_with_arg_count(g, BuiltinFnIdCtz, "ctz", 2);
+    create_builtin_fn_with_arg_count(g, BuiltinFnIdClz, "clz", 2);
 }
 
 static void init(CodeGen *g, Buf *source_path) {
diff --git a/src/link.cpp b/src/link.cpp
index 318d6ffa34..5d684c46e6 100644
--- a/src/link.cpp
+++ b/src/link.cpp
@@ -205,6 +205,9 @@ static void construct_linker_job_linux(LinkJob *lj) {
     if (!g->link_libc && (g->out_type == OutTypeExe || g->out_type == OutTypeLib)) {
         Buf *builtin_o_path = build_o(g, "builtin");
         lj->args.append(buf_ptr(builtin_o_path));
+
+        Buf *compiler_rt_o_path = build_o(g, "compiler_rt");
+        lj->args.append(buf_ptr(compiler_rt_o_path));
     }
 
     auto it = g->link_table.entry_iterator();