stage2: @shlWithOverflow

11 files changed, 159 insertions, 21 deletions

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,