循環(huán)級優(yōu)化

循環(huán)不變量外提

循環(huán)不變量是指在循環(huán)迭代空間內(nèi)值不發(fā)生變化的變量。由于循環(huán)不變量的值在循環(huán)的迭代空間內(nèi)不發(fā)生變化，因此可將其外提到循環(huán)外僅計算一次，避免其在循環(huán)體內(nèi)重復(fù)計算。示例如下，經(jīng)過循環(huán)不變量外提后，上述循環(huán)的計算強度得到了削弱，提高了代碼的性能。

優(yōu)化前代碼：

優(yōu)化后代碼：

循環(huán)展開

循環(huán)展開是一種常用的提高程序性能方法，它通過將循環(huán)體內(nèi)的代碼復(fù)制多次的操作，進而減少循環(huán)分支指令執(zhí)行的次數(shù)，增大處理器指令調(diào)度的空間，獲得更多的指令級并行。

優(yōu)化前代碼：

優(yōu)化后代碼：

循環(huán)合并

循環(huán)合并是指將具有相同迭代空間的兩個循環(huán)合成一個循環(huán)的過程，其屬于語句層次的循環(huán)變換。但并不是所有循環(huán)都可以進行合并，循環(huán)合并需要滿足合法性要求，有些情況下循環(huán)合并會導(dǎo)致結(jié)果錯誤。

優(yōu)化前代碼：

優(yōu)化后代碼：

滿足合法性要求的循環(huán)合并可以減小循環(huán)的迭代開銷以及并行化的啟動和通信開銷，還可能增強寄存器的重用。

優(yōu)化前代碼：

優(yōu)化后代碼：

循環(huán)分段

循環(huán)分段可將單層循環(huán)變換為多層嵌套循環(huán)，循環(huán)分段的段長可根據(jù)需要選取。如果原循環(huán)是可并行化的循環(huán)，則分段后依然可以實施并行化變換。通常采用循環(huán)分段技術(shù)實現(xiàn)外層的并行化以及內(nèi)層的向量化，以達到利用系統(tǒng)多層次并行資源的目的。

優(yōu)化前代碼：

優(yōu)化后代碼：

循環(huán)交換

循環(huán)交換是一個重排序變換，在程序的向量化和并行化識別以及增強數(shù)據(jù)局部性方面都起著重要的作用。

?優(yōu)化前代碼：

優(yōu)化后代碼：

循環(huán)交換在某些情況下也能提高寄存器的重用能力。為了提高寄存器重用能力的循環(huán)交換的目的在于把攜帶依賴的循環(huán)放在最內(nèi)層的位置，使可以被重用的值保留在寄存器中。

優(yōu)化前代碼：

優(yōu)化后代碼：

循環(huán)分塊

循環(huán)分塊是指通過增加循環(huán)嵌套的維度來提升數(shù)據(jù)局部性的循環(huán)變換技術(shù)，是對多重循環(huán)的迭代空間進行重新劃分的過程，循環(huán)分塊前后要保證迭代空間相同。循環(huán)分塊是循環(huán)交換和循環(huán)分段的結(jié)合?？梢蕴岣叱绦虻木植啃?，增加數(shù)據(jù)重用來提升程序的性能

C語言訪存數(shù)據(jù)是行優(yōu)先的原則，設(shè)置S長度與硬件平臺高速緩存行相匹配，將控制這些分段上進行迭代的循環(huán)移動最外層的位置，這樣單次迭代數(shù)據(jù)量得到了大幅度的減少，減少了從主存取數(shù)的時間，進而提升了性能。

對循環(huán)分塊前后優(yōu)化效果進行測試，編譯器版本為llvm-13，示例優(yōu)化前執(zhí)行時間為3600us，優(yōu)化后執(zhí)行時間為397us，可以看出有將近十倍的加速效果。

循環(huán)分布

循環(huán)分布將一個循環(huán)分解為多個循環(huán)，每個循環(huán)都有與原循環(huán)相同的迭代空間，但只包含原循環(huán)的語句子集。通過循環(huán)分布可以a減少指令緩存的壓力，還能增加寄存器的重用，常用于分解出可向量化或可并行化的循環(huán)，進而將可向量化部分的代碼轉(zhuǎn)為向量執(zhí)行。

優(yōu)化前代碼：

優(yōu)化后代碼：

循環(huán)分裂

循環(huán)分裂是對循環(huán)的迭代次數(shù)進行拆分，將循環(huán)的迭代次數(shù)拆成兩段或者多段，但是拆分后的循環(huán)不存在主體循環(huán)之說，也就是拆分成迭代次數(shù)都比較多的兩個或者多個循環(huán)。

?優(yōu)化前代碼：

優(yōu)化后代碼：