haskell - 将 G-Machine 源转换为 LLVM IR

Question

我正在用 LLVM 作为 Haskell 的后端来实现一个简单的惰性函数语言。我读过 Simon Peyton Jones 写的两本书(“函数式编程语言的实现”，以及“函数式语言的实现:教程”)，并在此基础上实现了 G-Machine compiler and interpreter .

我现在被困在从 G-Machine 指令生成 LLVM IR 代码的问题上。主要问题是 G-Machine 是堆栈机，而 LLVM IR 是寄存器机。因此，为了将 G-Machine 翻译成 LLVM IR，我必须在 LLVM IR 中维护某种运行时堆栈(如果我错了，请纠正我)。我正在考虑使用它的 IR 指令在 LLVM 堆栈上分配后续堆栈节点，但是我必须以链表方式创建该堆栈，其中每个堆栈元素都有一个指向前一个的指针，第一个有一个空指针。然而，这种方法不是非常理想，并且在 G-Machine 的“Push n”操作的情况下，它将具有 O(n) 的复杂度，而不是首选的 O(1)。其他想法可能是分配整个内存块而不是单个单元格。

我的问题是您是否看到解决我的问题的更好/不同的方法。

Answer 1

不要做链表堆栈，那太疯狂了。使用固定内存块。您可以使用指针堆栈和非指针堆栈，指针是指指向堆的东西。然后很容易进行垃圾收集，因为所有 GC 根都在指针堆栈上。

在 LLVM 寄存器中保留一些东西:堆指针、堆限制指针、两个堆栈指针。

如果幸运的话，LLVM 优化器会将低效的堆栈操作转变为有效的寄存器操作。