1、一. 代碼優(yōu)化概念、目的與原則二. 代碼優(yōu)化器的地位和結(jié)構(gòu)三. 代碼優(yōu)化分類四. 代碼優(yōu)化涉及的各個(gè)環(huán)節(jié)五. 四元式的改寫六. 引例：優(yōu)化主要方法簡介優(yōu)化的目的目的是為了產(chǎn)生更高效的代碼更高效的代碼。對程序進(jìn)行各種等價(jià)變換等價(jià)變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼更有效的目標(biāo)代碼，我們通常稱這種變換為優(yōu)化優(yōu)化。優(yōu)化的原則：優(yōu)化的原則：(1)(1)等價(jià)原則等價(jià)原則(3)(3)合算原則合算原則(2)(2)有效原則有效原則經(jīng)過優(yōu)化后不應(yīng)改變不應(yīng)改變程序運(yùn)行的結(jié)果。使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間較小存儲(chǔ)空間較小。應(yīng)盡可能以較低的代價(jià)較低的代價(jià)取得較好的優(yōu)

2、化效果。編譯前端代碼生成代碼優(yōu)化器代碼優(yōu)化器控制流分析控制流分析代碼變換代碼變換數(shù)據(jù)流分析數(shù)據(jù)流分析另一類重要的優(yōu)化是在生成目標(biāo)代碼目標(biāo)代碼時(shí)進(jìn)行的這類優(yōu)化很大程序上依賴于很大程序上依賴于具體的計(jì)算機(jī)。優(yōu)化可在編譯的各個(gè)階段進(jìn)行，不是優(yōu)化可在編譯的各個(gè)階段進(jìn)行，不是“最佳化最佳化”最主要一類優(yōu)化是在目標(biāo)代碼生成以前，對語法分析后的中間代碼中間代碼進(jìn)行的。這類優(yōu)化不依賴于不依賴于具體的計(jì)算機(jī)。1.1. 按所處階段分類按所處階段分類高級(jí)語言的源程序代碼優(yōu)化，由編程人員根據(jù)程序設(shè)計(jì)技術(shù)來進(jìn)行； 單個(gè)基本塊內(nèi)局部優(yōu)化2.2. 按所涉及范圍按所涉及范圍循環(huán)優(yōu)化 涉及所有代碼全局優(yōu)化可能涉及多個(gè)基本塊選擇

3、適當(dāng)?shù)乃惴ㄋ惴?源代碼源代碼安排適當(dāng)?shù)膶?shí)現(xiàn)語句實(shí)現(xiàn)語句源代碼的優(yōu)化很重要源代碼的優(yōu)化很重要設(shè)計(jì)語義設(shè)計(jì)語義動(dòng)作時(shí)動(dòng)作時(shí)考慮產(chǎn)生更加高效的更加高效的中間代碼中間代碼為后面的優(yōu)化階段做一些可能的預(yù)備工作可能的預(yù)備工作中間代碼中間代碼安排專門專門的優(yōu)化階段，進(jìn)行各種等價(jià)變換本章討論的重點(diǎn)目標(biāo)代碼目標(biāo)代碼有效地利用寄存器選擇指令( := , B, , A) 改寫成 A:=B(op , B, , A) 改寫成 A:=op B(op , B, C, A) 改寫成 A:=B op C(=, B, C, A) 改寫成 A:=BC (=,B, ,DC) 改寫成 DC:=B (jrop, B, C, L) 改寫成

4、 if B rop C goto L(j , , , L) 改寫成 goto L 一.基本塊 二.基本塊內(nèi)的優(yōu)化方法 三.流圖 四.基本塊的DAG表示及其應(yīng)用 五.應(yīng)用DAG時(shí)的相關(guān)問題2. 2. 各個(gè)操作按代碼的排列順各個(gè)操作按代碼的排列順序執(zhí)行；序執(zhí)行；3. 3. 若任一語句被執(zhí)行，則塊若任一語句被執(zhí)行，則塊內(nèi)所有語句都被執(zhí)行；否則，內(nèi)所有語句都被執(zhí)行；否則，塊內(nèi)語句都不執(zhí)行。塊內(nèi)語句都不執(zhí)行。1.1.入口入口就是其中的第一個(gè)語句； 出口出口就是其中的最后一個(gè)語句，都是唯唯一的一的局限于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化基本塊內(nèi)的優(yōu)化，或稱為局部局部優(yōu)化優(yōu)化。所謂基本塊基本塊，是指程序中

5、一順序執(zhí)行一順序執(zhí)行的語句序列，其中只有一個(gè)一個(gè)入入口和一個(gè)出口口和一個(gè)出口。1.1.基本塊基本塊在一個(gè)基本塊中的一個(gè)名字，在程序中的某個(gè)給定點(diǎn)是活躍的活躍的，是指如果在程序中（包括在本基本塊或在其他基本塊中）它的值在該點(diǎn)以后被引用如果一條三地址語句為 x：=y + z ，則稱對x定值定值 并 引用引用y和z此時(shí)T2被定值引用了 a 和 b2.2.定值與引用定值與引用此點(diǎn)T2是活躍的因?yàn)楹竺鎯商幰昧薚2T T2 2T T2 2T T2 21. 確定四元式程序中各個(gè)基本塊的入口語句6.2.1.6.2.1. 劃分四元式程序?yàn)榛緣K的算法劃分四元式程序?yàn)榛緣K的算法(1)程序的第一個(gè)語句(2)能由

6、條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句(3)緊跟在條件轉(zhuǎn)移語句后面的語句2. 對以上求出的每一入口語句，構(gòu)造其所屬的基本塊它是由該入口語句（開始）到另一入口語句(不包括該入口語句)，或到一停語句(包括該停語句)一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)，或到之間的語句序列組成的3. 刪除無用代碼凡未被納入某一基本塊中的語句，都是程序中控制流程無法到達(dá)的語句，從而也是不會(huì)被執(zhí)行到的語句，我們可把它們從程序中刪除入口語句4.4.劃分基本塊示例劃分基本塊示例(1)(1)read Xread X(2)(2)read Yread Y(3)(3)R := X mod YR := X mod Y(4)(4)if R=0

7、 goto(8)if R=0 goto(8)(5)(5)X := YX := Y(6)(6)Y := RY := R(7)(7)goto (3)goto (3)(8)(8)write Ywrite Y(9)(9)halthalt程序的第一條語句條件轉(zhuǎn)移語句轉(zhuǎn)到的語句在條件轉(zhuǎn)移語句后的語句無條件轉(zhuǎn)移語句轉(zhuǎn)到的語句基 本 塊如：對于如：對于 T T1 1 := 2 := 2 . . T T2 2 := 4 := 4 * * T T1 1此時(shí)可把此時(shí)可把 T T2 2 := 4 := 4 * * T T1 1 變換為變換為 T T2 2 := 8 := 8若兩個(gè)運(yùn)算對象都是編譯時(shí)的已知量編譯時(shí)的已知

8、量。可以在在編譯時(shí)計(jì)算出它的值編譯時(shí)計(jì)算出它的值，而不必等到程序運(yùn)行時(shí)再計(jì)算。我們稱這種變換為合并已知量合并已知量。1.1.合并常數(shù)和已知量合并常數(shù)和已知量 如：假定在一個(gè)基本塊里有語句：如：假定在一個(gè)基本塊里有語句： （1 1）T1 := A T1 := A * * B B （6 6）T4 := A T4 := A * * B B四元式（四元式（1 1）和（）和（6 6）中，它們的運(yùn)算相同）中，它們的運(yùn)算相同而且值不變，因此（而且值不變，因此（6 6）的運(yùn)算是多余的，）的運(yùn)算是多余的，可將它等價(jià)變換為：（可將它等價(jià)變換為：（66）T4 := T1T4 := T1消除多余運(yùn)算是指對程序中重復(fù)而

