选择好计算的次序，充分利用目标机的特点
指令选择
任务
为每条中间语言语句选择恰当的目标机指令或指令序列
原则
• 首先要保证语义的一致性；若目标机指令系统比较完 备，为中间语言语句找到语义一致的指令序列模板是 很直接的（不必考虑执行效率的情形下） • 其次要权衡所生成代码的效率（考虑时间/空间代价）
• 在基本块范围内考虑如何充分利用寄存器的问题 原则： 尽可能地让变量的值保留在寄存器中
尽可能引用变量在寄存器中的值
• 借助于在基本块范围内建立变量的待用信息链和 活跃信息链
一个简单的代码生成算法
待用信息
• 在一个基本块中，四元式i对变量A定值，如果i后面 的四元式j要引用A，且从i到j的四元式没有其它对A的 定值点，则称j是四元式i中对变量A的待用信息，同时 也称A是活跃的。 • 如果A被多处引用，则构成了A的待用信息链和活跃 信息链。 • 为了取得每个变量在基本块内的待用信息和活跃信 息，可从基本块的出口由后向前扫描，对每个变量建 立相应的待用信息链与活跃信息链。
目标代码生成要考虑的主要问题 一个简单的代码生成算法
由上述算法从 DAG 生成代码
基于树重写的代码生成 简单的图着色物理寄存器分配算法
代码生成要考虑的主要问题
指令选择
目标机指令集的性质和中间代码的形式决定 指令选择的难易
寄存器分配
充分、高效地使用寄存器
指令调度
• 对相干图进行着色（coloring）
使用k（物理寄存器数量）种颜色对相干图进行着色， 使任何相邻的结点具有不同的颜色（即两个相干的 伪寄存器不会分配到同一个物理寄存器）。
简单的图着色物理寄存器分配算法
一种启发式图着色算法
“一个图是否能用 k 种颜色着色”是 NP-完全问题 以下是一个简单的启发式 k-着色算法： • 假设图 G 中某个结点 n 的度数小于 k，从G 中删除 n 及其邻边得到图 G’，对 G 的k-着色问题可转化为 先对G’ k-着色，然后给结点 n 分配一个其相邻结点 在 G’ 的k-着色中没有使用过的颜色。 重复这个过程从图中删除度数小于 k 的结点，如果 可以到达一个空图，说明对原图可以成功实现 k-着 色；否则，原图不能成功实现 k-着色，可从 G 中选 择某个结点作为泄露候选，将其删除，算法可继续。
表中“待用信息链”与“活跃信息链”的每列从左至右为每 从后向前扫描一个四元式时相应变量的信息变化情况，空白 处为没变化。 待用信息和活跃信息在四元式上的标记如下所示： (1) T(3)L:=A(2)L-BFL (2) U(3)L:=AFL-CFL (3) V(4)L:=TFF+U(4)L (4) DFL:=VFF+UFF
这一点较难做到，因为执行效率往往与该语句的上下 文以及目标机体系结构（如流水线）有关
指令选择举例
为TAC 语句选择指令模板
假设一个目标机指令系统（一个简单汇编语言）
例 TAC 语句 a:=b+c 可转换为如下代码序列
MOV ADD MOV b, R0 c, R0 R 0, a
/* b 装入寄存器 R0 */ /* c 加到 R0 */ /* 存 R0 到 a */

