1
// 非 SSA 形式
2
int foo(int x, int y) {
3
    int a;
4
    if (x > 0) {
5
        a = x + y;    // a 的第一次赋值
6
    } else {
7
        a = x - y;    // a 的第二次赋值
8
    }
9
    return a;         // 使用 a —— 哪个值？
10
}
11

12
// SSA 形式
13
int foo_ssa(int x, int y) {
14
    int a1, a2, a3;
15
    if (x > 0) {
16
        a1 = x + y;
17
    } else {
18
        a2 = x - y;
19
    }
20
    a3 = phi(a1, a2);  // phi 函数：根据控制流选择 a1 或 a2
21
    return a3;
22
}

1
def construct_ssa(cfg):
2
    """从非 SSA 的 CFG 构造 SSA 形式"""
3

4
    # 第一步：计算支配关系
5
    dom_tree = compute_dominators(cfg)
6

7
    # 第二步：计算支配边界
8
    dom_frontier = compute_dominance_frontier(dom_tree)
9

10
    # 第三步：插入 phi 函数
11
    insert_phi_functions(cfg, dom_frontier)
12

13
    # 第四步：重命名变量
14
    rename_variables(cfg, dom_tree)
15

16
    return cfg
17

18
def compute_dominance_frontier(dom_tree):
19
    """计算支配边界：φ 函数的插入位置"""
20
    df = {}
21
    for node in dom_tree.nodes:
22
        df[node] = set()
23
        for predecessor in node.predecessors:
24
            runner = predecessor
25
            while runner != dom_tree.idom(node):
26
                df[runner].add(node)
27
                runner = dom_tree.idom(runner)
28
    return df
29

30
def insert_phi_functions(cfg, dom_frontier):
31
    """在支配边界处插入 φ 函数"""
32
    for var in cfg.all_variables:
33
        # 收集 var 的所有定义点
34
        defs = [block for block in cfg.blocks if var in block.definitions]
35

36
        # 在定义点的支配边界插入 φ 函数
37
        worklist = list(defs)
38
        visited = set()
39
        while worklist:
40
            block = worklist.pop()
41
            for frontier_block in dom_frontier[block]:
42
                if frontier_block not in visited:
43
                    visited.add(frontier_block)
44
                    # 插入 φ 函数
45
                    phi = PhiFunction(var, len(frontier_block.predecessors))
46
                    frontier_block.prepend(phi)
47
                    worklist.append(frontier_block)

1
class BasicBlock:
2
    """基本块"""
3
    def __init__(self, label):
4
        self.label = label
5
        self.instructions = []     # 指令列表
6
        self.predecessors = []     # 前驱基本块
7
        self.successors = []       # 后继基本块
8
        self.dominates = set()     # 支配的基本块
9
        self.idom = None           # 直接支配者
10

11
    def is_terminated(self):
12
        """检查基本块是否以终止指令结尾"""
13
        if not self.instructions:
14
            return False
15
        last = self.instructions[-1]
16
        return last.op in ('br', 'ret', 'switch', 'unreachable')
17

18
class ControlFlowGraph:
19
    """控制流图"""
20
    def __init__(self):
21
        self.blocks = []           # 基本块列表
22
        self.entry = None          # 入口基本块
23

24
    def add_block(self, block):
25
        self.blocks.append(block)
26

27
    def add_edge(self, src, dst):
28
        src.successors.append(dst)
29
        dst.predecessors.append(src)

1
def build_cfg_from_ir(instructions):
2
    """从 IR 指令序列构建控制流图"""
3
    cfg = ControlFlowGraph()
4
    current_block = BasicBlock("entry")
5
    cfg.entry = current_block
6
    cfg.add_block(current_block)
7

8
    for inst in instructions:
9
        # 遇到标签，开始新的基本块
10
        if inst.op == 'label':
11
            new_block = BasicBlock(inst.label)
12
            cfg.add_block(new_block)
13
            # 如果当前块没有终止指令，添加隐式跳转
14
            if not current_block.is_terminated():
15
                cfg.add_edge(current_block, new_block)
16
            current_block = new_block
17
            continue
18

19
        current_block.instructions.append(inst)
