從編譯器的角度來看循環(huán)優(yōu)化

一口Linux

今天我們來聊一聊循環(huán)優(yōu)化，看看編譯器是如何來做循環(huán)優(yōu)化的，以及我們可以如何做循環(huán)優(yōu)化。
完美的循環(huán)在開始之前，我們可以思考一下，什么樣的循環(huán)是編譯器需要的？或者說編譯器會想要去生成什么樣的代碼呢？
一般來說，理想的循環(huán)有如下的特性：

只執(zhí)行必要的工作，移除所有無關和不必要的計算；

應當使用最快的可使用指令來實現目標；也即循環(huán)內指令最少；

循環(huán)應盡量使用SIMD指令；SIMD指令(Single instruction, multiple data)能夠并行的處理多個數據，例如同時進行四個同類型變量的加法；

指令應當盡可能平衡的使用CPU單元；例如如果循環(huán)中的除法指令過多，就會導致整個循環(huán)在等待除法指令的執(zhí)行從而成為性能瓶頸；

循環(huán)內的內存訪問模式應當盡可能好；好的訪存模式能夠帶來好的性能；這是編譯器嘗試去生成代碼的目標，同樣的，這些目標對于我們自己進行循環(huán)優(yōu)化也有借鑒意義。
性能絆腳石接著，我們需要了解，什么會影響編譯器循環(huán)優(yōu)化的效果。兩個重要的因素是函數調用(function calls)和指針別名(pointer aliasing)。這是因為對于編譯器而言，優(yōu)化的前提是不影響代碼的正確運行，這使得編譯器在處理關鍵代碼中的變量是常數或者比較獨立的變量時會有比較好的優(yōu)化效果，這個時候上下文更短，更能夠進行判斷和分析；然而在存在函數調用和指針別名的情況下，編譯器很難判斷做出激進的優(yōu)化會不會影響代碼的正確運行，因而編譯器會選擇保守的優(yōu)化。
函數調用函數調用成為性能絆腳石的原因是因為函數調用可能會改變內存的情況，例如如下的代碼：
for (int i = 0; i if (debug) {
       A;
       printf("The data is NaN
");
   } else {
       B;
   }
}
這里debug變量可能是全局變量，也可能是堆上分配的變量，或者類的成員。在這些情況下，函數可能會修改debug的值。對于開發(fā)者而言，debug是否會變化是可以確定的，但是對于編譯器而言是比較難確定的。如果編譯器知道debug的值不會發(fā)生變化的話，編譯器可以嘗試將這個代碼做如下優(yōu)化：
if (debug) {
    for (int i = 0; i printf("The data is NaN
");
    }
} else {
    for (int i = 0; i ?如果能確定debug的值可以在編譯時直接變成單循環(huán)。
然而，編譯器并不知道這個debug變量是否會發(fā)生變化，所以其會假設函數printf()可能會修改debug的值，因此，編譯器不會像上面那樣去進行優(yōu)化。我們可以通過設置局部變量的方式讓編譯器了解到這個變量并不會發(fā)生變化：
bool debug_local = debug;
for (int i = 0; i if (debug_local) {
       A;
       printf("The data is NaN
");
   } else {
       B;
   }
}
由于是局部變量，所以不會在調用的函數中被修改，而其他的諸如全局變量、堆上變量等，可能會在函數中被修改。
此外，在有函數出現的情況下，編譯器自身的優(yōu)化能力就會下降。例如下面的例子：
double add(double a, double b) {
   return a + b;
}
for (int i = 0; i 如果編譯器能夠將add函數進行內聯，那么編譯器就可以嘗試做更多的優(yōu)化；但是如果add函數無法被內聯，編譯器就只能進行標量版本的循環(huán)，每次都去調用add函數。而一旦涉及到函數的調用，就需要進行跳轉，過多的跳轉會影響到程序的性能。
?可以通過LTO(Link Time Optimization)來進行優(yōu)化。
指針別名第二個影響性能的因素是指針別名(pointer aliasing)。在存在指針別名的情況下，編譯器不能將數據存儲在寄存器中，而必須將其存儲在內存中。這導致了訪存的低效。此外，指針別名也會影響循環(huán)矢量化。那么什么是指針別名呢？考慮如下的例子：
for (int i = 0; i 0;
   for (int j = 0; j 在這個例子中，a和b在存儲上沒有關聯，因而在內循環(huán)上可以進行一些優(yōu)化（見后文）。然而如果a和b有一定關聯，例如b指向的是a的一行，也即b[3]可能等于a[2][3]，那么這時候編譯器就不會進行優(yōu)化，從而生成性能比較差的代碼。
優(yōu)化前-內聯在編譯器開始優(yōu)化你的代碼前，編譯器會先進行內聯操作。內聯是指將函數調用轉換成編碼的格式，例如前文提到的：
double add(double a, double b) {
   return a + b;
}
for (int i = 0; i 可以將其內聯成：
for (int i = 0; i 內聯自身是一個小的編譯器優(yōu)化，因為能夠幫助我們減少調用函數的開銷。內聯更大的好處在于能夠為編譯器后續(xù)的優(yōu)化提供基礎。如果短函數定義與調用在同一文件中，編譯器就會嘗試去做內聯操作。
基礎優(yōu)化將變量維持在寄存器中在計算機中，寄存器訪存是最快的訪存方式，因此如果我們能夠盡可能的操作寄存器來存儲變量，就可以提高訪存的時間從而提高型男。
編譯器有專門的寄存器分配器(register allocator)來進行寄存器的分配。由于CPU中寄存器的數量是有限的，編譯器需要基于某些特征來判斷哪些變量適合放在寄存器中，哪些變量適合放在內存里。
有兩種情況會阻止編譯器將變量存在寄存器中：

變量過多：如果在循環(huán)中我們有過多的未使用變量，編譯器就無法將它們都存儲咋寄存器中。因此寄存器需要考慮將部分暫時用不到的變量放在內存中，在需要的時候再將這個變量加載到寄存器中，這種現象稱為寄存器溢出(register spilling)。

指針別名：如果存在指向標量A的指針B，那么我們可以通過直接修改A或者通過指針B來修改A的值。寄存器不會將A放在寄存器中，因為通過指針對其進行的修改將會丟失。針對這類標量的操作，都會遵循加載、修改、存儲的流程進行修改。?這里修改丟失是因為如果通過指針修改了A的值，仍然會使用寄存器中存儲的值去進行操作，這就導致了丟失現象的發(fā)生。
針對寄存器溢出現象，我們可以將循環(huán)拆分成多個循環(huán)來進行操作。那么我們該如何判斷是否存在寄存器溢出現象呢？我們可以通過使用編譯器優(yōu)化報告來判斷是否存在這種現象。
?后續(xù)將有文章介紹編譯器優(yōu)化報告相關內容。
C和C++都有嚴格的別名機制，這意味著當循環(huán)中同時存在標量和指向標量的指針時，比如存在int *p和int i時，除非我們能夠保證p不會指向i，否則寄存器會假設p可能指向i從而將i存儲在內存中。那么我們該如何讓編譯器知道變量不會被指針指向呢？對于全局變量、靜態(tài)變量和類成員等，我們可以通過復制成局部變量來讓編譯器意識到該變量不會被指針指向和修改。
移除無關運算在這個步驟，編譯器的目標是盡可能的移除循環(huán)中無用的部分。
無用計算有些計算并不需要，我們可以直接移除掉。如下所示：
void add(int* a, int* b) {
    (*a)++;
    if (b) (*b)++;
}
for (int i = 0; i nullptr);
}
在編譯器進行內聯以后，由于傳給add函數的參數int *b始終為nullptr，所以編譯器可以直接移除掉這部分的判斷：
for (int i = 0; i 在編譯的過程中，編譯器會盡可能的忽略掉不會執(zhí)行的代碼，也即所謂的死代碼消除(dead code elimination)。
循環(huán)不變量循環(huán)不變量(Loop invariant computation)是指在循環(huán)中需要，但是不需要每次都在循環(huán)中計算的部分。例如如下的代碼：
for (int i = 0; i switch (operation) {
        case ADD: a+= x * x; break;
        case SUB: a-= x * x; break;
    }
}
這個循環(huán)中，operation和x都是循環(huán)無關變量，因為他們不會隨著循環(huán)的發(fā)生而改變。編譯器會自動的計算出x*x的值，從而減少重復運算。只要編譯器能夠確定表達式是循環(huán)不變的，就會盡可能的進行這種優(yōu)化。稱為循環(huán)不變量代碼移動（loop invariant code motion）。
當涉及到operation的部分，情況會稍微有一些復雜。因為operation的值決定了整個函數的控制流，針對這種情況，編譯器會嘗試對不同的控制流創(chuàng)建循環(huán)：
auto x_2 = x * x;
if (operation == ADD) {
    for (int i = 0; i else if (operation == SUB) {
    for (int i = 0; i 這種轉換成為循環(huán)分裂(loop unswitching)。與前者相反的是，編譯器針對循環(huán)分裂采取比較保守的策略。隨著判斷變量的增多，循環(huán)分裂出來的代碼也會指數級增長。
這兩種優(yōu)化的主要難點在于如何尋找循環(huán)不變量。在編譯器無法進行準確的判斷的時候，編譯器往往偏向保守。
迭代器相關變量迭代器相關變量(Iterator variable dependent computation)是指依賴于迭代器變量的值。如下所示：
for (int i = 0; i auto min_val = a;
    if (i != 0) {
        min_val = std::min(a[i - 1], min_val);
    }
    if (i != (n - 1)) {
        min_val = std::min(a[i + 1], min_val);
    }
    b = min_val;
}
兩個判斷條件都非常的依賴于迭代器i的值，它們并不依賴于循環(huán)中的數據。因此，我們可以將它們移出循環(huán)并進行特殊判斷：
b[0] = std::min(a[0], a[1]);
for (int i = 1; i 1; i++) {
    auto min_val = a;
    min_val = std::min(a[i - 1], min_val);
    min_val = std::min(a[i + 1], min_val);
    b = min_val;
}
b[n - 1] = std::min(a[n - 2], a[n - 1]);
編譯器比較少的進行這種優(yōu)化。
使用更廉價(cheaper)的指令編譯器在生成代碼時盡可能的生成總開銷低的指令。常見的優(yōu)化成為變量歸納（induction variables）。如下：
for (int i = 0; i 3;
}
在循環(huán)中，i * 3的值隨著迭代器i而變化，因此，與其每次都進行乘法計算，編譯器嘗試可以通過開銷更低的加法運算實現：
tmp = 0;
for (int i = 0, int tmp = 0; i 3;
}
這在訪問數組元素的情況下特別有用。例如我們有一個MyClass類，每次進行跨對象訪問：
class MyClass {
    double a;
    double b;
    double c;
};
for (int i = 0; i 1.0;
}
對于a.b，會被轉換成(a+i*sizeof(MyClass)+8)。在這種情況下，編譯器知道第一個元素是a + 8，下一個元素的地址偏移sizeof(MyClass)，每次只需要采取加法計算新的地址，而不需要每次都進行乘法運算。
循環(huán)展開及相關優(yōu)化在做完前面提到的基礎優(yōu)化后，編譯器進入到優(yōu)化的下一階段。下一階段就是循環(huán)展開（loop unrolling）階段。例如如下的代碼：
for (int i = 0; i 2;
    b_val = load(b + index);
    store(a + i, b_val);
}
當這個循環(huán)迭代次數非常少的時候，循環(huán)操作本身的開銷和循環(huán)內部操作的開銷可能是一致的，在這種情況下，我們需要進行循環(huán)展開操作：
for (int i = 0; i 2;
    b_val = load(b + index);
    store(a + i, b_val);
    i++;
    index = i / 2;
    b_val = load(b + index);
    store(a + i, b_val);
    i++;
    index = i / 2;
    b_val = load(b + index);
    store(a + i, b_val);
    i++;
    index = i / 2;
    b_val = load(b + index);
    store(a + i, b_val);
    i++;
}
在這種情況下，我們提高了循環(huán)內部的工作量，相對減少了循環(huán)操作的開銷。展開有兩種好處，一是可以減少開銷，二是可以讓我們進行一些額外的優(yōu)化。例如在上面的例子中，i/2和(i+1)/2在i是偶數的情況下一致，就可以刪除一些不必要的負載：
for (int i = 0; i 2;
    b_val = load(b + index);
    store(a + i, b_val);
    i++;
    store(a + i, b_val);
    i++;
    index = i / 2;
    b_val = load(b + index);
    store(a + i, b_val);
    i++;
    store(a + i, b_val);
    i++;
}
在進行優(yōu)化后，我們只需要進行兩個load操作，而原來需要四次load操作。
此外，編譯器在基本塊級別上進行指令調度，進行循環(huán)展開可以增加基本塊的大小，從而調高了指令調度的可能。隨著基本塊大小的增加，編譯器可以更好地調度指令，目標是增加可用的指令級并行性，以更平衡的方式使用CPU資源等。
循環(huán)展開有如下的一些缺點：

循環(huán)展開增加了內存子系統(tǒng)的負載，特別是指令緩存和指令解碼單元。指令緩存和數據緩存類似，容量是有限的，當循環(huán)內部過大的時候，會出現較多的緩存垃圾。循環(huán)的前半部分指令后續(xù)還會被用到，但是因為緩存容量的問題被丟棄，這樣會產生miss的情況。這會降低指令的取指譯碼速度，因此編譯器在循環(huán)展開的時候會比較保守。

在現代CPU上，循環(huán)開銷可以忽略不急，因此，較為激進的編譯器循環(huán)展開策略已經是過去式了。在一些非常小的循環(huán)上，例如五次以內，編譯器會直接展開成為指令而不是循環(huán)。
在編譯器的早期，我們可以通過手動循環(huán)展開來獲取性能收益，但是在現代編譯器上，手動循環(huán)展開可能會阻礙其他的優(yōu)化，可以將這部分工作交給更專業(yè)的編譯器去做。例如我們可以通過pragma clang loop unroll factor(2)讓clang進行兩倍的循環(huán)展開。
循環(huán)流水(Loop pipelining)如果你對CPU流水線有一定了解，你會發(fā)現限制CPU運算速度的一個因素是指令依賴( instructions dependencies)，如果有指令A和指令B，前者的結果是后者的原數據，那么這兩者就存在依賴關系。例如：
for (int i = 0; i 循環(huán)之中包含四條指令，load指令不存在依賴現象，但是add指令一定要等待load指令執(zhí)行完才進行，同樣的，store指令也需要等待add指令指令。這些依賴關系阻礙了CPU達到它的最佳吞吐狀態(tài)，編譯器采用一種稱為循環(huán)流水線(loop pipelining)的技術來打破依賴鏈。
循環(huán)流水線有點類似于CPU中的流水線設計，將整體劃分為了多個階段，從而進行效率的提升。在這個例子中，我們可以將整個循環(huán)劃分為三個模塊：取值、計算和存儲。在單循環(huán)中，我們可以取i + 2迭代的值，計算i + 1迭代以及存儲i迭代：
val_a = load(a + 0);
val_b = load(b + 0);
val_c = add(val_a, val_b);
val_a = load(a + 1);
val_b = load(b + 1);
for (int i = 0; i 2; i++) {
    store(val_c, c + i);
    val_c = add(val_a, val_b);
    val_a = load(a + i + 2);
    val_b = load(b + i + 2);
}
store(val_c, n - 2);
val_c = add(val_a, val_b);
store(val_c, n - 1);
我們聚焦于循環(huán)內部�？梢钥吹剑�針對取值、計算和存儲三個階段，我們分別使用的是迭代i+2、i+1和i的值，這些值之間不存在任何的依賴關系，這樣能讓CPU更好的執(zhí)行它們。和流水線類似，我們需要處理開始和結果部分，這部分的時間復雜度往往是常量的，可以忽略不計。
值得注意的是，在現代CPU中，由于亂序執(zhí)行的存在，我們很難從循環(huán)流水線中取得性能優(yōu)化。
向量化(Vectorization)和相關優(yōu)化在進行了前文的優(yōu)化后，編譯器應當已經得到了一個沒有不必要計算、相對無依賴的簡潔代碼。然而，在許多情況下，可以通過向量化來提高速度。
向量化背后的基本思想是，CPU 中有特殊的向量寄存器，可以保存多個相同類型的值，例如同時對八個int進行加法運算，也就是我們常說的SIMD指令。SIMD也即Single instruction, multiple data，是計算機體系結構中費林分類法（Flynn's Taxonomy）的一種。該方法針對指令和數據進行劃分：

單一指令流單一資料流計算機（SISD）

單一指令流多資料流計算機（SIMD）

多指令流單一資料流計算機（MISD）

多指令流多資料流計算機（MIMD）例如，針對如下的代碼：
for (int i = 0; i 4) {
    double4> b_val = load4>(B + i);
    double4> c_val = load4>(C + i);
    double4> a_val = add4>(b_val, c_val);
    store4>(a_val, A + i);
}
如下圖所示：