CS 6120: 高度コンパイラ自主学習オンライン講座（2020）

• Cornell CSの博士課程レベル講義 CS 6120 は、コンパイラとプログラミング言語実装を体系的に学びたい人に向けて、中間表現、データフロー、最適化、並列化、JIT、ガベージコレクションまでを一連の流れで提供する
• 自主学習版は、仮想的な大学で 4単位・成績なし で履修する形式で、動画・講義ノート・論文読解・実装課題を線形スケジュールに沿って進めるようになっている
• 実習では LLVM と教育用IRの Bril を使い、抽象的なコンパイラ概念を実際のコード作成で確認できるよう設計されている
• 実際のCornellの授業と異なり、課題締切は無視できるが、Zulipの議論には参加できず、学期末プロジェクトの代わりに自主学習版独自の最終課題が与えられる
• 講座資料はGitHubで オープンソース として公開されており、問題を報告でき、修了後はフィードバックフォームを通じて改善意見を送れる

---

講座構成と受講方法

• CS 6120 は Cornell CS のAdrian Sampsonが作成したプログラミング言語実装の講義
• 汎用コンパイラの基本トピックと研究色のあるトピックをあわせて扱う
  • 中間表現
  • データフロー
  • 古典的最適化
  • 並列化
  • JITコンパイル
  • ガベージコレクション
• 学習は論文読解とオープンソースハック課題へとつながる
  • LLVM を使用
  • 授業用の教育IRである Bril を使用
• 自主学習カリキュラムは、動画視聴と論文読解を組み合わせた 線形スケジュール で構成される
• 一部のレッスンには 実装課題 が含まれており、自由度の高いコーディングを通じて抽象概念を身につける
• 実際のCS 6120と自主学習版には違いがある
  • 課題締切を無視できる
  • Zulipのディスカッションスレッドには参加できない
  • 実際の授業には学期末プロジェクトがある
  • 自主学習版の学期末課題は「コンパイラの魔法で世界を変えること」
• 講座は GitHubでオープンソース公開 されており、問題があればバグ報告できる
• 修了後は フィードバックフォーム に記入できる

レッスンと読み物の流れ

• 導入とプログラム表現

  • 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

• 解析と最適化の基礎

  • 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とループ・間接手続き解析

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

• メモリ管理と動的コンパイラ

  • 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

• 並列性と高速コンパイラ

  • 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
    • タイトルのみ一覧に含まれている

[GN⁺]

Hacker Newsの意見

• 動的コンパイラの部分は、ほぼ全面的にトレースコンパイルの話に近い。一般的にトレースコンパイルは行き止まりで、何度も捨てられてきた
  ここでより重要な概念は、タイプフィードバック、投機実行と逆最適化、高速なコンパイラと階層化だと思う
  講義全体は良さそうで、これだけ多くの資料がオンラインで公開されているのも素晴らしい

  • トレーシングは歴史的に見て、組織原理としては実用的でないことが明らかになったが、学んでおくと視野を広げてくれる概念だと思う
    言われているように、業界で実際にうまく動くものについて、もう少し文脈を補いたい
  • PyTorchのtorch.compileに取り組んでいるが、これもトレーシングコンパイラだ
    ただしこの領域はかなり狭いかもしれず、伝統的なコンパイラともかなり違うので、私たちの仕事の一部を見るとかなり居心地が悪いと感じるかもしれない
  • JAXもトレーシングコンパイラだ
    もちろん、TraceMonkeyやLuaJITとは問題空間が極端に異なることは分かっている
  • TraceMonkeyの論文が博士資格試験の読書リストに入っていて、ちょうどその試験の時期がTraceMonkeyがSpiderMonkeyから削除される時期と重なっていた
    当時の開発者の一人、おそらくJason Orendorffだったと思う人と話したが、トレーシングはうまくいかないと言っていて、限定的な条件では可能かもしれないと見ていた
    ただ、その条件が何だったのかは完全に忘れてしまった
  • トレースコンパイルは行き止まりではない
    LuaJITは大規模なプログラムでも、数億台のサーバーやデバイスでもうまく動いている
    学者ですらこの決まり文句を繰り返し続けているのは本当に残念だ。無知は幸福という言葉を思い出す

• 以前の関連記事:
  CS 6120: Advanced Compilers: The Self-Guided Online Course - https://news.ycombinator.com/item?id=39577878 - 2024年3月、コメント102件
  Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=35130975 - 2023年3月、コメント82件
  Advanced Compilers: Self-Guided Online Course - https://news.ycombinator.com/item?id=25386756 - 2020年12月、コメント232件

