为什么两个模块化操作不能像一个模块化操作那样优化

Question

我正在阅读一个处理时间戳的 C++ 函数，有一个像这样的表达式：

t % (60 * 60) % 60

我认为这个表达式严格等同于：

t % 60

然而，当我将这段代码输入https://godbolt.org时，我发现gcc并不这么认为。

信息：

• 源代码和编译结果：https://godbolt.org/z/fnsxjanja
• gcc 版本：x86-64 gcc 13.2（带有

  -O3

  ）
• clang 版本：x86-64 clang 17.0.1（带有

  -O3

  ）
• msvc 版本：x64 msvc v19.38（带有

  -O2

  ，因为没有

  -O3

  ）
• icx 版本：x86-64 icx 2024.0.0（带有

  -O3

  ）

以下 C++ 代码：

#include <cstdint>
uint64_t mod3600mod60(uint64_t n) { return n % 3600 % 60; }
uint64_t mod60(uint64_t n) { return n % 60; } 

将被编译成：

mod3600mod60(unsigned long):
        movabs  rax, 655884233731895169
        mov     rdx, rdi
        shr     rdx, 4
        mul     rdx
        movabs  rax, -8608480567731124087
        shr     rdx, 3
        imul    rdx, rdx, 3600
        sub     rdi, rdx
        mul     rdi
        mov     rax, rdx
        shr     rax, 5
        mov     rdx, rax
        sal     rdx, 4
        sub     rdx, rax
        mov     rax, rdi
        sal     rdx, 2
        sub     rax, rdx
        ret
mod60(unsigned long):
        movabs  rax, -8608480567731124087
        mul     rdi
        mov     rax, rdx
        shr     rax, 5
        mov     rdx, rax
        sal     rdx, 4
        sub     rdx, rax
        mov     rax, rdi
        sal     rdx, 2
        sub     rax, rdx
        ret

我知道对于除以常量或对常量取模，编译器会优化，但是对于两个连续的模，编译器似乎不会优化到与模一次相同的程度。

首先，我尝试分别用gcc、clang、msvc和icx编译上述两个函数，发现它们不会将这两个函数优化到相同的结果。

接下来，我尝试将两个模都更改为 2 的幂，发现对于以下两个函数：

#include <cstdint>
uint64_t mod2048mod64(uint64_t n) { return n % 2048 % 64; }
uint64_t mod64(uint64_t n) { return n % 64; } 

所有四个编译器都会将两者优化为完全相同。下面是gcc编译结果的例子：

mod2048mod64(unsigned long):
        mov     rax, rdi
        and     eax, 63
        ret
mod64(unsigned long):
        mov     rax, rdi
        and     eax, 63
        ret

接下来，我尝试将第一个模数更改为 2 的非幂，用于以下函数：

#include <cstdint>
uint64_t mod3200mod64(uint64_t n) { return n % 3200 % 64; }

所有四个编译器的优化仍将与单个编译器完全相同

% 64

。

接下来，我尝试将两个模数都改为更小的非2次方，以确认优化不足的原因是否是模数太大。对于以下两个函数：

#include <cstdint>
uint64_t mod6mod3(uint64_t n) { return n % 6 % 3; }
uint64_t mod3(uint64_t n) { return n % 3; } 

与 3600 和 60 一样，四个编译器都无法将这两个函数优化到相同的水平。这里以gcc的优化结果为例：

mod6mod3(unsigned long):
        movabs  rcx, -6148914691236517205
        mov     rax, rdi
        mul     rcx
        shr     rdx, 2
        lea     rax, [rdx+rdx*2]
        add     rax, rax
        sub     rdi, rax
        mov     rax, rdi
        mul     rcx
        mov     rax, rdx
        and     rdx, -2
        shr     rax
        add     rdx, rax
        mov     rax, rdi
        sub     rax, rdx
        ret
mod3(unsigned long):
        movabs  rax, -6148914691236517205
        mul     rdi
        mov     rax, rdx
        and     rdx, -2
        shr     rax
        add     rdx, rax
        mov     rax, rdi
        sub     rax, rdx
        ret

最后我将上述所有函数的参数和返回值分别改为

uint32_t

和

uint16_t

进行编译，得到的结果与

uint64_t

类似。

总结如下：

• 对于无符号整数以常数

  n % A % B

  为模的两个运算，其中

  A

  是

  B

  的倍数：
  • 对于

    B

    是2的幂的情况，gcc、clang、msvc、icx都可以将其优化为与单个

    n % B

    相同；
  • 对于

    B

    不是2的幂的情况，gcc、clang、msvc和icx无法将其优化为与单个

    n % B

    相同。

如果

n % A % B

是

n % B

的倍数，那么

A

和

B

在数学上不应该是严格等价的吗？

Answer 1

这个问题是基于一个根本性的误解。标题以错误的数学假设开始——这两个操作“是”等价的。但编译器根本没有义务使用相同的代码实现等效的操作。 因此，所有的实验证明的东西都很少。随着每个编译器的下一次更新，这些结果可能会改变。因此，完全缺乏版本号意味着这一点信息不是很有用。

我认为这个问题的部分原因是对代码优化如何工作的误解。您能想到的每一个特定优化都必须在编译器代码中实现，并被证明对于所有可能的合法输入都是稳健的，并且不会干扰其他优化。值得这样做吗？再次考虑具体的例子——这不是优化编译器的论点，而是更好的程序员的论点。如果您的意思是

x%60

，请写

x%60

。