¿Cómo implementar de manera eficiente cierres en LLVM IR?

Question

Empecé a agregar cierres (lambdas) a mi lenguaje que usa LLVM como back-end. Los he implementado para casos simples en los que siempre pueden incluirse, es decir, no es necesario generar el código para la definición de cierre, ya que está inlineado cuando se usa.

Pero cómo generar el código para un cierre en caso de que el cierre no esté siempre en línea (por ejemplo, se pasa a otra función que no está en línea). Preferiblemente, a los sitios de llamadas no les debería importar si se les pasan funciones regulares o cierres y los llamarían 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 podría pasarse a otra función que no sabe acerca del argumento adicional necesario.

He pensado en una posible solución utilizando los intrínsecos de trampolín de LLVM, que "suprimen" un único 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 toma exactamente tantos parámetros como declara el cierre. ¿Esto es factible? ¿Eficiente? ¿Hay mejores soluciones?

ejemplo 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 llegaría a inline def main() = 3 + 4 + 5, y que applyFunctionTo posiblemente podría ser compilado por separado, y no podemos cambiar el sitio llamado allí. Con cama elástica, me 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 
} 

¿Le parece justo?

Answer 1

Sonidos factibles y eficientes.

La manera alternativa, que no necesita camas elásticas, es definir el tipo de cierre como un par de puntero a la función y puntero al entorno, es decir, puntero de la pila. En la convención de llamadas C, los argumentos adicionales se ignoran, de modo que si proporciona el entorno como último argumento, puede incluso usar (función_ptr, nulo) como devolución de llamada para la función normal.

Answer 2

Una idea tonta sería que para cada cierre genere una estructura local de subprocesos para contener los datos requeridos (podría ser solo un puntero a una estructura local, o varios punteros).

El creador del cierre es el responsable de establecer las variables TLS y "guardar" el estado que tenían (para permitir llamadas recursivas).

El usuario 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.