9、且結(jié)果消除多余運(yùn)算是指對程序中重復(fù)而且結(jié)果不變的運(yùn)算，不變的運(yùn)算， 2.2.消除多余運(yùn)算；消除多余運(yùn)算； 如：如：（5 5）C := 2C := 2 （6 6）T4 := A T4 := A * * B B （7 7）T5 := 18 + CT5 := 18 + C （8 8）T6 := 4 T6 := 4 * * T5 T5 （9 9）Y := T6Y := T6消除無用賦值是指對程序中的無用賦值消除無用賦值是指對程序中的無用賦值予以消除予以消除 。3.3.消除無用賦值消除無用賦值 如：語句 x := y y * * * 2 2中的乘方運(yùn)算，通常需要調(diào)用一個(gè)函數(shù)來實(shí)現(xiàn)。可以用代數(shù)上等價(jià)的形式

10、，用簡單的運(yùn)算替換。 x := y y * * y y對基本塊中求值的表達(dá)式，用代數(shù)上等價(jià)的形式替換，以期使復(fù)雜運(yùn)算變成簡單運(yùn)算。我們稱這種變換為代數(shù)變換代數(shù)變換。4.4. 代數(shù)變換代數(shù)變換如果一個(gè)表達(dá)式 E 在前面已計(jì)算過，并且在這之后在這之后E E 中中變量的值沒有改變變量的值沒有改變，則稱 E 為公共子表達(dá)式公共子表達(dá)式。刪除公共子表示式刪除公共子表示式( (刪除多余運(yùn)算刪除多余運(yùn)算) )對于公共子表達(dá)式，我們可以避免對它的重復(fù)計(jì)算避免對它的重復(fù)計(jì)算，稱為刪除公共子表達(dá)式刪除公共子表達(dá)式(有時(shí)稱刪除多余運(yùn)算刪除多余運(yùn)算)。公共子表達(dá)式可以在基本塊內(nèi)基本塊內(nèi)，也可以在全局范圍內(nèi)全局范圍內(nèi)消

11、除。T6：=T2(復(fù)寫語句復(fù)寫語句)把T2賦給T6，x：=aT6中引用引用了T6的值，而這中間沒有改變這中間沒有改變T T6 6的值的值。因此，可以把x：=aT6變換為x：=aT2 這種變換稱為復(fù)寫傳播復(fù)寫傳播。5.5.復(fù)寫傳播復(fù)寫傳播( (重復(fù)傳送重復(fù)傳送) )“復(fù)寫”強(qiáng)調(diào)了重復(fù)性重復(fù)性，傳播是由復(fù)寫引起的復(fù)寫傳播的目的目的是使對某些變量的賦值變?yōu)闊o用賦值變?yōu)闊o用換言之，將來可以刪除刪除這些無用賦值語句6.6.復(fù)寫傳播示例復(fù)寫傳播示例T T6 6 := T := T2 2x := aT6x := aT2T T6 6 := T := T2 2T7 := T6T7 := T2T T6 6 :=

12、T := T2 2aT7 := T9aT2 := T9T T7 7 := T := T6 6T T8 8 := T := T4 4T9 := aT8T9 := aT4T T8 8 := T := T4 4T10 := T8T10 := T4T T8 8 := T := T4 4aT10 := xaT4 := xT T1010 := T := T8 8在在B2B2中有中有T T3 3 := aT := aT2 2 x := aT2x := T3在在B2B2中有中有T T3 3 := aT := aT2 2 aT4 := xaT4:= T3x := aTx := aT2 2 在在B3B3中有中有T

13、 T5 5 := aT := aT4 4 T9 := aT4T9 := T5在在B3B3中有中有T T5 5 := aT := aT4 4 aT2 := T9aT2 := T5T T9 9 := aT := aT4 4 由于某些變量的值在整個(gè)程序中不再被使用值在整個(gè)程序中不再被使用，因此，這些變量的賦值對程序運(yùn)算結(jié)果沒有任何作賦值對程序運(yùn)算結(jié)果沒有任何作用用。我們可以刪除對這些變量賦值的代碼。我們稱之為刪除無用賦值刪除無用賦值或刪除無用代碼刪除無用代碼。7.7. 刪除無用代碼刪除無用代碼( (刪除無用賦值刪除無用賦值) )8.8. 刪除無用代碼示例刪除無用代碼示例aTaT2 2 := T :=

14、 T5 5aTaT4 4 := T := T3 3gotogoto B2 B2無用代碼無用代碼DAG (Directed Acyclic Graph)DAG (Directed Acyclic Graph)無環(huán)路有向圖無環(huán)路有向圖一個(gè)基本塊的DAG是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG，描述出基本塊中每個(gè)運(yùn)算結(jié)果如何用于塊中后續(xù)運(yùn)算。 1.1. 概念概念1. 葉結(jié)點(diǎn)葉結(jié)點(diǎn)值值3. 結(jié)點(diǎn)標(biāo)識(shí)符結(jié)點(diǎn)標(biāo)識(shí)符2.其他結(jié)點(diǎn)其他結(jié)點(diǎn)運(yùn)算或運(yùn)算或變量變量圖的葉結(jié)點(diǎn)以一標(biāo)識(shí)標(biāo)識(shí)符符( (變量名變量名) )或常數(shù)常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值值。如果葉結(jié)點(diǎn)用來代表某變量變量A A的地址的地址，

15、則用addr(A)addr(A)作為該結(jié)點(diǎn)的標(biāo)記內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)以一運(yùn)算符運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果運(yùn)算的結(jié)果圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量這些變量具有該結(jié)點(diǎn)所代表的值 四元式的類型與DAG結(jié)點(diǎn) 數(shù)組元素的賦值數(shù)組元素的賦值A(chǔ)B := CAB := C為為3 3型四元式，將在型四元式，將在6.2.46.2.4節(jié)節(jié)討論；轉(zhuǎn)移討論；轉(zhuǎn)移gotogoto (s) (s) 是一個(gè)孤立結(jié)點(diǎn)是一個(gè)孤立結(jié)點(diǎn) 。2.2. 構(gòu)造基本塊的構(gòu)造基本塊的DAGDAG的思想的思想對于基本塊中的每個(gè)四元式對于基本塊中的每個(gè)四元式A :=

16、B op CA := B op C 1.1.如果它們都是葉結(jié)點(diǎn)，且其標(biāo)記均為常數(shù)，則如果它們都是葉結(jié)點(diǎn)，且其標(biāo)記均為常數(shù)，則直接執(zhí)行運(yùn)算直接執(zhí)行運(yùn)算B op CB op C，然后建立以其運(yùn)算結(jié)果，然后建立以其運(yùn)算結(jié)果P P為標(biāo)記的葉結(jié)點(diǎn)并把為標(biāo)記的葉結(jié)點(diǎn)并把A A附加到此結(jié)點(diǎn)上去附加到此結(jié)點(diǎn)上去 （如果以B或C為標(biāo)記的結(jié)點(diǎn)是為處理本四元式才建立的，則將它們刪除） 。首先找出（或建立）代表B和C“當(dāng)前值”的結(jié)點(diǎn) 2. 2. 如果如果B B或（和）或（和）C C是內(nèi)部結(jié)點(diǎn)，則建立以是內(nèi)部結(jié)點(diǎn)，則建立以opop為為標(biāo)記的新結(jié)點(diǎn)，此結(jié)點(diǎn)分別以標(biāo)記的新結(jié)點(diǎn)，此結(jié)點(diǎn)分別以B B、C C所標(biāo)記的所標(biāo)記的結(jié)點(diǎn)

