第十章 优化和目标代码生成

第一部分：优化

1 优化的基本概念

优化：对程序进行各种等价变换，使得从变换后的程序出发，可以生成更有效的目标代码。
优化的特点：等价，有效。
优化的级别：局部优化、循环优化、全局优化。
优化的种类：删除多余运算、合并已知量、复写传播、删除无用赋值、代码外提、强度消弱（例如乘法换为加法）、变换循环控制条件。

2 局部优化

局限于基本块范围内的优化称为基本块内的优化，或称局部优化。

2.1 基本块

基本块是程序中一顺序执行语句序列，其中只有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个语句。
对三地址语句为x:=y+z，称对x定值并引用y和z。
基本块中的一个名字在程序中的某个给定点是活跃的，是指如果在程序中(包括在本基本块或在其它基本块中)它的值在该点以后被引用。

2.2 基本块划分算法和流图

划分基本块的算法：

  1. 找出中间语言(三地址语句)程序中各个基本块的入口语句:程序第一个语句，或能由条件转移语句或无条件转移语句转移到的语句，或紧跟在条件转移语句后面的语句；
  2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的；
  3. 凡未被纳入某一基本块中的语句，可以从程序中删除。

流图：
以基本块为结点构成流图；
如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点；
如果在某个执行顺序中，基本块B2紧接在基本块B1之后执行，则从B1到B2有一条有向边（B1是B2的前驱，B2是B1的后继）。有一个条件或无条件转移语句从B1的最后一条语句转移到B2的第一条语句；或者在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句不是一个无条件转移语句。

示例：
基本块划分和流图

2.3 四元式的有向无环图(DAG)表示

在DAG增加标记和附加信息：
图的叶结点以一标识符或常数作为标记，表示该结点代表该变量或常数的值；
图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果；
各个结点上可能附加一个或多个标识符(称附加标识符)表示这些变量具有该结点所代表的值。
示例：
DAG的扩充

四元式的DAG表示：
四元式的DAG表示

2.4 局部优化算法

一个基本块，可用一个DAG来表示，对基本块中每一条四元式代码，依次构造对应的DAG图，最后基本块中所有四元式构造出来DAG连成整个基本块的DAG。

引入一个函数Node，保存和计算DAG中标识符与结点的对应关系：
函数Node

步骤：

  1. 准备操作数的结点
    1.1 如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点：
    如果当前四元式是0型，则记NODE(B)的值为n，转4；
    如果当前四元式是1型，则转2(1)；
    如果当前四元式是2型，则(i)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(ii)转2(2)。

  2. 合并已知量
    2.1 如果NODE(B)是标记为常数的叶结点，则转2(3)；否则，转3(1)。
    2.2 如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)；否则，转3(2)。
    2.3 执行op B (即合并已知量)。令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P作标记的叶结点n。置NODE(P)=n，转4。
    2.4 执行B op C (即合并已知量)。令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P作标记的叶结点n。置NODE(P)=n，转4。

  3. 删除公共子表达式
    3.1 检查DAG中是否已有一结点，其唯一后继为NODE(B)且标记为op(即公共子表达式)。如果没有，则构造该结点n，否则，把已有的结点作为它的结点并设该结点为n。转4。
    3.2 检查DAG中是否已有一结点，其左后继为NODE(B)，右后继为NODE(C)，且标记为op(即公共子表达式)。如果没有，则构造该结点n，否则，把已有的结点作为它的结点并设该结点为n。转4。

  4. 删除无用赋值
    4.1 如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n;否则，先把A从NODE(A)结点上的附加标识符集中删除(注意，如果NODE(A)是叶结点，则其A标记不删除)。把A附加到新结点n上并置NODE(A)=n。转处理下一四元式。

从DAG中得到的优化信息：
在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符；
在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是DAG各结点上的那些标记或者附加标识符。

3 循环优化

可能反复执行的代码序列的优化称为循环优化。

3.1 循环优化的措施

对循环中的代码，可以实行：
代码外提；
强度消弱；
删除归纳变量(变换循环控制条件)；
循环展开；
循环合并。

3.2 代码外提

