为什么 C++ 编译器可能会复制函数退出基本块？

Question

考虑以下代码片段：

int* find_ptr(int* mem, int sz, int val) {
    for (int i = 0; i < sz; i++) {
        if (mem[i] == val) { 
            return &mem[i];
        }
    }
    return nullptr;
}

GCC on -O3 将其编译为：

find_ptr(int*, int, int):
        mov     rax, rdi
        test    esi, esi
        jle     .L4                  # why not .L8?
        lea     ecx, [rsi-1]
        lea     rcx, [rdi+4+rcx*4]
        jmp     .L3
.L9:
        add     rax, 4
        cmp     rax, rcx
        je      .L8
.L3:
        cmp     DWORD PTR [rax], edx
        jne     .L9
        ret
.L8:
        xor     eax, eax
        ret
.L4:
        xor     eax, eax
        ret

在此程序集中，带有标签 .L4 和 .L8 的块是相同的。将 .L4 的跳转重写为 .L8 并删除 .L4 不是更好吗？我认为这可能是一个错误，但 clang also duplicates the xor-ret sequence back to back. However, ICC and MSVC 每个人都采用了完全不同的方法。

在这种情况下这是一种优化吗？如果不是，是否有时会是？这种行为背后的基本原理是什么？

Answer 1

这总是错过了优化。让两个 return-0 路径都使用相同的基本块将是当前编译器关心的所有微体系结构的纯粹胜利。

但不幸的是，这种优化失误在 gcc 中并不少见。通常它是 gcc 有条件地分支到的一个单独的 ret ，而不是分支到另一个现有路径中的 ret 。（x86 没有条件 ret，因此不需要任何堆栈清理的简单函数通常只需要分支到 ret。通常这么小的函数会被内联到一个完整的程序中，所以在现实生活中它可能不会造成太大伤害？）

CPU (since Pentium Pro if not earlier) 有一个 return 地址预测器堆栈，可以轻松预测 ret 指令的分支目标，因此 [=] 不会产生影响10=] 指令更频繁地 return 发送给一个调用者，而另一个指令更频繁地 return 发送给另一个调用者。将它们分开并让它们使用不同的条目对分支预测没有帮助。

关于 Pentium 4 的 IDK 及其跟踪缓存中的跟踪是否遵循 call/ret。但幸运的是，这不再重要了。 SnB 系列和 Ryzen 中的解码 uop 缓存是不是跟踪缓存； line/way 的 uop 缓存保存连续的 x86 机器代码块的 uops，无条件跳转结束 uop 缓存行。 (https://agner.org/optimize/) 因此，如果有的话，这对于 SnB 系列来说可能更糟，因为每个 return 路径都需要一个单独的 uop 缓存行，即使它们每个总共只有 2 uops（异或零和ret 都是单 uop 指令）。

将这个 MCVE 报告给 gcc 的 bugzilla，关键字是 missed-optimization：https://gcc.gnu.org/bugzilla/enter_bug.cgi?product=gcc

(更新：https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90178 由 OP 报告。尝试修复，但已恢复；目前它仍然打开。在这种情况下，它似乎是由 -mavx 引起的，也许是一些与需要或不需要 vzeroupper 的 return 路径交互。）

原因：

你可以看到它是如何到达 2 个退出块的：如果有可能需要运行 0 次，编译器通常会将 for 循环转换为 if(sz>0) { do{}while(); }，就像 gcc 在这里做的那样。所以有一个分支离开了函数而根本没有进入循环。但另一个出口是从循环中掉下来。也许在优化掉一些东西之前，有一些额外的清理工作。或者在创建第一个分支时只是这些路径被拆分了。

我不知道为什么 gcc 没有注意到并合并两个相同的以 ret 结尾的基本块。

也许它只是在一些 GIMPLE 或 RTL 通道中寻找它们实际上并不相同，并且只是在最终的 x86 代码生成期间才变得相同。也许在优化掉 save/restore 寄存器以保存一些它最终不需要的临时值之后？

如果你在某些优化通过后查看带有 -fdump-tree-... 选项的 GCC 的 GIMPLE 或 RTL，你可以更深入地挖掘：Godbolt 在 + 下拉列表中有 UI -> 树/RTL 输出。 https://godbolt.org/z/l9mVlE。但是除非您是 gcc-internals 专家并且计划开发补丁或想法来帮助 gcc 找到这种优化，否则可能不值得您花时间。

有趣的发现，它只发生在 -mavx 上（由 -march=skylake 启用或直接启用）。 GCC 和 clang 不知道如何自动矢量化在第一次迭代之前不知道行程计数的循环。例如像这样搜索循环或 memchr 或 strlen。所以 IDK 为什么 AVX 甚至完全不同。

（请注意，C 抽象机永远不会读取超出搜索点的 mem[i]，并且这些元素可能实际上不存在。例如，如果您将指向最后一个 [=28= 的指针传递给此函数，则没有 UB ] 在未映射的页面之前，并且 sz=1000，只要 *mem == val。所以要在没有 int mem[static sz] 保证对象大小的情况下自动矢量化，编译器必须对齐指针...不是那个C11 int mem[static sz] 甚至会有所帮助；即使是编译时常量大小大于最大可能行程计数的静态数组也不会让 gcc 自动矢量化。）

为什么 C++ 编译器可能会复制函数退出基本块？

Why might a C++ compiler duplicate a function exit basic block?

c++

gcc

x86-64

compiler-optimization