編譯原理第三版 第十章 代碼優(yōu)化

1、本章要點(diǎn)本章要點(diǎn) 階段階段: : 編譯的第四階段編譯的第四階段 任務(wù)任務(wù): :對(duì)程序進(jìn)行各種對(duì)程序進(jìn)行各種等價(jià)變換等價(jià)變換，使得從變換后，使得從變換后的程序出發(fā)，能生成更有的程序出發(fā)，能生成更有效的目標(biāo)代碼。效的目標(biāo)代碼。 重點(diǎn)重點(diǎn): : 局部?jī)?yōu)化局部?jī)?yōu)化 循環(huán)優(yōu)化循環(huán)優(yōu)化表表格格管管理理出出錯(cuò)錯(cuò)處處理理 詞詞 法法 分分 析析語(yǔ)語(yǔ) 法法 分分 析析中間代碼生成中間代碼生成優(yōu)優(yōu) 化化目標(biāo)代碼生成目標(biāo)代碼生成源程序源程序目標(biāo)程序目標(biāo)程序10.1 優(yōu)化概述優(yōu)化概述1. 問題的提出問題的提出(1) 編譯程序的作用編譯程序的作用 使計(jì)算機(jī)的使用方式從用機(jī)器語(yǔ)言編程發(fā)展到用使計(jì)算機(jī)的使用方式從用機(jī)器語(yǔ)言

2、編程發(fā)展到用高級(jí)語(yǔ)言編程。是計(jì)算機(jī)發(fā)展史上的一次飛躍。高級(jí)語(yǔ)言編程。是計(jì)算機(jī)發(fā)展史上的一次飛躍。(2) 早期編譯程序的不足早期編譯程序的不足 占用的空間大占用的空間大目標(biāo)程序質(zhì)量差目標(biāo)程序質(zhì)量差 運(yùn)行的時(shí)間長(zhǎng)運(yùn)行的時(shí)間長(zhǎng)2. 解決的方法解決的方法:代碼優(yōu)化代碼優(yōu)化:即對(duì)程序進(jìn)行各種等價(jià)變換，使得從變即對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)能生成更有效的目標(biāo)代碼。換后的程序出發(fā)能生成更有效的目標(biāo)代碼。u 優(yōu)化原則優(yōu)化原則:等價(jià)、有效、合算等價(jià)、有效、合算優(yōu)化不是目的，只是手段優(yōu)化不是目的，只是手段3. 優(yōu)化方法優(yōu)化方法 按優(yōu)化所涉及的按優(yōu)化所涉及的程序范圍程序范圍分：分： 局部?jī)?yōu)化局部?jī)?yōu)

3、化: 在基本塊上進(jìn)行的優(yōu)化在基本塊上進(jìn)行的優(yōu)化 合并已知量合并已知量 刪除無用賦值（無用代碼）刪除無用賦值（無用代碼） 刪除多余運(yùn)算（公共子表達(dá)式）刪除多余運(yùn)算（公共子表達(dá)式） 方法：方法：DAG； 特點(diǎn)：特點(diǎn)： 簡(jiǎn)單、成熟。簡(jiǎn)單、成熟。 循環(huán)優(yōu)化：循環(huán)優(yōu)化：在循環(huán)塊上進(jìn)行的優(yōu)化在循環(huán)塊上進(jìn)行的優(yōu)化 代碼外提代碼外提 運(yùn)算強(qiáng)度削弱運(yùn)算強(qiáng)度削弱 刪除歸納變量刪除歸納變量 方法：循環(huán)查找算法、數(shù)據(jù)流分析；復(fù)雜、高效。方法：循環(huán)查找算法、數(shù)據(jù)流分析；復(fù)雜、高效。 全局優(yōu)化：全局優(yōu)化：在整個(gè)程序上的優(yōu)化在整個(gè)程序上的優(yōu)化 方法：全局控制流分析、全局?jǐn)?shù)據(jù)流分析方法：全局控制流分析、全局?jǐn)?shù)據(jù)流分析; 特點(diǎn)

