目标代码生成.

Presentation on theme: "目标代码生成."— Presentation transcript:

1 目标代码生成

2 代码生成器 根据中间表示(IR)生成代码 代码生成器的三个任务 生成的目标程序应满足：保持源程序语义、高效
寄存器分配和指派：把哪个值放在哪个寄存器中 指令排序：按照什么顺序安排指令执行 生成的目标程序应满足：保持源程序语义、高效

3 要考虑的问题 代码生成器的输入 目标程序 由前端生成的源语言的中间表示和符号表信息 中间表示形式，在本书中主要是三地址代码、DAG等
目标机器的指令集体系结构 常见：RISC(精简指令集计算机)，CISC(复杂指令集计 算机)，基于堆栈的结构 本章中，采用一个非常简单的类RISC计算机作为目标 机，加入一些类CISC的寻址方式 生成汇编代码

4 要考虑的问题 指令选择 IR的层次 指令集体系结构中本身的特性 生成代码的质量，要考虑到目标代码的效率
INC a // if it’s a valid instr

5 要考虑的问题 寄存器分配和指派 有效地利用寄存器（最“小而快”的存储） 还需要考虑目标机器或操作系统对特定指令使用哪些 寄存器的规则
源程序的每个时刻，选择一组将被存放在寄存器中的变量 指定一个变量被放在哪个寄存器中 还需要考虑目标机器或操作系统对特定指令使用哪些 寄存器的规则

6 本书的目标语言 指令格式：一个运算符，一个目标地址，一个源 运算分量的列表 内存按照字节寻址 n个通用寄存器R0, R1, …

7 本书的目标语言的指令集 加载：LD dst, src 保存：ST dst, src 运算：OP dst, src1, src2
LD r, x LD r0, r1 LD r, #100 保存：ST dst, src ST x, r ST x, #100 运算：OP dst, src1, src2 SUB r1, r2, r3 无条件跳转：BR L 条件跳转：Bcond r, L 当r里的值小于0时跳转L：BLTZ r, L

8 指令中的dst和src 变量名x（内存中的位置） 寄存器r a(r)，其中a是一个变量，r是一个寄存器
LD R1, a(R2)表示赋值R1 = contents(a+contents(R2)) n(r)，其中n是一个整数，r是一个寄存器 LD R1, 100(R2)表示赋值R1 = contents(100+content(R2)) *r，表示r的内容所表示的位置上存放的内存位置 *n(r) LD R1, *100(R2)表示R1 = content(contents(100+content(R2))) #n，表示一个直接常数 LD R1, #100 ADD R1,R1,#100

9 目标机指令序列示例 对于实数数组a，

10 目标机指令序列示例（续）

11 程序和指令的代价 下面假设指令的代价为1加上对运算分量寻址的 代价 例如： 代码生成算法的目标是使程序在典型输入上运行 时的指令代价总和最小
寄存器寻址的附加代价为0 涉及内存位置的寻址方式的附加代价为1 例如： LD R0, R1 代价为1 LD R0, M 代价为2 LD R1,*100(R2) 代价为2 代码生成算法的目标是使程序在典型输入上运行 时的指令代价总和最小

12 代码生成怎么做？ 过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址 将中间代码划分为基本块，形成流图
为单个基本块生成代码的简单的算法 窥孔优化：对目标代码进行优化 全局寄存器分配算法：图着色方法 基于树重写的指令选择

13 回顾程序运行时空间的划分 靠近栈底 靠近栈顶

14 活动记录的栈分配 寄存器SP指向栈顶的活动记录的开始处 第一个过程main初始化栈区 HALT指令把控制返回给操作系统

15 活动记录的栈分配 过程调用时，caller增加SP的值，保存返回地址， 并把控制传递给callee
ADD SP, SP, #caller.recordSize // 增加栈指针 ST 0(SP), #here+16 // 保存返回地址（BR后的指令地址） BR callee.codeArea // 跳转到callee的第一条指令的地址 返回时，callee把控制传递给返回地址，caller把SP 恢复为以前的值 callee中：BR *0(SP) caller中：SUB SP, SP, #caller.recordSize

