1
编译原理第八章 代码生成上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 6月
2
本章目的词法分析、语法分析、语法制导翻译及中间代码生成是编译的前端，而目标代码的生成是编译的后端，编译优化是可选部件。代码生成的任务是在编译前端生成的中间代码的基础上，生成等价有效的目标代码，这也是一种程序变换，变换的结果是产生目标代码。等价是任一种程序变换的基本要求，因此讨论将集中在目标代码和如何产生有效的目标代码上。所谓有效，当然是指目标代码占用的空间要省，运行的时间要短，这涉及充分利用寄存器和生成优化的代码序列的问题
3
第八章 代码生成
§ 8.1 目标代码一,代码生成器的输入与输出输入必须含有两部分：一部分是前端生成的中间代码,
它是三地址表示的四元式 。 另一部分便是符号表,这是由前端产生的,用以决定中间代码的数据对象运行地址的所有信息都在符号表中存放着 。
输出是目标代码,其形式可以是绝对机器语言,可重定位机器语言或汇编语言的代码 。
4
二,目标机器目标机多种多样,要生成好的目标代码,必须熟悉目标机,
特别是指令系统的细节 。 作为一般讨论,我们不打算讨论十分依赖于目标机器细节的内容,当然也不可能生成完整的满意的代码 。 我们只讨论一般技术,只针对一种抽象的目标机,它是简单的,作为各种目标机的子集,它是公共的 。
目标机具有几个通用寄存器,它们同时可作为变址器 。
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
6
其他操作指令的指令意义为：
(1) MOV Ri,M (Ri)?M
(2) MOV M,Ri (M)?Ri
(3) J X goto X
(4) CMP A,B 将 A和 B的存储内容进行比较,
视 A<B,A＝ B,或 A>B,分别设 CJ＝ 0,CJ＝ 1,CJ＝ 2，
(5) J rop X,rop与 CJ,状态一致时 goto X，
例如 rop为 <则 CJ＝ 0,goto X。
7
§ 8.2 一个简单代码生成器一,待用信息定义 8.1 在基本块 B中,变量 A在 i点的值,j点引用,
并且 i?j的通路上没有 A的其他定值和引用,则 j为 i
处 A的下一个引用点,即待用信息 。
基本块内 i处一个变量的活跃信息是指基本块出口之后该变量是否还要被引用,而待用信息则是指基本块内的下一引用点,这些是寄存器分配所需的信息 。 因此在为基本块的每一语句生成目标代码时,
应先求出该语句中变量的待用信息和活跃信息 。 为计算变量的待用信息,在变量符号表中设待用信息栏和活跃信息栏,然后执行下列步骤：
8
(1) 开始时，把基本块中各变量的符号表的待用信息栏初始化为“非待用”，活跃信息栏按该变量在基本块出口后是否活跃而初始化为“活跃”或
“非活跃”。
(2) 从出口语句到入口语句反向扫描每个语句 (如：
P,x:=y op z),依次执行：
将符号表中 x变量的待用信息和活跃信息附加到语句 P上；然后将 x在符号表中的信息置为,非待用,,
,非活跃,。
将符号表中 y,z变量的待用信息和活跃信息附加到语句 P上；然后将符号表 y,z的待用置为 P,活跃栏置为,活跃,。
9
[例 8.1] 基本块中有四个语句如图 8.1的表左所列,
表右列出各变量的符号表的待用信息栏和活跃信息,待用信息用数字 1－ 4表示下一引用点的语句位置,0表示非待用；活跃信息由,＋,表示活跃,,－,表示不活跃,每个语句的变量的待用信息和活跃信息分别用上标和下标表示 。
(1) t3+:=a2+-b0-
(2) u4+:=a3++c0-
(3) v4+:=a0--t0-
(4) v0+:=v0-+u0-
图 8.1 求基本块内变量的待用信息 (例 8.1)
初始
10
二,寄存器描述和地址描述为了在代码生成中充分利用寄存器,生成尽可能简短的代码,将使用寄存器描述数组
RVALUE[Ri]记录寄存器 Ri是空闲着,还是已分配给某些变量；将使用变量地址描述数组
AVALUE[A]来记录变量 A的现行值是存放在某个寄存器中,还是在某个主存单元中,或者既在寄存器中又在主存中 。
11
三,如何生成目标代码给出了一个语句,例如,P,x:=y op z,如何生成目标代码呢？
这个语句通常可由二条指令来实现：
MOV y Ri
Op Ri z
第一条指令是将变量 y的现行值自它的存储单元
(仍用 y来表示 )传送到寄存器 Ri中 。 第二条指令将
Ri中的 y值与变量 z的值 (其存储位置仍用 z来表示 )
进行 op运算,结果 (即 x的值 )留在 Ri中,因此生成该语句的代码前必须确定保存 x值的寄存器 Ri。 换言之,为 x分配一个寄存器 Ri。 具体有以下几种情况：
12
(1) 最理想情况是：如果变量 y已占有寄存器
Ri(这由 AVALUE[y]可知 ),而且 y在 P以后不再被引用 (这由 P处 y的待用信息可知 )或 y同 x,即
P,x:=x op z,则 y占用的寄存器 Ri即可分配给
x。 这种情况下生成的代码只是第二条指令,
为最简短 。
(2) 若还有空余的可用寄存器 Ri,则将 Ri分配给 x,生成上述二条指令 。
13
(3) 如果已无可用寄存器,即寄存器均被占用,则只能从被占用的寄存器中选择一个 Ri,先将占用
Ri的变量的现行值逐一保存到主存单元中,然后才可分配给 x使用 。 选择标准是使这种复制副本的代价尽可能小,很明显,最好选在主存单元中已副本的占用 Ri的变量,或者该变量在 P以后不再被引用或在最远的将来才会被引用 。 在这种情况下,
如果变量 M在 Ri中的值需要在主存单元中复制副本,
则在 Ri分配给 x前,还得生成：
MOV Ri M
指令,此时生成的目标指令就可能多于两条 。
(4) 当然在上述寄存器重新分配,变量存储发生变化时还得修改相应的寄存器描述数组和地址描述数组 。
14
四,函数 getreg(P:x:=y op z)
给出参数 P,x:=y op z,当然也意味着给出了语句 P处的待用信息,活跃信息及当时各寄存器描述数组和变量地址描述数组,据此,为变量 x分配寄存器 R,以 R作为函数值返回 。
其算法为：
(1) 如果 y的现行值在某寄存器 Ri中,而该寄存器仅由 y
所占用,即 AVALUE[y]＝ {Ri,… }?RVALUE[Ri]={y}，
并且 y或与 x是同一标识符,或在 P以后不再引用,则此
Ri即为返回值 R,转 (4)。
(2) 存 在 尚 未 分 配 的 寄 存 器 Ri,即? i(1≤i≤n)?
RVALUE[Ri]={}时,Ri为返回值 R,转 (4)。
15
(3) 从已分配的 n个寄存器中选一个 Ri(设它为变量
A等所占用 ),使得占有 Ri的变量或者在主存中有副本,或者在 P点以后不再被引用,或者待用信息最大,即? i(1≤i≤n)?RVALUE[Ri] ＝
{A,… }?( AVALUE[A]={Ri,MA}?(在 P处 A不待用,
不活跃 )?(在 P处 A的待用信息 =max))
则可将 Ri作为返回值 R,在此之前对 RVALUE[Ri]
中的每个变量 B,如果 B不是 x,或者 B是 x也是 z，
但不是 y而且 y? RVALUE[Ri]则：
16
若 B在主存中无副本,即 MB? AVALUE[B]时生成复制副本指令 MOV Ri MB；
修改 Ri的数组 Ri中的变量地址描述数组,即若 B
同 y?(B 同 z?y? RVALUE[Ri]) 时,则令
AVALUE[B]={MB,Ri},否 则 令 AVALUE[B] ＝
{MB}；
删除 RVALUE[Ri]中的 B。
给出 R,返回 。
上述算法是对前面约定的简单指令系统而言的。
指令系统复杂会使 getreg的算法也因之复杂。
17
五,代码生成算法对于语句 P,x:=y op z,执行下列步骤：
(1) 调用 getreg(P,x:=y op z),设返回的寄存器为 R,供 x
存放现行值 。
(2) 由变量地址描述数组 AVALUE[y],AVALUE[z]确定变量 y,z的现行值存放位置 y?,z?,当现行值在寄存器中时,
便将该寄存器作为 y?或 z?。
(3) 如果 yR,生成目标代码
MOV y? R
Op R z?
否则只生成目标代码 op R z?。
当 y?或 z?为 R时,删除 AVALUE[y]或 AVALUE[z]中的 R。
(4) 修 改 两 个 描 述 数 组,表示 x 占用 R,即含
AVALUE[x]={R},RVALUE[R]={x}。
(5) 如果在 P点 y或 z不再被引用 (不待用,不活跃 ),并且其现行值占用某寄存器 R?,则释放该寄存器 R?,即从
RVALUE[R?]中删去 y或 z,从 AVALUE[y] 或 AVALUE[z]中删去 R?。
18
§ 8.3 寄存器分配以寄存器为操作数的指令比内存单元作为操作数的指令速度更快，因此要生成有效的代码就得充分利用寄存器，这在简单代码生成器中已有考虑，
但它局限在基本块中。从全局来看，将循环中经常使用的变量固定使用寄存器以提高代码运行效率是全局寄存器分配的一种策略，将数量确定的一组寄存器固定分配给哪几个变量才能获益最多呢？这需要确定一个标准，通常以执行代价能省多少来衡量。
19
一,执行代价的节省一条指令的执行代价为该指令访问主存单元的次数,其中指令本身也需访问主存后才能取得,以
§ 8.1的指令为例：
寄存器型指令,op Ri,Rj
执行代价为 1
直接地址型指令,op Ri,M
执行代价为 2
变址型指令,op Ri,c(Rj)
执行代价为 2
寄存器间接型指令,op Ri,*Rj
执行代价为 2
间接地址型指令,op Ri,*M
执行代价为 3
20
与原来简单代码生成算法相比,如果循环中某变量被固定分配了寄存器,则有两种可能节省执行代价；
(1) 在原来的算法中,仅当变量在基本块中被定值后,其值才占有寄存器 。 如果一变量固定占有了寄存器,那么在该变量定值前每引用一次,就可少访问主存一次,执行代价就省 1。
如果循环 L中变量 x在基本块 B中定值前引用次数为 USE(x,B),那么将寄存器固定分配给 x后,在一次循环 L中可省的执行代价为：
USE(x,B)
B?L
21
(2) 在原来的算法中,如果一变量在基本块中被定值,出了基本块以后是活跃的,则在基本块出口处应生成 MOV R Mx指令,将变量 x在寄存器 R中的值保存到主存单元 Mx中,释放寄存器 R,供后继基本块使用 。 这条存储指令的执行代价为 2,现在对循环 L中的变量 x固定分配给寄存器,如果 x
在基本块中定值且出基本块后活跃用 LIVE(x,
B)=1来表示 (否则 LIVE(x,B)=0),那么基本块出口处的上述存储指令就可以省去,执行代价因此省 2，
由于这个原因,变量 x在循环 L中可省的执行代价为,? LIVE(x,B)*2
B?L
22
所以循环中每个变量 x如果被固定分配到寄存器,
总共可省执行代价为：
[ USE(x,B)+ LIVE(x,B)*2]
B?L
显然在循环 L中有 n个可作固定分配寄存器,应分配给执行代价省得最多的 n个变量 。
编译原理第八章 代码生成上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 6月
2
本章目的词法分析、语法分析、语法制导翻译及中间代码生成是编译的前端，而目标代码的生成是编译的后端，编译优化是可选部件。代码生成的任务是在编译前端生成的中间代码的基础上，生成等价有效的目标代码，这也是一种程序变换，变换的结果是产生目标代码。等价是任一种程序变换的基本要求，因此讨论将集中在目标代码和如何产生有效的目标代码上。所谓有效，当然是指目标代码占用的空间要省，运行的时间要短，这涉及充分利用寄存器和生成优化的代码序列的问题
3
第八章 代码生成
§ 8.1 目标代码一,代码生成器的输入与输出输入必须含有两部分：一部分是前端生成的中间代码,
它是三地址表示的四元式 。 另一部分便是符号表,这是由前端产生的,用以决定中间代码的数据对象运行地址的所有信息都在符号表中存放着 。
输出是目标代码,其形式可以是绝对机器语言,可重定位机器语言或汇编语言的代码 。
4
二,目标机器目标机多种多样,要生成好的目标代码,必须熟悉目标机,
特别是指令系统的细节 。 作为一般讨论,我们不打算讨论十分依赖于目标机器细节的内容,当然也不可能生成完整的满意的代码 。 我们只讨论一般技术,只针对一种抽象的目标机,它是简单的,作为各种目标机的子集,它是公共的 。
目标机具有几个通用寄存器,它们同时可作为变址器 。
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
6
其他操作指令的指令意义为：
(1) MOV Ri,M (Ri)?M
(2) MOV M,Ri (M)?Ri
(3) J X goto X
(4) CMP A,B 将 A和 B的存储内容进行比较,
视 A<B,A＝ B,或 A>B,分别设 CJ＝ 0,CJ＝ 1,CJ＝ 2，
(5) J rop X,rop与 CJ,状态一致时 goto X，
例如 rop为 <则 CJ＝ 0,goto X。
7
§ 8.2 一个简单代码生成器一,待用信息定义 8.1 在基本块 B中,变量 A在 i点的值,j点引用,
并且 i?j的通路上没有 A的其他定值和引用,则 j为 i
处 A的下一个引用点,即待用信息 。
基本块内 i处一个变量的活跃信息是指基本块出口之后该变量是否还要被引用,而待用信息则是指基本块内的下一引用点,这些是寄存器分配所需的信息 。 因此在为基本块的每一语句生成目标代码时,
应先求出该语句中变量的待用信息和活跃信息 。 为计算变量的待用信息,在变量符号表中设待用信息栏和活跃信息栏,然后执行下列步骤：
8
(1) 开始时，把基本块中各变量的符号表的待用信息栏初始化为“非待用”，活跃信息栏按该变量在基本块出口后是否活跃而初始化为“活跃”或
“非活跃”。
(2) 从出口语句到入口语句反向扫描每个语句 (如：
P,x:=y op z),依次执行：
将符号表中 x变量的待用信息和活跃信息附加到语句 P上；然后将 x在符号表中的信息置为,非待用,,
,非活跃,。
将符号表中 y,z变量的待用信息和活跃信息附加到语句 P上；然后将符号表 y,z的待用置为 P,活跃栏置为,活跃,。
9
[例 8.1] 基本块中有四个语句如图 8.1的表左所列,
表右列出各变量的符号表的待用信息栏和活跃信息,待用信息用数字 1－ 4表示下一引用点的语句位置,0表示非待用；活跃信息由,＋,表示活跃,,－,表示不活跃,每个语句的变量的待用信息和活跃信息分别用上标和下标表示 。
(1) t3+:=a2+-b0-
(2) u4+:=a3++c0-
(3) v4+:=a0--t0-
(4) v0+:=v0-+u0-
图 8.1 求基本块内变量的待用信息 (例 8.1)
初始
10
二,寄存器描述和地址描述为了在代码生成中充分利用寄存器,生成尽可能简短的代码,将使用寄存器描述数组
RVALUE[Ri]记录寄存器 Ri是空闲着,还是已分配给某些变量；将使用变量地址描述数组
AVALUE[A]来记录变量 A的现行值是存放在某个寄存器中,还是在某个主存单元中,或者既在寄存器中又在主存中 。
11
三,如何生成目标代码给出了一个语句,例如,P,x:=y op z,如何生成目标代码呢？
这个语句通常可由二条指令来实现：
MOV y Ri
Op Ri z
第一条指令是将变量 y的现行值自它的存储单元
(仍用 y来表示 )传送到寄存器 Ri中 。 第二条指令将
Ri中的 y值与变量 z的值 (其存储位置仍用 z来表示 )
进行 op运算,结果 (即 x的值 )留在 Ri中,因此生成该语句的代码前必须确定保存 x值的寄存器 Ri。 换言之,为 x分配一个寄存器 Ri。 具体有以下几种情况：
12
(1) 最理想情况是：如果变量 y已占有寄存器
Ri(这由 AVALUE[y]可知 ),而且 y在 P以后不再被引用 (这由 P处 y的待用信息可知 )或 y同 x,即
P,x:=x op z,则 y占用的寄存器 Ri即可分配给
x。 这种情况下生成的代码只是第二条指令,
为最简短 。
(2) 若还有空余的可用寄存器 Ri,则将 Ri分配给 x,生成上述二条指令 。
13
(3) 如果已无可用寄存器,即寄存器均被占用,则只能从被占用的寄存器中选择一个 Ri,先将占用
Ri的变量的现行值逐一保存到主存单元中,然后才可分配给 x使用 。 选择标准是使这种复制副本的代价尽可能小,很明显,最好选在主存单元中已副本的占用 Ri的变量,或者该变量在 P以后不再被引用或在最远的将来才会被引用 。 在这种情况下,
如果变量 M在 Ri中的值需要在主存单元中复制副本,
则在 Ri分配给 x前,还得生成：
MOV Ri M
指令,此时生成的目标指令就可能多于两条 。
(4) 当然在上述寄存器重新分配,变量存储发生变化时还得修改相应的寄存器描述数组和地址描述数组 。
14
四,函数 getreg(P:x:=y op z)
给出参数 P,x:=y op z,当然也意味着给出了语句 P处的待用信息,活跃信息及当时各寄存器描述数组和变量地址描述数组,据此,为变量 x分配寄存器 R,以 R作为函数值返回 。
其算法为：
(1) 如果 y的现行值在某寄存器 Ri中,而该寄存器仅由 y
所占用,即 AVALUE[y]＝ {Ri,… }?RVALUE[Ri]={y}，
并且 y或与 x是同一标识符,或在 P以后不再引用,则此
Ri即为返回值 R,转 (4)。
(2) 存 在 尚 未 分 配 的 寄 存 器 Ri,即? i(1≤i≤n)?
RVALUE[Ri]={}时,Ri为返回值 R,转 (4)。
15
(3) 从已分配的 n个寄存器中选一个 Ri(设它为变量
A等所占用 ),使得占有 Ri的变量或者在主存中有副本,或者在 P点以后不再被引用,或者待用信息最大,即? i(1≤i≤n)?RVALUE[Ri] ＝
{A,… }?( AVALUE[A]={Ri,MA}?(在 P处 A不待用,
不活跃 )?(在 P处 A的待用信息 =max))
则可将 Ri作为返回值 R,在此之前对 RVALUE[Ri]
中的每个变量 B,如果 B不是 x,或者 B是 x也是 z，
但不是 y而且 y? RVALUE[Ri]则：
16
若 B在主存中无副本,即 MB? AVALUE[B]时生成复制副本指令 MOV Ri MB；
修改 Ri的数组 Ri中的变量地址描述数组,即若 B
同 y?(B 同 z?y? RVALUE[Ri]) 时,则令
AVALUE[B]={MB,Ri},否 则 令 AVALUE[B] ＝
{MB}；
删除 RVALUE[Ri]中的 B。
给出 R,返回 。
上述算法是对前面约定的简单指令系统而言的。
指令系统复杂会使 getreg的算法也因之复杂。
17
五,代码生成算法对于语句 P,x:=y op z,执行下列步骤：
(1) 调用 getreg(P,x:=y op z),设返回的寄存器为 R,供 x
存放现行值 。
(2) 由变量地址描述数组 AVALUE[y],AVALUE[z]确定变量 y,z的现行值存放位置 y?,z?,当现行值在寄存器中时,
便将该寄存器作为 y?或 z?。
(3) 如果 yR,生成目标代码
MOV y? R
Op R z?
否则只生成目标代码 op R z?。
当 y?或 z?为 R时,删除 AVALUE[y]或 AVALUE[z]中的 R。
(4) 修 改 两 个 描 述 数 组,表示 x 占用 R,即含
AVALUE[x]={R},RVALUE[R]={x}。
(5) 如果在 P点 y或 z不再被引用 (不待用,不活跃 ),并且其现行值占用某寄存器 R?,则释放该寄存器 R?,即从
RVALUE[R?]中删去 y或 z,从 AVALUE[y] 或 AVALUE[z]中删去 R?。
18
§ 8.3 寄存器分配以寄存器为操作数的指令比内存单元作为操作数的指令速度更快，因此要生成有效的代码就得充分利用寄存器，这在简单代码生成器中已有考虑，
但它局限在基本块中。从全局来看，将循环中经常使用的变量固定使用寄存器以提高代码运行效率是全局寄存器分配的一种策略，将数量确定的一组寄存器固定分配给哪几个变量才能获益最多呢？这需要确定一个标准，通常以执行代价能省多少来衡量。
19
一,执行代价的节省一条指令的执行代价为该指令访问主存单元的次数,其中指令本身也需访问主存后才能取得,以
§ 8.1的指令为例：
寄存器型指令,op Ri,Rj
执行代价为 1
直接地址型指令,op Ri,M
执行代价为 2
变址型指令,op Ri,c(Rj)
执行代价为 2
寄存器间接型指令,op Ri,*Rj
执行代价为 2
间接地址型指令,op Ri,*M
执行代价为 3
20
与原来简单代码生成算法相比,如果循环中某变量被固定分配了寄存器,则有两种可能节省执行代价；
(1) 在原来的算法中,仅当变量在基本块中被定值后,其值才占有寄存器 。 如果一变量固定占有了寄存器,那么在该变量定值前每引用一次,就可少访问主存一次,执行代价就省 1。
如果循环 L中变量 x在基本块 B中定值前引用次数为 USE(x,B),那么将寄存器固定分配给 x后,在一次循环 L中可省的执行代价为：
USE(x,B)
B?L
21
(2) 在原来的算法中,如果一变量在基本块中被定值,出了基本块以后是活跃的,则在基本块出口处应生成 MOV R Mx指令,将变量 x在寄存器 R中的值保存到主存单元 Mx中,释放寄存器 R,供后继基本块使用 。 这条存储指令的执行代价为 2,现在对循环 L中的变量 x固定分配给寄存器,如果 x
在基本块中定值且出基本块后活跃用 LIVE(x,
B)=1来表示 (否则 LIVE(x,B)=0),那么基本块出口处的上述存储指令就可以省去,执行代价因此省 2，
由于这个原因,变量 x在循环 L中可省的执行代价为,? LIVE(x,B)*2
B?L
22
所以循环中每个变量 x如果被固定分配到寄存器,
总共可省执行代价为：
[ USE(x,B)+ LIVE(x,B)*2]
B?L
显然在循环 L中有 n个可作固定分配寄存器,应分配给执行代价省得最多的 n个变量 。
