3

Godbolt 链接：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 -m32as 标志的程序集是：

  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

为什么编译器不将subarrayandsubsubarray计算移到内部循环之外？

随机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它是一个局部变量，因为 usingstd::cout << subsubarray[k];阻止了优化。

gcc 8.2-O3 -m32为上述代码生成的带有 as 标志的程序集是：

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

循环不变量被推出内部循环。randomvolatile做了什么来让 GCC 优化不变量？clang 6.0.0时不会发生优化。

4

1 回答 1

2

这不是关于随机 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 意味着只有您的指针不应该修改内存，而不是它是全局只读的） .

但是如果你“承诺”这些地址不重叠，优化就会回来。

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;博士;

如果您使用指针编译器可能无法证明地址没有别名并且将使用安全路径。如果您 100% 确定他们不会使用限制来告知它这一事实。

于 2018-08-07T23:50:30.777 回答