SSA 形式构造与优化 Pass 设计

静态单赋值（SSA）形式是现代编译器优化的基石。在 SSA 形式中，每个变量只被赋值一次，这使得数据流分析变得简洁高效。本文深入探讨 SSA 的构造算法和基于 SSA 的优化 Pass 设计。

一、支配树与支配边界

SSA 构造依赖于控制流图的支配关系。节点 A 支配节点 B 当且仅当从入口到 B 的所有路径都经过 A。支配边界是插入 Phi 节点的关键位置。

type DominatorTree struct {
    idom    map[int]int    // 直接支配者
    children map[int][]int  // 支配树子节点
    df      map[int][]int   // 支配边界
}

func (dt *DominatorTree) ComputeDominanceFrontier(cfg *CFG) {
    for _, b := range cfg.Blocks {
        dt.df[b.ID] = make([]int, 0)
    }
    for _, b := range cfg.Blocks {
        if len(b.Preds) >= 2 {
            for _, pred := range b.Preds {
                runner := pred
                for runner != dt.idom[b.ID] {
                    dt.df[runner] = append(dt.df[runner], b.ID)
                    runner = dt.idom[runner]
                }
            }
        }
    }
}

二、Phi 节点插入

标准 SSA 构造算法在变量的定义处和支配边界处插入 Phi 节点，然后通过重命名过程消除变量名冲突。

func InsertPhiNodes(cfg *CFG, dt *DominatorTree) {
    for _, v := range cfg.Variables {
        worklist := make([]int, 0)
        visited := make(map[int]bool)
        for _, def := range v.DefBlocks {
            worklist = append(worklist, def)
        }
        for len(worklist) > 0 {
            blockID := worklist[0]
            worklist = worklist[1:]
            for _, dfBlock := range dt.df[blockID] {
                if !visited[dfBlock] {
                    cfg.Blocks[dfBlock].AddPhi(v)
                    visited[dfBlock] = true
                    worklist = append(worklist, dfBlock)
                }
            }
        }
    }
}

三、变量重命名

以支配树先序遍历，为每个变量维护一个版本栈。遇到定义时压入新版本，遇到使用时取栈顶版本，离开作用域时弹出。

func RenameVariables(cfg *CFG, dt *DominatorTree) {
    stacks := make(map[string]*Stack)
    counters := make(map[string]int)
    var rename func(blockID int)
    rename = func(blockID int) {
        block := cfg.Blocks[blockID]
        // 重命名 Phi 节点
        for _, phi := range block.Phis {
            newName := fmt.Sprintf("%s_%d", phi.Var, counters[phi.Var])
            counters[phi.Var]++
            stacks[phi.Var].Push(newName)
            phi.Rename(newName)
        }
        // 重命名普通指令
        for _, inst := range block.Instructions {
            for _, use := range inst.Uses {
                inst.ReplaceUse(use, stacks[use].Top())
            }
            if inst.HasDef() {
                newName := fmt.Sprintf("%s_%d", inst.Def, counters[inst.Def])
                counters[inst.Def]++
                stacks[inst.Def].Push(newName)
                inst.RenameDef(newName)
            }
        }
        // 填充后继的 Phi 节点参数
        for _, succ := range block.Succs {
            for _, phi := range cfg.Blocks[succ].Phis {
                phi.AddArgument(blockID, stacks[phi.Var].Top())
            }
        }
        // 递归处理支配树子节点
        for _, child := range dt.children[blockID] {
            rename(child)
        }
        // 弹出本块压入的版本
        for _, inst := range block.Instructions {
            if inst.HasDef() {
                stacks[inst.Def].Pop()
            }
        }
    }
    rename(cfg.Entry)
}

四、基于 SSA 的优化 Pass

SSA 形式使许多优化变得简单：常量传播只需检查定义是否为常量；死代码消除只需检查变量是否有使用；全局值编号利用 SSA 的哈希等价性。

// 稀疏条件常量传播（SCCP）
func SCCP(cfg *CFG) {
    lattice := make(map[string]LatticeValue)
    worklist := initWorklist(cfg)
    for len(worklist) > 0 {
        inst := worklist.Pop()
        newVal := evaluate(inst, lattice)
        if newVal != lattice[inst.Def] {
            lattice[inst.Def] = newVal
            for _, use := range inst.Uses {
                worklist.Push(use)
            }
        }
    }
    // 用常量替换变量
    for name, val := range lattice {
        if val.IsConstant() {
            replaceAllUses(name, val.Constant)
        }
    }
}

五、SSA 的破坏与恢复

某些优化（如寄存器分配）需要破坏 SSA 形式。出 SSA 的标准方法是将 Phi 节点替换为对应前驱块中的复制指令，然后通过合并优化消除冗余复制。