【输入】
ssa控制流图。结点为一个phi函数或一条运算指令，边包含控制流边和ssa边
【输出】
所有ssa变量的最终LatCell（常量半格值）
【流程】
1. 算法维护两个工作表，一是流图边FlowWL，用于跟踪控制流的执行，二是ssa边SSAWL，用于单赋值变量的传播。还有一个ExecFlag映射，用于确保仅有控制流边导向的运算结点最多执行一次，多次执行是没必要的，因为运算涉及的分量不会变（没有ssa前驱边），ExecFlag(a,b)为true表示边a->b导向的结点b已执行，否则未执行
2. 两种结点的分析：
a) 对于phi结点，不管被哪种边导向，都先计算其LatCell（phi结果与各个phi参数的交），若与旧值不同，则将它的ssa后继边加入SSAWL，若控制流后继边尚未执行即对应ExecFlag为false，则将它的控制流后继边加入FlowWL
b) 对于运算结点，若是控制流边导向且未被执行过（到结点的所有边的ExecFlag为false）或ssa边导向且以前执行过（存在至少一条边的ExecFlag为true），则执行其运算，计算左值变量的LatCell（解释执行整数运算），若与旧值不同，则将ssa后继边加入SSAWL，若LatCell是常量且为条件运算，则将满足条件的Y或N边加入FlowWL，否则将所有控制流后继边加入FlowWL
3. 算法初始时，设置所有控制流边的ExecFlag为false，设置所有ssa变量的LatCell为未知（半格顶元素），将流图入口到第1个结点的边加入FlowWL。然后进行主循环，先从FlowWL移出一条边，若边的ExecFlag为false则设为true，判断尾结点类型，若为phi则转到上述2-a处理，若为运算则转到2-b处理；再从SSAWL移出一条边，若边尾结点为phi类型则转到2-a处理，否则为运算类型转到2-b处理，以上过程直至FlowWL和SSAWL皆为空
【分析】
该算法思想是符号执行，对于运算x=y或x=y+z（这里+泛指对整型有意义的操作），在常量半格中，x、y、z初值为未知，y和z单调降低，导致x也单调降低，它们最多降低2次，故当格值不变后，SSAWL终为空，另外由于ExecFlag的作用导致所有仅控制流边导向的结点最多执行一次，因此FlowWL终为空，算法是收敛的，复杂度取决于控制流边和ssa边的总数
posted on 2023-09-06 23:10
春秋十二月 阅读(22)
评论(0) 编辑 收藏 引用 所属分类:
Compiler