第八章 代码生成
编译器的最后一个阶段的工作是代码生成，不管代码生成，它取源程序的中间表示作输人都是适用的。
8.1 代码生成器的设计中的问题
8.1.1 目标程序
- 可执行目标模块
- 可重定位目标模块
- 允许程序模块分别编译
- 调用其它先前编译好的程序模块
- 汇编语言程序
- 目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素
- 指令的速度和机器特点是另一些重要的因素
8.1.3 寄存器分配
- 运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也快一些
- 寄存器分配
选择驻留在寄存器中的一组变量 - 寄存器指派
挑选变量要驻留的具体寄存器8.1.4 计算次序的选择
某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果8.2 目 标 机 器
8.2.1 目标机器的指令系统
- 选择可作为几种微机代表的寄存器机器
- 四字节组成一个字，有n个通用寄存器R0,R1, …,Rn-1。
- 二地址指令op源 目的
MOV {源传到目的}
ADD {源加到目的}
SUB {目的减去源}8.2.2 指令的代价
指令代价取成1加上它的源和目的地址模式的附加代价8.3 基本块和流图
8.3.1 基本块
- 基本块：连续的语句序列，控制流从它的开始进入，并从它的末尾离开
- 再用有向边表示基本块之间的控制流信息，就能得到程序的流图
- 三地址语句序列的划分基本块
- 三地址语句x := y + z引用y和z并对x定值
- 一个名字的值在基本块的某一点以后还要引用的话，我们说这个名字在该点是活跃的
- 基本块的等价
- 两个基本块计算一组同样的表达式
- 这些表达式的值分别代表同样的活跃名字的值
- 有很多等价变换可用于基本块
- 把控制流信息加到基本块集合，形成一个有向图来表示程序
- 首结点、前驱、后继
- 什么是循环?
- 所有结点是强连通的
- 唯一的循环入口
- 外循环和内循环
8.3.4 下次引用信息
- 为每个三地址语句x := y op z决定x、y和z的下次引用信息
- 对每个基本块从最后一个语句反向扫描到第一个语句，可以得到下次引用信息
- 利用下次引用信息，可以压缩临时变量需要的空间
8.4 一个简单的代码生成器
- 依次考虑基本块的每个语句，为其产生代码
- 假定三地址语句的每种算符都有对应的目标机器算符
- 假定计算结果留在寄存器中尽可能长的时间，除非： 该寄存器要用于其它计算，或者 到基本块结束
8.4.1 寄存器描述和地址描述
- 在代码生成过程中，需要跟踪寄存器的内容和名字的地址
- 寄存器描述记住每个寄存器当前存的是什么
- 在任何一点，每个寄存器保存若干个(包括零个)名字的值
- 名字的地址描述记住运行时每个名字的当前值可以在哪个场所找到
- 这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合
- 这些信息可以存于符号表中
- 这两个描述在代码生成过程中是变化的。
8.4.2 代码生成算法
对每个三地址语句x := y op z- 调用函数getreg决定放y op z计算结果的场所L
- 查看y的地址描述,确定y值当前的一个场所y
.如果y的值还不在L中，产生指令MOV y，L - 产生指令op z
，L，其中z是z的当前场所之一 - 如果y和/或z的当前值不再引用，在块的出口也不活跃，并且还在寄存器中，那么修改寄存器描述
8.4.3 寄存器选择函数
函数getreg返回保存x := y op z的x值的场所L - 如果名字y在R中，这个R不含其它名字的值,并且在执行x := y op z后y不再有下次引用，那么返回这个R作为L。
- 否则，返回一个空闲寄存器，如果有的话
- 否则，如果x在块中有下次引用，或者op是必须用寄存器的算符，那么找一个已被占用的寄存器R(可能产生MOV R，M指令，并修改 M的描述 )
- 否则，如果x在基本块中不再引用，或者找不到适当的被占用寄存器，选择x的内存单元作为L。
8.4.4 为变址和指针语句产生代码
变址与指针运算的三地址语句的处理和二元算符的处理相同8.4.5 条件语句
- 实现条件转移有两种方式：
- 根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正
- 用条件码来表示计算的结果或装入寄存器的值是负、零还是正
- 根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正