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

第十一章 目标代码生成 本章要点 目标机器模型 2. 一个简单代码生成器寄存器分配； DAG目标代码窥孔优化本章目标 理解和掌握目标机器模型，一个简单代码生成器，寄存器分配，DAG目标代码，窥孔优化等内容。 本章重点 代码生成器设计中的主要问题：存储管理、计算次序的选择、寄存器的分配、指令的选择等目标机器几种常用的地址模式和一些常用的指令 3. 基本块的代码生成算法 5. 窥孔优化技术。 本章难点 2. DAG的目标代码。 作业题 一、单项选择题： 二、多项选择题： 三、填空题： 一个基本块的DAG，其叶子结点以标识符为标记时，表示。 四、判断题： （ ） （ ）（ ）（ ）（ ）五、名词解释： 1. ； 3，4. 答：如果我们没有进行过数据流分析并且临时变量不可以跨基本块引用，则把基本块中所有临时变量均看为基本块出口之后的非活跃变量。而把所有非临时变量均看为基本块出口之后的活跃变量。如果某些临时变量可跨基本块引用，那么，也把它们看为基本块出口之后的活跃变量。 5. 代码生成器是是把语义分析后或优化后的中间代码变换成目标代码的程序。它以源程序的中间代码作为输入，并产生等价的目标代码作为输出。 6. 7. 六、简答题： 1. 1. 答案： 需要考虑： （1）代码生成器的输入，一般包括源程序的中间表示和符号表的信息。 （2）目标程序，一般是代码生成器的输出，通常有绝对机器代码、可再定位机器语言、汇编语言等。 （3）指令选择，主要考虑指令集的一致性和完全性。 （4）寄存器分配，由于指令对寄存器的操作常常要求比对存储单元的操作快且短，因此，如何充分利用计算机的寄存器，对于生成好的代码来说非常重要。 （5）计算顺序选择。计算完成的顺序会影响目标代码的有效性。 2. 答：目标代码一般有以下三种形式。 （1）能够立即执行的机器语言代码，所有地址均已定位（代真）。 （2）待装配的机器语言模块。当需要执行时，由连接装人程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。 （3）汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码。 3. 代码生成要着重考虑两个问题：一是如何使生成的目标代码较短；另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题都直接影响目标代码的执行速度。 4. 依次检查临时变量区域的单元，找到第一个不含活跃临时变量的单元，把它指派给待分配的临时变量。如果没有这样的单元，则在活动记录的临时变量区域中增加一个单元。 5. 按照中间代码生成算法，可能会产生连续跳转的情况，这种不必要的连续跳转可以在窥孔优化时删除。这种优化措施称之为控制流优化。 七、应用题： 1. 4. 对以下中间代码序列： T1:=A+B T2:=T1-C T3:=T2*T3 T4:=T1+T3 T5:=T3-E F:=T4*T5 (1) 应用DAG结点排序算法重新排序。 (2) 假设可用寄存器为R0，F是基本块出口处的活跃变量，应用简单代码生成算法分别生成排序前后的中间代码序列的目标代码，并比较其优劣。 5. 假设R0、R1和R2为可用寄存器，试对以下各表达式： (1) A+(B+(C*(D+E/F+G)*H))+(I*J) (2) (A*(B-C))*(D*(E*F))+((G+(H*I))+(J*(K+L)))分别生成其最优目标代码。 6. 有时，一个寄存器的值被存到存储单元中，然后这个值又立即被取到一个寄存器中： ST R1，L LD R2，L 这里R1和R2不一定是同一寄存器。请考虑通过窥孔优化，对这一对指令进行优化。 7. 给定基本块： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。 8. 设有基本块 　　 T1：＝2 　　 T2：＝10/T 　　 T3：＝S－R 　　 T4：＝S＋R 　　 A：＝T2 *T4 　　 B：A 　　 T5：＝S＋R 　　 T6：＝T3 *T5 　　 B：＝T6 (1)画出DAG图； (2)假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。 8. 答案：优化后的四元式 　　　　　　　 　　 T3：＝S－R 　　　　　　　 　　 T4：＝S＋R 　　　　　　　 　　 A：＝5*T4 　　　　　　　 　　 B：＝