2024-编译原理-分析优化篇
1. 数据流分析
我们目前已经学习了如何编译生成可执行代码，但是此时生成的代码的质量并不能够让人满意。因此，我们希望消除目标代码中的冗余指令，并且将低效的指令序列替换为具有相同功能的更加高效的序列，这便是“代码优化”。
编译期优化需要在不运行程序的条件下获知程序的行为信息，因此会用到不同的静态分析（Static Analysis）技术：
- 数据流分析：基于格（Lattice）理论研究数据流值（Dataflow Facts）在程序中的传播
- 符号执行：使用符号值代替具体值执行程序，探索路径约束
- 抽象解释：将程序的状态映射到抽象域
- 模型检验：穷举程序状态空间检验程序性质
1.1 基本概念
1.1.1 控制流图（Control Fow Graph，CFG）
控制流图
1.1.2 数据流值（Dataflow Facts）
对于每个程序点，定义两个集合： -
1.1.3 转移函数（Transfer Function）
每个基本块
1.1.4 数据流值初始化
根据分析的方向有不同的初始化要求。
前向分析（Forward Analysis）：
- 从
开始沿着CFG边方向分析 - 需初始化
- 从
后向分析（Backward Analysis）：
从
开始沿着CFG边反方向进行分析 需初始化
1.1.5 数据流合并操作
在交汇点（如分支合并）执行格（Lattice）上的合并操作：
1.2 Worklist算法
Worklist算法是广度优先遍历（BFS）算法的变体，通过跳过不发生变化的结点的方式进行剪枝，使得冗余计算次数减少。
1.3 数据流分析理论基础
1.4 数据流分析的例子
1.4.1 到达定义分析（Reaching Definitions）
目标：计算每个程序中点能到达的变量定义
格结构：
，其中 为所有定义的集合 转移函数：
合并：取并集
1.4.2 活跃变量分析（Live Variables）
目标：确定变量在程序点是否会被后续使用
格结构：
， 为变量集合 转移函数：
合并：取并集
1.4.3 可用表达式分析（Available Expressions）
目标：判断表达式在程序点是否已被计算且未修改
格结构：
， 为表达式集合 转移函数：
合并：取交集
1.4.4 小结
对于已学的三种数据流分析对比如下：
1.5 常量传播
1.5.1 常量传播分析的特点
- 有无穷多的数据流值（本质原因是常量取值的值域是无限的）
- 不是分配的（Non-Distributive）
1.5.2 格设计
- 值域：
: Undef，未初始化 : 已知常量值 : NAC，Not A Constant，非常量
1.5.3 转移函数规则
对于语句
赋值语句
x = expr：其中 的递归定义： 其它语句，不会传播常量，保持状态不变。（忽略load、store等内存操作）
1.5.4 合并规则
常量传播数据流值的合并规则如下：
1.5.5 常量传播的改进（选学）
在传统的常量传播基础上，可以进行以下优化：
稀疏常量传播
条件常量传播
稀疏条件常量传播（Sparse Conditional Constant Propagation）
- 将稀疏常量传播与条件常量传播相结合，就是当前主流的常量传播算法，稀疏条件常量传播算法，通常简写为 SCCP。
- LLVM 集成了 SCCP 为一个内置Pass，你可以通过
opt -sccp开启SCCP优化。