第九章 代码优化与代码生成

看了下2020年的考题，发现第九章的内容在大题中的占比有点高，来到了15分。第七章在大题中的占比来到了19分，并且有一道题是最后一题，考察的是写文法每个产生式对应的语义子程序。

9.1 概述

• 代码优化的任务：通过等价的程序变换，获得执行速度快，占用空间少的程序。
• 代码生成的任务：针对目标语言的特殊性，生成高性能的目标代码（与机器相关）。
• 算法优化：有效的数据结构和算法。
• 编译优化：
  ①中间代码优化（与机器无关）
  如：常数计算、公共代码段提取。
  ②目标代码优化（机器相关）
  如：特殊指令、特殊结构。
• 局部优化：基本块内部（使用DAG，考试一定会考到）
• 全局优化：循环优化、控制流分析与化简、数据流分析。

优化：对程序进行各种等价变换，使得从变换后的程序出发，能够生成更有效的目标代码。

• 等价：指不改变程序的运行结果。
• 有效：指目标代码运行时间短，占用的存储空间小。

优化的目的是为了产生更高效的代码，由优化编译程序提供的对代码的各种变换必须遵循：

• 等价原则。
• 有效原则：优化后产生的目标代码运行时间较短，占用的存储空间小。
• 合算原则：尽可能以较低的代价取得较好的优化效果。

优化的三个不同级别：

• 局部优化。
• 循环优化。
• 全局优化。

优化的种类：

• 删除多于运算（删除公用子表达式）。
• 代码外提。
• 强度削弱。
• 变换循环控制条件。
• 合并已知量。
• 复写转播。
• 删除无用赋值。

9.2 局部优化

基本块：指程序中一个顺序执行语句的序列，其中只有一个入口和一个出口。入口就是其中第一个语句，出口是最后一个语句。

局限于基本块范围之内的优化称为基本块的优化，或者称为局部优化，局部优化也是本次考试的重点，并且不会考察局部优化以外的优化。

1.划分四元式程序基本块的算法如下：
1.求出四元式程序中每个基本块的入口语句：

• 程序第一个语句；
• 能由条件转移或无条件转移语句转移到的语句；
• 紧跟在条件转移语句后面的语句。

2.确定基本块的算法：
对于1中求出的每一个入口语句，确定其所属的基本块：它是由 该入口语句到下一个入口语句之间（不包括下一个入口语句）、或到一转移语句（包含该转移语句）、或到一停语句（halt） 的语句序列组成。

一个例子：

入口语句分别是：（1）（3）（5）（8）
划分的基本块为：

• 第一块：（1）（2）
• 第二块：（3）（4）
• 第三块：（5）（6）（7）
• 第四块：（8）（9）

3.程序流图：

有向边的构造：

• 有一个条件或无条件转移语句从B₁的最后一条语句转移到B₂的第一条语句；（B指的是划分后的基本块，block）
• 在程序序列中，B₂紧跟在B₁后面，并且B₁的最后一条语句不是一个无条件转移语句。

满足以上两个条件之一，就一个从B₁射出一条有向边至B₂。

4.图表示法：

• 图的叶结点以一标识符或常数作为标记，表示该结点代表该变量或常数的值。
• 图的内部节点以一个运算符op作为标记，表示该节点代表应用该运算符对其后继节点所代表的值进行运算的结果。
• 图中各个结点可能附加一个或多个标识符，表示这些变量具有该点所代表的值（重复赋值）。

这次考试只考察0型四元式（后继节点个数为0）、1型四元式（有一个后继节点）和2型四元式（有两个后继节点）。

• 跳转语句中跳转到的地址用“（）”来标识。
• 将数组元素的值赋给变量是2型四元式，而为数组元素赋值是三型四元式。
  
  
  
  
  
  以上的构造过程过于复杂，看一个例子更加直观：

9.3 目标代码生成

目标代码生成器位于中间代码优化之后。输入为中间代码（三地址代码、语法树结构、后缀式），输出为目标代码（绝对机器代码、可重定位机器指令代码、汇编指令代码）。目标机：多通用寄存器、控制栈、堆等。


原则：尽可能留、尽可能用、及时腾空。

• 寄存器描述数组RVALUE：描述了寄存器R中有什么值（存的是哪个变量）；如T₁存放在R₀中：RVALUE(R₀) = {T₁}
• 变量地址描述数组AVALUE：记录变量的现行值存放在哪里，可以视寄存器，可以是内存单元。如：T₁存放在R₀中，即为AVALUE(T₁) = {R₀}；T₁存放在内存单元T₁，即为AVALUE(T₁) = {T₁}。
• 补充说明：因为寄存器的分配局限于基本块范围之内，一旦处理完基本块中所有四元式，对现行值在寄存器中的每个变量，如果它在基本块之后是活跃的，则要把它存在寄存器中的值存放到它的主存单元中。 即，最后执行一条ST指令。
• 强调：对形如A:=B的四元式，如果B的现行值在某个寄存器R_i中，则无须生成目标代码，只须在RVALUE(R_i)中增加一个A（即同时将R_i分配给B和A），并将AVALUE(A)修改为R_i即可。
• 代码生成算法：
  
  
  
  第五步有点关键，即如果B或C的现行值在基本块内不再引用且不是活跃变量，则删除RVALUE®中的B和C及AVALUE(B)和AVALUE©中的R，使寄存器不再被B和C占用。

看个例子：

作业

9.2 划分程序基本块并绘制程序流图

9.3 通过DAG图对基本块进行优化

9.4

9.5 较难的目标代码生成、寄存器描述及地址描述

9.6 综合性极强，并且是今年新加的题，极有可能成为期末考试的原题