计算待用信息的算法
（1）对各基本块的符号表中的“待用信息”栏 和“活跃信息”栏臵初值，即把“待用信息” 栏臵“非待用”，对“活跃信息”栏按在基本 块出口处是否为活跃而臵成“活跃”或“非活 跃”。这里假定变量都是活跃的，临时变量都 是非活跃的。
（2）从基本块出口到基本块入口由后向前依次 处理每个四元式。对每个四元式i: A:=B op C， 依次执行下述步骤：
a)
把符号表中变量A的待用信息和活跃信息附加到四 元式i上。 b) 把符号表中变量A的待用信息栏和活跃信息栏分别 臵为“非待用”和“非活跃”。（由于在i中对A的 定值只能在i以后的四元式才能引用，因而对i以前 的四元式来说A是不活跃也不可能是待用的） c) 把符号表中变量B和C的待用信息和活跃信息附加到 四元式i上。 d) 把符号表中变量B和C的待用信息栏臵为“i”，活跃 信息栏臵为“活跃”。
t:=a-b u:=a-c v:=t+u d:=v+u
MOV a,R0 SUB b,R0 u: = a－c MOV a,R1 SUB c,R1 v: = t＋u ADD R1,R0 d: = v＋u ADD R1,R0 MOV R0,d
由上述算法从 DAG 生成代码
从某个基本块的 DAG 表示得到的两段 TAC 代码
如 B` 或 C` 为R，则删除 AVALUE[B] 或 AVALUE[C] 中的 R
一个简单的代码生成算法
基本块的代码生成算法 （续前页）
·令 AVALUE[A]={R}，并令 RVALUE[R]={A}，以表示变量 A 的现行
值只在 R 中并且 R 中的值只代表 A 的现行值 。
·如 B 或 C 的现行值在基本块中不再被引用，它们也不是基本块出
一个简单的代码生成算法
寄存器描述数组和变量地址描述数组
• RVALUE[R] 描述寄存器 R 当前对应哪个变量 • AVALUE[A] 表示变量 A 的值存放在哪个寄存器中
一个简单的代码生成算法
基本块内 TAC 语句序列的简单代码生成
（假设只有形如 A:=B op C 的TAC 语句序列）
口之后的活跃变量（由语句 i 上的附加信息知道），并且其现行值在某 个寄存器 Rk 中，则删除 RVALUE[Rk] 中的 B 或C 以及 AVALUE[B] 或 AVALUE[C] 中的 Rk ，使该寄存器不再为 B 或 C 所占用。
step2: 处理完基本块中所有TAC 语句之后，对现行值在 某寄存器 R 中的每个变量 M，若它在出口之后是活跃 的，则生成 MOV 生成
一个简单代码生成器
目标代码生成在编译程序中的逻辑位臵
词法分析 字符流 单词流 语法分析树 中间表示 优化的中间表示 目标代码 优化的目标代码 语法分析 从中间表示 获取的流图 改进的流图 语义分析和中间代码生成 机器无关的代码优化 目标代码生成 针对机器的代码优化 指令调度 寄存器分配 窥孔优化
器分配算法将它们对应到真实寄存器或内存地址）。
其实也可以不是返回伪寄存器，而是在寄存器不够时返回一个内 存地址。
一个简单的代码生成算法举例
对于右图的基本块 （假定只有d在基本块的 出口是活跃的），利用上述算法可生成如下 代码序列：
语句 t: = a－b 生成的代码 寄存器描述 空寄存器 R0 包含 t R0 包含 t R1 包含 u R0 包含 v R1 包含 u R0 包含 d 地址描述 t 在 R0 中 t 在 R0 中 u 在 R1 中 u 在 R1 中 v 在 R0 中 d 在 R0 中 d 在 R0 中和存储器中
两遍的通用寄存器分配算法
• 第一遍先假定可用的通用寄存器是无限数量的，完 成指令选择 例如：前面介绍的简单代码生成算法中的 getreg 函数返回一个伪寄存器（不管物理寄存器的个数） • 第二遍将物理寄存器分配到伪寄存器。 物理寄存器数量不足时，会将一些伪寄存器泄露到 （spilled into）内存，图着色算法的核心任务是使 得泄露的伪寄存器数目最少。
T1:=a+b T2:=c+d T3:=e-T2 T4:=T1-T3 MOV a,R0 ADD b,R0 MOV c,R1 ADD d,R1 MOV e,R2 SUB R1,R2 SUB R2,R0 MOV R0,T4 T2:=c+d T3:=e-T2 T1:=a+b T4:=T1-T3 MOV c,R0 ADD d,R0 MOV e,R1 SUB R0,R1 MOV a,R0 ADD b,R0 SUB R1,R0 MOV R0,T4
• template 代表一棵树
• cost 是用来计算相应于该template代价的代码片段 • action 是使用该规则进行树重写时执行的代码片段
基于树重写的代码生成
例 若干VAX指令对应的树重写规则
基于树重写的代码生成
例 若干VAX指令对应的树重写规则
基于树重写的代码生成
函数 getreg（以 i: A:=B op C 为参数， 返回一个伪寄存器）
步骤：
• 若 RVALUE[R]={B} ，且在语句 i 之后 B 在基本块中不再被引用，同 时也不是基本块出口之后的活跃变量（由 i 上的附加信息可知道）， 则返回 R； • 否则，返回一个新的伪寄存器R’
注：这里的 getreg 返回伪寄存器（可以利用随后介绍的图着色寄存
从中间表示树生成代码
思路
• 根据树重写规则对中间表示树的子树逐步进行归 约，直至单个节点为止，该过程的所有子树集合构 成中间表示树的一种覆盖（cover）。 • 某个覆盖的代价是相应树重写规则的附加代价之和
• 找到一种代价最小的覆盖。 • 根据最小代价的覆盖进行代码生成。
简单的图着色物理寄存器分配算法
简单的图着色物理寄存器分配算法 基于寄存器相干图（register-interference graph） 的图着色寄存器分配算法
• 构造寄存器相干图 结点：每一个伪寄存器为一个结点。 边：如果程序中存在某点，一个结点在该点被定义， 而另一个结点在该点是活跃的，则在这两个结 点间连一条边。
第二段代码较优（少用了寄存器）
基于树重写的代码生成
例
a [ i ] := b 的一个可能的中间表示树
基于树重写的代码生成
树重写（Tree Rewriting）规则形如
其中 • replacement 代表树的单个节点 replacement template {cost} = {action}
step1：对每个TAC 语句i: A:=B op C，依次执行下述步骤：