ch09--目标代码生成.ppt

第9章目标代码生成 知识点 基本块 程序流图下次引用信息代码生成算法 2 43 9目标代码生成 9 1代码生成概述9 2基本块与流图9 3一个简单的代码生成程序 3 43 9 1代码生成概述 目标代码生成程序的任务将前端产生的中间代码转换为等价的目标代码对目标代码生成程序的要求 正确高质量本节内容 代码生成程序的位置代码生成程序设计有关的问题 1 有效地利用目标机器的资源2 所生成的目标代码应高效地运行 4 43 一 代码生成程序的位置 代码生成程序在编译模型中的位置 代码生成程序的输入中间代码 经过语法分析 语义检查之后得到的 正确的符号表记录了与名字有关的信息决定中间表示中的名字所代表的数据对象的运行地址假定 前期工作结果正确 可信中间代码足够详细 必要的类型转换符已正确插入 明显的语义错误已经发现 且正确恢复 5 43 代码生成程序的输出 目标代码目标代码形式绝对机器代码可把代码放在内存中固定的地方 立即执行可重定位机器代码 obj DOS o UNIX 开发灵活 允许各子模块单独编译由连接装配程序将它们连接在一起 生成可执行文件汇编代码 6 43 二 代码生成程序设计有关的问题 代码生成程序的具体细节依赖于目标机器和操作系统所有的代码生成程序固有的问题存储管理指令选择寄存器分配计算顺序的选择 7 43 存储管理 从名字到存储单元的转换由前端和代码生成程序共同完成三地址代码中的名字指向该名字在符号表中位置的指针符号表中的信息在处理声明语句时填入 类型 决定了它的域宽 地址 确定该名字在过程的数据区域中的相对位置上述信息用于确定中间代码中的名字对应的数据对象在运行时的地址 8 43 例如 中间代码与目标代码的对应 对于四元式j gotoiij n 12 n 12 n 12 8 n 20 n 20 16 n 36 n 36 4 n 40 将四元式j的地址记入与i相关的链表中 等待回填 四元式i的地址已有 可以直接生成机器指令 9 43 指令选择 机器指令系统的性质决定了指令选择的难易程度一致性完整性指令的执行速度机器的特点对每一类三地址语句 可以设计它的代码框架如x y z的代码框架可以是MOVy R0ADDz R0MOVR0 x a b cd a e a a 1 MOVb R0ADDc R0MOVR0 aMOVa R0ADDe R0MOVR0 d MOVa R0ADD 1 R0MOVR0 a INCa 10 43 寄存器分配 选出要使用寄存器的变量局部范围内在程序的某一点上寄存器指派可用寄存器专用寄存器通用寄存器寄存器对把寄存器指派给相应的变量变量需要什么样的寄存器操作需要什么样的寄存器 11 43 计算次序的选择 计算次序影响目标代码的效率如 RISC体系结构的一种通用的流水线限制是 从内存中取出存入寄存器的值在随后的几个周期内是不能用的 在这几个周期期间 可以调出不依赖于该寄存器值的指令来执行 如果找不到这样的指令 则这些周期就会被浪费 所以 对于具有流水线限制的体系结构 选择合适的计算次序是必需的 有些计算顺序可以用较少的寄存器来保留中间结果代码生成程序的设计原则能够正确地生成代码易于实现 便于测试和维护 12 43 9 2基本块与流图 基本块具有原子性的一组连续语句序列 控制从第一条语句流入 从最后一条语句流出 中途没有停止或分支如 t1 a at2 b bt3 t1 t2 基本块 t1 a at2 a bt3 2 t2t4 t1 t3t5 b bt6 t4 t5 13 43 基本块的划分方法 确定入口语句 下面的语句是入口语句 三地址代码的第一条语句goto语句转移到的语句紧跟在goto语句后面的语句确定基本块 与每一个入口语句相应的基本块 从一个入口语句 含该语句 到下一个入口语句 不含 之间的语句序列从一个入口语句 含该语句 到停止语句 含该语句 之间的语句序列 14 43 Pascal程序片断 i 1 while i 10 dobegina i a i b i i i 1end 1 i 0 2 ifi 10goto 4 3 goto 17 4 t1 4 i 5 t2 a 4 6 t3 4 i 7 t4 a 4 8 t5 t4 t3 t5 a i 9 t6 4 i 10 t7 b 4 11 t8 t7 t6 t8 b i 12 t9 t5 t8 13 t2 t1 t9 14 t10 i 1 15 i t10 16 goto 2 17 15 43 流图 把控制信息加到基本块集合中 形成程序的有向图 称为流图 控制流图 流图的结点是基本块如果一个结点基本块的入口语句是程序的第一条语句 则称此基本块结点为首结点 如果在某个执行序列中 基本块B2紧跟在基本块B1之后执行 则从B1到B2有一条有向边 B1是B2的前驱 B2是B1的后继 即如果 有一个条件 无条件转移语句从B1的最后一条语句转移到B2的第一条语句 B1的最后一条语句不是转移语句 并且在程序的语句序列中 B2紧跟在B1之后 16 43 流图示例 17 43 举例 1 i m 1 2 j n 3 t1 4 n 4 v a t1 5 i i 1 6 t2 4 i 7 t3 a t2 8 ift3vgoto 9 13 ifi jgoto 23 14 t6 4 i 15 x a t6 16 t7 4 i 17 t8 4 j 18 t9 a t8 19 a t7 t9 20 t10 4 j 21 a t10 x 22 goto 5 23 t11 4 i 24 x a t11 25 t12 4 i 26 t13 4 n 27 t14 a t13 28 a t12 t14 29 t15 4 n 30 a t15 x 基本块划分 B1 B2 B3 B4 B5 B6 18 43 流图 1 i m 1 2 j n 3 t1 4 n 4 v a t1 5 i i 1 6 t2 4 i 7 t3 a t2 8 ift3 vgoto 5 9 j j 1 10 t4 4 j 11 t5 a t4 12 ift5 vgoto 9 13 ifi jgoto 23 14 t6 4 i 15 x a t6 16 t7 4 i 17 t8 4 j 18 t9 a t8 19 a t7 t9 20 t10 4 j 21 a t10 x 22 goto 5 23 t11 4 i 24 x a t11 25 t12 4 i 26 t13 4 n 27 t14 a t13 28 a t12 t14 29 t15 4 n 30 a t15 x B1 B2 B3 B4 B5 B6 B2 B3 B6 B2 19 43 9 3一个简单的代码生成程序 依次处理基本块中的每条三地址语句考虑在基本块内充分利用寄存器的问题当生成计算某变量值的目标代码时 尽可能让变量的值保存在寄存器中 而不产生把该变量的值存入内存单元的指令 直到该寄存器必须用来存放其它的变量值 或已到达基本块的出口为止 后续的目标代码尽可能引用变量在寄存器中的值 在基本块之间如何充分利用寄存器的问题比较复杂 简单起见 在离开基本块时 把有关变量在寄存器中的当前值存放到内存单元中去 代码生成时需考察许多情形 如下次引用信息 活跃信息 当前值的存放位置等 在不同的情况下生成的代码也不同 20 43 本节内容 目标机器概述下次引用信息的计算代码生成算法 21 43 一 目标机器 设计代码生成程序的必要条件 熟悉目标机器一般信息编址方式 按字节编址每个字有4个字节寄存器 n个通用寄存器 R0 R1 Rn 1指令形式 OPS D其中OP MOV ADD SUBS 源操作数D 目的操作数 22 43 寻址方式 指令开销 指令所占用存储单元字数 1 S寻址方式占用字数 D寻址方式占用字数 23 43 举例 MOVR0 R1将寄存器R0的内容复制到R1中开销 1MOVR5 M将寄存器R5的内容放到存储单元M中开销 2ADD 1 R3将寄存器R3的内容增加1开销 2SUB4 R0 12 R1 将地址为 contents 12 contents R1 的单元中的值减去contents 4 contents R0 结果仍存放到地址为 contents 12 contents R1 的单元中 开销 3 24 43 三地址语句a b c的代码 1 MOVb R0ADDc R0指令开销为6MOVR0 a 2 MOVb aADDc a指令开销为6 3 假定R1和R2中分别包含b和c的值 b的值以后不再需要 ADDR2 R1MOVR1 a指令开销为3 4 假定R0 R1和R2中分别存放了a b和c的地址 MOV R1 R0ADD R2 R0指令开销为2 25 43 二 下次引用信息 在把三地址代码转换成为目标代码时 遇到的一个重要问题 如何充分利用寄存器 基本思路 在一个基本块范围内考虑把在基本块内还要被引用的变量的值尽可能保存在寄存器中把在基本块内不再被引用的变量所占用的寄存器尽早地释放如 翻译语句x yopzx y z在基本块中是否还会被引用 在哪些三地址语句中被引用 26 43 下次引用信息 三地址语句序列 i x 1j y xopz j是三地址语句i中x的下次引用信息假定讨论在一个基本块内的引用信息所有的变量在基本块出口处都是活跃的符号表中含有记录下次引用信息和活跃信息的域 语句i对变量x定值 没有对变量x定值的其他语句 语句j引用x在语句i处定的值 27 43 算法 输入 组成基本块的三地址语句序列输出 基本块中各名字的下次引用信息方法 1 把基本块中各变量在符号表中的下次引用信息域置为 无下次引用 活跃信息域置为 活跃 2 从基本块出口到入口由后向前依次处理各语句 对每个三地址语句i x yopz 依次执行下述步骤 a 把当前符号表中变量x的下次引用信息和活跃信息附加到语句i上 b 把符号表中x的下次引用信息和活跃信息分别置为 无下次引用 和 非活跃 c 把当前符号表中变量y和z的下次引用信息和活跃信息附加到语句i上 d 把符号表中y和z的下次引用信息均置为i 活跃信息均置为 活跃 abcd次序不能颠倒 28 43 计算B4中变量的下次引用信息 初始化符号表 变量下次活跃i无活a无活b无活t1无活t2无活t3无活t4无活t5无活t6无活t7无活t8无活t9无活t10无活 29 43 从出口到入口依次检查每条语句 i 无非活 t10 15 活 i无非活 t1无活 t9无活 t9 13 活 t5无活 t8无活 t2无活 t8 12 活 t7无活 t6无活 t7 11 活 b无活 t6 11 活 i 14 活 t5 12 活 t4无活 t3无活 t4 8 活 a无活 t3 8 活 i 9 活 t2 13 活 a 7 活 t1 13 活 i 6 活 i 4 活a 5 活b 10 活 30 43 三 代码生成算法 基本思路 依次把三地址语句转换为目标语言语句在基本块范围内 充分利用寄存器尽可能让变量的值保存在寄存器中后续的代码尽可能引用变量在寄存器中的值离开基本块时 把有关变量在寄存器中的值送到它的存储单元中MOVR M 31 43 考虑引用信息 代码生成时 要考察不同的情况不同的情况下 生成的目标代码也不同如a b c 1 b的值在Ri中 c的值在Rj中 且b不再活跃ADDRj Ri开销为1 2 b的值在Ri中 c的值在存储单元Mc中 且b不再活跃ADDMc Ri开销为2或MOVMc RjADDRj Ri开销为3 32 43 数据结构 寄存器描述器记录每个寄存器的当前内容开始时 寄存器描述器指示所有的寄存器均为空代码生成过程中 每个寄存器在任一给定时刻将保留0个或多个名字的值 地址描述器记录某时刻一个名字的当前值存放的位置 可能是 一个寄存器地址一个栈地址一个存储单元地址或这些地址的一个集合这些信息可以存放在符号表中 用来确定对一个名字的存取方式 33 43 函数getreg 输入 三地址语句x yopz寄存器描述器和名字的地址描述器输出 地址L L或者是寄存器 或者是存储单元 算法 1 若y的值在R中 且该R中不含其它名字的值 并且以后y不再活跃 没有下次引用信息 则返回R作为L 否则 转 2 2 有空R时 就返回一个空R作为L 否则 转 3 3 x在块中有下次引用 或op是一个需要寄存器的算符 则找一个已被占用的R 如果R的值尚未在存储单元中 用指令MOVR M将R的值存放到一个存储单元M中 并且更新地址描述器为M 返回R 如果R同时保存有几个变量的值 则对每一个需要存储的变量值都应产生一条MOV指令 转 4 4 返回x的存储单元Mx作为L 34 43 代码生成算法 输入 基本块的三地址语句输出 基本块的目标代码方法 对基本块中每个三地址语句x yopz执行以下操作 1 L getreg i x yopz 2 查看y的地址描述器 以确定y的值存放的当前位置y 若y的值同时存放在存储器和寄存器中 那么选择寄存器作为y 如果y的值在寄存器L中 更新y的地址描述器 y不在L中 和L的寄存器描述器 L中不含y的值 转 3 如果y的值不在L中 则生成指令 MOVy L 3 生成指令 opz L更新x的地址描述器 x的值在L中 如果L为寄存器 更新L的寄存器描述器 L中只含x的值 4 若y z的当前值没有下次引用 在块的出口非活跃 并且在寄存器中 则更新寄存器描述器及y z的地址描述器 此后 这些寄存器不再包含y和 或z的值 35 43 代码生成算法 续1 若三地址语句是x opy与x yopz类似若三地址语句是x y若y的值在R中 更新R的寄存器描述器和x的地址描述器 以记录x的值仅在保存y的那个寄存器中 若y没有下次引用 且在块的出口非活跃 则该寄存器不再保留y的值 若y的值在存储器My中 则调用函数getreg来找一个存放x值的地址L若L是寄存器 生成指令MOVy L 并更新L的寄存器描述器和x y的地址描述器 若L是内存地址 生成指令MOVMy Mx 更新x的地址描述器 36 43 在基本块的出口 使用MOV指令把那些在块出口是活跃的 且当前值还不在存储单元中的名字的值存储到它们的存储器地址中 使用寄存器描述器确定哪些名字的当前值仍保留在寄存器中使用地址描述器确定其中哪些名字的当前值还不在存储单元里使用活跃变量信息来确定是否需要存储其当前值 代码生成算法 续2 37 43 举例 考虑赋值语句x a b c三地址语句序列 t b cu a tx u假定在基本块的出口x是活跃的有两个寄存器R0和R1 38 43 翻译过程 t b c u a t x u 寄存器全空 MOVb R0MULc R0 R0含t t在R0中 MOVa R1ADDR0 R1 R0含tR1含u t在R0中u在R1中 R1含x x在R1中 MOVR1 X x在R1和内存单元中 语句生成的代码寄存器描述器地址描述器 39 43 为数组元素赋值语句生成目标代码 考虑两种语句形式 a b i 和a i b假定数组采用静态存储分配基址已知下标i存放的