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