4、：代價(jià)大、高效。特點(diǎn)：代價(jià)大、高效。10.2 局部?jī)?yōu)化局部?jī)?yōu)化 問題：?jiǎn)栴}： 什么是基本塊？什么是基本塊？ 怎樣劃分基本塊？怎樣劃分基本塊？ 在基本塊中可以進(jìn)行哪些優(yōu)化？在基本塊中可以進(jìn)行哪些優(yōu)化？ 怎樣進(jìn)行局部?jī)?yōu)化？怎樣進(jìn)行局部?jī)?yōu)化？10.2.1 基本塊和流圖基本塊和流圖 對(duì)一給定的程序，將其劃分為若干個(gè)基本塊，對(duì)一給定的程序，將其劃分為若干個(gè)基本塊， 在各個(gè)基本塊中分別進(jìn)行優(yōu)化即在各個(gè)基本塊中分別進(jìn)行優(yōu)化即稱為局部?jī)?yōu)化稱為局部?jī)?yōu)化。1. 基本塊是指基本塊是指: 程序中一順序執(zhí)行的語(yǔ)句程序中一順序執(zhí)行的語(yǔ)句(四元式四元式)序列序列, 其中只有一個(gè)入口其中只有一個(gè)入口 (第一個(gè)語(yǔ)句第一個(gè)語(yǔ)句)

5、, 一個(gè)出口一個(gè)出口(最后一最后一個(gè)語(yǔ)句個(gè)語(yǔ)句),執(zhí)行時(shí)只能從入口進(jìn)入執(zhí)行時(shí)只能從入口進(jìn)入, 出口退出。出口退出。 2. 劃分基本塊算法劃分基本塊算法步驟步驟1. 求出四元式程序中各基本塊的入口語(yǔ)句求出四元式程序中各基本塊的入口語(yǔ)句, 它們是它們是:(1) 程序的程序的第一個(gè)第一個(gè)語(yǔ)句語(yǔ)句, 或或(2) 由條件或無條件轉(zhuǎn)移語(yǔ)句由條件或無條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)到轉(zhuǎn)到的語(yǔ)句的語(yǔ)句, 或或(3) 緊跟在緊跟在條件轉(zhuǎn)移語(yǔ)句后面條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句的語(yǔ)句;步驟步驟2. 構(gòu)造每一個(gè)入口語(yǔ)句所屬的基本塊構(gòu)造每一個(gè)入口語(yǔ)句所屬的基本塊, 它們是它們是從入口語(yǔ)句到從入口語(yǔ)句到:(1) 下一個(gè)入口語(yǔ)句下一個(gè)入口語(yǔ)句(不

6、包括它不包括它), 或或(2) 一轉(zhuǎn)移語(yǔ)句一轉(zhuǎn)移語(yǔ)句(包括它包括它), 或或(3) 一停語(yǔ)句一停語(yǔ)句;步驟步驟3. 未納入任一基本塊的語(yǔ)句未納入任一基本塊的語(yǔ)句為控制無法到達(dá)的語(yǔ)句為控制無法到達(dá)的語(yǔ)句, 可予刪除?？捎鑴h除。例例求最大公因子程序求最大公因子程序(1) read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt3. 程序流圖（程序控制流程圖程序流圖（程序控制流程圖） 在基本塊的集合上增加控制流信息來表示一個(gè)程序。在基本塊的集合上增加控制流信息來表示

