如何实现编译器copy propagation（复制传播）及GCSE、CProp算法？

一、复制传播（Copy Propagation）正确实现 #

现有实现的核心缺陷 #

你的代码目前存在几个底层逻辑问题，导致无法覆盖复杂测试用例：

• 纯字符串匹配的替换逻辑没有做变量边界校验，会误替换包含目标变量名的其他变量（比如替换a的时候会误改aa、a1这类变量名）
• 没有处理变量重定义的覆盖场景，只要后续代码出现目标变量就直接替换，忽略了中间变量被重新赋值的情况
• 没有控制流感知能力，仅支持线性顺序的代码，遇到分支、循环等控制流结构完全失效
• 没有做到达定义分析，无法判断某个复制定义是否真的能到达变量的使用位置

正确实现步骤 #

1. 前置处理：将输入代码转换为三地址码（TAC）或者静态单赋值（SSA）形式，先做语法解析，避免纯字符串处理的各种边界错误
2. 合法复制识别：遍历所有基本块，筛选出符合要求的复制指令：必须是x = y形式，y为单一变量或常量、无副作用，x无特殊修饰符（如volatile）
3. 数据流分析：构建use-def/def-use链，同时执行到达定义分析，判断某条复制指令的定义是否能到达x的使用点，且中间x、y都没有被重定义
4. 安全替换：仅对符合上述条件的使用点执行替换，替换完成后配合死代码删除，清理无效的复制指令

现有代码快速优化建议 #

如果不想重构整体结构，可以先做几个小修改提升正确性：

• 替换strstr匹配变量的逻辑，改为拆分每一行的所有操作数，只匹配完全相等的独立变量
• 每次遇到变量的重定义时，清空该变量之前的use-def记录，避免传播过期的定义
• 对变量名前后做边界校验，比如匹配变量的时候确认前后是运算符、空格、等号等分隔符，避免子串误替换

二、全局公共子表达式消除（GCSE）算法原理 #

GCSE的核心目标是消除跨多个控制流路径的重复表达式计算，减少运行时冗余计算，执行流程如下：

• 前置准备：完成代码的SSA转换、基本块划分、可达性分析
• 局部优化前置：先执行局部公共子表达式消除（LCSE），清理每个基本块内部的重复计算
• 可用表达式分析：迭代执行数据流分析，计算每个程序点上哪些表达式已经被计算过，且表达式的所有操作数在此之后都没有被修改
• 冗余表达式替换：遍历所有表达式计算节点，如果该表达式在当前点是可用的，就将本次计算替换为之前存储的表达式结果
• 控制流适配：如果是SSA形式，需要插入phi节点合并不同控制流路径上的表达式结果

优化示例：

// 优化前
if (a > 10) {
    t1 = x * y + 2;
    b = t1 + 5;
} else {
    t2 = x * y + 2;
    c = t2 * 3;
}
// GCSE优化后
t = x * y + 2;
if (a > 10) {
    b = t + 5;
} else {
    c = t * 3;
}

三、CProp（常量传播）算法原理 #

CProp的作用是将编译期可确定为常量的变量直接替换为常量值，配合常量折叠可以大幅减少运行时计算，工业界常用的是稀疏条件常量传播（SCCP）版本，执行流程如下：

1. 初始化所有变量的取值状态为未知（UNDEF），如果变量初始赋值为常量则标记为对应常量值
2. 迭代传播常量值：遍历所有指令，如果指令的所有操作数都是常量，就计算出指令结果，将目标变量标记为对应常量
3. 控制流剪枝：如果分支判断的条件是常量，直接标记不可达分支，不再处理该分支内的代码
4. 变量替换：遍历所有变量的使用点，如果该变量在当前点的取值是确定的常量，直接替换为常量值，后续执行常量折叠进一步优化

内容的提问来源于stack exchange，提问作者Grace Mathew