08|IDE:从事实是否存在,到事实携带什么值
IDE(Interprocedural Distributive Environments)在 IFDS 的事实关系上附加值变换,用环境记录各事实的抽象值。
1. 让事实携带值
下面使用数学整数的伪代码,不涉及机器整数溢出:
calc(p):
a = p + 2
b = a * 5
return b
u = calc(1) // 调用 A
v = calc(4) // 调用 B两次调用分别得到 u=15、v=30。calc 的计算过程相同,可以先汇总为一个变换,再分别代入实参。
在方法内部选择有限事实域 D={p,a,b,ret}。环境 ρ:D→L 将每个事实映射到抽象值;例如 ρ(p)=1。L 包含 ⊥、每个整数常量及 ⊤,沿用 ⊥ ⊑ c ⊑ ⊤ 的顺序。
IDE 要求环境变换对合并满足分配律,并满足收敛条件(跳转函数不能无限次变化,第 4 节说明);边函数要支持有效的求值、组合、合并和等价判定。以适当的两元素值编码事实的存在性,可以将 IFDS 表示为 IDE 的特例。IDE 原始论文及作者摘要
2. 事实依赖与边函数
每条事实边上的值变换叫边函数(edge function),描述沿这条边传播时值怎样变化:
| 语句 | 事实依赖 | 边函数 | 输入为 1 时的过程 |
|---|---|---|---|
a=p+2 | p→a | f(t)=t+2 | a=3 |
b=a*5 | a→b | g(t)=5t | b=15 |
return b | b→ret | id(t)=t | 返回 15 |
表中省略了其他未修改事实的恒等边。赋值覆盖左侧旧值,因此要删除左侧的旧值边。
p→a 表示 a 依赖 p,f(t)=t+2 则计算值的变化。也可写成 λt.t+2,读作“将 t 映射到 t 加二的函数”;小写 λ 是匿名函数记号,大写 Λ 则是 IFDS 的辅助事实。
实线表示单步依赖及值变换,虚线汇总了整段计算。
3. 底值、未知值与常量生成
将算术函数扩展到未知与底值,规则如下:
| 函数 | 输入 ⊥ | 输入常量 c | 输入 ⊤ |
|---|---|---|---|
| 恒等 | ⊥ | c | ⊤ |
| 加 2 | ⊥ | c+2 | ⊤ |
| 乘 5 | ⊥ | 5c | ⊤ |
| 常量产生 k | ⊥ | k | k |
底值表示没有有效贡献。常量赋值 a=1 从辅助事实 Λ 向 a 生成值;为此,Λ 携带固定的非底占位值 ★,常量产生函数将它映射到 k。★ 不代表程序常量,沿辅助恒等边保持不变。
“加 2”和数学整数上的“乘 5”都保持不同常量不同,因此对单常量域的 Join 分配:两个不同常量先合成未知,或分别变换再合成未知,结果一致。
截断除法可能把两个不同常量映射到同一个常量,Java 的有限位宽也会改变某些运算的性质。因此,每种抽象变换都需要检查 IDE 的条件;无法精确表示的操作可采用满足条件的保守近似。
4. 同一路径组合,多条路径合并
顺序执行:函数组合
先 f 后 g,写作 g∘f,读作“g 复合 f”:
j(t) = g(f(t)) = 5(t+2)
j(1) = 15
j(4) = 30组合顺序很重要。f(g(t))=5t+2 是先乘五后加二,已经换成另一段程序。
分支汇合:逐点合并
如果另一条路径先加 4 再乘 5,那么有 j₁(t)=5(t+2)、j₂(t)=5(t+4)。汇总函数定义为:
(j₁ ⊔ j₂)(t) = j₁(t) ⊔ j₂(t)代入 t=1,两个结果为 15、25,合并为未知。两条路径若都算出 15,就保留 15。
函数表示必须对组合与逐点合并封闭、能判等,并保证更新收敛;仅有值格的有限高度还不够。本例的线性函数组合后仍可用系数表示,但合并未必如此:t+2 与 2t 在 t=2 时都为 4,其他整数输入上结果不同,合并应保留这个交点,不能直接当作处处未知。
线性常量传播(linear constant propagation)因此需要比两个线性系数更完整的函数表示。原论文采用额外分量表示合并后的函数,求值、组合与合并都有相应规则,见原论文及作者后续论文第 11 页。直接取顶函数是额外的保守近似,会丢掉交点处的常量;下文按精确组合与合并推演。
5. 从边函数到跳转函数
跳转函数(jump function)汇总过程入口到某个目标事实的值变换:沿路径组合边函数,再合并多条路径。它相当于第 07 篇的路径边附带一个函数,描述“从入口到这里,值怎样变化”。
写成四元组 〈d₁,n,d₂,j〉:
- d₁:该过程入口的源事实。
- n:目标程序点,决定所属过程。
- d₂:目标事实。
- j:入口值到目标值的汇总函数。
对 calc,得到:
| 目标位置 | 跳转函数条目 | 含义 |
|---|---|---|
| 加法之后 | 〈p,n₁,a,t↦t+2〉 | 入口 p 到 a |
| 乘法之后 | 〈p,n₂,b,t↦5(t+2)〉 | 入口 p 到 b |
| 方法出口 | 〈p,exit,ret,t↦5(t+2)〉 | 入口 p 到返回值 |
出口处的汇总组成过程摘要。A、B 分别把 1、4 代入同一个摘要,就能保留各自的返回值。
6. 两阶段求解:先汇总函数,再代入值
经典 IDE 先汇总函数,再从种子初值求值,算法见原论文。保留输入输出关系,就能避免先将 calc 的两个实参合为 1⊔4=⊤ 后丢失区别。
阶段一:传播与汇总函数
- 在过程入口的同一事实上建立恒等跳转函数。
- 遇到普通边,按执行顺序组合当前跳转函数和边函数。
- 多条路径到同一条目时逐点合并;条目改变才继续调度。
- 到达出口,生成或更新摘要,并应用到匹配的调用返回位置。
- 与 IFDS 一样,处理“调用先到”和“摘要先到”两种时序,直到函数条目稳定。
调用流边 Λ→p 上的 k₁、k₄ 分别从非底输入产生常量 1、4。沿用上一节的四元组与位置编号,id 为恒等函数;省略 calc 的 〈Λ,entry,Λ,id〉 等辅助恒等条目,按第 07 篇的调度方式推演:
| 步骤 | 当前任务 | 新条目 | 本次计算 / 后续动作 |
|---|---|---|---|
| 1 | 从种子出发 | 〈Λ, main入口, Λ, id〉 | 沿 main 的普通边到达 A |
| 2 | A 调用 calc(1) | 被调入口 〈p, entry, p, id〉;登记 Incoming(calc,p) ← A,附 k₁ | 调度 calc 入口;旁路保留 Λ |
| 3 | a=p+2 | 〈p, n₁, a, t↦t+2〉 | 组合 id 与边函数 |
| 4 | b=a*5 | 〈p, n₂, b, t↦5(t+2)〉 | 组合上一条与 t↦5t |
| 5 | return b 到达出口 | 〈p, exit, ret, t↦5(t+2)〉,记为摘要 j | 查 Incoming,把 j 应用到 A |
| 6 | 应用摘要到 A | 〈Λ, retA, u, j∘k₁〉,即 t↦15 | 继续 main,到达 B |
| 7 | B 调用 calc(4) | 〈p, entry, p, id〉 已存在,不再传播;Incoming(calc,p) 追加 B,附 k₄ | 摘要 j 已有,直接应用 |
| 8 | 应用摘要到 B | 〈Λ, retB, v, j∘k₄〉,即 t↦30 | main 到达出口,队列为空 |
第 7 步直接复用 j,calc 无需重算。若其他调度下 B 先于摘要到达,则先登记等待、摘要生成后再应用,最终条目相同。
阶段二:传播入口值并求值
从种子的初值出发,利用已稳定的调用关系与跳转函数求出过程入口值,再对所需条目求值。
| 查询 | 计算 | 结果 |
|---|---|---|
| A 返回后的 u | j(k₁(★)) | 15 |
| B 返回后的 v | j(k₄(★)) | 30 |
| calc 内部 p 的跨调用汇总 | 1 ⊔ 4 | ⊤ |
calc 内部 p 的跨调用汇总为未知,但调用者仍通过各自的实参与摘要得到 15、30。
7. 普通常量传播的分配性限制
第 05 篇的两条路径分别为 (x,y)=(2,3)、(3,2)。执行 z=x+y:
- 各自执行再合并:
5⊔5=5。 - 先逐变量合并再执行:
⊤+⊤=⊤。
结果不等,环境变换不满足分配律,不能直接拆成单事实值传播。calc 则只使用常量、复制和满足条件的一元线性变换。
本篇要点
- 边函数描述一步值变换,跳转函数汇总入口到目标事实的变换。
- 沿路径组合、路径间逐点合并;函数表示须封闭、可判等并保证收敛。
- 先汇总函数再求值,本例同一个摘要得到 u=15、v=30。
- 普通
z=x+y的环境变换不满足分配律;每类运算都须检查 IDE 的适用条件。
后续分为两个专题:第 09 篇用路径条件排除不可行路径,第 10 篇讨论跳转函数的存储与回收。
