stage2: @mulWithOverflow

11 files changed, 140 insertions, 29 deletions

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());