第七章 目标代码的生成

1、第七章第七章 目标代码的生成目标代码的生成一个简单代码生成器一个简单代码生成器 目标代码生成目标代码生成在编译程序中的逻辑位置在编译程序中的逻辑位置词法分析词法分析语法分析语法分析语义分析和中间代码生成语义分析和中间代码生成机器无关的代码优化机器无关的代码优化针对机器的代码优化针对机器的代码优化目标代码生成目标代码生成字符流字符流单词流单词流语法分析树语法分析树中间表示中间表示优化的中间表示优化的中间表示目标代码目标代码优化的目标代码优化的目标代码从中间表示从中间表示获取的流图获取的流图改进的流图改进的流图指令调度指令调度寄存器分配寄存器分配窥孔优化窥孔优化 目标目标代码生成要考虑的主要问题代

2、码生成要考虑的主要问题 一个一个简单的代码生成算法简单的代码生成算法 由上述算法由上述算法从从 DAG 生成代码生成代码 基于树重写的代码生成基于树重写的代码生成 简单的图着色物理寄存器分配算法简单的图着色物理寄存器分配算法 代码生成要考虑的主要问题代码生成要考虑的主要问题- 指令选择指令选择 目标机指令集的性质和中间代码的形式决定目标机指令集的性质和中间代码的形式决定 指令选择的难易指令选择的难易- 寄存器分配寄存器分配 充分、高效地使用寄存器充分、高效地使用寄存器- 指令调度指令调度 选择好计算的次序，充分利用目标机的特点选择好计算的次序，充分利用目标机的特点 指令选择指令选择- 任务任务

3、 为每条中间语言语句选择恰当的目标机指令或指令序列为每条中间语言语句选择恰当的目标机指令或指令序列- 原则原则 首先要保证语义的一致性；若目标机指令系统比较完首先要保证语义的一致性；若目标机指令系统比较完 备，为中间语言语句找到语义一致的指令序列模板是备，为中间语言语句找到语义一致的指令序列模板是 很直接的（不必考虑执行效率的情形下）很直接的（不必考虑执行效率的情形下） 其次要权衡所生成代码的效率（考虑时间其次要权衡所生成代码的效率（考虑时间/空间代价）空间代价） 这一点较难做到，因为执行效率往往与该语句的上下这一点较难做到，因为执行效率往往与该语句的上下 文以及目标机体系结构（如流水线）有关

4、文以及目标机体系结构（如流水线）有关 指令选择举例指令选择举例- 为为TAC 语句语句选择指令模板选择指令模板 假设一个目标机指令系统（一个简单汇编语言）假设一个目标机指令系统（一个简单汇编语言）- 例例 TAC 语句语句 a:=b+c 可转换为如下代码序列可转换为如下代码序列 MOVb, R0 /* b 装入寄存器装入寄存器 R0 */ ADDc, R0 /* c 加到加到 R0 */ MOVR0, a /* 存存 R0 到到 a */ （其他算术和逻辑运算的（其他算术和逻辑运算的TAC 语句与此类似，只是选语句与此类似，只是选 择不同的目标指令，如减运算选择指令择不同的目标指令，如减运算选

5、择指令“SUB”， ） 指令选择指令选择- 选择指令模板时可考虑选择指令模板时可考虑指令的代价指令的代价（cost） 例例 TAC 语句语句 a:=b+c 的几种转换方式的几种转换方式（1）MOV b, R0 ADD c, R0 MOV R0, a cost=6（2）MOV b, a ADD c, a cost=6（3）假定假定 R0, R1 和和 R2中分别中分别 存放了存放了a, b 和和 c 的地址的地址 MOV *R1, *R0 ADD *R2, *R0 cost=2（4）假定假定R1和和R2中分别包含中分别包含b 和和c的值的值, 并且并且b的值在这的值在这 个赋值以后不再需要个赋值

