CS 6120: curso en línea autodirigido de compiladores avanzados (2020)

• CS 6120, un curso de nivel doctoral de Cornell CS, ofrece un recorrido continuo desde representaciones intermedias, flujo de datos, optimización, paralelización, JIT y recolección de basura para quienes quieren aprender de forma sistemática sobre compiladores e implementación de lenguajes de programación
• La versión autodirigida se toma como si fuera en una universidad ficticia, con 4 créditos sin calificación, y sigue un calendario lineal de videos, apuntes, lectura de papers y tareas de implementación
• Las prácticas usan LLVM y el IR educativo Bril para comprobar conceptos abstractos de compiladores mediante escritura de código real
• A diferencia de la clase real de Cornell, aquí se pueden ignorar las fechas límite de las tareas, pero no se puede participar en las discusiones de Zulip, y en lugar del proyecto final hay una tarea final propia de la versión autodirigida
• El material del curso está publicado como código abierto en GitHub, así que se pueden reportar problemas, y al terminar se pueden enviar sugerencias de mejora mediante un formulario de feedback

---

Estructura del curso y forma de cursarlo

• CS 6120 es un curso sobre implementación de lenguajes de programación creado por Adrian Sampson de Cornell CS
• Cubre tanto temas fundamentales de compiladores de propósito general como temas con enfoque de investigación
  • representaciones intermedias
  • flujo de datos
  • optimización clásica
  • paralelización
  • compilación JIT
  • recolección de basura
• El aprendizaje continúa con lectura de papers y tareas de hacking de código abierto
  • usa LLVM
  • usa Bril, un IR educativo para la clase
• El currículo autodirigido está organizado como un calendario lineal que mezcla visualización de videos y lectura de papers
• Algunas lecciones incluyen tareas de implementación, diseñadas para aprender conceptos abstractos mediante escritura de código abierta
• Hay diferencias entre el CS 6120 real y la versión autodirigida
  • se pueden ignorar las fechas límite de las tareas
  • no se puede participar en los hilos de discusión de Zulip
  • la clase real tiene un proyecto final del semestre
  • la tarea final de la versión autodirigida es “cambiar el mundo con la magia de los compiladores”
• El curso está publicado como código abierto en GitHub, así que si hay problemas se pueden reportar bugs
• Al terminar, se puede completar este formulario de feedback

Flujo de lecciones y materiales de lectura

• Introducción y representación de programas

  • Lesson 1: Welcome & Overview
    • video
    • Producing Wrong Data Without Doing Anything Obviously Wrong!
    • SIGPLAN Empirical Evaluation Guidelines
  • Lesson 2: Representing Programs
    • representing programs
    • getting started with Bril

• Fundamentos de análisis y optimización

  • Lesson 3: Local Analysis & Optimization
    • simple dead code elimination
    • local value numbering
  • Lesson 4: Data Flow
    • data flow
    • implementation task
  • Lesson 5: Global Analysis
    • global analysis & optimization
    • Efficient Path Profiling
  • Lesson 6: Static Single Assignment
    • static single assignment
    • Provably Correct Peephole Optimizations with Alive

• LLVM y análisis de bucles e interprocedimental

  • Lesson 7: LLVM
    • introduction to LLVM
    • writing an LLVM pass
  • Lesson 8: Loop Optimization
    • video
  • Lesson 9: Interprocedural Analysis
    • video
    • Type-Based Alias Analysis

• Gestión de memoria y compiladores dinámicos

  • Lesson 10: Alias Analysis
    • video
    • A Unified Theory of Garbage Collection
    • Fast Conservative Garbage Collection
  • Lesson 11: Memory Management
    • video
    • An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes
    • Trace-Based Just-in-Time Type Specialization for Dynamic Languages
  • Lesson 12: Dynamic Compilers
    • Dynamic Compilers
    • Tracing via Speculation
    • Superoptimizer: A Look at the Smallest Program
    • Chlorophyll: Synthesis-Aided Compiler for Low-Power Spatial Architectures

