《编译原理与技术》练习题 29
练习 11
11.1 何谓代码优化？代码优化需要什么样的基础？ 11.2 编译过程中可以进行的优化是如何分类的？ 11.3 常用的代码优化技术有哪些？
11.4 使用基本的代码优化技术对下面的代码进行优化：
x = 1; ... y = 0; ...
if (y ) x := 0; ... if (x) y = 1; ...
11.5 对以下基本块B1和B2：
B1: 1. A := B?C
2. D := B/C 3. E := A+D 4. F := 2?E 5. G := B?C 6. H := G?G 7. F := H?G 8. L := F 9. M := L
B2: 1. B := 3
2. D := A+C 3. E := A?C 4. F := D+E 5. G :=B?F 6. H := A+C 7. I := A?C 8. J := H+I 9. K := B?5 10. L := K+J 11. M := L
分别构造出DAG，然后应用DAG就以下两种情况分别写出优化后的三地址中间代码： （1）假设变量G、L和M在基本块之后还要被引用；
《编译原理与技术》练习题 30
（2）假设只有变量L在基本块之后还要被引用。 11.6 下面的C语言程序
p = 0;
for ( i = 0; i<= 20; i ++ ) { p = p + a[i] ?b[i] };
经过编译得到的中间代码如下
(1) p := 0 (2) i := 1 (3) t1 := 4?i (4) t2 := addr(a) ? 4 (5) t3 := t2[t1] (6) t4 := 4?i (7) t5 := addr(b) ? 4 (8) t6 := t5[t4] (9) t7 := t3?t6 (10) p := p + t7 (11) i := i + 1 (12) if i ? 20 goto (3)
（1）把上述三地址程序划分为基本块并做出流图。 （2）将每个基本块的公共子表达式删除。
（3）找出流图中的循环，将循环不变量计算移出循环。 （4）找出每个循环中的归纳变量，并在可能之处删除它们。
11.7 请用窥孔优化技术对下列指令进行优化，其中R1和R2不一定是同一寄存器。
MOV R1, L MOV L, R1
11.8 窥孔优化经常使用模式变量描述，用一条规则表示一类优化，例如
MUL #2, %R ? ADD %R, %R
表示任何寄存器乘以2都可以用寄存器自身的加法代替（这里，用%R匹配任意的寄存器）。请考虑
如何在窥孔优化器中实现这种模式匹配。
11.9 请利用代码优化的思想（代码外提和强度消弱），优化下列C语言程序，写出优化后的C程序。
main ()
《编译原理与技术》练习题 31
{
}
int i, j; int r[20][10];
for ( i = 0; i < 20; i++ ) { }
for ( j = 0; j < 10; j++ ){ }
r[i][j] = 10?i?j;