稱為優(yōu)化代碼改進變換的標準代碼變換必須保程序的含義采取安全課件

1、第九章 獨立于機器的優(yōu)化詞法分析器語法分析器語義分析器源程序中間代碼生成器獨立于機器的代碼優(yōu)化器代碼生成器依賴于機器的代碼優(yōu)化器目標機器代碼符號表第1頁，共140頁。第九章 獨立于機器的優(yōu)化代碼優(yōu)化通過程序變換（局部變換和全局變換）來改進程序，稱為優(yōu)化代碼改進變換的標準代碼變換必須保程序的含義采取安全穩(wěn)妥的策略變換減少程序的運行時間平均達到一個可度量的值變換所作的努力是值得的第2頁，共140頁。第九章 獨立于機器的優(yōu)化本章介紹獨立于機器的優(yōu)化，即不考慮任何依賴目標機器性質的優(yōu)化變換 通過實例來介紹代碼改進的主要機會 數(shù)據(jù)流分析包括的幾類重要的全局收集的信息 數(shù)據(jù)流分析的一般框架 和一般框架有區(qū)

2、別的常量傳播 部分冗余刪除的優(yōu)化技術 循環(huán)的識別和分析第3頁，共140頁。9.1 優(yōu)化的主要種類9.1.1 優(yōu)化的主要源頭程序中存在許多程序員無法避免的冗余運算對于Aij和X.f1這樣訪問數(shù)組元素和結構體的域的操作（例如， Aij = Aij + 10）隨著程序被編譯，這些訪問操作展開成多步低級算術運算對同一個數(shù)據(jù)結構的多次訪問導致許多公共的低級運算程序員沒有辦法刪除這些冗余第4頁，共140頁。9.1 優(yōu)化的主要種類9.1.2 一個實例i = m 1; j = n; v = an;(1) i = m 1while (1) (2) j = n do i = i +1; while(aiv);(4

3、) v = at1 if (i = j) break;(5) i = i + 1 x=ai; ai=aj; aj=x;(6) t2 = 4 i (7) t3 = at2 x=ai; ai=an; an=x;(8) if t3 v goto (5)第5頁，共140頁。9.1 優(yōu)化的主要種類9.1.2 一個實例i = m 1; j = n; v = an;(9) j = j 1 while (1) (10) t4 = 4 j do i = i +1; while(aiv);(12) if t5v goto (9) if (i = j) break;(13) if i =j goto (23) x=

4、ai; ai=aj; aj=x;(14) t6 = 4 i(15 ) x = at6x=ai; ai=an; an=x;. . .第6頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6程序流圖第7頁，共140頁。9.1 優(yōu)化的主要種類9.1.3 公共子表達式刪除B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 =

5、 xgoto B2第8頁，共140頁。9.1 優(yōu)化的主要種類局部公共子表達式刪除, 復寫傳播, 刪除死代碼B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2第9頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto

6、 B6B4B3B5B6第10頁，共140頁。9.1 優(yōu)化的主要種類全局公共子表達式刪除, 復寫傳播, 刪除死代碼B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2第11頁，共140頁。9.1 優(yōu)化的主要種類全局公共子表達式刪除, 復寫傳播, 刪除死代碼B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 j

7、t9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B2第12頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6第13頁，共140頁。9.1 優(yōu)化的主要種類全局公共子表達式刪除, 復寫傳播, 刪除死代碼B5 x=ai; ai=

8、aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B2第14頁，共140頁。9.1 優(yōu)化的主要種類全局公共子表達式刪除, 復寫傳播, 刪除死代碼B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 =

9、 xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B2x = t3at2 = t5at4 = xgoto B2第15頁，共140頁。9.1 優(yōu)化的主要種類公共子表達式刪除、復寫傳播、刪除死代碼B6 x = ai; ai = an; an = x;t11 = 4 ix = at11t12 = 4 i t13 = 4 nt14 = at13at12 = t14t15 = 4 n at15 = x x = t3t14 = at1at2 = t14at1 =

10、x 第16頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6第17頁，共140頁。9.1 優(yōu)化的主要種類B6 x = ai; ai = an; an = x;at1能否作為公共子表達式？t11 = 4 ix = at11t12 = 4 i t13 = 4 nt14 = at13at12 = t14t15 = 4 n at15 = x x = t3t14 = at1at2 = t14at1 = x 第18頁，共140頁。9.1

