时间戳

首页 > 解决方案 > 为什么我展开的循环尾声的 gcc 代码生成看起来过于复杂？

c - 为什么我展开的循环尾声的 gcc 代码生成看起来过于复杂？

问题描述

感谢到目前为止的所有评论。很抱歉，我在最初的问题中使用了一个不好的例子，几乎每个人都会说：“哦，你应该使用memcopy！” 但这不是我的问题。

我的问题是关于应该如何进行手动循环展开的更通用的问题。这次考虑这个例子，通过对数组中的所有元素求和：

#include <stdlib.h>

double sum (size_t n, double *x) {
  size_t nr = n & 1;
  double *end = x + (n - nr);
  double sum_x = 0.0;
  for (; x < end; x++) sum_x += *x;
  if (nr) sum_x += *x;
  return sum_x;
  }

编译器生成的程序集承认类似的行为（与我原始问题中的数组复制示例所示）

sum:
  movq %rdi, %rcx
  andl $1, %ecx
  subq %rcx, %rdi
  leaq (%rsi,%rdi,8), %rdx
  cmpq %rdx, %rsi
  jnb .L5
  movq %rsi, %rax
  pxor %xmm0, %xmm0
.L3:
  addsd (%rax), %xmm0
  addq $8, %rax
  cmpq %rax, %rdx
  ja .L3
  movq %rsi, %rax
  notq %rax
  addq %rax, %rdx
  shrq $3, %rdx
  leaq 8(%rsi,%rdx,8), %rsi
.L2:
  testq %rcx, %rcx
  je .L1
  addsd (%rsi), %xmm0
.L1:
  ret
.L5:
  pxor %xmm0, %xmm0
  jmp .L2

但是，如果我现在在主循环之前安排“小数”部分（正如我后来在我发布的答案中挖掘出来的那样），编译器会做得更好。

#include <stdlib.h>

double sum (size_t n, double *x) {
  size_t nr = n & 1;
  double *end = x + n;
  double sum_x = 0.0;
  if (nr) sum_x += *x;
  for (x += nr; x < end; x++) sum_x += *x;
  return sum_x;
  }

sum:
  leaq (%rsi,%rdi,8), %rdx
  pxor %xmm0, %xmm0
  andl $1, %edi
  je .L2
  addsd (%rsi), %xmm0
.L2:
  leaq (%rsi,%rdi,8), %rax
  cmpq %rax, %rdx
  jbe .L1
.L4:
  addsd (%rax), %xmm0
  addq $8, %rax
  cmpq %rax, %rdx
  ja .L4
.L1:
  ret

我只使用了编译器标志-O2。所以正如彼得所说，编译器生成的程序集应该接近 C 源代码。那么问题来了，为什么编译器在后一种情况下会做得更好？

这不是一个真正与性能相关的问题。这只是我在检查编译器的汇编输出以查找我一直在编写的 C 项目中的 C 代码时无意识地发现（并且无法解释）的东西。再次感谢。感谢彼得为这个问题提出了一个更好的标题。

原始问题：

下面的小 C 函数将条目a向量复制到. 应用深度 2 的手动循环展开。nb

#include <stddef.h>

void foo (ptrdiff_t n, double *a, double *b) {
  ptrdiff_t i = 0;
  ptrdiff_t nr = n & 1;
  n -= nr;                  // `n` is an even integer
  while (i < n) {
    b[i] = a[i];
    b[i + 1] = a[i + 1];
    i += 2;
    }                       // `i = n` when the loop ends
  if (nr) b[i] = a[i];
  }

它在gcc -O2（任何gcc版本 5.4+）下提供 x64 程序集。但是，我发现输出的部分注释很奇怪。为什么编译器会生成它们？

foo:
  movq %rdi, %rcx
  xorl %eax, %eax
  andl $1, %ecx
  subq %rcx, %rdi
  testq %rdi, %rdi
  jle .L11
.L12:
  movsd (%rsi,%rax,8), %xmm0
  movsd %xmm0, (%rdx,%rax,8)
  movsd 8(%rsi,%rax,8), %xmm0
  movsd %xmm0, 8(%rdx,%rax,8)
  addq $2, %rax
  cmpq %rax, %rdi           // `i` in %rax, `n` in %rdi
  jg .L12                   // the loop ends, with `i = n`, BELOW IS WEIRD
  subq $1, %rdi             // n = n - 1;
  shrq %rdi                 // n = n / 2;
  leaq 2(%rdi,%rdi), %rax   // i = 2 * n + 2;  (this is just `i = n`, isn't it?)
.L11:
  testq %rcx, %rcx
  je .L10
  movsd (%rsi,%rax,8), %xmm0
  movsd %xmm0, (%rdx,%rax,8)
.L10:
  ret

一个类似的版本使用size_t而不是ptrdiff_t给出类似的东西：

#include <stdlib.h>

void bar (size_t n, double *a, double *b) {
  size_t i = 0;
  size_t nr = n & 1;
  n -= nr;                  // `n` is an even integer
  while (i < n) {
    b[i] = a[i];
    b[i + 1] = a[i + 1];
    i += 2;
    }                       // `i = n` when the loop ends
  if (nr) b[i] = a[i];
  }

bar:
  movq %rdi, %rcx
  andl $1, %ecx
  subq %rcx, %rdi
  je .L20
  xorl %eax, %eax
