【正文】 （ 3） while D(n)發(fā)生變化 do （ 4） for N – {n0}中的 n do （ 5） ?PnpDnnD的前驅)。 例 ? 2的唯一前驅是 1，加入 I(1)，而 3不是，其他節(jié)點的前驅都不是 2，因此 I(1)={1, 2} ? 3的前驅 2已經(jīng)選中，構造 I(3)，沒有節(jié)點可以加入， I(3)={3, 4, 5} ?構造 I(4)， 6可以加入，沒有其他節(jié)點， I(4)={4, 5, 6} ?構造 I(7)={7, 8, 9, 10} 區(qū)間圖 ?流圖 G?區(qū)間圖 I(G) ? I(G)的節(jié)點對應 G的區(qū)間 ? I(G)的初始節(jié)點是包含 G的初始節(jié)點的區(qū)間 ? I(G)的節(jié)點到其另一節(jié)點（一個區(qū)間 I到另一個區(qū)間 J）存在一條邊，當且僅當存在一條從 I的某個節(jié)點到 J的首節(jié)點的邊 ——不可能存在到 J的非首節(jié)點 n的邊，在算法中 n不可能被加入 J ?區(qū)間圖序列： I(G), I(I(G)), … ?最終得到 限制流圖 ：每個節(jié)點是孤立區(qū)間 ?若 G可約，則限制流圖為單節(jié)點 例 區(qū)間圖序列 節(jié)點分裂 ?如果原流圖不可約，得到不是單節(jié)點的限制流圖，可將節(jié)點分裂，繼續(xù)構造 ?分裂：若節(jié)點 n有 k個前驅，則用 n1, n2, …取代 n， n的第 i個前驅成為 ni的唯一前驅，而 n的所有后繼都成為 ni的后繼 T1－ T2分析 ?可達到區(qū)間分析同樣效果： ? T1變換：若 n是一個帶有循環(huán)的節(jié)點，即存在邊 n?m，則刪除這條邊 ? T2變換：若節(jié)點 n（不是初始節(jié)點）具有唯一的前驅 m，那么 m通過刪除 n并將 n的所有后繼（可能包括 m）變成 m的后繼即可消掉 n ?按任意順序對流圖 G應用 T1和 T2 ?直至產(chǎn)生一個無法再變換的流圖，結果是唯一的 ——即便先前應用了某些 T1和 T2，由 T1刪除或由 T2消掉的候選者仍是候選者 ?得到的結果就是限制流圖 例 T1和 T2變換 區(qū)域 ?region：首節(jié)點支配其他所有節(jié)點，除進入首節(jié)點的邊外，所有邊都在區(qū)域內(nèi) ?區(qū)間必為區(qū)域，反之不一定 ?用 T1和 T2化簡流圖 G ?一個節(jié)點代表 G的一個區(qū)域 ? a?b的邊 ——a表示的區(qū)域中的節(jié)點指向 b的首節(jié)點的一組邊 ? G中的每個節(jié)點和每條邊恰好由當前圖中的一個節(jié)點或一條邊代表 正確性 ?對 G本身，顯然正確 ?對節(jié)點 n（代表區(qū)域 R）使用 T1 ? n?n代表一組邊 E，顯然 E都指向 R的首節(jié)點 ?顯然 E（ n?n）加入 R， R仍為區(qū)域 ?刪除 n?n， n代表 R和 E，仍是區(qū)域，正確 ?使用 T2，利用節(jié)點 a消掉節(jié)點 b，分別代表區(qū)域 R和 S， a?b——E ? R、 S、 E組合為一個區(qū)域，首節(jié)點為 R的首節(jié)點，它支配 S中所有節(jié)點 ——若不然，必有通向 S首節(jié)點的路徑，最后一條邊不在 E中，此邊必為進入 b的某條其他邊，但既然使用了 T2，必然不存在這樣的邊 例 尋找支配節(jié)點 ?d支配 n： p1, p2, …, p k是 n的所有前驅且d≠n， d dom n當且僅當對每個 i， d dom pi ?算法 輸入：流圖 G，帶有節(jié)點集合 N，邊集合 E和初始節(jié)點 n0 輸出：關系 dom 方法：重復下面過程計算 D(n)——n的支配節(jié)點集合 （ 1） D(n0) = { n0 }。 首節(jié)點 n的選擇方法，初始所有節(jié)點均“未選中”： 構造 I(n0)并“選中”該區(qū)間中所有節(jié)點 。 流圖深度優(yōu)先表示的邊 1. 從節(jié)點 m到它的祖先的邊 ——retreating邊，若流圖可約，恰好就是回邊 2. 從節(jié)點 m到它的后代的邊 ——前進邊，dfst中所有邊都是前進邊 3. 邊 m?n， m和 n無祖先后代關系 ——交叉邊，若畫 dfst時，每個節(jié)點的孩子都是由左至右加入的，則交叉邊必是由右至左的 ? dfn[m]≥ dfn[n]??m?n是后退邊 流圖的深度 ?給定一個流圖的深度優(yōu)先生成樹，深度 ——無環(huán)路徑上后退邊的最大數(shù)目 ?例 ：例 3 ?深度不會大于循環(huán)嵌套的深度 區(qū)間（ interval） ? 流圖中的自然循環(huán)加上在該循環(huán)節(jié)點上的無環(huán)路結構 ——其中一個節(jié)點（首節(jié)點）支配所有其他節(jié)點 ? 形式化定義：給定一個具有初始節(jié)點 n0的流圖 G和 G的一個節(jié)點 n，首節(jié)點為 n的區(qū)間（記為 I(n)）定義如下： 1. n在 I(n)中 2. 若某個節(jié)點 m(m≠n0)的所有前驅在 I(n)中，則 m在 I(n)中 3. I(n)中沒有其他任何節(jié)點 區(qū)間劃分 算法 流圖的區(qū)間分析 輸入：帶有初始節(jié)點 n0的流圖 G 輸出：流圖 G 的不相交區(qū)間的一個劃分 方法：對任意的節(jié)點 n，通過上面概述的算法計算 I(n) I(n) := {n}。 10) i := G的節(jié)點數(shù) 。 8) T := 空 。 7) i := i 1。 5) search(s) end。 3) if s 標記為“未訪問” then begin。 begin 1) 將 n標記為已訪問 。用變量 i記錄 G的節(jié)點數(shù)，并遞減到 1，搜索時將深度優(yōu)先編號 dfn[n]賦予節(jié)點 n。 end def[main]={g}, def[one]={x}, def[two]={h} two：只調(diào)用 one， change[one]={x}，而 x不是全局變量，不加入 change[two]； x是 one的形參，對應的實參 y是 two的形參，因此 change[two]={h, y} one：兩次調(diào)用 two， h是全局變量?change[one]={h, x}； y是 two的形參，對應的實參為 w、 g，分別為 one的形參和全局變量， ?change[one]={g,h,w,x} main：調(diào)用 one， g、 h是全局變量?change[main]={g,h}； w、 x是 one的形參，對應實參為 h、 i，但 i是局部變量，因此 change[main]={g,h} 迭代 two： g為全局變量，而 w對應的實參k為局部變量，因此 change[two]={g,h,y} 繼續(xù)迭代沒有變化，停止 change信息的用途 ?計算塊 B的 a_kill[B] ? 只有 a是 change[q]中某個變量的別名，才可認為 B中對 q的調(diào)用注銷了含有 a的表達式 ?計算可用表達式 ? 從 q的入口到返回點的每條路徑，都計算 a+b，且在其后沒有對 a、 b的重新定義，才能認為 q產(chǎn)生了 a+b，別名的考慮也是如此 ? 最簡單的（保守、保險的）方法 ——過程調(diào)用不產(chǎn)生任何表達式 ? 更復雜、準確的方法 ——迭代計算 gen[p] 結構化流圖的數(shù)據(jù)流分析 ? 深度優(yōu)先搜索 ?例 ：流圖節(jié)點的深度優(yōu)先排序 例 ?例 ，深度優(yōu)先遍歷樹，節(jié)點的完整訪問順序為： 1, 3, 4, 6, 7, 8, 10, 8, 9, 8, 7, 6, 4, 5, 4, 3, 1, 2, 1 ?標注每個節(jié)點最后一次的出現(xiàn)： 1, 3, 4, 6, 7, 8, 10, 8, 9, 8, 7, 6, 4, 5, 4, 3, 1, 2, 1 ?標注的順序恰好是節(jié)點編號逆序 算法 深度優(yōu)先排序 輸入：流圖 G 輸出： G的深度優(yōu)先生成樹（ dfst） T和 G的節(jié)點的深度優(yōu)先順序 方法： 使用遞歸過程 search(n)，算法首先將 G的所有節(jié)點初始化為“未訪問”，然后調(diào)用 search(n0)，n0是起始節(jié)點。 local k。 two(g, x)。 x := …。 one(h, i)。 local i。 (6) for q的每個形式參數(shù) x（第 j個） do (7) if x在 change[q]中 then (8) for pi對 q的每次調(diào)用 do (9) if 本次調(diào)用的第 j個實參 a是全局變量或 pi的形式參數(shù) then 將 a添加到 change[pi]中 (10) end 例 global g, h。否則，對過程間的調(diào)用順序不做任何假設 輸出：對每個過程 p，給出 change[p]，即并非通過別名改變而是被 p顯示改變的的全局變量和 p的形參的集合 方法： 1. 通過檢查，對每個過程 p，計算 def[p] 2. 執(zhí)行以下程序 計算 change的迭代算法 (1) for 每個過程 p do change[p] := def[p]。 end h≡w, i≡x w≡y, w≡z w≡y, x≡z k≡w, y≡x 所有變量都可能是另一個變量的別名！ 存在過程調(diào)用時數(shù)據(jù)流分析 ? change[p]： p可能改變的變量集合 ? def[p]： p中顯式定義的全局變量及其形參 ? change[p] = def[p]∪ A ∪ G 1. A={a | a是全局變量或 p的形參，使得，對某個過程 q和整數(shù) i， p調(diào)用 q時將 a作為第 i個實參，且q的的 i個形參在 change[p]中 } 2. G={g | g是 change[q]中的全局變量，且 p調(diào)用了 q} 算法 輸入：過程 p1, p2, …, p n。 local k。 two(g, x)。 x := …。 one(h, i)。 local i。(a[2]) B3 利用指針信息 ?塊 B中引用了指針 p，則可對引用之前的語句應用 transs，獲得語句級的指針信息 ?利用這些信息進行更精確的數(shù)據(jù)流分析 ?計算到達定義（ kill和 gen） ? 只有當確定 p惟一指向 b，且 b不是數(shù)組時，才可得到結論： *p=a注銷了 b的定義 ? p若指向多個變量，則認為 *p=a對其中任何一個都沒有注銷 ——還是保守的 ?計算活躍變量（ def和 use）類似 過程間的數(shù)據(jù)流分析 ?首先確定一個過程對其他過程的 gen、 kill、 use和 def，然后獨立計算每個過程的數(shù)據(jù)流信息 ?例 注意參數(shù)互為別名的情況 ? 右圖為一個過程 p的流圖 ? x、 y為參數(shù) ? B1中的 b+x在 B3中是否可用？ ? 取決于 x、 b與 y是否互為別名 a := b + x y := c d := b + x B1 B2 B3 帶有過程調(diào)用的代碼模型 ?設定一種語言 ? 允許遞歸，無塊結構 ——過程可引用的變量只可能是全局變量和自身的局部變量 ? 參數(shù)傳遞為傳地址方式 ? 每個過程只有一個入口和一個返回節(jié)點 ?過程 p調(diào)用 q(u,v)， q可能改變哪些變量？ ? 只有全局變量和 u、 v，局部變量在 q結束后生存期也結束了 ? 只需檢查 q中對哪些全局變量和 u、 v進行了定義即可 別名的計算 ? 別名 ——≡關系，具有傳遞性 ——所有變量分成若干等價類 算法 簡單別名計算 輸入：過程和全局變量集合 輸出：等價關系 ≡：若 x、 y互為別名， x≡y，反之不一定 方法： 1. 若需要，將變量重新命名，使得任何過程使用相同的形參或局部變量標識符，也不允許局部變量、形參或全局變量共用同一個標識符 2. 若存在過程 p(x1, x2, …, x n)及其調(diào)用 p(y1, y2, …, y n)，則對所有的 i，令 xi ≡yi——形參都可以成為實參的別名 3. 通過以下關系式求出 ≡在形－實參對應別名上的自反傳遞閉包 a) 若 y≡x，則 x≡y b) 對任意 y，若 x≡y且 y≡z，則 x≡z 例 global g, h。(a[0]) B2 p := p +1 B4 p := q B5 p := amp。 c， q是指針， c是非零整數(shù)，則transs(S)=(S{(p,b)|b是任意變量 })∪ {(p,b)|(q,b)∈ S且 b為數(shù)組 } 3. s： p=q，則 transs(S)=(S{(p,b)|b是任意變量 })∪ {(p,b)|(q,b)∈ S} transB計算規(guī)則（續(xù)） 4. s將其他任何表達式的值賦予 p，則 transs(S)=S{(p,b)|b是任意變量 } 5. s不是為指針賦值，則 transs(S)=S ? ? 若 B由語句 s1, s2, …, s k組成，則 transB(S)=transs k(transs k1(…(trans s2(transs1(S)))…) ?PBB PoutBinBint r an sBout的前驅][][]),[(][ ??例 out[B1]=transB1(Φ )={(q, c)} o