西安理工大学《编译原理》编译原理作业集－第十章－修订.doc

第十章 优化 本章要点 优化概述局部优化基本块的DAG表示及其应用控制流分析和循环查找算法，到达定值与引用定值链，循环优化。 本章目标 考核学生对优化概述，局部优化，基本块的DAG表示及其应用，控制流分析和循环查找算法，到达定值与引用定值链，循环优化等内容的理解和掌握。 本章重点 1．对各类优化的理解，包括常量合并、公共子表达式删除、复写传播、死代码删除、循环优化（代码外提、归纳变量删除、强度削弱）等。 2．控制流分析：掌握建立程序流图的算法和流图中自然循环的识别算法。 本章难点 2. 循环优化； 作业题 一、单项选择题： 循环优化主要采用的三项优化措施是。代码外提削减运算强度删除归纳变量删除归纳变量强度削减代码外提答案：二、多项选择题： 2. a. 合并已知常量；b. 删除多余运算；c. 删除归纳变量；d. 强度削弱；e. 代码外提； 4. 四元式程序中各个基本块的入口语句是________。 a. 程序第一个语句；b. 能由条件转移语句或无条件转移语句转移到的语句； c. 紧跟在条件转移语句后面的语句；d. 调用语句； 5. 二．答案：1. a，b，c；2. c，d，e；3. c，d，e；4. a，b，c； 三、填空题： 就实施优化的范围来说，分优化和。四、判断题： （ ） （ ）五、名词解释： 1.；±C的赋值，且其中C为循环不变量，则称I为循环中的几本归纳变量。 如果I是循环中一几本归纳变量，J在循环中的定植总是可化归为I的同一线性函数，也即I=C1±C2，其中，C1和C2都是循环不变量，则称J是归纳变量，并称它与I同族。一个几本归纳变量也是归纳变量。 2. 程序基本块是指。 a. 一个子程序；b. 一个仅有一个入口和一个出口的语句； c. 一个没有嵌套的程序段；d. 一组顺序执行的程序段，仅有一个入口和一个出口； 3. 合并表达式中常量运算的目的是。 a. 使表达式中的常量尽可能少； b. 是表达式尽可能简短； c. 将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所有这种常量运算，使得生成的代码指令尽可能少； d. 以上都是； 4. 所谓在程序中某个给定点是活跃的，是指如果在程序中，______。 a. 该点以后被引用；b.该点以后被计算；c. 该点正在被计算；d. 该点一直被计算。 六、简答题： 1. 2. 在循环优化中，为什么要代码外提？试说明在哪些情况下可以外提？ 3. 如何理解有些程序优化后质量反而下降？ 4. 有一C语言程序如下： 1 main( ) 2 { int x; 3 x=25; 4 print(“%d\n”, x); 5 } 经过编译连接后，由符号调试器跟踪其执行，却无法检查变量x的值，因为调试器报告“无此变量”。试解释其原因。 5. 循环优化中都有哪些优化技术？ 6. 什么是基本块的DAG？ 7. 什么是复写传播？ 8. 由优化编译程序提供的对代码的各种变换都应遵循哪些原则？ 七、应用题： 1. 试构造下面的程序的流图，并找出其中所有回边及循环。read P x := 1 c := P * P if c 100 goto L1 B := P * P x := x + 1 B := B + x write x halt L1: B:= 10 x := x + 2 B := B + x write B if B 100 goto L2 halt L2: x := x + 1 goto L1 2. 对本题中所示的流图，求出其各结点n的控制结点集D(n)、回边及循环（n0为首结点）。 考虑下面求矩阵A、B成绩的程序片段： BEGIN FOR i := 1 TO n DO FOR j := 1 TO n DO FOR k = 1 TO n DO c[i, j] := c[i, j] + A[i, k} * B[k, j] END （1）假定对数组A、B、C采用静态存储分配，每个字占用4个字节，存储器以字节为单位编址。给出该程序的三地址代码序列。（2）构造该程序相应的流图。（3）删除流图中各基本块内的公共子表达式（4）指出流图中所有回边及其相应循环，并且进行循环优化。试求出如下四元式程序中的循环并进行循环优化I := 1 read J, K L: A := K * I B := J * I C := A * B write C I := I + 1 if I 100 goto L halt 5. 下面是应用筛法求2到N之间素数的程序：begin read N; for i := 2 to N do A[i] := true; /*置初值*/for i := 2 to N**0.5 do /*运算符**代表幂乘*/