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

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进行这种优化呢？

- Alex Guteniev

---

size在函数执行期间可以从外部进行修改，我猜是这样吗？ - Alan Birtles

这可以通过潜在的别名解释：编译器无法证明数据指向的元素之一不是大小本身。我相信这就是原因。例如，当data和size具有不同的类型时，它会进行向量化处理。 - KamilCuk

@AlanBirtles，但这将是一个竞争条件，所以编译器在这种情况下可以自由地做任何事情。对于并发修改，应该使用std::atomic或其他多线程工具，以确保适当的原子性和内存顺序。还要注意指针也可以被同时修改，这并不妨碍add2的向量化。 - Alex Guteniev

虽然不熟悉汇编语言，但即使for (size_t i = 0; i < size; ++i) { data[i] += 1;}似乎也没有处理向量化别名的代码。我猜他们对这种优化有一套模式，而这个例子不是其中之一。 - Jarod42

希望一个[[assume(&va.size < va.data || &va.size >= va.data + va.size)]]能够起作用。这应该可以在两种情况下防止运行时检查，无论优化器是否插入这样的运行时检查都无关紧要。 - MSalters

Answer 1

看起来编译器无法意识到（并且没有添加代码来检查）data[i]永远不会指向this->size。这将导致循环的迭代次数在第一次迭代之前无法计算，这是除了ICC之外没有任何主流编译器能够处理的事情。

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

（启动时需要更多的检查代码，矢量化就必须更有利可图，与基线x86-64相比，64位标量元素并不那么糟糕，特别是当编译器不知道PGO中size通常不小且循环热点时。我尝试了gcc -march=icelake-client和-march=znver4，不仅启用了AVX2，还为具有非常好的矢量吞吐量和缓存/内存带宽的CPU设置了调优启发式算法。但仍然没有成功，所以这种可能的别名可能是一个完全的障碍，而不是启发式决策。）

---

编译器对别名问题的关注证据： this->size

请注意GCC的循环分支是cmp rax, QWORD PTR [rdi+8]，其中rax保存i，[rdi+8]是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。使用-fno-strict-aliasing会再次禁用向量化。（并使编译器额外“偏执”，在每次迭代中重新加载this->data和other.data，就像MSVC一直在做的那样。同时还会破坏那些编译器对add2的向量化。）

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

---

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 指令。

在使用汇编语言（asm）循环遍历两个具有索引寻址的数组时，一种高效的方法是相对于另一个数组进行寻址。在C++中这样做是未定义行为，并且会使代码变得晦涩难懂，因此这是编译器应该为您完成的工作。在循环之外使用sub rsi, rdi（指针相减），然后循环体可以是mov eax, [rsi + rdi]（第二个数组 = 差值 + 第一个数组）/ add [rdi], eax（第一个数组）/ add rdi, 8（增加指针，也是另一个数组的索引）。

MSVC实际上会进行这种优化，而其他编译器尚未掌握这一点。（Godbolt）

// 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系列上，包括至少Skylake，它会在发出/重命名时解开，进入ROB。但是vpaddd ymm1, ymm1, [rdx]只需要1个微操作。纯加载vmovdqu即使使用索引寻址模式，也始终只需要1个微操作。

索引存储也不理想（存储地址微操作无法在Haswell / Skylake上在端口7上运行），而MSVC确实避免了这个问题。但是它可以通过使用索引寻址模式从b[]进行纯加载，然后使用简单寻址模式（如[rdx+32]）进行内存源vpadd + 存储，以获得最佳效果。

所以MSVC确实节省了一些代码大小，并且通过只需要一个循环开销的增量，以及在AGU端口争用方面获得了一些后端吞吐量的好处，因此可以以接近每个时钟周期1个向量的速度运行，同时L1d缓存命中可以让它每个周期执行2次加载和1次存储（英特尔的优化手册表明Skylake无法完全维持32字节的加载/存储，原因不明）。

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

我不知道为什么MSVC更喜欢使用lea来增加指针。或者为什么更喜欢使用sub ecx/jne而不是在循环之前使用lea与结束指针进行比较，然后循环的结束可以是cmp rax, r8/jne之类的，这样在AMD上不仅在英特尔上也会融合成一个单一的微操作。

- Peter Cordes

---

std::vector没有size_t成员，通常避免使用它。是的，在MSVC valarray中我遇到了这个问题。幸运的是，在循环之前它会保存大小，并且我的当前PR将添加一个解释，以便不会丢失。libc++的valarray使用两个指针，所以没问题。然而，许多STL和非STL的std::span实现都是指针和大小的组合，所以随着C++17的采用，这个问题就变得更加严重。 - Alex Guteniev

相对于128位向量，基线x86-64中的64位标量元素并不那么糟糕。你可以将大小和元素设置为32位或16位，以使标量版本变得不那么吸引人。 - Alex Guteniev

@AlexGuteniev：噢对了，对于继承或组合而言是的，因为使用指向子对象类型的指针的代码可以假设填充始终是填充。我指的是 struct { int *data; uint32_t size; uint8_t foo, bar; } 这个结构只有 2 字节的填充。所以对于 std::span 来说并没有用，但是 std::span 无论如何都会使用 size_t。 - Peter Cordes

在选择使用两个寄存器寻址的操作时，我认为MSVC尽量避免使用它，因此避免索引存储并非巧合，但仍不关心哪个操作是双寄存器寻址的。将“a[i] = a[i] - b[i]”（双寄存器寻址加载）与“a[i] = b[i] - a[i]”（双寄存器寻址减法）的循环进行比较。 - Alex Guteniev

看起来，使用Clang级别的循环展开，可以只增加两个指针并完全避免双寄存器寻址，额外增加的成本将是最小的。 - Alex Guteniev