Take a detour: Kaleidoscope

在 MP1 中, 我们实现了一个 Cool 语言的前端, 通过这个前端, 就能把 Cool 语言的源程序文件变成对应的 AST. 在之后的 MP2 中, 会在 MP1 的基础上生成源程序对应的 LLVM IR 格式的中间代码.

本文的目的是, 通过引导大家阅读 LLVM 官网上的一个实现语言 Kaleidoscope 的例子, 让大家熟悉 LLVM IR 和 LLVM库的使用. 在此之前, 先简要介绍一下 LLVM.

LLVM 源码简介

clang 为 LLVM 编译器提供C/C++/Objective C/ObjectiveC++的前端. LLVM 把编译器的基本功能做成了库, 方便了对这些功能的复用 (而 GCC 的代码很难复用, 而且受 GPL 限制) . 利用 LLVM 的库，可以实现自己的语言的编译器，开展程序分析和变换、程序优化等工作.

LLVM 的库（XXX库的静态库文件名为libXXX.a）按源文件的文件夹分, 有下面这些（其中头文件在　include/llvm/ 下，源程序文件在lib/下）：

IR/ : 编译生成 LLVMCore 库, 包含关于 LLVM IR 的函数, 负责 IR construction (包括 data layout、basic blocks、function) 以及 IR verifier. 我们会调用这个库中的函数来生成 IR 代码, 而不是用printf来手工输出. 这个库的说明见 Programmers Manual : The Core LLVM Class Hierarchy Reference
ADT/(在　include/llvm/ 下): 包含一些抽象数据结构的声明, 在整个 LLVM 项目中都会被用到. LLVM 自定义了许多基础的数据结构, 如链表、集合等. 使用说明见 Programmers Manual: Picking the Right Data Structure for a Task
Support/ : 编译生成 LLVMSupport 库，提供一些 general utilities，比如字符、文件、DWARF 格式的 Debug 信息等, 在 LLVM 中大量使用. Programmers Manual: Important and usefull LLVM APIs 里有对其中个别 API 的介绍
TableGen/ : 该目录下的源程序编译后生成 llvm-tblgen 可执行程序(在 bin 目录下, 可能没有链接到系统路径), 用于翻译TableGen 文件(*.tb). TableGen 用来记录 domain-specific 信息, 如特定处理器架构的寄存器布局等. 生成的文件主要在 lib/Target/ 中使用. 利用 TableGen, 可以实现Target-independent Code Generator. 除了用于代码生成，clang 的报错信息也使用了 TableGen. 文档见 TableGen.
Analysis/ : 编译生成 LLVMAnalysis 库，提供各种 IR 分析遍, 例如 alias analysis、dependence analysis、打印 call graph、 memory dependence analysis 等.
Transforms/ : 编译生成 LLVMInstrumentation、LLVMipo、LLVMScalarOpts、LLVMTransformUtils 等库，提供多种IR 上的程序变换遍以及用于程序变换的utilities, 例如死代码消除、constant propagation、loop invariant code motion、loop strength reduction、loop unroll、promote memory to register 等.

LLVM’s Analysis and Transform Passes 列举了所有的LLVM IR上的分析和变换 passes
MC/ : Machine Code相关的表示与使用接口, 包含 assembly 和 disassembly 等子项目. 编译后生成可执行文件 llvm-mc , Intro to the LLVM MC Project(2010)这篇博客对MC 做了介绍

其他未列出的目录暂时用不到, 或者看名字也能猜出其含义.

Kaleidoscope 阅读

词法分析

阅读教程 Implementing a language with LLVM 的第一章, 了解Kaleidoscope 语言的设计和词法分析的代码.

在 LLVM 的源码里面也有 Kaleidoscope 的源码, 位于/examples/Kaleidoscope.

你可以直接使用 build 工具 (make, ninja) 来编译，命令类似于 make Kaleidoscope-Ch2 , ninja Kaleidoscope-Ch2.
如果使用IDE，则需要修改 target 的设置，然后再 build.

如果 target 设置为 Kaleidoscope, 比如执行 make Kaleidoscope, 会生成一些我们用不到的程序. e.g. BuildingAJIT-Ch1
然后，在你的 build/bin (或 build/Debug/bin) 目录下执行 ./Kaleidoscope-Ch2 就能运行词法分析器了.

回答下列问题 :

解释函数 gettok() 如何向调用者传递 token 类别、token 语义值（数字值、变量名）

语法分析和 AST 的构建

阅读教程的第二章, 理解 parser 是如何工作的. 这里的实现不同于在 MP1 中的做法, 而是采用手工编写的递归下降的语法分析器.

回答下列问题：

解释 ExprAST 里的 virtual 的作用，在继承时的原理（解释 vtable).virtual 在 MP1 的 support code 里面也出现了. 这个问题是希望大家理解 C++ 的继承.
解释代码里的 <std::unique_ptr> 和为什么要使用它？
阅读 src/toy.cpp 中的 MainLoop 及其调用的函数. 阅读 HandleDefinition 和 HandleTopLevelExpression ，忽略 Codegen 部分，说明两者对应的 AST 结构.
Kaleidoscope 如何在 Lexer 和 Parser 间传递信息？（token、语义值、用什么函数和变量）
Kaleidoscope 如何处理算符优先级（重点解释 ParseBinOpRHS ）？解释a*b*c、a*b+c、a+b*c分别是如何被分析处理的？
解释 Error、ErrorP 的作用，举例说明它们在语法分析中的应用。
Kaleidoscope 不支持声明变量和给变量赋值，那么变量的作用是什么？

中间代码生成

阅读 LLVM 教程的第三章. 从这里开始才真正涉及到 LLVM, 这里使用了 LLVMCore 库来生成 LLVM IR. LLVM IR的说明详见 LLVM Language Reference Manual.