gcc 12 在查找向量中的最小元素时生成的汇编代码比 gcc 8 更差

Question

测试代码：

#include <vector>
#include <cstdint>
#include <algorithm>

uint32_t find_min(const std::vector<uint32_t>& v)
{
    return std::distance(v.begin(), std::min_element(v.begin(), v.end()));
}

查找向量中最小元素的索引。

GCC 8 生成的代码：

find_min(std::vector<unsigned int, std::allocator<unsigned int> > const&):
        mov     rcx, QWORD PTR [rdi+8]
        mov     rsi, QWORD PTR [rdi]
        xor     eax, eax
        cmp     rcx, rsi
        je      .L1
        lea     rax, [rsi+4]
        mov     rdx, rsi
        cmp     rcx, rax
        je      .L4
.L6:
        mov     edi, DWORD PTR [rdx]
        cmp     DWORD PTR [rax], edi
        cmovb   rdx, rax
        add     rax, 4
        cmp     rcx, rax
        jne     .L6
.L4:
        mov     rax, rdx
        sub     rax, rsi
        sar     rax, 2
.L1:
        ret

GCC 12 生成的代码：

find_min(std::vector<unsigned int, std::allocator<unsigned int> > const&):
        mov     r8, QWORD PTR [rdi+8]
        mov     rdi, QWORD PTR [rdi]
        xor     eax, eax
        cmp     rdi, r8
        je      .L1
        lea     rdx, [rdi+4]
        cmp     r8, rdx
        je      .L1
        mov     esi, DWORD PTR [rdi]
        mov     rax, rdi
.L4:
        mov     ecx, DWORD PTR [rdx]
        cmp     ecx, esi
        jnb     .L3
        mov     esi, ecx
        mov     rax, rdx
.L3:
        add     rdx, 4
        cmp     r8, rdx
        jne     .L4
        sub     rax, rdi
        sar     rax, 2
.L1:
        ret

两个编译器都使用

-O3

标志，使用 Compiler Explorer 生成这些代码：https://godbolt.org/z/ehv9Mv584

我们可以看到 GCC 8 生成的代码使用

cmovb

，而 GCC 12 生成的代码使用分支。在我的实际测试中，GCC 8 生成的代码运行速度更快。

我的问题是，有没有办法让 GCC 12 生成类似 GCC 8 的汇编代码，使用

cmovb

而不是分支？

---

我找到了解决方案，禁用

-ftree-partial-pre

标志即可解决此问题：

uint32_t __attribute__((optimize("no-tree-partial-pre"))) find_min(const std::vector<uint32_t>& v) {....}

任何人都可以帮助解释部分冗余消除（PRE）在这种情况下是如何工作的吗？

Answer 1

这似乎是一个调整选择/成本模型启发式。正如 @HolyBlackCat 注意到的，

-march=znver3

（这意味着相同的

-mtune

）使用 2x

cmovb

来更新值和指针。 （神箭）。

-march=icelake-server

甚至

-march=sapphirerapids

仍然会产生分支汇编。

如果分支不能很好地预测，那么无分支汇编在 Broadwell 和以后的版本中可能会更好，所以这可能值得在 https://gcc.gnu.org/bugzilla/ 上报告，并带有“错过优化” " 关键字，特别是如果您测试它的非小数组大小并发现它更快。

---

希望配置文件引导优化（PGO：

-fprofile-generate

/测试运行/

-fprofile-use

）能够根据数据的实际可预测性做出有分支与无分支的良好选择。也许它是在假设新的

max

很少见的情况下对大型数组进行优化（这对于均匀分布的随机值来说是正确的。）但它布置了分支，以便在这种情况下采用它，而不是放置

 块mov

说明不合规矩。相关：gcc 优化标志 -O3 使代码比 -O2 慢回复：分支与无分支，其中无分支速度较慢，因为条件是可预测的；如果我没记错的话，PGO 在那里提供了帮助。 （GCC 的无分支汇编具有比必要的更长的依赖链。）

---

GCC8 的无分支代码生成对于非小型数组来说是不利的，所以现代 GCC 没有做到这一点是一件好事。请注意，它仅使用一个

cmov

来更新指针，并且 从

cmp

中的有条件更新的指针加载。所以下一次迭代的加载地址取决于本次迭代的compare + cmov。正如 uiCA 向我们展示，这种数据依赖性会造成每次迭代 7 个周期的延迟瓶颈。

用 C 语言来说，就像

biggest_ptr = (*ptr > *biggest_ptr) ? ptr : biggest_ptr;

-fno-tree-partial-pre

为您提供 one-

cmov

GCC8 代码生成。 （这对于您的情况来说很好，因为无序执行可以隐藏延迟，因此执行与周围的代码重叠。）对于较大的数组来说这是一场灾难。

---

GCC13 的带有两个

cmovb

指令的无分支汇编仅在下一次迭代中使用更新的最大值，而不是指针。因此，指针更新 cmov 是循环携带的依赖链的一部分，该链只有 1 个周期长。但值更新

cmovb

与

cmp  esi, ecx

形成一条链，每次迭代的总延迟瓶颈为 2 个周期。 （uiCA 有一个依赖图可视化工具，有助于发现为什么该版本不是 1 个周期。）

uiCA 预测 假设完美的分支预测，分支版本可以在 Rocket Lake 上每次迭代运行 1.33 个周期。 （这类似于 Ice Lake，但未禁用 mov-elimination。）它预测 Skylake 和 Ice Lake 上的周期/迭代次数为 2.0，但没有解释原因。它的 RKL 预测可能只有在每次迭代都有新的 max

 时才有意义。它的计数假设 

mov

 指令实际运行。但在 Skylake 上，它说第一个 cmp/jcc 只能在端口 6 上运行，而不能在端口 0 上运行，这只有在被占用时才是正确的。 uiCA（以及其他工具，如 IACA 和我认为 LLVM-MCA）仅适用于无分支循环，所以我不确定这是否有意义。