Interesante compilador de proyectos

Question

Actualmente estoy en el proceso de elegir un proyecto para un curso de compilación de nivel de graduado durante las próximas 8 semanas. Me gustaría hacer algo relacionado con la optimización ya que no he trabajado mucho en esa área antes, pero cualquier cosa en el campo es juego limpio.

¿Cuál es el proyecto de compilador más interesante que has hecho? ¿De qué aprendiste más?

---

Editar: Gracias a todos por sus sugerencias. Me disculpo por no actualizar esto por tanto tiempo.

El proyecto que terminé haciendo fue una simple optimización de autovectorización en LLVM. LLVM tiene tipos de vectores, pero no parecía haber ninguna forma de aprovecharlos sin soporte para el front-end. Esta optimización convirtió el código escalar normal en código vectorial.

Dado que la auto-vectorización es una optimización bastante difícil de implementar, limitamos nuestro alcance tanto como pudimos. En primer lugar, para exponer el paralelismo del nivel de instrucción en el código, buscamos lazos de un bloque que coincidieran con nuestros criterios, luego los desenrollamos un número específico de veces para que pudieran ser convenientemente vectorizables. Luego implementamos el algoritmo de empaquetado establecido en Exploiting Superword Level Parallelism with Multimedia Instruction Sets por Larsen y Amarasinghe.

Incluso una versión simplificada de esta optimización es bastante complicada. Hay muchas restricciones; por ejemplo, no desea vectorizar una variable que viva fuera del ciclo, ya que el resto del programa espera que sea escalar. Hemos dedicado muchas horas en las últimas semanas. El proyecto fue muy divertido y aprendimos mucho.

Answer 1

Si está interesado en la optimización, la Vectorización de bucles utilizando conjuntos de instrucciones SSE y MMX podría ser interesante.

Answer 2

Creo que escribir mi propio lenguaje de scripting integrado fue uno de los proyectos relacionados con el compilador más interesantes que he hecho. Me enseñó todos los aspectos del proceso, desde el diseño hasta el concepto, y como lo estaba haciendo desde el principio, podía hacerlo tan simple o complejo como lo necesitaba, lo que me permitió entender los conceptos sin mucho ruido, que modificaba un sistema establecido. proyecto podría tener.

Answer 3

Una vez escribí un lenguaje de programación y una máquina virtual para ejecutarlo. El lenguaje fue capaz de interactuar con la función escrita específicamente para que estuviera contenida en una DLL (esto era antes de la automatización OLE) en Windows de 16 bits.

Hacer todo el trabajo de principio a fin me dio una gran comprensión en un idioma de ambos extremos. Había leído varios libros de compilación en ese momento (como el infame libro del Dragón) pero nunca me hundí hasta que escribí algo concreto. Ahora, muchos años después, el trabajo que hice me ha dado una apreciación y una comprensión más ricas de que cosas como la VM Java y la CLR funcionen.

Answer 4

Para compiladores de aprendizaje, hacerlo de extremo a extremo es la mejor idea. Usando una máquina de fondo simple, NO un x86, en lugar de seleccionar una máquina simple como un MIPS bare-bones. Hice mi proyecto de compilador de pregrado apuntando a un simulador de PDP-11, que era un gran objetivo, ya que mantenía las cosas muy simples. Gracias a un código de muestra, podríamos hacer un compilador de lenguaje imperativo simple en unas cuatro semanas. ¡Cª!

Hoy, con lenguajes potentes como ML, hacer un compilador debería ser mucho más fácil.

Lo que debe hacer dependerá realmente de su interés. Si está en optimización, busque algún tipo de marco simple donde eso es todo lo que necesita para preocuparse.

Creo que la zona más fructífera de hoy ha sido la compilación de destinos enhebrados o en compilación justo a tiempo.

Answer 5

La detección de bucles y el desenrollado parametrizado deberían ser lo suficientemente difíciles como para que resulte interesante. No es muy sexy, pero ser demasiado sexy en 8 semanas te hundirá.

Answer 6

