Loop Interchange如何幫助編譯器生成更高效的可執(zhí)行代碼

編者按：C/C++代碼在編譯時，編譯器將源碼翻譯成CPU可識別的指令序列并生成可執(zhí)行代碼，而最終代碼的運行效率取決于由編譯器生成的可執(zhí)行代碼。在大部分情況下，編寫源代碼時就已經決定了程序可以在何種程度下被編譯器優(yōu)化。即使對源代碼做微小改動也可能會對編譯器生成的代碼運行效率產生重大影響。因此，源代碼的優(yōu)化可以在一定程度上幫助編譯器生成更高效的可執(zhí)行代碼。

本文將以Loop Interchange的場景為例，講述在編寫代碼時可以拿到更優(yōu)性能的書寫方式。

1. Loop Interchange 相關基本概念

1.1 訪問局部性

訪問局部性指的是在計算機科學領域中應用程序在訪問內存的時候，傾向于訪問內存中較為靠近的值。這種局部性是出現在計算機系統中的一種可預測行為，我們可以利用系統的這種強訪問局部性來進行性能優(yōu)化。訪問局部性分為三種基本形式，分別為時間局部性、空間局部性、循序局部性。

而本文主要講述的Loop Interchange主要是利用了空間局部性。空間局部性指的是，最近引用過的內存位置以及其周邊的內存位置容易再次被使用。比較常見于循環(huán)中，比如在一個數組中，如果第3個元素在上一個循環(huán)中被使用，那么本次循環(huán)中極有可能會使用第4個元素；如果本次循環(huán)確實使用第4個元素，就是命中上一次迭代所prefetch到的cache數據。

所以對于數組循環(huán)運算，可以利用空間局部性這一特征，保證兩次相鄰循環(huán)中對數組元素的訪問在內存上是更加靠近的，即循環(huán)訪問數組中的元素時stride越小，相應的性能可能會有所優(yōu)化。

那么，數組在內存上是如何存儲的呢？

1.2 Row-major 和 Column-major

Row-major 和 Column-major 是兩種將多維數組存儲在線性存儲中的方式。數組的元素在內存中是連續(xù)的；Row-major ordering代表行的連續(xù)元素在內存中彼此相鄰，而Column-major ordering則是代表列的連續(xù)元素彼此相鄰，如下圖所示。

雖然Row和Column的名稱看起來像是特指二維數組，但是Row-major和Column-major也可以推廣適用于任何維度的數組。

那么在C/C++中，數組是以以上哪種方式存儲的呢？

舉一個小例子，用cachegrind工具來展示C使用兩種不同的訪問形式的CPU的cache丟失率對比。

按行訪問：

?

#include?

