前言

最近遇到一个性能问题，与Auto-Vectorization in LLVM有关，翻译一下官方介绍
http://llvm.org/docs/Vectorizers.html

简单一句话概括：将代码通过编译矢量优化，编译成运行速度更快的机器码。

一、Auto-Vectorization in LLVM

LLVM有两个矢量器：The Loop Vectorizer 循环矢量器（在循环上运行）和The SLP Vectorizer SLP矢量器。这些矢量器关注不同的优化机会，使用不同的技术。SLP矢量器将代码中发现的多个标量合并为向量，而循环向量器则扩展循环中的指令，以在多个连续迭代中操作。

默认情况下，循环矢量器和SLP矢量器都处于启用状态。

二、The Loop Vectorizer

2.1 使用方法

默认情况下启用循环矢量器，但可以使用命令行标志通过clang禁用它：

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

Command line flags

循环矢量器使用成本模型来确定最佳矢量化因子和展开因子。但是，矢量器的用户可以强制矢量器使用特定的值。“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 ...

Pragma loop hint directives

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语言拓展

2.2 诊断

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

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

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

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

-Rpass analysis=loop vectorize标识导致矢量化失败的语句。如果另外提供了-fsave优化记录，则可能会列出导致矢量化失败的多种原因（这种行为在将来可能会发生变化）。

考虑以下循环：

#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]

而命令行-rpassanalysis=loop vectorize表示switch语句不能矢量化。

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

为了确保生成行和列号，包括命令行选项-gline tables only和-gcolumn info。详见《Clang用户手册》

2.3 功能

LLVM循环矢量器有许多功能，允许它对复杂的循环进行矢量化。

Loops with unknown trip count

循环矢量器支持具有未知行程计数的循环。在下面的循环中，迭代的开始点和结束点是未知的，循环向量器有一种机制来对不从零开始的循环进行矢量化。在这个例子中，“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;
}

Runtime Checks of Pointers

在下面的例子中，如果指针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;
}

Reductions

在本例中，sum变量由循环的连续迭代使用。通常，这会阻止矢量化，但矢量器可以检测到“sum”是一个缩减变量。变量“sum”变成一个整数向量，在循环结束时，数组的元素被加在一起以创建正确的结果。我们支持许多不同的归约运算，例如加法、乘法、异或和或。

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

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

Inductions

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

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

If Conversion

循环向量器能够“展平”代码中的IF语句并生成单个指令流。循环向量器支持最内层循环中的任何控制流。最里面的循环可能包含IFs、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;
}

Pointer Induction Variables

这个例子使用标准c++库的“累加”函数。这个循环使用C++迭代器，这些指针是指针，而不是整数索引。循环矢量器检测指针感应变量，并对该循环进行矢量化。这个特性很重要，因为许多C++程序使用迭代器。

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

Reverse Iterators

循环向量器可以对倒数循环进行矢量化。

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

Scatter / Gather

循环向量器可以将代码矢量化，使其成为分散/聚集内存的标量指令序列。

int 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=#”时将这些代码矢量化。

Vectorization of Mixed Types

循环矢量器可以对混合类型的程序进行矢量化。矢量化成本模型可以估计类型转换的成本，并决定矢量化是否有益。

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

Global Structures Alias Analysis

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

支持许多变体，但是有些依赖于未定义行为被忽略的变体（就像其他编译器一样），仍然没有被矢量化。

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

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

Vectorization of function calls

循环矢量器可以对内部数学函数进行矢量化。有关这些函数的列表，请参见下表。

请注意，如果库调用访问外部状态（如“errno”），优化器可能无法将与这些内部函数对应的数学库函数矢量化。为了更好地优化C/C++数学库函数，使用“-fNO数学ErrNO”。

循环向量器知道目标上的特殊指令，并将对包含映射到指令的函数调用的循环进行矢量化。例如，如果SSE4.1 roundps指令可用，则以下循环将在Intel x86上矢量化。

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

Partial unrolling during vectorization

现代处理器具有多个执行单元，只有具有高度并行性的程序才能充分利用机器的整个宽度。循环向量器通过执行循环的部分展开来提高指令级并行度（ILP）。

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

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

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

Epilogue Vectorization

在对循环进行矢量化时，如果循环行程计数未知或不能平均分配矢量化和展开因子，则通常需要一个标量余数（epilogue）循环来执行循环的尾部迭代。当向量化和展开因子较大时，行程计数较小的循环可能会将大部分时间花费在标量（而不是矢量）代码中。为了解决这个问题，内环矢量器被增强了一个特性，允许它用矢量化和展开因子组合对尾数循环进行矢量化，这使得小行程计数循环更有可能仍然在矢量化代码中执行。下图显示了带有运行时检查的典型尾声矢量化循环的CFG。如图所示，控制流的结构避免了重复运行时指针检查，并优化了具有非常小跳闸计数的循环的路径长度。

2.3 性能提升

本节将在一个简单的基准测试gcc循环上显示Clang的执行时间。这个基准测试是来自doritnuzman的GCC自动矢量化页面的循环集合。

下面的图表比较了GCC-4.7、ICC-13和Clang SVN在-O3下有无循环矢量化，针对“corei7-avx”，运行在Sandybridge iMac上。Y轴以毫秒为单位显示时间。越低越好。最后一列显示了所有内核的几何平均值。

和配置相同的Linpack pc。结果是Mflops，越高越好。

可以看到Clang如果无循环矢量化，被GCC和ICC吊打，最好还是开启。

2.4 持续发展方向

对LLVM循环向量器的流程进行建模和基础设施升级。

三、The SLP Vectorizer

3.1 详情

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矢量器处理代码自下而上，跨越基本块，搜索标量进行组合。

3.2 用法

默认情况下，SLP矢量器处于启用状态，但可以使用命令行标志通过clang禁用它：

$ clang -fno-slp-vectorize file.c

四、尾巴

处理了好多性能优化的问题，有锁竞争的问题，有代码逻辑的问题，有跨进程等待的问题，还有各色各样的问题，我是第一次遇到相同的代码在同一个型号的cpu下运行速度有差异的问题，最后分析出来是编译器优化的问题。虽然分析的过程很曲折，但是结果很满意，自己的格局又变大了一点。