nanopass之七--非尾调用

2015-03-11

1. Scheme子集6
2. * 4.1. verify-scheme
3. 4.2. remove-complex-opera
4. * 4.3. flatten-set!
5. * 4.4. impose-calling-conventions
6. * 4.5. uncover-frame-conflict
7. * 4.6. pre-assign-frame
8. * 4.7. assign-new-frame
9. * 4.8. introduce-allocation-forms
10. .9. select-instructions
11. * 4.10. uncover-register-conflict
12. * 4.11. finalize-frame-locations
13. * 4.12. discard-call-live
14. * 4.13. finalize-locations
15. * 4.14. expose-frame-var
16. * 4.15. expose-basic-blocks
17. * 4.16. Iterating
18. 样板运行时代码

这次作业我们将对我们的源语言做一项改变：加入非尾调用。尽管只是一个很小的变化，但是它影响了编译器很多地方。

2. 调用约定

为了处理非尾调用，我们需要添加一系列额外的调用约定：

• 在非尾调用的时候，调用者负责修改frame指针，以确保被调者的frame在自己的frame上方，并且调用者负责将参数放到被调者的frame中。
• 在返回的时候，被调者负责修改frame指针让它指向原来的frame。

3. Scheme子集7

这次我们要处理的Scheme子集的语法在Value和Effect中加入了非尾调用。

Program -> (letrec ([label (lambda (uvar) Body)]) Body) Body -> (locals (uvar*) Tail) Tail -> Triv | (binop Value Value) | (Value Value*) | (if Pred Tail Tail) | (begin Effect* Tail) Pred -> (true) | (false) | (relop Value Value) | (if Pred Pred Pred) | (begin Effect* Pred) Effect -> (nop) | (set! uvar Value) | (Value Value*) | (if Pred Effect Effect) | (begin Effect* Effect) Value -> Triv | (binop Value Value) | (Value Value*) | (if Pred Value Value) | (begin Effect* Value) Triv -> uvar | int | label

唯一变量(uvar)，标签(label)，整数(int)，二元操作(binop)和关系操作(relop)相比之前的子集没有变化。关于整数的机器限制也依然还在。

4. 要做的事

为了处理新的源语言，我们需要对以下步骤做少量的更新：

• verify-scheme
• remove-complex-opera*
• flatten-set!
• select-instructions
• uncover-register-conflict
• assign-registers
• assign-frame
• finalize-frame-locations
• finalize-locations

下面这些需要做较大的更新：

• impose-calling-conventions
• uncover-frame-conflict
• discard-call-live

需要重写：

• expose-frame-var

需要添加：

• pre-assign-frame
• assign-new-frame

• introduce-allocation-forms

并且要对我们的寄存器和frame分配步骤的迭代做一些小的修改。

这看起来好像有很多工作要做，确实也是。幸运的是，总共只有一个步骤assign-new-frame是新的，因为assign-new-frame本质上跟assign-frame是一样的。

新加入的以及更新的步骤在4.1到4.15部分是描述。迭代的变化在4.16部分中描述。

4.1. verify-scheme

这步需要加两个简单的match语句来处理Value和Effect中的非尾调用。

4.2. remove-complex-opera*

这步需要加两个简单的match语句来处理Value和Effect中的非尾调用。

4.3. flatten-set!

这步需要加两个简单的match语句来处理Value和Effect中的非尾调用。

这一步输出的语法如下所示。

Program -> (letrec ([label (lambda (uvar) Body)]) Body) Body -> (locals (uvar*) Tail) Tail -> Triv | (binop Triv Triv) | (Triv Triv*) | (if Pred Tail Tail) | (begin Effect* Tail) Pred -> (true) | (false) | (relop Triv Triv) | (if Pred Pred Pred) | (begin Effect* Pred) Effect -> (nop) | (set! uvar Triv) | (set! uvar (binop Triv Triv)) | (set! uvar (Triv Triv*)) | (Triv Triv*) | (if Pred Effect Effect) | (begin Effect* Effect) Triv -> uvar | int | label

4.4. impose-calling-conventions

