c++ - 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 到 (a*a*a)*( a*a*a)).但是乘法可以写成重复的加法所以使用上面的公式我认为可以证明

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

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

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

两个问题:

1. 在 C/C++ 中加法与有符号整数无关但乘法是真的吗？

2. 如果使用有符号溢出进行优化，GCC 不减少代数表达式的事实不是优化失败吗？使用 -fwrapv 优化不是更好吗(我理解 a - (b - c) 到 (a + c) - b 并没有减少多少，但我担心更复杂的情况)？这是否意味着使用 -fwrapv 进行优化有时效率更高，有时则不然？

Answer 1

1. 不，乘法在有符号整数中不相关。考虑 (0 * x) * x 与 0 * (x * x) - 后者可能具有未定义的行为，而前者始终已定义。

2. 未定义行为的可能性只会引入新优化机会，经典示例是将 x + 1 > x 优化为 true 对于有符号 x，这是一种不适用于无符号整数的优化。

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

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

作为另一个例子，尝试 (a + a) - a - gcc 会将其优化为 a 用于签名 a 以及未签名。