Commit c47ed0c912
Changed files (13)
src
arch
test
behavior
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});
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});
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});
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))
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;
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);
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),
}
}
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 });
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;
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);
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());
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);
+}
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));