7、一個(gè)程序。(1)控制流程圖是控制流程圖是: 具有唯一首結(jié)點(diǎn)的有向圖具有唯一首結(jié)點(diǎn)的有向圖 G = ( N, E, n0 )。 其中：其中：N為結(jié)點(diǎn)集為結(jié)點(diǎn)集, E為有向邊集為有向邊集, n0為首結(jié)點(diǎn)為首結(jié)點(diǎn) 所謂首結(jié)點(diǎn)所謂首結(jié)點(diǎn), 即它到圖中任一結(jié)點(diǎn)均有通路。即它到圖中任一結(jié)點(diǎn)均有通路。 控制流程圖簡(jiǎn)稱為控制流程圖簡(jiǎn)稱為流圖流圖。(2) 程序流圖程序流圖: 流圖流圖G = ( N, E, n0 ) 中中 結(jié)點(diǎn)集結(jié)點(diǎn)集N為基本塊集；為基本塊集； 首結(jié)點(diǎn)首結(jié)點(diǎn)n0為含有第一個(gè)語(yǔ)句的基本塊；為含有第一個(gè)語(yǔ)句的基本塊； 有向邊集有向邊集E的構(gòu)成規(guī)則的構(gòu)成規(guī)則:i ju 基本塊基本塊j緊跟在基本塊緊跟在

8、基本塊 i 之后之后, 且基本塊且基本塊 i 的出口語(yǔ)句不是無條件轉(zhuǎn)移語(yǔ)句或停語(yǔ)句；的出口語(yǔ)句不是無條件轉(zhuǎn)移語(yǔ)句或停語(yǔ)句；u 基本塊基本塊i 的出口語(yǔ)句是的出口語(yǔ)句是 goto (s) 或或 if . . . goto (s) 且且 (s) 是基本塊是基本塊j 的入口語(yǔ)句的入口語(yǔ)句 ； 例例 程序的四元式序列程序的四元式序列: :(1) read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:= Y(6) Y:=R(7) goto (3)(8) write Y(9) halt(1) read X(2) read Y(3) R:=X mod

9、Y(4) if R=0 goto (8)(5) X:= Y(6) Y:=R(7) goto (3)(8) write Y(9) haltB1B2B3B4程程 序序 流流 圖圖4.4.基本塊內(nèi)的優(yōu)化基本塊內(nèi)的優(yōu)化 例例對(duì)以下求向量?jī)?nèi)積的對(duì)以下求向量?jī)?nèi)積的PASCAL程序段的中間代碼進(jìn)行優(yōu)化程序段的中間代碼進(jìn)行優(yōu)化:P := 0; (設(shè)設(shè)low=1,w=4)for I := 1 to 20 do (AI地址：地址：I*w+(base-low*w)P:= P + AI * BI(1) P:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A) - 4(5) T3:=T2T1 B2(

10、6) T4:=4*I(7) T5:=addr(B) - 4(8) T6:=T5T4(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)刪除公共子表達(dá)式刪除公共子表達(dá)式 (3)、(6)為公共子式為公共子式 可將可將(6)改為改為T4:=T1B1(1) P:=0(2) I:=1 B1(3)T1:=4*I B2(4) T2:=addr(A) - 4(5) T3:=T2T1 (6) T4:=T1(7) T5:=addr(B) - 4 (8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if

11、 I20 goto (3)圖圖1 1 優(yōu)化前的四元優(yōu)化前的四元式式圖圖2 刪除公共子表達(dá)式和復(fù)寫傳播刪除公共子表達(dá)式和復(fù)寫傳播進(jìn)行復(fù)寫傳播進(jìn)行復(fù)寫傳播 B2中中(6) T4:=T1 (8) T6:=T5T4 可改為可改為(8)T6:=T5T1T4：=T1T6:=T5T1(1) P:=0 B1(2) I:=1(3)T1:=4* I B2 (4) T2:=addr(A) - 4(5) T3:=T2T1 (6) T4:=T1(7) T5:=addr(B) - 4 (8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)(

12、1) P:=0(2) I:=1 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3)T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)外提循環(huán)不變外提循環(huán)不變式式：(4)、(7)為循環(huán)為循環(huán)不變式，可外提至不變式，可外提至B1中中刪除無用代碼刪除無用代碼圖圖2 2 刪除公共子表達(dá)式和刪除公共子表達(dá)式和復(fù)寫傳播復(fù)寫傳播圖圖3 3刪除無用代碼和代碼外刪除無用代碼和代碼外提提(1) P:=0(2) I:=1 B1(4) T2:=addr(

13、A) - 4(7) T5:=addr(B) - 4(3)T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)(1) P:=0(2) I:=1 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3) T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(3) T1:=T1+4(12) if I20 goto (5)運(yùn)算強(qiáng)度削弱運(yùn)算強(qiáng)度削弱 由由(3)

