循环展开（Loop Unrolling）

循环展开（Loop Unrolling）是一种优化技术，它通过减少循环的迭代次数来减少循环的开销。循环展开的基本思想是将循环体中的多次迭代合并为一次迭代，从而减少循环的迭代次数。循环展开的优点是可以减少循环的开销，缺点是会增加代码的长度，可能会增加缓存的失效率。

一个直观的例子

假设有如下的循环：

void add(float *a, float *b, float *c, int n) {
  for (int i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
  }
}

我们可以将这个循环展开为：

void add(float *a, float *b, float *c, int n) {
  for (int i = 0; i < n; i+=2) {
    c[i] = a[i] + b[i];
    c[i+1] = a[i+1] + b[i+1];
  }
}

这样，每次迭代处理两个元素，减少了循环的迭代次数。但如果n不能被2整除，我们需要在循环的最后处理剩余的元素：

void add(float *a, float *b, float *c, int n) {
  for (int i = 0; i < n; i+=2) {
    c[i] = a[i] + b[i];
    c[i+1] = a[i+1] + b[i+1];
  }
  for (int i = n-n%2; i < n; i++) {
    c[i] = a[i] + b[i];
  }
}

为什么要这样做？

循环展开对于编译器优化非常有意义，如果循环体中的操作有些可以消除冗余，可以被矢量化，或者可以被其他优化技术处理，那么循环展开可以通过增加代码长度，来间接增加编译器的优化空间。例如，下面这个循环：

void fma(float *a, float *b, float *c, int n, float scale, float bias) {
  for (int i = 0; i < n; ++i) {
    float t = a[i] * scale;
    b[i] = t + bias;
    c[i] = t + bias;  // 与 b[i] 做了相同的计算
  }
}

展开后可以发现，这里有冗余的操作，可以被编译器优化掉：

void fma(float *a, float *b, float *c, int n, float scale, float bias) {
  for (int i = 0; i < n; i += 2) {
    float t0 = a[i]     * scale;
    float s0 = t0 + bias;   // t0 + bias 只算一次
    b[i]     = s0;
    c[i]     = s0;

    float t1 = a[i + 1] * scale;
    float s1 = t1 + bias;
    b[i + 1] = s1;
    c[i + 1] = s1;
  }
  // 处理 n 为奇数时的剩余元素 ...
}

展开后循环体变成更长的直线代码，重复的 t + bias 一目了然，值编号（CSE）可以轻松将其合并；同时每次迭代处理两个元素，也为 SIMD 矢量化创造了条件。