这步也需要添加两个match语句处理非尾调用，而且，它必须记录下它找到的非尾调用的出去的frame变量的链表(如果你这步的版本还没有处理Pred和Effect表达式，这次必须做了)。

对于一个Effect中的非尾，这个步骤执行如下转换：

(proc e0 ... en-1 en ... en+k-1) => (return-point rp-label (begin (set! nfv0 en) ... (set! nfvk-1 en+k-1) (set! p0 e0) ... (set! pn-1 en-1) (set! ra rp-label) (proc fp ra p0 ... pn-1 nfv0 ... fvk-1)))

其中变量nfv0到nfvk-1是新的唯一变量，rp-label是新的标签。

变量列表(nfv0 ... nfvk-1)还必须记录为新的frame之一，放到包在body外面的在new-frames表中(见下面的语法)。最简单的实现方法是把他们加到一个链表中存储，这个链表的变量是一个Body辅助函数可以访问到的变量。所有其它的辅助函数也需要放到Body里面去。

我们使用新的new-frame变量而不是frame变量，因为我们还不知道哪些会是向外流出的变量，即，调用者的frame应该是多大。这会由新的步骤assign-new-frame决定。

new-frame中的变量的分配顺序是无关的，正如寄存器分配顺序那样。然而，所有的new-frame分配都应该在所有寄存器分配之前，这样可以限定参数寄存器的生命期。

对于一个出现在赋值右手边的非尾调用，这步执行的转换本质上跟上面的转换是一样的，除了return-point表后面要跟一个赋值，将左手边的变量赋给返回值寄存器，被调者是将返回值放在这个寄存器中的。

(set! uvar (proc e0 ... en-1 en ... en+k-1)) => (begin return-point code, as above (set! uvar rv))

做这个的最简单的方式是回调Effect辅助函数来处理，然后用赋值生成begin表达式，使用类似下面的match语句。

[(set! ,var (,rator ,rand* ...)) (make-begin (,(Effect (,rator ,rand* ...)) (set! ,var ,return-value-register)))]

新的new-frames表将包装在body，为每个body里面的frame列出new-frame变量(有序)。例如：

(new-frames ((nfv.17 nfv.18 nfv.19) (nfv.20)) tail)

声明tail包含两个return-point表，其中一个有三个传出的new-frame参数(nfv.17, nfv.18和nfv.19)，另一个有一个new-frame参数(nfv.20)。这个列表不需要特定的顺序，但是对列表中每一项，第一个传出参数必须是在第一个位置，第二个在第二个位置，依次类推。

这个步骤还要做的一件事是，将new-frame变量包含到locals表中。如果没有这么做，uncover-frame-conflict将不会在冲突表中为它们创建关联项。

这一步的输出的语法如下所示。

Program -> (letrec ([label (lambda () Body)]*) Body) Body -> (locals (uvar*) (new-frames (Frame*) Tail)) Frame -> (uvar*) Tail -> (Triv Loc*) | (if Pred Pred Pred) | (begin Effect* Tail) Pred -> (true) | (false) | (relop Triv Triv) | (if Pred Pred Pred) | (begin Effect* Pred) Effect -> (nop) | (set! Var Triv) | (set! Var (binop Triv Triv)) | (return-point label (Triv Loc*)) | (if Pred Effect Effect) | (begin Effect* Effect) Loc -> reg | fvar Var -> uvar | Loc Triv -> Var | int | label

4.5. uncover-frame-conflict

这步需要加一个match语句来处理非尾调用，即，return-point表。除此之后，它还要决定call-live变量集合和frame位置。如果一个变量或者frame位置在整个调用过程都是live的，那么它就是call-live的，也就是，在调用返回之后，它的值仍然可能被使用。

call-live的变量和frame位置的集合记录在一个新的call-live表，包装在body外面给assign-new-frame使用。集合将call-live变量(不是frame位置)单独记录在一个spills包装外面，提供给pre-assign-frame使用。

