复制传播 | Codeboy's Blog

形式陈述

要传播的是当时的等值事实

固定单过程局部标量 IR，复制不产生可观察事件，变量没有通过地址被外部修改。所有使用都有定义，指令按顺序读取右侧再写左侧。输出观察包括返回值和控制选择；本页不改写存储别名、volatile、寄存器约定或调试变量。

执行 y:=x 后记录有向复制对 $(y,x)$ ，含义是在当前位置 y 与 x 同值，因此读取 y 可以改读 x。箭头只是替换方向；它不意味着运行时建立引用。之后只要 y 或 x 任一端被赋值，该事实就删除。

例如 x 初值1，执行 y:=x; x:=9; return y 必须返回1。错误地把最后的 y 换成 x 会返回9。只在目标 y 被覆盖时删事实、却忘记来源 x 的重定义，是最常见的错误之一。

可用复制对的方程

候选全集 C 收集本过程实际出现的非自复制 $(y,x)$ ，两端都是变量。常量传播另用数值域处理，不在本页伪装成名为“3”的变量。对赋值 v:=e：

KILL_v=\{(y,x)\in C:v=y\text{ 或 }v=x\},

先删 KILL，再在当前语句是 v:=x 且 $v\ne x$ 时生成 $(v,x)$ 。v:=v 不产生新关系；它也可保守地删掉旧相关事实，尽管更精细的实现可以证明这次自复制不改值而保留它们。

合流用交集，因为替换必须对所有到达路径都成立。人工入口事实为空，其他可达块从 C 初始化，经前向 must 求解逐步收紧。基本块按语句顺序组合转移，不把其中全部复制无序保留。

替换一条语句时先看它的 IN 事实，只改右侧和分支、返回的读取，不改赋值左侧。一个简单实现每个操作数只替换一步，并按原始指令更新事实；这样证明最直接，也不会因循环的名字替换链而在编译器里无限循环。下载实现只变换入口可达块，不可达块原样保留；分析集合仅为可达块分配，因此改写也必须遍历同一可达集合。删除不可达块是另一个明确的步骤。若进一步沿链追到代表元，需要检测环并证明链上每一条同时成立。

直觉

y:=x; return y 可以写成 y:=x; return x。但在中间插入 x:=9 就不一定可以：y 保存的是复制那一刻的旧 x。复制传播把一次读取换成另一个名字，前提是在这次读取发生时，两者仍被证明相等。它不会使 y 从此自动跟着 x 变化。

例子与边界

两条分支怎样给出同一替换

先用公共子表达式消除得到下面的 OPT-8 中间代码：

text

E: x := a+b
   y := x
   if p goto T else F
T: u := x
   goto J
F: u := x
   goto J
J: z := x
   dead := z+1
   r := u+y
   return r

E 出口有 {(y,x)}。T 与 F 的出口都加入同一个 (u,x)，所以 J 入口为 {(y,x),(u,x)}。虽然 u 的赋值有两个不同身份，它们建立的是同一个数值关系。

J.1 执行后又有 (z,x)。因此 J.2 的 z 可改成 x，J.3 的两个输入可同时改成 x，得到 dead:=x+1; r:=x+x。x 从 E 到这里没有被覆盖，所以替换成立。y、u、z 的复制此时仍保留；是否删除它们由死代码消除另做。

上方显示y等于x、左右分支都建立u等于x，汇合交集保留两对；下方显示改写x会同时使两对失效 — 复制事实对两端写入都敏感

若 F 改为 u:=0，该路没有 (u,x)，交集便只剩 (y,x)。J.3 可以把 y 换成 x，却不能把 u 换成 x。不能因为 T 路提供了关系就忽略 F。

推论与应用

可靠性是不变关系的保持

对任意到达当前点的具体执行，证明分析集合里的每一对 $(y,x)$ 都满足 $\rho(y)=\rho(x)$ 。入口集合为空，性质直接成立。复制生成时，右侧值被原样写入目标，所以新对成立；赋值杀掉所有包含被写变量的旧对，其余对两端都没变，继续成立。汇合的交集保证从哪条前驱到来都拥有这项关系。

把一个读取 y 换成同值 x，不改变该原语的输入；确定性原语因此产生同一结果。对整个运行逐步归纳，分支读取也不变，所以经过同样的块并返回同值。替换时不能从“当前分析预计将来相等”倒用一项尚未建立的事实；必须使用语句之前的集合。

这份证明同样说明它为何保守：若两条路分别执行 u:=x 与 u:=x+0，本分析只在第一路生成复制对，于是不会传播 u，尽管数学整数下两者确实相等。更强的值编号或关系分析能发现它；保守性不是实现错误。

成本与边界

候选对有 Q 项，每个块事实至多删除 Q 次。位集求解可以预计算每个被写变量要杀掉的对。设 N 个块、M 条边、最大入度 Δ，朴素“每次重扫全部前驱”的工作队列上界为 $O((N+MQ)(\Delta+1)(1+\lceil Q/w\rceil))$ 个字操作，另计语句扫描和候选构造；保存边界集需 $O(N(1+\lceil Q/w\rceil))$ 个字。Q=0时依然需要扫描图与队列，因子中的1保留这部分工作。更高效的增量合流需要额外数据结构，不能由“用队列”自动得到。

在 SSA 中，变量没有重新定义，许多复制能沿唯一的定义—使用链直接消除；仍须保持支配和 φ 的前驱槽位含义。现有SSA 构造与消解已经给出回边上的复制传播，本页的贡献是没有 SSA 保证时的全路径条件。

迁移任务：在 T 的 u:=x 后增加 x:=9，F 不变。J 入口的 (y,x) 与 (u,x) 都应消失，因为 T 路改写了右端。取 a=2、b=3、p=true，y和u仍为5，r应为10；错误传播会算出18。再把新增语句改为 q:=9，两对均保留，说明 KILL 应围绕实际写变量，而不是“见到赋值就全部清空”。

参考资料

Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., 2007，§9.1 的全局优化、§9.2 的数据流分析。本文使用显式可用复制对实现一个保守版本。
Steven S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997，§12.5 “Copy Propagation”。复制传播、失效条件与后续优化的教材背景。

形式陈述 ​

要传播的是当时的等值事实 ​

可用复制对的方程 ​

两条分支怎样给出同一替换 ​

可靠性是不变关系的保持 ​