CS 6120: curso online autodirigido de compiladores avançados (2020)

• O CS 6120 de nível de doutorado da Cornell CS oferece, em um fluxo contínuo, representação intermediária, fluxo de dados, otimização, paralelização, JIT e coleta de lixo para quem quer aprender de forma sistemática sobre compiladores e implementação de linguagens de programação
• A versão autodirigida é oferecida no formato de uma universidade fictícia, com 4 créditos sem nota, em que o aluno segue um cronograma linear com vídeos, notas escritas, leitura de artigos e tarefas de implementação
• As atividades práticas usam LLVM e a IR educacional Bril, projetadas para confirmar conceitos abstratos de compiladores por meio da escrita de código real
• Diferentemente da disciplina real em Cornell, é possível ignorar os prazos das tarefas, mas não participar das discussões no Zulip, e no lugar do projeto final há uma tarefa final exclusiva da versão autodirigida
• O material do curso é disponibilizado como código aberto no GitHub, permitindo relatar problemas, e após concluir o curso é possível enviar sugestões de melhoria por meio de um formulário de feedback

---

Estrutura do curso e forma de estudo

• O CS 6120 é um curso de implementação de linguagens de programação criado por Adrian Sampson, da Cornell CS
• Ele cobre tanto tópicos básicos de compiladores de uso geral quanto temas de pesquisa
  • representação intermediária
  • fluxo de dados
  • otimizações clássicas
  • paralelização
  • compilação JIT
  • coleta de lixo
• O aprendizado leva à leitura de artigos e a tarefas de hacking em código aberto
  • usa LLVM
  • usa a IR educacional Bril
• O currículo autodirigido é composto por um cronograma linear que mistura assistir a vídeos e ler artigos
• Algumas lições incluem tarefas de implementação, incentivando o aprendizado de conceitos abstratos por meio de escrita de código aberta
• Há diferenças entre o CS 6120 real e a versão autodirigida
  • é possível ignorar os prazos das tarefas
  • não é possível participar das threads de discussão no Zulip
  • a disciplina real tem um projeto final de semestre
  • a tarefa final da versão autodirigida é “mudar o mundo com a magia dos compiladores”
• O curso é publicado como código aberto no GitHub, então é possível relatar bugs se houver problemas
• Após concluir, é possível preencher o formulário de feedback

Fluxo das lições e materiais de leitura

• Introdução e representação 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álise e otimização

  • 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 e análise de loops e interprocedural

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

• Gerenciamento de memória e 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 e 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
    • apenas o título está incluído na lista

[GN⁺]

Comentários do Hacker News

• A parte sobre compiladores dinâmicos é, em quase sua totalidade, mais próxima de conteúdo sobre compilação por traces. Em geral, compilação por traces foi um beco sem saída e já foi abandonada várias vezes
  O conceito mais importante aqui, na minha visão, é feedback de tipos, execução especulativa e desotimização, compiladores rápidos e em camadas
  O curso como um todo parece bom, e é excelente que tanto material tenha sido disponibilizado online

  • Historicamente, ficou claro que tracing não é prático como princípio organizador, mas acho que é um conceito que vale aprender porque amplia a forma de pensar
    Como você disse, eu gostaria de dar mais contexto sobre o que realmente funciona bem na indústria
  • Estou trabalhando em torch.compile do PyTorch, e isso também é um compilador por tracing
    Só que essa área pode ser bem estreita e também é muito diferente dos compiladores tradicionais, então talvez você ache algumas partes do que fazemos bem desconfortáveis
  • O JAX também é um compilador por tracing
    Claro, sei que o espaço de problemas é extremamente diferente de TraceMonkey ou LuaJIT
  • O artigo do TraceMonkey estava na lista de leitura do meu exame de qualificação de doutorado, e por coincidência a época da prova foi a mesma em que o TraceMonkey estava sendo removido do SpiderMonkey
    Na época, conversei com um dos desenvolvedores, acho que era o Jason Orendorff, e ele disse que tracing não estava dando muito certo e que talvez funcionasse em condições limitadas
    Mas esqueci completamente quais eram essas condições
  • Compilação por traces não é um beco sem saída
    LuaJIT funciona bem em programas grandes e também em centenas de milhões de servidores e dispositivos
    É realmente uma pena que até acadêmicos continuem repetindo esse chavão. Lembra o ditado de que a ignorância é uma bênção

• Posts anteriores relacionados:
  CS 6120: Advanced Compilers: The Self-Guided Online Course - https://news.ycombinator.com/item?id=39577878 - março de 2024, 102 comentários
  Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=35130975 - março de 2023, 82 comentários
  Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=25386756 - dezembro de 2020, 232 comentários