14、T1:=4*I (11) I:=I+1 可改為可改為: 將將(3)外提至外提至B1 (11)后增加后增加(3) (3) T1:=T1+4圖圖3 刪除無用代碼和代碼外提刪除無用代碼和代碼外提圖圖4 運(yùn)算強(qiáng)度削弱運(yùn)算強(qiáng)度削弱(1) P:=0(2) I:=1 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3) T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(3) T1:=T1+4(12) if I20 goto (5)(5) T3:=T2T1 B2(8) T6:=T5T1

15、(9) T7:=T3*T6(10) P:=P+T7(3) T1:=T1+4(12) if T180 goto (5)(1) P:=0 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3) T1:=4變換循環(huán)控制條件變換循環(huán)控制條件刪除歸納變量刪除歸納變量 (12) if I20 goto (5) 分析分析I的作用的作用:計(jì)算計(jì)算 T1:=4*I循環(huán)控制條件循環(huán)控制條件 I20遞歸賦值遞歸賦值: I:=I+1 變換控制條件變換控制條件:計(jì)數(shù)法計(jì)數(shù)法: I20比較法比較法: T180 刪除刪除(11)圖圖4. 4. 運(yùn)算強(qiáng)度削弱運(yùn)算強(qiáng)度削弱合并已知量合并已知量 B

16、1中中(2) I:=1 (3)T1:=4*I (3) 可改為可改為: (3) T1:=4 刪除刪除(2)圖圖5. 變換循環(huán)控制條件與合并變換循環(huán)控制條件與合并已知量已知量小結(jié)小結(jié) 局部?jī)?yōu)化局部?jī)?yōu)化: 刪除公共子表達(dá)式刪除公共子表達(dá)式 合并已知量合并已知量 復(fù)寫傳播復(fù)寫傳播 刪除無用賦值刪除無用賦值 循環(huán)優(yōu)化循環(huán)優(yōu)化: 外提循環(huán)不變式外提循環(huán)不變式 運(yùn)算強(qiáng)度削弱運(yùn)算強(qiáng)度削弱 變換循環(huán)控制條件變換循環(huán)控制條件 優(yōu)化前后比較優(yōu)化前后比較:循環(huán)循環(huán)B2 優(yōu)化前優(yōu)化前 優(yōu)化后優(yōu)化后 四元式個(gè)數(shù)四元式個(gè)數(shù) 10 6乘法個(gè)數(shù)乘法個(gè)數(shù) 3 1 以上優(yōu)化方法均可用算法實(shí)現(xiàn)以上優(yōu)化方法均可用算法實(shí)現(xiàn)基本塊內(nèi)還可進(jìn)

17、行以下幾種變換基本塊內(nèi)還可進(jìn)行以下幾種變換臨時(shí)變量改名臨時(shí)變量改名. 交換語(yǔ)句的位置交換語(yǔ)句的位置. 代數(shù)變換代數(shù)變換. u說明說明: 無用賦值的判定無用賦值的判定: 對(duì)對(duì)A賦值后賦值后, A不被引用不被引用 (全局?jǐn)?shù)據(jù)流分析全局?jǐn)?shù)據(jù)流分析) 對(duì)對(duì)A賦值后賦值后, 引用前又重新賦值引用前又重新賦值 ( 容易判定容易判定) A僅在遞歸賦值僅在遞歸賦值(A:=A+C)中被引用中被引用(全局?jǐn)?shù)據(jù)全局?jǐn)?shù)據(jù)流分析流分析) #10.2.2. 基本塊的基本塊的DAG表示及其應(yīng)用表示及其應(yīng)用1. 無環(huán)路有向圖無環(huán)路有向圖DAG (Directed Acyclic Graph)(1) 定義定義: 若有向圖中所有

