08 编译器原理与技术---代码生成

1 .第 8 章 代码生成 编译原理与技术

2 .一 个简单的代码生成算法 涉及存储管理，指令选择，寄存器分配和计算次序选择等基本 问题 8 代码生成 内容提要 前端 代码 优化器 中间 代码 源程序 代码 生成器 中间 代码 目标 程序

3 .8.1 代码生成器 的设计中的问题 第 8 章 代码生成

4 .8.1.1 目标程序 绝对机器语言程序 目标程序将装入到内存的固定地方 粗略地说，相当于现在的可执行目标模块（第 10 章 介绍 ） 可重定位目标模块 代码中含重定位信息，以适应重定位要求 允许程序模块分别编译 调用其它先前编译好的 程序模块 汇编语言程序 免去编译器重复汇编器的工作 从教学角度，增加可读性 8.1 代码生成器 的设计中的问题 . L7: testl % eax ,% eax je .L3 testl % edx ,% edx je .L7 movl % edx ,% eax jmp .L7 . L3: leave ret 可 重定位目标模块中 ，需要 有绿色部分的 重定位 信息

5 .8.1.2 指令的选择 目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素 指令的速度和机器特点是另一些重要的因素 若不考虑目标程序的效率，指令的选择是直截了当的 例 三 地址语句 x = y + z ( x，y 和 z 都静态分配 ) MOV y, R0 /  把 y 装入寄存器 R0  / ADD z, R0 /  把 z 加到 R0 上  / MOV R0, x /  把 R0 存入 x 中  / 8.1 代码生成器 的设计中的问题

6 .逐条语句地产生代码，常常得到低质量的代码 语句 序列 a = b + c d = a + e 的代码如下 MOV b, R0 ADD c , R0 MOV R0, a MOV a, R0 ADD e , R0 MOV R0, d 8.1 代码生成器 的设计中的问题 －－ 多余的 指令 －－ 若 a 不再使用 ，这也是多余的指令

7 .8.1.3 寄存器分配 运算对象处于寄存器和处于内存相比，指令要短一些，执行也快一些 寄存器分配 选择驻留在寄存器中的一组变量 寄存器指派 挑选变量要驻留的具体寄存器 8.1 代码生成器 的设计中的问题

8 .8.1.4 计算次序的选择 程序中计算的执行次序会影响目标代码的执行效率 例 对表达式的计算而言，一种计算次序可能会比其它次序需要较少的寄存器来保存中间结果 选择 最佳计算次序是一个 NP 完全问题 8.1 代码生成器 的设计中的问题

9 .8.2 目标机器 第 8 章 代码生成

10 .8.2.1 目标机器的指令系统 选择可作为几种微机代表的寄存器机器 四个字节组成一个字，有 n 个通用寄存器 R 0 , R 1 , … , R n-1 二地址指令： op 源，目的 MOV { 源传到目的} ADD { 源加到目的} SUB { 目的减去源 } 汇编指令翻译成机器指令时，指令内容占一个单元，源和目的可能占用额外的单元（ 即本章要考虑的附加 代价） 8.2 目标机器

11 .地址模式和它们的汇编语言形式及附加代价 模式 形式 地址 附加 代价 直接量 #c c 1 绝对地址 M M 1 寄存器 R R 0 变址 c(R) c + contents(R ) 1 间接 寄存器  R contents(R) 0 间接 变址  c(R ) contents(c + contents(R )) 1 8.2 目标机器

12 .例 指令实例 MOV R0, M MOV 4(R0), M 4(R0 ) 的值： contents(4 + contents(R0 )) MOV  4(R0), M  4(R0) 的值： contents(contents(4 + contents(R0))) MOV #1, R0 8.2 目标机器

13 .8.2.2 指令的代价 指令代价简化为 1 + 指令的源和目的地址模式的附加代价 指令 代价 MOV R0, R1 1 MOV R5, M 2 ADD #1, R3 2 SUB 4(R0),  12(R1 ) 3 8.2 目标机器

