LLVM 自動向量化

LLVM 有兩個向量化器：在迴圈上運作的 迴圈向量化器，以及 SLP 向量化器。這些向量化器專注於不同的最佳化機會，並使用不同的技術。SLP 向量化器將程式碼中找到的多個純量合併成向量，而迴圈向量化器則擴展迴圈中的指令，以對多個連續迭代進行運算。

迴圈向量化器和 SLP 向量化器預設都是啟用的。

迴圈向量化器

用法

迴圈向量化器預設為啟用，但可以使用命令列標誌透過 clang 將其停用

$ 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 ...

Pragma 迴圈提示指令

#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]) {
  ^

若要確保產生行號和欄號，請加入命令列選項 -gline-tables-only 和 -gcolumn-info。如需詳細資訊，請參閱 Clang 使用者手冊

特性

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 語句，並產生單一指令流。迴圈向量器支援最內層迴圈中的任何控制流程。最內層迴圈可能包含複雜的 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++ 函式庫的「累加」函式。此迴圈使用 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;
}

分散/收集

迴圈向量器可以向量化變成分散/收集記憶體的純量指令序列的程式碼。

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]);
}

向量化期間的部分展開

現代處理器具有多個執行單元，只有包含高度平行性的程式才能充分利用機器的整個寬度。迴圈向量器透過執行迴圈的部分展開來增加指令級平行性 (ILP)。

在以下範例中，整個陣列會累加到變數「sum」中。這樣做效率很低，因為處理器只能使用單一執行埠。透過展開程式碼，迴圈向量器允許同時使用兩個或多個執行埠。

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

迴圈向量器會使用成本模型來決定何時展開迴圈是有利的。展開迴圈的決定取決於暫存器壓力和產生的程式碼大小。

結尾向量化

向量化迴圈時，如果迴圈執行次數未知或無法被向量化和展開因子整除，通常需要一個純量餘數（結尾）迴圈來執行迴圈的尾部迭代。當向量化和展開因子很大時，執行次數較少的迴圈可能會將大部分時間花費在純量（而不是向量）程式碼中。為了 address this issue, 內部迴圈向量器增強了一項功能，允許它使用向量化和展開因子組合來向量化結尾迴圈，這使得執行次數較少的迴圈更有可能仍在向量化程式碼中執行。下圖顯示了使用運行時檢查的典型結尾向量化迴圈的 CFG。如圖所示，控制流程的結構方式避免了重複的運行時指標檢查，並優化了執行次數非常少的迴圈的路徑長度。

效能

本節顯示 Clang 在一個簡單基準測試上的執行時間：gcc-loops。此基準測試是 Dorit Nuzman 從 GCC 自動向量化頁面收集的迴圈集合。

下表比較了 GCC-4.7、ICC-13 和 Clang-SVN 在 -O3 下啟用和未啟用迴圈向量化的情況，針對「corei7-avx」進行了調整，並在 Sandybridge iMac 上運行。Y 軸顯示時間（以毫秒為單位）。越低越好。最後一欄顯示所有內核的幾何平均值。

以及使用相同配置的 Linpack-pc。結果為 Mflops，越高越好。

持續發展方向

向量化計劃

對 LLVM 迴圈向量器的過程進行建模並升級其基礎架構。

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