基本塊的優(yōu)化
很多重要的局部?jī)?yōu)化技術(shù)首先把一個(gè)基本塊轉(zhuǎn)換成為一個(gè)無環(huán)有向圖(directed acyclic graph ， DAG)
基本塊的DAG表示
例.png
基本塊中的每個(gè)語句s都對(duì)應(yīng)一個(gè)內(nèi)部結(jié)點(diǎn)N
- 結(jié)點(diǎn)N的標(biāo)號(hào)是s中的運(yùn)算符；同時(shí)還有一個(gè)定值變量表被關(guān)聯(lián)到N，表示s是在此基本塊內(nèi)最晚對(duì)表中變量進(jìn)行定值的語句。
- N的子結(jié)點(diǎn)是基本塊中在s之前、最后一個(gè)對(duì)s所使用的運(yùn)算分量進(jìn)行定值的語句對(duì)應(yīng)的結(jié)點(diǎn) 。如果s的某個(gè)運(yùn)算分量在基本塊內(nèi)沒有在s 之前被定值，則這個(gè)運(yùn)算分量對(duì)應(yīng)的子結(jié)點(diǎn)就是代表該運(yùn)算分量初始值的葉結(jié)點(diǎn)(為區(qū)別起見，葉節(jié)點(diǎn)的定值變量表中的變量加上下腳標(biāo)0)
- 在為語句x=y+z構(gòu)造結(jié)點(diǎn)N的時(shí)候，如果x已經(jīng)在某結(jié)點(diǎn)M的定值變量表中，則從M的定值變量表中刪除變量x。
基于基本塊的DAG刪除無用代碼
從一個(gè)DAG上刪除所有沒有附加活躍變量（活躍變量是指其值可能會(huì)在以后被使用的變量）的根結(jié)點(diǎn)(即沒有父結(jié)點(diǎn)的結(jié)點(diǎn))。重復(fù)應(yīng)用這樣的處理過程就可以從DAG中消除所有對(duì)應(yīng)于無用代碼的結(jié)點(diǎn)。
例.png
數(shù)組元素賦值指令的表示
例.png
根據(jù)基本塊的DAG可以獲得一些非常有用的信息
-
確定哪些變量的值在該基本塊中賦值前被引用過
在DAG中創(chuàng)建了葉結(jié)點(diǎn)的那些變量
-
確定哪些語句計(jì)算的值可以在基本塊外被引用
在DAG構(gòu)造過程中為語句s（該語句為變量x定值）創(chuàng)建的節(jié)點(diǎn)N，在DAG構(gòu)造結(jié)束時(shí)x仍然是N的定值變量。
從DAG到基本塊的重組
-
對(duì)每個(gè)具有若干定值變量的節(jié)點(diǎn)，構(gòu)造一個(gè)三地址語句來計(jì)算其中某個(gè)變量的值
傾向于把計(jì)算得到的結(jié)果賦給一個(gè)在基本塊出口處活躍的變量(如果沒有全局活躍變量的信息作為依據(jù)，就要假設(shè)所有變量都在基本塊出口處活躍，但是不包含編譯器為處理表達(dá)式而生成的臨時(shí)變量)
如果結(jié)點(diǎn)有多個(gè)附加的活躍變量，就必須引入復(fù)制語句，以便給每一個(gè)變量都賦予正確的值。
例.png
例.png
