稱為優(yōu)化代碼改進(jìn)變換的標(biāo)準(zhǔn)代碼變換必須保程序的含義采取安全課件

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

2、別的常量傳播 部分冗余刪除的優(yōu)化技術(shù) 循環(huán)的識(shí)別和分析第3頁，共140頁。9.1 優(yōu)化的主要種類9.1.1 優(yōu)化的主要源頭程序中存在許多程序員無法避免的冗余運(yùn)算對于Aij和X.f1這樣訪問數(shù)組元素和結(jié)構(gòu)體的域的操作（例如， Aij = Aij + 10）隨著程序被編譯，這些訪問操作展開成多步低級算術(shù)運(yùn)算對同一個(gè)數(shù)據(jù)結(jié)構(gòu)的多次訪問導(dǎo)致許多公共的低級運(yùn)算程序員沒有辦法刪除這些冗余第4頁，共140頁。9.1 優(yōu)化的主要種類9.1.2 一個(gè)實(shí)例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 一個(gè)實(shí)例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 公共子表達(dá)式刪除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)化的主要種類局部公共子表達(dá)式刪除, 復(fù)寫傳播, 刪除死代碼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)化的主要種類全局公共子表達(dá)式刪除, 復(fù)寫傳播, 刪除死代碼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)化的主要種類全局公共子表達(dá)式刪除, 復(fù)寫傳播, 刪除死代碼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)化的主要種類全局公共子表達(dá)式刪除, 復(fù)寫傳播, 刪除死代碼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)化的主要種類全局公共子表達(dá)式刪除, 復(fù)寫傳播, 刪除死代碼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)化的主要種類公共子表達(dá)式刪除、復(fù)寫傳播、刪除死代碼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能否作為公共子表達(dá)式？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 把a(bǔ)t1作為公共子表達(dá)式是不穩(wěn)妥的 因?yàn)锽5有對下標(biāo)變量at2和at4的賦值第19頁，共140頁。9.1 優(yōu)化的主要種類9.1.4 復(fù)寫傳播復(fù)寫語句：形式為f = g的賦值優(yōu)化過程中會(huì)大量引入復(fù)寫t = d + ea = t 刪除局部公共子表達(dá)式期間引進(jìn)復(fù)寫t = d + eb = tc = tc = d + eb = d + ea = d + e第20頁，共140頁。9.1 優(yōu)化的主要種類9.1.

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

13、1.5 死代碼刪除死代碼是指計(jì)算的結(jié)果決不被引用的語句一些優(yōu)化變換可能會(huì)引起死代碼例： 為便于調(diào)試，可能在程序中加打印語句，測試后改成右邊的形式 debug = true;| debug = false; . . .|. . . if (debug) print |if (debug) print 靠優(yōu)化來保證目標(biāo)代碼中沒有該條件語句部分第23頁，共140頁。9.1 優(yōu)化的主要種類9.1.5 死代碼刪除死代碼是指計(jì)算的結(jié)果決不被引用的語句一些優(yōu)化變換可能會(huì)引起死代碼例：復(fù)寫傳播可能會(huì)引起死代碼刪除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)化的其它重要技術(shù)歸納變量刪除強(qiáng)度削弱例：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后，關(guān)系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也可以進(jìn)行類似的變換第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ù)流抽象流圖上的點(diǎn)基本塊中，兩個(gè)相鄰的語句之間為程序的一個(gè)點(diǎn)基本塊的開始點(diǎn)和結(jié)束點(diǎn)流圖上的路徑點(diǎn)序列p1, p2, , pn，對1和n - 1間的每個(gè)i，滿足(1) pi是先于一個(gè)語句的點(diǎn)，pi1是同一塊中位于該語句后的點(diǎn)，或者(2) pi是某塊的結(jié)束點(diǎn)，pi1是后繼塊的開始點(diǎn)第32頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象流圖上路徑實(shí)例 - (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ù)流抽象 分析程序的行為時(shí)，必須在其流圖上考慮

19、所有的執(zhí)行路徑（在調(diào)用或返回語句被執(zhí)行時(shí)，還需要考慮執(zhí)行路徑在多個(gè)流圖之間的跳轉(zhuǎn)） - 通常，從流圖得到的程序執(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ù)流抽象 分析程序的行為時(shí)，必須在其流圖上考慮所有的執(zhí)行路徑（在調(diào)用或返回語句被執(zhí)行時(shí)，還需要考慮執(zhí)行路徑在多個(gè)流圖之間的跳轉(zhuǎn)） - 每個(gè)程序點(diǎn)的不同狀態(tài)數(shù)也可能無限程序狀態(tài)：存儲(chǔ)單元到值的映射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ū)分到達(dá)一個(gè)程序點(diǎn)的不同執(zhí)行路徑，也不試圖掌握該點(diǎn)每個(gè)完整的狀態(tài) 它從這些狀態(tài)中抽取解決特定數(shù)據(jù)流分析所需信息，以總結(jié)出用于該分析目的的一組有限的事實(shí) 并且這組事實(shí)和到達(dá)這個(gè)程序點(diǎn)的路徑無關(guān)，即從任何路徑到達(dá)該程序點(diǎn)都有這樣的事實(shí) 分析的目的不同，從程序狀態(tài)提煉的信息也不同第36頁，共140頁