17、為其左、右直接后繼結(jié)點(diǎn)，并將結(jié)點(diǎn)為其左、右直接后繼結(jié)點(diǎn)，并將A A附加到附加到新建的結(jié)點(diǎn)上。新建的結(jié)點(diǎn)上。 注意，若在此之前，注意，若在此之前，DAGDAG中已有結(jié)點(diǎn)其上有附中已有結(jié)點(diǎn)其上有附加標(biāo)記加標(biāo)記A A，且此結(jié)點(diǎn)無前驅(qū)，則在建立新結(jié)點(diǎn)，且此結(jié)點(diǎn)無前驅(qū)，則在建立新結(jié)點(diǎn)的同時(shí)，應(yīng)把老結(jié)點(diǎn)上附加的的同時(shí)，應(yīng)把老結(jié)點(diǎn)上附加的A A刪除，以表示刪除，以表示A A的當(dāng)前值由新建立的結(jié)點(diǎn)代表；的當(dāng)前值由新建立的結(jié)點(diǎn)代表； v3.若DAG中原來已有代表B op C的結(jié)點(diǎn)，則不必建立新的結(jié)點(diǎn)，只須把變量A附加到表示B op C之值的結(jié)點(diǎn)上去即可。2.2. 構(gòu)造基本塊的構(gòu)造基本塊的DAGDAG的算法（算法

18、的算法（算法6.26.2）1. 葉結(jié)點(diǎn)生成葉結(jié)點(diǎn)生成 代碼類型判斷代碼類型判斷3.查找、處理公共子表達(dá)式查找、處理公共子表達(dá)式2.常數(shù)參數(shù)與非常數(shù)參數(shù)的判斷常數(shù)參數(shù)與非常數(shù)參數(shù)的判斷4.賦值號(hào)處理賦值號(hào)處理 構(gòu)造基本塊的構(gòu)造基本塊的DAGDAG的算法流程的算法流程初始化生成B01生成CB是常數(shù)2B不是常數(shù)尋找公共子表達(dá)式B、C都是常數(shù)B或者C不是常數(shù)合并已知量生成新常數(shù)P處理賦值號(hào)處理A合并已知量生成新常數(shù)P尋找公共子表達(dá)式n13.14T0T T0 0 := 3.14 := 3.14T T1 1 := 2 := 2 * * T T0 0T T2 2 := R + r := R + rA :=

19、TA := T1 1 * * T T2 2B := AB := AT T3 3 := 2 := 2 * * T T0 0T T4 4 := R + r := R + rT T5 5 := T := T3 3 * * T T4 4T T6 6 := R r := R rB := TB := T5 5 * * T T6 6文法文法G GNODE(3.14)NODE(3.14)無定義，構(gòu)造一個(gè)標(biāo)記為無定義，構(gòu)造一個(gè)標(biāo)記為3.143.14的結(jié)點(diǎn)的結(jié)點(diǎn)當(dāng)前代碼為當(dāng)前代碼為0 0型，記型，記NODE(3.14)NODE(3.14)的值為的值為n1,n1,轉(zhuǎn)轉(zhuǎn)4 4T T0 0 := 3.14 := 3.1

20、4NODE(TNODE(T0 0) )無定義，將無定義，將T T0 0附加在結(jié)點(diǎn)附加在結(jié)點(diǎn)n1n1上上令令NODE(TNODE(T0 0) = n1) = n1，轉(zhuǎn)處理下一條代碼，轉(zhuǎn)處理下一條代碼T T1 1 := 2 := 2 * * T T0 0NODE(2)NODE(2)無定義，構(gòu)造一個(gè)標(biāo)記為無定義，構(gòu)造一個(gè)標(biāo)記為2 2的結(jié)點(diǎn)的結(jié)點(diǎn)當(dāng)前代碼為當(dāng)前代碼為2 2型，型，NODE(TNODE(T0 0) )已定義，轉(zhuǎn)已定義，轉(zhuǎn)2 2（2 2）NODE(2) NODE(2) 和和NODE(TNODE(T0 0) )均均已定義，轉(zhuǎn)已定義，轉(zhuǎn)2 2（4 4）執(zhí)行執(zhí)行 2 2 * * T T0 0 ，

21、新得到常數(shù)，新得到常數(shù)6.28 ,NODE(2) 6.28 ,NODE(2) 是處理當(dāng)前代碼時(shí)是處理當(dāng)前代碼時(shí)新構(gòu)造出來的，刪除之，新構(gòu)造出來的，刪除之，NODE(6.28)NODE(6.28)無定義，無定義，構(gòu)造一個(gè)標(biāo)記構(gòu)造一個(gè)標(biāo)記為為6.286.28的結(jié)點(diǎn)的結(jié)點(diǎn)n2n2，置，置NODE(6.28) = n2NODE(6.28) = n2，轉(zhuǎn)，轉(zhuǎn)4 4NODE(TNODE(T1 1) )無定義，將無定義，將T T1 1附加在結(jié)點(diǎn)附加在結(jié)點(diǎn)n2n2上上令令NODE(TNODE(T1 1) = n2) = n2，轉(zhuǎn)處理下一條代碼，轉(zhuǎn)處理下一條代碼n22T1n26.28T T2 2 := R +

22、r := R + rNODE(R)NODE(R)無定義，構(gòu)造一個(gè)標(biāo)記為無定義，構(gòu)造一個(gè)標(biāo)記為R R的結(jié)點(diǎn)的結(jié)點(diǎn)n3n3，令令NODE(R) = NODE(R) = n3n3當(dāng)前代碼為當(dāng)前代碼為2 2型，型，NODE(r) NODE(r) 無定義，無定義，構(gòu)造一個(gè)標(biāo)記為構(gòu)造一個(gè)標(biāo)記為r r的結(jié)點(diǎn)的結(jié)點(diǎn)n4n4，令令NODE(r) = n4NODE(r) = n4，轉(zhuǎn)，轉(zhuǎn)2 2（2 2）n3Rn4rNODE(R) NODE(R) 不是標(biāo)記為常數(shù)的結(jié)點(diǎn)，轉(zhuǎn)不是標(biāo)記為常數(shù)的結(jié)點(diǎn)，轉(zhuǎn)3 3（2 2）DAGDAG中無結(jié)點(diǎn)其左后繼為中無結(jié)點(diǎn)其左后繼為NODE(R) NODE(R) ，故構(gòu)造一個(gè)結(jié)點(diǎn)，故構(gòu)造一

23、個(gè)結(jié)點(diǎn)n5n5，其左后繼為其左后繼為NODE(R)NODE(R)，右后繼為，右后繼為 NODE(r)NODE(r)，轉(zhuǎn)，轉(zhuǎn)4 4n5+NODE(TNODE(T2 2) )無定義，將無定義，將T T2 2附加在結(jié)點(diǎn)附加在結(jié)點(diǎn)n5n5上，上，令令NODE(T2) = n5NODE(T2) = n5，轉(zhuǎn)處理下一條代碼，轉(zhuǎn)處理下一條代碼T2A := TA := T1 1 * * T T2 2NODE(TNODE(T1 1) )已定義，當(dāng)前代碼為已定義，當(dāng)前代碼為2 2型，型， NODE(TNODE(T2 2) )已定義，轉(zhuǎn)已定義，轉(zhuǎn)2 2（2 2）NODE(TNODE(T1 1) )不是標(biāo)記為常數(shù)的結(jié)