En mi clase de compiladores de pregrado, primero escribimos un analizador de descendencia recursiva (descendente) para un lenguaje similar a Pascal desde cero: analizador léxico, analizador, todo.

Aproximadamente a la mitad del semestre, pasamos a los generadores de analizador sintáctico/escáner como lex/yacc o flex/bison. Creamos un compilador que tomaría nuestro subconjunto de Pascal y lo compilaría para ensamblarlo para una máquina de pila que se nos proporcionó (la máquina de pila es súper simple, pero los principios siguen siendo los mismos).

Si está interesado en los compiladores, no puedo recomendar lo suficiente el Dragon Book. Está destinado a ser utilizado para un curso de licenciatura de 1 semestre, y la segunda mitad como un curso de posgrado, y cubre cada pedacito de teoría y optimización que pueda desear. Incluso Joel likes it. =)

Saludos

Answer 7

Considere la inferencia de tipos para un lenguaje de tipo dinámico existente.

Answer 8

Con un margen de tiempo de 8 semanas, tendrá que tener cuidado con "scope creep". Eso no es demasiado ambicioso, esp. si este proyecto incluye otros aspectos de la construcción del compilador (lexing/parsing), o si todavía está aprendiendo las herramientas (depurador, yacc) y las estructuras de datos intermedios (DAG).

Dicho esto, mi primera sugerencia sería probar algunos análisis de variables en vivo. Los algoritmos están bastante bien establecidos, por lo que simplemente necesita codificarlo específicamente para sus estructuras de datos, etc.

Esto le permitiría hacer una forma limitada de eliminación de código muerto. Es decir, si detecta que una variable se declara pero nunca se utiliza, no le asigne espacio. Si detecta que se establece un valor pero nunca lo lee, no genere el conjunto.

El análisis de variables en vivo también puede ayudar con la asignación de registros, por lo que es posible que también pueda abordar eso si hay tiempo, y debería poder reutilizar algo de lo que crea para la eliminación de código muerto.

Answer 9

Puede escribir un optimizador para IronScheme, ya que actualmente lo hace todo bien, excepto algunas funciones 'intrínsecas'. :)

Answer 10

Hace unos años, diseñé una DSL y escribí el compilador para un producto que mi empresa producía. La DSL usaba una combinación extraña de reglas declarativas, lógica impulsada por eventos y herencia compositiva. Fue un proyecto muy divertido, y aprendí mucho.

Realmente despertó mi interés en los analizadores sintácticos & compiladores, por lo que he tratado de mantenerse al día con los nuevos desarrollos interesantes en la tecnología del compilador.

Con respecto a la optimización, aquí está un artículo de la diversión que leí el año pasado:

http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf

En este artículo, los autores describen una técnica para la detección automática de optimizaciones de mirilla (superando el rendimiento de varios populares Back-ends del compilador C++) sin que un experto tenga que escribir muchos códigos de casos especiales. Su técnica utiliza algoritmos de aprendizaje no supervisados ​​para descubrir reemplazos de mirilla de alto valor.

Después de leerlo, se me ocurrió que su enfoque podría aumentarse proporcionando al algoritmo una "descripción de la máquina" enumerando todas las instrucciones (con sus efectos principales y sus efectos secundarios) compatibles con la arquitectura del procesador de destino . Entonces, en lugar de usar un enfoque de fuerza bruta para encontrar secuencias de instrucción equivalentes, el solucionador podría encontrar esas secuencias mucho más fácilmente.

El algoritmo de aprendizaje automático seguiría utilizando observaciones empíricas para determinar la secuencia de instrucciones más eficiente (porque los efectos de caché, microoperaciones y canalización casi exigen datos de temporización empíricos), pero la equivalencia de resultados podría predecirse utilizando un algebraico theorem-prover, que funciona en la descripción de la máquina.

En el documento, hablan de cómo sus optimizadores solo podían descubrir secuencias de reemplazo de mirilla de dos o tres instrucciones (porque, de lo contrario, la búsqueda de fuerza bruta tomaría demasiado tiempo y consumiría demasiada memoria). Poner un solucionador inteligente en el lugar correcto del algoritmo podría permitirle trabajar con secuencias de reemplazo más largas.