18、通路均非環(huán)路若有向圖中所有通路均非環(huán)路, 則稱其為則稱其為DAG(2) 基本塊的基本塊的DAG(用于描述計(jì)算過程用于描述計(jì)算過程): 是為結(jié)點(diǎn)是為結(jié)點(diǎn)附加了信息附加了信息的的DAG。 葉結(jié)點(diǎn)葉結(jié)點(diǎn):下標(biāo)記下標(biāo)記: 常數(shù)或標(biāo)識(shí)符常數(shù)或標(biāo)識(shí)符右標(biāo)記右標(biāo)記: 標(biāo)識(shí)符標(biāo)識(shí)符 內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn): 下標(biāo)記下標(biāo)記: 運(yùn)算符運(yùn)算符 右標(biāo)記右標(biāo)記: 標(biāo)識(shí)符標(biāo)識(shí)符(3) 結(jié)點(diǎn)形式結(jié)點(diǎn)形式 (1) A:=Bn1 AB 0 0型型 n2n1n1 n2n3 AopopB1 1型型A:=a+*bca:=b*-c+b*-c的的DAG（中間代（中間代 碼的圖形表碼的圖形表 示）示）2型型BC(2) A:= op B(3) A:=

19、B op C2. 基本塊基本塊DAG構(gòu)造算法構(gòu)造算法構(gòu)造構(gòu)造還原還原四元式序列四元式序列DAG 基本思想基本思想: 構(gòu)造算法構(gòu)造算法: 表格結(jié)構(gòu)表格結(jié)構(gòu):標(biāo)識(shí)符標(biāo)識(shí)符(常數(shù)常數(shù))結(jié)點(diǎn)對(duì)應(yīng)表結(jié)點(diǎn)對(duì)應(yīng)表,函數(shù)函數(shù)NODE(A)=算法大意：算法大意：對(duì)基本塊中每一個(gè)四元式對(duì)基本塊中每一個(gè)四元式A:=B op C 執(zhí)行以下步驟：執(zhí)行以下步驟： 構(gòu)造葉結(jié)點(diǎn)構(gòu)造葉結(jié)點(diǎn) NODEB、NODEC, 按四元式類型判轉(zhuǎn)按四元式類型判轉(zhuǎn);檢查合并已知量檢查合并已知量:若四元式的運(yùn)算對(duì)象均為常數(shù)若四元式的運(yùn)算對(duì)象均為常數(shù), 則生成該運(yùn)算結(jié)果的結(jié)點(diǎn)則生成該運(yùn)算結(jié)果的結(jié)點(diǎn); 檢查公共子表達(dá)式檢查公共子表達(dá)式:若四元式為公

20、共子表達(dá)式若四元式為公共子表達(dá)式, 則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)(即加右標(biāo)記即加右標(biāo)記); 檢查無用賦值檢查無用賦值: 若若NODEA已是某結(jié)點(diǎn)的右標(biāo)記已是某結(jié)點(diǎn)的右標(biāo)記, 則從該右標(biāo)記集合中刪除后再建立新結(jié)點(diǎn)。則從該右標(biāo)記集合中刪除后再建立新結(jié)點(diǎn)。n無定義無定義初始化初始化取下一條四元式取下一條四元式 (0)A:=B、（、（1）A:=opB、（、（2）A:=BopCNODE（B）定義）定義？構(gòu)造新結(jié)點(diǎn)構(gòu)造新結(jié)點(diǎn)n標(biāo)記為標(biāo)記為B找到標(biāo)記為找到標(biāo)記為B B的結(jié)點(diǎn)，設(shè)為的結(jié)點(diǎn)，設(shè)為nB為常數(shù)葉結(jié)點(diǎn)為常數(shù)葉結(jié)點(diǎn)？計(jì)算計(jì)算P=op B刪除剛生成刪除剛生成B結(jié)點(diǎn)結(jié)點(diǎn)DAG中有唯一