• Paralelismo y compiladores rápidos

  • Lesson 13: Concurrency & Parallelism
    • video
    • Threads Cannot Be Implemented as a Library
    • Exploiting Superword Level Parallelism with Multimedia Instruction Sets
    • A Type and Effect System for Deterministic Parallel Java
    • Formal Verification of a Realistic Compiler
  • Lesson 14: Fast Compilers
    • solo el título está incluido en la lista

[GN⁺]

Comentarios en Hacker News

• La parte sobre compiladores dinámicos es casi por completo contenido sobre compilación por trazas. En general, la compilación por trazas fue un callejón sin salida y se ha descartado varias veces
  Aquí, los conceptos más importantes serían retroalimentación de tipos, ejecución especulativa y desoptimización, compiladores rápidos y estratificación
  El curso completo se ve bien, y también es excelente que hayan publicado en línea tanto material

  • Históricamente se ha visto que el tracing no es práctico como principio organizador, pero creo que es un concepto que amplía la manera de pensar si lo aprendes
    Como dijiste, me gustaría dar más contexto sobre lo que realmente funciona en la industria
  • Trabajo en torch.compile de PyTorch, y esto también es un compilador por trazas
    Dicho eso, esta área puede ser bastante estrecha y también muy distinta de los compiladores tradicionales, así que quizá algunas partes de lo que hacemos te resulten bastante incómodas
  • JAX también es un compilador por trazas
    Claro, sé que el espacio del problema es extremadamente diferente al de TraceMonkey o LuaJIT
  • El paper de TraceMonkey estaba en la lista de lectura para mi examen de candidatura doctoral, y justo coincidió con la época en que TraceMonkey estaba siendo eliminado de SpiderMonkey
    Hablé con uno de los desarrolladores de entonces, creo que era Jason Orendorff, y me dijo que el tracing no terminaba de funcionar, aunque pensaba que quizá podría servir bajo condiciones limitadas
    Pero olvidé por completo cuáles eran esas condiciones
  • La compilación por trazas no es un callejón sin salida
    LuaJIT funciona bien incluso en programas grandes, y en cientos de millones de servidores y dispositivos
    Da mucha pena que incluso académicos sigan repitiendo este lugar común. Me hace pensar en eso de que la ignorancia es una bendición

• Publicaciones relacionadas anteriores:
  CS 6120: Advanced Compilers: The Self-Guided Online Course - https://news.ycombinator.com/item?id=39577878 - marzo de 2024, 102 comentarios
  Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=35130975 - marzo de 2023, 82 comentarios
  Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=25386756 - diciembre de 2020, 232 comentarios

• Me confunde un poco por qué este curso se considera avanzado. La mayoría de los temas, por ejemplo eliminación de código muerto, flujo de datos, análisis de dominadores y forma SSA, parecen cosas que entrarían en un primer curso de compiladores

  • La numeración del curso es bastante regular, así que se puede buscar cuál sería el curso de “compiladores introductorios”: https://www.cs.cornell.edu/courses/cs4120/2026sp/?schedule
    En resumen, compiladores en realidad se divide en dos materias, y la primera cubre los elementos mínimos para construir un compilador: análisis léxico, análisis sintáctico, generación de código y asignación de registros
    La segunda materia trata de cómo construir un compilador optimizador
  • He leído muchísimos materiales relacionados, pero la mayoría no incluía ese contenido
    En la práctica, ya sea en compiladores o intérpretes, el backend casi siempre queda como “ejercicio para el lector”
    Es difícil imaginar cuántas cosas quedan por descubrir todavía: cómo hacer cierres, cómo rastrear entornos, pattern matching, representación en memoria, etc.
    Todo lo interesante hay que investigarlo por cuenta propia
    P. D.: esto es solo un año de eso: https://gist.githubusercontent.com/mamcx/e1743571b9a1ea163a7...
  • Creo que los no especialistas normalmente empiezan por el análisis sintáctico y muchas veces nunca llegan al backend
    Leí dos libros sobre intérpretes y compiladores, y no trataban mucho el backend
    Supongo que esto podría estar más cerca de un curso introductorio al backend
  • Entonces me pregunto qué es lo avanzado. Si se cubren bien eliminación de código muerto, flujo de datos, SSA, selección de instrucciones y asignación de registros, eso ya es prácticamente el 98% del backend

