編譯方法、技術(shù)與實(shí)踐課件：中間代碼優(yōu)化

中間代碼優(yōu)化?數(shù)據(jù)流分析理論與框架?到達(dá)定值分析?可用表達(dá)式分析?活躍變量分析?局部?jī)?yōu)化/全局優(yōu)化提綱?代碼優(yōu)化O

在目標(biāo)代碼中消除不必要的指令O

把一個(gè)指令序列替換為一個(gè)完成相同功能的更快的指令序列?全局優(yōu)化?基于數(shù)據(jù)流分析技術(shù)O

用以收集程序相關(guān)信息的算法引言?編譯器只能通過(guò)一些相對(duì)低層的語(yǔ)義等價(jià)轉(zhuǎn)換來(lái)優(yōu)化代碼?冗余運(yùn)算的原因O

源程序中的冗余O

高級(jí)程序設(shè)計(jì)語(yǔ)言編程的副產(chǎn)品?比如A[i][j].f=0;A[i][j].k=1;中的冗余運(yùn)算?語(yǔ)義不變的優(yōu)化O

公共子表達(dá)式消除O

復(fù)制傳播O

死代碼消除O

常量折疊優(yōu)化的主要來(lái)源自動(dòng)化重構(gòu)技術(shù)：重寫規(guī)則：(1)

with上下文管理器重寫規(guī)則;(2)

推導(dǎo)表達(dá)式重寫規(guī)則;(3)

lambda表達(dá)式重寫規(guī)則;(4)

yield

from重寫規(guī)則;(5)

map、reduce

、filter

、sorted重寫規(guī)則;(6)

裝飾器重寫規(guī)則等;擬實(shí)現(xiàn)方法：?源碼靜態(tài)分析，生成AST樹?對(duì)AST樹進(jìn)行規(guī)則匹配，并完成相應(yīng)替換語(yǔ)義功能一致的不同改寫策略優(yōu)化的主要來(lái)源實(shí)現(xiàn)機(jī)制不同優(yōu)化的例子(1)?快速排序算法優(yōu)化的例子(2)?三地址代碼?循環(huán)：O

B2O

B3O

B2、B3、B4、

B5Quicksort的流圖?數(shù)據(jù)流分析O

用于獲取數(shù)據(jù)沿著程序執(zhí)行路徑流動(dòng)的信息的相關(guān)技術(shù)O

是優(yōu)化的基礎(chǔ)?例如O

兩個(gè)表達(dá)式是否一定計(jì)算得到相同的值？

(公共子表達(dá)式)O

一個(gè)語(yǔ)句的計(jì)算結(jié)果有沒(méi)有可能被后續(xù)語(yǔ)句使用？(死代碼消除)數(shù)據(jù)流分析?程序點(diǎn)O

三地址語(yǔ)句之前或之后的位置O

基本塊內(nèi)部：一個(gè)語(yǔ)句之后的程序點(diǎn)等于下一個(gè)語(yǔ)句之前的程序點(diǎn)O

如果流圖中有B1到B2的邊，那么B2的第一個(gè)語(yǔ)句之前的點(diǎn)可能緊跟在B1的最后語(yǔ)句之后的點(diǎn)后面執(zhí)行?從p1到p2的執(zhí)行路徑：p1,p2,…,pnO

要么pi是一個(gè)語(yǔ)句之前的點(diǎn)，且pi+1是該語(yǔ)句之后的點(diǎn)O

要么pi是某個(gè)基本塊的結(jié)尾，且pi+1是該基本塊的某個(gè)后繼的開頭數(shù)據(jù)流抽象(1)?出現(xiàn)在某個(gè)程序點(diǎn)的程序狀態(tài)O

在某個(gè)運(yùn)行時(shí)刻，當(dāng)指令指針指向這個(gè)程序點(diǎn)時(shí)，

各個(gè)變量和動(dòng)態(tài)內(nèi)存中存放的值O

指令指針可能多次指向同一個(gè)程序點(diǎn)?因此一個(gè)程序點(diǎn)可能對(duì)應(yīng)多個(gè)程序狀態(tài)?數(shù)據(jù)流分析把可能出現(xiàn)在某個(gè)程序點(diǎn)上的程

序狀態(tài)集合總結(jié)為一些特性O(shè)

不管程序怎么運(yùn)行，當(dāng)它到達(dá)某個(gè)程序點(diǎn)時(shí)，

程序狀態(tài)總是滿足分析得到的特性O(shè)

