如何在LLVM IR中有效地实现闭包？

Question

我开始在我的语言中添加闭包(lambdas),使用LLVM作为后端.我已经将它们实现为可以始终内联的简单情况,即闭包定义本身的代码不需要生成,因为它在内联使用时也是如此.

但是如果闭包并不总是内联的话,如何为闭包生成代码(例如,它被传递给另一个没有内联的函数).优选地,呼叫站点不应该关心它们是否被传递给常规功能或闭包并且将它们称为正常功能.

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

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

代码示例:

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
}

这看起来是对的吗？

Answer 1

听起来可行而且效率高.

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