编译原理第十一章

1、2 优化：是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。 编译程序的优化工作旨在生成较好性能的目标代码，为此，编译程序需要对代码（中间代码或目标代码）进行各种方式的变换 变换的宗旨是：等价-经优化工作变换后的代码运行结果应与原来程序运行结果一样。 3 优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行 中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，在很大程度上依赖于具体的机器 4 依据优化所涉及的程序范围，可分为三个不同的级别。 局部优化指的是在只有一个入口、一个出口的基本程序块

2、上进行的优化。 循环优化是对循环中的代码进行的优化。 全局优化是在整个程序范围内进行的优化。 5 常用的优化技术有： 删除多余运算，循环不变代码外提， 强度削弱，变换循环控制条件， 合并已知量与复写传播 删除无用赋值。 举例6 P =0for I =1 to 20 doP =P+AI*BI;假定每个元素占假定每个元素占4个字长编址个字长编址 经过编译得到的中间代码如图经过编译得到的中间代码如图 7 删除多余运算（删除公共子表达式）删除多余运算（删除公共子表达式） 代码外提代码外提 89 强度削弱强度削弱 ： 10 变换循环控制条件：变换循环控制条件： 合并已知量与复写传播合并已知量与复写传播

3、四元式（四元式（3）可变为）可变为T14 四元式四元式(6)把把T1的值复写到的值复写到T4中，四元式（中，四元式（8）要）要引用引用T4的值，而从四元式（的值，而从四元式（6）到四元式（）到四元式（8）之）之间未改变间未改变T4和和T1的值，则将四元式（的值，则将四元式（8）改为）改为T6 =T5T11112 删除无用赋值删除无用赋值 （6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I 13局部优化局部优化 指基本块内的优化 是指程序中一个顺序执行的语句序列，其中只有一个入口语句和一个出口语句。控制流只能从其入口语句进入，从其出口语句退出,没有中途停止或分

4、支 局部优化工作包括对于一个给定的程序，把它划分为一系列的基本块,在各个基本块范围内分别进行优化 如何分基本块？如何分基本块？14基本块的划分基本块的划分 先定义基本块的入口语句： 程序的第一个语句；或者， 条件转移语句或无条件转移语句的 转移目标语句；或者， 紧跟在条件转移语句后面的语句。 15划分中间代码（四元式程序）为基本块的算法 其步骤如下： 求出四元式程序中各个基本块的入口语句。 对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。 凡未被纳入某一基本块的语句、都