不同的分析技術(shù)關(guān)心不同的信息?為了高效、自動(dòng)地進(jìn)行數(shù)據(jù)流分析，通常要求這些特性能夠被高效地表示和求解數(shù)據(jù)流抽象(2)?路徑O

1,2,3,4,9O

1,2,3,4,5,6,7,8,9O

…?第一次到達(dá)(5)，a=1；第二次到達(dá)(5)，a=243；且之后都是

243?我們可以說(shuō)：O

點(diǎn)(5)具有特性a=1ora=243O

表示成為<a,{1,243}>例子(1)?分析得到的性質(zhì)集合應(yīng)該是一個(gè)安全的估計(jì)值O

即根據(jù)這些性質(zhì)進(jìn)行優(yōu)化不會(huì)改變程序的語(yǔ)義有可能做激

進(jìn)的優(yōu)化嗎？?不同的需求對(duì)應(yīng)不同的性質(zhì)集合與算法性質(zhì)和算法?數(shù)據(jù)流值O

某個(gè)程序點(diǎn)所有可能的狀態(tài)集合的抽象表示O

和某個(gè)程序點(diǎn)關(guān)聯(lián)的數(shù)據(jù)流值：程序運(yùn)行中經(jīng)過(guò)這個(gè)點(diǎn)時(shí)必然滿足的這個(gè)條件?

域O

所有可能的數(shù)據(jù)流值的集合?不同的應(yīng)用選用不同的域，比如到達(dá)定值O

目標(biāo)是分析在某個(gè)點(diǎn)上，各個(gè)變量的值由哪些語(yǔ)

句定值O

因此數(shù)據(jù)流值是定值(即三地址語(yǔ)句)的集合，

表明集合中的定值對(duì)某個(gè)變量定值了

數(shù)據(jù)流分析模式?基于控制流的約束O

IN[si+1]=OUT[si]?基于語(yǔ)句語(yǔ)義的約束(傳遞函數(shù))?數(shù)據(jù)流分析：對(duì)一組約束求解O

IN[s]=fs(OUT[s])O

OUT[s]=fs(IN[s])數(shù)據(jù)流分析(逆向)(正向)O

IN[s]和OUT[s]?假設(shè)我們考慮各個(gè)變量在某個(gè)程序點(diǎn)上是OUT[s]：x:10;

y:7;

z:3IN[s]：x:NAC;

y:7;

z:3

s:

x=y+z

例子(1)

s:

x=3

IN[s]：x:NAC;OUT[s]：x:3;否常量y:7;y:7;z:3z:3s1:

x

=

3s:

z

=

x+ys2:

y

=

3OUT[s2]：x:4，y:3，z:NACIN[s]：x:NAC，y:NAC，z:NACx

=

4;y

=

4;z

=

a+b;OUT[s1]：x:3，y:4，z:NAC例子(2)OUT[s]:

??基本塊的控制流非常簡(jiǎn)單O

從頭到尾不會(huì)中斷O

沒(méi)有分支?基本塊的效果就是各個(gè)語(yǔ)句的效果的復(fù)合?可以預(yù)先處理基本塊內(nèi)部的數(shù)據(jù)流關(guān)系，給出基本塊對(duì)應(yīng)的傳遞函數(shù)；IN[B]=fB

(OUT[B])或者OUT[B]=fB

(IN[B])?設(shè)基本塊包含語(yǔ)句s1,s2,…,snfB=fsn?

…?fs2?fs1基本塊上的數(shù)據(jù)流模式?前向數(shù)據(jù)流問(wèn)題O

B的傳遞函數(shù)根據(jù)IN[B]計(jì)算得到OUT[B]O

IN[B]和B的各前驅(qū)基本塊的OUT值之間具有約束關(guān)系?逆向數(shù)據(jù)流問(wèn)題O

B的傳遞函數(shù)根據(jù)OUT[B]計(jì)算IN[B]O

OUT[B]和B的各后繼基本塊的IN值之間具有約束關(guān)系前向數(shù)據(jù)流的例子：假如：OUT[B1]

：x:3

y:4

z:NACOUT[B2]

：x:3

y:5

z:7OUT[B3]

：x:3

y:4

z:7則：IN[B]

：

x:3

y:NAC

z:NAC基本塊之間的控制流約束B1B3BB2s:

z

=

x+ys2:

y

=

3s1:

x

=

3OUT[s1]：x:3，y:4，z:NAC

OUT[s2]：x:4，y:3，z:NACIN[s]：x:4，y:3，z:NACOUT[s]:

z:NAC

vs.

z:7?目標(biāo)是尋找一個(gè)最“精確的”、滿足約束的解O

