C/C++ 中有符号整数表达式的代数归约

Question

我想看看 GCC 是否会将带符号和无符号整数的 a - (b - c) 减少到 (a + c) - b，所以我创建了两个测试

//test1.c
unsigned fooau(unsigned a, unsigned b, unsigned c) { return a - (b - c); }
signed   fooas(signed   a, signed   b, signed   c) { return a - (b - c); }
signed   fooms(signed   a) { return a*a*a*a*a*a; }
unsigned foomu(unsigned a) { return a*a*a*a*a*a; }  

//test2.c
unsigned fooau(unsigned a, unsigned b, unsigned c) { return (a + c) - b; }
signed   fooas(signed   a, signed   b, signed   c) { return (a + c) - b; }
signed   fooms(signed   a) { return (a*a*a)*(a*a*a); }
unsigned foomu(unsigned a) { return (a*a*a)*(a*a*a); }

我先用gcc -O3 test1.c test2.c -S编译，然后看汇编。对于这两个测试，fooau 是相同的，但 fooas 不是。

据我所知，无符号算术可以从 the following formula

(a%n + b%n)%n = (a+b)%n

可以用来证明无符号算术是结合的。但是由于 signed overflow is undefined behavior 这个等式不一定适用于有符号加法（即有符号加法不是关联的），这解释了为什么 GCC 没有将有符号整数的 a - (b - c) 减少到 (a + c) - b。但是我们可以通过 -fwrapv 告诉 GCC 使用这个公式。对两个测试使用此选项 fooas 是相同的。

但是乘法呢？对于这两个测试，fooms 和 foomu 都被简化为三个乘法 (a*a*a*a*a*a to (a*a*a)*(a*a*a))。但是乘法可以写成重复加法所以使用上面的公式我认为可以证明

((a%n)*(b%n))%n = (a*b)%n

我认为这也可以表明无符号模乘法也是结合的。但是由于 GCC 只对 foomu 使用了三个乘法，这表明 GCC 假定有符号整数乘法是关联的。

这对我来说似乎是矛盾的。对于加法，有符号算术不是关联的，但对于乘法，它是关联的。

两个问题：

加法与有符号整数无关但乘法在C/C++中是真的吗？
如果使用有符号溢出来优化，GCC不减少代数表达式不是优化失败吗？优化使用 -fwrapv 不是更好吗（我知道 a - (b - c) 到 (a + c) - b 并没有减少多少，但我担心更复杂的情况）？这是否意味着优化有时使用 -fwrapv 更有效而有时不是？

Answer 1

不，乘法在有符号整数中不具有关联性。考虑 (0 * x) * x 与 0 * (x * x) - 后者可能具有未定义的行为，而前者始终已定义。
未定义行为的可能性只会引入新的优化机会，经典示例是将已签名的x + 1 > x优化为true x，对无符号整数不可用的优化。

我认为您不能假设 gcc 未能将 a - (b - c) 更改为 (a + c) - b 表示错过了优化机会；这两个计算在 x86-64 上编译为相同的两条指令（leal 和 subl），只是顺序不同。

事实上，实现有权假设算术是关联的，并将其用于优化，因为 UB 上可能发生任何事情，包括模算术或无限范围算术。但是，你作为程序员无权假设结合性，除非你能保证没有中间结果溢出。

作为另一个例子，尝试 (a + a) - a - gcc 将优化为 a 有符号 a 以及无符号。

Answer 2

如果对任何定义的输入集具有相同的结果，则可以执行有符号整数表达式的代数归约。所以如果表达式

a * a * a * a * a * a

已定义——也就是说，a 足够小，在计算过程中不会发生有符号溢出——然后任何乘法重新分组都会产生相同的值，因为没有小于 6 的乘积 as 可以溢出。

a + a + a + a + a + a也是如此。

如果相乘（或相加）的变量不完全相同，或者如果加法与减法混合在一起，情况就会发生变化。在这些情况下，重新分组和重新排列计算可能会导致有符号溢出，而这在规范计算中不会发生。

例如，取表达式

a - (b - c)

在代数上，这等同于

(a + c) - b

但是编译器无法进行重新排列，因为中间值 a+c 可能会溢出输入，而这不会导致原始值溢出。假设我们有 a=INT_MAX-1; b=1; c=2; 然后 a+c 导致溢出，但是 a - (b - c) 被计算为 a - (-1)，即 INT_MAX，没有溢出。

如果编译器可以假定有符号溢出不会陷入陷阱，而是以模 INT_MAX+1 计算，那么这些重新排列是可能的。 -fwrapv 选项允许 gcc 做出该假设。

C/C++ 中有符号整数表达式的代数归约

Algebraic reductions of signed integer expressions in C/C++

c

c++

optimization

gcc

integer