From 1f4aa5ef78f4b516530f26aaeedf3794a0a9f585 Mon Sep 17 00:00:00 2001 From: Jakub Konka Date: Thu, 17 Feb 2022 18:55:25 +0100 Subject: x64: add lowering for single operand imul and idiv --- src/arch/x86_64/Emit.zig | 31 +++++++++++++++++++++++++++++++ src/arch/x86_64/Mir.zig | 7 +++++-- 2 files changed, 36 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/arch/x86_64/Emit.zig b/src/arch/x86_64/Emit.zig index 5d15b28ee8..9088a395a7 100644 --- a/src/arch/x86_64/Emit.zig +++ b/src/arch/x86_64/Emit.zig @@ -138,6 +138,8 @@ pub fn lowerMir(emit: *Emit) InnerError!void { .shr => try emit.mirShift(.shr, inst), .sar => try emit.mirShift(.sar, inst), + .imul => try emit.mirIMulIDiv(.imul, inst), + .idiv => try emit.mirIMulIDiv(.idiv, inst), .imul_complex => try emit.mirIMulComplex(inst), .push => try emit.mirPushPop(.push, inst), @@ -683,6 +685,27 @@ fn mirShift(emit: *Emit, tag: Tag, inst: Mir.Inst.Index) InnerError!void { } } +fn mirIMulIDiv(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); @@ -1048,6 +1071,7 @@ const Tag = enum { brk, nop, imul, + idiv, syscall, ret_near, ret_far, @@ -1276,6 +1300,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, .imul => OpCode.oneByte(if (is_one_byte) 0xf6 else 0xf7), else => null, }, .o => return switch (tag) { @@ -1409,6 +1434,8 @@ inline fn getModRmExt(tag: Tag) ?u3 { => 0x4, .shr => 0x5, .sar => 0x7, + .imul => 0x5, + .idiv => 0x7, else => null, }; } @@ -2204,6 +2231,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..83afc1612b 100644 --- a/src/arch/x86_64/Mir.zig +++ b/src/arch/x86_64/Mir.zig @@ -220,8 +220,11 @@ 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, -- cgit v1.2.3 From 2c13a4b87e1d9ae5c5c1117bc03b5fb67825ca34 Mon Sep 17 00:00:00 2001 From: Jakub Konka Date: Fri, 18 Feb 2022 01:12:19 +0100 Subject: x64: implement div_exact for ints (signed+unsigned) --- src/arch/x86_64/CodeGen.zig | 102 +++++++++++++++++++++++++++++++++++++++----- src/arch/x86_64/Emit.zig | 29 ++++++++++++- src/arch/x86_64/Mir.zig | 7 +++ 3 files changed, 127 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index 441af51de2..0846d0b45e 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -1254,10 +1254,92 @@ fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void { 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 dst_ty = self.air.typeOfIndex(inst); + const tag = self.air.instructions.items(.tag)[inst]; + switch (tag) { + .div_exact => {}, + .div_trunc, .div_floor, .div_float => return self.fail("TODO implement {}", .{tag}), + else => unreachable, + } + + if (dst_ty.zigTypeTag() != .Int) { + return self.fail("TODO implement {} for operands of type {}", .{ tag, dst_ty.zigTypeTag() }); + } + + const signedness = dst_ty.intInfo(self.target.*).signedness; + const ty = if (signedness == .signed) Type.isize else dst_ty; + const abi_size = @intCast(u32, ty.abiSize(self.target.*)); + + const lhs = try self.resolveInst(bin_op.lhs); + blk: { + switch (lhs) { + .register => |reg| { + if (reg.to64() == .rax) break :blk; + }, + else => {}, + } + try self.register_manager.getReg(.rax, inst); // track inst -> rax in register manager + try self.genSetReg(ty, .rax, lhs); + } + if (signedness == .signed) { + _ = try self.addInst(.{ + .tag = .cwd, + .ops = (Mir.Ops{ + .flags = 0b11, + }).encode(), + .data = undefined, + }); + } + const dst_mcv = MCValue{ .register = registerAlias(.rax, abi_size) }; + + try self.register_manager.getReg(.rdx, null); + self.register_manager.freezeRegs(&.{ .rax, .rdx }); + defer self.register_manager.unfreezeRegs(&.{ .rax, .rdx }); + + const rhs = try self.resolveInst(bin_op.rhs); + const divisor = blk: { + switch (rhs) { + .register, .stack_offset => break :blk rhs, + else => { + const reg = try self.copyToTmpRegister(ty, rhs); + break :blk MCValue{ .register = reg }; + }, + } + }; + + switch (divisor) { + .register => |reg| { + _ = try self.addInst(.{ + .tag = .idiv, + .ops = (Mir.Ops{ + .reg1 = registerAlias(reg, abi_size), + }).encode(), + .data = undefined, + }); + }, + .stack_offset => |off| { + const flags: u2 = switch (abi_size) { + 1 => 0b00, + 2 => 0b01, + 4 => 0b10, + 8 => 0b11, + else => unreachable, + }; + _ = try self.addInst(.{ + .tag = .idiv, + .ops = (Mir.Ops{ + .reg2 = .rbp, + .flags = flags, + }).encode(), + .data = .{ .imm = @bitCast(u32, -off) }, + }); + }, + else => unreachable, + } + + break :result dst_mcv; + }; return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } @@ -4126,7 +4208,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 +4218,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 +4284,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) }, }); @@ -4272,8 +4354,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 +4481,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 9088a395a7..e2de913c18 100644 --- a/src/arch/x86_64/Emit.zig +++ b/src/arch/x86_64/Emit.zig @@ -142,6 +142,8 @@ pub fn lowerMir(emit: *Emit) InnerError!void { .idiv => try emit.mirIMulIDiv(.idiv, inst), .imul_complex => try emit.mirIMulComplex(inst), + .cwd => try emit.mirCwd(inst), + .push => try emit.mirPushPop(.push, inst), .pop => try emit.mirPushPop(.pop, inst), @@ -737,6 +739,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); @@ -1139,6 +1152,10 @@ const Tag = enum { sal, shr, sar, + cbw, + cwd, + cdq, + cqo, fn isSetCC(tag: Tag) bool { return switch (tag) { @@ -1258,6 +1275,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) { @@ -1592,7 +1611,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); } diff --git a/src/arch/x86_64/Mir.zig b/src/arch/x86_64/Mir.zig index 83afc1612b..17d0503bda 100644 --- a/src/arch/x86_64/Mir.zig +++ b/src/arch/x86_64/Mir.zig @@ -228,6 +228,13 @@ pub const Inst = struct { imul, idiv, + /// 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 /// 0b01 reg1, [reg2 + imm32] -- cgit v1.2.3 From bd396d7e076c09d162f679c7d26ba883dbe5d7cf Mon Sep 17 00:00:00 2001 From: Jakub Konka Date: Fri, 18 Feb 2022 17:36:03 +0100 Subject: x64: add unsigned div and move logic into a helper fn --- src/arch/x86_64/CodeGen.zig | 185 ++++++++++++++++++++++++++------------------ src/arch/x86_64/Emit.zig | 11 ++- src/arch/x86_64/Mir.zig | 1 + 3 files changed, 119 insertions(+), 78 deletions(-) (limited to 'src') diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index 0846d0b45e..db36d9b264 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -1252,37 +1252,54 @@ fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airShlWithOverflow 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 result: { - const dst_ty = self.air.typeOfIndex(inst); - const tag = self.air.instructions.items(.tag)[inst]; - switch (tag) { - .div_exact => {}, - .div_trunc, .div_floor, .div_float => return self.fail("TODO implement {}", .{tag}), - else => unreachable, - } +/// Perform signed and unsigned integer division. +/// TODO it might be wise to split some functionality into integer and floating-point +/// specialised functions. +/// Supports AIR tag: +/// .div_exact, .div_trunc, .div_floor, .mod, .rem +fn genDivOp(self: *Self, inst: Air.Inst.Index, op_lhs: Air.Inst.Ref, op_rhs: Air.Inst.Ref) !MCValue { + const dst_ty = self.air.typeOfIndex(inst); + const tag = self.air.instructions.items(.tag)[inst]; - if (dst_ty.zigTypeTag() != .Int) { - return self.fail("TODO implement {} for operands of type {}", .{ tag, dst_ty.zigTypeTag() }); - } + switch (tag) { + .div_exact, .div_trunc, .div_floor, .mod, .rem => {}, + .div_float => return self.fail("TODO implement genDivOp for {}", .{tag}), + else => unreachable, + } + + if (dst_ty.zigTypeTag() != .Int) { + return self.fail("TODO implement {} for operands of type {}", .{ tag, dst_ty.zigTypeTag() }); + } + if (dst_ty.abiSize(self.target.*) > 8) { + return self.fail("TODO implement {} for ABI size larger than 8", .{tag}); + } - const signedness = dst_ty.intInfo(self.target.*).signedness; - const ty = if (signedness == .signed) Type.isize else dst_ty; - const abi_size = @intCast(u32, ty.abiSize(self.target.*)); + const signedness = dst_ty.intInfo(self.target.*).signedness; + const tmp_ty = switch (signedness) { + .signed => Type.isize, + .unsigned => dst_ty, + }; + const abi_size = @intCast(u32, tmp_ty.abiSize(self.target.*)); - const lhs = try self.resolveInst(bin_op.lhs); - blk: { - switch (lhs) { - .register => |reg| { - if (reg.to64() == .rax) break :blk; - }, - else => {}, - } - try self.register_manager.getReg(.rax, inst); // track inst -> rax in register manager - try self.genSetReg(ty, .rax, lhs); + const lhs = try self.resolveInst(op_lhs); + blk: { + switch (lhs) { + .register => |reg| { + if (reg.to64() == .rax) break :blk; + }, + else => {}, } - if (signedness == .signed) { + try self.register_manager.getReg(.rax, inst); // track inst -> rax in register manager + try self.genSetReg(tmp_ty, .rax, lhs); + } + + try self.register_manager.getReg(.rdx, null); + self.register_manager.freezeRegs(&.{ .rax, .rdx }); + defer self.register_manager.unfreezeRegs(&.{ .rax, .rdx }); + + // Prep rdx for the op + switch (signedness) { + .signed => { _ = try self.addInst(.{ .tag = .cwd, .ops = (Mir.Ops{ @@ -1290,56 +1307,76 @@ fn airDiv(self: *Self, inst: Air.Inst.Index) !void { }).encode(), .data = undefined, }); - } - const dst_mcv = MCValue{ .register = registerAlias(.rax, abi_size) }; - - try self.register_manager.getReg(.rdx, null); - self.register_manager.freezeRegs(&.{ .rax, .rdx }); - defer self.register_manager.unfreezeRegs(&.{ .rax, .rdx }); - - const rhs = try self.resolveInst(bin_op.rhs); - const divisor = blk: { - switch (rhs) { - .register, .stack_offset => break :blk rhs, - else => { - const reg = try self.copyToTmpRegister(ty, rhs); - break :blk MCValue{ .register = reg }; - }, - } - }; + }, + .unsigned => { + _ = try self.addInst(.{ + .tag = .xor, + .ops = (Mir.Ops{ + .reg1 = .rdx, + .reg2 = .rdx, + }).encode(), + .data = undefined, + }); + }, + } - switch (divisor) { - .register => |reg| { - _ = try self.addInst(.{ - .tag = .idiv, - .ops = (Mir.Ops{ - .reg1 = registerAlias(reg, abi_size), - }).encode(), - .data = undefined, - }); - }, - .stack_offset => |off| { - const flags: u2 = switch (abi_size) { - 1 => 0b00, - 2 => 0b01, - 4 => 0b10, - 8 => 0b11, - else => unreachable, - }; - _ = try self.addInst(.{ - .tag = .idiv, - .ops = (Mir.Ops{ - .reg2 = .rbp, - .flags = flags, - }).encode(), - .data = .{ .imm = @bitCast(u32, -off) }, - }); + const rhs = try self.resolveInst(op_rhs); + const divisor = blk: { + switch (rhs) { + .register, .stack_offset => break :blk rhs, + else => { + const reg = try self.copyToTmpRegister(tmp_ty, rhs); + break :blk MCValue{ .register = reg }; }, - else => unreachable, } + }; + const op_tag: Mir.Inst.Tag = switch (signedness) { + .signed => .idiv, + .unsigned => .div, + }; - break :result dst_mcv; + switch (divisor) { + .register => |reg| { + _ = try self.addInst(.{ + .tag = op_tag, + .ops = (Mir.Ops{ + .reg1 = registerAlias(reg, abi_size), + }).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, + } + + return switch (tag) { + .mod, .div_exact, .div_trunc, .div_floor => MCValue{ .register = .rax }, + .rem => MCValue{ .register = .rdx }, + else => unreachable, }; +} + +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 + try self.genDivOp(inst, bin_op.lhs, bin_op.rhs); return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } @@ -1348,7 +1385,7 @@ fn airRem(self: *Self, inst: Air.Inst.Index) !void { const result: MCValue = if (self.liveness.isUnused(inst)) .dead else - return self.fail("TODO implement rem for {}", .{self.target.cpu.arch}); + try self.genDivOp(inst, bin_op.lhs, bin_op.rhs); return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } @@ -1357,7 +1394,7 @@ fn airMod(self: *Self, inst: Air.Inst.Index) !void { const result: MCValue = if (self.liveness.isUnused(inst)) .dead else - return self.fail("TODO implement mod for {}", .{self.target.cpu.arch}); + try self.genDivOp(inst, bin_op.lhs, bin_op.rhs); return self.finishAir(inst, result, .{ bin_op.lhs, bin_op.rhs, .none }); } diff --git a/src/arch/x86_64/Emit.zig b/src/arch/x86_64/Emit.zig index e2de913c18..bfef415ad2 100644 --- a/src/arch/x86_64/Emit.zig +++ b/src/arch/x86_64/Emit.zig @@ -138,8 +138,9 @@ pub fn lowerMir(emit: *Emit) InnerError!void { .shr => try emit.mirShift(.shr, inst), .sar => try emit.mirShift(.sar, inst), - .imul => try emit.mirIMulIDiv(.imul, inst), - .idiv => try emit.mirIMulIDiv(.idiv, 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), @@ -687,7 +688,7 @@ fn mirShift(emit: *Emit, tag: Tag, inst: Mir.Inst.Index) InnerError!void { } } -fn mirIMulIDiv(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); @@ -1085,6 +1086,7 @@ const Tag = enum { nop, imul, idiv, + div, syscall, ret_near, ret_far, @@ -1319,7 +1321,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, .imul => OpCode.oneByte(if (is_one_byte) 0xf6 else 0xf7), + .idiv, .div, .imul => OpCode.oneByte(if (is_one_byte) 0xf6 else 0xf7), else => null, }, .o => return switch (tag) { @@ -1455,6 +1457,7 @@ inline fn getModRmExt(tag: Tag) ?u3 { .sar => 0x7, .imul => 0x5, .idiv => 0x7, + .div => 0x6, else => null, }; } diff --git a/src/arch/x86_64/Mir.zig b/src/arch/x86_64/Mir.zig index 17d0503bda..490c69a38c 100644 --- a/src/arch/x86_64/Mir.zig +++ b/src/arch/x86_64/Mir.zig @@ -227,6 +227,7 @@ pub const Inst = struct { /// 0b11 qword ptr [reg2 + imm32] imul, idiv, + div, /// ops flags: form: /// 0b00 AX <- AL -- cgit v1.2.3 From da86839af085bb5921d7f0112fda5ad9536dda10 Mon Sep 17 00:00:00 2001 From: Jakub Konka Date: Fri, 18 Feb 2022 18:23:50 +0100 Subject: x64: clean up implementation of divs, mod, rem for integers --- src/arch/x86_64/CodeGen.zig | 231 +++++++++++++++++++++++++++++++------------- src/arch/x86_64/Emit.zig | 26 ++++- src/arch/x86_64/Mir.zig | 7 ++ 3 files changed, 195 insertions(+), 69 deletions(-) (limited to 'src') diff --git a/src/arch/x86_64/CodeGen.zig b/src/arch/x86_64/CodeGen.zig index db36d9b264..d0085d687a 100644 --- a/src/arch/x86_64/CodeGen.zig +++ b/src/arch/x86_64/CodeGen.zig @@ -1252,52 +1252,38 @@ fn airShlWithOverflow(self: *Self, inst: Air.Inst.Index) !void { return self.fail("TODO implement airShlWithOverflow for {}", .{self.target.cpu.arch}); } -/// Perform signed and unsigned integer division. -/// TODO it might be wise to split some functionality into integer and floating-point -/// specialised functions. -/// Supports AIR tag: -/// .div_exact, .div_trunc, .div_floor, .mod, .rem -fn genDivOp(self: *Self, inst: Air.Inst.Index, op_lhs: Air.Inst.Ref, op_rhs: Air.Inst.Ref) !MCValue { - const dst_ty = self.air.typeOfIndex(inst); - const tag = self.air.instructions.items(.tag)[inst]; - - switch (tag) { - .div_exact, .div_trunc, .div_floor, .mod, .rem => {}, - .div_float => return self.fail("TODO implement genDivOp for {}", .{tag}), - else => unreachable, - } - - if (dst_ty.zigTypeTag() != .Int) { - return self.fail("TODO implement {} for operands of type {}", .{ tag, dst_ty.zigTypeTag() }); - } - if (dst_ty.abiSize(self.target.*) > 8) { - return self.fail("TODO implement {} for ABI size larger than 8", .{tag}); - } - - const signedness = dst_ty.intInfo(self.target.*).signedness; - const tmp_ty = switch (signedness) { - .signed => Type.isize, - .unsigned => dst_ty, - }; - const abi_size = @intCast(u32, tmp_ty.abiSize(self.target.*)); - - const lhs = try self.resolveInst(op_lhs); - blk: { - switch (lhs) { - .register => |reg| { - if (reg.to64() == .rax) break :blk; - }, - else => {}, - } - try self.register_manager.getReg(.rax, inst); // track inst -> rax in register manager - try self.genSetReg(tmp_ty, .rax, lhs); +/// 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 }); - // Prep rdx for the op + 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(.{ @@ -1320,15 +1306,12 @@ fn genDivOp(self: *Self, inst: Air.Inst.Index, op_lhs: Air.Inst.Ref, op_rhs: Air }, } - const rhs = try self.resolveInst(op_rhs); - const divisor = blk: { - switch (rhs) { - .register, .stack_offset => break :blk rhs, - else => { - const reg = try self.copyToTmpRegister(tmp_ty, rhs); - break :blk MCValue{ .register = reg }; - }, - } + 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, @@ -1340,7 +1323,7 @@ fn genDivOp(self: *Self, inst: Air.Inst.Index, op_lhs: Air.Inst.Ref, op_rhs: Air _ = try self.addInst(.{ .tag = op_tag, .ops = (Mir.Ops{ - .reg1 = registerAlias(reg, abi_size), + .reg1 = reg, }).encode(), .data = undefined, }); @@ -1363,38 +1346,150 @@ fn genDivOp(self: *Self, inst: Air.Inst.Index, op_lhs: Air.Inst.Ref, op_rhs: Air }, else => unreachable, } +} - return switch (tag) { - .mod, .div_exact, .div_trunc, .div_floor => MCValue{ .register = .rax }, - .rem => MCValue{ .register = .rdx }, - 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 - try self.genDivOp(inst, bin_op.lhs, bin_op.rhs); + 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 - try self.genDivOp(inst, bin_op.lhs, bin_op.rhs); + 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 - try self.genDivOp(inst, bin_op.lhs, bin_op.rhs); + 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 }); } @@ -4368,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, }); @@ -4379,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, }); diff --git a/src/arch/x86_64/Emit.zig b/src/arch/x86_64/Emit.zig index bfef415ad2..7e2a4272dc 100644 --- a/src/arch/x86_64/Emit.zig +++ b/src/arch/x86_64/Emit.zig @@ -161,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(), @@ -373,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"); @@ -391,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", .{}), } @@ -1158,6 +1178,8 @@ const Tag = enum { cwd, cdq, cqo, + cmove, + cmovz, fn isSetCC(tag: Tag) bool { return switch (tag) { @@ -1365,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) { @@ -1382,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) { diff --git a/src/arch/x86_64/Mir.zig b/src/arch/x86_64/Mir.zig index 490c69a38c..8055498439 100644 --- a/src/arch/x86_64/Mir.zig +++ b/src/arch/x86_64/Mir.zig @@ -286,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] -- cgit v1.2.3