实验 2 C1 语言的 LLVM IR 代码生成器

在本实验中，将通过实现一个 syntax tree visitor，为 C1 语言构建 LLVM IR 代码生成器。

2.1 实验要求

2.1.1 Lab2-1预热实验

首先，你要按照Environment一章准备好clang和llvm。然后将llvm-install/bin加入到环境变量PATH中。

在预热实验中，你需要完成以下几个任务。

完成以下 C 语言代码到 LLVM IR 的人工翻译。
```
int fib(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fib(n - 1) + fib(n - 2);
}
int main() {
  int x = 0;
  for (int i = 1; i < 8; ++i) {
    x += fib(i);
  }
  return x;
}
```
在此任务中，你可以参考 clang -S -emit-llvm 时的输出。

编写的 LLVM IR 请存放于<your-repo>/lab2/fib.ll中。你应当使用lli命令测试其结果，正确的输出中应有 return code 为 33。在 bash 中你可以通过echo $?查看 return code。
编写一个 gen_fib.cpp，使用 IRBuilder 构建你在上一题中所编写的 LLVM IR 并打印。
你可以参考公共仓库中的 llvm-irgen-example。你需要思考BasicBlock的使用，以正确生成输出。

编写的程序请存放于 <your-repo>/lab2/gen_fib.cpp 中。你应当通过 Makefile 或 CMake 完成一个配套的自动构建；对于 Makefile，你可以使用llvm-config获取 LLVM 安装信息；对于 CMake，你可以参考 Embedding LLVM in your project。

2.1.2 Lab2-2实验要求和提交细则

Lab2-2的实验代码在<your repo>/c1interpreter中完成。本次实验中你要完成的内容有两项：

完成assembly_builder.cpp 中的所有空白 visit 方法，注意添加充分的,适当的注释。
在 <your repo>/c1interpreter 下建立 test 文件夹，其中存放你的测试样例。请确保你的程序至少在你的测试样例下工作正常，并尽可能让你的测试样例覆盖面更广。
在 <your repo>/c1interpreter/doc/ 下增加lab2-2.md，描述实验中遇到的问题、分析和设计，注意长短适中，逻辑合理。

请不要修改除此以外的任何仓库内容。

本次实验中，你可以使用 c1recognizer reference implementation 作为 c1recognizer 的实现，以避免一些问题。实验批改中也会使用此实现，不会将上一次的错误延伸至本次评分中。

本次实验的参考实现以及需要的链接库,参见仓库.本参考实现没有某些语义检查的内容.

2.2 LLVM IR 及其构建

2.2.1 LLVM IR

LLVM IR 是 LLVM 所约定的、与硬件架构无关的中间代码表示。它通过一些抽象的指令来表达程序，其具体内容参见 Reference Manual。不推荐你一开始从头到尾详细阅读 Reference Manual；而是建议你先浏览其中的主要内容，然后开展实验，并在遇到有对LLVM IR不理解的时候再在其中查找相关说明。

LLVM 在定义了 IR 规范的同时也提供了用于表示和构建 IR 的库和相关数据结构。在你的 LLVM 安装目录下的 include/llvm/IR 中有与之相关的头文件。指令相关的数据结构和操作接口的定义参见 Instruction.h、Instruction.def、 InstrTypes.h 和 Instructions.h；其实现参见 Instruction.cpp 和 Instructions.cpp。

2.2.2 LLVM IRBuilder

LLVM IR构建相关的主要内容位于 IRBuilder.h 中, 其中类 IRBuilder及其超类中声明的各个 Create* 方法与 LLVM IR 的指令相对应，例如 CreateRetVoid 用于创建返回值为空的 ReturnInst 指令。

在 LLVM 的 Tutorial 中给出了较为详细的样例介绍 IRBuilder 的创建和使用，请参考并理解。

实验2代码框架 c1interpreter 中，已经提供了对IRBuilder 实例的构建，参见 main.cpp 的第70-74行，你需要阅读理解其间调用的相关代码。

2.2.3 IRBuilder 的工作逻辑

为了消除一些可能出现的疑惑，这里简单解释一下 IRBuilder 的工作逻辑：