精確：能夠進(jìn)行更多的改進(jìn)數(shù)據(jù)流方程解的精確性和安全性O(shè)

滿足約束：根據(jù)分析結(jié)果來(lái)改進(jìn)代碼是安全的x

=

4;y

=

4;z

=

a+b;?數(shù)據(jù)流方程通常沒(méi)有唯一解IN[s]：x:3，y:4，z:NAC不同精度

要求?數(shù)據(jù)流分析理論與框架?到達(dá)定值分析?可用表達(dá)式分析?活躍變量分析?局部?jī)?yōu)化/全局優(yōu)化提綱?到達(dá)定值O

如果存在一條從定值d后面的程序點(diǎn)到達(dá)某個(gè)點(diǎn)p的路徑，且這條路徑上d沒(méi)有被殺死，那么定值d到達(dá)p?殺死：路徑上對(duì)x的其他定值殺死了之前對(duì)x的定值?直觀含義O

如果d到達(dá)p，那么在p點(diǎn)使用的值就可能是由d定值的?思考：不確定是否賦值該怎么辦？O

*p=3(不確定p的指向)O

過(guò)程參數(shù)、數(shù)組、指針等等到達(dá)定值?B1

中全部定值到達(dá)B2的開頭?d5到達(dá)B2的開頭

(循環(huán))?d2被d5殺死，不能

到達(dá)B3、B4的開頭?d4不能到達(dá)B2的開頭，因?yàn)楸籨7殺死?d6到達(dá)B2的開頭到達(dá)定值的例子?到達(dá)定值的解允許不精確，但必須是安全的O

分析得到的到達(dá)定值可能實(shí)際上不會(huì)到達(dá)O

但是實(shí)際到達(dá)的一定被分析出來(lái)，否則不安全?對(duì)于可能定值的情況，怎么做才是安全的？?確定變量x在某個(gè)程序點(diǎn)

?假設(shè)所有可能定值都不是否常量

能到達(dá)?確定變量是否先使用后

定值(未初始化就使用)?假設(shè)所有可能定值都能

到達(dá)到達(dá)定值?定值d:u=v+wO

生成了對(duì)變量u的定值d，殺死了其他對(duì)u的定值O

生成-殺死：O

OUT[B]=fB(IN[B])O

fd(x)=gend

∪(x-killd)?把x=IN[B]帶入?特別地，其中g(shù)end=tzjhb3b，killd={程序中其他對(duì)u的

定值}語(yǔ)句/基本塊的傳遞方程(1)?OUT[B]=gend

∪(IN[B]-killd)?生成-殺死形式的函數(shù)的并置(復(fù)合)O

f2(f1(x))=gen2

∪(gen1

∪

(x-kill1)-kill2)=(gen2

∪(gen1-kill2))∪(x-kill1

∪kill2))O

生成的定值：由第二部分生成、以及由第一個(gè)部分生成且沒(méi)有被第二部分殺死O

殺死的定值：被第一部分殺死的定值、以及被第二部分殺死的定值語(yǔ)句/基本塊的傳遞方程(1)?設(shè)B有n個(gè)語(yǔ)句，第i個(gè)語(yǔ)句的傳遞函數(shù)為fi?fB(x)=genB

∪(x-killB)?genB

=genn

∪(genn-

1-killn)∪(genn-2-killn-

1-killn)∪(gen1-kill2-kill3

…-killn)?killB=kill1

∪kill2

∪…∪killn?killB

為被B各個(gè)語(yǔ)句殺死的定值的并集?genB是被第i個(gè)語(yǔ)句生成，且沒(méi)有被其后的句子殺死的定值的集合語(yǔ)句/基本塊的傳遞方程(2)gen和kill的例子?只要一個(gè)定值能夠沿某條路徑到達(dá)一個(gè)程序點(diǎn)，這個(gè)定值就是到達(dá)定值?

IN[B]=∪P是B的前驅(qū)基本塊OUT[P]O

如果從基本塊P到B有一條控制流邊，那么OUT[P]在IN[B]中O

一個(gè)定值必然先在某個(gè)前驅(qū)的OUT值中，才能出現(xiàn)在B的IN中?∪稱為到達(dá)定值的交匯運(yùn)算符到達(dá)定值的控制流方程?ENTRY基本塊的傳遞函數(shù)是常函數(shù)OUT[ENTRY]=空集?其他基本塊OUT[B]=genB

∪(IN[B]-killB)IN[B]=∪P是B的前驅(qū)基本塊OUT[P]?迭代解法O

首先求出各基本塊的gen和killO

