尽管世代方法在处理年轻对象时非常高效，但它在处理成熟对象时却相对低效，因为每当一个垃圾回收过程涉及某个成熟对象时，该对象都会被移动，而且它们不太可能变成垃圾。另一种 被称为列车算法的增量式回收方法用于改进对成熟对象的处理。它可以用来回收所有的垃圾。 但是更好的方法是使用世代方法来处理年轻的对象，只有当这些对象经历了几轮世代回收之后仍然存在，才将它们提升到另一个由列车算法管理的堆区。列车算法的另一个优点是我们永远不需要进行全面的垃圾回收过程，而在世代垃圾回收中却仍然必须偶尔那样做。

为了描述列车算法的动机,我们首先看一个简单的例子。该例子告诉我们为什么在世代方法中必须偶尔进行一轮全面的垃圾回收。给出了位于两个区域i和j中的两个相互连接的对象，其中j>i。因为这两个对象都有来自其区域之外的指针，只对区域i或只对区域j进行回收都不能回收这两个对象。然而，它们可能实际上是一个循环垃圾结构中的一部分，没有外部链接指向该垃圾结构。一般来说，这里显示的对象之间的“链接”可能涉及很多对象和一条很长的引用链。

简单的基于跟踪的回收器是以全面停顿的方式进行垃圾回收的，它可能造成用户程序的运行的长时间的停顿。我们可以每次只做部分垃圾回收工作，从而减少一次停顿的长度。我们可以按照时间来分割工作任务，使垃圾回收和增变者的运行交错进行。我们也可以按照空间来分割工作任务，每次只完成一部分垃圾的回收。前者称为增量式回收（incremental collection),后者称为部分回收（partial collection)。

增量式回收器将可达性分析任务分割成为若干个较小单元，并允许增变者和这些任务单元交错运行。可达集合会随着增变者的运行发生变化，因此增量式回收是很复杂的。我们将看到，寻找一个稍微保守的解决方法将使得跟踪更加髙效。

我们必须控制启动跟踪过程的频率，这很重要。跟踪步骤就像是一场赛跑。增变者创建出必须被扫描的新对象和新引用，而跟踪过程则试图扫描所有可达对象，并重新扫描同时产生的脏卡片。
下面给出一个并行、并发垃圾回收算法的大概描述，我们可以仔细看一下，：

1)扫描每个增变者线程的根集，将所有可以从根集中直接到达的对象设为待扫描状态。完成这一步的最简单的增量式做法是等待一个增变者线程调用内存管理器，如果那时它的根集还没有被扫描，就让它扫描自己的根集。如果所有其他跟踪工作都已经完成，而某个增变者线程还没有调用内存分配函数，那么必须暂停这个线程，扫描它的根集。

有时候，虽然程序员使用了带有垃圾回收机制的语言，但是仍然希望自己管理内存，或者管理部分内存。也就是说，尽管仍然存在一些引用指向某些对象，但程序员知道这些对象不会再被访问。一个来自编译的例子可以说明这一问题。

我们已经看到，词法分析器通常会管理一个符号表，为它碰到的每个标识符创建一个对象。比如，这些对象可能作为词法值被附加于语法分析树中代表这些标识符的叶子结点上。然而，以这些标识符的字符串作为键值构造一个散列表有助于对这些对象进行定位。这个散列表可以在词法分析器碰到一个标识符词法单元时更容易找到对应的对象。

我们的编译器模型的最后一个步骤是代码生成器。它以编译器前端生成的中间表示（IR)和相关的符号表信息作为输人，输出语义等价的目标程序。

对代码生成器的要求是很严格的。目标程序必须保持源程序的语义含义，还必须具有很的质量。也就是说，它必须有效地利用目标机器上的可用资源。此外，代码生成器本身必须能高效运行。

