使用 clang -O3 优化的 ARM（Apple M1）模块化算法的错误结果

Question

过去几天我一直在用这段“无害”的代码（最小的可重现示例，更大的模块化乘法例程的一部分）来解决我的问题：

#include <iostream>
#include <limits>

using ubigint = unsigned long long int;
using bigint = long long int;

void modmul(bigint a, bigint b, ubigint p) {
    ubigint ua = a < 0 ? -a : a;
    ubigint ub = b < 0 ? -b : b;

    ua %= p;
    ub %= p;

    std::cout << "ua: " << ua << '\n';
}

int main() {
    bigint minbigint = std::numeric_limits<bigint>::min();
    bigint maxbigint = std::numeric_limits<bigint>::max();
    std::cout << "minbigint: " << minbigint << '\n';
    std::cout << "maxbigint:  " << maxbigint << '\n';

    modmul(minbigint, maxbigint, 2314); // expect ua: 2036, got ua: 0
}

我正在使用从 Homebrew 安装的 clang 12.0 在 macOS 11.4 上编译

clang version 12.0.0 
Target: arm64-apple-darwin20.5.0 
Thread model:posix 
InstalledDir: /opt/homebrew/opt/llvm/bin

当用 clang -O1 编译时，程序吐出预期的结果（在本例中，2036，我用 Wolfram Mathematica、Mod[9223372036854775808, 2314] 进行了检查，这是正确的） .但是，当我使用 clang -O2 或 clang -O3（完全优化）进行编译时，变量 ua 不知何故被清零（其值变为 0）。我在这里完全不知所措，不知道为什么会这样。 IMO，这段代码中没有 UB，也没有溢出，也没有任何可疑的地方。我将不胜感激任何建议，或者如果你能在你身边重现该问题。

PS：代码在任何其他平台（包括 Windows/Linux/FreeBSD/Solaris）和任何编译器组合上的行为都符合预期。我只在带有 clang 12 的 Apple M1 上遇到此错误（未在 M1 上使用其他编译器进行测试）。

Answer 1

UPDATE：正如@harold在评论区指出的，从0开始的negq和subq是完全一样的。所以我下面关于 negq 和 subq 的讨论是不正确的。请忽略那部分，很抱歉在发布答案之前没有仔细检查。

关于原问题，我重新编译了一个稍微简单的代码godbolt，发现有问题的编译器优化在main而不是modmul。在 main 中，clang 看到 modmul 的所有操作数都是常量，因此它决定在编译时计算 modmul。在计算ubigint ua = a < 0 ? -a : a;时，clang发现是有符号整数溢出UB所以决定return0打印出来。这似乎是一件激进的事情，但由于 UB，它是合法的。此外，由于二进制补码系统的限制，没有数学上正确的答案，因此 return 0 可以说与任何其他结果一样好（或一样坏）。

下面是旧答案

正如有人在评论部分指出的那样，您代码中下面的两行是未定义的行为——有符号整数溢出 UB。

    ubigint ua = a < 0 ? -a : a;
    ubigint ub = b < 0 ? -b : b;

如果您想知道 clang 在 2 个不同的优化级别下产生 2 个不同结果的幕后究竟做了什么，请考虑下面的一个简单示例。

using ubigint = unsigned long long int;
using bigint = long long int;

ubigint
negate(bigint a)
{
    ubigint ua = -a;
    return ua;
}

使用-O0编译时

negate(long long):                             # @negate(long long)
        pushq   %rbp
        movq    %rsp, %rbp
        movq    %rdi, -8(%rbp)
        xorl    %eax, %eax
        subq    -8(%rbp), %rax  # Negation is performed here
        movq    %rax, -16(%rbp)
        movq    -16(%rbp), %rax
        popq    %rbp
        retq

用-O3编译

negate(long long):                             # @negate(long long)
        movq    %rdi, %rax
        negq    %rax  # Negation is performed here
        retq

在 -O0 处，clang 使用正常的 subq 指令执行 0 和 %rax 的二进制减法并产生具有整数环绕行为的结果。

-O3 时，clang 可以做得更好，它使用 negq 指令，只用二进制补码替换操作数（即翻转所有位并加 1）。但是，您可以看到只有在有符号整数溢出是未定义行为时这种优化才是合法的（因此编译器可以忽略溢出情况）。如果标准要求整数环绕行为，clang 必须退回到未优化的版本。

使用 clang -O3 优化的 ARM（Apple M1）模块化算法的错误结果

Wrong result on modular arithmetic on ARM (Apple M1) with clang -O3 optimization

c++

unsigned-long-long-int

clang++

integer-arithmetic

apple-m1