令所有的OUT[B]都是空集，然后不停迭代，得到最小不動(dòng)點(diǎn)的解控制流方程的迭代解法(1)控制流方程的迭代解法(2)?

輸入：流圖、各基本塊的kill和gen集合?輸出：IN[B]和OUT[B]?方法：?7個(gè)bit從左到右表示d1,d2,…,dn?for循環(huán)時(shí)依次遍歷B1,B2,B3,B4,EXIT?每一列表示一次迭代計(jì)算；?B1生成d1,d2,d3

，殺死d4,d5,d6,d7?B2生成d4,d5

，殺死d1,d2,d7?B3生成d6

，殺死d3到達(dá)定值求解的例子?B4生成d7

，殺死d1,d4?解法的正確性O(shè)

直觀解釋：不斷向前傳遞各個(gè)定值，直到該定值被殺死為止?算法為什么能終止？O

各個(gè)OUT[B]在算法執(zhí)行過(guò)程中不會(huì)變小O

且OUT[B]顯然有有窮的上界O

只有一次迭代之后增大了某個(gè)OUT[B]的值，算法才會(huì)進(jìn)行下一次迭代?最大迭代次數(shù)是流圖的結(jié)點(diǎn)個(gè)數(shù)nO

定值經(jīng)過(guò)n步必然已經(jīng)到達(dá)所有可能到達(dá)的結(jié)點(diǎn)?算法結(jié)束時(shí)，各個(gè)OUT/IN值必然滿足數(shù)據(jù)流方程控制流方程的迭代解法(3)?數(shù)據(jù)流分析理論與框架?到達(dá)定值分析?可用表達(dá)式分析?活躍變量分析?局部?jī)?yōu)化/全局優(yōu)化提綱?主要用途O

消除全局公共子表達(dá)式O

復(fù)制傳播?直觀意義：在點(diǎn)p上，x+y已經(jīng)被計(jì)算過(guò)了，

不用再重新計(jì)算了?x+y在p點(diǎn)可用的條件O

從流圖入口結(jié)點(diǎn)到達(dá)p的每條路徑都對(duì)x+y求值，且在最后一次求值之后再?zèng)]有對(duì)x或者y賦值可用表達(dá)式分析?在x的應(yīng)用點(diǎn)u可以用y替代x的條件：從流圖的首節(jié)點(diǎn)到達(dá)u的每條路徑都存在復(fù)制語(yǔ)句x=y，并且從最后一條復(fù)制語(yǔ)句x=y到u之間沒(méi)有再次對(duì)x或者y進(jìn)行定值?生成-殺死O

殺死：基本塊對(duì)x或y賦值，且沒(méi)有重新計(jì)算x+y，那么它殺死了x+yO

生成：基本塊求值x+y，且之后沒(méi)有對(duì)x或者y賦值，那么它生成了x+y可用表達(dá)式分析?可用表達(dá)式傳遞函數(shù)O

對(duì)于可用表達(dá)式數(shù)據(jù)流模式而言，O

如果基本塊B對(duì)x或者y進(jìn)行了(或可能進(jìn)行)定值，且以后沒(méi)有重新計(jì)算x+y，則稱B殺死表達(dá)式x+y。O

如果基本塊B對(duì)x+y進(jìn)行計(jì)算，并且之后沒(méi)有重新定值x或y，則稱B生成表達(dá)式x+y?fB(x)=e_genB

∪(x-e_killB)O

e_genB

：基本塊B所生成的可用表達(dá)式的集合O

e_killB

：基本塊B所殺死的U中的表達(dá)式的集合；U表示所有出現(xiàn)在程序中一個(gè)或多個(gè)語(yǔ)句的右部

的表達(dá)式的全集

可用表達(dá)式分析?

初始化S={}?從頭到尾逐個(gè)處理基本塊中的指令x=y+zO把y+z添加到S中；O

從S中刪除任何涉及變量x的表達(dá)式?遍歷結(jié)束時(shí)得到基本塊生成的表達(dá)式集合；?殺死的表達(dá)式集合O

表達(dá)式的某個(gè)分量在基本塊中定值，且沒(méi)有被再次生成計(jì)算基本塊生成的表達(dá)式基本塊生成/殺死的表達(dá)式的例子?ENTRY結(jié)點(diǎn)的出口處沒(méi)有可用表達(dá)式O

OUT[ENTRY]={}?其他基本塊的方程O

OUT[B]=e_genB

∪(IN[B]-e_killB)O

IN[B]=∩P是B的前驅(qū)基本塊OUT[P]?和其他方程類比O

