为什么编译器在这里错过矢量化？

2024-05-24

考虑以下valarray类：

#include <stdlib.h>

struct va
{
    void add1(const va& other);
    void add2(const va& other);

    size_t* data;
    size_t  size;
};

void va::add1(const va& other) {
    for (size_t i = 0; i < size; ++i) {
        data[i] += other.data[i];
    }
}

void va::add2(const va& other){
    for (size_t i = 0, s = size; i < s; ++i) {
        data[i] += other.data[i];
    }
}

The add2函数针对不同的编译器（MSVC、Clang、GCC、ICC）进行矢量化，而add1不是。看https://godbolt.org/z/c61qvrrbv https://godbolt.org/z/c61qvrrbv

这是通过潜在的别名来解释的：编译器无法证明所指向的元素之一data不是size itself.

然而，也存在潜在的重叠元素data and other.data。对于 MSVC，这些元素和指针本身可能存在别名，因为它没有利用严格别名规则。这适用于两者add1 and add2.

编译器正在检查他们怀疑的所有可能的别名，并执行向量化操作add2.

他们为什么不添加更多检查并进行优化add1?

看起来编译器无法意识到（并且不添加代码来检查）data[i]从不指向this->size.这将使循环行程计数在第一次迭代之前无法计算，这是除 ICC 之外任何主流编译器都无法处理的问题。

希望编译器能够在应用矢量化逻辑之前学会检查可能的重叠，例如(.data > this) || (.data+.size) < this;希望有一种有效的方法来做到这一点。他们已经发明了代码来检查两个数组之间的重叠add2.

（启动时需要的检查代码越多，向量化本身的利润就越高；与 128 位向量相比，64 位标量元素在基线 x86-64 上并没有那么糟糕，尤其是当编译器不这样做时从PGO得知，尺寸通常不小，而且循环很热。我尝试过gcc -march=icelake-client and -march=znver4不仅启用 AVX2，还为具有非常好的向量吞吐量和缓存/内存带宽的 CPU 设置调整启发式。但仍然没有乐趣，所以这种可能的混叠可能是一个完整的障碍，而不是一个启发式的决定。）

Asm 证据表明编译器担心别名`this->size`

注意GCC的循环分支是如何的cmp rax, QWORD PTR [rdi+8], where rax holds i and [rdi+8] is this->size（x86-64 SysV 调用约定），因此每次迭代都会重新加载它。如果我们编译-O3 -fno-tree-vectorize，我们看到 GCC 的add2在循环之前将大小加载到寄存器中，与循环内的大小进行比较，即提升负载。事实上，GCC 并没有这样做add1是一个非常明显的迹象表明它认为data[i] += ...可以修改this->size.

# GCC's add1 inner loop with -O3   -march=icelake-client
.L3:
        mov     rcx, QWORD PTR [rsi+rax*8]
        add     QWORD PTR [rdx+rax*8], rcx
        inc     rax
        cmp     rax, QWORD PTR [rdi+8]
        jb      .L3

另外，将类型更改为unsigned *data;或任何不能指向size_t让 GCC、Clang 和 ICC 自动矢量化add1. Using -fno-strict-aliasing再次禁用矢量化。（并且使编译器额外“偏执”，重新加载this->data and other.data每次迭代，就像 MSVC 一直在做的那样。也打破了矢量化add2对于那些编译器。）

更改指针类型对 MSVC 没有帮助，因为它不进行基于类型的别名分析；它总是表现得像gcc -fno-strict-aliasing。 MSVC 的add2我认为，已经检查的不仅仅是指向数组的重叠；可能其中一些额外的 cmp/jcc 正在检查this->data[i] += ...不会改变.data指针指向this or other.

`std::vector`没有`size_t`会员，通常会避免这种情况

std::vector<size_t>不会有这个问题（至少在非 MSVC 编译器中），因为基于类型的别名知道size_t *不能指向另一个指针。std::vector通常存储三个指针：.begin, .end, and end_of_capacity，所以尺寸信息是end-begin，不是直接存储大小的成员。

对于迭代一个数组，通常至少与递增指针一样有效for (... ; ptr < endp ; ptr++) *ptr所以你没有使用索引寻址模式。大概就是这个原因std::vector通常是这样布局的，而不是一个指针和两个size_t成员。

有些 RISC 机器甚至没有双寄存器索引寻址模式。对于迭代两个数组，一些 CPU 使用更少的指令会做得更好，只需增加一个索引而不是两个指针增量，但这取决于微体系结构，例如一些 x86 CPU 未层压 https://stackoverflow.com/questions/26046634/micro-fusion-and-addressing-modes add reg, [reg + reg]在后端分成 2 个 uop，而不是保持微融合，尤其是对于 3 操作数 AVX 指令。

使用索引寻址在 CPU 上循环两个数组的一种有效方法（在 asm 中）是相对于另一个数组对一个数组进行寻址。在 C++ 中执行此操作是 UB 的行为，并且会混淆您的代码，因此编译器应该为您做这些事情。sub rsi, rdi在循环之外（减去指针），那么循环体可以是mov eax, [rsi + rdi]（第二个数组 = 差值 + 第一个数组）/add [rdi], eax（第一个数组）/add rdi, 8（增加指针，该指针也是另一个数组的索引。）