6、以后不再需要 ADD R2, R1 MOV R1, a cost=3 一个一个简单的代码生成算法简单的代码生成算法- 基本块内基本块内 TAC 语句序列的简单代码生成语句序列的简单代码生成 在基本块范围内考虑如何充分利用寄存器的问题在基本块范围内考虑如何充分利用寄存器的问题 原则：原则： 尽可能地让变量的值保留在寄存器中尽可能地让变量的值保留在寄存器中 尽可能引用变量在寄存器中的值尽可能引用变量在寄存器中的值 借助于在基本块范围内建立变量的借助于在基本块范围内建立变量的待用信息链待用信息链和和 活跃信息链活跃信息链 一个一个简单的代码生成算法简单的代码生成算法- 待用信息待用信息 在一个基本块

7、中，四元式在一个基本块中，四元式i对变量对变量A定值，如果定值，如果i后面后面的四元式的四元式j要引用要引用A，且从，且从i到到j的四元式没有其它对的四元式没有其它对A的的定值点，则称定值点，则称j是四元式是四元式i中对变量中对变量A的的待用信息待用信息，同时，同时也称也称A是是活跃活跃的。的。 如果如果A被多处引用，则构成了被多处引用，则构成了A的待用信息链和活跃的待用信息链和活跃信息链。信息链。 为了取得每个变量在基本块内的待用信息和活跃信为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由后向前扫描，对每个变量建息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息

8、链与活跃信息链。立相应的待用信息链与活跃信息链。n计算待用信息的算法计算待用信息的算法（1 1）对各基本块的符号表中的）对各基本块的符号表中的“待用信息待用信息”栏栏和和“活跃信息活跃信息”栏置初值，即把栏置初值，即把“待用信息待用信息”栏置栏置“非待用非待用”，对，对“活跃信息活跃信息”栏按在基本栏按在基本块出口处是否为活跃而置成块出口处是否为活跃而置成“活跃活跃”或或“非活非活跃跃”。这里假定变量都是活跃的，临时变量都。这里假定变量都是活跃的，临时变量都是非活跃的。是非活跃的。（2 2）从基本块出口到基本块入口由后向前依次）从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式处

9、理每个四元式。对每个四元式i: A:=B op Ci: A:=B op C，依次执行下述步骤：依次执行下述步骤：a) a) 把符号表中变量把符号表中变量A A的待用信息和活跃信息附加到四的待用信息和活跃信息附加到四元式元式i i上。上。b) b) 把符号表中变量把符号表中变量A A的待用信息栏和活跃信息栏分别的待用信息栏和活跃信息栏分别置为置为“非待用非待用”和和“非活跃非活跃”。（由于在。（由于在i i中对中对A A的的定值只能在定值只能在i i以后的四元式才能引用，因而对以后的四元式才能引用，因而对i i以前以前的四元式来说的四元式来说A A是不活跃也不可能是待用的）是不活跃也不可能是待用

10、的）c) c) 把符号表中变量把符号表中变量B B和和C C的待用信息和活跃信息附加到的待用信息和活跃信息附加到四元式四元式i i上。上。d) d) 把符号表中变量把符号表中变量B B和和C C的待用信息栏置为的待用信息栏置为“i”i”，活，活跃信息栏置为跃信息栏置为“活跃活跃”。注意，以上注意，以上a a）和）和b b），），c c）和）和d d）的次序不能颠倒。）的次序不能颠倒。【例】若用【例】若用A A，B B，C C，D D表示变量，用表示变量，用T T，U U，V V表示表示中间变量，有四元式如下：中间变量，有四元式如下： （1）T=A-B （2）U=A-C （3）V=T+U （4）

11、D=V+U 其名字表中的待用信息和活跃信息如下表，用其名字表中的待用信息和活跃信息如下表，用“F”F”表示表示“非待用非待用”“”“非活跃非活跃”，用，用“L”L”表示活跃。表示活跃。 一个一个简单的代码生成算法简单的代码生成算法- 寄存器描述数组和变量地址描述数组寄存器描述数组和变量地址描述数组 RVALUER 描述寄存器描述寄存器 R 当前对应哪个变量当前对应哪个变量 AVALUEA 表示变量表示变量 A 的值存放在哪个寄存器中的值存放在哪个寄存器中 一个一个简单的代码生成算法简单的代码生成算法- 基本块内基本块内 TAC 语句序列的简单代码生成语句序列的简单代码生成 （假设只有形如（假设