LLVM IR 在内存中是以若干条顺序执行（中间无分支）的指令序列构成的基本块 BasicBlock（以下简称 BB）为单位来组织的。一个函数 Function 包含有多个 BB。对于含有分支指令的情形，一般是在某一个 BB 结尾处放一条分支语句（br等）并跳转至其它 BB。在 LLVM 框架中，生成 BB 的接口是 BasicBlock::Create。
IRBuilder 的工作方式是，首先指定当前 BB，然后逐指令插入（如调用 builder.CreateAdd 插入一条加指令）。当完成了一个 BB 后，通过 builder.SetInsertPoint 更改当前 BB。
IRBuilder 在每一次插入新指令时，如果这一指令会产生结果（这是一个新的静态单赋值 Static Single Assignment 变量），则用于创建和插入指令的方法调用会有一个返回值，类型为 llvm::Value，用以代表这一 SSA value。

2.3 Visitor Pattern

在Lab1的visitor pattern一节,以及第三次习题课的visitor pattern一节中，我们给出了对于visitor pattern的比较具体的例子以及描述。

在Lab1中，你已经通过实现和使用访问者类 syntax_tree_builder，在 Parse Tree 上遍历，来构建 Syntax Tree

注意，如果你仔细观察 syntax_tree.h 中的 syntax_tree_visitor 类声明，你会发现 visit 方法并没有返回值，也没有一个通用的 visit 方法用于处理子树（而是使用 subtree->accept(*this)来调用访问者 *this 访问子树 subtree ）。

2.4 Assembly Builder

类 assembly_builder 是一个实现 syntax_tree_visitor 的访问者类。它维护了 llvm::Module、llvm::IRBuilder 等构建 LLVM IR 所必须的类，并通过一些约定进行代码生成。

2.4.1 assembly_builder 的主要成员

你需要注意理解它的主要成员：

llvm::LLVMContext &context;
llvm::IRBuilder<> builder;
std::unique_ptr<llvm::Module> module;
std::unique_ptr<runtime_info> runtime;

llvm::Value *value_result;
int int_const_result;
double float_const_result;
bool is_result_int;

llvm::Function *current_function;
int bb_count;

bool lval_as_rval;
bool in_global;
bool constexpr_expected;

c1_recognizer::error_reporter &err;
bool error_flag;

...
// Line 108
void enter_scope() {...}
void exit_scope() {...}

std::tuple<llvm::Value *, bool, bool, bool> lookup_variable(std::string name)
{...}

std::unordered_map<std::string, llvm::Function *> functions;

它们的含义和功能如下：

context、builder、module 会在各种 LLVM 接口中要求传入，包括指针形式和引用形式。请使用 module.get() 来获取 module 的指针，否则会引起 unique_ptr 的 deconstruction。
value_result 和 int_const_result, float_const_result 是用来保存表达式结果的。对于需要常量表达式的情形（包括全局变量初始化和数组长度），结果在 int_const_result, float_const_result 中保存；否则在 value_result 中保存通过 IRBuilder 构建出的匿名变量。
current_function 保存了当前正在生成的函数。这对于 if 和 while 语句的编译会有帮助，在为这些语句创建新的 BasicBlock 时需要传入这一指针。
bb_count 用于对当前函数中的 BasicBlock 数量进行计数，用于对函数中的各个 BasicBlock 命名。
lval_as_rval 用于表示当前上下文以何种方式引用正要处理的左值。如为真，则 visit(lval_syntax &) 应对得到的左值地址取值；否则不进行取值。
in_global 用于表示当前是否处于全局区域。这是为了区分变量声明语句 var_def_stmt_syntax 在全局和局部的不同行为而设立的 flag。
err用于报错。通过调用 err.error(node.line, node.pos, "explanation"); 进行一次报错。这里 node 是 syntax tree 上的一个节点。
error_flag 用于标记错误状态。它在开始生成前被置为 false，当发现语义错误时，置为 true，结束时检查之，可以防止未通过语义检查的程序被输出或执行。
enter_scope 和 exit_scope 用于维护作用域。当作用域开始时，创建新的数据结构以待新作用域中的变量加入；结束时，销毁当前作用域的符号，并将当前作用域更新回退到外围最近的作用域。
lookup_variable 用于查找变量。传入变量名，返回为一个四元组，成员依次为变量地址在 LLVM 数据结构中的表示、是否为常量、是否为数组、是否为整型。
declare_variable 用于声明新变量。传入变量名和变量地址在 LLVM 数据结构中的表示、是否为常量、是否为数组、是否为整型，返回值为是否成功声明。
functions 用于维护当前所有的函数，为函数名到 LLVM 函数对象指针的映射。

注意：这其中的 flag 仅仅是为了方便你整理思路而预设的，你需要在你的代码中的合适位置为它们赋值。 它们的初始值在 assembly_builder.h 中的 assembly_builder::build 方法中可以看到。

