展开用于自动矢量化的指针增量循环

Question

我想知道是否展开这个循环：

for (int i = 0; i < n; i++) {
    *p = a[i]*b[i];
    p++;
}

进入

for (int i = 0; i < n; i+=4) {
    *(p + 0) = a[i + 0]*b[i + 0];
    *(p + 1) = a[i + 1]*b[i + 1];
    *(p + 2) = a[i + 2]*b[i + 2];
    *(p + 3) = a[i + 3]*b[i + 3];
    p+=4;
}

将在自动矢量化方面帮助编译器。

我可以想象它无论如何都会矢量化第一个循环。但是明确有帮助吗？

Answer 1

一般来说，您可以通过按照标准算法实现算法来帮助您自己和优化器。

例如：

#include <boost/iterator/zip_iterator.hpp>

void bar(int n, int * p, const int * a, const int * b)
{
    auto source_begin = boost::make_zip_iterator(boost::make_tuple(a, b));
    auto source_end = boost::make_zip_iterator(boost::make_tuple(a + n, b + n));

    std::transform(source_begin, source_end, p, [](auto&& source) {
        return boost::get<0>(source) * boost::get<1>(source);
    });
}

clang 3.9.1 变成：

bar(int, int*, int const*, int const*):                        # @bar(int, int*, int const*, int const*)

... alignment stuff ...
.LBB0_7:                                # =>This Inner Loop Header: Depth=1
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi]
        vmovdqu ymmword ptr [rsi + 4*rdi], ymm0
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi + 32]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi + 32]
        vmovdqu ymmword ptr [rsi + 4*rdi + 32], ymm0
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi + 64]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi + 64]
        vmovdqu ymmword ptr [rsi + 4*rdi + 64], ymm0
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi + 96]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi + 96]
        vmovdqu ymmword ptr [rsi + 4*rdi + 96], ymm0
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi + 128]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi + 128]
        vmovdqu ymmword ptr [rsi + 4*rdi + 128], ymm0
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi + 160]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi + 160]
        vmovdqu ymmword ptr [rsi + 4*rdi + 160], ymm0
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi + 192]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi + 192]
        vmovdqu ymmword ptr [rsi + 4*rdi + 192], ymm0
        vmovdqu ymm0, ymmword ptr [rcx + 4*rdi + 224]
        vpmulld ymm0, ymm0, ymmword ptr [rdx + 4*rdi + 224]
        vmovdqu ymmword ptr [rsi + 4*rdi + 224], ymm0
        add     rdi, 64
        add     rbx, 8
        jne     .LBB0_7
.LBB0_8:
        test    r14, r14
        je      .LBB0_11
        lea     rbx, [rdx + 4*rdi]
        lea     rax, [rcx + 4*rdi]
        lea     rdi, [rsi + 4*rdi]
        neg     r14
.LBB0_10:                               # =>This Inner Loop Header: Depth=1
        vmovdqu ymm0, ymmword ptr [rax]
        vpmulld ymm0, ymm0, ymmword ptr [rbx]
        vmovdqu ymmword ptr [rdi], ymm0
        add     rbx, 32
        add     rax, 32
        add     rdi, 32
        add     r14, 1
        jne     .LBB0_10
.LBB0_11:
        cmp     r8, r9
        je      .LBB0_16
        lea     rsi, [rsi + 4*r9]
        lea     rcx, [rcx + 4*r9]
        lea     rdx, [rdx + 4*r9]
.LBB0_13:
        add     rcx, 4
        add     rdx, 4
.LBB0_14:                               # =>This Inner Loop Header: Depth=1
        mov     rax, rdx
        mov     edx, dword ptr [rcx - 4]
        imul    edx, dword ptr [rax - 4]
        mov     dword ptr [rsi], edx
        add     rsi, 4
        lea     rdx, [rax + 4]
        cmp     r11, rcx
        lea     rcx, [rcx + 4]
        jne     .LBB0_14
        cmp     r10, rax
        jne     .LBB0_14
.LBB0_16:
        pop     rbx
        pop     r14
        vzeroupper
        ret

忽略对齐检查，我想你会同意编译器做得很好。

然而，gcc似乎错过了这个机会。可能的缺陷？

Answer 2

为了成功的自动向量化，您的编译器需要能够确定所涉及的变量不使用别名，这意味着编译器需要确定 a、b 和 p 永远不会重叠，例如：

void somefunction()
{
    int a[12] = { ... };
    int b[12] = { ... }
    int p[12];

    /* Compiler knows: a, b and p do not overlap */
}

void multiply(int n, int* p, int* a, int* b)
{
    /* Compiler unsure: a, b and p could overlap, e.g.:
         multiply(8, array1, array1, array1);
       or worse:
         multiply(8, array1 + 1, array1, array1 + 2);
    */
}

如果它们重叠，第一次迭代可能会影响下一次迭代，因此它们不能并行执行。

对于一个函数，您实际上可以使用restrict关键字向编译器保证参数不会重叠。不幸的是，只有 C 标准正式支持，C++ 还没有。但是，许多 C++ 编译器都支持类似的关键字，例如__restrict__ 用于 gcc 和 clang，__restrict 用于 MSVC。例如对于 gcc:

void multiply(int n, int* __restrict__ p, int* __restrict__ a, int* __restrict__ b)

{
    for (int i = 0; i < n; i++) {
       p[i] = a[i]*b[i];
    }
}

生成的代码（使用 gcc -O2 -ftree-vectorize）看起来相当不错：

multiply(int, int*, int*, int*):
        test    edi, edi
        jle     .L1
        lea     r8d, [rdi-4]
        lea     r9d, [rdi-1]
        shr     r8d, 2
        add     r8d, 1
        cmp     r9d, 2
        lea     eax, [0+r8*4]
        jbe     .L9
        xor     r9d, r9d
        xor     r10d, r10d
.L5:
        movdqu  xmm0, XMMWORD PTR [rdx+r9]
        add     r10d, 1
        movdqu  xmm2, XMMWORD PTR [rcx+r9]
        movdqa  xmm1, xmm0
        psrlq   xmm0, 32
        pmuludq xmm1, xmm2
        psrlq   xmm2, 32
        pshufd  xmm1, xmm1, 8
        pmuludq xmm0, xmm2
        pshufd  xmm0, xmm0, 8
        punpckldq       xmm1, xmm0
        movups  XMMWORD PTR [rsi+r9], xmm1
        add     r9, 16
        cmp     r10d, r8d
        jb      .L5
        cmp     eax, edi
        je      .L12
.L3:
        cdqe
.L7:
        mov     r8d, DWORD PTR [rdx+rax*4]
        imul    r8d, DWORD PTR [rcx+rax*4]
        mov     DWORD PTR [rsi+rax*4], r8d
        add     rax, 1
        cmp     edi, eax
        jg      .L7
        rep ret
.L1:
        rep ret
.L12:
        rep ret
.L9:
        xor     eax, eax
        jmp     .L3

更新： 如果没有 restrict 关键字，gcc 显然会生成一个函数来检测别名并为两种情况生成代码。

顺便说一下，您的展开版本没有考虑 n 不是 4 的倍数的情况，因此在功能上有所不同！

展开用于自动矢量化的指针增量循环

Unrolling pointer increment loop for auto vectorization

c++

simd

loop-unrolling

auto-vectorization