这次作业我们将对我们的源语言做一项改变：加入非尾调用。尽管只是一个很小的变化，但是它影响了编译器很多地方。
为了处理非尾调用，我们需要添加一系列额外的调用约定：
在非尾调用的时候，调用者负责修改frame指针，以确保被调者的frame在自己的frame上方，并且调用者负责将参数放到被调者的frame中。
在返回的时候，被调者负责修改frame指针让它指向原来的frame。
这次我们要处理的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)相比之前的子集没有变化。关于整数的机器限制也依然还在。
为了处理新的源语言，我们需要对以下步骤做少量的更新：
下面这些需要做较大的更新：
需要重写：
需要添加：
丢弃：
并且要对我们的寄存器和frame分配步骤的迭代做一些小的修改。
这看起来好像有很多工作要做，确实也是。幸运的是，总共只有一个步骤assign-new-frame是新的，因为assign-new-frame本质上跟assign-frame是一样的。
新加入的以及更新的步骤在4.1到4.15部分是描述。迭代的变化在4.16部分中描述。
这步需要加两个简单的match语句来处理Value和Effect中的非尾调用。
这步需要加两个简单的match语句来处理Value和Effect中的非尾调用。
这步需要加两个简单的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
这步也需要添加两个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
这步需要加一个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)))))
这一步为所有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)))))
对于每个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复杂得多。所以我们决定不要搞得这么复杂。
这个步骤去掉了，即，不再出现在compiler-passes的参数中了。之前由它引入的locate表，现在要由pre-assign-frame引入，并且ulocals表现在是由assign-new-frame引入。
这个步骤需要添加一个简单的match语句来处理Effect中的return-point表。
这个步骤需要添加一个简单的match语句来处理Effect中的return-point表。
一个非尾调用实际上就是对所有caller-save寄存器的一个的赋值。对于uncover-frame-conflict的情况，我们不需要关心冲突涉及的寄存器。对于uncover-register-conflict，在一个调用之后只有寄存器可能是live的(因为所有的call-live变量都已经被spilled了)，并且我们不关心寄存器对寄存器的冲突。因此，我们不需要担心非尾调用就是赋值这个问题，尽管我们可以检验除了frame指针和返回值寄存器以外，没有其它寄存器在return-point表之后是live的。
这个步骤需要添加一个简单的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会不知道如何处理。
这个步骤现在必须处理Effect和Pred表达式来寻找非尾调用，不像之前，所有的调用都是在Tail中的。
这个步骤需要添加一个简单的match语句来处理Effect中的return-point表。
这个步骤现在必须敏感地追踪frame指针寄存器的变化。这个很有必要，因为现在我们会在return-point表之前上推frame指针，然而frame变量可能会出现在return-point表中。出现在代码中的frame变量的下标受到frame指针变化的影响，需要调整相应的量。为了使它更通用，这一步需要能够处理任意位置frame指针的增加和减少，防止优化步骤以某种方式移动或者改变它们，例如，如果两个或者多个非尾调用连续出现时，把frame指针放在一个地方。
需要告知这个步骤使用的每个辅助函数，当前frame指针寄存器偏移是多少。它还需要返回最后的偏移量，做为一个附加的回返值，即，既要返回转换后的表达式，又要返回最后的frame指针偏移。Effect辅助函数需要识别frame指针的增加和减少的量并相应地调整偏移。对于if表达式，then和else部分开始的偏移应该相同，即，test部分之后的偏移量，并且最好检验一下结束时的then和else部分的偏移是相同的。
这个步骤需要添加一个match语句来处理Effect中的(return-point rp-label tail)表。
它应该将剩下的表达式打包到一个lambda表达式中，并将rp-label绑定到这个lambda表达式，像其它Tail表达式一个处理放到tail内部的表达式，并像其它Effect表达式那样处理"before"表达式（同一个begin表达式中，在return-point表之前的部分，如果有）。
由于一些变量(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
))
都没有变化。
在tests6.ss里面有一个小的测试集，包括会通过的和不通过的测试。你需要确保你的编译器步骤至少能够通过这个测试集。
在tests6.ss里面有一个小的测试集，包括会通过的和不通过的测试。你需要确保你的编译器步骤至少能够通过这个测试集。