16 例子 0(SP)

17 名字的运行时刻地址 三地址语句中的名字实际上是指向符号表中该名 字条目的指针 考虑语句x = 0，假设x的符号表条目包含了x的相 对地址12
如果x分配在静态区，且静态区开始位置为static，那 么x的实际运行时刻地址是static+12 ST 112, #0 // static = 100 如果x分配在栈区， ST 12(SP), #0

18 代码生成怎么做？ 过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图
过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图 为单个基本块生成代码的简单的算法 窥孔优化：对目标代码进行优化 全局寄存器分配算法：图着色方法 基于树重写的指令选择

19 基本块和流图 为了更好的分配寄存器和完成指令选择，按照如 下方法组织中间代码：
把中间代码划为基本块。每个基本块是满足下列条件 的最大的连续三地址指令序列： 控制流只能从基本块中的第一条指令进入该块。没有跳转 到基本块中间的转移指令 除了基本块的最后一个指令，控制流不会跳转或停止 流图中的结点是基本块，流图的边指明了哪些基本块 可能紧随一个基本块之后运行 流图可以作为优化的基础

20 划分基本块的算法 输入：一个三地址指令序列 输出：输入序列对应的一个基本块列表，其中每 个指令恰好被分配给一个基本块 方法：
确定基本块的首指令 中间代码的第一个三地址指令是一个首指令 任意一个条件或无条件转移指令的目标指令是一个首指令 紧跟在一个条件或无条件转移指令之后的指令是一个首指令 每个首指令对应一个基本块 从它自己开始，直到下一个首指令（不含）或者结尾指令之 间的所有指令

21 划分示例 第一个指令 跳转指令的目标 跳转指令的下一条 基本块 1 3, 2, 13 10, 12
1-1, 2-2, 3-9, 10-11, , 13-17

22 流图 表达基本块之间的控制流 流图的结点是基本块 在流图中额外增加入口和出口结点
从基本块B到基本块C之间有一条边当且仅当基本块C 的第一个指令可能紧跟在B的最后一条指令之后执行 存在边的原因 B的结尾指令是一条跳转到C的开头的条件/无条件跳转 按照原来的三地址语句序列中的顺序，C紧跟在B之后，且B 的结尾不存在跳转语句 称B是C的前驱，C是B的后继 在流图中额外增加入口和出口结点 入口到流图的第一个基本块有一条边 从任何包含了可能是程序的最后执行指令的基本块到 出口有一条边

23 流图示例 这里把到达指令的标号或序号替换为到达基本块的跳转。好处：当改变某些指令后，就可以不修改跳转的目标

24 循环 程序的大部分运行时间花费在循环上，因此循环 是识别的重点(优化的目标) 通过流图识别“循环”
若满足以下条件，则流图中的一个结点集合L是 一个循环： L中有一个循环入口结点，它是唯一的前驱可能在循 环外的结点。从整个流图的入口结点开始到L中的任 何结点的路径都必然经过循环入口结点。 L的每个结点都有一个到达L的入口结点的非空路径， 并且该路径都在L中。

25 循环示例

26 基本块内的后续使用信息 变量值的使用 这些信息可以用于代码生成
三地址语句i向变量x赋值，如果另一个语句j的运算分 量为x，且从i开始有一条路径到达j，且路径上没有对 x赋值，那么j就使用了i处计算得到的x的值 此时我们说变量x在语句i处活跃 程序执行完语句i后，x中存放的值将被后面语句使用 这些信息可以用于代码生成 如果x在i处不活跃，则可以删掉这个赋值语句i 利用后续使用信息，可以压缩临时变量需要的空间 （如果t1和t2的生存期不重叠，可以压缩在同一单元）

