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

第十一章 目标代码生成 本章要点 目标机器模型 2. 一个简单代码生成器寄存器分配； DAG目标代码窥孔优化本章目标 理解和掌握目标机器模型，一个简单代码生成器，寄存器分配，DAG目标代码，窥孔优化等内容。 本章重点 代码生成器设计中的主要问题：存储管理、计算次序的选择、寄存器的分配、指令的选择等目标机器几种常用的地址模式和一些常用的指令 3. 基本块的代码生成算法 5. 窥孔优化技术。 本章难点 2. DAG的目标代码。 作业题 一、单项选择题： 二、多项选择题： 1. 2. 代码生成应着重考虑的问题是________。 a. 每一个语法成分的语义；b. 目标程序运行所占的空间；c. 目标程序的运行速度；d. 充分利用寄存器，减少对存储单元的访问；e. 使生成的目标代码尽可能短； 3. 代码生成器的输入包括。 a. 语法分析树；b. 源程序中间表示；c. 符号表中的信息；d. 语法分析表； 4. 一般引入________用以记录代码生成时所需收集的信息。 a. 内情向量；b. 待用信息；c. 寄存器描述数组；d. 变量地址描述数组。 5. 寄存器描述数组RVALUE动态地记录着寄存器的下面信息________： a. 是否空闲；b. 是否已分配给某个寄存器；c. 是否已分配给某几个寄存器；d. 是否通用； 二．答案：1. a，b，c；2. d，e；3. b，c；4. b，c，d；5. a，b，c； 三、填空题： 一个基本块的DAG，其叶子结点以标识符为标记时，表示。 四、判断题： （ ） （ ）五、名词解释： 1. ； 3. 答：如果我们没有进行过数据流分析并且临时变量不可以跨基本块引用，则把基本块中所有临时变量均看为基本块出口之后的非活跃变量。而把所有非临时变量均看为基本块出口之后的活跃变量。如果某些临时变量可跨基本块引用，那么，也把它们看为基本块出口之后的活跃变量。 六、简答题： 1. 1. 答案： 需要考虑： （1）代码生成器的输入，一般包括源程序的中间表示和符号表的信息。 （2）目标程序，一般是代码生成器的输出，通常有绝对机器代码、可再定位机器语言、汇编语言等。 （3）指令选择，主要考虑指令集的一致性和完全性。 （4）寄存器分配，由于指令对寄存器的操作常常要求比对存储单元的操作快且短，因此，如何充分利用计算机的寄存器，对于生成好的代码来说非常重要。 （5）计算顺序选择。计算完成的顺序会影响目标代码的有效性。 2. 答：目标代码一般有以下三种形式。 （1）能够立即执行的机器语言代码，所有地址均已定位（代真）。 （2）待装配的机器语言模块。当需要执行时，由连接装人程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。 （3）汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码。 代码生成要着重考虑两个问题：一是如何使生成的目标代码较短；另一是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题都直接影响目标代码的执行速度。 七、应用题： 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：＝