基于Python实现的编译原理实验

1.总述

MP1中完成了cool语言的lexer和parser，除了支持cool的全部语法外，在基本要求之上还可以处理很多其他错误，例如feature和formal的大小写问题、if和while表达式的错误等等。

MP2中完成了cool编译器的后端，可以由AST生成llvm IR指令，实现的是MP2要求中的COOL语言子集，包括int和bool常量、算术和比较运算、let、if、while、赋值和除数为0的运行时错误处理。

2.问题与解决

MP1中的问题与解决请看 mp1/answers.txt 和 mp1/src/README.md

MP2中遇到的问题列举如下：

main中printf使用的格式字符串一开始放在了main函数里，导致出错，改到main前面即可。（放在 CgenClassTable::code_module 函数的 codeGenMainmain 和 code_main 之间。）
想要 [25 x i8]* 类型，用 op_arr_type(INT8,25) 再 get_ptr_type 不行，用 op_arr_type(INT8_PTR,25) 就可以。其中参考了operand和value_printer的具体实现。
程序崩溃，用gdb调试很长时间，发现 ValuePrinter vp 没有给出stream。
if分支语句的实现中发现value_printer不支持phi，所以申请一块栈上的空间用于保存每个分支的结果。
if的false部分执行完毕后不加跳转，直接进入读取结果的部分，导致出错，查了一些资料发现是basic block的要求，所以即便是强制跳转到下一条指令也必须写出来。
写测试程序的时候循环中有if语句，循环次数过多，导致if申请的空间过多，栈溢出。减小循环次数即可。这个问题在不使用phi的情况下还没想出一个好的解决方案。
在test-1中带优化make，会报opt命令的参数错误，可能是由于llvm新版本和旧的参数不兼容。

3.设计实现

MP1的设计实现请看 mp1/answers.txt 和 mp1/src/README.md

MP2的整体思路是对AST递归生成llvm IR，生成llvm IR的代码已经在value_printer中提供了。

由于只需要支持Main类的main函数，所以写一个main函数把Main_main包装起来，调用Main_main后再调用printf将Main_main的返回值输出。

之后就是每种表达式的代码生成。

算术运算和比较运算比较简单，以加法为例：

return vp.add(e1->code(env),e2->code(env));

先递归生成两个操作数的代码，然后生成这两个operand的相加指令即可。

int和bool常量的生成也很简单，以int为例：

return int_value(atoi(token->get_string()));

直接把int的值这个token转换为整数，作为operand返回即可。

block表达式的代码生成就是对每个子表达式生成代码，然后返回最后一个表达式的结果。

对于let表达式，先获取新变量的类型，然后申请对应大小的空间，再计算初始值。如果没有初始值，则使用0（对于int）或者false（对于bool）作为初始值，然后将这个初始值存储到新申请的空间里面去。之后使用 env->add_local 将这个新变量加入符号表，执行let表达式的body，再使用 env->kill_local 恢复原来的符号表。

对于OBJECT表达式（即一个变量），使用 env->lookup 找到其所在的内存地址，然后load即可。

对于赋值表达式，使用 env->lookup 找到其所在的内存地址后计算右值，然后将右值store再地址中。

if和while是最复杂的两种表达式。

对于if，先根据then后面表达式的类型确定整个if表达式的类型，然后为其申请内存空间。然后计算条件部分（pred）的值，根据这个值生成条件跳转语句。之后分别生成true的语句块和false的语句块。这两个语句块执行完毕后都把结果保存进之前申请的内存空间中，并跳转到endif标签处。endif标签会读取之前申请的内存空间中的值并返回。生成标签的部分调用 new_label 函数，每个if使用新的整数后缀以保证标签不重复。

拿 if 1<2 then 3 else 4 fi 举例，其llvm IR汇编代码如下：

```assembly %vtpm.0 = icmp slt i32 1, 2 %vtpm.1 = alloca i32 br i1 %vtpm.0, label %true0, label %false0

true0: store i32 3, i32* %vtpm.1 br label %endif0

false0: store i32 4, i32* %vtpm.1 br label %endif0

endif0: %vtpm.2 = load i32, i32* %vtpm.1 ret i32 %vtpm.2 ```

while语句与if语句较为类似，区别在于不用申请空间，而且跳转的标签不一样。while语句生成的结构大致是：先跳转到pred_label，即循环的开始，这里计算循环条件，如果条件满足则跳转至循环体body_label，否则调到循环结束endloop_label。循环体执行后跳回循环的最开始pred_label，判断循环条件，进行下一轮循环。循环结束处返回0（MP2的要求）。

以 while 1<2 loop 1+1 pool; 为例，其llvm IR汇编代码如下：

```assembly br label %pred0

pred0: %vtpm.0 = icmp slt i32 1, 2 br i1 %vtpm.0, label %body0, label %endloop0

body0: %vtpm.1 = add i32 1, 1 br label %pred0

endloop0: ret i32 0 ```

