【文章內(nèi)容簡(jiǎn)介】 ，當(dāng)且僅當(dāng)基本塊 C的第一個(gè)指令有可能在 B的最后一個(gè)指令之后執(zhí)行。原因： ? B的結(jié)尾指令是一條跳轉(zhuǎn)到 C的開頭的條件 /無條件語句 ? 在原來的序列中， C緊跟在 B之后，且 B的結(jié)尾不是無條件跳轉(zhuǎn)語句 ? B是 C的 前驅(qū) ， C是 B的 后繼 ?流圖中增加額外的入口，出口結(jié)點(diǎn)各一個(gè) ? 不對(duì)應(yīng)于實(shí)際的中間指令 （ 是增加 ） 。 ? 入口到第一條指令有一條邊 ? 從任何可能最后執(zhí)行的基本塊到出口有一條邊 流圖繪制舉例 流圖的例子 ?因跳轉(zhuǎn)而生成的邊 ? B3?B3 ? B4?B2 ? B6?B6 ?因?yàn)轫樞蚨傻倪? ? 其它 循環(huán) ?程序的大部分運(yùn)行時(shí)間花費(fèi)在循環(huán)上 ?因此循環(huán)是識(shí)別的重點(diǎn) ?循環(huán)的定義 ? 循環(huán) L是一個(gè)結(jié)點(diǎn)集合 ? 存在一個(gè)循環(huán)入口（ loop entry）節(jié)點(diǎn)，其唯一的前驅(qū)可以是循環(huán) L之外的結(jié)點(diǎn) ? 其余結(jié)點(diǎn)都存在到達(dá) L的入口的非空路徑，且路徑都在 L中。 循環(huán)的例子 ?循環(huán) ? {B3} ? {B6} ? {B2,B3,B4} 基本塊的幾種優(yōu)化 ? 一個(gè)基本塊可用一個(gè) DAG圖表示 (基本的 DAG圖 ) ? 每個(gè)變量對(duì)應(yīng)于一個(gè)結(jié)點(diǎn)，表示初始值 ? 每條語句 s有一個(gè)相關(guān)結(jié)點(diǎn) N,具有 ? 子結(jié)點(diǎn)：對(duì)應(yīng)于其它語句 ,是在 s之前，最后一個(gè)對(duì) s所使用的某個(gè)運(yùn)算分量進(jìn)行定值的語句。 ? 標(biāo)記： s的運(yùn)算符 ? 附加標(biāo)記：一組變量，表明 s是在此基本塊內(nèi)最晚對(duì)該變量定值 ? 某些輸出結(jié)點(diǎn)：結(jié)點(diǎn)對(duì)應(yīng)的變量在基本塊出口處活躍 （ 出口活躍屬于全局?jǐn)?shù)據(jù)流分析 ） DAG示例 語句 S的結(jié)點(diǎn) N和子結(jié)點(diǎn) s運(yùn)算符當(dāng)結(jié)點(diǎn)標(biāo)記 附加標(biāo)記 變量的結(jié)點(diǎn) DAG圖的構(gòu)造 ?為基本塊中出現(xiàn)的每個(gè)變量建立結(jié)點(diǎn)（表示基本值） ?順序掃描各個(gè)三地址指令 ? 如果指令為 x=y op z ? 為這個(gè)指令建立結(jié)點(diǎn) N，標(biāo)號(hào)為 op； ? N的子結(jié)點(diǎn)為 y、 z當(dāng)前關(guān)聯(lián)的結(jié)點(diǎn)； ? X和 N關(guān)聯(lián)； ? 如果指令為 x=y； ? 不建立新結(jié)點(diǎn)； ? 設(shè) y關(guān)聯(lián)到 N，那么 x現(xiàn)在也關(guān)聯(lián)到 N ?掃描結(jié)束后，對(duì)于所有在出口處活躍的變量 x，將x所關(guān)聯(lián)的結(jié)點(diǎn)設(shè)置為輸出結(jié)點(diǎn) DAG的作用 ?DAG圖描述了基本塊運(yùn)行時(shí)各個(gè)值之間的關(guān)系。 ?可以 DAG為基礎(chǔ)，對(duì)代碼進(jìn)行轉(zhuǎn)換 ? 消除局部公共子表達(dá)式 ? 消除死代碼 ? 對(duì)語句重新排序 ? 重新排序運(yùn)算分量的順序 局部公共子表達(dá)式 ? 局部公共子表達(dá)式的發(fā)現(xiàn) ? 建立某個(gè)結(jié)點(diǎn) M之前，首先檢查是否存在一個(gè)結(jié)點(diǎn) N，它和 M具有相同的運(yùn)算符和子結(jié)點(diǎn)（順序相同）。 ? 如果存在，則不需要生成新的結(jié)點(diǎn)，用 N代表 M； ? 例如： ? a=b+c ? b=ad ? c=b+c ? d=ad ? 找出公共的表達(dá)式？ ? 注意：兩個(gè) b+c實(shí)際上并不是公共子表達(dá)式 消除死代碼 ?在 DAG圖上消除沒有附加活躍變量的根結(jié)點(diǎn)（沒有父結(jié)點(diǎn)的結(jié)點(diǎn)），即可消除死代碼 ?如果圖中 c、 e不是活躍變量，則可以刪除標(biāo)號(hào)為 e、 c的結(jié)點(diǎn)。 DAG方法的不足 為了計(jì)算第四式的 e值，而有的 2,3式實(shí)際上是冗余的，也就是第一式和第四式等價(jià)。該代碼本可優(yōu)化，但發(fā)現(xiàn)不了 在 DAG上應(yīng)用代數(shù)恒等式的優(yōu)化 ?消除計(jì)算步驟 ? x+0=0+x=x x0=x ? x*1=1*x=x x/1=x ?降低計(jì)算強(qiáng)度 ? X2=x*x 2*x=x+x ?常量合并 ? 2* ?實(shí)現(xiàn)這些優(yōu)化時(shí)，只需要在 DAG圖上尋找特定的模式 56 數(shù)組引用－避免誤優(yōu)化 ?注意： a[j]可能改變 a[i]的值，因此不能和普通的運(yùn)算符一樣構(gòu)造相應(yīng)的結(jié)點(diǎn) ? x=a[i] ? a[j]=y ? z=a[i] ?從數(shù)組取值的運(yùn)算 x=a[i]對(duì)應(yīng)于 “ =[]”的結(jié)點(diǎn)， x作為這個(gè)結(jié)點(diǎn)的標(biāo)號(hào)之一； ?對(duì)數(shù)組賦值的運(yùn)算對(duì)應(yīng)于 “ []=”的結(jié)點(diǎn)；沒有關(guān)聯(lián)的變量、且殺死所有依賴于 a的變量； Killed節(jié)點(diǎn)不能成為公共子表達(dá)式 ? 殺手 ? 被殺者 ? 殺手 引入新的運(yùn)算符 數(shù)組引用的 DAG的例子 ?b=12+a ?x=b[i] ?b[j]=y ?注意 a是被殺死結(jié)點(diǎn)的孫結(jié)點(diǎn)。 x ? 如果沒有殺手的出現(xiàn)則被殺者本可以象前述一樣進(jìn)行優(yōu)化。 ? 殺死的意思－－指不能參加優(yōu)化 指針賦值 /過程調(diào)用 ?通過指針進(jìn)行取值 /賦值： x=*p *q=y。最粗略地估計(jì)：