21、后繼中有唯一后繼為為B且標(biāo)記為且標(biāo)記為op的結(jié)的結(jié)？NODE（P）定義）定義？生成新結(jié)生成新結(jié)n標(biāo)為標(biāo)為P找到結(jié)點(diǎn)設(shè)找到結(jié)點(diǎn)設(shè)n有有,設(shè)為設(shè)為n構(gòu)造新結(jié)點(diǎn)構(gòu)造新結(jié)點(diǎn)n標(biāo)為標(biāo)為P，令，令B為其唯一為其唯一后繼后繼NODE（A）定義？）定義？將將A標(biāo)記在結(jié)點(diǎn)標(biāo)記在結(jié)點(diǎn)n上上NODE（C）定義）定義？生成新結(jié)生成新結(jié)n標(biāo)為標(biāo)為C找到結(jié)點(diǎn)設(shè)為找到結(jié)點(diǎn)設(shè)為nB和和C都為常數(shù)都為常數(shù)？計(jì)算計(jì)算P=Bop C刪除剛生成刪除剛生成的新結(jié)的新結(jié)B和和CDAG中有以中有以B、C為后繼且標(biāo)記為后繼且標(biāo)記為為op的結(jié)點(diǎn)？的結(jié)點(diǎn)？有，設(shè)為有，設(shè)為n 構(gòu)造新結(jié)點(diǎn)構(gòu)造新結(jié)點(diǎn)n標(biāo)為標(biāo)為P，令，令B、C為其為其左右后繼左右后繼

