计算一个结点n的代价包括在给定寄存器数量的情况下对S求值时所需要的全部加载和保 存运算，也包括了计算S的根结点处的运算符所需要的代价。代价向量的第0个元素存放的是把子树S的值计算出来并保存到内存的最优代价。只需要考虑S的根结点的各子树的最优程序的 不同组合，就可以生成S的最优程序。这是由连续求值的性质来确保的。这个限制减少了需要考虑的情况。
动态规划算法有三个步骤（假设目标机器具有r个寄存器）：

1)对表达式树的每个结点n自底向上地计算得到一个代价数组C,其中C的第i个元素 C[i]是在假设有i（1≤i≤r)个可用寄存器的情况下对以n为根的子树S求值并将结果存放在一个寄存器中的最优代价。

如果我们简单地把每个高级语言结构独立地翻译成为机器代码，那么会带来相当大的运行时的开销。下面讨论如何消除这样的低效率因素。在目标代码中消除不必要的指令，或者把一个指令 序列替换为一个完成同样功能的较快的指令序列，通常被称为“代码改进”或者“代码优化”。

局部代码优化（在一个基本块内改进代码）的相关知识已经简单地了解过了。下面我们将处理全局代码优化问题。在全局优化中，代码的改进将考虑在多个基本块内发生的事情。我们会讨论一些主要的代码改进机会。

优化的主要来源

编译器的优化必须保持源程序的语义。除了一些非常特殊的场合之外，一旦程序员选择并实现了某种算法，编译器不可能完全理解这个程序并把它替换为一个全然不同且更加高效的等价算法。编译器只知道如何应用一些相对低层的语义转换。在进行转换时，编译器用到一些常见的性质，比如像i+o = i这样的代数恒等式或使用一些程序语义（如在同样的值上进行同样的运算必然得到同样的结果）。

大部分全局优化是基于数据流分析（data-flow analyse)技术实现的。数据流分析技术是一组用以收集程序相关信息的算法。所有数据流分析的结果都具有相同的形式：对于程序中的每个指令，它们描述了该指令每次执行时必然成立的一些性质。不同性质的分析方法各不相同。比如，对于常量传播分析而言，要判断在程序的每个点上，程序使用的各个变量是否在该点上具有唯一的常量值。比如，这个信息可以用于把变量引用替换为常量值。另一个例子是，活跃性分析确定在程序的每个点上，在某个变量中存放的值是否一定会在被读取之前被覆盖掉。如果是，我们就不需要在寄存器或内存位置上保留这个值。

“到达定值”是最常见和有用的数据流模式之一。只要知道当控制到达程序中每个点的时候，每个变量-可能在程序中的哪些地方被定值，我们就可以确定很多有关x的性质。下面仅仅给出两个例子：一个编译器能够根据到达定值信息知道x在点p上的值是否为常量，而如果x在点p 上被使用，则调试器可以指出x是否未经定值就被使用。

如果存在一条从紧随在定值后面的程序点到达某一个程序点P的路径，并且在这条路径上 d没有被“杀死”，我们就说定值d到达程序点p。如果在这条路径上有对变量x的其他定值，我们就说变量x的这个定值被“杀死”了e。直观地讲，如果某个变量x的一个定值d到达点p,在点p处使用的x的值可能就是由d最后定值的。

一个重要的优化是在循环中找到归纳变量并优化它们的计算。对于一个变量^如果存在 一个正的或负的常数c使得每次x被赋值时它的值总是增加c，那么x就称为“归纳变量”。比如， 在i和t2都是B2组成的循环中的归纳变量。归纳变量可以通过每次迭代进行一次简 单的增量运算（加法或减法）来计算。把一个高代价的运算（比如乘法）替换为一个代价较低的运 算（比如加法）的转换被称为强度消减（strength reduction)。但是归纳变量不仅允许我们在适当的 时候进行强度消减优化；在我们沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，我们常常可以将这组变量删剩一个。

