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