未能优化看似明显的循环不变量（但 volatile 限定符确实有魔力）
failure to optimize seemingly obvious loop invariant (but volatile qualifier did magic)
神马 Link: https://godbolt.org/g/Hv6MAL
typedef int cell;
cell y;
const cell *phys_addr = (const cell*)0x12340;
int main() {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
y = subsubarray[k];
}
}
}
}
期望编译器将上述代码优化为类似于以下内容的感觉很自然：
int main() {
for (int i = 0; i < 20; i++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
for (int j = 0; j < 30; j++) {
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
for (int k = 0; k < 50; k++) {
y = subsubarray[k];
}
}
}
}
但是 gcc 8.2 生成的带有 -O3 -m32 作为标志的程序集是：
push ebp
push edi
push esi
push ebx
sub esp, 8
mov eax, DWORD PTR phys_addr
mov DWORD PTR [esp], 0
mov DWORD PTR [esp+4], eax
mov ebp, eax
.L4:
xor esi, esi
.L3:
lea edi, [0+esi*4]
xor eax, eax
.L2:
mov edx, DWORD PTR [ebp+0]
mov ecx, DWORD PTR [esp+4]
shr edx, 2
add edx, DWORD PTR [esp]
lea ebx, [ecx+edx*4]
lea edx, [eax+esi]
add eax, 1
mov ecx, DWORD PTR [ebx+edi]
shr ecx, 2
add edx, ecx
mov edx, DWORD PTR [ebx+edx*4]
mov DWORD PTR y, edx
cmp eax, 50
jne .L2
add esi, 1
cmp esi, 30
jne .L3
add DWORD PTR [esp], 1
mov eax, DWORD PTR [esp]
add ebp, 4
cmp eax, 20
jne .L4
add esp, 8
xor eax, eax
pop ebx
pop esi
pop edi
pop ebp
ret
为什么编译器不将 subarray 和 subsubarray 计算移到内部循环之外？
随机volatile变魔术
我随机添加了 volatile 以防止 DCE 删除所有代码，然后以某种方式将循环不变量提升到内部循环之外。
int main() {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
volatile cell y = subsubarray[k];
}
}
}
return 0;
}
这主要不是因为 y 是局部变量，因为使用 std::cout << subsubarray[k]; 阻止了优化。
gcc 8.2 以 -O3 -m32 作为上述代码的标志生成的程序集是：
main:
push ebp
push edi
xor edi, edi
push esi
push ebx
sub esp, 20
mov ebp, DWORD PTR phys_addr
.L4:
mov eax, DWORD PTR [ebp+0+edi*4]
xor ecx, ecx
shr eax, 2
add eax, edi
lea ebx, [ebp+0+eax*4]
lea esi, [ebx+200]
.L3:
mov edx, DWORD PTR [ebx+ecx*4]
mov DWORD PTR [esp], ecx
shr edx, 2
add edx, ecx
sal edx, 2
lea eax, [ebx+edx]
add edx, esi
.L2:
mov ecx, DWORD PTR [eax]
add eax, 4
mov DWORD PTR [esp+16], ecx
cmp edx, eax
jne .L2
mov ecx, DWORD PTR [esp]
add ecx, 1
cmp ecx, 30
jne .L3
add edi, 1
cmp edi, 20
jne .L4
add esp, 20
xor eax, eax
pop ebx
pop esi
pop edi
pop ebp
ret
循环不变量被推出内部循环。随机 volatile 做了什么让 GCC 优化不变量？ clang 6.0.0.
时不会进行优化
这不是随机 volatile 解决你的问题 - 问题更深。
正如您已经猜到的，问题确实与 "y"
有关
检查这个例子：
typedef int cell;
const cell *phys_addr = (const cell*)0x12340;
int main() {
cell y = 1;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
y /= subsubarray[k];
}
}
}
return y;
}
我使用了除法技巧来避免硬优化（gcc 可以评估所有循环并直接在普通赋值中提供 y；当使用加法、减法或乘法时，它也会展开最内层的循环 - 请玩 godbolt 看看看起来如何）
现在反汇编看起来像这样：
https://godbolt.org/g/R1EGSb
main:
push ebp
push edi
push esi
push ebx
sub esp, 12
mov eax, DWORD PTR phys_addr
mov DWORD PTR [esp], 0
mov DWORD PTR [esp+4], eax
mov eax, 1
.L4:
mov esi, DWORD PTR [esp]
mov edi, DWORD PTR [esp+4]
mov edx, DWORD PTR [edi+esi*4]
mov DWORD PTR [esp+8], edx
shr edx, 2
add edx, esi
xor esi, esi
lea edi, [edi+edx*4]
lea ebp, [edi+200]
.L3:
mov ebx, DWORD PTR [edi+esi*4]
shr ebx, 2
add ebx, esi
sal ebx, 2
lea ecx, [edi+ebx]
add ebx, ebp
.L2:
cdq
idiv DWORD PTR [ecx]
add ecx, 4
cmp ebx, ecx
jne .L2
add esi, 1
cmp esi, 30
jne .L3
add DWORD PTR [esp], 1
mov edi, DWORD PTR [esp]
cmp edi, 20
jne .L4
add esp, 12
pop ebx
pop esi
pop edi
pop ebp
ret
phys_addr:
.long 74560
.L2 是最内层的循环，因此代码看起来像预期的那样 - 子数组和子子数组是较早预先计算的。
所以您可能想知道 - 为什么当 "y" 是本地时一切正常，而当全局不是。
要明确 - "y" 不必在 main 中声明。它可以像这样静态化
static cell y;
const cell * __restrict__ phys_addr = (const cell*)0x12340;
或使用命名空间
namespace wtf{ cell y; }
const cell * __restrict__ phys_addr = (const cell*)0x12340;
然后将 y 称为 wtf::y;
还是不错的。
所有压缩到别名。要查看它，让我们先将 y 更改为指针：
typedef int cell;
cell * y;
const cell * phys_addr = (const cell*)0x12340;
int main() {
cell ylocal;
y = &ylocal;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
*y /= subsubarray[k];
}
}
}
return *y;
}
再次没有循环优化....
可能假设 y 和 phys_addr 重叠 - 写入 y 可能会修改一些记忆单元，因此所有词典都必须使用最新数据进行计算（phys_addr 中的 const 意味着只有你的指针不应该修改内存，并不是说它是全局只读的。
但是如果你"promise"那些地址不重叠优化就会回来。
typedef int cell;
cell * __restrict__ y;
const cell * __restrict__ phys_addr = (const cell*)0x12340;
int main() {
cell ylocal;
y = &ylocal;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
*y /= subsubarray[k];
}
}
}
return *y;
}
TL；DR；
如果您使用的是指针，编译器可能无法证明地址没有别名并将使用安全路径。如果您 100% 确定他们不会使用 restrict 来告知该事实。
神马 Link: https://godbolt.org/g/Hv6MAL
typedef int cell;
cell y;
const cell *phys_addr = (const cell*)0x12340;
int main() {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
y = subsubarray[k];
}
}
}
}
期望编译器将上述代码优化为类似于以下内容的感觉很自然：
int main() {
for (int i = 0; i < 20; i++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
for (int j = 0; j < 30; j++) {
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
for (int k = 0; k < 50; k++) {
y = subsubarray[k];
}
}
}
}
但是 gcc 8.2 生成的带有 -O3 -m32 作为标志的程序集是：
push ebp
push edi
push esi
push ebx
sub esp, 8
mov eax, DWORD PTR phys_addr
mov DWORD PTR [esp], 0
mov DWORD PTR [esp+4], eax
mov ebp, eax
.L4:
xor esi, esi
.L3:
lea edi, [0+esi*4]
xor eax, eax
.L2:
mov edx, DWORD PTR [ebp+0]
mov ecx, DWORD PTR [esp+4]
shr edx, 2
add edx, DWORD PTR [esp]
lea ebx, [ecx+edx*4]
lea edx, [eax+esi]
add eax, 1
mov ecx, DWORD PTR [ebx+edi]
shr ecx, 2
add edx, ecx
mov edx, DWORD PTR [ebx+edx*4]
mov DWORD PTR y, edx
cmp eax, 50
jne .L2
add esi, 1
cmp esi, 30
jne .L3
add DWORD PTR [esp], 1
mov eax, DWORD PTR [esp]
add ebp, 4
cmp eax, 20
jne .L4
add esp, 8
xor eax, eax
pop ebx
pop esi
pop edi
pop ebp
ret
为什么编译器不将 subarray 和 subsubarray 计算移到内部循环之外？
随机volatile变魔术
我随机添加了 volatile 以防止 DCE 删除所有代码，然后以某种方式将循环不变量提升到内部循环之外。
int main() {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
volatile cell y = subsubarray[k];
}
}
}
return 0;
}
这主要不是因为 y 是局部变量，因为使用 std::cout << subsubarray[k]; 阻止了优化。
gcc 8.2 以 -O3 -m32 作为上述代码的标志生成的程序集是：
main:
push ebp
push edi
xor edi, edi
push esi
push ebx
sub esp, 20
mov ebp, DWORD PTR phys_addr
.L4:
mov eax, DWORD PTR [ebp+0+edi*4]
xor ecx, ecx
shr eax, 2
add eax, edi
lea ebx, [ebp+0+eax*4]
lea esi, [ebx+200]
.L3:
mov edx, DWORD PTR [ebx+ecx*4]
mov DWORD PTR [esp], ecx
shr edx, 2
add edx, ecx
sal edx, 2
lea eax, [ebx+edx]
add edx, esi
.L2:
mov ecx, DWORD PTR [eax]
add eax, 4
mov DWORD PTR [esp+16], ecx
cmp edx, eax
jne .L2
mov ecx, DWORD PTR [esp]
add ecx, 1
cmp ecx, 30
jne .L3
add edi, 1
cmp edi, 20
jne .L4
add esp, 20
xor eax, eax
pop ebx
pop esi
pop edi
pop ebp
ret
循环不变量被推出内部循环。随机 volatile 做了什么让 GCC 优化不变量？ clang 6.0.0.
这不是随机 volatile 解决你的问题 - 问题更深。
正如您已经猜到的，问题确实与 "y"
有关检查这个例子：
typedef int cell;
const cell *phys_addr = (const cell*)0x12340;
int main() {
cell y = 1;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
y /= subsubarray[k];
}
}
}
return y;
}
我使用了除法技巧来避免硬优化（gcc 可以评估所有循环并直接在普通赋值中提供 y；当使用加法、减法或乘法时，它也会展开最内层的循环 - 请玩 godbolt 看看看起来如何）
现在反汇编看起来像这样： https://godbolt.org/g/R1EGSb
main:
push ebp
push edi
push esi
push ebx
sub esp, 12
mov eax, DWORD PTR phys_addr
mov DWORD PTR [esp], 0
mov DWORD PTR [esp+4], eax
mov eax, 1
.L4:
mov esi, DWORD PTR [esp]
mov edi, DWORD PTR [esp+4]
mov edx, DWORD PTR [edi+esi*4]
mov DWORD PTR [esp+8], edx
shr edx, 2
add edx, esi
xor esi, esi
lea edi, [edi+edx*4]
lea ebp, [edi+200]
.L3:
mov ebx, DWORD PTR [edi+esi*4]
shr ebx, 2
add ebx, esi
sal ebx, 2
lea ecx, [edi+ebx]
add ebx, ebp
.L2:
cdq
idiv DWORD PTR [ecx]
add ecx, 4
cmp ebx, ecx
jne .L2
add esi, 1
cmp esi, 30
jne .L3
add DWORD PTR [esp], 1
mov edi, DWORD PTR [esp]
cmp edi, 20
jne .L4
add esp, 12
pop ebx
pop esi
pop edi
pop ebp
ret
phys_addr:
.long 74560
.L2 是最内层的循环，因此代码看起来像预期的那样 - 子数组和子子数组是较早预先计算的。
所以您可能想知道 - 为什么当 "y" 是本地时一切正常，而当全局不是。
要明确 - "y" 不必在 main 中声明。它可以像这样静态化
static cell y;
const cell * __restrict__ phys_addr = (const cell*)0x12340;
或使用命名空间
namespace wtf{ cell y; }
const cell * __restrict__ phys_addr = (const cell*)0x12340;
然后将 y 称为 wtf::y;
还是不错的。
所有压缩到别名。要查看它，让我们先将 y 更改为指针：
typedef int cell;
cell * y;
const cell * phys_addr = (const cell*)0x12340;
int main() {
cell ylocal;
y = &ylocal;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
*y /= subsubarray[k];
}
}
}
return *y;
}
再次没有循环优化....
可能假设 y 和 phys_addr 重叠 - 写入 y 可能会修改一些记忆单元，因此所有词典都必须使用最新数据进行计算（phys_addr 中的 const 意味着只有你的指针不应该修改内存，并不是说它是全局只读的。
但是如果你"promise"那些地址不重叠优化就会回来。
typedef int cell;
cell * __restrict__ y;
const cell * __restrict__ phys_addr = (const cell*)0x12340;
int main() {
cell ylocal;
y = &ylocal;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 30; j++) {
for (int k = 0; k < 50; k++) {
const cell *subarray = (&phys_addr[i] + phys_addr[i]/sizeof(cell));
const cell *subsubarray = (&subarray[j] + subarray[j]/sizeof(cell));
*y /= subsubarray[k];
}
}
}
return *y;
}
TL；DR；
如果您使用的是指针，编译器可能无法证明地址没有别名并将使用安全路径。如果您 100% 确定他们不会使用 restrict 来告知该事实。