20

21
        # 遇到终止指令，当前基本块结束
22
        if inst.op == 'br':
23
            # 条件跳转：两个后继
24
            true_block = find_block(cfg, inst.true_label)
25
            false_block = find_block(cfg, inst.false_label)
26
            cfg.add_edge(current_block, true_block)
27
            cfg.add_edge(current_block, false_block)
28
        elif inst.op == 'jmp':
29
            # 无条件跳转：一个后继
30
            target = find_block(cfg, inst.target)
31
            cfg.add_edge(current_block, target)
32
        elif inst.op == 'ret':
33
            pass  # 返回，无后继
34

35
    return cfg

1
def compute_dominators(cfg):
2
    """计算支配关系（迭代数据流算法）"""
3
    entry = cfg.entry
4
    dom = {}
5

6
    # 初始化：入口只被自己支配，其他被所有块支配
7
    for block in cfg.blocks:
8
        if block == entry:
9
            dom[block] = {entry}
10
        else:
11
            dom[block] = set(cfg.blocks)
12

13
    # 迭代直到不变
14
    changed = True
15
    while changed:
16
        changed = False
17
        for block in cfg.blocks:
18
            if block == entry:
19
                continue
20
            # dom(B) = {B} ∪ ∩ dom(P) for all P in preds(B)
21
            new_dom = {block}
22
            if block.predecessors:
23
                pred_doms = [dom[p] for p in block.predecessors]
24
                intersection = set.intersection(*pred_doms)
25
                new_dom |= intersection
26

27
            if new_dom != dom[block]:
28
                dom[block] = new_dom
29
                changed = True
30

31
    return dom

1
; 一个简单的加法函数
2
define i32 @add(i32 %a, i32 %b) {
3
entry:
4
  %result = add i32 %a, %b
5
  ret i32 %result
6
}
7

8
; 带条件分支的函数
9
define i32 @abs(i32 %x) {
10
entry:
11
  %cmp = icmp sgt i32 %x, 0        ; 有符号比较: x > 0
12
  br i1 %cmp, label %pos, label %neg
13

14
pos:
15
  ret i32 %x
16

17
neg:
18
  %result = sub i32 0, %x           ; 0 - x = -x
19
  ret i32 %result
20
}
21

22
; 带 phi 函数的函数
23
define i32 @max(i32 %a, i32 %b) {
24
entry:
25
  %cmp = icmp sgt i32 %a, %b
26
  br i1 %cmp, label %then, label %else
27

28
then:
29
  br label %merge
30

31
else:
32
  br label %merge
33

34
merge:
35
  %result = phi i32 [ %a, %then ], [ %b, %else ]
36
  ret i32 %result
37
}

1
# 生成 LLVM IR
2
cat > example.c << 'EOF'
3
int sum(int n) {
4
    int result = 0;
5
    for (int i = 0; i < n; i++) {
6
        result += i;
7
    }
8
    return result;
9
}
10
EOF
11

12
# 未优化的 IR
13
clang -emit-llvm -S -O0 example.c -o example_O0.ll
14

15
# 优化后的 IR
16
clang -emit-llvm -S -O2 example.c -o example_O2.ll
17

18
# 对比
19
diff example_O0.ll example_O2.ll
20

21
# 使用 opt 运行特定优化 Pass
22
opt -passes=mem2reg,adce example_O0.ll -S -o example_opt.ll

1
class IRGenerator(ASTVisitor):
2
    """从 AST 生成 SSA 形式的 IR"""
3

4
    def __init__(self):
5
        self.instructions = []
6
        self.counter = 0
7
        self.current_block = BasicBlock("entry")
8

9
    def new_temp(self):
10
        """生成新的临时变量名"""
11
        self.counter += 1
12
        return f"%t{self.counter}"
13

14
    def emit(self, instruction):
15
        """发射一条 IR 指令"""
16
        self.instructions.append(instruction)
17
        return instruction.result
18

19
    def visit_NumberLit(self, node):
20
        temp = self.new_temp()
21
        self.emit(IRInst('const', temp, node.value))
22
        return temp
23

24
    def visit_BinaryOp(self, node):
