LLVM 中的自动向量化

LLVM 有两个向量化器：

循环向量化器：作用于循环，这些向量化器使用不同的技术进行向量化。
SLP 向量化器：将代码中的多个标量合成向量。

两个向量化器都是默认启用的。

循环向量化器

使用

循环向量化器默认启用。你可以通过 -vectorize-loops 选项来禁用它：

$ clang ... -fno-vectorize  file.c

命令行标志

循环向量化使用成本模型来决定最佳向量化因子和展开因子。但是，向量化的用户可以强制向量化使用特定值。'clang' 和 'opt' 都支持：

用户可以通过命令行标志“-force-vector-width”控制向量化 SIMD 宽度：

$ clang  -mllvm -force-vector-width=8 ...
$ opt -loop-vectorize -force-vector-width=8 ...

用户可以通过命令行标志“-force-vector-interleave”控制展开因子。

$ clang  -mllvm -force-vector-interleave=2 ...
$ opt -loop-vectorize -force-vector-interleave=2 ...

progma loop 提示指令

#pragma clang loop 指令允许为后续的 for、while、do-while 或 c++11 范围 for 循环指定循环向量化提示。该指令可以启用或禁用向量和交错。还可以手动指定向量宽度和交错计数。以下示例显式地启用了向量和交错：

#pragma clang loop vectorize(enable) interleave(enable)
while(...) {
  ...
}

以下示例通过指定向量宽度和交错计数来隐式启用向量化并交错：

#pragma clang loop vectorize_width(2) interleave_count(2)
for(...) {
  ...
}

请参阅 Clang 语言扩展的详细信息。

诊断

许多循环无法向量化，包括具有复杂控制流、不可向量化类型和不可向量化调用的循环。循环向量化器会生成优化备注，可以使用命令行选项查询这些备注，以识别和诊断循环向量化器跳过的循环。

使用以下方式启用优化备注：

-Rpass=loop-vectorize 标识成功向量化循环。

-Rpass-missed=loop-vectorize 标识向量化失败的循环，并指示是否指定了向量化。

-Rpass-analysis=loop-vectorize 标识导致向量化失败的语句。如果此外还提供 -fsave-optimization-record ，则可能列出多个向量化失败的原因（此行为将来可能会改变）。

考虑以下循环：

#pragma clang loop vectorize(enable)
for (int i = 0; i < Length; i++) {
  switch(A[i]) {
  case 0: A[i] = i*2; break;
  case 1: A[i] = i;   break;
  default: A[i] = 0;
  }
}

命令行 -Rpass-missed=loop-vectorize 打印出注释：

no_switch.cpp:4:5: remark: loop not vectorized: vectorization is explicitly enabled [-Rpass-missed=loop-vectorize]

并且命令行 -Rpass-analysis=loop-vectorize 指出 switch 语句不能向量化。

