Enna1/LLVM-Study-Notes 项目中的 SSA 构造算法详解

引言

静态单赋值形式(Static Single Assignment, SSA)是编译器优化中一种重要的中间表示形式。本文将深入解析 Enna1/LLVM-Study-Notes 项目中关于 SSA 构造算法的内容，帮助读者理解 SSA 的核心概念和构建过程。

SSA 构造概述

SSA 构造算法通常分为两个主要阶段：

1. 插入 Φ 函数：在控制流合并点插入必要的 Φ 函数
2. 变量重命名：为变量赋予唯一的版本号

在深入算法细节前，我们需要掌握几个关键概念。

基础概念

支配关系(Dominator)

• 支配(N dom M)：在控制流图中，从入口节点到 M 的所有路径都必须经过 N
• 真支配(N sdom M)：N dom M 且 N ≠ M
• 直接支配(N idom M)：N dom M 且不存在中间节点 N' 使得 N dom N' 且 N' dom M

支配树(Dominator Tree)

支配树是一种树形结构，其中：

• 父节点是其子节点的直接支配节点
• 根节点是控制流图的入口节点

支配边界(Dominance Frontier)

对于节点 N，其支配边界 DF(N) 是满足以下条件的节点集合：

1. N 支配 W 的至少一个前驱节点
2. N 不严格支配 W

数学表达式为：DF(N) = { W | N dom pred(W) AND !(N sdom W) }

迭代支配边界(Iterated Dominance Frontier)

DF+(S) 表示集合 S 的迭代支配边界，通过不断计算 DF 直到达到不动点：

1. DF₁(S) = DF(S)
2. DF₂(S) = DF(S ∪ DF₁(S))
3. 重复直到 DFₙ(S) = DFₙ₊₁(S)

SSA 构造算法详解

第一阶段：插入 Φ 函数

算法伪代码如下：

for each variable a:
    defsites[a] = { blocks where a is defined }
    for each block b in defsites[a]:
        for each block d in DF(b):
            if d has no Φ-function for a:
                insert Φ-function for a in d
                add d to defsites[a]

这个算法实际上是在动态计算迭代支配边界。它首先计算 DF(defsites)，然后将不在 defsites 中的节点加入，再计算新的 DF，直到没有新节点加入。

第二阶段：变量重命名

重命名算法采用递归方式处理基本块：

rename(B):
    for each instruction I in B:
        if I is a Φ-function:
            replace its operands with current stack values
        replace uses of variables with current stack values
        if I defines a variable:
            push new version onto stack
            replace definition with new version
    
    for each successor S of B:
        for each Φ-function in S:
            set operand corresponding to B to current stack value
    
    for each child C of B in dominator tree:
        rename(C)
    
    pop stack for each definition in B

算法从入口块开始调用 rename(entry)，通过深度优先遍历支配树来完成变量重命名。

实例分析

普通形式 IR

考虑以下控制流图：

A: x = 1
   if cond goto B else goto C
B: x = 2
   goto D
C: x = 3
   goto D
D: y = x + 1

SSA 形式 IR

转换为 SSA 形式后：

A: x1 = 1
   if cond goto B else goto C
B: x2 = 2
   goto D
C: x3 = 3
   goto D
D: x4 = Φ(x2, x3)
   y1 = x4 + 1

可以看到在合并点 D 处插入了 Φ 函数，并为每个定义赋予了唯一版本号。

LLVM 中的实现

LLVM 中实现了迭代支配边界计算的核心类 IDFCalculator，主要功能包括：

1. 构造函数：初始化支配树和活跃块标记
2. 设置定义块：setDefiningBlocks() 设置变量定义的基本块集合
3. 设置活跃块：setLiveInBlocks() 可选设置变量活跃的基本块集合
4. 计算函数：calculate() 执行实际的迭代支配边界计算

计算过程使用优先队列，按照支配树层级和 DFS 编号排序，确保从叶子节点向上处理，这与理论算法中的后序遍历方式一致。

总结

SSA 形式为编译器优化提供了便利，其构造过程虽然复杂但有章可循。理解支配关系和支配边界是掌握 SSA 构造的关键。LLVM 的实现将理论算法与实际工程相结合，通过优先队列等数据结构高效实现了迭代支配边界计算。

通过本文的解析，希望读者能够深入理解 SSA 构造的原理和实现细节，为进一步学习编译器优化打下坚实基础。