Merge pull request #10927 from ziglang/x64-idiv-imul

stage2,x64: implement integer division

3 files changed, 341 insertions, 24 deletions

diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig
index 441af51de2..d0085d687a 100644
--- a/src/arch/x86_64/CodeGen.zig
+++ b/src/arch/x86_64/CodeGen.zig
@@ -1252,30 +1252,244 @@ fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void {
     return self.fail("TODO implement airShlWithOverflow for {}", .{self.target.cpu.arch});
 }
 
+/// Generates signed or unsigned integer division.
+/// Requires use of .rax and .rdx registers. Spills them if necessary.
+/// Quotient is saved in .rax and remainder in .rdx.
+fn genIntDivOpMir(
+    self: *Self,
+    ty: Type,
+    signedness: std.builtin.Signedness,
+    lhs: MCValue,
+    rhs: MCValue,
+) !void {
+    const abi_size = @intCast(u32, ty.abiSize(self.target.*));
+    if (abi_size > 8) {
+        return self.fail("TODO implement genIntDivOpMir for ABI size larger than 8", .{});
+    }
+
+    try self.register_manager.getReg(.rax, null);
+    try self.register_manager.getReg(.rdx, null);
+    self.register_manager.freezeRegs(&.{ .rax, .rdx });
+    defer self.register_manager.unfreezeRegs(&.{ .rax, .rdx });
+
+    const dividend = switch (lhs) {
+        .register => lhs,
+        else => blk: {
+            const reg = try self.copyToTmpRegister(ty, lhs);
+            break :blk MCValue{ .register = reg };
+        },
+    };
+    try self.genSetReg(ty, .rax, dividend);
+
+    self.register_manager.freezeRegs(&.{dividend.register});
+    defer self.register_manager.unfreezeRegs(&.{dividend.register});
+
+    switch (signedness) {
+        .signed => {
+            _ = try self.addInst(.{
+                .tag = .cwd,
+                .ops = (Mir.Ops{
+                    .flags = 0b11,
+                }).encode(),
+                .data = undefined,
+            });
+        },
+        .unsigned => {
+            _ = try self.addInst(.{
+                .tag = .xor,
+                .ops = (Mir.Ops{
+                    .reg1 = .rdx,
+                    .reg2 = .rdx,
+                }).encode(),
+                .data = undefined,
+            });
+        },
+    }
+
+    const divisor = switch (rhs) {
+        .register => rhs,
+        else => blk: {
+            const reg = try self.copyToTmpRegister(ty, rhs);
+            break :blk MCValue{ .register = reg };
+        },
+    };
+    const op_tag: Mir.Inst.Tag = switch (signedness) {
+        .signed => .idiv,
+        .unsigned => .div,
+    };
+
+    switch (divisor) {
+        .register => |reg| {
+            _ = try self.addInst(.{
+                .tag = op_tag,
+                .ops = (Mir.Ops{
+                    .reg1 = reg,
+                }).encode(),
+                .data = undefined,
+            });
+        },
+        .stack_offset => |off| {
+            _ = try self.addInst(.{
+                .tag = op_tag,
+                .ops = (Mir.Ops{
+                    .reg2 = .rbp,
+                    .flags = switch (abi_size) {
+                        1 => 0b00,
+                        2 => 0b01,
+                        4 => 0b10,
+                        8 => 0b11,
+                        else => unreachable,
+                    },
+                }).encode(),
+                .data = .{ .imm = @bitCast(u32, -off) },
+            });
+        },
+        else => unreachable,
+    }
+}
+
+fn genInlineIntDivFloor(self: *Self, ty: Type, lhs: MCValue, rhs: MCValue) !MCValue {
+    const signedness = ty.intInfo(self.target.*).signedness;
+    const dividend = switch (lhs) {
+        .register => |reg| reg,
+        else => try self.copyToTmpRegister(ty, lhs),
+    };
+    self.register_manager.freezeRegs(&.{dividend});
+
+    const divisor = switch (rhs) {
+        .register => |reg| reg,
+        else => try self.copyToTmpRegister(ty, rhs),
+    };
+    self.register_manager.freezeRegs(&.{divisor});
+    defer self.register_manager.unfreezeRegs(&.{ dividend, divisor });
+
+    try self.genIntDivOpMir(Type.isize, signedness, .{ .register = dividend }, .{ .register = divisor });
+
+    _ = try self.addInst(.{
+        .tag = .xor,
+        .ops = (Mir.Ops{
+            .reg1 = divisor.to64(),
+            .reg2 = dividend.to64(),
+        }).encode(),
+        .data = undefined,
+    });
+    _ = try self.addInst(.{
+        .tag = .sar,
+        .ops = (Mir.Ops{
+            .reg1 = divisor.to64(),
+            .flags = 0b10,
+        }).encode(),
+        .data = .{ .imm = 63 },
+    });
+    _ = try self.addInst(.{
+        .tag = .@"test",
+        .ops = (Mir.Ops{
+            .reg1 = .rdx,
+            .reg2 = .rdx,
+        }).encode(),
+        .data = undefined,
+    });
+    _ = try self.addInst(.{
+        .tag = .cond_mov_eq,
+        .ops = (Mir.Ops{
+            .reg1 = divisor.to64(),
+            .reg2 = .rdx,
+        }).encode(),
+        .data = undefined,
+    });
+    try self.genBinMathOpMir(.add, Type.isize, .{ .register = divisor.to64() }, .{ .register = .rax });
+    return MCValue{ .register = divisor };
+}
+
 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});