11、優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6 把at1作為公共子表達式是不穩(wěn)妥的 因為B5有對下標變量at2和at4的賦值第19頁，共140頁。9.1 優(yōu)化的主要種類9.1.4 復寫傳播復寫語句：形式為f = g的賦值優(yōu)化過程中會大量引入復寫t = d + ea = t 刪除局部公共子表達式期間引進復寫t = d + eb = tc = tc = d + eb = d + ea = d + e第20頁，共140頁。9.1 優(yōu)化的主要種類9.1.

12、4 復寫傳播復寫語句：形式為f = g的賦值優(yōu)化過程中會大量引入復寫復寫傳播變換的做法是在復寫語句f = g后，盡可能用g代表fB5x = t3at2 = t5at4 = t3goto B2x = t3at2 = t5at4 = xgoto B2第21頁，共140頁。9.1 優(yōu)化的主要種類9.1.4 復寫傳播復寫語句：形式為f = g的賦值優(yōu)化過程中會大量引入復寫復寫傳播變換的做法是在復寫語句f = g后，盡可能用g代表f復寫傳播變換本身并不是優(yōu)化，但它給其它優(yōu)化帶來機會常量合并（編譯時可完成的計算）死代碼刪除pi = 3.14 y = pi 5第22頁，共140頁。9.1 優(yōu)化的主要種類9.

13、1.5 死代碼刪除死代碼是指計算的結果決不被引用的語句一些優(yōu)化變換可能會引起死代碼例： 為便于調試，可能在程序中加打印語句，測試后改成右邊的形式 debug = true;| debug = false; . . .|. . . if (debug) print |if (debug) print 靠優(yōu)化來保證目標代碼中沒有該條件語句部分第23頁，共140頁。9.1 優(yōu)化的主要種類9.1.5 死代碼刪除死代碼是指計算的結果決不被引用的語句一些優(yōu)化變換可能會引起死代碼例：復寫傳播可能會引起死代碼刪除B5x = t3at2 = t5at4 = t3goto B2at2 = t5at4 = t3go

