5.5.4 Combining Instruction Sequences

This section describes the details on how instruction sequences are represented

and combined. Recall from 5.5.1 that an instruction sequence is

represented as a list of the registers needed, the registers modified, and the

actual instructions. We will also consider a label (symbol) to be a degenerate

case of an instruction sequence, which doesn’t need or modify any registers.

So to determine the registers needed and modified by instruction sequences we

use the selectors

本节介绍指令序列的表示方式以及如何将其组合的细节。回顾 5.5.1 节：一个指令序列表示为由所需寄存器、被修改寄存器和实际指令三部分构成的表。我们还将标号（符号）视为指令序列的退化情形——它既不需要也不修改任何寄存器。为了确定指令序列所需和修改的寄存器，我们使用选择函数

and to determine whether a given

sequence needs or modifies a given register we use the predicates

而为了判断某个给定序列是否需要或修改某个给定寄存器，我们使用谓词

In terms of these predicates and selectors, we can implement the various

instruction sequence combiners used throughout the compiler.

借助这些谓词和选择函数，我们可以实现编译器中用到的各种指令序列组合器。

The basic combiner is append-instruction-sequences. This takes as

arguments an arbitrary number of instruction sequences that are to be executed

sequentially and returns an instruction sequence whose statements are the

statements of all the sequences appended together. The subtle point is to

determine the registers that are needed and modified by the resulting sequence.

It modifies those registers that are modified by any of the sequences; it needs

those registers that must be initialized before the first sequence can be run

(the registers needed by the first sequence), together with those registers

needed by any of the other sequences that are not initialized (modified) by

sequences preceding it.

最基本的组合器是 `append-instruction-sequences`。它接受任意数量的指令序列作为参数，这些序列将被顺序执行，并返回一个指令序列，其语句是所有序列的语句依次拼接而成。微妙之处在于如何确定结果序列所需和修改的寄存器。它修改的寄存器是任意一个子序列所修改的寄存器的并集；它所需的寄存器包括：第一个序列运行前必须已初始化的寄存器（即第一个序列所需的寄存器），以及其余任意序列所需但未被其前驱序列初始化（修改）的寄存器。

The sequences are appended two at a time by append-2-sequences. This

takes two instruction sequences seq1 and seq2 and returns the

instruction sequence whose statements are the statements of seq1

followed by the statements of seq2, whose modified registers are those

registers that are modified by either seq1 or seq2, and whose

needed registers are the registers needed by seq1 together with those

registers needed by seq2 that are not modified by seq1. (In

terms of set operations, the new set of needed registers is the union of the

set of registers needed by seq1 with the set difference of the registers

needed by seq2 and the registers modified by seq1.) Thus,

append-instruction-sequences is implemented as follows:

各序列通过 `append-2-sequences` 两两拼接。该过程接受两个指令序列 seq1 和 seq2，返回一个指令序列，其语句是 seq1 的语句后接 seq2 的语句，其被修改寄存器是 seq1 或 seq2 所修改的寄存器，其所需寄存器是 seq1 所需的寄存器，加上 seq2 所需但未被 seq1 修改的寄存器。（用集合运算表述：新的所需寄存器集合是 seq1 所需寄存器集合，与 seq2 所需寄存器集合和 seq1 所修改寄存器集合之差的并集。）因此，`append-instruction-sequences` 的实现如下：

This procedure uses some simple operations for manipulating sets represented as

lists, similar to the (unordered) set representation described in

2.3.3:

这个过程使用了一些简单的集合操作，集合以表的形式表示，类似于 2.3.3 节中描述的（无序）集合表示方式：

Preserving, the second major instruction sequence combiner, takes a list

of registers regs and two instruction sequences seq1 and

seq2 that are to be executed sequentially. It returns an instruction

sequence whose statements are the statements of seq1 followed by the

statements of seq2, with appropriate save and restore

instructions around seq1 to protect the registers in regs that

are modified by seq1 but needed by seq2. To accomplish this,

preserving first creates a sequence that has the required saves

followed by the statements of seq1 followed by the required

restores. This sequence needs the registers being saved and restored in

addition to the registers needed by seq1, and modifies the registers

modified by seq1 except for the ones being saved and restored. This

augmented sequence and seq2 are then appended in the usual way. The

following procedure implements this strategy recursively, walking down the list

of registers to be preserved:

`preserving` 是第二个主要的指令序列组合器，它接受一个寄存器表 regs 以及两个将顺序执行的指令序列 seq1 和 seq2，返回一个指令序列，其语句是 seq1 的语句后接 seq2 的语句，并在 seq1 周围插入适当的 save 和 restore 指令，以保护 regs 中那些被 seq1 修改但又被 seq2 所需的寄存器。为此，`preserving` 首先构建一个序列，该序列由必要的保存指令、seq1 的语句、必要的恢复指令依次组成。这个序列除了需要 seq1 所需的寄存器之外，还需要那些被保存和恢复的寄存器，并且它修改的寄存器是 seq1 所修改的寄存器，但不包括那些被保存和恢复的寄存器。然后将这个增强后的序列与 seq2 按常规方式拼接。下面的过程通过沿待保护寄存器表递归下降来实现这一策略：

Another sequence combiner, tack-on-instruction-sequence, is used by

compile-lambda to append a procedure body to another sequence. Because

the procedure body is not “in line” to be executed as part of the combined

sequence, its register use has no impact on the register use of the sequence in

which it is embedded. We thus ignore the procedure body’s sets of needed and

modified registers when we tack it onto the other sequence.

另一个序列组合器 `tack-on-instruction-sequence` 由 `compile-lambda` 用来将过程体追加到另一个序列的末尾。由于过程体并非"内联"在组合序列中执行，其寄存器使用情况对嵌入它的那个序列的寄存器使用没有任何影响。因此，当我们将过程体追加到另一个序列时，会忽略过程体所需和修改的寄存器集合。

Compile-if and compile-procedure-call use a special combiner

called parallel-instruction-sequences to append the two alternative

branches that follow a test. The two branches will never be executed

sequentially; for any particular evaluation of the test, one branch or the

other will be entered. Because of this, the registers needed by the second

branch are still needed by the combined sequence, even if these are modified by

the first branch.

`compile-if` 和 `compile-procedure-call` 使用一种名为 `parallel-instruction-sequences` 的特殊组合器，将测试之后的两个备选分支拼接起来。这两个分支永远不会被顺序执行；对于测试的每一次特定求值，只会进入其中一个分支。正因为如此，第二个分支所需的寄存器在组合序列中仍然是必需的，即使这些寄存器已被第一个分支修改。