Dart-on-LLVM

Esta es una historia sobre un experimento para compilar el lenguaje Dart usando el framework de compilación LLVM. En apariencia esto es bastante inútil, ya que

Dart ya tiene una máquina virtual excelente que usa compilación just-in-time para obtener un rendimiento excelente. Dado que Dart es dinámicamente tipado (más precisamente, es opcionalmente tipado), un compilador JIT es un encaje natural — puede usar los tipos disponibles en tiempo de ejecución para realizar optimizaciones que un compilador estático no puede hacer.

Otra razón por la que Dart-on-LLVM parece una tarea de locos es que, a pesar del nombre, LLVM no es una máquina virtual, y hasta hace poco no era adecuado para lenguajes con garbage collection. Con adecuado nos referimos a:

• GC de movimiento, preciso (sin fugas)

• Altamente optimizado

Esto se debe a que, una vez que el optimizador ha destrozado tu código, ya no tenías forma de encontrar los punteros GC-able en el stack. Una estrategia común era mover todos los punteros a áreas de memoria especiales, pero esto anula muchas de las estrategias de optimización en un compilador moderno, que depende de la asignación de registros de variables locales para hacer su magia. Podías tener buen GC o rendimiento completo, no ambos.

Pero soplan nuevos vientos en LLVM-land. Recientemente, LLVM ha añadido algo de soporte de GC en forma de la característica experimental Statepoint. Esto ha sido usado por varios grupos valientes, incluyendo a la gente detrás del experimento LLV8 y Azul, que lo están usando para un nuevo compilador de primer nivel para su JVM.

Parece que construir una VM real basada en LLVM ha pasado de ser "misión imposible" a ser simplemente "misión difícil". Al mismo tiempo, strong mode hace que Dart sea más estáticamente tipado, y menos dinámico. Además, en Google estamos construyendo Flutter para iOS, donde la compilación JIT está prohibida. Ambos desarrollos alinean mejor a Dart con los objetivos y trade-offs del proyecto LLVM.

LLVM es un framework de compilación Open Source moderno y bien mantenido, que nos da mucha optimización y plataformas "gratis". Por ejemplo, hay un paso completo de inlining que puede inlinear cualquier función dentro de cualquier otra, y contiene heurísticas para cuándo hacerlo.

También parece una comunidad abierta y acogedora, que recibe contribuciones.

• El contexto es Dart en Strong Mode en un escenario compilado ahead-of-time

• Evaluar la viabilidad de usar el soporte de Statepoint para GC preciso y de movimiento

• Evaluar el rendimiento

Nosotros (Erik Corry y Dmitry Olshansky) basamos nuestro experimento en el runtime discontinuado "Dartino". Este era un runtime experimental de Dart optimizado para dispositivos pequeños. Tenía algunas ventajas sobre usar el DartVM como base:

• Ya había un backend experimental de LLVM para Dartino, construido por Martin Kustermann. No tenía soporte de GC, así que crasheaba cuando se quedaba sin memoria.

• Dartino hace uso de mucha de la maquinaria de Dart2JS, y por lo tanto no necesita un parser completo, front end, etc. Los bytecodes de Dartino que usamos como entrada ya tienen muchas de las características difíciles de Dart eliminadas. Por ejemplo, las closures son objetos, y los argumentos opcionales se han convertido en diferentes versiones de funciones.

• Ambos ya conocíamos Dartino.

• Dartino viene con un runtime relativamente completo y es capaz de ejecutar aplicaciones grandes, por ejemplo, alojar Dart2JS. No tiene mucho soporte de IO de Unix y el modelo de threading es diferente, así que no es un reemplazo directo.

El experimento existente de Dartino LLVM se bifurcó de Dartino hace un tiempo, cuando el GC era muy simple (semispace Cheney collector, sin generaciones, pausas grandes, 2x de sobrecarga de memoria). Hicimos cherry-pick de cambios de la rama principal de Dartino para obtener un GC convencional de 2 generaciones con write barriers. No hay read barriers, y la recolección es stop-the-world, sin GC concurrente (aunque los Statepoints de LLVM parecen tener soporte para estas características, y casi con seguridad están siendo usados por Azul en su VM de código cerrado).

No hicimos cherry-pick del soporte de compactación de la generación vieja de versiones más nuevas de Dartino.

El pipeline anterior muestra el camino desde el código fuente Dart hasta el código máquina. En una implementación real, las primeras partes se reemplazarían por algo basado en el formato 'kernel' (frontend de código Dart preprocesado).

llvm-codegen está enlazado a nuestra propia copia de LLVM, y realiza optimizaciones de alto nivel. En esta etapa, LLVM mantiene la ficción de que los punteros son válidos a través de los GC, pero los punteros están marcados con un "address space" no predeterminado que prohíbe a LLVM razonar sobre sus patrones de bits de formas que serían incorrectas en presencia de GC de movimiento. Varias intrínsecas personalizadas de LLVM se usan para marcar puntos donde puede ocurrir el GC.

