编译原理 第八部分

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

所谓有效，无非从时间和空间两个因素来考虑，即使得变换之后的程序运行速度更快、占用存储空间更少，这两个因素需要均衡考虑

目标代码生成是编译的最后一个阶段。目标代码生成器把语法分析后或优化后的中间代码变换成目标代码。

目标代码（object code）指计算机科学中编译器或汇编器处理源代码后所生成的代码，它一般由机器代码或接近于机器语言的代码组成。

优化的分类；

代码优化的分类

根据代码优化是否涉及具体的计算机来划分，代码优化可分为两大类

一类是与机器有关的优化，这类优化一般在目标代码上进行，需要依赖于具体的机器。具体的有对寄存器优化、多处理机的优化、特殊指令的优化等

另一类是与机器无关的优化，在中间代码上进行

据代码优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别

局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化

循环优化是对循环中的代码进行的优化，在一个程序运行时，相当多的一部分时间会花在循环上，因此，基于循环的优化非常重要。

全局优化是在整个程序范围内进行的优化

代码优化的目的是为了产生效率更高的代码。编译程序中的代码优化阶段提供的对代码的各种变换必须遵循一定的原则。

如果一个表达式E在前面已经计算过，并且在这之后E中变量的值没有改变，则称E为公共子表达式，是指在一个基本程序块内计算结果相同的子表达式。

对相同的子表达式只在第一次出现时计算并且仅计算一次，其结果暂存入Ti，而不必重复计算，这样既节约了空间，又节省了时间。这种优化称为删除公共子表达式，也称为删除多余运算

代码外提是指将循环中的不变运算提到循环体前面

处在循环体内的不变运算，不论循环体重复执行多少次都不影响其计算结果，这样的运算只会浪费代码执行时间

因此将这类运算提到循环体外并不影响程序运行结果，还可加快代码执行速度

强度削弱是指用执行效率较高的操作等价地替换原操作

对于非算术运算可削弱强度，如尽量使用寄存器，少访问内存（或外存）等

对中间代码级的运算尽可能降低运算级别

for循环中，控制变量i的作用域是本循环体。如果在循环体内存在一个变量（或临时变量）T与循环控制变量i保持线性关系，同时在循环的后面不引用i，而删去i又不影响程序结果，则可由T取代i的控制循环次数的作用。从循环中删除i，这种方法称为变换循环控制条件，或者称为删除归纳变量。

已知量是指常数或在编译时就能确定其值的变量

合并已知量是指在编译时就将源程序中关于已知量的表达式之值先行算出，不必生成计算该表达式的代码

复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值，也不影响其运行结果的变量。

变量的最后一次引用到下次引用之前的最近一次赋值期间，可视为无用变量

在变量的无用期内，对它的任何赋值均可删除。对于那些被赋值后从未被引用的变量，对其进行赋值操作也是无用赋值，可删除

删除无用赋值语句可以减少程序中的无用的变量，还可以使代码更简洁

示例：

局部优化（local）是指基本块内的优化。

对于给定的程序，我们可以把它划分为一系列的基本块。在各个基本块的范围内，分别进行优化。局限在基本块范围内的优化称为基本块内的优化，或者称为局部优化。

所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出，不存在跳转和分叉汇合的情况。

第一步：确定四元式程序（中间代码）中各个基本块的人口语句

所谓入口语句，严格地说来就是下述语句之一：

程序的第一个语句；

能够由条件转移语句或无条件转移语句转移到的目标语句；

紧跟在条件转移语句后面的语句。

第二步：对每一入口语句，构造其所属的基本块

下述条件之一：

由该入口语句到下一入口语句(不包括下一入口语句) 之间的所有语句序列组成一个基本块；

由该入口语句到一转移语句(包括该转移语句)之间的所有语句序列组成一个基本块；

由该入口语句到一停语句(包括该停语句)之间的所有语句序列组成的一个基本块。

第三步：凡未被纳入某一基本块的语句，都是程序中控制流程无法达到的语句，因而也是不会被执行到的语句，我们可以把它们删除

DAG（Directed Acyclic Graph）即无环有向图，它是有向图中的一种，通常用来对基本块进行优化。

这种有向图是一种其结点带有下述标记或附加信息的DAG：

1．图的叶结点(即没有后继的结点)以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。

2．图的内部结点（即有后继的结点）以一运算符作为标记，表示该节点代表应用该运算符对其后继结点所代表的值进行运算的结果。

