Merge pull request #9517 from ziglang/generic-functions

stage2 generic functions

1 files changed, 625 insertions, 191 deletions

diff --git a/src/Sema.zig b/src/Sema.zig
index 753ef8fb9c..825737e4c5 100644
--- a/src/Sema.zig
+++ b/src/Sema.zig
@@ -29,13 +29,6 @@ owner_func: ?*Module.Fn,
 /// This starts out the same as `owner_func` and then diverges in the case of
 /// an inline or comptime function call.
 func: ?*Module.Fn,
-/// For now, AIR requires arg instructions to be the first N instructions in the
-/// AIR code. We store references here for the purpose of `resolveInst`.
-/// This can get reworked with AIR memory layout changes, into simply:
-/// > Denormalized data to make `resolveInst` faster. This is 0 if not inside a function,
-/// > otherwise it is the number of parameters of the function.
-/// > param_count: u32
-param_inst_list: []const Air.Inst.Ref,
 branch_quota: u32 = 1000,
 branch_count: u32 = 0,
 /// This field is updated when a new source location becomes active, so that
@@ -43,8 +36,22 @@ branch_count: u32 = 0,
 /// access to the source location set by the previous instruction which did
 /// contain a mapped source location.
 src: LazySrcLoc = .{ .token_offset = 0 },
-next_arg_index: usize = 0,
 decl_val_table: std.AutoHashMapUnmanaged(*Decl, Air.Inst.Ref) = .{},
+/// When doing a generic function instantiation, this array collects a
+/// `Value` object for each parameter that is comptime known and thus elided
+/// from the generated function. This memory is allocated by a parent `Sema` and
+/// owned by the values arena of the Sema owner_decl.
+comptime_args: []TypedValue = &.{},
+/// Marks the function instruction that `comptime_args` applies to so that we
+/// don't accidentally apply it to a function prototype which is used in the
+/// type expression of a generic function parameter.
+comptime_args_fn_inst: Zir.Inst.Index = 0,
+/// When `comptime_args` is provided, this field is also provided. It was used as
+/// the key in the `monomorphed_funcs` set. The `func` instruction is supposed
+/// to use this instead of allocating a fresh one. This avoids an unnecessary
+/// extra hash table lookup in the `monomorphed_funcs` set.
+/// Sema will set this to null when it takes ownership.
+preallocated_new_func: ?*Module.Fn = null,
 
 const std = @import("std");
 const mem = std.mem;
@@ -80,45 +87,6 @@ pub fn deinit(sema: *Sema) void {
     sema.* = undefined;
 }
 
-pub fn analyzeFnBody(
-    sema: *Sema,
-    block: *Scope.Block,
-    fn_body_inst: Zir.Inst.Index,
-) SemaError!void {
-    const tags = sema.code.instructions.items(.tag);
-    const datas = sema.code.instructions.items(.data);
-    const body: []const Zir.Inst.Index = switch (tags[fn_body_inst]) {
-        .func, .func_inferred => blk: {
-            const inst_data = datas[fn_body_inst].pl_node;
-            const extra = sema.code.extraData(Zir.Inst.Func, inst_data.payload_index);
-            const param_types_len = extra.data.param_types_len;
-            const body = sema.code.extra[extra.end + param_types_len ..][0..extra.data.body_len];
-            break :blk body;
-        },
-        .extended => blk: {
-            const extended = datas[fn_body_inst].extended;
-            assert(extended.opcode == .func);
-            const extra = sema.code.extraData(Zir.Inst.ExtendedFunc, extended.operand);
-            const small = @bitCast(Zir.Inst.ExtendedFunc.Small, extended.small);
-            var extra_index: usize = extra.end;
-            extra_index += @boolToInt(small.has_lib_name);
-            extra_index += @boolToInt(small.has_cc);
-            extra_index += @boolToInt(small.has_align);
-            if (small.has_comptime_bits) {
-                extra_index += (extra.data.param_types_len + 31) / 32;
-            }
-            extra_index += extra.data.param_types_len;
-            const body = sema.code.extra[extra_index..][0..extra.data.body_len];
-            break :blk body;
-        },
-        else => unreachable,
-    };
-    _ = sema.analyzeBody(block, body) catch |err| switch (err) {
-        error.NeededSourceLocation => unreachable,
-        else => |e| return e,
-    };
-}
-
 /// Returns only the result from the body that is specified.
 /// Only appropriate to call when it is determined at comptime that this body
 /// has no peers.