2.4.2 语义检查

在代码生成过程中，可以顺便进行语义检查。

类型检查

C1 语言的类型共九种：函数、常量整型、常量整型数组、变量整型、变量整型数组、常量浮点型、常量浮点型数组、变量浮点型、变量浮点型数组，类型检查发生在函数调用、赋值、左值取值时。根据各类型的语义，你需要处理类型错误，具体来说：
1. 被调用的函数不存在
2. 赋值语句中的左值所引用的量为常量
3. 左值表达式中进行索引时，被索引的符号不是数组，或者索引不是整型
整型和浮点型表达式的算术或关系运算、赋值的规则与 C 语言类似。例如，
1. 浮点型表达式之间不能进行 == 或 != 关系运算
2. 整型和浮点型之间进行算术或关系运算，要将整型数转换成浮点型数之后再进行运算
3. 整型和浮点型之间赋值，要按赋值号左边的运算对象的类型对赋值号右边的结果进行类型转换，再进行赋值
当发生错误时，合适的处理方式是报错并忽略这一支子树，返回一个占位标记值，继续处理。你可以使用 assembly_builder::error_flag 作为一个 builder 对象的错误标记，在开始生成时重置为假，结束后检查是否为真；若为真，则清空截至目前已生成的IR代码。
名称重复检查

在遇到函数或变量声明时，你需要检查所声明的函数或变量在当前作用域内是否有重名的函数或变量。

函数的名称冲突通过维护 functions 来检查。

变量的名称冲突通过检查 declare_variable 返回值来检查。若为真，则声明成功，无冲突；否则发生冲突。

由于 C1 语言分别处理函数和变量，你可以不考虑函数、变量之间的名称冲突。

2.4.3 函数创建

调用 Function::Create 创建函数的IR对象时，需要指定函数类型、链接方式、函数名和模块。

由于 C1 语言的函数均没有参数，并且返回类型为空，因此可以固定地按如下方法来创建：

current_function = Function::Create(FunctionType::get(Type::getVoidTy(context), {}, false),
                                    GlobalValue::LinkageTypes::ExternalLinkage,
                                    name, module.get());

函数对象创建后，需要为其准备入口点对应的 BasicBlock。你可以通过调用 BasicBlock::Create 创建 BB，并使用 builder.SetInsertPoint 方法设置好 IRBuilder 的插入点。

在完成对函数内语句的IR指令生成后，别忘了通过调用 IRBuilder::CreateRetVoid 添加返回指令 ret void。

2.4.4 表达式的处理

表达式的处理需要分两种情况进行。

constexpr_expected 为真

此时应当在处理子表达式后, 通过 int_const_result或者float_const_result 取出结果，根据表达式的行为直接计算出常量结果，存回到 int_const_result或者float_const_result 内。

对于字面值，若为整数，则直接将 node.intConst 存入即可；若为浮点数，则直接将 node.floatConst 存入即可。
constexpr_expected为假

此时应当在处理子表达式后，通过 value_result 取出结果，根据表达式的行为调用相应的builder 的成员方法进行代码生成，将生成的匿名变量存回到 value_result 内。

对于整型字面值（整数），应构建一个 ConstantInt 对象：ConstantInt::get(Type::getInt32Ty(context), node.intConst)。

对于浮点型字面值（浮点数），假设C1 编译器用双精度浮点型存储，则应构建一个 ConstantFP 对象：ConstantFP::get(Type::getDoubleTy(context), node.floatConst)。

2.4.5 变量定义的处理

变量定义首先分为局部和全局两种情况。这将由 in_global 这一标志区分。

局部变量

对于局部变量，你应当通过调用 IRBuilder::CreateAlloca 创建 alloca 指令。这一指令能够在栈上分配空间，具体的使用方式请参考文档。你需要思考如何使用 alloca 指令创建变量并获取指向它的指针值。

对于局部变量，无论变量为常量或可变量，其初始化表达式均不要求是常量表达式。
全局变量

对于全局变量，你应当使用 global 指示。它能够在全局区域内声明符号，并在链接时分配数据段空间，具体的使用方式见参考文档。这里给出一个提示：LLVM IR的库接口中与之等价的内容在 llvm::GlobalVariable 类中，你需要使用类似于 new GlobalVariable 的方式在当前 module 中创建一个全局变量定义。GlobalVariable 所代表的值本身也是一个指向变量的指针，因此和 alloca 指令的结果是一致的，可以统一在lval_syntax中处理。

