MP2

MP2 要求为 Cool 语言的一个子集实现编译器的LLVM中间代码生成阶段. 该子集能表示仅由单个名为Main.main()的无参函数组成的 Cool 程序.

0. 预备练习：LLVM 指令的熟悉

下载 llvm-examples.tar.gz, 针对其中 llvm-examples/ 目录中的 C 程序（fib.c 除外），使用 make all 将它们编译成 LLVM IR. 你将看到每个C程序有对应的 .ll 文件
使用 llvm-as < printf .ll | lli 运行 printf.ll
手工将 llvm-examples/fib.c 翻译成 LLVM IR，不能使用LLVM 前端
- 用 getelementptr 来索引数组
- 参考前面的 C 文件和其对应的 ll 文件，理解如何编写函数声明、全局变量、printf 和 getelementptr.
提交要求:
- 预备练习的作业提交到git库中的 homework/mp20 下
- 提交内容包括:
  - 手工翻译得到的LLVM IR文件fib-m.ll
  - Makefile: 包含编译fib-m.ll得到可执行文件的目标fib-m, 以及直接编译fib.c得到可执行文件的目标fib
  - fib.md(txt): 说明在你手工编写中遇到的问题及处理对策、以及你认为翻译中比较重要的部分

1. COOL 语言子集

Figure 1 中定义的语言子集中没有包含 Cool 的以下语言特征：方法和方法调用、属性、继承、构造器、new 和 case. 类Main 是唯一的类，并且类中仅有一个方法 Main.main() : Int. 这个方法是LLVM 中的一个全局函数.

你需要实现的类型只有 Int 和 Bool. 为了从语言中去掉对象, 需要对 Cool 的定型规则做如下两点小改动：

可以假设条件表达式的两个分支具有有相同的类型 (都是Int 或都是Bool). 从而整个条件表达式的类型就是分支的类型, 即Int 或 Bool.
loop 表达式的类型为 Int, 并且值为 0 .

MP2不能使用 Cool 的运行库，你也不能使用 IO 类执行输入-输出, 但是可以让 main 函数返回一个结果.

代码生成器使用在 MP1 中构造的 AST，并用 mp2.tar.gz 中提供的静态分析工具 semant 做静态检查. 代码生成器应能产生 LLVM 汇编代码，它忠实实现任一正确的 Cool 程序. 代码生成阶段不需要做错误恢复, Cool 程序的错误检测已经在编译器的前端中做了.

这次实验比 MP1 更困难, 建议立即开始.

2. MP2 distribution

*mp2.tar.gz* 可以在在网上下载, 直接通过 git 分发吧

mp2 目录下包含一个介绍所给框架代码布局与代码生成器结构 README, 在做之前请先阅读.

mp2/src 下的框架代码是你要修改的部分, 其他目录的代码请不要修改. 该目录下包含这些文件:

cgen.cc: 该文件包含代码生成器的代码, 它已经提供了代码生成的一部分实现，阅读理解这部分代码将有助于你编写代码生成器的剩余部分的代码. 这部分代码包含对从 AST 构建类继承图代码的调用.
cgen.h: 这是代码生成器的头文件，其中提供了实现继承图的类. 你可以在这个文件里添加你想添加的.
cool-tree.handcode.h: 这个文件包含 AST 节点类的声明, 你可以通过修改这个文件给 cool-tree.h 中的类增加域声明. 这个文件里定义的宏会被 cool-support/include/cool-tree.h 包含.
请阅读 cool-tree.handcode.h 和 cool-tree.h, 理解它们之间的关系，以及在描述 AST 节点类的特征. 例如, 如果你想在 Feature_class 里加上一个纯虚函数 void addMe(int), 在它的子类里面加上这个虚函数的实现. 你需要在宏Feature_EXTRAS 里添加 virtual void addMe(int)=0, 在 Feature_SHARED_EXTRAS 里添加 void addMe(int);.
Makefile: 这个文件是 src/ 目录的 Makefile.
value_printer.{cc,h}, operand.{cc,h}: 这些文件包含了一个用来打印简单 LLVM 指令的库.
coolrt.{c,h}: 这些文件提供 COOL 运行时库的实现, 在MP2中不会用到.

输入make cgen-1 可以编译你的代码生成器，它会编译 cool-support 目录中的文件并将这些目标文件链接到你的程序中.

注意, cgen.{h,cc} 使用条件编译来判定宏 MP3 是否定义以构建两个不同的程序. 在make cgen-1 时，宏 MP3未定义, 你不需要对宏 MP3定义的代码区域中添加代码.

tools-bin 目录下是一些二进制工具，如 lexer、 parser、 semant.

cool-support/src 和 cool-support/include 目录下也应该看一看, cgen_supp.cc 包含一些可以使用的函数.

reference-cgen-1-binary.tar.gz 是提供的参考代码生成器.

3. 测试代码生成器

mp2/test-1/ 目录是用于测试你的代码生成器的地方. 你需要编写自己的测试例子来测试你的编译器. 建议你先用分离的简单例子测试, 如一个常量、2个常量上的简单算术运算，然后再用更复杂的表达式测试. 希望你尽量让你编写的测试例子保持简洁.

这个目录下有自己的 Makefile, 它提供如下一些编译目标:

