编译原理课后第十一章答案.pdf 15页

'《编译原理》课后习题答案第十一章第11章代码优化第１题何谓代码优化？进行优化所需要的基础是什么？答案：对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。第２题编译过程中可进行的优化如何分类？答案：依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。第３题最常用的代码优化技术有哪些？答案：1.删除多余运算2.代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值计算机咨询网（www.jsjzx.net）陪着您1 《编译原理》课后习题答案第十一章第4题图11.23是图11.22的C代码的部分三地址代码序列。voidquicksort(m,n)intm,n;{inti,j;intv,x;if(n<=m)return;/*fragmentbeginshere*/i=m-1;j=n;v=a[n];while(1){doi=i+1;while(a[i]v);if(i>=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;/*fragmentendshere*/quicksort(m,j);quicksort(i+1,n);}图11.22(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3vgoto(9)(13)ifi>=jgoto(23)计算机咨询网（www.jsjzx.net）陪着您2 《编译原理》课后习题答案第十一章(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t6:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x图11.23(1)请将图11.23的三地址代码序列划分为基本块并做出其流图。(2)将每个基本块的公共子表达式删除。(3)找出流图中的循环,将循环不变量计算移出循环外。(4)找出每个循环中的归纳变量，并在可能的地方删除它们。答案：（1）基本块计算机咨询网（www.jsjzx.net）陪着您3 《编译原理》课后习题答案第十一章流图（2）B5中（14）和（16）是公共子表达式、（17）和（20）是公共子表达式，B5变为（14）t6:=4*I（15）（16）t7:=t6（17）t8:=4*J…（20）t10:=t8（21）（22）B6中（23）和（25）是公共子表达式、（26）和（29）是公共子表达式，B6变为（23）t11:=4*I（24）（25）t12:=t11（26）t13:=4*n计算机咨询网（www.jsjzx.net）陪着您4 《编译原理》课后习题答案第十一章…（29）t15:=t13（3）循环①{B2}②{B3}③{B2，B3，B4，B5}(4)在循环{B2，B3，B4，B5}中，原来的(14)(17)都可以删除。计算机咨询网（www.jsjzx.net）陪着您5 《编译原理》课后习题答案第十一章第5题：如下程序流图(图11.24)中，B3中的i=∶2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗?图11.24答案：不能。因为B3不是循环出口B4的必经结点。循环不变量外移的条件外有：（a）(I)s所在的结点是L的所有出口结点的必经结点(II)A在L中其他地方未再定值(III)L中所有A的引用点只有s中A的定值才能到达（b）A在离开L之后不再是活跃的，并且条件(a)的(II)和(III)成立。所谓A在离开L后不再是活跃的是指，A在L的任何出口结点的后继结点的入口处不是活跃的（从此点后不被引用）（3）按步骤（1）所找出的不变运算的顺序，依次把符合（2）的条件(a)或(b)的不变运算s外提到L的前置结点中。如果s的运算对象（B或C）是在L中定值的，则只有当这些定值四元式都已外提到前置结点中时，才可把s也外提到前置结点。计算机咨询网（www.jsjzx.net）陪着您6 《编译原理》课后习题答案第十一章第6题试对以下基本块B1和B2：B1：A：=B*CD：=B/CE：=A+DF：=2*EG：=B*CH：=G*GF：=H*GL：=FM：=LB2：B：=3D：=A+CE：=A*CF：=D+EG：=B*FH：=A+CI：=A*CJ：=H+IK：=B*5L：=K+JM：=L分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：（1）假设只有G、L、M在基本块后面还要被引用。（2）假设只有L在基本块后面还要被引用。答案:B1：基本块对应的DAG如下：计算机咨询网（www.jsjzx.net）陪着您7 《编译原理》课后习题答案第十一章根据DAG图,优化后的语句序列为A：=B*CG：=AD：=B/CE：=A+DH：=A*AF：=A*HL：=FM：=F（1）假设只有G、L、M在基本块后面还要被引用；S1：=B*CG：=S1S2：=S1*S1S3：=S1*S2L：=S3M：=S3（2）假设只有L在基本块后面还要被引用；S1：=B*CS2：=S1*S1S3：=S1*S2L：=S3（备注：S1，S2，S3为新引入的临时变量）或者：计算机咨询网（www.jsjzx.net）陪着您8 《编译原理》课后习题答案第十一章B2:基本块对应的DAG如下：优化后的四元式序列：对假设（１）B:=3计算机咨询网（www.jsjzx.net）陪着您9 《编译原理》课后习题答案第十一章D:=A+CE:=A*CF:=D+EG:=B*FK:=B*5L:=K+FM:=L对假设（2）B:=3D:=A+CE:=A*CF:=D+EK:=B*5L:=K+F计算机咨询网（www.jsjzx.net）陪着您10 《编译原理》课后习题答案第十一章第7题分别对图11.25和11.26的流图：(1)求出流图中各结点n的必经结点集D(n)。(2)求出流图中的回边。(3)求出流图中的循环。图11.25图11.26计算机咨询网（www.jsjzx.net）陪着您11 《编译原理》课后习题答案第十一章答案：对图11.25：（1）流图中各结点N的必经结点集D(n)：D(1)={1}D(2)={1,2}D(3)={1,2,3}D(4)={1,2,3,4}D(5)={1,2,3,5}D(6)={1,2,3,6}D(7)={1,2,7}D(8)={1,2,7,8}（2）回边：7→2（3）循环：{2，3，4，5，6，7}对图11.26：(1)流图中各结点N的必经结点集D(n)：D(l)＝{1}D(2)＝{1,2}D(3)＝{1,2,3}D(4)={1,2,3,4}D(5)＝{1,2,5}D(6)＝{1,2,5,6}(2)求出流图中的回边：5→2，4→3(3)求出流图中的循环：回边5→2对应的循环：｛2，5，3，4｝回边4→3对应的循环：｛3，4｝计算机咨询网（www.jsjzx.net）陪着您12 《编译原理》课后习题答案第十一章附加题问题1：给出如下4元式序列：(1)J:=0;(2)L1:I:=0;(3)IFI<8,gotoL3;(4)L2:A:=B+C;(5)B:=D*C;(6)L3:IFB=0,gotoL4;(7)WriteB;(8)gotoL5;(9)L4:I:=I+1;(10)IFI<8,gotoL2;(11)L5:J:=J+1;(12)IFJ<=3,gotoL1;(13)STOP①画出上述4元式序列的程序流程图G,②求出G中各结点N的必经结点集D(n),③求出G中的回边与循环。答案：①四元式程序基本块入口语句的条件是：(1)它们是程序的第一个语句；或，(2)能由条件转移语句或无条件转移语句转移到的语句；或，(3)紧跟在条件转移语句后的语句。(4)根据这3个条件，可以判断，设1，2，3，4，6，7，9，11，13为入口语句，故基本块为l，2/3，4/5，6，7/8，9/1O，11/12，13，故可画出程序流图如下图所示-1- 《编译原理》课后习题答案第十一章②D(l)＝{1}，D(2)＝{1，2}，D(3)＝{1，2，3}，D(4)={1，2，4}，D(5)＝{1，2，4，5}，D(6)＝{1，2，4，6}，D(7)＝{1，2，4，7}，D(8)＝{1，2，4，7，8}，即为所求必经结点集。③回边的定义为：假设a→b为流图中一条有向边，若bDOMa，则a→b为流图中一条回边。故当已知必经结点集时，可立即求出所有回边。易知本题回边只有7→2。(按递增顺序考察所有回边。）称满足如下两个条件的结点序列为一个循环。(1)它们强连通，即任意两个结点，必有一通路，且该通路上各结点都属于该结点序列，如序列只包含一个结点，则必有一有向边从该结点引到自身。(2)它们中间有一个而且只有一个是入口结点。所谓入口结点，是指序列中具有下列性质的结点，从序列外某结点有一有向边引到它，或它就是程序流图的首结点。求出回边7→2，可知循环为234567，即为所求。问题2：基本块的DAG如下图所示，若(1)B在该基本块出口处不活跃,(2)B在该基本块出口处活跃的，请分别给出以下代码经过优化后的代码。A:＝B+CB:＝A-DC:＝B+CD:＝A-D-2- 《编译原理》课后习题答案第十一章答案：①当B在出口不活跃时，则B在外面就无用了，故B：=A-D这条赋值语句可删去，另外，由于代码生成方面的关系，可把D的赋值语句提前到C的赋值语句以前。故得到：A:=B+CD:=A-DC:=D+C②当B在出口活跃时，则B在出口处要引用，B的赋值语句就不可删去了，然而D与B充全一样，故D的赋值语句可简化，得：A:＝B+CB:＝A-DD:=BC:=B+C-3-'