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

2020-10-12 07:05:59

欢迎回到“编译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();}。

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