Debido a los tagged pointers, el bitcode de LLVM es muy feo con muchos casts y adds. Por lo tanto, este documento contiene "pseudocódigo LLVM", y no el archivo .ll real. Si estás acostumbrado a archivos .ll reales, esto va a parecer como "Los primeros balbuceos de un bebé con .ll", ¡perdón! Lo siguiente representa el código para un dispatch dinámico después de mem2reg, el paso que eleva las variables locales del stack a registros SSA:

%class = load_class(%this)
%id = load_class_id(%class)
%offset = add 291, %id
%code = array_load(@dartino_vtable, %offset)
%method_result = call %code(%process, %16)
; We can still use “%this” here, even if there has been a GC in the call

Después de que el optimizador ha corrido, el lookup bastante laborioso de arriba se ha sacado del loop, dejando solo la instrucción de llamada. Esto es posible porque los punteros de clase son inmutables en Dart y hemos adjuntado varios metadatos a las instrucciones de carga (no mostrados), incluyendo invariant.load y never.faults (esto último es una adición a nuestra versión modificada de LLVM).

Una vez que las optimizaciones de alto nivel se han ejecutado, hacemos lowering de la mayoría de las intrínsecas a instrucciones normales de LLVM. Por ejemplo, el write barrier se reduce a una serie de stores (Dartino usa un esquema de card marking que le debe mucho a la sección 6.2.3 del PhD de Urs). Después del lowering, cada puntero de variable local es reescrito por una intrínseca opaca en cada posible punto de GC (básicamente cada llamada). Esto inhibe muchas optimizaciones (por eso tuvimos que hacer los pasos de optimización antes del lowering), pero sirve para dos propósitos:

• La intrínseca se usará más adelante para generar stack maps, detallando la ubicación de los punteros GC-able en el stack.

• Los valores SSA se dividen en valores antes-del-GC y después-del-GC, lo que hace visible el GC para el optimizador y previene codegen inválido.

La llamada ahora se ve más así (el dispatch se ha sacado de un loop, así que %code contiene el puntero de código — el loop no se muestra)

%statepoint_token = call token (…) @llvm.experimental.gc.statepoint(326, 0, %code, 3, 0, %process, %this, %16)
%method_result = call @llvm.experimental.gc.result(token %statepoint_token)
%this.relocated = call coldcc @llvm.experimental.gc.relocate(token %statepoint_token, 10, 10) ; (%this, %this)
%16.relocated = call coldcc @llvm.experimental.gc.relocate(token %statepoint_token, 11, 11) ; (%16, %16)
; We now have to use %this.relocated instead of %this,
; and %16.relocated instead of %16

La transformación es bastante torpe, creando un token especial en la llamada transformada, y usándolo como argumento en las llamadas a gc.result y gc.relocate. Los punteros GC-able siguen marcados especialmente (con un address space no nulo, no mostrado en el pseudo-LLVM de arriba), lo cual inhibe algunas optimizaciones en la siguiente etapa.

El paso final es la generación de código, realizada por el programa de LLVM llc. Este paso se puede hacer con un LLVM ToT completamente sin parchear con el comando llc -O3. El único backend con soporte para las intrínsecas experimentales de GC es actualmente x64, pero no vemos barreras fundamentales para añadir y subir soporte para ARM. El sitio de llamada del dispatch dinámico ahora se ve así:

movq %rdx, (%rsp)
movq %rcx, 8(%rsp)
movq %rdx, 16(%rsp)
movq %rbx, %rdi
movq %rcx, %rsi
callq *%r14

Esto usa la convención de llamadas estándar (basada principalmente en registros) para x64. Antes de cada llamada, un grupo de registros se vuelca al stack, donde el GC puede moverlos si es necesario. No hay soporte para valores GC-able guardados por el callee (V8 y DartVM tampoco soportan esto).

El bytecode de Dartino está optimizado para simplicidad y compacidad en un entorno muy dinámicamente tipado. Para este análisis intentamos mirar hacia un escenario donde se usa strong mode y los tipos se conocen al compilar. En este escenario, el dispatch de métodos y el acceso a variables miembro en objetos sería más simple y rápido. Para acercarnos a ese escenario, estamos haciendo uso de algunos análisis de programa completo al generar código LLVM.

La consecuencia más importante de esto es que si solo unas pocas clases tienen un método foo(), entonces verificamos esas clases y llamamos al método foo() directamente. A diferencia de algún mecanismo de dispatch tipo vtable, esto permite a LLVM inlinear el método donde tiene sentido. Esto es una gran ventaja, especialmente para getters y setters, que son una gran característica de Dart.

El compilador todavía tiene que manejar muchos problemas de lenguaje dinámico, lo cual hace mayormente correcto (ver sección de estado de tests más abajo). En particular, los enteros pueden desbordarse y convertirse en objetos de número reales alojados en el heap en cualquier momento. Junto con la sobrecarga de operadores, esto hace que incluso simples for-loops sean bastante complicados. Más análisis estático probablemente pueda mejorar esto.

Una diferencia con el DartVM real es que no verificamos stack overflows ni verificamos interrupciones de thread en los back edges de los loops. Basado en la experiencia de V8, estimamos que arreglar esto podría costar alrededor del 10% de rendimiento.