27 算法 – 确定基本块内每条语句中变量的活跃性和下一次使用信息
更准确的做法是用下一章“活跃变量分析”的结果 输入 基本块B，假设在B的出口时符号表中B的所有非临时 变量都置为“活跃”且“（在B内）无后续使用”， 临时变量置为“不活跃”且“无后续使用” 输出 对B中每个语句i: x=y+z，将x、y、z的活跃性及下一次 使用信息关联到i 方法：对B反向扫描。对于每个语句i: x=y+z 令语句i和x、y、z的当前活跃性信息/下一次使用信息 （在当前符号表中找到的）关联起来 在符号表中，设置x为“不活跃”和“无后续使用” 在符号表中，设置y和z为“活跃”，并把它们的下一 次使用信息设置为语句i

28 例子 假设在出口处a, b活跃，其余变量不活跃 1) t1 = a * a 2) t2 = a * b 3) t3 = 2 * t2
4) t4 = t1 + t3 5) t5 = b * b 6) t6 = t4 + t5 7) a = t6 假设在出口处a, b活跃，其余变量不活跃 7) b, t6活跃，a不活跃，t6被7使用 6) b, t4, t5活跃，t6不活跃，t4, t5被6使用 5) b, t4活跃，t5不活跃，b被5使用 4) b, t1, t3活跃，t4不活跃，t1, t3被4使用 3) b, t1, t2活跃，t3不活跃，t2被3使用 2) a, b, t1活跃，t2不活跃，a和b被2使用 1) a, b活跃，t1不活跃，a被1使用 每一刻至多三个变量活跃，可以压缩存储空间

29 例2 假设在出口处i, j, a活跃，其余变量不 活跃 8)i, j, a活跃，j在8上被使用 7)i, j, a, t4活跃，t4被7使用
6)i, j, a, t3活跃，t4不活跃，t3被6使用 5)i, j, a, t2活跃，t3不活跃，t2被5使用 4)i, j, a, t1活跃，t2不活跃，t1和j被4使用 3)i, j, a活跃，t1不活跃，i被3使用

30 基本块的优化 针对基本块本身的局部优化，就可以有很好的效果 DAG图可反映变量及其值对其他变量的依赖关系 构造方法
更彻底的全局优化需要基本块之间的数据分析（下一章） DAG图可反映变量及其值对其他变量的依赖关系 构造方法 基本块中出现的每个变量有一个对应的DAG叶结点表示 其初始值 基本块每个语句s有一个结点N 结点N的标号是s中的运算符，同时还有一组变量被关联到N。 表示s是最晚对这些变量进行定值的语句 N的子结点是基本块中的其它语句对应的结点，这些结点对应 的是最后一个对s中的运算分量进行定值的语句

31 DAG的构造 为基本块中出现的每个变量建立结点(表示初始 值)，初始时各变量和相应结点关联 顺序扫描各三地址指令，进行如下处理：
指令x = y op z 为该指令建立结点N，标号为op，令x和N关联（ N取代了原 先关联的结点） N的子结点为y、z当前关联的结点 指令x= y 假设y关联到N，那么x现在也关联到N

32

33 DAG的作用 DAG描述了基本块运行时各变量的值之间的依赖 关系 DAG帮助我们对代码进行一些优化： 消除局部公共子表达式 消除死代码
语句重排序 对运算分量进行符合代数规则的重排序

34 DAG中的局部公共子表达式 所谓公共子表达式就是重复计算一个已经计算得 到的值的指令
若b在出口处不活跃，则可优化为仅三条语句： a-d是，b+c不是

35 消除死代码 删除没有附加活跃变量且没有父节点的结点 假设e和c不是活跃变量（但a、b是），则可以删 除标记e和c的结点 a = b + c
b = b – d c = c + d e = b + c

36 基于代数恒等式的优化 消除计算步骤 强度消减 常量合并：将常量表达式替换为求出的值
使用代数转换规则，比如交换律和结合律，可以发现公 共子表达式 x*y=y*x a=b+c, e=c+d+b 编译器的设计者应该仔细阅读语言手册，以免其不一定 遵守数学上的代数恒等式

