1. 數(shù)學(xué)基礎(chǔ)：兩者的共同點(diǎn)是都基于數(shù)據(jù)流值的半格和對(duì)組合運(yùn)算封閉的傳遞函數(shù)，不同點(diǎn)是區(qū)域分析算法還要求傳遞函數(shù)是一個(gè)半格，不僅支持組合運(yùn)算，而且支持交匯運(yùn)算和閉包運(yùn)算，交匯運(yùn)算用于把有相同后繼的不同執(zhí)行路徑組合起來，閉包運(yùn)算用于環(huán)上（比如循環(huán)）執(zhí)行零到多次的效果
2. 流程：迭代算法由初始化和循環(huán)求不動(dòng)解組成，以前向數(shù)據(jù)流為例，其中初始化包括初始化入口基本塊的out集合為合適值，其它基本塊的out集合為半格的頂元素；循環(huán)求不動(dòng)解遍歷除入口外（因?yàn)槿肟诘膐ut不會(huì)變）的每個(gè)基本塊，計(jì)算其out集合，直至所有基本塊的out不再改變。區(qū)域分析算法由計(jì)算層次區(qū)域序列、構(gòu)造區(qū)域傳遞函數(shù)和計(jì)算各區(qū)域入口值組成，計(jì)算層次區(qū)域序列自底向上，基本塊為葉子區(qū)域，自然循環(huán)分為循環(huán)體區(qū)域和循環(huán)區(qū)域，都是內(nèi)部區(qū)域，不是自然循環(huán)的整個(gè)流圖為根區(qū)域；區(qū)域傳遞函數(shù)有2個(gè)，一是R區(qū)域入口到其直接子區(qū)域S的入口的數(shù)據(jù)流值傳遞，記作Fin(R,S)，另一是R區(qū)域入口到其直接子區(qū)域出口基本塊B（可能有多個(gè)）出口處的數(shù)據(jù)流值傳遞，記作Fout(R,B)，區(qū)域傳遞函數(shù)的計(jì)算自底向上，對(duì)于葉子區(qū)域，F(xiàn)in是恒等函數(shù)，F(xiàn)out和迭代算法的傳遞函數(shù)一樣，取決于具體數(shù)據(jù)流問題；對(duì)于更大的區(qū)域（非葉子區(qū)域），遍歷每個(gè)子區(qū)域，F(xiàn)in由所有Fout(R,B)交匯而成，B為S在R中的前驅(qū)，若R為循環(huán)區(qū)域，則再求Fout的閉包，遍歷S的每個(gè)出口基本塊B，F(xiàn)out由Fout(S,B)和Fin(R,S)組合而成。計(jì)算各區(qū)域入口值自頂向下，根區(qū)域的In值等于流圖入口的In值，其它區(qū)域S的In值等于Fin(R,S)，R為父區(qū)域，所有Fin在前一環(huán)節(jié)已構(gòu)造好
3. 結(jié)果：對(duì)同一數(shù)據(jù)流問題比如到達(dá)定值，兩種算法求得的數(shù)據(jù)流值是一樣的。為什么區(qū)域分析算法是正確的？因?yàn)樗鼘?shí)際是按照程序控制流來構(gòu)造傳遞函數(shù)的，包含了所有可能執(zhí)行路徑數(shù)據(jù)流值傳遞的效果，這相當(dāng)于迭代算法求不動(dòng)解的過程，所以最后只要一個(gè)流圖的入口值，就能算出各區(qū)域的入口值。為什么迭代算法是收斂的？因?yàn)榘敫袷菃握{(diào)的且高度有窮。收斂速度取決于遍歷基本塊的順序，如果按基本塊深度優(yōu)先排序（逆后序）遍歷，那么迭代輪數(shù)不超過流圖的深度（各條無環(huán)路徑后退邊的最大數(shù)）加2
4. 區(qū)別：迭代算法用于可歸約流圖和不可歸約流圖，區(qū)域分析算法僅能用于可歸約流圖
posted on 2023-09-06 23:18
春秋十二月 閱讀(106)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Compiler