24、點(diǎn)，不是標(biāo)記為常數(shù)的結(jié)點(diǎn)，轉(zhuǎn)轉(zhuǎn)3 3（2 2）DAGDAG中無結(jié)點(diǎn)其左后繼為中無結(jié)點(diǎn)其左后繼為NODE(TNODE(T1 1) )，故構(gòu)造結(jié)點(diǎn)，故構(gòu)造結(jié)點(diǎn)n6n6，其左后繼為其左后繼為NODE(TNODE(T1 1) )，右后繼為右后繼為NODE(TNODE(T2 2) )，轉(zhuǎn)，轉(zhuǎn)4 4n6*NODE(A)NODE(A)無定義，將無定義，將A A附加到結(jié)點(diǎn)附加到結(jié)點(diǎn)n6n6上，上，令令NODE(A) = n6NODE(A) = n6，轉(zhuǎn)處理下一條代碼，轉(zhuǎn)處理下一條代碼AB := AB := ANODE(A)NODE(A)已定義，當(dāng)前代碼為已定義，當(dāng)前代碼為0 0型，轉(zhuǎn)型，轉(zhuǎn)4 4NODE(B)

25、NODE(B)無定義，將無定義，將B B附加到結(jié)點(diǎn)附加到結(jié)點(diǎn)n6n6上，上，令令NODE(B) = n6NODE(B) = n6，轉(zhuǎn)處理下一條代碼，轉(zhuǎn)處理下一條代碼T T3 3 := 2 := 2 * * T T0 0NODE(2)NODE(2)無定義，構(gòu)造一個(gè)標(biāo)記為無定義，構(gòu)造一個(gè)標(biāo)記為2 2的結(jié)點(diǎn)的結(jié)點(diǎn)n7n7，令令NODE(2) = n7NODE(2) = n7n72當(dāng)前代碼為當(dāng)前代碼為2 2型，型，NODE(TNODE(T0 0) )已定義，轉(zhuǎn)已定義，轉(zhuǎn)2 2（2 2）NODE(2)NODE(2)和和NODE(TNODE(T0 0) )都為標(biāo)記為常數(shù)的結(jié)點(diǎn)，轉(zhuǎn)都為標(biāo)記為常數(shù)的結(jié)點(diǎn)，轉(zhuǎn)2

26、 2（4 4）執(zhí)行執(zhí)行2 2 * * T T0 0 ，得到，得到6.286.28，NODE(2)NODE(2)是處理當(dāng)前代碼時(shí)構(gòu)造出來的，刪除之；是處理當(dāng)前代碼時(shí)構(gòu)造出來的，刪除之；NODE(6.28)NODE(6.28)已有定義已有定義n2n2，轉(zhuǎn)，轉(zhuǎn)4 4NODE(TNODE(T3 3) )無定義，將無定義，將T3T3附加到附加到NODE(6.28)NODE(6.28)上，上，即附加到即附加到n2n2上，轉(zhuǎn)處理下一條代碼上，轉(zhuǎn)處理下一條代碼T1,T3A,BT T4 4 := R + r := R + rNODE(R)NODE(R)已定義，當(dāng)前代碼為已定義，當(dāng)前代碼為2 2型，型， NODE

27、(rNODE(r) )已定義，轉(zhuǎn)已定義，轉(zhuǎn)2 2（2 2）NODE(R)NODE(R)不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，轉(zhuǎn)不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，轉(zhuǎn)3 3（2 2）DAGDAG中結(jié)點(diǎn)中結(jié)點(diǎn)n5n5其左后繼為其左后繼為NODE(R)NODE(R)，右后繼為，右后繼為NODE(rNODE(r),),且其標(biāo)記為且其標(biāo)記為 + + ，故將，故將n5n5作為當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)作為當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)4 4NODE(TNODE(T4 4) )無定義，將無定義，將T T4 4附加到結(jié)點(diǎn)附加到結(jié)點(diǎn)n5n5上，上，令令NODE(TNODE(T4 4) = n5 ) = n5 ，轉(zhuǎn)處理下一條代碼，轉(zhuǎn)處理下一條代碼T2,T4T T5 5

28、:= T := T3 3 * * T T4 4NODE(TNODE(T3 3) )已定義，當(dāng)前代碼為已定義，當(dāng)前代碼為2 2型，型，NODE(TNODE(T4 4) ) 已定義已定義 ，轉(zhuǎn)，轉(zhuǎn)2 2（2 2）NODE(TNODE(T4 4) ) 不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn) ，轉(zhuǎn)，轉(zhuǎn)3 3（2 2）DAGDAG中結(jié)點(diǎn)中結(jié)點(diǎn)n6n6其左后繼為其左后繼為NODE(TNODE(T3 3) )，右后繼為，右后繼為NODE(TNODE(T4 4) )，且標(biāo)記為且標(biāo)記為 * * ，故將，故將n6n6作為當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)作為當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)4 4NODE(TNODE(T5 5) )無定義，故將無定義

29、，故將T T5 5附加到結(jié)點(diǎn)附加到結(jié)點(diǎn)n6n6上，上，轉(zhuǎn)處理下一條代碼轉(zhuǎn)處理下一條代碼A,B,T5T T6 6 := R r := R rNODE(R)NODE(R)已定義，當(dāng)前代碼為已定義，當(dāng)前代碼為2 2型，型，NODE(rNODE(r) )已定義，轉(zhuǎn)已定義，轉(zhuǎn)2 2（2 2）NODE(R)NODE(R)不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，轉(zhuǎn)不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，轉(zhuǎn)3 3（2 2）DAGDAG中無結(jié)點(diǎn)其左后繼為中無結(jié)點(diǎn)其左后繼為NODE(R)NODE(R)，右后繼為，右后繼為NODE(rNODE(r) )，且標(biāo)記為且標(biāo)記為 - - ；故構(gòu)造結(jié)點(diǎn)；故構(gòu)造結(jié)點(diǎn)n7n7，使，使其左后繼為其左后繼為NODE

30、(R)NODE(R)，右后繼為右后繼為NODE(rNODE(r) )，且標(biāo)記為，且標(biāo)記為 - - ，轉(zhuǎn)，轉(zhuǎn)4 4n7-NODE(TNODE(T6 6) )無定義，將無定義，將T T6 6附加到結(jié)點(diǎn)附加到結(jié)點(diǎn)n7n7上，上，轉(zhuǎn)處理下一條代碼轉(zhuǎn)處理下一條代碼T6B := TB := T5 5 * * T T6 6NODE(TNODE(T5 5) )已定義，當(dāng)前代碼為已定義，當(dāng)前代碼為2 2型，型，NODE(TNODE(T6 6) )已定義，已定義，轉(zhuǎn)轉(zhuǎn)2 2（2 2）NODE(TNODE(T5 5) )不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，轉(zhuǎn)轉(zhuǎn)3 3（2 2）DAGDAG中無結(jié)點(diǎn)其左后繼