.L21:
  movsd (%rsi,%rax,8), %xmm0
  movsd %xmm0, (%rdx,%rax,8)
  movsd 8(%rsi,%rax,8), %xmm0
  movsd %xmm0, 8(%rdx,%rax,8)
  addq $2, %rax
  cmpq %rax, %rdi           // `i` in %rax, `n` in %rdi
  ja .L21                   // the loop ends, with `i = n`, BUT BELOW IS WEIRD
  subq $1, %rdi             // n = n - 1;
  andq $-2, %rdi            // n = n & (-2);
  addq $2, %rdi             // n = n + 2;  (this is just `i = n`, isn't it?)
.L20:
  testq %rcx, %rcx
  je .L19
  movsd (%rsi,%rdi,8), %xmm0
  movsd %xmm0, (%rdx,%rdi,8)
.L19:
  ret

这是另一个等价物，

#include <stdlib.h>

void baz (size_t n, double *a, double *b) {
  size_t nr = n & 1;
  n -= nr;
  double *b_end = b + n;
  while (b < b_end) {
    b[0] = a[0];
    b[1] = a[1];
    a += 2;
    b += 2;
    }                       // `b = b_end` when the loop ends
  if (nr) b[0] = a[0];
  }

但是下面的程序集看起来更奇怪（尽管在 下生成-O2）。现在n,a和b都被复制了，当循环结束时，我们用 5 行代码来结束b_copy = 0?!

baz:                        // initially, `n` in %rdi, `a` in %rsi, `b` in %rdx
  movq %rdi, %r8            // n_copy = n;
  andl $1, %r8d             // nr = n_copy & 1;
  subq %r8, %rdi            // n_copy -= nr;
  leaq (%rdx,%rdi,8), %rdi  // b_end = b + n;
  cmpq %rdi, %rdx           // if (b >= b_end) jump to .L31
  jnb .L31
  movq %rdx, %rax           // b_copy = b;
  movq %rsi, %rcx           // a_copy = a;
.L32:
  movsd (%rcx), %xmm0
  addq $16, %rax
  addq $16, %rcx
  movsd %xmm0, -16(%rax)
  movsd -8(%rcx), %xmm0
  movsd %xmm0, -8(%rax)
  cmpq %rax, %rdi           // `b_copy` in %rax, `b_end` in %rdi
  ja .L32                   // the loop ends, with `b_copy = b_end`
  movq %rdx, %rax           // b_copy = b;
  notq %rax                 // b_copy = ~b_copy;
  addq %rax, %rdi           // b_end = b_end + b_copy;
  andq $-16, %rdi           // b_end = b_end & (-16);
  leaq 16(%rdi), %rax       // b_copy = b_end + 16;
  addq %rax, %rsi           // a += b_copy;   (isn't `b_copy` just 0?)
  addq %rax, %rdx           // b += b_copy;
.L31:
  testq %r8, %r8            // if (nr == 0) jump to .L30
  je .L30
  movsd (%rsi), %xmm0       // xmm0 = a[0];
  movsd %xmm0, (%rdx)       // b[0] = xmm0;
.L30:
  ret

谁能解释编译器在这三种情况下的想法？

标签： cgccassemblyx86loop-unrolling

解决方案

看起来如果我以以下方式展开循环，编译器可以生成更整洁的代码。

#include <stdlib.h>
#include <stddef.h>

void foo (ptrdiff_t n, double *a, double *b) {
  ptrdiff_t i = n & 1;
  if (i) b[0] = a[0];
  while (i < n) {
    b[i] = a[i];
    b[i + 1] = a[i + 1];
    i += 2;
    }
  }

void bar (size_t n, double *a, double *b) {
  size_t i = n & 1;
  if (i) b[0] = a[0];
  while (i < n) {
    b[i] = a[i];
    b[i + 1] = a[i + 1];
    i += 2;
    }
  }

void baz (size_t n, double *a, double *b) {
  size_t nr = n & 1;
  double *b_end = b + n;
  if (nr) b[0] = a[0];
  b += nr;
  while (b < b_end) {
    b[0] = a[0];
    b[1] = a[1];
    a += 2;
    b += 2;
    }
  }

foo:
  movq %rdi, %rax
  andl $1, %eax
  je .L9
  movsd (%rsi), %xmm0
  movsd %xmm0, (%rdx)
  cmpq %rax, %rdi
  jle .L11
.L4:
  movsd (%rsi,%rax,8), %xmm0
  movsd %xmm0, (%rdx,%rax,8)
  movsd 8(%rsi,%rax,8), %xmm0
  movsd %xmm0, 8(%rdx,%rax,8)
  addq $2, %rax
.L9:
  cmpq %rax, %rdi
  jg .L4
.L11:
  ret

bar:
  movq %rdi, %rax
  andl $1, %eax
  je .L20
  movsd (%rsi), %xmm0
  movsd %xmm0, (%rdx)
  cmpq %rax, %rdi
  jbe .L21
.L15:
  movsd (%rsi,%rax,8), %xmm0
  movsd %xmm0, (%rdx,%rax,8)
  movsd 8(%rsi,%rax,8), %xmm0
  movsd %xmm0, 8(%rdx,%rax,8)
  addq $2, %rax
.L20:
  cmpq %rax, %rdi
  ja .L15
.L21:
  ret

baz:
  leaq (%rdx,%rdi,8), %rcx
  andl $1, %edi
  je .L23
  movsd (%rsi), %xmm0
  movsd %xmm0, (%rdx)
.L23:
  leaq (%rdx,%rdi,8), %rax
  cmpq %rax, %rcx
  jbe .L22
.L25:
  movsd (%rsi), %xmm0
  addq $16, %rax
  addq $16, %rsi
  movsd %xmm0, -16(%rax)
  movsd -8(%rsi), %xmm0
  movsd %xmm0, -8(%rax)
  cmpq %rax, %rcx
  ja .L25
.L22:
  ret

推荐阅读