128位乘64位本机划分

Question

我需要在 Rust 中执行 128 位乘 64 位除法。x86-64 ISA 包含用于此目的的本机 DIV 指令。但是，我编译的测试代码没有使用该指令。

测试代码：

pub fn div(hi: u64, lo: u64, divisor: u64) -> u64 {
   assert!(hi < divisor);

   let dividend = ((hi as u128) << 64) + lo as u128;
   (dividend / divisor as u128) as u64
}

编译器资源管理器输出：

example::div:
    push    rax
    cmp     rdi, rdx
    jae     .LBB0_1
    mov     rax, rdi
    mov     rdi, rsi
    mov     rsi, rax
    xor     ecx, ecx
    call    qword ptr [rip + __udivti3@GOTPCREL]
    pop     rcx
    ret
.LBB0_1:
    ...

相反，通过 __udivti3 执行低效的 128 位乘 128 位除法。这可能是因为如果商不适合 64 位，DIV 指令会导致 CPU 异常。然而，就我而言，这是不可能的： hi < 除数，lo < 2^64 -> 被除数 = hi * 2^64 + lo <= (除数 - 1) * 2^64 + 2^64 - 1 = 除数 * 2^64 - 1 -> 被除数/除数 <= 2^64 - 1 / 除数 < 2^64

如何强制编译器使用本机指令？

Answer 1

您唯一的选择是使用内联汇编。可能存在一些模糊的编译器标志组合，可以强制 llvm 自行执行优化，但我认为尝试找到它并不值得付出努力。通过组装，它看起来像这样：

use std::arch::asm;
pub fn div(hi: u64, lo: u64, divisor: u64) -> u64 {

    assert!(hi < divisor);

    #[cfg(target_arch = "x86_64")]
    unsafe {
        let mut quot = lo;
        let mut _rem = hi;
        asm!(
            "div {divisor}",
            divisor = in(reg) divisor,
            inout("rax") quot,
            inout("rdx") _rem,
            options(pure, nomem, nostack)
        );
        quot
    }
    #[cfg(not(target_arch = "x86_64"))]
    {
        let dividend = ((hi as u128) << 64) + lo as u128;
        (dividend / divisor as u128) as u64
    }
}

神箭

在 x86_64 上，这只是将除法编译为一点寄存器改组，然后是div, 并在其他系统上执行调用__udivti3。它也不应该过多地妨碍优化器，因为它是纯粹的。

绝对值得对您的应用程序进行实际基准测试，看看这是否真的有帮助。llvm 比内联汇编更容易推理整数除法，并且在其他地方错过优化很容易导致该版本的运行速度比使用默认版本慢。