31、為中無結(jié)點(diǎn)其左后繼為NODE(TNODE(T5 5) )，故構(gòu)造結(jié)點(diǎn)故構(gòu)造結(jié)點(diǎn)n8n8，使其左后繼為，使其左后繼為NODE(TNODE(T5 5) )，右后繼為右后繼為NODE(TNODE(T6 6) )，且標(biāo)記為，且標(biāo)記為 * * ，轉(zhuǎn)，轉(zhuǎn)4 4n8*NODE(B)NODE(B)已定義，故將已定義，故將B B從從NODE(B)NODE(B)結(jié)點(diǎn)（當(dāng)前為結(jié)點(diǎn)（當(dāng)前為n6n6）中的附加標(biāo)識(shí)符集中刪除中的附加標(biāo)識(shí)符集中刪除A,T5B將將B B附加到附加到n8n8上，令上，令NODE(B) = n8NODE(B) = n8，轉(zhuǎn)處理下一條代碼，轉(zhuǎn)處理下一條代碼所有代碼處理完畢，構(gòu)造過程結(jié)所有代碼處理完

32、畢，構(gòu)造過程結(jié)束束文法文法G G的最終的最終DAGDAG如上圖所示如上圖所示4.4. 構(gòu)構(gòu)造造DAGDAG示例示例例例6.2 對如下的基本塊構(gòu)造基本塊DAG ：（1） T1 := A*B（2） T2 := 3/2（3） T3 := T1-T2（4） X := T3（5） C := 5（6） T4 := A*B（7） C := 2（8） T5 := 18+C（9） T6 := T4*T5（10）Y := T 基本塊的優(yōu)化處理 v第一，合并常數(shù)和已知量的運(yùn)算，并將產(chǎn)生第一，合并常數(shù)和已知量的運(yùn)算，并將產(chǎn)生的運(yùn)算結(jié)果標(biāo)記為葉結(jié)點(diǎn)，不再產(chǎn)生運(yùn)算的的運(yùn)算結(jié)果標(biāo)記為葉結(jié)點(diǎn)，不再產(chǎn)生運(yùn)算的內(nèi)部結(jié)點(diǎn)（見圖內(nèi)部

33、結(jié)點(diǎn)（見圖6-2(b), (g)） T2 := 3/2v第二，合并公共子表達(dá)式第二，合并公共子表達(dá)式v 基本塊內(nèi)多次出現(xiàn)同一運(yùn)算的四元式，僅基本塊內(nèi)多次出現(xiàn)同一運(yùn)算的四元式，僅構(gòu)造第一個(gè)四元式運(yùn)算的內(nèi)部結(jié)點(diǎn)；以后的構(gòu)造第一個(gè)四元式運(yùn)算的內(nèi)部結(jié)點(diǎn)；以后的各次出現(xiàn)，只把要賦予結(jié)果的各變量標(biāo)識(shí)符各次出現(xiàn)，只把要賦予結(jié)果的各變量標(biāo)識(shí)符附加到相應(yīng)內(nèi)部結(jié)點(diǎn)（見圖附加到相應(yīng)內(nèi)部結(jié)點(diǎn)（見圖6-2(e)）（1） T1 := A*B（3） T3 := T1-T2（4） X := T3（6） T4 := A*Bv第三，消除基本塊內(nèi)無用賦值。第三，消除基本塊內(nèi)無用賦值。v在基本塊內(nèi)被多次賦值的變量，若在被引用之在基本

34、塊內(nèi)被多次賦值的變量，若在被引用之前被再次賦值，算法前被再次賦值，算法6.2的第（的第（4）步，除了把）步，除了把此變量名附加到新產(chǎn)生的結(jié)點(diǎn)之外，還把它從此變量名附加到新產(chǎn)生的結(jié)點(diǎn)之外，還把它從老結(jié)點(diǎn)的附加標(biāo)識(shí)符集中逐出（見圖老結(jié)點(diǎn)的附加標(biāo)識(shí)符集中逐出（見圖6-2(f)），），使對該變量的前一次賦值無效使對該變量的前一次賦值無效v C=5 v c=2由由DAGDAG重寫代碼重寫代碼重寫中間代碼的順序應(yīng)遵循重寫中間代碼的順序應(yīng)遵循(2)(2)轉(zhuǎn)移語句轉(zhuǎn)移語句( (如果有的話如果有的話) )仍然是基本仍然是基本塊的最后一個(gè)語句塊的最后一個(gè)語句 ( (保證基本塊的正確性保證基本塊的正確性) )(1)

35、(1)其中任一內(nèi)部結(jié)點(diǎn)在其后繼結(jié)點(diǎn)之其中任一內(nèi)部結(jié)點(diǎn)在其后繼結(jié)點(diǎn)之前被重寫前被重寫( (保證計(jì)算的正確性保證計(jì)算的正確性) )目的：生成有效目標(biāo)代碼目的：生成有效目標(biāo)代碼n13.14T0B := A B := A * * T T6 6n26.28n3Rn4rn5+n6*T1,T3T2,T4n7-T6n8*A,T5BT T0 0 := 3.14 := 3.14T T1 1 := 6.28 := 6.28T T3 3 := 6.28 := 6.28T T2 2 := R + r := R + rT T4 4 := T := T2 2A := 6.28 A := 6.28 * * T T2 2T T

36、5 5 := A := AT T6 6 := R r := R rT T0 0T T1 1T T3 3T T2 2T T4 4A AT T5 5T T6 6B B基本塊基本塊n1n1結(jié)點(diǎn)標(biāo)記為常數(shù)，結(jié)點(diǎn)標(biāo)記為常數(shù)，故產(chǎn)生故產(chǎn)生 T T0 0 := 3.14 := 3.14n2n2結(jié)點(diǎn)標(biāo)記為常數(shù)，結(jié)點(diǎn)標(biāo)記為常數(shù)，故產(chǎn)生故產(chǎn)生 T T1 1 := 6 := 6.28.286.6. 由由DAGDAG重寫重寫代碼示例代碼示例n2n2結(jié)點(diǎn)標(biāo)記為常數(shù)，結(jié)點(diǎn)標(biāo)記為常數(shù)，故產(chǎn)生故產(chǎn)生 T T3 3 := 6.28 := 6.28T T4 4與與T T2 2同標(biāo)記在一個(gè)結(jié)點(diǎn)，同標(biāo)記在一個(gè)結(jié)點(diǎn)，故產(chǎn)生故產(chǎn)生 T

37、T4 4 := T := T2 2T T5 5與與A A同標(biāo)記在一個(gè)結(jié)點(diǎn)，同標(biāo)記在一個(gè)結(jié)點(diǎn)，故產(chǎn)生故產(chǎn)生 T T5 5 := A := An2n2結(jié)點(diǎn)標(biāo)記為常數(shù)，結(jié)點(diǎn)標(biāo)記為常數(shù)，故產(chǎn)生故產(chǎn)生 A := 6.28 A := 6.28 * * T T2 2重寫過程結(jié)束重寫過程結(jié)束，基本塊基本塊如上所示如上所示B := A B := A * * T T6 6T T0 0 := 3.14 := 3.14T T1 1 := 6.28 := 6.28T T3 3 := 6.28 := 6.28T T2 2 := R + r := R + rT T4 4 := T := T2 2A := 6.28 A :=

38、 6.28 * * T T2 2T T5 5 := A := AT T6 6 := R r := R rT T0 0 := 3.14 := 3.14T T1 1 := 2 := 2 * * T T0 0B := TB := T5 5 * * T T6 6T T2 2 := R + r := R + rA := TA := T1 1 * * T T2 2B := AB := AT T3 3 := 2 := 2 * * T T0 0T T4 4 := R + r := R + rT T5 5 := T := T3 3 * * T T4 4T T6 6 := R r := R r基本塊基本塊G G基