除此之外，还有一个除数为0的运行时错误处理。在除法运算中，计算两个操作数之后，插入比较语句来比较除数和0的关系，如果相等则调用abort函数终止程序执行，如果不等则正常进行除法。此处的跳转逻辑相当于之前的if语句。

在 mp2/test-1 中，写了很多测试文件，对每种类型的表达式进行了全面的测试，而且还有一个综合测试程序 prime.cl ，程序执行结果都与预期一致。

4. 除了这些缺陷以外, clang静态分析器还有哪些缺陷?

正如官网中这个网页所提到的，clang静态分析器还有很多缺陷。

没有对系统库的很多类建模

例如下面的代码

```c++ #include

using namespace std;

void foo(string a) { int *pi = 0; if (a.size()>2) pi = new int; if (a.size()>1) delete pi; }

void foo2(int a) { int *pi = 0; if (a>2) pi = new int; if (a>1) delete pi; } ```

NewDeleteLeaks 这个checker会对 foo 报 Potential leak of memory pointed to by 'pi' 警告，但是不会对 foo2 报错，就说明checker对 string::size() 的定义一无所知。

new 和 delete 无法跟踪到构造函数和析构函数

```c++ class C{ int *p; public: C(){p=new int();} ~C(){} };

void foo() { C c=new C(); delete c; int p = new int(); } ```

以上代码只有 int *p = new int(); 这里一处报告泄露，因为 new 和 delete 无法跟踪到C的构造函数和析构函数，C内的内存泄露不会被发现。

无法分析异常处理

```c++ #include

void foo() { int *p = new int(); std::string("abc").substr(10); // throws std::length_error delete p; }

int main(){ try{ foo(); }catch(...){ return 0; } return 0; } ```

抛出异常后 delete p; 不会执行，会产生内存泄漏，但checker没有报错。

当然除此之外还会有很多其他的缺陷，在此就不一一例举了。

以动态内存、或文件等资源有关的缺陷检查为例，对clang 静态分析器进行如下使用和分析工作：

1. 是否能检查该类缺陷?

我选择的是 alpha.unix.Stream 这个checker。这个checker的主要目的是跟踪使用 fopen 打开的文件的状态，它可以报告很多问题，例如：

调用 fopen 后未检查返回值是否是NULL就使用文件

