将Lisp编译为x86-64：基本函数

欢迎回到“编译Lisp”系列。上一次，我们完成了将其余常量作为标记指针立即数添加的操作。由于只有值(无法对其进行操作)没有多大用处，我们将添加一些原始的一元函数。

“原语”在这里指的是它们内置于编译器中，因此我们实际上不会编译对汇编过程调用的调用。这也称为编译器内部机制。“一元”表示函数只有一个参数，“函数”有点用词不当，因为这些函数不是可以作为变量传递的实值。您只能在调用中使用它们的非字面名称。

虽然我们仍未添加读取器/解析器，但可以想象其语法如下所示：

添加函数调用将需要添加一个新的编译器数据结构，并将其添加到AST中，但不是添加到编译后的代码中。编译后的代码仍然只知道直接类型。

INTEGER？，它接受一个对象，如果它是整数，则返回TRUE，否则返回FALSE。

Bool？，它接受一个对象，如果它是布尔值，则返回TRUE，否则返回FALSE。

函数add1、sub1和char/整数转换函数将是我们在编译代码中处理对象编码的第一次实际体验。太好了!。

NULL？、ZERO？、NOT、INTEGER？和BOOL？的实现。都是如此相似，所以我在这篇文章中只会转载其中的一到两个。其余内容可以在sets/code/lisp/compiling-unary.c上看到。

为了实现这些功能，我们还需要比mov和ret更多的指令。今天我们要补充的是：

因为shl、shr或和和的实现非常简单-就像mov一样，真的-我也将在POST中省略它们。Add、sub、cmp和setcc的实现更加有趣。

对，也称为cons单元格、二元组，可能还有其他东西，是Lisp的基本数据结构。至少是原来的Lisp。如今，我们也有像矢量这样的奇特结构。

对正好是另外两个对象的容器。出于历史原因和一致性原因，我将它们命名为Car和CDR，但是您可以随心所欲地称它们为Car和CDR。不管名称如何，它们都可以表示为如下所示的C结构：

这对于保存对象对很有用(考虑坐标、复数、…)。但它对制作链表也非常有用。Lisp中的链表由持有一个对象的汽车和持有另一个列表的CDR组成。最终，最后一个cdr为零，表示该列表的结束。看看这张方便的图表。

