代码生成算法 假设中间代码形为： 假设中间代码形为： Ａ：＝Ｂ ｏｐ Ｃ 基本块代码生成算法：对每个中间代码依次执行： 基本块代码生成算法：对每个中间代码依次执行： ３１５页 （见Ｐ３１５页）
第11页
编译原理 目标代码： 目标代码：
对例11.1假设只有 和R1是可用寄存器，用上算法生成的目标代码和相 假设只有R0和 是可用寄存器 是可用寄存器， 对例 假设只有 应的RVALUE和AVALUE如下表： 如下表： 应的 和 如下表
目标指令
第6页
编译原理
待用信息 计算变量待用信息算法 １、开始，将基本块中各变量的符号表登记项中的待用信息栏填为“非待 用”，并根据该变量在基本块出口之后是否活跃填写活跃信息栏。 ２、从基本块出口到基本块入口由后往前依次处理各中间代码，对每一中间 代码 ｉ：Ａ：＝Ｂ ｏｐ Ｃ 依次执行： ａ）将符号表中变量Ａ的待用信息和活跃信息附加到中间代码ｉ上； ｂ）将符号表中变量Ａ的待用信息和活跃信息分别置为“非待用”和 “非活跃”； ｃ）将符号表中变量Ｂ和Ｃ的待用信息和活跃信息附加到中间代码ｉ上； ｄ）将符号表中变量Ｂ和Ｃ的待用信息均置为ｉ，活跃信息均置为“活 跃”。 注意：次序不可颠倒。 如果中间代码形式为 Ａ：＝ ｏｐ Ｂ 或 Ａ：＝ Ｂ 除 不涉及Ｃ外步骤完全相同。
第2页
编译原理 11.1
代码生成器的输入
基本问题
目标程序
指令选择.2 目标机器模型
假设目标计算机有下列指令形式
第4页
编译原理 指令的意义： 指令的意义：
第5页
编译原理 11.3 一个简单的代码生成器
将每条中间代码变换成目标代码，并在一个基本块范围内考虑充分利用寄存器问题。 将每条中间代码变换成目标代码， 并在一个基本块范围内考虑充分利用寄存器问题。 A:=(B+C)*D+E 例： 高级语言 中间代码 T1:=B+C T2:=T1*D A:=T2+E （1） LD ） R,B (2) ADD R,C (3) ST R,T1 (4) LD R,T1 (5) MUL R,D (6) ST R,T2 (7) LD R,T2 (8) ＡＤＤ Ｒ，Ｅ Ｒ，Ａ （９）ＳＴ 优化： （1） 优化： ） (2) (３) ３ （ ４) （５） LD ADD MUL ＡＤＤ ＳＴ R,B R,C R,D Ｒ，Ｅ Ｒ，Ａ
第12页
编译原理 各中间代码对应的目标代码
第13页
编译原理 11.4 寄存器分配
如何更有效的分配寄存器。 如何更有效的分配寄存器。
指令执行代价： 指令执行代价：
每条指令的执行代价＝每条指令访问主存单元次数＋１ 每条指令的执行代价＝每条指令访问主存单元次数＋
对下循环程序段设R0、R1、R2江固定分给某三个变量使用，下面确定这 江固定分给某三个变量使用， 对下循环程序段设 、 、 江固定分给某三个变量使用 三个变量并生成该循环的目标代码。 三个变量并生成该循环的目标代码。
第7页
编译原理
考察基本块： 考察基本块： Ｔ：＝Ａ－Ｂ Ｕ：＝Ａ－Ｃ Ｖ：＝Ｔ＋Ｕ Ｗ：＝Ｖ＋Ｕ Ｗ是基本块出口的活跃变量，则有下表
设
第8页
编译原理 符号表中的待用及活跃信息
第9页
编译原理
第10页
编译原理
寄存器描述和地址描述 寄存器描述数组ＲＶＡＬＵＥ动态记录个寄存器信息。 ＲＶＡＬＵＥ动态记录个寄存器信息 寄存器描述数组ＲＶＡＬＵＥ动态记录个寄存器信息。 变量地址描述数组ＡＶＡＬＵＥ ＡＶＡＬＵＥ动态记录各变量现行值的 变量地址描述数组ＡＶＡＬＵＥ动态记录各变量现行值的 存放位置。 存放位置。
编译原理
第十一章
目标代码生成
编译原理 目标代码的形式
机器语言代码 所有地址已定位，可立即执行 所有地址已定位， 待装配的机器语言模块 汇编语言代码
代码生成考虑（执行速度）： 代码生成考虑（执行速度）： 如何使生成的代码较短 如何利用计算机的寄存器， 如何利用计算机的寄存器，减少目标代码中访问存储单元的 次数
第19页
编译原理
第20页
第14页
编译原理
第15页
编译原理
第16页
编译原理 11.5 DAG的目标代码 的目标代码
为生成更有效的目标代码，对基本块中间代码序列，应按怎样的次序生成 为生成更有效的目标代码，对基本块中间代码序列， 器目标代码 例： 基本块中间代码序列为Ｇ： 基本块中间代码序列为Ｇ： Ｔ１：＝ Ａ＋Ｂ Ｔ２：＝ Ｃ＋Ｄ Ｅ－Ｔ２ Ｔ３：＝ Ｅ－Ｔ２ －Ｔ３ Ｔ４：＝ Ｔ１－Ｔ３
其ＤＡＧ图如下： ＤＡＧ图如下 图如下：
第17页
编译原理
第18页
编译原理
用ＤＡＧ把其改写为Ｇ‘： ＤＡＧ把其改写为 把其改写为Ｇ Ｔ２：＝ Ｔ３：＝ Ｔ１：＝ Ｔ４：＝
Ｃ＋Ｄ Ｅ－Ｔ２ Ｅ－Ｔ２ Ａ＋Ｂ －Ｔ３ Ｔ１－Ｔ３
设Ｒ０和Ｒ１是两个可使用的寄存器，Ｔ４是基本块出口之后的活跃变量， 是两个可使用的寄存器，Ｔ４是基本块出口之后的活跃变量， ，Ｔ 则生成的目标代码如下： 则生成的目标代码如下：