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