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

一口Linux

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

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

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

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

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

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

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

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

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

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

單一指令流單一資料流計(jì)算機(jī)（SISD）

單一指令流多資料流計(jì)算機(jī)（SIMD）

多指令流單一資料流計(jì)算機(jī)（MISD）

多指令流多資料流計(jì)算機(jī)（MIMD）例如，針對(duì)如下的代碼：
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);
}
如下圖所示：