第八章代码生成.ppt

第八章　代码生成Code Generation * 代码生成器的三个任务 8.1 代码生成器设计中的问题 Depend on the target language and OS Memory management Instruction selection Register allocation Evaluation order 8.1.1代码生成器设计的输入 IR of the source program produced by the front end Symbol table, used to determine the run-time address of the data objects denoted by the names in the IR Assume the input is free of error type checking has taken place obvious semantic errors have been detected 8.1.2 Target program (Output of the code generator) Absolute machine language Fixed location in memory, immediately executed Relocatable machine language (object module)可重定位目标模块 允许程序模块分别编译 调用其它先前编译好的程序模块 汇编语言程序 编译器不必重复汇编器的工作 从教学角度，增加可读性 8.1.3 Instruction selection 指令选择 目标机器指令系统的性质决定了指令选择的难易程度，指令系统的一致性和完整性是重要的因素 指令的速度和机器特点是重要的因素 若不考虑目标程序的效率，指令的选择是直截了当的。 例, 三地址语句x = y + z（x,y和z都是静态分配） LD R0, y /*把y装入寄存器R0*/ ADD R0, R0, z /*z加到R0上*/ ST x, R0 /*把R0存入x中*/ 逐个语句地产生代码，常常得到低质量的代码。例， 语句序列 a = b + c d = a + e 的代码如下 LD R0, b ADD R0, R0, c ST a, R0 LD R0, a ADD R0, R0, e ST d, R0 所生成代码的质量取决于它的执行速度和长度。 例，如果目标机器有加1指令（INC）， 则　a = a+1 可以直接用一条指令INC a实现，而不是指令序列： LD R0, a ADD R0, R0， #1 ST a, R0 8.1.4 Register allocation 寄存器分配 运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也快一些。充分利用寄存器对生成好的代码尤为重要。 寄存器分配 选择驻留在寄存器中的一组变量 寄存器指派 register assignment 挑选变量要驻留的具体寄存器 NP-complete problem 8.1.5 choice of evaluation order 计算次序的选择 某种计算次序可能会比其它次序需要较少的a寄存器来保存中间结果 Also an NP-complete problem. 8.2 目标语言 目标机器的指令系统 字节寻址 四字节组成一个字 有n个通用寄存器R0, R1, …, Rn-1 指令形式 加载运算 保存运算 计算运算 无条件跳转 条件跳转 寻址模式和它们的汇编语言形式及相关开销 指令实例 Instruction costs 指令开销 指令开销：它的源和目的地址模式的附加开销再加上1 指令 cost LD R0，R1 1 LD R0，X 2 LD R1，*100(R2) 2 例 三地址语句 x = y – z 的机器指令序列： LD R2，y LD R2，z SUB R1，R1，R2 ST x，R1 三地址语句 b = a[i] 的机器指令序列(数组a的元素占8个字节)： LD R1，i MUL R1，R1，8 LD R2，a(R1) ST b, R2 例 三地址语句 a[j] = c的机器指令序列： LD R1，c LD R2，j MUL R2，R2，8 ST a(R2