如何在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可能会单独编译，我们无法在调用站点进行更改。使用trampolining，我想生成的代码大概是这样的（以伪代码表示，*表示指针）：

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
}

这是否看起来正确？

- Erkki Lindpere

---

实现闭包和实现带有虚拟方法的对象之间没有区别。 - SK-logic

你说的可能是对的，但是这种语言目前还没有虚方法。至少在那之前它会有闭包和很多其他东西。我可能会以愚蠢的顺序添加一些功能，因为我只是为了学习而这样做。我只希望最终能从中得到一些有用的东西。 - Erkki Lindpere

我的意思是，对于闭包来说没有发明任何新东西的理由：你可以做与C++编译器正在做的相同的事情。很有可能这已经是最有效的方法了。 - SK-logic

抱歉，我没有完全理解您的意思。我在上面添加了一个代码示例。不会有lambda lifting，因为我无法修改调用站点（但也许我误解了您的意思或在原始问题中传达错误）。如果函数指针在环境中，那么如何从函数中获取环境？另外，也许我之前没有表达清楚，我强烈希望调用站点不会因为传递给它们的是lambda还是常规函数而发生变化。并且应该优先选择常规函数。 - Erkki Lindpere

啊，没事了。我现在明白你的意思了。这与另一个答案提出的替代方案相似。不过我想我会尝试一下蹦床。 - Erkki Lindpere

Answer 1

听起来可行且高效。

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

- zch

---

我现在会尝试使用trampolines，但是如果程序中传递的大多数函数都是具有自由变量的闭包或对象方法（其中“this”可以被视为自由变量），那么将函数作为一对指针传递的替代方案实际上可能更好。我不确定语言最终会变成什么样子，但我可能会考虑以后切换到那种表示方式。 - Erkki Lindpere

Answer 2

一个愚蠢的想法是为每个闭包生成一个线程本地结构来保存所需的数据（可以只是指向本地结构或几个指针）。

闭包的创建者负责设置TLS变量并“保存”它们的状态（以允许递归调用）。

然后用户正常调用函数，执行并使用环境。

调用结束后，闭包的创建者将原始值“恢复”到TLS变量中。

- Matthieu M.