nanopass之七--非尾调用

2015-03-11

作业7

内容

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

1. 背景

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

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. 样板和运行时代码

都没有变化。

6. 测试

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

7. 编码提示

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

nanopass翻译scheme