3．图中各个结点可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。

一个基本块，可用一个DAG来表示。可以利用DAG来描述四元式，如图所示，列出了各种四元式以及相对应的DAG的结点形式。图中为结点编号，结点下面的符号（运算符，标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。

​

假设DAG各结点信息将用某种适当的数据结构来存放。并设有一个标识符（包括常数）A与结点NODE(A)的对应表，即用大写字母――A，B等表示四元式中的变量名或常数。NODE(A)是描述这种对应关系的一个函数，即用NODE(A)表示A在DAG中的相应结点，它的值可以是一个结点的编号n或者无定义。NODE(A)＝n代表DAG中存在一个结点n，A是其上的标记或附加标识符

把各种形式的四元式按其对应结点的后继个数分为四类。其中：

0型四元式：有0个后继结点，如四元式(0)；

1型四元式：有1个后继结点，如四元式(1) ；

2型四元式：有2个后继结点，如四元式(2) 、 (3) 和(4) ；

3型四元式：有3个后继结点，如四元式(5)

初始时，DAG为空。

对基本块中的每一条四元式，依次执行以下步骤：

1.如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点；

2.

3.

4.

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

将四元式表示成相应的DAG后，可以利用DAG来进行优化。

利用基本块来进行优化的主要思想是： 首先将一个基本块中的每一个四元式依次表示成对应的DAG，再将这些DAG合成对于一个较大的DAG，即为该基本块的DAG。然后按照构造DAG结点的顺序重写四元式序列，就可以得到经过“合并已知量”、“删除无用赋值”、“删除公共子表达式”的等价的基本块，即为优化后的基本块。

示例：

在程序设计语言中，循环是必不可少的控制结构之一。所谓循环，粗略地说，就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，因而为了提高目标代码的效率必须着重考虑循环的代码优化。

循环优化是指在循环体中进行的专项优化，是提高程序运行效率的主要途径。因为在一个执行n次的循环体内进行一项优化，从运行效率上来说，相当于进行了n项优化。

为了进行循环优化，首先必须找出程序中的循环，为找出程序中的循环，就需要对程序的控制流程进行分析。我们将使用程序的控制流程图对所讨论的循环给出定义，并介绍怎样从程序的控制流程图中找出程序的循环。

对循环中的代码段，可以进行代码外提、强度削弱和删除归纳变量等优化。

一个控制流程图就是具有唯一首结点的有向图。

所谓首结点，就是从它开始到控制流程图中任何结点都有一条通路的结点。

一个控制流程图表示成一个三元组G＝(N，E，n0)，其中，N代表图中所有结点集，E代表图中所有有向边集，n0代表首结点。以下把控制流程图简称为流图。

一个程序可用一个流图来表示。流图中的有限结点集N就是程序的基本块集，流图中的结点就是程序中的基本块。流图的首结点就是包含程序第一个语句的基本块。

程序流图中的有向边集E是这样构成的：

假设流图中结点i和结点j分别对应于程序的基本块i和基本块j，则当下述条件1.或2.有一个成立时，从结点i有一有向边引向结点j：

1.基本块j在程序中的位置紧跟在基本块i之后，并且基本块i的出口语句不是无条件转移语句goto(s)或停语句。

2．基本块i的出口语句是goto(s)或if…goto(s)，并且(s)是基本块j的入口语句。

示例：

循环的定义

在流图中,称具有下列性质的结点序列为一个循环：

循环就是流图中具有唯一入口结点的强连通子图，从循环外要进入循环，必须首先经过循环的入口结点。

循环的查找

为了查找循环，需对程序流图中各结点的控制关系进行分析，即利用控制点（dominator）查找循环

循环优化方法

代码外提

减少循环中程序代码数目的一个重要办法是代码外提。这种变换把循环不变运算，即运算产生的结果不受循环执行次数影响的表达式，放到循环的前面

实行代码外提时，在循环的入口结点前面建立一个新结点(基本块)，称之为循环的前置结点。循环的前置结点以循环的入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点

强度削弱

强度削弱是指把程序中执行时间较长的运算替换为执行时间较短的运算。例如把循环中的乘法运算用递归加法运算来实现

删除归纳变量

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

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

删除归纳变量是在强度削弱之后进行的

代码生成要考虑的主要问题

目标代码的三种形式

机器指令形式(op source ,destination)

ADD s,d //d+s ? dSUB s,d //d-s ? dMOV s,d //s ? d

欢迎关注我的其它发布渠道