no_switch.cpp:4:5: remark: loop not vectorized: loop contains a switch statement [-Rpass-analysis=loop-vectorize]
  switch(A[i]) {
  ^

功能

LLVM 循环向量化器具有许多功能，允许它向量化复杂的循环。

具有未知迭代次数的循环

循环向量化器支持具有未知迭代次数的循环。在下面的循环中，迭代 start 和 finish 点是未知的，循环向量化器有一种机制来向量化不以零开始的循环。在这个例子中，‘n’ 可能不是向量宽度的倍数，向量化器必须将最后几次迭代作为标量代码执行。保留循环的标量副本会增加代码大小。

void bar(float *A, float* B, float K, int start, int end) {
  for (int i = start; i < end; ++i)
    A[i] *= B[i] + K;
}

指针运行时检查

在下面的示例中，如果指针 A 和 B 指向连续的地址，那么无法向量化代码，因为 A 的一些元素会在从数组 B 读取之前被写入。

一些程序员使用 ‘restrict’ 关键字来通知编译器指针是互不重叠的，但在我们的示例中，循环向量器没有办法知道指针 A 和 B 是唯一的。循环向量器通过在运行时检查数组 A 和 B 是否指向不重叠的内存位置来处理这个循环。如果数组 A 和 B 重叠，则执行循环的标量版本。

void bar(float *A, float* B, float K, int n) {
  for (int i = 0; i < n; ++i)
    A[i] *= B[i] + K;
}

规约

在这个例子中，变量 sum 在循环中迭代使用。这通常会阻止向量化。但向量化器可以检测到 sum 是一个规约变量。变量 sum 变成一个整数向量，在循环结束时，数组的元素被加到一起以创建正确的结果。我们支持多种不同的规约操作，比如加法、惩罚、XOR、AND 和 OR。

int foo(int *A, int n) {
  unsigned sum = 0;
  for (int i = 0; i < n; ++i)
    sum += A[i] + 5;
  return sum;
}

当使用 -ffast-math 时，我们支持浮点规约操作。

归纳

在这个例子中，归纳变量 i 的值被保存到一个数组中。循环向量化器知道如何向量化归纳变量。

void bar(float *A, int n) {
  for (int i = 0; i < n; ++i)
    A[i] = i;
}

if 转换

循环向量化器能够“展平”代码中的条件语句并生成一个指令流。循环向量化器支持最内层循环中的任何控制流。最内存循环可以包含复杂的 if, else 甚至 goto 嵌套：

int foo(int *A, int *B, int n) {
  unsigned sum = 0;
  for (int i = 0; i < n; ++i)
    if (A[i] > B[i])
      sum += A[i] + 5;
  return sum;
}

指针归纳变量

此示例使用了标准 C++ 库中的“accumulate”函数。此循环使用 C++ 迭代器，迭代器是指针，而不是整型索引。循环向量化器可以检测指针归纳变量并可以向量化此循环。这个特性很重要，因为许多 C++ 程序使用迭代器：

int baz(int *A, int n) {
  return std::accumulate(A, A + n, 0);
}

反向迭代器

循环向量化器可以向量化计数向后的循环。

void foo(int *A, int n) {
  for (int i = n; i > 0; --i)
    A[i] +=1;
}

Scatter/Gather

循环向量器可以将离散内存的读写操作向量化成标量代码：

void foo(int * A, int * B, int n) {
  for (intptr_t i = 0; i < n; ++i)
      A[i] += B[i * 4];
}

在许多情况下成本模型会告诉 LLVM 这不是有益的，LLVM 只有在使用 -mllvm -force-vector-width=# 的才能强制进行向量化这种代码。

混合类型的向量化

循环向量化器可以向量化混合类型的程序。向量化器成本模型可以估计类型转换的成本，并决定是否向量化是有利可图：

void foo(int *A, char *B, int n) {
  for (int i = 0; i < n; ++i)
    A[i] += 4 * B[i];
}

全局结构别名分析

对全局结构的访问也可以进行向量化，使用别名分析来确保访问不会别名化。还可以在指向结构成员的指针访问上添加运行时检查。

许多变体都得到了支持，但一些依赖于忽略未定义行为（如其他编译器所做的那样）的变体仍然没有被向量化。

struct { int A[100], K, B[100]; } Foo;

void foo() {
  for (int i = 0; i < 100; ++i)
    Foo.A[i] = Foo.B[i] + 100;
}

函数调用的向量化

循环向量化器可以向量化内置数学函数。请参见表格下方列出的这些函数：

pow

exp

exp2

sin

cos

sqrt

log

log2

log10

fabs

floor

ceil

fma

trunc

nearbyint

fmuladd

若库函数访问外部状态，例如 errno，则优化器可能无法向量化这些与内置函数对应的库函数，为了更好的优化 C/C++ 数学库函数，请使用 -fno-math-errno。

循环展开器知道目标平台的特殊指令，并且会展开包含映射到这些指令的函数调用的循环。例如，若 SSE4.1 roundps 指令可用，则下面的循环会在 Intel x86 上展开：

void foo(float *f) {
  for (int i = 0; i != 1024; ++i)
    f[i] = floorf(f[i]);
}

这些数学函数只有在使用指定的目标向量库时才能够向量化，该库提供了该数学函数的向量实现。使用 clang 时，通过命令行选项 -fveclib 处理，该选项使用下面的向量库之一： “accelerate,libmvec,massv,svml,sleef,darwin_libsystem_m,armpl,amdlibm”

$ clang ... -fno-math-errno -fveclib=libmvec file.c

向量化过程中的部分展开

现代处理器具有多个执行但愿，只有包含高度并行性的程序才能充分利用整个机器的整个宽度。循环向量化器通过执行循环的部分展开来增加指令集并行性（ILP）。

在下面的示例中，整个数组被累加到变量 sum 中。其效率低下，因为处理器只能使用单个执行端口。通过展开代码，循环向量化器允许同时使用两个或多个执行端口：

int foo(int *A, int n) {
  unsigned sum = 0;
  for (int i = 0; i < n; ++i)
      sum += A[i];
  return sum;
}

循环展开器使用成本模型来决定何时展开循环是有利可图的。展开循环的决定取决于寄存器压力和生成的代码大小。

尾部向量化

在向量化循环时，通常需要一个标量尾部（epilogue）循环来执行循环的尾迭代，如果循环的迭代次数未知或不能被向量化和解卷积因子整除。当向量化和解卷积因子较大时，具有较小迭代次数的循环可能会花费大部分时间在标量（而不是向量）代码中。为了解决这个问题，内部循环向量化器增强了一个功能，允许它以向量和解卷积因子的组合来向量化尾部循环，这使得具有较小迭代次数的循环更有可能仍然在向量化代码中执行。下图显示了具有运行时检查的典型尾部向量化循环的控制流图。如图所示，控制流结构避免了重复运行时指针检查，并优化了具有非常小迭代次数的循环的路径长度。

早期退出向量化

在具有单个早期退出的循环向量化中，早期退出之后的循环块会被条件化处理，并且向量循环将始终通过锁存器退出。如果早期退出被触发，向量循环的后继块（ middle.split 下方）将通过一个中间块（ vector.early.exit 下方）分支到早期退出块。这个中间块负责计算在早期退出块中使用的任何循环定义变量的退出值。否则， middle.block 会在来自锁存器的退出块或标量余下循环之间进行选择。

SLP 向量化器

SLP 向量化（也称为超级字级并行）的目标是将类似的独立指令组合成向量指令。内存访问、算术运算、比较运算、PHI 节点等都可以使用这种技术进行向量化。

例如，以下函数对其输入 (a1, b1) 和 (a2, b2) 执行非常相似的运算。基本块向量化器可以将这些合并为向量操作。

void foo(int a1, int a2, int b1, int b2, int *A) {
  A[0] = a1*(a1 + b1);
  A[1] = a2*(a2 + b2);
  A[2] = a1*(a1 + b1);
  A[3] = a2*(a2 + b2);
}

SLP 向量化器自底向上处理代码，跨基本块搜索要组合的标量。

使用

SLP 向量化器默认启用，但可以通过 clang 使用命令行标志禁用：

$ clang -fno-slp-vectorize file.c