32 位平台上的无符号 64x64->128 位整数乘法

Question

在探索活动的背景下，我开始研究 32 位平台的整数和定点算术构建块。我的主要目标是 ARM32（特别是 ARM32 armv7），同时关注 RISC-V32，我预计 RISC-V32 在嵌入式领域的重要性会不断提高。我选择检查的第一个示例构建块是无符号 64x64->128 位整数乘法。本网站上有关此构建块的其他问题未提供 32 位平台的详细介绍。

在过去的三十年里，我多次实现了这个和其他算术构建块，但总是使用汇编语言，用于各种体系结构。然而，此时我的希望和愿望是这些可以直接用 ISO-C 进行编程，而不使用内在函数。理想情况下，单一版本的 C 代码将生成跨架构的良好机器代码。我知道操纵 HLL 代码来控制机器代码的方法通常很脆弱，但希望处理器架构和工具链已经足够成熟，使之变得可行。

汇编语言实现中使用的一些方法不太适合移植到 C。在下面的示例代码中，我选择了似乎适合 HLL 实现的六个变体。除了生成所有变体所共有的部分积之外，两种基本方法是： (1) 使用 64 位算术对部分积求和，让编译器负责 32 位半部分之间的进位传播。在这种情况下，有多种选择对部分乘积求和的顺序。(2) 使用32位运算进行求和，直接模拟进位标志。在这种情况下，我们可以选择在加法之后 ( a = a + b; carry = a < b;) 或加法之前 ( carry = ~a < b; a = a + b;) 生成进位。下面的变体 1 到 3 属于前一类，变体 5 和 6 属于后者。

在Compiler Explorer中，我专注于感兴趣平台的工具链 gcc 12.2 和 clang 15.0。我用 编译-O3。总体发现是，平均而言，clang 生成的代码比 gcc 更高效，并且变体之间的差异（使用的指令和寄存器的数量）在 clang 中更为明显。虽然对于 RISC-V 作为较新的架构来说，这可能是可以理解的，但令我惊讶的是，armv7它已经存在了十几年了。

其中三个案例尤其值得注意。虽然我之前曾与编译器工程师合作过，并且对基本代码转换、阶段顺序问题等有合理的理解，但我知道可能适用于该代码的唯一技术是习语识别，而且我不知道这如何解释观察本身。第一种情况是变体 3，其中 clang 15.0 生成非常紧凑的代码，仅包含 10 条指令，我认为这些指令无法改进：

