第9章目标代码生成 目标代码生成是把语法分析优化后的中间代码变换成目标 代码。目标代码的形式主要包括如下3种形式: 1、具有绝对地址的机器语言程序。能立即执行的机器语言 代码,主程序与子程序需要同时编译。 2、可浮动的机器语言程序。目标程序由若干个目的模块组 成,各模块包含目标程序的一部分代码,这些代码可在存 储空间浮动,装入到存储空间的任何位置。需要连接装入 程序把它们和某些运行程序连接起来才能运行 3、汇编语言形式的程序。尚须经过汇编程序汇编,转换成 可执行的机器语言代码
1 第9章 目标代码生成 目标代码生成是把语法分析优化后的中间代码变换成目标 代码。目标代码的形式主要包括如下3种形式： 1、具有绝对地址的机器语言程序。能立即执行的机器语言 代码，主程序与子程序需要同时编译。 2、可浮动的机器语言程序。目标程序由若干个目的模块组 成，各模块包含目标程序的一部分代码，这些代码可在存 储空间浮动，装入到存储空间的任何位置。需要连接装入 程序把它们和某些运行程序连接起来才能运行。 3、汇编语言形式的程序。尚须经过汇编程序汇编，转换成 可执行的机器语言代码
基本块 所谓基本块是指按顺序执行(不含分支结构 的中间代码(四元式)序列,其中只有一个入 口和一个出口,入口是第一个操作,出口是最 后一个操作。 对于基本块来说,执行只能从其入口进入,出口退 出 对于一个中间代码序列,可以把它划分为一系列的 基本块,在各基本块范围内,进行代码优化以及目 标代码生成
2 基本块 • 所谓基本块是指按顺序执行（不含分支结构） 的中间代码（四元式）序列，其中只有一个入 口和一个出口，入口是第一个操作，出口是最 后一个操作。 –对于基本块来说，执行只能从其入口进入，出口退 出。 –对于一个中间代码序列，可以把它划分为一系列的 基本块,在各基本块范围内，进行代码优化以及目 标代码生成
基本块划分的算法 1.求出程序中各个基本块的入口语句,它们是: (1)程序的第一个语句,或 (2)能由条件转移语句或无条件转移语句转移到的语句,或 (3)紧跟在条件转移语句或无条件转移语句后面的语句 2.对求出的每一入口语句,构造其所属的基本块 (即找出口语句)由该入口语句到: (1)下一入口语句或到 (2)转移语句 或到 (3)停语句之间的语句序列组成一个基本块 3.凡未被纳入某一基本块的语句,都是程序中控制流无法到 达的语句,可从程序中删除
3 基本块划分的算法 1．求出程序中各个基本块的入口语句，它们是： (1) 程序的第一个语句，或 (2) 能由条件转移语句或无条件转移语句转移到的语句，或 (3) 紧跟在条件转移语句或无条件转移语句后面的语句. 2．对求出的每一入口语句，构造其所属的基本块 （即找出口语句）由该入口语句到： (1) 下一入口语句 或到 (2) 转移语句 或到 (3) 停语句 之间的语句序列组成一个基本块。 3．凡未被纳入某一基本块的语句，都是程序中控制流无法到 达的语句，可从程序中删除
§9.2一个假想的计算机模型 以字节编址,主存容量为216个字节,机器字长为16bit 有8个通用寄存器:RO,R1,…,R7,且长度也为16bit 每条指令占用一个机器字,形式如下 OP arc, dst OP表示操作码,占4bit;arc和dst分别表示源操作数 和目的操作数的地址,各占6bit 由于6bit不能对整个内存空间进行寻址,因此将操作 数或其地址存放在紧跟指令之后的单元中
4 §9.2 一个假想的计算机模型 • 以字节编址，主存容量为2 16个字节，机器字长为16bit, 有8个通用寄存器：R0,R1,…,R7，且长度也为16bit。 每条指令占用一个机器字，形式如下： OP arc, dst OP表示操作码，占4bit；arc和dst分别表示源操作数 和目的操作数的地址，各占6bit。 由于6bit不能对整个内存空间进行寻址，因此将操作 数或其地址存放在紧跟指令之后的单元中
表9-1一个假想机的寻址方式 编码 名称 助记符 含义 汇编后的情况 寄存器模式 R(R)为操作数 2 间接寄存器模式 R(R)为操作数地址 变址模式 x(R)(R)+x为操作数地址X之值在本指令之后的单元中 间接变址模式 xB)/(R)+x为存放操作数地x之值在本指令之后的单元中 址的单元地址 文字常数X在本指令之后的单 5 直接操作数 #xx为操作数 元中 x为符号名,其值为操X的数据单元地址在本指令之 绝对地址 X 作数 后的单元中 间接地址 XX为符号名,其值为操作X的数据单元地址在本指令之 数地址 后的单元中
5
常用指令 1.传送指令: MOV arc,dst(arc)=→dst 2.运算指令: Add arc,dst(dst)+(arc)→dst SUB arc. dst (dst)-(arc)→dst 3.比较指令: CMP arc,dst 执行arc-dst,并对状态字PSW相应的标志位置位。 当(arc)=(dst)时,PSW的标志位Z置1。 当arc)-(dst)时,PSW的标志位N置1。 当arc)>(dst)时,PSW的标志位P置 4.控制指令: BR,j」,j=,j≠}ds:分别表示无条件、N=1、NvZ=1、Z=1 和Z=0转移
6 常用指令 1. 传送指令: MOV arc, dst (arc)dst 2. 运算指令：ADD arc, dst (dst)+(arc) dst SUB arc, dst (dst)-(arc)dst 3. 比较指令： CMP arc, dst 执行arc-dst，并对状态字PSW相应的标志位置位。 当(arc)=(dst)时， PSW的标志位Z置1。 当(arc)(dst)时， PSW的标志位P置1。 4. 控制指令： {BR, j<, j, j=, j} dst: 分别表示无条件、N=1、NZ=1、Z=1 和Z=0转移
常用四元式的的目标代码 、四元式(+,A,B,T)对3、四元式(jnZ,A,一,P) 应的指令为: 对应的指令为 MOVA, RO MOⅤA,R0 addB, RO: CMP RO.O MOV RO. T: 1≠P 其余二元操作四元式的翻译4、四元式(J,一,一,P)对 与此类拟; 应的指令为:BRP; 2、四元式(=,B,一,A)对5、四元式(Jrop,A,B,P) 应的指令为: 对应的指令为 MOVB, RO MOVA, RO MOV RO, A CMP RO, B: Drop P
7 常用四元式的的目标代码 1、四元式（+，A，B，T）对 应的指令为： MOV A，R0； ADD B，R0； MOV R0, T； 其余二元操作四元式的翻译 与此类拟； 2、四元式（=，B，—，A）对 应的指令为： MOV B，R0； MOV R0，A； 3、四元式（jnZ，A，—，P） 对应的指令为: MOV A，R0； CMP R0, 0; j P’； 4、四元式（J，—，—，P）对 应的指令为： BR P’； 5、四元式（Jrop，A，B，P） 对应的指令为 MOV A，R0； CMP R0，B； Jrop P’；
四元式目标地址的确定 (1)在把四元式翻译为目标指令时,是按四元式表中 四元式的顺序依次执行,为计算每个四元式所对应 的目标地址,必须累计每条指令的字节数。到达某 四元式时,所累计的字节数就是该四元式的目标地 址(相对的)。 (2)转移语句中转移地址所指的四元式是基本块的入 口语句,把这种语句按岀现的顺序生成汇编代码标 号L1, 等,并用一张标号表存放起来表格内 容为四元式序号与对应汇编代码标号
8 四元式目标地址的确定 （1）在把四元式翻译为目标指令时，是按四元式表中 四元式的顺序依次执行，为计算每个四元式所对应 的目标地址，必须累计每条指令的字节数。到达某 四元式时，所累计的字节数就是该四元式的目标地 址（相对的）。 （2）转移语句中转移地址所指的四元式是基本块的入 口语句，把这种语句按出现的顺序生成汇编代码标 号L1，L2…...等，并用一张标号表存放起来,表格内 容为四元式序号与对应汇编代码标号
§9.3代码生成程序的雏形 为每个基本块的生成高质量代码: 总的指令条数要少; 尽可能利用寄存器,少产生访问内存的指令,为 此需要充分合理的利用寄存器: 尽可能把后面还要引用的变量仍保存在寄存器中; 应把不再使用的变量所占用的寄存器及时释放掉; 为此需引入两个概念:基本块内变量的引用信息和 活跃信息
9 §9.3 代码生成程序的雏形 • 为每个基本块的生成高质量代码： – 总的指令条数要少； – 尽可能利用寄存器，少产生访问内存的指令，为 此需要充分合理的利用寄存器： • 尽可能把后面还要引用的变量仍保存在寄存器中； • 应把不再使用的变量所占用的寄存器及时释放掉； • 为此需引入两个概念：基本块内变量的引用信息和 活跃信息
引用信息与活跃信息 如果变量A在某点P的值(P是四元式的编号)在从P可 达的某四元式q中被引用,则称变量A在P点是活跃的, 并称四元式q是变量A的引用信息。 (p) A=B+C, A在P点是活跃的 (r) E=A+F (a D=A+v q是变量A的引用信息 假定 ①所有的临时变量均看作是出基本块后的非活跃变量 ②所有的非临时变量都看作是出基本块后的活跃变量
10 引用信息与活跃信息 • 如果变量A在某点P的值（P是四元式的编号）在从P可 达的某四元式q中被引用，则称变量A在P点是活跃的， 并称四元式q是变量A的引用信息。 (p) A=B+C; A在P点是活跃的 (r) E=A+F; ….. (q) D=A+V; q是变量A的引用信息 假定 ①所有的临时变量均看作是出基本块后的非活跃变量。 ②所有的非临时变量都看作是出基本块后的活跃变量