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