22、NODE（P）定義）定義？生成新結(jié)生成新結(jié)n標(biāo)為標(biāo)為P找到結(jié)點(diǎn)設(shè)找到結(jié)點(diǎn)設(shè)nNYYNNYNY將將A從原從原結(jié)刪除結(jié)刪除NNYYNY(0)(1)(2)算法框圖：算法框圖：例例 試構(gòu)造以下基本塊的試構(gòu)造以下基本塊的DAG(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+S(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+S(8) T5:=T3*T4(9) T6:=R - S(10) B:=T5*T6n1n2n3n4n5n6n8n7 T6 _ 構(gòu)造構(gòu)造DAG還原為四元式還原為四元式(1)T0:=3.14(2)T1:=6.28(3)T3:=6.28(

23、4)T2:=R+S(5)T4:=T2(6)A:=6.28*T2(7)T5:=A(8)T6:=R - S(9)B:=A*T6 效果分析效果分析比較比較 運(yùn)運(yùn) 算算已知量已知量 公共公共 無用無用 乘乘 法法 加、減法加、減法 總條數(shù)總條數(shù) 子式子式 賦值賦值 優(yōu)化前優(yōu)化前 (2) (6) (3) (7) (5) 5條條 3條條 10條條優(yōu)化后優(yōu)化后 已合并已合并 已刪除已刪除 已刪除已刪除 2條條 2條條 9條條 3.14T0n226.28T1RS+T2*AT3,T4,T5*B,B3. DAG的其它優(yōu)化信息的其它優(yōu)化信息(1) 優(yōu)化信息優(yōu)化信息葉結(jié)點(diǎn)的下標(biāo)記標(biāo)識(shí)符：塊外定值葉結(jié)點(diǎn)的下標(biāo)記標(biāo)識(shí)符：

24、塊外定值, 塊內(nèi)引用的標(biāo)塊內(nèi)引用的標(biāo)識(shí)符識(shí)符各結(jié)點(diǎn)的右標(biāo)記標(biāo)識(shí)符：塊內(nèi)定值各結(jié)點(diǎn)的右標(biāo)記標(biāo)識(shí)符：塊內(nèi)定值, 塊外可引用的塊外可引用的標(biāo)識(shí)符標(biāo)識(shí)符(2) 進(jìn)一步優(yōu)化進(jìn)一步優(yōu)化: 刪除其它形式的無用賦值刪除其它形式的無用賦值 A被賦值被賦值,永遠(yuǎn)不引用永遠(yuǎn)不引用:A不出現(xiàn)在任何基本塊的葉不出現(xiàn)在任何基本塊的葉結(jié)點(diǎn)下標(biāo)記中，且結(jié)點(diǎn)下標(biāo)記中，且A無前驅(qū)無前驅(qū); A被定值被定值, 僅遞歸賦值中引用僅遞歸賦值中引用; A:=B op C之后為之后為 D:=A A僅此引用僅此引用 , 則可改為則可改為 D:=B op C. 例例 基本塊基本塊P: (1) A:=B*C (2) D:=B/C (3) E:=A

25、+D (4) F:=2*E (5) G:=B*C (6) H:=G*G (7) F:=H*G (8) L:=F (9) M:=Ln1 n2 n3A,G n4 D* /n8 H *n9 F,L,M n5 E* +n6n72 B CF *還原還原: (1) A:=B*C (2) G:=A (3) D:=B/C (4) E:=A+D (5) H:=G*G (6) F:=H*G (7) L:=F (8) M:=L若僅若僅G,L,M后面引用后面引用:(1) G:=B*C(2) H:=G*G(3) L:=H*G(4) M:=L若僅僅若僅僅L后面引用后面引用:(1) G:=B*C(2) H:=G*G(3)

26、L:=H*G4. DAG構(gòu)造算法的進(jìn)一步討論構(gòu)造算法的進(jìn)一步討論 對(duì)數(shù)組元素賦值對(duì)數(shù)組元素賦值 多個(gè)變量共用單元多個(gè)變量共用單元 間接賦值間接賦值(1) 對(duì)數(shù)組元素賦值對(duì)數(shù)組元素賦值例例 源程序源程序: (1) X:=AI (2) AJ:=Y (3) Z:=AI四元式四元式: (1) S1:=addr(A) - 1 (2) X:=S1I (3) S2:=addr(A) - 1 (4) S2J:=Y (5) S3:=addr(A) - 1 (6) Z:=S3I問題問題: (2),(6)是否為公共子式是否為公共子式? I=J , YAI時(shí)時(shí), XZn5 X,Z n8 = = n3 S1,S2,S3

27、n1 n2 n4 n6 n7addr(A) 1 I J Y解決方法解決方法: 構(gòu)造構(gòu)造 =結(jié)點(diǎn)時(shí)結(jié)點(diǎn)時(shí)把把a(bǔ)ddr(A)祖先結(jié)點(diǎn)中祖先結(jié)點(diǎn)中= 結(jié)點(diǎn)注銷結(jié)點(diǎn)注銷即不可再附加右標(biāo)記但可引用。即不可再附加右標(biāo)記但可引用。(取消作為公共子式的資格取消作為公共子式的資格)n9 Z-(2) 多個(gè)變量共享同一單元多個(gè)變量共享同一單元 問題問題: 對(duì)其中一個(gè)變量賦值對(duì)其中一個(gè)變量賦值, 即對(duì)其它變量賦值。即對(duì)其它變量賦值。 解決方法解決方法:構(gòu)造此類結(jié)點(diǎn)時(shí)構(gòu)造此類結(jié)點(diǎn)時(shí), 把把DAG中結(jié)點(diǎn)上與它有該關(guān)系中結(jié)點(diǎn)上與它有該關(guān)系的標(biāo)識(shí)符注銷即不可再引用該結(jié)點(diǎn)的值的標(biāo)識(shí)符注銷即不可再引用該結(jié)點(diǎn)的值, 若需要引用若需

28、要引用, 則重則重新構(gòu)造葉結(jié)點(diǎn)。新構(gòu)造葉結(jié)點(diǎn)。(3) 間接賦值間接賦值: *P:=W 問題問題: P指向哪一個(gè)變量指向哪一個(gè)變量? 解決方法解決方法: 為保險(xiǎn)計(jì)為保險(xiǎn)計(jì), 把把DAG各結(jié)點(diǎn)上標(biāo)識(shí)符均注銷。各結(jié)點(diǎn)上標(biāo)識(shí)符均注銷。(4) 如果不是按構(gòu)造結(jié)點(diǎn)的順序重寫代碼，那么將如果不是按構(gòu)造結(jié)點(diǎn)的順序重寫代碼，那么將DAG還原時(shí)還原時(shí) 需要遵循一定的次序：需要遵循一定的次序： 對(duì)數(shù)組對(duì)數(shù)組A任何元素引用或賦值任何元素引用或賦值, 必須跟在原來位于其前面必須跟在原來位于其前面的對(duì)數(shù)組的對(duì)數(shù)組A任何元素的賦值之后。任何元素的賦值之后。 對(duì)共享同一單元的變量引用或賦值對(duì)共享同一單元的變量引用或賦值,必須

29、跟在原來位于其必須跟在原來位于其前面的任何賦值之后。前面的任何賦值之后。 對(duì)任何變量的引用或賦值對(duì)任何變量的引用或賦值, 必須跟在原來位于其前面的任必須跟在原來位于其前面的任何過程調(diào)用或間接賦值之后。何過程調(diào)用或間接賦值之后。#10.3 循環(huán)優(yōu)化循環(huán)優(yōu)化 1.循環(huán)的定義：循環(huán)的定義： 程序流圖中滿足下述性質(zhì)的結(jié)點(diǎn)序列程序流圖中滿足下述性質(zhì)的結(jié)點(diǎn)序列稱為循環(huán)：稱為循環(huán)：它們是強(qiáng)連通的。它們是強(qiáng)連通的。 即其中任何兩個(gè)結(jié)點(diǎn)間必有通路即其中任何兩個(gè)結(jié)點(diǎn)間必有通路, 且該通路上的結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列且該通路上的結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列;單結(jié)點(diǎn)時(shí)有自回路。單結(jié)點(diǎn)時(shí)有自回路。 有且僅有一個(gè)入口結(jié)點(diǎn)。有且僅有一

30、個(gè)入口結(jié)點(diǎn)。 所謂入口結(jié)點(diǎn)為從序列外某結(jié)點(diǎn)有一有向邊引向它或所謂入口結(jié)點(diǎn)為從序列外某結(jié)點(diǎn)有一有向邊引向它或它為程序流圖的首結(jié)點(diǎn)。它為程序流圖的首結(jié)點(diǎn)。 例例 1234567循環(huán)循環(huán): : 6 4, 5, 6, 7 2, 3, 4, 5, 6, 7 非循環(huán)非循環(huán): 2, 4 2, 3, 4 4, 6, 7 4, 5, 7 程程 序序 流流 圖圖說明說明: :用用SPSP方法寫方法寫的程序的程序, ,其流其流圖中任何反圖中任何反復(fù)執(zhí)行的代復(fù)執(zhí)行的代碼均歸入某碼均歸入某個(gè)循環(huán)個(gè)循環(huán)(入口結(jié)點(diǎn)入口結(jié)點(diǎn)不唯一不唯一)2.循環(huán)優(yōu)化方法循環(huán)優(yōu)化方法 代碼外提代碼外提 強(qiáng)度削弱強(qiáng)度削弱 刪除歸納變量刪除歸納變量(1)代碼外提代碼外提 1)循環(huán)不變運(yùn)算循環(huán)不變運(yùn)算: 對(duì)于循環(huán)中形如對(duì)于循環(huán)中形如 A:=B op C的代碼，如果的代碼，如果B和和C均為常數(shù)均為常數(shù), 或到達(dá)它們的定值點(diǎn)在循環(huán)外或到達(dá)它們的定值點(diǎn)在循環(huán)外(由由ud鏈可知鏈可