第11章-作业及习题参考答案
- 格式：doc
- 大小：204.00 KB
- 文档页数：10
1 / 10 第11章
（8分）将下面程序划分为基本块，并画出其基本块程序流图。
(1) if a
(2) halt
(3) if c
(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答：根据不同的阶段，分为中间代码优化和目标代码的优化。
根据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化。
3答：最常用的代码优化技术有：
（1）删除多余运算 （2）代码外提
（3）强度削弱 （4）变换循环控制条件
（5）合并已知量和复写传播 （6）删除无用赋值
4 图11.23是图11.22的C代码的部分四元式代码序列
(1) 请将图11.23的四元式代码序列划分为基本块并做出其流图?
(2) 将每个基本块的公共子表达式删除?
(3) 找出流图中的循环,将循环不变量计算移出循环外?
(4) 找出每个循环中的归纳变量，并且在可能的地方删除它们
图11.22
void quicksort(m,n)
int m,n; { int i,j;
int v,x; if (n<=m) return;
/* fragment begins here */
i = m-1;
j = n;
v = a[n];
while(1) {
do i = i+1;while (a[i]
do j = j-1; while (a[j]>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;
/* 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:=a[t1]
(5) i:=i+1
(6) t2:=4*i
(7) t3:=a[t2]
(8) if t3< v goto (5)
(9) j:=j-1
(10) t4:=4*j
(11) t5:=a[t4]
(12) if t5> v goto (9)
(13) if i >= j goto (23)
(14) t6:=4*i
(15) x:=a[t6] (16) t7:=4*i
(17) t8:=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
答：
（1）1-4为第1块，5-8为第2块，9-12为第3块，13句为第4块，14-22为第5块，23-30句为第6块。流图如下：
B1 3 / 10
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)中，有基本归纳变量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:=a[t1]
(p) t4 := 4 * n
(p+1) t8 := t4
(p+2) t10 := t4
(5) i:=i+1
(6) t2:=4*i
(7) t3:=a[t2]
(8) if t3< v goto (5)
(9) j:=j-1 //删除
(10) t4:=t4 + 4
(11) t5:=a[t4]
(12) if t5> v goto (9)
(13) if t2 >= t4 goto (23)
(14) t6:=4*i
(15) x:=a[t6]
(16) t7:=4*i
(17) t8:=t8 + 4 (18) t9:=a[t8]
(19) a[t7]:=t9
(20) t10:=t10 + 4
(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
至于程序段中存在的大量4 * i公共子表达式，在代码优化时，不会在“删除归纳变量”步骤中删除。
5．如下程序流图(图11.24)中，B3中的i∶=2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗?
图11.24
答：不能将i=2提成前置节点，这样不管中间的判断如何，最后j=2。
6. 试对以下基本块B1和B2：
B1：(a) A := B * C B2: B := 3
(b) D := B / C D := A + C 5 / 10 (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：
n1
B n2
C n3 A, G
* n4 D
(h) n5 E
/ + n6
2 n7
*
n8 H
* n9 * F, L n1
B n2
C n3 A, G
* n4 D
(g) n5 E
/ + n6
2 n7
*
n8 H
* n9 * F n1
B n2
C n3 A, G
* n4 D
(f) n5 E
/ + n6
2 n7
* F
n8 H
*
n1
B n2
C n3 A, G
* n4 D
(e) n5 E
/ + n6
2 n7
* F
n8 G
*
n1
B n2
C n3 A
* n4 D
(d) n5 E
/ + n6
2 n7
* F n1
B n2
C n3 A
* n4 D
(c) n5 E
/ +
n1
B n2
C n3 A
* n4 D
(b) /
n1
B n2
C n3 A
*
(a)
优化后的四元式序列：
(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：
n1
B n2
C n3 A, G
* n4 D
(i) n5 E
/ + n6
2 n7
*
n8 H
* n9 * F, L, M
n2
A n3
C n4 D
+
(e) n1
3 B E n5
* n6 F
+ n7
* G n2
A n3
C n4 D +
(d) n1
3 B E n5 * n6 F + n1
A n2
C n3 D
+
(c) n1
B 3 E n4 *
n1
A n2
C n3 D
+
(b) n1
B 3 n1
B 3
(a)