5、是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。 16(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(5) if B= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt语句（1）是程序的第一个语句，因此它是入口语句。语句（4）和语句（8）是条件转移语句或无条件转移语句的转移目标语句，因此是入口语句。语句（6）是紧跟在条件转移语句后面的语句，因此是入口语句。语句（1），（2）和（3）构成一个基本块，语句（4）和（5）构成一个基本块，语句（6）和（7）构成一个基本

6、块，语句（8）和（9）构成一个基本块。 17基本块内的优化变换 两类重要的局部等价变换可用于基本块：保结构的变换和代数变换 18 有四元式程序：t1 := 4 - 2t2 := t1 /2 t3 := a * t2t4 := t3 * t1t5 := b + t4c := t5 * t519 进行合并已知量变换后得到：t1 := 2t2 := t1 /2 t3 := a * t2t4 := t3 * t1t5 := b + t4c := t5 * t520 再进行复写传播和删除无用赋值等变换后得到：t2 := 2 /2 t3 := a * t2t4 := t3 * 2t5 := b + t4c

7、 := t5 * t521 再进行合并已知量变换后得到：t2 := 1 t3 := a * t2t4 := t3 * 2t5 := b + t4c := t5 * t5 22 再进行复写传播和删除无用赋值等变换后得到：t3 := a * 1t4 := t3 * 2t5 := b + t4c := t5 * t5接着使用代数变换后有：t3 := at4 := t3 * 2t5 := b + t4c := t5 * t523 使用复写传播和删除无用赋值变换后又有：t4 := a * 2t5 := b + t4c := t5 * t5再使用代数变换：t4 := a + at5 := b + t4c

8、:= t5 * t524 重新命名临时变量：t1 := a + at5 := b + t1c := t5 * t5还可减少临时变量：t1 := a + at1 := b + t1c := t1 * t1 OK25基本块的基本块的DAG表示表示 一个有向图中，我们称任一有向边ninj(或表示为有序对（ni，nj）)中的结点ni为结点nj的前驱（父结），结点nj为结点ni的后继（子结）。 任一有向边序列n1n2，n2n3，nk-1nk为从结点n1到结点nk的一条通路 。如果其中n1nk，则称该通路为环路 如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG 2627 此处要用到的

9、有向图，是一种其结点带有下述标记或附其结点带有下述标记或附加信息的加信息的DAG： 图的，即无后继的结点，以一标识符（变量名）或常数作为标记，表示这个结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为这个结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。 图的，即有后继的结点,以一运算符作为标记，表示这个结点代表应用该运算符对其后继结点所代表的值进行运算的结果。 图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 28 这种DAG可用来描述计算过程，又称为描述计算过程的DAG 一个基本块，可用一个DAG来表示。

10、下图列出各种四元式及相对应的DAG的结点形式。图中ni为结点编号，结点下面的符号（运算符、标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。 29（0）A：=B （：（：=，B，-，A） （1）A：=op B （op，B，-，A） （2）A：=B op C （op，B，C，A） 30 假设DAG各结点信息将用某种适当的数据结构来存放。并设有一个标识符（包括常数）与结点的对应表。NODE（A）是描述这种对应关系的一个函数，它的值或者是一个结点的编号n，或者无定义。前一个情况代表DAG中存在一个结点n，A是其上的标记或附加标识符。 31下面是仅含0，1，2型四元式的基本块的DAG

11、构造算法。 首先，首先，DAG为空。为空。对基本块的每一四元式，依次执行：对基本块的每一四元式，依次执行：1 如果如果NODE（B）无定义，则构造一标记为）无定义，则构造一标记为B的叶结点并定的叶结点并定义义NODE（B）为这个结点；）为这个结点；如果当前四元式是如果当前四元式是0型，则记型，则记NODE（B）的值为）的值为n，转，转4。如果当前四元式是如果当前四元式是1型，则转型，则转2.（1）。）。如果当前四元式是如果当前四元式是2型，则：（型，则：（）如果）如果NODE（C）无定义，）无定义，则构造一标记为则构造一标记为C的叶结点并定义的叶结点并定义NODE（C）为这个结点，（）为这个结

12、点，（）转转2.（2）。）。2 （1） 如果如果NODE（B）是标记为常数的叶结点，则转）是标记为常数的叶结点，则转2.（3），），否则转否则转3.（1）。）。（2） 如果如果NODE（B）和）和NODE（C）都是标记为常数的叶结）都是标记为常数的叶结点，则转点，则转2.（4），否则转），否则转3.（2）。）。（3） 执行执行opB（即合并已知量），令得到的新常数为（即合并已知量），令得到的新常数为P。如。如果果NODE（B）是处理当前四元式时新构造出来的结点，则删除它。）是处理当前四元式时新构造出来的结点，则删除它。如果如果NODE（P）无定义，则构造一用）无定义，则构造一用P做标记的叶结点

13、做标记的叶结点n。置。置NODE（P）n，转，转4.。（4） 执行执行BopC(即合并已知量即合并已知量)，令得到的新常数为，令得到的新常数为P。如。如果果NODE（B）或）或NODE（C）是处理当前四元式时新构造出来的结）是处理当前四元式时新构造出来的结点，则删除它。如果点，则删除它。如果NODE（P）无定义，则构造一用）无定义，则构造一用P做标记的叶做标记的叶结点结点n。置。置NODE（P）n，转，转4.。 32 3（1） 检查检查DAG中是否已有一结点，其唯一后继为中是否已有一结点，其唯一后继为NODE（B），且标记为），且标记为op（即找公共子表达式）。如果（即找公共子表达式）。如果没

14、有，则构造该结点没有，则构造该结点n，否则就把已有的结点作为它的结，否则就把已有的结点作为它的结点并设该结点为点并设该结点为n，转，转4.。（2） 检查检查DAG中是否已有一结点，其左后继为中是否已有一结点，其左后继为NODE（B），右后继为），右后继为NODE（C），且标记为），且标记为op(即找即找公共子表达式公共子表达式)。如果没有，则构造该结点。如果没有，则构造该结点n，否则就把，否则就把已有的结点作为它的结点并设该结点为已有的结点作为它的结点并设该结点为n。转。转4.。4如果如果NODE（A）无定义，则把）无定义，则把A附加在结点附加在结点n上上并令并令NODE（A）n；否则先把；否

15、则先把A从从NODE（A）结点上）结点上的附加标识符集中删除（注意，如果的附加标识符集中删除（注意，如果NODE（A）是叶结）是叶结点，则其标记点，则其标记A不删除），把不删除），把A附加到新结点附加到新结点n上并令上并令NODE（A）n。转处理下一四元式。转处理下一四元式。 33 例 试构造以下基本块G的DAG。(1) T0 =3.14(2) T1 =2 * T0(3) T2 =R + r(4) A =T1 * T2(5) B =A(6) T3 =2 * T0(7) T4 =R + r(8) T5 =T3 * T4(9) T6 =R - r(10) B =T5 * T6 3435 将图11.

16、10（k）的基本块G的DAG按原来构造其结点的顺序，重新写成四元式，得到以下的四元式序列G G: (1) T0 =3.14(2) T1 =6.28(3) T3 =6.28(4) T2 =R+r(5) T4 =T2(6) A =6.28*T2(7) T5 =A(8) T6 =R-r(9) B =A*T6原来：G (1) T0 =3.14(2) T1 =2 * T0(3) T2 =R + r(4) A =T1 * T2(5) B =A(6) T3 =2 * T0(7) T4 =R + r(8) T5 =T3 * T4(9) T6 =R - r(10) B =T5 * T6 1 G中的代码（2）和（

17、6）的已知量都已合并。2 G中（5）的无用赋值已被删除。3 G中（3）和（7）的公共子表达式R+r只被计算一次，删除了多余运算。所以G是G的优化结果。 36控制流分析和循环优化 循环中的代码反复执行，因而为了提高目标代码的效率必须着重考虑循环的代码优化。 进行循环优化必须找出程序中的循环，这就需要对程序的控制流程进行分析 37控制流程图 一个控制流程图就是具有唯一首结点的有向图。 首结点就是从它开始到控制流程图中任何结点都有一条通路的结点。 把一个控制流程图表示成一个三元组G（N，E，n0），其中，N代表图中所有结点集，E代表图中所有有向边集，n0代表首结点。 控制流程图简称为流图流图。38

18、一个程序可用一个流图来表示。流图中的有限结点集N就是程序的基本块集，流图中的结点就是程序中的基本块。流图的首结点就是包含程序第一个语句的基本块。 程序流图中的有向边集E是这样构成的：假设流图中结点i和结点j分别对应于程序的基本块i和基本块j，则当下述条件1)或2)有一个成立时，从结点i有一有向边引向结点j：1). 基本块j在程序中的位置紧跟在基本块i之后，并且基本块的出口语句不是无条件转移语句goto（s）或停语句。2). 基本块i的出口语句是goto（s）或ifgoto（s），并且（s）是基本块j的入口语句。 39 (1) read x(2) read y(3) r =x mod y(4)

