反编译器如何将多条SSA形式指令合并为单条语句？

反编译器将多条SSA形式指令合并为简洁语句的核心，是追踪值的依赖链并进行表达式化简——本质是把分散的赋值、运算指令，按照数据流依赖关系重组为等价的复合表达式，就像你给出的数组求平均例子，分步的临时变量赋值会被折叠成一个完整的计算语句。

一、SSA指令合并的核心步骤 #

• 数据流依赖分析：为每条SSA指令建立值的依赖图，比如你例子中res依赖sum和d，sum依赖t1和v3，t1依赖v1和v2，而v1/v2/v3对应数组元素，d是常量3。
• 临时变量消除：结合死代码消除（Dead Code Elimination）和复制传播（Copy Propagation），对只被使用一次的临时变量（如v1、t1、sum），直接将其定义的表达式替换到所有引用它的位置，这是合并的基础。
• 表达式化简与重组：把替换后的表达式转换为抽象语法树，通过常量折叠（如把d=3直接替换为常量）、结合律/交换律优化，将分散的运算重组为符合高级语言语法的紧凑表达式。

二、已有的成熟实现算法 #

• SSA-Based Value Numbering：为每个值分配唯一编号，识别等价表达式，同时追踪值的传递路径，自动替换临时变量为原始表达式，是反编译器处理简单表达式合并的基础算法。
• 表达式树折叠优化：将SSA指令序列转换为抽象语法树（AST），遍历树节点时，将仅作为中间节点的临时变量直接合并到父节点中，最终生成紧凑的复合表达式。
• 全局值编号（Global Value Numbering, GVN）：在整个函数范围内分析值的依赖关系，不仅能合并单基本块内的指令，还能处理跨基本块的等价表达式，适合循环内这类复杂场景的指令合并。

三、针对示例的具体合并过程 #

1. 梳理所有临时变量的依赖链：res = sum / d → sum = t1 + v3 → t1 = v1 + v2 → v1=A[i-1], v2=A[i], v3=A[i+1], d=3。
2. 应用复制传播：将sum替换为t1+v3，t1替换为v1+v2，d替换为3，得到res = (v1+v2 + v3)/3。
3. 替换数组访问变量：将v1/v2/v3替换为对应的数组索引表达式，最终得到B[i] = (A[i-1]+A[i]+A[i+1])/3。
4. 消除未被引用的临时变量（d、v1、t1等），完成语句合并。

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