25
        left = self.visit(node.left)
26
        right = self.visit(node.right)
27
        temp = self.new_temp()
28
        self.emit(IRInst(node.op, temp, left, right))
29
        return temp
30

31
    def visit_VarDecl(self, node):
32
        if node.init:
33
            value = self.visit(node.init)
34
            self.emit(IRInst('store', node.name, value))
35

36
    def visit_Identifier(self, node):
37
        temp = self.new_temp()
38
        self.emit(IRInst('load', temp, node.name))
39
        return temp
40

41
    def visit_IfStmt(self, node):
42
        cond = self.visit(node.condition)
43
        then_label = f"then_{self.counter}"
44
        else_label = f"else_{self.counter}"
45
        merge_label = f"merge_{self.counter}"
46

47
        self.emit(IRInst('br', None, cond, then_label, else_label))
48

49
        self.emit(IRInst('label', then_label))
50
        self.visit(node.then_branch)
51
        self.emit(IRInst('jmp', None, merge_label))
52

53
        self.emit(IRInst('label', else_label))
54
        if node.else_branch:
55
            self.visit(node.else_branch)
56
        self.emit(IRInst('jmp', None, merge_label))
57

58
        self.emit(IRInst('label', merge_label))
59

60
    def visit_ReturnStmt(self, node):
61
        value = self.visit(node.value)
62
        self.emit(IRInst('ret', None, value))

1
def verify_ssa(cfg):
2
    """验证 CFG 是否满足 SSA 性质"""
3
    definitions = {}  # 变量 → 定义位置
4

5
    for block in cfg.blocks:
6
        for inst in block.instructions:
7
            if inst.op == 'phi':
8
                continue  # phi 函数例外
9
            if inst.result in definitions:
10
                raise VerificationError(
11
                    f"Variable {inst.result} defined multiple times: "
12
                    f"first at {definitions[inst.result]}, "
13
                    f"again at {block.label}"
14
                )
15
            definitions[inst.result] = block.label

1
def verify_types(cfg):
2
    """验证 IR 的类型一致性"""
3
    types = {}  # 变量 → 类型
4

5
    for block in cfg.blocks:
6
        for inst in block.instructions:
7
            if inst.op == 'add':
8
                if types[inst.operands[0]] != types[inst.operands[1]]:
9
                    raise VerificationError(
10
                        f"Type mismatch in add: "
11
                        f"{types[inst.operands[0]]} vs {types[inst.operands[1]]}"
12
                    )
13
                types[inst.result] = types[inst.operands[0]]

1
# 构造一个简单 CFG 的 SSA 形式
2
cfg = ControlFlowGraph()
3
entry = BasicBlock("entry")
4
then_bb = BasicBlock("then")
5
else_bb = BasicBlock("else")
6
merge = BasicBlock("merge")
7

8
cfg.entry = entry
9
cfg.add_edge(entry, then_bb)
10
cfg.add_edge(entry, else_bb)
11
cfg.add_edge(then_bb, merge)
12
cfg.add_edge(else_bb, merge)
13

14
# 在 then 和 else 中定义变量 a
15
# → 需要在 merge 中插入 phi 函数
16
dom = compute_dominators(cfg)
17
df = compute_dominance_frontier(dom)
18
insert_phi_functions(cfg, df)

1
# 生成并查看 LLVM IR
2
cat > fib.c << 'EOF'
3
int fib(int n) {
4
    if (n <= 1) return n;
5
    return fib(n-1) + fib(n-2);
6
}
7
EOF
8

9
clang -emit-llvm -S -O0 fib.c -o fib.ll
10
cat fib.ll
11

12
# 使用 opt 优化
13
opt -passes=mem2reg,sccp,adce fib.ll -S -o fib_opt.ll
14
cat fib_opt.ll

1
cat > hello.go << 'EOF'
2
package main
3
func add(a, b int) int { return a + b }
4
func main() { println(add(3, 4)) }
5
EOF
6

7
# 查看 Go 编译器的 SSA 阶段
8
GOSSAFUNC=add go build -o hello hello.go
9
# 会在浏览器中打开 SSA 的各个优化阶段