37 数组引用的DAG表示 两次使用的a[i]不能当成公共子表达式 DAG中表示数组引用的正确方法：
从数组取值的运算（x=a[i]），对应于=[]结点 这个结点的左右子节点是数组起始地址a0和下标i 变量x关联到这个结点 对数组赋值的运算（ a[j]=y ），对应于[]=结点 这个结点的三个子节点分别表示a0、j和y 没有变量关联到这个结点 此结点创建后，当前已经建立的、其值依赖于a0的所有结点 被杀死。被杀死的结点不会再关联别的变量（即，不会成 为公共子表达式）

38 例子 x关联的结点N首先被创建。但是当[]=结点被创建时，N就被杀死了。因此当要建立z关联的结点时，不会认为和N等同，而是需要创建新结点

39 例2 []=结点的子节点都不是数组结点，但它有孙结点a0，所以还是杀死了依赖于a0的结点=[]。
b x 设a为数组，b为指针 []=结点的子节点都不是数组结点，但它有孙结点a0，所以还是杀死了依赖于a0的结点=[]。 结点被杀死，意味着不能被复用，考虑之后的指令m = b[i]

40 指针赋值和过程调用 处理对指针所指空间的赋值的时候，同样要杀死 可能被指针赋值改变的结点。如果不能确定指针 指向的范围，那么，需要杀死所有的节点。 某些情况下，可以确定一个指针在代码中的某个位置 会指向哪个变量，比如p=&x, *p=y， 那么只需要杀 死以x为附加变量的结点，不需要杀死其它结点。 指针分析技术 过程调用的情况类似

41 从DAG重构三地址代码 每个结点构造一条三地址语句，计算对应的值 结果应该尽量赋给一个活跃的变量
如果结点有多个关联的变量，则用复制语句给其 他关联变量赋值

42 例子 大多数机器上复制比减法更高效，且全局分析后可能继续优化消除b 若b在出口处不活跃，则仅生成三条语句： 若b, d在出口处都活跃，则：
a = b + c d = a – d b = d c = d + c 大多数机器上复制比减法更高效，且全局分析后可能继续优化消除b

43 重构的规则 注意求值顺序 指令顺序必须遵守DAG中结点的顺序 如果两个指令之间相互影响，它们的顺序就不该改变
对数组赋值要跟在原来之前的赋值/求值之后 对数组元素求值要跟在原来之前的赋值指令后 对变量的使用必须跟在所有原来在它之前的过程调用和指 针间接赋值之后 任何过程调用或指针间接赋值必须跟在原来在它之前的变 量求值之后

44 代码生成怎么做？ 过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图 
过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图  为单个基本块生成代码的简单的算法 窥孔优化：对目标代码进行优化 全局寄存器分配算法：图着色方法 基于树重写的指令选择

45 一个简单的代码生成器 为单个基本块生成代码：依次考虑各个三地址指令， 并跟踪记录哪个值存放在哪个寄存器中，以避免生 成不必要的加载(LD)和保存(ST)指令 尽可能利用寄存器，并减少寄存器/内存间数据交换？ 通常，寄存器在如下情形使用： 大部分体系结构要求各个运算分量必须存放在寄存器中 寄存器适合存放临时变量（只在基本块中使用的变量的值） 寄存器用来存放在一个基本块中计算而在另一个基本块中 使用的值，例如循环的下标 寄存器用来帮助进行运行时刻存储管理，如运行时刻栈的 指针 寄存器数量有限，上述使用有竞争关系

46 算法的基本思想 假设每个运算符对应唯一的机器指令，且运算分 量和结果必须存放在寄存器中 为一个三地址指令生成机器指令时 数据结构
只有当运算分量不在寄存器中时，才从内存加载 尽量保证只有当寄存器中值不再被使用时，才覆盖掉 数据结构 寄存器描述符：记录各个寄存器当前存放了哪些变量 的值。一个寄存器可以存放一个或者多个变量的值 地址描述符：记录每个名字的当前值存放在哪些位置， 可以是寄存器，也可以是内存地址，或者它们的集合 （当值被赋值传输的时候）

