Mem2Reg
大致流程
- 计算支配树
- 概念 如果到达 $y$ 一定要经过 $x$，那么 $x$ 支配 $y$
- 计算支配边界
- 概念 如果 $x$ 不支配 $y$，但 $x$ 支配 $y$ 的至少一个前驱，那么 $y$ 属于 $x$ 的支配边界
- 含义 $x$ 的支配边界是所有 $x$ 「影响但不完全控制」的节点
- 对于所有
store，标记其「所在基本块的支配边界」需要插入 phi
- 对于上面的所有标记，插入空的
phi
- 深度优先遍历所有基本块，维护每个变量的当前值
- 利用当前值填充
phi 的值
- 如果未曾到过本块，遍历所有指令
- 如果是
load，替换为当前值
- 如果是
store，删除并更新当前值
实现细节
- 维护当前值时用
Vec<HashMap<Variable, Operand>> 可以避免拷贝已有数据
- 往数组里面的
store 不可随意删除，可能会有从相同数组的 load
尾递归优化
大致流程
- 遍历所有无返回值的函数
- 收集所有下一步返回的
call，如果无则说明不需进行尾递归优化
- 把所有形参替换成
phi，仅当从函数入口到达时值为形参
- 将各处
call 替换为跳转到 phi 所在块，相应地增加 phi 的参数
实现细节
- 如果函数只有一个
ret，并且在单独的基本块，则可以通过 call 后面是不是直接跳转到无出边的基本块，来判断是不是下一步返回的 call
- 如果 IR 中
phi 不能放在入口，需要从入口跳转到一个新的基本块