05|常量传播:计算变量的值与精度损失
沿控制流传播数值信息,可以判断到达某条语句时,变量是否总是同一个常量。
1. 传播、折叠有什么区别?
int a = 3;
int b = a + 4;
use(b);| 名称 | 在例子中做什么 |
|---|---|
| 常量传播(constant propagation) | 沿控制流确定使用 a 时它仍为 3,进而算出 b=7;求值 a+4 是传播规则里的一步 |
| 常量折叠(constant folding) | 把已经确定的常量表达式替换成结果,如将 3+4 改写成 7 |
编译器语境下,“常量传播”也指将变量的使用替换为常量,进而为折叠创造机会。本系列只用它指计算常量状态的分析,不改写程序。
2. 单常量域与环境
使用单常量域:一个变量只能记录一个确定常量,或“未知常量”。数学记号是:
L = {⊥} ∪ {所有整数常量} ∪ {⊤}
⊥ ⊑ c ⊑ ⊤c:一个确定整数,例如 3。⊤:可能不止一个值,无法用单个常量概括;这里简称未知。⊥:尚无路径贡献的底值,不是源程序中未初始化的变量。
⊑ 沿用第 03 篇的读法“不比……更粗”。不同常量互不可比。这种“底、一层互不可比的元素、顶”三层结构在文献中叫平坦格(flat lattice),常量传播用它时也称 constant propagation lattice:
连线表示按 ⊑ 相邻的可比较元素,向上更粗,与第 03 篇的格图约定相同。图中只画出几个常量,省略号代表其余整数。
将全部变量映射到这些值,就得到环境(environment),例如 ρ={a↦3,b↦7};ρ 读作 rho,↦ 表示映射到。环境为每个变量记一个值,无法确定时记 ⊤。
整个节点不可达时记为 UNREACHABLE,跳过转移;逐变量合并中,尚未计算的贡献记为 ⊥。例如循环头先收到入口的 i=0,回边尚无贡献,合并为 0⊔⊥=0。可达入口的未知参数设为 ⊤,示例局部变量均先赋值再读取。
3. 合并两份环境
继续沿用第 03 篇向上更粗的顺序。每个变量分别合并,⊔ 读作 Join:
| 左值 | 右值 | Join ⊔ | 原因 |
|---|---|---|---|
⊥ | 3 | 3 | 尚无贡献不改变已有结果 |
| 3 | 3 | 3 | 两边一致 |
| 3 | 5 | ⊤ | 一个常量装不下两个值 |
| 3 | ⊤ | ⊤ | 另一边已无法确定 |
不可达分支不贡献环境。这里的域虽然含无限多个数学整数,但最长严格上升链只有 ⊥ → c → ⊤ 三个元素(按第 04 篇引用教材的定义,高度为 2);n 个变量的环境逐变量排序,最长链也只有 2n 步。元素无限不等于高度无限。
int a;
if (flag) a = 3;
else a = 3;
int b = a + 4;两边都贡献 a=3,汇合仍为 3,所以 b=7。若 else 改为 a=5,a 的实际取值有 3 和 5 两种,单常量域只能用 ⊤ 概括,b 也随之成为 ⊤。
单常量传播与逐变量合并的标准框架可对照 Static Program Analysis 第 5.2 节。
4. 循环为什么会把常量变成未知?
int i = 0;
while (again()) {
i = i + 1;
}
use(i);把 again() 视为未知条件,允许零次或多次循环,忽略其副作用。采用普通常量传播,不用条件约束筛选路径。
| 轮次 | 循环头输入 | 循环体输出 | 合并入口 i=0 后 |
|---|---|---|---|
| 首次 | 0 | 1 | 0 ⊔ 1 = ⊤ |
| 重算 | ⊤ | ⊤ | 0 ⊔ ⊤ = ⊤ |
第二轮后结果稳定为未知,因为退出时的 i 随循环次数变化。
若把循环体改为 i=0,回边仍贡献 0,循环头与出口都保持 0。是否能证明循环终止,是另一个分析问题。
5. 为什么合并后 x、y 都未知,z 却本可确定?
int x, y;
if (flag) { x = 2; y = 3; }
else { x = 3; y = 2; }
int z = x + y;两条真实路径上 z 都等于 5。逐变量合并却得到:
{x↦2,y↦3} ⊔ {x↦3,y↦2} = {x↦⊤,y↦⊤}
再计算 x+y,得到 z↦⊤。原因是独立保存 x、y 的域丢掉了“它们相加为 5”的关联,容许了原来不存在的组合。可以换用能记录变量间关系的域(关系域,如线性等式),或者像第 09 篇那样分别沿路径分析,但状态和计算都会更复杂。
这里先合并再执行,与分别执行再合并的结果不同。这个差别涉及分配律,也是第 07—08 篇判断分析能否使用 IFDS/IDE 的依据。
若将 z=x+y 移入两个分支、在汇合前计算,就能保留 5⊔5=5:此时变量间的关联尚未丢失。
6. 接入工作列表求解器
第 04 篇的队列、变化检测和后继调度仍然可用,需要替换的是状态与规则:
- 状态由污点集合换成环境,合并按变量逐项执行。
- 可达的
x=c覆盖 x 的旧值,记录 c。 x=y复制 y 的抽象值。x=y+z先检查是否有⊥,有则结果为⊥;否则有⊤时结果为⊤,两者均为常量时求和。- 某节点输出改变后,重新计算受影响的后继,直到队列为空。
实现 Java 分析时,常量运算要遵循 Java 的整数位宽、溢出和异常语义。前面的循环即使发生整数溢出,i 仍有多个可能值,分析结果依然是 ⊤。
本篇要点
- 常量传播用环境记录各变量的常量、未知
⊤或尚无贡献⊥,可复用工作列表框架。 - 平坦格元素无限、高度有限;
3⊔3=3,3⊔5=⊤。 - 逐变量合并会丢失关联,导致先合并再计算与先计算再合并不同;
x+y恒为 5 的例子说明了这一限制。
将计算封装成方法后,还需要传递实参与返回值。