所谓变量A在某点d的定值到达另一点u（或称变量A的定值点d到达另一点u），是指流图中从d有一通路到达u且该通路上没有A的其它定值。
循环不变运算：对四元式A:=B op C,若B和C是常数，或者到达它们的B和C的定值点都在循环外；
把循环不变运算提到循环体外。

查找循环中不变运算的算法：
依次查看L中各基本块的每个四元式，如果它的每个运算对象或为常数，或者定值点在 L外，则将此四元式标记为”不变运算”；
重复第3步直至没有新的四元式被标记为”不变运算”为止；
依次查看尚未被标记为”不变运算”的四元式，如果它的每个运算对象或为常数，或定值点在L之外，或只有一个到达-定值点且该点上的四元式已被标记为”不变运算”，则把被查看的四元式标记为”不变运算”。

代码外提

四元式S(A:=B OP C）外提的条件：

  1. S所在的结点是L所有出口结点的必经结点；
  2. A在L中其他地方未再定值；
  3. L中所有A的引用点只有S中的A的定值才能到达。

或

  1. A在离开L后不再是活跃的；
  2. A在L中其他地方未再定值；
  3. L中所有A的引用点只有S中的A的定值才能到达。

代码外提算法：

  1. 求出L的所有不变运算；
  2. 对每个不变运算s:A:=B op C 或 A:=op B 或 A:=B检查是否满足外提的条件；
  3. 按步骤1所找出不变运算的次序，依次把符合步骤2的条件(1)或(2)的不变运算s外提到L的前置结点中。但是，如果s的运算对象(B或C)是在L中定值的，那么，只有当这些定值四元式都已外提到前置结点中时，才能把s也外提到前置结点中。
3.3 强度消弱

强度消弱是把程序中执行时间较长的运算转换为执行时间较短的运算。
强度消弱通常是针对循环控制变量有线性关系的变量赋值进行。
经过强度消弱后，循环中可能出现一些新的无用赋值。
对于消弱下标变量地址计算的强度非常有效。

3.4 删除归纳变量

如果循环中对变量I只有唯一的形如I:=I±C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量；
如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为I的同一线性函数，也即J=C1*I±C2，其中C1和C2都是循环不变量，则称J是归纳变量，并称它与I同族。基本归纳变量也是归纳变量。

删除归纳变量在强度削弱以后进行，强度削弱和删除归纳变量的统一算法框架：

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

第二部分：目标代码生成

4 目标代码生成器

任务：
把分析、翻译、优化后的中间代码变换成目标代码。

输入：
源程序的中间表示，以及符号表中的信息；
类型检查。

输出：
绝对指令代码：能够立即执行的机器语言代码，所有地址已经定位；
可重新定位指令代码：待装配的机器语言模块，执行时，由连接装配程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；
汇编指令代码：需要经过汇编程序转换成可执行的机器语言代码。

5 目标代码生成需要考虑的问题

如何充分利用计算机的指令系统的特点；
如何充分利用计算机的寄存器，减少目标代码中访问存贮单元的次数。在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量；在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。

6 目标机器模型

一个抽象的计算机模型：
具有多个通用寄存器，可用作累加器和变址器；
运算必须在某个寄存器中进行；
含有四种类型的指令形式。

示例：
代码外提

代码外提

代码外提

7 带寄存器分配优化的代码生成

以基本块为单位生成目标代码：
依次把四元式的中间代码变换成目标代码；
在基本块的范围内考虑如何充分利用寄存器；
进入基本块时，所有寄存器空闲；
离开基本块时，把存在寄存器中的现行的值存回主存中，释放所有寄存器；
不特别说明，所有说明变量在基本块出口之后均为非活跃变量。

在一个基本块的范围内考虑充分利用寄存器：

  1. 要做到
    1.1 尽可能留：在生成计算某变量值的目标代码时，尽可能让该变量保留在寄存器中；
    1.2 尽可能用：后续的目标代码尽可能引用变量在寄存器中的值，而不访问内存；
    1.3 及时腾空：在离开基本块时，把存在寄存器中的现行的值放到主存中。
  2. 要知道
    2.1 四元式指令：每条指令中各变量在将来会被使用的情况；
    2.2 变量：每个变量现行值的存放位置；
    2.3 寄存器：每个寄存器当前的使用状况。

8 待用信息和活跃信息

如果在一个基本块内，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其他定值，那么，我们称j是四元式i的变量A的待用信息，即下一个引用点。
变量的符号表登记项中含有记录待用信息和活跃信息的栏。

二元组(x, x)表示变量的待用信息和活跃信息：
第1元：i表示待用信息， ^表示非待用；
第2元：y表示活跃，^表示非活跃；
待用信息和活跃信息的变化(x，x)→(x，x)，用后者更新前者。

计算待用信息和活跃信息的算法：

  1. 把基本块中各变量的符号表中的待用信息栏填为“非待用”，并根据该变量在基本块出口之后是不是活跃的，把其中的活跃信息栏填为“活跃”或“非活跃”；
  2. 从基本块出口到入口由后向前依次处理各个四元式i:A:=B op C：
    2.1 把符号表中变量A的待用信息和活跃信息附加到四元式i上；
    2.2 把符号表中A的待用信息和活跃信息分别置为“非待用”和“非活跃”；
    2.3 把符号表中变量B和C的待用信息和活跃信息附加到四元式i上；
    2.4 把符号表中B和C的待用信息均置为i，活跃信息均置为“活跃”.

9 变量地址描述和寄存器描述

变量地址描述数组AVALUE[A]={R1, R2, A}：动态记录各变量现行值的存放位置。
寄存器描述数组RVALUE[R]={A,B}：动态记录各寄存器的使用信息。

对于四元式A:=B，如果B的现行值在某寄存器Ri中，则无须生成目标代码，只须在RVALUE(Ri)中增加一个A，(即把Ri同时分配给B和A)，并把AVALUE(A)改为Ri。

10 代码生成算法

对每个四元式: i: A:=B op C，依次执行：

  1. 以四元式: i: A:=B op C 为参数，调用函数过程GETREG(i: A:=B op C)，返回一个寄存器R，用作存放A的寄存器。
  2. 利用AVALUE[B]和AVALUE[C]，确定B和C现行值的存放位置B’和C’。如果其现行值在寄存器中，则把寄存器取作B’和C’。
  3. 如果B’≠R，则生成目标代码： 
    1
    2
    LD  R,  B’
    op  R,  C’
    否则生成目标代码 op R, C’。如果B’或C’为R，则删除AVALUE[B]或AVALUE[C]中的R。
  4. 令AVALUE[A]={R}, RVALUE[R]={A}。
  5. 若B或C的现行值在基本块中不再被引用，也不是基本块出口之后的活跃变量，且其现行值在某寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C] 中的Rk ，使得该寄存器不再为B或C占用。

