编译原理与技术练习题汇总

《编译原理与技术》练习题 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;