展开循环并使用向量化进行独立求和

Question

对于以下循环，只有在使用关联数学（例如使用-Ofast）时，GCC才会对其进行向量化处理。

float sumf(float *x)
{
  x = (float*)__builtin_assume_aligned(x, 64);
  float sum = 0;
  for(int i=0; i<2048; i++) sum += x[i];
  return sum;
}

这里是使用-Ofast -mavx编译选项的汇编代码。

sumf(float*):
    vxorps  %xmm0, %xmm0, %xmm0
    leaq    8192(%rdi), %rax
.L2:
    vaddps  (%rdi), %ymm0, %ymm0
    addq    $32, %rdi
    cmpq    %rdi, %rax
    jne .L2
    vhaddps %ymm0, %ymm0, %ymm0
    vhaddps %ymm0, %ymm0, %ymm1
    vperm2f128  $1, %ymm1, %ymm1, %ymm0
    vaddps  %ymm1, %ymm0, %ymm0
    vzeroupper
    ret

这清楚地显示了循环已经被向量化。

但是这个循环也有一个依赖链。为了克服加法的潜伏期，我需要在x86_64上至少展开和进行部分求和三次（不包括Skylake，它需要展开八次，并使用FMA指令进行加法，在Haswell和Broadwell上需要展开10次）。就我所理解的来说，我可以使用-funroll-loops展开循环。

以下是使用-Ofast -mavx -funroll-loops时的汇编代码。

sumf(float*):
    vxorps  %xmm7, %xmm7, %xmm7
    leaq    8192(%rdi), %rax
.L2:
    vaddps  (%rdi), %ymm7, %ymm0
    addq    $256, %rdi
    vaddps  -224(%rdi), %ymm0, %ymm1
    vaddps  -192(%rdi), %ymm1, %ymm2
    vaddps  -160(%rdi), %ymm2, %ymm3
    vaddps  -128(%rdi), %ymm3, %ymm4
    vaddps  -96(%rdi), %ymm4, %ymm5
    vaddps  -64(%rdi), %ymm5, %ymm6
    vaddps  -32(%rdi), %ymm6, %ymm7
    cmpq    %rdi, %rax
    jne .L2
    vhaddps %ymm7, %ymm7, %ymm8
    vhaddps %ymm8, %ymm8, %ymm9
    vperm2f128  $1, %ymm9, %ymm9, %ymm10
    vaddps  %ymm9, %ymm10, %ymm0
    vzeroupper
    ret

GCC确实将循环展开了8次。但它没有做独立的求和运算，而是进行了8次依赖的求和运算。这毫无意义，与不展开一样糟糕。

如何让GCC展开循环并进行独立的部分求和？

编辑:

对于SSE，即使没有-funroll-loops选项，Clang也会展开到四个独立的部分求和，但我不确定它的AVX代码是否同样高效。编译器在使用-Ofast时不应需要-funroll-loops选项，所以看到Clang至少针对SSE做得正确是好的。

Clang 3.5.1使用-Ofast。

sumf(float*):                              # @sumf(float*)
    xorps   %xmm0, %xmm0
    xorl    %eax, %eax
    xorps   %xmm1, %xmm1
.LBB0_1:                                # %vector.body
    movups  (%rdi,%rax,4), %xmm2
    movups  16(%rdi,%rax,4), %xmm3
    addps   %xmm0, %xmm2
    addps   %xmm1, %xmm3
    movups  32(%rdi,%rax,4), %xmm0
    movups  48(%rdi,%rax,4), %xmm1
    addps   %xmm2, %xmm0
    addps   %xmm3, %xmm1
    addq    $16, %rax
    cmpq    $2048, %rax             # imm = 0x800
    jne .LBB0_1
    addps   %xmm0, %xmm1
    movaps  %xmm1, %xmm2
    movhlps %xmm2, %xmm2            # xmm2 = xmm2[1,1]
    addps   %xmm1, %xmm2
    pshufd  $1, %xmm2, %xmm0        # xmm0 = xmm2[1,0,0,0]
    addps   %xmm2, %xmm0
    retq

ICC 13.0.1使用-O3时，会展开成两个独立的部分和。ICC显然假定只有-O3时才使用可结合的数学运算。

