编译原理 第九章 目标代码生成

编译原理 第九章 目标代码生成

概述

目标代码生成旨在把语义分析后或优化后的中间代码变换成目标代码。它以源程序的中间代码和符号表中的信息作为输入,以语义等价的目标程序作为输出。

设计目标代码生成器,要着重考虑虑指令的选择、寄存器的分配与指派以及指令的计算顺序等问题。

代码生成器的输入

代码生成器的输入包括中间代码和符号表。中间代码的形式有很多种,如后缀 式、四元式、三元式、间接三元式、语法树以及 DAG 图等。

目标代码生成器可以利用符号表中的信息来决定中间代码里的名字所表示的数据对象在运行时的地址,它是可重定位的地址。

代码生成器的输出

目标代码一般具有如下 3 种形式:

  • 绝对机器语言代码
    • 可立即执行,所有地址均已定位
  • 可重定位机器代码
    • 有在连接装配程序将其与某些运行程序连接后,才能转换成可执行的机器语言代码
  • 汇编语言代码
    • 只有经过汇编程序汇编后,才能转换成可执行的机器语言代码

指令的选择

目标代码的质量是由代码的运行速度和代码所占空间的大小决定的。目标机本身的特性也很重要。

寄存器的分配

寄存器具有访问速度快、操作指令短的特点,只是数量较少。寄存器的使用涉及如下两点:

  • 寄存器的分配。在程序的某一点,确定要放在寄存器中的变量集合。
  • 寄存器的指派。选出变量将要存放的具体寄存器。

计算顺序的选择

一个有效的计算顺序要 求存放中间结果的寄存器数量尽可能的少,以提高目标代码的运行效率。

目标机器模型

本书中,目标代码的形式是汇编语言。则目标机的指令也就是汇编语言的语法。

常用目标机指令:

四种指令的寻址方式:

一个简单的代码生成器

基本块:一段连续的顺序执行的语句序列,拥有一个入口和一个出口。入口是该语句序列的首语句,出口时该语句序列的尾语句。

活跃:一个基本块中的一个名字在程序中的某个给定点是活跃的,是指如果在程序中(包括在本基本块或在其他基本块中)它的值在该点以后被引用。

将三地址代码序列划分成若干基本块的方法:

  1. 基本块的入口语句
    • 代码序列的第一条语句
    • 能由条件或者无条件转移语句转移到的语句
    • 紧随条件转移语句后面的语句
  2. 依据 1 得到的每一条入口语句,构建其基本块
    • 入口语句与下一入口语句(不包括该入口语句)之间的语句序列
    • 入口语句与下一转移语句(包括该转移语句)之间的语句序列
    • 入口语句与一停语句(包括该停语句)之间的语句序列
  3. 删除那些未出现在任何基本块中的语句

待用信息与活跃信息

在一个基本块中,如果中间代码 i 对 A 定值,中间代码 j 引用了 A 值,且从 i 到 j 之间没有 A 的其他定值,则称 j 是代码 i 中变量 A 的待用信息,并且,A 在 i 处是活跃的。

待用信息有助于把基本块内还要被引用的变量值尽可能地保存在寄存器中,同 时,把基本块内不再被引用的变量所占用的寄存器及早释放。

计算变量待用信息的方法:

  1. 开始时,把基本块中各变量在符号表中的待用信息域置为“非待用”,并根 据该变量在基本块出口之后是否活跃,把活跃信息域置为“活跃”或“非活跃”。
  2. 从基本块出口到基本块入口由后向前依次处理每条中间代码。对形如 \(i: A:=B\ op\ C\) 的中间代码(形式为 \(A:=op\ B\)\(A:=B\) 也适用,只是其中不涉及 C),依次执行下述步骤:
    1. 把符号表中变量 A 的待用信息和活跃信息附加到中间代码 i 上;
    2. 把符号表中 A 的待用信息和活跃信息分别置为“非待用”和“非活跃”;
    3. 把符号表中变量 B 和 C 的待用信息和活跃信息附加到中间代码 i 上;
    4. 把符号表中 B 和 C 的待用信息均置为 i,活跃信息均置为“活跃”。

寄存器描述和地址描述

使用寄存器描述数组 RVALUE 和变量地址描述数组 AVALUE 来描述变量占用寄存器的详细情况。

\(RVALUE[R_i]=\{A, B\}\) 表示寄存器 \(R_i\) 被 A 和 B 占用;AVALUE 动态地记录着各变量现行值的存放位置,比如,\(AVALUE[X]=\{R_i, R_j\}\) 表示变量 X 存放在寄存器 \(R_i\)\(R_j\) 中。

简单代码生成算法

GETREG 寄存器分配算法,其参数是第 i 条中间代码 \(i:X:=Y\ op\ Z\),该函数返回存放 X 的现行寄存器:

简单代码生成算法,对每条中间代码 \(i:X:=Y\ op\ Z\),完成下述步骤:

典型中间代码对应的目标代码:

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×