如何有效地实现闭包在LLVM IR？ [英] How to efficiently implement closures in LLVM IR?

问题描述

我开始在我使用LLVM作为后端的语言中添加closures（lambdas）。我已经实现它们为简单的情况下，他们可以总是内联，即代码闭包定义本身不需要生成，因为它是内联使用。

I started adding closures (lambdas) to my language that uses LLVM as the backend. I have implemented them for simple cases where they can be always inlined i.e. code for the closure definition itself doesn't need to be generated, as it is inlined where used.

但是如何在闭包不总是内联的情况下生成闭包的代码（例如，它被传递给另一个未内联的函数）。优选地，调用站点不应该关心它们是否传递常规函数或闭包，并且将它们称为正常函数。

But how to generate the code for a closure in case the closure isn't always inlined (for example, it is passed to another function that isn't inlined). Preferably, the call sites shouldn't care whether they are passed regular functions or closures and would call them as normal functions.

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

I could generate a function with a synthetic name, but it would have to take the referencing environment as an extra argument and that function couldn't just be passed to another function that doesn't know about the needed extra argument.

我想到了一个可能的解决方案使用LLVM的蹦床内在函数，它从一个函数切除一个单一的参数，返回一个指针指向一个少一个参数的蹦床函数。在这种情况下，如果为闭包生成的函数使用引用环境作为第一个参数，我可以删除它，并获取一个函数，该函数需要与闭包实际声明的参数一样多的参数。这个声音是否可行？高效？是否有更好的解决方案？

I have thought of one possible solution using LLVM's trampoline intrinsics, which "excise" a single parameter from a function, returning a pointer to a trampoline function that takes one less parameter. In this case, if the function generated for the closure took the referencing environment as the first parameter, I could excise it and get back a function that takes exactly as many parameters as the closure actually declares. Does this sound doable? Efficient? Are there any better solutions?

代码示例：

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 分开，我们不能改变呼叫站点。使用蹦床，我想象生成的代码将是这样的（用伪代码表示，*表示指针）：

Now, lets imagine that this wouldn't get inlined to def main() = 3 + 4 + 5, and that applyFunctionTo would possibly be compiled separately, and we can't change the call site there. With trampolining, I imagine the generated code would be something like this (expressed in pseudocode, * means pointer):

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
}

这看起来是否正确？

推荐答案

有效。

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

The alternative way, that does not need trampolines, is to define closure type as a pair of function pointer and pointer to environment ie stack pointer. In C calling convention the extra arguments are ignored so if you provide environment as last argument you can even use (function_ptr, null) as callback for regular function.

这篇关于如何有效地实现闭包在LLVM IR？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！