47 代码生成算法（1） 重要子函数：getReg(I) 代码生成算法逐个处理三地址指令

48 代码生成算法（2） I为运算语句x = y op z 调用getReg(I)，为x、y、z选择寄存器Rx、Ry、Rz
查看Ry的寄存器描述符，如果y不在Ry中，那么生成 指令“LD Ry, y’”，其中y’是存放y的内存地址之一 （由y的地址描述符得到） 类似的处理z 生成指令“op Rx, Ry, Rz”

49 代码生成算法（3） I是复制语句x=y 调用getreg(I)，为x和y选择相同的寄存器Ry 查看Ry的寄存器描述符，如果y不在Ry中，那么生成 指令“LD Ry, y’”，其中y’是存放y的内存地址之一 （由y的地址描述符得到） 基本块的结尾：为每个活跃的、不在内存中（由 x的地址描述符知）的变量x生成指令“ST x R”， 其中R是存放x值的寄存器

50 代码生成算法（4） 代码生成的同时更新寄存器描述符和地址描述符 对于指令“LD R, x” 对于指令“ST x, R”
对于x=y op z的指令“OP Rx,Ry,Rz” 修改Rx的寄存器描述符，使之只包含x 修改x的地址描述符，使之只包含Rx（不包含x的内存位置） 从任何不同于x的变量的地址描述符中删除Rx 对于复制语句x=y 如果生成“LD Ry, y’”，按照上面第一个规则处理 把x加入到Ry的寄存器描述符中（ Ry同时存放了x和y的当前值） 修改x的地址描述符，使之只包含Ry（不包含x的内存位置）

51 例子 a, b, c, d在出口处活跃 t, u, v是临时变量

52 getReg的设计（1） 任务：为运算分量和结果分配寄存器 目标：减少LD、ST指令 为x = y op z的运算分量y和z分配寄存器
如果y已经在某个寄存器中，不需要进行处理，选择 这个寄存器作为Ry 如果y不在寄存器中，且有空闲寄存器，选择一个空 闲寄存器作为Ry 如果y不在寄存器中，且没有空闲寄存器？

53 getReg的设计（2） 如果y不在寄存器中，且没有空闲寄存器，则需 要复用一个寄存器R，其寄存器描述符表示v是保 存在其中的变量
如果v的地址描述符说v还在其他地方，done 如果v就是x（即结果），且x不是运算分量z，done 如果v在此之后不再被使用（不活跃），done 否则Spill：生成指令“ST v, R”，并修改v的地址描述 符 如果R中存放了多个变量的值，则可能需要生成 多条ST指令 从所有可能的R中选择代价最小（生成ST最少）的R

54 getReg的设计（3） 为x = y op z的结果x分配寄存器的方法基本上和 上面Load y的寄存器分配一样，但是
如果y在该指令之后不会被使用，且Ry仅保存了y的值， 那么可以选择Ry（对z也一样） 处理复制x= y时：先选择Ry ，然后让Rx = Ry

55 示例 d = (a-b)+(a-c)+(a-c)的三地址代码序列: t1 = a-b t2 = a-c t3 = t1 + t2
d = t3 + t2

56 statements code generated register descriptor address descriptor
假设只有两个寄存器 statements code generated register descriptor address descriptor registers empty t1 := a - b LD R0,a LD R1, b SUB R1, R0,R1 R0含a R1含t1 a in R0 t1 in R1 t2 := a - c ST t1, R1 LD R1, c SUB R0, R0, R1 R1含c R0含t2 c in R1 t2 in R0 t3 := t1+ t2 LD R1,t1 ADD R1,R1,R0 R1含t3 t3 in R1 d := t3 + t2 R1含d d in R1 t2 in R0 ST d, R1 d在R1和内存中

57 代码生成怎么做？ 过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图 
过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图  为单个基本块生成代码的简单的算法  窥孔优化：对目标代码进行优化 全局寄存器分配算法：图着色方法 基于树重写的指令选择

