1. 迭代算法在什么情況下是正確的
數據流值滿足半格的定義，以及數據流方程中的傳遞函數滿足單調性
2. 迭代算法在什么情況下必定收斂
在滿足正確性的前提下，當數據流值對應的半格高度有限時，必定收斂。以最小元為初值的迭代收斂于最小不動點，以最大元為初值的迭代收斂于最大不動點
3. IDEAL、MOP、MFP三種解的意義與關系
IDEAL是理想解即最精確的解，它將程序入口entry到某點p所有可達路徑（可執行路徑）的尾端的數據流值做聚合操作，區分來自不同路徑的數據流值，若聚合操作是交運算，則最大下界為其值，任何大于IDEAL的解都是錯誤的，而小于IDEAL的解是保守的；若聚合操作是并運算，則最小上界為其值，任何小于IDEAL的解都是錯誤的，而大于IDEAL的解是保守的。MOP是全路徑聚合解，它將entry到p所有流圖路徑（不一定可執行）的尾端的數據流值做聚合操作，區分來自不同路徑的數據流值，若包含了不可執行路徑，則會丟失精確性，否則等于IDEAL；MFP是基于數據流方程與迭代算法求得的最大或最小不動點解，它在每個控制流圖的匯合節點做聚合操作而非路徑尾端，不區分來自不同路徑的數據流值，若傳遞函數不滿足分配律，則會丟失精確性，否則等于MOP。故精確性關系為MFP<=MOP<=IDEAL，可知MFP解是安全的，基于MFP作的優化是正確的
4. 為什么不采用IDEAL和MOP解
因為一般程序路徑數可能無限，所以沒有求MOP的有效算法，且不可達路徑是一個不可判定問題，所以沒有求IDEAL的有效算法
posted on 2023-09-06 22:53
春秋十二月 閱讀(69)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler