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

Question

考虑以下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];
    }
}

该add2函数针对不同的编译器（MSVC、Clang、GCC、ICC）进行了向量化，而add1并非如此。参见https://godbolt.org/z/c61qvrrbv

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

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

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

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

Answer 1

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

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

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

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

请注意 GCC 的循环分支是cmp rax, QWORD PTR [rdi+8]，其中rax保存i和[rdi+8]是this->size（x86-64 SysV 调用约定），因此每次迭代都会重新加载它。如果我们使用 进行编译-O3 -fno-tree-vectorize，我们会看到 GCCadd2在循环之前将大小加载到寄存器中，与循环内的大小进行比较，即提升负载。事实上，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;或任何不能指向 a 的内容size_t可以让 GCC、Clang 和 ICC 自动向量化add1. 使用-fno-strict-aliasing再次禁用矢量化。（并且使编译器变得更加“偏执”，重新加载this->data和other.data每次迭代，就像 MSVC 一直在做的那样。同时也打破了add2这些编译器的矢量化。）

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

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

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

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

有些 RISC 机器甚至没有双寄存器索引寻址模式。对于迭代两个数组，一些 CPU 使用更少的指令会做得更好，只需增加一个索引而不是两个指针增量，但这取决于微体系结构，例如，一些 x86 CPU在后端未层压 add reg, [reg + reg]为 2 个微指令，而不是保持微架构-融合，特别是对于 3 操作数 AVX 指令。

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

MSVC 实际上会进行其他编译器尚未采用的优化。（神箭）

// 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。它将在问题上取消层压/重命名为 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与结束指针进行比较。然后循环的结尾可能是/或其他东西，它会在 AMD 上融合成单个 uop，而不仅仅是 Intel。leamovcmp rax, r8jne