58 窥孔优化 先生成目标代码，然后对目标代码进行“优化”转换 窥孔优化：简单却又有效的，用于局部改进目标代码的 技术
使用一个滑动窗口（窥孔）来检查目标指令，在窥孔范 围内，寻找更快更短的指令 窥孔优化的每一次优化可能又产生出新的优化机会。因 此，通常要多次扫描目标代码 窥孔优化的种类 冗余指令消除 控制流优化 代数化简 使用机器特有指令

59 消除冗余指令 指令序列 LD R0,a ST a, R0 可以删除ST指令，前提是ST指令前面没有标号（即， 两个指令在同一个基本块中）

60 消除不可达代码 消除级联跳转 紧跟在无条件跳转之后的不带标号的指令可以被 删除

61 控制流优化

62 其它两种类型的窥孔优化 代数化简和强度消减 使用机器特有的指令 代数恒等的指令可以删除
强度消减：把代价高的运算替换为目标机器上代价较 低的等价运算 使用机器特有的指令 目标机器有时会有能够高效实现某些特定运算的硬件 指令

63 代码生成怎么做？ 过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图 
过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图  为单个基本块生成代码的简单的算法  窥孔优化：对目标代码进行优化  全局寄存器分配算法：图着色方法 基于树重写的指令选择

64 全局寄存器分配 前面代码生成算法里面介绍了基本块中如何使用 寄存器来存放值，并且在每个基本块的结尾处， 所有活跃变量的值都被保存到内存中
如果能全局考虑，就可以减少一部分ST和LD指令 把一些寄存器指派给频繁使用的变量，使得这些 寄存器在不同基本块中的指派保持一致 方法一：分配固定的多个寄存器来存放内部循环中最 活跃的值，其他的寄存器存放基本块中的局部值 缺点：固定的个数并不总是最佳的 经典做法：图着色方法(graph coloring) 寄存器冲突图

65 寄存器冲突图(register interference graph)
寄存器分配的原则：若t1和t2同时活跃，则不能 将它们分配到同一个寄存器中 构造无向图： 每个结点代表一个变量 t1和t2之间有边：它们在程序的某个点上同时活跃 活跃变量分析（下一章） 这就是寄存器冲突图 若t1和t2之间无边，则可以将它们分配到同一个寄存 器中

66 E.g., b and c cannot be in the same register
例子 a := b + c d := -a e := d + f f := 2 * e b := d + e e := e - 1 b := f + c a f e d c b E.g., b and c cannot be in the same register E.g., b and d can be in the same register

67 图着色问题 图着色问题是指，给图上结点着色，使得有边的 两个结点（“邻居”）总是不同颜色
如果一个图能用k种颜色着色，则称它为“k-可 着色的”

68 用图着色进行寄存器分配 图：寄存器冲突图 颜色：寄存器 设k为物理寄存器的个数
图上结点：变量 颜色：寄存器 设k为物理寄存器的个数 若程序的寄存器冲突图是k-可着色的，那么可以 用不多于k个寄存器对程序进行寄存器分配

69 Graph Coloring. Example.
Consider the example RIG r4 r1 r2 r3 a f e d c b There is no coloring with less than 4 colors There are 4-colorings of this graph

70 a f e d c b r4 r1 r2 r3 a := b + c d := -a e := d + f b := d + e
e := e - 1 b := f + c r2 := r3 + r4 r3 := -r2 r2 := r3 + r1 r1 := 2 * r2 r3 := r3 + r2 r2 := r2 - 1 r3 := r1 + r4 a f e d c b r4 r1 r2 r3

71 解决图着色问题 确定一个图是否k-可着色是NP完全问题 使用启发式算法，基于如下观察： 假设图上有一个结点t，它有少于k个邻居
如果得到的图是k-可着色的，那么原来的图必然也是 k-可着色的 原因：t的邻居个数n<k，所以一定存在一种与邻居都不同的 颜色给t着色

72 图着色问题的启发式算法 在图上选择一个结点t，它的邻居个数小于k 将t入栈，从图上删除t和它的边
图为空：从栈顶开始给结点着色，每一步着色 时总是选择与已经着色的邻居不同的颜色 图不空：？

