stage2: @addWithOverflow

11 files changed, 245 insertions, 34 deletions

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.