21、。9.2 數(shù)據(jù)流分析介紹9.2.1 數(shù)據(jù)流抽象點(diǎn)(5)所有程序狀態(tài)：a 1, 243 由d1, d3定值(1) 到達(dá)定值 - d1, d3的定值 到達(dá)點(diǎn)(5)(2) 常量合并 - a在點(diǎn)(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 到達(dá)-定值到達(dá)一個(gè)程序點(diǎn)的所有定值可用來判斷一個(gè)變量在某程序點(diǎn)是否為常量可用來判斷一個(gè)變量在某程序點(diǎn)是否無初值別名給到達(dá)-定值的計(jì)算帶來困難定值的注銷在一條執(zhí)行路

22、徑上，對x的賦值注銷先前對x的所有賦值第39頁，共140頁。9.2 數(shù)據(jù)流分析介紹gen和kill分別表示一個(gè)基本塊生成和注銷的定值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是怎樣計(jì)算的對三地址指令 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ù)流分析介紹到達(dá)-定值的數(shù)據(jù)流等式 genB：B中能到達(dá)B的結(jié)束點(diǎn)的定值語句 killB：整個(gè)程序中決不會(huì)到達(dá)B結(jié)束點(diǎn)的定值 INB：能到達(dá)B的開始點(diǎn)的定值集合 OUTB：能到達(dá)B的結(jié)束點(diǎn)的定值集合兩組等式（根據(jù)gen和kill定義IN和OUT） INB = P是B的前驅(qū) OUTP OUTB = genB (INB killB) OUTENTRY = 到達(dá)-定值方程組的迭代求解第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ù)演示迭代計(jì)算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ù)流分析介紹到達(dá)-定值數(shù)據(jù)流等式是正向的方程 OUT B = gen B (IN B kill B)IN B = P是B的前驅(qū) OUT P某些數(shù)據(jù)流等式是反向的到達(dá)-定值數(shù)據(jù)流等式的合流運(yùn)算是求并集 IN B = P是B的前驅(qū) OUT P 某些數(shù)據(jù)流等式的合流運(yùn)算是求交集對到達(dá)-定值數(shù)據(jù)流方程，迭代求它的最小解某些數(shù)據(jù)流方程可能需要求最大解第55頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.2 數(shù)據(jù)流分析模式數(shù)據(jù)流值