make file.ll: 编译Cool程序文件 file.cl 到LLVM 汇编码
make file.bc: 从 file.ll 创建LLVM 字节码
make file.exe: 从 file.bc 创建链接后的可执行文件
make file.out: 执行可执行文件，将结果输出到 file.out
make file.verigy: 验证你的LLVM 代码是否符合LLVM 语言的规定
make file-opt.bc: 从 file.exe.bc 创建优化后的LLVM字节码文件，从而你可以了解 LLVM 是否能优化你的代码

4. 设计代码生成器

代码生成器可以有多种实现可能. 一种合理的做法是将代码生成分为两遍, 即所提供的框架代码中采用的方法. 第一遍确定每个类的对象内存布局, 即用哪些 LLVM 数据类型来创建每个类、并为程序中出现的所有常量生成 LLVM 常量. 第二遍利用第一遍得到的信息递归地遍历程序中的每种结构特征，为每个表达式生成 LLVM 代码.

以下列出一些你在设计代码生成器时必须考虑的要点:

理解 Cool 程序的运行时语义.　CoolAid (或这里) 有对 Cool 的非形式描述和形式描述.
理解 LLVM 的指令、类型和声明.
仔细思考对象、let 变量和临时变量在内存中如何分配以及分配在哪里.
使用简单的树遍历器生成未优化的 LLVM 代码. 重点是针对每个树节点，生成局部尽量优化的代码，例如避免不必要的类型转换, 使用 getelementptr 来引用对象中的域, 使用合适的聚合类型等.
忽略 Cool 的垃圾回收. 需要内存时直接调用i8* @malloc(i32) 获取堆上空间, 不用释放这些对象.

5. 表示 COOL 语言中的对象和值

你的编译器设计的重点是为COOL 语言中的对象和值 (包括变量、堆对象和临时变量) 开发正确的表示和内存分配策略. MP2 中只考虑 Int 和 Bool 值, 这些值只会作为变量或临时变量存在.

下面是一些指导建议:

基本(primitive)类型的的值应该直接表示为虚拟寄存器 (类型为 i32 for Int, i1 for Bool)
Int 或 Bool 只有在实际的对象操作需要作用在这些类型的数据上时, 才需要放在堆上. 普通的算术运算操作、对Int 或 Bool类型的变量进行赋值都不是对象操作. MP2中暂时还没有对象操作.
当 Int 或 Bool 值必须被放在堆上时，在执行对象操作前, 你需要给它分配一个堆上的对象, 把寄存器中的值放在这个堆对象中. 这称作 "boxing".
当Int 或 Bool 对象需要再次被当作一个 primitive 类型使用时(比如算术运算)，你需要把它的值从对象中取出来, 放到LLVM寄存器里面. 这称作 "unboxing".
MP2 中是不需要把 Int 和 Bool 放到堆上的，它们总是保存在寄存器中.
同理, @Main_main 的返回值是 i32 而不是 i32*
let-变量可以看作是值(对象)的名字(指针). 因为作用域是局部的, 即使 let- 变量是 primitive type(i32 或 i1), 也可以使用alloca 指令在栈上分配空间. 再用 mem2reg(LLVM 的优化) 把它变成 SSA 寄存器. alloca 必须放在 let-block 的开始才能使用这个优化.

6. 实验攻略

因为实验的工作量比较大, 建议按下面的步骤来构建你的编译器:

先生成 @main(), 这样在前期就能对代码生成器进行测试.
实现 Int 和 Bool 的常数. 作为LLVM 的 i32 和 i1 生成它们, 然后测试.
实现算术和比较运算, 你还可以实现 block 表达式({1 +2 ; 2 <= 1}). 测试!
按照上一节的指示实现 let. 在环境中记录变量名和内存地址的绑定关系. 测试!
实现赋值语句. 考虑赋值的左边（LHS）和右边（RHS）, 把什么东西复制过去了. 测试!
实现 loop 和 if-then-else. 这里需要了解 LLVM 的 BasicBlocks. 本文最后会给出参考.
最后, 实现运行时的错误处理. CoolAid 最后一页列出了几个检查. 现在能做的只有除零. 如果出现除零错误, 你应该直接调用 abort(). 这个函数已经在框架代码里设置.
彻底地测试你的编译器.

7. 提交要求

PBXXXXXXXX                     : git 根目录
├── doc/                         存放MP1、MP2的设计调测分析报告
└── mp2/
    ├── Makefile.common
    ├── README
    ├── cool-support
    ├── src
    │   ├── Makefile
    │   ├── cgen.cc               : 这个
    │   ├── cgen.h                : 这个
    │   ├── cool-tree.handcode.h  : 还有这个, 只有这三个可以修改.
    │   ├── coolrt.c
    │   ├── coolrt.h
    │   ├── operand.cc
    │   ├── operand.h
    │   ├── stringtab.handcode.h
    │   ├── value_printer.cc
    │   └── value_printer.h
    ├── test-1
    ├── test-2
    └── tools-bin

8. 参考

关于 Basic Block 等 LLVM 设施的使用, 可以参考 Kaleidoscope 的做法. 第五章有Kaleidoscope 对分支和循环的实现.

还有一个 Stacker 语言, 也是使用 LLVM 实现的一个语言. 似乎 LLVM 2.3 以后的文档里没包含这个文章了.

MP2

MP2