将Lisp编译为x86-64：堆分配

欢迎回到“编译Lisp”系列。上次我们添加了对IF表达式的支持。这一次，我们将添加对基本堆分配的支持。

堆分配有几种形式，但我们现在关心的是cons原语。与编译器中的AST_NEW_Pair非常类似，consout应该：

一旦我们有了那一对，我们就可以查看它的数据了。这意味着我们现在可能还应该实现CAR和CDR原始函数。

为了生成打包和拆分对的代码，我们可能应该知道它们在内存中是如何布局的。

Pair包含两个并排的元素-有点像一个两个元素的数组，第一个元素(Pair[0])是汽车，第二个元素(Pair[1])是CDR。

未标记的指针指向第一个元素的地址，而标记指针有一些额外信息(kPairTag==1)，我们需要获取ridof来检查这些元素。如果不这样做，我们将尝试从指针后面的一个字节开始读取，也就是在车中间的某个地方。这会给我们提供错误的数据。

为了让事情更具体，假设我们的配对分配为0x10000。我们的汽车位于*(0x10000)(使用C表示法)，CDR位于*(0x10000+kWordSize)。本例中的标记指针为0x10001，kWordSize为8。

无论何时需要新对象，我们都可以调用malloc。这带来了一系列问题，特别是malloc做了很多我们实际上并不需要的内部记账工作，并且没有好的方法来跟踪我们分配了哪些内存并且需要垃圾收集(我们稍后会处理)。它还有一个不幸的属性，需要C函数调用基础设施，这是我们还没有的。

相反，我们要做的是在进程开始时分配一大块内存。那将是我们的一大堆。然后，为了跟踪到目前为止我们已经使用了哪些内存，我们将在每次分配时撞击指针。因此，在我们分配一对之前，堆看起来是这样的：

空单元格不一定是空的，但它们是未使用的，并且它们与数据有关。

注意堆指针是如何移动到2个字上的，而成对指针是返回的cons单元格。虽然我们将标记成对指针，但为了在图中清晰起见，我将其指向汽车的开头。

为了首先获得这一大块内存，我们将让外部C代码(现在，这是我们的测试处理程序)调用malloc。

您可能在想，当内存用完时，我们该怎么办。在本系列的某个时刻，我们将拥有一个垃圾收集器，它可以为我们回收一些空间。不过，现在我们要做的就是…。没什么。没错，我们甚至不会引发某种“内存不足”错误。请记住，我们还没有错误报告功能！相反，我们将使用Valgrind和AddressSaniizer等工具来确保没有超出分配的缓冲区。

为了快速方便地从那么大的缓冲区进行分配，我们将堆指针保存在一个寄存器中。我们的编译器发出使用RBP、RSP和RIX的指令，所以我们必须选择另一个指令。Ghuloum使用RSI，所以我们也将使用它。

为了首先获得RSI中的堆指针，我们必须从外部C代码捕获它。为此，我们将通过修改函数prologue向入口点添加一个参数。

还记得JitFunction吗？这就是C代码用来理解如何调用我们的mmap-ed函数的地方。我们需要先修改这个。

现在需要接受一个新参数-指向堆的指针，这意味着我们的kFunctionPrologue需要在调用约定中的第一个参数寄存器中获取该参数，并将其存储在安全的地方。这个寄存器是RDI，所以我们可以发出一个mov rsi，rdi来存储我们的堆指针。

现在，对于Lisp入口点的生存期，我们可以使用名称RSI来引用堆并相应地修改它。我们将保持一个内部约定，即RSI始终指向下一个可用的内存块。

想要分配内存吗？将当前堆指针复制到rax中，并使用add rsi，allocationSize更新堆指针。我们需要添加一个用于在寄存器之间移动数据的新结构。老实说，我有点惊讶我们现在还不需要那个。

想把你的车和CDR放在你的新车里吗？分别写入rax的偏移量0和kWordSize。我们将重用我们的间接存储指令。

