mem2reg 是什么mem2regMemory to Register Promotion 是编译器里最基础、收益最大的一类优化把存在内存里的局部变量提升成 SSA 寄存器值。为什么需要它写代码时局部变量通常先分配在栈上intfoo(intx,inty){inta;// 栈上分配if(x0){a1;// 写内存}else{a2;// 写内存}returnay;// 读内存}对应的 LLVM IR未优化define i32 foo(i32 %x, i32 %y) { entry: %a alloca i32 ; 在栈上分配 4 字节 %cmp icmp sgt i32 %x, 0 br i1 %cmp, label %then, label %else then: store i32 1, ptr %a ; 写内存 br label %merge else: store i32 2, ptr %a ; 写内存 br label %merge merge: %a_val load i32, ptr %a ; 读内存 %result add i32 %a_val, %y ret i32 %result }问题alloca、store、load 都是内存操作每次读写都要访问栈慢且妨碍后续优化。mem2reg 之后define i32 foo(i32 %x, i32 %y) { entry: %cmp icmp sgt i32 %x, 0 br i1 %cmp, label %then, label %else then: br label %merge else: br label %merge merge: %a_val phi i32 [ 1, %then ], [ 2, %else ] ; 直接用 SSA 值 %result add i32 %a_val, %y ret i32 %result }alloca、store、load 全部消失a 变成了 SSA 值 %a_val。1.2 哪些变量可以被提升不是所有alloca都能提升。必须满足条件说明局部只在当前函数内使用不逃逸非别名没有被取地址传给别的函数标量不是数组、结构体等聚合类型只被 load/store 直接访问没有getelementptr等复杂寻址LLVM 的mem2regpass 会自动检查这些条件。mem2reg 的核心步骤放置 Phi 重命名是的mem2reg 的本质就是两步① 放置 Phi 节点Place Phi Nodes ② 重命名Rename这两步合起来就是 SSA 构造算法Cytron et al. 1991。第一步放置 Phi 节点当控制流汇合时比如 if-else 的 merge 点来自不同路径的变量值需要合并。SSA 要求每个值只定义一次所以需要在汇合点插入phi指令来“选择”来自哪条路径的值。怎么决定在哪里插 phi答案是支配边界Dominance Frontier, DF。块 B 的支配边界 DF(B)那些“不被 B 严格支配但至少有一个前驱被 B 支配”的块。直观理解DF(B) 是“B 的定义第一次需要和其他路径合并”的地方。算法对每个变量 a 1. 找到 a 的所有定义点store 指令所在的块 2. 计算这些定义点的迭代支配边界 DF 3. 在 DF 中的每个块插入 phi 节点迭代支配边界 DF因为插入 phi 节点本身也算一个新的定义可能又产生新的支配边界所以要迭代直到不动点。第二步重命名Rename插入 phi 节点后还需要把每个load替换成对应的 SSA 值并给 phi 节点填上正确的操作数。算法在支配树上做 DFS维护一个栈记录每个变量当前的定义SSA 值 从入口块开始沿支配树 DFS 遇到 store a v 把 v 压入 a 的栈 遇到 load a 用 a 的栈顶替换 遇到 phi a phi(...) 把 phi 结果压入 a 的栈 处理完当前块递归处理支配树上的子块 回溯时弹出当前块压入的所有值后支配边界、控制依赖、控制流依赖的作用标准 mem2reg 用的是支配边界不是后支配边界Cytron 的经典 SSA 构造算法也就是 mem2reg 的核心用的是支配边界Dominance Frontier, DF不是后支配边界。概念方向用途支配边界 DF从入口往前看放置 phi 节点后支配边界 PDF从出口往后看控制依赖分析、剪枝 SSA后支配边界Post-Dominance Frontier, PDF后支配如果从块 B 到出口的每条路径都经过块 C则 C 后支配 B。后支配边界 PDF(B)那些“不被 B 严格后支配但至少有一个后继被 B 后支配”的块。用途控制依赖分析块 Y 控制依赖于块 X当且仅当 Y 在 X 的后支配边界上。剪枝 SSAPruned SSA标准 SSA 在 DF 上插 phi可能插入“死的” phi变量在那个点已经不再被使用。用后支配信息可以剪掉这些死 phi。半剪枝 SSASemi-Pruned SSA用变量的活跃性liveness来剪枝比完全剪枝更简单。控制依赖Control Dependence定义块 Y 控制依赖于块 X如果Y 后支配 X 的某个后继但不后支配 X 本身。直观理解X 是一个分支点Y 只在 X 的某条分支上执行那么 Y 控制依赖于 X。在 mem2reg 中的作用标准 mem2reg 不直接使用控制依赖。但在剪枝 SSA中控制依赖可以帮助判断“某个 phi 节点是否真的需要”。在死代码消除、指令调度中控制依赖是核心分析。控制流依赖Control Flow Dependence这是一个更宽泛的术语指“一个块的执行与否依赖于另一个块的控制流决策”。控制依赖是控制流依赖的一种形式化。在 mem2reg 中控制流依赖决定了“哪些路径会到达汇合点”从而决定 phi 节点的操作数。总结三者在 mem2reg 中的关系标准 mem2regCytron 算法 支配边界 DF → 放置 phi 节点 支配树 DFS → 重命名 后支配边界 PDF / 控制依赖 不直接参与标准 mem2reg 用于 - 剪枝 SSA去掉死 phi - 控制依赖分析后续优化 - 死代码消除 控制流依赖 决定 phi 节点的操作数来自哪条路径 是控制依赖的广义说法详细例子从 alloca 到 phi原始 C 代码intfoo(intx,inty){inta;if(x0){a1;}else{a2;}returnay;}未优化的 LLVM IRdefine i32 foo(i32 %x, i32 %y) { entry: %a alloca i32 %cmp icmp sgt i32 %x, 0 br i1 %cmp, label %then, label %else then: store i32 1, ptr %a br label %merge else: store i32 2, ptr %a br label %merge merge: %a_val load i32, ptr %a %result add i32 %a_val, %y ret i32 %result }控制流图CFGentry / \ / \ then else \ / \ / merge | exit计算支配树和支配边界支配树entry ├── then │ └── merge └── else └── mergeentry 支配所有块。then 支配 merge不因为从 entry 到 merge 可以走 else 路径不经过 then。else 支配 merge同理不支配。支配边界DF(then) {merge}merge 不被 then 严格支配但 merge 的一个前驱then被 then 支配。DF(else) {merge}同理。DF(entry) {}entry 支配所有块。变量 a 的定义点store i32 1, ptr %a在 then 块。store i32 2, ptr %a在 else 块。计算 DFDF({then, else}) DF(then) ∪ DF(else) {merge} ∪ {merge} {merge}在 merge 块插入 phi 节点merge: %a_val phi i32 [ 1, %then ], [ 2, %else ]重命名沿支配树 DFS从 entry 开始 entry没有 a 的定义继续 进入 thenentry 的子块 then遇到 store a 1 把 1 压入 a 的栈 栈a [1] 进入 mergethen 的子块 merge遇到 phi a phi(...) 第一个操作数来自 then对应栈顶的 1 把 phi 结果 %a_val 压入栈 栈a [1, %a_val] 遇到 load a 用栈顶 %a_val 替换 处理完回溯 弹出 %a_val 栈a [1] 弹出 1 栈a [] 进入 elseentry 的子块 else遇到 store a 2 把 2 压入 a 的栈 栈a [2] 进入 mergeelse 的子块 mergephi 已经处理过第二个操作数来自 else对应栈顶的 2 遇到 load a 用栈顶 %a_val 替换 回溯 弹出 2 栈a []最终 SSA 形式define i32 foo(i32 %x, i32 %y) { entry: %cmp icmp sgt i32 %x, 0 br i1 %cmp, label %then, label %else then: br label %merge else: br label %merge merge: %a_val phi i32 [ 1, %then ], [ 2, %else ] %result add i32 %a_val, %y ret i32 %result }后支配边界与控制依赖的作用扩展在上面的例子中标准 mem2reg 只用到了支配边界。但如果我们要做剪枝 SSA就会用到后支配边界。后支配树exit └── merge ├── then └── elsemerge 后支配 then 和 else。exit 后支配所有块。后支配边界PDF(then) {entry}entry 不被 then 严格后支配但 entry 的一个后继then被 then 后支配。PDF(else) {entry}同理。控制依赖then 控制依赖于 entry因为 then 只在 entry 的某条分支上执行。else 控制依赖于 entry。merge 不控制依赖于任何块它在所有路径上都执行。在剪枝 SSA 中如果变量 a 在 merge 之后不再被使用那么 merge 处的 phi 节点是“死的”可以删除。判断“是否死”需要活跃性分析liveness analysis而后支配边界帮助确定控制依赖关系。总结概念作用mem2reg把栈上的局部变量提升为 SSA 寄存器值核心步骤放置 phi 节点 重命名支配边界 DF决定在哪里插 phi 节点迭代支配边界 DF因为插 phi 本身产生新定义需要迭代重命名沿支配树 DFS用栈维护当前定义替换 load后支配边界 PDF不直接参与标准 mem2reg用于剪枝 SSA、控制依赖分析控制依赖块 Y 控制依赖于块 X如果 Y 只在 X 的某条分支上执行控制流依赖控制依赖的广义说法决定 phi 节点的操作数来自哪条路径一句话mem2reg 就是“放置 phi 重命名”用支配边界决定 phi 放哪用支配树 DFS 完成重命名。后支配边界和控制依赖不直接参与标准算法但在剪枝 SSA、死代码消除等后续优化中发挥重要作用。