12、只有形如 A:=B op C 的的TAC 语句序列）语句序列） step1：对每个对每个TAC 语句语句i: A:=B op C，依次执行下述步骤：依次执行下述步骤： 以以 i: A:=B op C 为参数，调用为参数，调用 getreg(i: A:=B op C); 从从 getreg 返返 回时，得到一寄存器回时，得到一寄存器 R（这里先假定（这里先假定 R 为伪寄存器），用它作存为伪寄存器），用它作存 放放 A 现行值的寄存器；（函数现行值的寄存器；（函数 getreg 稍后介绍）。稍后介绍）。 利用利用 AVALUEB 和和 AVALUEC，确定出，确定出 B 和和 C 现行值存放位置

13、现行值存放位置 B 和和 C，如果其现行值在寄存器中，则把寄存器取作，如果其现行值在寄存器中，则把寄存器取作B 和和 C。 如如 BR，则生成目标代码，则生成目标代码 MOV B, R OP C, R 否则，生成目标代码否则，生成目标代码 OP C, R 如如 B 或或 C 为为R，则删除，则删除 AVALUEB 或或 AVALUEC 中的中的 R 一个一个简单的代码生成算法简单的代码生成算法- 基本块的代码生成算法基本块的代码生成算法 （续前页（续前页） 令令 AVALUEA=R，并令，并令 RVALUER=A，以表示变量，以表示变量 A 的现行的现行值只在值只在 R 中并且中并且 R 中的

14、值只代表中的值只代表 A 的现行值的现行值 。 如如 B 或或 C 的现行值在基本块中不再被引用，它们也不是基本块出的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由语句口之后的活跃变量（由语句 i 上的附加信息知道），并且其现行值在某上的附加信息知道），并且其现行值在某个寄存器个寄存器 Rk 中，则删除中，则删除 RVALUERk 中的中的 B 或或C 以及以及 AVALUEB 或或 AVALUEC 中的中的 Rk ，使该寄存器不再为，使该寄存器不再为 B 或或 C 所占用。所占用。 step2: : 处理完基本块中所有处理完基本块中所有TAC 语句之后，对现行值在语句之后

15、，对现行值在 某寄存器某寄存器 R 中的每个变量中的每个变量 M，若它在出口之后是活跃，若它在出口之后是活跃 的，则生成的，则生成 MOV R, M，将其存入主存将其存入主存- 函数函数 getreg（以（以 i: A:=B op C 为参数，为参数， 返回一个伪寄存器返回一个伪寄存器） 步骤步骤： 若若 RVALUER=B ，且在语句，且在语句 i 之后之后 B 在基本块中不再被引用，同在基本块中不再被引用，同 时也不是基本块出口之后的活跃变量（由时也不是基本块出口之后的活跃变量（由 i 上的附加信息可知道），上的附加信息可知道）， 则返回则返回 R； 否则否则，返回一个新的伪寄存器，返回一

16、个新的伪寄存器R注：注：这里的这里的 getreg 返回伪寄存器（可以利用随后介绍的图着色寄存返回伪寄存器（可以利用随后介绍的图着色寄存 器分配算法将它们对应到真实寄存器或内存地址）。器分配算法将它们对应到真实寄存器或内存地址）。 其实也可以不是返回伪寄存器，而是在寄存器不够时返回一个内其实也可以不是返回伪寄存器，而是在寄存器不够时返回一个内 存地址。存地址。 一个一个简单的代码生成算法简单的代码生成算法举例举例- 对于右图的基本块对于右图的基本块 （假定只有（假定只有d在基本块的在基本块的 出口是活跃的），利用上述算法可生成如下出口是活跃的），利用上述算法可生成如下 代码序列：代码序列：t:

17、=a-b u:=a-c v:=t+u d:=v+u 由上述算法由上述算法从从 DAG 生成代码生成代码- 从某个基本块的从某个基本块的 DAG 表示得到的两段表示得到的两段 TAC 代码代码 - - + + a0T1T1:=a+bT2:=c+dT3:=e-T2T4:=T1-T3T4c0d0T3T2b0e0 - -T2:=c+dT3:=e-T2T1:=a+bT4:=T1-T3- 将上述简单的代码生成算法应用于如下两个基本块将上述简单的代码生成算法应用于如下两个基本块 比较比较其结果（这里假设基本块出口处只有其结果（这里假设基本块出口处只有T4是活跃的）是活跃的）T1:=a+bT2:=c+dT3:

18、=e-T2T4:=T1-T3T2:=c+dT3:=e-T2T1:=a+bT4:=T1-T3MOV a,R0ADD b,R0MOV c,R1ADD d,R1MOV e,R2SUB R1,R2SUB R2,R0MOV R0,T4MOV c,R0ADD d,R0MOV e,R1SUB R0,R1MOV a,R0ADD b,R0SUB R1,R0MOV R0,T4第二段代码较优第二段代码较优（少用了寄存器）（少用了寄存器） 由上述算法由上述算法从从 DAG 生成代码生成代码- 例例 a i := b 的一个可能的中间表示树的一个可能的中间表示树 基于树重写的代码生成基于树重写的代码生成- 树重写（树重

19、写（Tree Rewriting）规则形如）规则形如 replacement template cost = action 其中其中 replacement 代表树的单个节点代表树的单个节点 template 代表一棵树代表一棵树 cost 是用来计算相应于该是用来计算相应于该template代价的代码片段代价的代码片段 action 是使用该规则进行树重写时执行的代码片段是使用该规则进行树重写时执行的代码片段 基于树重写的代码生成基于树重写的代码生成- 例例 若干若干VAX指令对应的树重写规则指令对应的树重写规则 基于树重写的代码生成基于树重写的代码生成- 例例 若干若干VAX指令对应的树重

20、写规则指令对应的树重写规则 基于树重写的代码生成基于树重写的代码生成- 从中间表示树生成代码从中间表示树生成代码 基于树重写的代码生成基于树重写的代码生成 思路思路 根据树重写规则对中间表示树的子树逐步进行归根据树重写规则对中间表示树的子树逐步进行归 约，直至单个节点为止，该过程的所有子树集合构约，直至单个节点为止，该过程的所有子树集合构 成中间表示树的一种成中间表示树的一种覆盖覆盖（cover）。）。 某个某个覆盖的代价覆盖的代价是相应树重写规则的附加代价之和是相应树重写规则的附加代价之和 找到一种代价最小的覆盖。找到一种代价最小的覆盖。 根据最小代价的覆盖进行代码生成。根据最小代价的覆盖进

21、行代码生成。 简单的图着色物理寄存器分配算法简单的图着色物理寄存器分配算法- 两遍的通用寄存器分配算法两遍的通用寄存器分配算法 第一遍先假定可用的通用寄存器是无限数量的，完第一遍先假定可用的通用寄存器是无限数量的，完 成指令选择成指令选择 例如：前面介绍的简单代码生成算法中的例如：前面介绍的简单代码生成算法中的 getreg 函数返回一个伪寄存器（不管物理寄存器的个数）函数返回一个伪寄存器（不管物理寄存器的个数） 第二遍将物理寄存器分配到伪寄存器。第二遍将物理寄存器分配到伪寄存器。 物理寄存器数量不足时，会将一些伪寄存器泄露到物理寄存器数量不足时，会将一些伪寄存器泄露到 （spilled into）内存，图着色算法的核心任务是使）内存，图着色算法的核心任务是使 得泄露的伪寄存器数目最少。得泄露的伪寄存器数目最少。- 基于寄存器相干图基于寄存器相干图（register-interference graph） 的图着色寄存器分配算法的图着色寄存器分配算法 构造寄存器构造寄存器相干图相干图 结点结点：每一个伪寄存器为一个结点。：每一个伪寄存器为一个结点。 边边：如果程序中存在某点，一个结点在该点被定义，：如果程序中存在某点，一个结点在该点被定义， 而另一个结点在该点是活跃的，则在