编译原理 第八章代码生成 上海交通大学 张冬茉 Email:Zhang-dm@cssjtu.edu.cn 2004年6月
1 编译原理 第八章 代码生成 上海交通大学 张冬茉 Email:zhang-dm@cs.sjtu.edu.cn 2004年6月
本章目的 词法分析、语法分析、语法制导翻译及中间代码 生成是编译的前端,而目标代码的生成是编 译的后端,编译优化是可选部件。代码生成 的任务是在编译前端生成的中间代码的基础 上,生成等价有效的目标代码,这也是一种 程序变换,变换的结果是产生目标代码。等 价是任一种程序变换的基本要求,因此讨论 将集中在目标代码和如何产生有效的目标代 码上。所谓有效,当然是指目标代码占用的 空间要省,运行的时间要短,这涉及充分利 用寄存器和生成优化的代码序列的问题 2
2 本章目的 词法分析、语法分析、语法制导翻译及中间代码 生成是编译的前端，而目标代码的生成是编 译的后端，编译优化是可选部件。代码生成 的任务是在编译前端生成的中间代码的基础 上，生成等价有效的目标代码，这也是一种 程序变换，变换的结果是产生目标代码。等 价是任一种程序变换的基本要求，因此讨论 将集中在目标代码和如何产生有效的目标代 码上。所谓有效，当然是指目标代码占用的 空间要省，运行的时间要短，这涉及充分利 用寄存器和生成优化的代码序列的问题
第八章代码生成 §8.1目标代码 代码生成器的输入与输出 输入必须含有两部分:一部分是前端生成的中间代码 它是三地址表示的四元式。另一部分便是符号表,这 是由前端产生的,用以决定中间代码的数据对象运行 地址的所有信息都在符号表中存放着。 输出是目标代码,其形式可以是绝对机器语言、可重 定位机器语言或汇编语言的代码。 3
3 第八章 代码生成 §8.1 目标代码 一、代码生成器的输入与输出 输入必须含有两部分：一部分是前端生成的中间代码， 它是三地址表示的四元式。另一部分便是符号表，这 是由前端产生的，用以决定中间代码的数据对象运行 地址的所有信息都在符号表中存放着。 输出是目标代码，其形式可以是绝对机器语言、可重 定位机器语言或汇编语言的代码
、目标机器 目标机多种多样,要生成好的目标代码,必须熟悉目标机, 特别是指令系统的细节。作为一般讨论,我们不打算讨论 十分依赖于目标机器细节的内容,当然也不可能生成完整 的满意的代码。我们只讨论一般技术,只针对一种抽象的 目标机,它是简单的,作为各种目标机的子集,它是公共 的。 目标机具有几个通用寄存器,它们同时可作为变址器 4
4 二、目标机器 目标机多种多样，要生成好的目标代码，必须熟悉目标机， 特别是指令系统的细节。作为一般讨论，我们不打算讨论 十分依赖于目标机器细节的内容，当然也不可能生成完整 的满意的代码。我们只讨论一般技术，只针对一种抽象的 目标机，它是简单的，作为各种目标机的子集，它是公共 的。 目标机具有几个通用寄存器，它们同时可作为变址器
指令形式为二地址形式: op源,目的 其中op为操作码,源和目的作为两个操作对象都是数据域, 它们可以是内存地址,也可以是寄存器,或常数。指令的 地址模式可有: (1)绝对地址型: 0pRi,M(Ri)op(M)→Ri (2)寄存器型 op Ri, ri(Riop(r=Ri (3)变址型: op ri, c(ri(riop((ri+c)=i (4)间接型: op Ri, *Ri(Riop((ri)=Ri op ri, *M Riop((m)=Ri op Ri, *c(Ri(iop(((ri+c))=Ri
5 指令形式为二地址形式： op 源，目的 其中op为操作码，源和目的作为两个操作对象都是数据域， 它们可以是内存地址，也可以是寄存器，或常数。指令的 地址模式可有： (1) 绝对地址型： op Ri, M (Ri)op(M)Ri (2) 寄存器型： op Ri, Rj (Ri)op(Rj) Ri (3) 变址型： op Ri, c(Rj) (Ri)op((Ri)+c) Ri (4) 间接型： op Ri, *Rj (Ri)op((Rj)) Ri op Ri, *M (Ri)op((M)) Ri op Ri, *c(Rj) (Ri)op(((Ri)+c)) Ri
其他操作指令的指令意义为: (1)MovR,M(Ri)→M (2) MOVM, R (M)→R (3)JX goto X (4) CMPA, B 将A和B的存储内容进行比较, 视AB,分别设CJ=0,CJ=1,CJ=2, (5)J rop X rop与CJ,状态一致时 goto X, 例如rop为<则CJ=0, goto X 6
6 其他操作指令的指令意义为： (1) MOV Ri , M (Ri) M (2) MOV M, Ri (M) Ri (3) J X goto X (4) CMPA，B 将A和B的存储内容进行比较， 视AB，分别设CJ＝0，CJ＝1，CJ＝2， (5) J rop X. rop与CJ，状态一致时goto X， 例如rop为<则CJ＝0，goto X
§82一个简单代码生成器 待用信息 定义81在基本块B中,变量A在i点的值,点引用 并且ij的通路上没有A的其他定值和引用,则j为i 处A的下一个引用点,即待用信息。 基本块内i处一个变量的活跃信息是指基本块出口 之后该变量是否还要被引用,而待用信息则是指基 本块内的下一引用点,这些是寄存器分配所需的信 息。因此在为基本块的每一语句生成目标代码时, 应先求出该语句中变量的待用信息和活跃信息。为 计算变量的待用信息,在变量符号表中设待用信息 栏和活跃信息栏,然后执行下列步骤: 7
7 §8.2 一个简单代码生成器 一、待用信息 定义8.1 在基本块B中，变量A在i点的值，j点引用， 并且i→j的通路上没有A的其他定值和引用，则j为i 处A的下一个引用点，即待用信息。 基本块内i处一个变量的活跃信息是指基本块出口 之后该变量是否还要被引用，而待用信息则是指基 本块内的下一引用点，这些是寄存器分配所需的信 息。因此在为基本块的每一语句生成目标代码时， 应先求出该语句中变量的待用信息和活跃信息。为 计算变量的待用信息，在变量符号表中设待用信息 栏和活跃信息栏，然后执行下列步骤：
(1)开始时,把基本块中各变量的符号表的待 用信息栏初始化为“非待用”,活跃信息栏按该变 量在基本块出口后是否活跃而初始化为“活跃”或 “非活跃”。 (2)从出口语句到入口语句反向扫描每个语句(如: P:x:=yopz),依次执行: 将符号表中x变量的待用信息和活跃信息附加到语 句P上;然后将x在符号表中的信息置为“非待用” “非活跃” 将符号表中y,z变量的待用信息和活跃信息附加 到语句P上;然后将符号表y、z的待用置为P,活跃 栏置为“活跃” 8
8 (1) 开始时，把基本块中各变量的符号表的待 用信息栏初始化为“非待用”，活跃信息栏按该变 量在基本块出口后是否活跃而初始化为“活跃”或 “非活跃”。 (2) 从出口语句到入口语句反向扫描每个语句(如： P：x:=y op z)，依次执行： • 将符号表中x变量的待用信息和活跃信息附加到语 句P上；然后将x在符号表中的信息置为“非待用” 、 “非活跃” 。 • 将符号表中y，z变量的待用信息和活跃信息附加 到语句P上；然后将符号表y、z的待用置为P，活跃 栏置为“活跃”
[例8.1]基本块中有四个语句如图8.1的表左所列 表右列出各变量的符号表的待用信息栏和活跃 信息,待用信息用数字1-4表示下一引用点的 语句位置,0表示非待用;活跃信息由“+”表 示活跃,“一”表示不活跃,每个语句的变量 的待用信息和活跃信息分别用上标和下标表示。 2)u4=a3+c (3) a 0+u 图81求基本块内变量的待用信息(例8 初始
9 [例8.1] 基本块中有四个语句如图8.1的表左所列， 表右列出各变量的符号表的待用信息栏和活跃 信息，待用信息用数字1－4表示下一引用点的 语句位置，0表示非待用；活跃信息由“＋”表 示活跃， “－”表示不活跃，每个语句的变量 的待用信息和活跃信息分别用上标和下标表示。 (1) t3 + :=a2 + -b 0 - (2) u 4 + :=a3 ++c0 - (3) v 4 + :=a0 - -t 0 - (4) v 0 + :=v0 -+u0 - 图8.1 求基本块内变量的待用信息(例8.1) 初始
、寄存器描述和地址描述 为了在代码生成中充分利用寄存器,生成尽可 能简短的代码,将使用寄存器描述数组 RVALUE|R记录寄存器R是空闲着,还是已 分配给某些变量;将使用变量地址描述数组 AVALUE|A来记录变量A的现行值是存放在 某个寄存器中,还是在某个主存单元中,或 者既在寄存器中又在主存中。 10
10 二、寄存器描述和地址描述 为了在代码生成中充分利用寄存器，生成尽可 能 简短 的代 码 ， 将使用 寄存 器描 述数 组 RVALUE[Ri ]记录寄存器Ri是空闲着，还是已 分配给某些变量；将使用变量地址描述数组 AVALUE[A]来记录变量A的现行值是存放在 某个寄存器中，还是在某个主存单元中，或 者既在寄存器中又在主存中