优化

熟练掌握：
（1）局部优化：基本块，流图，DAG优化。
（2）循环优化：代码外提，强度削弱，删除归纳变量。

一、局部优化

• 划分基本块
  基本块：程序中一顺序执行的语句序列，其中第一句为其唯一的入口，最后一句为其唯一的出口。
  划分三地址代码为基本块的算法：
  1）求三地址代码中各个基本块的入口语句：
  ① 程序的第一条语句
  ② 能由条件转移语句或无条件转移语句转移到的语句
  ③ 紧跟在条件转移语句后面的语句
  2）对每一个入口语句，其基本块是由该入口语句到下一个入口语（不包括此入口语句）、或到一个转移语句（包括此转移语句）、或到一停语句(包括此停语句）之间的语句序列组成。
  3）将未划入基本块的语句删除。⭐

二、循环优化

• 代码外提

???? 查找循环 L 的不变运算的算法

① 依次查看 L 中各基本块的每个代码，如果它的每个运算对象或为常数，或者定值点在 L 外，则将此代码标记为“不变运算”。
② 重复第③步直至没有新的代码被标记为“不变运算”为止。
③ 依次查看尚未被标记为“不变运算”的代码，如果它的每个运算对象或为常数，或定值点在 L 外，或只有一个到达一定值点且该点上的代码已经标记为“不变运算”，则把被查看的代码标记为“不变运算”。

???? 代码外提算法

（1）求出循环 L 的所有不变运算。
（2）对上一步中所求得的每一不变运算 s：A：= B op C 或者 A ：= B，检查它是否满足一下条件 ① 或 ② ：
①
（i） s 所在的结点是 L 的所有出口结点的必经结点；
（ii） A 在 L 中其他地方未再定值；
（iii）L 中所有 A 的引用点只有 s 中 A 的定值才能到达。
②
A 在离开 L 后不再是活跃的，并且条件 ① 的（ii）和（iii）成立。

• 强度削弱

是指把程序中执行时间较长的运算替换为执行时间较短的运算，例如把循环中的乘法运算用递归加法来替换，通常是针对与循环控制变量有线性关系的变量赋值进行操作。

• 删除归纳变量

基本归纳变量：如果循环中对变量 I 只有唯一的形如 I：= I ± C的赋值，且其中 C 为循环不变量，则称 I 为循环中的基本归纳变量。

归纳变量：如果 I 是循环中的一基本归纳变量，J 在循环中的定值总是可以化归为 I 的同一线性函数，也即 J = C1 * I ± C2，其中 C1 和 C2 都是循环不变量，则称 J 是归纳变量，并称它与 I 同族。

???? 统一给出强度削弱和删除归纳变量的算法框架：

① 利用循环不变运算信息，找出循环中所有基本归纳变量。
② 找出所有其他归纳变量 A，并找出 A 且与已知基本归纳变量 X 的同族线性函数关系 FA（X）。
③ 对 2 中找出的每一归纳变量 A，进行强度削弱。
④ 删除对归纳变量的无用赋值。
⑤ 删除基本归纳变量。如果基本归纳变量 B 在循环出口之后不是活跃的，并且在循环中，除在其自身的递归赋值中被引用外，只在形如 if B rop Y goto L 中被引用，则可选取一与 B 同族的归纳变量 M 来替换 B 进行条件控制。最后删除循环中对 B 的递归赋值的代码。