39、本塊基本塊GG優(yōu)化效果比較優(yōu)化效果比較消除無用賦值合并公共子表達(dá)式合并常數(shù)和已知量的運(yùn)算v3 3型四元式型四元式BC:=DBC:=D對應(yīng)的對應(yīng)的DAGDAG結(jié)點(diǎn)形式結(jié)點(diǎn)形式x := aix := aiaj := yaj := yz := ai z := ai 四元式序列為：四元式序列為：（1 1）T1:=addr(A)-1T1:=addr(A)-1（2 2）X:=T1iX:=T1i（3 3）T2:=addr(A)-1T2:=addr(A)-1（4 4）T2j:=YT2j:=Y（5 5）T3:=addr(A)-1T3:=addr(A)-1（6 6）Z:=T3iZ:=T3i例考慮如下的源程序段：例

40、考慮如下的源程序段：v基本塊的DAG，算法6.2（1 1）T1:=addr(A)-1T1:=addr(A)-1（2 2）X:=T1iX:=T1i（3 3）T2:=addr(A)-1T2:=addr(A)-1（4 4）T2j:=YT2j:=Y（5 5）T3:=addr(A)-1T3:=addr(A)-1（6 6）Z:=T3iZ:=T3i；優(yōu)化：優(yōu)化：（1 1）T1 := addr(A)-1T1 := addr(A)-1（2 2）X := T1iX := T1i（3 3）Z := XZ := X（4 4）T1j := YT1j := Y原因：原因：對一個(gè)數(shù)對一個(gè)數(shù)組元素賦值時(shí)，組元素賦值時(shí)，可能改

41、變表達(dá)可能改變表達(dá)式式aiai的的值值，所以即使所以即使a a和和i i都沒有改變，都沒有改變，其值可能已改其值可能已改變了。變了。優(yōu)化前優(yōu)化前x := aix := aiaj := yaj := yz := ai z := ai 此時(shí)此時(shí)Z=yZ=y優(yōu)化后優(yōu)化后x := aix := aiz := xz := xaj := y aj := y 此時(shí)此時(shí)Z=aiZ=ai例：在例：在 i = j i = j 并且并且 y != ai y != ai 時(shí)，時(shí)，2.2. 數(shù)組元素引用問題解決方法數(shù)組元素引用問題解決方法 在建立對一個(gè)數(shù)組在建立對一個(gè)數(shù)組A A的元素賦值的結(jié)點(diǎn)時(shí)，的元素賦值的結(jié)點(diǎn)時(shí)，“

42、封鎖封鎖”那些以那些以addr(Aaddr(A) )作為它的后代之一、作為它的后代之一、且所標(biāo)記的運(yùn)算符為且所標(biāo)記的運(yùn)算符為“= ”= ”的結(jié)點(diǎn)。的結(jié)點(diǎn)。 謂封鎖一個(gè)結(jié)點(diǎn)，是指在該結(jié)點(diǎn)上做一個(gè)謂封鎖一個(gè)結(jié)點(diǎn)，是指在該結(jié)點(diǎn)上做一個(gè)標(biāo)志標(biāo)志，表示不允許在這些結(jié)點(diǎn)上再附加任，表示不允許在這些結(jié)點(diǎn)上再附加任何新的標(biāo)識(shí)符，從而何新的標(biāo)識(shí)符，從而取消了它作為公共子表取消了它作為公共子表達(dá)式的資格達(dá)式的資格。v所構(gòu)造的DAG 優(yōu)化后的四元式序列 （1 1）T1 := addr(A)-1T1 := addr(A)-1（2 2）X := T1iX := T1i（3 3）T1j := Y T1j := Y （4

43、4）Z := T1iZ := T1i與原四元式是完全等價(jià)與原四元式是完全等價(jià) 6.3 全局優(yōu)化 全局優(yōu)化需要在整個(gè)程序范圍內(nèi)，對程序全局優(yōu)化需要在整個(gè)程序范圍內(nèi)，對程序中的全部變量的中的全部變量的定值和引用定值和引用之間的關(guān)系進(jìn)行分之間的關(guān)系進(jìn)行分析，這一分析過程稱為數(shù)據(jù)流分析。析，這一分析過程稱為數(shù)據(jù)流分析。 確切地查找基本塊中的無用賦值，不僅確切地查找基本塊中的無用賦值，不僅需要了解需要了解基本塊中基本塊中對變量的定值和引用的情況，對變量的定值和引用的情況，還應(yīng)知道在還應(yīng)知道在基本塊外基本塊外變量是否被引用。變量是否被引用。 數(shù)據(jù)流分析作用：數(shù)據(jù)流分析作用： 對消除無用賦值提供了可靠的依據(jù)

44、，對消除無用賦值提供了可靠的依據(jù)， 循環(huán)優(yōu)化和全局優(yōu)化一種強(qiáng)有力的工具循環(huán)優(yōu)化和全局優(yōu)化一種強(qiáng)有力的工具 流圖以基本塊為流圖以基本塊為結(jié)點(diǎn)結(jié)點(diǎn)。如果一個(gè)結(jié)點(diǎn)的入口語句是程序的第一條如果一個(gè)結(jié)點(diǎn)的入口語句是程序的第一條語句，則稱此結(jié)點(diǎn)為語句，則稱此結(jié)點(diǎn)為首結(jié)點(diǎn)首結(jié)點(diǎn)。通過構(gòu)造一個(gè)有向圖，稱之為通過構(gòu)造一個(gè)有向圖，稱之為流圖流圖，我們，我們可以可以將控制流的信息增加到基本塊的集合將控制流的信息增加到基本塊的集合上上來表示一個(gè)程序。來表示一個(gè)程序。1.1. 概念概念程序流圖的結(jié)點(diǎn)集就是程序的基本塊集。程序流圖的結(jié)點(diǎn)集就是程序的基本塊集。v構(gòu)造構(gòu)造 程序流圖的方法是：程序流圖的方法是：v 對于程序中的

45、兩個(gè)基本塊對于程序中的兩個(gè)基本塊Bi和和Bj，如果，如果Bj緊接著緊接著Bi被執(zhí)行，則從被執(zhí)行，則從Bi引一條有向邊到結(jié)引一條有向邊到結(jié)點(diǎn)點(diǎn)Bj，稱，稱Bi為為Bj的的直接前驅(qū)直接前驅(qū)，Bj為為Bi的的直接后直接后繼繼。 v規(guī)則規(guī)則1：按基本塊在程序中排列的自然次序，：按基本塊在程序中排列的自然次序，Bj緊跟在緊跟在Bi之后，且之后，且Bi的出口語句不是無條的出口語句不是無條件轉(zhuǎn)移或停語句；件轉(zhuǎn)移或停語句；v規(guī)則規(guī)則2：Bi的出口語句是一個(gè)無條件轉(zhuǎn)移或條的出口語句是一個(gè)無條件轉(zhuǎn)移或條件轉(zhuǎn)移語句，且其目標(biāo)是件轉(zhuǎn)移語句，且其目標(biāo)是Bj的入口語句。的入口語句。2. 2. 構(gòu)造程序流圖示例構(gòu)造程序流圖