Comparamos contra el DartVM regular con JIT, y el nuevo soporte ahead-of-time que se ha añadido al DartVM para Flutter. Los benchmarks son de Dartino.

Ejecutar un programa de corta duración como Hello World muestra principalmente el tiempo de startup. El sistema basado en JIT invierte tiempo compilando código, y ambas soluciones non-LLVM aquí están deserializando un data heap en el startup.

Tenemos un rendimiento comparable a la tecnología ahead-of-time existente de Flutter (que es un objetivo en movimiento — estas mediciones se hicieron a finales de noviembre de 2016 en una potente estación de trabajo Linux de 64 bit). El JIT sigue estando muy por delante. El rendimiento de garbage collection del fork de Dartino en el que estamos corriendo, no está a la altura. También medimos el tiempo de startup. Dartino-LLVM genera datos estáticos para las clases, constantes y dispatch tables. Estos son cargados por el linker runtime ld.linux altamente optimizado, y cargan más rápido que el snapshot actual del data heap de Dart AOT, dando muy buen rendimiento de startup. Para los tests de startup el CPU governor se configuró en "performance".

Para este estudio no nos hemos enfocado especialmente en lograr 100% compatibilidad con Dart. Es suficiente hacer "las cosas difíciles", es decir, GC y manejo de excepciones, para demostrar que son posibles. En algunos casos tomamos un atajo que demostraba que una solución real era posible sin perder tiempo implementando la solución real. Aquí hay algunos lugares donde hicimos concesiones:

• Al igual que Dartino, no tenemos enteros de precisión infinita. Sin embargo, verificamos todas las operaciones de int por desbordamiento y cambiamos dinámicamente a una representación de número boxed (sin embargo, la representación boxed es solo de 64 bit, con wrapping).

• En no-such-method (esencialmente una verificación de tipo fallida), no seguimos la semántica completa de Dart, que incluye llamar al método no-such-method y verificar si hay un getter con el mismo nombre que el método faltante que retorna un objeto con un método 'call'. Sin embargo, sí lanzamos una excepción en un safe point (un punto donde puede ocurrir una asignación).

• No verificamos stack overflow en las llamadas, ni verificamos interrupciones en los back edges de los loops. LLVM sí tiene soporte experimental para esto. Las soluciones con las que nos comparamos sí soportan esto. La experiencia de V8 sugiere que arreglar esto podría causar alrededor de 10% de degradación de rendimiento.

• Nuestro compilador front-end es un Dart2JS modificado. Como Dartino fue discontinuado, no se ha mantenido al día con los últimos cambios del lenguaje, y por lo tanto hay algunos tests que no podemos ejecutar.

• El manejo de excepciones de Dart está completamente implementado aparte de las excepciones relacionadas con no-such-method. Para esto usamos el soporte de manejo de excepciones integrado en LLVM, que parece adecuado para la tarea y bien alineado con el modelo de excepciones de Dart (que en el fondo no es muy diferente de C++, para el cual LLVM fue diseñado).

En total, pasamos casi el 90% de los tests que Dartino podía pasar. De los que fallamos, las mayores razones son problemas con el front-end del compilador y problemas manejando eventos de no-such-method.

De los ca 11,6% de tests que fallan, aquí hay un desglose de por qué fallan:

El soporte experimental de GC de LLVM parece ser completamente funcional en x64. El rendimiento del prototipo estuvo a la par con nuestra solución ahead-of-time más madura basada en DartVM.

Para el análisis de rendimiento no estamos usando Dart strong mode, lo cual se puede esperar que genere oportunidades de optimización que aprovechan las fortalezas de LLVM. Sin embargo, estamos haciendo uso de algunas asunciones de closed world, que creemos son realistas.

Podemos compilar la última etapa desde bitcode de LLVM a código máquina usando solo un build LLVM ToT sin parchear (marcado en azul en el diagrama de pipeline de arriba). Las optimizaciones realizadas en esta etapa (-O3) no causaron ninguna miscompilation ni problemas de GC que hayamos observado.

No ha habido decisión sobre cómo y si usar este enfoque para Dart o Flutter, pero aquí hay algunos pensamientos al azar sobre avenidas interesantes que se podrían explorar.

• Tener un lenguaje propio distinto a C++-with-handles para escribir rutinas de runtime. El backend sería LLVM-with-Statepoints. (Hay un pequeño experimento de Forth en la rama actual, pero algo más sustancial sería necesario para escribir más que las rutinas nativas más simples.)

• ¿Qué impacto tendría el wrapping de enteros de 64 bit?

• ¿Cómo podemos usar conocimiento de programa completo para generar código mientras permitimos la compilación paralela de proyectos grandes?

Soporte de GC de LLVM http://llvm.org/docs/Statepoints.html Repositorio de Dartino-LLVM https://github.com/dartino/sdk/tree/llvm Repo modificado de LLVM https://github.com/ErikCorryGoogle/llvm PhD de Urs Hölzle: http://hoelzle.org/publications/urs-thesis.pdf LLV8: https://github.com/ispras/llv8