编译原理课后答案第五章代码优化.ppt

第五章第五章 代码优化代码优化 第五章第五章 代码优化代码优化 5.1 完成以下选择题：(1)优化可生成 的目标代码。a.运行时间较短 b.占用存储空间较小c.运行时间短但占用内存空间大 d.运行时间短且占用存储空间小第五章第五章 代码优化代码优化 (2)下列 优化方法不是针对循环优化进行的。a.强度削弱 b.删除归纳变量 c.删除多余运算 d.代码外提 (3)基本块内的优化为 。a.代码外提，删除归纳变量 b.删除多余运算，删除无用赋值c.强度削弱，代码外提 d.循环展开，循环合并第五章第五章 代码优化代码优化 (4)在程序流图中，我们称具有下述性质 的结点序列为一个循环。a.它们是非连通的且只有一个入口结点 b.它们是强连通的但有多个入口结点c.它们是非连通的但有多个入口结点 d.它们是强连通的且只有一个入口结点(5)关于必经结点的二元关系，下列叙述中不正确的是 。a.满足自反性 b.满足传递性 c.满足反对称性 d.满足对称性【解答】(1)d (2)c (3)b (4)d (5)d第五章第五章 代码优化代码优化 5.2 何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？【解答】优化根据涉及的程序范围可分为三种。(1)局部优化是指局限于基本块范围内的一种优化。一个基本块是指程序中一组顺序执行的语句序列(或四元式序列)，其中只有一个入口(第一个语句)和一个出口(最后一个语句)。对于一个给定的程序，我们可以把它划分为一系列的基本块，然后在各个基本块范围内分别进行优化。通常应用DAG方法进行局部优化。第五章第五章 代码优化代码优化 (2)循环优化是指对循环中的代码进行优化。例如，如果在循环语句中某些运算结果不随循环的重复执行而改变，那么该运算可以提到循环外，其运算结果仍保持不变，但程序运行的效率却提高了。循环优化包括代码外提、强度削弱、删除归纳变量、循环合并和循环展开。第五章第五章 代码优化代码优化 5.3将下面程序划分为基本块并作出其程序流图。read(A,B)F=1C=A*AD=B*BifC100gotoL2haltL2:F=F-1gotoL1第五章第五章 代码优化代码优化 【解答】先求出四元式程序中各基本块的入口语句，即程序的第一个语句，或者能由条件语句或无条件转移语句转移到的语句，或者条件转移语句的后继语句。然后对求出的每一入口语句构造其所属的基本块，它是由该入口语句至下一入口语句(不包括该入口语句)或转移语句(包括该转移语句)或停语句(包括该停语句)之间的语句序列组成的。凡未被纳入某一基本块的语句都从程序中删除。要注意基本块的核心只有一个入口和一个出口，入口就是其中第一个语句，出口就是其中最后一个语句。如果发现某基本块有两个以上的入口或两个以上的出口，则划分基本块有误。第五章第五章 代码优化代码优化 程序流图画法是当下述条件(1)和(2)有一个成立时，从结点i有一有向边引到结点j：(1)基本块j在程序中的位置紧跟在基本块i之后，并且基本块i的出口语句不是无条件转移语句goto(s)或停语句。(2)基本块i的出口语句是goto(s)或ifgoto(s)，并且(s)是基本块j的入口语句。应用上述方法求出本题所给程序的基本块及程序流图见图5-1，图中的有向边、实线是按流图画法(1)画出的，虚线是按流图画法(2)画出的。第五章第五章 代码优化代码优化 图5-1程序流图第五章第五章 代码优化代码优化 5.4 基本块的DAG如图5-2所示。若：(1)b在该基本块出口处不活跃；(2)b在该基本块出口处活跃；请分别给出下列代码经过优化之后的代码：(1)a=b+c(2)b=a-d (3)c=b+c(4)d=a-d第五章第五章 代码优化代码优化 图5-2习题5.4的DAG图第五章第五章 代码优化代码优化 【解答】(1)当b在出口处不活跃时，生成优化后的代码为 a=b0+c0 d=a-d0 c=d+c0 (2)当b在出口活跃时，生成优化后的代码为 a=b0+c0 b=a-d0 d=b c=d+c0第五章第五章 代码优化代码优化 5.5 对于基本块P：S0=2S1=3/S0S2=T-CS3=T+CR=S0/S3H=RS4=3/S1S5=T+CS6=S4/S5H=S6*S2第五章第五章 代码优化代码优化 (1)应用DAG对该基本块进行优化；(2)假定只有R、H在基本块出口是活跃的，试写出优化后的四元式序列。【解答】(1)根据DAG图得到优化后的四元式序列为S0=2S4=2S1=1.5S2=T-C第五章第五章 代码优化代码优化 S3=T+CS5=S3R=2/S3S6=RH=S6*S2(2)若只有R、H在基本块出口是活跃的，优化后的四元式序列为S2=T-CS3=T+CR=2/S3H=R*S2第五章第五章 代码优化代码优化 5.6 试画出如下中间代码序列的程序流图，并求出：(1)各结点的必经结点集合D(n)；(2)流图中的回边与循环。J=0L1：I=0if I 8 goto L3L2：A=B+CB=D*C第五章第五章 代码优化代码优化 L3：if B=0 goto L4writeBgotoL5L4：I=I+1ifI8gotoL2L5：J=J+1ifJ=3gotoL1halt第五章第五章 代码优化代码优化 【解答】(1)各结点的必经结点集分别为D(n0)=n0D(n1)=n0,n1D(n2)=n0,n1,n2D(n3)=n0,n1,n3D(n4)=n0,n1,n3,n4D(n5)=n0,n1,n3,n5D(n6)=n0,n1,n3,n6D(n7)=n0,n1,n3,n6,n7程序流图如图5-3所示。第五章第五章 代码优化代码优化 图5-3习题5.6的程序流图第五章第五章 代码优化代码优化 由于有n5n2和n6n1，而n2不是n5的必经结点，n1是n6的必经结点，所以n6n1为回边；即该回边表示的循环为 n1,n2,n3,n4,n5,n6，入口结点为n1，出口结点为n6。5.7 证明：如果已知有向边nd是一回边，则由结点d、结点n以及有通路到达n而该通路不经过d的所有结点组成一个循环。【解答】根据题意画出示意图，如图5-4所示。第五章第五章 代码优化代码优化 图5-4具有回边nd的流图第五章第五章 代码优化代码优化 证明过程如下：(1)令结点d、结点n以及有通路到达n而该通路不经过d的所有结点构成集合L(即图5-4中的全部结点)，则L必定是强连通的。为了证明这一点，令M=L-d,n。由L的组成成分可知M中每一结点ni都可以不经过d而到达n。又因d DOM n(已知nd为回边，由回边定义知必有d DOM n)，所以必有d DOM ni，如图5-4所示。如不然，则从首结点就可以不经过d而到达ni，从而也可以不经过d到达n，这与d DOM n矛盾。因d DOM ni第五章第五章 代码优化代码优化 所以d必有通路到达M中任一结点ni，而M中任一结点又可以通过n到达d(nd为回边)，从而M中任意两个结点之间必有一通路，L中任意两个结点之间亦必有一通路。此外，由M中结点性质可知：d到M中任一结点ni的通路上所有结点都应属于M，ni到n的通路上所有结点也都属于M。因此，L中任意两结点间通路上所有结点都属于L，也即，L是强连通的。第五章第五章 代码优化代码优化 (2)因为对所有niL，都有d DOM ni，所以d必为L的一个入口结点。我们说d也一定是L的唯一入口结点。如不然，必有另一入口结点d1L且d1d。d1不可能是首结点，否则d DOM n不成立(因为有d DOM d1，如果d1是首结点，则d就是首结点d1的必经结点，则只能是d=d1，与dd1矛盾)。现设d1不是首结点，且设d1在L之外的前 驱 是 d2，那 么，d2和 n之 间 必 有 一 条 通 路d2d1n，且该通路不经过d，从而d2应属于M，这与d2L矛盾。所以不可能存在上述结点d1，也即d是循环的唯一入口结点。至此，我们已经满足了循环的定义：循环是程序流图中具有唯一入口结点的强连通子图，也即，L是包含回边nd的循环，d是循环的唯一入口结点。第五章第五章 代码优化代码优化 5.8 对下面四元式代码序列：A=0 I=1 L1:B=J+1 C=B+I A=C+A if I=100 goto L2 I=I+1 goto L1 L2:write A halt第五章第五章 代码优化代码优化 (1)画出其控制流程图；(2)求出循环并进行循环的代码外提和强度削弱优化。【解答】(1)在构造程序的基本块的基础上画出该程序的流图，如图5-5所示。第五章第五章 代码优化代码优化 图5-5习题5.8的程序流图第五章第五章 代码优化代码优化 (2)很容易看出，B3B2是流图中的一条有向边，并且有B2 DOM B3，故B3B2为流图中的一条回边。循环可通过回边求得，即找出由结点B2、结点B3以及有通路到达B3但不经过B2的所有结点。所以，由回边组成的B3B2循环是 B2，B3。进行代码外提就是将循环中的不变运算外提到循环入口结点前新设置的循环前置结点中。经检查，找出的不变运算为B2中的B=J+1。因此，代码外提后的程序流图如图5-6所示。第五章第五章 代码优化代码优化 图5-6习题5.8中代码外提后的程序流图第五章第五章 代码优化代码优化 我们知道，强度削弱不仅可对乘法运算进行，也可对加法运算进行。由于本题中的四元式程序不存在乘法运算，所以只能进行加法运算的强度削弱。从图5-5中可以看到，B2中的C=B+I，变量B因代码外提其定值点已在循环之外，故相当于常数。而另一加数I值由B3中的I=I+1决定，即每循环一次I值增1；也即每循环一次，B2中的C=B+I其C值增量与B3中的I相同，即常数1。因此，我们可以对C进行强度削弱，即将B2中的四元式C=B+I外提到前置结点B2中，同时在B3中I=I+1之后给C增加一个常量1。进行强度削弱后的结果如图5-7所示。第五章第五章 代码优化代码优化 图5-7习题5.8中强度削弱后的程序流图第五章第五章 代码优化代码优化 5.9 某程序流图如图5-8所示。(1)给出该流图中的循环；(2)指出循环不变运算；(3)指出哪些循环不变运算可以外提。第五章第五章 代码优化代码优化 图5-8习题5.9的程序流图第五章第五章 代码优化代码优化 【解答】(1)流图中的循环为B2,B3,B4。(2)B3中的i=2是循环不变运算。(3)循环不变运算外提的条件是：该不变运算所在的结点是循环所有出口结点的必经结点；当把循环不变运算A=B op C(B或op C可以没有)外提时，要求循环中其他地方不再有A的定值点；当把循环不变运算A=B op C外提时，要求循环中A的所有引用点都是而且仅仅是这个定值所能到达的。由于i=2所在的结点不是循环所有出口结点的必经结点，故不能外提。第五章第五章 代码优化代码优化 5.10 一程序流图如图5-9所示，试分别对其进行代码外提、强度削弱和删除归纳变量等优化。第五章第五章 代码优化代码优化 图5-9习题5.10的程序流图第五章第五章 代码优化代码优化 【解答】由图5-9可知，B5B4与B6B2为流图的有向边，从而有D(B5)=B1，B2，B3，B4，B5D(B6)=B1，B2，B3，B4，B6故有B4 DOM B5和B2 DOM B6，因此B5B4和B6B2为回边(其余都不是回边)，即分别组成了循环B4，B5、B2，B3，B4，B5，B6。对循环B4，B5、B2，B3，B4，B5，B6进行代码外提、强度削弱和删除归纳变量等优化后，其优化后的程序流图如图5-10所示。第五章第五章 代码优化代码优化 图5-10习题5.10中优化后的程序流图