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不是.

据我所知,无符号算术可以从以下公式推导出来

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

这可以用来表明无符号算术是关联的.但由于签订溢出是未定义的行为, 这种平等并不一定保持签署加法(即签署另外是不是联想),这解释了为什么GCC并没有减少a - (b - c)到(a + c) - b符号整数.但是我们可以告诉GCC使用这个公式-fwrapv.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假设有符号整数乘法是关联的.

这似乎与我相矛盾.对于加法,有符号算术不是关联的,但对于乘法则是.

两个问题:

1. 添加是否与有符号整数无关,但乘法是否在C/C++中？

2. 如果使用带符号溢出进行优化,那么GCC不会减少代数表达式的优化失败吗？那岂不是更好更好的优化使用-fwrapv(我明白a - (b - c)到(a + c) - b是没有太大的减少,但我担心的是更复杂的情况)？这是否意味着优化有时使用-fwrapv更有效,有时它不是？

Answer 1

1. 不,乘法在有符号整数中不是关联的.考虑(0 * x) * xvs. 0 * (x * x)- 后者具有潜在的未定义行为,而前者始终被定义.

2. 未定义行为的可能性永远只能引入新的优化机会,典型的例子是优化x + 1 > x以true供签署x,优化是不适用于无符号整数.

我认为你不能认为gcc未能改变a - (b - c)以(a + c) - b代表错失的优化机会; 这两个计算在x86-64(leal和subl)上编译为相同的两个指令,只是顺序不同.

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

作为另一个例子,try (a + a) - a-gcc将优化它以a用于签名a和无符号.