要标记您的指针吗？添加rax，标签或或rax，标签。这两条指令是等价的，因为堆对象中的所有三个可标记位都将为零。

这种单词对齐现在很容易维护，因为所有对的大小都是16，是8的倍数。稍后，当我们添加符号、字符串和其他包含非对象数据的数据类型时，我们必须在分配之间插入填充以保持对齐不变。

一旦我们分配了对，除非我们也能戳到它们的元素，否则就没有什么用了。

要实现CAR，我们将从指针中删除标记，并从寄存器指向的内存中读取：MOV rax，[ptr+car-tag]。你也可以用subrax，tag，然后是mov来做这件事。

既然我们已经想好了问题的抽象解决方案，我们就应该编写一些代码。

INT COMPILE_CALL(Buffer*buf，ASTNode*Callable，ASTNode*args，WORD STACK_INDEX，Env*varenv){if(AST_IS_Symbol(Callable)){//...。If(AST_Symbol_Matches(Callable，"；cons"；)){return build_cons(buf，/*car=*/operand1(Args)，/*cdr=*/operand2(Args)，stack_index，varenv)；}//...}}。

我们真的不需要为cons添加一个全新的函数，因为我们没有对参数或任何东西进行结构递归，但是Compile_callust变得越来越大，这有助于使它变得更小。

COMPILE_CONS与我上面描述的几乎完全相同。我将RSI拉到了kHeapPointer中，这样我们以后就可以在需要时更改它。

Const寄存器kHeapPointer=kRsi；int编译_cons(buffer*buf，ASTNode*car，ASTNode*cdr，int stack_index，env*varenv){//编译并存储car_(build_expr(buf，car，stack_index，varenv))；emit_store_reg_direct(buf，/*dst=*/ind(kHeapPointer，kCarOffset)，/*src=*/kRax)；//编译并存储Cdr_(Compile_expr(buf，cdr，stack_index，varenv))；emit_store_reg_direct(buf，/*dst=*/ind(kHeapPointer，kCdrOffset)，/*src=*/kRax)；//在rax中存储带标签的指针emit_mov_reg_reg(buf，/*dst=*/krax，/*src=*/kHeapPointer)；emit_or_reg_imm8(buf，/*dst=*/kRax，kPairTag)；//撞击堆指针emit_add_reg_imm32(buf，/*dst=*/kHeapPointer，kPairSize)；返回0；}。

请注意，即使我们一个接一个地编译两个表达式，我们也不需要转储STACK_INDEX或任何东西。这是因为我们不是在堆栈上存储结果，而是在对中存储结果。

Void emit_mov_reg_reg(buffer*buf，Register dst，Register src){buffer_write8(buf，kRexPrefix)；buffer_write8(buf，0x89)；buffer_write8(buf，0xc0+src*8+dst)；}。

好的，这就是缺点。让我们实现CAR和CDR。这些都是非常简短的实现：

INT COMPILE_CALL(Buffer*buf，ASTNode*Callable，ASTNode*args，WORD STACK_INDEX，Env*varenv){if(AST_IS_Symbol(Callable)){//...。If(AST_Symbol_Matches(Callable，"；car"；)){_(COMPILE_EXPR(buf，operand1(Args)，STACK_INDEX，varenv))；emit_load_reg_direct(buf，/*dst=*/kRax，/*src=*/Ind(kRax，kCarOffset-kPairTag))；return 0；}if(AST_Symbol_Matches(Callable，"；Cdr"；)){_(Compile_expr(buf，operand1(Args)，stack_index，varenv))；emit_load_reg_direct(buf，/*dst=*/kRax，/*src=*/ind(kRax，kCdrOffset-kPairTag))；返回0；}//...}}。

就这样。这就是整个实现！现在我们有了这些构建块，添加新功能并不是那么困难，这是一件很好的事情。

我已经为这个实现编写了几个测试。为了使测试变得轻松，我还添加了一种新类型的测试工具，它可以传递测试一个缓冲区和一个堆。我将其命名为-等待它-runheap_test。

不管怎样，这是一个我们可以分配对的测试。为了全面测试它，我添加了一些用于检查对象内部的帮助器：OBJECT_Pair_Car和OBJECT_Pair_Cdr。请注意，这些函数可能与相应的AST函数相同，但不一定相同。我认为，C编译器可以假设对结构元素重新排序。

Test build_cons(buffer*buf，uword*heap){ASTNode*node=Reader_Read("；(Cons 1 2)"；)；int Compile_Result=COMPILE_ENTRY(buf，node)；ASSERT_EQ(COMPILE_RESULT，0)；//clang-要求的格式关闭字节[]={//mov rax，0x2 0x48，0xc7，0xc0，0x04，0x00，0x00，0x00，0x00，//mov[rsi]，rax 0x48，0x89，0x46，0x00，//mov rax，0x4 0x48，0xc7，0xc0，0x08，0x00，0x00，0x00，//mov[rsi+kWordSize]，rax 0x48，0x89，0x46，0x08，//mov rax，RSI 0x48，0x89，0xf0，//rax，0x00，0x00，0x00，//mov[rsi+kWordSize]，rax 0x48，0x89，0x08，//mov rax，RSI 0x48，0x89，0xf0，//rax。KPairTag 0x48，0x83，0xc8，0x01，//添加RSI，2*kWordSize 0x48，0x81，0xc6，0x10，0x00，0x00，0x00，}；//clang-format on Expect_ENTRY_CONTAINS_CODE(BUF，EXPECTED)；BUFFER_MAKE_EXECUTABLE(BUF)；uWORD RESULT=TESTING_EXECUTE_ENTRY(BUF，HEAP)；ASSERT(OBJECT_IS_Pair(RESULT))；ASSERT_EQ_FMT(OBJECT_ENCODE_INTEGER(1)，OBJECT_Pair_CAR(RESULT)，"；)；ASSERT_EQ_FMT(OBJECT_ENCODE_INTEGER(2)，OBJECT_Pair_CDR(RESULT)，"；0x%lx"；)；AST_HEAP_FREE(节点)；PASS()；}。

这是一个阅读一对汽车的测试。CDR的测试是如此相似，我不会在这里包括它。

Test COMPILE_CAR(buffer*buf，uword*heap){ASTNode*node=Reader_Read("；(CAR(Cons 1 2))"；)；int COMPILE_RESULT=COMPILE_ENTRY(buf，node)；ASSERT_EQ(COMPILE_RESULT，0)；//clang-要求的格式关闭字节[]={//mov rax，0x2 0x48，0xc7，0xc0，0x04，0x00，0x00，0x00，0x00，//mov[rsi]，rax 0x48，0x89，0x46，0x00，//mov rax，0x4 0x48，0xc7，0xc0，0x08，0x00，0x00，0x00，//mov[rsi+kWordSize]，rax 0x48，0x89，0x46，0x08，//mov rax，RSI 0x48，0x89，0xf0，//rax，0x00，0x00，0x00，//mov[rsi+kWordSize]，rax 0x48，0x89，0x08，//mov rax，RSI 0x48，0x89，0xf0，//rax。KPairTag 0x48，0x83，0xc8，0x01，//添加RSI，2*kWordSize 0x48，0x81，0xc6，0x10，0x00，0x00，0x00，//mov rax，[rax-1]0x48，0x8b，0x40，0xff，}；//clang-format on Expect_ENTRY_CONTAINS_CODE(BUF，EXPECTED)；BUFFER_MAKE_EXECUTABLE(BUF)；uWORD RESULT=TESTING_EXECUTE_ENTRY(BUF，HEAP)；ASSERT_EQ_FMT(OBJECT_ENCODE_INTEGER(1)，RESULT，"；0x%lx"；)；AST_HEAP_FREE(节点)；PASS()；}。

我在这篇文章中没有讨论可变长度的对象，因为我想重点介绍分配和查看已分配数据结构的基础知识。下一次，我们将添加符号和字符串。