在实际场景中，call-live变量和frame位置是那些在return-point表之后还是live的。将所有的call-live变量集合收集起来最简单的实现方式是用一个Effect辅助函数处理return-point表并且将它们加到一个表示运行集合的变量中存储，这个变量是Body的辅助函数可访问的。所有其它的的辅助函数也需要放在Body中。

// 好长一段不会翻译

在这步的输出中，只有Body的语法有所不同。不同之处在于外面包装添加了spills，call-live和frame-conflict。

Body -> (locals (uvar*) (new-frames (Frame*) (spills (uvar*) (frame-conflict conflict-graph (call-live (uvar/fvar*) Tail)))))

4.6. pre-assign-frame

这一步为所有spills列表中的变量找到对应的frame位置。它跟assign-frame的不同只在于输入和输出表的Body部分。跟assign-frame类似，它消除spills表但是保留其它的表。它还添加了一个locate表，这是在输入中没有的。输出语法的Body如下所示。

Body -> (locals (uvar*) (new-frames (Frame*) (locate ([uvar fvar]*) (frame-conflict conflict-graph (call-live (uvar/fvar*) Tail)))))

4.7. assign-new-frame

对于每个body，这一步决定body的frame的大小，基于变量的位置和call-live列表中的frame变量。它然后为new-frames表中的每个new-frame变量列表选择位置，重写body的代码放到位于body的frame上方的被调者的frame中。

frame的大小很简单，就是call-live变量或者frame变量的frame位置的最大下标加一。frame变量的下标可以直接通过helpers.ss中的frame-var-index取得，而决定变量的下标涉及到先通过locate表找到它被赋值到哪个frame变量。

一旦frame大小n确定之后，每个传出的new-frame变量序列被分配到frame位置的fvn，fvn+1等等。这些被记录到locate表中，跟之前步骤已经做过的分配放到一起。还有，每个return-point表被重写为上推和下压frame指针寄存器，移动nb个字节，nb由procedure的frame元素数目n决定。

(return-point rp-label tail) => (begin (set! fp (+ fp nb)) (return-point rp-label tail) (set! fp (- fp nb)))

nb可以通过对n左移位得到，左移的量由helpers.ss中的变量align-shift决定。

例如，考虑下面的Body。

(locals (nfv.17 nfv.18 nfv.19 nfv.20 local ...) (new-frames ((nfv.17 nfv.18 nfv.19) (nfv.20)) (locate ([rp.12 fv0] [x.3 fv2]) (frame-conflict conflict-table (call-live (rp.12 x.3 fv1) tail)))))

frame大小是3，因为call-live变量和frame变量的最大的位置下标是2（rp.12下标是0，x.3下标是1，fv1是2。0，2和1中间最大的数是2）。所以每个frame变量的序列从fv3开始分配位置，输出如下面所示。

(locals (local ...) (ulocals () (locate ([rp.12 fv0] [x.3 fv2] [nfv.17 fv3] [nfv.18 fv4] [nfv.19 fv5] [nfv.20 fv3]) (frame-conflict conflict-table tail))))

不再需要new-frames表和call-live表，所以它们被去掉了。还有，new-frame变量也已经从locals表中去掉了，这个替换过程很简单，只是把new-frame表中出现的变量从locals表中去掉。

还有一个新的表出现：ulocals表是由introduce-allocation-forms插入的，现在我们的编译器只是简单的丢弃它。

在上面例子的tail中，对每个return-point表，frame指针上推和下移的量是3乘以align-shift，或者说是24，如果按helpers.ss中给出的align-shift的标准值计算。

理想情况，我们应该对每个出现非尾调用的地方分别地计算以决定frame大小，而不是考虑“所有的用这个大小就够了”的方式，这会导致一些包含调用的地方frame过大。这需要uncover-frame-conflict提供更多的关于call-live的信息，并且它还会使assign-new-frame复杂得多。所以我们决定不要搞得这么复杂。

4.8. introduce-allocation-forms

这个步骤去掉了，即，不再出现在compiler-passes的参数中了。之前由它引入的locate表，现在要由pre-assign-frame引入，并且ulocals表现在是由assign-new-frame引入。

4.9. select-instructions

这个步骤需要添加一个简单的match语句来处理Effect中的return-point表。

