Archipelago群岛 · 公开课笔记

COURSE · 6.1100

6.1100 计算机语言工程

课程以「Decaf 源程序 → 可执行 x86-64 代码」为完整工程主线，串联解析、IR、语义检查、代码生成与优化。 学习重点不只是单个算法，而是如何选择程序表示，让正确性、可分析性与高效代码生成能逐层衔接。 建议按 L1–L6 完成前端与未优化后端，再读 L7–L12 的数据流、循环、寄存器分配…

12 篇编号讲义 · 12 篇内容 · 46 个已标注 tags
DOMAIN
编程语言
STATUS
complete
COURSE ID
6.1100
RELATIONS
暂无结构化数据

LECTURE NOTES · 12

来自目录与 frontmatter
#TITLESTATUSTAGSUPDATED
01编译器概览（Overview of Compilation）lec1完成302用正则表达式与上下文无关文法规范语言lec2完成403自顶向下分析（Top-Down Parsing）lec3完成404中间表示（OPP）lec4完成405语义分析（Semantic Analysis）lec5完成406代码生成lec6完成407程序分析与优化（基本块内）lec7完成408数据流分析（Dataflow Analysis）lec8完成409循环优化（Loop Optimizations）lec9完成410寄存器分配（Register Allocation）lec10完成511并行化（Parallelization）lec11完成412数据流分析的理论基础（Foundations of Dataflow Analysis）lec12完成4

课程资料与说明

来自课程 index.md

6.1100 计算机语言工程

MIT 6.1100 / 6.035 Computer Language Engineering · Spring 2025 · Martin Rinard

TL;DR

  • 课程以「Decaf 源程序 → 可执行 x86-64 代码」为完整工程主线，串联解析、IR、语义检查、代码生成与优化。
  • 学习重点不只是单个算法，而是如何选择程序表示，让正确性、可分析性与高效代码生成能逐层衔接。
  • 建议按 L1–L6 完成前端与未优化后端，再读 L7–L12 的数据流、循环、寄存器分配和并行化。

资料来源与整理说明

  • 官方入口：课程大纲、课程进度、逐讲 lecture notes / slides与编译器项目。
  • 各讲以官方 slides 为主来源，并吸收与本讲直接相关的 re-lecture 讲义和 recitation 材料；页面 frontmatter 保留对应主讲义链接。
  • 官网列出的课堂录像位于 MIT Panopto，需登录才能访问，当前无法取得可公开核验的 transcript；因此本轮没有把未核验的字幕当作课程原文。

先行条件

6.1020/6.031 Software Construction

6.1903 Introduction to Low-level Programming in C and Assembly

6.1910/6.004 Computation Structures

课程定位与范围

分析与实现高级编程语言相关的问题。编译器的基本概念、功能和结构。理论与实践的互动。使用工具构建软件。包括一个关于编译器设计和实现项目。

主讲教师：Martin Rinard。

资源

推荐教材

这门课没有必备教材，但如果你坚持，我们认为这是一本不错的参考教材：

Cooper， Keith D.， 和 Torczon， Linda，《Engineering a Compiler》，第3版，Morgan Kaufmann，2022 年

  • 一本帮助理解现代编译器的新型参考教材。涵盖本课程中提到的许多优化内容（如数据流、指令调度、寄存器分配），以及现代编译器中常见的一些高级优化（如静态单赋值（SSA））。

你可能感兴趣的其他编译器教材：

  • 虎书： 一本经典之作。引导你完成一个有深度的代码组织编译器项目。
  • 龙书： 这是一篇非常非常厚重的经典参考文献，讲述为类 C 语言（例如 Decaf）编写优化编译器的过程。
  • 鲸书：全面涵盖高级编译器优化。
  • 《Lisp in Small Pieces》, 1996： 这是一本非常酷的书，从零开始构建了多个解释器，展示了语言设计选择之间的相互作用。
  • 《Crafting Interpretres》, 2021：我们对想学习编译器一般知识的人（即本课程之外）的默认推荐。