• Fico um pouco confuso sobre por que este curso é avançado. A maioria dos tópicos, como eliminação de código morto, fluxo de dados, análise de dominadores e forma SSA, parece algo que entraria num primeiro curso de compiladores

  • A numeração da disciplina é bem regular, então dá para procurar qual seria o curso de “compiladores introdutórios”: https://www.cs.cornell.edu/courses/cs4120/2026sp/?schedule
    Resumindo, compiladores na prática são divididos em duas disciplinas, e a primeira cobre os elementos mínimos para construir um compilador: análise léxica, análise sintática, geração de código e alocação de registradores
    A segunda disciplina trata de como construir um compilador otimizador
  • Já li material relacionado em enorme quantidade, mas esse tipo de conteúdo não estava na maioria deles
    Na prática, seja em compiladores ou interpretadores, o backend quase sempre fica como “exercício para o leitor”
    É difícil imaginar quanta coisa ainda há para descobrir sobre como criar closures, rastrear ambientes, pattern matching, representação de memória e assim por diante
    Tudo que é interessante você precisa ir atrás por conta própria
    P.S.: isso é só o conteúdo de um desses anos: https://gist.githubusercontent.com/mamcx/e1743571b9a1ea163a7...
  • Acho que não especialistas geralmente começam por análise sintática e muitas vezes não chegam a ver o backend
    Li dois livros sobre interpretadores e compiladores, e eles não cobriam muito do backend
    Talvez isso esteja mais próximo de uma disciplina introdutória de backend
  • Então fico me perguntando o que exatamente é avançado. Se cobrir direito eliminação de código morto, fluxo de dados, SSA, seleção de instruções e alocação de registradores, isso já é praticamente 98% do backend

• Existem outros cursos universitários online e autodirigidos de ciência da computação nesse estilo?

  • Existem dezenas. Basta pesquisar por “mooc”
    Alguns professores também publicam aulas e tarefas fora da estrutura de “mooc”
    Já tive professor que respondeu quando fiz perguntas nos comentários. Às vezes a internet ainda é bem legal

• Comparado com Writing a C compiler, da Nora Sandler, como muda o ganho que o leitor pode ter?

  • Esse livro é mais próximo do que você obteria em um curso de compiladores de graduação, enquanto este curso cobre conteúdo mais avançado
    Se você é iniciante ou está estudando por hobby, é melhor começar por esse livro ou por material de nível parecido e depois tentar este curso enquanto preenche as lacunas

• Existe também algum curso autoguiado de compiladores básicos para ver antes de entrar no nível avançado?

  • Gosto da estrutura de Essentials of Compilation [1][2] e Writing a C Compiler [3]
    Se você quiser começar por interpretadores, Essentials of Programming Languages [4] é bom
    Reconheço que Crafting Interpreters é popular aqui e em outros lugares, mas pessoalmente não gosto. Ainda assim, outras pessoas gostam, então vale a pena tentar, e dá para ler de graça
    EOC e EOPL são um pouco acadêmicos, mas, exceto para quem se incomoda com Scheme e Racket, acho que são bastante acessíveis. A versão em Python de EOC reduz esse problema
    Depois disso, livros de compiladores mais profundos e acadêmicos ficam bem mais fáceis de abordar
    [1] https://mitpress.mit.edu/9780262047760/essentials-of-compila... - versão em Racket, com versão de acesso aberto
    [2] https://mitpress.mit.edu/9780262048248/essentials-of-compila... - versão em Python, com versão de acesso aberto
    [3] https://nostarch.com/writing-c-compiler - permite escolher a linguagem de implementação
    [4] https://mitpress.mit.edu/9780262062794/essentials-of-program... - em Scheme, mas pode ser usado no Racket
  • Recomendo olhar Crafting Interpreters [1]
    É dividido em duas partes, e a primeira constrói um interpretador de percurso de árvore em Java antes de avançar para uma versão escrita em C
    1. https://craftinginterpreters.com/
  • Não testei pessoalmente, mas existe “the-super-tiny-compiler”:
    https://github.com/jamiebuilds/the-super-tiny-compiler
  • É antigo, mas eu recomendaria começar pelo clássico de David Gries, Compiler Construction for Digital Computers
    Junto com alguns dos livros modernos recomendados aqui, isso deve ser suficiente
    David Gries - https://www.cs.cornell.edu/gries/ e https://en.wikipedia.org/wiki/David_Gries
    O cientista da computação neerlandês Dick Grune escreveu sobre Compiler Construction for Digital Computers: “várias gerações de criadores de compiladores cresceram com este livro, e não se arrependeram”
    O próprio Dick Grune também é conhecido por livros sobre compiladores e linguagens de programação - https://dickgrune.com/index.html e https://en.wikipedia.org/wiki/Dick_Grune

• Vi um podcast sobre o compilador Rust e acho que disseram que, em algum ponto, entra um algoritmo de aprendizado de máquina para decidir se um código pode derrubar o sistema

  • Nunca ouvi falar disso e tenho quase certeza de que está errado. Claro, “aprendizado de máquina” é um termo amplo
    Você tem alguma fonte?

• Estou realmente curioso sobre o que alexia massalin anda fazendo hoje em dia além de receber royalties de patente do microunity