• この講義がなぜ上級なのか少し混乱する。大半のトピック、たとえばデッドコード削除、データフロー、支配者解析、SSA形式は、コンパイラの最初の講義に入っていそうに見える

  • 講義番号がかなり規則的なので、「入門コンパイラ」講義が何かを調べられる: https://www.cs.cornell.edu/courses/cs4120/2026sp/?schedule
    短く言えば、コンパイラは実質的に2科目に分かれていて、最初の科目ではコンパイラを作るための最小要素である字句解析、構文解析、コード生成、レジスタ割り当てを扱う
    2つ目の科目は、最適化コンパイラを作る方法に当たる
  • 関連資料をものすごくたくさん読んできたが、そうした内容は大半には含まれていなかった
    実際、コンパイラでもインタプリタでも、バックエンドはほとんど常に「読者に任せる練習問題」のままだ
    クロージャを作る方法、環境を追跡する方法、パターンマッチング、メモリ表現など、まだ見つけ出すべきことがどれほど多いか想像しにくいほどだ
    面白いことはすべて自分で見つけなければならない
    追伸: これはそのうちの1年分にすぎない: https://gist.githubusercontent.com/mamcx/e1743571b9a1ea163a7...
  • 非専門家はたいてい構文解析から始めて、バックエンドに触れないままになることが多いと思う
    インタプリタとコンパイラの本を2冊読んだが、バックエンドはあまり扱われていなかった
    おそらくバックエンド入門講義に近いのではないかと思う
  • では何が上級なのか気になる。デッドコード削除、データフロー、SSA、命令選択、レジスタ割り当てをきちんと扱えば、実質的に**バックエンドの98%**に近い

• このような自己主導型のオンライン大学レベル計算機科学講義は他にもあるだろうか?

  • 何十個もある。「mooc」で検索すればよい
    一部の教授は「mooc」フレームワークの外でも講義と課題を公開している
    コメントで質問したときに返事をくれた教授もいた。インターネットはまだかなり素敵な場所であることもある

• Nora SandlerのWriting a C compilerと比べたとき、読者が得られる利点はどう違うだろうか?

  • その本は学部レベルのコンパイラ講義で得られる内容により近く、この講義はそれよりさらに上級の内容を扱っている
    初心者や趣味で掘り下げる人なら、その本や同程度の資料から始めて、その後この講義に挑戦しながら抜けを埋めるほうがよい

• 上級段階に入る前に見られる 基礎的なコンパイラ の自習型講義はあるだろうか？

  • Essentials of Compilation [1][2] と Writing a C Compiler [3] の構成が好きです。
    インタプリタから始めたいなら Essentials of Programming Languages [4] が良いです。
    このサイトや他の場所で Crafting Interpreters が人気なのは認めますが、個人的にはあまり好きではありません。それでも他の人には好まれているので、試してみる価値はあり、無料で読めます。
    EOC と EOPL はやや学術寄りですが、Scheme や Racket に抵抗がある人を除けば、かなり取り組みやすいと思います。EOC の Python 版はその問題を和らげてくれます。
    その次には、より深く学術的なコンパイラ本にも入りやすくなります。
    [1] https://mitpress.mit.edu/9780262047760/essentials-of-compila... - Racket 版、オープンアクセス版あり
    [2] https://mitpress.mit.edu/9780262048248/essentials-of-compila... - Python 版、オープンアクセス版あり
    [3] https://nostarch.com/writing-c-compiler - 実装言語を選べる
    [4] https://mitpress.mit.edu/9780262062794/essentials-of-program... - Scheme だが Racket で利用可能
  • Crafting Interpreters [1] を見るのを勧めます。
    2部構成で、前半では Java で木走査インタプリタを作り、その後 C で書かれた版へ進みます。
    1. https://craftinginterpreters.com/
  • 自分では試していませんが、“the-super-tiny-compiler” もあります:
    https://github.com/jamiebuilds/the-super-tiny-compiler
  • 古いですが古典として、David Gries の Compiler Construction for Digital Computers から始めるのを勧めます。
    ここで勧められている現代的な本を何冊か併せて読めば十分でしょう。
    David Gries - https://www.cs.cornell.edu/gries/ および https://en.wikipedia.org/wiki/David_Gries
    オランダの計算機科学者 Dick Grune は Compiler Construction for Digital Computers について、「何世代ものコンパイラ作者がこの本とともに育ち、しかも彼らはそれを後悔しなかった」と書いています。
    Dick Grune 自身もコンパイラと言語処理系の本で有名です - https://dickgrune.com/index.html および https://en.wikipedia.org/wiki/Dick_Grune

• Rust コンパイラを扱ったポッドキャストを見たのですが、システムをクラッシュさせうるコードかどうかを判断する際、どこかの段階で 機械学習アルゴリズム が使われていると言っていた気がします

  • そんな話は聞いたことがなく、ほぼ間違いだと確信しています。もちろん「機械学習」という言葉の範囲は広いですが。
    出典はありますか？

• alexia massalin が最近 microunity の特許ロイヤルティ を受け取る以外に何をしているのか、本当に気になります