名称: ssa-constructor 描述: ‘构建静态单赋值形式。用途：(1) 构建优化编译器，(2) 实现程序分析，(3) 验证。’ 版本: 1.0.0 标签:

编译器
ssa
优化
中间表示难度: 中级语言:
python
rust
c++ 依赖: []

SSA 构造器

将程序转换为静态单赋值（SSA）形式。

何时使用

构建优化编译器
程序分析
验证
寄存器分配

此技能的功能

重命名变量 - 每个定义获得唯一名称
插入 φ-函数 - 在分支处合并值
计算支配关系 - 用于 φ 放置
优化 SSA - 构造后进行优化

SSA 形式

之前（多重定义）：
  x = 1
  x = 2
  y = x + 1

之后（SSA）：
  x₁ = 1
  x₂ = 2  
  y₁ = x₂ + 1

实现

from dataclasses import dataclass, field
from typing import Dict, List, Set, Optional

@dataclass
class CFGNode:
    """控制流图节点"""
    id: str
    statements: List = field(default_factory=list)
    predecessors: List['CFGNode'] = field(default_factory=list)
    successors: List['CFGNode'] = field(default_factory=list)
    dom: Set['CFGNode'] = field(default_factory=set)
    idom: Optional['CFGNode'] = None
    df: Set['CFGNode'] = field(default_factory=set)  # 支配前沿

@dataclass
class Program:
    """SSA 形式的程序"""
    cfg: Dict[str, CFGNode]
    entry: str

@dataclass
class SSAStmt:
    """SSA 语句"""
    pass

@dataclass
class SSADef(SSAStmt):
    """x = y op z"""
    target: str
    op: str
    args: List[str]

@dataclass
class PhiFunc(SSAStmt):
    """φ(x₁, x₂, ...)"""
    target: str
    args: List[tuple[str, str]]  # (值, 块)

class SSAConstructor:
    """转换为 SSA 形式"""
    
    def __init__(self):
        self.version: Dict[str, int] = {}  # 变量 -> 当前版本
        self.current_version: Dict[str, int] = {}  # 每块
        self.phi_inserted: Dict[str, List[str]] = {}  # 变量 -> 插入 φ 的块
    
    def construct(self, cfg: Dict[str, CFGNode], entry: str) -> Program:
        """将控制流图转换为 SSA"""
        
        # 步骤 1: 计算支配关系
        self.compute_dominance(cfg, entry)
        
        # 步骤 2: 计算支配前沿
        self.compute_dominance_frontier(cfg, entry)
        
        # 步骤 3: 插入 φ-函数
        self.insert_phi_functions(cfg)
        
        # 步骤 4: 重命名变量
        self.rename_variables(cfg, entry)
        
        return Program(cfg, entry)
    
    def compute_dominance(self, cfg: Dict[str, CFGNode], entry: str):
        """计算支配关系"""
        
        # 初始化
        for node in cfg.values():
            if node.id == entry:
                node.dom = {node}
            else:
                node.dom = set(cfg.keys())
        
        # 迭代计算
        changed = True
        while changed:
            changed = False
            
            for node in cfg.values():
                if node.id == entry:
                    continue
                
                new_dom = {node}
                for pred in node.predecessors:
                    new_dom &= pred.dom
                new_dom.add(node)
                
                if new_dom != node.dom:
                    node.dom = new_dom
                    changed = True
    
    def compute_dominance_frontier(self, cfg: Dict[str, CFGNode], entry: str):
        """计算支配前沿"""
        
        for node in cfg.values():
            node.df = set()
        
        for node in cfg.values():
            if len(node.predecessors) >= 2:
                for pred in node.predecessors:
                    # 向上遍历支配树
                    runner = pred
                    while runner != node.idom and runner != entry:
                        runner.df.add(node.id)
                        runner = runner.idom
    
    def compute_idom(self, cfg: Dict[str, CFGNode], entry: str):
        """计算直接支配者"""
        
        for node in cfg.values():
            if node.id == entry:
                node.idom = None
                continue
            
            # IDOM = 最近的严格支配者
            doms = list(node.dom - {node})
            if doms:
                # 移除任何支配另一个的
                for d in doms:
                    for other in doms:
                        if d != other and other in cfg[d].dom:
                            doms.remove(d)
                node.idom = doms[0] if doms else None
    
    def insert_phi_functions(self, cfg: Dict[str, CFGNode]):
        """在支配前沿插入 φ-函数"""
        
        # 跟踪需要 φ 的变量
        to_process: Dict[str, List[str]] = {}  # 变量 -> 块
        
        # 找到所有定义的变量
        all_vars = set()
        for node in cfg.values():
            for stmt in node.statements:
                if isinstance(stmt, SSADef):
                    all_vars.add(stmt.target)
        
        for var in all_vars:
            to_process[var] = []
            
            # 初始：变量被定义的块
            for node in cfg.values():
                for stmt in node.statements:
                    if isinstance(stmt, SSADef) and stmt.target == var:
                        to_process[var].append(node.id)
        
        # 迭代地在 DF 处添加 φ
        for var, blocks in to_process.items():
            for block_id in blocks:
                block = cfg[block_id]
                for df_block in block.df:
                    if df_block not in self.phi_inserted.get(var, []):
                        # 插入 φ
                        cfg[df_block].statements.insert(
                            0,
                            PhiFunc(var, [])
                        )
                        # 添加到处理中
                        if df_block not in to_process[var]:
                            to_process[var].append(df_block)

