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

一口Linux

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

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

應(yīng)當使用最快的可使用指令來實現(xiàn)目標；也即循環(huán)內(nèi)指令最少；

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

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

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

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

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

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

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

單一指令流單一資料流計算機（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);
}
如下圖所示：