为了简单起见，对于全局变量，无论变量为常量或可变量，其初始化表达式均要求是常量表达式。因为有此要求，C1 的编译中不需要插入比 main 函数早的代码来完成全局变量的初始化，只需要使用构造函数 GlobalVariable::GlobalVariable 中的 Initializer 参数指定初始化的常量值即可；根据变量类型不同，它应为一个 ConstantInt 、ConstantFP 或ConstantArray。

无论对于何种声明，当出现数组声明时，你都需要检查数组长度是否不小于初始化列表长度；若小于，则应通过err.error报错。

此处报错的原因是 clang 和 gcc 的行为是忽视超出部分并报 warning，简化要求起见，报错即可。

变量定义好后，你需要通过 declare_variable 将其加入当前的上下文环境中。

2.4.6 左值的处理

左值若在 constexpr_expected 为真时被引用，应进行报错，因为变量并非常量表达式。这是由 C++ 11 中 constexpr 的定义延伸而来的，甚至不认为全局 const 变量的值是编译时常量。(比如const int m = 1; int a[m] = {m}; 后面两个m都当做是非法的)

左值的使用分为两种情况：作为左值和作为右值使用。这将由 lval_as_rval 这一标志区分。

作为左值使用

即作为被赋值的对象。这时，你应当取出其地址，存入 value_result 中。你需要检查变量的类型，对数组引用进行正确的索引（通过 getelementptr 指令）。
作为右值使用

当作为右值使用时，除了上述步骤外，你还需要将值取出（通过 load指令），然后将取出的值所关联的 Value 指针存入 value_result 中。

请注意，你需要仔细处理常量和数组这两个类型相关的内容。这在上面语义检查一节有详细的介绍。

2.4.7 控制流结构的处理

在 LLVM IR 中，单个 BasicBlock 中最后一条语句应为跳转，包括 ret void（builder.CreateRetVoid）、br（builder.CreateBr等）。对于控制流结构，你需要分析它需要哪几个 BasicBlock 来完成其功能，然后进行这些 BasicBlock 的创建，分别设置 builder 的插入点为这些块（builder.SetInsertPoint）并进行相应的代码生成。别忘了一定有一个 BB 块用作未来的代码生成，即这一控制流结构结束后的语句的 IR 插入点。

BasicBlock 的创建可固定地使用 BasicBlock::Create(context, "BB" + std::to_string(bb_count++), current_function)。

2.4.8 整型和浮点型的类型转换

为了进行必要的整型和浮点型的类型转换,可以通过IRBuilder::CreateFPToSI和IRBuilder::CreateSIToFP进行.

2.5 C1 语言的运行时

为了让生成的 C1 代码能支持标准的输入和输出以方便测试自己的程序执行结果，我们引入了 C1 语言的运行时，它包含如下全局变量和函数：

int input_ivar;
float input_fvar;
void inputInt();
void inputFloat();
int output_ivar;
float output_fvar;
void outputInt();
void outputFloat();

当执行 inputInt() 时，会将从标准输入设备得到的整数输入赋值给 input_ivar ；当执行 outputInt()时，会将 output_ivar 的值打印到标准的输出设备。

当执行 inputFloat() 时，会将从标准输入设备得到的整数输入赋值给 input_fvar ；当执行 outputFloat()时，会将 output_fvar 的值打印到标准的输出设备。

上述4个变量和4个函数形成了 C1 语言的运行时。运行时在实际投入使用的编程语言和环境中都有出现，例如 glibc，libstdc++，JRE 中 JVM 以外的组件，.NET Core 的 corefx，等等。它们通过某种方式实现，预先定义好并允许程序通过某种方式引用和使用。

在 C1 语言中，不同于 C/C++ 需要使用 #include 引用运行时库的声明，在实验2的软件包中预先给出了产生这些内容定义的代码，参见 runtime.cpp 中的 runtime_info::runtime_info。

2.6 实验代码的编译和运行

实验代码的编译和运行与实验1类似，这里只对不同的部分另作解释：

使用 CMake 创建 Makefile

首先，安装c1recognizer。在 <your repo>/c1recognizer/build 目录下：

  cmake -DCMAKE_INSTALL_PREFIX=/your/install/prefix ..
  make install

然后在<your repo>/c1interpreter 下:

    mkdir build
    cd build
    cmake -DCMAKE_BUILD_TYPE=Debug -DLLVM_DIR=/your/llvm/installation/lib/cmake/llvm -Dc1recognizer_DIR=/your/c1recgonizer/installation/cmake ..