MSVC 实际上会进行其他编译器尚未采用的优化。 (Godbolt https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DIApACYAQuYukl9ZATwDKjdAGFUtAK4sGIMwDMpK4AMngMmAByPgBGmMQSAGykAA6oCoRODB7evv5BaRmOAmER0SxxCVzJdpgOWUIETMQEOT5%2BgbaY9sUMjc0EpVGx8Um2TS1teZ0KE4PhwxWj1QCUtqhexMjsHOYB4cjeWADUJgFus%2Bi0eDEAdAhn2CYaAILPLwD0H8ceLCl08QUx1mdFox1QKUcLDwAC9MMcAO6EBAbAjHAD66OImFmxDwDlIxxiXjRhGOwEwBCBePQ4KoxwICHhDFQeCUdOOmFUBGITGOyCZyAA1uFgO8AG6s2n8VAQcJogBUmOxuPxaKYhPlxyVWJxPLVRJWJgA7FZXscLcd%2BMRjnLBMc8GcACIaU4BCwOs5uLgaMySDRnD2OyzWI2m96WyPHJgmACsFkdsadpxDAWTMTjCbjTsDEctJpzrwL73euK8DmO4pjRfD5stkrwtKY6HQXAgaAYs0rMbMiXBjPiRvdeYtDabLbM7YEXar5j7qAHxCHZredYtXy8nbwwAitIV6CYTVza%2BBsMw6MVB6P7vX32VerxFaZ2OO6FQOIYYA4aKZtBSI9POELwtDI4WPN5jRzYci1eMduxAEBm1bKdOzRWde37Z8VlOWsXktL5APPNFQPhZ0GQQNkAFpHhI8DI2tW0SOAvA3WTAMbxYr1CMDFMrEsPBsJNFco0tK8Y3jRNk2sMiF2fW4xMzSS6PzSCS1UmCXjgqsEKQycOxnHtEnvVUK1kwchIAhiICY0lWOODRCSBMjaI4t03GBHjpP4wTcJEi0FIk7NeJkxd5MPcSsyTZSLWLGtCxeDg1loThY14PwOC0UhUE4NwvI9BQNi2UjAh4UgCE0RK1iFfxEluAAORJjWNABODREg0Y1EgCOrmuNIJko4SQ0oqrLOF4BQQAc8qMsS0g4FgGBEBQVA/gBMgKCnVb6AScVkBSFJ0XFLhmvRAwCD1dFVESaQsHFfFMAANTwTAEQAeRSRhOFKmhaHO4gJogGIRpicJmgATy%2B3gQeYYgwdemJtDqabSrQFg2EEV6GFoCGZtILBiWANwxFoCbuF4LAWEMYBxFx/BsXqcUcRGrk6hJHZSvlboRuuGJeVhjwsBG/UWEhtYqAMYAFCel73s%2BsmZEEEQxHYKQFfkJQ1BG3QzH0KmUDy/QbgmyA1ghXpSY%2BV6zGOD5mgFEAXgegANMxeFQRniBpJmTa6HoshcBh3E8do9FCBZykqPRCkyAQpj8LhUnSGOGCGCPll9pGGjmOO9FqeoBH6FpU5GKpxgGHOE9mAZi6WKo1gKzZtgkJKUuG3Hso4Y4rskY4WAUXbK2O24zr1W1cEIEgUwCLgVl4aatBWNYmWbUYICq/w6tuMwuACAJmskafYy4Mweua/ROCG0gRdjBz0syjvxsmsqKrWealtR/5tvISgP7WkB8WQGYX0XBjQOVuvdaWb0PrpW%2BnQP6AMga42huDSGpBkGw3hojBwqDUbowIJjbGI18ZeEJsTUmpUKZUxpplOmmdGak0yizZAbNUGcwGplHmfMwYC3ZnPPEIsyZiwllLZ6UC5bfVkErcQqt%2BCCEUCodQuNdD9T1qYEMlhDYxGNmvLKkIsik0oq9AIxxKKU3FKoV2WUPZe20fXbomdnAQFcBXYIgca6RwTtHXoLivFZHcenPOvRC6tGDnkSu9j859DmP40uVdJihPjmXIu4cS7N3WI3FWLcOCpVIHfN2nAu4NUotdB0yBkDHCAdvW4xpbiuggOPIgNo9gzzni/JemAV4JB0QNS%2B19b4jQfrYJ%2B89KqkGqtPW4%2B8AigLqpIWMvUNB1Q0G1c%2BHAAht3vmNZ%2BM1X6LTfhAJAv8v4bSOaMSWzAUgKBRAQPGmA7rbEgbLGBvAfrwMoIgzK6CcalS%2BZgpGOCVp4IITjGhmACZE1oCTVBlCjDUPJngemjh6HM1UKzc6rDBBc1xpw8GPDUHC1FnwYRjzoGoNkcIUQ0jpDkvkZrJRegDBGH1uomwPNbG6PNpwQxxiLSmLtg8NMMIGAe0vu7eINj4B2L9o45xCTQ5uJSbXKOSdvFys8SqvxiqPEZ0icElxgSs7Vy1QE7OaqknzDKKkme6SippIGjkvJo1O6qCKSU4AZTbQ8k3EKbC9T8CNKni07ZC914TOuqA5q3U6qxljL2a60gem8D6bkgZWyJpTRfnNPZhyVqf3iN/TaeaEiHCpheYg3rbn3MeqIp5ZK4GAnecDUGsNUG/IRv8%2BWuDGD4KxiC8mYKSEQqhfLGF1Mdg0IRXQpmuMmEsPlmw7mNwuF4vlgSwRRKmCSxJeIl5kjKUq2pbIWlijMq6ATaog2bLJUcv0Vyoxlo%2BVbAFU6F1iRimSEouKYxbtrGNm9jog1MrA4uLDpapV6qihZB8RqkoxrYkRKCaa3IiTANRKNWB7VcSQnIdztEuDaSG62utfajZ%2BTnWup7iWownry0MB9WPf1k9mmz2DaM5eWAulZN6SAG%2BKb25puGW0sZIBJBcFuFwOq0blmRt7LGAIbUE2cHWXxzZHBWk7KyZYx1gyRmL1IB7DIzhJBAA%3D)

