《编译原理教程》课后习题答案 第五章 代码优化.ppt

第五章 代码优化 5.1 完成以下选择题： (1) 优化可生成 的目标代码。 a. 运行时间较短 b. 占用存储空间较小 c. 运行时间短但占用内存空间大 d. 运行时间短且占用存储空间小 (2) 下列 优化方法不是针对循环优化进行的。 a. 强度削弱 b. 删除归纳变量 c. 删除多余运算 d. 代码外提 (3) 基本块内的优化为 。 a. 代码外提，删除归纳变量 b. 删除多余运算，删除无用赋值 c. 强度削弱，代码外提 d. 循环展开，循环合并 (4) 在程序流图中，我们称具有下述性质 的结点序列为一个循环。 a. 它们是非连通的且只有一个入口结点 b. 它们是强连通的但有多个入口结点 c. 它们是非连通的但有多个入口结点 d. 它们是强连通的且只有一个入口结点 (5) 关于必经结点的二元关系，下列叙述中不正确的是 。 a. 满足自反性 b. 满足传递性 c. 满足反对称性 d. 满足对称性 【解答】 (1) d (2) c (3) b (4) d (5) d 5.2 何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？ 【解答】 优化根据涉及的程序范围可分为三种。 (1) 局部优化是指局限于基本块范围内的一种优化。一个基本块是指程序中一组顺序执行的语句序列(或四元式序列)，其中只有一个入口(第一个语句)和一个出口(最后一个语句)。对于一个给定的程序，我们可以把它划分为一系列的基本块，然后在各个基本块范围内分别进行优化。通常应用DAG方法进行局部优化。 (2) 循环优化是指对循环中的代码进行优化。例如，如果在循环语句中某些运算结果不随循环的重复执行而改变，那么该运算可以提到循环外，其运算结果仍保持不变，但程序运行的效率却提高了。循环优化包括代码外提、强度削弱、删除归纳变量、循环合并和循环展开。 5.3 将下面程序划分为基本块并作出其程序流图。 read(A,B) F=1 C=A*A D=B*B if CD goto L1 E=A*A F=F+1 E=E+F write(E) halt L1: E=B*B F=F+2 E=E+F write(E) if E 100 goto L2 halt L2: F=F-1 goto L1 【解答】 先求出四元式程序中各基本块的入口语句，即程序的第一个语句，或者能由条件语句或无条件转移语句转移到的语句，或者条件转移语句的后继语句。然后对求出的每一入口语句构造其所属的基本块，它是由该入口语句至下一入口语句(不包括该入口语句)或转移语句(包括该转移语句)或停语句(包括该停语句)之间的语句序列组成的。凡未被纳入某一基本块的语句都从程序中删除。要注意基本块的核心只有一个入口和一个出口，入口就是其中第一个语句，出口就是其中最后一个语句。如果发现某基本块有两个以上的入口或两个以上的出口，则划分基本块有误。 程序流图画法是当下述条件(1)和(2)有一个成立时，从结点i有一有向边引到结点j： (1) 基本块j在程