[swarthmore cs75] Compiler 4 – Diamondback
[swarthmore cs75] Compiler 4 – Diamondback
课程回顾
Swarthmore学院16年开的编译系统课，总共10次大作业。本随笔记录了相关的课堂笔记以及第6次大作业。
-
函数声明
增加函数声明、函数调用的抽象语法；在转换成anf之前还要检查函数声明和调用是否正确。
well_formed函数分别检查Program中的的函数声明列表ds和main是否有错误。
well_formed_decl函数还需要检查函数体是否正确（参考下图右边第一个递归的例子）。
well_formed_expr函数，检查expr中调用的函数是否已经定义，接着递归调用well_formed_expr检查参数（参考下图右边第二例子）。
anf_p将Program转换为anf文法（参考下图fact函数）：首先使用anf处理main，接下来用anf_d处理函数声明，anf_d中函数体需要递归处理。
acompile_p为Program生成汇编代码：acompile_decl为函数声明生成汇编代码，acompile_aexpr为main生成汇编代码。
acompile_cexpr为函数调用生成汇编代码。
acompile_decl为函数体生成汇编代码（目前只支持一个参数），包括初始化（如提前分配空间）、递归处理函数体等。
下图为函数调用时栈帧的情况，绿色是Caller的职责，红色是Callee的职责（保存old ebp，申请空间，恢复esp/ebp等）。 -
尾递归
普通递归vs.尾递归：普通递归的栈空间使用情况先是达到一个峰值，然后逐渐减小；而尾递归的空间复杂度始终为O(1)。
tail position vs. non tail position：为了能够使用尾递归优化汇编代码，需要确定哪些位置是tail position（一旦该位置表达式求值完成，整个表达式就完成了求值）。
在递归判断tail position的时候，需要注意如果整个表达式是另一个表达式的子表达式，而且这个子表达式的位置不是tail position的时候，这个子表达式的位置则不是tail position。
如：let ans = if … else … in k(ans + x)，这个整个if表达式的位置就不能算是tail position。
如：let ans = (let x = 10 in x) in ans
Callee的职责：
1. 使用push ebp存储old ebp。
2. 使用mov ebp, esp更新ebp。
3. 为local vars提前分配存储空间。
Caller的职责：
1. 将参数的值[esp-4]移动到eax中。
2. 使用eax覆盖原来的参数[ebp+8]。
3. 将esp指向old ebp。
4. pop ebp，恢复ebp并将esp+4（指向返回地址）。
5. 使用jmp跳转到f函数体（使用call会将返回地址再次压栈）。
tail call optimization & proper tail calls
两个参数的情况：如下图，z存储在[ebp+12]，w存储在[ebp+8]，如果尾递归调用f(z, y)，需要将这两个位置的值进行更新。
多个参数的情况：
使用c-stack convention：调用者负责将参数格式，参数，返回指针压入栈中。
使用functional language convention：调用者压入返回指针；被调用者负责管理参数。 -
α-renaming
为了能够使转换成anf的变量名不产生混淆，需要对变量进行重命名。
源代码：let x = 10, y = (let x = 5 in x) + x in yANF：
let x = 10 in let x = 5 in y = x + x in y实现α-renaming：
编程作业
撰写中