73 Graph Coloring Example (1)
Start with the RIG and with k = 4: a b f Stack: {} c e d Remove a and then d

74 Graph Coloring Example (2)
Now all nodes have fewer than 4 neighbors and can be removed: c, b, e, f b f Stack: {d, a} c e

75 Graph Coloring Example (3)
Start assigning colors to: f, e, b, c, d, a a r2 b r3 r1 f c e d r4 r2 r3

76 若化简的最终图不空 图上所有结点都有至少k个邻居 例：对下图进行3-着色 a f e d c b

77 若化简的最终图不空 删除a后就get stuck了 选择一个结点作为a candidate for spilling 假设选择f
b

78 删除f并将其入栈，然后继续化简图 按顺序b, d, e, c e d c b

79 着色阶段：到达给f着色的时刻 希望f的邻居只使用了少于3种颜色 若不幸运，则spill f e d c b r3 r1 r2 ? f

80 Spilling 若不幸运，则要为f分配内存空间（通常在栈上） 在使用f的每条指令之前插入“LD f, fa”
在给f定值的每条指令之后插入“ST fa, f”

81 This is the new code after spilling f
Spilling. Example. This is the new code after spilling f a := b + c d := -a LD f, fa e := d + f b := d + e e := e - 1 f := 2 * e ST fa, f LD f, fa b := f + c

82 重做活跃变量分析 新的活跃变量信息与原来的差不多，除了f 现在f只在下面两种程序点活跃：
在LD f, fa和下一条指令之间 在ST fa, f和上一条指令之间 Spilling缩减了f的活跃区间，因此减少了它和其 他变量冲突的可能 所以寄存器冲突图上f的邻居变少

83 Spilling后的寄存器冲突图 与原图的唯一区别：被spill的结点f的边减少了 现在的图是3-可着色的 a f e d c b a f

84 Spilling 可能需要多次spill才能成功着色 最困难的是选择哪个变量spill 一些启发式技术

85 代码生成怎么做？ 过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图 
过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图  为单个基本块生成代码的简单的算法  窥孔优化：对目标代码进行优化  全局寄存器分配算法：图着色方法  基于树重写的指令选择

86 树重写实现指令选择 在某些机器上，同一个三地址指令可以使用多种 机器指令实现
指令选择：为实现中间表示形式中出现的运算符 而选择适当的机器指令 树重写：用树来表示中间代码，按照特定的规则 不断覆盖这棵树并生成机器指令

87 例子 在中间代码插入运行时刻地址后得到这棵树

88 目标指令选择 通过应用一个树重写规则序列来生成。 重写规则形式： 一组树重写规则被称为一个树翻译方案 树重写规则示例：

89 LD R0, #a ADD R0, R0, SP ADD R0, R0, i(SP) LD R1, b INC R1 ST *R0, R1

90 树翻译方案的工作模式 给定一颗输入树，树重写规则中的模板被用来匹 配输入树的子树
如果找到一个匹配的模板，那么输入树中匹配的 子树将被替换为相应规则中的替换结点，并且执 行规则的相应动作。动作可能是生成相应的机器 指令序列 不断匹配，直到这颗树被归约成单个结点，或找 不到匹配的模板为止 实践中的树翻译方案：能够对每个输入树生成代 价最小的指令序列

91 树翻译方案生成目标指令示例 如何完成树匹配？ 如果在某个给定时刻有多个模板可以匹配 把树重写规则替换成相应的上下文无关文法的产生式
产生式的右部是其指令模板的前缀表示 使用LR分析器来完成树匹配 如果在某个给定时刻有多个模板可以匹配 匹配到大树优先

92 本章总结 过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图 
过程调用和返回的代码生成，名字（过程名或变 量名）的运行时刻地址  将中间代码划分为基本块，形成流图  为单个基本块生成代码的简单的算法  窥孔优化：对目标代码进行优化  全局寄存器分配算法：图着色方法  基于树重写的指令选择 