《编泽技术原理及方法》习题解答 第八章习题解答

第八章——习题解答1.试把以下程序划分为基本块并作出其程序流图。 cin>>C; A=0; B=1;L1:A=A+B; if(B>=C) gotoL2; B=B+1; gotoL1;L2:cout<<A; return;解：2.试把以下程序划分为基本块并作出其程序流图。cin>>A,B;F=1;C=A*A;D=B*B;if(C<D) gotoL1;E=A*A;F=F+1;E=E+F;cout<<E;return;L1:E=B*B;F=F+2;E=E+F;cout<<E;if(E>100) gotoL2;return;L2:F=F–1;gotoL1;解：3.对下列中间代码（四元式）进行优化：（1）消除多余运算T1=C*B;D=D+T1;T2=C*B;A=D+T2;T3=C*B;C=D+T3;（2）合并已知量J=1;T1=5*J;A=T1–2;B=A+J;（3）删除无用赋值J=5;A=3;A=8+C;B=A+C;解：（1）T1=C*B;D=D+T1;A=D+T1;C=A;（2）J=1;A=3;B=4;（3）A=8+C;B=A+C;4.试对以下基本块B1和B2：B1:A=B*C;B2:B=3;D=B/D;D=A+C;E=A+D;E=A*C;F=2*E;F=D+E;G=B*C;G=B*F;H=G*G;H=A+C;F=H*G;I=A*C;L=F;J=H+I;M=L;K=B*5;L=K+J;M=L;分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：（1）假设只有G，L，M在基本块后面还要被引用。（2）假设只有L在基本块后面还要被引用。解：B1:DAG图： （1） A=B*CG=AH=G*GF=H*GL=FM=L （2） A=B*C H=A*A L=H*A