46、示例 (1) read X(1) read X(2) read Y(2) read YB1(3) R := X mod Y(3) R := X mod Y (4) if R=0 goto(8) (4) if R=0 goto(8)B2(5) X := Y(5) X := Y(6) Y := R(6) Y := R (7) goto (3) (7) goto (3)B3B3 (8) write Y (8) write Y(9) halt(9) haltB4B4程序流圖示例程序流圖示例(1)I := 0(1)I := 0(2)I := I + 1(2)I := I + 1(3)If I = N g

47、oto(3)If I = N goto（5 5）(4)goto (4)goto （8 8）(5)T := M + I(5)T := M + I(6)M := T(6)M := T(7)goto (7)goto （2 2）(8)stop(8)stop6.3.2 6.3.2 到達(dá)定值數(shù)據(jù)流方程到達(dá)定值數(shù)據(jù)流方程 為了進(jìn)行循環(huán)優(yōu)化和全局優(yōu)化，需要分析為了進(jìn)行循環(huán)優(yōu)化和全局優(yōu)化，需要分析程序中所有變量的定值（指對變量賦值）和引程序中所有變量的定值（指對變量賦值）和引用之間的關(guān)系，這一工作稱為用之間的關(guān)系，這一工作稱為數(shù)據(jù)流分析數(shù)據(jù)流分析 一、作用一、作用 分析程序中所有變量的定值分析程序中所有變量的定

48、值(指對變量的賦指對變量的賦值或輸入值值或輸入值)和引用之間的關(guān)系、基本塊出口的和引用之間的關(guān)系、基本塊出口的活躍變量信息等，以進(jìn)行循環(huán)優(yōu)化和全局優(yōu)化。活躍變量信息等，以進(jìn)行循環(huán)優(yōu)化和全局優(yōu)化。 二、方法二、方法 1、使用、使用變量到達(dá)定值數(shù)據(jù)流方程變量到達(dá)定值數(shù)據(jù)流方程和和變變量引用定值鏈量引用定值鏈 2、使用、使用活躍變量數(shù)據(jù)流方程活躍變量數(shù)據(jù)流方程三、基本概念三、基本概念a)點(diǎn)點(diǎn) 程序中某一四元式的位置程序中某一四元式的位置(序號(hào)或地址序號(hào)或地址)b)定值點(diǎn)定值點(diǎn) 對某變量對某變量賦值或輸入值賦值或輸入值的四元式的位置的四元式的位置c)引用點(diǎn)引用點(diǎn) 引用某變量的四元式的位置引用某變量的四

49、元式的位置d)變量變量A的到達(dá)與定值的到達(dá)與定值 若若d點(diǎn)是變量點(diǎn)是變量A的一個(gè)定值點(diǎn)，的一個(gè)定值點(diǎn)，u點(diǎn)是點(diǎn)是A的的一個(gè)引用點(diǎn)，存在一條從一個(gè)引用點(diǎn)，存在一條從d到到u的通路，的通路，并在此通路上沒有對并在此通路上沒有對A的其他定值點(diǎn)，則的其他定值點(diǎn)，則稱稱d點(diǎn)對點(diǎn)對A的定值能達(dá)到的定值能達(dá)到u點(diǎn)。點(diǎn)。e)引用定值鏈引用定值鏈 假定在程序中某點(diǎn)假定在程序中某點(diǎn)u引用了變量引用了變量A，則把，則把能到達(dá)能到達(dá)u的的A的所有定值點(diǎn)的全體，稱為的所有定值點(diǎn)的全體，稱為A在引用點(diǎn)在引用點(diǎn)u的引用定值鏈的引用定值鏈(ud鏈鏈)到達(dá)定值數(shù)據(jù)流方程求解到達(dá)定值數(shù)據(jù)流方程求解a)基本量基本量 1) INB

50、能到達(dá)基本塊能到達(dá)基本塊B入口點(diǎn)的各個(gè)變量的定值點(diǎn)集入口點(diǎn)的各個(gè)變量的定值點(diǎn)集合。合。 B B入口集合入口集合 2)OUTB 能到達(dá)基本塊能到達(dá)基本塊B出口點(diǎn)的各變量全部定值點(diǎn)集出口點(diǎn)的各變量全部定值點(diǎn)集合。合。B B出口集合出口集合 3)GENB 基本塊基本塊B中定值并能到達(dá)中定值并能到達(dá)B出口點(diǎn)的所有定值點(diǎn)出口點(diǎn)的所有定值點(diǎn)集合。集合。B B中中“生成生成”的集合的集合 4)KILLB 因因B中定值而注銷所有與它相關(guān)變量的定值點(diǎn)中定值而注銷所有與它相關(guān)變量的定值點(diǎn)集合。集合。B B中中“殺死殺死”的集合的集合3 3. . 示例示例(1) a := d(1) a := d(2)if a=b

51、then goto B(2)if a=b then goto B2 2(3)b := 1(3)b := 1(4)c := 1(4)c := 1(5)a := a + b(5)a := a + bB B1 1B B2 2B B3 3B B4 4(1) a := d(1) a := d基本塊基本塊InGenKillOutB1 1 1B213 1，3B314 1，4B413451345(3)b := 1(3)b := 1(4)c := 1(4)c := 1(5)a := a + b(5)a := a + ba aa ab b 集合集合GENB及及KILLB可以根據(jù)程序流圖，可以根據(jù)程序流圖，對基本塊

52、對基本塊B的的DAG葉結(jié)點(diǎn)所標(biāo)記的葉結(jié)點(diǎn)所標(biāo)記的標(biāo)識(shí)符標(biāo)識(shí)符及及內(nèi)部結(jié)點(diǎn)的內(nèi)部結(jié)點(diǎn)的附加標(biāo)識(shí)符附加標(biāo)識(shí)符進(jìn)行考察，確定各個(gè)進(jìn)行考察，確定各個(gè)定值點(diǎn)。定值點(diǎn)。 對程序流圖中的所有基本塊對程序流圖中的所有基本塊B求出相應(yīng)求出相應(yīng)INB之后，按如下規(guī)則確定到達(dá)之后，按如下規(guī)則確定到達(dá)B中點(diǎn)中點(diǎn)P的任一的任一變量變量A的全部定值點(diǎn)。的全部定值點(diǎn)。 規(guī)則規(guī)則1：如果：如果B中中P點(diǎn)之前有點(diǎn)之前有A的定值（可的定值（可能為多個(gè)），則這些定值點(diǎn)中，離能為多個(gè)），則這些定值點(diǎn)中，離P最近最近的那個(gè)點(diǎn)就是能到達(dá)的那個(gè)點(diǎn)就是能到達(dá)P的唯一定值點(diǎn)；的唯一定值點(diǎn)； 規(guī)則規(guī)則2：如果：如果B中中P點(diǎn)之前無點(diǎn)之前無A的定

53、值，則的定值，則能到達(dá)能到達(dá)P的的A的定值點(diǎn)是包含在集合的定值點(diǎn)是包含在集合INB中的那些中的那些A的定值點(diǎn)。的定值點(diǎn)。 四個(gè)集合之間內(nèi)在的關(guān)系四個(gè)集合之間內(nèi)在的關(guān)系 首先，程序中某一點(diǎn)首先，程序中某一點(diǎn)d對變量對變量A的定值可到達(dá)的定值可到達(dá)基本塊基本塊B的出口之后，當(dāng)且僅當(dāng)?shù)某隹谥螅?dāng)且僅當(dāng) （1）此定值能到達(dá)基本塊）此定值能到達(dá)基本塊B的入口之前，且的入口之前，且B中不再對中不再對A重新定值重新定值 （即（即dINB-KILLB ） ； （2）或者點(diǎn)）或者點(diǎn)d在在B中，且對中，且對A的定值能到達(dá)的定值能到達(dá)B的出口之后（即的出口之后（即dGENB） OUTB=INBKILLB GENB