14 .例 a = b + c，a、b 和 c 都静态分配内存单元 - 可生成 MOV b, R0 ADD c, R0 MOV R0, a 代价 = 6 - 也可生成 MOV b, a ADD c, a 代价 = 6 - 若 R0，R1 和 R2 分别含 a，b 和 c 的地址，则可生成 MOV  R1,  R0 ADD  R2,  R0 代价 = 2 - 若 R1 和 R2 分别含 b 和 c 的值 ，且 b 以后 不再需要，则可生成 ADD R2, R1 MOV R1, a 代价= 3 8.2 目标机器

15 .8.3 基本块和流图 第 8 章 代码生成

16 .怎样为三地址语句序列生成目标代码？ 先给出本节用例 prod = 0; i = 1 ; do { prod = prod + a[ i ]  b[ i ]; i = i +1; } while ( i <= 20); 其三地址代码见 右边 8.3 基本块和流图 (1 ) prod = 0 (2) i = 1 (3) t 1 = 4  i (4) t 2 = a[t 1 ] (5) t 3 = 4  i (6) t 4 = b[t 3 ] (7) t 5 = t 2  t 4 (8) t 6 = prod + t 5 (9) prod = t 6 (10) t 7 = i +1 (11) i = t 7 (12) if i <= 20 goto (3)

17 .8.3.1 基本块 基本 块 连续 的语句序列， 控制流 从 它的开始进入 ，并 从 它 的 末尾离开 流图 再用 有向边表示基本 块之 间 的控制流信息， 就能得 到 程序的流图 8.3 基本块和流图 (1 ) prod = 0 (2) i = 1 (3) t 1 = 4  i (4) t 2 = a[t 1 ] (5) t 3 = 4  i (6) t 4 = b[t 3 ] (7) t 5 = t 2  t 4 (8) t 6 = prod + t 5 (9) prod = t 6 (10) t 7 = i +1 (11) i = t 7 (12) if i <= 20 goto (3)

18 .划分 基本块的方法 首先确定所有入口语句 序列的第一个语句是入 口语句 能 由转移语句转到 的语 句 是入口 语句 紧跟 在转移语句 后面的 语句 是入口 语句 每个 入口语句到下一 个 入口 语句之前（或到 程 序结束 ）的语句序列 构 成一个 基本块 8.3 基本块和流图 (1 ) prod = 0 (2) i = 1 (3) t 1 = 4  i (4) t 2 = a[t 1 ] (5) t 3 = 4  i (6) t 4 = b[t 3 ] (7) t 5 = t 2  t 4 (8) t 6 = prod + t 5 (9) prod = t 6 (10) t 7 = i +1 (11) i = t 7 (12) if i <= 20 goto (3)

19 .8.3 基本块和流图 (1 ) prod = 0 (2) i = 1 (3) t 1 = 4  i (4) t 2 = a[t 1 ] (5) t 3 = 4  i (6) t 4 = b[t 3 ] (7) t 5 = t 2  t 4 (8) t 6 = prod + t 5 (9) prod = t 6 (10) t 7 = i +1 (11) i = t 7 (12) if i <= 20 goto (3) (1 ) prod = 0 (2) i = 1 (3) t 1 = 4  i (4) t 2 = a[t 1 ] (5 ) t 3 = 4  i (6) t 4 = b[t 3 ] (7 ) t 5 = t 2  t 4 (8) t 6 = prod + t 5 (9 ) prod = t 6 (10) t 7 = i +1 (11) i = t 7 (12) if i <= 20 goto (3) B 1 B 2

20 .8.3.2 基本块的优化 术语 三地址语句 x = y + z 引用 y 和 z 并且对 x 定值 一个名字的值在基本块的某一点以后还要引用的话，则说这个名字（变量）在该点是 活跃 的 基本块的等价 两个基本块的出口点有同样的活跃变量集合 对其中每个变量，定义其值的两个表达式相等 有很多等价变换可用于基本块 局部变换 全局变换（下一章介绍） 8.3 基本块和流图