变量重命名

    def rename_variables(self, cfg: Dict[str, CFGNode], entry: str):
        """将变量重命名为 SSA 形式"""
        
        self.version = {v: 0 for v in self.get_all_vars()}
        
        self.rename_block(cfg[entry], set())
    
    def rename_block(self, block: CFGNode, seen: Set[str]):
        """重命名块中的变量"""
        
        # 为此块创建新版本映射
        block_versions = dict(self.version)
        self.current_version[block.id] = block_versions
        
        new_stmts = []
        
        for stmt in block.statements:
            if isinstance(stmt, PhiFunc):
                # 从前驱添加参数
                new_args = []
                for pred in block.predecessors:
                    pred_versions = self.current_version.get(pred.id, {})
                    # 使用到达定义
                    v = pred_versions.get(stmt.target, 
                                          self.version.get(stmt.target, 0))
                    new_args.append((f"v_{v}", pred.id))
                
                stmt.args = new_args
            
            if isinstance(stmt, SSADef):
                # 递增版本
                self.version[stmt.target] = self.version.get(stmt.target, 0) + 1
                new_name = f"{stmt.target}_{self.version[stmt.target]}"
                
                # 重命名参数
                new_args = []
                for arg in stmt.args:
                    if arg in self.version:
                        new_args.append(f"{arg}_{self.version[arg]}")
                    else:
                        new_args.append(arg)
                
                new_stmts.append(SSADef(new_name, stmt.op, new_args))
            else:
                new_stmts.append(stmt)
        
        block.statements = new_stmts
        
        # 重命名后继块
        for succ in block.successors:
            if succ.id not in seen:
                seen.add(succ.id)
                self.rename_block(succ, seen)

SSA 转回正常形式

class SSAToNormal:
    """将 SSA 转回正常形式"""
    
    def convert(self, ssa_program: Program) -> 'Program':
        """将 SSA 转换为正常形式"""
        
        cfg = ssa_program.cfg
        
        # 识别 φ-函数
        phi_funcs = self.find_phi_functions(cfg)
        
        # 为每个 φ 创建前驱列表
        for var, blocks in phi_funcs.items():
            for block_id in blocks:
                block = cfg[block_id]
                phi = self.get_phi(block, var)
                
                # 用移动替换 φ
                moves = self.phi_to_moves(phi, block.predecessors)
                block.statements.extend(moves)
                
                # 移除 φ
                block.statements.remove(phi)
        
        return ssa_program
    
    def phi_to_moves(self, phi: PhiFunc, preds: List[CFGNode]) -> List:
        """将 φ 转换为移动"""
        
        moves = []
        
        for (value, pred_id), pred in zip(phi.args, preds):
            moves.append(SSADef(phi.target, 'move', [value]))
        
        return moves

关键概念

概念	描述
SSA	每个变量只定义一次
版本化	x → x₁, x₂, …
φ-函数	在控制流交汇处合并
支配关系	所有路径都经过
支配前沿	需要 φ 的地方

优化优势

常量传播
复制传播
死代码消除
寄存器分配

提示

正确计算支配关系
在支配前沿放置 φ
单独处理函数
考虑最小 SSA

经典参考文献

参考文献	重要性
Cytron 等人，《高效计算静态单赋值形式和控制依赖图》（TOPLAS 1991）	原始 SSA 论文
Appel，《现代编译器实现 in ML》，第 19 章（1998）	SSA 构造算法
Cooper & Torczon，《工程编译器》，第 9 章（2003）	实用 SSA 实现

研究工具与工件

生产编译器中的 SSA 实现：

编译器	学习要点
LLVM	工业级 SSA，优化过程
GCC	GIMPLE SSA 形式
HotSpot JVM	JVM 级别 SSA
GraalVM	Truffle 框架

学术/研究

SSA 书籍（Click & Cooper） - 综合参考
Cytron 等人 - 原始 SSA 论文

研究前沿

1. SSA 扩展

内存 SSA：指针分析集成
并发 SSA：线程特定版本
调试 SSA：调试信息保留

2. SSA 销毁

挑战：将 SSA 转回正常形式
方法：φ-转移动转换，复制传播
论文：《SSA 销毁》（Brandt 等人）

实现陷阱

陷阱	实际后果	解决方案
错误支配关系	不正确 φ 放置	使用迭代 DF 计算
缺失 φ	程序语义错误	正确计算 DF
版本爆炸	版本过多	使用最小 SSA

“最小 vs 修剪 SSA”权衡

最小 SSA：在每个 DF 处插入 φ，可能有未使用 φ
修剪 SSA：仅保留后续使用的变量的 φ，φ 更少但需要活性分析 |

SSA构造器Skill ssa-constructor

SSA 构造器

何时使用

此技能的功能

SSA 形式

实现

变量重命名

SSA 转回正常形式

关键概念

优化优势

提示

相关技能

经典参考文献

研究工具与工件

学术/研究

研究前沿

1. SSA 扩展

2. SSA 销毁

实现陷阱

“最小 vs 修剪 SSA”权衡