4.10. uncover-register-conflict

这个步骤需要添加一个简单的match语句来处理Effect中的return-point表。

一个非尾调用实际上就是对所有caller-save寄存器的一个的赋值。对于uncover-frame-conflict的情况，我们不需要关心冲突涉及的寄存器。对于uncover-register-conflict，在一个调用之后只有寄存器可能是live的(因为所有的call-live变量都已经被spilled了)，并且我们不关心寄存器对寄存器的冲突。因此，我们不需要担心非尾调用就是赋值这个问题，尽管我们可以检验除了frame指针和返回值寄存器以外，没有其它寄存器在return-point表之后是live的。

4.11. finalize-frame-locations

这个步骤需要添加一个简单的match语句来处理Effect中的return-point表。它还需要处理每次调用中的live的位置集合，就像它们是任意的Triv表达式，以方在live位置集合中出现了任何new-frame变量。例如，

(proc rbp r15 r8 r9 nfv.20)

应该被转换为

(proc rbp r15 r8 r9 fv3)

如果nfv.20已经被分配到了frame变量fv3。

如果没有完成这个，当nfv.20出现在live set中时，uncover-register-conflict会不知道如何处理。

4.12. discard-call-live

这个步骤现在必须处理Effect和Pred表达式来寻找非尾调用，不像之前，所有的调用都是在Tail中的。

4.13. finalize-locations

这个步骤需要添加一个简单的match语句来处理Effect中的return-point表。

4.14. expose-frame-var

这个步骤现在必须敏感地追踪frame指针寄存器的变化。这个很有必要，因为现在我们会在return-point表之前上推frame指针，然而frame变量可能会出现在return-point表中。出现在代码中的frame变量的下标受到frame指针变化的影响，需要调整相应的量。为了使它更通用，这一步需要能够处理任意位置frame指针的增加和减少，防止优化步骤以某种方式移动或者改变它们，例如，如果两个或者多个非尾调用连续出现时，把frame指针放在一个地方。

需要告知这个步骤使用的每个辅助函数，当前frame指针寄存器偏移是多少。它还需要返回最后的偏移量，做为一个附加的回返值，即，既要返回转换后的表达式，又要返回最后的frame指针偏移。Effect辅助函数需要识别frame指针的增加和减少的量并相应地调整偏移。对于if表达式，then和else部分开始的偏移应该相同，即，test部分之后的偏移量，并且最好检验一下结束时的then和else部分的偏移是相同的。

4.15. expose-basic-blocks

这个步骤需要添加一个match语句来处理Effect中的(return-point rp-label tail)表。

它应该将剩下的表达式打包到一个lambda表达式中，并将rp-label绑定到这个lambda表达式，像其它Tail表达式一个处理放到tail内部的表达式，并像其它Effect表达式那样处理"before"表达式（同一个begin表达式中，在return-point表之前的部分，如果有）。

4.16. Iterating

由于一些变量(call-live变量)是在迭代开始之前给定的frame位置，我们需要对迭代做一个简单的修改，将finalize-frame-locations移到迭代的最上面，这样每次从最下面过来都会运行它，最下面运行的是assign-frame。在每次迭代之前，以及由pre-assign-frame和assign-new-frame分配最终位置之后，都需要运行finalize-frame-locations。做这个修改并且添加新的步骤之后，compiler-passes参数如下面所示。

(compiler '( verify-scheme remove-complax-opera* flatten-set! impose-calling-conventions uncover-frame-conflict pre-assign-frame assign-new-frame (iterate finalize-frame-locations select-instructions uncover-register-conflict assign-registers (break when everybody-home?) assign-frame) discard-call-live finalize-locations expose-frame-var expose-basic-blocks flatten-program generate-x86-64 ))

5. 样板和运行时代码

都没有变化。

在tests6.ss里面有一个小的测试集，包括会通过的和不通过的测试。你需要确保你的编译器步骤至少能够通过这个测试集。

7. 编码提示

在tests6.ss里面有一个小的测试集，包括会通过的和不通过的测试。你需要确保你的编译器步骤至少能够通过这个测试集。