54、 (6.1)其次，程序中某一點(diǎn)其次，程序中某一點(diǎn)d d對變量對變量A A的定值可到的定值可到達(dá)基本塊達(dá)基本塊B B的入口之前，當(dāng)且僅當(dāng)此定值能的入口之前，當(dāng)且僅當(dāng)此定值能到達(dá)到達(dá)B B的某一直接前驅(qū)之后。的某一直接前驅(qū)之后。 （6.26.2）。）。 INB=PrBedbbOUT(PredB代表代表B的所有前驅(qū)基本塊集合的所有前驅(qū)基本塊集合)b)基本方程 OUTB=INBKILLBGENB (6.1) INB= （6.2） 注：注：1)由于所有由于所有KILLB和和GENB可從給定的流可從給定的流圖中直接求出，所以，上述等式是關(guān)于變量圖中直接求出，所以，上述等式是關(guān)于變量INB和和OUTB的線性

55、聯(lián)立方程組，稱為到達(dá)的線性聯(lián)立方程組，稱為到達(dá)定值數(shù)定值數(shù)據(jù)流方程。據(jù)流方程。 2)流圖中若有流圖中若有n個(gè)基本塊，則此方程共有個(gè)基本塊，則此方程共有2n個(gè)，個(gè)，其中其中GENB就是基本塊內(nèi)就是基本塊內(nèi)DAG圖上的附標(biāo)，圖上的附標(biāo)， KILLB指若指若Ai在本塊內(nèi)定值，就將所有在本塊內(nèi)定值，就將所有Ai定值點(diǎn)定值點(diǎn)(除本定值點(diǎn)除本定值點(diǎn))均注銷。均注銷。PrBedbbOUT(PredB代表B的所有前驅(qū)基本塊集合)算法算法6.3 迭代法求解集合方程組(6.1)-(6.2)1 for ( i=1; i=N; i+ ) 2 INBi = ;3 OUTBi = GENBi; 4 CHANGE = 1;

56、5 while( CHANGE ) 6 CHANGE=0;7 for ( i=1; i=N; i+ ) 8 NEWIN= ;9 if ( NEWIN! = INBi ) 10 CHANGE=1;11 INBi=NEWIN;12 OUTBi = ( INBi - KILLBi )GENBi; PrBedbbOUT例6.4 圖6-66.3.3引用定值鏈引用定值鏈(ud鏈鏈)的計(jì)算及應(yīng)用的計(jì)算及應(yīng)用1、定義、定義假定在程序中某點(diǎn)假定在程序中某點(diǎn)u u引用了變量引用了變量A A，到達(dá)到達(dá)u的變量的變量A的的定值點(diǎn)集合定值點(diǎn)集合稱為變量稱為變量A在在u點(diǎn)的點(diǎn)的ud鏈。鏈。2、構(gòu)成規(guī)則、構(gòu)成規(guī)則a)在基本

57、塊在基本塊B中，變量中，變量A在引用點(diǎn)在引用點(diǎn)u前有定值點(diǎn)前有定值點(diǎn)d，并且并且d點(diǎn)的定值鏈能到達(dá)點(diǎn)的定值鏈能到達(dá)u，則，則A在在u點(diǎn)的點(diǎn)的ud鏈鏈=d. (6.5)b)若在基本塊若在基本塊B中，在中，在u點(diǎn)之前點(diǎn)之前無對無對A的定值點(diǎn)，的定值點(diǎn)，則變量則變量A在在u點(diǎn)的點(diǎn)的ud鏈鏈=INB中有關(guān)中有關(guān)A定值定值的集的集合合注：這里，鏈?zhǔn)侵笇⒓现懈鞫ㄖ迭c(diǎn)連在一起構(gòu)注：這里，鏈?zhǔn)侵笇⒓现懈鞫ㄖ迭c(diǎn)連在一起構(gòu)成鏈，以便于檢索。成鏈，以便于檢索。(6.6)例例6.5 變量變量I的引用點(diǎn)為的引用點(diǎn)為d2和和d6，J的引用為的引用為d4，d5和和d7。求出它們的求出它們的ud鏈。鏈。 對于基本塊對于基

58、本塊B1，由于，由于I的的引用點(diǎn)引用點(diǎn)d2之前有唯一的之前有唯一的定值點(diǎn)定值點(diǎn)d1，因此，因此， I在在d2的的ud鏈為鏈為d1。 對基本塊對基本塊B3，由于，由于J的引的引用點(diǎn)用點(diǎn)d4之前無之前無J的塊內(nèi)定的塊內(nèi)定值點(diǎn)，故值點(diǎn)，故J在在d4的的ud鏈為鏈為INB3中所包含的中所包含的J點(diǎn)的點(diǎn)的定值點(diǎn)，即定值點(diǎn)，即 d2，d4，d5。常數(shù)傳播及相應(yīng)地合并已知量 如果能到達(dá)某一點(diǎn)如果能到達(dá)某一點(diǎn)P有變量有變量A的唯一定值的唯一定值點(diǎn)點(diǎn)d：A := c （c為常數(shù)）為常數(shù)） P是是A的一個(gè)引用點(diǎn)，那么，在的一個(gè)引用點(diǎn)，那么，在P點(diǎn)點(diǎn)A的值的值也必然為也必然為c，故可將，故可將P點(diǎn)對點(diǎn)對A的引用代之

59、的引用代之以常數(shù)以常數(shù)c，這種操作稱為常數(shù)傳播。，這種操作稱為常數(shù)傳播。 在圖在圖6-6中，由于中，由于INB5=d3，d4，d5，故能到達(dá)，故能到達(dá)d6的的I 的定值點(diǎn)是的定值點(diǎn)是唯一的，即唯一的，即d3：I := 1 從而可知在從而可知在d6對對I的引用可替之以的引用可替之以常數(shù)常數(shù)1，也就是可，也就是可將將d6改寫為改寫為d6：I := 6 算法算法6.4 常數(shù)傳播和合并已知量的處理CHANGE=1;while(CHANGE) CHANGE=0; for (程序中的每個(gè)語句s) for(s的每個(gè)運(yùn)算量v) if(v在引用點(diǎn)s的ud鏈僅含一個(gè)d且語句d為v=C(C為常數(shù)) ) 把s中所有對

60、v的引用均替換為C; CHANGE=1; if(s右端含有運(yùn)算符且每個(gè)運(yùn)算量都為常數(shù)) C=s的右端表達(dá)式； 把語句s替換為A=C(A為語句的s左部量); CHANGE=1; 6.3.4活躍變量及數(shù)據(jù)流方程活躍變量及數(shù)據(jù)流方程1、活躍變量、活躍變量 變量變量A A在程序中某一點(diǎn)在程序中某一點(diǎn)P P是活躍的，是指在程是活躍的，是指在程序流圖中，存在一條從序流圖中，存在一條從P P到到A A的引用點(diǎn)的通路。的引用點(diǎn)的通路。 顯然，如果變量顯然，如果變量A A在基本塊在基本塊B B中的中的P P點(diǎn)定值，點(diǎn)定值，且從且從P P開始直到開始直到B B的出口都沒有的出口都沒有A A的引用點(diǎn)，若的引用點(diǎn)，若