14、to B2x = t3at2 = t5at4 = xgoto B2第24頁，共140頁。9.1 優(yōu)化的主要種類9.1.6 代碼外提代碼外提是循環(huán)優(yōu)化的一種循環(huán)優(yōu)化的其它重要技術歸納變量刪除強度削弱例：while (i = limit 2 ) 代碼外提后變換成t = limit 2;while (i v goto B3B3第26頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1B1B2j = j 1t4 = t4 4t5 = at4if t5 v goto B3B4B3B5B6t4 = 4 jif i = j goto B6j = j 1t4 = 4 j

15、t5 = at4if t5 v goto B3B3除第一次外，t4 = 4 j在B3的入口一定保持在j = j 1后，關系t4 = 4 j + 4也保持第27頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1t4 = 4 ji = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6B2也可以進行類似的變換第28頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1t4 = 4 jt2 = 4 ii = i + 1t2 = t2+ 4t3 = at

16、2if t3 v goto B3if i = j goto B6B4B3B5B6第29頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1t4 = 4 jt2 = 4 ii = i + 1t2 = t2+ 4t3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6循環(huán)控制條件可以用t2和t4來表示第30頁，共140頁。9.1 優(yōu)化的主要種類i = m 1j = nt1 = 4 nv = at1t2 = 4 it4 = 4 jt2 = t2 + 4t3 = at2if t3 v goto B3if t2 = t4 go

17、to B6at2 = t5at4 = t3goto B2B4B3B5t14 = at1at2 = t14at1 = t3B6第31頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象流圖上的點基本塊中，兩個相鄰的語句之間為程序的一個點基本塊的開始點和結束點流圖上的路徑點序列p1, p2, , pn，對1和n - 1間的每個i，滿足(1) pi是先于一個語句的點，pi1是同一塊中位于該語句后的點，或者(2) pi是某塊的結束點，pi1是后繼塊的開始點第32頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象流圖上路徑實例 - (1, 2, 3, 4, 9) - (1, 2, 3,

18、 4, 5, 6, 7, 8, 3, 4, 9) - (1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4, 9) - (1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, )路徑長度無限 - 路徑數(shù)無限B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()=0 goto B4d1: a = 1(2)(3)(4)(5)(6)(7)(8)(9)第33頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象 分析程序的行為時，必須在其流圖上考慮

19、所有的執(zhí)行路徑（在調用或返回語句被執(zhí)行時，還需要考慮執(zhí)行路徑在多個流圖之間的跳轉） - 通常，從流圖得到的程序執(zhí)行路徑數(shù)無限，且執(zhí)行路徑長度沒有有限的上界B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()=0 goto B4d1: a = 1(2)(3)(4)(5)(6)(7)(8)(9)第34頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象 分析程序的行為時，必須在其流圖上考慮所有的執(zhí)行路徑（在調用或返回語句被執(zhí)行時，還需要考慮執(zhí)行路徑在多個流圖之間的跳轉） - 每個程序點的不同狀態(tài)數(shù)也可能無限程序狀態(tài)：存儲單元到值的映射B1(1)d

20、2: b = ad3: a = 243 goto B3B4B2B3if read()=0 goto B4d1: a = 1(2)(3)(4)(5)(6)(7)(8)(9)第35頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象把握所有執(zhí)行路徑上的所有程序狀態(tài)一般來說是不可能的 數(shù)據(jù)流分析并不打算區(qū)分到達一個程序點的不同執(zhí)行路徑，也不試圖掌握該點每個完整的狀態(tài) 它從這些狀態(tài)中抽取解決特定數(shù)據(jù)流分析所需信息，以總結出用于該分析目的的一組有限的事實 并且這組事實和到達這個程序點的路徑無關，即從任何路徑到達該程序點都有這樣的事實 分析的目的不同，從程序狀態(tài)提煉的信息也不同第36頁，共140頁

21、。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象點(5)所有程序狀態(tài)：a 1, 243 由d1, d3定值(1) 到達定值 - d1, d3的定值 到達點(5)(2) 常量合并 - a在點(5)不是 常量B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()next和q-next互為別名程序分析必須是穩(wěn)妥的本章其余部分僅考慮變量無別名的情況第38頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.3 到達-定值到達一個程序點的所有定值可用來判斷一個變量在某程序點是否為常量可用來判斷一個變量在某程序點是否無初值別名給到達-定值的計算帶來困難定值的注銷在一條執(zhí)行路

22、徑上，對x的賦值注銷先前對x的所有賦值第39頁，共140頁。9.2 數(shù)據(jù)流分析介紹gen和kill分別表示一個基本塊生成和注銷的定值d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4第40頁，共140頁。9.2 數(shù)據(jù)流分析介紹基本塊的

23、gen和kill是怎樣計算的對三地址指令 d: u = v + w，它的狀態(tài)遷移函數(shù)是 fd(x) = gend (x killd)若：f1(x) = gen1 (x kill1), f2(x) = gen2 (x kill2)則： f2(f1(x) = gen2 (gen1 (x kill1) kill2)= (gen2 (gen1 kill2) (x (kill1 kill2)若基本塊B有n條三地址指令killB = kill1 kill2 killn genB = genn (genn1 killn) (genn2 killn1 killn) (gen1 kill2 kill3 kill

24、n) 第41頁，共140頁。9.2 數(shù)據(jù)流分析介紹到達-定值的數(shù)據(jù)流等式 genB：B中能到達B的結束點的定值語句 killB：整個程序中決不會到達B結束點的定值 INB：能到達B的開始點的定值集合 OUTB：能到達B的結束點的定值集合兩組等式（根據(jù)gen和kill定義IN和OUT） INB = P是B的前驅 OUTP OUTB = genB (INB killB) OUTENTRY = 到達-定值方程組的迭代求解第42頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 B2 000 0000 B3 000 0000 B4 000 0000gen B1 = d

25、1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第43頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 000 0000 B2 000 0000 B3 000 0000 B4 000 0000gen B1 = d1,

26、 d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第44頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 000 0000 B3 000 0000 B4 000 0000gen B1 = d1, d

27、2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第45頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 111 0000 000 0000 B3 000 0000 B4 000 0000gen B1

28、= d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第46頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 000 0000 B4 000 0000

29、gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第47頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000

30、0000 B4 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第48頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100

31、B3 001 1100 000 1110 B4 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第49頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 11

32、1 0000 001 1100 B3 001 1100 000 1110 B4 001 1110 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第50頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B

33、1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第51頁，共140頁

34、。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 111 0111 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j =

35、j 1d6: a = u2B3第52頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN B OUT B B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1100 000 1110 B4 001 1110 001 0111gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i =

36、u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第53頁，共140頁。9.2 數(shù)據(jù)流分析介紹 IN BOUT B B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1110 000 1110 B4 001 1110 001 0111不再繼續(xù)演示迭代計算gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i =

37、m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第54頁，共140頁。9.2 數(shù)據(jù)流分析介紹到達-定值數(shù)據(jù)流等式是正向的方程 OUT B = gen B (IN B kill B)IN B = P是B的前驅 OUT P某些數(shù)據(jù)流等式是反向的到達-定值數(shù)據(jù)流等式的合流運算是求并集 IN B = P是B的前驅 OUT P 某些數(shù)據(jù)流等式的合流運算是求交集對到達-定值數(shù)據(jù)流方程，迭代求它的最小解某些數(shù)據(jù)流方程可能需要求最大解第55頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.2 數(shù)據(jù)流分析模式數(shù)據(jù)流值

38、數(shù)據(jù)流分析總把程序點和數(shù)據(jù)流值聯(lián)系起來數(shù)據(jù)流值代表在程序點能觀測到的所有可能程序狀態(tài)集合的一個抽象語句s前后兩點數(shù)據(jù)流值用INs和OUTs來表示數(shù)據(jù)流問題就是通過基于語句語義的約束（遷移函數(shù)）和基于控制流的約束來尋找所有語句s的INs和OUTs 的一個解第56頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.2 數(shù)據(jù)流分析模式遷移函數(shù) f語句前后兩點的數(shù)據(jù)流值受該語句的語義約束若沿執(zhí)行路徑正向傳播，則OUTs = fs(INs)若沿執(zhí)行路徑逆向傳播，則INs = fs(OUTs)若基本塊B由語句s1, s2, , sn依次組成，則INsi+1 = OUTsi, i = 1, 2, , n1（逆向）

39、fB = fn . . . f2 f1 (逆向 fB = f1 . . . fn - 1 fn )OUTB = fB (INB) (逆向 INB = fB (OUTB) )第57頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.2 數(shù)據(jù)流分析模式控制流約束正向傳播 INB = P是B的前驅OUTP（可能用）逆向傳播 OUTB = S是B的后繼INS （可能用）約束方程組的解通常不是唯一的求解的目標是要找到滿足這兩組約束（控制流約束和遷移約束）的最“精確”解第58頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.4 活躍變量定義 x的值在p點開始的某條執(zhí)行路徑上被引用，則說x在p點活躍，否則稱x在p點已

40、經死亡 INB：塊B開始點的活躍變量集合 OUTB：塊B結束點的活躍變量集合 useB：塊B中有引用且在引用前無定值的變量集 defB：塊B中有定值的變量集應用 一種重要應用就是基本塊的寄存器分配第59頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.4 活躍變量例 useB2 = i, j defB2 = i, j d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第60頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.4 活躍變量活躍變量數(shù)據(jù)流等式 IN B = useB (OUT B

41、 defB ) OUTB = S是B的后繼 IN S IN EXIT = 和到達定值等式之間的聯(lián)系與區(qū)別 都以集合并算符作為它們的匯合算符 信息流動方向相反，IN和OUT的作用相互交換 use和def分別取代gen和kill 仍然需要最小解第61頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.5 可用表達式 x = y + z x = y + z x = y + z . . . . y = z = . . . p p py + z 在p點 y + z 在p點 y + z 在p點可用不可用不可用第62頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.5 可用表達式下面兩種情況下， 4i在B3的入口都可

42、用t1 = 4i沒有對i 賦值t2 = 4iB1B2B3t1 = 4ii =t0 = 4it2 = 4iB1B2B3第63頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.5 可用表達式定義 若到點p的每條執(zhí)行路徑都計算x + y，并且計算后沒有對x或y賦值，那么稱x + y在點p可用e_genB：塊B產生的可用表達式集合e_killB： 塊B注銷的可用表達式集合 IN B： 塊B入口的可用表達式集合OUT B：塊B出口的可用表達式集合應用公共子表達式刪除第64頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.5 可用表達式數(shù)據(jù)流等式 OUT B = e_genB (IN B e_killB ) IN

43、 B = P是B的前驅 OUT P IN ENTRY = 同先前的主要區(qū)別 使用而不是作為這里數(shù)據(jù)流等式的匯合算符 求最大解而不是最小解第65頁，共140頁。9.2 數(shù)據(jù)流分析介紹IN集合的不同初值比較 （以B2為例）B1B2簡寫成：I j+1 = OUTB1 O jO j+1 = G (I j+1 K)O0 = （初值為空集）O0 = U （初值為全集）I 1 = I 1 = OUTB1 O1 = GO1 = G (OUTB1 K)I 2 = OUTB1 GI2=(OUTB1G) (OUTB1K)O 2 = G O 2 = G (OUTB1 K)INB2= OUTB1 OUTB2OUTB2

44、= G (INB2 K)第66頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.6 小結三個數(shù)據(jù)流問題 到達定值、活躍變量、可用表達式每個問題的組成數(shù)據(jù)流值的論域、數(shù)據(jù)流的方向、遷移函數(shù)、邊界條件、匯合算符、數(shù)據(jù)流等式見書上表9.2第67頁，共140頁。9.3 數(shù)據(jù)流分析的基礎本節(jié)內容把各種數(shù)據(jù)流模式作為一個整體抽象地研究形式地回答數(shù)據(jù)流算法的下列幾個基本問題在什么情況下數(shù)據(jù)流分析中使用的迭代算法是正確的迭代算法所得解的精度如何迭代算法是否收斂數(shù)據(jù)流方程的解的含義是什么第68頁，共140頁。9.3 數(shù)據(jù)流分析的基礎數(shù)據(jù)流分析框架(D, V, , F)包括 數(shù)據(jù)流分析的方向D，它可以是正向或逆向 數(shù)

45、據(jù)流值的論域 半格V、匯合算子 V到V的遷移函數(shù)族F 包括適用于邊界條件（ENTRY和EXIT結點）的常函數(shù)第69頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.1 半格半格(V, )是一個集合V和一個二元交運算(匯合運算) ，交運算滿足下面三點性質 冪等性：對所有的x，x x = x 交換性：對所有的x和y，x y = y x 結合性：對所有的x, y和z，x (y z) = (x y) z半格有頂元 （可以還有底元）對V中的所有x， x = x對V中的所有x， x = 第70頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.1 半格偏序關系集合V上的關系 自反性：對所有的x，x x 反對稱性

46、：對所有的x和y，如果x y并且y x,那么x = y 傳遞性：對所有的x, y和z，如果x y并且y z，那么x z此外，關系的定義x y當且僅當(x y)并且(x y) 第71頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.1 半格半格和偏序關系之間的聯(lián)系 半格(V, )的匯合運算確定了半格值集V上一種偏序 ： 對V中所有的x和y，x y當且僅當x y = x 若x y等于g，則g就是x和y的最大下界第72頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.1 半格例半格的論域V是先前全域U的冪集集合并作為匯合運算：是頂元，U是底元， x = x并且U x = U，對應的偏序關系是 集合交作為

47、匯合運算：U是頂元， 是底元，對應偏序關系是 數(shù)據(jù)流方程組通常有很多解，但是按偏序意義上的最大解是最精確的(1) 到達定值：最精確的解含最少定值(2) 可用表達式：最精確的解含最多表達式 第73頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.1 半格格圖右邊是定值子集形成的格這是一個格，本課程用半格概念就夠了 是x y的最大下界 x y d1d2d3d1, d2d1, d3d2, d3d1, d2, d3( )( )第74頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.1 半格積半格（定義略）上一頁數(shù)據(jù)流值的集合是定值集合的冪集可以用從每個變量的一個簡單定值半格構造出的積半格來表示整個定值半格

48、半格的高度上升鏈是序列x1 x2 xn半格的高度就是其中最長上升鏈中的個數(shù)若半格的高度有限，證明數(shù)據(jù)流分析迭代算法的收斂則非常容易第75頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.2 遷移函數(shù)遷移函數(shù)族F : V V有下列性質 F包括恒等函數(shù) F封閉于復合 若F中所有函數(shù)f 都有單調性，即 x y蘊涵f(x) f(y)，或 f(x y) f(x) f(y)則稱框架(D, V, , F)是單調的 框架(D, V, , F)的分配性 對F中所有的f，f(x y) = f(x) f(y) 第76頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.2 遷移函數(shù)例到達定值分析若f1(x) = G1 (x

49、 K1)，f2(x) = G2 (x K2)若G和K是空集，則f是恒等函數(shù)f2(f1(x) = G2 (G1 (x K1) K2) = (G2 (G1 K2) (x (K1 K2)因此f1和f2的復合f為f = G (x K)的形式分配性可以由檢查下面的條件得到 G (y z) K) = (G (y K) (G (z K)分配性： f(y z) = f(y) f(z) 第77頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.3 一般框架的迭代算法以正向數(shù)據(jù)流分析為例(1) OUTENTRY = vENTRY;(2) for (除了ENTRY以外的每個塊B) OUTB =;(3) while (任

50、何一個OUT出現(xiàn)變化)(4) for (除了ENTRY以外的每個塊B) (5) INB = /P是B的前驅 OUTP;(6) OUTB = fB(INB);(7) 第78頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.3 一般框架的迭代算法算法的一些可以證明的性質如果算法收斂，則結果是數(shù)據(jù)流方程組的一個解如果框架單調，則所求得的解是數(shù)據(jù)流方程組的最大不動點如果框架單調并且半格的高度有限，那么可以保證算法收斂第79頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.4 數(shù)據(jù)流解的含義結論：算法所得解是理想解的穩(wěn)妥近似理想解所考慮的路徑執(zhí)行路徑集：流圖上每一條路徑都屬于該集合 若流圖有環(huán)，則執(zhí)行路徑數(shù)

51、是無限的程序可能的執(zhí)行路徑集：程序執(zhí)行所走的路徑屬于該集合 這是理想解所考慮的路徑集可能的執(zhí)行路徑集 執(zhí)行路徑集尋找所有可能執(zhí)行路徑是不可判定的以下討論以正向數(shù)據(jù)流分析為例第80頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.4 數(shù)據(jù)流解的含義理想解若路徑P = ENTRY B1 B2 Bk，定義 fP fk1 f2 f1IDEALB = /P是從ENTRY到B的一條可能路徑 fP(vENTRY)有關理解解的結論任何大于理想解IDEAL的回答一定是不對的任何小于或等于IDEAL的值是穩(wěn)妥的在穩(wěn)妥的值中，越接近IDEAL的值越精確第81頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.4 數(shù)據(jù)流解

52、的含義執(zhí)行路徑上的解（meet over paths）MOPB = /P是從ENTRY到B的一條路徑 fP(vENTRY)MOP解不僅匯集了所有可能路徑的數(shù)據(jù)流值，而且還包括了那些不可能被執(zhí)行路徑的數(shù)據(jù)流值對所有的塊B，MOPB IDEALB，簡寫成MOP IDEALMOP的定義并沒有通向一個直接算法第82頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.4 數(shù)據(jù)流解的含義先前算法得到的最大不動點解MFP不是先找出到達一個塊的所有路徑，然后用匯合運算，而是訪問每個基本塊，并且不一定按照程序執(zhí)行時的次序在每個匯合點，把匯合運算作用在到目前為止得到的數(shù)據(jù)流值上，其中所用一些初值是人工引入的 MFP:

53、 maximal fixed point B1ENTRYB4B3B2第83頁，共140頁。9.3 數(shù)據(jù)流分析的基礎9.3.4 數(shù)據(jù)流解的含義MFP與MOP的聯(lián)系MFP訪問塊未必遵循次序由各塊的初值和遷移函數(shù)的單調性保證結果一致MFP較早地使用匯合運算 迭代算法的INB4 = f3(f1(vENTRY) f2(vENTRY) 而MOPB4 = (f3 f1) (vENTRY) (f3 f2) (vENTRY) 數(shù)據(jù)流分析框架具有分配性時，結果是一樣的MFP MOP IDEALB1ENTRYB4B3B2第84頁，共140頁。9.4 常 量 傳 播9.4.1 常量傳播框架的數(shù)據(jù)流值單個變量的數(shù)據(jù)流值

54、半格 變量的類型所允許的所有常量 值NAC表示不是常量 值UNDEF表示沒有定義程序中各變量的半格的積把程序中每個變量映射到 該半格上的一個“值”UNDEFNAC 3 2 1 0 1 2 3 第85頁，共140頁。9.4 常 量 傳 播9.4.2 常量傳播框架的遷移函數(shù) 令fs是語句s的遷移函數(shù)，m = fs(m)，用m和m之間的聯(lián)系來表達fs (m是變量到“值”的映射)(1) 如果s不是賦值語句，則fs是恒等函數(shù)(2) 若s對變量x賦值，則對所有v x，m(v) = m(v)，再看m(x)：若s的右部是一個常量c，則m(x) = c若s的右部是y + z m(x) = m(y) + m(z)

55、，若m(y)和m(z)都是常量值 m(x) = NAC，若m(y)或m(z)是NAC m(x) = UNDEF， 否則第86頁，共140頁。9.4 常 量 傳 播9.4.3 常量傳播框架的單調性 m(y)m(z)m(x)UNDEF UNDEF UNDEFc2 UNDEFNACNACUNDEFUNDEF c1 c2 c1 + c2NACNACUNDEFNACNAC c2NACNACNAC(1) 賦值語句的形式不是x = y + z fs不改變m(x)的值，或者改變成一個常量 在這些情況下，fs肯定是單調的第87頁，共140頁。9.4 常 量 傳 播9.4.3 常量傳播框架的單調性 m(y)m(z

56、)m(x)UNDEF UNDEF UNDEFc2 UNDEFNACNACUNDEFUNDEF c1 c2 c1 + c2NACNACUNDEFNACNAC c2NACNACNAC(1) 賦值語句的形式不是x = y + z fs不改變m(x)的值，或者改變成一個常量 在這些情況下，fs肯定是單調的(2) 賦值語句的形式是x = y + z見右邊， fs單調第88頁，共140頁。9.4 常 量 傳 播9.4.4 常量傳播框架的非分配性不管取什么路徑，在塊B3的出口，z的值是5迭代算法在塊B3的入口而不是出口使用匯合運算 f3(f1(m0) f2(m0) f3(f1(m0) f3(f2(m0)不具

57、有分配性算法未能發(fā)現(xiàn)B3出口z是5，這個結果雖不精確但安全B1EXITz = x + yx = 2y = 3B3B2x = 3y = 2第89頁，共140頁。9.4 常 量 傳 播9.4.5 結果的解釋ENTRY塊置初值UNDEF 其它塊置初值UNDEFx在塊B4入口是10塊B5的x引用可以用10代替和執(zhí)行路徑B1 B3 B4 B5不符若程序正確的話，認為x在塊B5入口的值只能為10是合適的 if Q goto B2B1B2B4B3x = 10if Q goto B5B5B7B6 = x第90頁，共140頁。9.5 部 分 冗 余 刪 除本節(jié)內容 冗余計算以公共子表達式的形式出現(xiàn)，或以循環(huán)不變

58、表達式的形式出現(xiàn) 冗余可能只出現(xiàn)在一部分路徑上 討論最小化x + y這樣表達式的計算次數(shù)的方法 策略是，一個計算盡量不做，除非它不得不做 首先討論冗余的不同形式，以建立直觀認識，然后描述廣義的冗余刪除問題，最后提出算法 算法涉及到求解多個正向或逆向的數(shù)據(jù)流問題第91頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源公共子表達式B1B2B4B3b = 7d = b + ca = b + ce = b + cB1B2B4B3b = 7t = b + cd = tt = b + ca = te = t第92頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源完全冗余

59、塊B4的表達式b + c是完全冗余的，因為所有到達B4的路徑都計算b + c ，并且b和c都未重新定值B2和B3的出邊的集合形成一個割集，若把該割集刪掉，則從起點到B4的路徑都被割斷 B1B2B4B3b = 7d = b + ca = b + ce = b + c第93頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源循環(huán)不變表達式a = b + ct = b + ca = t第94頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源部分冗余表達式B1B2B4B3a = b + cd = b + cB1B2B4B3t = b + ct = b + ca = t

60、d = t第95頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源放置b + c的副本來使B4中的b + c完全冗余 B1B2B4B3a = b + cd = b + cB1B2B4B3t = b + ct = b + ca = td = t第96頁，共140頁。9.5 部 分 冗 余 刪 除9.5.2 能否刪除所有的冗余B3 B4是一條關鍵邊：源結點有多個后繼目標結點有多個前驅B1B2B3B4d = b + ca = b + cB5B1B2B3B6t = b + ct = b + ca = tB5d = tB4增加新塊來刪除冗余第97頁，共140頁。9.5 部 分 冗 余