编译原理蒋宗礼课件第11章精品.ppt

* 第11章?代码生成 11.1 代码生成器设计中的问题 11.2 目标语言 11.3 一个简单的代码生成器 11.4 窥孔优化 11.5 寄存器分配与指派 11.6 本章小结 * 第11章?代码生成 代码生成是编译的最后一个阶段，由代码生成器完成。其任务是把中间代码转换为等价的、具有较高质量的目标代码，以充分利用目标机器的资源。当然，代码生成器本身也必须具有较高的运行效率。 目标代码可以是绝对地址的机器代码，或相对地址的机器代码，也可以是汇编代码。 本章用微型机的汇编指令来表示目标代码。 * 11.1 代码生成器设计中的问题 虽然代码生成器的具体实现依赖于目标机器的体系结构、指令系统和操作系统，但存储管理、指令选择、寄存器分配和计算顺序等问题却是设计各种代码生成器都要考虑的问题，本节讨论这类共性问题。 * 11.1.1 代码生成器的输入 代码生成器的输入包括中间代码和符号表信息，符号表信息主要用来确定中间代码中的变量所代表的数据对象的运行时地址。 假设在代码生成前，编译器的前端已经将源程序扫描、分析和翻译成为足够详细的中间代码，其中变量的值已经可以表示为目标机器能够直接操作的量(位、整数、实数、指针等)； 已经完成了必要的类型检查； 在需要的地方已经插入了类型转换符；明显的语义错误(如试图把浮点数作为数组下标)也都已经被检测出来了。 * 11.1.2 目标代码的形式 代码生成器的输出是目标代码。目标代码的形式主要有如下3种： 绝对机器语言代码。所有地址均已定位，可以立即被执行。适于小程序的编译，因为它们可以迅速地被执行。 可重定位的机器语言代码。允许分别将子程序编译成一组可重定位模块，再由连接装配器将它们和某些运行程序连接起来，转换成能执行的机器语言程序。好处是比较灵活，并能利用已有的程序资源，代价是增加了连接和装配的开销。 汇编语言代码。生成汇编语言代码后还需要经过汇编程序汇编成可执行的机器语言代码，但其好处是简化了代码生成过程并增加了可读性。 * 11.1.3 指令选择 所谓指令选择是指寻找一个合适的机器指令序列来实现给定的中间代码。 目标机器指令系统的性质决定了指令选择的难易程度 指令系统的一致性和完备性是两个重要的因素 特殊机器指令的使用和指令速度是另一些重要的因素 * 11.1.3 指令选择 若不考虑目标程序的效率，指令的选择将非常简单： 如：三地址语句x := y + z翻译成如下代码序列：（x，y和z都是静态分配） MOV y, R0 /* 把y装入寄存器R0 */ ADD z, R0 /* z加到R0上 */ MOV R0, x /* 把R0存入x中 */ 逐个语句地产生代码，常常得到低质量的代码 * 11.1.3 指令选择 语句序列 a := b + c d := a + e 的代码如下 MOV b, R0 ADD c, R0 MOV R0, a -- 若a不再使用，第三条也多余 MOV a, R0 -- 多余的指令 ADD e, R0 MOV R0, d * 11.1.3 指令选择 如果目标机器有加l指令(INC)，则a :＝a+1的最有效实现是： INC a 而不是 MOV a, R0 ADD #1, R0 MOV R0, a * 11.1.4 寄存器分配 将运算对象放在寄存器中的指令通常要比将运算对象放在内存中的指令快且短，因此，要想生成高质量的目标代码，必须充分使用目标机器的寄存器，寄存器的使用包括： 寄存器分配：为程序的某一点选择驻留在寄存器的一组变量 寄存器指派：确定变量将要驻留的具体寄存器 * 11.1.4 寄存器分配 选择最优的寄存器指派方案是一个NP完全问题，如果考虑到目标机器的硬件和(或)操作系统对寄存器的使用约束，该问题还会进一步复杂。有关寄存器分配和指派的策略将在11.5节再进行详细讨论。 * 11.1.5 计算顺序选择 计算执行的顺序同样会影响目标代码的效率。后面将会看到，某些计算顺序比其它顺序需要较少的寄存器来保存中间结果，因而其目标代码的效率也要高。 选择最佳计算顺序也是一个NP完全问题。为简单起见，只讨论如何按给定的三地址码的顺序生成目标代码。 * * * * * * * * * * * * * *