19、if r=0 goto (8)(5) x =y(6) y =r(7) goto (3)(8) write y(9) halt 4041流图的简洁表示42 在程序流图中，我们称具有下列性质的结点序列在程序流图中，我们称具有下列性质的结点序列为一个循环：为一个循环： 它们是强连通的。也即，其中任意两个结它们是强连通的。也即，其中任意两个结点之间，必有一条通路，而且该通路上各结点都点之间，必有一条通路，而且该通路上各结点都属于该结点序列。如果序列只包含一个结点，则属于该结点序列。如果序列只包含一个结点，则必有一有向边从该结点引到其自身。必有一有向边从该结点引到其自身。 它们中间有且只有一个是入口结点

20、。所谓它们中间有且只有一个是入口结点。所谓入口结点，是指序列中具有下述性质的结点：入口结点，是指序列中具有下述性质的结点：从序列外某结点，有一有向边引到它，或者从序列外某结点，有一有向边引到它，或者它就是程序流图的首结点。它就是程序流图的首结点。因此，我们定义的循环就是程序流图中具有因此，我们定义的循环就是程序流图中具有唯一入口结点的强连通子图，从循环外要进入循唯一入口结点的强连通子图，从循环外要进入循环，必须首先经环，必须首先经过循环的入口结点。 43 在程序流图中，对任意两个结点m和n，如果从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点， 记为m DOM n。流图中结

21、点n的所有必经结点的集合，称为结点n的必经结点集， 记为D（n）。 循环的入口结点是循环中所有结点的必经结点。44 D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,745循环的查找算法循环的查找算法 假设ab是流图中的一条有向边，如果b DOM a，则称ab是流图中的一条回边。 如果已知有向边nd是回边，那么就可以求出由它组成的循环。该循环就是由结点d、结点n以及有通路到达n而该通路不经过d的所有结点组成，并且d是该循环的唯一入口结点。 46 有向边66、74、42是回边。因为根据前例的结果有6 DOM

22、6，4 DOM 7，2 DOM 4，其它有向边都不是回边。 对于例子，由回边66组成的循环就是6,由回边74组成的循环是4，5，6，7；由回边42组成的循环是2，3，4，5，6，7。 47循环优化循环优化 循环优化的三种重要技术是代码外提代码外提；删删除归纳变量除归纳变量和强度削弱强度削弱。 只对代码外提再进行一些讨论 48 代码外提代码外提 这种变换把循环不变运算，即产生的结果独立于循环执行次数的表达式，放到循环的前面 所讨论的循环只存在一个入口。实行代码外提时，在循环的入口结点前面建立一个新结点（基本块），称之为循环的前置结点。循环的前置结点以循环的入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点 4950 前置结点也是唯一的,循环中外提的代码将全部提至前置结点中 EG 是否在任何情况下，都可把循环不变运算是否在任何情况下，都可把循环不变运算外提呢外提呢