编译原理课后答案 第五章 代码优化.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=1,C=A*A,D=B*B,if C100,goto,L,2,halt,L,2:,F=F-1,goto,L,1,【解答】,先求出四元式程序中各基本块的入口语句，即程序的第一个语句，或者能由条件语句或无条件转移语句转移到的语句，或者条件转移语句的后继语句。然后对求出的每一入口语句构造其所属的基本块，它是由该入口语句至下一入口语句(不包括该入口语句)或转移语句(包括该转移语句)或停语句(包括该停语句)之间的语句序列组成的。凡未被纳入某一基本块的语句都从程序中删除。要注意基本块的核心只有一个入口和一个出口，入口就是其中第一个语句，出口就是其中最后一个语句。如果发现某基本块有两个以上的入口或两个以上的出口，则划分基本块有误。,程序流图画法是当下述条件(1)和(2)有一个成立时，从结点,i,有一有向边引到结点,j：,(1),基本块,j,在程序中的位置紧跟在基本块,i,之后，并且基本块,i,的出口语句不是无条件转移语句,goto,(s),或停语句。,(2)基本块,i,的出口语句是,goto,(s),或,if,goto,(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=b,0,+c,0,d=a,-,d,0,c=d+c,0,(2),当,b,在出口活跃时，生成优化后的代码为,a=b,0,+c,0,b=a,-,d,0,d=b,c=d+c,0,5.5,对于基本块,P,：,S,0,=2,S,1,=3/S,0,S,2,=T,-,C,S,3,=T+C,R=S,0,/S,3,H=R,S,4,=3/S,1,S,5,=T+C,S,6,=S,4,/S,5,H=S,6,*S,2,(1),应用,DAG,对该基本块进行优化；,(2),假定只有,R,、,H,在基本块出口是活跃的，试写出优化后的四元式序列。,【解答】,(1),根据,DAG,图得到优化后的四元式序列为,S,0,=2,S,4,=2,S,1,=1.5,S,2,=T,-,C,S,3,=T+C,S,5,=S,3,R=2/S,3,S,6,=R,H=S,6,*S,2,(2),若只有,R,、,H,在基本块出口是活跃的，优化后的四元式序列为,S,2,=T,-,C,S,3,=T+C,R=2/S,3,H=R*S,2,5.6,试画出如下中间代码序列的程序流图，并求出：,(1),各结点的必经结点集合,D(n),；,(2),流图中的回边与循环。,J=0,L,1,：,I=0,if I 8,goto,L,3,L,2,：,A=B+C,B=D*C,L,3,：,if B=0,goto,L,4,write B,goto,L,5,L,4,：,I=I+1,if I8,goto,L,2,L,5,：,J=J+1,if J=3,goto,L,1,halt,【解答】,(1),各结点的必经结点集分别为,D(n,0,)=n,0,D(n,1,)=n,0,n,1,D(n,2,)=n,0,n,1,n,2,D(n,3,)=n,0,n,1,n,3,D(n,4,)=n,0,n,1,n,3,n,4,D(n,5,)=n,0,n,1,n,3,n,5,D(n,6,)=n,0,n,1,n,3,n,6,D(n,7,)=n,0,n,1,n,3,n,6,n,7,程序流图如图,5-3,所示。,图,5-3,习题,5.6,的程序流图,由于有,n,5,n,2,和,n,6,n,1,，,而,n,2,不是,n,5,的必经结点，,n,1,是,n,6,的必经结点，所以,n,6,n,1,为回边；即该回边表示的循环为,n,1,n,2,n,3,n,4,n,5,n,6,，,入口结点为,n,1,，,出口结点为,n,6,。,5.7,证明：如果已知有向边,n,d,是一回边，则由结点,d,、,结点,n,以及有通路到达,n,而该通路不经过,d,的所有结点组成一个循环。,【解答】,根据题意画出示意图，如图,5-4,所示。,图,5-4,具有回边,n,d,的流图,证明过程如下：,(1),令结点,d,、,结点,n,以及有通路到达,n,而该通路不经过,d,的所有结点构成集合,L(,即图,5-4,中的全部结点,),，则,L,必定是强连通的。为了证明这一点，令,M=L,-,d,n,。,由,L,的组成成分可知,M,中每一结点,n,i,都可以不经过,d,而到达,n,。,又因,d DOM n(,已知,n,d,为回边，由回边定义知必有,d DOM n),，,所以必有,d DOM,n,i,，,如图,5-4,所示。如不然，则从首结点就可以不经过,d,而到达,n,i,，,从而也可以不经过,d,到达,n,，,这与,d DOM n,矛盾。因,d DOM,n,i,所以,d,必有通路到达,M,中任一结点,n,i,，,而,M,中任一结点又可以通过,n,到达,d(n,d,为回边,),，从而,M,中任意两个结点之间必有一通路，,L,中任意两个结点之间亦必有一通路。此外，由,M,中结点性质可知：,d,到,M,中任一结点,n,i,的通路上所有结点都应属于,M,，,n,i,到,n,的通路上所有结点也都属于,M,。,因此，,L,中任意两结点间通路上所有结点都属于,L,，,也即，,L,是强连通的。,(2),因为对所有,n,i,L,，,都有,d DOM,n,i,，,所以,d,必为,L,的一个入口结点。我们说,d,也一定是,L,的唯一入口结点。如不然，必有另一入口结点,d,1,L,且,d,1,d,。,d,1,不可能是首结点，否则,d DOM n,不成立,(,因为有,d DOM d,1,，,如果,d,1,是首结点，则,d,就是首结点,d,1,的必经结点，则只能是,d=d,1,，,与,d,d,1,矛盾,),。现设,d,1,不是首结点，且设,d,1,在,L,之外的前驱是,d,2,，,那么，,d,2,和,n,之间必有一条通路,d,2,d,1,n,，,且该通路不经过,d,，,从而,d,2,应属于,M,，,这与,d,2,L,矛盾。所以不可能存在上述结点,d,1,，,也即,d,是循环的唯一入口结点。,至此，我们已经满足了循环的定义：循环是程序流图中具有唯一入口结点的强连通子图，也即，,L,是包含回边,n,d,的循环，,d,是循环的唯一入口结点。,5.8,对下面四元式代码序列：,A=0,I=1,L,1,:B=J+1,C=B+I,A=C+A,if I=100,goto,L,2,I=I+1,goto,L,1,L,2,:,write A,halt,(1),画出其控制流程图；,(2),求出循环并进行循环的代码外提和强度削弱优化。,【解答】,(1),在构造程序的基本块的基础上画出该程序的流图，如图,5-5,所示。,图,5-5,习题,5.8,的程序流图,(2),很容易看出，,B,3,B,2,是流图中的一条有向边，并且有,B,2,DOM B,3,，,故,B,3,B,2,为流图中的一条回边。循环可通过回边求得，即找出由结点,B,2,、,结点,B,3,以及有通路到达,B,3,但不经过,B,2,的所有结点。所以，由回边组成的,B,3,B,2,循环是,B,2,，,B,3,。,进行代码外提就是将循环中的不变运算外提到循环入口结点前新设置的循环前置结点中。经检查，找出的不变运算为,B,2,中的,B=J+1,。,因此，代码外提后的程序流图如图,5-6,所示。,图,5-6,习题,5.8,中代码外提后的程序流图,我们知道，强度削弱不仅可对乘法运算进行，也可对加法运算进行。由于本题中的四元式程序不存在乘法运算，所以只能进行加法运算的强度削弱。从图,5-5,中可以看到，,B,2,中的,C=B+I,，,变量,B,因代码外提其定值点已在循环之外，故相当于常数。而另一加数,I,值由,B,3,中的,I=I+1,决定，即每循环一次,I,值增,1,；也即每循环一次，,B,2,中的,C=B+I,其,C,值增量与,B,3,中的,I,相同，即常数,1,。因此，我们可以对,C,进行强度削弱，即将,B,2,中的四元式,C=B+I,外提到前置结点,B,2,中，同时在,B,3,中,I=I+1,之后给,C,增加一个常量,1,。进行强度削弱后的结果如图,5-7,所示。,图,5-7,习题,5.8,中强度削弱后的程序流图,5.9,某程序流图如图,5-8,所示。,(1),给出该流图中的循环；,(2),指出循环不变运算；,(3),指出哪些循环不变运算可以外提。,图,5-8,习题,5.9,的程序流图,【解答】,(1),流图中的循环为,B,2,B,3,B,4,。,(2)B,3,中的,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,可知，,B,5,B,4,与,B,6,B,2,为流图的有向边，从而有,D(B,5,)=B,1,，,B,2,，,B,3,，,B,4,，,B,5,D(B,6,)=B,1,，,B,2,，,B,3,，,B,4,，,B,6,故有,B,4,DOM B,5,和,B,2,DOM B,6,，,因此,B,5,B,4,和,B,6,B,2,为回边,(,其余都不是回边,),，即分别组成了循环,B,4,，,B,5,、,B,2,，,B,3,，,B,4,，,B,5,，,B,6,。,对循环,B,4,，,B,5,、,B,2,，,B,3,，,B,4,，,B,5,，,B,6,进行代码外提、强度削弱和删除归纳变量等优化后，其优化后的程序流图如图,5-10,所示。,图,5-10,习题,5.10,中优化后的程序流图,