0. 基礎(chǔ)知識盤點

0.1 循環(huán)（loop）

定義
loop（llvm里理解為natural loop）是定義在CFG中的一個結(jié)點集合L，并具有以下屬性[1][2]：

有單一的入口結(jié)點（稱為header），該結(jié)點支配loop中的所有結(jié)點；

存在一條進入循環(huán)頭的回邊；

相關(guān)術(shù)語

entering block：一個非loop內(nèi)的結(jié)點有一條邊連接到loop。當只有一個entering block且其只有一條邊連接到header，稱之為preheader；作為非loop結(jié)點的peheader支配整個loop；

latch：有一條邊連接到header；

backedge：稱為回邊，一條從latch到header的邊；

exiting edge：一條邊從loop內(nèi)到loop外，邊的出發(fā)結(jié)點稱之為exiting block，目標結(jié)點稱之為exit block；

上面右圖中，黃色區(qū)域是一個loop，而紅色區(qū)域不是，為什么呢？
因為紅色區(qū)域a和c都是入口結(jié)點，不滿足單一入口結(jié)點的性質(zhì)。

0.2 Scalar Evolution（SCEV）

定義

SCEV是編譯器對變量進行分析的優(yōu)化（往往只針對整數(shù)類型），且主要用于分析循環(huán)中變量是如何被更新的，然后根據(jù)這個信息來進行優(yōu)化。

循環(huán)鏈

如圖所示，循環(huán)中歸納變量var的起始值為start，迭代的方式為?，步長為step；

它的循環(huán)鏈（chrec，Chains of Recurrences）如下：

var = {start, ? , step}
// ?∈{+,?}
// start: starting value
// step: step in each iteration

舉個例子：

intm=0;
for(inti=0;i

	

	那么m的循環(huán)鏈為：m = {0,+,n}。

	1. Induction Variable（歸納變量）

	1.1 定義

	循環(huán)的每次迭代中增加或減少固定量的變量，或者是另一個歸納變量的線性函數(shù)。

	舉個例子[3]，下面循環(huán)中的i和j都是歸納變量：

	
for(i=0;i

	

	1.2 益處

	歸納變量優(yōu)化的好處，有但不局限于以下幾點：

	用更簡單的指令替換原來的計算方式。

	比如，上面的例子中識別到歸納變量，將對應(yīng)的乘法替換為代價更小的加法。

	
j=-17;
for(i=0;i

	

	減少歸納變量的數(shù)目，降低寄存器壓力。

	
externintsum;
intfoo(intn){
inti,j;
j=5;
for(i=0;i

	

	當前的loop有兩個歸納變量：i、j，用其中一個變量表達另外一個后，如下：

	
externintsum;
intfoo(intn){
inti;
for(i=0;i

	

	歸納變量替換，使變量和循環(huán)索引之間的關(guān)系變得明確，便于其他優(yōu)化分析（如依賴性分析）。舉例如下，將c表示為循環(huán)索引相關(guān)的函數(shù)：

	
intc,i;
c=10;
for(i=0;i

	

	轉(zhuǎn)換為：

	
intc,i;
c=10;
for(i=0;i

	

	2. 實踐

	2.1 相關(guān)編譯選項

				compiler
			

				option
		

				gcc
			

				-fivopt
		

				畢昇
			

				-indvars
		

	2.2 優(yōu)化用例

	歸納變量的優(yōu)化（ivs）在llvm中的位置是：llvmlibTransformsScalarIndVarSimplify.cpp

	讓我們通過一個用例，看看畢昇編譯器的優(yōu)化過程。

	如下圖，假設(shè)上面func里面的部分就是要優(yōu)化的代碼，下面func里面就是預(yù)期生成的結(jié)果：

	

	它的IR用例test.ll是：

	

	編譯命令是：

	opt test.ll -indvars -S

	當前的例子中，header、latch和exiting block都是同一個BB，即bb5。

	

	步驟一：依據(jù) def-use 關(guān)系，遍歷loop的 ExitBlock 中phi結(jié)點的操作數(shù)的來源，計算出最終值同時替換它，繼而替換該phi結(jié)點的使用。

	例子中，計算 %tmp2.lcssa ，其唯一的操作數(shù)是 %tmp2 = add nuw nsw i32 %i.01.0, 3 ，該表達式所在的loop是bb5，此時 %tmp2 的循環(huán)鏈為

	
%tmp2={3,+,3}<%bb5>


	

	獲取當前l(fā)oop的不退出循環(huán)的最大值是199999，那當前 %tmp2=add(3, mul(3,199999))=600000；接下來會看當前的替換不是高代價（代價的計算會依據(jù)不同架構(gòu)有所不同），同時在phi結(jié)點的 user 中替換該值。優(yōu)化結(jié)果如下：

	

	步驟二：遍歷 ExitingBlock ，對其跳轉(zhuǎn)條件進行計算，依據(jù) def-use 的關(guān)系，刪除相應(yīng)的指令。

	例子中，計算出 br i1 %0, label %bb5, label %bb7 的 %0 是 false，跳轉(zhuǎn)指令替換后，%0 = icmp ult i32 %tmp4，200000 不存在 user，將其加入到“死指令”中。優(yōu)化結(jié)果如下：

	

	步驟三：刪除所有“死指令”，并看看他的操作數(shù)是否要一并刪除。

	例子中，作為 %0 的操作數(shù)的 %tmp4 還有其他的 user %x.03.0，因此不能被視為“死指令”被刪除。優(yōu)化結(jié)果如下：

	

	步驟四：刪除 HeaderBlock 中的“死”phi結(jié)點。

	例子中， %tmp4 和phi結(jié)點 %x.03.0 構(gòu)成了一個不會有成果的循環(huán)，就會刪除它們，同理刪除 %tmp2 和 %i.01.0 。優(yōu)化結(jié)果如下：

	

	原文標題：編譯器優(yōu)化那些事兒（4）：歸納變量

	文章出處：【微信公眾號：openEuler】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

	   審核編輯：彭靜