【输入】
调用图，其顶端是根过程
【输出】
每个过程每个参数的icp值
【算法步骤】
1. 将根过程加入工作表，遍历调用图，构建每个过程的形参集合，初始化每个形参的icp值为未知（icp格的顶元素）
2. 从工作表移出一个过程p，若工作表为空则终止
3. 遍历p的指令序列，对每个调用点遍历被调过程q的形参，对每个形参x，若对应的传入实参是p的一个形参，则计算x的icp值（等于x旧值和传入实参的icp值之交）
4. 若x的icp值比旧值小，则将q加入工作表，转到步骤2继续
【算法分析】
数学基础是icp半格，高度为3，所以必定收敛（因为半格是单调偏序的，icp最多变小2次：未知->常量，常量->非常量）。步骤1复杂度取决于过程数及其参数数量，步骤2～4之外循环次数取决于调用图的深度，内循环取决于调用点数、被调过程的参数数量。该算法是位置无关的，不能处理特定调用点的特定过程之常量传播，另外过程的形参集合不能有交集
【应用】
可以计算出每个过程入口形参对应的常量实参集合，进而可以运用全局常数传播使结果更精确。如果确定了一个过程的哪些参数是常量，那么可以克隆出一个副本，对副本进行优化，比如裁剪调用和起始代码序列，使之不传递常数参数，再运用过程内优化
posted on 2023-09-06 23:02
春秋十二月 阅读(42)
评论(0) 编辑 收藏 引用 所属分类:
Compiler