编译优化实战：基本块转换与五大数据流分析详解
编译优化实战：基本块转换与五大数据流分析详解
编译原理中的代码优化是提高程序执行效率的关键技术。通过各种优化方法，编译器可以在不改变程序语义的情况下，减少运行时间、降低资源消耗。本文将深入讲解代码优化的核心技术和方法，包括基本块优化和数据流分析等，帮助读者掌握编译优化的精髓。
前言
在编译原理中，"定值"指的是对变量的赋值操作，这会消除之前对该变量的所有赋值；"引用"则是指使用变量的值；而"活跃范围"定义为从变量被赋值到其最后一次被引用的范围。
例如，在以下代码中：
a = ... // 10
....
.... = a+1 // 20
... =
a = ... // 25
...
.... = a+2 // 40
变量a在第10行被赋值，第20行是其最后一次使用，因此a的活跃范围是{10,20}。之后在第25行再次赋值，形成新的活跃范围{25,40}。
一、基本块的优化
局部优化技术通常将基本块转换为有向无环图(DAG)，以明确变量之间的依赖关系和指令执行顺序。每个语句s对应一个内部节点N：
- 节点
N的标签是s中的运算符，并关联一个定值变量表，表示s是在此基本块内最晚对表中变量进行赋值的语句 N的子节点是基本块中在s之前、最后一个对s所使用的运算分量进行赋值的语句对应的节点
基于DAG删除无用代码： 删除所有没有附加活跃变量（活跃变量是指其值可能会在以后被使用的变量）的根结点(即没有父结点的结点) 。
二、数据流分析
1. 到达-定值分析 (Reaching-Definition Analysis)
"定值"是指将一个值赋给变量的语句。如果某个变量x的一个定值d到达点p，则在点p处使用的x的值可能就是由d最后赋予的。
计算方法：
引用-定值链(Use-Definition Chains)，即ud链，对于变量的每一次引用，到达该引用的所有定值都在该列表中。
ud链的核心在于，可以通过该链，明确当前使用的链，在哪里被定值，被定值是否是常量等。
应用：
- 循环不变计算的检测
如果表达式的运算分量是常数，或者所有定值点都在循环外部，则可将该表达式标记为循环不变。可以提到循环外部。 - 常量合并
- 判定变量
x在p点上是否未经定值就被引用 - 强度削弱
1.1 强度削弱
强度削弱利用了归纳变量和到达定值分析的结果。对于一个变量x，如果存在一个正的或负的常量c，使得每次x被赋值时，它的值总是增加c，则称x为归纳变量。
计算方法: 寻找L中只有一次定值的变量k，它具有下面的形式：k=c′×j+d′。其中c′和d′是常量，j是基本的或非基本的归纳变量.
效果：
2. 活跃变量分析 (Live-Variable Analysis)
对于变量x和程序点p，如果在流图中沿着从p开始的某条路径会引用变量x在p点的值，则称变量x在 点p是活跃(live)的，否则称变量x在点p不活跃(dead)。
活跃变量分析的核心在于，在寄存器分配时，同时活跃(即为冲突)的变量分配到不同的寄存器。
此外，如果变量是不冲突的，那么可以进行寄存器合并，但是寄存器合并时，会导致寄存器的占用时间增长，而导致存在寄存器溢出，需要降寄存器写回内存的风险。
计算方法：
3. 定值引用链分析
定值-引用链：设变量x有一个定值d，该定值所有能够到达的引用u的集合称为x在d处的定值-引用链，简称du链。
- 删除无用赋值
如果定值之后，再也没有被引用，那么就是无用定值/赋值，可以删除。 - 基本块分配寄存器
分配寄存器时，优先选择不后续不再被引用的寄存器。
此外，在进行寄存器分配时，同时活跃的变量，即为“冲突”的，不可以将其放入同一个寄存器。
通过画出冲突图，利用图着色算法，对寄存器进行分配。
4. 可用表达式分析 (Available-Expression Analysis)
删除公共表达式：如果一个表达式在程序的每个分支上都进行了计算，那么在分支的汇聚出口，我们可以直接使用该表达式结果。
在点 p上，x op y已经在之前被计算过，不需要重新计算。
计算方法：
用途：
- 消除全局公共子表达式
- 进行复制传播
5. 支配节点树(Dominator Tree)
如果从流图的入口结点到结点n的每条路径都经过结点d，则称结点d支配(dominate)结点n，记为d dom n。
通过支配节点树，我们可以分析程序的必经路径和必经路径边界信息。利用支配节点树的边界信息，可以产生SSA表达式的phi节点。
计算方法：
支配结点树的例子：
总结
常用的优化方法包括：
- 删除公共子表达式 : 可用表达式
- 复制传播 : 可用表达式
- 删除无用代码：定值引用链
- 常量合并：引用定值链
- 代码移动：引用定值链
- 强度削弱：引用定值链
- 删除归纳变量：引用定值链