// Compilers still optimize without __restrict, but it gets rid of the noise of extra checking
void foo(int *__restrict a, int *__restrict b){
    for (int i=0 ; i<10240; i++){
        a[i] += b[i];
    }
}

void foo(int * __restrict,int * __restrict) PROC                              ; foo, COMDAT
        lea     rax, QWORD PTR [rcx+32]
        sub     rdx, rcx       ;;;; <---- Pointer subtraction
        mov     ecx, 320                      ; 00000140H
        npad    4
$LL4@foo:
        vmovdqu ymm1, YMMWORD PTR [rax-32]            ;; unrolled with 4 vectors
        vpaddd  ymm1, ymm1, YMMWORD PTR [rdx+rax-32]
        vmovdqu YMMWORD PTR [rax-32], ymm1

        vmovdqu ymm2, YMMWORD PTR [rax]
        vpaddd  ymm1, ymm2, YMMWORD PTR [rdx+rax]
        vmovdqu YMMWORD PTR [rax], ymm1

        vmovdqu ymm1, YMMWORD PTR [rax+32]
        vpaddd  ymm1, ymm1, YMMWORD PTR [rdx+rax+32]
        vmovdqu YMMWORD PTR [rax+32], ymm1

        vmovdqu ymm1, YMMWORD PTR [rax+64]
        vpaddd  ymm1, ymm1, YMMWORD PTR [rdx+rax+64]
        vmovdqu YMMWORD PTR [rax+64], ymm1

        lea     rax, QWORD PTR [rax+128]
        sub     rcx, 1
        jne     SHORT $LL4@foo
        vzeroupper
        ret     0

不幸的是，MSVC 搞反了，并使用双寄存器寻址模式作为内存源操作数vpaddq. It'll 未层压 https://stackoverflow.com/questions/26046634/micro-fusion-and-addressing-modes正在讨论/重命名为 Intel Sandybridge 系列上的 ROB，至少包括 Skylake，可能会稍后一些。但vpaddd ymm1, ymm1, [rdx]将为 1 uop。纯负载vmovdqu即使使用索引寻址模式，也始终为 1 uop。

索引存储也不理想（存储地址 uop 无法在 Haswell / Skylake 上的端口 7 上运行），MSVC 确实避免了这种情况。但它可以通过执行纯负载来获得两全其美的效果b[]使用索引寻址模式，然后是内存源vpadd+ 使用简单寻址模式存储，例如[rdx+32].

因此，MSVC 确实节省了一些代码大小，并且通过仅需要一个循环开销增量，在后端吞吐量方面获得了一些好处，并且在 AGU 端口争用中，因此可以在每个时钟接近 1 个向量的情况下运行，并且 L1d 缓存命中可以让它运行每个周期执行 2 次加载 + 1 次存储（Intel 的优化手册表明，由于某些未知原因，Skylake 无法完全支持 32 字节加载/存储），

使用 GCC 和 clang 等存储的索引寻址模式，它只能在 Haswell / Skylake 上以每 1.5 个周期 1 个向量运行。（Ice Lake 有两个负载 AGU 和两个独立的存储 AGU，避免了这个瓶颈，但我不知道索引寻址模式的非分层在 Ice Lake 或 Alder Lake 上是否仍然存在。）

我不知道 MSVC 更喜欢什么lea用于递增指针。或者为了更喜欢sub ecx/jne而不是与结束指针进行比较lea在循环之前而不是mov。那么循环的结束可能是cmp rax, r8/jne或者其他东西，它会在 AMD 上融合成单个微指令，而不仅仅是英特尔。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)