对DAG的各种优化处理可以在生成DAG图时进行，也可以在DAG构造完成后通过对DAG的运算完成。在完成这些优化处理之后，我们就可以根据优化得到的DAG重组生成相应基本块的三地址代码。对每个具有一个或多个附加变量的结点，我们构造一个三地址语句来计算其中某个变量的值。我们倾向于把计算得到的结果赋给一个在基本块出口处活跃的变量。但是，如果我们没有全局活跃变量的信息作为依据，就要假设程序的所有变量都在基本块出口处活跃（但是不包含编译器为了处理表达式而生成的临时变量）。
如果结点有多个附加的活跃变量，我们就必须引入复制语句，以便给每一个变量都赋予正确的值。有时我们可以通过全局优化技术，设法用其中的一两个变量来替代其他变量，从而消除这些复制语句。
我们的代码生成算法依次考虑了各个三地址指令，并决定需要哪些加载指令来把必需的运算分量加载进寄存器。在生成加载指令之后，它开始生成运算代码。然后，如果有必要把结果存放人一个内存位置，它还会生成相应的保存指令。
为了做出这些必要的决定，我们需要一个数据结构来说明哪些程序变量的值当前被存放在哪个或哪些寄存器里面。我们还需要知道当前存放在一个给定变量的内存位置上的值是否就是这个变量的正确值。因为变量的新值可能已经在寄存器中计算出来但还没有存放到内存中。这个数据结构具有下列描述符：
让我们考虑如何针对一个三地址指令I实现函数getReg（I)。实现这个函数可以选择很多种方法，当然也存在一些绝对不可以选择的方法。这些错误方法会因丢失一个或多个活跃变量的值而导致生成错误代码。我们用处理一个运算指令的步骤来开始我们的讨论，还是用x=y+z作为一般性的例子。首先，我们必须为y和z分别选择一个寄存器。这两次选择所面临的问题是相同的，因此我们将集中考虑为y选择寄存器Ry的方法。选择规则如下：
1)如果y当前就在一个寄存器中，则选择一个已经包含了y的寄存器作为Ry。不需要生成一个机器指令来把y加载到这个寄存器。
另一个窥孔优化的机会是消除不可达的指令。一个紧跟在无条件跳转之后的不带标号的指令可以被删除。通过重复这个运算，就可以删除一个指令序列。比如，为了调试的目的，一个大型程序中可能含有一些只有当变量debug等于1时才运行的代码片断。在中间表示形式中，这个代码看起来可能就像
if debug == 1 goto L1
goto L2
L1: print debugging information
L2:
一个显而易见的窥孔优化方法是消除级联跳转指令。因此，不管debug的值是什么，上面的代码序列可以被替换为：
简单的中间代码生成算法经常生成目标为无条件跳转指令的无条件跳转指令，到达条件跳转指令的无条件跳转指令，或者到达无条件跳转指令的条件跳转指令。这些不必要的跳转指令可以通过下面几种窥孔优化技术从中间代码或者目标代码中消除。我们可以把序列
goto L1
...
L1: goto L2
替换为
goto L2
...
LI: goto L2
如果没有跳转到L1的指令，并且语句L1:goto L2之前是一个无条件跳转指令，所以可以消除这个语句。
代码生成算法在单个基本块的运行期间使用寄存器来存放值。但是，在每个基本块的结尾处，所有活跃变量的值都被保存到内存中。为了省略一部分这样的保存及相应的加载指令，我们可以把一些寄存器指派给频繁使用的变量，并且使得这些寄存器在不同基本块中的(即全局的）指派保持一致。因为程序的大部分时间花在它的内部循环上，所以一个自然的全局寄存器指派方法是试图在整个循环中把频繁使用的值存放在固定的寄存器中。从现在开始，假设我们知道一个流图的循环结构，并且我们知道在一个基本块中计算的哪些值会在该基本块外使用。
指令选择可能是一个大型的排列组合任务。对于像CISC这样的具有丰富寻址模式的机器，或者具有某些特殊目的指令（比如信号处理指令）的机器尤其如此。即使我们假设求值的顺序已经给定，并且假设寄存器通过另一个独立的机制进行分配，指令选择——为实现中间表示形式中出现的运算符而选择目标语言指令的问题——仍然是一个规模很大的排列组合任务。
我们把指令选择当作一个树重写问题来处理。目标指令的树形表示已经在代码生成器的生成器中得到有效使用。这种生成器可以依据目标机器的高层规约自动构造出一个代码生成器的指令选择阶段。对于某些机器，相对于使用树表示方法而言，使用DAG表示方法能够生成更好的代码。但是DAG匹配比树匹配更加复杂。
在考虑通用的树匹配方法之前，我们先考虑一个特殊的匹配方法。这个方法使用LR语法分析器来完成模式匹配。输人树可以用前缀方式表示为一个串。比如，树的前缀表示为：
=ind + +Ca Rsp ind + Ci RsP + Mb C1
一个树翻译方案可以转换为一个语法制导的翻译方案，方法是把每个树重写规则替换为相应的上下文无关文法的产生式。对于一个树重写规则，相应的产生式的右部就是其指令模板的前缀表示方式。
根据这个翻译方案的产生式，我们可以使用某个LR语法分析器构造技术来构建一个LK语法分析器。目标代码通过每一步归约中发出的机器指令来生成。
当一个基本块仅包含单一的表达式求值时，或者我们认为以逐次处理各个表达式的方式为基本块生成代码就已经足够了，那么我们就可以最佳地选择寄存器。在下面的算法中，我们引人对一个表达式树（即一个表达式的语法树）的结点添加数字标号的方案。在使用固定个数的寄存器来对一个表达式求值的情况下，该方案允许我们为表达式生成最优的代码。
Ershov 数
一开始，我们给一个表达式树的每个结点各赋予一个数值。该数表示如果我们不把任何临时值存放问内存的话，计算该表达式需要多少个寄存器。这些数有时被称为Ershou数（Ershov nurnher)。这是根据A.Ershov命名的，他为只有一个算术寄存器的机器使用了类似的方案。对我们的机器模型而言，计算Ershov数的规则如下：
假设在我们的机器模型中，所有的运算分量都必须在寄存器中，且寄存器可以同时用于存放某个运算的运算分量和结果。可以证明，如果在计算表达式的过程中不允许把中间结果保存回内存，那么一个结点的标号就等于计算该结点对应的表达式时需要的最少的寄存器个数。因为在这个机器模型中，我们必须把每个运算分量加载到寄存器中，且必须计算每个内部结点所对应的中间结果，所以，造成生成代码不是最优代码的唯一可能是我们使用了不必要的将临时结果存回内存的指令。对这个断言的证明包含在下面的算法中。这个算法生成的代码不包含将临时结果存回内存的指令，而这个代码所使用的寄存器数目就是根结点的标号。