Anyhoo ... ¡házmelo saber cuando termines con ese proyecto! ¡Y no olvides mencionarme en tu sección de "Agradecimientos"! ;-)

Answer 11

Otros proyectos interesantes podrían incluir:

• Añadir una optimización de llamada a la de código abierto de Sun JVM.

• Agregue una optimización de valor de retorno (NRVO) con nombre a las VM de Python o Ruby.

• Agregar compilación en tiempo de ejecución en expresiones regulares a código de bytes, para su blanco favorito (.Net ya lo tiene. Estoy bastante seguro de Java no lo hace.)

Answer 12

Mientras escribe el el propio idioma es una actividad académica divertida y tradicional, ya hay demasiados proyectos relacionados con el compilador implementados deficientemente. Además, 8 semanas no es suficiente tiempo para hacer un buen trabajo en una implementación completa del lenguaje.

Si está interesado en "algo relacionado con la optimización", elija un idioma o VM ya existente y optimícelo para obtener rendimiento, tamaño o ambos. Esto evitará tener que reinventar toda la implementación del lenguaje, le permite enfocarse en el problema de optimización, producirá un producto útil para otras personas y no solo otro ejercicio académico, e incluso puede ser útil para conseguir un trabajo.

Creo que el intérprete de bytecode Parrot y varios analizadores .Net Iron-language podrían beneficiarse incluso de simples optimizaciones.

Answer 13

Además de las sugerencias de "Dragon Book", también recomiendo "Advanced Compiler Design & Implementation", de Steven S.Muchnick, que se enfoca en representaciones intermedias, generación de código y técnicas de optimización.

Answer 14

Busca ayuda para el proyecto Shed Skin, que compila Python para C++. Creo que durante el verano, se hizo un llamado de ayuda. ¡La determinación de maneras de mejorar la compilación a C++ proporcionaría una optimización fenomenal para los programas de Python!

http://code.google.com/p/shedskin/

Answer 15

Aquí hay otra idea ... aunque sigue siendo un poco grande vaga:

La mayoría de optimización se realiza en tiempo de compilación (excepto en los compiladores JIT, que optimizan en tiempo de ejecución). Pero también hay muchas oportunidades de optimización en tiempo de enlace y en tiempo de instalación.

Estoy particularmente interesado en la idea de una plataforma en la que no se moleste en enlazar hasta el momento de la instalación. Pero durante ese proceso de vinculación de tiempo de instalación, adopta una estrategia de optimización agresiva, ya que conoce mucha información detallada sobre la arquitectura de la máquina y puede tomar decisiones de optimización más sutiles y bien informadas.

Answer 16

Generación automática de código en línea usando pruebas heurísticas para compensaciones de tamaño/velocidad.

Answer 17

He hecho esto en mi propia enseñanza "mucho antes". No le daría tanto énfasis a la optimización en cuanto a otras cosas, como la inferencia de tipo o JIT o bytecoding o el formato de objeto/soporte de depuración.

No hay problema en concentrarse en la optimización siempre y cuando también demuestre que es mucho menos importante de lo que la gente piensa. Lo único que importa en el código que:

• carreras en bucles apretados en la parte inferior de la pila de llamadas (es decir, sin llamar a las funciones, de manera explícita o implícitamente)
• realidad ocupa un porcentaje significativo de tiempo de una aplicación (es decir, si el código rara vez se ejecuta, optimizarlo no ayudará mucho).

Esto es bastante pequeña fracción de todo el código que el compilador verá.

Edición: Lamentablemente, no puedo dejar de trabajar con los compiladores Fortran, que codifican el código sin piedad, por lo que es muy difícil de depurar, mientras que tiene efecto épsilon en el rendimiento.

Answer 18

El compilador B :: CC perl se beneficiaría de agregar y analizar tipos. Todavía no tengo suficiente tiempo para eso.

Tuve suficiente tiempo últimamente. http://blogs.perl.org/users/rurban/2011/02/use-types.html