.B1.8: 
    vaddps    (%rdi,%rdx,4), %ymm1, %ymm1                   #5.29
    vaddps    32(%rdi,%rdx,4), %ymm0, %ymm0                 #5.29
    vaddps    64(%rdi,%rdx,4), %ymm1, %ymm1                 #5.29
    vaddps    96(%rdi,%rdx,4), %ymm0, %ymm0                 #5.29
    addq      $32, %rdx                                     #5.3
    cmpq      %rax, %rdx                                    #5.3
    jb        ..B1.8        # Prob 99%                      #5.3

- Z boson

---

手动添加8个累加器？ - user3528438

@user3528438，那样做就失去了编译器为我完成这个任务的全部意义。我最多只会展开四次，如果必须手动展开，我宁愿使用指令集（实际上这也是我会做的）。顺便说一下，ICC 展开成两个部分求和。ICC 更好。 - Z boson

公平地说，我认为你对编译器的要求太高了。或许再给几年时间？ - Mysticial

好的，请告诉我它是否有效，因为我真的很好奇，不幸的是，我不太擅长阅读汇编语言。 - Gilles

@Zboson：Skylake的vaddps具有4个周期延迟，每个周期的吞吐量为2。（它放弃了3c FP加法单元，并使用4个周期延迟的FMA单元进行加法和乘法。）您需要8个向量累加器才能饱和Skylake的FP加法、乘法或FMA吞吐量。我完全同意，如果编译器展开在使用更多累加器方面更加智能化，那将非常好。clang 3.7 on godbolt使用了4个累加器，但是无意义地展开了更多。（uop缓存很小，因此只展开所需的数量。gcc默认仅通过-fprofile-use展开。） - Peter Cordes

Answer 1

使用gcc内置函数和__builtin_会产生以下结果:

typedef float v8sf __attribute__((vector_size(32)));
typedef uint32_t v8u32 __attribute__((vector_size(32)));

static v8sf sumfvhelper1(v8sf arr[4])
{
  v8sf retval = {0};
  for (size_t i = 0; i < 4; i++)
    retval += arr[i];
  return retval;
}

static float sumfvhelper2(v8sf x)
{
  v8sf t = __builtin_shuffle(x, (v8u32){4,5,6,7,0,1,2,3});
  x += t;
  t = __builtin_shuffle(x, (v8u32){2,3,0,1,6,7,4,5});
  x += t;
  t = __builtin_shuffle(x, (v8u32){1,0,3,2,5,4,7,6});
  x += t;
  return x[0];
}

float sumfv(float *x)
{
  //x = __builtin_assume_aligned(x, 64);
  v8sf *vx = (v8sf*)x;
  v8sf sumvv[4] = {{0}};
  for (size_t i = 0; i < 2048/8; i+=4)
    {
      sumvv[0] += vx[i+0];
      sumvv[1] += vx[i+1];
      sumvv[2] += vx[i+2];
      sumvv[3] += vx[i+3];
    }
  v8sf sumv = sumfvhelper1(sumvv);
  return sumfvhelper2(sumv);
}

这是gcc 4.8.4的命令gcc -Wall -Wextra -Wpedantic -std=gnu11 -march=native -O3 -fno-signed-zeros -fno-trapping-math -freciprocal-math -ffinite-math-only -fassociative-math -S转换后的结果:

sumfv:
    vxorps  %xmm2, %xmm2, %xmm2
    xorl    %eax, %eax
    vmovaps %ymm2, %ymm3
    vmovaps %ymm2, %ymm0
    vmovaps %ymm2, %ymm1
.L7:
    addq    $4, %rax
    vaddps  (%rdi), %ymm1, %ymm1
    subq    $-128, %rdi
    vaddps  -96(%rdi), %ymm0, %ymm0
    vaddps  -64(%rdi), %ymm3, %ymm3
    vaddps  -32(%rdi), %ymm2, %ymm2
    cmpq    $256, %rax
    jne .L7
    vaddps  %ymm2, %ymm3, %ymm2
    vaddps  %ymm0, %ymm1, %ymm0
    vaddps  %ymm0, %ymm2, %ymm0
    vperm2f128  $1, %ymm0, %ymm0, %ymm1
    vaddps  %ymm0, %ymm1, %ymm0
    vpermilps   $78, %ymm0, %ymm1
    vaddps  %ymm0, %ymm1, %ymm0
    vpermilps   $177, %ymm0, %ymm1
    vaddps  %ymm0, %ymm1, %ymm0
    vzeroupper
    ret

第二个辅助函数并不是必需的，但在gcc中对向量元素求和往往会产生糟糕的代码。如果您愿意使用平台相关的指令集，您可能可以用__builtin_ia32_hadps256()替换其中的大部分内容。

- EOF