int?main(){
????size_t?i,j;
????const?size_t?dim?=?1024?;
????int?matrix?[dim][dim];

????for?(i=0;i

	?

	

	按列訪問：

	?
#include?

int?main(){

????size_t?i,j;

????const?size_t?dim?=?1024?;

????int?matrix?[dim][dim];

????for?(i=0;i

	?

	

	根據上述C代碼中對相同數組的兩種不同訪問方式時cache丟失率的對比，可以說明在C/C++代碼中，數組是以Row-major形式儲存的。也就是說，如果前一步訪問了a[i][j]，那么對a[i][j+1]的訪問會命中cache。這樣就不會執(zhí)行對主存儲器的訪問，而cache比主內存快，因此遵循相應編程語言的儲存形式使其可以命中cache可能會帶來優(yōu)化。

	至于其他常用的編程語言，Fortran、MATLAB等則是默認Column-major形式。

	1.3 Loop Interchange

	Loop Interchange利用系統傾向于訪問內存中較為靠近的值的特征以及C/C++ Row-major的特點，通過改變循環(huán)嵌套中兩個循環(huán)之間的執(zhí)行順序，增加整體代碼空間局部性。此外，它還可以啟用其他重要的代碼轉換，例如，Loop Reordering就是Loop Interchange擴展到兩個以上循環(huán)被重新排序時的優(yōu)化。在LLVM中，Loop Interchange需要通過使能-mllvm -enable-loopinterchange選項啟用。

	2. 優(yōu)化示例

	2.1 基礎場景

	簡單看下面一個矩陣運算的示例：

	原始代碼：

	?
??for(int?i?=?0;?i?

	?

	試著把jk兩層循環(huán)進行Loop Interchange之后的代碼：

	?
??for(int?i?=?0;?i?

	?

	可以發(fā)現，在原始代碼中，最內層的k每次迭代，C要訪問的數據不變，A每次訪問的stride為1，大概率命中cache，但B由于每次訪問的stride為1024，幾乎每次都會cache miss。Loop Interchange之后，j位于最內層循環(huán)，每次迭代時A每次要訪問的數據不變，C和B每次訪問的stride為1，都會有很大概率命中cache，cache命中率大大增加。

	那么cache命中率是否真的增加，以及兩者的性能又如何呢？

	原始代碼：

	?
$?time?-p?./a.out?


	?

	

	?
$?sudo?perf?stat?-r?3?-e?cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads?./a.out

	?

	

	Loop Interchange后的結果如下：

	?
$?time?-p?./a.out?


	?

	

	?
$?sudo?perf?stat?-r?3?-e?cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads?./a.out


	?

	

	兩者相比：

	L1-dcache-loads的數目差不多，因為要訪問的數據總量差不多；

	L1-dcache-load-misses所占L1-dcache-loads的比例在進行Loop Interchange代碼修改后降低了將近10倍。

	同時，性能數據上也能帶來接近9.5%的性能提升。

	2.2 特殊場景

	當然，在實際使用時，并不是所有的場景都是如2.1中所示的那種工整的可Loop Interchange場景。

	?
for?(?int?i?=?0;?i?

	?

	如上述場景，如果N是超大數組，那么Loop Interchange理論上可以帶來較大收益；但由于兩層循環(huán)中間增加一個分支判斷，導致原本可以Loop Interchange的場景無法實現。

	針對這種場景，可以考慮將中間的分支判斷邏輯剝離，可以先保證Loop Interchange使得數組res在連續(xù)內存上進行訪問；至于中間的判斷分支邏輯，可以在Loop Interchange兩層循環(huán)后再進行回退。

	?
for?(?int?m?=?0;?m?

	?

	當然，這樣的源碼修改也需要考慮cost是否值得，如果該if分支進入頻率非常高，那么之后回退帶來的cost也會較大，可能就需要重新考慮Loop Interchange是否值得；反之，如果分支進入頻率非常低，那么Loop Interchange的實現還是可以帶來可觀的收益的。

	3. 畢昇編譯器在LLVM社區(qū)的貢獻

	畢昇編譯器團隊在LLVM社區(qū)中對Loop Interchange pass也做出了不小的貢獻。團隊從legality、profitability等方面對Loop Interchange pass做了全方位的增強，同時也對該pass所支持的場景做了大量的擴展。在Loop Interchange方面，近兩年來團隊小伙伴為社區(qū)提供了二十余個主要的patch，包含Loop Interchange，以及相關的dependence analysis、loop cache analysis、delinearization等分析和優(yōu)化的增強。簡單舉幾個例子：

	D114916 [LoopInterchange] Enable loop interchange with multiple outer loop indvars (https://reviews.llvm.org/D114916)

	D114917 [LoopInterchange] Enable loop interchange with multiple inner loop indvars (https://reviews.llvm.org/D1149167)

	這兩個patch將Loop Interchange的應用場景擴展到內層或者外層循環(huán)中包含不止一個induction variable的情況：

	?
for?(c?=?0,?e?=?1;?c?+?e?

	?

	D118073 [IVDescriptor] Get the exact FP instruction that does not allow reordering (https://reviews.llvm.org/D118073)

	D117450 [LoopInterchange] Support loop interchange with floating point reductions (https://reviews.llvm.org/D117450)

	這兩個patch將Loop Interchange的應用場景擴展到支持浮點類型的reduction計算的場景：

	?
double?matrix[dim][dim];
for?(j=0;j

	?

	D120386 [LoopInterchange] Try to achieve the most optimal access pattern after interchange (https://reviews.llvm.org/D120386)

	這個patch增強了Interchange的能力使編譯器能夠將循環(huán)體permute成為全局最優(yōu)的循環(huán)順序：

	?
void?f(int?e[100][100][100],?int?f[100][100][100])?{
??for?(int?a?=?0;?a?

	?

	=>

	?
void?f(int?e[100][100][100],?int?f[100][100][100])?{
??for?(int?c?=?0;??c?

	?

	D124926 [LoopInterchange] New cost model for loop interchange (https://reviews.llvm.org/D124926)

	這個patch為loop interchange提供了一個全新的，功能更強的cost model，可以更準確地對loop interchange的profitability做出判斷。

	結語

	如果想要盡可能的利用Loop Interchange優(yōu)化，那在書寫C/C++代碼時，請盡可能保證每個迭代之間對數組或數列的訪問stride越小越好；stride越接近1，空間局部性就越高，自然cache命中率也會更高，在性能數據上也可以拿到更理想的收益。另外，由于C/C++的存儲方式為Row-major ordering，所以在訪問多維數組時，請注意內層循環(huán)要為Column才能拿到更小的stride。　　

	? ? ? 審核編輯：彭靜