@@ -162,7 +130,6 @@ pub fn analyzeBody(
         const inst = body[i];
         const air_inst: Air.Inst.Ref = switch (tags[inst]) {
             // zig fmt: off
-            .arg                          => try sema.zirArg(block, inst),
             .alloc                        => try sema.zirAlloc(block, inst),
             .alloc_inferred               => try sema.zirAllocInferred(block, inst, Type.initTag(.inferred_alloc_const)),
             .alloc_inferred_mut           => try sema.zirAllocInferred(block, inst, Type.initTag(.inferred_alloc_mut)),
@@ -499,6 +466,26 @@ pub fn analyzeBody(
                 i += 1;
                 continue;
             },
+            .param => {
+                try sema.zirParam(block, inst, false);
+                i += 1;
+                continue;
+            },
+            .param_comptime => {
+                try sema.zirParam(block, inst, true);
+                i += 1;
+                continue;
+            },
+            .param_anytype => {
+                try sema.zirParamAnytype(block, inst, false);
+                i += 1;
+                continue;
+            },
+            .param_anytype_comptime => {
+                try sema.zirParamAnytype(block, inst, true);
+                i += 1;
+                continue;
+            },
 
             // Special case instructions to handle comptime control flow.
             .repeat_inline => {
@@ -648,6 +635,7 @@ fn resolveValue(
     air_ref: Air.Inst.Ref,
 ) CompileError!Value {
     if (try sema.resolveMaybeUndefValAllowVariables(block, src, air_ref)) |val| {
+        if (val.tag() == .generic_poison) return error.GenericPoison;
         return val;
     }
     return sema.failWithNeededComptime(block, src);
@@ -665,6 +653,7 @@ fn resolveConstValue(
         switch (val.tag()) {
             .undef => return sema.failWithUseOfUndef(block, src),
             .variable => return sema.failWithNeededComptime(block, src),
+            .generic_poison => return error.GenericPoison,
             else => return val,
         }
     }
@@ -1044,7 +1033,6 @@ fn zirEnumDecl(
             .namespace = &enum_obj.namespace,
             .owner_func = null,
             .func = null,
-            .param_inst_list = &.{},
             .branch_quota = sema.branch_quota,
             .branch_count = sema.branch_count,
         };
@@ -1324,57 +1312,44 @@ fn zirIndexablePtrLen(sema: *Sema, block: *Scope.Block, inst: Zir.Inst.Index) Co
 
     const inst_data = sema.code.instructions.items(.data)[inst].un_node;
     const src = inst_data.src();
-    const array_ptr = sema.resolveInst(inst_data.operand);
-    const array_ptr_src = src;
+    const array = sema.resolveInst(inst_data.operand);
+    const array_ty = sema.typeOf(array);
 
-    const elem_ty = sema.typeOf(array_ptr).elemType();
-    if (elem_ty.isSlice()) {
-        const slice_inst = try sema.analyzeLoad(block, src, array_ptr, array_ptr_src);
-        return sema.analyzeSliceLen(block, src, slice_inst);
+    if (array_ty.isSlice()) {
+        return sema.analyzeSliceLen(block, src, array);
     }
-    if (!elem_ty.isIndexable()) {
-        const cond_src: LazySrcLoc = .{ .node_offset_for_cond = inst_data.src_node };
-        const msg = msg: {
-            const msg = try sema.mod.errMsg(
-                &block.base,
-                cond_src,
-                "type '{}' does not support indexing",
-                .{elem_ty},
-            );
-            errdefer msg.destroy(sema.gpa);
-            try sema.mod.errNote(
-                &block.base,
-                cond_src,
-                msg,
-                "for loop operand must be an array, slice, tuple, or vector",
-                .{},
-            );
-            break :msg msg;
-        };
-        return sema.mod.failWithOwnedErrorMsg(&block.base, msg);
-    }
-    const result_ptr = try sema.fieldPtr(block, src, array_ptr, "len", src);
-    const result_ptr_src = array_ptr_src;
-    return sema.analyzeLoad(block, src, result_ptr, result_ptr_src);
-}
 
-fn zirArg(sema: *Sema, block: *Scope.Block, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {
-    const inst_data = sema.code.instructions.items(.data)[inst].str_tok;
-    const arg_name = inst_data.get(sema.code);
-    const arg_index = sema.next_arg_index;
-    sema.next_arg_index += 1;
-
-    // TODO check if arg_name shadows a Decl
-    _ = arg_name;
-
-    if (block.inlining) |_| {
-        return sema.param_inst_list[arg_index];
+    if (array_ty.isSinglePointer()) {
+        const elem_ty = array_ty.elemType();
+        if (elem_ty.isSlice()) {
+            const slice_inst = try sema.analyzeLoad(block, src, array, src);
+            return sema.analyzeSliceLen(block, src, slice_inst);
+        }
+        if (!elem_ty.isIndexable()) {
+            const msg = msg: {
+                const msg = try sema.mod.errMsg(
+                    &block.base,
+                    src,
+                    "type '{}' does not support indexing",
+                    .{elem_ty},
+                );
+                errdefer msg.destroy(sema.gpa);
+                try sema.mod.errNote(
+                    &block.base,
+                    src,
+                    msg,
+                    "for loop operand must be an array, slice, tuple, or vector",
+                    .{},
+                );
+                break :msg msg;
+            };
+            return sema.mod.failWithOwnedErrorMsg(&block.base, msg);
+        }
+        const result_ptr = try sema.fieldPtr(block, src, array, "len", src);
+        return sema.analyzeLoad(block, src, result_ptr, src);
     }
 
-    // Set the name of the Air.Arg instruction for use by codegen debug info.
-    const air_arg = sema.param_inst_list[arg_index];
-    sema.air_instructions.items(.data)[Air.refToIndex(air_arg).?].ty_str.str = inst_data.start;
-    return air_arg;
+    return sema.mod.fail(&block.base, src, "TODO implement Sema.zirIndexablePtrLen", .{});
 }
 
 fn zirAllocExtended(
@@ -2385,6 +2360,40 @@ fn zirCall(
     return sema.analyzeCall(block, func, func_src, call_src, modifier, ensure_result_used, resolved_args);
 }
 
+const GenericCallAdapter = struct {
+    generic_fn: *Module.Fn,
+    precomputed_hash: u64,
+    func_ty_info: Type.Payload.Function.Data,
+    comptime_vals: []const Value,
+
+    pub fn eql(ctx: @This(), adapted_key: void, other_key: *Module.Fn) bool {
+        _ = adapted_key;
+        // The generic function Decl is guaranteed to be the first dependency
+        // of each of its instantiations.
+        const generic_owner_decl = other_key.owner_decl.dependencies.keys()[0];
+        if (ctx.generic_fn.owner_decl != generic_owner_decl) return false;
+
+        // This logic must be kept in sync with the logic in `analyzeCall` that
+        // computes the hash.
+        const other_comptime_args = other_key.comptime_args.?;
+        for (ctx.func_ty_info.param_types) |param_ty, i| {
+            if (ctx.func_ty_info.paramIsComptime(i) and param_ty.tag() != .generic_poison) {
+                if (!ctx.comptime_vals[i].eql(other_comptime_args[i].val, param_ty)) {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+
+    /// The implementation of the hash is in semantic analysis of function calls, so
+    /// that any errors when computing the hash can be properly reported.
+    pub fn hash(ctx: @This(), adapted_key: void) u64 {
+        _ = adapted_key;
+        return ctx.precomputed_hash;
+    }
+};
+
 fn analyzeCall(
     sema: *Sema,
     block: *Scope.Block,
@@ -2393,41 +2402,44 @@ fn analyzeCall(
     call_src: LazySrcLoc,
     modifier: std.builtin.CallOptions.Modifier,
     ensure_result_used: bool,
-    args: []const Air.Inst.Ref,
+    uncasted_args: []const Air.Inst.Ref,
 ) CompileError!Air.Inst.Ref {
+    const mod = sema.mod;
+
     const func_ty = sema.typeOf(func);
     if (func_ty.zigTypeTag() != .Fn)
-        return sema.mod.fail(&block.base, func_src, "type '{}' not a function", .{func_ty});
+        return mod.fail(&block.base, func_src, "type '{}' not a function", .{func_ty});
 
-    const cc = func_ty.fnCallingConvention();
+    const func_ty_info = func_ty.fnInfo();
+    const cc = func_ty_info.cc;
     if (cc == .Naked) {
         // TODO add error note: declared here
-        return sema.mod.fail(
+        return mod.fail(
             &block.base,
             func_src,
             "unable to call function with naked calling convention",
             .{},
         );
     }
-    const fn_params_len = func_ty.fnParamLen();
-    if (func_ty.fnIsVarArgs()) {
+    const fn_params_len = func_ty_info.param_types.len;
+    if (func_ty_info.is_var_args) {
         assert(cc == .C);
-        if (args.len < fn_params_len) {
+        if (uncasted_args.len < fn_params_len) {
             // TODO add error note: declared here
-            return sema.mod.fail(
+            return mod.fail(
                 &block.base,
                 func_src,
                 "expected at least {d} argument(s), found {d}",
-                .{ fn_params_len, args.len },
+                .{ fn_params_len, uncasted_args.len },
             );
         }
-    } else if (fn_params_len != args.len) {
+    } else if (fn_params_len != uncasted_args.len) {
         // TODO add error note: declared here
-        return sema.mod.fail(
+        return mod.fail(
             &block.base,
             func_src,
             "expected {d} argument(s), found {d}",
-            .{ fn_params_len, args.len },
+            .{ fn_params_len, uncasted_args.len },
         );
     }
 
@@ -2442,21 +2454,30 @@ fn analyzeCall(
         .never_inline,
         .no_async,
         .always_tail,
-        => return sema.mod.fail(&block.base, call_src, "TODO implement call with modifier {}", .{
+        => return mod.fail(&block.base, call_src, "TODO implement call with modifier {}", .{
             modifier,
         }),
     }
 
     const gpa = sema.gpa;
 
-    const is_comptime_call = block.is_comptime or modifier == .compile_time;
+    const is_comptime_call = block.is_comptime or modifier == .compile_time or
+        func_ty_info.return_type.requiresComptime();
     const is_inline_call = is_comptime_call or modifier == .always_inline or
-        func_ty.fnCallingConvention() == .Inline;
+        func_ty_info.cc == .Inline;
     const result: Air.Inst.Ref = if (is_inline_call) res: {
+        // TODO look into not allocating this args array
+        const args = try sema.arena.alloc(Air.Inst.Ref, uncasted_args.len);
+        for (uncasted_args) |uncasted_arg, i| {
+            const param_ty = func_ty.fnParamType(i);
+            const arg_src = call_src; // TODO: better source location
+            args[i] = try sema.coerce(block, param_ty, uncasted_arg, arg_src);
+        }
+
         const func_val = try sema.resolveConstValue(block, func_src, func);
         const module_fn = switch (func_val.tag()) {
             .function => func_val.castTag(.function).?.data,
-            .extern_fn => return sema.mod.fail(&block.base, call_src, "{s} call of extern function", .{
+            .extern_fn => return mod.fail(&block.base, call_src, "{s} call of extern function", .{
                 @as([]const u8, if (is_comptime_call) "comptime" else "inline"),
             }),
             else => unreachable,
@@ -2502,14 +2523,6 @@ fn analyzeCall(
         sema.func = module_fn;
         defer sema.func = parent_func;
 
-        const parent_param_inst_list = sema.param_inst_list;
-        sema.param_inst_list = args;
-        defer sema.param_inst_list = parent_param_inst_list;
-
-        const parent_next_arg_index = sema.next_arg_index;
-        sema.next_arg_index = 0;
-        defer sema.next_arg_index = parent_next_arg_index;
-
         var child_block: Scope.Block = .{
             .parent = null,
             .sema = sema,
@@ -2529,16 +2542,229 @@ fn analyzeCall(
         try sema.emitBackwardBranch(&child_block, call_src);
 
         // This will have return instructions analyzed as break instructions to
-        // the block_inst above.
-        try sema.analyzeFnBody(&child_block, module_fn.zir_body_inst);
+        // the block_inst above. Here we are performing "comptime/inline semantic analysis"
+        // for a function body, which means we must map the parameter ZIR instructions to
+        // the AIR instructions of the callsite.
+        const fn_info = sema.code.getFnInfo(module_fn.zir_body_inst);
+        const zir_tags = sema.code.instructions.items(.tag);
+        var arg_i: usize = 0;
+        try sema.inst_map.ensureUnusedCapacity(gpa, @intCast(u32, args.len));
+        for (fn_info.param_body) |inst| {
+            switch (zir_tags[inst]) {
+                .param, .param_comptime, .param_anytype, .param_anytype_comptime => {},
+                else => continue,
+            }
+            sema.inst_map.putAssumeCapacityNoClobber(inst, args[arg_i]);
+            arg_i += 1;
+        }
+        _ = try sema.analyzeBody(&child_block, fn_info.body);
+        break :res try sema.analyzeBlockBody(block, call_src, &child_block, merges);
+    } else if (func_ty_info.is_generic) res: {
+        const func_val = try sema.resolveConstValue(block, func_src, func);
+        const module_fn = func_val.castTag(.function).?.data;
+        // Check the Module's generic function map with an adapted context, so that we
+        // can match against `uncasted_args` rather than doing the work below to create a
+        // generic Scope only to junk it if it matches an existing instantiation.
+        const namespace = module_fn.owner_decl.namespace;
+        const fn_zir = namespace.file_scope.zir;
+        const fn_info = fn_zir.getFnInfo(module_fn.zir_body_inst);
+        const zir_tags = fn_zir.instructions.items(.tag);
+        const new_module_func = new_func: {
+            // This hash must match `Module.MonomorphedFuncsContext.hash`.
+            // For parameters explicitly marked comptime and simple parameter type expressions,
+            // we know whether a parameter is elided from a monomorphed function, and can
+            // use it in the hash here. However, for parameter type expressions that are not
+            // explicitly marked comptime and rely on previous parameter comptime values, we
+            // don't find out until after generating a monomorphed function whether the parameter
+            // type ended up being a "must-be-comptime-known" type.
+            var hasher = std.hash.Wyhash.init(0);
+            std.hash.autoHash(&hasher, @ptrToInt(module_fn));
+
+            const comptime_vals = try sema.arena.alloc(Value, func_ty_info.param_types.len);
+
+            for (func_ty_info.param_types) |param_ty, i| {
+                const is_comptime = func_ty_info.paramIsComptime(i);
+                if (is_comptime and param_ty.tag() != .generic_poison) {
+                    const arg_src = call_src; // TODO better source location
+                    const casted_arg = try sema.coerce(block, param_ty, uncasted_args[i], arg_src);
+                    if (try sema.resolveMaybeUndefVal(block, arg_src, casted_arg)) |arg_val| {
+                        arg_val.hash(param_ty, &hasher);
+                        comptime_vals[i] = arg_val;
+                    } else {
+                        return sema.failWithNeededComptime(block, arg_src);
+                    }
+                }
+            }
+
+            const adapter: GenericCallAdapter = .{
+                .generic_fn = module_fn,
+                .precomputed_hash = hasher.final(),
+                .func_ty_info = func_ty_info,
+                .comptime_vals = comptime_vals,
+            };
+            const gop = try mod.monomorphed_funcs.getOrPutAdapted(gpa, {}, adapter);
+            if (gop.found_existing) {
+                const callee_func = gop.key_ptr.*;
+                break :res try sema.finishGenericCall(
+                    block,
+                    call_src,
+                    callee_func,
+                    func_src,
+                    uncasted_args,
+                    fn_info,
+                    zir_tags,
+                );
+            }
+            gop.key_ptr.* = try gpa.create(Module.Fn);
+            break :new_func gop.key_ptr.*;
+        };
+
+        {
+            try namespace.anon_decls.ensureUnusedCapacity(gpa, 1);
+
+            // Create a Decl for the new function.
+            const new_decl = try mod.allocateNewDecl(namespace, module_fn.owner_decl.src_node);
+            // TODO better names for generic function instantiations
+            const name_index = mod.getNextAnonNameIndex();
+            new_decl.name = try std.fmt.allocPrintZ(gpa, "{s}__anon_{d}", .{
+                module_fn.owner_decl.name, name_index,
+            });
+            new_decl.src_line = module_fn.owner_decl.src_line;
+            new_decl.is_pub = module_fn.owner_decl.is_pub;
+            new_decl.is_exported = module_fn.owner_decl.is_exported;
+            new_decl.has_align = module_fn.owner_decl.has_align;
+            new_decl.has_linksection = module_fn.owner_decl.has_linksection;
+            new_decl.zir_decl_index = module_fn.owner_decl.zir_decl_index;
+            new_decl.alive = true; // This Decl is called at runtime.
+            new_decl.has_tv = true;
+            new_decl.owns_tv = true;
+            new_decl.analysis = .in_progress;
+            new_decl.generation = mod.generation;
+
+            namespace.anon_decls.putAssumeCapacityNoClobber(new_decl, {});
+
+            var new_decl_arena = std.heap.ArenaAllocator.init(sema.gpa);
+            errdefer new_decl_arena.deinit();
+
+            // Re-run the block that creates the function, with the comptime parameters
+            // pre-populated inside `inst_map`. This causes `param_comptime` and
+            // `param_anytype_comptime` ZIR instructions to be ignored, resulting in a
+            // new, monomorphized function, with the comptime parameters elided.
+            var child_sema: Sema = .{
+                .mod = mod,
+                .gpa = gpa,
+                .arena = sema.arena,
+                .code = fn_zir,
+                .owner_decl = new_decl,
+                .namespace = namespace,
+                .func = null,
+                .owner_func = null,
+                .comptime_args = try new_decl_arena.allocator.alloc(TypedValue, uncasted_args.len),
+                .comptime_args_fn_inst = module_fn.zir_body_inst,
+                .preallocated_new_func = new_module_func,
+            };
+            defer child_sema.deinit();
+
+            var child_block: Scope.Block = .{
+                .parent = null,
+                .sema = &child_sema,
+                .src_decl = new_decl,
+                .instructions = .{},
+                .inlining = null,
+                .is_comptime = true,
+            };
+            defer {
+                child_block.instructions.deinit(gpa);
+                child_block.params.deinit(gpa);
+            }
+
+            try child_sema.inst_map.ensureUnusedCapacity(gpa, @intCast(u32, uncasted_args.len));
+            var arg_i: usize = 0;
+            for (fn_info.param_body) |inst| {
+                const is_comptime = switch (zir_tags[inst]) {
+                    .param_comptime, .param_anytype_comptime => true,
+                    .param, .param_anytype => false,
+                    else => continue,
+                } or func_ty_info.paramIsComptime(arg_i);
+                const arg_src = call_src; // TODO: better source location
+                const arg = uncasted_args[arg_i];
+                if (try sema.resolveMaybeUndefVal(block, arg_src, arg)) |arg_val| {
+                    const child_arg = try child_sema.addConstant(sema.typeOf(arg), arg_val);
+                    child_sema.inst_map.putAssumeCapacityNoClobber(inst, child_arg);
+                } else if (is_comptime) {
+                    return sema.failWithNeededComptime(block, arg_src);
+                }
+                arg_i += 1;
+            }
+            const new_func_inst = try child_sema.resolveBody(&child_block, fn_info.param_body);
+            const new_func_val = try child_sema.resolveConstValue(&child_block, .unneeded, new_func_inst);
+            const new_func = new_func_val.castTag(.function).?.data;
+            assert(new_func == new_module_func);
+
+            arg_i = 0;
+            for (fn_info.param_body) |inst| {
+                switch (zir_tags[inst]) {
+                    .param_comptime, .param_anytype_comptime, .param, .param_anytype => {},
+                    else => continue,
+                }
+                const arg = child_sema.inst_map.get(inst).?;
+                const arg_val = (child_sema.resolveMaybeUndefValAllowVariables(&child_block, .unneeded, arg) catch unreachable).?;
+
+                if (arg_val.tag() == .generic_poison) {
+                    child_sema.comptime_args[arg_i] = .{
+                        .ty = Type.initTag(.noreturn),
+                        .val = Value.initTag(.unreachable_value),
+                    };
+                } else {
+                    child_sema.comptime_args[arg_i] = .{
+                        .ty = try child_sema.typeOf(arg).copy(&new_decl_arena.allocator),
+                        .val = try arg_val.copy(&new_decl_arena.allocator),
+                    };
+                }
+
+                arg_i += 1;
+            }
+
+            // Populate the Decl ty/val with the function and its type.
+            new_decl.ty = try child_sema.typeOf(new_func_inst).copy(&new_decl_arena.allocator);
+            new_decl.val = try Value.Tag.function.create(&new_decl_arena.allocator, new_func);
+            new_decl.analysis = .complete;
 
-        const result = try sema.analyzeBlockBody(block, call_src, &child_block, merges);
+            // The generic function Decl is guaranteed to be the first dependency
+            // of each of its instantiations.
+            assert(new_decl.dependencies.keys().len == 0);
+            try mod.declareDeclDependency(new_decl, module_fn.owner_decl);
 
-        break :res result;
+            // Queue up a `codegen_func` work item for the new Fn. The `comptime_args` field
+            // will be populated, ensuring it will have `analyzeBody` called with the ZIR
+            // parameters mapped appropriately.
+            try mod.comp.bin_file.allocateDeclIndexes(new_decl);
+            try mod.comp.work_queue.writeItem(.{ .codegen_func = new_func });
+
+            try new_decl.finalizeNewArena(&new_decl_arena);
+        }
+
+        break :res try sema.finishGenericCall(
+            block,
+            call_src,
+            new_module_func,
+            func_src,
+            uncasted_args,
+            fn_info,
+            zir_tags,
+        );
     } else res: {
-        if (func_ty.fnIsGeneric()) {
-            return sema.mod.fail(&block.base, func_src, "TODO implement generic fn call", .{});
+        const args = try sema.arena.alloc(Air.Inst.Ref, uncasted_args.len);
+        for (uncasted_args) |uncasted_arg, i| {
+            if (i < fn_params_len) {
+                const param_ty = func_ty.fnParamType(i);
+                const arg_src = call_src; // TODO: better source location
+                args[i] = try sema.coerce(block, param_ty, uncasted_arg, arg_src);
+            } else {
+                args[i] = uncasted_arg;
+            }
         }
+
         try sema.requireRuntimeBlock(block, call_src);
         try sema.air_extra.ensureUnusedCapacity(gpa, @typeInfo(Air.Call).Struct.fields.len +
             args.len);
@@ -2561,6 +2787,75 @@ fn analyzeCall(
     return result;
 }
 
+fn finishGenericCall(
+    sema: *Sema,
+    block: *Scope.Block,
+    call_src: LazySrcLoc,
+    callee: *Module.Fn,
+    func_src: LazySrcLoc,
+    uncasted_args: []const Air.Inst.Ref,
+    fn_info: Zir.FnInfo,
+    zir_tags: []const Zir.Inst.Tag,
+) CompileError!Air.Inst.Ref {
+    const callee_inst = try sema.analyzeDeclVal(block, func_src, callee.owner_decl);
+
+    // Make a runtime call to the new function, making sure to omit the comptime args.
+    try sema.requireRuntimeBlock(block, call_src);
+
+    const comptime_args = callee.comptime_args.?;
+    const runtime_args_len = count: {
+        var count: u32 = 0;
+        var arg_i: usize = 0;
+        for (fn_info.param_body) |inst| {
+            switch (zir_tags[inst]) {
+                .param_comptime, .param_anytype_comptime, .param, .param_anytype => {
+                    if (comptime_args[arg_i].val.tag() == .unreachable_value) {
+                        count += 1;
+                    }
+                    arg_i += 1;
+                },
+                else => continue,
+            }
+        }
+        break :count count;
+    };
+    const runtime_args = try sema.arena.alloc(Air.Inst.Ref, runtime_args_len);
+    {
+        const new_fn_ty = callee.owner_decl.ty;
+        var runtime_i: u32 = 0;
+        var total_i: u32 = 0;
+        for (fn_info.param_body) |inst| {
+            switch (zir_tags[inst]) {
+                .param_comptime, .param_anytype_comptime, .param, .param_anytype => {},
+                else => continue,
+            }
+            const is_runtime = comptime_args[total_i].val.tag() == .unreachable_value;
+            if (is_runtime) {
+                const param_ty = new_fn_ty.fnParamType(runtime_i);
+                const arg_src = call_src; // TODO: better source location
+                const uncasted_arg = uncasted_args[total_i];
+                const casted_arg = try sema.coerce(block, param_ty, uncasted_arg, arg_src);
+                runtime_args[runtime_i] = casted_arg;
+                runtime_i += 1;
+            }
+            total_i += 1;
+        }
+    }
+    try sema.air_extra.ensureUnusedCapacity(sema.gpa, @typeInfo(Air.Call).Struct.fields.len +
+        runtime_args_len);
+    const func_inst = try block.addInst(.{
+        .tag = .call,
+        .data = .{ .pl_op = .{
+            .operand = callee_inst,
+            .payload = sema.addExtraAssumeCapacity(Air.Call{
+                .args_len = runtime_args_len,
+            }),
+        } },
+    });
+    sema.appendRefsAssumeCapacity(runtime_args);
+    return func_inst;
+}
+
 fn zirIntType(sema: *Sema, block: *Scope.Block, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {
     _ = block;
     const tracy = trace(@src());
@@ -3186,13 +3481,15 @@ fn zirFunc(
 
     const inst_data = sema.code.instructions.items(.data)[inst].pl_node;
     const extra = sema.code.extraData(Zir.Inst.Func, inst_data.payload_index);
-    const param_types = sema.code.refSlice(extra.end, extra.data.param_types_len);
+    var extra_index = extra.end;
+    const ret_ty_body = sema.code.extra[extra_index..][0..extra.data.ret_body_len];
+    extra_index += ret_ty_body.len;
 
     var body_inst: Zir.Inst.Index = 0;
     var src_locs: Zir.Inst.Func.SrcLocs = undefined;
     if (extra.data.body_len != 0) {
         body_inst = inst;
-        const extra_index = extra.end + extra.data.param_types_len + extra.data.body_len;
+        extra_index += extra.data.body_len;
         src_locs = sema.code.extraData(Zir.Inst.Func.SrcLocs, extra_index).data;
     }
 
@@ -3204,9 +3501,8 @@ fn zirFunc(
     return sema.funcCommon(
         block,
         inst_data.src_node,
-        param_types,
         body_inst,
-        extra.data.return_type,
+        ret_ty_body,
         cc,
         Value.initTag(.null_value),
         false,
@@ -3214,7 +3510,6 @@ fn zirFunc(
         false,
         src_locs,
         null,
-        &.{},
     );
 }
 
@@ -3222,9 +3517,8 @@ fn funcCommon(
     sema: *Sema,
     block: *Scope.Block,
     src_node_offset: i32,
-    zir_param_types: []const Zir.Inst.Ref,
     body_inst: Zir.Inst.Index,
-    zir_return_type: Zir.Inst.Ref,
+    ret_ty_body: []const Zir.Inst.Index,
     cc: std.builtin.CallingConvention,
     align_val: Value,
     var_args: bool,
@@ -3232,21 +3526,59 @@ fn funcCommon(
     is_extern: bool,
     src_locs: Zir.Inst.Func.SrcLocs,
     opt_lib_name: ?[]const u8,
-    comptime_bits: []const u32,
 ) CompileError!Air.Inst.Ref {
     const src: LazySrcLoc = .{ .node_offset = src_node_offset };
     const ret_ty_src: LazySrcLoc = .{ .node_offset_fn_type_ret_ty = src_node_offset };
-    const bare_return_type = try sema.resolveType(block, ret_ty_src, zir_return_type);
+
+    // The return type body might be a type expression that depends on generic parameters.
+    // In such case we need to use a generic_poison value for the return type and mark
+    // the function as generic.
+    var is_generic = false;
+    const bare_return_type: Type = ret_ty: {
+        if (ret_ty_body.len == 0) break :ret_ty Type.initTag(.void);
+
+        const err = err: {
+            // Make sure any nested param instructions don't clobber our work.
+            const prev_params = block.params;
+            block.params = .{};
+            defer {
+                block.params.deinit(sema.gpa);
+                block.params = prev_params;
+            }
+            if (sema.resolveBody(block, ret_ty_body)) |ret_ty_inst| {
+                if (sema.analyzeAsType(block, ret_ty_src, ret_ty_inst)) |ret_ty| {
+                    break :ret_ty ret_ty;
+                } else |err| break :err err;
+            } else |err| break :err err;
+        };
+        switch (err) {
+            error.GenericPoison => {
+                // The type is not available until the generic instantiation.
+                is_generic = true;
+                break :ret_ty Type.initTag(.generic_poison);
+            },
+            else => |e| return e,
+        }
+    };
 
     const mod = sema.mod;
 
-    const new_func = if (body_inst == 0) undefined else try sema.gpa.create(Module.Fn);
+    const new_func: *Module.Fn = new_func: {
+        if (body_inst == 0) break :new_func undefined;
+        if (sema.comptime_args_fn_inst == body_inst) {
+            const new_func = sema.preallocated_new_func.?;
+            sema.preallocated_new_func = null; // take ownership
+            break :new_func new_func;
+        }
+        break :new_func try sema.gpa.create(Module.Fn);
+    };
     errdefer if (body_inst != 0) sema.gpa.destroy(new_func);
 
     const fn_ty: Type = fn_ty: {
         // Hot path for some common function types.
-        if (zir_param_types.len == 0 and !var_args and align_val.tag() == .null_value and
-            !inferred_error_set)
+        // TODO can we eliminate some of these Type tag values? seems unnecessarily complicated.
+        if (!is_generic and block.params.items.len == 0 and !var_args and
+            align_val.tag() == .null_value and !inferred_error_set)
         {
             if (bare_return_type.zigTypeTag() == .NoReturn and cc == .Unspecified) {
                 break :fn_ty Type.initTag(.fn_noreturn_no_args);
@@ -3265,30 +3597,24 @@ fn funcCommon(
             }
         }
 
-        var any_are_comptime = false;
-        const param_types = try sema.arena.alloc(Type, zir_param_types.len);
-        for (zir_param_types) |param_type, i| {
-            // TODO make a compile error from `resolveType` report the source location
-            // of the specific parameter. Will need to take a similar strategy as
-            // `resolveSwitchItemVal` to avoid resolving the source location unless
-            // we actually need to report an error.
-            const param_src = src;
-            param_types[i] = try sema.resolveType(block, param_src, param_type);
-
-            any_are_comptime = any_are_comptime or blk: {
-                if (comptime_bits.len == 0)
-                    break :blk false;
-                const bag = comptime_bits[i / 32];
-                const is_comptime = @truncate(u1, bag >> @intCast(u5, i % 32)) != 0;
-                break :blk is_comptime;
-            };
+        const param_types = try sema.arena.alloc(Type, block.params.items.len);
+        const comptime_params = try sema.arena.alloc(bool, block.params.items.len);
+        for (block.params.items) |param, i| {
+            param_types[i] = param.ty;
+            comptime_params[i] = param.is_comptime;
+            is_generic = is_generic or param.is_comptime or
+                param.ty.tag() == .generic_poison or param.ty.requiresComptime();
         }
 
         if (align_val.tag() != .null_value) {
             return mod.fail(&block.base, src, "TODO implement support for function prototypes to have alignment specified", .{});
         }
 
-        const return_type = if (!inferred_error_set) bare_return_type else blk: {
+        is_generic = is_generic or bare_return_type.requiresComptime();
+
+        const return_type = if (!inferred_error_set or bare_return_type.tag() == .generic_poison)
+            bare_return_type
+        else blk: {
             const error_set_ty = try Type.Tag.error_set_inferred.create(sema.arena, .{
                 .func = new_func,
                 .map = .{},
@@ -3301,10 +3627,11 @@ fn funcCommon(
 
         break :fn_ty try Type.Tag.function.create(sema.arena, .{
             .param_types = param_types,
+            .comptime_params = comptime_params.ptr,
             .return_type = return_type,
             .cc = cc,
             .is_var_args = var_args,
-            .is_generic = any_are_comptime,
+            .is_generic = is_generic,
         });
     };
 
@@ -3363,11 +3690,16 @@ fn funcCommon(
     const is_inline = fn_ty.fnCallingConvention() == .Inline;
     const anal_state: Module.Fn.Analysis = if (is_inline) .inline_only else .queued;
 
+    const comptime_args: ?[*]TypedValue = if (sema.comptime_args_fn_inst == body_inst) blk: {
+        break :blk if (sema.comptime_args.len == 0) null else sema.comptime_args.ptr;
+    } else null;
+
     const fn_payload = try sema.arena.create(Value.Payload.Function);
     new_func.* = .{
         .state = anal_state,
         .zir_body_inst = body_inst,
         .owner_decl = sema.owner_decl,
+        .comptime_args = comptime_args,
         .lbrace_line = src_locs.lbrace_line,
         .rbrace_line = src_locs.rbrace_line,
         .lbrace_column = @truncate(u16, src_locs.columns),
@@ -3380,6 +3712,113 @@ fn funcCommon(
     return sema.addConstant(fn_ty, Value.initPayload(&fn_payload.base));
 }
 
+fn zirParam(
+    sema: *Sema,
+    block: *Scope.Block,
+    inst: Zir.Inst.Index,
+    is_comptime: bool,
+) CompileError!void {
+    const inst_data = sema.code.instructions.items(.data)[inst].pl_tok;
+    const src = inst_data.src();
+    const extra = sema.code.extraData(Zir.Inst.Param, inst_data.payload_index);
+    const param_name = sema.code.nullTerminatedString(extra.data.name);
+    const body = sema.code.extra[extra.end..][0..extra.data.body_len];
+
+    // TODO check if param_name shadows a Decl. This only needs to be done if
+    // usingnamespace is implemented.
+    _ = param_name;
+
+    // We could be in a generic function instantiation, or we could be evaluating a generic
+    // function without any comptime args provided.
+    const param_ty = param_ty: {
+        const err = err: {
+            // Make sure any nested param instructions don't clobber our work.
+            const prev_params = block.params;
+            block.params = .{};
+            defer {
+                block.params.deinit(sema.gpa);
+                block.params = prev_params;
+            }
+
+            if (sema.resolveBody(block, body)) |param_ty_inst| {
+                if (sema.analyzeAsType(block, src, param_ty_inst)) |param_ty| {
+                    break :param_ty param_ty;
+                } else |err| break :err err;
+            } else |err| break :err err;
+        };
+        switch (err) {
+            error.GenericPoison => {
+                // The type is not available until the generic instantiation.
+                // We result the param instruction with a poison value and
+                // insert an anytype parameter.
+                try block.params.append(sema.gpa, .{
+                    .ty = Type.initTag(.generic_poison),
+                    .is_comptime = is_comptime,
+                });
+                try sema.inst_map.putNoClobber(sema.gpa, inst, .generic_poison);
+                return;
+            },
+            else => |e| return e,
+        }
+    };
+    if (sema.inst_map.get(inst)) |arg| {
+        if (is_comptime or param_ty.requiresComptime()) {
+            // We have a comptime value for this parameter so it should be elided from the
+            // function type of the function instruction in this block.
+            const coerced_arg = try sema.coerce(block, param_ty, arg, src);
+            sema.inst_map.putAssumeCapacity(inst, coerced_arg);
+            return;
+        }
+        // Even though a comptime argument is provided, the generic function wants to treat
+        // this as a runtime parameter.
+        assert(sema.inst_map.remove(inst));
+    }
+
+    try block.params.append(sema.gpa, .{
+        .ty = param_ty,
+        .is_comptime = is_comptime or param_ty.requiresComptime(),
+    });
+    const result = try sema.addConstant(param_ty, Value.initTag(.generic_poison));
+    try sema.inst_map.putNoClobber(sema.gpa, inst, result);
+}
+
+fn zirParamAnytype(
+    sema: *Sema,
+    block: *Scope.Block,
+    inst: Zir.Inst.Index,
+    is_comptime: bool,
+) CompileError!void {
+    const inst_data = sema.code.instructions.items(.data)[inst].str_tok;
+    const param_name = inst_data.get(sema.code);
+
+    // TODO check if param_name shadows a Decl. This only needs to be done if
+    // usingnamespace is implemented.
+    _ = param_name;
+
+    if (sema.inst_map.get(inst)) |air_ref| {
+        const param_ty = sema.typeOf(air_ref);
+        if (is_comptime or param_ty.requiresComptime()) {
+            // We have a comptime value for this parameter so it should be elided from the
+            // function type of the function instruction in this block.
+            return;
+        }
+        // The map is already populated but we do need to add a runtime parameter.
+        try block.params.append(sema.gpa, .{
+            .ty = param_ty,
+            .is_comptime = false,
+        });
+        return;
+    }
+
+    // We are evaluating a generic function without any comptime args provided.
+
+    try block.params.append(sema.gpa, .{
+        .ty = Type.initTag(.generic_poison),
+        .is_comptime = is_comptime,
+    });
+    try sema.inst_map.put(sema.gpa, inst, .generic_poison);
+}
+
 fn zirAs(sema: *Sema, block: *Scope.Block, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {
     const tracy = trace(@src());
     defer tracy.end();
@@ -4898,18 +5337,18 @@ fn analyzeArithmetic(
 ) CompileError!Air.Inst.Ref {
     const lhs_ty = sema.typeOf(lhs);
     const rhs_ty = sema.typeOf(rhs);
-    if (lhs_ty.zigTypeTag() == .Vector and rhs_ty.zigTypeTag() == .Vector) {
+    const lhs_zig_ty_tag = try lhs_ty.zigTypeTagOrPoison();
+    const rhs_zig_ty_tag = try rhs_ty.zigTypeTagOrPoison();
+    if (lhs_zig_ty_tag == .Vector and rhs_zig_ty_tag == .Vector) {
         if (lhs_ty.arrayLen() != rhs_ty.arrayLen()) {
             return sema.mod.fail(&block.base, src, "vector length mismatch: {d} and {d}", .{
-                lhs_ty.arrayLen(),
-                rhs_ty.arrayLen(),
+                lhs_ty.arrayLen(), rhs_ty.arrayLen(),
             });
         }
         return sema.mod.fail(&block.base, src, "TODO implement support for vectors in zirBinOp", .{});
-    } else if (lhs_ty.zigTypeTag() == .Vector or rhs_ty.zigTypeTag() == .Vector) {
+    } else if (lhs_zig_ty_tag == .Vector or rhs_zig_ty_tag == .Vector) {
         return sema.mod.fail(&block.base, src, "mixed scalar and vector operands to binary expression: '{}' and '{}'", .{
-            lhs_ty,
-            rhs_ty,
+            lhs_ty, rhs_ty,
         });
     }
 
@@ -4929,7 +5368,9 @@ fn analyzeArithmetic(
     const is_float = scalar_tag == .Float or scalar_tag == .ComptimeFloat;
 
     if (!is_int and !(is_float and floatOpAllowed(zir_tag))) {
-        return sema.mod.fail(&block.base, src, "invalid operands to binary expression: '{s}' and '{s}'", .{ @tagName(lhs_ty.zigTypeTag()), @tagName(rhs_ty.zigTypeTag()) });
+        return sema.mod.fail(&block.base, src, "invalid operands to binary expression: '{s}' and '{s}'", .{
+            @tagName(lhs_zig_ty_tag), @tagName(rhs_zig_ty_tag),
+        });
     }
 
     if (try sema.resolveMaybeUndefVal(block, lhs_src, casted_lhs)) |lhs_val| {
@@ -5728,6 +6169,10 @@ fn analyzeRet(
     const casted_operand = if (!need_coercion) operand else op: {
         const func = sema.func.?;
         const fn_ty = func.owner_decl.ty;
+        // TODO: In the case of a comptime/inline function call of a generic function,
+        // this needs to be the resolved return type based on the function parameter type
+        // expressions being evaluated with comptime arguments passed in. Otherwise, this
+        // ends up being .generic_poison and failing the comptime/inline function call analysis.
         const fn_ret_ty = fn_ty.fnReturnType();
         break :op try sema.coerce(block, fn_ret_ty, operand, src);
     };
@@ -6545,15 +6990,8 @@ fn zirFuncExtended(
         break :blk align_tv.val;
     } else Value.initTag(.null_value);
 
-    const comptime_bits: []const u32 = if (!small.has_comptime_bits) &.{} else blk: {
-        const amt = (extra.data.param_types_len + 31) / 32;
-        const bit_bags = sema.code.extra[extra_index..][0..amt];
-        extra_index += amt;
-        break :blk bit_bags;
-    };
-
-    const param_types = sema.code.refSlice(extra_index, extra.data.param_types_len);
-    extra_index += param_types.len;
+    const ret_ty_body = sema.code.extra[extra_index..][0..extra.data.ret_body_len];
+    extra_index += ret_ty_body.len;
 
     var body_inst: Zir.Inst.Index = 0;
     var src_locs: Zir.Inst.Func.SrcLocs = undefined;
@@ -6570,9 +7008,8 @@ fn zirFuncExtended(
     return sema.funcCommon(
         block,
         extra.data.src_node,
-        param_types,
         body_inst,
-        extra.data.return_type,
+        ret_ty_body,
         cc,
         align_val,
         is_var_args,
@@ -6580,7 +7017,6 @@ fn zirFuncExtended(
         is_extern,
         src_locs,
         lib_name,
-        comptime_bits,
     );
 }
 
@@ -6797,19 +7233,12 @@ fn safetyPanic(
     const msg_inst = msg_inst: {
         // TODO instead of making a new decl for every panic in the entire compilation,
         // introduce the concept of a reference-counted decl for these
-        var new_decl_arena = std.heap.ArenaAllocator.init(sema.gpa);
-        errdefer new_decl_arena.deinit();
-
-        const decl_ty = try Type.Tag.array_u8.create(&new_decl_arena.allocator, msg.len);
-        const decl_val = try Value.Tag.bytes.create(&new_decl_arena.allocator, msg);
-
-        const new_decl = try sema.mod.createAnonymousDecl(&block.base, .{
-            .ty = decl_ty,
-            .val = decl_val,
-        });
-        errdefer sema.mod.deleteAnonDecl(&block.base, new_decl);
-        try new_decl.finalizeNewArena(&new_decl_arena);
-        break :msg_inst try sema.analyzeDeclRef(new_decl);
+        var anon_decl = try block.startAnonDecl();
+        defer anon_decl.deinit();
+        break :msg_inst try sema.analyzeDeclRef(try anon_decl.finish(
+            try Type.Tag.array_u8.create(anon_decl.arena(), msg.len),
+            try Value.Tag.bytes.create(anon_decl.arena(), msg),
+        ));
     };
 
     const casted_msg_inst = try sema.coerce(block, Type.initTag(.const_slice_u8), msg_inst, src);
@@ -7469,8 +7898,10 @@ fn coerce(
     inst: Air.Inst.Ref,
     inst_src: LazySrcLoc,
 ) CompileError!Air.Inst.Ref {
-    if (dest_type_unresolved.tag() == .var_args_param) {
-        return sema.coerceVarArgParam(block, inst, inst_src);
+    switch (dest_type_unresolved.tag()) {
+        .var_args_param => return sema.coerceVarArgParam(block, inst, inst_src),
+        .generic_poison => return inst,
+        else => {},
     }
     const dest_type_src = inst_src; // TODO better source location
     const dest_type = try sema.resolveTypeFields(block, dest_type_src, dest_type_unresolved);
@@ -8671,6 +9102,7 @@ fn typeHasOnePossibleValue(
 
         .inferred_alloc_const => unreachable,
         .inferred_alloc_mut => unreachable,
+        .generic_poison => return error.GenericPoison,
     };
 }
 
@@ -8793,6 +9225,8 @@ pub fn addType(sema: *Sema, ty: Type) !Air.Inst.Ref {
         .fn_ccc_void_no_args => return .fn_ccc_void_no_args_type,
         .single_const_pointer_to_comptime_int => return .single_const_pointer_to_comptime_int_type,
         .const_slice_u8 => return .const_slice_u8_type,
+        .anyerror_void_error_union => return .anyerror_void_error_union_type,
+        .generic_poison => return .generic_poison_type,
         else => {},
     }
     try sema.air_instructions.append(sema.gpa, .{
@@ -8810,7 +9244,7 @@ fn addConstUndef(sema: *Sema, ty: Type) CompileError!Air.Inst.Ref {
     return sema.addConstant(ty, Value.initTag(.undef));
 }
 
-fn addConstant(sema: *Sema, ty: Type, val: Value) CompileError!Air.Inst.Ref {
+pub fn addConstant(sema: *Sema, ty: Type, val: Value) SemaError!Air.Inst.Ref {
     const gpa = sema.gpa;
     const ty_inst = try sema.addType(ty);
     try sema.air_values.append(gpa, val);