前向傳播O

交匯運(yùn)算是交集運(yùn)算可用表達(dá)式的數(shù)據(jù)流方程?注意：OUT值的初始化值是全集O

這樣的初始集合可以求得更有用的解可用表達(dá)式分析的迭代方法?數(shù)據(jù)流分析理論與框架?到達(dá)定值分析?可用表達(dá)式分析?活躍變量分析?局部?jī)?yōu)化/全局優(yōu)化提綱?活躍變量分析O

x在p上的值是否會(huì)在某條從p出發(fā)的路徑中使用O

一個(gè)變量x在p上活躍，當(dāng)且僅當(dāng)存在一條從p點(diǎn)開始的路徑，該路徑的末端使用了x，且路徑上沒(méi)有對(duì)x進(jìn)行覆蓋?用途O

寄存器分配/死代碼刪除/無(wú)用賦值…O

(考慮我們前面講的優(yōu)化)?數(shù)據(jù)流值O

(活躍)變量的集合活躍變量分析OUT[B]B1B2B3B4aijmnu1u2u3活躍變量分析OUT[B]B1B2B3B4axxxxi√xx√j√√√√mxxxxnxxxxu1xxxxu2√√√√u3√√√√活躍變量分析?基本塊的傳遞函數(shù)仍然是生成-殺死形式，但是從OUT值計(jì)算出IN值(逆向)?IN[B]=fB(OUT[B])?fB(x)=useB

∪(x-defB)O

useB

，在基本塊B中引用，但是引用前在B中沒(méi)有被定值的集合;可能在B中先于定值被使

用(GEN)O

defB

，在基本塊中定值，但是定值前在B中沒(méi)

有被引用的變量的集合;在B中一定先于使用被定值(KILL)基本塊內(nèi)的數(shù)據(jù)流方程活躍變量分析的迭代方法?語(yǔ)句的傳遞函數(shù)O

s:x=y+zO

uses

={y,z}Odefs={x}-{y,z}//x=y+z是模板，y、z可能和x相同?假設(shè)基本塊中包含語(yǔ)句s1,s2,…,sn，那么?useB

=use1

∪(use2-def1)∪(use3-def1-def2)

∪(usen-def1-def2

…-defn-1)?defB=def1

∪def2

∪…∪defnUSEB和DEFB的用法?任何變量在程序出口處不再活躍O

IN[EXIT]=空集?對(duì)于所有不等于EXIT的基本塊O

IN[B]=useB

∪(OUT[B]-defB)O

OUT[B]=∪S是B的后繼基本塊IN[S]?和到達(dá)定值相比較O

都使用并集運(yùn)算∪作為交匯運(yùn)算O

數(shù)據(jù)流值的傳遞方向相反：因此初始化的值活躍變量數(shù)據(jù)流方程不一樣輸入：流圖G，各個(gè)基本塊B的use和def輸出：IN[B]和OUT[B]活躍變量數(shù)據(jù)流方程活躍變量數(shù)據(jù)流方程求解例子活躍變量數(shù)據(jù)流方程求解例子OUT[B]aijmnu1u2u3B1x√√xxx√√B2xx√xxx√√B3xx√xxx√√B4x√√xxx√√三種數(shù)據(jù)流方程的總結(jié)?數(shù)據(jù)流分析理論與框架?到達(dá)定值分析?可用表達(dá)式分析?活躍變量分析?局部?jī)?yōu)化/全局優(yōu)化提綱?

如果EO

在某次出現(xiàn)之前必然已經(jīng)被計(jì)算過(guò)，且O

E的分量在該次計(jì)算之后一

直沒(méi)有被改變，?那么E的本次出現(xiàn)就是一個(gè)公共子表達(dá)式?如果上一次E的值賦給了x，且x的值至今沒(méi)有被修改過(guò)，

那么我們就可以使用x，而不需要計(jì)算E全局公共子表達(dá)式?

右圖O

在B2、B3

中計(jì)算了4*i和4*jO

到達(dá)B5之前必然經(jīng)過(guò)B2、B3O

t2、t4在賦值之后沒(méi)有被改變過(guò)，因此B5

中可直接使用它們O

t4在替換t8之后，B5：a[t8]和B3：a[t4]又相同?同樣：O

B5

中賦給x的值和B2

中賦給t3的值相同O

B6

中的a[t13]和B1

中的a[t1]不同，因?yàn)锽5

中可能改變a的值全局公共子表達(dá)式的例子消除公共子表達(dá)式后?形如u=v的復(fù)制語(yǔ)句使得語(yǔ)句