name: common-subexpression-eliminator description: ‘实现公共子表达式消除 (CSE)。使用场景：(1) 构建编译器，(2) 优化代码，(3) 程序分析。’ version: 1.0.0 tags:
- 优化
- 编译器过程
- cse
- 代码移动 difficulty: 中级 languages:
- python
- rust dependencies:
- ssa-constructor
公共子表达式消除器
实现公共子表达式消除优化。
使用时机
- 构建优化编译器
- 程序优化
- 代码分析
- 性能调优
此技能的作用
- 识别冗余 - 查找重复计算
- 消除 - 重用计算值
- 处理内存 - 考虑别名问题
- 优化 - 全局和局部 CSE
关键概念
| 概念 | 描述 |
|---|---|
| 可用表达式 | 已计算且未被杀死 |
| 杀死 | 表达式无效化 |
| 全局 | 跨基本块 |
| 保守 | 避免别名问题 |
提示
- 保守处理别名
- 考虑副作用
- 使用哈希进行快速比较
- 跟踪内存操作
相关技能
constant-propagation-pass- 常量传播dead-code-eliminator- 删除死代码loop-optimizer- 循环优化
经典参考文献
| 参考文献 | 重要性 |
|---|---|
| Cocke, “Global Common Subexpression Elimination” (1970) | 原始 CSE 算法 |
| Tjaden & Flynt, “Global Subexpression Elimination” (1970s) | 早期 CSE 工作 |
| Rosen, “Global Value Numbers and Redundant Computations” (1988) | 值编号框架 |
| Click & Cooper, “Combining Analyses, Optimizing and Using Them” (1995) | CSE 与其他分析的集成 |
研究工具与成果
现实世界的 CSE 实现研究：
| 工具 | 重要性 |
|---|---|
| GCC GIMPLE | GCC 中的生产级 CSE |
| LLVM SELC | 基于标量演化的 CSE |
| MLIR CSE | 方言级共用 |
| GraalVM Truffle | 带 CSE 的部分评估 |
| HotSpot C1/C2 | 客户端/服务器编译器 CSE |
关键优化
- 冗余负载消除 (RLE)：超越表达式 CSE
- 存储 CSE：对相同位置的公共存储
- 线性速度冗余：有利与冗余
研究前沿
当前的 CSE 研究：
| 方向 | 关键论文 | 挑战 |
|---|---|---|
| 值编号 | Rosen, Wegman & Zadeck, “Global Value Numbers and Redundant Computations” (POPL 1988) | 比 CSE 更强大 |
| SCEV (标量演化) | LLVM 的 SCEV 分析 | 循环携带依赖 |
| 部分冗余 | Morel & Renvoise, “Global Optimization by Suppression of Partial Redundancies” (CACM 1979) | 跨路径冗余 |
| 懒惰代码移动 | Knoop, Rüthing & Steffen, “Lazy Code Motion” (PLDI 1992) | 最优放置 |
热点话题
- 量子电路中的冗余：量子编译的 CSE
- 图冗余消除：数据流图中的冗余消除
- 近似计算：CSE 中的可容忍近似
实现陷阱
常见的 CSE 错误：
| 陷阱 | 真实示例 | 预防方法 |
|---|---|---|
| 别名违规 | 对别名指针进行 CSE | 对指针保守 |
| 副作用 | CSE 移除 io 操作 | 精确跟踪纯度 |
| 内存排序 | 乱序存储 CSE | 精确建模内存 |
| 除法安全 | 除零的 CSE | 检查除数非零 |
| 溢出 | CSE 改变溢出 | 保留溢出行为 |
| 加载/存储排序 | 错误地重新排序加载 | 建模内存模型 |
“指针别名”错误
CSE 错误地假设没有别名：
// 可能别名 - CSE 会出错
a[i] = x;
b[j] = a[i]; // 可能与上面的 a[i] 相同！
解决方案：保守 - 如果指针可能别名，则不进行 CSE。