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
春秋十二月 阅读(25)
评论(0) 编辑 收藏 引用 所属分类:
Compiler