编译原理答案第九章

9.1解：程序的流图如下9.2解：各结点n的控制结点集D(n)如下：D(n0)={n0}D(n1)={n0,n1}D(n2)={n0,n1,n2}D(n3)={n0,n1,n2,n3}D(n4)={n0,n1,n2,n4}D(n5)={n0,n1,n2,n5}D(n6)={n0,n1,n2,n5,n6}D(n7)={n0,n1,n2,n5,n6,n7}回边和循环：因为D(n5)={n0,n1,n2,n5}，且n5-n2，所以n5-n2为一条回边。根据它求出的循环L1={n2,n5,n3,n4}。因为D(n6)={n0,n1,n2,n5,n6}，且n6-n1，所以n6-n1为一条回边。根据这条回边，求出的循环L2={n6,n1,n5,n3,n4,n2}。9.3解：（1）设数组元素按行存放，A、B、C数组都是n*n的二维数组，各维的下界均为0，每个元素占一个字（4个字节），则数组元素（如A[i,j]）的地址计算公式为：D(A[i,j])=addr(A)+((i-0)*n+(j-0))*4=addr(A)+4*(i*n+j)该程序的三地址代码序列被划分成基本块后如下：（2）程序流图如下：（3）仅基本块B7中有公共子表达式，删除公共子表达式后基本块B7变换成：（4）根据（2）的程序流图，每个结点的控制结点集如下：D(B1)={B1}D(B2)={B1,B2}D(B3)={B1,B2,B3}D(B4)={B1,B2,B3,B4}D(B5)={B1,B2,B3,B4,B5}D(B6)={B1,B2,B3,B4,B5,B6}D(B7)={B1,B2,B3,B4,B5,B6,B7}D(B8)={B1,B2,B3,B4,B5,B6,B8}D(B9)={B1,B2,B3,B4,B9}根据回边B7-B6，循环L1为：L1={B7,B6}根据回边B8-B4，循环L2为：L2={B8,B6,B7,B5,B4}根据回边B9-B2,循环L3为：L3={B9,B4,B5,B6,B7,B8,B3,B2}经循环优化后三地址代码序列变为:9.4解：把本题的三地址代码划分成基本块并画出其程序流图显示在图9.4(1)中，其中有三个基本块B1，B2，B3，有一条回边B2-B2，相应的循环是{B2}。（1）代码外提：由于循环中没有不变运算，故不做此项优化（2）强度削弱：B2中A和B都是I的归纳变量。优化结果显示在图9.4(2)中。（3）删除归纳变量：变换循环控制条件，删除归纳变量I后的流图显示在图9.4(3)中9.5解：采用字节地址，两个字节作为一个机器字。（1）程序的四元式中间代码如下：B1:readN/*置初值*/i:=2B2:ifiNgotoB4/*第一个for语句*/B3:T1:=iT2:=addr(A)/*数组A的基地址*/T1:=2*T1T2[T1]:=truei:=i+1gotoB2B4:i:=2T3:=N**0.5T3:=[T3]+1/*[T3]是对T3的值取整*/B5:ifiT3gotoB12B6:T4:=iT5:=addr(A)T4:=2*T4ifT5[T4]gotoB8B7:gotoB11B8:j:=2*iB9:ifjNgotoB11/*第三个for语句*/B10:T6:=jT7:=addr(A)T6:=2*T6T7[T6]=falsej:=j+igotoB9B11:i:=i+1gotoB5B12:（2）根据四元式的中间代码，可划分成基本块B1，B2，B3，B4，B5，B6，B7，B8，B9，B10，B11。其程序流图如下：考察上面的程序流图：D(B3)={B1,B2,B3}又有B3-B2，因此B3-B2是一条回边。根据它找到的循环L1={B2,B3}。D(B10)={B1,B2,B4,B5,B6,B9,B10}，又有B10-B9，所以B10-B9是一条回边。根据这条回边找到循环L2={B9,B10}。D(B11)={B1,B2,B4,B5,B6,B9,B11}，又有B11-B5，因此B11-B5是一条回边。根据这条回边找到循环L3={B11,B9,B10,B8,B7,B6,B5}（3）进行代码外提把在循环中不随循环变化的操作提到循环外的前置结点中，且在基本块中作复写传播和删除无用赋值。结果程序流图如下：（4）进行强度削弱和删除归纳变量后，其程序流图如下：9.6解：本题程序的程序流图如图9.6(1)所示。（1）计算各基本块的到达_定值集IN[B]。公式为：IN[B]=∪OUT[P]P∈P[B]OUT[B]=GEN[B]∪(IN[B]-KILL[B])GEN[B]和KILL[B]由程序流图直接求出，显示在表9.6(1)中。表9.6(1)基本块GEN[B]位向量KILL[B]位向量B1{d1,d2}11000000{d3,d4,d6}00110100B2{d3,d4}00110000{d1,d2,d6}11000100B3{d6}00000100{d1,d4}10010000B4{}00000000{}00000000求各基本块到达_定值的初值及各遍的执行结果显示在表9.6(2)中。表9.6(2)基本块初值第一遍后第二遍后第三遍后IN[B]OUT[B]IN[B]OUT[B]IN[B]OUT[B]IN[B]OUT[B]B10000000011000000000000001100000000000000110000000000000011000000B20000000000110000110001000011000011100100001100001110010000110000B30000000000000100001100000010010000110000001001000011000000100100B40000000000000000001100000011000000110000001100000011000000110000（2）求各基本块中各变量引用点的ud链：假设在程序中某点u引用了变量a，则把能到达u的a的所有定值点，称为a在引用点u的引用_定值链（简称ud链）。可以利用到达_定值信息来计算各个变量在任何引用点的ud链。由图9.6(1)的程序流图可知，I的引用点是d3、d5和d6，J的引用点是d3和d8。B2中I和J的引用点d3前面没有对I和J的定值点，其ud链在IN[B2]={d1,d2,d3,d6}中，所以I在引用点d3的ud链是{d1,d6}；J在引用点d3的ud链是{d2,d3}。在B2中I的引用点d5前面有I的定值点d4，且在d4定值后到达d5，所以I在引用点d5的ud链是{d4}。B3中I的引用点d6前面没有I的定值点，其ud链是IN[B3]中I的所有定值点，所以是{d4}。B4中J的引用点d8前面没有对J的定值点，其ud链是IN[B4]中J的所有定值点。已知IN[B4]={d3,d4}，所以，J的引用点d8的ud链是{d3}。（3）各基本块出口的活跃变量集V_OUT[B]：对程序中某变量a和某点P，如果存在一条从P开始的道路，其中引用了a在P点的值，则称a在点P是活跃的。计算公式如下：V_IN[B]=USE[B]∪(V_OUT[B]-DEF[B])V_OUT[B]=∪V_IN[S]S∈S[B]其中，S[B]是B的所有后继块组成的集合。DEF[B]和USE[B]可以从给定流图直接求出。从图9.6(1)的流图中求出的各基本块的DEF[B]和USE[B]显示在表9.6(3)中。表9.6(3)基本块USE[B]DEF[B]B1Φ{I,J}B2{I,J}ΦB3{I}ΦB4{J}Φ计算次序为B4,B3,B2,B1，各次迭代结果显示在表9.6(4)中。表9.6(4)基本块第一次迭代后第二次迭代后第三次迭代后V_IN[B]V_OUT[B]V_IN[B]V_OUT[B]V_IN[B]V_OUT[B]B1Φ{I,J}Φ{I,J}Φ{I,J}B2{I,J}{I,J}{I,J}{I,J}{I,J}{I,J}B3{I}Φ{I,J}{I,J}{I,J}{I,J}B4{J}Φ{J}Φ{J}Φ（4）各基本块变量定值点的du链一个变量a在某点P定值后该定值到达a的那些引用点成为该定值点的定值-引用链（简称du链）。使用下面的方程式进行计算：D_IN[B]=D_USE[B]∪(D_OUT[B]-D_DEF[B])D_OUT[B]=∪D_IN[S]S∈S[B]其中S[B]是B的后继基本块集。D_USE[B]和D_DEF[B]根据程序流图可直接求出。本题根据图9.6(1)的程序流图求出的D_USE[B]和D_DEF[B]显示在表9.6(5)中。表9.6(5)基本块D_DEF[B]D_USE[B]B1{(d3,I),(d5,I),(d6,I),(d3,J),(d8,J)}{}B2{(d6,I),(d8,J)}{(d3,I),(d3,J)}B3{(d3,I),(d5,I)}{(d6,I)}B4{}{(d8,J)}变量I和J的D_IN[B]和D_OUT[B]的计算结果分别显示在表9.6(6)和表9.6(7)中。表9.6(6)基本块第一次迭代后第二次迭代后第三次迭代后D_IN[B]D_OUT[B]D_IN[B]D_OUT[B]D_IN[B]D_OUT[B]B1000000000010000000000000001000000000000000100000B2001000000000010000100000000001000010000000000100B3000001000000000000000100001000000000010000100000B4000000000000000000000000000000000000000000000000根据表9.6(6)，D_OUT[B1]=00100000，故I在B1中定值点d1的du链是{d3}。D_OUT[B2]=00000100，故I在B2中定值点d4的du链是{d5,d6}。D_OUT[B3]=00100000，故I在B3中定值点d6的du链是{d3}。表9.6(7)基本块第一次迭代后第二次迭代后第三次迭代后D_IN[B]D_OUT[B]D_IN[B]D_OUT[B]D_IN[B]D_OUT[B]B1000000000010000000000000001000000000000000100000B2001000000000000100100000001000010010000000100001B3000000000000000000100000001000000010000000100000B4000000010000000000000001000000000000000100000000根据表9.6(7)，D_OUT[B1]=00100000，J在B1中定值点d2的du链是{d3}。D_OUT[B2]=00100001，故J在B2中定值点d3的du链是{d3,d8}。9.7解：对本题程序划分基本块并构造其程序流图，结果显示在图9.7(1)中，流图中以深度为主次序为：B1,B2,B3,B5,B7,B4,B6。（１）各基本块的到达－定值集IN[B]：从图9.7(1)的程序流图直接求GEN[B]和KILL[B]，显示在表9.7(1)中。到达－定值集的计算结果显示在表9.7(2)中。表9.7(1)基本块GEN[B]位向量KILL[B]位向量B1{d1}1000000000{d5}0000100000B2{d2}0100000000{d9}0000000010B3{}0000000000{}0000000000B5{d7}0000001000{}0000000000B7{d9}0000000010{d2}0100000000B4{}0000000000{}0000000000B6{d5}0000100000{d1}1000000000表9.7(2)基本块初值第一次迭代第二次迭代第三次迭代IN[B]OUT[B]IN[B]OUT[B]IN[B]OUT[B]IN[B]OUT[B]