c void f(){ FILE *p=fopen("test","w"); ftell(p); //Stream pointer might be NULL fclose(p); }

调用文件相关API的参数类型有误（例如 fseek 的第三个参数）

c void f2(){ FILE *p=fopen("test","w"); fseek(p,1,3); //The whence argument to fseek() should be SEEK_SET, SEEK_END, or SEEK_CUR fclose(p); }

文件被关闭多次

c void f3(){ FILE *p=fopen("test","w"); fclose(p); fclose(p); //Try to close a file Descriptor already closed. Cause undefined behaviour }

打开的文件没有被关闭

c void f4(){ FILE *p=fopen("test","w"); } //Opened File never closed. Potential Resource leak

使用 clang --analyze -Xanalyzer -analyzer-checker=alpha.unix.Stream streamtest.c 可以检测出以上所有错误。

2. 检查能力到什么程度（程序存在哪些特征时检查不出来）?

只支持部分文件相关函数。经测试， fprintf 、 fscanf 等函数就不支持。

c void f(){ FILE *p=fopen("test","w"); fprintf(p,"test"); fclose(p); }

这段代码就不会报 Stream pointer might be NULL 警告。

c int foo(){ FILE *f=fopen("test","r"); if(f){ fcloseall(); fclose(f); }}

fcloseall 函数也不支持。以上代码中 f 显然被关闭了两次，但不会报warning。

fclose 的参数可能为NULL或一定为NULL时不会报错。

c void foo(){ FILE *p=fopen("test1","r"); fclose(p);}void foo2(){ fclose(NULL);}

这两个函数都不会报错。

存在escape时有可能误报

c void do_something();void escape1(){ FILE *f=fopen("test","r"); do_something(f);}

这段代码中checker看不到 do_something 的定义，checker默认为 do_something 不会关闭文件，所以报leak。（而与之前的SimpleStreamChecker不同，SimpleStreamChecker不会报leak。）如果 do_something 中关闭了文件则是误报。

FILE *global_f;void escape2(){ FILE *f=fopen("test","r"); global_f=f;}

这段代码中 f 传给了全局变量，所以没有报leak，即使全局变量 global_f 从未被关闭。

3. 检查的实现机制是什么？列出相关的源码位置和主要处理流程

调用 fopen 后未检查返回值是否是NULL就使用文件

处理 fopen 、 tmpfile 等打开文件的函数时，会调用211行的 StreamChecker::OpenFileAux 方法，其中会为 fopen 的返回值绑定状态。绑定的状态分为两种： Opened 和 OpenFailed ，这会使得ExplodedGraph产生两个分支，分别代表文件打开成功和失败，对应于 fopen 的值是否为NULL。

调用 ftell 等函数使用文件指针时，checker会调用341行的 StreamChecker::CheckNullStream 方法。其中会根据函数指针那个参数分为两种情况做处理。如果函数指针是NULL，则报 Stream pointer might be NULL 错误。

调用文件相关API的参数类型有误

以 fseek 为例，在第258行 StreamChecker::Fseek 中，对第2（从0开始计数）个参数做出判断，如果参数不是在0~2范围内则报错 Illegal whence argument

文件被关闭多次

处理 fclose 时，会调用364行的 StreamChecker::CheckDoubleClose 方法。这里会检查，如果文件指针已经是 Closed 状态，则报 Try to close a file Descriptor already 错误。否则会把文件指针置为 Closed 状态。

打开的文件没有被关闭

当局部变量超出作用域等产生DeadSymbols的情况发生时，397行的 StreamChecker::checkDeadSymbols 会被调用。这里会循环遍历所有的DeadSymbols，如果仍然是 Opened 状态，则报错 Opened File never closed. Potential Resource leak 。

4. （可选）从实现机制上分析，为什么检查不出来上述问题2的解答中所列的特征？

有些文件相关函数不支持的问题：checker中未对这些函数进行处理。
fclose 的参数可能为NULL或一定为NULL时不会报错：处理 fclose 的函数根本没判断 fclose 的参数是否可能为NULL。
存在escape时有可能误报：传给不知道定义的函数时，无法得知这个函数中是否可能将文件关闭。一般情况下函数不会这么做，所以默认是函数不会关闭。传给全局变量的情况中，无法得知函数返回后全局变量会被如何使用，所以无法判断。

5. （可选）如果想增强检查能力，可以怎么做？

存在escape的情况很难处理，因为有很多信息checker无法得知，也就无法判断。
不支持某些文件操作函数和 fclose 的参数为NULL的情况可以通过简单的修改以增强检查能力。我们可以将 fprintf 和 fscanf 等函数也加入checker检查的函数调用中，同时在 fclose 的处理中检查参数是否为NULL。

我对这个checker进行了一些修改，可以增强其检查能力。修改后的checker放在了 sa/StreamChecker.cpp 。修改后的checker可以处理 fprintf 函数和 fclose 的参数为NULL的情况。

测试代码如下：

c #include<stdio.h>void foo(){ FILE *p=fopen("test1","r"); fclose(p);}void foo2(){ fclose(NULL);}void foo(){ FILE *p=fopen("test","w"); fprintf(p,"test"); fclose(p);}

现在这三个函数都可以报 warning: Stream pointer might be NULL ，而之前的checker遇到这些情况不会报warning。

对这个checker的修改可以由diff得出：

python $ diff StreamChecker.cpp StreamChecker.cpp.old 64 c64 < * II_clearerr, * II_feof, * II_ferror, * II_fileno, * II_fprintf; -- - > * II_clearerr, * II_feof, * II_ferror, * II_fileno; 74 c74 < II_ferror(nullptr), II_fileno(nullptr), II_fprintf(nullptr) {}-- - > II_ferror(nullptr), II_fileno(nullptr) {} 94 d93 < void Fprintf(CheckerContext & C, const CallExpr * CE) const; 143, 144 d141 < if(!II_fprintf) < II_fprintf = & Ctx.Idents.get("fprintf"); 202, 205 d198 < if(FD - > getIdentifier() == II_fprintf) { < Fprintf(C, CE); < return true; < } 246, 250 c239 < ProgramStateRef state = C.getState(); < if(!CheckNullStream(state - > getSVal(CE - > getArg(0), C.getLocationContext()), < state, C)) < return; < state = CheckDoubleClose(CE, state, C); -- - > ProgramStateRef state = CheckDoubleClose(CE, C.getState(), C); 346, 352 d334 < ProgramStateRef state = C.getState(); < if(!CheckNullStream(state - > getSVal(CE - > getArg(0), C.getLocationContext()), < state, C)) < return; < } < < void StreamChecker::Fprintf(CheckerContext & C, const CallExpr * CE) const {

可以看出新增了对 printf 和 fclose 时文件指针为NULL的处理。

5.参考资料

http://llvm.org/docs/Passes.html#mem2reg-promote-memory-to-register
http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html
http://llvm.org/docs/tutorial/LangImpl05.html#llvm-ir-for-if-then-else
http://releases.llvm.org/3.9.0/docs/LangRef.html
https://github.com/invictusjs/cool-llvm/tree/master/codegen/test-1
https://github.com/CharlieMartell/Compiler-Construction/blob/master/mps/mp3/src/cgen.cc
https://github.com/invictusjs/cool-llvm/blob/master/codegen/src/cgen.cc