0. 基礎(chǔ)知識(shí)盤(pán)點(diǎn)

0.1 循環(huán)（loop）

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

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

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

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

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

latch：有一條邊連接到header；

backedge：稱(chēng)為回邊，一條從latch到header的邊；

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

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

0.2 Scalar Evolution（SCEV）

定義

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

循環(huán)鏈

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

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

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

舉個(gè)例子：

intm=0;
for(inti=0;i

	

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

	1. Induction Variable（歸納變量）

	1.1 定義

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

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

	
for(i=0;i

	

	1.2 益處

	歸納變量?jī)?yōu)化的好處，有但不局限于以下幾點(diǎn)：

	用更簡(jiǎn)單的指令替換原來(lái)的計(jì)算方式。

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

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

	

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

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

	

	當(dāng)前的loop有兩個(gè)歸納變量：i、j，用其中一個(gè)變量表達(dá)另外一個(gè)后，如下：

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

	

	歸納變量替換，使變量和循環(huán)索引之間的關(guān)系變得明確，便于其他優(yōu)化分析（如依賴(lài)性分析）。舉例如下，將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. 實(shí)踐

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

				compiler
			

				option
		

				gcc
			

				-fivopt
		

				畢昇
			

				-indvars
		

	2.2 優(yōu)化用例

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

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

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

	

	它的IR用例test.ll是：

	

	編譯命令是：

	opt test.ll -indvars -S

	當(dāng)前的例子中，header、latch和exiting block都是同一個(gè)BB，即bb5。

	

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

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

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


	

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

	

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

	例子中，計(jì)算出 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é)點(diǎn)。

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

	

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

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

	   審核編輯：彭靜