1、第11章作业及习题参考答案第11章（8分）将下面程序划分为基本块，并画出其基本块程序流图。(1) if ab goto (3)(2) halt(3) if cd goto (5)(4) goto (8)(5) t1:=y+z(6) x :=t1(7) goto (1)(8) t2:=y-z(9) x :=t2(10) goto (1)11.1答：所谓代码优化即对代码进行等价变换，使得变换后的代码与变换前代码运行结果相同，而运行速度加快或占用存储空间少，或两者兼有。进行优化的基础是中间或目标代码生成，以及基本块的识别、控制流分析和数据流分析。2答：根据不同的阶段，分为中间代码优化和目标代码的优化
2、。 根据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化。3答：最常用的代码优化技术有： （1）删除多余运算 （2）代码外提 （3）强度削弱 （4）变换循环控制条件 （5）合并已知量和复写传播 （6）删除无用赋值4 图11.23是图11.22的C代码的部分四元式代码序列(1) 请将图11.23的四元式代码序列划分为基本块并做出其流图? (2) 将每个基本块的公共子表达式删除?(3) 找出流图中的循环,将循环不变量计算移出循环外? (4) 找出每个循环中的归纳变量，并且在可能的地方删除它们图11.22void quicksort(m,n)int m,n; int i,j; int v,
3、x; if (n=m) return; /* fragment begins here */ i = m-1;j = n;v = an;while(1) do i = i+1;while (aiv);if (i=j) break;x = ai; ai = aj;aj = x; x = ai; ai = an; an = x; /* fragment ends here */ quicksort (m,j);quicksort(i+1,n); 图11.23(1) i:=m-1(2) j:=n(3) t1:=4*n(4) v:=at1(5) i:=i+1(6) t2:=4*i(7) t3:=at2
4、(8) if t3 v goto (9)(13)if i = j goto (23)(14)t6:=4*i(15)x:=at6(16) t7:=4*i(17) t8:=4*j(18) t9:=at8(19) at7:=t9(20) t10:=4*j(21) at10:=x(22) goto (5)(23) t11:=4*i(24) x:=at11(25) t12:=4*i(26) t13:=4*n(27) t14:=at13(28) at12:=t14(29) t15:=4*n(30) at15:=x答：（1）1-4为第1块，5-8为第2块，9-12为第3块，13句为第4块，14-22为第5块
5、，23-30句为第6块。流图如下： B1 B2 B3 B4 B5 B6 (2) (14)和(16)都有4*i的运算，将(16)换成t7=t6(17)和(20)都有4*j的运算，将(20)换成t10=t8(23)和(25)都有4*i的运算，将(25)换成t12=t11(3)、(26)和(29)都有4*n的运算，将(26)换成t13=t1,(29)换成t15=t1(3) 有(5)-(8)、(9)-(12)、(5)-(22)三个循环。三个循环中没有循环不变量。(4) 在循环(5)-(8)中，有基本归纳变量i和归纳变量t2；在循环(9)-(12)中，有基本归纳变量j和归纳变量t4；在循环(5)-(22
6、)中，有基本归纳变量i和归纳变量t7、基本归纳变量j和归纳变量t8、t10。注意到B6：(23)-(30)不在循环内，且B6中依然对i存在引用，所以i不能删除；但j可以删除(1) i:=m-1(2) j:=n(3) t1:=4*n(4) v:=at1(p) t4 := 4 * n(p+1) t8 := t4(p+2) t10 := t4(5) i:=i+1(6) t2:=4*i(7) t3:=at2(8) if t3 v goto (9)(13)if t2 = t4 goto (23)(14)t6:=4*i(15)x:=at6(16) t7:=4*i(17) t8:=t8 + 4(18) t9
7、:=at8(19) at7:=t9(20) t10:=t10 + 4(21) at10:=x(22) goto (5)(23) t11:=4*i(24) x:=at11(25) t12:=4*i(26) t13:=4*n(27) t14:=at13(28) at12:=t14(29) t15:=4*n(30) at15:=x至于程序段中存在的大量4 * i公共子表达式，在代码优化时，不会在“删除归纳变量”步骤中删除。5如下程序流图(图11.24)中，B3中的i=2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗? 图11.24 答：不能将i=2提成前置节点，这
8、样不管中间的判断如何，最后j=2。6. 试对以下基本块B1和B2：B1：(a) A := B * C B2: B := 3 (b) D := B / C D := A + C (c) E := A + D E := A * C (d) F := 2 * E F:= D + E (e) G := B * C G := B * F (f) H := G * G H := A + C (g) F := H * G I := A * C (h) L := F J := H + I (i) M := L K := B * 5 (j) L := K + J (k) M := L解：B1的DAG： 优化后的
9、四元式序列：(1) 假设只有G、L、M在基本块后还要被引用 G := B * C H := G * G L := H * G M := L(2) 假设只有L在基本块后还要被引用 A := B * C H := A * A L := H * A B2的DAG： 优化后的四元式序列：(1) 假设只有G、L、M在基本块后还要被引用B2: D := A + C E := A * C F:= D + E G := 3 * F L := 15 + F M := L(2) 假设只有L在基本块后还要被引用B2: D := A + C E := A * C F:= D + E L := 15 + F7. 对图1
10、1.25和11.26的流图：(1) 求出流图中各结点n的必经结点集D(n)； (2) 求出流图中的回边；(3) 求出流图中的循环。图11.25 解答：（1）D(1)=1D(2)=1,2 D(3)=1,2,3 D(4)=1,2,3,4D(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解答：（2）B1D(1) = 1 D(2) = 1, 2 D(3) = 1, 2, 3 D(4) = 1, 2, 3, 4D(5) = 1, 2, 5 D(6) = 1, 2, 5, 6回边：43 52循环：3,
11、4 2, 3, 4, 5作业问题归纳：（2012级）B1 B2 B3 B4 B5 B6 4（1）基本块划分 （2）循环查找（问题与7雷同，这里不描述）错误解答1：对源代码进行了基本块的划分！（连最基本的题意都没搞清楚！）2.基本块划分出错，最常见的是将14也划分成单独一块。（提示，牢记划分的依据）3.流图画错，特别是在B5和B6之间常有连线（明显B5无法直接到B6，因为B5里写的是无条件跳转）。此外，流图回边线头朝向错误(特别是指向自身的结点)。7.（错误解答1、最严重的错误，针对图11.26）（1）求出流图中各结点的必经结点集D(n).解D(1)=1 D(2)=1,2 . D(11)=1.2
12、,3,4,8,9,10,11 (2)流图中的回边为75 93 (3)流图中的循环为(5)(6)(7) (4)(5)(6)(7)(8)(9)点评：上述解答将一行四元式指令当做一个结点，明显错误。上课或书本里提到了，而且图11.26已经将画了结点，并给出结点的编号B1B6。明显是上课没听。错误解答2：回边B4B3 B5B2循环 B3，B4错误解答3：回边B4B3 B5B2循环 B3，B4 B2，B5 B2,B3，B5点评：上课已提，有多少调回边就有多少个循环，那么两条回边应该就为两个循环。错误解答4： B5B2 组成的循环为B2，B5或B2,B3，B5点评：上课已提，找到某条回边（如B5B2）后，定循环时，应将有通路到达B5，且不经过B2的所有结点也包括进去。明显，B3和B4都有通路到达B5，且不经过B2，因此，循环应为B2、B3、B4、B5。文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意!
