compiler-construction - for - llvm 3.7 1

¿Cómo implementar eficientemente cierres en LLVM IR?

Question

Comencé a agregar cierres (lambdas) a mi idioma que usa LLVM como backend. Los he implementado para casos simples donde pueden estar siempre en línea, es decir, no es necesario generar el código para la definición de cierre, ya que está en línea donde se usa.

Pero cómo generar el código para un cierre en caso de que el cierre no siempre esté en línea (por ejemplo, se pasa a otra función que no está en línea). Preferiblemente, los sitios de llamada no deberían preocuparse si se pasan funciones regulares o cierres y los llamarían como funciones normales.

Podría generar una función con un nombre sintético, pero tendría que tomar el entorno de referencia como un argumento adicional y esa función no se podría pasar a otra función que no conozca el argumento adicional que se necesita.

He pensado en una posible solución utilizando los intrínsecos de trampolín de LLVM, que "eliminan" un solo parámetro de una función, devolviendo un puntero a una función de trampolín que toma un parámetro menos. En este caso, si la función generada para el cierre tomó el entorno de referencia como el primer parámetro, podría suprimirlo y recuperar una función que tome exactamente tantos parámetros como el cierre realmente declara. ¿Esto suena factible? ¿Eficiente? ¿Hay mejores soluciones?

Ejemplo de código:

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)
}

Ahora, imaginemos que esto no se alinearía con def main() = 3 + 4 + 5 , y que applyFunctionTo posiblemente se compile por separado, y no podemos cambiar el sitio de llamadas allí. Con el trampolín, imagino que el código generado sería algo como esto (expresado en pseudocódigo, * significa puntero):

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
}

¿Esto parece correcto?

Answer 1

Suena factible y eficiente.

La forma alternativa, que no necesita trampolines, es definir el tipo de cierre como un par de puntero de función y puntero al entorno, es decir, puntero de pila. En la convención de llamada C, los argumentos adicionales se ignoran, por lo que si proporciona un entorno como último argumento, incluso puede usar (function_ptr, null) como devolución de llamada para la función normal.

Answer 2

Una idea estúpida sería que, para cada cierre, genere una estructura local de hilos para contener los datos necesarios (podría ser solo un puntero a una estructura local, o varios punteros).

El creador del cierre es el responsable de configurar las variables TLS y "guardar" el estado que tenían (para permitir una llamada recursiva).

El usuario luego llama a la función normalmente, se ejecuta y usa el entorno.

Después de la llamada, el creador del cierre "restaura" los valores originales en las variables TLS.