编译原理代码生成.ppt

第九章 代码生成 学习内容 目标机器 存储管理 基本块、流图 简单代码生成算法 寄存器分配 窥孔优化 基本块dag表示、从dag生成代码 9.1 设计中的问题 输入 前端生成的中间表示形式 线性化表示：后缀表示形式 四元式表示：三地址码 虚拟机表示：抽象栈机器代码 图形化表示：语法树、DAG 符号表信息 类型检查、类型转换已完成 输入是无错误的 设计中的问题（续） 目标程序 绝对机器语言 固定内存地址，可直接执行 可重定位机器语言 多模块连接 灵活、分别编译 汇编语言 简单——符号指令、宏的使用 设计中的问题（续） 内存管理 名字?数据地址，与前端协作 符号表 标号?指令地址 backpatching技术 设计中的问题（续） 指令选择 指令集特性 一致性、完整性 指令速度、机器特性 代码质量：速度、大小 丰富的指令集?多种代码生成方式 选择最高效方式 设计问题（续） 寄存器分配 allocation、assignment 最优化assignment——NP-完全问题 register-pair 计算顺序 调整计算顺序?提高效率 NP-完全问题 设计问题（续） 代码生成方法 正确性是第一位的 设计目标：易于实现、测试、维护 9.6节：生成算法，9.9节：窥孔优化 9.7节：寄存器使用算法——控制流 9.10、9.11节：代码选择 9.12节：代码生成——树重构 9.2 目标机器 寄存器：R0，R1，…，Rn-1 指令：op source, destination 寻址方式 MOV R0, M MOV 4(R0), M MOV *4(R0), M 指令开销 长度 MOV R0, R1：开销1 MOV R5, M：开销2 ADD #1, R3：开销2 SUB 4(R0), *12(R1)：开销3 指令开销——翻译方法 a = b + c MOV b, R0 开销6ADD c, R0MOV R0, a MOV b, a 开销6ADD c, a MOV *R1, *R0 开销2ADD *R2, *R0 ADD R2, R1 开销3MOV R1, a 9.3 运行时存储管理 静态分配，栈分配 翻译如下三地址码 call return halt action 9.3.1 静态分配 call翻译为 MOV #here, callee.static_area GOTO callee.code_area return翻译为 GOTO *callee.static_area 例9.1 例9.1（续） 100: ACTION1 120: MOV #140, 364 132: GOTO 200 140: ACTION2 160: HALT … 200: ACTION3 220: GOTO *364 … /* 300-363: c的活动记录 */ 300: /* 返回地址 */ 304: /* 局部数据 */ … /* 364-451: p的活动记录 */ 364: /* 返回地址 */ 368: /* 局部数据 */ 9.3.2 栈分配 使用相对活动记录起始的偏移 活动记录的地址——栈寄存器，SP “第一个过程” MOV #stackstart, SP 第一个过程的代码 HALT 栈分配——函数调用和返回 调用 ADD #caller.recordsize, SP /* 指向被调函数活 动记录 */ MOV #here + 16, *SP /* 保存返回地址 */ GOTO callee.code_area 返回 GOTO *0(SP) 栈寄存器调整回调用者的活动记录 SUB #caller.recordsize, SP 例9.2 例9.2（续） /* s的代码 */ 100: MOV #600, SP /* 初始化栈 */ 108: ACTION1 128: ADD #ssize, SP /* 调用序列开始 */ 136: MOV #152, *SP /* 返回地址压栈 */ 144: GOTO 300 /* call q */ 152: SUB #ssize, SP /* 恢复栈 */ 160: ACTION2 180: HALT … /* p的代码 */ 200: ACTION3 220: GOTO *0(SP) /* return */ … 例9.2（续） /* q的代码 */ 300: ACTION4 /* 条件转移到456 */ 320: ADD #qsize, SP 328: MOV #344, *SP /* 返回地址压栈 */ 336: GOTO 200