指令选择可能是一个大型的排列组合任务。对于像CISC这样的具有丰富寻址模式的机器，或者具有某些特殊目的指令（比如信号处理指令）的机器尤其如此。即使我们假设求值的顺序已经给定，并且假设寄存器通过另一个独立的机制进行分配，指令选择——为实现中间表示形式中出现的运算符而选择目标语言指令的问题——仍然是一个规模很大的排列组合任务。

我们把指令选择当作一个树重写问题来处理。目标指令的树形表示已经在代码生成器的生成器中得到有效使用。这种生成器可以依据目标机器的高层规约自动构造出一个代码生成器的指令选择阶段。对于某些机器，相对于使用树表示方法而言，使用DAG表示方法能够生成更好的代码。但是DAG匹配比树匹配更加复杂。

在考虑通用的树匹配方法之前，我们先考虑一个特殊的匹配方法。这个方法使用LR语法分析器来完成模式匹配。输人树可以用前缀方式表示为一个串。比如，树的前缀表示为：

=ind + +Ca Rsp  ind + Ci RsP + Mb C1

一个树翻译方案可以转换为一个语法制导的翻译方案，方法是把每个树重写规则替换为相应的上下文无关文法的产生式。对于一个树重写规则，相应的产生式的右部就是其指令模板的前缀表示方式。

根据这个翻译方案的产生式，我们可以使用某个LR语法分析器构造技术来构建一个LK语法分析器。目标代码通过每一步归约中发出的机器指令来生成。

当一个基本块仅包含单一的表达式求值时，或者我们认为以逐次处理各个表达式的方式为基本块生成代码就已经足够了，那么我们就可以最佳地选择寄存器。在下面的算法中，我们引人对一个表达式树（即一个表达式的语法树）的结点添加数字标号的方案。在使用固定个数的寄存器来对一个表达式求值的情况下，该方案允许我们为表达式生成最优的代码。

Ershov 数

一开始，我们给一个表达式树的每个结点各赋予一个数值。该数表示如果我们不把任何临时值存放问内存的话，计算该表达式需要多少个寄存器。这些数有时被称为Ershou数（Ershov nurnher)。这是根据A.Ershov命名的，他为只有一个算术寄存器的机器使用了类似的方案。对我们的机器模型而言，计算Ershov数的规则如下：

假设在我们的机器模型中，所有的运算分量都必须在寄存器中，且寄存器可以同时用于存放某个运算的运算分量和结果。可以证明，如果在计算表达式的过程中不允许把中间结果保存回内存，那么一个结点的标号就等于计算该结点对应的表达式时需要的最少的寄存器个数。因为在这个机器模型中，我们必须把每个运算分量加载到寄存器中，且必须计算每个内部结点所对应的中间结果，所以，造成生成代码不是最优代码的唯一可能是我们使用了不必要的将临时结果存回内存的指令。对这个断言的证明包含在下面的算法中。这个算法生成的代码不包含将临时结果存回内存的指令，而这个代码所使用的寄存器数目就是根结点的标号。

计算一个结点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实际是一个常量且可以被折叠的情况下认为不是一个常量），但是把一个实际可到达的定值当作不可到达就是不安全的（我们可能把*替换为一个常量，但是实际上程序有时会赋予一个不同于该常量的值）。