【正文】 。 ? 內(nèi)部節(jié)點(diǎn)用運(yùn)算符作為標(biāo)記，表示計(jì)算的值。每個節(jié)點(diǎn)的值都可以用關(guān)于變量初始值的表達(dá)式表示。 ? 各節(jié)點(diǎn)可能附加有一個或者多個標(biāo)識符。同一個節(jié)點(diǎn)的標(biāo)識符表示相同的值。 DAG圖的例子 ? + b c a ? a d b ? + b c c ? a d d + + b0 c0 d0 b,d a c 四元式的分類 ? 0型： = x _ y ? 1型： op x _ y(單目運(yùn)算） ? 2型： op x y z relop x y z(z是序號 ) 基本塊 DAG圖構(gòu)造算法 ? 輸入：一個基本塊 輸出：相應(yīng) DAG圖 ? 算法說明： ? 通過逐個掃描四元式來逐步建立 DAG圖。 ? 函數(shù) node(x)表示和標(biāo)識符 x相應(yīng)的最近建立的節(jié)點(diǎn)。他代表掃描到當(dāng)前的四元式的時(shí)候，標(biāo)識符 x的值對應(yīng)的節(jié)點(diǎn)。 ? 步驟 1：初始化：無任何節(jié)點(diǎn)， node對任何標(biāo)識符無定義。 ? 步驟 2：依次對基本塊中的每個四元式 op x y z執(zhí)行如下步驟。 ? 如果 node(x)沒有定義，建立葉子節(jié)點(diǎn)，標(biāo)記為 x，讓 node(x) 等于這個節(jié)點(diǎn)。如果 node(y)沒有定義，為 y建立節(jié)點(diǎn)。 ? 如果四元式為 0型， n=node(x)。 ? 如果四元式為 1型，尋找標(biāo)記為 op且子節(jié)點(diǎn)為 node(x)的節(jié)點(diǎn)，如果找不到，建立這樣的節(jié)點(diǎn)。 基本塊 DAG圖構(gòu)造算法（續(xù)） ? 對于 2型四元式，查看是否存在標(biāo)記為 op的節(jié)點(diǎn)，且其左右子節(jié)點(diǎn)分別為 node(x)和 node(y)。如果找不到，建立這樣的節(jié)點(diǎn)。 ? 步驟 3：如果 z為標(biāo)識符，從 node(z)中刪除標(biāo)識符 z，并把 z加入到步驟 4所找到或者建立的節(jié)點(diǎn) n的標(biāo)識符表中，并設(shè)置node(z)為 n。 ? 說明： ? 處理 2型四元式的時(shí)候，如果 op是可交換的運(yùn)算符，可以允許其左右節(jié)點(diǎn)可以互換。 生成 DAG圖的例子 ? * 4 i t1 =[] a t1 t2 ? * 4 i t3 =[] b t3 t4 ? * t2 t4 t5 + prod t5 t6 ? = t6 prod + i 1 t7 ? = t7 i = i 20 (3) a 4 i * =[] =[] b * + prod0 1 + 20 = DAG圖的應(yīng)用 ? 公共子表達(dá)式 ：構(gòu)造中，尋找是否有標(biāo)記為 op且子節(jié)點(diǎn)為 node(x), node(y)的節(jié)點(diǎn)時(shí)，自然完成了公共子表達(dá)式的尋找。 ? 在基本塊中，其值被引用的標(biāo)識符 ：構(gòu)造了葉節(jié)點(diǎn)的標(biāo)識符。 ? 結(jié)果能夠在基本塊外被引用的四元式 op x y z：設(shè)它對應(yīng)的節(jié)點(diǎn)為 n，如果 DAG圖構(gòu)造結(jié)束的時(shí)候， n的標(biāo)志符表不為空。 []=和 amp。=運(yùn)算符的處理 ? 對數(shù)組的賦值需要特別的處理，這是因?yàn)閿?shù)組的下標(biāo)是變量。對于數(shù)組元素的賦值可能改變數(shù)組中任何一個元素的值。 ? =[] A i t1 []= A j t2 ? amp。= y t2 t2 =[] A i t3 ? A[i]并不是公共子表達(dá)式。 ? 在處理對數(shù)組 A的元素的賦值四元式的時(shí)候，應(yīng)該注銷所有以=[]為標(biāo)記， A為左節(jié)點(diǎn)的節(jié)點(diǎn)。從而不可能在此節(jié)點(diǎn)的標(biāo)識符表中再附上其他的標(biāo)識符。 ? 處理對指針?biāo)缚臻g的賦值的時(shí)候，同樣要注銷相應(yīng)的節(jié)點(diǎn)。如果不能確定指針指向的范圍，那么，需要注銷所有的節(jié)點(diǎn)。 A i =[] j []= t1 t2 y amp。= =[] 從 DAG圖到四元式序列 ? 在 DAG圖中，有些運(yùn)算已經(jīng)進(jìn)行了合并。 ? 如果不考慮 []=和 amp。=算符，可以依照 DAG圖中的拓?fù)渑判虻玫降拇涡蜻M(jìn)行。但是，有了[]=和 amp。=算符之后，計(jì)算的次序必須修正。 ? 實(shí)際上，我們可以按照各個節(jié)點(diǎn)生成的順序來從 DAG圖生成四元式序列。 從 DAG重建四元式序列算法 ? 按照 DAG圖中各個節(jié)點(diǎn)的生成次序?qū)γ總€節(jié)點(diǎn)作如下處理： ? 若是葉子節(jié)點(diǎn)，且附加標(biāo)識符表為空，不生成四元式。 ? 若是葉子節(jié)點(diǎn)，標(biāo)記為 x，附加標(biāo)識符為 z，生成 = x z。 ? 若是內(nèi)部節(jié)點(diǎn)，附加標(biāo)識符為 z，根據(jù)其標(biāo)記 op和子節(jié)點(diǎn)數(shù)目，生成下列 4種形式的四元式。 ? op不是 =[]或 []=，也不是 relop，有兩個子節(jié)點(diǎn)，生成 op x y z ? 如果是 =[]或 []=，生成 op x y z。 ? 如果是 relop，生成 relop x y z， z是基本塊序號。 ? 只有一個子節(jié)點(diǎn)，生成 op x _ z。 從 DAG重建四元式序列算法 (續(xù) ) ? 若是內(nèi)部節(jié)點(diǎn)，且無附加標(biāo)識符，則添加一個局部于本基本塊的臨時(shí)性附加標(biāo)識符，按照上一情況生成。 ? 如果節(jié)點(diǎn)的標(biāo)識符重包含多個附加標(biāo)識符 z1,z2,… ,zk時(shí)： ? 若是葉子節(jié)點(diǎn)，標(biāo)記為 z，生成一系列四元式 ? = z z1 ? = z z2 ? … … … ? = z zn ? 不是葉子節(jié)點(diǎn)，生成四元式序列： ? = z z2 ? … … … ? = z zn 使用 DAG圖進(jìn)行優(yōu)化的例子 (四元式序列 ) ? 四元式序列片斷 : ? * 4 i t10 =[] A t10 t11 ? = t11 x * 4 i t12 ? []= A t12 t13 * 4 j t14 ? =[] A t14 t15 amp。= t15 t13 t13 ? * 4 j t16 []= A t16 t17 ? amp。= x t17 t17 i j B2 使用 DAG圖進(jìn)行優(yōu)化的例子 (DAG圖 ) ? 在第 10個節(jié)點(diǎn)生成后 , node(t11)變成無定義 . 1: 4 2: i 3: * t10 4: A t12 5:=[] t11 6:[]= t13 8:* 7: j t14 9: =[] t15 10:amp。= t16 11:[]= t17 12: amp。= 13: B2 x 從 DAG圖到四元式序列 ? * 4 i t10 (3) ? =[] A t10 t11 (5) ? := t11 x (5) ? []= A t10 t13 (6) ? * 4 j t14 (8) ? =[] A t14 t15 (9) ? amp。= t15 t13 t13 (10) ? []= A t14 t17 (11) ? amp。= x t17 t17 (12) ? i j B2 (13) DAG的其他應(yīng)用 ? 常量合并 : ? * 2 pi t1 ? * t1 r t2 ? = t2 l ? 無用代碼刪除 : ? 對于 = t10 t12，如果 t12不需要使用，那么，這個四元式不需要生成。 * * 2 pi r0 與循環(huán)有關(guān)的優(yōu)化 ? 循環(huán)不變表達(dá)式外提（代碼外提） ? 歸納變量刪除 ? 計(jì)算強(qiáng)度削弱 循環(huán)不變式外提（代碼外提） ? 有些表達(dá)式位于循環(huán)之內(nèi)，但是該表達(dá)式的值不隨著循環(huán)的重復(fù)執(zhí)行而改變，該表達(dá)式被稱為循環(huán)的不變表達(dá)式。 ? 如果按照前面講的代碼生成方案，每一次循環(huán)都講計(jì)算一次。 ? 如果把這個表達(dá)式提取到循環(huán)外面，該計(jì)算就只被執(zhí)行一次。從而可以獲得更加好的效率。 循環(huán)不變式的例子 ? 計(jì)算半徑為 r的從 10度到 360度的扇形的面積： ? for(n=1。 n36。 n++) ? {S:=10/360*pi*r*r*n。 printf(“Area is %f”, S)。 } ? 顯然，表達(dá)式 10/360*pi*r*r中的各個量在循環(huán)過程中不改變?？梢孕薷某绦蛉缦拢? ? C= 10/360*pi*r*r*n。 ? for(n=1。 n36。 n++) ? {S:=C*n。 printf(“Area is %f”, S)。 } ? 修改后的程序中， C的值只需要被計(jì)算一次，而原來的程序需要計(jì)算 36次。 四元式的循環(huán)不變式 ? (1)= 1 n (2) n 36 (21) ? (3)GO (4) (4)/ 10 360 tl ? (5)* tl pi t2 (6)* t2 r t3 ? (7)* t3 r t4 (8)* t4 n t5 ? (9)= t5 S … … … … ? (18)+ n 1 t9 (19)= t9 n ? (20)GO (4) (21) ? 其中，四元式 4,5,6,7是循環(huán)不變四元式。 循環(huán)不變四元式的相對性 ? 對于多重嵌套的循環(huán)，循環(huán)不變四元式是相對于某個循環(huán)而言的?？赡軐τ诟油鈱拥难h(huán)，它就不是循環(huán)不變式。 ? 例子： for(i = 1。 i10。 i++) for(n=1。 n360/(5*i)。 n++) {S:=(5*i)/360*pi*r*r*n。...} ? 5*i和 (5*i)/360*pi*r*r對于 n的循環(huán)（內(nèi)層循環(huán)）是不變表達(dá)式，但是對于外層循環(huán)，它們不是循環(huán)不變表達(dá)式。 循環(huán)不變表達(dá)式優(yōu)化需要解決的問題 ? 如何識別循環(huán)中的不變表達(dá)式？ ? 把循環(huán)表達(dá)式外提到什么地方？ ? 什么條件下，不變表達(dá)式可以外提？ 歸納變量的刪除（例子） ? 例子： prod=0。 i = 1。 for(i = 1。 i= 20。 i++) prod = prod+A[i]*B[i]。 ? i作為計(jì)數(shù)器。每次重復(fù)， i的值增加 1，而 A[i], B[i]對應(yīng)的地址 t1, t3增加 4（假定每個數(shù)組元素占 4個字節(jié)）。 ? 我們可以刪除 i，而使用 t1或者 t3進(jìn)行循環(huán)結(jié)束條件的測試。 歸納變量的刪除 ? 在循環(huán)中，如果變量 i的值隨著循環(huán)的每次重復(fù)都固定地增加或者減少某個常量，則稱 i為循環(huán)的歸納變量。 ? 如果在一個循環(huán)中有多個歸納變量，歸納變量的個數(shù)往往可以減少，甚至減少到 1個。減少歸納變量的優(yōu)化稱為歸納變量的刪除。 歸納變量的刪除（四元式例子） = 0 prod = l i * 4 i t1 =[] a t1 t2 * 4 i t3 =[] b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod + i 1 t7 = t7 i = i 20 B2 = 0 prod = 0 t1 + 4 t1 t1 + 4 t3 t3 =[] a t1 t2 =[] b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod = t1 80 B2 歸納變量的刪除 ? 歸納變量刪除一方面可以刪除變量，減少四元式，另外，刪除歸納變量同時(shí)也削減了計(jì)算強(qiáng)度。 ? 為了進(jìn)行歸納變量刪除優(yōu)化，必要的是找出歸納變量。 計(jì)算強(qiáng)度削弱 ? 在刪除歸納變量的過程中 ,已經(jīng)將一些乘法運(yùn)算轉(zhuǎn)換成為加法運(yùn)算。 ? 還有一類經(jīng)?？梢员粦?yīng)用的是對于下標(biāo)變量地址的計(jì)算。 計(jì)算強(qiáng)度削減（下標(biāo)變量） ? 對于數(shù)組 T a[n1][n2]… [nm]，其下標(biāo)變量a[i1][i2][i3]… [im]的地址計(jì)算如下： ? base+d；其中 base為 a[0][0]… [0]的地址。 ? d=((… ((i1*n2+i2)*n3+i3)… )*nm+im)*sizeof(T)。 ? 當(dāng)滿足某些情況的時(shí)候，地址的計(jì)算可以使用加法來代替乘法。 下標(biāo)變量計(jì)算強(qiáng)度的削減（例子） ? for(v1=v10。 v1v1f。 v1++) for(v2=v20。 v2v2f。 v2++) {… A[i1][i2][i3]… } ? i1, i2, i3都可以表示成為：Ck0+Ck1*V1+Ck2*V2(k=1,2,3)。 ? A[i1][i2][i3]的地址為 base+d。 d=(i1*n2*n3+i2*n3+i3)。 ? 將 i1,i2,i3的表達(dá)式代入 d的表達(dá)式，可以得到d=C0’+C1’*V1+C2’*V2. 下標(biāo)變量計(jì)算強(qiáng)度的削減（例子） ? 顯然，在上面的例子中，每次內(nèi)循環(huán) d的值增加 C2’；每次外循環(huán) , d的值增加 C1’（但是 V2被重置）。 ? 顯然我們可以這樣計(jì)算 A[i1][i2][i3]的地址： ? 在循環(huán)開始的時(shí)候，設(shè)置初值 d1=(base+C0’)+C1’*V10。 ? 在進(jìn)入外層循環(huán)后，進(jìn)入內(nèi)存循環(huán)前，設(shè)置 d2=d1+C2’*V20 ? 在內(nèi)存循環(huán)，使用 d2作為地址獲取 A[i1][i2][i3]的值。 ? 內(nèi)存循環(huán)體每次運(yùn)行結(jié)束之前，將 d2的值增加 C2’。 ? 每次外層循環(huán)體運(yùn)行結(jié)束之前，將 d1的值增加 C1’。 ? 顯然，對于 A[i1][i2][i3]的地址計(jì)算變成了加法運(yùn)算。 下標(biāo)變量計(jì)算強(qiáng)度的削減結(jié)果 D1 = base+C0+C1’*V10。 fo