+    const result: MCValue = if (self.liveness.isUnused(inst)) .dead else result: {
+        const tag = self.air.instructions.items(.tag)[inst];
+        const ty = self.air.typeOfIndex(inst);
+
+        if (ty.zigTypeTag() != .Int) {
+            return self.fail("TODO implement {} for operands of dst type {}", .{ tag, ty.zigTypeTag() });
+        }
+
+        if (tag == .div_float) {
+            return self.fail("TODO implement {}", .{tag});
+        }
+
+        // Spill .rax and .rdx upfront to ensure we don't spill the operands too late.
+        try self.register_manager.getReg(.rax, null);
+        try self.register_manager.getReg(.rdx, null);
+
+        const lhs = try self.resolveInst(bin_op.lhs);
+        const rhs = try self.resolveInst(bin_op.rhs);
+
+        const signedness = ty.intInfo(self.target.*).signedness;
+        if (signedness == .unsigned) {
+            try self.genIntDivOpMir(ty, signedness, lhs, rhs);
+            break :result MCValue{ .register = .rax };
+        }
+
+        switch (tag) {
+            .div_exact, .div_trunc => {
+                try self.genIntDivOpMir(ty, signedness, lhs, rhs);
+                break :result MCValue{ .register = .rax };
+            },
+            .div_floor => {
+                break :result try self.genInlineIntDivFloor(ty, lhs, rhs);
+            },
+            else => unreachable,
+        }
+    };
     return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none });
 }
 
 fn airRem(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 rem for {}", .{self.target.cpu.arch});
+    const result: MCValue = if (self.liveness.isUnused(inst)) .dead else result: {
+        const ty = self.air.typeOfIndex(inst);
+        if (ty.zigTypeTag() != .Int) {
+            return self.fail("TODO implement .rem for operands of dst type {}", .{ty.zigTypeTag()});
+        }
+        // Spill .rax and .rdx upfront to ensure we don't spill the operands too late.
+        try self.register_manager.getReg(.rax, null);
+        try self.register_manager.getReg(.rdx, null);
+        const lhs = try self.resolveInst(bin_op.lhs);
+        const rhs = try self.resolveInst(bin_op.rhs);
+        const signedness = ty.intInfo(self.target.*).signedness;
+        try self.genIntDivOpMir(ty, signedness, lhs, rhs);
+        break :result MCValue{ .register = .rdx };
+    };
     return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none });
 }
 
 fn airMod(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 mod for {}", .{self.target.cpu.arch});
+    const result: MCValue = if (self.liveness.isUnused(inst)) .dead else result: {
+        const ty = self.air.typeOfIndex(inst);
+        if (ty.zigTypeTag() != .Int) {
+            return self.fail("TODO implement .mod for operands of dst type {}", .{ty.zigTypeTag()});
+        }
+        // Spill .rax and .rdx upfront to ensure we don't spill the operands too late.
+        try self.register_manager.getReg(.rax, null);
+        try self.register_manager.getReg(.rdx, null);
+        const lhs = try self.resolveInst(bin_op.lhs);
+        const rhs = try self.resolveInst(bin_op.rhs);
+        const signedness = ty.intInfo(self.target.*).signedness;
+        switch (signedness) {
+            .unsigned => {
+                try self.genIntDivOpMir(ty, signedness, lhs, rhs);
+                break :result MCValue{ .register = .rdx };
+            },
+            .signed => {
+                const div_floor = try self.genInlineIntDivFloor(ty, lhs, rhs);
+                try self.genIMulOpMir(ty, div_floor, rhs);
+
+                const reg = try self.copyToTmpRegister(ty, lhs);
+                try self.genBinMathOpMir(.sub, ty, .{ .register = reg }, div_floor);
+
+                break :result MCValue{ .register = reg };
+            },
+        }
+    };
     return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none });
 }
 
