第九章 代码生成,学习内容,目标机器 存储管理 基本块、流图 简单代码生成算法 寄存器分配 窥孔优化 基本块dag表示、从dag生成代码,9.1 设计中的问题,输入 前端生成的中间表示形式 线性化表示：后缀表示形式 四元式表示：三地址码 虚拟机表示：抽象栈机器代码 图形化表示：语法树、DAG 符号表信息 类型检查、类型转换已完成 输入是无错误的,设计中的问题（续）,目标程序 绝对机器语言 固定内存地址，可直接执行 可重定位机器语言 多模块连接 灵活、分别编译 汇编语言 简单符号指令、宏的使用,设计中的问题（续）,内存管理 名字数据地址，与前端协作 符号表 标号指令地址 backpatching技术,设计中的问题（续）,指令选择 指令集特性 一致性、完整性 指令速度、机器特性 代码质量：速度、大小 丰富的指令集多种代码生成方式 选择最高效方式,设计问题（续）,寄存器分配 allocation、assignment 最优化assignmentNP-完全问题 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 开销6 ADD c, R0 MOV R0, a MOV b, a 开销6 ADD c, a MOV *R1, *R0 开销2 ADD *R2, *R0 ADD R2, R1 开销3 MOV R1, a,R0：a的地址 R1：b的地址 R2：c的地址,R1：b的值 R2：c的值,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 /* call p */ 344: SUB #qsize, SP 352: ACTION5 372: ADD #qsize, SP 380: MOV #396, *SP /* 返回地址压栈 */ 388: GOTO 300 /* call q */ 396: SUB #qsize, SP 404: ACTION6 424: ADD #qsize, SP 432: MOV #448, *SP /* 返回地址压栈 */ 440: GOTO 300 /* call q */ 448: SUB #qsize, SP 456: GOTO *0(SP) /* return */ 600:,9.3.3 运行时名字的地址,x := 0 相对地址12 位于静态分配区域，地址static static12 := 0 static = 100 MOV #0, 112 display方式，地址在寄存器R3中 t1 := 12 + R3 *t1 := 0 MOV #0, 12(R3),9.4 基本块和流图,9.4.1 基本块，basic block 连续语句序列，执行过程中没有分支 t1 := a * a t2 := a * b t3 := 2 * t2 t4 := t1 + t3 t5 := b * b t6 := t4 + t5 x := y + z：定义x，使用（引用）y、z,算法9.1 基本块的划分,输入 三地址码序列 输出 划分后的基本块 方法 首先确定入口语句（leader，基本块的第一个语句）集，确定规则： 程序的第一条语句 条件转移或无条件转移语句的目的语句 条件转移或无条件转移语句之后的语句 每个leader对应的基本块： leader下个leader（或程序尾）,例9.3,beginprod := 0i := 1do beginprod := prod + ai * bi;i := i + 1endwhile i = 20 end,例9.3（续）,prod := 0 i := 1 t1 := 4 * i t2 := a t1 t3 := 4 * i t4 := b t3 t5 := t2 * t4 t6 := prod + t5 prod := t6 t7 := i + 1 i := t7 if i = 20 goto (3),9.4.2 基本块的变换,基本块进行表达式计算 等价计算相同的表达式 变换不改变计算的表达式集合 提高代码质量 保结构变换 structure-preserving transformation 代数变换 algebraic transformation,9.4.3 保结构变换,公共子表达式删除 a := b + c b := a d c := b + c d := a d a := b + c b := a d c := b + c d := b,d与b相同 c与a不同！,保结构变换（续）,无用代码删除 x := y + z x在后续代码中未被使用，则可将此语句删除 重命名临时变量 t := b + c，t临时变量 u := b +c，u新临时变量，对t的引用对u的引用，基本块结果不变 定义临时变量的语句都定义新的临时变量 基本块等价变换，范式基本块,保结构变换（续）,语句交换 t1 := b + c t2 := x + y 两个语句交换位置不影响运算结果 x、y都不是t1，b、c都不是t2 注意：范式基本块允许所有可能的语句交换,9.4.4 代数变换,允许改变表达式代数上等价 x := x + 0删除 x := x * 1删除 x := y * 2 x := y * y提高性能,9.4.5 流图,基本块间添加控制流信息程序 流图，flow graph 节点基本块 首（initial）节点该基本块的入口语句就是程序的第一条语句,流图的构造,基本块B1到B2有一条有向边代码执行序列中B2紧跟在B1之后： B1的最后一条语句（无）条件转向到B2的第一条语句 程序中B2紧跟在B1之后，且B1的最后一条语句不是无条件转移语句 B1B2的前驱，B2B1的后继,例9.4,9.4.6 基本块的表示,记录 计数器：四元组（三地址码语句）数目 指向leader的指针 指向前驱基本块和后继基本块的指针 优化时代码改变或移动 跳转到语句号跳转到基本块,9.4.7 循环（loop）,什么是循环？如何找到循环？ 循环满足如下条件的一组节点 这组节点是强连通的任何两个节点间都存在一条（完全包含在循环内的）路径 这组节点具有唯一的一个入口（entry）从循环外的节点到达循环内的节点，唯一的途径是先到达入口节点 内部不包含其他循环的循环内层循环，inner loop,9.5 下次引用信息,next-use information 名字的使用（use） 三地址码语句i为x赋值 语句j将x作为运算对象，而i到j的控制流路径中无其他对x赋值的语句 语句j使用了语句i计算的x值 对语句x := y op z，确定x、y、z下次使用的位置，以决定寄存器可否释放 由后向前扫描基本块,9.5.1 计算下次引用信息,基本方法 每个变量记录下次引用信息和活跃信息 假定每个临时变量在基本块出口后非活跃 非临时变量在出口后活跃 若临时变量跨基本块，假定其活跃 算法：当扫描到语句i：x := y op z 将x、y、z的下次引用信息和活跃信息附加在语句i之上 设置x为“非活跃”和“没有下次引用” 设置y、z为“活跃”，下次引用信息设置为i,不可交换！,9.5.2 临时名字的存储分配,两个临时名字活跃期不重叠相同地址 利用下次使用信息,t1 := a * a t2 := a * b t3 := 2 * t2 t4 := t1 + t3 t5 := b * b t6 := t4 + t5,t1 := a * a t2 := a * b t2 := 2 * t2 t1 := t1 + t2 t2 := b * b t1 := t1 + t2,t5,t4,t3,t1,t2,9.6 一个简单的代码生成器,每个中间语言指令目标语言指令 计算结果尽量保存在寄存器，除非 需要用寄存器进行其他计算 下面语句是函数调用、转移或标号 基本块结束！ a := b + c Ri=b, Rj=c ADD Rj, Ri开销1 Ri=b ADD c, Ri开销2 或 MOV c, Rj ADD Rj, Ri开销3,9.6.1 寄存器描述符和地址描述符,代码生成程序用来保存寄存器内容和名字的地址 寄存器描述符： 当前每个寄存器内容，分配新寄存器时用 初始：所有寄存器均空 代码生成过程中：保存0个或多个名字值 地址描述符： 名字的当前值保存在何处？ 寄存器、栈位置或是内存地址 可能在多个位置,9.6.2 代码生成算法,输入：基本块，对每个语句x := y op z： 为计算结果分配位置Lgetreg 提取y的值 查询y的位置y地址描述符，寄存器优先 yLMOV y, L 生成计算指令 查询z的位置z OP z, L 更新x的地址描述符和L的寄存器描述符 若y、z不再被引用，从寄存器描述符删除,