第12章 代码生成(2学时)精要.ppt

第12章 代码生成 代码生成概述 简单的代码生成程序 代码生成程序的开发方法 全局寄存器分配（图着色法） 12.1 代码生成概述 代码生成程序的设计重点：代码生成的质量（空间 和 时间效率） 本章内容 简单介绍：代码生成程序的构造方法 重点讨论：全局寄存器分配算法——图着色法（因为执行效率很大程度依赖于寄存器的使用） 一、代码生成程序在编译系统中的位置 在编译的后端 作用： 将中间代码转换为目标代码 目标代码的形式： 能够立即执行的机器语言代码 待装配的机器语言模块 汇编语言代码 依赖于：目标机结构、指令系统、操作系统 二、设计代码生成程序的一般问题 代码生成程序的输入：中间代码 和 符号表中的信息 指令的选择：寻找一个合适的目标机指令序列 注意：指令集的一致性和完整性；指令速度；机器用语。 寄存器分配：确定在程序的哪个点，将哪些变量或中间量的值放在寄存器中。 指令调度：确定程序指令的执行顺序。 流水线结构中，指令调度是必需的。 二、设计代码生成程序的一般问题 代码生成程序的输入 中间代码： 线性表示法：后缀式 三地址表示法：四元式 抽象机表示法：栈式机器码 图形表示法：语法树 符号表中的信息： 所需存储单元个数 静态数据区域中的相对地址（全局变量） 动态数据区域中的相对地址（局部变量） 二、设计代码生成程序的一般问题 指令的选择：寻找一个合适的目标机指令序列 注意： 指令集的一致性和完整性 指令速度 机器用语 基本原则：（冲突时折中考虑） 减少产生代码的尺寸 减少目标代码的执行时间 降低目标代码的能耗 二、设计代码生成程序的一般问题 寄存器分配：确定在程序的哪个点，将哪些值放在寄存器中。 寄存器的使用： （1）在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量。 （2）在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。 寄存器分配原则： （1）生成某变量的目标对象值时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配为止。 （2）当到达基本块出口时，将变量的值存放在内存中。 （3）在同一基本块内，后面不再被引用的变量所占用的寄存器要尽早释放。 寄存器分配方法：图着色法 二、设计代码生成程序的一般问题 指令调度：确定程序指令的执行顺序。（流水线结构中，指令调度是必需的） RISC体系结构的通用流水线调度限制：从内存中取入寄存器中的值在随后的某几个周期中是不能用的。 提高执行效率的方法：尽可能找出一条或若干条指令（与被取值无关），在取值指令之后能够立即执行。 举例：参见P277表12.1 12.2 一个简单的代码生成程序 重点讨论：在一个基本块内如何充分利用寄存器，以提高目标代码的运行效率。 本节主要内容： 一、计算机模型 二、待用信息链表法 三、代码生成算法 一、计算机模型 假定一台计算机 具有n+1个通用寄存器R0,R1,…,Rn。即可作累加器又可作变址器。 运算器用op表示 内存单元用M表示 变量所在的内存单元用变量名表示 常量用C表示 间址存取用*表示 指令形式包含四种类型：间接地址型、寄存器型、变址型、间接型（参见P278 表12.2） 二、待用信息链表法 寄存器分配原则之一： 在同一基本块内，后面还要被引用的变量值尽可能保存在寄存器中；后面不再被引用的变量所占用的寄存器要尽早释放。 为确定后面哪些变量被引用，哪些不被引用，需要确定每个变量的： 待用信息 活跃信息 在符号表中设置每个变量的“待用信息”和“活跃信息”的栏目，计算方法参见P279。 举例参见P279-280 三、代码生成算法 分配操作存储器 R:GETTEG(i: A := B op C) 取B和C现行值存放的位置B’和C’ B’=AVALUE[B] C’=AVALUE[C] 生成目标码 OP R,C’ 生成目标码 LD R,B’ OP R,C’ B’=R? 修改寄存器使用信息和 地址描述信息 Y N 参见P281 GETREG分配算法 参见P282算法流程图 12.3 几种常用的代码生成程序的开发方法 一、解释性代码生成法 P282 二、模式匹配代码生成法 P283 三、表驱动代码生成法 P284 12.4 全局寄存器分配（图着色法） 一、图着色法的基本思想 P284 二、图着色法的基本算法 P285-289 三、举例 P289 一、图着色法的基本思想 P284 将一个程序的所有对象和可供使用的实际寄存器视为一个无向图的不同结点。 若两个对象之间满足下列条件之一，则在它们之间引入一条边，表示它们相互干扰： (1)同时为活跃变量的两个对象 (2)一个对象与之不能也不应该分配的寄存器 然后，利用最大可供使用寄存器数的颜色种数，对干扰图的所有结点进行着色。着色的过程就是对该干扰图进行有效