具有挑战性的是，从数学上讲，为给定源程序生成一个最优的目标程序是不可判定问题码生成中碰到的很多子问题（比如寄存器分配)都具有难以处理的计算复杂性。在实践中，我们使用那些能够产生良好但不一定最优的代码的启发性技术。幸运的是，启发性技术已经非常成熟，一个精心设计的代码生成器所产生的代码要比那些由简单的生成器生成的代码快好几倍。

构造一个能够产生高质量机器代码的代码生成器的难度会受到目标机器的指令集体系结构的极大影响。最常见的目标机体系结构是RISC(精简指令集计算机）、CISC(复杂指令集计算机）和基于堆桟的结构。

RISC机通常有很多寄存器、三地址指令、简单的寻址方式和一个相对简单的指令集体系结构。相反，CISC机通常具有较少寄存器、两地址指令、多种寻址方式、多种类型的寄存器、可变长度的指令和具有副作用的指令。

在基于栈的机器中，运算是通过把运算分量压人一个栈，然后再对栈顶的运算分量进行运算而完成的。为了获得高性能，栈顶元素通常保存在寄存器中。因为人们觉得堆栈组织的限制太多，并且需要太多的交换和拷贝操作，所以基于堆栈的机器几乎已经消失了。

目标机指令集本身的特性对指令选择的难度有很大的影响。比如，指令集的统一性和完整性是两个很重要的因素。如果目标机没有以统一的方式支持每种数据类型，那么总体规则的每个例外都需要进行特别处理。比如，在某些机器上，浮点数运算使用单独的寄存器完成。
代码生成器必须把IR程序映射成为可以在目标机上运行的代码序列。完成这个映射的复杂性由如下的因素决定：

*IR的层次。

*指令集体系结构本身的特性。

*想要达到的生成代码的质量。

如果IR是高层次的，代码生成器就要使用代码模板把每个IR语句翻译成为机器指令序列。但是，这种逐个语句生成代码的方式通常会产生质量不佳的代码。这些代码需要进一步优化。如果IR中反映了相关计算机的某些低层次细节，那么代码生成器就可以使用这些信息来生成更 加高效的代码序列。

我们将说明如何使用静态和栈式内存分配为简单的过程调用和返回生成代码，以此将IR中的名字转换成为目标代码中的地址。我们描述了每个正在执行的程序是如何在它的逻辑地址空间上运行的。这个空间被划分成为四个代码及数据区域：

1)一个静态确定的代码区Code。这个区存放可执行的目标代码。目标代码的大小可以在编译时刻确定。

2)一个静态确定的静态数据区Static。这个区存放全局常量和编译器生成的其他数据。全局常量和编译器数据的大小也可以在编译时刻确定。

3)一个动态管理的堆区heap。这个区存放程序运行时刻分配和释放的数据对象。Heap的大小不能在编译时刻静态确定。

首先，在流图里面把到达指令的序号或标号的跳转指令替换为到达基本块的跳转，这么做是很正常的。回忆一下，所有条2件或无条件跳转指令总是跳转到某些基本块的首指令，而现在这些跳转指令指向了相应的基本块。

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

流图就是通常的图，它可以用任何适合表示图的数据结构来表示。结点（即基本块）的内容需要有它们自己的表示方式。我们可以用一个指向该基本块在三地址指令数组中的首指令的指针，再加上基本块的指令数量或一个指向结尾指令的指针来表示结点的内容。但是，因为我们可能会频繁改变一个基本块中的指令数量，所以为每个基本块创建一个指令链表是一种高效的表示方法。

在DAG上消除死代码的操作可以按照如下方式实现。我们从一个DAG上删除所有没有附加活跃变量的根结点（即没有父结点的结点）。重复应用这样的处理过程就可以从DAG中消除所有对应于死代码的结点。

代数恒等式表示基本块的另一类重要的优化方法。比如，我们可以使用诸如:

x+0=0+x=x  x-0 =x

x*1=1*x=x  x/1 =x

这样的恒等式来从一个基本块中消除计算步骤。

另一类代数优化是局部强度消减（reduction in strength)，就是把一个代价较高的运算替换为 一个代价较低的运算。比如：