将Lisp编译为x86-64：带标签的过程调用

欢迎回到编译Lisp系列。上次，我们学习了智能指令编码。这一次，我们将使用这些知识来编译过程调用。

Lisp中常用的函数表达式是lambda--一个可以接受参数和关闭变量的匿名函数。过程调用不是这样的。它们是更简单的构造，只接受参数并返回值。

我们首先添加过程调用作为完全闭包支持的垫脚石，这将帮助我们建立某种内部调用约定，并在事情变得太复杂之前弄清楚堆栈操作。

(标签((add(code(X Y)(+x y)(sub(code(X Y)(-x y)(labelcall sub 4(Labelcall Add 12)；=>；1。

(Label((阶乘(code(X)(if(<；x2)1(*x(labelcall阶乘(-x 1)(labelcall阶乘5))；=>；120。

这些代码片段相当平淡无奇，但它们展示了我们添加的一些新功能，例如：

Ghuloum没有解释他为什么这样做，但我想，之所以选择标签Form而不是允许多个独立的顶级绑定，是因为它更容易解析和遍历。

为了编译程序，我们将遍历标签中的每个绑定。对于每个绑定，我们将为每个代码对象生成代码。

编译代码对象需要为它们的参数创建一个环境。我们稍后将建立一个调用约定，以便我们的编译器知道在哪里可以找到参数。

然后，一旦我们发出了绑定的所有代码，我们将编译正文。正文可以(但不是必须)包含labelcall表达式。

为了编译labelcall表达式，我们将编译提供的所有参数，将它们保存在堆栈上的连续位置，然后发出CALL指令。

当所有这些部分放在一起时，得到的机器代码将如下所示：

您可以看到，所有代码对象都将按顺序编译，紧随其后的是Labels窗体的正文。

因为我还没有想出如何在生成代码的开头以外的其他地方开始执行，而且我没有将生成的代码存储在任何中间缓冲区中，并且因为我们事先不知道任何代码的大小，所以我做了这个时髦的事情，我向主体代码发出一个JMP。

我们不会使用System V AMD64ABI。该调用约定要求参数首先在某些寄存器中传递，然后在堆栈上传递。相反，我们将在堆栈上传递所有参数。

这使我们的代码变得更简单，但这也意味着在以后的某个时刻，我们将不得不添加不同类型的调用约定，以便我们可以调用外部函数(如printf、或exit等)。这些函数期望它们的参数在寄存器中。我们以后再担心这件事。

如果我们借用并改编Ghuloum教程中的优秀图表，这意味着就在我们进行过程调用之前，我们的堆栈将如下所示：

低地址|...|+-++|...|+-++->；|arg3|RSP-56输出|+-+参数||arg2|RSP-48|+。|arg1|rsp-40+-++||rsp-32+->；|local3|rsp-24|+-+本地||local2|rsp-16|+-++->；|local1|RSP-8+-+base|返回点|RSP高地址。

您可以在[RSP]处看到第一个返回点。这是当前函数的调用方放置的返回点。

上面是我们用let声明的任何局部变量，或者可能是来自某些计算的中间值。

其上方是为第二个返回点预留的空白区域。这是将要调用的函数的返回点。CALL指令将在评估所有参数后填写。

返回点上方是所有传出参数。对于被调用的过程，它们将显示为本地人。

CALL指令递减RSP，然后写入[RSP]。这意味着如果我们只是发出一个调用，第一个本地代码将被覆盖。不好。更糟糕的是，堆栈的布局方式将意味着本地将看起来像参数。

为了解决这个问题，我们需要首先调整RSP以指向最后一个本地。这样，减量会将其移到本地地址之下，返回地址将位于本地地址和参数之间。

在CALL指令之后，堆栈看起来会有所不同。除了RSP，实际上什么都不会改变。对RSP的此更改意味着被调用方具有不同的视图：

低地址|...|+-++|...|+-|arg3|RSP-24位于|+-+args||arg2|RSP-16|+。|arg1|RSP-8+-+BASE|返回点|RSP+-+|~|+-~|+-~|高位地址。

返回点下方空白处的彩色空白表示堆栈上的值是“隐藏”的，因为它们高于(高于)[RSP]的地址。被调用的函数将无法访问这些值。

如果被调用的函数想要使用其参数之一，它可以将其从其指定位置移出堆栈。

这个调用惯例的一个不幸后果是Valgrind不理解它。Valgrind无法理解调用方已专门将数据放在堆栈上以供被调用方读取，并认为这是未初始化值的移动/跳转。这意味着我们现在在这些标签调用测试中会遇到一些错误。

最后，当函数返回时，ret指令将从堆栈中弹出返回指针并跳转到堆栈。这将把我们带回到之前的呼叫框架。

就是这样！我还没有找到一个好的工具，可以让我在程序执行时可视化堆栈。Gdb可能有一个隐藏在某个没有文档的地方的模式，它就是这样做的。卡特有点喜欢，但我真的不太明白它是怎么挑剔的。也许有一天卡地克的x86-64Mu叉会做到这一点。

为了使这组更改有意义，我将自上而下地逐一解释所有部分。

首先，我们将查看新的和改进的COMPILE_ENTRY，它已经进行了更新以处理标签表单。这将对代码体执行常见的Lisp entrypointsetup、一些检查和前面提到的JMP。

然后，我们将实际了解一下如何编译标签。这意味着逐个检查绑定并编译它们的代码对象。

然后，我们将了解编译代码对象意味着什么。提示：它很像LET。

最后，我们将在编译Label表单的正文时将它们全部捆绑在一起。

这段代码的大部分都在检查。过去只编译表达式的内容现在验证了，在将其放入其组成部分(绑定和正文)之前，我们传入的内容至少模糊地看起来像是格式良好的标签表单。

Int COMPILE_ENTRY(buffer*buf，ASTNode*node){buffer_write_arr(buf，kEntryPrologue，sizeof kEntryPrologue)；Assert(AST_IS_Pair(Node)&；&；#34；程序必须有标签)；//假定它(标签...)。ASTNode*labels_sym=AST_Pair_Car(Node)；Assert(AST_is_Symbol(Labels_Sym)&；&；&34；程序必须有标签&34；)；Assert(AST_Symbol_Matches(Labels_sym，&34；Labels&34；)&；&；&34；程序必须有标签"；)；//跳到正文单词body_pos=emit_jmp(buf，kLabelPlaceholder)；ASTNode*args=AST_Pair_Cdr(节点)；ASTNode*bindings=operand1(Args)；Assert(AST_IS_Pair(绑定)||AST_is_nil(绑定))；ASTNode*body=operand2(Args)；_(编译_标签(buf，绑定，body，/*labels=*/null，body_pos))；buffer_write_arr(buf，kFunctionEpilogue，sizeof kFunctionEpilogue)；return 0；}。

COMPILE_ENTRY分派给COMPILE_LABEL以迭代所有标签。COMPILE_LABESTS是一个递归函数，它在其参数中跟踪到目前为止的所有标签，所以我们从一个空的标签环境开始。

我们还将JMP的位置传递给它，这样在它编译正文之前，它就可以修补跳转目标。

在COMPILE_LABEL中，我们首先有一个基本情况：如果没有标签，我们应该只发出主体。

Int Compile_Labels(Buffer*buf，ASTNode*bindings，ASTNode*Body，Env*Labels，Word Body_pos){if(AST_is_nil(Bindings)){emit_backpatch_imm32(buf，body_pos)；//基本情况：无绑定。编译BODY_(COMPILE_EXPR(buf，body，/*STACK_INDEX=*/-kWordSize，/*varenv=*/null，labels))；返回0；}//...}。

我们还将跳跃位置修补到要发射标签主体的位置。在没有标签的基本情况下，跳转有点没用，因为没有要跳过的中间代码，但这没什么。在大多数情况下，都会有绑定。

我们传入一个空的varenv，因为我们一路上没有积累任何当地人；只有标签。出于同样的原因，我们给出了-kWordSize-第一个槽的STACK_INDEX。

如果我们有标签，另一方面，我们应该处理第一个标签，即：

Int编译_Labels(Buffer*buf，ASTNode*绑定，ASTNode*Body，Env*Labels，Word Body_pos){//....。Assert(AST_IS_Pair(绑定))；//获取下一个绑定ASTNode*binding=AST_Pair_CAR(绑定)；ASTNode*name=AST_Pair_CAR(绑定)；Assert(AST_IS_Symbol(Name))；ASTNode*binding_code=AST_Pair_Car(AST_Pair_Cdr(绑定))；word function_location=buffer_len(Buf)；//将名称绑定到指令流环境条目=env_bind(AST_Symbol_CSTR(Name)，function_location，labels)；//编译绑定函数_(Compile_code(buf，binding_code，&；entry))；_(Compile_Labels(buf，AST_Pair_Cdr(Bindings)，body，&；entry，body_pos))；返回0；}。

重要的是要注意，我们在编译代码对象之前是绑定的，并且我们在编译之前使代码位置可用！这意味着代码对象可以引用它们自己，甚至可以递归地调用它们自己。

由于我们随后将绑定传递到标签以进行递归调用，因此标签也可以访问在它们之前定义所有标签。

我将其分成两个函数：一个是分离代码对象的帮助器(我不想在标签中这样做，因为我认为这样会使主题变得混乱)，另一个递归函数负责将参数放入环境中。

因此COMPILE_CODE只是将(code(x y z...)。Body)转换为形式参数和Body。由于Compile_code_impl将需要递归地构建有关STACK_INDEX和varenv的信息，因此我们对其进行补充。

Int编译_code(buffer*buf，ASTNode*code，Env*labels){ASSERT(AST_IS_Pair(Code))；ASTNode*code_sym=AST_Pair_Car(Code)；Assert(AST_IS_Symbol(Code_Sym))；Assert(AST_Symbol_Matches(code_sym，"；code"；))；ASTNode*args=AST_Pair_Cdr(Code)；ASTNode*formals=operand1(Args)；ASTNode*code_body=operand2(Args)；return CODE_IMPL(buf，formals，code_body，/*STACK_INDEX=*/-kWordSize，/*varenv=*/null，labels)；}。

我说这会像是出租。我的意思是，与letbody一样，代码对象也有“局部参数”--形式参数。根据我们的调用约定，我们必须将参数的名称绑定到连续的堆栈位置。

在基本情况下，我们没有任何形式，所以我们编译正文：

Int build_code_impl(buffer*buf，ASTNode*formals，ASTNode*body，word stack_index，env*varenv，env*labels){if(AST_is_nil(Formals)){_(build_expr(buf，body，stack_index，varenv，labels))；buffer_write_arr(buf，kFunctionEpilogue，sizeof kFunctionEpilogue)；return 0；}//...}。

我们也发出这个函数结语，现在它就是ret。我去掉了PUSH RBP/MOV RBP，RSP/POP RBP舞蹈，因为我们改为只使用RSP。我在之前的指令编码间歇帖子中提到了这一点。

在我们至少有一个形式的情况下，我们将名称绑定到堆栈位置，然后继续我们的快乐之路。

Int CODE_IMPL(Buffer*buf，ASTNode*Forals，ASTNode*Body，WORD STACK_INDEX，Env*varenv，Env*Labels){//...。Assert(AST_IS_Pair(Formal))；ASTNode*name=AST_Pair_Car(Formal)；Assert(AST_IS_Symbol(Name))；Env entry=Env_Bind(AST_Symbol_CSTR(Name)，stack_index，varenv)；return Compile_code_impl(buf，AST_air_Cdr(Formals)，body，stack_index-kWordSize，&；entry，labels)；}。

如果我们不能调用这些程序，它们又有什么用呢？让我们了解一下如何编译过程调用。

调用过程的代码必须按照被调用过程期望的方式将参数和返回地址精确地放在堆栈上。

把这份合同做好可能会很棘手。我花了几个小时让它不会坠毁。然后，即使它没有崩溃，它也返回了错误数据。原来我是不小心重写了寄信人的地址，而是回到了一个陌生的地方。

制作跟踪RSP和堆栈更改的手工图表确实有助于理解调用约定错误。

我们将从将更多代码转储到COMPILE_CALL开始。此代码将查找形式为(labelcall name...)的内容。

ARG_STACK_INDEX，这是堆栈上建议使用ARG的第一个位置。因为我们为返回地址跳过了一个空格，所以这比当前(可用)槽索引多一个空格。

RSP_ADJUST，这是我们需要调整RSP的量。如果没有来自let的局部变量或来自过程调用的传入参数，则该值将为0。加上本地人和/或争论，这将是那些人占用的空间总量。

INT COMPILE_CALL(Buffer*buf，ASTNode*Callable，ASTNode*args，WORD STACK_INDEX，Env*varenv，Env*Labels){//...。IF(AST_Symbol_Matches(Callable，"；labelcall"；)){ASTNode*Label=Operand1(Args)；Assert(AST_is_Symbol(Label))；ASTNode*call_args=AST_Pair_Cdr(Args)；//跳过堆栈上的空格以放置返回地址字arg_stack_index=stack_index-kWordSize；//我们输入COMPILE_CALL，其中STACK_INDEX指向堆栈上的下一个//可用位置。添加kWordSize(STACK_INDEX为负)//这样它只是本地变量N的倍数，而不是N+1.word RSP_ADJUST=STACK_INDEX+kWordSize；返回COMPILE_Labelcall(buf，label，call_args，arg_stack_index，varenv，labels，rsp_adjust)；}//...}。

COMPILE_LABELCALL是我们软编写的有趣的递归函数之一。它的工作是编译所有参数，并将它们的结果存储在连续的堆栈位置。

在基本情况下，它没有要编译的参数。它应该只是调整堆栈指针，调用过程，调整回堆栈指针，然后返回。

Void emit_rsp_adjust(缓冲区*buf，字调整){if(adjust<；0){emit_sub_reg_imm32(buf，krsp，-adjut)；}ELSE if(adjust>；0){emit_add_reg_imm32(buf，krsp，adjust)；}}int Compile_labelcall(Buffer*buf，ASTNode*Callable，ASTNode*args，word stack_index，env*varenv，env*labels，word RSP_ADJUST){if(AST_is_nil(Args)){word code_address；if(！Env_find(labels，AST_Symbol_CSTR(Callable)，&；CODE_ADDRESS)){return-1；}//保存本地变量emit_rsp_adjust(buf，rsp_adjust)；emit_call_imm32(buf，code_address)；//取消保存本地变量emit_rsp_adjust(buf，-rsp_adjust)；return 0；}//...}。

Emit_rsp_adjust是一个方便的函数，它需要一些堆栈调整增量。如果它是负的，它将发出SUB指令。如果是正数，则为ADD。否则，它什么也做不了。

Int编译_labelcall(Buffer*buf，ASTNode*Callable，ASTNode*args，WORD STACK_INDEX，Env*varenv，Env*Labels，Word RSP_ADJUST){//...。Assert(AST_IS_Pair(Args))；ASTNode*arg=AST_Pair_Car(Args)；_(COMPILE_EXPR(buf，arg，stack_index，varenv，labels))；emit_store_reg_direct(buf，ind(krsp，stack_index)，krax)；return Compile_labelcall(buf，callable，AST_air_cdr(Args)，stack_index-kWordSize，varenv，labels，rsp_adjut)；}。

好了，这还不算太糟，不是吗？我是说，如果你第一次就做对了。我当然没有。事实上，我在几个月前就放弃了这个编译器的第一个版本，因为我不能正确地调用过程。有了这篇文章，我现在已经度过了那个特别棘手的里程碑！

我不会在这篇文章中包含所有的测试，但是编译过程中提供了完整的测试。这是其中的一些。

Test CODE_CODE_WITH_TWO_PARAMS(Buffer*buf){ASTNode*node=Reader_Read("；(code(X Y)(+x y))"；)；int COMPILE_RESULT=COMPILE_CODE(buf，node，/*labels=*/null)；ASSERT_EQ(CODE_RESULT，0)；//clang-format off byte预期[]={//mov rax，[rsp-16]0x48，0x8b，0x44，0x24，0xf0，//mov[rsp-24]，rax 0x48，0x89，0x44，0x24，0x24，0xe8，//mov rax，[rsp-8]0x48，0x8b，0x44，0x24，0xf8，//add rax，[rsp-24]0x48，0x03，0x44，0x24，0xe8，/ret/0xc3，}；//clang-format on expect_equals_bytes(buf，expred)；AST_HEAP_FREE(节点)；PASS()；}。

正如预期的那样，这采用[RSP-8]中的第一个参数和[RSP-16]中的第二个参数，将临时参数存储在[RSP-24]中。这个测试不测试执行，因为我不想编写测试基础设施正式地设置过程调用。

Test COMPILE_LABEL_WITH_ONE_LABEL(Buffer*buf){ASTNode*node=Reader_Read("；(labels((const(code()5)1)"；)；int COMPILE_RESULT=COMPILE_ENTRY(buf，node)；ASSERT_EQ(COMPILE_RESULT，0)；//clang-format off byte预期[]={//mov rsi，RDI 0x48，0x89，0xfe，//jmp 0x08 0xe9，0x08，0x00，0x00，0x00，//mov rax，编译(5)0x48，0xc7，0xc0，0x14，0x00，0x00，0x00，//ret 0xc3，//mov rax，0x2 0x48，0xc7，0xc0，0x04，0x00，0x00，0x00，//ret 0xc3，}；//clang-format on expect_equals_bytes(buf，expred)；buffer_make_executable(Buf)；uword result=TESTING_EXECUTE_ENTRY(buf，/*heap=*/null)；ASSERT_EQ_FMT(OBJECT_ENCODE_INTEGER(1)，RESULT，"；0x%lx"；)；AST_HEAP_FREE(节点)；PASS()；}。

这将测试是否跳过编译的过程主体(check！)、发出编译的过程主体(check！)和发出标签窗体的主体(check！)。这一次我们可以执行。

Test build_labelcall_with_one_param(buffer*buf){ASTNode*node=Reader_Read("；(labels((id(code(X)x)(Labelcall Id 5))"；)；int Compile_Result=Compile_Entry(buf，node)；assert_EQ(Compile_Result，0)；//clang-要求的格式关闭字节[]={//mov rsi，RDI 0x48，0x89，0xfe，//jmp 0x06 0xe9，0x06，0x00，0x00，0x00，//mov rax，[rsp-8]0x48，0x8b，0x44，0x24，0xf8，//ret 0xc3，//mov rax，编译(5)0x48，0xc7，0xc0，0x14，0x00，0x00，0x00，//mov[RSP-16]，rax 0x48，0x89，0xf8，//ret 0xc3，//mov rax，编译(5)0x48，0xc7，0xc0，0x14，0x00，0x00，0x00，//mov[RSP-16]。0x24，0xf0，//调用`id`0xe8，0xe9，0xff，0xff，0xff，//ret 0xc3，}；//clang-Expect_EQUALS_BYTES上的格式(buf，期望。

.