B2:DAG图： （1） D=A+C E=A*C F=D+E G=3*F L=15+F M=L （2） D=A+C E=A*C F=D+E L=15+F5.考察以下矩阵相乘程序：for(i=1;i<=n;i++)for(j=1;j<=n;j++)C[i][j]=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++)C[i][j]=C[i][j]+A[i][k]*B[k][j];（1）假设其中数组A，B，C均按静态分配的方式分配存贮单元，试写出以上程序的四元式中间代码。（2）把（1）中得到的四元式序列划分为基本块，并作出其流图。解：（1）i=1;L1:if(i>n) gotoL3;i=i+1;j=1;L2:if(j>n) gotoL1;T1=i*n;T1=T1+j;T2=c;T2[T1]=0;j=j+1;gotoL2;i=1;L3:if(i>n) gotoL6;i=i+1;j=1;L4:if(j>n) gotoL3; j=j+1;k=1;L5:if(k>n) gotoL4;T3=i*n;T3=j+T3;T4=c;T5=T3+k;T6=a;T7=k*n;T7=T7+j;T8=b;T9=T4[T3];T10=T6[T5];T11=T8[T7];T12=T10*T11;T12=T12+T9;T4[T3]=T12;k=k+1;gotoL5;L6:…（2）6.将下列循环四元式进行代码外提：I=1;L1:if(I>10)gotoL2;T1=2*J;T2=T1+1;X=T2;I=I+1;gotoL1;L2:…解：I=1;T1=2*J;T2=T1+1;X=T2;L1:if(I>10)gotoL2;I=I+1;gotoL1;L2:…7.将下列循环语句削减运算强度：for(k=1;;){a=k*x;}其中k是循环变量，x是循环中不变量。解：t=x;for(k=1;;){a=t;}8.对图8.15流图：（1）求出流图中各结点的必经结点集D(n)。（2）求出流图中的回边。（3）求出流图中的循环。图8.15流图解：（1） D(B1)={B1} D(B2)={B1,B2} D(B3)={B1,B2,B3} D(B4)={B1,B2,B3,B4} D(B5)={B1,B2,B3,B5} D(B6)={B1,B2,B3,B6} D(B7)={B1,B2,B7} D(B8)={B1,B2,B7,B8}（2）由于有B2DOMB7，故B7→B2为回边（3）包含回边B7→B2的循环是{B2,B3,B4,B5,B6,B7}9.将下列中间程序段进行合并常量、删除多余运算、代码外提、强度削弱和变换循环控制条件。图8.16流图解：优化后的程序流图为：10.对以下四元式程序，求出其中循环并进行循环优化。I=1;cin>>J,K;L:A=K*1;B=J*1;C=A*B;cout<<C;I=I+1;if(I<100)gotoL;return;解：I=1;cin>>J,K;A=K*1;B=J*1;C=A*B;L:cout<<C;I=I+1;if(I<100)gotoL;return;11.以下程序段是某程序的最内循环，试对它进行循环优化。A=0;I=1;L1:B=J+1;C=B+I;A=C+A;if(I==100)gotoL2;I=I+1;gotoL1;L2:…解：I=1;B=J+1;A=B*100;L1:A=A+I;if(I==100)gotoL2;I=I+1;gotoL1;L2:…12.对以下程序（a）和（b）分别作出其流图并计算：（1）各基本块的到达-定值集IN[B]。（2）各基本块中各变量引用点的ud链。（3）各基本块出口的活跃变量集OUT[B]。（4）各基本块中变量定值点的du链。I=1;N=0;J=0;L1:I=2;L1:J=J+1;L2:if(I<N)gotoL4;cin>>I;cin>>N;if(I<100)gotoL2;L3:N=N+1;cout<<J;gotoL1;return;L4:J=N/I;L2:I=I*I;if(J==0)gotoL3;gotoL1;I=I+1;gotoL2;（b）解：（a）流图：定值点：d1:I=1;d2:J=0;d3:J=J+1;d4:cin>>I;d5:cout<<J;d6:I=I*I;GEN[B1]={d1,d2} KILL[B1]={d3,d4,d5,d6}GEN[B2]={d3,d4} KILL[B2]={d1,d2,d6}GEN[B3]={} KILL[B3]={}GEN[B4]={d6} KILL[B4]={d4}基本块BIN[B]OUT[B]B1000000110000B2111001001100B3001100001100B4001100001001I在引用点d6的ud链为{d4}；J在引用点d3的ud链为{d2,d3}，在引用点d5的ud链为{d3}。基本块BL-DEF[B]L-USE[B]B1{(d6,I),(d3,J),(d5,J)}{}B2{(d6,I),(d5,J)}{(d3,J)}B3{}{(d5,J)}B4{}{(d6,I)}基本块BL-OUT[B]L-IN[B]B4{(d3,J)}{(d6,I),(d3,J)}B3{}{(d5,J)}B2{(d6,I),(d3,J),(d5,J)}{(d3,J)}B1{(d3,J)}{}I的定值点d4的du链为{d6}；J的定值点d2的du链为{d3}，定值点d3的du链为{d3,d5}（b）流图：定值点：d1:N=0;d2:I=2;d3:cin>>N;d4:N=N+1d5:J=N/Id6:I=I+1GEN[B1]={d1} KILL[B1]={d3,d4,d5,d6}GEN[B2]={d2} KILL[B2]={}GEN[B3]={} KILL[B3]={}GEN[B4]={d3} KILL[B4]={d1}GEN[B5]={d4} KILL[B5]={d1,d5}GEN[B6]={d5} KILL[B6]={}GEN[B7]={d6} KILL[B7]={d2}基本块BIN[B]OUT[B]B1000000100000B2111101111101B3111111111111B4111111011111B5111111011101B6111111111111B7111111101111N在引用点d4的ud链为{d1,d3,d4}，在引用点d5的ud链为{d1,d3,d4}；I在引用点d5的ud链为{d2,d6}，在引用点d6的ud链为{d2,d6}。基本块BL-DEF[B]L-USE[B]B1{(d4,N),(d5,N)}{}B2{(d5,I),(d6,I)}{}B3{}{}B4{(d4,N),(d5,N)}{}B5{(d5,N)}{(d4,N)}B6{}{(d5,N),(d5,I)}B7{(d5,I),(d6,I)}{(d6,I)}基本块BL-OUT[B]L-IN[B]B7{(d4,N),(d5,N),(d5,I),(d6,I)}{(d4,N),(d5,N),(d6,I)}B6{(d4,N),(d5,N),(d5,I),(d6,I)}{(d4,N),(d5,N),(d5,I),(d6,I)}B5{(d4,N),(d5,N),(d5,I),(d6,I)}{(d4,N),(d5,I),(d6,I)}B4{(d4,N),(d5,I),(d6,I)}{(d5,I),(d6,I)}B3{(d4,N),(d5,N),(d5,I),(d6,I)}{(d4,N),(d5,N),(d5,I),(d6,I)}B2{(d4,N),(d5,N),(d5,I),(d6,I)}{(d4,N),(d5,N)}B1{(d4,N),(d5,N)}{}N的定值点d1的du链为{d4,d5}，定值点d3的du链为{d4}，定值点d4的du链为{d4,d5}；I的定值点d2的du链为{d5,d6}，定值点d6的du链为{d5,d6}。13.对图8.16的流图，计算：（1）各基本块的到达-定值集IN[B]。（2）各基本块中变量引用点的ud链。（3）各基本块的活跃变量集OUT[B]。图8.17流图解：GEN[B1]={d1,d2} KILL[B1]={d3,d4,d5,d6,d7,d8,d9,d10,d11}GEN[B2]={d3,d4} KILL[B2]={d5,d8}GEN[B3]={d