常数传播优化

实现数据流常数传播优化。

何时使用

构建编译器
学习程序分析
实现优化
静态程序分析

这个技能的作用

收集常数 - 跟踪程序中已知的值
传播 - 使用格操作进行前向数据流分析
优化 - 用常数替换变量/表达式
处理条件语句 - 使用条件分支来精化分析

关键概念

概念	描述
格	偏序：⊥（未初始化）< 常数 < ⊤（未知/NAC）
转移函数	语句如何转换格值
合并	在控制流合并点的格交（∩ 用于常数）
工作列表算法	迭代定点计算
条件敏感性	使用分支条件来精化值

格结构

        ⊤ (NAC - 非常数)
       / | \
      1  2  3  ...（特定常数）
       \ | /
        ⊥ (UNDEF - 未定义)

提示

在控制流合并点使用合并（∩）
保守处理：未知 = NAC（非常数）
考虑数组和指针作为杀死定义
与复制传播结合以获得更好结果
SSA 形式显著简化分析

实现

from dataclasses import dataclass
from typing import Dict, Set, Optional
from enum import Enum

class ConstValue(Enum):
    UNDEF = 0   # 底部：未定义
    NAC = 1     # 顶部：非常数
    
@dataclass
class ConstantProp:
    lattice: Dict[str, any]  # 变量 -> 常数值或 UNDEF/NAC
    
    def transfer_assign(self, var: str, expr):
        if self.is_constant_expr(expr):
            self.lattice[var] = self.eval_const(expr)
        else:
            self.lattice[var] = ConstValue.NAC
    
    def join(self, v1, v2):
        if v1 == v2:
            return v1
        if v1 == ConstValue.UNDEF:
            return v2
        if v2 == ConstValue.UNDEF:
            return v1
        return ConstValue.NAC  # 不同的常数

经典参考文献

参考文献	重要性
Wegman & Zadeck, “Constant Propagation with Conditional Branches” (TOPLAS 1991)	基础稀疏条件常数传播算法
Cytron et al., “Efficiently Computing Static Single Assignment Form” (TOPLAS 1991)	SSA 构造实现高效常数传播
Kildall, “A Unified Approach to Global Program Optimization” (POPL 1973)	原始数据流框架

研究工具与制品

编译器优化工具：

工具	学习内容
LLVM SCCP	稀疏条件常数传播过程
GCC SSA-CCP	GCC 的常数传播实现

权衡与限制

算法权衡

方法	精度	复杂度	用例
简单常数传播	低	O(n)	快速过程
条件常数传播	中等	O(n²)	大多数编译器
稀疏常数传播 (SSA)	中等	O(n)	现代编译器
SCCP	高	O(n)	优化编译器

何时不使用

过程间：需要上下文敏感分析
指针/别名：可能需要指针分析
数组元素：需要保守处理

实现陷阱

陷阱	实际后果	解决方案
错误合并	不精确或错误结果	使用正确的格操作
未初始化变量	虚假常数	正确跟踪 UNDEF
别名	错误常数值	对指针保守
循环	不终止	使用带扩展的工作列表

常数传播优化Skill constant-propagation-pass

常数传播优化

何时使用

这个技能的作用

关键概念

格结构

提示

实现

相关技能

经典参考文献

研究工具与制品

权衡与限制

算法权衡

何时不使用

实现陷阱