这里通过配置LLVM_DIR和c1recognizer_DIR的值，指定了两个依赖库的寻找路径。请注意替换其中的路径为你的安装位置。

编译

本次的环境较为整洁，直接使用如下命令编译即可：
```
make -j
```
运行

编译后，build 目录下会出现可执行程序 c1i。这一程序的功能是接受单个输入文件，通过使用你实现的 visitor 进行代码生成；生成后，若参数中指定了 -emit-llvm，则将生成的代码打印，否则直接执行之。

例如：

>>> cat test.c1
void main()
{
  output_ivar = 10;
  outputInt();
}
>>> ./c1i -emit-llvm test.c1
; ModuleID = 'test.c1'
source_filename = "test.c1"

@input_ivar = global i32 0
@input_fvar = global double 0.000000e+00
@output_ivar = global i32 0
@output_fvar = global double 0.000000e+00

declare void @inputInt_impl(i32*)

declare void @inputFloat_impl(double*)

declare void @outputInt_impl(i32*)

declare void @outputFloat_impl(double*)

define void @inputInt() {
entry:
  call void @inputInt_impl(i32* @input_ivar)
  ret void
}

define void @inpuFloat() {
entry:
  call void @inputFloat_impl(double* @input_fvar)
  ret void
}

define void @outputInt() {
entry:
  call void @outputInt_impl(i32* @output_ivar)
  ret void
}

define void @outputFloat() {
entry:
  call void @outputFloat_impl(double* @output_fvar)
  ret void
}

define void @main() {
entry:
  store i32 10, i32* @output_ivar
  call void @outputInt()
  ret void
}
>>> ./c1i test.c1
10

这里的执行入口点是main()函数。

2.7 实验提示

本次实验较为复杂，这里给出一些帮助开展实验的提示。

首先，你可以通过 -emit-llvm 参数观察输出的 IR，也可以通过直接执行来观察其行为。

然后，实验进行中，推荐你按以下顺序逐步完善：

构造一个包含所有函数声明的、可以运行的代码生成器

首先你需要快速构造一个可以运行的代码生成器，它包含 c1 程序的所有函数定义（注意,函数体可以认为是空）。你可以参照如下提示来构造：
- 在对 C1程序的处理中（visit(assembly &)），遍历所有 global_def_syntax 类型的成员，依次对其生成。
- 在函数的生成中，创建好函数和最初始的标准块，函数体内的语句暂时视为空。在这里，别忘了对重名函数的报错。
- 在变量定义和语句的生成中，什么也不做。
这样，你能够尽早地完成程序结构的生成。完成后，你应当通过 -emit-llvm 来观察程序输出的 IR 的结构。
补充语句块和函数调用的代码生成
- 语句块的生成：遍历其所有语句，依次生成即可，这很简单。
- 生成函数调用语句，在这里别忘了检查所调用的函数是否已声明。
你可以为 main 函数生成直接调用 output 的代码，以便在测试执行时输出output_var的默认值 0。
补充对表达式以及赋值语句的代码生成
- binop_expr_syntax和unaryop_expr_syntax的代码生成。
- literal_syntax的生成。其实将先前的 0 替换为 syntax tree 中保存的字面值即可。
- lval_syntax的代码生成。这里你可以暂时不考虑类型检查和数组的存在。
- assign_stmt_syntax的代码生成。别忘了设置lval_as_rval的值。
- 在各表达式的处理中，填上根据 constexpr_expected 不同而决定的const_result = 0、value_result = ConstantInt::get(Type::getInt32Ty(context), node.intConst) 或 value_result = ConstantFP::get(Type::getDoubleTy(context), node.floatConst)。
这时代码生成器虽然还没有支持对变量声明的处理，但是可以使用预定义的 output_var 和 input_var 变量，在C1 程序中可以通过 input() 获取一个输入，然后将其通过一系列运算并输出的程序了。进行测试。
变量的声明和类型检查
- var_def_stmt_syntax的代码生成。参见前面的详细介绍。
- lval_syntax中的类型检查和数组的索引操作实现。
至此，你已经可以编写不包含控制结构的程序了。别忘了类型错误的报错。进行测试。
分支结构的处理
- cond_syntax 的代码生成。这应该没有任何难度，和 binop_expr_syntax 的行为是类似的。
- - if_stmt_syntax和while_stmt_syntax的代码生成。这是本次实验的难点，多加思考。
至此，完整的代码生成已经完成。设计样例，详细地测试其各方面功能。一个可能合适的复杂程序是斐波那契数列递归求值，通过全局变量来传递返回值即可。

Lab2