umul64wide:
        push    {r4, lr}
        umull   r12, r4, r2, r0
        umull   lr, r0, r3, r0
        umaal   lr, r4, r2, r1
        umaal   r0, r4, r3, r1
        ldr     r1, [sp, #8]
        strd    r0, r4, [r1]
        mov     r0, r12
        mov     r1, lr
        pop     {r4, pc}

相比之下，gcc 生成两倍数量的指令，并且需要两倍数量的寄存器。我假设它无法识别如何使用umaal此处的乘法累加指令，但这就是完整的故事吗？相反的情况，但没有那么戏剧性，出现在变体 6 中，其中 gcc 12.2 生成了 18 条指令的序列，寄存器使用率较低：

umul64wide:
        mov     ip, r0
        push    {r4, r5, lr}
        mov     lr, r1
        umull   r0, r1, r0, r2
        ldr     r4, [sp, #12]
        umull   r5, ip, r3, ip
        adds    r1, r1, r5
        umull   r2, r5, lr, r2
        adc     ip, ip, #0
        umull   lr, r3, lr, r3
        adds    r1, r1, r2
        adc     r2, ip, #0
        adds    r2, r2, r5
        adc     r3, r3, #0
        adds    r2, r2, lr
        adc     r3, r3, #0
        strd    r2, r3, [r4]
        pop     {r4, r5, pc}

生成的代码很好地将模拟的进位传播转变为真实的进位传播。clang 15.0 使用了 9 个指令和 5 个寄存器，如果不花费更多时间进行分析，我无法真正弄清楚它想要做什么。第三个观察结果是关于变体 5 与变体 6 生成的机器代码中的差异，特别是 clang。它们使用相同的基本算法，其中一种变体在加法之前计算模拟进位，另一种变体在加法之后计算模拟进位。我最终确实发现一种变体，即变体 4，似乎在两个工具链和两种架构中都很有效。然而，在我继续进行其他构建模块并面临类似的斗争之前，我想询问：

(1) 在下面的代码中是否有我没有考虑到的编码习惯或算法可能会带来更好的结果？(2) 是否有特定的优化开关，例如假设的-ffrobnicate（请参见此处），未包含在其中-O3，以帮助编译器针对此类位操作场景更一致地生成高效代码？解释哪些编译器机制可能会导致观察到的代码生成中出现显着差异的情况，以及如何影响或解决这些差异，也可能会有所帮助。

umul64wide:
        push    {r4, lr}
        umull   r12, r4, r2, r0
        umull   lr, r0, r3, r0
        umaal   lr, r4, r2, r1
        umaal   r0, r4, r3, r1
        ldr     r1, [sp, #8]
        strd    r0, r4, [r1]
        mov     r0, r12
        mov     r1, lr
        pop     {r4, pc}

Answer 1

我避免使用((x += y) < y)溢出测试，因为并非每个 ISA 都能有效地处理条件标志，并且在使用标志寄存器的结果时可能会禁止重新排序；x86[-64] 是一个明显的例子，尽管后面的 BMI(2) 指令可能有助于缓解这种情况。我还添加了一个 32 x 32 -> 64 位 C 实现来进行比较 - 但我希望任何现代 ISA 至少能够提供像 ARM 那样的“高字”乘法umulh。

/******************************************************************************/

/* stackoverflow.com/questions/74713642 */

#include <inttypes.h>
#include <stdio.h>

/* umul_32_32 : 32 x 32 => 64 */

/* force inline (non-portable), or implement it as macro, e.g.,
 * #define umul_32_32(rh, rl, x, y) do { ... } while (0) */

#if (1)

static inline __attribute__((always_inline))
uint64_t umul_32_32 (uint32_t x, uint32_t y)
{
    return (((uint64_t) x) * y);
}

#else

/* if no widening multiply is available, the compiler probably
 * generates something at least as efficient as the following -
 * or (worst case) it calls a builtin function. */

static inline __attribute__((always_inline))
uint64_t umul_32_32 (uint32_t x, uint32_t y)
{
    uint32_t m0, m1, m2, m3; /* (partial products) */
    uint32_t x0, x1, y0, y1;

    x0 = x & UINT16_MAX, x1 = x >> (16);
    y0 = y & UINT16_MAX, y1 = y >> (16);

    m0 = x0 * y0, m1 = x1 * y0;
    m2 = x0 * y1, m3 = x1 * y1;
    m1 += m0 >> (16);
    m3 += m2 >> (16);
    m1 += m2 & UINT16_MAX;

    uint32_t rh = m3 + (m1 >> (16));
    uint32_t rl = m1 << (16) | (m0 & UINT16_MAX);

    return (((uint64_t) rh) << 32 | rl);

    /* 32 x 32 => 64 : no branching or carry overflow tests. */
}

#endif

/* ensure the function is called to inspect code gen / assembly,
 * otherwise gcc and clang evaluate this at compile time. */

__attribute__((noinline)) void umul_64_64 (

    uint64_t *rh, uint64_t *rl, uint64_t x, uint64_t y)
{
    uint64_t m0, m1, m2, m3; /* (partial products) */
    uint32_t x0, x1, y0, y1;

    x0 = (uint32_t) (x), x1 = (uint32_t) (x >> (32));
    y0 = (uint32_t) (y), y1 = (uint32_t) (y >> (32));

    m0 = umul_32_32(x0, y0), m1 = umul_32_32(x1, y0);
    m2 = umul_32_32(x0, y1), m3 = umul_32_32(x1, y1);
    m1 += m0 >> (32);
    m3 += m2 >> (32);
    m1 += m2 & UINT32_MAX;

    *rh = m3 + (m1 >> (32));
    *rl = m1 << (32) | (m0 & UINT32_MAX);

    /* 64 x 64 => 128 : no branching or carry overflow tests. */
}

#if (0)

int main (void)
{
    uint64_t x = UINT64_MAX, y = UINT64_MAX, rh, rl;

    umul_64_64(& rh, & rl, x, y);
    fprintf(stdout, "0x%016" PRIX64 ":0x%016" PRIX64 "\n", rh, rl);

    return (0);
}

#endif

/******************************************************************************/

对于 ARM-7，我得到的结果或多或少与您的“变体 3”代码相同，这并不奇怪，因为它的基本思想相同。我在 gcc-12 和 gcc-trunk 上尝试了不同的标志，但无法改进它。

我大胆猜测，随着 Apple 对 AArch64 芯片的投资，只是针对 clang 进行了更积极的优化和资金投入，这也有利于 32 位 ARM-7。但这纯粹是猜测。对于这样一个主要平台来说，这是一个相当明显的差距。