21 .删除局部公共子表达式 a = b + c a = b + c b = a  d b = a  d c = b + c c = b + c d = a  d d = b 删除死代码 定值 x = y + z 以后不再引用， 则称 x 为死变量 8.3 基本块和流图 可变换成

22 .交换相邻的独立语句 t 1 = b + c t 2 = x + y t 2 = x + y t 1 = b + c 当且仅当 t 1 和 t 2 不相同， x 和 y 都不是 t 1 ， 并且 b 和 c 都不是 t 2 代数 变换 x = x + 0 可以 删除 x = x  1 可以 删除 x = y  2 改 成 x = y  y 8.3 基本块和流图

23 .8.3.3 流图 把控制流信息加 到基本块 集合 ， 形成一 个 有向图来 表示程序 流图中的节点 首结点、前驱、后继 什么是循环 ? 所有结点是 强连通 的 唯一的循环 入口 外循环和内循环 8.3 基本块和流图 (1 ) prod = 0 (2) i = 1 (3) t 1 = 4  i (4) t 2 = a[t 1 ] (5) t 3 = 4  i (6) t 4 = b[t 3 ] (7) t 5 = t 2  t 4 (8) t 6 = prod + t 5 (9 ) prod = t 6 (10) t 7 = i +1 (11) i = t 7 (12) if i <= 20 goto B2 B 1 B 2

24 .8.3.4 下次引用信息 为每个三地址语句 x = y op z 决定 x、y 和 z 的下次引用信息 i: x = y op z . . . 没有对 x 的赋值 j: … = x … . . . 没有对 x 的赋值 k: … = … x 对每个基本块从最后一个语句反向扫描到第一个语句 ，可以得到下次引用信息 利用下次引用信息，可以压缩临时变量需要的空间 8.3 基本块和流图

25 .8.4 一 个简单的代码生成器 第 8 章 代码生成

26 .在 没有收集全局 信息前， 暂且 以基本块 为单位来 生成 代码 8.4 一 个简单的代码生成器 (1 ) prod = 0 (2) i = 1 (3) t 1 = 4  i (4) t 2 = a[t 1 ] (5) t 3 = 4  i (6) t 4 = b[t 3 ] (7) t 5 = t 2  t 4 (8) t 6 = prod + t 5 (9 ) prod = t 6 (10) t 7 = i +1 (11) i = t 7 (12) if i <= 20 goto B2 B 1 B 2

27 .基本考虑： 依次考虑基本块的每个语句，为其产生代码 假定三地址语句的每种算符都有对应的目标机器算符 假定计算结果留在寄存器中尽可能长的 时间，除非 ： 该寄存器要用于其它计算，或者 到基本块结束 为此，在生成代码过程中需要记录一些信息 8.4 一 个简单的代码生成器

28 .8.4.1 寄存器描述和地址描述 例 对 a = b + c 如果 寄存器 Ri 含 b，Rj 含 c， 且 b 此后不再活跃 产生 ADD Rj , Ri ， 结果 a 在 Ri 中 如果 Ri 含 b， 但 c 在内存单元 ，b 仍然不再活跃 产生 ADD c, Ri ， 或者产生 MOV c, Rj ADD Rj , Ri 若 c 的值以后还要用,第二种代码较有吸引力 8.4 一 个简单的代码生成器

29 .在代码生成过程中，需要跟踪寄存器的内容和名字的地址 寄存器 描述记住每个寄存器当前存的是什么 在 任何一点，每个寄存器保存若干个 ( 或 零 个)名字的值 例 // 语句前， R0 保存 变量 a 的值 b = a // 不为该语句产生任何指令 // 语句后， R0 保存 变量 a 和 b 的值 名字（变量）的地址 描述记住运行时每个名字的当前值可以在哪个场所找到 这个 场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合 例 MOV c , R0 后， c 的值可在 R0 和 c 的存储单元 找到 名字的地址信息存于符号表，另建寄存器描述表 这两个描述在代码生成 过程中是 变化的 8.4 一 个简单的代码生成器