实际数据流值是通过程序的所有可能执行路径来定义的。所有的数据流模式计算得到的 都是对实际数据流值的估算。我们必须保证所有的估算误差都在“安全”的方向上。如果一个策略性决定不允许我们改变程序计算出的内容，它就被认为是“安全的”（或者说“保守的”）。 遗憾的是，安全的策略会让我们错失一些能够保持程序含义的代码改进机会。但实际上对所有的代码优化技术而言，没有哪个安全的策略可以不错失任何机会。使用不安全策略就是以改变程序含义的代价来加快代码速度。一般来说，这是不可接受的。

因此在设计一个数据流模式的时候，我们必须知道这些信息将如何被使用，并保证我们做出的任何估算都是在“保守”或者说“安全”的方向上。每个模式和应用都要单独考虑。比如，如果我们把到达定值信息用于常量折叠，那么把一个实际不可到达的定值当作可到达就是安全的（我们可能在x实际是一个常量且可以被折叠的情况下认为不是一个常量），但是把一个实际可到达的定值当作不可到达就是不安全的（我们可能把*替换为一个常量，但是实际上程序有时会赋予一个不同于该常量的值）。

有些代码改进转换所依赖的信息是按照程序控制流的相反方向进行计算的，我们现在将要研究这样的一个例子。在活跃变量分析（live-variable analysis)中，我们希望知道对于变量x和程 序点P, *在点上的值是否会在流图中的某条从点P出发的路径中使用。如果是，我们就说x在 p上活跃，否则就说*在p上是死的。

活跃变量信息的重要用途之一是为基本块进行寄存器分配。这个问题的某些方面，在一个值被计算并保存到一个寄存器中后，它很可能会在基本块中使用。如果它在基本块的结尾处是死的，就不必在结尾处保存这个值。另外，在所有寄存器都被占用时，如果我们还需要申请一个寄存器的话，那么应该考虑使用一个存放了已死亡的值的寄存器，因为这个值不需要保存到内存。

交汇运算是交集运算，任何发现x+y在某个程序点上不可用的理由都会在流图中沿着所有可能的路径向前传播，直到x+y被重新计算并再次变得可用为止。第二，只有两个理由可能会使x+y变成不可用的。

1）因为x或y在基本块B中被定值且其后没有计算x+y，因此x+y被杀死。在这种情况下，我们第一次应用传递函数fs的时候，x+y就会从OUT[B]中被删除。

2)在某些路径中，x+y—直没有被计算。因为x+y肯定不会在OUT[ENTRY]中，并且它也不会在上面说的那条路径中被生成。我们可以通过对路径长度的归纳来证明x + y最终会从这条路径的所有基本块的IN和OUT值中删除。

把域V画成一个格图对我们会有所帮助。格图的结点是V的元素，而它的边是向下的，即如果y≤x，那么从x到y有一个边。给出了一个到达定值数据流模式的集合V。其中有三个定值：d1、d2和d3。因为半格中的偏序关系在≤是⊇,从这三个定值的集合的子集到 其所有超集有一个向下的边。因为 ≤是传递的，如果有一条从x到y的路径，我们可以按照惯例省略从x到y的边。因此，虽然在这个例子中{d1,d2,d3}≤{d1},我们并没有画出这条边，因为这个边可以用经过d1，d2的路径来表示。

有一点也很有用，即我们可以从这样的图中读出交汇值。因为x ∧y就是它们的最大下界，因此这个值总是最高的、从x和y都有向下的路径到达的元素z。比如，如果想x是 {d1}而y是{d2},那么z就是{d1，d2}。这是正确的，因为这里的交汇运算是并集运算。顶元素将出现在格图的顶部，也就是说，从T到图中的每个元素都有一条向下的路径。类似地，底元素将出现在图的底部，从每个元素都有一条边到达丄。

数据流框架具有有穷高度的情况。因为每个IN[B]和OUT[B]的值在每次被改变时都会减小，而程序在某一轮循环中没有值改变时就会停止，因此算法的迭代次数不会大于框架高度和流图结点个数的乘积，因此算法必然终止。
我们可以对算法进行推广，使之能够处理各种数据流问题。通用数据流框架的迭代解法。

输入：一个由下列部分组成的数据流框架：

1)一个数据流图，它有两个被特别标记为ENTRY和EXIT的结点。

2)数据流的方向D。

3)一个值集V。