[工學(xué)]編譯原理第10章-資料下載頁(yè)
2025-02-17 13:14本頁(yè)面
【正文】 沒有 ，則 構(gòu)造該結(jié)點(diǎn) n，否則就把已有的結(jié)點(diǎn) 作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為 n，轉(zhuǎn) 4。 ?copyright / 31 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 31 4.{附加標(biāo)記 A} – 如果 NODE(A)無(wú)定義 ，則把 A附加 在結(jié)點(diǎn) n上并令 NODE(A)=n； 否則先 把 A從 NODE(A)結(jié)點(diǎn)上附加標(biāo)識(shí) 符集中 刪除 （注意，如果 NODE(A)是葉結(jié)點(diǎn)，則其 標(biāo)記 A不刪除），把 A附加 到新結(jié)點(diǎn) n上并令 NODE(A)=n。轉(zhuǎn)處理下一代碼。 ? 構(gòu)造結(jié)束后，可由 DAG重新生成原基本塊的一 個(gè)優(yōu)化的代碼序列。 ?copyright / 32 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 32 基本塊的 DAG構(gòu)造舉例 p283～ 284 原代碼 (1)T0:= (2)T1:=2*T0 (3)T2:=R+r (4)A:=T1*T2 (5)B:=A (6)T3:=2*T0 (7)T4:=R+r (8)T5:=T3*T4 (9)T6:=Rr (10)B:=T5*T6 對(duì)應(yīng)表 編號(hào) 標(biāo)記 左 右 附加 標(biāo)記 DAG構(gòu)造過程 n1 T0 1 T0 n2 2 n2 T1 2 T1 n3 R0 3 R0 n4 r0 4 r0 n5 + T2 5 + 3 4 T2 n6 * A 6 * 2 5 A ,B ,B 7,T3 ,T3 ,T4 ,T4 ,T5 ,T5 n7 － T6 7 3 4 T6 n8 * B 刪除 其它 B 8 * 6 7 B 合并已知量 刪除多余運(yùn)算 刪除無(wú)用賦值 復(fù)寫傳播 A=*T2 ?copyright / 33 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 33 利用 DAG優(yōu)化舉例 p283～ 284 n1 T0 n2 T1 n3 R0 n4 r0 n5 + T2 n6 * A ,T3 ,T4 ,T5 n7 T6 n8 * B 編號(hào) 標(biāo)記 左 右 附加 標(biāo)記 1 T0 2 T1 3 R0 4 r0 5 + 3 4 T2 6 * 2 5 A ,T3 ,T4 ,T5 7 3 4 T6 8 * 6 7 B 假設(shè)所有臨時(shí)變量 塊外無(wú)用只保留 A,B 進(jìn)一步優(yōu)化代碼 (1)S1:=R+r (2)A:=*S1 (3)S2:=Rr (4)B:=A*S2 重建優(yōu)化代碼 (1)T0:= (2)T1:= (3)T3:=T1 (4)T2:=R+r (5)T4:=T2 (6)A:=*T2 (7)T5:=A (8)T6:=Rr (9)B:=A*T6 刪除無(wú)用賦值 重排代碼 換名 T2S1 T6S2 ?copyright / 34 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 34 基本塊的 DAG構(gòu)造課堂練習(xí) 原代碼 (1)T1:=A*B (2)T2:=3/2 (3)T3:=T1T2 (4)X:=T3 (5)C:=2 (6)T4:=A*B (7)T5:=18+C (8)T6:=T4*T5 (9)Y:=T6 請(qǐng)給出 DAG構(gòu)造過程 n1 A0 n2 B0 n3 * T1 合并已知量 n4 T2 n5 － T3 ,X n6 2 C ,T4 合并已知量 n7 20 T5 n8 * T6 ,Y ?copyright / 35 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 35 利用 DAG優(yōu)化課堂練習(xí) － n1 A0 n2 B0 n3 * T1 n4 T2 n5 T3 ,X n6 2 C ,T4 n7 20 T5 n8 * T6 ,Y 請(qǐng)給出重建代碼 √ √ √ (1)T1:=A*B (2)T4:=T1 √ (3)T2:= √ (4)T3:= (5)X:=T3 √ (6)C:=2 √ (7)T5:=20 √ (8)T6:=T1*20 (9)Y:=T6 假設(shè)所有臨時(shí)變量 和 C塊外無(wú)用 請(qǐng)給出 進(jìn)一步優(yōu)化代碼 僅保留與 X， Y相關(guān)內(nèi)容 (1)T1:=A*B (2)X:= (3)Y:=T1*20 ?copyright / 36 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 36 利用 DAG可實(shí)現(xiàn)的優(yōu)化 p285 ? 構(gòu)造 DAG時(shí)實(shí)現(xiàn)的優(yōu)化 – 合并已知量 刪除無(wú)用賦值 刪除多余運(yùn)算 復(fù)寫傳播 ? 從構(gòu)造出的 DAG中可得到的優(yōu)化信息 – 在基本 塊外被定值 并在基本塊內(nèi)被引用的所有標(biāo)識(shí) 符就是作為 葉子結(jié)點(diǎn) 上 的那些標(biāo)識(shí)符 – 在基本 塊內(nèi)被定值 且該值能在基本塊后面被引用的 所有標(biāo)識(shí)符，就是 DAG各結(jié)點(diǎn)上的那些 附加標(biāo)識(shí)符 ? 利用上述信息 ,可以 進(jìn)一步優(yōu)化 (刪除無(wú)用賦值 ) – 例如 某結(jié)點(diǎn)上 無(wú)附加標(biāo)記 或 附加標(biāo)記在塊外無(wú)用 ， 且 無(wú)前驅(qū) ，則 不生成 對(duì)計(jì)算該結(jié)點(diǎn)值的代碼 ?copyright / 37 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 37 循環(huán)優(yōu)化 p287 ?代碼外提 ?強(qiáng)度削弱 ?刪除歸納變量 ?copyright / 38 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 38 作業(yè)： 306 3 B1 DAG圖。（中國(guó)科技） D： =B*C E： =AB B： =B*C A： =ED 作業(yè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1