0. 基礎知識盤點

0.1 循環(huán)（loop）

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

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

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

相關術語

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

latch：有一條邊連接到header；

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

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

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

0.2 Scalar Evolution（SCEV）

定義

SCEV是編譯器對變量進行分析的優(yōu)化（往往只針對整數類型），且主要用于分析循環(huán)中變量是如何被更新的，然后根據這個信息來進行優(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)的每次迭代中增加或減少固定量的變量，或者是另一個歸納變量的線性函數。

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

	
for(i=0;i

	

	1.2 益處

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

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

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

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

	

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

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

	

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

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

	

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

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

	

	轉換為：

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

	

	2. 實踐

	2.1 相關編譯選項

				compiler
			

				option
		

				gcc
			

				-fivopt
		

				畢昇
			

				-indvars
		

	2.2 優(yōu)化用例

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

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

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

	

	它的IR用例test.ll是：

	

	編譯命令是：

	opt test.ll -indvars -S

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

	

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

	例子中，計算 %tmp2.lcssa ，其唯一的操作數是 %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；接下來會看當前的替換不是高代價（代價的計算會依據不同架構有所不同），同時在phi結點的 user 中替換該值。優(yōu)化結果如下：

	

	步驟二：遍歷 ExitingBlock ，對其跳轉條件進行計算，依據 def-use 的關系，刪除相應的指令。

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

	

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

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

	

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

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

	

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

	文章出處：【微信公眾號：openEuler】歡迎添加關注！文章轉載請注明出處。

	   審核編輯：彭靜