From 0cd361219c107bce48f2d7b44c6f3dd05ea6ccf4 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Fri, 20 Aug 2021 15:23:55 -0700 Subject: stage2: field type expressions support referencing locals The big change in this commit is making `semaDecl` resolve the fields if the Decl ends up being a struct or union. It needs to do this while the `Sema` is still in scope, because it will have the resolved AIR instructions that the field type expressions possibly reference. We do this after the decl is populated and set to `complete` so that a `Decl` may reference itself. Everything else is fixes and improvements to make the test suite pass again after making this change. * New AIR instruction: `ptr_elem_ptr` - Implemented for LLVM backend * New Type tag: `type_info` which represents `std.builtin.TypeInfo`. It is used by AstGen for the operand type of `@Type`. * ZIR instruction `set_float_mode` uses `coerced_ty` to avoid superfluous `as` instruction on operand. * ZIR instruction `Type` uses `coerced_ty` to properly handle result location type of operand. * Fix two instances of `enum_nonexhaustive` Value Tag not handled properly - it should generally be handled the same as `enum_full`. * Fix struct and union field resolution not copying Type and Value objects into its Decl arena. * Fix enum tag value resolution discarding the ZIR=>AIR instruction map for the child Sema, when they still needed to be accessed. * Fix `zirResolveInferredAlloc` use-after-free in the AIR instructions data array. * Fix `elemPtrArray` not respecting const/mutable attribute of pointer in the result type. * Fix LLVM backend crashing when `updateDeclExports` is called before `updateDecl`/`updateFunc` (which is, according to the API, perfectly legal for the frontend to do). * Fix LLVM backend handling element pointer of pointer-to-array. It needed another index in the GEP otherwise LLVM saw the wrong type. * Fix LLVM test cases not returning 0 from main, causing test failures. Fixes a regression introduced in 6a5094872f10acc629543cc7f10533b438d0283a. * Implement comptime shift-right. * Implement `@Type` for integers and `@TypeInfo` for integers. * Implement union initialization syntax. * Implement `zirFieldType` for unions. * Implement `elemPtrArray` for a runtime-known operand. * Make `zirLog2IntType` support RHS of shift being `comptime_int`. In this case it returns `comptime_int`. The motivating test case for this commit was originally: ```zig test "example" { var l: List(10) = undefined; l.array[1] = 1; } fn List(comptime L: usize) type { var T = u8; return struct { array: [L]T, }; } ``` However I changed it to: ```zig test "example" { var l: List = undefined; l.array[1] = 1; } const List = blk: { const T = [10]u8; break :blk struct { array: T, }; }; ``` Which ended up being a similar, smaller problem. The former test case will require a similar solution in the implementation of comptime function calls - checking if the result of the function call is a struct or union, and using the child `Sema` before it is destroyed to resolve the fields. --- src/Module.zig | 320 +++------------------------------------------------------ 1 file changed, 15 insertions(+), 305 deletions(-) (limited to 'src/Module.zig') diff --git a/src/Module.zig b/src/Module.zig index 319363e9b8..d55931bec8 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -554,8 +554,8 @@ pub const Decl = struct { assert(struct_obj.owner_decl == decl); return &struct_obj.namespace; }, - .enum_full => { - const enum_obj = ty.castTag(.enum_full).?.data; + .enum_full, .enum_nonexhaustive => { + const enum_obj = ty.cast(Type.Payload.EnumFull).?.data; assert(enum_obj.owner_decl == decl); return &enum_obj.namespace; }, @@ -660,6 +660,7 @@ pub const Struct = struct { /// is necessary to determine whether it has bits at runtime. known_has_bits: bool, + /// The `Type` and `Value` memory is owned by the arena of the Struct's owner_decl. pub const Field = struct { /// Uses `noreturn` to indicate `anytype`. /// undefined until `status` is `have_field_types` or `have_layout`. @@ -3091,6 +3092,9 @@ fn semaDecl(mod: *Module, decl: *Decl) !bool { if (linksection_ref == .none) break :blk Value.initTag(.null_value); break :blk (try sema.resolveInstConst(&block_scope, src, linksection_ref)).val; }; + // Note this resolves the type of the Decl, not the value; if this Decl + // is a struct, for example, this resolves `type` (which needs no resolution), + // not the struct itself. try sema.resolveTypeLayout(&block_scope, src, decl_tv.ty); // We need the memory for the Type to go into the arena for the Decl @@ -3193,6 +3197,15 @@ fn semaDecl(mod: *Module, decl: *Decl) !bool { if (type_changed and mod.emit_h != null) { try mod.comp.work_queue.writeItem(.{ .emit_h_decl = decl }); } + } else if (decl_tv.ty.zigTypeTag() == .Type) { + // In case this Decl is a struct or union, we need to resolve the fields + // while we still have the `Sema` in scope, so that the field type expressions + // can use the resolved AIR instructions that they possibly reference. + // We do this after the decl is populated and set to `complete` so that a `Decl` + // may reference itself. + var buffer: Value.ToTypeBuffer = undefined; + const ty = decl.val.toType(&buffer); + try sema.resolveDeclFields(&block_scope, src, ty); } if (decl.is_exported) { @@ -4450,309 +4463,6 @@ pub const PeerTypeCandidateSrc = union(enum) { } }; -pub fn analyzeStructFields(mod: *Module, struct_obj: *Struct) CompileError!void { - const tracy = trace(@src()); - defer tracy.end(); - - const gpa = mod.gpa; - const zir = struct_obj.owner_decl.namespace.file_scope.zir; - const extended = zir.instructions.items(.data)[struct_obj.zir_index].extended; - assert(extended.opcode == .struct_decl); - const small = @bitCast(Zir.Inst.StructDecl.Small, extended.small); - var extra_index: usize = extended.operand; - - const src: LazySrcLoc = .{ .node_offset = struct_obj.node_offset }; - extra_index += @boolToInt(small.has_src_node); - - const body_len = if (small.has_body_len) blk: { - const body_len = zir.extra[extra_index]; - extra_index += 1; - break :blk body_len; - } else 0; - - const fields_len = if (small.has_fields_len) blk: { - const fields_len = zir.extra[extra_index]; - extra_index += 1; - break :blk fields_len; - } else 0; - - const decls_len = if (small.has_decls_len) decls_len: { - const decls_len = zir.extra[extra_index]; - extra_index += 1; - break :decls_len decls_len; - } else 0; - - // Skip over decls. - var decls_it = zir.declIteratorInner(extra_index, decls_len); - while (decls_it.next()) |_| {} - extra_index = decls_it.extra_index; - - const body = zir.extra[extra_index..][0..body_len]; - if (fields_len == 0) { - assert(body.len == 0); - return; - } - extra_index += body.len; - - var decl_arena = struct_obj.owner_decl.value_arena.?.promote(gpa); - defer struct_obj.owner_decl.value_arena.?.* = decl_arena.state; - - try struct_obj.fields.ensureCapacity(&decl_arena.allocator, fields_len); - - // We create a block for the field type instructions because they - // may need to reference Decls from inside the struct namespace. - // Within the field type, default value, and alignment expressions, the "owner decl" - // should be the struct itself. Thus we need a new Sema. - var sema: Sema = .{ - .mod = mod, - .gpa = gpa, - .arena = &decl_arena.allocator, - .code = zir, - .owner_decl = struct_obj.owner_decl, - .namespace = &struct_obj.namespace, - .owner_func = null, - .func = null, - .fn_ret_ty = Type.initTag(.void), - }; - defer sema.deinit(); - - var block: Scope.Block = .{ - .parent = null, - .sema = &sema, - .src_decl = struct_obj.owner_decl, - .instructions = .{}, - .inlining = null, - .is_comptime = true, - }; - defer assert(block.instructions.items.len == 0); // should all be comptime instructions - - if (body.len != 0) { - _ = try sema.analyzeBody(&block, body); - } - - const bits_per_field = 4; - const fields_per_u32 = 32 / bits_per_field; - const bit_bags_count = std.math.divCeil(usize, fields_len, fields_per_u32) catch unreachable; - var bit_bag_index: usize = extra_index; - extra_index += bit_bags_count; - var cur_bit_bag: u32 = undefined; - var field_i: u32 = 0; - while (field_i < fields_len) : (field_i += 1) { - if (field_i % fields_per_u32 == 0) { - cur_bit_bag = zir.extra[bit_bag_index]; - bit_bag_index += 1; - } - const has_align = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - const has_default = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - const is_comptime = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - const unused = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - - _ = unused; - - const field_name_zir = zir.nullTerminatedString(zir.extra[extra_index]); - extra_index += 1; - const field_type_ref = @intToEnum(Zir.Inst.Ref, zir.extra[extra_index]); - extra_index += 1; - - // This string needs to outlive the ZIR code. - const field_name = try decl_arena.allocator.dupe(u8, field_name_zir); - if (field_type_ref == .none) { - return mod.fail(&block.base, src, "TODO: implement anytype struct field", .{}); - } - const field_ty: Type = if (field_type_ref == .none) - Type.initTag(.noreturn) - else - // TODO: if we need to report an error here, use a source location - // that points to this type expression rather than the struct. - // But only resolve the source location if we need to emit a compile error. - try sema.resolveType(&block, src, field_type_ref); - - const gop = struct_obj.fields.getOrPutAssumeCapacity(field_name); - assert(!gop.found_existing); - gop.value_ptr.* = .{ - .ty = field_ty, - .abi_align = Value.initTag(.abi_align_default), - .default_val = Value.initTag(.unreachable_value), - .is_comptime = is_comptime, - .offset = undefined, - }; - - if (has_align) { - const align_ref = @intToEnum(Zir.Inst.Ref, zir.extra[extra_index]); - extra_index += 1; - // TODO: if we need to report an error here, use a source location - // that points to this alignment expression rather than the struct. - // But only resolve the source location if we need to emit a compile error. - gop.value_ptr.abi_align = (try sema.resolveInstConst(&block, src, align_ref)).val; - } - if (has_default) { - const default_ref = @intToEnum(Zir.Inst.Ref, zir.extra[extra_index]); - extra_index += 1; - // TODO: if we need to report an error here, use a source location - // that points to this default value expression rather than the struct. - // But only resolve the source location if we need to emit a compile error. - gop.value_ptr.default_val = (try sema.resolveInstConst(&block, src, default_ref)).val; - } - } -} - -pub fn analyzeUnionFields(mod: *Module, union_obj: *Union) CompileError!void { - const tracy = trace(@src()); - defer tracy.end(); - - const gpa = mod.gpa; - const zir = union_obj.owner_decl.namespace.file_scope.zir; - const extended = zir.instructions.items(.data)[union_obj.zir_index].extended; - assert(extended.opcode == .union_decl); - const small = @bitCast(Zir.Inst.UnionDecl.Small, extended.small); - var extra_index: usize = extended.operand; - - const src: LazySrcLoc = .{ .node_offset = union_obj.node_offset }; - extra_index += @boolToInt(small.has_src_node); - - if (small.has_tag_type) { - extra_index += 1; - } - - const body_len = if (small.has_body_len) blk: { - const body_len = zir.extra[extra_index]; - extra_index += 1; - break :blk body_len; - } else 0; - - const fields_len = if (small.has_fields_len) blk: { - const fields_len = zir.extra[extra_index]; - extra_index += 1; - break :blk fields_len; - } else 0; - - const decls_len = if (small.has_decls_len) decls_len: { - const decls_len = zir.extra[extra_index]; - extra_index += 1; - break :decls_len decls_len; - } else 0; - - // Skip over decls. - var decls_it = zir.declIteratorInner(extra_index, decls_len); - while (decls_it.next()) |_| {} - extra_index = decls_it.extra_index; - - const body = zir.extra[extra_index..][0..body_len]; - if (fields_len == 0) { - assert(body.len == 0); - return; - } - extra_index += body.len; - - var decl_arena = union_obj.owner_decl.value_arena.?.promote(gpa); - defer union_obj.owner_decl.value_arena.?.* = decl_arena.state; - - try union_obj.fields.ensureCapacity(&decl_arena.allocator, fields_len); - - // We create a block for the field type instructions because they - // may need to reference Decls from inside the struct namespace. - // Within the field type, default value, and alignment expressions, the "owner decl" - // should be the struct itself. Thus we need a new Sema. - var sema: Sema = .{ - .mod = mod, - .gpa = gpa, - .arena = &decl_arena.allocator, - .code = zir, - .owner_decl = union_obj.owner_decl, - .namespace = &union_obj.namespace, - .owner_func = null, - .func = null, - .fn_ret_ty = Type.initTag(.void), - }; - defer sema.deinit(); - - var block: Scope.Block = .{ - .parent = null, - .sema = &sema, - .src_decl = union_obj.owner_decl, - .instructions = .{}, - .inlining = null, - .is_comptime = true, - }; - defer assert(block.instructions.items.len == 0); // should all be comptime instructions - - if (body.len != 0) { - _ = try sema.analyzeBody(&block, body); - } - - const bits_per_field = 4; - const fields_per_u32 = 32 / bits_per_field; - const bit_bags_count = std.math.divCeil(usize, fields_len, fields_per_u32) catch unreachable; - var bit_bag_index: usize = extra_index; - extra_index += bit_bags_count; - var cur_bit_bag: u32 = undefined; - var field_i: u32 = 0; - while (field_i < fields_len) : (field_i += 1) { - if (field_i % fields_per_u32 == 0) { - cur_bit_bag = zir.extra[bit_bag_index]; - bit_bag_index += 1; - } - const has_type = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - const has_align = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - const has_tag = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - const unused = @truncate(u1, cur_bit_bag) != 0; - cur_bit_bag >>= 1; - _ = unused; - - const field_name_zir = zir.nullTerminatedString(zir.extra[extra_index]); - extra_index += 1; - - const field_type_ref: Zir.Inst.Ref = if (has_type) blk: { - const field_type_ref = @intToEnum(Zir.Inst.Ref, zir.extra[extra_index]); - extra_index += 1; - break :blk field_type_ref; - } else .none; - - const align_ref: Zir.Inst.Ref = if (has_align) blk: { - const align_ref = @intToEnum(Zir.Inst.Ref, zir.extra[extra_index]); - extra_index += 1; - break :blk align_ref; - } else .none; - - if (has_tag) { - extra_index += 1; - } - - // This string needs to outlive the ZIR code. - const field_name = try decl_arena.allocator.dupe(u8, field_name_zir); - const field_ty: Type = if (field_type_ref == .none) - Type.initTag(.void) - else - // TODO: if we need to report an error here, use a source location - // that points to this type expression rather than the union. - // But only resolve the source location if we need to emit a compile error. - try sema.resolveType(&block, src, field_type_ref); - - const gop = union_obj.fields.getOrPutAssumeCapacity(field_name); - assert(!gop.found_existing); - gop.value_ptr.* = .{ - .ty = field_ty, - .abi_align = Value.initTag(.abi_align_default), - }; - - if (align_ref != .none) { - // TODO: if we need to report an error here, use a source location - // that points to this alignment expression rather than the struct. - // But only resolve the source location if we need to emit a compile error. - gop.value_ptr.abi_align = (try sema.resolveInstConst(&block, src, align_ref)).val; - } - } - - // TODO resolve the union tag_type_ref -} - /// Called from `performAllTheWork`, after all AstGen workers have finished, /// and before the main semantic analysis loop begins. pub fn processOutdatedAndDeletedDecls(mod: *Module) !void { -- cgit v1.2.3 From 2b40815a220bbbd657bfa441e304090f11f1eb4c Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Sat, 21 Aug 2021 15:00:40 -0700 Subject: stage2: fix wrong value for Decl owns_tv In the case of a comptime function call of a function that returns a type, resulting in a compiler crash on deinit(). --- src/Module.zig | 1 - src/Sema.zig | 4 ++++ test/behavior/generics.zig | 25 +++++++++++++++++++++++-- test/behavior/generics_stage1.zig | 21 --------------------- 4 files changed, 27 insertions(+), 24 deletions(-) (limited to 'src/Module.zig') diff --git a/src/Module.zig b/src/Module.zig index d55931bec8..29c091abd3 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -4037,7 +4037,6 @@ pub fn createAnonymousDeclFromDeclNamed( new_decl.ty = typed_value.ty; new_decl.val = typed_value.val; new_decl.has_tv = true; - new_decl.owns_tv = true; new_decl.analysis = .complete; new_decl.generation = mod.generation; diff --git a/src/Sema.zig b/src/Sema.zig index 8ffc828fba..36ac4d224d 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -866,6 +866,7 @@ fn zirStructDecl( .ty = Type.initTag(.type), .val = struct_val, }, type_name); + new_decl.owns_tv = true; errdefer sema.mod.deleteAnonDecl(&block.base, new_decl); struct_obj.* = .{ .owner_decl = new_decl, @@ -986,6 +987,7 @@ fn zirEnumDecl( .ty = Type.initTag(.type), .val = enum_val, }, type_name); + new_decl.owns_tv = true; errdefer sema.mod.deleteAnonDecl(&block.base, new_decl); enum_obj.* = .{ @@ -1152,6 +1154,7 @@ fn zirUnionDecl( .ty = Type.initTag(.type), .val = union_val, }, type_name); + new_decl.owns_tv = true; errdefer sema.mod.deleteAnonDecl(&block.base, new_decl); union_obj.* = .{ .owner_decl = new_decl, @@ -1223,6 +1226,7 @@ fn zirErrorSetDecl( .ty = Type.initTag(.type), .val = error_set_val, }, type_name); + new_decl.owns_tv = true; errdefer sema.mod.deleteAnonDecl(&block.base, new_decl); const names = try new_decl_arena.allocator.alloc([]const u8, fields.len); for (fields) |str_index, i| { diff --git a/test/behavior/generics.zig b/test/behavior/generics.zig index 2d487a6f16..ef772deb4e 100644 --- a/test/behavior/generics.zig +++ b/test/behavior/generics.zig @@ -80,7 +80,7 @@ fn max_f64(a: f64, b: f64) f64 { } test "type constructed by comptime function call" { - var l: List(10) = undefined; + var l: SimpleList(10) = undefined; l.array[0] = 10; l.array[1] = 11; l.array[2] = 12; @@ -90,9 +90,30 @@ test "type constructed by comptime function call" { try expect(ptr[2] == 12); } -fn List(comptime L: usize) type { +fn SimpleList(comptime L: usize) type { var T = u8; return struct { array: [L]T, }; } + +test "function with return type type" { + var list: List(i32) = undefined; + var list2: List(i32) = undefined; + list.length = 10; + list2.length = 10; + try expect(list.prealloc_items.len == 8); + try expect(list2.prealloc_items.len == 8); +} + +pub fn List(comptime T: type) type { + return SmallList(T, 8); +} + +pub fn SmallList(comptime T: type, comptime STATIC_SIZE: usize) type { + return struct { + items: []T, + length: usize, + prealloc_items: [STATIC_SIZE]T, + }; +} diff --git a/test/behavior/generics_stage1.zig b/test/behavior/generics_stage1.zig index 4b768a5b4f..4fa52f5377 100644 --- a/test/behavior/generics_stage1.zig +++ b/test/behavior/generics_stage1.zig @@ -3,27 +3,6 @@ const testing = std.testing; const expect = testing.expect; const expectEqual = testing.expectEqual; -pub fn List(comptime T: type) type { - return SmallList(T, 8); -} - -pub fn SmallList(comptime T: type, comptime STATIC_SIZE: usize) type { - return struct { - items: []T, - length: usize, - prealloc_items: [STATIC_SIZE]T, - }; -} - -test "function with return type type" { - var list: List(i32) = undefined; - var list2: List(i32) = undefined; - list.length = 10; - list2.length = 10; - try expect(list.prealloc_items.len == 8); - try expect(list2.prealloc_items.len == 8); -} - test "generic struct" { var a1 = GenNode(i32){ .value = 13, -- cgit v1.2.3 From f378b0adce80aa6f85d9bf6bf97172426de2c719 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Sat, 21 Aug 2021 20:42:45 -0700 Subject: stage2: comptime function with the same args is memoized * Introduce `memoized_calls` to `Module` which stores all the comptime function calls that are cached. It is keyed on the `*Fn` and the comptime arguments, but it does not yet properly detect comptime function pointers and avoid memoizing in this case. So it will have false positives for when a comptime function call mutates data through a pointer parameter. * Sema: Add a new helper function: `resolveConstMaybeUndefVal` * Value: add `enumToInt` method and use it in `zirEnumToInt`. It is also used by the hashing function. * Value: fix representation of optionals to match error unions. Previously it would not handle nested optionals correctly. Now it matches the memory layout of error unions and supports nested optionals properly. This required changes in all the backends for generating optional constants. * TypedValue gains `eql` and `hash` methods. * Value: Implement hashing for floats, optionals, and enums. Additionally, the zig type tag is added to the hash, where it was not previously, so that values of differing types will get different hashes. --- src/Module.zig | 77 +++++++++++++++++++-- src/Sema.zig | 155 +++++++++++++++++++++++++++++++----------- src/TypedValue.zig | 15 +++- src/codegen/c.zig | 16 +++-- src/codegen/llvm.zig | 33 ++++----- src/codegen/wasm.zig | 11 +-- src/value.zig | 107 ++++++++++++++++++++++++++--- test/behavior/eval.zig | 13 ++++ test/behavior/eval_stage1.zig | 13 ---- 9 files changed, 340 insertions(+), 100 deletions(-) (limited to 'src/Module.zig') diff --git a/src/Module.zig b/src/Module.zig index 29c091abd3..4ed39c9954 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -66,6 +66,10 @@ import_table: std.StringArrayHashMapUnmanaged(*Scope.File) = .{}, /// to the same function. monomorphed_funcs: MonomorphedFuncsSet = .{}, +/// The set of all comptime function calls that have been cached so that future calls +/// with the same parameters will get the same return value. +memoized_calls: MemoizedCallSet = .{}, + /// We optimize memory usage for a compilation with no compile errors by storing the /// error messages and mapping outside of `Decl`. /// The ErrorMsg memory is owned by the decl, using Module's general purpose allocator. @@ -157,6 +161,60 @@ const MonomorphedFuncsContext = struct { } }; +pub const MemoizedCallSet = std.HashMapUnmanaged( + MemoizedCall.Key, + MemoizedCall.Result, + MemoizedCall, + std.hash_map.default_max_load_percentage, +); + +pub const MemoizedCall = struct { + pub const Key = struct { + func: *Fn, + args: []TypedValue, + }; + + pub const Result = struct { + val: Value, + arena: std.heap.ArenaAllocator.State, + }; + + pub fn eql(ctx: @This(), a: Key, b: Key) bool { + _ = ctx; + + if (a.func != b.func) return false; + + assert(a.args.len == b.args.len); + for (a.args) |a_arg, arg_i| { + const b_arg = b.args[arg_i]; + if (!a_arg.eql(b_arg)) { + return false; + } + } + + return true; + } + + /// Must match `Sema.GenericCallAdapter.hash`. + pub fn hash(ctx: @This(), key: Key) u64 { + _ = ctx; + + var hasher = std.hash.Wyhash.init(0); + + // The generic function Decl is guaranteed to be the first dependency + // of each of its instantiations. + std.hash.autoHash(&hasher, @ptrToInt(key.func)); + + // This logic must be kept in sync with the logic in `analyzeCall` that + // computes the hash. + for (key.args) |arg| { + arg.hash(&hasher); + } + + return hasher.final(); + } +}; + /// A `Module` has zero or one of these depending on whether `-femit-h` is enabled. pub const GlobalEmitH = struct { /// Where to put the output. @@ -2255,15 +2313,26 @@ pub fn deinit(mod: *Module) void { } mod.export_owners.deinit(gpa); - var it = mod.global_error_set.keyIterator(); - while (it.next()) |key| { - gpa.free(key.*); + { + var it = mod.global_error_set.keyIterator(); + while (it.next()) |key| { + gpa.free(key.*); + } + mod.global_error_set.deinit(gpa); } - mod.global_error_set.deinit(gpa); mod.error_name_list.deinit(gpa); mod.test_functions.deinit(gpa); mod.monomorphed_funcs.deinit(gpa); + + { + var it = mod.memoized_calls.iterator(); + while (it.next()) |entry| { + gpa.free(entry.key_ptr.args); + entry.value_ptr.arena.promote(gpa).deinit(); + } + mod.memoized_calls.deinit(gpa); + } } fn freeExportList(gpa: *Allocator, export_list: []*Export) void { diff --git a/src/Sema.zig b/src/Sema.zig index 36ac4d224d..d543b59ac0 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -649,6 +649,24 @@ fn resolveValue( return sema.failWithNeededComptime(block, src); } +/// Value Tag `variable` will cause a compile error. +/// Value Tag `undef` may be returned. +fn resolveConstMaybeUndefVal( + sema: *Sema, + block: *Scope.Block, + src: LazySrcLoc, + inst: Air.Inst.Ref, +) CompileError!Value { + if (try sema.resolveMaybeUndefValAllowVariables(block, src, inst)) |val| { + switch (val.tag()) { + .variable => return sema.failWithNeededComptime(block, src), + .generic_poison => return error.GenericPoison, + else => return val, + } + } + return sema.failWithNeededComptime(block, src); +} + /// Will not return Value Tags: `variable`, `undef`. Instead they will emit compile errors. /// See `resolveValue` for an alternative. fn resolveConstValue( @@ -2565,6 +2583,19 @@ fn analyzeCall( defer merges.results.deinit(gpa); defer merges.br_list.deinit(gpa); + // If it's a comptime function call, we need to memoize it as long as no external + // comptime memory is mutated. + var memoized_call_key: Module.MemoizedCall.Key = undefined; + var delete_memoized_call_key = false; + defer if (delete_memoized_call_key) gpa.free(memoized_call_key.args); + if (is_comptime_call) { + memoized_call_key = .{ + .func = module_fn, + .args = try gpa.alloc(TypedValue, func_ty_info.param_types.len), + }; + delete_memoized_call_key = true; + } + try sema.emitBackwardBranch(&child_block, call_src); // This will have return instructions analyzed as break instructions to @@ -2589,12 +2620,32 @@ fn analyzeCall( const arg_src = call_src; // TODO: better source location const casted_arg = try sema.coerce(&child_block, param_ty, uncasted_args[arg_i], arg_src); try sema.inst_map.putNoClobber(gpa, inst, casted_arg); + + if (is_comptime_call) { + const arg_val = try sema.resolveConstMaybeUndefVal(&child_block, arg_src, casted_arg); + memoized_call_key.args[arg_i] = .{ + .ty = param_ty, + .val = arg_val, + }; + } + arg_i += 1; continue; }, .param_anytype, .param_anytype_comptime => { // No coercion needed. - try sema.inst_map.putNoClobber(gpa, inst, uncasted_args[arg_i]); + const uncasted_arg = uncasted_args[arg_i]; + try sema.inst_map.putNoClobber(gpa, inst, uncasted_arg); + + if (is_comptime_call) { + const arg_src = call_src; // TODO: better source location + const arg_val = try sema.resolveConstMaybeUndefVal(&child_block, arg_src, uncasted_arg); + memoized_call_key.args[arg_i] = .{ + .ty = sema.typeOf(uncasted_arg), + .val = arg_val, + }; + } + arg_i += 1; continue; }, @@ -2626,19 +2677,61 @@ fn analyzeCall( sema.fn_ret_ty = fn_ret_ty; defer sema.fn_ret_ty = parent_fn_ret_ty; - _ = try sema.analyzeBody(&child_block, fn_info.body); - const result = try sema.analyzeBlockBody(block, call_src, &child_block, merges); + // This `res2` is here instead of directly breaking from `res` due to a stage1 + // bug generating invalid LLVM IR. + const res2: Air.Inst.Ref = res2: { + if (is_comptime_call) { + if (mod.memoized_calls.get(memoized_call_key)) |result| { + const ty_inst = try sema.addType(fn_ret_ty); + try sema.air_values.append(gpa, result.val); + sema.air_instructions.set(block_inst, .{ + .tag = .constant, + .data = .{ .ty_pl = .{ + .ty = ty_inst, + .payload = @intCast(u32, sema.air_values.items.len - 1), + } }, + }); + break :res2 Air.indexToRef(block_inst); + } + } - // Much like in `Module.semaDecl`, if the result is a struct or union type, - // we need to resolve the field type expressions right here, right now, while - // the child `Sema` is still available, with the AIR instruction map intact, - // because the field type expressions may reference into it. - if (sema.typeOf(result).zigTypeTag() == .Type) { - const ty = try sema.analyzeAsType(&child_block, call_src, result); - try sema.resolveDeclFields(&child_block, call_src, ty); - } + _ = try sema.analyzeBody(&child_block, fn_info.body); + const result = try sema.analyzeBlockBody(block, call_src, &child_block, merges); + + if (is_comptime_call) { + const result_val = try sema.resolveConstMaybeUndefVal(block, call_src, result); + + // TODO: check whether any external comptime memory was mutated by the + // comptime function call. If so, then do not memoize the call here. + { + var arena_allocator = std.heap.ArenaAllocator.init(gpa); + errdefer arena_allocator.deinit(); + const arena = &arena_allocator.allocator; + + for (memoized_call_key.args) |*arg| { + arg.* = try arg.*.copy(arena); + } + + try mod.memoized_calls.put(gpa, memoized_call_key, .{ + .val = result_val, + .arena = arena_allocator.state, + }); + delete_memoized_call_key = false; + } + + // Much like in `Module.semaDecl`, if the result is a struct or union type, + // we need to resolve the field type expressions right here, right now, while + // the child `Sema` is still available, with the AIR instruction map intact, + // because the field type expressions may reference into it. + if (sema.typeOf(result).zigTypeTag() == .Type) { + const ty = try sema.analyzeAsType(&child_block, call_src, result); + try sema.resolveDeclFields(&child_block, call_src, ty); + } + } - break :res result; + break :res2 result; + }; + break :res res2; } 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; @@ -3305,31 +3398,9 @@ fn zirEnumToInt(sema: *Sema, block: *Scope.Block, inst: Zir.Inst.Index) CompileE } if (try sema.resolveMaybeUndefVal(block, operand_src, enum_tag)) |enum_tag_val| { - if (enum_tag_val.castTag(.enum_field_index)) |enum_field_payload| { - const field_index = enum_field_payload.data; - switch (enum_tag_ty.tag()) { - .enum_full => { - const enum_full = enum_tag_ty.castTag(.enum_full).?.data; - if (enum_full.values.count() != 0) { - const val = enum_full.values.keys()[field_index]; - return sema.addConstant(int_tag_ty, val); - } else { - // Field index and integer values are the same. - const val = try Value.Tag.int_u64.create(arena, field_index); - return sema.addConstant(int_tag_ty, val); - } - }, - .enum_simple => { - // Field index and integer values are the same. - const val = try Value.Tag.int_u64.create(arena, field_index); - return sema.addConstant(int_tag_ty, val); - }, - else => unreachable, - } - } else { - // Assume it is already an integer and return it directly. - return sema.addConstant(int_tag_ty, enum_tag_val); - } + var buffer: Value.Payload.U64 = undefined; + const val = enum_tag_val.enumToInt(enum_tag_ty, &buffer); + return sema.addConstant(int_tag_ty, try val.copy(sema.arena)); } try sema.requireRuntimeBlock(block, src); @@ -3414,7 +3485,10 @@ fn zirOptionalPayloadPtr( return sema.mod.fail(&block.base, src, "unable to unwrap null", .{}); } // The same Value represents the pointer to the optional and the payload. - return sema.addConstant(child_pointer, pointer_val); + return sema.addConstant( + child_pointer, + try Value.Tag.opt_payload_ptr.create(sema.arena, pointer_val), + ); } } @@ -3451,7 +3525,8 @@ fn zirOptionalPayload( if (val.isNull()) { return sema.mod.fail(&block.base, src, "unable to unwrap null", .{}); } - return sema.addConstant(child_type, val); + const sub_val = val.castTag(.opt_payload).?.data; + return sema.addConstant(child_type, sub_val); } try sema.requireRuntimeBlock(block, src); @@ -9095,7 +9170,7 @@ fn wrapOptional( inst_src: LazySrcLoc, ) !Air.Inst.Ref { if (try sema.resolveMaybeUndefVal(block, inst_src, inst)) |val| { - return sema.addConstant(dest_type, val); + return sema.addConstant(dest_type, try Value.Tag.opt_payload.create(sema.arena, val)); } try sema.requireRuntimeBlock(block, inst_src); diff --git a/src/TypedValue.zig b/src/TypedValue.zig index 48b2c04970..83242b5329 100644 --- a/src/TypedValue.zig +++ b/src/TypedValue.zig @@ -23,9 +23,18 @@ pub const Managed = struct { }; /// Assumes arena allocation. Does a recursive copy. -pub fn copy(self: TypedValue, allocator: *Allocator) error{OutOfMemory}!TypedValue { +pub fn copy(self: TypedValue, arena: *Allocator) error{OutOfMemory}!TypedValue { return TypedValue{ - .ty = try self.ty.copy(allocator), - .val = try self.val.copy(allocator), + .ty = try self.ty.copy(arena), + .val = try self.val.copy(arena), }; } + +pub fn eql(a: TypedValue, b: TypedValue) bool { + if (!a.ty.eql(b.ty)) return false; + return a.val.eql(b.val, a.ty); +} + +pub fn hash(tv: TypedValue, hasher: *std.hash.Wyhash) void { + return tv.val.hash(tv.ty, hasher); +} diff --git a/src/codegen/c.zig b/src/codegen/c.zig index e7994ffd06..bc3e357827 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -319,18 +319,20 @@ pub const DeclGen = struct { .Bool => return writer.print("{}", .{val.toBool()}), .Optional => { var opt_buf: Type.Payload.ElemType = undefined; - const child_type = t.optionalChild(&opt_buf); + const payload_type = t.optionalChild(&opt_buf); if (t.isPtrLikeOptional()) { - return dg.renderValue(writer, child_type, val); + return dg.renderValue(writer, payload_type, val); } try writer.writeByte('('); try dg.renderType(writer, t); - if (val.tag() == .null_value) { - try writer.writeAll("){ .is_null = true }"); - } else { - try writer.writeAll("){ .is_null = false, .payload = "); - try dg.renderValue(writer, child_type, val); + try writer.writeAll("){"); + if (val.castTag(.opt_payload)) |pl| { + const payload_val = pl.data; + try writer.writeAll(" .is_null = false, .payload = "); + try dg.renderValue(writer, payload_type, payload_val); try writer.writeAll(" }"); + } else { + try writer.writeAll(" .is_null = true }"); } }, .ErrorSet => { diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig index 745fb036db..b80dcf0feb 100644 --- a/src/codegen/llvm.zig +++ b/src/codegen/llvm.zig @@ -810,27 +810,22 @@ pub const DeclGen = struct { return self.todo("handle more array values", .{}); }, .Optional => { - if (!tv.ty.isPtrLikeOptional()) { - var buf: Type.Payload.ElemType = undefined; - const child_type = tv.ty.optionalChild(&buf); - const llvm_child_type = try self.llvmType(child_type); - - if (tv.val.tag() == .null_value) { - var optional_values: [2]*const llvm.Value = .{ - llvm_child_type.constNull(), - self.context.intType(1).constNull(), - }; - return self.context.constStruct(&optional_values, optional_values.len, .False); - } else { - var optional_values: [2]*const llvm.Value = .{ - try self.genTypedValue(.{ .ty = child_type, .val = tv.val }), - self.context.intType(1).constAllOnes(), - }; - return self.context.constStruct(&optional_values, optional_values.len, .False); - } - } else { + if (tv.ty.isPtrLikeOptional()) { return self.todo("implement const of optional pointer", .{}); } + var buf: Type.Payload.ElemType = undefined; + const payload_type = tv.ty.optionalChild(&buf); + const is_pl = !tv.val.isNull(); + const llvm_i1 = self.context.intType(1); + + const fields: [2]*const llvm.Value = .{ + try self.genTypedValue(.{ + .ty = payload_type, + .val = if (tv.val.castTag(.opt_payload)) |pl| pl.data else Value.initTag(.undef), + }), + if (is_pl) llvm_i1.constAllOnes() else llvm_i1.constNull(), + }; + return self.context.constStruct(&fields, fields.len, .False); }, .Fn => { const fn_decl = switch (tv.val.tag()) { diff --git a/src/codegen/wasm.zig b/src/codegen/wasm.zig index 4814ba0b55..422afef9c4 100644 --- a/src/codegen/wasm.zig +++ b/src/codegen/wasm.zig @@ -1198,7 +1198,12 @@ pub const Context = struct { // When constant has value 'null', set is_null local to '1' // and payload to '0' - if (val.tag() == .null_value) { + if (val.castTag(.opt_payload)) |pl| { + const payload_val = pl.data; + try writer.writeByte(wasm.opcode(.i32_const)); + try leb.writeILEB128(writer, @as(i32, 0)); + try self.emitConstant(payload_val, payload_type); + } else { try writer.writeByte(wasm.opcode(.i32_const)); try leb.writeILEB128(writer, @as(i32, 1)); @@ -1208,10 +1213,6 @@ pub const Context = struct { }); try writer.writeByte(wasm.opcode(opcode)); try leb.writeULEB128(writer, @as(u32, 0)); - } else { - try writer.writeByte(wasm.opcode(.i32_const)); - try leb.writeILEB128(writer, @as(i32, 0)); - try self.emitConstant(val, payload_type); } }, else => |zig_type| return self.fail("Wasm TODO: emitConstant for zigTypeTag {s}", .{zig_type}), diff --git a/src/value.zig b/src/value.zig index 7b3056bfcf..5ac9f142c4 100644 --- a/src/value.zig +++ b/src/value.zig @@ -133,12 +133,21 @@ pub const Value = extern union { /// When the type is error union: /// * If the tag is `.@"error"`, the error union is an error. /// * If the tag is `.eu_payload`, the error union is a payload. - /// * A nested error such as `((anyerror!T1)!T2)` in which the the outer error union + /// * A nested error such as `anyerror!(anyerror!T)` in which the the outer error union /// is non-error, but the inner error union is an error, is represented as /// a tag of `.eu_payload`, with a sub-tag of `.@"error"`. eu_payload, /// A pointer to the payload of an error union, based on a pointer to an error union. eu_payload_ptr, + /// When the type is optional: + /// * If the tag is `.null_value`, the optional is null. + /// * If the tag is `.opt_payload`, the optional is a payload. + /// * A nested optional such as `??T` in which the the outer optional + /// is non-null, but the inner optional is null, is represented as + /// a tag of `.opt_payload`, with a sub-tag of `.null_value`. + opt_payload, + /// A pointer to the payload of an optional, based on a pointer to an optional. + opt_payload_ptr, /// An instance of a struct. @"struct", /// An instance of a union. @@ -238,6 +247,8 @@ pub const Value = extern union { .repeated, .eu_payload, .eu_payload_ptr, + .opt_payload, + .opt_payload_ptr, => Payload.SubValue, .bytes, @@ -459,7 +470,12 @@ pub const Value = extern union { return Value{ .ptr_otherwise = &new_payload.base }; }, .bytes => return self.copyPayloadShallow(allocator, Payload.Bytes), - .repeated, .eu_payload, .eu_payload_ptr => { + .repeated, + .eu_payload, + .eu_payload_ptr, + .opt_payload, + .opt_payload_ptr, + => { const payload = self.cast(Payload.SubValue).?; const new_payload = try allocator.create(Payload.SubValue); new_payload.* = .{ @@ -656,12 +672,20 @@ pub const Value = extern union { try out_stream.writeAll("(eu_payload) "); val = val.castTag(.eu_payload).?.data; }, + .opt_payload => { + try out_stream.writeAll("(opt_payload) "); + val = val.castTag(.opt_payload).?.data; + }, .inferred_alloc => return out_stream.writeAll("(inferred allocation value)"), .inferred_alloc_comptime => return out_stream.writeAll("(inferred comptime allocation value)"), .eu_payload_ptr => { try out_stream.writeAll("(eu_payload_ptr)"); val = val.castTag(.eu_payload_ptr).?.data; }, + .opt_payload_ptr => { + try out_stream.writeAll("(opt_payload_ptr)"); + val = val.castTag(.opt_payload_ptr).?.data; + }, }; } @@ -776,6 +800,38 @@ pub const Value = extern union { } } + pub fn enumToInt(val: Value, ty: Type, buffer: *Payload.U64) Value { + if (val.castTag(.enum_field_index)) |enum_field_payload| { + const field_index = enum_field_payload.data; + switch (ty.tag()) { + .enum_full, .enum_nonexhaustive => { + const enum_full = ty.cast(Type.Payload.EnumFull).?.data; + if (enum_full.values.count() != 0) { + return enum_full.values.keys()[field_index]; + } else { + // Field index and integer values are the same. + buffer.* = .{ + .base = .{ .tag = .int_u64 }, + .data = field_index, + }; + return Value.initPayload(&buffer.base); + } + }, + .enum_simple => { + // Field index and integer values are the same. + buffer.* = .{ + .base = .{ .tag = .int_u64 }, + .data = field_index, + }; + return Value.initPayload(&buffer.base); + }, + else => unreachable, + } + } + // Assume it is already an integer and return it directly. + return val; + } + /// Asserts the value is an integer. pub fn toBigInt(self: Value, space: *BigIntSpace) BigIntConst { switch (self.tag()) { @@ -1132,7 +1188,10 @@ pub const Value = extern union { } pub fn hash(val: Value, ty: Type, hasher: *std.hash.Wyhash) void { - switch (ty.zigTypeTag()) { + const zig_ty_tag = ty.zigTypeTag(); + std.hash.autoHash(hasher, zig_ty_tag); + + switch (zig_ty_tag) { .BoundFn => unreachable, // TODO remove this from the language .Void, @@ -1157,7 +1216,10 @@ pub const Value = extern union { } }, .Float, .ComptimeFloat => { - @panic("TODO implement hashing float values"); + // TODO double check the lang spec. should we to bitwise hashing here, + // or a hash that normalizes the float value? + const float = val.toFloat(f128); + std.hash.autoHash(hasher, @bitCast(u128, float)); }, .Pointer => { @panic("TODO implement hashing pointer values"); @@ -1169,7 +1231,15 @@ pub const Value = extern union { @panic("TODO implement hashing struct values"); }, .Optional => { - @panic("TODO implement hashing optional values"); + if (val.castTag(.opt_payload)) |payload| { + std.hash.autoHash(hasher, true); // non-null + const sub_val = payload.data; + var buffer: Type.Payload.ElemType = undefined; + const sub_ty = ty.optionalChild(&buffer); + sub_val.hash(sub_ty, hasher); + } else { + std.hash.autoHash(hasher, false); // non-null + } }, .ErrorUnion => { @panic("TODO implement hashing error union values"); @@ -1178,7 +1248,16 @@ pub const Value = extern union { @panic("TODO implement hashing error set values"); }, .Enum => { - @panic("TODO implement hashing enum values"); + var enum_space: Payload.U64 = undefined; + const int_val = val.enumToInt(ty, &enum_space); + + var space: BigIntSpace = undefined; + const big = int_val.toBigInt(&space); + + std.hash.autoHash(hasher, big.positive); + for (big.limbs) |limb| { + std.hash.autoHash(hasher, limb); + } }, .Union => { @panic("TODO implement hashing union values"); @@ -1257,6 +1336,11 @@ pub const Value = extern union { const err_union_val = (try err_union_ptr.pointerDeref(allocator)) orelse return null; break :blk err_union_val.castTag(.eu_payload).?.data; }, + .opt_payload_ptr => blk: { + const opt_ptr = self.castTag(.opt_payload_ptr).?.data; + const opt_val = (try opt_ptr.pointerDeref(allocator)) orelse return null; + break :blk opt_val.castTag(.opt_payload).?.data; + }, .zero, .one, @@ -1354,13 +1438,14 @@ pub const Value = extern union { /// Valid for all types. Asserts the value is not undefined and not unreachable. pub fn isNull(self: Value) bool { return switch (self.tag()) { + .null_value => true, + .opt_payload => false, + .undef => unreachable, .unreachable_value => unreachable, .inferred_alloc => unreachable, .inferred_alloc_comptime => unreachable, - .null_value => true, - - else => false, + else => unreachable, }; } @@ -1390,6 +1475,10 @@ pub const Value = extern union { return switch (val.tag()) { .eu_payload => true, else => false, + + .undef => unreachable, + .inferred_alloc => unreachable, + .inferred_alloc_comptime => unreachable, }; } diff --git a/test/behavior/eval.zig b/test/behavior/eval.zig index 67103e01ff..1b6540cd32 100644 --- a/test/behavior/eval.zig +++ b/test/behavior/eval.zig @@ -148,3 +148,16 @@ const List = blk: { array: T, }; }; + +test "comptime function with the same args is memoized" { + comptime { + try expect(MakeType(i32) == MakeType(i32)); + try expect(MakeType(i32) != MakeType(f64)); + } +} + +fn MakeType(comptime T: type) type { + return struct { + field: T, + }; +} diff --git a/test/behavior/eval_stage1.zig b/test/behavior/eval_stage1.zig index 3599d5a477..644de50fd0 100644 --- a/test/behavior/eval_stage1.zig +++ b/test/behavior/eval_stage1.zig @@ -356,19 +356,6 @@ test "binary math operator in partially inlined function" { try expect(s[3] == 0xd0e0f10); } -test "comptime function with the same args is memoized" { - comptime { - try expect(MakeType(i32) == MakeType(i32)); - try expect(MakeType(i32) != MakeType(f64)); - } -} - -fn MakeType(comptime T: type) type { - return struct { - field: T, - }; -} - test "comptime function with mutable pointer is not memoized" { comptime { var x: i32 = 1; -- cgit v1.2.3