38、數(shù)據(jù)流分析總把程序點(diǎn)和數(shù)據(jù)流值聯(lián)系起來數(shù)據(jù)流值代表在程序點(diǎn)能觀測到的所有可能程序狀態(tài)集合的一個(gè)抽象語句s前后兩點(diǎn)數(shù)據(jù)流值用INs和OUTs來表示數(shù)據(jù)流問題就是通過基于語句語義的約束（遷移函數(shù)）和基于控制流的約束來尋找所有語句s的INs和OUTs 的一個(gè)解第56頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.2 數(shù)據(jù)流分析模式遷移函數(shù) f語句前后兩點(diǎn)的數(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的前驅(qū)OUTP（可能用）逆向傳播 OUTB = S是B的后繼INS （可能用）約束方程組的解通常不是唯一的求解的目標(biāo)是要找到滿足這兩組約束（控制流約束和遷移約束）的最“精確”解第58頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.4 活躍變量定義 x的值在p點(diǎn)開始的某條執(zhí)行路徑上被引用，則說x在p點(diǎn)活躍，否則稱x在p點(diǎn)已

40、經(jīng)死亡 INB：塊B開始點(diǎn)的活躍變量集合 OUTB：塊B結(jié)束點(diǎn)的活躍變量集合 useB：塊B中有引用且在引用前無定值的變量集 defB：塊B中有定值的變量集應(yīng)用 一種重要應(yīng)用就是基本塊的寄存器分配第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 = 和到達(dá)定值等式之間的聯(lián)系與區(qū)別 都以集合并算符作為它們的匯合算符 信息流動(dòng)方向相反，IN和OUT的作用相互交換 use和def分別取代gen和kill 仍然需要最小解第61頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.5 可用表達(dá)式 x = y + z x = y + z x = y + z . . . . y = z = . . . p p py + z 在p點(diǎn) y + z 在p點(diǎn) y + z 在p點(diǎn)可用不可用不可用第62頁，共140頁。9.2 數(shù)據(jù)流分析介紹9.2.5 可用表達(dá)式下面兩種情況下， 4i在B3的入口都可

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

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

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

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

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

48、半格的高度上升鏈?zhǔn)切蛄衳1 x2 xn半格的高度就是其中最長上升鏈中的個(gè)數(shù)若半格的高度有限，證明數(shù)據(jù)流分析迭代算法的收斂則非常容易第75頁，共140頁。9.3 數(shù)據(jù)流分析的基礎(chǔ)9.3.2 遷移函數(shù)遷移函數(shù)族F : V V有下列性質(zhì) F包括恒等函數(shù) F封閉于復(fù)合 若F中所有函數(shù)f 都有單調(diào)性，即 x y蘊(yùn)涵f(x) f(y)，或 f(x y) f(x) f(y)則稱框架(D, V, , F)是單調(diào)的 框架(D, V, , F)的分配性 對F中所有的f，f(x y) = f(x) f(y) 第76頁，共140頁。9.3 數(shù)據(jù)流分析的基礎(chǔ)9.3.2 遷移函數(shù)例到達(dá)定值分析若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為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ù)流分析的基礎(chǔ)9.3.3 一般框架的迭代算法以正向數(shù)據(jù)流分析為例(1) OUTENTRY = vENTRY;(2) for (除了ENTRY以外的每個(gè)塊B) OUTB =;(3) while (任

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

51、是無限的程序可能的執(zhí)行路徑集：程序執(zhí)行所走的路徑屬于該集合 這是理想解所考慮的路徑集可能的執(zhí)行路徑集 執(zhí)行路徑集尋找所有可能執(zhí)行路徑是不可判定的以下討論以正向數(shù)據(jù)流分析為例第80頁，共140頁。9.3 數(shù)據(jù)流分析的基礎(chǔ)9.3.4 數(shù)據(jù)流解的含義理想解若路徑P = ENTRY B1 B2 Bk，定義 fP fk1 f2 f1IDEALB = /P是從ENTRY到B的一條可能路徑 fP(vENTRY)有關(guān)理解解的結(jié)論任何大于理想解IDEAL的回答一定是不對的任何小于或等于IDEAL的值是穩(wěn)妥的在穩(wěn)妥的值中，越接近IDEAL的值越精確第81頁，共140頁。9.3 數(shù)據(jù)流分析的基礎(chǔ)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的定義并沒有通向一個(gè)直接算法第82頁，共140頁。9.3 數(shù)據(jù)流分析的基礎(chǔ)9.3.4 數(shù)據(jù)流解的含義先前算法得到的最大不動(dòng)點(diǎn)解MFP不是先找出到達(dá)一個(gè)塊的所有路徑，然后用匯合運(yùn)算，而是訪問每個(gè)基本塊，并且不一定按照程序執(zhí)行時(shí)的次序在每個(gè)匯合點(diǎn)，把匯合運(yùn)算作用在到目前為止得到的數(shù)據(jù)流值上，其中所用一些初值是人工引入的 MFP:

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

54、半格 變量的類型所允許的所有常量 值NAC表示不是常量 值UNDEF表示沒有定義程序中各變量的半格的積把程序中每個(gè)變量映射到 該半格上的一個(gè)“值”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)系來表達(dá)fs (m是變量到“值”的映射)(1) 如果s不是賦值語句，則fs是恒等函數(shù)(2) 若s對變量x賦值，則對所有v x，m(v) = m(v)，再看m(x)：若s的右部是一個(gè)常量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 常量傳播框架的單調(diào)性 m(y)m(z)m(x)UNDEF UNDEF UNDEFc2 UNDEFNACNACUNDEFUNDEF c1 c2 c1 + c2NACNACUNDEFNACNAC c2NACNACNAC(1) 賦值語句的形式不是x = y + z fs不改變m(x)的值，或者改變成一個(gè)常量 在這些情況下，fs肯定是單調(diào)的第87頁，共140頁。9.4 常 量 傳 播9.4.3 常量傳播框架的單調(diào)性 m(y)m(z

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

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

58、表達(dá)式的形式出現(xiàn) 冗余可能只出現(xiàn)在一部分路徑上 討論最小化x + y這樣表達(dá)式的計(jì)算次數(shù)的方法 策略是，一個(gè)計(jì)算盡量不做，除非它不得不做 首先討論冗余的不同形式，以建立直觀認(rèn)識(shí)，然后描述廣義的冗余刪除問題，最后提出算法 算法涉及到求解多個(gè)正向或逆向的數(shù)據(jù)流問題第91頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源公共子表達(dá)式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的表達(dá)式b + c是完全冗余的，因?yàn)樗械竭_(dá)B4的路徑都計(jì)算b + c ，并且b和c都未重新定值B2和B3的出邊的集合形成一個(gè)割集，若把該割集刪掉，則從起點(diǎn)到B4的路徑都被割斷 B1B2B4B3b = 7d = b + ca = b + ce = b + c第93頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源循環(huán)不變表達(dá)式a = b + ct = b + ca = t第94頁，共140頁。9.5 部 分 冗 余 刪 除9.5.1 冗余的根源部分冗余表達(dá)式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是一條關(guān)鍵邊：源結(jié)點(diǎn)有多個(gè)后繼目標(biāo)結(jié)點(diǎn)有多個(gè)前驅(qū)B1B2B3B4d = b + ca = b + cB5B1B2B3B6t = b + ct = b + ca = tB5d = tB4增加新塊來刪除冗余第97頁，共140頁。9.5 部 分 冗 余