当A是B的倍数时，为何两次模运算无法优化为单次模运算？

我在阅读一段处理时间戳的C++代码时，遇到表达式：

t % (60 * 60) % 60

从数学角度看，该表达式与t % 60严格等价，但测试发现GCC等主流编译器并未将其优化为单次模运算。

测试环境 #

• x86-64 GCC 13.2（开启-O3）
• x86-64 Clang 17.0.1（开启-O3）
• x64 MSVC v19.38（开启-O2，无-O3选项）
• x86-64 ICX 2024.0.0（开启-O3）

测试代码 #

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

编译后两个函数的汇编代码存在差异，说明编译器未进行等价优化。

对比实验 #

我开展了多组对比实验，结果如下：

1. 两个模数均为2的幂

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

   四款编译器均能将其优化为完全相同的汇编代码，等价于单次%64运算。

2. 第一个模数为非2的幂、第二个模数为2的幂

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

   四款编译器仍能将其优化为单次%64运算。

3. 两个模数均为非2的幂

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

   四款编译器均无法将两次模运算优化为单次模运算，汇编代码存在差异。

4. 修改整数类型
   将参数与返回值改为uint32_t、uint16_t后，得到的结果与uint64_t类似。

实验结论 #

对于无符号整数的连续两次常量模运算n % A % B（A是B的倍数）：

• 当B是2的幂时，四款编译器均可将其优化为单次n % B运算；
• 当B不是2的幂时，四款编译器均无法完成该等价优化。

疑问 #

当A是B的倍数时，n % A % B与n % B在数学上严格等价，为何编译器无法将两次模运算优化为单次？

内容的提问来源于stack exchange，提问作者2n8 asm