@@ -4126,7 +4340,7 @@ fn genInlineMemset(
 }
 
 fn genSetReg(self: *Self, ty: Type, reg: Register, mcv: MCValue) InnerError!void {
-    const abi_size = ty.abiSize(self.target.*);
+    const abi_size = @intCast(u32, ty.abiSize(self.target.*));
     switch (mcv) {
         .dead => unreachable,
         .ptr_stack_offset => |off| {
@@ -4136,7 +4350,7 @@ fn genSetReg(self: *Self, ty: Type, reg: Register, mcv: MCValue) InnerError!void
             _ = try self.addInst(.{
                 .tag = .lea,
                 .ops = (Mir.Ops{
-                    .reg1 = registerAlias(reg, @intCast(u32, abi_size)),
+                    .reg1 = registerAlias(reg, abi_size),
                     .reg2 = .rbp,
                 }).encode(),
                 .data = .{ .imm = @bitCast(u32, -off) },
@@ -4202,7 +4416,7 @@ fn genSetReg(self: *Self, ty: Type, reg: Register, mcv: MCValue) InnerError!void
                 _ = try self.addInst(.{
                     .tag = .mov,
                     .ops = (Mir.Ops{
-                        .reg1 = registerAlias(reg, @intCast(u32, abi_size)),
+                        .reg1 = registerAlias(reg, abi_size),
                     }).encode(),
                     .data = .{ .imm = @truncate(u32, x) },
                 });
@@ -4249,7 +4463,7 @@ fn genSetReg(self: *Self, ty: Type, reg: Register, mcv: MCValue) InnerError!void
                             .tag = .mov_sign_extend,
                             .ops = (Mir.Ops{
                                 .reg1 = reg.to64(),
-                                .reg2 = src_reg,
+                                .reg2 = registerAlias(src_reg, abi_size),
                             }).encode(),
                             .data = undefined,
                         });
@@ -4260,7 +4474,7 @@ fn genSetReg(self: *Self, ty: Type, reg: Register, mcv: MCValue) InnerError!void
                             .tag = .mov_zero_extend,
                             .ops = (Mir.Ops{
                                 .reg1 = reg.to64(),
-                                .reg2 = src_reg,
+                                .reg2 = registerAlias(src_reg, abi_size),
                             }).encode(),
                             .data = undefined,
                         });
@@ -4272,8 +4486,8 @@ fn genSetReg(self: *Self, ty: Type, reg: Register, mcv: MCValue) InnerError!void
             _ = try self.addInst(.{
                 .tag = .mov,
                 .ops = (Mir.Ops{
-                    .reg1 = registerAlias(reg, @divExact(src_reg.size(), 8)),
-                    .reg2 = src_reg,
+                    .reg1 = registerAlias(reg, abi_size),
+                    .reg2 = registerAlias(src_reg, abi_size),
                 }).encode(),
                 .data = undefined,
             });
@@ -4399,7 +4613,7 @@ fn genSetReg(self: *Self, ty: Type, reg: Register, mcv: MCValue) InnerError!void
             _ = try self.addInst(.{
                 .tag = .mov,
                 .ops = (Mir.Ops{
-                    .reg1 = registerAlias(reg, @intCast(u32, abi_size)),
+                    .reg1 = registerAlias(reg, abi_size),
                     .reg2 = .rbp,
                     .flags = 0b01,
                 }).encode(),
diff --git a/src/arch/x86_64/Emit.zig b/src/arch/x86_64/Emit.zig
index 5d15b28ee8..7e2a4272dc 100644
--- a/src/arch/x86_64/Emit.zig
+++ b/src/arch/x86_64/Emit.zig
@@ -138,8 +138,13 @@ pub fn lowerMir(emit: *Emit) InnerError!void {
             .shr => try emit.mirShift(.shr, inst),
             .sar => try emit.mirShift(.sar, inst),
 
+            .imul => try emit.mirMulDiv(.imul, inst),
+            .idiv => try emit.mirMulDiv(.idiv, inst),
+            .div => try emit.mirMulDiv(.div, inst),
             .imul_complex => try emit.mirIMulComplex(inst),
 
+            .cwd => try emit.mirCwd(inst),
+
             .push => try emit.mirPushPop(.push, inst),
             .pop => try emit.mirPushPop(.pop, inst),
 
@@ -156,6 +161,8 @@ pub fn lowerMir(emit: *Emit) InnerError!void {
             .cond_set_byte_eq_ne,
             => try emit.mirCondSetByte(tag, inst),
 
+            .cond_mov_eq => try emit.mirCondMov(.cmove, inst),
+
             .ret => try emit.mirRet(inst),
 
             .syscall => try emit.mirSyscall(),
@@ -368,6 +375,24 @@ fn mirCondSetByte(emit: *Emit, mir_tag: Mir.Inst.Tag, inst: Mir.Inst.Index) Inne
     return lowerToMEnc(tag, RegisterOrMemory.reg(ops.reg1.to8()), emit.code);
 }
 
+fn mirCondMov(emit: *Emit, tag: Tag, inst: Mir.Inst.Index) InnerError!void {
+    const ops = Mir.Ops.decode(emit.mir.instructions.items(.ops)[inst]);
+    if (ops.flags == 0b00) {
+        return lowerToRmEnc(tag, ops.reg1, RegisterOrMemory.reg(ops.reg2), emit.code);
+    }
+    const imm = emit.mir.instructions.items(.data)[inst].imm;
+    const ptr_size: Memory.PtrSize = switch (ops.flags) {
+        0b00 => unreachable,
+        0b01 => .word_ptr,
+        0b10 => .dword_ptr,
+        0b11 => .qword_ptr,
+    };
+    return lowerToRmEnc(tag, ops.reg1, RegisterOrMemory.mem(ptr_size, .{
+        .disp = imm,
+        .base = ops.reg2,
+    }), emit.code);
+}
+
 fn mirTest(emit: *Emit, inst: Mir.Inst.Index) InnerError!void {
     const tag = emit.mir.instructions.items(.tag)[inst];
     assert(tag == .@"test");
@@ -386,7 +411,7 @@ fn mirTest(emit: *Emit, inst: Mir.Inst.Index) InnerError!void {
                 return lowerToMiEnc(.@"test", RegisterOrMemory.reg(ops.reg1), imm, emit.code);
             }
             // TEST r/m64, r64
-            return emit.fail("TODO TEST r/m64, r64", .{});
+            return lowerToMrEnc(.@"test", RegisterOrMemory.reg(ops.reg1), ops.reg2, emit.code);
         },
         else => return emit.fail("TODO more TEST alternatives", .{}),
     }
@@ -683,6 +708,27 @@ fn mirShift(emit: *Emit, tag: Tag, inst: Mir.Inst.Index) InnerError!void {
     }
 }
 
+fn mirMulDiv(emit: *Emit, tag: Tag, inst: Mir.Inst.Index) InnerError!void {
+    const ops = Mir.Ops.decode(emit.mir.instructions.items(.ops)[inst]);
+    if (ops.reg1 != .none) {
+        assert(ops.reg2 == .none);
+        return lowerToMEnc(tag, RegisterOrMemory.reg(ops.reg1), emit.code);
+    }
+    assert(ops.reg1 == .none);
+    assert(ops.reg2 != .none);
+    const imm = emit.mir.instructions.items(.data)[inst].imm;
+    const ptr_size: Memory.PtrSize = switch (ops.flags) {
+        0b00 => .byte_ptr,
+        0b01 => .word_ptr,
+        0b10 => .dword_ptr,
+        0b11 => .qword_ptr,
+    };
+    return lowerToMEnc(tag, RegisterOrMemory.mem(ptr_size, .{
+        .disp = imm,
+        .base = ops.reg2,
+    }), emit.code);
+}
+
 fn mirIMulComplex(emit: *Emit, inst: Mir.Inst.Index) InnerError!void {
     const tag = emit.mir.instructions.items(.tag)[inst];
     assert(tag == .imul_complex);
@@ -714,6 +760,17 @@ fn mirIMulComplex(emit: *Emit, inst: Mir.Inst.Index) InnerError!void {
     }
 }
 
+fn mirCwd(emit: *Emit, inst: Mir.Inst.Index) InnerError!void {
+    const ops = Mir.Ops.decode(emit.mir.instructions.items(.ops)[inst]);
+    const tag: Tag = switch (ops.flags) {
+        0b00 => .cbw,
+        0b01 => .cwd,
+        0b10 => .cdq,
+        0b11 => .cqo,
+    };
+    return lowerToZoEnc(tag, emit.code);
+}
+
 fn mirLea(emit: *Emit, inst: Mir.Inst.Index) InnerError!void {
     const tag = emit.mir.instructions.items(.tag)[inst];
     assert(tag == .lea);
@@ -1048,6 +1105,8 @@ const Tag = enum {
     brk,
     nop,
     imul,
+    idiv,
+    div,
     syscall,
     ret_near,
     ret_far,
@@ -1115,6 +1174,12 @@ const Tag = enum {
     sal,
     shr,
     sar,
+    cbw,
+    cwd,
+    cdq,
+    cqo,
+    cmove,
+    cmovz,
 
     fn isSetCC(tag: Tag) bool {
         return switch (tag) {
@@ -1234,6 +1299,8 @@ inline fn getOpCode(tag: Tag, enc: Encoding, is_one_byte: bool) ?OpCode {
             .brk => OpCode.oneByte(0xcc),
             .nop => OpCode.oneByte(0x90),
             .syscall => OpCode.twoByte(0x0f, 0x05),
+            .cbw => OpCode.oneByte(0x98),
+            .cwd, .cdq, .cqo => OpCode.oneByte(0x99),
             else => null,
         },
         .d => return switch (tag) {
@@ -1276,6 +1343,7 @@ inline fn getOpCode(tag: Tag, enc: Encoding, is_one_byte: bool) ?OpCode {
             .setnl, .setge => OpCode.twoByte(0x0f, 0x9d),
             .setle, .setng => OpCode.twoByte(0x0f, 0x9e),
             .setnle, .setg => OpCode.twoByte(0x0f, 0x9f),
+            .idiv, .div, .imul => OpCode.oneByte(if (is_one_byte) 0xf6 else 0xf7),
             else => null,
         },
         .o => return switch (tag) {
@@ -1319,6 +1387,7 @@ inline fn getOpCode(tag: Tag, enc: Encoding, is_one_byte: bool) ?OpCode {
             .sbb => OpCode.oneByte(if (is_one_byte) 0x18 else 0x19),
             .cmp => OpCode.oneByte(if (is_one_byte) 0x38 else 0x39),
             .mov => OpCode.oneByte(if (is_one_byte) 0x88 else 0x89),
+            .@"test" => OpCode.oneByte(if (is_one_byte) 0x84 else 0x85),
             else => null,
         },
         .rm => return switch (tag) {
@@ -1336,6 +1405,7 @@ inline fn getOpCode(tag: Tag, enc: Encoding, is_one_byte: bool) ?OpCode {
             .movzx => OpCode.twoByte(0x0f, if (is_one_byte) 0xb6 else 0xb7),
             .lea => OpCode.oneByte(if (is_one_byte) 0x8c else 0x8d),
             .imul => OpCode.twoByte(0x0f, 0xaf),
+            .cmove, .cmovz => OpCode.twoByte(0x0f, 0x44),
             else => null,
         },
         .oi => return switch (tag) {
@@ -1409,6 +1479,9 @@ inline fn getModRmExt(tag: Tag) ?u3 {
         => 0x4,
         .shr => 0x5,
         .sar => 0x7,
+        .imul => 0x5,
+        .idiv => 0x7,
+        .div => 0x6,
         else => null,
     };
 }
@@ -1565,7 +1638,15 @@ const RegisterOrMemory = union(enum) {
 
 fn lowerToZoEnc(tag: Tag, code: *std.ArrayList(u8)) InnerError!void {
     const opc = getOpCode(tag, .zo, false).?;
-    const encoder = try Encoder.init(code, 1);
+    const encoder = try Encoder.init(code, 2);
+    switch (tag) {
+        .cqo => {
+            encoder.rex(.{
+                .w = true,
+            });
+        },
+        else => {},
+    }
     opc.encode(encoder);
 }
 
@@ -2204,6 +2285,10 @@ test "lower M encoding" {
     try expectEqualHexStrings("\xFF\x24\x25\x10\x00\x00\x00", emit.lowered(), "jmp qword ptr [ds:0x10]");
     try lowerToMEnc(.seta, RegisterOrMemory.reg(.r11b), emit.code());
     try expectEqualHexStrings("\x41\x0F\x97\xC3", emit.lowered(), "seta r11b");
+    try lowerToMEnc(.idiv, RegisterOrMemory.reg(.rax), emit.code());
+    try expectEqualHexStrings("\x48\xF7\xF8", emit.lowered(), "idiv rax");
+    try lowerToMEnc(.imul, RegisterOrMemory.reg(.al), emit.code());
+    try expectEqualHexStrings("\xF6\xE8", emit.lowered(), "imul al");
 }
 
 test "lower M1 and MC encodings" {
diff --git a/src/arch/x86_64/Mir.zig b/src/arch/x86_64/Mir.zig
index 83922d03a2..8055498439 100644
--- a/src/arch/x86_64/Mir.zig
+++ b/src/arch/x86_64/Mir.zig
@@ -220,10 +220,21 @@ pub const Inst = struct {
         sar_mem_index_imm,
 
         /// ops flags: form:
-        ///      0bX0  reg1
-        ///      0bX1  [reg1 + imm32]
+        ///      0b00  reg1
+        ///      0b00  byte ptr [reg2 + imm32]
+        ///      0b01  word ptr [reg2 + imm32]
+        ///      0b10  dword ptr [reg2 + imm32]
+        ///      0b11  qword ptr [reg2 + imm32]
         imul,
         idiv,
+        div,
+
+        /// ops flags: form:
+        ///      0b00  AX      <- AL
+        ///      0b01  DX:AX   <- AX
+        ///      0b10  EDX:EAX <- EAX
+        ///      0b11  RDX:RAX <- RAX
+        cwd,
 
         /// ops flags:  form:
         ///      0b00  reg1, reg2
@@ -275,6 +286,13 @@ pub const Inst = struct {
         cond_jmp_eq_ne,
         cond_set_byte_eq_ne,
 
+        /// ops flags:
+        ///     0b00 reg1, reg2,
+        ///     0b01 reg1, word ptr  [reg2 + imm]
+        ///     0b10 reg1, dword ptr [reg2 + imm]
+        ///     0b11 reg1, qword ptr [reg2 + imm]
+        cond_mov_eq,
+
         /// ops flags:  form:
         ///       0b00   reg1
         ///       0b01   [reg1 + imm32]