参考文献

你会发现这些参考文献对编写编译器很有帮助。

  1. 完整的 Intel x64 manual——包含所有细节的官方PDF。
  2. x86 和 amd64 指令参考——由 Félix Cloutier 根据英特尔手册导出的可导航参考
  3. x86 维基 — 关于 x86 指令工作原理的好入门介绍
  4. x64 速查表——布朗大学CS033中详细介绍寄存器和汇编命令的列表和表格
  5. Agner Fog 的优化页面——这是一个非常有用的参考页面，里面有关于如何优化x86-64代码的手册。特别是，看看指令表。
  6. Godbolt —— 允许你输入 C 代码，并提供各种编译器（如 gcc 和 clang）的逐行汇编输出，非常有用，有助于了解如何将某些操作转换为汇编。

工具

  1. Shell
    1. The Missing Semester of Your CS Education — Learn about the shell and the terminal, then you look like a pro.
  2. Scala
    1. Tour of Scala
    2. Scala Book
    3. Scala Patterns for Compiler Design

其他灵感来源

概述

  1. LLVM compiler architecture
  2. GCC compiler architecture

博客

  1. Russ Cox 的博客——Russ是Go语言的开发者之一，Go是一种流行语言。
  2. Matt Might 的博客——Matt是犹他大学的教授，写过一些非常有趣的文章（例如《Yacc已经死了》）
  3. Ralf 的胡言乱语——Ralf写了很多热门博客文章，探讨C++和Rust等系统语言背后的复杂性。
  4. 学术界的嵌入——同理。

论文

  1. 寄存器分配与通过图着色溢出——G.J. Chaitin / 1982。关于简单寄存器分配的优秀（简短）论文。
  2. 线性扫描寄存器分配
  3. 《迭代寄存器融合》— Lal George / 1996。对柴廷设计提出了改进和替代方案。如果 Chaitin 风格（+/-Briggs）寄存器分配还不够，这篇论文值得一读——实际上，理解权衡本身就很有价值
  4. superword 级 并行性结合循环展开，是一种实现向量化编译器的简单方法

理论

  1. Order Theory for Computer Scientists——Matt Might 关于数据流分析基础的总结。
  2. Davey， B. A. 和 H. A. Priestley，Introduction to Lattices and Order，第二版，剑桥大学出版社，2002年。

Decaf 编译器项目

项目的真实主线是把 C 语言子集 Decaf 编译为可执行的 x86-64 代码，不包含 MITScript 解释器或垃圾回收器。五个阶段对应课程的纵向切片：

  1. 词法与语法分析：把 Decaf 字符流变成 token 和语法树，报告词法 / 语法错误。
  2. IR 与语义检查：建立符号表与中间表示，检查声明、类型和函数调用等上下文相关约束。
  3. 未优化代码生成：先以正确性为目标，将 IR 降级为符合 ABI 的 x86-64 汇编。
  4. 数据流优化：建立可复用的数据流框架，并用必需的优化 pass 验证它。
  5. 开放式优化：根据基准测试选择常量传播、CSE、循环不变式外提、寄存器分配、窥孔优化或并行化等技术。

相关课程

你可能会发现其他公开课程的讲座幻灯片或笔记很有用，尤其是在项目后期阶段：

如果你渴望更高级的内容，可以看看这个：

中文课程：

讲义目录

单元讲义学习主线
全景与前端L1 编译器概览 · L2 语言规范 · L3 自顶向下分析从源语言到 token、语法树和 AST
IR 与语义L4 中间表示 · L5 语义分析用符号表、类型与 IR 固化程序含义
后端L6 代码生成结构化 IR、CFG、SSA 与 x86-64
程序分析L7 块内优化 · L8 数据流分析 · L12 数据流理论从局部事实到 CFG 上的不动点
高级优化L9 循环优化 · L10 寄存器分配 · L11 并行化利用支配、活跃性与依赖信息改写程序