为什么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;
}

-O3上的GCC将其编译为：

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是相同的。重写to .L4to .L8和drop 会更好.L4吗？我以为这可能是一个错误，但是clang 也将xor- ret序列背对背重复。但是，ICC和MSVC各自采用完全不同的方法。

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

Answer 1

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

但是不幸的是，这种错失的优化在gcc中并不罕见。retgcc 通常是有条件地分支到一个单独的裸机，而不是ret在另一个现有路径中分支到一个。（x86没有条件的ret，因此不需要任何堆栈清理的简单函数通常只需要跳转到一个ret。通常，这种小的函数会被内联到完整的程序中，因此，在现实生活？）

现代的CPU具有一个返回地址预测变量堆栈，该堆栈可以轻松预测ret指令的分支目标，因此不会产生像一条ret指令更多地返回一个调用者而另一条指令更频繁地返回到另一个调用者这样的效果，因此它不会帮助分支预测将它们分开，并让它们使用不同的条目。（这可能对-mtune=pentium3没有RAS预测器的其他古老的CPU 可能有帮助，但是即使那样，您通常也不会为此花费额外的代码大小。）

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

使用关键字missed-optimization向MCC的bugzilla报告此MCVE：https : //gcc.gnu.org/bugzilla/enter_bug.cgi?product=gcc

（更新：https：//gcc.gnu.org/bugzilla/show_bug.cgi？id = 90178由OP报告，并在几天后修复。）

原因：

您可以看到它如何到达2个出口块：编译器通常将for循环转换为if(sz>0) { do{}while(); }是否有可能需要运行0次，如gcc在这里所做的那样。因此，有一个分支使函数完全不进入循环。但是另一个退出是从循环中退出。也许在优化一些东西之前，需要进行一些额外的清理。或者，在创建第一个分支时，只是分解了这些路径。

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

也许它只是在一些GIMPLE或RTL传递中寻找它们，它们实际上并不相同，并且仅在最终的x86代码生成期间才变得相同。也许在优化掉了寄存器的保存/恢复以容纳一些它最终不需要的临时文件之后？

如果-fdump-tree-...在某些优化通过之后使用选项查看GCC的GIMPLE或RTL，则可以进行更深入的研究：Godbolt在+下拉菜单-> tree / RTL输出中具有UI的含义。 https://godbolt.org/z/l9mVlE。但是，除非您是gcc内部专家，并且计划开发补丁程序或想法来帮助gcc找到这种优化方法，否则可能不值得您花时间。

有趣的发现，它仅在-mavx（由-march=skylake或直接启用）时发生。GCC和clang不知道如何在第一次迭代之前未知跳数的情况下自动矢量化循环。例如，像这样的搜索循环或memchr或strlen。因此IDK为何AVX甚至会有所作为。

（请注意，在C抽象机从不读取mem[i]超出了搜索点，并且可能实际上并不存在的那些元素。如没有UB，如果你通过这个函数指针到最后int一个未映射页之前，和sz=1000，只要*mem == val，所以自动-vectorize如果没有int mem[static sz]保证的对象大小，则编译器将不得不对齐指针... C11 int mem[static sz]甚至都无法提供帮助；即使静态的编译时常数大小的数组（大于可能的最大行程计数）也不会使gcc自动运行-vectorize。）