这表示列表(列表42 69 613)，该列表也可以表示为(con42(cons 69(Cons 613nil)。

我们将使用这些列表来表示Lisp的语法树，因此我们需要实现对来编译列表程序。

在之前的帖子中，我们在编译器和编译后的代码中以相同的方式实现了直接类型。我最初写这篇文章是做同样的事情：我自己手动布局对象偏移量，手动读取和写入mobject。其动机是让您熟悉编译代码中的内存布局，但最终结果是内容太多，速度太快。当我们开始在编译的代码中分配对时，我们将了解内存布局。

在编译器中，我们将使用C结构代替手动内存布局，这使得代码更容易阅读。不过，我们仍然会标记这些指针。

Const unsign int kPairTag=0x1；//0b001 const uword kHeapTagMask=((Uword)0x7)；//0b000...001 const uword kHeapPtrMask=~kHeapTagMask；//0b1111...1000。

这将添加Pair标签和一些遮罩。正如我们在前面的帖子中指出的那样，heap object标记都位于指针的最低三位。我们可以使用这个方便的实用函数来掩饰这些。

每当我们想要实际访问结构成员时，我们都需要使用它。说到结构成员，下面是Pair的定义：

下面是一些用于分配和操作Pair结构的函数，以隐藏实现细节：

ASTNode*AST_HEAP_ALLOC(unsign char tag，uword size){//初始化为0 uword address=(Uword)calloc(size，1)；return(ASTNode*)(address|tag)；}void AST_Pair_Set_car(ASTNode*node，ASTNode*car)；void AST_Pair_Set_Cdr(ASTNode*node，ASTNode*Cdr)；ASTNode*AST_NEW_Pair(ASTNode*CAR，ASTNode*Cdr){ASTNode*node=AST_heap_alloc(kPairTag，sizeof(Pair))；AST_Pair_Set_Car(节点，Car)；AST_Pair_Set_Cdr(节点，Cdr)；Return节点；}bool AST_is_Pair(ASTNode*节点){return((Uword)node&；kHeapTagMage。}Pair*AST_AS_Pair(ASTNode*node){Assert(AST_IS_Pair(Node))；return(Pair*)object_address(Node)；}ASTNode*AST_Pair_Car(ASTNode*node){return AST_AS_Pair(Node)->；car；}void AST_air_set_car(ASTNode*node，ASTNode*car){AST_AS_Pair(Node)->；car=car；}ASTNode*AST_Pair_Cdr(ASTNode*node){return AST_AS_Pair(Node)->；Cdr；}void AST_Pair_Set_Cdr(ASTNode*node，ASTNode*Cdr){AST_AS_Pair(Node)->；Cdr=Cdr；}。

首先，AST_HEAP_ALLOC非常有意地将其分配的内存清零，如果成员未初始化，则可能会读出在CAR或CDR中具有无效指针的Astruct成员。如果我们对其进行零初始化，默认情况下，成员指针表示对象0，不会发生任何崩溃。

其次，我们通过AST_AS_Pair不断移动ASTNode指针。此函数有两个目的：捕捉无效使用(通过断言对象确实是一对对象)和屏蔽低位。否则我们就得在每一次行动中单独做掩蔽。

第三，我抽象出了AST_HEAP_ALLOC，这样我们就不会在任何地方公开callocfunction。这允许我们稍后将分配器换成更智能的东西，比如凹凸分配器、竞技场分配器等等。

Void AST_HEAP_FREE(ASTNode*节点){if(！AST_IS_HEAP_OBJECT(Node)){return；}if(AST_IS_Pair(Node)){AST_heap_free(AST_Pair_Car(Node))；AST_heap_free(AST_Pair_Cdr(Node))；}free((void*)object_address(Node))；}。

这假设每个ASTNode*都拥有对其所有成员的引用。因此，不要借用引用在对象之间共享。如果您需要存储对某个对象的区域引用，请确保您拥有它。否则你会得到一张双人票。实际上，这应该不会对我们造成太大影响，因为每个程序都是一棵大树。

我们还需要符号！我的意思是，我们可以试着把我们需要的所有函数映射成整数，但那不是很有趣。谁想尝试和调试函数#67上的程序崩溃？不是我。因此，让我们添加一个可以表示事物名称的数据类型。

我之所以选择这种可变长度的对象表示，是因为它类似于我们将如何在汇编中分配符号，而C语言中的机制则不是那么简单。此结构指示符号的内存布局是紧跟内存中该字节数的长度字段。请注意，在结构中包含此变量数组是C99的一个特性。

如果您没有C99或不喜欢这个实现，也没问题。只需存储一个char*并为该字符串分配另一个对象。

您也可以选择根本不存储长度，而是使用NUL-Terminateit。这样做的优点是不需要处理可变长度的数组(它只是一个带标签的字符*)，但缺点是查找长度为O(N)。

Symbol*AST_AS_Symbol(ASTNode*node)；ASTNode*AST_NEW_Symbol(const char*str){word data_length=strlen(Str)+1；//对于NUL ASTNode*node=AST_heap_alloc(kSymbolTag，sizeof(Symbol)+data_length)；Symbol*s=AST_AS_Symbol(节点)；s->；length=data_length；memcpy(s-&

看看我们如何手动指定我们想要的尺寸。有点挑剔，但很管用。

是否存储NUL字节由您决定。如果不这样做，它会为每个字符串节省一个字节，但这会使调试器中打印出的字符串有点麻烦，因为您不能像对待普通的C字符串那样简单地对待它们。

一些Lisp实现使用符号表来确保使用等效C字符串值定位的符号返回相同的指针。这允许实现通过测试指针相等来测试符号相等。我认为我们可以牺牲一点内存和运行时速度来简化实现，所以我不打算这么做。

Bool AST_IS_Symbol(ASTNode*node){return((Uword)node&；kHeapTagMask)==kSymbolTag；}Symbol*AST_AS_Symbol(ASTNode*node){assert(AST_is_Symbol(Node))；return(Symbol*)object_address(Node)；}const char*AST_Symbol_CSTR(ASTNode*node){return(const char*)AST_as_Symbol(。}bool AST_Symbol_Matches(ASTNode*node，const char*CSTR){return strcmp(AST_Symbol_CSTR(Node)，CSTR)==0；}。

我们将函数调用表示为列表。这意味着以下程序：

这有点冗长。我们可以做一些公用事业来缩短长度。

ASTNode*list1(ASTNode*item0){return AST_new_Pair(item0，AST_nil())；}ASTNode*list2(ASTNode*item0，ASTNode*item1){return AST_new_Pair(item0，list1(Item1))；}ASTNode*new_unary_call(const char*name，ASTNode*arg){return list2(AST_。

呼。我们已经构建了所有这些数据结构和标记指针等等，但实际上还没有对它们做任何事情。让我们来看看编译器系列中的编译器部分吧！

首先，我们必须重新访问COMPILE_EXPR并添加另一个案例。如果我们在表达式中看到Pair值，则表示调用。

Int COMPILE_EXPR(Buffer*buf，ASTNode*节点){//立即成员的测试...。If(AST_IS_Pair(Node)){return Compile_Call(buf，AST_Pair_Car(Node)，AST_Pair_Cdr(Node))；}assert(0&；&；"；意外节点类型"；)；}。

我擅自将可调用函数和参数分开，以便Compile_call函数处理得更少。

我们现在只支持原始的一元函数调用，这意味着我们对编译器接受的内容有一个非常有限的模式。(添加1 5)isok。(Add1(Add1 5))可以。(Blargle 5)不是，因为这个blargle不在上面的列表中。((Foo)1)不是，因为被调用的东西不是无符号的。

INT COMPILE_CALL(Buffer*buf，ASTNode*Callable，ASTNode*args){assert(AST_Pair_CdR(Args)==AST_nil()&；&；"；只支持一元函数调用"；)；IF(AST_is_Symbol(Callable)){//打开此处的不同原语...。}Assert(0&；&；"；意外呼叫类型"；)；}。

COMPILE_CALL应该查看它是什么符号，并根据它是哪个符号发出不同的代码。不过，总体模式将如下所示：

如果我们看到Add1，则编译参数(如上所述)。然后，将1加到rax。不过请注意，我们并不是简单地添加文字1。我们添加了1的objectPresentation，即1<；<；2。想一想为什么！当你有一个想法时，点击脚注。2个。

如果您想知道下划线(_)函数是什么，我制作了一个宏来测试编译表达式的返回值，并在出现错误时返回。我们现在还没有任何非中止错误案例，但是我厌倦了一遍又一遍地编写if(result！=0)return result；。

请注意，没有运行时错误检查。我们的编译器将允许(Add1nil)滑过并损坏指针。这并不理想，但是我们现在还没有错误报告的工具。

Sub1类似于Add1，不同之处在于它使用SUB指令。您也可以只使用立即表示为-1的add。

整数->；字符不同。我们必须更改对象的标签。为此，我们将整数向左移位，然后将字符标记放到它上面，这是通过具有0b00标记(没有掩码)的整数来简化的。

其中，[括号]中的数字是97。下面是用来发出程序集的代码，该程序集就是这样做的：

If(AST_Symbol_Matches(Callable，"；Integer->；char"；)){_(Compile_expr(buf，operand1(Args)；emit_shl_reg_imm8(buf，krax，kCharShift-kIntegerShift)；emit_or_reg_imm8(buf，krax，kCharTag)；return 0；}。

请注意，我们不会以全量向左移动。我们只是根据差值进行移位，因为整数已经移位了两位。

Char->；整数类似，只是它只是一个shr。一旦将值向右移位，字符标记就会从末尾去掉，因此不需要将其屏蔽。

零？是我们的第一个原语，有令人兴奋的汇编指令~。我们可以使用cmp和setcc。基本思路是：

如果它们相等(这意味着结果为0)，则将al设置为1。

A1是RAX的较低8位的名称。还有AH(用于后8位，但不是最高位)、CL/CH等。

If(AST_Symbol_Matches(Callable，"；nil？"；)){_(build_expr(buf，operand1(Args)；emit_cmp_reg_imm32(buf，krax，object_nil())；emit_mov_reg_imm32(buf，krax，0)；emit_setcc_imm8(buf，kequence，kal)；Emit_or_reg_imm8(buf，krax，kBoolTag)；返回0；}。

CMP在标志寄存器中留下一个位设置(ZF)，然后设置CC进行检查。顺便说一句，setcc是在某些情况发生时设置寄存器的指令组的名称。我花了很长时间才意识到，因为人们通常写sete或setnz之类的东西。而CC的意思是“条件码”。

如果你想简化你的生活--我们明天要做很多比较--我们可以把它提取到一个函数中，该函数将rax与某个立即值进行比较，然后重构Compile_call来调用它。

Void编译_比较_imm32(buffer*buf，int32_t值){emit_cmp_reg_imm32(buf，krax，value)；emit_mov_reg_imm32(buf，krax，0)；emit_setcc_imm8(buf，kequence，kal)；emit_shl_reg_imm8(buf，krax，kBoolShift)；

我们还来看看cmp和setcc的实现，因为它们涉及一些有趣的指令编码。

事实证明，当与cmp进行比较的寄存器是rax时，cmp有一条最短路径。这意味着如果我们愿意，我们可以保存一(1)个完整的字节！

Void emit_cmp_reg_imm32(buffer*buf，Register Left，int32_t right){buffer_write8(buf，kRexPrefix)；if(Left==kRax){//优化：CMP rax，{imm32}可以编码为3D{imm32}或81//f8{imm32}。Buffer_write8(buf，0x3d)；}Else{buffer_write8(buf，0x81)；buffer_write8(buf，0xf8+Left)；}buffer_write32(buf，右)；}。

对于setcc，我们必须定义“部分寄存器”这一新概念，以便我们可以正确地对指令进行编码。我们不能重用寄存器，因为RAX有两个部分寄存器。因此，我们添加了一个PartialRegister。

Void emit_setcc_imm8(buffer*buf，dition cond，PartialRegister dst){buffer_write8(buf，0x0f)；buffer_write8(buf，0x90+cond)；buffer_write8(buf，0xc0+dst)；}。

再说一遍，这个编码不是我想出来的。这是英特尔的设计。

零？Primitive与nil几乎相同，我们可以重用Compile_Compare_imm32函数。

现在我们讲到整数？这是相似的，但又足够不同，我将重现下面的实现。我们只想查看最低的2位，而不是比较rax中的整数。这可以通过找出其他位，然后进行比较来完成。为此，我们发出AND FIRST并与标记进行比较。

可以稍微缩短实现时间，因为和设置了零标志。这意味着我们可以跳过CMP。但这只是一条指令，而且我很懒，所以我在重用现有的基础设施。

我在这里只包括几个测试，因为新的测试总共添加了283行，并且有点重复性。

Test COMPILE_UNARY_ADD1(Buffer*buf){ASTNode*node=new_unary_call("；Add1"；，AST_NEW_INTEGER(123))；int COMPILE_RESULT=COMPILE_Function(buf，node)；ASSERT_EQ(COMPILE_RESULT，0)；//mov rax，imm(123)；add rax，imm(1)；预期RET字节[]={0x48，0xc7，0xc0，0xec，0x01，0x00，0x00，0x48，0x05，0x04，0x00，0x00，0x00，0xc3}；expect_equals_bytes(buf，期望)；buffer_make_Executable(Buf)；uword result=TESTING_EXECUTE_EXPR(BUF)；ASSERT_EQ(RESULT，OBJECT。

测试COMPILE_UNARY_ADD1_NESTED(BUFFER*buf){ASTNode*node=new_unary_call("；Add1"；，new_unary_call("；Add1"；，AST_NEW_INTEGER(123)；INT COMPILE_RESULT=COMPILE_Function(buf，node)；ASSERT_EQ(COMPILE_RESULT，0)；//mov rax，imm(123)；add rax，imm。预计返回字节[]={0x48，0xc7，0xc0，0xec，0x01，0x00，0x00，0x48，0x05，0x04，0x00，0x00，0x00，0x00，0x48，0x05，0x04，0x00，0x00，0xc3}；EXPECT_EQUALS_BYTES(buf，期望)；buffer_make_executable(Buf)；uUF。AST_HEAP_FREE(节点)；PASS()；}。

测试compile_unary_booleanp_with_non_boolean_returns_false(BUFFER*buf){ASTNode*NODE=NEW_UNARY_CALL("；Boolean？"；，AST_NEW_INTEGER(5))；INT COMPILE_RESULT=COMPILE_Function(BUF，NODE)；ASSERT_EQ(COMPILE_RESULT，0)；//0：48 c7 c0 14 00 00 00 mov rax，0x14//7：48 83 e0 3f and rax，0x3f//b：48 3D 1f 00 00 00 CMP rax，0x0000001f//11：48 c7 c0 00 00 00 mov rax，0x0//18：0f 94 c0设置//1b：48 c1 e0 07 shl rax，0x7//1f：48 83 c0。0xe0，0x3f，0x48，0x3d，0x1f，0x00，0x00，0x00，0x48，0xc7，0xc0，0x00，0x00，0x00，0x00，0x0f，0x94，0xc0，0x48，0xc1，0xe0，0x07，0x48，0x83，0xc8，0x1f}；EXPECT_EQUALS_BYTES(buf，期望)；Buffer_make_Executable(Buf)；uword result=TESTING_EXECUTE_EXPR(Buf)；ASSERT_EQ(RESULT，OBJECT_FALSE())；AST_HEAP_FREE(节点)；PASS()；}。

我要从defuse.ca上搞到花哨的拆卸。我把它加进去是因为它让我以后更容易阅读和推理考试。您只需确保测试中的文本和二进制表示不会不同步，因为这可能会使…非常混乱。

不管怎样，今天的节目到此为止。把你对名单的评论发过来吧！下一次，二进制原语。

关于如何称呼这两个物体，存在着长期的争议。最初的Lisp机器(IBM704)有一个特殊的硬件布局，这导致了CAR和CDR两个名称的创建。现在没有人再用这种硬件了，所以这些名字都是历史名称。有些人称它们为first/fst和Second/snd。其他人称它们为Head/HD和Tail/tl。有些人则有不同的想法。--↩。

如果您说“保留标记”或“加1会使其成为一对”或其他变体，那么您是正确的！否则，我建议回到前几个帖子的图表，然后在一张纸上手写几个数字的二进制表示法。-↩