Commit e106e18d96
Changed files (15)
src
arch
test
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 {
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 {
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 {
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 {
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;
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;
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),
}
}
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 });
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),
}
}
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);
},
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,
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);
+}
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;
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);
+}
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();