【正文】 search(n)。 begin 1) 將 n標(biāo)記為已訪(fǎng)問(wèn) 。 2) for n的每個(gè)后繼 s do。 3) if s 標(biāo)記為“未訪(fǎng)問(wèn)” then begin。 4) 將邊 n?s添加到 T。 5) search(s) end。 6) dfn[n] := i。 7) i := i 1。 end。 8) T := 空 。 9) for G的每個(gè)節(jié)點(diǎn) n do 將 n 標(biāo)記為“未訪(fǎng)問(wèn)” 。 10) i := G的節(jié)點(diǎn)數(shù) 。 11) search(n0)。 流圖深度優(yōu)先表示的邊 1. 從節(jié)點(diǎn) m到它的祖先的邊 ——retreating邊，若流圖可約，恰好就是回邊 2. 從節(jié)點(diǎn) m到它的后代的邊 ——前進(jìn)邊，dfst中所有邊都是前進(jìn)邊 3. 邊 m?n， m和 n無(wú)祖先后代關(guān)系 ——交叉邊，若畫(huà) dfst時(shí)，每個(gè)節(jié)點(diǎn)的孩子都是由左至右加入的，則交叉邊必是由右至左的 ? dfn[m]≥ dfn[n]??m?n是后退邊 流圖的深度 ?給定一個(gè)流圖的深度優(yōu)先生成樹(shù)，深度 ——無(wú)環(huán)路徑上后退邊的最大數(shù)目 ?例 ：例 3 ?深度不會(huì)大于循環(huán)嵌套的深度 區(qū)間（ interval） ? 流圖中的自然循環(huán)加上在該循環(huán)節(jié)點(diǎn)上的無(wú)環(huán)路結(jié)構(gòu) ——其中一個(gè)節(jié)點(diǎn)（首節(jié)點(diǎn)）支配所有其他節(jié)點(diǎn) ? 形式化定義：給定一個(gè)具有初始節(jié)點(diǎn) n0的流圖 G和 G的一個(gè)節(jié)點(diǎn) n，首節(jié)點(diǎn)為 n的區(qū)間（記為 I(n)）定義如下： 1. n在 I(n)中 2. 若某個(gè)節(jié)點(diǎn) m(m≠n0)的所有前驅(qū)在 I(n)中，則 m在 I(n)中 3. I(n)中沒(méi)有其他任何節(jié)點(diǎn) 區(qū)間劃分 算法 流圖的區(qū)間分析 輸入：帶有初始節(jié)點(diǎn) n0的流圖 G 輸出：流圖 G 的不相交區(qū)間的一個(gè)劃分 方法：對(duì)任意的節(jié)點(diǎn) n，通過(guò)上面概述的算法計(jì)算 I(n) I(n) := {n}。 while 存在所有前驅(qū)都在 I(n)中的節(jié)點(diǎn) m≠n0 do I(n) := I(n) ∪ m。 首節(jié)點(diǎn) n的選擇方法，初始所有節(jié)點(diǎn)均“未選中”： 構(gòu)造 I(n0)并“選中”該區(qū)間中所有節(jié)點(diǎn) 。 while 存在一個(gè)還“未選中”但其一個(gè)前驅(qū)節(jié)點(diǎn)被選中的節(jié)點(diǎn) m do 構(gòu)造 I(m)并選中該區(qū)間中所有節(jié)點(diǎn) 02。 例 ? 2的唯一前驅(qū)是 1，加入 I(1)，而 3不是，其他節(jié)點(diǎn)的前驅(qū)都不是 2，因此 I(1)={1, 2} ? 3的前驅(qū) 2已經(jīng)選中，構(gòu)造 I(3)，沒(méi)有節(jié)點(diǎn)可以加入， I(3)={3, 4, 5} ?構(gòu)造 I(4)， 6可以加入，沒(méi)有其他節(jié)點(diǎn)， I(4)={4, 5, 6} ?構(gòu)造 I(7)={7, 8, 9, 10} 區(qū)間圖 ?流圖 G?區(qū)間圖 I(G) ? I(G)的節(jié)點(diǎn)對(duì)應(yīng) G的區(qū)間 ? I(G)的初始節(jié)點(diǎn)是包含 G的初始節(jié)點(diǎn)的區(qū)間 ? I(G)的節(jié)點(diǎn)到其另一節(jié)點(diǎn)（一個(gè)區(qū)間 I到另一個(gè)區(qū)間 J）存在一條邊，當(dāng)且僅當(dāng)存在一條從 I的某個(gè)節(jié)點(diǎn)到 J的首節(jié)點(diǎn)的邊 ——不可能存在到 J的非首節(jié)點(diǎn) n的邊，在算法中 n不可能被加入 J ?區(qū)間圖序列： I(G), I(I(G)), … ?最終得到 限制流圖 ：每個(gè)節(jié)點(diǎn)是孤立區(qū)間 ?若 G可約，則限制流圖為單節(jié)點(diǎn) 例 區(qū)間圖序列 節(jié)點(diǎn)分裂 ?如果原流圖不可約，得到不是單節(jié)點(diǎn)的限制流圖，可將節(jié)點(diǎn)分裂，繼續(xù)構(gòu)造 ?分裂：若節(jié)點(diǎn) n有 k個(gè)前驅(qū)，則用 n1, n2, …取代 n， n的第 i個(gè)前驅(qū)成為 ni的唯一前驅(qū)，而 n的所有后繼都成為 ni的后繼 T1－ T2分析 ?可達(dá)到區(qū)間分析同樣效果： ? T1變換：若 n是一個(gè)帶有循環(huán)的節(jié)點(diǎn)，即存在邊 n?m，則刪除這條邊 ? T2變換：若節(jié)點(diǎn) n（不是初始節(jié)點(diǎn)）具有唯一的前驅(qū) m，那么 m通過(guò)刪除 n并將 n的所有后繼（可能包括 m）變成 m的后繼即可消掉 n ?按任意順序?qū)α鲌D G應(yīng)用 T1和 T2 ?直至產(chǎn)生一個(gè)無(wú)法再變換的流圖，結(jié)果是唯一的 ——即便先前應(yīng)用了某些 T1和 T2，由 T1刪除或由 T2消掉的候選者仍是候選者 ?得到的結(jié)果就是限制流圖 例 T1和 T2變換 區(qū)域 ?region：首節(jié)點(diǎn)支配其他所有節(jié)點(diǎn)，除進(jìn)入首節(jié)點(diǎn)的邊外，所有邊都在區(qū)域內(nèi) ?區(qū)間必為區(qū)域，反之不一定 ?用 T1和 T2化簡(jiǎn)流圖 G ?一個(gè)節(jié)點(diǎn)代表 G的一個(gè)區(qū)域 ? a?b的邊 ——a表示的區(qū)域中的節(jié)點(diǎn)指向 b的首節(jié)點(diǎn)的一組邊 ? G中的每個(gè)節(jié)點(diǎn)和每條邊恰好由當(dāng)前圖中的一個(gè)節(jié)點(diǎn)或一條邊代表 正確性 ?對(duì) G本身，顯然正確 ?對(duì)節(jié)點(diǎn) n（代表區(qū)域 R）使用 T1 ? n?n代表一組邊 E，顯然 E都指向 R的首節(jié)點(diǎn) ?顯然 E（ n?n）加入 R， R仍為區(qū)域 ?刪除 n?n， n代表 R和 E，仍是區(qū)域，正確 ?使用 T2，利用節(jié)點(diǎn) a消掉節(jié)點(diǎn) b，分別代表區(qū)域 R和 S， a?b——E ? R、 S、 E組合為一個(gè)區(qū)域，首節(jié)點(diǎn)為 R的首節(jié)點(diǎn)，它支配 S中所有節(jié)點(diǎn) ——若不然，必有通向 S首節(jié)點(diǎn)的路徑，最后一條邊不在 E中，此邊必為進(jìn)入 b的某條其他邊，但既然使用了 T2，必然不存在這樣的邊 例 尋找支配節(jié)點(diǎn) ?d支配 n： p1, p2, …, p k是 n的所有前驅(qū)且d≠n， d dom n當(dāng)且僅當(dāng)對(duì)每個(gè) i， d dom pi ?算法 輸入：流圖 G，帶有節(jié)點(diǎn)集合 N，邊集合 E和初始節(jié)點(diǎn) n0 輸出：關(guān)系 dom 方法：重復(fù)下面過(guò)程計(jì)算 D(n)——n的支配節(jié)點(diǎn)集合 （ 1） D(n0) = { n0 }。 （ 2） for N – {n0}中的 n do D(n) := N。 （ 3） while D(n)發(fā)生變化 do （ 4） for N – {n0}中的 n do （ 5） ?PnpDnnD的前驅(qū))。(}{:)( ??例 D(2)={2}∪ D(1)={1,2} D(3)={3}∪ {{1}∩ {1,2}∩ {1,2,…,10})={1,3} D(4)={4}∪ {{1,3}∩ {1,2,…,10})={1,3,4} D(5)={5}∪ {1,3,4}={1,3,4,5} D(6)={6}∪ {1,3,4}={1,3,4,6} D(7)={7}∪ {{1,3,4}∩ {1,3,4,6}∩ {1,2,…,10})={1,3,4,7} D(8)={8}∪ {1,3,4,7}={1,3,4,7,8} D(9)={9}∪ {1,3,4,7,8}={1,3,4,7,8,9} D(10)={10}∪ {1,3,4,7,8}={1,3,4,7,8,10} 不再改變 高效數(shù)據(jù)流算法 ? 迭代算法中的深度優(yōu)先順序 ?前面的研究都假定信息沿?zé)o環(huán)路徑傳播，實(shí)際上環(huán)路沒(méi)有影響 ——?jiǎng)h除環(huán)，形成更短的無(wú)環(huán)路徑，信息傳播沒(méi)有改變 ?無(wú)環(huán)路徑：修改數(shù)據(jù)流迭代算法的節(jié)點(diǎn)訪(fǎng)問(wèn)順序，加快算法速度 ?區(qū)間深度 ：得到限制流圖所需的區(qū)間劃分次數(shù) ? Knuth統(tǒng)計(jì)得到：典型流圖的區(qū)間深度很低，評(píng)價(jià)為 ?深度 ：無(wú)環(huán)路徑上后退邊的最大數(shù)目 ?區(qū)間深度永遠(yuǎn)不會(huì)比深度小 迭代次數(shù) ?a?b是后退邊時(shí)， b的深度優(yōu)先編號(hào)才比a的編號(hào)小 ——修改算法 ，按每個(gè)塊B深度優(yōu)先編號(hào)順序計(jì)算到達(dá)定義 ?假定存在定義 d的傳播路徑： 3?5?19?35?16?23?45?4?10?17 ?第一次迭代： d?out[3]?in[5]?out[5]… ?out[35]，在 16處截?cái)?——先計(jì)算的in[16]、 out[16]，后計(jì)算的 35 ?第二次迭代：在 4處截?cái)? ?第三次迭代：完成 迭代次數(shù)（續(xù)） ?一般的，迭代次數(shù)不超過(guò)后退邊數(shù)目＋ 1 ?所需遍歷次數(shù)是深度＋ 1 ?使用深度優(yōu)先算法的遍數(shù)實(shí)際上是深度＋ 2——遍歷次數(shù)不超過(guò) 5 ?可用表達(dá)式或其他通過(guò)前向傳播計(jì)算的數(shù)據(jù)流問(wèn)題，按深度優(yōu)先順序計(jì)算 ?活躍變量等后向傳播計(jì)算的問(wèn)題，按深度優(yōu)先順序的逆序計(jì)算 基于結(jié)構(gòu)的數(shù)據(jù)流分析 ?訪(fǎng)問(wèn)節(jié)點(diǎn)的次數(shù)不會(huì)大于區(qū)間深度，平均次數(shù)比區(qū)間深度小得多 ?算法基于 T1和 T2變換得到結(jié)構(gòu)上 ?對(duì)區(qū)域 R中的每個(gè)塊 B，計(jì)算從區(qū)域首節(jié)點(diǎn)到 B的末尾的路徑上所產(chǎn)生和注銷(xiāo)的定義集合 genR, B和 killR, B ?然后計(jì)算 轉(zhuǎn)移函數(shù) transR, B(S)： S中哪些定義會(huì)沿著 R中路徑到達(dá) B的末尾 基于結(jié)構(gòu)的數(shù)據(jù)流分析（續(xù)） ? 到達(dá)塊 B末尾的定義可分為兩類(lèi) 1. 在 R中產(chǎn)生并傳播到 B末尾 ——與 S無(wú)關(guān) 2. 不是在 R中產(chǎn)生，但在到 B末尾的路徑中也未注銷(xiāo)，若它在 S中則它在 transR,B(S)中 ? transR,B(S)=genR,B∪ (S killR,B) ? 算法核心思想：對(duì)流圖使用 T T2變換逐漸變大的區(qū)域計(jì)算 transR,B 基于結(jié)構(gòu)的數(shù)據(jù)流分析算法 ?起點(diǎn)是單個(gè)塊 B構(gòu)成的區(qū)域 ? genB,B=gen[B]， killB,B=kill[B] ?使用 T2變換： R1消掉 R2構(gòu)成 R ? R2到 R1首節(jié)點(diǎn)的邊不屬于 R—— R中沒(méi)有 R2到 R1后退邊 ——R中 路徑都是先穿過(guò) R1（可無(wú)）， 然后穿過(guò) R2（可無(wú)），但不能 返回 R1——R2不會(huì)影響 R1中節(jié)點(diǎn)轉(zhuǎn)移函數(shù) ?對(duì) R1中的 B： genR,B=genR1,B， killR,B=killR1,B T2變換（續(xù)） ? 對(duì) R2中的 B，滿(mǎn)足下列任一條件的定義都能到達(dá) B的末尾 1. 定義是在 R2中產(chǎn)生的 2. 定義是 R1產(chǎn)生的，并到達(dá) R2首節(jié)點(diǎn)的某個(gè)前驅(qū)節(jié)點(diǎn)的末尾，在 R2首節(jié)點(diǎn)到 B末尾的路徑上沒(méi)有被注銷(xiāo) 3. 定義屬于 S，到達(dá) R2首節(jié)點(diǎn)的某個(gè)前驅(qū)沒(méi)有注銷(xiāo)，在 R2首節(jié)點(diǎn)到 B末尾的路徑上也沒(méi)有注銷(xiāo) ? 關(guān)鍵：能到達(dá) R2首節(jié)點(diǎn)前驅(qū)末尾的定義 ? genR,B = genR2,B∪ (G – killR2,B) killR,B = killR2,B∪ (K – genR2,B) G： R2首節(jié)點(diǎn)所有前驅(qū) P的 genR1,P的并集 K： R2首節(jié)點(diǎn)所有前驅(qū) P的 killR1,P的交集 T1變換的處理 ? 無(wú)需考慮環(huán)路 ? 在 B末尾產(chǎn)生的定義必 是下面兩種情況之一 1. 在 R1中產(chǎn)生，并且不需回邊即到達(dá) B 2. 在 R1中產(chǎn)生，經(jīng)一條回邊到達(dá)首節(jié)點(diǎn)的一個(gè)前驅(qū)，且在首節(jié)點(diǎn)到 B的路徑中未注銷(xiāo) ? genR,B = genR1,B∪ (G – killR1,B) killR,B = killR1,B G： R中首節(jié)點(diǎn)所有前驅(qū) P的 genR1,P的并集 例 ?使用 T2由 C消掉 D形成 R，則 ?對(duì) C： genR,C=genC,C=000, killR,C=killC,C=010 ?對(duì) D：只有一個(gè)前驅(qū) C genR,D=genD,D∪ (genC,CkillD,D)=001 killR,D=killD,D∪ (killC,CgenD,D)=010 塊 gen kill A 100 010 B 010 101 C 000 010 D 001 000 例 （續(xù)） ?使用 T1由 R形成 S，則 ? kill不變： killS,C=killR,C=000, killS,D=killR,D=010 ?計(jì)算 gen：唯一回邊是 D?C，則 genS,C=genR,C∪ (genR,DkillR,C)=001 killS,D=killR,D∪ (killR,DgenR,D)=001 ?對(duì)區(qū)域 T的計(jì)算類(lèi)似 ? genT,A=100, killT,A=010, genT,B=010, killT,B=101 例 （續(xù)） ?使用 T2由 T消掉 S形成最終單一節(jié)點(diǎn) ? A、 B的 gen和 kill不變 ?對(duì) C、 D， C有兩個(gè)前驅(qū) A、 B，則 G=genT,A∪ genT,B=110 K=killT,A∩ killT,B=000 計(jì)算 gen和 kill genU,C=genS,C∪ (GkillS,C)=101 killU,C=killS,C∪ (KgenS,C)=010 genU,D=genS,D∪ (GkillS,D)=101 killU,D=killS,D∪ (KgenS,D)=010 算法 基于結(jié)構(gòu)的到達(dá)定義 輸入：可約流圖 G以及 G中每個(gè)塊 B的定義集合gen[B]和 kill[B] 輸出：每個(gè)塊 B的 in[B] 方法： 1. 找出 G的 (T1, T2)分解 2. 對(duì)分解中的每個(gè)區(qū)域 R，從內(nèi)向外計(jì)算 R中每個(gè)塊 B的 genR,B和 killR,B 3. 如果 U是整個(gè)圖構(gòu)成的區(qū)域的名字，那么對(duì)每個(gè)塊 B，in[B]設(shè)置為 B的所有前驅(qū) P的 genU,P的并集 速度上的改進(jìn) ? 若有轉(zhuǎn)移函數(shù) G∪ (SK)，從 K中刪除某些成員不會(huì)改變函數(shù)，因此 T2變換計(jì)算中的 killR,B=killR2,B∪ (KgenR2,