基本块和流图

本节介绍一种用图来表示中间代码的方法。即使这个图没有显式地被代码生成算法生成，它对于讨论代码生成也是有帮助的。

基本块

把中间代码划分称为基本块(basic block)。

划分方法：

我们以第一个指令作为一个新基本块的开始，然后不断把后续的指令加进入，直到我们碰到一个无条件跳转、条件跳转、或者下一条指令前的标号为止。

知道一个变量的值接下来会在什么时候使用对于生成良好的代码是非常重要的。如果一个变量的值当前存放在一个寄存器里，且之后一直不会被使用，那么这个寄存器就可以分派给另一个变量。

在一个三地址语句中对一个名字的使用(use)的定义如下。假设三地址语句i给x赋值给一个值。如果语句j的一个运算分量为x，并从语句i开始可以通过未对x进行赋值的路径到达语句j，那么我们说语句j使用了在语句i处计算得到的值。我们可以进一步说x在语句i处活跃(live)。

GPT：具体来说，一个变量在程序的某个点活跃，意思是从这个点出发，有可能在将来某个点再次使用（use）到这个变量的值。

（对基本块中每个语句确定活跃性和后续使用信息的算法：《编译原理》p340）

当将一个中间代码程序划分成为基本块之后，我们使用一个流图来表示它们之间的控制流。

我们通常会增加两个分别称为入口(entry)和”出口(exit)”的节点。它们不和任何可执行的中间指令对应。

在流图里面把到达指令的序号或标号的跳转指令替换为到达基本块的跳转。这么做的原因是，在流图构造完之后经常会对多个基本块中的指令做出实质性改变。如果跳转的目标是指令，我们将不得不在每次改变了某个目标指令之后修正跳转指令的目标。

if expr goto labelxxx -> if expr goto BLOCKXXX

我们可能频繁地改变一个基本块中的指令数量，所以为每一个基本块创建一个指令链表是一种高效地表示方式。

每个程序会花大量时间执行循环，所以对于一个编译器来说，为循环生成优良的代码就变得非常重要。

假设有一个结点集合L。

（END）