compiler-construction - 如何在LLVM IR中高效实现闭包？

Question

我开始向使用 LLVM 作为后端的语言添加闭包(lambda)。我已经在简单的情况下实现了它们，在这些情况下它们总是可以内联，即不需要生成闭包定义本身的代码，因为它在使用时内联。

但是，如果闭包并不总是内联的(例如，它被传递给另一个不内联的函数)，如何生成闭包的代码。最好，调用站点不应该关心它们是传递常规函数还是闭包，而是将它们作为普通函数调用。

我可以生成一个具有合成名称的函数，但它必须将引用环境作为额外参数，并且该函数不能仅仅传递给另一个不知道所需额外参数的函数。

我想到了一种使用 LLVM 的蹦床内在函数的可能解决方案，该解决方案从函数中“切除”单个参数，返回指向少一个参数的蹦床函数的指针。在这种情况下，如果为闭包生成的函数将引用环境作为第一个参数，我可以删除它并返回一个与闭包实际声明的参数完全相同的函数。这听起来可行吗？高效的？有没有更好的解决方案？

代码示例:

def applyFunctionTo(value: Int, f: (Int) -> Int) = f(value)

def main() = {
  val m := 4;
  val n := 5;
  val lambda := { (x: Int) => x + m + n };
  applyFunctionTo(3, lambda)
}

现在，让我们假设这不会内联到 def main() = 3 + 4 + 5，并且 applyFunctionTo 可能会单独编译，并且我们无法更改那里的调用站点。通过蹦床，我想生成的代码会是这样的(用伪代码表示，*表示指针):

def main$lambda$1(env: {m: Int, n: Int}*, x: Int) = x + env.m + env.n
def main() = {
  m = 4
  n = 5
  env* = allocate-space-for {Int, Int}
  env = {m, n}
  tramp* = create-trampoline-for(main$lambda$1*, env*)
  return applyFunctionTo(3, tramp*)
  // release memory for env and trampoline if the lambda didn't escape
}

这看起来正确吗？

Answer 1

听起来可行且高效。

不需要蹦床的另一种方法是将闭包类型定义为一对函数指针和指向环境的指针，即堆栈指针。在 C 调用约定中，额外的参数将被忽略，因此如果您提供环境作为最后一个参数，您甚至可以使用 (function_ptr, null) 作为常规函数的回调。