From b2343e63bd06d1312ca80745236bb42358062115 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Thu, 16 Dec 2021 02:23:15 +0100 Subject: stage2: move inferred error set state into func --- src/codegen/c.zig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/codegen') diff --git a/src/codegen/c.zig b/src/codegen/c.zig index f54ae7f76d..8babcb9a83 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -722,7 +722,7 @@ pub const DeclGen = struct { try bw.writeAll(" payload; uint16_t error; } "); const name_index = buffer.items.len; if (err_set_type.castTag(.error_set_inferred)) |inf_err_set_payload| { - const func = inf_err_set_payload.data.func; + const func = inf_err_set_payload.data; try bw.writeAll("zig_E_"); try dg.renderDeclName(func.owner_decl, bw); try bw.writeAll(";\n"); -- cgit v1.2.3 From a2958a4ede0af4b4559eeb142c0400ae640db63e Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Fri, 17 Dec 2021 03:40:48 +0100 Subject: stage2: allow multiple inferred error sets per Fn This allows the inferred error set of comptime and inline invocations to be resolved separately from the inferred error set of the runtime version or other comptime/inline invocations. --- src/Module.zig | 112 +++++++++++++++++++++++++++++++----------------------- src/Sema.zig | 46 ++++++++++++++-------- src/codegen/c.zig | 2 +- src/type.zig | 4 +- 4 files changed, 99 insertions(+), 65 deletions(-) (limited to 'src/codegen') diff --git a/src/Module.zig b/src/Module.zig index b5d856efd0..7031dc20a5 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -1207,23 +1207,9 @@ pub const Fn = struct { is_cold: bool = false, is_noinline: bool = false, - /// These fields are used to keep track of any dependencies related to functions - /// that return inferred error sets. It's values are not used when the function - /// does not return an inferred error set. - inferred_error_set: struct { - /// All currently known errors that this function returns. This includes direct additions - /// via `return error.Foo;`, and possibly also errors that are returned from any dependent functions. - /// When the inferred error set is fully resolved, this map contains all the errors that the function might return. - errors: std.StringHashMapUnmanaged(void) = .{}, - - /// Other functions with inferred error sets which the inferred error set of this - /// function should include. - functions: std.AutoHashMapUnmanaged(*Fn, void) = .{}, - - /// Whether the function returned anyerror. This is true if either of the dependent functions - /// returns anyerror. - is_anyerror: bool = false, - } = .{}, + /// Any inferred error sets that this function owns, both it's own inferred error set and + /// inferred error sets of any inline/comptime functions called. + inferred_error_sets: InferredErrorSetList = .{}, pub const Analysis = enum { queued, @@ -1239,37 +1225,69 @@ pub const Fn = struct { success, }; - pub fn deinit(func: *Fn, gpa: Allocator) void { - func.inferred_error_set.errors.deinit(gpa); - func.inferred_error_set.functions.deinit(gpa); - } + /// This struct is used to keep track of any dependencies related to functions instances + /// that return inferred error sets. Note that a function may be associated to multiple different error sets, + /// for example an inferred error set which this function returns, but also any inferred error sets + /// of called inline or comptime functions. + pub const InferredErrorSet = struct { + /// The function from which this error set originates. + /// Note: may be the function itself. + func: *Fn, - pub fn addErrorSet(func: *Fn, gpa: Allocator, err_set_ty: Type) !void { - switch (err_set_ty.tag()) { - .error_set => { - const names = err_set_ty.castTag(.error_set).?.data.names.keys(); - for (names) |name| { - try func.inferred_error_set.errors.put(gpa, name, {}); - } - }, - .error_set_single => { - const name = err_set_ty.castTag(.error_set_single).?.data; - try func.inferred_error_set.errors.put(gpa, name, {}); - }, - .error_set_inferred => { - const dependent_func = err_set_ty.castTag(.error_set_inferred).?.data; - try func.inferred_error_set.functions.put(gpa, dependent_func, {}); - }, - .error_set_merged => { - const names = err_set_ty.castTag(.error_set_merged).?.data.keys(); - for (names) |name| { - try func.inferred_error_set.errors.put(gpa, name, {}); - } - }, - .anyerror => { - func.inferred_error_set.is_anyerror = true; - }, - else => unreachable, + /// All currently known errors that this error set contains. This includes direct additions + /// via `return error.Foo;`, and possibly also errors that are returned from any dependent functions. + /// When the inferred error set is fully resolved, this map contains all the errors that the function might return. + errors: std.StringHashMapUnmanaged(void) = .{}, + + /// Other functions with inferred error sets which the inferred error set of this + /// function should include. + functions: std.AutoHashMapUnmanaged(*Fn, void) = .{}, + + /// Whether the function returned anyerror. This is true if either of the dependent functions + /// returns anyerror. + is_anyerror: bool = false, + + pub fn addErrorSet(self: *InferredErrorSet, gpa: Allocator, err_set_ty: Type) !void { + switch (err_set_ty.tag()) { + .error_set => { + const names = err_set_ty.castTag(.error_set).?.data.names.keys(); + for (names) |name| { + try self.errors.put(gpa, name, {}); + } + }, + .error_set_single => { + const name = err_set_ty.castTag(.error_set_single).?.data; + try self.errors.put(gpa, name, {}); + }, + .error_set_inferred => { + const dependent_func = err_set_ty.castTag(.error_set_inferred).?.data.func; + try self.functions.put(gpa, dependent_func, {}); + }, + .error_set_merged => { + const names = err_set_ty.castTag(.error_set_merged).?.data.keys(); + for (names) |name| { + try self.errors.put(gpa, name, {}); + } + }, + .anyerror => { + self.is_anyerror = true; + }, + else => unreachable, + } + } + }; + + pub const InferredErrorSetList = std.SinglyLinkedList(InferredErrorSet); + pub const InferredErrorSetListNode = InferredErrorSetList.Node; + + pub fn deinit(func: *Fn, gpa: Allocator) void { + var it = func.inferred_error_sets.first; + while (it) |node| { + const next = node.next; + node.data.errors.deinit(gpa); + node.data.functions.deinit(gpa); + gpa.destroy(node); + it = next; } } }; diff --git a/src/Sema.zig b/src/Sema.zig index 30c59f9efa..f23ffe24c0 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -3896,11 +3896,12 @@ fn analyzeCall( const bare_return_type = try sema.analyzeAsType(&child_block, ret_ty_src, ret_ty_inst); // If the function has an inferred error set, `bare_return_type` is the payload type only. const fn_ret_ty = blk: { - // TODO instead of reusing the function's inferred error set, this code should - // create a temporary error set which is used for the comptime/inline function - // call alone, independent from the runtime instantiation. - if (func_ty_info.return_type.castTag(.error_union)) |payload| { - const error_set_ty = payload.data.error_set; + if (func_ty_info.return_type.tag() == .error_union) { + const node = try sema.gpa.create(Module.Fn.InferredErrorSetListNode); + node.data = .{ .func = module_fn }; + parent_func.?.inferred_error_sets.prepend(node); + + const error_set_ty = try Type.Tag.error_set_inferred.create(sema.arena, &node.data); break :blk try Type.Tag.error_union.create(sema.arena, .{ .error_set = error_set_ty, .payload = bare_return_type, @@ -5066,6 +5067,10 @@ fn funcCommon( }; errdefer if (body_inst != 0) sema.gpa.destroy(new_func); + var maybe_inferred_error_set_node: ?*Module.Fn.InferredErrorSetListNode = null; + errdefer if (maybe_inferred_error_set_node) |node| sema.gpa.destroy(node); + // Note: no need to errdefer since this will still be in its default state at the end of the function. + const fn_ty: Type = fn_ty: { // Hot path for some common function types. // TODO can we eliminate some of these Type tag values? seems unnecessarily complicated. @@ -5107,7 +5112,11 @@ fn funcCommon( 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, new_func); + const node = try sema.gpa.create(Module.Fn.InferredErrorSetListNode); + node.data = .{ .func = new_func }; + maybe_inferred_error_set_node = node; + + const error_set_ty = try Type.Tag.error_set_inferred.create(sema.arena, &node.data); break :blk try Type.Tag.error_union.create(sema.arena, .{ .error_set = error_set_ty, .payload = bare_return_type, @@ -5198,7 +5207,14 @@ fn funcCommon( .rbrace_line = src_locs.rbrace_line, .lbrace_column = @truncate(u16, src_locs.columns), .rbrace_column = @truncate(u16, src_locs.columns >> 16), + .inferred_error_sets = .{ + .first = maybe_inferred_error_set_node, + }, }; + if (maybe_inferred_error_set_node) |node| { + new_func.inferred_error_sets.prepend(node); + } + maybe_inferred_error_set_node = null; fn_payload.* = .{ .base = .{ .tag = .function }, .data = new_func, @@ -9204,14 +9220,14 @@ fn analyzeRet( // add the error tag to the inferred error set of the in-scope function, so // that the coercion below works correctly. if (sema.fn_ret_ty.zigTypeTag() == .ErrorUnion) { - if (sema.fn_ret_ty.errorUnionSet().tag() == .error_set_inferred) { + if (sema.fn_ret_ty.errorUnionSet().castTag(.error_set_inferred)) |payload| { const op_ty = sema.typeOf(uncasted_operand); switch (op_ty.zigTypeTag()) { .ErrorSet => { - try sema.func.?.addErrorSet(sema.gpa, op_ty); + try payload.data.addErrorSet(sema.gpa, op_ty); }, .ErrorUnion => { - try sema.func.?.addErrorSet(sema.gpa, op_ty.errorUnionSet()); + try payload.data.addErrorSet(sema.gpa, op_ty.errorUnionSet()); }, else => {}, } @@ -12496,10 +12512,10 @@ fn coerceInMemoryAllowedErrorSets( // of inferred error sets. if (src_ty.castTag(.error_set_inferred)) |src_payload| { if (dest_ty.castTag(.error_set_inferred)) |dst_payload| { - const src_func = src_payload.data; - const dst_func = dst_payload.data; + const src_func = src_payload.data.func; + const dst_func = dst_payload.data.func; - if (src_func == dst_func or dst_func.inferred_error_set.functions.contains(src_func)) { + if (src_func == dst_func or dst_payload.data.functions.contains(src_func)) { return .ok; } } @@ -13894,10 +13910,10 @@ fn wrapErrorUnion( } }, .error_set_inferred => ok: { - const func = dest_err_set_ty.castTag(.error_set_inferred).?.data; - if (func.inferred_error_set.is_anyerror) break :ok; + const data = dest_err_set_ty.castTag(.error_set_inferred).?.data; + if (data.is_anyerror) break :ok; const expected_name = val.castTag(.@"error").?.data.name; - if (func.inferred_error_set.errors.contains(expected_name)) break :ok; + if (data.errors.contains(expected_name)) break :ok; // TODO error set resolution here before emitting a compile error return sema.failWithErrorSetCodeMissing(block, inst_src, dest_err_set_ty, inst_ty); }, diff --git a/src/codegen/c.zig b/src/codegen/c.zig index 8babcb9a83..f54ae7f76d 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -722,7 +722,7 @@ pub const DeclGen = struct { try bw.writeAll(" payload; uint16_t error; } "); const name_index = buffer.items.len; if (err_set_type.castTag(.error_set_inferred)) |inf_err_set_payload| { - const func = inf_err_set_payload.data; + const func = inf_err_set_payload.data.func; try bw.writeAll("zig_E_"); try dg.renderDeclName(func.owner_decl, bw); try bw.writeAll(";\n"); diff --git a/src/type.zig b/src/type.zig index 298df2cffc..3360477a03 100644 --- a/src/type.zig +++ b/src/type.zig @@ -2869,7 +2869,7 @@ pub const Type = extern union { pub fn isAnyError(ty: Type) bool { return switch (ty.tag()) { .anyerror => true, - .error_set_inferred => ty.castTag(.error_set_inferred).?.data.inferred_error_set.is_anyerror, + .error_set_inferred => ty.castTag(.error_set_inferred).?.data.is_anyerror, else => false, }; } @@ -4156,7 +4156,7 @@ pub const Type = extern union { pub const base_tag = Tag.error_set_inferred; base: Payload = Payload{ .tag = base_tag }, - data: *Module.Fn, + data: *Module.Fn.InferredErrorSet, }; pub const Pointer = struct { -- cgit v1.2.3 From f3d635b6683ba4a53f82ae8087b1cf78552abac5 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Sat, 18 Dec 2021 04:42:13 +0100 Subject: stage2: @addWithOverflow --- lib/std/math/big/int.zig | 36 ++++++++++------ lib/std/math/big/int_test.zig | 24 +++++++---- src/Air.zig | 8 ++++ src/Liveness.zig | 2 +- src/Sema.zig | 99 ++++++++++++++++++++++++++++++++++++++++--- src/arch/aarch64/CodeGen.zig | 7 +++ src/arch/arm/CodeGen.zig | 7 +++ src/arch/riscv64/CodeGen.zig | 7 +++ src/arch/x86_64/CodeGen.zig | 7 +++ src/codegen/c.zig | 8 ++++ src/codegen/llvm.zig | 43 ++++++++++++++++--- src/print_air.zig | 12 ++++++ src/value.zig | 79 ++++++++++++++++++++++++---------- test/behavior/math.zig | 27 ++++++++++++ test/behavior/math_stage1.zig | 27 ------------ 15 files changed, 311 insertions(+), 82 deletions(-) (limited to 'src/codegen') diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig index d7bcf9badc..ec0143a3d7 100644 --- a/lib/std/math/big/int.zig +++ b/lib/std/math/big/int.zig @@ -443,12 +443,12 @@ pub const Mutable = struct { } } - /// r = a + b with 2s-complement wrapping semantics. + /// r = a + b with 2s-complement wrapping semantics. Returns whether overflow occurred. /// r, a and b may be aliases /// /// Asserts the result fits in `r`. An upper bound on the number of limbs needed by /// r is `calcTwosCompLimbCount(bit_count)`. - pub fn addWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) void { + pub fn addWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) bool { const req_limbs = calcTwosCompLimbCount(bit_count); // Slice of the upper bits if they exist, these will be ignored and allows us to use addCarry to determine @@ -463,6 +463,7 @@ pub const Mutable = struct { .limbs = b.limbs[0..math.min(req_limbs, b.limbs.len)], }; + var carry_truncated = false; if (r.addCarry(x, y)) { // There are two possibilities here: // - We overflowed req_limbs. In this case, the carry is ignored, as it would be removed by @@ -473,10 +474,17 @@ pub const Mutable = struct { if (msl < req_limbs) { r.limbs[msl] = 1; r.len = req_limbs; + } else { + carry_truncated = true; } } - r.truncate(r.toConst(), signedness, bit_count); + if (!r.toConst().fitsInTwosComp(signedness, bit_count)) { + r.truncate(r.toConst(), signedness, bit_count); + return true; + } + + return carry_truncated; } /// r = a + b with 2s-complement saturating semantics. @@ -581,13 +589,13 @@ pub const Mutable = struct { r.add(a, b.negate()); } - /// r = a - b with 2s-complement wrapping semantics. + /// r = a - b with 2s-complement wrapping semantics. Returns whether any overflow occured. /// /// r, a and b may be aliases /// Asserts the result fits in `r`. An upper bound on the number of limbs needed by /// r is `calcTwosCompLimbCount(bit_count)`. - pub fn subWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) void { - r.addWrap(a, b.negate(), signedness, bit_count); + pub fn subWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) bool { + return r.addWrap(a, b.negate(), signedness, bit_count); } /// r = a - b with 2s-complement saturating semantics. @@ -1039,7 +1047,7 @@ pub const Mutable = struct { pub fn bitNotWrap(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void { r.copy(a.negate()); const negative_one = Const{ .limbs = &.{1}, .positive = false }; - r.addWrap(r.toConst(), negative_one, signedness, bit_count); + _ = r.addWrap(r.toConst(), negative_one, signedness, bit_count); } /// r = a | b under 2s complement semantics. @@ -2443,17 +2451,18 @@ pub const Managed = struct { r.setMetadata(m.positive, m.len); } - /// r = a + b with 2s-complement wrapping semantics. + /// r = a + b with 2s-complement wrapping semantics. Returns whether any overflow occured. /// /// r, a and b may be aliases. If r aliases a or b, then caller must call /// `r.ensureTwosCompCapacity` prior to calling `add`. /// /// Returns an error if memory could not be allocated. - pub fn addWrap(r: *Managed, a: Const, b: Const, signedness: Signedness, bit_count: usize) Allocator.Error!void { + pub fn addWrap(r: *Managed, a: Const, b: Const, signedness: Signedness, bit_count: usize) Allocator.Error!bool { try r.ensureTwosCompCapacity(bit_count); var m = r.toMutable(); - m.addWrap(a, b, signedness, bit_count); + const wrapped = m.addWrap(a, b, signedness, bit_count); r.setMetadata(m.positive, m.len); + return wrapped; } /// r = a + b with 2s-complement saturating semantics. @@ -2481,17 +2490,18 @@ pub const Managed = struct { r.setMetadata(m.positive, m.len); } - /// r = a - b with 2s-complement wrapping semantics. + /// r = a - b with 2s-complement wrapping semantics. Returns whether any overflow occured. /// /// r, a and b may be aliases. If r aliases a or b, then caller must call /// `r.ensureTwosCompCapacity` prior to calling `add`. /// /// Returns an error if memory could not be allocated. - pub fn subWrap(r: *Managed, a: Const, b: Const, signedness: Signedness, bit_count: usize) Allocator.Error!void { + pub fn subWrap(r: *Managed, a: Const, b: Const, signedness: Signedness, bit_count: usize) Allocator.Error!bool { try r.ensureTwosCompCapacity(bit_count); var m = r.toMutable(); - m.subWrap(a, b, signedness, bit_count); + const wrapped = m.subWrap(a, b, signedness, bit_count); r.setMetadata(m.positive, m.len); + return wrapped; } /// r = a - b with 2s-complement saturating semantics. diff --git a/lib/std/math/big/int_test.zig b/lib/std/math/big/int_test.zig index d226f20083..4c1d12116e 100644 --- a/lib/std/math/big/int_test.zig +++ b/lib/std/math/big/int_test.zig @@ -590,8 +590,9 @@ test "big.int addWrap single-single, unsigned" { var b = try Managed.initSet(testing.allocator, 10); defer b.deinit(); - try a.addWrap(a.toConst(), b.toConst(), .unsigned, 17); + const wrapped = try a.addWrap(a.toConst(), b.toConst(), .unsigned, 17); + try testing.expect(wrapped); try testing.expect((try a.to(u17)) == 9); } @@ -602,8 +603,9 @@ test "big.int subWrap single-single, unsigned" { var b = try Managed.initSet(testing.allocator, maxInt(u17)); defer b.deinit(); - try a.subWrap(a.toConst(), b.toConst(), .unsigned, 17); + const wrapped = try a.subWrap(a.toConst(), b.toConst(), .unsigned, 17); + try testing.expect(wrapped); try testing.expect((try a.to(u17)) == 1); } @@ -614,8 +616,9 @@ test "big.int addWrap multi-multi, unsigned, limb aligned" { var b = try Managed.initSet(testing.allocator, maxInt(DoubleLimb)); defer b.deinit(); - try a.addWrap(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); + const wrapped = try a.addWrap(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); + try testing.expect(wrapped); try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb) - 1); } @@ -626,8 +629,9 @@ test "big.int subWrap single-multi, unsigned, limb aligned" { var b = try Managed.initSet(testing.allocator, maxInt(DoubleLimb) + 100); defer b.deinit(); - try a.subWrap(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); + const wrapped = try a.subWrap(a.toConst(), b.toConst(), .unsigned, @bitSizeOf(DoubleLimb)); + try testing.expect(wrapped); try testing.expect((try a.to(DoubleLimb)) == maxInt(DoubleLimb) - 88); } @@ -638,8 +642,9 @@ test "big.int addWrap single-single, signed" { var b = try Managed.initSet(testing.allocator, 1 + 1 + maxInt(u21)); defer b.deinit(); - try a.addWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(i21)); + const wrapped = try a.addWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(i21)); + try testing.expect(wrapped); try testing.expect((try a.to(i21)) == minInt(i21)); } @@ -650,8 +655,9 @@ test "big.int subWrap single-single, signed" { var b = try Managed.initSet(testing.allocator, 1); defer b.deinit(); - try a.subWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(i21)); + const wrapped = try a.subWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(i21)); + try testing.expect(wrapped); try testing.expect((try a.to(i21)) == maxInt(i21)); } @@ -662,8 +668,9 @@ test "big.int addWrap multi-multi, signed, limb aligned" { var b = try Managed.initSet(testing.allocator, maxInt(SignedDoubleLimb)); defer b.deinit(); - try a.addWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); + const wrapped = try a.addWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); + try testing.expect(wrapped); try testing.expect((try a.to(SignedDoubleLimb)) == -2); } @@ -674,8 +681,9 @@ test "big.int subWrap single-multi, signed, limb aligned" { var b = try Managed.initSet(testing.allocator, 1); defer b.deinit(); - try a.subWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); + const wrapped = try a.subWrap(a.toConst(), b.toConst(), .signed, @bitSizeOf(SignedDoubleLimb)); + try testing.expect(wrapped); try testing.expect((try a.to(SignedDoubleLimb)) == maxInt(SignedDoubleLimb)); } diff --git a/src/Air.zig b/src/Air.zig index 0e8a63acb1..72e281d03e 100644 --- a/src/Air.zig +++ b/src/Air.zig @@ -135,6 +135,12 @@ pub const Inst = struct { /// is the same as both operands. /// Uses the `bin_op` field. min, + /// Integer addition with overflow. Both operands are guaranteed to be the same type, + /// and the result is bool. The wrapped value is written to the pointer given by the in + /// operand of the `pl_op` field. Payload is `Bin` with `lhs` and `rhs` the relevant types + /// of the operation. + /// Uses the `pl_op` field with payload `Bin`. + add_with_overflow, /// Allocates stack local memory. /// Uses the `ty` field. alloc, @@ -804,6 +810,8 @@ pub fn typeOfIndex(air: Air, inst: Air.Inst.Index) Type { const ptr_ty = air.typeOf(datas[inst].pl_op.operand); return ptr_ty.elemType(); }, + + .add_with_overflow => return Type.initTag(.bool), } } diff --git a/src/Liveness.zig b/src/Liveness.zig index f090329d5a..a7128e2cc2 100644 --- a/src/Liveness.zig +++ b/src/Liveness.zig @@ -381,7 +381,7 @@ fn analyzeInst( const extra = a.air.extraData(Air.AtomicRmw, pl_op.payload).data; return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.operand, .none }); }, - .memset, .memcpy => { + .memset, .memcpy, .add_with_overflow => { const pl_op = inst_datas[inst].pl_op; const extra = a.air.extraData(Air.Bin, pl_op.payload).data; return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.lhs, extra.rhs }); diff --git a/src/Sema.zig b/src/Sema.zig index 05cdcb794f..82901e8a8c 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -1051,10 +1051,10 @@ fn zirExtended(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai .@"asm" => return sema.zirAsm( block, extended, inst), .typeof_peer => return sema.zirTypeofPeer( block, extended), .compile_log => return sema.zirCompileLog( block, extended), - .add_with_overflow => return sema.zirOverflowArithmetic(block, extended), - .sub_with_overflow => return sema.zirOverflowArithmetic(block, extended), - .mul_with_overflow => return sema.zirOverflowArithmetic(block, extended), - .shl_with_overflow => return sema.zirOverflowArithmetic(block, extended), + .add_with_overflow => return sema.zirOverflowArithmetic(block, extended, extended.opcode), + .sub_with_overflow => return sema.zirOverflowArithmetic(block, extended, extended.opcode), + .mul_with_overflow => return sema.zirOverflowArithmetic(block, extended, extended.opcode), + .shl_with_overflow => return sema.zirOverflowArithmetic(block, extended, extended.opcode), .c_undef => return sema.zirCUndef( block, extended), .c_include => return sema.zirCInclude( block, extended), .c_define => return sema.zirCDefine( block, extended), @@ -7310,6 +7310,7 @@ fn zirOverflowArithmetic( sema: *Sema, block: *Block, extended: Zir.Inst.Extended.InstData, + zir_tag: Zir.Inst.Extended, ) CompileError!Air.Inst.Ref { const tracy = trace(@src()); defer tracy.end(); @@ -7317,7 +7318,95 @@ fn zirOverflowArithmetic( const extra = sema.code.extraData(Zir.Inst.OverflowArithmetic, extended.operand).data; const src: LazySrcLoc = .{ .node_offset = extra.node }; - return sema.fail(block, src, "TODO implement Sema.zirOverflowArithmetic", .{}); + const lhs_src: LazySrcLoc = .{ .node_offset_builtin_call_arg0 = extra.node }; + const rhs_src: LazySrcLoc = .{ .node_offset_builtin_call_arg1 = extra.node }; + const ptr_src: LazySrcLoc = .{ .node_offset_builtin_call_arg2 = extra.node }; + + const lhs = sema.resolveInst(extra.lhs); + const rhs = sema.resolveInst(extra.rhs); + const ptr = sema.resolveInst(extra.ptr); + + const lhs_ty = sema.typeOf(lhs); + + // Note, the types of lhs/rhs (also for shifting)/ptr are already correct as ensured by astgen. + const dest_ty = lhs_ty; + if (dest_ty.zigTypeTag() != .Int) { + return sema.fail(block, src, "expected integer type, found '{}'", .{dest_ty}); + } + + const target = sema.mod.getTarget(); + + const maybe_lhs_val = try sema.resolveMaybeUndefVal(block, lhs_src, lhs); + const maybe_rhs_val = try sema.resolveMaybeUndefVal(block, rhs_src, rhs); + + const result: struct { + overflowed: enum { yes, no, undef }, + wrapped: Air.Inst.Ref, + } = result: { + const air_tag: Air.Inst.Tag = switch (zir_tag) { + .add_with_overflow => blk: { + // If either of the arguments is zero, `false` is returned and the other is stored + // to the result, even if it is undefined.. + // Otherwise, if either of the argument is undefined, undefined is returned. + if (maybe_lhs_val) |lhs_val| { + if (!lhs_val.isUndef() and lhs_val.compareWithZero(.eq)) { + break :result .{ .overflowed = .no, .wrapped = rhs }; + } + } + if (maybe_rhs_val) |rhs_val| { + if (!rhs_val.isUndef() and rhs_val.compareWithZero(.eq)) { + break :result .{ .overflowed = .no, .wrapped = lhs }; + } + } + if (maybe_lhs_val) |lhs_val| { + if (maybe_rhs_val) |rhs_val| { + if (lhs_val.isUndef() or rhs_val.isUndef()) { + break :result .{ .overflowed = .undef, .wrapped = try sema.addConstUndef(dest_ty) }; + } + + const result = try lhs_val.intAddWithOverflow(rhs_val, dest_ty, sema.arena, target); + const inst = try sema.addConstant( + dest_ty, + result.wrapped_result, + ); + + if (result.overflowed) { + break :result .{ .overflowed = .yes, .wrapped = inst }; + } else { + break :result .{ .overflowed = .no, .wrapped = inst }; + } + } + } + + break :blk .add_with_overflow; + }, + .sub_with_overflow, + .mul_with_overflow, + .shl_with_overflow, + => return sema.fail(block, src, "TODO implement Sema.zirOverflowArithmetic for {}", .{zir_tag}), + else => unreachable, + }; + + try sema.requireRuntimeBlock(block, src); + return block.addInst(.{ + .tag = air_tag, + .data = .{ .pl_op = .{ + .operand = ptr, + .payload = try sema.addExtra(Air.Bin{ + .lhs = lhs, + .rhs = rhs, + }), + } }, + }); + }; + + try sema.storePtr2(block, src, ptr, ptr_src, result.wrapped, src, .store); + + return switch (result.overflowed) { + .yes => Air.Inst.Ref.bool_true, + .no => Air.Inst.Ref.bool_false, + .undef => try sema.addConstUndef(Type.initTag(.bool)), + }; } fn analyzeArithmetic( diff --git a/src/arch/aarch64/CodeGen.zig b/src/arch/aarch64/CodeGen.zig index 4e77d67727..fda673631d 100644 --- a/src/arch/aarch64/CodeGen.zig +++ b/src/arch/aarch64/CodeGen.zig @@ -521,6 +521,8 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .max => try self.airMax(inst), .slice => try self.airSlice(inst), + .add_with_overflow => try self.airAddWithOverflow(inst), + .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), .cmp_lt => try self.airCmp(inst, .lt), @@ -968,6 +970,11 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } +fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) .dead else return self.fail("TODO implement div for {}", .{self.target.cpu.arch}); diff --git a/src/arch/arm/CodeGen.zig b/src/arch/arm/CodeGen.zig index ae53d6cad8..bcc1b927e7 100644 --- a/src/arch/arm/CodeGen.zig +++ b/src/arch/arm/CodeGen.zig @@ -519,6 +519,8 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .max => try self.airMax(inst), .slice => try self.airSlice(inst), + .add_with_overflow => try self.airAddWithOverflow(inst), + .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), .cmp_lt => try self.airCmp(inst, .lt), @@ -998,6 +1000,11 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } +fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) .dead else return self.fail("TODO implement div for {}", .{self.target.cpu.arch}); diff --git a/src/arch/riscv64/CodeGen.zig b/src/arch/riscv64/CodeGen.zig index 17ef79b725..1d67ad0abf 100644 --- a/src/arch/riscv64/CodeGen.zig +++ b/src/arch/riscv64/CodeGen.zig @@ -500,6 +500,8 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .max => try self.airMax(inst), .slice => try self.airSlice(inst), + .add_with_overflow => try self.airAddWithOverflow(inst), + .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), .cmp_lt => try self.airCmp(inst, .lt), @@ -913,6 +915,11 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } +fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) .dead else return self.fail("TODO implement div for {}", .{self.target.cpu.arch}); diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index 378184f70a..8fadcdd5f5 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -553,6 +553,8 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .max => try self.airMax(inst), .slice => try self.airSlice(inst), + .add_with_overflow => try self.airAddWithOverflow(inst), + .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), .cmp_lt => try self.airCmp(inst, .lt), @@ -1027,6 +1029,11 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } +fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) diff --git a/src/codegen/c.zig b/src/codegen/c.zig index f54ae7f76d..b086d15b48 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -1155,6 +1155,8 @@ fn genBody(f: *Function, body: []const Air.Inst.Index) error{ AnalysisFail, OutO .mul_sat => try airSatOp(f, inst, "muls_"), .shl_sat => try airSatOp(f, inst, "shls_"), + .add_with_overflow => try airAddWithOverflow(f, inst), + .min => try airMinMax(f, inst, "<"), .max => try airMinMax(f, inst, ">"), @@ -1864,6 +1866,12 @@ fn airSatOp(f: *Function, inst: Air.Inst.Index, fn_op: [*:0]const u8) !CValue { return ret; } +fn airAddWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { + _ = f; + _ = inst; + return f.fail("TODO add with overflow", .{}); +} + fn airNot(f: *Function, inst: Air.Inst.Index) !CValue { if (f.liveness.isUnused(inst)) return CValue.none; diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig index 58239fdaea..d12dad2403 100644 --- a/src/codegen/llvm.zig +++ b/src/codegen/llvm.zig @@ -1714,6 +1714,8 @@ pub const FuncGen = struct { .max => try self.airMax(inst), .slice => try self.airSlice(inst), + .add_with_overflow => try self.airAddWithOverflow(inst), + .bit_and, .bool_and => try self.airAnd(inst), .bit_or, .bool_or => try self.airOr(inst), .xor => try self.airXor(inst), @@ -3133,6 +3135,38 @@ pub const FuncGen = struct { } } + fn airAddWithOverflow(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { + if (self.liveness.isUnused(inst)) + return null; + + const pl_op = self.air.instructions.items(.data)[inst].pl_op; + const extra = self.air.extraData(Air.Bin, pl_op.payload).data; + + const ptr = try self.resolveInst(pl_op.operand); + const lhs = try self.resolveInst(extra.lhs); + const rhs = try self.resolveInst(extra.rhs); + + const ptr_ty = self.air.typeOf(pl_op.operand); + const lhs_ty = self.air.typeOf(extra.lhs); + + const intrinsic_name: []const u8 = if (lhs_ty.isSignedInt()) + "llvm.sadd.with.overflow" + else + "llvm.uadd.with.overflow"; + + const llvm_lhs_ty = try self.dg.llvmType(lhs_ty); + + const llvm_fn = self.getIntrinsic(intrinsic_name, &.{llvm_lhs_ty}); + const result_struct = self.builder.buildCall(llvm_fn, &[_]*const llvm.Value{ lhs, rhs }, 2, .Fast, .Auto, ""); + + const result = self.builder.buildExtractValue(result_struct, 0, ""); + const overflow_bit = self.builder.buildExtractValue(result_struct, 1, ""); + + self.store(ptr, ptr_ty, result, .NotAtomic); + + return overflow_bit; + } + fn airAnd(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { if (self.liveness.isUnused(inst)) return null; @@ -3511,7 +3545,7 @@ pub const FuncGen = struct { fn airBreakpoint(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { _ = inst; - const llvm_fn = self.getIntrinsic("llvm.debugtrap"); + const llvm_fn = self.getIntrinsic("llvm.debugtrap", &.{}); _ = self.builder.buildCall(llvm_fn, undefined, 0, .C, .Auto, ""); return null; } @@ -3946,13 +3980,10 @@ pub const FuncGen = struct { return self.builder.buildInBoundsGEP(base_ptr, &indices, indices.len, ""); } - fn getIntrinsic(self: *FuncGen, name: []const u8) *const llvm.Value { + fn getIntrinsic(self: *FuncGen, name: []const u8, types: []*const llvm.Type) *const llvm.Value { const id = llvm.lookupIntrinsicID(name.ptr, name.len); assert(id != 0); - // TODO: add support for overload intrinsics by passing the prefix of the intrinsic - // to `lookupIntrinsicID` and then passing the correct types to - // `getIntrinsicDeclaration` - return self.llvmModule().getIntrinsicDeclaration(id, null, 0); + return self.llvmModule().getIntrinsicDeclaration(id, types.ptr, types.len); } fn load(self: *FuncGen, ptr: *const llvm.Value, ptr_ty: Type) ?*const llvm.Value { diff --git a/src/print_air.zig b/src/print_air.zig index 3e503735b9..e11826c874 100644 --- a/src/print_air.zig +++ b/src/print_air.zig @@ -228,6 +228,7 @@ const Writer = struct { .atomic_rmw => try w.writeAtomicRmw(s, inst), .memcpy => try w.writeMemcpy(s, inst), .memset => try w.writeMemset(s, inst), + .add_with_overflow => try w.writeAddWithOverflow(s, inst), } } @@ -348,6 +349,17 @@ const Writer = struct { try s.print(", {s}, {s}", .{ @tagName(extra.op()), @tagName(extra.ordering()) }); } + fn writeAddWithOverflow(w: *Writer, s: anytype, inst: Air.Inst.Index) @TypeOf(s).Error!void { + const pl_op = w.air.instructions.items(.data)[inst].pl_op; + const extra = w.air.extraData(Air.Bin, pl_op.payload).data; + + try w.writeOperand(s, inst, 0, pl_op.operand); + try s.writeAll(", "); + try w.writeOperand(s, inst, 1, extra.lhs); + try s.writeAll(", "); + try w.writeOperand(s, inst, 2, extra.rhs); + } + fn writeMemset(w: *Writer, s: anytype, inst: Air.Inst.Index) @TypeOf(s).Error!void { const pl_op = w.air.instructions.items(.data)[inst].pl_op; const extra = w.air.extraData(Air.Bin, pl_op.payload).data; diff --git a/src/value.zig b/src/value.zig index e3d315b6e4..085883f7af 100644 --- a/src/value.zig +++ b/src/value.zig @@ -1969,20 +1969,18 @@ pub const Value = extern union { return @divFloor(@floatToInt(std.math.big.Limb, std.math.log2(w_value)), @typeInfo(std.math.big.Limb).Int.bits) + 1; } - /// Supports both floats and ints; handles undefined. - pub fn numberAddWrap( + pub const OverflowArithmeticResult = struct { + overflowed: bool, + wrapped_result: Value, + }; + + pub fn intAddWithOverflow( lhs: Value, rhs: Value, ty: Type, arena: Allocator, target: Target, - ) !Value { - if (lhs.isUndef() or rhs.isUndef()) return Value.initTag(.undef); - - if (ty.isAnyFloat()) { - return floatAdd(lhs, rhs, ty, arena); - } - + ) !OverflowArithmeticResult { const info = ty.intInfo(target); var lhs_space: Value.BigIntSpace = undefined; @@ -1994,8 +1992,30 @@ pub const Value = extern union { std.math.big.int.calcTwosCompLimbCount(info.bits), ); var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined }; - result_bigint.addWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits); - return fromBigInt(arena, result_bigint.toConst()); + const overflowed = result_bigint.addWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits); + const result = try fromBigInt(arena, result_bigint.toConst()); + return OverflowArithmeticResult{ + .overflowed = overflowed, + .wrapped_result = result, + }; + } + + /// Supports both floats and ints; handles undefined. + pub fn numberAddWrap( + lhs: Value, + rhs: Value, + ty: Type, + arena: Allocator, + target: Target, + ) !Value { + if (lhs.isUndef() or rhs.isUndef()) return Value.initTag(.undef); + + if (ty.isAnyFloat()) { + return floatAdd(lhs, rhs, ty, arena); + } + + const overflow_result = try intAddWithOverflow(lhs, rhs, ty, arena, target); + return overflow_result.wrapped_result; } fn fromBigInt(arena: Allocator, big_int: BigIntConst) !Value { @@ -2040,20 +2060,13 @@ pub const Value = extern union { return fromBigInt(arena, result_bigint.toConst()); } - /// Supports both floats and ints; handles undefined. - pub fn numberSubWrap( + pub fn intSubWithOverflow( lhs: Value, rhs: Value, ty: Type, arena: Allocator, target: Target, - ) !Value { - if (lhs.isUndef() or rhs.isUndef()) return Value.initTag(.undef); - - if (ty.isAnyFloat()) { - return floatSub(lhs, rhs, ty, arena); - } - + ) !OverflowArithmeticResult { const info = ty.intInfo(target); var lhs_space: Value.BigIntSpace = undefined; @@ -2065,8 +2078,30 @@ pub const Value = extern union { std.math.big.int.calcTwosCompLimbCount(info.bits), ); var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined }; - result_bigint.subWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits); - return fromBigInt(arena, result_bigint.toConst()); + const overflowed = result_bigint.subWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits); + const wrapped_result = try fromBigInt(arena, result_bigint.toConst()); + return OverflowArithmeticResult{ + .overflowed = overflowed, + .wrapped_result = wrapped_result, + }; + } + + /// Supports both floats and ints; handles undefined. + pub fn numberSubWrap( + lhs: Value, + rhs: Value, + ty: Type, + arena: Allocator, + target: Target, + ) !Value { + if (lhs.isUndef() or rhs.isUndef()) return Value.initTag(.undef); + + if (ty.isAnyFloat()) { + return floatSub(lhs, rhs, ty, arena); + } + + const overflow_result = try intSubWithOverflow(lhs, rhs, ty, arena, target); + return overflow_result.wrapped_result; } /// Supports integers only; asserts neither operand is undefined. diff --git a/test/behavior/math.zig b/test/behavior/math.zig index 1073183a3c..2cd67854af 100644 --- a/test/behavior/math.zig +++ b/test/behavior/math.zig @@ -444,3 +444,30 @@ test "128-bit multiplication" { var c = a * b; try expect(c == 6); } + +test "@addWithOverflow" { + var result: u8 = undefined; + try expect(@addWithOverflow(u8, 250, 100, &result)); + try expect(result == 94); + try expect(!@addWithOverflow(u8, 100, 150, &result)); + try expect(result == 250); +} + +test "small int addition" { + var x: u2 = 0; + try expect(x == 0); + + x += 1; + try expect(x == 1); + + x += 1; + try expect(x == 2); + + x += 1; + try expect(x == 3); + + var result: @TypeOf(x) = 3; + try expect(@addWithOverflow(@TypeOf(x), x, 1, &result)); + + try expect(result == 0); +} diff --git a/test/behavior/math_stage1.zig b/test/behavior/math_stage1.zig index e665b90740..63ff2cdec0 100644 --- a/test/behavior/math_stage1.zig +++ b/test/behavior/math_stage1.zig @@ -6,14 +6,6 @@ const maxInt = std.math.maxInt; const minInt = std.math.minInt; const mem = std.mem; -test "@addWithOverflow" { - var result: u8 = undefined; - try expect(@addWithOverflow(u8, 250, 100, &result)); - try expect(result == 94); - try expect(!@addWithOverflow(u8, 100, 150, &result)); - try expect(result == 250); -} - test "@mulWithOverflow" { var result: u8 = undefined; try expect(@mulWithOverflow(u8, 86, 3, &result)); @@ -90,25 +82,6 @@ fn testCtzVectors() !void { try expectEqual(@ctz(u16, @splat(64, @as(u16, 0b00000000))), @splat(64, @as(u5, 16))); } -test "small int addition" { - var x: u2 = 0; - try expect(x == 0); - - x += 1; - try expect(x == 1); - - x += 1; - try expect(x == 2); - - x += 1; - try expect(x == 3); - - var result: @TypeOf(x) = 3; - try expect(@addWithOverflow(@TypeOf(x), x, 1, &result)); - - try expect(result == 0); -} - test "allow signed integer division/remainder when values are comptime known and positive or exact" { try expect(5 / 3 == 1); try expect(-5 / -3 == 1); -- cgit v1.2.3 From ddd2ef822f99979d3ea61583a91ab236942e6367 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Sat, 18 Dec 2021 06:11:46 +0100 Subject: stage2: @returnAddress() --- src/Air.zig | 4 ++++ src/Liveness.zig | 1 + src/Sema.zig | 6 +++++- src/arch/aarch64/CodeGen.zig | 5 +++++ src/arch/arm/CodeGen.zig | 5 +++++ src/arch/riscv64/CodeGen.zig | 5 +++++ src/arch/x86_64/CodeGen.zig | 5 +++++ src/codegen/c.zig | 5 +++++ src/codegen/llvm.zig | 10 ++++++++++ src/print_air.zig | 1 + 10 files changed, 46 insertions(+), 1 deletion(-) (limited to 'src/codegen') diff --git a/src/Air.zig b/src/Air.zig index 72e281d03e..9e4a61b9a2 100644 --- a/src/Air.zig +++ b/src/Air.zig @@ -195,6 +195,9 @@ pub const Inst = struct { /// Lowers to a hardware trap instruction, or the next best thing. /// Result type is always void. breakpoint, + /// Yields the return address of the current function. + /// Uses the `no_op` field. + ret_addr, /// Function call. /// Result type is the return type of the function being called. /// Uses the `pl_op` field with the `Call` payload. operand is the callee. @@ -785,6 +788,7 @@ pub fn typeOfIndex(air: Air, inst: Air.Inst.Index) Type { .ptrtoint, .slice_len, + .ret_addr, => return Type.initTag(.usize), .bool_to_int => return Type.initTag(.u1), diff --git a/src/Liveness.zig b/src/Liveness.zig index a7128e2cc2..160a2e97d3 100644 --- a/src/Liveness.zig +++ b/src/Liveness.zig @@ -281,6 +281,7 @@ fn analyzeInst( .dbg_stmt, .unreach, .fence, + .ret_addr, => return trackOperands(a, new_set, inst, main_tomb, .{ .none, .none, .none }), .not, diff --git a/src/Sema.zig b/src/Sema.zig index 9b9371c856..03ee58dc06 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -8739,8 +8739,12 @@ fn zirRetAddr( block: *Block, extended: Zir.Inst.Extended.InstData, ) CompileError!Air.Inst.Ref { + const tracy = trace(@src()); + defer tracy.end(); + const src: LazySrcLoc = .{ .node_offset = @bitCast(i32, extended.operand) }; - return sema.fail(block, src, "TODO: implement Sema.zirRetAddr", .{}); + try sema.requireRuntimeBlock(block, src); + return try block.addNoOp(.ret_addr); } fn zirBuiltinSrc( diff --git a/src/arch/aarch64/CodeGen.zig b/src/arch/aarch64/CodeGen.zig index fda673631d..1c6d54485b 100644 --- a/src/arch/aarch64/CodeGen.zig +++ b/src/arch/aarch64/CodeGen.zig @@ -547,6 +547,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .block => try self.airBlock(inst), .br => try self.airBr(inst), .breakpoint => try self.airBreakpoint(), + .ret_addr => try self.airRetAddr(), .fence => try self.airFence(), .call => try self.airCall(inst), .cond_br => try self.airCondBr(inst), @@ -1416,6 +1417,10 @@ fn airBreakpoint(self: *Self) !void { return self.finishAirBookkeeping(); } +fn airRetAddr(self: *Self) !void { + return self.fail("TODO implement airRetAddr for {}", .{self.target.cpu.arch}); +} + fn airFence(self: *Self) !void { return self.fail("TODO implement fence() for {}", .{self.target.cpu.arch}); //return self.finishAirBookkeeping(); diff --git a/src/arch/arm/CodeGen.zig b/src/arch/arm/CodeGen.zig index bcc1b927e7..0039d78434 100644 --- a/src/arch/arm/CodeGen.zig +++ b/src/arch/arm/CodeGen.zig @@ -545,6 +545,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .block => try self.airBlock(inst), .br => try self.airBr(inst), .breakpoint => try self.airBreakpoint(), + .ret_addr => try self.airRetAddr(), .fence => try self.airFence(), .call => try self.airCall(inst), .cond_br => try self.airCondBr(inst), @@ -1850,6 +1851,10 @@ fn airBreakpoint(self: *Self) !void { return self.finishAirBookkeeping(); } +fn airRetAddr(self: *Self) !void { + return self.fail("TODO implement airRetAddr for {}", .{self.target.cpu.arch}); +} + fn airFence(self: *Self) !void { return self.fail("TODO implement fence() for {}", .{self.target.cpu.arch}); //return self.finishAirBookkeeping(); diff --git a/src/arch/riscv64/CodeGen.zig b/src/arch/riscv64/CodeGen.zig index 1d67ad0abf..51703681e9 100644 --- a/src/arch/riscv64/CodeGen.zig +++ b/src/arch/riscv64/CodeGen.zig @@ -526,6 +526,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .block => try self.airBlock(inst), .br => try self.airBr(inst), .breakpoint => try self.airBreakpoint(), + .ret_addr => try self.airRetAddr(), .fence => try self.airFence(), .call => try self.airCall(inst), .cond_br => try self.airCondBr(inst), @@ -1354,6 +1355,10 @@ fn airBreakpoint(self: *Self) !void { return self.finishAirBookkeeping(); } +fn airRetAddr(self: *Self) !void { + return self.fail("TODO implement airRetAddr for {}", .{self.target.cpu.arch}); +} + fn airFence(self: *Self) !void { return self.fail("TODO implement fence() for {}", .{self.target.cpu.arch}); //return self.finishAirBookkeeping(); diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index 8fadcdd5f5..3b40293527 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -579,6 +579,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .block => try self.airBlock(inst), .br => try self.airBr(inst), .breakpoint => try self.airBreakpoint(), + .ret_addr => try self.airRetAddr(), .fence => try self.airFence(), .call => try self.airCall(inst), .cond_br => try self.airCondBr(inst), @@ -1839,6 +1840,10 @@ fn airBreakpoint(self: *Self) !void { return self.finishAirBookkeeping(); } +fn airRetAddr(self: *Self) !void { + return self.fail("TODO implement airRetAddr for {}", .{self.target.cpu.arch}); +} + fn airFence(self: *Self) !void { return self.fail("TODO implement fence() for {}", .{self.target.cpu.arch}); //return self.finishAirBookkeeping(); diff --git a/src/codegen/c.zig b/src/codegen/c.zig index b086d15b48..070aa0a238 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -1125,6 +1125,7 @@ fn genBody(f: *Function, body: []const Air.Inst.Index) error{ AnalysisFail, OutO .arg => airArg(f), .breakpoint => try airBreakpoint(f), + .ret_addr => try airRetAddr(f), .unreach => try airUnreach(f), .fence => try airFence(f, inst), @@ -2191,6 +2192,10 @@ fn airBreakpoint(f: *Function) !CValue { return CValue.none; } +fn airRetAddr(f: *Function) !CValue { + return f.fail("TODO implement codegen for airRetAddr", .{}); +} + fn airFence(f: *Function, inst: Air.Inst.Index) !CValue { const atomic_order = f.air.instructions.items(.data)[inst].fence; const writer = f.object.writer(); diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig index d12dad2403..0a2b12dd1e 100644 --- a/src/codegen/llvm.zig +++ b/src/codegen/llvm.zig @@ -1747,6 +1747,7 @@ pub const FuncGen = struct { .br => try self.airBr(inst), .switch_br => try self.airSwitchBr(inst), .breakpoint => try self.airBreakpoint(inst), + .ret_addr => try self.airRetAddr(inst), .call => try self.airCall(inst), .cond_br => try self.airCondBr(inst), .intcast => try self.airIntCast(inst), @@ -3550,6 +3551,15 @@ pub const FuncGen = struct { return null; } + fn airRetAddr(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { + _ = inst; + const i32_zero = self.context.intType(32).constNull(); + const usize_llvm_ty = try self.dg.llvmType(Type.usize); + const llvm_fn = self.getIntrinsic("llvm.returnaddress", &.{}); + const ptr_val = self.builder.buildCall(llvm_fn, &[_]*const llvm.Value{i32_zero}, 1, .Fast, .Auto, ""); + return self.builder.buildPtrToInt(ptr_val, usize_llvm_ty, ""); + } + fn airFence(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { const atomic_order = self.air.instructions.items(.data)[inst].fence; const llvm_memory_order = toLlvmAtomicOrdering(atomic_order); diff --git a/src/print_air.zig b/src/print_air.zig index e11826c874..17af7ebf62 100644 --- a/src/print_air.zig +++ b/src/print_air.zig @@ -159,6 +159,7 @@ const Writer = struct { .breakpoint, .unreach, + .ret_addr, => try w.writeNoOp(s, inst), .const_ty, -- cgit v1.2.3 From c47ed0c912d2f445710fe4486fa071dd63601989 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Mon, 20 Dec 2021 02:06:09 +0100 Subject: stage2: @mulWithOverflow --- src/Air.zig | 10 +++++++- src/Liveness.zig | 2 +- src/Sema.zig | 56 +++++++++++++++++++++++++++++++++++++++---- src/arch/aarch64/CodeGen.zig | 6 +++++ src/arch/arm/CodeGen.zig | 6 +++++ src/arch/riscv64/CodeGen.zig | 6 +++++ src/arch/x86_64/CodeGen.zig | 6 +++++ src/codegen/c.zig | 7 ++++++ src/codegen/llvm.zig | 15 +++++++----- src/print_air.zig | 7 ++++-- src/value.zig | 48 +++++++++++++++++++++++++------------ test/behavior/math.zig | 24 +++++++++++++++++++ test/behavior/math_stage1.zig | 8 ------- 13 files changed, 164 insertions(+), 37 deletions(-) (limited to 'src/codegen') diff --git a/src/Air.zig b/src/Air.zig index 9e4a61b9a2..5d54be7392 100644 --- a/src/Air.zig +++ b/src/Air.zig @@ -141,6 +141,12 @@ pub const Inst = struct { /// of the operation. /// Uses the `pl_op` field with payload `Bin`. add_with_overflow, + /// Integer multiplication with overflow. Both operands are guaranteed to be the same type, + /// and the result is bool. The wrapped value is written to the pointer given by the in + /// operand of the `pl_op` field. Payload is `Bin` with `lhs` and `rhs` the relevant types + /// of the operation. + /// Uses the `pl_op` field with payload `Bin`. + mul_with_overflow, /// Allocates stack local memory. /// Uses the `ty` field. alloc, @@ -815,7 +821,9 @@ pub fn typeOfIndex(air: Air, inst: Air.Inst.Index) Type { return ptr_ty.elemType(); }, - .add_with_overflow => return Type.initTag(.bool), + .add_with_overflow, + .mul_with_overflow, + => return Type.initTag(.bool), } } diff --git a/src/Liveness.zig b/src/Liveness.zig index 160a2e97d3..6859f64660 100644 --- a/src/Liveness.zig +++ b/src/Liveness.zig @@ -382,7 +382,7 @@ fn analyzeInst( const extra = a.air.extraData(Air.AtomicRmw, pl_op.payload).data; return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.operand, .none }); }, - .memset, .memcpy, .add_with_overflow => { + .memset, .memcpy, .add_with_overflow, .mul_with_overflow => { const pl_op = inst_datas[inst].pl_op; const extra = a.air.extraData(Air.Bin, pl_op.payload).data; return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.lhs, extra.rhs }); diff --git a/src/Sema.zig b/src/Sema.zig index 03ee58dc06..38183d1052 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -7343,8 +7343,8 @@ fn zirOverflowArithmetic( overflowed: enum { yes, no, undef }, wrapped: Air.Inst.Ref, } = result: { - const air_tag: Air.Inst.Tag = switch (zir_tag) { - .add_with_overflow => blk: { + switch (zir_tag) { + .add_with_overflow => { // If either of the arguments is zero, `false` is returned and the other is stored // to the result, even if it is undefined.. // Otherwise, if either of the argument is undefined, undefined is returned. @@ -7377,14 +7377,62 @@ fn zirOverflowArithmetic( } } } + }, + .mul_with_overflow => { + // If either of the arguments is zero, the result is zero and no overflow occured. + // If either of the arguments is one, the result is the other and no overflow occured. + // Otherwise, if either of the arguments is undefined, both results are undefined. + + if (maybe_lhs_val) |lhs_val| { + if (!lhs_val.isUndef()) { + if (lhs_val.compareWithZero(.eq)) { + break :result .{ .overflowed = .no, .wrapped = lhs }; + } else if (lhs_val.compare(.eq, Value.one, dest_ty)) { + break :result .{ .overflowed = .no, .wrapped = rhs }; + } + } + } - break :blk .add_with_overflow; + if (maybe_rhs_val) |rhs_val| { + if (!rhs_val.isUndef()) { + if (rhs_val.compareWithZero(.eq)) { + break :result .{ .overflowed = .no, .wrapped = rhs }; + } else if (rhs_val.compare(.eq, Value.one, dest_ty)) { + break :result .{ .overflowed = .no, .wrapped = lhs }; + } + } + } + + if (maybe_lhs_val) |lhs_val| { + if (maybe_rhs_val) |rhs_val| { + if (lhs_val.isUndef() or rhs_val.isUndef()) { + break :result .{ .overflowed = .undef, .wrapped = try sema.addConstUndef(dest_ty) }; + } + + const result = try lhs_val.intMulWithOverflow(rhs_val, dest_ty, sema.arena, target); + const inst = try sema.addConstant( + dest_ty, + result.wrapped_result, + ); + + if (result.overflowed) { + break :result .{ .overflowed = .yes, .wrapped = inst }; + } else { + break :result .{ .overflowed = .no, .wrapped = inst }; + } + } + } }, .sub_with_overflow, - .mul_with_overflow, .shl_with_overflow, => return sema.fail(block, src, "TODO implement Sema.zirOverflowArithmetic for {}", .{zir_tag}), else => unreachable, + } + + const air_tag: Air.Inst.Tag = switch (zir_tag) { + .add_with_overflow => .add_with_overflow, + .mul_with_overflow => .mul_with_overflow, + else => return sema.fail(block, src, "TODO implement runtime Sema.zirOverflowArithmetic for {}", .{zir_tag}), }; try sema.requireRuntimeBlock(block, src); diff --git a/src/arch/aarch64/CodeGen.zig b/src/arch/aarch64/CodeGen.zig index 1c6d54485b..e34475f1ee 100644 --- a/src/arch/aarch64/CodeGen.zig +++ b/src/arch/aarch64/CodeGen.zig @@ -522,6 +522,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -976,6 +977,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) .dead else return self.fail("TODO implement div for {}", .{self.target.cpu.arch}); diff --git a/src/arch/arm/CodeGen.zig b/src/arch/arm/CodeGen.zig index 0039d78434..779ce52036 100644 --- a/src/arch/arm/CodeGen.zig +++ b/src/arch/arm/CodeGen.zig @@ -520,6 +520,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -1006,6 +1007,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) .dead else return self.fail("TODO implement div for {}", .{self.target.cpu.arch}); diff --git a/src/arch/riscv64/CodeGen.zig b/src/arch/riscv64/CodeGen.zig index 51703681e9..c8f7173b1c 100644 --- a/src/arch/riscv64/CodeGen.zig +++ b/src/arch/riscv64/CodeGen.zig @@ -501,6 +501,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -921,6 +922,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) .dead else return self.fail("TODO implement div for {}", .{self.target.cpu.arch}); diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index 3b40293527..fe8d8b55f7 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -554,6 +554,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -1035,6 +1036,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airDiv(self: *Self, inst: Air.Inst.Index) !void { const bin_op = self.air.instructions.items(.data)[inst].bin_op; const result: MCValue = if (self.liveness.isUnused(inst)) diff --git a/src/codegen/c.zig b/src/codegen/c.zig index 070aa0a238..f6a3105760 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -1157,6 +1157,7 @@ fn genBody(f: *Function, body: []const Air.Inst.Index) error{ AnalysisFail, OutO .shl_sat => try airSatOp(f, inst, "shls_"), .add_with_overflow => try airAddWithOverflow(f, inst), + .mul_with_overflow => try airMulWithOverflow(f, inst), .min => try airMinMax(f, inst, "<"), .max => try airMinMax(f, inst, ">"), @@ -1873,6 +1874,12 @@ fn airAddWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { return f.fail("TODO add with overflow", .{}); } +fn airMulWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { + _ = f; + _ = inst; + return f.fail("TODO mul with overflow", .{}); +} + fn airNot(f: *Function, inst: Air.Inst.Index) !CValue { if (f.liveness.isUnused(inst)) return CValue.none; diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig index 0a2b12dd1e..209e3fb4de 100644 --- a/src/codegen/llvm.zig +++ b/src/codegen/llvm.zig @@ -1714,7 +1714,8 @@ pub const FuncGen = struct { .max => try self.airMax(inst), .slice => try self.airSlice(inst), - .add_with_overflow => try self.airAddWithOverflow(inst), + .add_with_overflow => try self.airOverflow(inst, "llvm.sadd.with.overflow", "llvm.uadd.with.overflow"), + .mul_with_overflow => try self.airOverflow(inst, "llvm.smul.with.overflow", "llvm.umul.with.overflow"), .bit_and, .bool_and => try self.airAnd(inst), .bit_or, .bool_or => try self.airOr(inst), @@ -3136,7 +3137,12 @@ pub const FuncGen = struct { } } - fn airAddWithOverflow(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { + fn airOverflow( + self: *FuncGen, + inst: Air.Inst.Index, + signed_intrinsic: []const u8, + unsigned_intrinsic: []const u8, + ) !?*const llvm.Value { if (self.liveness.isUnused(inst)) return null; @@ -3150,10 +3156,7 @@ pub const FuncGen = struct { const ptr_ty = self.air.typeOf(pl_op.operand); const lhs_ty = self.air.typeOf(extra.lhs); - const intrinsic_name: []const u8 = if (lhs_ty.isSignedInt()) - "llvm.sadd.with.overflow" - else - "llvm.uadd.with.overflow"; + const intrinsic_name = if (lhs_ty.isSignedInt()) signed_intrinsic else unsigned_intrinsic; const llvm_lhs_ty = try self.dg.llvmType(lhs_ty); diff --git a/src/print_air.zig b/src/print_air.zig index 17af7ebf62..2204d16bd6 100644 --- a/src/print_air.zig +++ b/src/print_air.zig @@ -229,7 +229,10 @@ const Writer = struct { .atomic_rmw => try w.writeAtomicRmw(s, inst), .memcpy => try w.writeMemcpy(s, inst), .memset => try w.writeMemset(s, inst), - .add_with_overflow => try w.writeAddWithOverflow(s, inst), + + .add_with_overflow, + .mul_with_overflow, + => try w.writeOverflow(s, inst), } } @@ -350,7 +353,7 @@ const Writer = struct { try s.print(", {s}, {s}", .{ @tagName(extra.op()), @tagName(extra.ordering()) }); } - fn writeAddWithOverflow(w: *Writer, s: anytype, inst: Air.Inst.Index) @TypeOf(s).Error!void { + fn writeOverflow(w: *Writer, s: anytype, inst: Air.Inst.Index) @TypeOf(s).Error!void { const pl_op = w.air.instructions.items(.data)[inst].pl_op; const extra = w.air.extraData(Air.Bin, pl_op.payload).data; diff --git a/src/value.zig b/src/value.zig index 085883f7af..19546ed8b9 100644 --- a/src/value.zig +++ b/src/value.zig @@ -2130,20 +2130,13 @@ pub const Value = extern union { return fromBigInt(arena, result_bigint.toConst()); } - /// Supports both floats and ints; handles undefined. - pub fn numberMulWrap( + pub fn intMulWithOverflow( lhs: Value, rhs: Value, ty: Type, arena: Allocator, target: Target, - ) !Value { - if (lhs.isUndef() or rhs.isUndef()) return Value.initTag(.undef); - - if (ty.isAnyFloat()) { - return floatMul(lhs, rhs, ty, arena); - } - + ) !OverflowArithmeticResult { const info = ty.intInfo(target); var lhs_space: Value.BigIntSpace = undefined; @@ -2152,16 +2145,42 @@ pub const Value = extern union { const rhs_bigint = rhs.toBigInt(&rhs_space); const limbs = try arena.alloc( std.math.big.Limb, - std.math.big.int.calcTwosCompLimbCount(info.bits), + lhs_bigint.limbs.len + rhs_bigint.limbs.len, ); var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined }; var limbs_buffer = try arena.alloc( std.math.big.Limb, - std.math.big.int.calcMulWrapLimbsBufferLen(info.bits, lhs_bigint.limbs.len, rhs_bigint.limbs.len, 1), + std.math.big.int.calcMulLimbsBufferLen(lhs_bigint.limbs.len, rhs_bigint.limbs.len, 1), ); - defer arena.free(limbs_buffer); - result_bigint.mulWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits, limbs_buffer, arena); - return fromBigInt(arena, result_bigint.toConst()); + result_bigint.mul(lhs_bigint, rhs_bigint, limbs_buffer, arena); + + const overflowed = !result_bigint.toConst().fitsInTwosComp(info.signedness, info.bits); + if (overflowed) { + result_bigint.truncate(result_bigint.toConst(), info.signedness, info.bits); + } + + return OverflowArithmeticResult{ + .overflowed = overflowed, + .wrapped_result = try fromBigInt(arena, result_bigint.toConst()), + }; + } + + /// Supports both floats and ints; handles undefined. + pub fn numberMulWrap( + lhs: Value, + rhs: Value, + ty: Type, + arena: Allocator, + target: Target, + ) !Value { + if (lhs.isUndef() or rhs.isUndef()) return Value.initTag(.undef); + + if (ty.isAnyFloat()) { + return floatMul(lhs, rhs, ty, arena); + } + + const overflow_result = try intMulWithOverflow(lhs, rhs, ty, arena, target); + return overflow_result.wrapped_result; } /// Supports integers only; asserts neither operand is undefined. @@ -2194,7 +2213,6 @@ pub const Value = extern union { std.math.big.Limb, std.math.big.int.calcMulLimbsBufferLen(lhs_bigint.limbs.len, rhs_bigint.limbs.len, 1), ); - defer arena.free(limbs_buffer); result_bigint.mul(lhs_bigint, rhs_bigint, limbs_buffer, arena); result_bigint.saturate(result_bigint.toConst(), info.signedness, info.bits); return fromBigInt(arena, result_bigint.toConst()); diff --git a/test/behavior/math.zig b/test/behavior/math.zig index 2cd67854af..963fe3f0d5 100644 --- a/test/behavior/math.zig +++ b/test/behavior/math.zig @@ -451,6 +451,14 @@ test "@addWithOverflow" { try expect(result == 94); try expect(!@addWithOverflow(u8, 100, 150, &result)); try expect(result == 250); + + var a: u8 = 200; + var b: u8 = 99; + try expect(@addWithOverflow(u8, a, b, &result)); + try expect(result == 43); + b = 55; + try expect(!@addWithOverflow(u8, a, b, &result)); + try expect(result == 255); } test "small int addition" { @@ -471,3 +479,19 @@ test "small int addition" { try expect(result == 0); } + +test "@mulWithOverflow" { + var result: u8 = undefined; + try expect(@mulWithOverflow(u8, 86, 3, &result)); + try expect(result == 2); + try expect(!@mulWithOverflow(u8, 85, 3, &result)); + try expect(result == 255); + + var a: u8 = 123; + var b: u8 = 2; + try expect(!@mulWithOverflow(u8, a, b, &result)); + try expect(result == 246); + b = 4; + try expect(@mulWithOverflow(u8, a, b, &result)); + try expect(result == 236); +} diff --git a/test/behavior/math_stage1.zig b/test/behavior/math_stage1.zig index 63ff2cdec0..381f89634b 100644 --- a/test/behavior/math_stage1.zig +++ b/test/behavior/math_stage1.zig @@ -6,14 +6,6 @@ const maxInt = std.math.maxInt; const minInt = std.math.minInt; const mem = std.mem; -test "@mulWithOverflow" { - var result: u8 = undefined; - try expect(@mulWithOverflow(u8, 86, 3, &result)); - try expect(result == 2); - try expect(!@mulWithOverflow(u8, 85, 3, &result)); - try expect(result == 255); -} - test "@subWithOverflow" { var result: u8 = undefined; try expect(@subWithOverflow(u8, 1, 2, &result)); -- cgit v1.2.3 From 58d67a6718d5d0673389fa19f5bb20812b4bb22a Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Mon, 20 Dec 2021 03:58:19 +0100 Subject: stage2: make anyopaque sized While this is technically incorrect, proper handling of anyopaque, as well as regular opaque, is probably best left until pointers to zero-sized types having no bits is abolished. --- src/codegen/llvm.zig | 28 ++++++++++++++++------------ src/type.zig | 2 +- 2 files changed, 17 insertions(+), 13 deletions(-) (limited to 'src/codegen') diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig index 209e3fb4de..07fe138786 100644 --- a/src/codegen/llvm.zig +++ b/src/codegen/llvm.zig @@ -761,21 +761,25 @@ pub const DeclGen = struct { dg.context.intType(8); return llvm_elem_ty.pointerType(llvm_addrspace); }, - .Opaque => { - const gop = try dg.object.type_map.getOrPut(gpa, t); - if (gop.found_existing) return gop.value_ptr.*; + .Opaque => switch (t.tag()) { + .@"opaque" => { + const gop = try dg.object.type_map.getOrPut(gpa, t); + if (gop.found_existing) return gop.value_ptr.*; - // The Type memory is ephemeral; since we want to store a longer-lived - // reference, we need to copy it here. - gop.key_ptr.* = try t.copy(dg.object.type_map_arena.allocator()); + // The Type memory is ephemeral; since we want to store a longer-lived + // reference, we need to copy it here. + gop.key_ptr.* = try t.copy(dg.object.type_map_arena.allocator()); - const opaque_obj = t.castTag(.@"opaque").?.data; - const name = try opaque_obj.getFullyQualifiedName(gpa); - defer gpa.free(name); + const opaque_obj = t.castTag(.@"opaque").?.data; + const name = try opaque_obj.getFullyQualifiedName(gpa); + defer gpa.free(name); - const llvm_struct_ty = dg.context.structCreateNamed(name); - gop.value_ptr.* = llvm_struct_ty; // must be done before any recursive calls - return llvm_struct_ty; + const llvm_struct_ty = dg.context.structCreateNamed(name); + gop.value_ptr.* = llvm_struct_ty; // must be done before any recursive calls + return llvm_struct_ty; + }, + .anyopaque => return dg.context.intType(8), + else => unreachable, }, .Array => { const elem_type = try dg.llvmType(t.childType()); diff --git a/src/type.zig b/src/type.zig index a81bd3ed32..fb16a4d0f1 100644 --- a/src/type.zig +++ b/src/type.zig @@ -1575,6 +1575,7 @@ pub const Type = extern union { .extern_options, .@"anyframe", .anyframe_T, + .anyopaque, .@"opaque", .single_const_pointer, .single_mut_pointer, @@ -1654,7 +1655,6 @@ pub const Type = extern union { return payload.error_set.hasCodeGenBits() or payload.payload.hasCodeGenBits(); }, - .anyopaque, .void, .type, .comptime_int, -- cgit v1.2.3 From 964dbeb82623515b8392c8c7cb9317246812174e Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Mon, 20 Dec 2021 21:53:40 +0100 Subject: stage2: @subWithOverflow --- src/Air.zig | 7 +++++++ src/Liveness.zig | 7 ++++++- src/Sema.zig | 44 ++++++++++++++++++++++--------------------- src/arch/aarch64/CodeGen.zig | 6 ++++++ src/arch/arm/CodeGen.zig | 6 ++++++ src/arch/riscv64/CodeGen.zig | 6 ++++++ src/arch/x86_64/CodeGen.zig | 6 ++++++ src/codegen/c.zig | 7 +++++++ src/codegen/llvm.zig | 1 + src/print_air.zig | 1 + test/behavior/math.zig | 16 ++++++++++++++++ test/behavior/math_stage1.zig | 8 -------- 12 files changed, 85 insertions(+), 30 deletions(-) (limited to 'src/codegen') diff --git a/src/Air.zig b/src/Air.zig index 5d54be7392..912e70daed 100644 --- a/src/Air.zig +++ b/src/Air.zig @@ -141,6 +141,12 @@ pub const Inst = struct { /// of the operation. /// Uses the `pl_op` field with payload `Bin`. add_with_overflow, + /// Integer subtraction with overflow. Both operands are guaranteed to be the same type, + /// and the result is bool. The wrapped value is written to the pointer given by the in + /// operand of the `pl_op` field. Payload is `Bin` with `lhs` and `rhs` the relevant types + /// of the operation. + /// Uses the `pl_op` field with payload `Bin`. + sub_with_overflow, /// Integer multiplication with overflow. Both operands are guaranteed to be the same type, /// and the result is bool. The wrapped value is written to the pointer given by the in /// operand of the `pl_op` field. Payload is `Bin` with `lhs` and `rhs` the relevant types @@ -822,6 +828,7 @@ pub fn typeOfIndex(air: Air, inst: Air.Inst.Index) Type { }, .add_with_overflow, + .sub_with_overflow, .mul_with_overflow, => return Type.initTag(.bool), } diff --git a/src/Liveness.zig b/src/Liveness.zig index 6859f64660..ad0ce7ffb9 100644 --- a/src/Liveness.zig +++ b/src/Liveness.zig @@ -382,7 +382,12 @@ fn analyzeInst( const extra = a.air.extraData(Air.AtomicRmw, pl_op.payload).data; return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.operand, .none }); }, - .memset, .memcpy, .add_with_overflow, .mul_with_overflow => { + .memset, + .memcpy, + .add_with_overflow, + .sub_with_overflow, + .mul_with_overflow, + => { const pl_op = inst_datas[inst].pl_op; const extra = a.air.extraData(Air.Bin, pl_op.payload).data; return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.lhs, extra.rhs }); diff --git a/src/Sema.zig b/src/Sema.zig index 38183d1052..2eb661503e 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -7365,16 +7365,27 @@ fn zirOverflowArithmetic( } const result = try lhs_val.intAddWithOverflow(rhs_val, dest_ty, sema.arena, target); - const inst = try sema.addConstant( - dest_ty, - result.wrapped_result, - ); - - if (result.overflowed) { - break :result .{ .overflowed = .yes, .wrapped = inst }; - } else { - break :result .{ .overflowed = .no, .wrapped = inst }; + const inst = try sema.addConstant(dest_ty, result.wrapped_result); + break :result .{ .overflowed = if (result.overflowed) .yes else .no, .wrapped = inst }; + } + } + }, + .sub_with_overflow => { + // If the rhs is zero, then the result is lhs and no overflow occured. + // Otherwise, if either result is undefined, both results are undefined. + if (maybe_rhs_val) |rhs_val| { + if (rhs_val.isUndef()) { + break :result .{ .overflowed = .undef, .wrapped = try sema.addConstUndef(dest_ty) }; + } else if (rhs_val.compareWithZero(.eq)) { + break :result .{ .overflowed = .no, .wrapped = lhs }; + } else if (maybe_lhs_val) |lhs_val| { + if (lhs_val.isUndef()) { + break :result .{ .overflowed = .undef, .wrapped = try sema.addConstUndef(dest_ty) }; } + + const result = try lhs_val.intSubWithOverflow(rhs_val, dest_ty, sema.arena, target); + const inst = try sema.addConstant(dest_ty, result.wrapped_result); + break :result .{ .overflowed = if (result.overflowed) .yes else .no, .wrapped = inst }; } } }, @@ -7382,7 +7393,6 @@ fn zirOverflowArithmetic( // If either of the arguments is zero, the result is zero and no overflow occured. // If either of the arguments is one, the result is the other and no overflow occured. // Otherwise, if either of the arguments is undefined, both results are undefined. - if (maybe_lhs_val) |lhs_val| { if (!lhs_val.isUndef()) { if (lhs_val.compareWithZero(.eq)) { @@ -7410,20 +7420,11 @@ fn zirOverflowArithmetic( } const result = try lhs_val.intMulWithOverflow(rhs_val, dest_ty, sema.arena, target); - const inst = try sema.addConstant( - dest_ty, - result.wrapped_result, - ); - - if (result.overflowed) { - break :result .{ .overflowed = .yes, .wrapped = inst }; - } else { - break :result .{ .overflowed = .no, .wrapped = inst }; - } + const inst = try sema.addConstant(dest_ty, result.wrapped_result); + break :result .{ .overflowed = if (result.overflowed) .yes else .no, .wrapped = inst }; } } }, - .sub_with_overflow, .shl_with_overflow, => return sema.fail(block, src, "TODO implement Sema.zirOverflowArithmetic for {}", .{zir_tag}), else => unreachable, @@ -7432,6 +7433,7 @@ fn zirOverflowArithmetic( const air_tag: Air.Inst.Tag = switch (zir_tag) { .add_with_overflow => .add_with_overflow, .mul_with_overflow => .mul_with_overflow, + .sub_with_overflow => .sub_with_overflow, else => return sema.fail(block, src, "TODO implement runtime Sema.zirOverflowArithmetic for {}", .{zir_tag}), }; diff --git a/src/arch/aarch64/CodeGen.zig b/src/arch/aarch64/CodeGen.zig index e34475f1ee..b381116a51 100644 --- a/src/arch/aarch64/CodeGen.zig +++ b/src/arch/aarch64/CodeGen.zig @@ -522,6 +522,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -977,6 +978,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); diff --git a/src/arch/arm/CodeGen.zig b/src/arch/arm/CodeGen.zig index 779ce52036..f887810d9a 100644 --- a/src/arch/arm/CodeGen.zig +++ b/src/arch/arm/CodeGen.zig @@ -520,6 +520,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -1007,6 +1008,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); diff --git a/src/arch/riscv64/CodeGen.zig b/src/arch/riscv64/CodeGen.zig index c8f7173b1c..56904206ab 100644 --- a/src/arch/riscv64/CodeGen.zig +++ b/src/arch/riscv64/CodeGen.zig @@ -501,6 +501,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -922,6 +923,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index fe8d8b55f7..be26372031 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -554,6 +554,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .slice => try self.airSlice(inst), .add_with_overflow => try self.airAddWithOverflow(inst), + .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -1036,6 +1037,11 @@ fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); } +fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); +} + fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); diff --git a/src/codegen/c.zig b/src/codegen/c.zig index f6a3105760..68b700db17 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -1157,6 +1157,7 @@ fn genBody(f: *Function, body: []const Air.Inst.Index) error{ AnalysisFail, OutO .shl_sat => try airSatOp(f, inst, "shls_"), .add_with_overflow => try airAddWithOverflow(f, inst), + .sub_with_overflow => try airSubWithOverflow(f, inst), .mul_with_overflow => try airMulWithOverflow(f, inst), .min => try airMinMax(f, inst, "<"), @@ -1874,6 +1875,12 @@ fn airAddWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { return f.fail("TODO add with overflow", .{}); } +fn airSubWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { + _ = f; + _ = inst; + return f.fail("TODO sub with overflow", .{}); +} + fn airMulWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { _ = f; _ = inst; diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig index 07fe138786..4089a39cb3 100644 --- a/src/codegen/llvm.zig +++ b/src/codegen/llvm.zig @@ -1719,6 +1719,7 @@ pub const FuncGen = struct { .slice => try self.airSlice(inst), .add_with_overflow => try self.airOverflow(inst, "llvm.sadd.with.overflow", "llvm.uadd.with.overflow"), + .sub_with_overflow => try self.airOverflow(inst, "llvm.ssub.with.overflow", "llvm.usub.with.overflow"), .mul_with_overflow => try self.airOverflow(inst, "llvm.smul.with.overflow", "llvm.umul.with.overflow"), .bit_and, .bool_and => try self.airAnd(inst), diff --git a/src/print_air.zig b/src/print_air.zig index 2204d16bd6..d6bfaac4bc 100644 --- a/src/print_air.zig +++ b/src/print_air.zig @@ -231,6 +231,7 @@ const Writer = struct { .memset => try w.writeMemset(s, inst), .add_with_overflow, + .sub_with_overflow, .mul_with_overflow, => try w.writeOverflow(s, inst), } diff --git a/test/behavior/math.zig b/test/behavior/math.zig index 963fe3f0d5..50a7267c93 100644 --- a/test/behavior/math.zig +++ b/test/behavior/math.zig @@ -495,3 +495,19 @@ test "@mulWithOverflow" { try expect(@mulWithOverflow(u8, a, b, &result)); try expect(result == 236); } + +test "@subWithOverflow" { + var result: u8 = undefined; + try expect(@subWithOverflow(u8, 1, 2, &result)); + try expect(result == 255); + try expect(!@subWithOverflow(u8, 1, 1, &result)); + try expect(result == 0); + + var a: u8 = 1; + var b: u8 = 2; + try expect(@subWithOverflow(u8, a, b, &result)); + try expect(result == 255); + b = 1; + try expect(!@subWithOverflow(u8, a, b, &result)); + try expect(result == 0); +} diff --git a/test/behavior/math_stage1.zig b/test/behavior/math_stage1.zig index 381f89634b..139593b9f5 100644 --- a/test/behavior/math_stage1.zig +++ b/test/behavior/math_stage1.zig @@ -6,14 +6,6 @@ const maxInt = std.math.maxInt; const minInt = std.math.minInt; const mem = std.mem; -test "@subWithOverflow" { - var result: u8 = undefined; - try expect(@subWithOverflow(u8, 1, 2, &result)); - try expect(result == 255); - try expect(!@subWithOverflow(u8, 1, 1, &result)); - try expect(result == 0); -} - test "@shlWithOverflow" { var result: u16 = undefined; try expect(@shlWithOverflow(u16, 0b0010111111111111, 3, &result)); -- cgit v1.2.3 From e106e18d96595bdc4bc037e0b36900992a576160 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Tue, 21 Dec 2021 01:38:46 +0100 Subject: stage2: @shlWithOverflow --- src/Air.zig | 7 +++++++ src/Liveness.zig | 3 ++- src/Sema.zig | 47 +++++++++++++++++++++++++++++++++++-------- src/arch/aarch64/CodeGen.zig | 12 ++++++++--- src/arch/arm/CodeGen.zig | 12 ++++++++--- src/arch/riscv64/CodeGen.zig | 12 ++++++++--- src/arch/x86_64/CodeGen.zig | 12 ++++++++--- src/codegen/c.zig | 7 +++++++ src/codegen/llvm.zig | 36 +++++++++++++++++++++++++++++++++ src/print_air.zig | 1 + src/value.zig | 31 ++++++++++++++++++++++++++++ test/behavior/eval.zig | 16 +++++++++++++++ test/behavior/eval_stage1.zig | 16 --------------- test/behavior/math.zig | 28 ++++++++++++++++++++++++++ test/behavior/math_stage1.zig | 20 ------------------ 15 files changed, 203 insertions(+), 57 deletions(-) (limited to 'src/codegen') diff --git a/src/Air.zig b/src/Air.zig index 912e70daed..0d660ff6ae 100644 --- a/src/Air.zig +++ b/src/Air.zig @@ -153,6 +153,12 @@ pub const Inst = struct { /// of the operation. /// Uses the `pl_op` field with payload `Bin`. mul_with_overflow, + /// Integer left-shift with overflow. Both operands are guaranteed to be the same type, + /// and the result is bool. The wrapped value is written to the pointer given by the in + /// operand of the `pl_op` field. Payload is `Bin` with `lhs` and `rhs` the relevant types + /// of the operation. + /// Uses the `pl_op` field with payload `Bin`. + shl_with_overflow, /// Allocates stack local memory. /// Uses the `ty` field. alloc, @@ -830,6 +836,7 @@ pub fn typeOfIndex(air: Air, inst: Air.Inst.Index) Type { .add_with_overflow, .sub_with_overflow, .mul_with_overflow, + .shl_with_overflow, => return Type.initTag(.bool), } } diff --git a/src/Liveness.zig b/src/Liveness.zig index ad0ce7ffb9..a9f7fffca4 100644 --- a/src/Liveness.zig +++ b/src/Liveness.zig @@ -387,7 +387,8 @@ fn analyzeInst( .add_with_overflow, .sub_with_overflow, .mul_with_overflow, - => { + .shl_with_overflow, + => { const pl_op = inst_datas[inst].pl_op; const extra = a.air.extraData(Air.Bin, pl_op.payload).data; return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.lhs, extra.rhs }); diff --git a/src/Sema.zig b/src/Sema.zig index 2eb661503e..2ac4d327b1 100644 --- a/src/Sema.zig +++ b/src/Sema.zig @@ -7425,8 +7425,32 @@ fn zirOverflowArithmetic( } } }, - .shl_with_overflow, - => return sema.fail(block, src, "TODO implement Sema.zirOverflowArithmetic for {}", .{zir_tag}), + .shl_with_overflow => { + // If lhs is zero, the result is zero and no overflow occurred. + // If rhs is zero, the result is lhs (even if undefined) and no overflow occurred. + // Oterhwise if either of the arguments is undefined, both results are undefined. + if (maybe_lhs_val) |lhs_val| { + if (!lhs_val.isUndef() and lhs_val.compareWithZero(.eq)) { + break :result .{ .overflowed = .no, .wrapped = lhs }; + } + } + if (maybe_rhs_val) |rhs_val| { + if (!rhs_val.isUndef() and rhs_val.compareWithZero(.eq)) { + break :result .{ .overflowed = .no, .wrapped = lhs }; + } + } + if (maybe_lhs_val) |lhs_val| { + if (maybe_rhs_val) |rhs_val| { + if (lhs_val.isUndef() or rhs_val.isUndef()) { + break :result .{ .overflowed = .undef, .wrapped = try sema.addConstUndef(dest_ty) }; + } + + const result = try lhs_val.shlWithOverflow(rhs_val, dest_ty, sema.arena, target); + const inst = try sema.addConstant(dest_ty, result.wrapped_result); + break :result .{ .overflowed = if (result.overflowed) .yes else .no, .wrapped = inst }; + } + } + }, else => unreachable, } @@ -7434,7 +7458,8 @@ fn zirOverflowArithmetic( .add_with_overflow => .add_with_overflow, .mul_with_overflow => .mul_with_overflow, .sub_with_overflow => .sub_with_overflow, - else => return sema.fail(block, src, "TODO implement runtime Sema.zirOverflowArithmetic for {}", .{zir_tag}), + .shl_with_overflow => .shl_with_overflow, + else => unreachable, }; try sema.requireRuntimeBlock(block, src); @@ -9041,11 +9066,17 @@ fn log2IntType(sema: *Sema, block: *Block, operand: Type, src: LazySrcLoc) Compi switch (operand.zigTypeTag()) { .ComptimeInt => return Air.Inst.Ref.comptime_int_type, .Int => { - var count: u16 = 0; - var s = operand.bitSize(sema.mod.getTarget()) - 1; - while (s != 0) : (s >>= 1) { - count += 1; - } + const bits = operand.bitSize(sema.mod.getTarget()); + const count = if (bits == 0) + 0 + else blk: { + var count: u16 = 0; + var s = bits - 1; + while (s != 0) : (s >>= 1) { + count += 1; + } + break :blk count; + }; const res = try Module.makeIntType(sema.arena, .unsigned, count); return sema.addType(res); }, diff --git a/src/arch/aarch64/CodeGen.zig b/src/arch/aarch64/CodeGen.zig index b381116a51..0142e6abf8 100644 --- a/src/arch/aarch64/CodeGen.zig +++ b/src/arch/aarch64/CodeGen.zig @@ -524,6 +524,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .add_with_overflow => try self.airAddWithOverflow(inst), .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), + .shl_with_overflow => try self.airShlWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -975,17 +976,22 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airAddWithOverflow for {}", .{self.target.cpu.arch}); } fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airSubWithOverflow for {}", .{self.target.cpu.arch}); } fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airMulWithOverflow for {}", .{self.target.cpu.arch}); +} + +fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airShlWithOverflow for {}", .{self.target.cpu.arch}); } fn airDiv(self: *Self, inst: Air.Inst.Index) !void { diff --git a/src/arch/arm/CodeGen.zig b/src/arch/arm/CodeGen.zig index f887810d9a..9e43808d1f 100644 --- a/src/arch/arm/CodeGen.zig +++ b/src/arch/arm/CodeGen.zig @@ -522,6 +522,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .add_with_overflow => try self.airAddWithOverflow(inst), .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), + .shl_with_overflow => try self.airShlWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -1005,17 +1006,22 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airAddWithOverflow for {}", .{self.target.cpu.arch}); } fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airSubWithOverflow for {}", .{self.target.cpu.arch}); } fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airMulWithOverflow for {}", .{self.target.cpu.arch}); +} + +fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airShlWithOverflow for {}", .{self.target.cpu.arch}); } fn airDiv(self: *Self, inst: Air.Inst.Index) !void { diff --git a/src/arch/riscv64/CodeGen.zig b/src/arch/riscv64/CodeGen.zig index 56904206ab..3930e7364e 100644 --- a/src/arch/riscv64/CodeGen.zig +++ b/src/arch/riscv64/CodeGen.zig @@ -503,6 +503,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .add_with_overflow => try self.airAddWithOverflow(inst), .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), + .shl_with_overflow => try self.airShlWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -920,17 +921,22 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airAddWithOverflow for {}", .{self.target.cpu.arch}); } fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airSubWithOverflow for {}", .{self.target.cpu.arch}); } fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airMulWithOverflow for {}", .{self.target.cpu.arch}); +} + +fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airShlWithOverflow for {}", .{self.target.cpu.arch}); } fn airDiv(self: *Self, inst: Air.Inst.Index) !void { diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index be26372031..9629280583 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -556,6 +556,7 @@ fn genBody(self: *Self, body: []const Air.Inst.Index) InnerError!void { .add_with_overflow => try self.airAddWithOverflow(inst), .sub_with_overflow => try self.airSubWithOverflow(inst), .mul_with_overflow => try self.airMulWithOverflow(inst), + .shl_with_overflow => try self.airShlWithOverflow(inst), .div_float, .div_trunc, .div_floor, .div_exact => try self.airDiv(inst), @@ -1034,17 +1035,22 @@ fn airMulSat(self: *Self, inst: Air.Inst.Index) !void { fn airAddWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airAddResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airAddWithOverflow for {}", .{self.target.cpu.arch}); } fn airSubWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airSubResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airSubWithOverflow for {}", .{self.target.cpu.arch}); } fn airMulWithOverflow(self: *Self, inst: Air.Inst.Index) !void { _ = inst; - return self.fail("TODO implement airMulResultWithOverflow for {}", .{self.target.cpu.arch}); + return self.fail("TODO implement airMulWithOverflow for {}", .{self.target.cpu.arch}); +} + +fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void { + _ = inst; + return self.fail("TODO implement airShlWithOverflow for {}", .{self.target.cpu.arch}); } fn airDiv(self: *Self, inst: Air.Inst.Index) !void { diff --git a/src/codegen/c.zig b/src/codegen/c.zig index 68b700db17..12ce813a0f 100644 --- a/src/codegen/c.zig +++ b/src/codegen/c.zig @@ -1159,6 +1159,7 @@ fn genBody(f: *Function, body: []const Air.Inst.Index) error{ AnalysisFail, OutO .add_with_overflow => try airAddWithOverflow(f, inst), .sub_with_overflow => try airSubWithOverflow(f, inst), .mul_with_overflow => try airMulWithOverflow(f, inst), + .shl_with_overflow => try airShlWithOverflow(f, inst), .min => try airMinMax(f, inst, "<"), .max => try airMinMax(f, inst, ">"), @@ -1887,6 +1888,12 @@ fn airMulWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { return f.fail("TODO mul with overflow", .{}); } +fn airShlWithOverflow(f: *Function, inst: Air.Inst.Index) !CValue { + _ = f; + _ = inst; + return f.fail("TODO shl with overflow", .{}); +} + fn airNot(f: *Function, inst: Air.Inst.Index) !CValue { if (f.liveness.isUnused(inst)) return CValue.none; diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig index 4089a39cb3..78848bee28 100644 --- a/src/codegen/llvm.zig +++ b/src/codegen/llvm.zig @@ -1721,6 +1721,7 @@ pub const FuncGen = struct { .add_with_overflow => try self.airOverflow(inst, "llvm.sadd.with.overflow", "llvm.uadd.with.overflow"), .sub_with_overflow => try self.airOverflow(inst, "llvm.ssub.with.overflow", "llvm.usub.with.overflow"), .mul_with_overflow => try self.airOverflow(inst, "llvm.smul.with.overflow", "llvm.umul.with.overflow"), + .shl_with_overflow => try self.airShlWithOverflow(inst), .bit_and, .bool_and => try self.airAnd(inst), .bit_or, .bool_or => try self.airOr(inst), @@ -3176,6 +3177,41 @@ pub const FuncGen = struct { return overflow_bit; } + fn airShlWithOverflow(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { + if (self.liveness.isUnused(inst)) + return null; + + const pl_op = self.air.instructions.items(.data)[inst].pl_op; + const extra = self.air.extraData(Air.Bin, pl_op.payload).data; + + const ptr = try self.resolveInst(pl_op.operand); + const lhs = try self.resolveInst(extra.lhs); + const rhs = try self.resolveInst(extra.rhs); + + const ptr_ty = self.air.typeOf(pl_op.operand); + const lhs_ty = self.air.typeOf(extra.lhs); + const rhs_ty = self.air.typeOf(extra.rhs); + + const tg = self.dg.module.getTarget(); + + const casted_rhs = if (rhs_ty.bitSize(tg) < lhs_ty.bitSize(tg)) + self.builder.buildZExt(rhs, try self.dg.llvmType(lhs_ty), "") + else + rhs; + + const result = self.builder.buildShl(lhs, casted_rhs, ""); + const reconstructed = if (lhs_ty.isSignedInt()) + self.builder.buildAShr(result, casted_rhs, "") + else + self.builder.buildLShr(result, casted_rhs, ""); + + const overflow_bit = self.builder.buildICmp(.NE, lhs, reconstructed, ""); + + self.store(ptr, ptr_ty, result, .NotAtomic); + + return overflow_bit; + } + fn airAnd(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value { if (self.liveness.isUnused(inst)) return null; diff --git a/src/print_air.zig b/src/print_air.zig index d6bfaac4bc..b3a1be28f4 100644 --- a/src/print_air.zig +++ b/src/print_air.zig @@ -233,6 +233,7 @@ const Writer = struct { .add_with_overflow, .sub_with_overflow, .mul_with_overflow, + .shl_with_overflow, => try w.writeOverflow(s, inst), } } diff --git a/src/value.zig b/src/value.zig index 19546ed8b9..c105e3e742 100644 --- a/src/value.zig +++ b/src/value.zig @@ -2548,6 +2548,37 @@ pub const Value = extern union { return fromBigInt(allocator, result_bigint.toConst()); } + pub fn shlWithOverflow( + lhs: Value, + rhs: Value, + ty: Type, + allocator: Allocator, + target: Target, + ) !OverflowArithmeticResult { + const info = ty.intInfo(target); + var lhs_space: Value.BigIntSpace = undefined; + const lhs_bigint = lhs.toBigInt(&lhs_space); + const shift = @intCast(usize, rhs.toUnsignedInt()); + const limbs = try allocator.alloc( + std.math.big.Limb, + lhs_bigint.limbs.len + (shift / (@sizeOf(std.math.big.Limb) * 8)) + 1, + ); + var result_bigint = BigIntMutable{ + .limbs = limbs, + .positive = undefined, + .len = undefined, + }; + result_bigint.shiftLeft(lhs_bigint, shift); + const overflowed = !result_bigint.toConst().fitsInTwosComp(info.signedness, info.bits); + if (overflowed) { + result_bigint.truncate(result_bigint.toConst(), info.signedness, info.bits); + } + return OverflowArithmeticResult{ + .overflowed = overflowed, + .wrapped_result = try fromBigInt(allocator, result_bigint.toConst()), + }; + } + pub fn shlSat( lhs: Value, rhs: Value, diff --git a/test/behavior/eval.zig b/test/behavior/eval.zig index 84af3ecfbb..01d62f353f 100644 --- a/test/behavior/eval.zig +++ b/test/behavior/eval.zig @@ -451,3 +451,19 @@ test "comptime bitwise operators" { try expect(~@as(u128, 0) == 0xffffffffffffffffffffffffffffffff); } } + +test "comptime shlWithOverflow" { + const ct_shifted: u64 = comptime amt: { + var amt = @as(u64, 0); + _ = @shlWithOverflow(u64, ~@as(u64, 0), 16, &amt); + break :amt amt; + }; + + const rt_shifted: u64 = amt: { + var amt = @as(u64, 0); + _ = @shlWithOverflow(u64, ~@as(u64, 0), 16, &amt); + break :amt amt; + }; + + try expect(ct_shifted == rt_shifted); +} diff --git a/test/behavior/eval_stage1.zig b/test/behavior/eval_stage1.zig index 348c685a26..8f7e7dbe0d 100644 --- a/test/behavior/eval_stage1.zig +++ b/test/behavior/eval_stage1.zig @@ -162,22 +162,6 @@ test "const ptr to comptime mutable data is not memoized" { } } -test "comptime shlWithOverflow" { - const ct_shifted: u64 = comptime amt: { - var amt = @as(u64, 0); - _ = @shlWithOverflow(u64, ~@as(u64, 0), 16, &amt); - break :amt amt; - }; - - const rt_shifted: u64 = amt: { - var amt = @as(u64, 0); - _ = @shlWithOverflow(u64, ~@as(u64, 0), 16, &amt); - break :amt amt; - }; - - try expect(ct_shifted == rt_shifted); -} - test "runtime 128 bit integer division" { var a: u128 = 152313999999999991610955792383; var b: u128 = 10000000000000000000; diff --git a/test/behavior/math.zig b/test/behavior/math.zig index 50a7267c93..b3821f7732 100644 --- a/test/behavior/math.zig +++ b/test/behavior/math.zig @@ -511,3 +511,31 @@ test "@subWithOverflow" { try expect(!@subWithOverflow(u8, a, b, &result)); try expect(result == 0); } + +test "@shlWithOverflow" { + var result: u16 = undefined; + try expect(@shlWithOverflow(u16, 0b0010111111111111, 3, &result)); + try expect(result == 0b0111111111111000); + try expect(!@shlWithOverflow(u16, 0b0010111111111111, 2, &result)); + try expect(result == 0b1011111111111100); + + var a: u16 = 0b0000_0000_0000_0011; + var b: u4 = 15; + try expect(@shlWithOverflow(u16, a, b, &result)); + try expect(result == 0b1000_0000_0000_0000); + b = 14; + try expect(!@shlWithOverflow(u16, a, b, &result)); + try expect(result == 0b1100_0000_0000_0000); +} + +test "overflow arithmetic with u0 values" { + var result: u0 = undefined; + try expect(!@addWithOverflow(u0, 0, 0, &result)); + try expect(result == 0); + try expect(!@subWithOverflow(u0, 0, 0, &result)); + try expect(result == 0); + try expect(!@mulWithOverflow(u0, 0, 0, &result)); + try expect(result == 0); + try expect(!@shlWithOverflow(u0, 0, 0, &result)); + try expect(result == 0); +} diff --git a/test/behavior/math_stage1.zig b/test/behavior/math_stage1.zig index 139593b9f5..2633f23aac 100644 --- a/test/behavior/math_stage1.zig +++ b/test/behavior/math_stage1.zig @@ -6,26 +6,6 @@ const maxInt = std.math.maxInt; const minInt = std.math.minInt; const mem = std.mem; -test "@shlWithOverflow" { - var result: u16 = undefined; - try expect(@shlWithOverflow(u16, 0b0010111111111111, 3, &result)); - try expect(result == 0b0111111111111000); - try expect(!@shlWithOverflow(u16, 0b0010111111111111, 2, &result)); - try expect(result == 0b1011111111111100); -} - -test "overflow arithmetic with u0 values" { - var result: u0 = undefined; - try expect(!@addWithOverflow(u0, 0, 0, &result)); - try expect(result == 0); - try expect(!@subWithOverflow(u0, 0, 0, &result)); - try expect(result == 0); - try expect(!@mulWithOverflow(u0, 0, 0, &result)); - try expect(result == 0); - try expect(!@shlWithOverflow(u0, 0, 0, &result)); - try expect(result == 0); -} - test "@clz vectors" { try testClzVectors(); comptime try testClzVectors(); -- cgit v1.2.3