• ¿Habrá otros cursos universitarios autodirigidos de ciencias de la computación en línea de este estilo?

  • Hay decenas. Basta con buscar “mooc”
    Algunos profesores también publican clases y tareas fuera del marco de los “mooc”
    Incluso hubo profesores que me respondieron cuando pregunté en los comentarios. A veces internet sigue siendo bastante genial

• Comparado con Writing a C compiler de Nora Sandler, ¿en qué difiere el beneficio que puede obtener el lector?

  • Ese libro se parece más a lo que obtienes en un curso universitario de compiladores de nivel de licenciatura, mientras que este curso cubre contenido más avanzado que eso
    Si eres principiante o lo exploras como hobby, conviene empezar con ese libro o con materiales de un nivel similar, y luego intentar este curso mientras vas llenando los huecos

• ¿Habrá también algún curso autodidacta de compiladores básicos para ver antes de entrar en el nivel avanzado?

  • Me gusta la estructura de Essentials of Compilation [1][2] y Writing a C Compiler [3]
    Si quieres empezar desde intérpretes, Essentials of Programming Languages [4] está bien
    Reconozco que Crafting Interpreters es popular aquí y en otros lados, pero personalmente no me gusta. Aun así, a otras personas sí les gusta, así que vale la pena intentarlo y además se puede leer gratis
    EOC y EOPL son algo académicos, pero salvo para quienes se sientan incómodos con Scheme y Racket, me parecen bastante accesibles. La versión en Python de EOC reduce ese problema
    Después de eso, los libros de compiladores más profundos y académicos se vuelven más fáciles de abordar
    [1] https://mitpress.mit.edu/9780262047760/essentials-of-compila... - versión en Racket, hay versión de acceso abierto
    [2] https://mitpress.mit.edu/9780262048248/essentials-of-compila... - versión en Python, hay versión de acceso abierto
    [3] https://nostarch.com/writing-c-compiler - permite elegir el lenguaje de implementación
    [4] https://mitpress.mit.edu/9780262062794/essentials-of-program... - es Scheme, pero se puede usar en Racket
  • Recomiendo revisar Crafting Interpreters [1]
    Está dividido en dos partes; la primera construye un intérprete de recorrido de árbol en Java y luego avanza a una versión escrita en C
    1. https://craftinginterpreters.com/
  • No lo he probado personalmente, pero está “the-super-tiny-compiler”:
    https://github.com/jamiebuilds/the-super-tiny-compiler
  • Aunque es viejo, recomiendo empezar con el clásico Compiler Construction for Digital Computers de David Gries
    Junto con algunos de los libros modernos recomendados aquí, debería ser suficiente
    David Gries - https://www.cs.cornell.edu/gries/ y https://en.wikipedia.org/wiki/David_Gries
    El informático neerlandés Dick Grune escribió sobre Compiler Construction for Digital Computers: “varias generaciones de creadores de compiladores crecieron con este libro, y no se arrepintieron”
    El propio Dick Grune también es conocido por sus libros sobre compiladores y lenguajes de programación - https://dickgrune.com/index.html y https://en.wikipedia.org/wiki/Dick_Grune

• Vi un pódcast sobre el compilador de Rust, y creo que dijeron que en algún punto entra un algoritmo de aprendizaje automático para decidir si es código que puede hacer colapsar el sistema

  • Nunca había oído algo así y estoy casi seguro de que es incorrecto. Claro, la expresión “aprendizaje automático” puede ser amplia
    ¿Tienes una fuente?

• De verdad me pregunto qué está haciendo hoy en día alexia massalin, aparte de recibir regalías de la patente de microunity