算法中，GETREG(i: A:=B op C) 返回一个用来存放A的值的寄存器。
寄存器分配算法：

  1. (尽可能用B独占的寄存器)如果B的现行值在某个寄存器Ri中，RVALUE[Ri]中只包含B，此外，或者B与A是同一个标识符，或者B的现行值在执行四元式A:=B op C之后不会再引用，则选取Ri为所需要的寄存器R，并转4；
  2. (尽可能用空闲寄存器)如果有尚未分配的寄存器，则从中选取一个Ri为所需要的寄存器R，并转4；
  3. (抢占非空闲寄存器)从已分配的寄存器中选取一个Ri为所需要的寄存器R。最好使得Ri满足以下条件：占用Ri的变量的值也同时存放在该变量的贮存单元中，或者在基本块中要在最远的将来才会引用到或不会引用到。为Ri中的变量生成必要的存数指令；
  4. 给出R，返回。

寄存器分配算法第三步中，生成存数指令算法如下：
对RVALUE[Ri]中每一变量M，如果M不是A，或者如果M是A又是C，但不是B并且B也不在RVALUE[Ri]中，则：

  1. 如果AVALUE[M]不包含M，则生成目标代码 ST Ri，M；
  2. 如果M是B，或者M是C但同时B也在RVALUE[Ri]中，则令AVALUE[M]={M， Ri} ，否则令AVALUE[M]={M}；
  3. 删除RVALUE[Ri]中的M。